» »

NSA in GCHQ se pripravljata na kvantno lomljenje šifrirnih algoritmov

NSA in GCHQ se pripravljata na kvantno lomljenje šifrirnih algoritmov

Slo-Tech - Moderni šifrirni algoritmi se naslanjajo na dejstvo, da poznamo vrsto matematičnih problemov, ki so v eno smer enostavno izračunljivi, v obratno pa toliko težje, da jih v celotni dosedanji zgodovini vesolja ne bi bili mogli. Analogija je množenje dveh velikih praštevil, kar je z današnjo tehnologijo trivialen problem, medtem ko je faktorizacija psevdopraštevil bistveno težji problem. Ob primerni implementaciji so današnji šifrirni algoritmi inherentno varni, četudi bo računska moč napredovala. Razen če dobimo dejansko uporabne kvantne računalnike, ki bodo predvidoma sposobni zlomiti asimetrične algoritme, kot so DSA, Diffie Hellman ali RSA.

Kvantni računalniki niso več zgolj teoretične zamisli, temveč imamo primitivne prototipe že tu. Google razvija svojega, NSA želi svojega, za trenutne komercialne izvedenke pa nismo niti prepričani, kako delujejo. Pravi kvantni računalniki izkoriščajo kvantno prepletenost kubitov, zaradi česar lahko algoritem poganjajo na vseh možnih vrednostih spremenljivk hkrati. Kvantni računalnik ni a priori hitrejši od klasičnega. Tak je le, če za problem obstaja kvantni algoritem - tak primer je Shorov algoritem za faktorizacijo števil.

Zato so nekateri šifrirni algoritmi ranljivi, drugi pa ne. RSA in ostali, ki se zanašajo na neizvedljivost faktorizacije, so trivialno zlomljivi s Shorovim algoritmom. DSA, Diffie-Hellman in ostali, ki izkoriščajo težavnost izračuna diskretnega logaritma, so prav tako ranljivi. Simetrični algoritmi so po drugi strani nekoliko ranljivi, a ne nujno za odpis. Kvantni računalnik se skozi prostor 22n prebije v času 2n, torej bo zanj 128-bitni AES enako težaven, kot je 64-bitni AES za klasični računalnik. Podobno velja tudi za zgoščevalne funkcije (npr. SHA-256).

Doslej so s Shorovim algoritmov uspeli faktorizirati število 21, z drugim algoritmom (AQC) pa 143 in 56153, kar se ne sliši ravno impresivno in za varnost šifriranja ne predstavlja nobene grožnje. A kakor si nihče ni znal pred 50 leti predstavljati, česa bodo zmožni današnji računalniki, tako se NSA že danes boji, česa bodo zmožni računalniki čez 50 let. Če bodo kvantni računalnik realnost, bo današnje šifriranje tako neuporabno, kot je danes Cezarjeva šifra.

NSA se zato pospešeno pripravlja na to možnost in razvija algoritme, ki bodo na kvantne računalnike odporni. Trenutno je priporočen nekvantni nabor znan pod oznako Suite B, pripravljajo pa tako imenovane kvantno odporne algoritme (quantum resistant algorithms), o katerih bomo v prihodnosti gotovo še dosti slišali. Vse institucionalne uporabnike, ki še niso prešli na algoritme iz Suite B, pozivajo, naj ne hitijo s prehodom na Suite B. Namesto tega naj počakajo na naslednji Suite, ki bo kvantno odporen. Tudi britanska agencija GCHQ je pred kratkim v članku prepoznala realnost v tako imenovanem post-kvantnem svetu.

Skupaj s spremembo smernic za razvoj šifrirnih algoritmov je to pomenljivo sporočilo, saj kaže, da so znanstveniki razvoj kvantnih računalnikov prepoznali kot realno možnost. Z razvojem novih algoritmov lahko pričakujemo, da bodo sčasoma začeli kapljati tudi v programsko opremo, ki je namenjena poslovnim in kasneje domačim uporabnikom.

12 komentarjev

ales85 ::

Na koncu nam ostane še to, da zaupamo, da bodo ti algoritmi, če bodo dani v standarde oziroma javnosti, lahko preverljivi za javnost, da se lahko na njih zanese. V nasprotnem primeru bomo pač imeli super novi algoritem, ki bo zaradi novih stranskih lukenj bolj ranljiv kot obstoječi. Še vedno pa lahko kombiniramo staro in novo (seveda na račun performans).

