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 ja , niin yleinen ratkaisu on


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

josta edelleen jakoyhtälöa ja sen antamaa jakojäännöstä käyttäen saadaan

ja näin hän lähettää meille salatun viestin z = 428.

D1. Viestin purkaminen tapahtuu kaavasta


Nyt siis jakoyhtälöitä, jakojäännöksiä ja kongruensseja käyttäen saadaan






ja niin lähettäjän lähettämä viesti 355 kulki välin niin salattuna, että se vieraisiin käsiin joutuessaankin pysyy salaisena.