KeijoV¨a¨an¨anen SALAUSMENETELM¨AT(801346A)4op,2ov Luentorunkojaharjoitusteht¨av¨at

Luentorunko ja harjoitusteht¨av¨at

SALAUSMENETELM¨ AT (801346A) 4 op, 2 ov

Keijo V¨a¨an¨anen

I JOHDANTO

Salakirjoitukset kurssilla tarkastelemme menetelmi¨a, jotka mahdollistavat tiedon siir- t¨amisen tai tallentamisen niin, ett¨a ainoastaan tarkoitettu vastaanottaja saa viestin selville. L¨ahett¨aj¨an teht¨av¨an¨a on salakirjoittaa (encrypt) selv¨akielinen teksti (plaintext) salakirjoitukseksi (cryptotext) ja vastaanottajan teht¨av¨an¨a puolestaan avata (decrypt) salakirjoitus selv¨akieliseksi tekstiksi. Menettelyn tulee olla sellainen, ett¨a mahdollinen salakirjoituksen sieppaaja ei kykene murtamaan sit¨a (ts. selvitt¨am¨a¨an selv¨akielist¨a teksti¨a) ainakaan nopeasti.

Aikaisemmin salakirjoituksia tarvittiin l¨ahinn¨a sotilaallisiin tai diplomaattisiin tarkoituk- siin. Viimeisten runsaan 20 vuoden aikana tietokoneisiin perustuvan tiedonv¨alityk- sen yleistyminen on merkinnyt sit¨a, ett¨a salausmenetelmi¨a tarvitaan p¨aivitt¨ain hyvin monilla muillakin yhteiskunnan alueilla (pankit, yritykset ym.).

Esimerkki (Caesar). Salakirjoitus tehd¨a¨an siirt¨am¨all¨a kirjaimia k askelta eteenp¨ain, esim k = 3 antaa seuraavaa:

A B C D E F G H I J K L M N O P Q R S T U V X Y Z A¨O¨

↓

D E F G H I J K L M N O P Q R S T U V X Y Z A¨O A B C¨ selv¨akielinen teksti : ALOIT AM M E

↓

salakirjoitus : DORLXDP P H

salakirjoitus : KHOS

↓ avattuna selv¨akieliseksi : HELP

T¨am¨a salakirjoitus on helppoa murtaa kokeilemalla eri siirtovaihtoehdot (26 kpl).

Selv¨akielinen teksti ja salakirjoitettu teksti kirjoitetaan k¨aytt¨am¨all¨a jotakin aakkostoa (kirjaimet, numerot, muut merkit). Jotta matemaattisia menetelmi¨a voitaisiin k¨aytt¨a¨a, korvataan kirjaimet usein numeroilla, esimerkiksi A= 0, B = 1, ...,O¨ = 26. Selv¨akieli- nen teksti ja salakirjoitus jaetaan viestiyksikk¨oihin ja salaaminen tehd¨a¨an yksikk¨o ker- rallaan. Viestiyksikk¨o voi olla kirjain (kuten ¨askeisess¨a esimerkiss¨a), kirjainpari tai tie- tyn pituinen kirjainjono. Salakirjoittamiseen k¨aytet¨a¨an yleens¨a bijektiivist¨a funktiota E :P →C, miss¨a

P ={selv¨akieliset viestiyksik¨ot}={m}, C ={salakirjoitetut viestiyksik¨ot}={c}.

Avaaminen tapahtuu t¨all¨oin k¨a¨anteisfunktion D= E⁻¹ avulla.

Salakirjoitusj¨arjestelm¨a¨an kuuluvat siis: (i)P, (ii) C, (iii) avainjoukko K ={k}, miss¨a kukin avain k m¨a¨ar¨a¨a salausfunktion Ek ja avausfunktion Dk, jolle Dk(Ek(m)) = m.

L¨ahett¨aj¨a tuntee ennakolta Ek:n ja vastaanottaja Dk:n, jolloin j¨arjestelm¨a toimii seu- raavan kaavion mukaisesti.

Hyv¨alt¨a salakirjoitusj¨arjestelm¨alt¨a edellytet¨a¨an:

(i) Ek(m) ja Dk(c) voidaan laskea helposti.

(ii) Jollei tunneta D_k:ta, niin m ei selvi¨a c:st¨a (ts. sieppaajalla on vaikea teht¨av¨a).

Kaikissa perinteisiss¨a salakirjoitusj¨arjestelmiss¨aDksaadaan v¨alitt¨om¨astiEk:sta (ei tosin aina niin helposti kuin ¨askeisess¨a esimerkiss¨a). N¨ain ollen l¨ahett¨aj¨an ja vastaanottajan tulee sopia jollakin tavalla avaimesta ja pit¨a¨a t¨am¨a sopimuksensa salassa muilta. T¨ast¨a syyst¨a n¨aist¨a j¨arjestelmist¨a k¨aytet¨a¨an nimityst¨a yksityisen avaimen salakirjoitus. Run- saat 20 vuotta sitten kehitettiin ensimm¨aiset julkisen avaimen j¨arjestelm¨at, joille on ominaista se, ett¨a E_k ei paljasta D_k:ta (ainakaan helposti). N¨am¨a perustuvat ns. yk- sisuuntaisiin funktioihin (one-way function)f, joiden k¨a¨anteisfunktiota on k¨ayt¨ann¨oss¨a mahdotonta (tai ainakin hyvin vaikeaa) m¨a¨aritt¨a¨a.

Useimmat k¨ayt¨oss¨a olevat salakirjoitusmenetelm¨at perustuvat lukuteorian tuloksiin.

T¨ast¨a syyst¨a aloitamme kurssin kertaamalla er¨ait¨a lukuteorian alkeiden tuloksia.

II LUKUTEORIAA

1. Jakoalgoritmi ja eri kantaiset esitykset

Luvuista puhuttaessa tarkoitamme seuraavassa luonnollisia lukuja N = {0,1,2, ...} tai kokonaislukuja Z={0,±1,±2, ...}.

Lause 1 (jakoalgoritmi). Jos a, b ∈ Z, b 6= 0, niin on olemassa sellaiset yksik¨asitteiset q, r∈Z, ett¨a

a=qb+r, 0≤r < |b|.

Olemme tottuneet k¨asittelem¨a¨an lukuja 10-j¨arjestelm¨ass¨a, esimerkiksi 2367 = 2·10³+ 3·10² + 6·10 + 7. Luku 10 on luonnollinen biologisista syist¨a, mutta mik¨a¨an ei est¨a valitsemasta kantalukua b ≥ 2 muutenkin. Annettu a ∈ N voidaan esitt¨a¨a helposti jakoalgoritmia k¨aytt¨aenb-kantaisessa j¨arjestelm¨ass¨a. Esimerkiksi luvun 319 8-kantainen esitys saadaan jakamalla toistuvasti 8:lla:

319 = 39·8 + 7, 39 = 4·8 + 7, joten

310 = (4·8 + 7)·8 + 7 = 4·8²+ 7·8 + 7.

Merkitsemme 319 = 4778. Vastaavasti esimerkiksi 2516 = 2·6²+ 5·6 + 1 = 103. Jos siis kantaluku b6= 10, merkitsemme sen n¨akyviin alaindeksin¨a.

10-j¨arjestelm¨an ohella erityisen t¨arke¨a on 2-kantainen eli bin¨a¨arij¨arjestelm¨a, jota tietokoneet ymm¨art¨av¨at.

2. Jaollisuus

M¨a¨aritelm¨a. Jos a, b ∈ Z ja on olemassa sellainen c ∈ Z, ett¨a a = bc, niin b on a:n tekij¨a (tai aon jaollinen b:ll¨a). T¨all¨oin merkit¨a¨an b|a.

Jaollisuudella on seuraava ominaisuus.

Lause 2. Jos n|aja n|b, niin n|(ra+sb) ∀r, s∈Z.

Seurauksia: 1) n|aja n|b⇒n|(a±b), 2) n|a⇒n|ra ∀ r∈Z, 3) n|aja a|b⇒n|b.

Jokaisellaa∈Z on aina ns. triviaalit tekij¨at ±1 ja ±a.

M¨a¨aritelm¨a. Luku p≥2 on alkuluku, jos sill¨a on vain triviaalit tekij¨at (±1 ja±p).

Alkulukuja on ¨a¨arett¨om¨an monta ja kaikki positiiviset kokonaisluvut voidaan esitt¨a¨a oleellisesti yksik¨asitteisesti niiden avulla, sill¨a on voimassa

Lause 3 (aritmetiikan peruslause). Jokainen positiivinen kokonaisluku ≥ 2 voidaan esitt¨a¨a j¨arjestyst¨a vaille yksik¨asitteisesti alkulukujen tulona.

Seurauksia: 1) Jos p on alkuluku ja p|ab, niin p|atai p|b.

2) Jos r|aja s|aja luvuillar ja sei ole yhteisi¨a alkulukutekij¨oit¨a, niinrs|a.

3) Jos tunnetaan luvun esitys alkulukujen tulona (∃ L3 perusteella), niin positiivisten tekij¨oiden lukum¨a¨ar¨a on helppo laskea. Esimerkiksi

4200 = 2³·3·5²·7,joten tekij¨oiden lukum¨a¨ar¨a on (3+1)(1+1)(2+1)(1+1)=48.

M¨a¨aritelm¨a. Olkoot a, b ∈ Z ja ainakin toinen 6= 0. Lukujen a ja b suurin yhteinen tekij¨a syt(a, b) on suurin luonnollinen luku, joka on sek¨a a:n ett¨a b:n tekij¨a.

N¨ahd¨a¨an helposti, ett¨a d > 0 onsyt(a, b), jos 1) d|a ja d|b,

2) n|aja n|b⇒n|d.

Josa:n jab:n alkutekij¨aesitykset tunnetaan, niin on helppoa antaasyt(a, b).Esimerkiksi 4200 = 2³·3·5²·7 ja 10780 = 2²·5·7²·11,joten

syt(4200,10780) = 2²·5·7 = 140.

Suuria lukuja tarkasteltaessa niiden alkutekij¨aesitysten l¨oyt¨aminen on vaikeaa. Kuitenkin on olemassa menettely, ns. Eukleideen algoritmi, jonka avullasytl¨oytyy helposti. Kyse on jakoalgoritmin toistuvasta soveltamisesta. Voimme olettaa, ett¨a a≥b > 0.

Eukleideen algoritmi:

a=q1b+r1, 0< r1 < b, b=q₂r₁+r₂, 0< r₂ < r₁, r1 =q3r²+r³, 0< r3 < r2,

· · ·

rn−2 =qnrn−1+rn, 0< rn < rn−1, rn−1 =qn+1rn.

Lause 4. Viimeinen nollasta eroava jakoj¨a¨ann¨os r_n = syt(a, b). Edelleen on olemassa sellaiset u, v ∈Z (l¨oytyv¨at helposti Eukleideen algoritmilla), ett¨a

syt(a, b) =ua+vb.

Lukuja a ja b sanotaan kesken¨a¨an jaottomiksi tai suhteellisiksi alkuluvuiksi, jos syt(a, b) = 1.

M¨a¨aritelm¨a. Ns. Eulerin funktio ϕon m¨a¨aritelty ∀n≥1 jaϕ(n) on niiden kokonais- lukujen blukum¨a¨ar¨a, joille 0≤b < n ja syt(b, n) = 1, ts.

ϕ(n) =|{0≤b < n|syt(b, n) = 1}|. (|A|tarkoittaa joukon A alkioiden lukum¨a¨ar¨a¨a.) Lause 5. Eulerin funktiolla ϕ on ominaisuudet:

1) ϕ(1) = 1;

2) Jos p on alkuluku, niin ϕ(p^k) =p^k−1(p−1), erityisesti ϕ(p) =p−1;

3) Jos p ja q6=p ovat alkulukuja, niin ϕ(pq) = (p−1)(q−1).

3. Kongruensseista

Esittelemme nyt jaollisuuteen perustuvan kongruenssik¨asitteen, jonka otti k¨aytt¨o¨on Gauss.

M¨a¨aritelm¨a. Jos a, b, n ∈ Z, n ≥ 2, niin a on kongruentti b modulo n, merk. a ≡ b (mod n), jos m|(a−b).

Ominaisuuksia:

1) a ≡ a (mod n); a ≡ b (mod n) ⇔ b ≡ a (mod n); a ≡ b (mod n) ja b≡c(mod n)⇒a≡c(mod n).

2) Jos a≡b(mod n) ja c≡d (mod n), niin a±c≡b±d (mod n) ja ac≡bd (mod n).

Ominaisuuden 1) perusteella kongruenssi (modn) on ekvivalenssirelaatio, joten se jakaa Z:n alkiot ekvivalenssiluokkiin, ns. j¨a¨ann¨osluokkiin (mod n). Luvun am¨a¨ar¨a¨am¨a j¨a¨an- n¨osluokka on

¯

a={x ∈Z|x ≡a(mod n)}={a+kn|k ∈Z}.

Selv¨asti ¯a = ¯b ⇔ a ≡ b (mod n). Jos a ∈ Z, niin jakoalgoritmin mukaan on olemassa yksik¨asitteisetq, r ∈Z, joille

a=qn+r, 0≤r < n.

T¨all¨oin ¯a = r,¯ joten jokainen kokonaisluku kuuluu t¨asm¨alleen yhteen luokista

¯0,¯1,¯2, ..., n−1. N¨am¨a j¨a¨ann¨osluokat ovat erillis¨a, joten j¨a¨ann¨osluokkia (mod n) on n kpl. K¨ayt¨amme niiden joukolle merkint¨a¨a Zn,joten edellisen mukaan

Z_n ={¯0,¯1,¯2, ...n−1}.

Ominaisuuteen 2) nojautuen voimme m¨a¨aritell¨a j¨a¨annosluokkien (mod n) summan ja tulon asettamalla

¯

a+ ¯b=a+b, ¯a¯b=ab.

Asettamalla lis¨aksi −¯a = −a ja ¯a−¯b = ¯a+ (−¯b), voimme suorittaa j¨a¨ann¨osluokilla (mod n) yhteen-, v¨ahennys- ja kertolaskuja. Lis¨aksi joukostaZtutut laskus¨a¨ann¨ot ovat voimassa, ts. Zn on vaihdannainen ykk¨osellinen rengas ykk¨osalkionaan ¯1.

Tarkastelemme seuraavaksi k¨a¨anteisalkion olemassaoloa. Olkoon ¯a 6= ¯0. Milloin on olemassa sellainen ¯x, ett¨a ¯a¯x= ¯1? Voimme yht¨apit¨av¨asti kysy¨a, milloin kongruenssilla ax≡1 (mod n) on ratkaisu x?

Lause 6. Kongruenssilla ax ≡ 1 (mod n) on ratkaisu jos ja vain jos syt(a, n) = 1.

Ratkaisut muodostavat t¨asm¨alleen yhden j¨a¨ann¨osluokan (modn).

Lauseen 6 todistuksesta k¨ay ilmi, miten yht¨al¨on ¯a¯x = ¯1 ratkaisu ¯a⁻¹ = ¯x l¨oytyy Eukleideen algoritmin avulla. Luokkaa ¯a, jolle ¯a⁻¹ on olemassa, sanotaan alkuluokaksi (mod n). Alkuluokkien lukum¨a¨ar¨a onϕ(n) ja niiden muodostamalle joukolle k¨aytet¨a¨an merkint¨a¨aZ^∗_n.Z^∗_non vaihdannainen ryhm¨a kertolaskun suhteen. Josn=pon alkuluku, niin Z^∗_p = Z_p − {¯0}, joten Z_p:n jokaisella nollasta eroavalla alkiolla on k¨a¨anteisalkio.

Joukossa Z^∗_p voidaan siis suorittaa rajoituksetta kaikkia nelj¨a¨a laskutoimitusta, vain nollalla jakaminen ei ole mahdollista, ja kaikki rationaaliluvuilta tutut laskus¨a¨ann¨ot toimivat. Zp on n¨ain esimerkki ¨a¨arellisest¨a kunnasta. N¨am¨a ovat t¨arkeit¨a joissakin salakirjoitusmenetelmiss¨a.

Kun otetaan yksi alkio jokaisesta j¨a¨ann¨osluokasta (modn), saadaan ns t¨aydellinen j¨a¨an- n¨ossysteemi (mod n). Vastaavasti ottamalla yksi alkio kustakin alkuluokasta (mod n), saadaan supistettu j¨a¨ann¨ossysteemi (modn). Helposti todetaan, ett¨a josa₁, a₂, ..., a_ϕ(n) on supistettu j¨a¨ann¨ossysteemi ja syt(a, n) = 1, niin my¨os aa1, aa2, ..., aa_ϕ(n) on supis- tettu j¨a¨ann¨ossysteemi. T¨ah¨an tietoon nojautuen ei ole vaikea todistaa

Lause 7 (Eulerin lause). Jos syt(a, n) = 1, niin a^ϕ(n) ≡1 (mod n).

Seuraus (Fermat’n pieni lause). Jos p on alkuluku ja p-a,niin a^p−1 ≡1 (mod p).

Lause 7 voidaan my¨os lausua muodossa: Jos ¯a ∈ Z^∗_n, niin ¯a^ϕ(n) = ¯1. T¨ast¨a k¨ay ilmi, ett¨a ¯a⁻¹ = ¯a^ϕ(n)−1, joten k¨a¨anteisalkio ¯a⁻¹ saadaan potenssiinkorotuksella laskemalla

¯

a^ϕ(n)−1.

Olkoon seuraavassaa(modn) jakoj¨a¨ann¨os, kunajaetaann:ll¨a. Tarkastelemme potenssin a^` (mod n) nopeaa laskemista, kun syt(a, n) = 1. Jakoalgoritmin mukaan

`=qϕ(n) +r, 0≤r < ϕ(n).

Eulerin lauseen mukaan a^ϕ(n) ≡1 (mod n),joten a^` = (a^ϕ(n))^qa^r ≡a^r (mod n)

eli a^` (mod n) =a^r (mod n). Olkoon luvunr bin¨a¨ariesitys

r =ek·2^k+ek−1·2^k−1+...+e1·2 +e0, ei ∈ {0,1}, ek= 1.

Lasketaan per¨akk¨aisill¨a neli¨o¨onkorotuksilla:

a1 = a² (mod n),

a₂ = a²₁ (mod n)(=a²² (mod n)), a₃ = a²₂ (mod n)(=a²³ (mod n)),

. . .

ak =a²_k−1 (mod n)(=a^2k (mod n)).

T¨am¨an j¨alkeen saadaan

a^{`</sup> ≡a<sup>r</sup> ≡a<sup>e</sup><sub>k</sub><sup>k</sup>a<sup>e</sup><sub>k−1</sub><sup>k−1</sup>...a<sup>e</sup><sub>2</sub><sup>2</sup>a<sup>e</sup><sub>1</sub><sup>1</sup>a<sup>e0</sup> (mod n), josta a<sup>`} (mod n) on nopeasti laskettavissa.

III PERINTEISI ¨A SALAKIRJOITUSJ ¨ARJESTELMI ¨A 1. Caesar ja sen yleistyksi¨a

Oletamme, ett¨a k¨ayt¨amme aakkostoa, jossa on N symbolia.

- suomenkielinen aakkosto,N = 27,

- suomenkielinen aakkosto ja v¨ali, N = 28,

- suomenkielinen aakkosto, v¨ali ja numerot, N = 38, - englanninkielinen aakkosto,N = 26

(¨aja ¨o puuttuvat, w lis¨a¨a).

T¨all¨oin on yksinkertaista asettaa joukon ZN alkiot vastaamaan aakkoston symboleja.

Esimerkiksi suomenkielist¨a aakkostoa vastaa Z₂₇, A= 0, B = 1, ...,O¨ = 26,

miss¨a j¨at¨amme j¨a¨ann¨osluokkien (mod 27) yl¨aviivat pois.

Aikaisemmin tarkastelemamme Caesarin menetelm¨an salausfunktio E_k ja avausfunktio Dk ovat yo. merkinn¨oill¨a yksinkertaisesti

E_k(x) =x+k; D_k(x) =x−k,

miss¨a laskutoimitukset tehd¨a¨an joukossa ZN.

Kuten aikaisemmin totesimme, t¨am¨a j¨arjestelm¨a on helppo murtaa kokeilemalla kaikki avaimet k, joita on N −1 kpl.

Tarkastelemme nyt yleisemp¨a¨a j¨arjestelm¨a¨a, miss¨a yhteenlasku korvataan affiinilla ku- vauksella. T¨at¨a varten valitsemme a ∈ Z^∗_N, b ∈ ZN. Avaimemme on nyt k = (a, b) ja salausfunktio on

E(x) =Ea,b(x) =ax+b.

Avainten lukum¨a¨ar¨a on t¨all¨oin ϕ(N)·N.

Erikoistapaukset:

a= 1⇒Caesar:E(x) =x+b.

b= 0⇒ns. kertolasku Caesar:E(x) =ax.

Selv¨asti E :ZN →ZN on bijektio ja sen k¨a¨anteisfunktio on avausfunktio D:

y =ax+b⇔ax=y−b⇔x=a⁻¹y−a⁻¹b.

Edell¨a a∈Z^∗_N, joten a⁻¹∃. Siis avausfunktio D(y) =Da,b(y) =a⁻¹y−a⁻¹b.

Yhteenveto affiinista j¨arjestelm¨ast¨a:

P =C =ZN.

K ={(a, b)}, miss¨a a∈Z^∗_N ja b∈ZN. Salausfunktio E(x) =ax+b.

Avausfunktio D(y) =a⁻¹y−a⁻¹b.

Affiinin j¨arjestelm¨an murtaminen.

1) Kokeillaan kaikki avaimet.

2) K¨aytet¨a¨an hyv¨aksi kirjainten esiintymistiheyksi¨a (tarvitaan aika pitk¨a salakirjoitusteksti).

Em. j¨arjestelm¨at ovat erikoistapauksia yksinkertaisesta sijoitusj¨arjestelm¨ast¨a. Siin¨a on avainjoukkona ZN:n permutaatioiden muodostama joukko SN, jonka alkiot σ kirjoite- taan usein muotoon

σ =

0 1 . . . N −1 σ(0) σ(1) . . . σ(N −1)

.

N¨am¨a ovat bijektioita, joten niill¨a on k¨a¨anteiskuvaus σ⁻¹. Yksinkertainen sijoitusj¨arjestelm¨a:

P =C =Z_N. K =S_N.

Salausfunktio E(x) =σ(x).

Avausfunktio D(y) =σ⁻¹(y).

Joukon S_N alkioiden lukum¨a¨ar¨a on N!, joten avaimia on runsaasti. Er¨as tapa v¨alitt¨a¨a avain on k¨aytt¨a¨a avainsanaa (sana tai lyhyt lause, josta j¨atet¨a¨an toistuvat kirjaimet pois).

Avainsana Caesar: avain k = (a,avainsana), 0 ≤ a < N. Olkoon a = 4 ja avainsana

”kes¨a meni”

σ ↓ A B C

4

D E F G H I J K L M N O P Q R S

Y Z O K E S A¨ M N I A B C D F G H J L

T U V X Y Z A¨ O¨

O P Q R T U V X ↑σ⁻¹

selv¨a

↓σ

sala

V I D E O Y H T E Y S L U E N T O

Q N K E F T M O E T L B P E D O F

selv¨a

↑σ⁻¹

sala

Yksinkertainen sijoitusj¨arjestelm¨a on murrettavissa kirjainten esiintymistiheyksi¨a tutki- malla, koska kirjaimenxkuvaE(x) on sama koko ajan. T¨ast¨a johtuen on kehitetty my¨os ns. moniaakkosj¨arjestelmi¨a, joista esimerkkin¨a tarkastelemme Vigen´eren j¨arjestelm¨a¨a.

Vigen´ere j¨arjestelm¨an avain koostuu useammasta Caesar j¨arjestelm¨an avaimesta, joita sovelletaan jaksollisesti.

Oletetaan, ett¨a k1, k2, ..., kr ∈ ZN. Jaetaan selv¨akielinen teksti r:n pituisiin osiin x₁, x₂, ..., x_r.Kunkin osani:s kirjainx_isalakirjoitetaan Caesar salausfunktionE_ki avulla, ts,

selv¨a sala

xi →Eki(xi) =xi +ki =yi.

Vastaava avausfunktio on Dk_i(yi) = yi − ki. Avaimet ki annetaan usein avainsanan avulla.

Esimerkki. Suomenkielinen aakkostoZ₂₇.

Salasana ¨OLJY ⇒r= 4 ja k₁ = 26, k₂ = 11, k₃ = 9, k₄= 23.

T¨ass¨a j¨arjestelm¨ass¨a sama kirjain kuvautuu eri kirjaimiksi paikasta riippuen, joten yksinkertainen kirjainten esiintymistiheyteen perustuva analyysi ei toimi. Kuitenkin, jos avaimen pituus r selvi¨a¨a, voidaan kunkin ki murtaa erikseen (kuten Caesarissa).

Avaimen pituuden m¨a¨aritt¨amiseksi on olemassa menetelmi¨a.

2. Salakirjoitus matriiseilla

Jos viestiyksik¨on pituus onr >1 kirjainta, on luontevaa tarkastella viestiyksikk¨oj¨aZ^r_N:n vektoreina ja k¨aytt¨a¨a salauksessa r×r matriiseja. Rajoitumme seuraavassa tapaukseen r= 2.

Kertaamme lyhyesti matriisien laskus¨a¨ant¨oj¨a:

Z²_N:n alkiot ovat x

y

; 2×2 matriisit

a b c d

,

- yht¨asuuruus ⇔ samoilla paikolla olevat alkiot yht¨asuuria, - yhteenlasku

x y

+

u v

=

x+u y+v

;

a b c d

+

x u y v

=

a+x b+u c+y d+v

, - skalaarilla kertominen a

x y

= ax

ay

, u

a b c d

=

au bu cu du

,

- kertolasku

a b c d

x y

=

ax+by cx+dy

, a b

c d

x u y v

=

ax+by au+bv cx+dy cu+dv

, ei vaihdannainen, - yksikk¨omatriisi I =

1 0 0 1

on kertolaskun neutraalialkio, - k¨a¨anteismatriisi: MatriisinA=

a b c d

k¨a¨anteismatriisi on matriisiA⁻¹,jolle AA⁻¹ =A⁻¹A=I,

mik¨ali t¨allainen matriisi on olemassa. Voidaan osoittaa, ett¨a A⁻¹ on olemassa jos ja vain jos D=ad−bc∈Z^∗_N, ja t¨all¨oin

A⁻¹ =D⁻¹

d −b

−c a

.

Esimerkki Z26, A=

2 3 7 8

. M¨a¨arit¨a A⁻¹.

Lause 1. Jos A=

a b c d

, a, b, c, d∈ZN, D=ad−bc∈Z^∗_N, ja B =

e f

∈Z²_N, niin affiini kuvaus

E :Z²_N →Z²_N ; E(X) =AX+B, on bijektio, jonka k¨a¨anteiskuvaus on

D:Z²_N →Z²_N ; D(Y) =A⁻¹(Y −B).

Matriisisalakirjoitus:

P =C =Z²_N ={ x

y

, x, y ∈Z_N}. Avain k ={A, B}, A=

a b c d

, D=ad−bc∈Z^∗_N, B= e

f

∈Z²_N. Salausfunktio E(X) =AX +B.

Avausfunktio D(Y) =A⁻¹Y −A⁻¹B.

Huom. Jos valitsemme A = I =

1 0 0 1

, niin E(X) = X + B, joten kyseess¨a on Vigen´ere j¨arjestelm¨a, miss¨a r = 2. Vastaavasti saamme matriisisalakirjoituksen erikoistapauksena yleisen Vigen´ere j¨arjestelm¨an, jos tarkastelemmer×r matriiseja.

Tarkastelemme nyt matriisisalakirjoituksen murtamista, kun B = 0

0

ja tunnemme kaksi paria selv¨ateksti¨a ja vastaavat salakirjoitukset. T¨am¨a on mahdollista esimerkiksi niin, ett¨a sieppaaja onnistuu jotenkin l¨ahett¨am¨a¨an teksti¨a tarkasteltavan kanavan kautta.

Olkoot tuntemamme selv¨atekstitP1 jaP2ja vastaavat salakirjoituksetC1jaC2. T¨all¨oin C1 =AP1 ja C2 =AP2

eli

C =AP,miss¨a P = (P1, P2) ja C = (C1, C2).

Jos nyt P₁ ja P₂ on valittu niin, ett¨aP⁻¹ on olemassa, niin saamme A=CP⁻¹

ja j¨arjestelm¨a on murrettu.

Tapauksessa B6= 0

0

tarvitsemme murtamiseen viel¨a kolmannen parin P3 ja C3: C₁ =AP₁+B, C₂ =AP₂+B, C₃ =AP₃+B.

T¨all¨oin p¨a¨asemme yo:n kaltaiseen tilanteeseen v¨ahent¨am¨all¨a kolmannen yht¨al¨on kahdesta ensimm¨aisest¨a:

C1−C3 =A(P1−P3), C2−C3 =A(P2−P3).

Jos t¨ast¨a saadaan A, niin sen j¨alkeenB =C₁−AP₁.

IV JULKISEN AVAIMEN SALAKIRJOITUS (PUBLIC KEY CRYPTOGRAPHY)

1. Yleinen periaate

Nykyaikaisissa tiedonv¨alitysj¨arjestelmiss¨a perinteisill¨a salakirjoitusmenetelmill¨a on esi- merkiksi seuraavat ongelmat:

- Avaimista sopiminen ja niiden v¨alitt¨aminen. Jos verkossa on n k¨aytt¨aj¨a¨a, tarvitaan

n 2

=n(n−1)/2 avainta. Jos joku k¨aytt¨aj¨a haluaa vaihtaa avaimensa (tai uusi k¨aytt¨aj¨a liittyy verkkoon), tarvitaan n−1 (tai n) sopimusta uusista avaimista.

-Allekirjoitusongelma, koska normaali allekirjoitus on korvattava jotenkin.

Aikaisemmin, kun salausta k¨aytettiin l¨ahinn¨a sotilaallisissa tai diplomaattisissa tarkoituk- sissa, n¨am¨a seikat eiv¨at tuottaneet suurta ongelmaa.

Vuonna 1976 Diffie ja Hellman esittiv¨at ajatuksen julkisen avaimen j¨arjestelmist¨a, joissa yo. ongelmat on selvitetty. T¨allaisessa j¨arjestelm¨ass¨a kukin k¨aytt¨aj¨a U (user) muo- dostaa oman salausmenettelyns¨a EU ja avausmenettelyns¨aDU,jotka toteuttavat ehdon

(J A 1) DU(EU(m)) =m ∀m∈P (selv¨akieliset viestiyksik¨ot).

Kukin k¨aytt¨aj¨aU julkaisee salausmenettelyns¨aEU avainkirjassa, joka on kaikkien k¨aytet- t¨aviss¨a. Avausmenettely DU pidet¨a¨an vain U:n omana tietona.

Jos k¨aytt¨aj¨a A haluaa l¨ahett¨a¨a selv¨akielisen viestiyksik¨on m k¨aytt¨aj¨alle B, h¨an etsii avainkirjastaB:n salakirjoitusmenettelynEB ja salakirjoittaa sanomansa sen avulla, ts.

c= E_B(m). Kun B saa salakirjoitetun viestin c, h¨an saa sanoman selville k¨aytt¨am¨all¨a (salaista) avausmenettely¨a¨an DB:

DB(c) =DB(EB(m)) =

(J A 1)m.

Jotta menettely olisi toimiva ja salaisuus s¨ailyisi, tarvitsemme seuraavat ehdot, joiden tulee olla voimassa kaikille k¨aytt¨ajilleU:

(J A 2) Menettelyt EU ja DU ovat nopeita eiv¨atk¨a tarvitse liian paljon muistia.

(J A 3) On k¨ayt¨ann¨oss¨a mahdotonta m¨a¨aritt¨a¨aEU:n avulla menettely¨aD_U^∗, jolle D_U^∗(EU(m)) =m ∀m∈P.

Ominaisuus (J A 3) s¨ailytt¨a¨a j¨arjestelm¨an salaisena ja mahdollistaa salausmenettelyn julkaisemisen avainkirjassa. Jos joku k¨aytt¨ajist¨a vaihtaa avaimensa, riitt¨a¨a vaihtaa uusi EU avainkirjaan. Uuden k¨aytt¨aj¨an mukaantulo on yht¨a yksinkertaista.

Em. menettely muodostetaan usein k¨aytt¨am¨all¨a yksisuuntaista funktiota tai salaovi- funktiota.

M¨a¨aritelm¨a. Funktio f on yksisuuntainen, jos sen arvot ovat helposti laskettavissa ja k¨a¨anteisfunktion f⁻¹ (joka ∃) m¨a¨ar¨a¨aminen on hyvin vaikeaa. Salaovifunktio on sellainen yksisuuntainen funktio, jonka k¨a¨anteisfunktio on helppoa m¨a¨ar¨at¨a jonkin lis¨atiedon (salaovi) avulla.

Funktiota ei yleens¨a onnistuta todistamaan yksisuuntaiseksi, joten joudutaan k¨ayt- t¨am¨a¨an funktioita, joiden uskotaan olevan yksisuuntaisia. T¨allaisten funktioiden muo- dostaminen perustuu usein vaikeisiin ja paljon tutkittuihin lukuteorian ongelmiin, esi- merkiksi RSA-j¨arjestelm¨ass¨a suurten lukujen tekij¨oiden jakamisen vaikeuteen. Jos meill¨a on k¨ayt¨oss¨amme salaovifunktioita fU,niin voimme muodostaa ehdot (J A 1),(J A 2) ja (J A 3) toteuttavan j¨arjestelm¨an valitsemalla

EU =fU ja DU =f_U⁻¹.

Tarkastelemme nyt allekirjoitusongelmaa, jonka ratkaisemiseksi asetamme kaksi uutta vaatimusta, joiden tulee olla voimassa kaikille k¨aytt¨ajilleU.

(J A 4) EU(DU(c)) =c ∀c∈C.

(J A 5) On k¨ayt¨ann¨oss¨a mahdotonta m¨a¨aritt¨a¨aEU:n avulla menettely¨aD_U^∗, jolle EU(D^∗_U(c)) =c∀c∈C.

Julkisen avaimen j¨arjestelm¨ass¨a on useinP =Csama kaikilla k¨aytt¨ajill¨a. JosAl¨ahett¨a¨a B:lle selv¨akielisen viestin, h¨an l¨ahett¨a¨a allekirjoituksen s muodossa m=DA(s), jolloin B etsii avainkirjastaE_A:n ja laskee

EA(m) =EA(DA(s) =

(J A 4)s.

Allekirjoituksen muodostaa pari (s, DA(s) =m). Menettely edellytt¨a¨a ehtoja (J A2),(J A4) ja (J A 5), erityisesti ehto (J A 5) varmistaa, ett¨a vain A voi toimia l¨ahett¨aj¨an¨a. A ei voi my¨osk¨a¨an j¨alkik¨ateen kielt¨a¨a viesti¨a.

A

s −→ DA(s) =m −→^m m −→^B EA(m) =s

↑E_A Allekirjoitus on pari (s, D_A(s) =m) Avainkirja

Eo. menettely voidaan toteuttaa salaovifunktiollaf valitsemallaEA=f, DA=f⁻¹. Jos halutaan suorittaa salakirjoitus ja allekirjoitus, tarvitaan ominaisuudet (J A 1)− (J A 5). T¨all¨oin A muodostaa allekirjoitusosasta s tekstin c = E_B(D_A(s)). B soveltaa t¨ah¨an funktiota EA◦DB :

EA(DB(c)) =EA(DB(EB(DA(s)))) =EA(DA(s)) =s.

EA l¨oytyy avainkirjasta, mutta vain B tuntee DB:n ja voi m¨a¨aritt¨a¨a s:n. B k¨aytt¨a¨a A:n allekirjoituksena paria (s, DB(c) =DA(s)) kuten edell¨a.

A

s −→ EB(DA(s)) =c −→ c −→^B EA(DB(c)) =s

↑EB ↑EA

−→ Avainkirja−→

Koska julkisen avaimen salakirjoitus vaatii yleens¨a paljon enemm¨an aikaa kuin perin- teiset menetelm¨at, sit¨a k¨aytet¨a¨an usein perinteisen menetelm¨an ohella avainten vaih- dossa, ts. k¨aytett¨av¨an perinteisen menetelm¨an avaimet vaihdetaan julkisen avaimen menetelm¨all¨a.

2. RSA-menetelm¨a

(1978, Rivest, Shamir ja Adleman)

RSA-menetelm¨ass¨a salaovifunktion muodostaminen perustuu vuosisatoja tutkittuun lukuteorian ongelmaan: Kuinka annettu (suuri) luku n jaetaan alkutekij¨oihin? Yk- sisuuntaisen funktion perusta on nyt se, ett¨a annettujen lukujen tulo on nopeasti las- kettavissa, mutta tekij¨oiden l¨oyt¨aminen tulosta vaatii nopeiltakin koneilta liikaa aikaa.

Olkoot nyt p ja q kaksi alkulukua ja n= pq.T¨all¨oin ϕ(n) = (p−1)(q−1). Valitsemme nyt sellaisen luvun e, 1 < e < ϕ(n), ett¨a syt(e, ϕ(n)) = 1 (mik¨a tahansa alkuluku e v¨alilt¨a max{p, q} < e < ϕ(n) k¨ay). Eukleideen algoritmin avulla l¨oyd¨amme ehdon 1 < d < ϕ(n) toteuttavan luvun d, jolle ed ≡ 1 (mod ϕ(n)). T¨all¨oin ed = 1 +`ϕ(n) er¨a¨all¨a `∈N.

Eulerin lauseeseen nojautuen saamme seuraavan lauseen.

Lause 1. Kaikilla a∈Z_n on a^ed =a.

Olkoon nyt f : Zn → Zn, f(a) = a^e, ja g : Zn → Zn, g(a) = a^d. T¨all¨oin g = f⁻¹ Lauseen 1 perusteella ja molempien funktioiden arvot ovat nopeasti laskettavissa potenssiin korotuksella (mod n), kun e ja d tunnetaan. Jos nyt n ja e tunnetaan, niin f(a) on laskettavissa, mutta d:n laskeminen ei onnistu ilman lukua ϕ(n), jonka l¨oyt¨aminen edellytt¨a¨a p:n ja q:n tuntemista eli n:n tekij¨oihinjakoa. Luku d on siis salaovi, jota ilman f⁻¹ ei l¨oydy, ts. f on salaovifunktio.

RSA-j¨arjestelm¨ass¨a kukin k¨aytt¨aj¨a U valitsee yo:n tapaan alkuluvut pU ja qU, laskee luvun nU =pUqU, valitsee sitten luvuneU, 1< eU < ϕ(nU), eUdU ≡1 (mod ϕ(nU)).

Avainkirjassa kukin k¨aytt¨aj¨a julkaisee avaimensa KU = (nU, eU), mutta pit¨a¨a omana tietonaan luvun dU (ja luvut pU, qU), joka muodostaa salaoven.

Kun k¨aytt¨aj¨a A haluaa l¨ahett¨a¨a viestin k¨aytt¨aj¨alle B, h¨an muuntaa viestins¨a Zn_B:n alkioiksi (seuraavassa esitett¨av¨all¨a tavalla) ja toimii eo. yleisen periaatteen mukaisesti.

Alkion m∈ZnB salakirjoitus on E_B(m) =m^eB =c∈Z_nB.

Vain B tiet¨a¨a luvun d_B, joten h¨anen avausfunktionsa on DB(c) =c^dB =m^eBdB =m.

Allekirjoitus onnistuu my¨os yleisen periaatteen mukaisesti, Al¨ahett¨a¨a allekirjoituksensa s muodossa DA(s) =s^dA =m∈Zn_A. Pari (s, m) muodostaa allekirjoituksen.

Jos halutaan salaus ja allekirjoitus, niin voimme toimia yleisen periaatteen mukaisesti, jos n_A < n_B.

T¨all¨oin A laskee ensin s^dA(mod nA) = m (a(mod n) =x, 0 ≤ x < n, x ≡ a(mod n)) ja sitten m^eB(mod n_B) =c,ts. salattu allekirjoitus on

c= (s^dA(mod nA))^eB(mod nB).

Saatuaan c:n B laskee ensin

c^dB(mod n_B) =m^eBdB(mod n_B) =m ja sitten

m^eA(mod n_A) =s^dAeA(mod n_A) =s.

T¨am¨a menettely ei toimi, jos n_B < n_A, koska t¨all¨oin voisi m(mod n_B) olla sama use- ammalla arvolla m. Jos nB < nA, vaihdetaan j¨arjestyst¨a: A laskee ensin s^eB(mod nB) =m1 ja sitten m^d₁^A(mod nA) =c eli

c= (s^eB(mod nB))^dA(mod nA).

VastaavastiBavaac:n laskemalla ensinc^eA(modnA) =m1, ja sittenm^d₁^B(modnB) =s.

3. Tekstin esitt¨aminen Z_n:n alkioina

Edell¨a olemme muuntaneet N:n symbolin aakkoston yleens¨a luvuiksi 0,1, ..., N −1, jotka voidaan tulkita my¨os Z_N:n alkioiksi. Esimerkiksi RSA j¨arjestelm¨ass¨a toimitaan joukossa Zn, miss¨anon suuri. Jos jaammeN-aakkostolla kirjoitetun tekstink-pituisiin osiin a = a₁, a₂, ..., a_k, 0 ≤ a_i < N, voidaan jokainen t¨allainen osa esitt¨a¨a k¨a¨ant¨aen yksik¨asitteisestiN-kantaisessa j¨arjestelm¨ass¨a muodossa

a=a₁N^k−1+a₂N^k−1+...+a_k.

Nyta≤N^k−1,joten jos valitsemmek:n niin, ett¨aN^k ≤n,niinN-aakkostonkpituiset sanat voidaan esitt¨a¨a k¨a¨ant¨aen yksik¨asitteisestiZn:n osajoukkona luonnollisella tavalla.

Jos taas n≤N<sup>`</sup>, niin jokaista Zn:n alkiota vastaa er¨as N-aakkoston `-pituinen sana.

Jos siis k¨ayt¨amme RSA-j¨arjestelm¨a¨a ja jokainen k¨aytt¨aj¨a U valitsee lukunsa nU niin, ett¨a

N^k ≤nU ≤N<sup>`</sup>, k, `∈N,

niin kaikki k¨aytt¨aj¨at voivat valita

P ={k−kirjaimiset sanat} ⊂ZnU

C =Z_nU ⊂ {`-kirjaimiset sanat}. Esimerkki.

4. Diskreetti logaritmi

Reaalilukujen joukossa lukujen b^x ja log_bx laskeminen tietyll¨a tarkkuudella on yht¨a helppoa. Tarkastelemme nyt vastaavaa tilannetta joukossa Z^∗_n. Jos b ∈ Z^∗_n, niin b^x on laskettavissa nopeasti suurillakin x ∈ N. Oletamme nyt, ett¨a tied¨amme alkion y ∈Z^∗_n olevan muotoa y = b^x. Kuinka x = log_by saadaan selville (t¨ass¨a logaritmi on ns.

diskreetti logaritmi, ei R:n logaritmifunktio)? T¨alle ns. ”diskreetin logaritmin ongel- malle” ei tunneta nopeaa ratkaisua yleisess¨a tapauksessa, joten voimme j¨alleen rakentaa yksisuuntaisen funktio.

M¨a¨aritelm¨a. Luku g, 1≤g≤n−1, on primitiivijuuri (mod n), jos Z^∗_n ={¯g^k|k= 0,1, ..., ϕ(n)−1}={¯1,g,¯ ¯g², ...,¯g^ϕ(n)−1}.

Esimerkki.

Lause 2. Primitiivijuuri (mod n) on olemassa jos ja vain jos n on 2,4, p^{`</sup>,2p<sup>`}, `= 1,2, ..., miss¨a p >2 on alkuluku.

Jos g on primitiivijuuri (mod n) (n on L2:n muotoa), niin sen m¨a¨ar¨a¨am¨a¨a j¨a¨ann¨oslu- okkaa sanotaan Z^∗_n:n primitiiviseksi alkioksi.

M¨a¨aritelm¨a. Olkoon g∈Z^∗_n primitiivinen. Alkion y∈Z^∗_n diskreetti logaritmi kannan g suhteen on sellainen luku k ∈ {0,1, ..., ϕ(n)−1}, jolle y = g^k. T¨all¨oin merkitsemme k = log_gy.

Usein valitsemme edell¨a n=p (alkuluku), jolloin Z_p on ¨a¨arellinen kunta.

5. Diffie-Hellman avaimenvaihto

Oletamme t¨ass¨a, ett¨a joukossa Z^∗_n on primitiivinen alkio g. Tiedonsiirtoj¨arjestelm¨an avaimen vaihtomenettely voidaan hoitaa seuraavasti:

Kaikki k¨aytt¨aj¨at tuntevat luvunnja primitiivialkiong. Kukin k¨aytt¨aj¨aU valitsee luvun mU ∈ {1, ..., ϕ(n)−1}ja laskeeg^mU, jonka h¨an julkaisee. K¨aytt¨ajien AjaB keskin¨aisen yhteydenpidon avaimen m¨a¨ar¨a¨a g^mAmB.

K¨aytt¨aj¨a Asaa avaimen potenssiinkorotuksella (g^mB)^mA =g^mAmB ja k¨aytt¨aj¨a B vas- taavasti (g^mA)^mB =g^mAmB.

Sieppaaja tuntee vain alkiotg^mA ja g^mB. Jos h¨an ratkaisisi diskreetin logaritmin ongel- man, ts. mA:n tai mB:n, avain l¨oytyisi. Muuten sen l¨oyt¨aminen ei ilmeisesti onnistu (g^mAg^mB =g^mA+mB).

Esimerkki.

6. El Gamal salakirjoitusj¨arjestelm¨a

Olkoon b ∈ Z^∗_p annettu (yleens¨a valitaan b primitiivialkioksi, mutta se ei ole v¨alt- t¨am¨at¨ont¨a). Kaikki k¨aytt¨aj¨at tuntevat p:n ja b:n. Lis¨aksi oletamme, ett¨a P =C =Z^∗_p (tai jotkin osajoukot).

Kukin k¨aytt¨aj¨a U valitsee luvun mU ∈ {1,2, ..., p−2} ja pit¨a¨a sen omana tietonaan.

Julkiseen avainkirjaan annetaan b^mU ∈Z^∗_p.

Jos joku k¨aytt¨aj¨a haluaa l¨ahett¨a¨a viestin m ∈ Z^∗_p k¨aytt¨aj¨alle A, h¨an valitsee k ∈ N ja l¨ahett¨a¨a parin

(b^k, mb^mAk)∈Z^∗_p².

Koska b^mAk = (b^mA)^k ja b^mA on avainkirjassa, on pari laskettavissa nopeasti potenssiinkorotuksella. K¨aytt¨aj¨a A (ja vain h¨an) tuntee luvun mA, joten h¨an laskee parin ensimm¨aisen komponentin avulla (b^k)^mA = b^mAk. Jakamalla n¨ain saadulla alki- olla toisen komponentin A saa

mb^mAk b^mAk =m.

Jos sieppaaja ratkaisee diskreetin logaritmin ongelman, on murtaminen helppoa. Muuten on ilmeisesti vaikea saada b^mAk alkioista b^k ja b^mA.

Edell¨a viesti m on naamioitu alkion b^mAk avulla ja ensimm¨ainen komponentti on johtolanka b^k, jonka avullaA (ja vain h¨an) voi riisua naamion.

7. Selk¨areppuongelma

Oletetaan, ett¨a k positiivista kokonaislukua sis¨alt¨av¨a joukko {v1, v2, ..., vk} ja posi- tiivinen kokonaisluku V on annettu. Kysyt¨a¨an, onko olemassa sellainen osajoukko I ⊂ {1,2, ..., k}, ett¨a

X

i∈I

vi =V.

(Jos sekk¨arepun tilavuus on V ja on k esinett¨a, joiden tilavuudet ovat v1, v2, ..., vk, niin voidaanko reppu pakata n¨aill¨a esineill¨a tasan t¨ayteen?) T¨am¨a kysymys on ns.

selk¨areppuongelma. Se voidaan muotoilla my¨os seuraavasti:

Selk¨areppuongelma. Olkoot v1, v2, ..., vk ja V annettuja positiivisia kokonaislukuja.

Onko olemassa sellaiset luvut ε_i ∈ {0,1}, i= 1, ..., k, ett¨a ε1v1+ε2v2+...+εkvk =V?

Esimerkki.

Josk on suuri, niin on osoitettu, ett¨a selk¨areppuongelma on yleisess¨a tapauksessa hyvin vaikea ratkaista. Er¨aiss¨a erikoistapauksissa ongelma on kuitenkin helppo ratkaista.

M¨a¨aritelm¨a. k-jono v₁, v₂, ..., v_k on superkasvava, jos ∀ j = 2, ..., k vj > v1+...+vj−1.

Vastaava selk¨areppua sanotaan my¨os superkasvavaksi.

Esimerkki.

Superkasvava selk¨areppu on helppo ratkaista seuraavasti: {v1, v2, ..., vk} superkasvava, V.

Jos v₁ +v₂ +...+v_k < V, ratkaisua ei ole. Oletamme, ett¨a V ≤ v₁ +v₂ +...+v_k. Mahdollisessa ratkaisussa ε1, ε2, ..., εk on

εk = 1, jos ja vain jos V ≥vk;

t¨am¨an j¨alkeen saamme rekursiivisesti kaikilla j =k−1, k−2, ...,1 εj = 1 jos ja vain jos V −(εkvk+...+εj+1vj+1)≥vj.

N¨ain saamme luvutε1, ε2, ..., εk∈ {0,1}.JosV =ε1v1+ε2v2+...+εkvk,niin selk¨areppu ratkeaa ja ε1, ε2, ..., εk on ratkaisu, muuton selk¨areppu ei ratkea.

Esimerkki.

8. Selk¨areppuj¨arjestelm¨a

Sovitaan, ett¨a selv¨akieliset viestiyksik¨ot ovat bin¨a¨arilukuja, joiden pituus on≤k (t¨ah¨an p¨a¨ast¨a¨an k¨aytt¨am¨all¨a aakkostolle lukuvastineita ja muuntamalla tietty¨a kirjainm¨a¨ar¨a¨a vastaava luku bin¨a¨ariluvuksi). Tyypillinen selv¨akielinen viestiyksikk¨o on

m= (m₁m₂...m_k)₂ =m₁2^k−1+m₂2^k−1+...+m_k, m_i ∈ {0,1}. Esimerkki.

Kukin k¨aytt¨aj¨a U valitsee superkasvavan k-jonon u1, u2, ...uk ja sellaiset kokonaisluvut nU ja aU, ett¨a

(1) nU > u₁+u₂+...+u_k, 1< aU < nU, syt(aU, nU) = 1.

T¨am¨an j¨alkee U m¨a¨aritt¨a¨a (Eukleideen algoritmilla) luvun bU, jolle (2) aUbU ≡1 (mod nU) (ts. a⁻¹_U =bU Z^∗_nU:ss¨a).

Seuraavaksi k¨aytt¨aj¨a U laskee k-jonon u^∗_i =aUu_i(mod nU), i= 1,2, ..., k.

U-pit¨a¨a luvutui, nU, aU jabU vain omana tietonaan, mutta julkaiseek-jononu^∗₁, u^∗₂, ..., u^∗_k avaimenaan, ts. KU = {u^∗₁, u^∗₂, ..., u^∗_k}. Jos joku haluaa l¨ahett¨a¨a U:lle viestin m = (m1m2...mk)2, h¨an k¨aytt¨a¨a salausfunktiota

EU(m) =m1u^∗₁+m2u^∗₂ +...+mku^∗_k =c,

joka on helppoa laskea avaimesta KU. Avausmenettely DU koostuu kahdesta osasta.

Salaoven muodostaa luku bU, jonka U tuntee. Ensimm¨aisess¨a vaiheessa U laskee (2):n avulla

bUc≡bU(m1auu1+m2aUu2+...+mkaUuk)

≡m1u1+m2u2+...+mkuk(mod nU).

Ehdon (1) mukaisesti yo. kongruenssista seuraa yht¨al¨o m1u1+m2u2+...+mkuk =bUc (mod nU).

Toisessa vaiheessa ratkaistaan t¨am¨a superkasvava selk¨areppu ja saadaanm= (m1m2...mk)2. Kun Ahaluaa l¨ahett¨a¨a sanoman m= (m₁m₂...m_k)₂ B:lle, toimitaan seuraavasti:

Menettelyn idea on luonnollisesti siin¨a, ett¨aB:n superkasvava jonob1, b2, ..., bksotketaan kertomalla a_B:ll¨a B:n avainjonoksi b^∗₁, b^∗₂, ..., b^∗_k, joka ei ole superkasvava. Sieppaajan tulisi salakirjoituksen murtamiseksi ratkaista t¨am¨an jonon avulla muodostettu yleiselt¨a n¨aytt¨av¨a selk¨areppuongelma m₁b^∗₁ +m₂b^∗₂+...+m_kb^∗_k =c.

Yo:n j¨arjestelm¨an esittiv¨at vuonna 1978 Merkle ja Hellman ja se saavutti yksinker- taisuutensa ja nopeutensa takia suuren suosion. Kuitenkin Shamir onnistui murta- maan menetelm¨an jo vuonna 1982. My¨os menetelm¨an parannuksia on murrettu, joten selk¨areppuj¨arjestelm¨a¨a ei pidet¨a kovin luotettavana.

9. Huomautuksia

Edell¨a emme ole k¨asitelleet esiteltyjen julkisen avaimen j¨arjestelmien heikkouksia, esim.

murtamismahdollisuuksia. RSA:ta pidet¨a¨an varsin turvallisena, kun p ja q ovat riit- t¨av¨an suuria (≈150 numeroa) sek¨a niiden valinnassa otetaan huomioon er¨ait¨a rajoituk- sia. Samoin diskreetti logaritmi lienee luotettava, kun kuntaZp (tai yleisempi ¨a¨arellinen kunta) on riitt¨av¨an suuri. Voimme my¨os kysy¨a t¨asm¨allisemp¨a¨a tietoa eri menetelmien vaatimien laskutoimitusten m¨a¨arist¨a (tarvittavasta ajasta). Luonnollisesti tulee esille my¨os kysymys siit¨a, miten esim. RSA:n tarvitsemia suuria alkulukuja on l¨oydett¨aviss¨a.

Syvent¨avien opintojen kurssilla ”Kryptografia” tarkastellaan l¨ahemmin n¨ait¨a kysymyk- si¨a sek¨a esitell¨a¨an menetelmi¨a, jotka vaativat syv¨allisempi¨a matematiikan tietoja.

HARJOITUSTEHT ¨AV ¨AT:

1. Yst¨av¨asi K l¨ahett¨a¨a sinulle Caesarin yhteenlaskumenetelm¨all¨a kirjoitetun viestin

” ¨O H X H H T T L O H U P S S H S S H R”.

Avaa viesti.

2. Avaa seuraava Caesarin yhteenlaskumenetelm¨all¨a laadittu englanninkielinen salakir- joitus

A L Y U N Y M N W I G G I H X C P C M I L.

Mik¨a on ollut avain?

3. Jaa luvut

211, 212, 213, 721

alkutekij¨oihin. M¨a¨arit¨a my¨os lukujen bin¨a¨ariesitykset.

4. Esit¨a luku 1995

a) 5-kantaisessa, b) 8-kantaisessa,

