sunnuntai 28. syyskuuta 2008

Esimerkki viestin salaamisesta ja purkamisesta

Nytpä sitten numeerinen esimerkki viime kerran teoriaan. Tässä mukana paljon kongruenssien pyörittämistä laskimella käsiteltävien kokoisiksi.

A1. Valitaan alkuluvuiksi (nyt pienet) p = 19 ja q = 23.
A2. m = pq = 437
A3. b = (p - 1)(q - 1) = 396
A4. Valitaan a = 7

Näin on saatu viestien salaamisen avain m = 437 ja a = 7

B1. Muodostetaan Diofantoksen yhtälö ax - by = 1
siis 7x - 396y = 1

Eukleideen algoritmilla
396 = 56*7 + 4
7 = 1*4 + 3
4 = 1*3 + 1
3 = 3*1 + 0

Ratkaistaan jakojäännökset
4 = 396 - 56*7
3 = 7 - 1*4
1 = 4 - 1*3

Ja nyt viimeisestä jakojäännöksiä edeltä sijoittaen saadaan
1 = 4 - 1*3
= 4 - 1*(7 - 1*4) = -1*7 + 2*4
= -1*7 + 2*(396-56*7) = -113*7 + 2*396

Siten 7*(-113) + 396*2 = 1 ja alkuperäise diofantoksen yhtälön yhtenä ratkaisuna on x = -113 ja y = 2.

Nyt saatu x:n arvo ei negatiivisena tarkoitukseemme käy ja siten joudun täydentämään 10. syyskuuta kirjoitettua Diofantoksen yhtälöiden teoriaa. Jos yhtälön eräät ratkaisut ovat x_{o} ja y_{o}, niin yleinen ratkaisu on
\begin{matrix} x=x_{o}+\frac{b}{syt(a,b)}*n\\ y=y_{o}-\frac{a}{syt(a,b)}*n \end{matrix}

Nyt tämän avulla löydämme x:lle ensimmäisen positiivisen ratkaisun -113 + 396 = 283 ja näin on nyt saatu purkuavain t = 283.

C1. Lähettäjä haluaa lähettää meille viestin 355, siis s = 355
C2. Viestin hän kryptaa saamillaan salausavaimilla muotoon
z=355^{7}(mod437)\equiv 355^{3}*355^{3}*355
josta edelleen jakoyhtälöa ja sen antamaa jakojäännöstä käyttäen saadaan
\equiv 126*126*355\equiv 565\: 5980\equiv 428(mod437)
ja näin hän lähettää meille salatun viestin z = 428.

D1. Viestin purkaminen tapahtuu kaavasta
s=z^{t}(mod\; m)

Nyt siis jakoyhtälöitä, jakojäännöksiä ja kongruensseja käyttäen saadaan
s=428^{283}\equiv \left(428^{2} \right)^{141}*428\equiv 81^{141}*428
\equiv \left(81^{2} \right)^{70}*81*428\equiv 6^{70}*81*428\equiv \left(6^{7} \right)^{10}*81*428
\equiv 256^{10}*81*428\equiv \left(256^{2} \right)^{5}*81*428\equiv 423^{5}*81*428
\equiv 423^{2}*423^{2}*423*81*428
\equiv 196*196*423*428*81
\equiv 204*81\equiv 355(mod\; 437)
ja niin lähettäjän lähettämä viesti 355 kulki välin niin salattuna, että se vieraisiin käsiin joutuessaankin pysyy salaisena.

Ei kommentteja: