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_une7W0hRUV4LEgtq5QK2SUaOvFMwC9S2JB2Bag2AtsA6boi24ytSXkAZ59SkOVcErqFGBtxdQ_OZhlRrJLZej_nB1_pUlRrXaqAFoCc8zFvDXAlTqm5gwBRYddky0dRhf2PpgXyIxclv0K_jhqiQ=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_uEfiviBFso5rp75Ul9dtHoCLHdyzt9GoWUa3l2hHSShcknJNbT0YHG7mlsRf-qDDWoRBJSyGBNO0er6fXwp2ox856ob5QDfRfRwp5UaJwG9fHIMCuEyXmSnNv_dU1mthQqJxOMpAeMElZel7Q=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_sM0Gwt24M0YLOpCdWxGBADtqjmeC2drX2roRvwI5Ywdqy4d2uc7-I4o6NDuq0VbWt_bXiRW2wemFkb9xu_RXNJK0fiZFDexwPxHYmy164ADHzvrVeqFnmLRJJd24be05KIjRt_jarn55QwV-_mLKfglG53HzGPd-Zzl6iA9tN-iM03i6BRPsg8-ExB49PN-yV550Gh8K0DiywMpgq5BXUeCTuYsBbJhlPKxVTHUY9SHPPvm_SgF4jJlIcB2epBLbRaVCIlG4IQ2PHboQJWpaHymjXc=s0-d)
ja Eulerin lauseen perusteella on
![s^{\varphi (m)}\equiv 1\; (mod\; m)](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_uXl1uvjX4pe_lpJCPvcYb5snwRnHXhLmCzEtYyPPOwGQZnBfrskF8dUVk1KQq_nKcLC2pZTruTYFSS5fEOqhpqPiwmxdq6Aql-RIuzcCWv6Dp1j4nW0fBGeYIYA-uZhX9_FZQa9_8yVMn2TE6y42kbNhZNVsrRmHn7K9gtF77H3fqvombb1ED7Xzw2DkFX=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.