c) 32 kantaisessa lukuj¨arjestelm¨ass¨a.

5. Laske 2123·1223.

6. Tarkastellaan 26-kantaista j¨arjestelm¨a¨a, miss¨a englanninkieliset aakkosetA−Z esit- t¨av¨at numeroita 0-25. Laske (Y ES)·(N O).

7. M¨a¨ar¨a¨a lukujen a) 101, 3040 b) 1690, 650 suurin yhteinen tekij¨a.

8. Etsi sellaiset kokonaisluvut x ja y, ett¨a 213x−89y= 1,

1≤x, y≤212.

9. Todista jaollisuuss¨a¨ann¨ot luvuille 2, 3, 5, 9 ja 11.

10. Ratkaise kongruenssit a)3x≡4 (mod 7), b) 14x≡1 (mod 27), c) 2x≡1 (mod p), miss¨a p≥3 on alkuluku.

11. Ratkaise kongruenssit

a) 5x≡1 (mod 7) ja (mod 5), b) 3z ≡3 (mod 3) ja (mod 9), c) 4x² ≡2 (mod 7).

12. Kirjoita yhteen- ja kertolaskutaulut joukoille Z7 ja Z8.

13. Laske a⁻¹, kun

a) a= 15∈Z₁₇, b) a= 16∈Z₁₉, c) a= 3∈Z₉.

