Quantum Computers: A kriptográfia vége?

Hirdetés

A kvantumszámítás egyike azoknak a technológiáknak, amelyek annyira ígéretesek, hogy a TV-karakterek elnevezik, amikor okosnak akarnak hangzni.

A kvantumszámítás mint ötlet már egy ideje fennáll - az elméleti lehetőséget eredetileg Jurij Manin és Richard Feynman 1982-ben vezette be. Az utóbbi néhány évben azonban a terület aggasztóan közeledett a praktikussághoz.

Az olyan vállalatok, mint a Google és a Microsoft, valamint az olyan kormányzati ügynökségek, mint az NSA, már évek óta lázasan üldözik a kvantumszámítógépeket. A D-Wave nevű vállalat olyan eszközöket gyártott és értékesített, amelyek (bár nem megfelelő számítógépek, és képesek csak néhány algoritmust végezzen el) kvantumtulajdonságok kiaknázása, és egy újabb növekményes lépés az a felé vezető úton teljesen Turing-teljes Mi az a Turing-teszt, és vajon lesz-e soha?A Turing-teszt célja annak meghatározása, hogy a gépek gondolkodnak-e. Az Eugene Goostman program valóban megfelel-e a Turing-tesztnek, vagy csak az alkotók csaltak? Olvass tovább kvantumgép.

Nem tűnik ésszerűtlennek mondani, hogy olyan áttörések történhetnek, amelyek lehetővé teszik az első nagyméretű kvantumszámítógép építését egy évtized alatt.

Akkor miért érdekli az összes érdeklődés? Miért érdekelne? A számítógépek folyamatosan gyorsabbak Mi a Moore törvénye, és mi köze van hozzád? [MakeUseOf magyarázat]A szerencsének nincs köze Moore törvényéhez. Ha ez az egyesület volt, akkor összekeverjük Murphy törvényével. Azonban nem voltál messze, mert Moore törvénye és Murphy törvénye ... Olvass tovább - Mi olyan különleges a kvantumszámítógépeknél?

Annak magyarázata érdekében, hogy miért olyan fontosak ezek a gépek, vissza kell lépnünk és pontosan meg kell vizsgálnunk, hogy mi a kvantumszámítógép, és miért működnek. Először beszéljünk egy „futásidejű komplexitás” elnevezésű koncepcióról.

Mi a futásidejű komplexitás?

Az egyik nagy meglepetés a számítástechnika kezdeti napjaiban az volt a felfedezés, hogy ha van számítógépe, amely megoldja a egy bizonyos méret egy bizonyos idő alatt, a számítógép sebességének megduplázása nem feltétlenül teszi lehetővé a problémák kétszeres megoldását nagy.

Néhány algoritmus nagyon gyorsan növekszik a teljes végrehajtási időben, a probléma méretének növekedésével - néhány algoritmus gyorsan befejezhető adott 100 adatpontot, de az algoritmus befejezéséhez 1000 adatpontot igényelne egy számítógép, amelynek a Föld mérete egy milliárd dollárral működik évek. A futásidejű komplexitás ennek az ötletnek a formalizálása: megvizsgálja a probléma bonyolultságának növekedésének görbéjét, és az adott görbe alakját használja az algoritmus osztályozásához.

Általában ezeket a nehézségi osztályokat funkciókkal fejezik ki. Egy olyan algoritmust, amely arányosan nehezebbé válik, amikor az adatkészlet megnöveli a működését (mint egy egyszerű számlálási függvény), úgy kell mondani, hogy egy olyan futásiidejű komplexitású funkció, amely „n” (mint itt, ez is tart n a feldolgozáshoz szükséges időegységek n adat pontok).

Alternatív megoldásként „lineárisnak” is lehet nevezni, mert ha ábrázolja, akkor egyenest kap. Lehet, hogy más funkciók is n ^ 2 vagy 2 ^ n vagy n! (n tényező). Ezek polinomiális és exponenciálisak. Az utóbbi két esetben az exponenciálisok olyan gyorsan növekednek, hogy szinte minden esetben semmi esetre sem oldhatók meg, kivéve a nagyon triviális példákat.

Futásidejű komplexitás és kriptográfia

Ha először hallja ezt a cuccot, és értelmetlennek és okosnak hangzik, próbáljuk meg megalapozni ezt a vitát. A futásidejű komplexitás kritikus a kriptográfia szempontjából, amely abban rejlik, hogy a titkos kulcs ismeretében sokkal könnyebbé válik a dekódolás, mint azoknak, akik nem. Ideális kriptográfiai séma szerint a dekódolásnak lineárisnak kell lennie, ha van kulcs, és 2 ^ k (ahol k a kulcs bitjeinek száma), ha nem.

