Kaip veikia RSA

Įž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.

Šaltinis

Advertisements

One comment

  1. 26^23(mod 55) = 86
    36^23(mod 55) = 71
    39^23(mod 55) = 84
    35^23(mod 55) = 85
    The result of number(mod 55) must be less then 55. So you should choose R>86.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s