Cracare RSA (sau alți algoritmi) manual de către un înțelept

Puterea criptografiei RSA vine din duritatea (sau așa credem noi) factorizării numerelor mari. Pentru lungimi de cheie de peste 2048 de biți, este imposibil ca computerele actuale sau viitoare să factorizeze acele numere într-un timp rezonabil.

Dar ce zici de creierul uman? Sunt oameni cu abilități remarcabile la matematică; de exemplu, savanti care pot efectua multe calcule complexe. Imaginați-vă o persoană care este fixată pe factorizarea numerelor compuse. Poate că abilitățile lui sau ei ar putea fi sporite de droguri.

Este aceasta o preocupare reală atunci când proiectați cifruri criptografice? Ar putea o organizație diabolică să angajeze pe unul dintre acești oameni pentru a sparge chei criptografice (pentru orice cifru modern)? Poate există vreun exemplu din viața reală?

Gândirea ta este împotriva bunului simț în criptografie și computere. Și să fiu sincer, este o pseudoștiință flagrantă.

Creierul uman și neuronii din interior operează pe stări scalare. Deși este discutabil dacă procesul creierului este determinist sau probabilist, acesta nu are capacitatea de a crea suprapoziții de stări așa cum ar putea face computerele cuantice. Astfel, nu are niciun avantaj față de supercalculatoarele clasice în factorizarea întregilor sau logaritmul discret (algoritmul lui Shor), și nici nu are niciun avantaj la căutarea prin baze de date nesortate (algoritmul lui Grover).

Pentru creierul uman, este prea ușor să ignori adâncimea 2048+ biți figura. Să facem un exercițiu de estimare inginerească pentru a ilustra.

Postarea inițială a lui @derjack măsoară aproape 700 de caractere. Iată un număr de 2048 de biți, scris cu 617 cifre zecimale (aproape la fel de lung ca întrebarea):

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448280710318450446268407511633591722075539194702809692695116208601753153385228164358637425253452063124531982403270024154882788029124087013649227429510942494747262878176328960795460204004486651813356499189783184670257748061985168288109350852763136493356212118910302261417784227884243069534873234110239729827362916848850208533176280055919120540762635115410724871087269605319201076899957787049604743491139956908133927452563472712188255099007744935013999050172650250829825

Puteți să mă credeți pe cuvânt că este un număr compus (adică nu prim).

Puteți, de asemenea, să aruncați o privire mai atentă și să observați că ultima cifră este 5 și prin urmare, 5 este un divizor. Dar pur și simplu ca o provocare, puteți găsi factorii mai mari?

Să stabilim o limită inferioară a timpului în care un om existent ar putea sparge acest lucru. Referințele mele sunt neplăcute aici¹, dar pare plauzibil de luat 3850 de cuvinte pe minut ca limită superioară a vitezei de citire umană. Convertit, are 302 de caractere pe secundă (cu lungimea medie a cuvintelor de 4,7 în engleză²). De asemenea, voi extrapola această cifră la numere lungi; asa ca ajungem la stadionul de 300 de cifre pe secundă viteza de citire.

>>> 617 / 301.6
2.045755968169761

The cel mai rapid cititor uman din lume va avea nevoie nu mai puțin mai mult de 2045 milisecunde doar pentru a încărca numărul în memoria lor. Pentru cititorii mai obișnuiți, ca mine și tine, există un factor de 17¹; asa de doar citind numărul va dura 35 de secunde nu mai puțin.Observați că pentru estimarea limita inferioară pe care o facem aici, trebuie să presupunem infinit performanța întregului-FLOPS a creierului. Cele 35 de secunde ar fi IO-ul înainte de calcul.

¹: https://www.brainread.com/en/the-fastest-reader-in-the-world/

²: https://norvig.com/mayzner.html

Acum, vă recomand să repetați singuri exercițiul, de ex. pentru 4096 de biți. Nu sunt de două ori mai multe! Nivel de abstractizare greșit, dacă așa credeți. 4096-bit numbers are on average 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than 2048-bit numbers, in absolute value.

Exercițiul vă poate ajuta să realizați cât de ușor este să auzi ceva despre calculele „N-biți” și să-ți imaginezi că ai înțeles ceva. Asta e cale mai greu decât pare... dacă faci calculul.

Orice ființă umană care poate factoriza numerele de 2048 de biți în capul său mai repede decât un computer este aproape sigur o ființă umană care, de fapt, a descoperit un nou algoritm de factorizare a numerelor. Care, dacă ar fi implementat pe un computer, ar fi și mai rapid.

Dar asta nu exclude acest lucru.

O să fiu puțin mai puțin decât total precis mai jos. De exemplu, voi amesteca problemele de decizie și algoritmii pentru a menține termenii simpli.

Nu știm cât de greu este factorizarea numerelor. Știm că este într-o clasă de complexitate BQP, care pentru computerele clasice (sau un om care rulează un algoritm clasic în cap) în NP.

O problemă este în NP dacă este relativ ieftin verifica ai primit raspunsul corect. Exemplul de aici este că, dacă cineva afirmă că factorii unui număr sunt A și B, îl puteți verifica prin... calculând A*B și văzând dacă se potrivește.

Dar nu există nicio dovadă că NP nu este același cu P. Dacă NP=P, atunci fiecare problemă a cărei soluție poate fi verificat rapid poate fi rezolvat rapid. (Acest lucru este foarte ondulat, dar este adevărat în aceste limite). Și dacă NP=P, atunci BQP care este în NP este și în P.

