Kedysi dávno, ešte v r. 2001 som použil veľmi starú, ale elegantnú metódu na riešenie faktorizácie modulu RSA...Fermatova faktorizácia
Úloha bola rozlúštiť správu zašifrovanú pomocou RSA - ktorá bola ale kódovaná ala známa "kódová kniha", tj. veľmi ľahko lúštiteľná pomocou ceruzky a papiera - Kľúč na šifrovanie bol veľmi jednoduchý: (modul, e) = (2479, 101):
"...Kedze modul je maly, da sa pouzit metoda faktorizacie.
Z faktorizacnych metod som si ako najjednoduchsiu a najrychlejsiu pre moje ucely zvolil klasicku Fermatovu metodu:
Najprv som si vypocital hornu celociselnu hranicu z hodnoty odmocniny z modulu n=2479, t.j. h=[2479^(1/2)]=50.
V prvom kroku som postupoval podla Fermatovej procedury, ktora je udana nasledovnou podmienkou (symbolika je ako obvykle, druha odmocnina je SQRT a mocnina je ozn. "strieskou" , t.j. '^'.): SQRT(h^2-n) by malo byt cele cislo. Ak nie je, hodnota h sa inkrementuje, t.j. h=h+1 a vypocet vyrazu opakujeme dotial, pokial nedostaneme cele cislo. Ak sme dospeli k celociselnemu vysledku a ked ozn. tuto hodnotu pism. a a cislo kroku v procedure ako k, dostavame rovnicu: sqrt((h+(k-1))^2-n)=a.
Z nej upravou ziskame nasledovnu rovnicu pre n: n=(h+(k-1)-a)*(h+(k-1)+a).
Co je vlastne n rozlozene na faktory p a q, t.j. n=p*q.
Na nasom konkretnom module to vyzera nasaledovne:
I. sqrt(50^2-2479) = 4,582575694956, co nie je cele cislo,
II. sqrt(51^2-2479) = 11,04536101719, co tiez nevyhovuje,
III. sqrt(52^2-2479) = 15, dostali sme cele cislo, takze mozme upravovat: n = 2479 = (52+15)*(52-15)=67*37, p=67 a q=37.
Teraz je uz mozne pristupit k vypoctu desifrovacieho exponentu.
Eulerova funkcia pre modul je fi(n) = fi(p)*fi(q) (co, mimochodom vyplyva z multiplikativnej vlastnosti tejto funkcie) = (p-1)*(q-1).
Pre nase ciselne hodnoty je to: fi(2479)=(67-1)*(37-1) =2376.
Z podmienky RSA pre sifrovaci a desifrovaci exponent e*d = 1 mod fi(n) vyplyva kongruencia 101*d = 1 mod 2376, ktora sa riesi Euklidovym algoritmom nasledovne:
Rozpiseme si ju podla definicie: 101*d-1=2376*k, kde k je lubovolne cele cislo, z coho upravou 1=101*d+2376*k.
Je to vlastne diofanticka rovnica.
Takze teraz uz postupujeme podla algoritmu. 2376 = 101*23+53, 101=53*1+48, 53=48*1+5, 48=5*9+3, 5=3*1+2, 3=2*1+1
Dostali sme zvysok 1, takze dalej postupujeme tak, ze si z posledne rovnosti vyjadrime tento zvysok a postupujeme naspat dosadzovanim jednotlivych medzivysledkov takto: 1=3+2*(-1)=3*2+5*(-1)=48*2+5*(-19)=53*(-19)+48*21=101*21+53*(-40)=2376*(- 40)+101*941
Z tohto a z diofantickej rovnice vyplyva k=-40 a to co sme si zelali, nas desifrovaci exponent d=941...."
....
U našich východných výskumníkov bol tento modul o dosť väčší a predstavte si, mal dokonca "úctyhodných" 2831 bitov:
n = 9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999919
Všimnime si však, že je v ňom 542 deviatok, po ktorých nasledujú číslice 1 a 9, čo je celkovo 544 číslic. Je to síce prekvapujúce, ale aj toto číslo sa dá faktorizovať podľa "starého dobrého" Fermata.
_________________________________________________________________________________
Nie je ťažké si uvedomiť, že dané číslo je veľmi blízko číslu 100^272 (pretože 272 * 2 = 544 číslic). Číslo 100 sa dá vyjadriť ako 10^2, dá sa z toho vypozorovať, že druhá odmocnina daného modulu musí byť rádovo porovnateľná s hodnotou 10^272. Takže nech
t = 10²⁷²
Pretože t² je približne rovné n, počítajme rozdiel:
r = t² - n = 81
Určite viete, že druhá odmocnina z uvedeného výsledku je deväť, tj. √81 = 9, z toho jasne dostávame, že r = 9².
Ak si všetko čo sme doteraz zistili, zapíšeme do jedného riadku, dostávame:
n = t²-9²
Vieme, že z dobre známej identity a²-b² = (a+b)·(a-b) môžeme nahliadnuť, že:
n = (t+9)·(t-9). A sme na konci, tu je naša faktorizácia, tj. rozloženie na prvočinitele. Teda máme:
n = 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000009 · 99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999991
Na záver, práve sme "zázračne" rozlomili 2831 bitový RSA modul s pomocou“quantového počítania”, a to takmer zadarmo. Z tohto malého exkurzu do elementárnej teórie čísel vyplýva varovanie:
Ak chcete šifrovať pomocou RSA, nikdy nepoužívajte čísla, ktoré majú unikátne a špecifické vlastnosti.
______________________________________________________________
Voľná inšpirácia výskumným článkom čínských odborníkov na quantové počítanie: A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer :)