Más szavakkal, az üzenet kulcs nélküli dekódolásának legjobb algoritmusának egyszerűen a lehetséges kulcsok kitalálására kell törekednie, ami mindössze néhány száz bit hosszú kulcsok számára megoldhatatlan.

A szimmetrikus kulcsos rejtjelezéshez (amelyben a két félnek lehetősége van titokban biztonságosan kicserélni a kommunikáció megkezdése elõtt) ez elég egyszerû. Az aszimmetrikus kriptográfia esetében ez nehezebb.

Az aszimmetrikus kriptográfia, amelyben a titkosítási és a visszafejtési kulcsok különböznek egymástól, és amelyek nem könnyen kiszámíthatók, sokkal nehezebb matematikai a szimmetrikus kriptográfia mellett megvalósítható szerkezet, de sokkal erősebb is: az aszimmetrikus kriptográfia magánbeszélgetéseket tesz lehetővé, még megérintve is sorokat! Ezenkívül lehetővé teszi „digitális aláírások” létrehozását, amelyek lehetővé teszik annak ellenőrzését, hogy ki jött az üzenetből, és hogy azt nem hamisították-e meg.

Ezek nagy teljesítményű eszközök, amelyek alkotják a modern adatvédelem alapját: aszimmetrikus kriptográfia nélkül az elektronikus eszközök felhasználóinak nem lenne megbízható védelme a kíváncsiságú szemmel szemben.

Mivel az aszimmetrikus kriptográfia nehezebb építeni, mint a szimmetrikus, a mai szokásos titkosítási sémák nem olyan erősek ahogy lehetnek: a leggyakoribb titkosítási szabvány, az RSA, feltörhető, ha hatékonyan megtalálja a nagyon nagy szám. A jó hír az, hogy ez egy nagyon nehéz probléma.

A legismertebb algoritmust, amely nagy számoknak az alkotóelemeikbe történı faktorozását nevezi, az általános számmező-szitának nevezi, és futásiidejének bonyolultsága kissé lassabban növekszik, mint 2 ^ n. Következésképpen a kulcsoknak körülbelül tízszer hosszabbaknak kell lenniük ahhoz, hogy hasonló biztonságot biztosítsanak, amit az emberek általában tolerálnak, mint az üzleti tevékenység költségeit. A rossz hír az, hogy a teljes játékteret megváltozik, amikor a kvantumszámítógépeket beledobják a keverékbe.

Quantum Computers: A titkosító játék megváltoztatása

A kvantum számítógépek azért működnek, mert egyszerre több belső állapotuk is lehet, a „szuperpozíció” elnevezésű kvantum-jelenség révén. Ez azt jelenti, hogy egyszerre megtámadhatják a probléma különböző részeit, megosztva a világegyetem lehetséges verziói között. Úgy is konfigurálhatják, hogy a problémát megoldó ágak a legnagyobb amplitúdóval felcsavaródjanak, így amikor benyitja a dobozt Schrodinger macska, a belső állapot azon változata, amelyet valószínűleg bemutatni fog, egy önelégült macska, amelynek dekódolása van üzenet.

A kvantum számítógépekkel kapcsolatos további információkért lásd: a közelmúltban megjelent cikkünk Hogyan működnek az optikai és a kvantum számítógépek?Közeledik az Exascale kor. Tudja, hogyan működnek az optikai és kvantumszámítógépek, és ezek az új technológiák válnak-e jövőnkként? Olvass tovább !

Ennek előnye, hogy a kvantumszámítógépek nemcsak lineárisan gyorsabbak, a normál számítógépek módja is: kettő, tíz, vagy száz a gyorsabb elérés nem sok segítséget jelent a hagyományos kriptográfia esetében, amelynek több milliárdszor túl lassú a feldolgozása. A kvantumszámítógépek támogatják azokat az algoritmusokat, amelyeknek a növekvő futási ideje bonyolultabb, mint az egyébként lehetséges. Ez az, ami alapvetően különbözik a kvantumszámítógépeket a többi jövőbeli számítási technológiától, például grafén és memrisz számítása A legújabb számítógépes technológia, amelyet látnia kell, hogy elhiggyeNézze meg a legújabb számítógépes technológiákat, amelyek az elektronika és a PC-k világát átalakítják az elkövetkező néhány évben. Olvass tovább .

