Oppikerta 6, 16.2.1999

(1) Abadi-Needham (jatko)

(2) Julkisen avaimen protokollien erityispiirteitä

1. Allekirjoita ennen salausta (Abadi-Needhamin 5. periaate)
2. Ole perillä siitä, mikä (avaintieto) erottaa oliot toisistaan. Saman avaimen käyttöä eri tarkoituksiin kannattaa välttää. Saman protokollan eri ajot pitää voida erottaa.
3. Varmistu siitä ettei vastustaja voi käyttää allekirjoitustasi tai salauksen purkuasi oraakkelina, ts. hän ei saa sinua suorittamaan näitä operaatioitasi mille tahansa syötteelle siten, että hän saa jonkin haluamansa asian lasketuksi sinun avullasi.
4. Pidä lukua biteistä: minkä tehtävänä on toteuttaa "ekvivokaatiota" (monimerkityksisyyttä), minkä redundanssia ja minkä laskennallista monimutkaisuutta. Redundanssin pitää perustua tukevasti sovellusyhteyteen eikä lisäbittejä saa voida käyttää sinua vastaan.
5. Älä oleta kenenkään muiden "salaisuuksien" olevan salaisia - lukuunottamatta varmenneviranomaista (johon tyypillisesti pitää voida luottaa).
6. Älä oleta saamasi viestin olevan mitään erityistä muotoa, ellet voi tarkistaa tätä.
7. Kryptoprimitiivien (parametrien) rajat pitää selvittää: montako avainta tietyllä algoritmilla kannattaa enintään generoida, kuinka suuren salaliiton kynnysprotokolla sallii, montako blokkia tietyllä algoritmilla voi salata.
8. Vankka turvallisuus perustuu eksplisiittisyyteen: pitää olla selvillä kaikista erityisominaisuuksista, joita voi käyttää julkisen avaimen primitiivin vastaiseen hyökkäykseen: Tällaisia voivat olla erityiset yhtälöt (esim. multiplikatiivinen homeomorfismi) sekä yleiset turvaominaisuudet, kuten nimeäminen, tyypitys, tuoreus sekä alkuoletukset ja tavoiteltavat tulokset.

(3) Lisää allekirjoituksesta

• peruskäsitteiden luokittelua.
• joitakin uusia esimerkkejä allekirjoitusalgoritmeista
• erityistilanteita ja niihin soveltuvia allekirjoituksia (ei tällä kerralla).

Luokitusta

• voidaanko koko viesti purkaa allekirjoituksesta (viestinpalautus, 'message recovery': RSA, Rabin, Nyberg-Rueppel): vai onko allekirjoitus viestin liite ja itse viesti tarvitaan todennuksessa ('appendix': DSA, ElGamal, Schnorr, Feige-Fiat-Shamir, Guillou-Quisquater)
• onko allekirjoitus deterministinen vai satunnaistettu (=samasta viestistä voi samoilla avaimilla eri kerroilla tulla eri allekirjoitus)

Systeemiä, jossa viestin palautus on mahdollinen, voidaan käyttää samaan tapaan kuin liiteallekirjoitusta (ja usein näin tehdäänkin). Jos näin ei tehdä, tarvitaan sellaista muunnosta, jolla viestiin lisätään redundanssia ennen allekirjoitusta (esim. viesti toistetaan eli M:n sijasta onkin MM). Tällöin verifioija tuleekin palauttaneeksi ensin redundantin viestin ja hyväksymiskriteerinä toteaa onko redundanssi sellaista kuin pitääkin ja vasta sitten suorittaa käänteismuunnoksen alkuperäiseksi viestiksi. Redundanssifunktioita esitellään hieman myöhemmin.

ElGamal ja Rabin allekirjoittajina; DSA

Viestin M allekirjoittaminen:

• valitaan salassa pidettävä satunnaisluku k, syt(k,p-1)=1
• lasketaan a = g^k(mod p)
• ratkaistaan sellainen luku b että M = x*a + k*b (mod p-1). Tämä tapahtuu laskemalla b = k^-1(M-x*a) (mod p-1), missä k:n käänteisluku modulo p-1 on olemassa koska k on suhteellinen alkuluku mod p-1.
• allekirjoitus on (a,b) (joka on kaksi kertaa viestin mittainen)

Vastaavasti Rabinin julkisen avaimen salausalgoritmista saadaan allekirjoitusalgoritmi: allekirjoitus on oleellisesti viestin neliöjuuri. Sen pystyy laskemaan vain osapuoli, joka tuntee modulin n tekijät p ja q.

DSA on DSS-standardin käyttämä algoritmi, joka muistuttaa ElGamalin allekirjoitusta, mutta parametrien valinta tehdään Schnorrin periaatteiden mukaan (1991, -93, -96)

1. valitse 160-bittinen alkuluku q.
2. valitse sellainen 521-1024 -bittinen alkuluku p, että (p-1)/q menee tasan.
3. valitse satunnainen h ja laske g = h^(p-1)/q mod p (Jos tulos olisi = 1 valitse uudestaan)
4. valitse satunnainen k ja laske y = g^k mod p.
5. Julkinen avain on nelikko (p,q,g,y).

Viestin M allekirjoittaminen (H on tiivistefunktio):

• valitaan salassa pidettävä satunnaisluku k, 0<k<q.
• lasketaan a = ( g^k mod p ) mod q, ts. redusoidaan ensin p:n suhteen ja sitten vielä q:n suhteen.
• lasketaan b = k^-1(H(M)+x*a) mod q.
• allekirjoitus on (a,b)

Fiat-Shamirin algoritmissa suoritetiin nollatietotunnistus käyttäen periaatetta "sitoutuminen-haaste-vaste". Korvaamalla todentajan lähettämä haaste viestistä laskettavalla tiivisteellä saadaan aikaan allekirjoitusalgoritmi (Feige-Fiat-Shamir). Sama muunnos toimii muissa vastaavissa nollatietoalgoritmeissa.