Isotropic ::

dvomim. verjetno bo nsa pač nekaj časa imela secret algoritme, kot je imela diferencialno kriptografijo ~20-30 let, preden so jo odkrili in javno objavili drugi researcherji.

Zgodovina sprememb…

LightBit ::

Se že tresem.

matijadmin ::

Kar nekaj je odprtih algoritmov, ki so v teoriji odporni na tovrstno lomljenje. Problem so patenti, nihče ne želi nanje vezati svojega razvoja (tudi v skladu s pogoji brezplačne uproabe), pa malenkost počasnejši so.
Vrnite nam techno!

WhiteAngel ::

Hmnja, malce sem skeptičen glede kvantnih računalnikov. Ne pozabit, da je 2^256 in tako dalje, zelo velika številka, če moraš vsako od njenih vrednosti preveriti. Tudi za čez 50 let.

vostok_1 ::

Zanimivo da je AES prav tako dovzeten. Sem mislu da so simetrični algoritmi bolj kvantno odporni...še posebej tist, ki niso stream cipher. Not good.

poweroff ::

V resnici je največje število, ki so ga uspeli (namerno) faktorizirati s kvantnimi algoritmi 143 in ne 21.

"Ponesreči" pa so uspeli faktorizirati še števila 3599, 11663 ter 56153.
sudo poweroff

one too many ::

Matthai ravno v tej povezavi trdijo, kar trdi tudi novica, da so s Schorovim algoritmom eksperimentalno faktorizirali 21. Faktorizacijo 143 pa so dosegli z drugim pristopom (če pravilno razumem, gre za kvantno simulirano ohlajanje).

Na KSO temelji tudi kvantni računalnik D-wave na sliki, za katerega pa še ni jasno, ali računa kaj hitreje kot klasični računalniki.

LightBit ::

vostok_1 je izjavil:

Zanimivo da je AES prav tako dovzeten. Sem mislu da so simetrični algoritmi bolj kvantno odporni...še posebej tist, ki niso stream cipher. Not good.

AES 256 bi bil v primeru obstoja učinkovitega kvantnega računalnika varen toliko kot je sedaj AES 128 (če ne upoštevamo related-key napadov na AES), kar je še vedno dovolj.

Yacked2 ::

LightBit je izjavil:

vostok_1 je izjavil:

Zanimivo da je AES prav tako dovzeten. Sem mislu da so simetrični algoritmi bolj kvantno odporni...še posebej tist, ki niso stream cipher. Not good.

AES 256 bi bil v primeru obstoja učinkovitega kvantnega računalnika varen toliko kot je sedaj AES 128 (če ne upoštevamo related-key napadov na AES), kar je še vedno dovolj.


Damo pa višjo potenco od 32 pa je :)
Korak naprej ni vedno ustrezen...sploh če si na robu prepada!

McHusch ::

poweroff je izjavil:

V resnici je največje število, ki so ga uspeli (namerno) faktorizirati s kvantnimi algoritmi 143 in ne 21.

"Ponesreči" pa so uspeli faktorizirati še števila 3599, 11663 ter 56153.


U hvala, popravljeno. To je skoraj cel velikostni razred razlike :-)

LightBit ::

Yacked2 je izjavil:

Damo pa višjo potenco od 32 pa je :)

?


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

IBM-ov petkubitni kvantni računalnik na voljo javnosti!

Oddelek: Novice / Znanost in tehnologija
279778 (7168) nekikr
»

NSA in GCHQ se pripravljata na kvantno lomljenje šifrirnih algoritmov

Oddelek: Novice / Varnost
128562 (6123) LightBit
»

NSA želi kvantni računalnik

Oddelek: Novice / Zasebnost
2914902 (11489) Fave
»

Januarski poizkus dokaza problema P = NP neuspešen

Oddelek: Novice / Znanost in tehnologija
64256 (2792) Thomas
»

Kako so ugotovili, da je 2<sup>13466917</sup>-1 praštevilo. (strani: 1 2 )

Oddelek: Znanost in tehnologija
529446 (7949) larpo

Več podobnih tem