Konkrét példaként a Shor algoritmusa, amelyet csak kvantumszámítógépen lehet végrehajtani, nagy számokra képes napló (n) ^ 3 idő, ami drasztikusan jobb, mint a legjobb klasszikus támadás. Az általános számmező-szita 2048 bittel rendelkező számának tényezőjéhez való felhasználása körülbelül 10 ^ 41 időegységet vesz igénybe, ami több mint trillió trillió billió eredményt eredményez. Shor algoritmusával ugyanaz a probléma csak körülbelül 1000 egység időt vesz igénybe.

Minél hosszabb ideig vannak a gombok, annál erősebb a hatás. Ez a kvantumszámítógépek hatalma.

Ne tévessze meg téged - a kvantumszámítógépeknek sok lehetséges, nem gonosz felhasználása van. A kvantumszámítógépek hatékonyan meg tudják oldani az utazó eladó problémáját, lehetővé téve a kutatók számára, hogy hatékonyabb szállítási hálózatokat építsenek ki és jobb áramköröket tervezzenek. A kvantumszámítógépeknek már nagy teljesítményük van a mesterséges intelligencia területén.

A kriptográfiaban betöltött szerepük katasztrófa lesz. Azok a titkosítási technológiák, amelyek lehetővé teszik világunk működésének megőrzését, attól függnek, hogy az egész tényező-problémát nehéz-e megoldani. Az RSA és a kapcsolódó titkosítási sémák lehetővé teszik, hogy bízzon abban, hogy a megfelelő webhelyen van, azaz a fájlok a letöltés nem tele van rosszindulatú programmal, és hogy az emberek nem kémkednek az internetes böngészés során (ha Tor).

A kriptográfia biztonságban tartja bankszámláját és biztosítja a világ nukleáris infrastruktúráját. Amikor a kvantumszámítógépek praktikussá válnak, az egész technológia nem működik. Az első szervezet, amely kvantumszámítógépet fejlesztett, ha a világ továbbra is azon a technológián működik, amelyet ma használunk, ijesztően erős helyzetbe kerül.

Tehát elkerülhetetlen a kvantum apokalipszis? Mit tehetünk vele? Mint kiderül... igen.

Post-kvantum kriptográfia

A titkosítási algoritmusoknak számos olyan osztálya van, amelyeket tudomásunk szerint kvantumszámítógépen nem szignifikánsan gyorsabban lehet megoldani. Ezeket együttesen posztkvantum-kriptográfiának nevezzük, és reményt adnak arra, hogy a világ át tud térni olyan kriptoszisztémákra, amelyek biztonságban maradnak a kvantum-titkosítás világában.

Az ígéretes jelöltek közé tartozik a rács-alapú titkosítás, például a Ring-Learning With Error, amely biztonságát bizonyíthatóan összetett gépi tanulási probléma és többváltozós kriptográfia, amely biztonságát az okozza, hogy nehéz megoldani a nagyon nagy, egyszerű rendszereket egyenletek. A témáról bővebben a Wikipedia cikk. Óvakodj: ezeknek a dolgoknak a többsége bonyolult, és előfordulhat, hogy a matematikai hátteret jelentős mértékben fel kell gyorsítani, mielőtt valóban belemerülne a részletekbe.

Ennek sok eleme az, hogy a kvantum utáni kriptozémémák nagyon hűvösek, de nagyon fiatalok is. Több munkára van szükségük ahhoz, hogy hatékonyak és praktikusak legyenek, és bizonyítsák biztonságát. A kriptoszisztémákba bízhatunk azért, mert elég hosszú ideig dobtunk rájuk klinikailag paranoid géneket hogy minden nyilvánvaló hiányosságot mára felfedeztek, és a kutatók különféle tulajdonságokat bizonyítottak, amelyek ezeket teszik erős.

A modern kriptográfia a fénytől, mint fertőtlenítőszertől függ, és a legtöbb kvantum utáni kriptográfiai rendszer egyszerűen túl új ahhoz, hogy bízhasson a világ biztonságában. Ugyanakkor odaérnek, és egy kis szerencsével és némi előkészítéssel a biztonsági szakértők befejezhetik a kapcsolót, még mielőtt az első kvantumszámítógép online lesz.

Ha azonban kudarcot vallnak, a következmények súlyosak lehetnek. Az a gondolat, hogy bárki rendelkezik ilyen hatalommal, megdöbbentő, még akkor is, ha optimista vagy a szándékukkal kapcsolatban. Az a kérdés, hogy ki először fejleszti ki a működő kvantumszámítógépet, azt mindenkinek nagyon óvatosan figyelnie kell, ahogy a következő évtizedbe lépünk.

Aggódik a kriptográfia bizonytalansága a kvantumszámítógépekkel szemben? Mit veszsz? Ossza meg gondolatait az alábbi megjegyzésekben!

Kép kreditek: Bináris gömb Via Shutterstock útján