14. Laske

4¹⁰ (mod 5), 5¹⁰¹ (mod 25), 101¹⁰¹ (mod 3), 101¹⁰¹ (mod 9), 15⁵⁵ (mod 91) ja 2^1000000 (mod 77).

15. K¨aytet¨a¨an suomenkielist¨a aakkostoa t¨aydennettyn¨a tyhj¨all¨a v¨alill¨a (=27) ja affiinia j¨arjestelm¨a¨a, jonka avain on (5,24). Salakirjoita teksti ”T U LKAA AP U U N”.Mik¨a on avausfunktio?

16. Seuraava teksti on muodostettu affiinilla j¨arjestelm¨all¨a:

V CLM P CAV ESV F Y DV OV IZHP CY XAXGBDAT Y Z.

Mik¨a on selv¨akielinen teksti?

17. Teht¨av¨asi on selvitt¨a¨a affiinilla j¨arjestelm¨all¨a tehty salakirjoitus, jossa k¨aytet¨a¨an 37- kirjaimista aakkostoa, jonka kirjaimet ovat luvut 0-9 (vastaavat lukuja 0-9), englan-

ninkieliset aakkosetA−Z (vastaavat lukuja 10-35) ja tyhj¨a (=36). Salakirjoitusteksti on

OH7F86BB46R3627O266BB9.

Tied¨at, ett¨a sanoman on l¨ahett¨anyt ”007”. Mik¨a on sanoma?

18. Ovatko funktiot

a) σ(i) =i+ 17, b) σ(i) = 17i

permutaatioita joukossa Z₂₆?

19. Laske Caesarin yhteenlasku- ja kertolaskumenetelmien sek¨a affiinin j¨arjestelm¨an suh- teelliset osuudet kaikista yksinkertaisista sijoitusj¨arjestelmist¨a, kunN=26, 27, 28 ja yleisess¨a tapauksessa.

20. K¨aytet¨a¨an avainsana Caesaria, jonka avain on (5,SY Y SKU U). Salakirjoita teksti SY KSY ON T U LLU T.

21. Salakirjoita teksti

DOES SU RJ ECT ION BECOM E IN J ECT ION Vigen´eren j¨arjestelm¨all¨a, kun avainsana on IN J ECT ION.

22. Valitse jokin 2. pituinen avain Vigen´eren j¨arjestelm¨ass¨a. Salakirjoita jokin 25-30 merkki¨a pitk¨a teksti. Anna se toiselle harjoitusryhm¨an j¨asenelle murrettavaksi.

23. Seuraavien matriisien alkiot ovat joukon Z_N alkioita. M¨a¨arit¨a A⁻¹, kun a) A=

1 3 4 3

, N = 5; b)A=

15 17

4 9

, N = 26; c) A=

3 6 2 5

, N = 28.

24. K¨ayt¨amme suomenkielist¨a aakkostoa, miss¨a A− O¨ on 0-26 ja tyhj¨a=27, joten N = 28. Salakirjoita matriisisalakirjoituksella k¨aytt¨am¨all¨a edellisen teht¨av¨an c)- kohdan matriisia AtekstiY HT EY S T OIM II.

25. K¨ayt¨amme englanninkielist¨a aakkostoa, miss¨a A−Z on 0-25, tyhj¨a=26, ?=27 ja

!=28, jotenN=29. Saat matriisisalakirjoituksella (miss¨aB = 0

0

) tehdyn sanoman

GF P Y J P X?U Y XST LADP LW

ja tied¨at, ett¨a viisi viimeist¨a kirjainta on l¨ahett¨aj¨an nimi KARLA. Avaa sanoma.

26. Oletetaan, ett¨a n = pq, miss¨a p ja q ovat erisuuria alkulukuja. Osoita, ett¨a luvun ϕ(n) tunteminen on yht¨apit¨av¨a¨a tekij¨oiden p ja q tuntemisen kanssa.

27. Salakirjoita teksti SELKAREP P U¨ RSA-j¨arjestelm¨an avaimella (n, e) = (91,11).

Murra t¨am¨a salausmenettely m¨a¨ar¨a¨am¨all¨a salaovi d.

28. Laske tulot

117·103, 7008·6992

k¨aytt¨aen kaavaa (a+b)(a−b) =a²−b². Esit¨a seuraavat luvut 250997, 1689999

ainakin kahden tekij¨an tulona.

29. a) Salakirjoita teksti TAKE IT AWAY RSA-j¨arjestelm¨an avaimella (n, e)=

(2773, 17) muuntamalla se ensin 2 kirjaimen osissa Zn:n alkioiksi.

b) Murra a)-kohdan salausmenettely m¨a¨ar¨a¨am¨all¨a salaovi d.

c) Avaa a)-kohdan salakirjoitus ja totea, ett¨a saat alkuper¨aisen tekstin.

30. Tietoverkon k¨aytt¨ajienAjaBRSA-avaimet ovat (n_A, e_A) = (2773,17) ja (n_B, e_B) = (2047,179). Miss¨a muodossa A l¨ahett¨a¨a allekirjoituksensa AK B:lle? Ent¨a salattu allekirjoitus? Selvit¨a samat kysymyksetB:n l¨ahett¨aess¨a allekirjoituksensaBG A:lle.

31. a) M¨a¨arit¨a primitiivijuuri (mod n), merkit¨a¨an g, kun n=3, 4, 5, 6, 7, 9, 10, 11.

b) Laske tapauksissan=5, 9 ja 11 Z^∗_n:ss¨a logg(−k), kun k=1,2.

32. M¨a¨arit¨a Z^∗₂₅:n primitiivinen alkio g ja laske log_g(−1), log_g2 ja log_g3.

33. Osoita, ett¨a 2 on kunnan Z₃₇ primitiivinen alkio ja laske log2 28, log2 8, log2 (-10).

34. Olkoon n=37 ja g=2. Diffie-Hellman avaimenvaihdossa k¨aytt¨aj¨anAsalainen ekspo- nentti mA=18 ja k¨aytt¨aj¨anB mB=23. Mitk¨a ovat A:n ja B:n julkaisemat alkiot ja mik¨a on yhteinen avain?