Pentru problemele din NP, nu cunoaștem niciun algoritm clasic care să fie mult mai rapid decât „încercați orice posibilitate” aici pentru definiții generoase ale „atât de mult”. (cei mai rapidi algoritmi de factoring sunt strict sub-exponențiali; ca O(e^(k + biți^(1/3)*ln(biți)^(2/3)) dacă am copiat corect).

Așadar, dacă cineva a venit cu un algoritm pentru a factoriza numerele mari, care este timpul polinomial, ar putea, teoretic, să învețe cum să ruleze algoritmul în capul său și să fie capabil să factorizeze numere mari compuse mai rapid decât poate orice computer.

Acest lucru este neplauzibil. Și, sincer, un astfel de algoritm ar fi probabil mai valoros de împărtășit decât de băgat în cap.

Savantul ar putea găsi o factorizare rapidă fără arătând NP=P sau chiar că BQP=P; de exemplu, s-ar putea ca factorizarea anumitor tipuri de numere prime pe care le folosim pentru criptografie este mai ușoară decât problema generală sau poate că un procent mare din astfel de numere compuse sunt ușor de factorizat (dar nu toate) sau că există un alt „caz de colț” care îi permite să funcționeze (chiar și uneori) extrem de mai rapid decât „încercați fiecare caz”. Un astfel de rezultat ar fi puternic, dar nu ar fi revoluționar pe scara rescrierii multor din ceea ce considerăm matematică interesantă (ceea ce un algoritm P eficient pentru problemele NP ar face, sincer).

Celelalte răspunsuri au subliniat deja în mod corect că creierele animalelor sunt mult mai lente și mai predispuse la erori decât computerele moderne în toate sarcinile de calcul, cu excepția unora selectați, care beneficiază foarte mult de tipul specific de recunoaștere a modelelor și abilități de planificare pentru care au fost dezvoltate creierele. . Evident, asta nu înseamnă că un creier animal nu poate fi util criptografic: într-adevăr, cele mai bune atacuri criptografice cunoscute astăzi au fost toate găsite cel puțin parțial de creierul animal. Cu toate acestea, pentru schemele criptografice standard, pare foarte puțin probabil ca un creier să poată face acest lucru alerga un atac de succes (ar putea fi, totuși, foarte util în stadiul de planificare aceasta).

Acestea fiind spuse, mi se pare amuzantă întrebarea dacă ar putea fi proiectată o schemă criptografică care să fie sigură împotriva tuturor atacurilor cunoscute care se bazează pe un algoritm de atac complet specificabil, dar care nu este sigură împotriva criptoanalizei pe hârtie și creion. Nu cred că răspunsul la aceasta este evident negativ. S-ar putea, de exemplu, să ne gândim la codificarea unei secvențe lungi de biți aleatoriu într-o serie de scheme Winograd. Receptorul ar rezolva manual schemele Winograd și ulterior va post-procesa secvența de biți recuperată pentru a-și amplifica avantajul de decodare față de modelele de limbaj de ultimă generație și va obține un pad unic care nu poate fi reconstruit cu precizie ridicată prin metode automate.În cele din urmă, OTP-ul derivat ar fi folosit pentru a cripta un mesaj scurt.

Cu toate acestea, din moment ce nu există dovezi că creierul este intrinsec mai bun la orice decât computerele, toate astfel de scheme vor fi predispuse în cele din urmă la atacuri automate practice.

Numărul de 2048 biți și 617 cifre zecimale @ulidtko postat mai sus poate fi factorizat în ore sau mai puțin și, eventual, de către un savant cu un calulator întreg mare. Am luat în calcul acest lucru și am găsit forma specială a factorilor. Factorii mici sunt ușori, dar factorii mari nu sunt dacă nu găsiți formă specială.

Tipul savant de abilitate necesar este abilitatea de a identifica modele în binar reprezentarea factorilor mai mici ai numărului de 2048 de biți.

Iată valorile zecimale și binare ale celor mai mici factori: 3 - 11, 5 - 101, 7 - 111, 13 - 1101, 17 - 10001, 97 - 1100001, 193 - 11000001, 241 - 11110001, 257 - 100000001

Poți vedea modelul? Există 3 modele. Primul model toate 1 sunt 11.111 Al doilea model 101,10001, 100000001 Al treilea model altul 1101, 1100001, 11110001

Al doilea model este 2^k+1. Primul model este 2^k-1. Dacă alegeți al 2-lea model și împărțiți în încercare cei 2^k+1, acest lucru se reduce factorizarea.

Factorii sunt: 3^3 x 5^2 x 7 x 13 x 17 x (2^768+1)(2^384+1)(2^256+1)(2^192+1)(2^128+1)(2^96+1)(2^64+1)(2^48+1)(2^32+1)(2^24+1)(2^16+1)(2^12+1)(2^8+1)

După împărțirea celor 2^k+1 mai mari, rămâneți cu 1044225=3^3 x 5^2 x 7 x 13 x 17 a factoriza.

Istorie: Alan Turing și spargerea mașinii Enigma. Prin urmare:

Este aceasta o preocupare reală atunci când proiectați cifruri criptografice? Ar putea o organizație diabolică să angajeze pe unul dintre acești oameni pentru a sparge chei criptografice (pentru orice cifru modern)?

Da, în măsura în care poți să-ți găsești Alan Turing și să oferi ceea ce este necesar (sau să-l construiești de la zero, așa cum a fost cazul „bombelor”) mașinii Enigma.

Nu, dacă crezi că Alan Turing o va face folosind hârtie și creion.

De fapt, dacă ai putea găsi un expert în factoring, asta ar constitui o dovadă că p=np (sau că o fraudă masivă a fost efectuată pe cheltuiala ta) voi paria o sumă mare pe aceasta din urmă.