Nyt sitten edellä olleiden työkalujen esittelyn jälkeen itse salakirjoittamiseen ja sen purkamiseen.
A. Julkisen salakirjoitusavaimen muodostaminen
A1. Valitse kaksi suurta alkulukua
p ja
q
A2. Laske niiden tulo
m = pq
A3. Laske Eulerin funktion arvo
b = &phi(
m)=(
p-1)(
q-1)
A4. Valitse jokin kokonaisluku a &ge 2, jolla ei ole yhteistä tekijää luvun
b kanssa.
Luvut
m ja
a muodostavat sinulle lähetettävän viestin salausavaimen. Ne voidaan julkistaa vaikkapa lehdessä tai internetissä. Huomattavaa on, että julkistetun luvun
m perusteella ei voida saada selville lukua
b muutoin kuin löytämällä
m:n tekijät
p ja
q. Tämä on taas ylivoimainen tehtävä tehokkaimmillekin tietokoneille jos
p ja
q ovat kyllin suuria. (Kts. teksti 27. elokuuta alkuluvuista)
B. henkilökohtaisen purkuavaimen muodostaminen
B1. Määritä Eukleideen algoritmilla yhtälölle
ax - by = 1 jokin ratkaisu
x = t ja
y = u. (Kts. kirjoitukset 1. ja 10. syyskuuta)
- ratkaisu on olemassa, koska syt(
a,b) = 1
- ratkaisu
x = t toteuttaa yhtälön
at = 1
bu = 1 +
u&phi (
m)
Luku
t muodostaa purkuavaimen, jota ei anneta muilla vaan säilytetään tarkasti. Tämän purkuavaimen selvillesaaminen edellyttää yhtälön
ax - by = 1 ratkaisemista, mikä taas edellyttää luvun
b tuntemista, eikä tämä siis onnistu tietokoneellakaan, jos alun alkuluvut on valittu suuriksi.
C. Viestin salaaminen ja lähettäminen
C1. Lähettäjä kirjoittaa sanomansa luvuksi
s, missä 0 &le
s <
m
C2. Lähettäjä kryptaa sanomansa s luvuksi
![z=s^{a}\; (mod\; m)](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tUNVAsL9Zie1t_47A-n4zM62uDejP8qr2hnCsYQ3OrSKbqG3xrN1tHM9Zl6AJlIoWG5hfW9--zKrHt62LEz8ejxGfduw3lSpVlbmNdIlffcFLve0patG0pQWC8WXpK8pD-kXLBWjBnowwSMFF3xQ=s0-d)
- tämä onnistuu, koska luvut
a ja
m ovat julkisia
C3. Lähettäjä lähettää sinulle luvun
z.
D. Vastaanotetun sanoman purkaminen
D1. Saatuasi viestin
z laske potenssi
![z^{t}\; (mod\; m)](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vnnt5LeS0v2xxQsh0ciioL_p0MrqI6nlDjxXCMHTFdOK_HmlJHzyQla8O6BvMHTGvaFlmEOFFTnlaFOoXup3O7Hc-_5mtw8ZKCVP-WcgZ7RV2X6ShNKU0fHWbcO0R96FsWx5SddiMaCzho1I0=s0-d)
käyttämällä henkilökohtaista purkuavaintasi
t. Saat tulokseksi alkuperäisen sanoman s. Miksi? Siksi, että
![z^{t}=(s^{a})^{t}=s^{at}=s^{1+u\varphi (m)}=s\cdot (s^{\varphi (m)})^{u}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_v-rzfIwzQZGMGh-9BRLwNp41zh7wAtBINH32Wp0Dk9n5c_02OglJVbKw9Iw4fMnDkl59SLy8vFHTSAZvHbeq1W4-bwdJHeLNN3Dfu8JjZp3_KkvrlCYxtUdZ0QXhMT4tIgrpTm_ST87r6fMMryS2iX_RPAyi-CsH3OVZhAwKECP1NiQdleuAo1g2mgCDsKjWXgnbfOSq4_oFDBtRnpyRKepQFOMrj4bnhNccHDbHGQQY4Kvr3Uv-szRJYy0Urid2Rzj6LKW3nPnwSFb4-9LweiSNjC=s0-d)
ja Eulerin lauseen perusteella on
![s^{\varphi (m)}\equiv 1\; (mod\; m)](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_ucbF1GYKhNUItDJeosrKoJl4h5a5y_joHTqXQKe1oc28g1p5CFslix59qIDVoyj-d9UZnIW33vTC6QePBKUyXEdynni3ZEMIuGPxNCEUGePMXiqwMeSPbA2T6AuYNtrAKojSppNiTKSltt3A7zKkeDDiY1Ia0w9QYiFG8YnZt0HtkAqbu7TBD-JlIfZ1qW=s0-d)
, joten
Seuraavalla kerralla vielä konkreettinen esimerkki yllä olevasta, tosin hyvin pienillä luvuilla, koska niilläkin siitä tulee käsin laskien aika työläs.