Įžanga
RSA kodavimas yra labai įdomus pavyzdys, kaip abstraktų matematinį modelį galima sėkmingai panaudoti realiam gyvenime. Šiame įraše pabandysim išsiaiškinti kaip vyksta RSA duomenų kodavimas iš matematinės pusės.
Paprastos funkcijos
Matematiškai funkcijos yra toks pats reiškinys, kaip ir programavime. Pavyzdžiui:
foo(x) = 10*x-2
Jeigu į funkciją perduosim 2, tuomet ji gražins 18. Viskas logiška. Mes taip pat galima parašyti funkciją, kuri daro lygiai tą patį, tik atvirkščiai:
bar(x) = (x+2)/10
Jeigu į funkciją perduosim 18, tuomet ji gražins 2. Kadangi bar(x) funkcija daro funkcijai foo(x) priešingus veiksmus, tai bar(x) funkcija yra atvirkštinė funkcijai foo(x).
Dabar pesikelkim į programavimo terpę. Pavyzdžiui, jeigu mes turim foo(x) funkcijos pradinį kodą, tačiau neturim bar(x) funkcijos pradinio kodo. Ar yra įmanoma parašyti bar(x) funkcija, kuri yra atvirkštinė funkcijai foo(x) ? Mes žinom kas bus siunčiama į bar(x) funkciją ir ką ji turėtų gražinti. Teoretiškai atsakymas būtų taip. Tačiau, yra keletas specialių funkcijų, kurių veikimo principas yra žinomas, tačiau parašyti jai atvirkštinę funkciją yra labai sunkus uždavinys.
Modulių aritmetika
Daugelis programuotojų yra sutikę % operatorių, kuris gražina dalybos liekaną. Pavyzdžiui:
10 % 3 = 1
Matematikoje, idėja yra panaši, tačiau pati modulių teorija yra skirtinga. Modulių aritmetika sudaro begalinis skaičius, kuris yra sukamas apie realaus skaičiaus lanką. Skaičiai, kurie neužbaigia ciklo yra vadinami kartotiniai. Analogišką operaciją programavime, matematikoje galime užrašyti taip:
10 = 1 (mod 3)
Skamba tai kaip: “10 turi kartotinį 1, moduliu 3”.
Liekaną geriau pamatysime, jeigu išskaidysime skaičių į jo dedamąsias:
6 + 4 = 0(mod 3) + 1(mod 3) = 1(mod 3)
Šioje išraiškoje, skaičius 6 liekana yra 0, o 4 liekana yra 1. Į (mod 3) veiksmą galime žiūrėti kaip į trijų valandų laikrodį, kuriame ciklas kartojasi su kiekvienu apsisukimu.
Įdomiausia modulių aritmetikoje, kad veiksmuose mes galime pakeisti skaičius jų liekanomis ir vistiek gauti teisingą atsakymą:
4 = 1(mod 3 ) 6 + 4 = 6 + 1 = 1(mod 3)
Jeigu naudojame kaip pagrindą 10 – mūsų visiškai nejaudina koks yra skaičius, mums svarbu kokiu skaičiumi yra baigiama:
37383 = 3(mod 10) 33313134 = 4(mod 10)
Didžiausias bendras daliklis
Didžiausias bendras daliklis ( GCD funkcija ) yra dviejų skaičių didžiausias skaičius, iš kurio dalinasi abu skaičiai:
gcd(22,11) = 11 gcd(23,55) = 1 gcd(999,99) = 9
Kuomet dviejų skaičių didžiausias bendras daliklis yra lygūs vienam, tai yra sakoma, kad skaičiai vienas kitam yra pirminiai. Kaip pavyzdžiui 23 ir 55 yra vienas kitam pirminiai.
Eulerio Totient Funkcija
Eurelio Totient Funkcija yra žymima graikiška raide phi(N) ir žymi skaičių kiekį (1;N-1) intervale, kurie yra pirminiai skaičiui N.
Pavyzdžiui:
phi(4) = 2 ( 1 ir 3 yra pirminiai skaičiui 4 ) phi(6) = 2 ( 1 ir 5 yra pirminiai skaičiui 6 ) phi(8) = 4 ( 1, 3, 5 ir 7 yra pirminiai skaičiui 8 )
Išsiskaičiuoti pirminius skaičius taip pat galima ir pasitelkus kitą išraišką:
phi(P*Q) = (P-1)*(Q-1)
Jeigu P ir Q yra pirminiai.
Eurelio Totient Teorema
Šita teorema yra pats svarbiausias raktas, vedantis prie RSA algoritmo:
Jeigu gcd(T, R) = 1 ir T < R, tuomet T^(phi(R)) = 1 (mod R)
Mes galima patikrinti teoremą, panaudodami kelis mažus skaičius. Jeigu pažymėsime T = 5 ir R = 6, gausime:
phi(6) = (2-1)*(3-1) = 1 * 2 = 2 5^(phi(6)) = 5^2 = 25 25 = 24 + 1 = 6*4 +1 = 1(mod 6)
Teoremos nagrinėjimas
Toliau paimkime Eurelio Totient teoremą ir su ja pažaiskime:
T^(phi(R)) = 1(mod R)
Padauginkime šitą teoremą iš jos paties. Dėka modulių daugybos viskas atrodys taip:
T^(phi(R))*T^(phi(R)) = 1*1(mod R) T^(2*phi(R)) = 1(mod R)
Pakartoję ciklą gausime:
T^(3*phi(R)) = 1(mod R)
Galime tęsti kiek norime. Atradus tokį dėsningumą mes galime praplėsti Eurelio Totient Teoremą:
Jeigu GCD(T, R) = 1 ir T < R, tuomet T^(K*phi(R)) = 1(mod R), kur K bet koks skaičius
Galima pastebėti, jog K gali būti tik sveikasis skaičius, kas reiškia, kad K*phi(R) dalinsis be liekanos iš phi(R). Taigi dėsnį galime perfrazuoti:
Jeigu GCD(T, R) = 1 ir T < R, tuomet T^S = 1(mod R), kuomet S = 0(mod phi(R))
Tęskime savo žaidimą ir padauginkime gautą lygtį iš T:
T^S*T = 1*T(mod R) T^(S+1) = T(mod R)
Pakartojam:
T^(S+1)*T = T*T(mod R) T(S+2) = T^2(mod R)
Ir taip toliau. Matome dėsningumą. Iš jo galime nusręsti, kad S ne R kartotinis, o phi(R). Iš šito seka nauja taisyklė:
T^E = T^F(mod R), kuomet E = F(mod phi(R))
Idėja
Grįžkime prie ankstesnės lygties ir panagrinėkime ją dėtaliau:
T^(S+1) = T(mod R)
Vienoje lygties pusėje mes turim T, pakeliam jį kvadratu. Kitoje lygties pusėje mes su T atliekame modulių aritmetikas. Mes turi dvi lygtis, kurios yra lygios ir kuriose dalyvauja tas pats vienas kintamasis.
Tačiau kas gi čia tokio stebuklingo? O stebuklinga yra tai, kad mes galime lengvai jas atskirti. Būtent šiuo atveju, paimkime kažkokius du nauju skaičius P ir Q, tuomet:
P*Q = S+1, kiekvienai S reikšmei
Arba:
P*Q = 1(mod phi(R))
Tuomet mes galima parašyti:
T^(P*Q) = T(mod R)
Kas yra tas pats, kas ir:
(T^P)^Q = T(mod R)
Ir tai mes jau galime perskelti į du žingsnius:
T^P = X(mod R) ir X^Q = T(mod R)
Generuojam raktų porą
Norint sugeneruoti tam tikrus raktus, pirmiausiai reikia parinkti reikšmę R. Taigi, galime pradėti atsitiktinai imdami du skaičius, U ir V, ir juos daugindami:
R = U*V
Abudu skaičiai turi būti pirminiai vienas kito atžvilgiu. Paskui bus galima lengvai rasti skaičiaus R pirminius skaičius:
phi(R) = (U-1)*(V-1)
Pavyzdys
Tam, kad pamatyti, kaip viskas suskaičiuojama, paimkime mažus skaičius, tarkime U = 5, V = 11:
R = U*V = 5*11 = 55 phi(R) = phi(55) = (5-1)*(11-1) = 4*10 = 40
Dabar reikia rasti skaičius, kurie tinka lygčiai:
P*Q = 1(mod 40)
Žinoma, jų yra begalinis skaičius, tačiau pradėkime nuo P = 7.
7*Q = 1(mod 40)
Perrašom dešinę pusę:
7*Q = K*40 + 1
Pirmas skaičius, kuris tenkina lygtį yra Q = 23:
7*23 = 161 = 4 * 40 + 1
Taigi, mūsų viešas raktas yra P = 7, o privatus Q = 23.
Tarkime, norime išsiųsti žodį “VGTU”. Painaudoję ASCII kodų lentelę, skaičiais tai atrodytų taip:
86 71 84 85
Dabar užkoduojam kiekvieną simbolį su viešu raktu:
86^7 (mod 55) = 26 71^7(mod 55) = 36 84^7(mod 55) = 39 85^7(mod 55) = 35
Gauvome tokį kodą:
26 36 39 35
Jeigu išversime visą tai pasitelkdami ASCII lentelę, gausime “SUB$’#”, kas visiškai neturi nieko bendro su mūsų siunčiama žinute. Kuomet duomenys baigia savo kelią per nesaugią liniją, gavėjo pusėje vyksta duomenų dekodavimas pagal privatų raktą Q = 23.
26^23(mod 55) = 86 36^23(mod 55) = 71 39^23(mod 55) = 84 35^23(mod 55) = 85
Gavome kodą:
86 71 84 85
Kas iš ASCII kodų lentelės surenka “VGTU”.
Galite pabandyti atkoduoti:
68 10 20 20 34 43 23 29 07 17 12 36
Su privačiu raktu Q = 23 ir R = 55.
Išvados
RSA yra gan paprastas kodavimo algoritmas, tačiau nežinant raktų, jį iškoduoti su dabartiniais kompiuteriais gali užtrukti ant tiek ilgai, kad saulė jau išnaudos visus savo resursus ir sprogs, o kompiuteris vis dar bandys iškoduoti RSA kodą.
Jis neparodo simbolių priklausomybės, kaip tarkim T (84) ir U (85) skiriasi tik viena eile, tačiau užkoduojant juos RSA, jų skirtumo eilė pasikeitė T (39) ir U (35) ir netgi tapo neigiama.
Talking trees 