Oppikerta 9, 16.3.1999

• erityistyyppisiä allekirjoituksia; lähinnä tilanteita, ei niinkään itse algoritmeja.
• sokean allekirjoituksen sovelluksena anonyymi sähköraha. Samalla hieman yleistä pohdintaa yhtäältä sähköisestä maksamisesta ja toisaalta anonymiteetistä.

Lisää allekirjoituksesta (jatkoa oppikerralta 6)

Redundanssifunktioita [HAC 442-445 #PKCS1]

viesti (jonka oletetaan olevan rajoitetun mittainen)
--> täydennys (alkunollilla 8:n monikerran pituiseksi)
--> jatkaminen (viestin lopputavuja kopioidaan alkuun kunnes riittävä pituus t on saavutettu)
--> redundanssin lisääminen (joka tavun väliin jälkimmäisestä ns. varjofunktiolla laskettu tavu)
--> katkaisu ja pakottaminen (eivät aivan nimensä veroisia: MSB pois ja tilalle 1, bitit 1-4 oikealta bittien 5-8 tilalle, niiden itsensä tilalle 0110 !)
--> allekirjoitus (joka säilyttää bittien määrän ja mahdollistaa viestin palauttamisen)

Viestin pituus voi kasvaa esim 150:stä 1024 bittiin. Allekirjoituksen todentaminen kulkee vastakkaiseen suuntaan ja sisältää kolme vaihetta, joissa voi tapahtua hylkääminen.

Tämä on siis esimerkki siitä, mitä mutkia periaatteessa yksinkertaistenkin kryptoprimitiivien implementointi voi edellyttää. Redundanssin käsite sinänsä tulee esille myös jäljempänä sähkörahan yhteydessä (Chaumin algoritmin "erityisluku").

Erityistilanteisiin soveltuvia allekirjoituksia

Nimityksen taustalla on lisäprotokolla, jolla saadaan aikaan se, että allekirjoittaja, vaikka häntä todennukseen tarvitaankin, ei voi kieltää laatimaansa allekirjoitusta. Lisäprotokolla tavallaan ajaa perusprotokollan kahdesti ja varmistaa vielä, että allekirjoittaja on suorittanut sen oikein.

Käyttötarkoituksia voisivat olla esimerkiksi [HAC:476]:

• A pääsee johonkin palveluun (esim. pankin tallelokeroille) vain allekirjoittamalla B:lle päiväyksen (tms.). B ei kuitenkaan saa myöhemmin ilman A:n apua pystyä todentamaan tätä allekirjoitusta jollekulle kolmannelle osapuolelle. Jotta allekirjoituksella olisi B:lle merkitystä tarvitaan lisäprotokolla.
• Softatalo A allekirjoittaa tuotteensa. Ostaja B voi todentaa allekirjoituksen A:n avulla, mutta ei voi tehdä samaa myydessään tuotteen luvattomasti edelleen C:lle. Perusprotokolla riittää, jos B vain haluaa varmistua siitä, että tuote on A:n tekemä. Jos A:lle halutaan sälyttää jonkinlaista muodollistakin vastuuta virheistä (tai ainakin viruksista), tarvitaan lisäprotokollaa.

• ne pystyy erottamaan A:n omista allekirjoituksista;
• vain A ja B voivat muodostaa niitä (yleinen väärentämättömyys);
• B ei voi muodostaa allekirjoitusta, jota ei voisi tunnistaa tyypiltään valtuutetun allekirjoitukseksi;
• A pystyy tunnistamaan, mikä useasta valtuutetusta on laatinut tietyn allekirjoituksen;
• valtuutettu ei pysty kiistämään laatimaansa allekirjoitusta.

Ryhmäallekirjoituksen perusominaisuudet [Schn:84]:

• Vain ennalta määrätyn ryhmän jäsenet voivat allekirjoittaa viestejä.
• Kuka tahansa pystyy verfioimaan allekirjoituksen, mutta ei sitä kuka ryhmän jäsenistä sen laati.
• Kiistanalainen allekirjoitus voidaan avata siten, että allekirjoittaja paljastuu (eri menetelmissä tähän joko tarvitaan tai ei tarvita ryhmän jäsenten yhteistyötä).

Bittiin sitoutuminen (bit commitment) [Schn:86-]. Jos A:lta pyydetään ennustusta jostain 0-1-ilmiöstä, johon ennustuksen julkaiseminen voi vaikuttaa, A:n on voitava pitää ennustus aluksi omana tietonaan. Mutta silloin hän voi tietenkin muuttaa sitä haluamaansa suuntaan ilmiön tapahduttua. Jotta tällaisella ennustuksella (ja A:n kyvyllä tehdä sellainen) olisi jotain merkitystä, A:n pitää voida sitoutua siihen vakuuttavalla tavalla.

Vastaavasta asiasta oli esimerkki nollatietoyksilöinnin yhteydessä: siinä osapuoli A sitoutui johonkin, jota toinen osapuoli B ei siinä vaiheessa "ymmärtänyt", sai B:ltä haasteen ja pystyi vastaamalla siihen vakuuttamaan B:n, että sitoutuminen oli ollut asianmukainen (vastasi A:n salaista avainta). Nyt "asianmukaisuus" on sitä, että A ei muuta valintaansa.

Harjoitus: Miten seuraavat sitoutumiset tarkastetaan ja mikä estää A:ta huijaamasta? Mitä etua jälkimmäisessä on ensimmäiseen verrattuna?

1. Symmetriseen salaukseen perustuva sitoutuminen:

1. B lähettää A:lle satunnaisen luvun R (eräänlaisen nonce-luvun)
2. A valitsee satunnaisen avaimen K ja palauttaa B:lle arvon E_K(R,s), missä s on A:n ennustusbitti (tai yhtä hyvin bittijono).

Vastausta: (1) A lähettää B:lle avaimen K. (2) A lähettää B:lle viestin R1, R2, s. (jne)

Sokea allekirjoitus: A saa viestilleen M allekirjoituksen B:ltä ilman, että B näkee viestiä M tai edes allekirjoitusta {M}_KB ! Tämä tapahtuu siten että B saa allekirjoittavakseen A:lta jonkin M:stä muunnetun viestin M' ja A pystyy sitten muuntamaan allekirjoituksen {M'}_KB muotoon {M}_KB. Yhtenä sovelluksena on anonyymi elektroninen käteinen, johon siirrytään tuotapikaa (luennolla nimittäin). Harjoitus: Soveltamalla potenssin laskusääntöjä keksi, miten tällainen järjestelmä voitaisiin toteuttaa RSA-allekirjoituksen yhteyteen. Käytä jonkinmoista "sokeutustekijää", jolla muunnat M:n M':ksi. (Vastaus: vrt. Chaumin protokolla jäljempänä.)

Sähköraha

Luokitusta ja vaatimuksia

Sähköinen käteinen on vain yksi mahdollisuus toteuttaa maksu. Muita sähköisesti käytettäviä maksuvälineitä ovat mm. luottokortit ja pankkikortit (credit card ja debit card). Samalla tavoin kuin nämä edustavat tilivelkaa ja tilirahaa, sähkörahaa voi olla molemmissa muodoissa ja myös yhdistelmänä (luotollisen pankkikortin tapaan).

Yleisiä (ja ilmeisiä) vaatimuksia maksuvälineelle:

• kuljetettavuus, talletettavuus, käyttöönotettavuus ja (tekninen) käytettävyys: markka merkitsee markkaa maksutapahtuman molemmilla osapuolilla, myös virheiden sattuessa (erityisesti raha ei voi hävitä).
• jaettavuus, joka käteisen tapauksessa toteutuu vaihtorahan avulla. Maksutapahtumassa kuitenkin edellytetään jakamattomuutta (atomisuutta) ja erillisyyttä: maksuväline voidaan liittää jakamattomana tiettyyn maksun kohteeseen ja toisaalta eri maksutapahtumat voidaan erottaa toisistaan.
• homogeenisuus: jokainen markka on yhtä arvokas. Poikkeavat voidaan havaita väärennöksiksi.
• arvon vakaus, sisältää yleisen luottamuksen arvoon, myös siihen, että välinettä ei ole väärennetty.
• tietty määrä jäljittämättömyyttä: tavoite on ristiriitainen yksityisyyden suojan ja rikollisuuden estämisen välillä.

Yksityisyydellä on kuitenkin poliittiset rajoitteet. Erityisesti anonymiteetti pitäisi voida purkaa joissain erityistilanteissa, esimerkiksi kun on syytä epäillä kiristystä, rahanpesua tms. rikollista. Tällaisten tapausten varalta on ehdotettu samantapaisia järjestelmiä kuin on key-escrow. Yksi sellainen on "Digital payment systems with passive anonymity-revoking trustees" (J. Camenisch, U. Maurer, M. Stadler, 1997, [22 PS-sivua]). Siinä luotetut osapuolet eivät ole tekemisissä tilinavauksen eivätkä maksutapahtuman kanssa (joka voi olla on- tai off-line). He astuvat kuvaan vasta, jos perusteltu epäilys herää. Tämäkin järjestelmä perustuu diskreetin logaritmin vaikeuteen.

Harjoitus: Kootaan ja jäsennetään ajatuksia erityyppisistä sähköisen maksamisen muodoista ja niihin liittyvistä tietoturvatavoitteista. Pohjaksi tälle olkoot seuraavat karkeat luokittelut:
on-line --- off-line (onko rahalaitos mukana vai ei)
suora --- epäsuora (onko maksun saaja mukana vai ei)
käteinen --- tiliraha --- luotto (missä raha sijaitsee matkallaan asiakkaan rahalaitoksesta maksun saajan rahalaitokseen)
kolikot --- setelit --- shekit (liittyy paitsi edelliseen, myös rahasumman suuruuteen ja määrämittaisuuteen)

Yksi digitaalisen käteisen tavoiteluettelo on seuraava [Schn:146]:

1. Riippumattomuus (sijainnista; erityisesti siis kuljetettavuus verkossa)
2. Turvallisuus (ei voi väärentää)
3. Yksityisyys (jäljittämättömyys, nimettömyys)
4. Off-line-maksu
5. Siirrettävyys (käyttäjältä toiselle)
6. Jaettavuus

Protokollia

1. tilin muodostaminen: P avaa tilin B:hen (ja tallettaa sinne rahaa; tätä ei seuraavassa käsitellä)
2. nosto: P nostaa rahamäärän M tililtään B:stä
3. maksu: P siirtää M:n V:n haltuun
4. talletus: V muuttaa B:n avulla M:n itselleen käypään muotoon (tyypillisesti talletus V:n tilille joko B:ssä tai jossain muussa pankissa)

1. maksaja P:
   u := satunnainen erityisluku (setelin numeroksi)
   r := satunnaisluku (sokkotekijäksi)
   P --> B: u· r^e =: [1]
2. pankki B:
   nosto P:n tililtä
   [2] := [1]^d    (Allekirjoitus, tulos = u^d·r)
   B --> P: [2]
3. maksaja P:
   [3] := [2]·r^-1    (Sokkotekijän poisto)
   Jos [3]^e on erisuuri kuin u, lopeta protokolla.    (Allekirjoituksen verifiointi)
   Odotusta
   P --> V: [3]   (= u^d)    (Maksu B:n allekirjoittamalla setelillä numero u)
4. vastaanottaja V:
   Jos [3]^e ei ole muodoltaan erityisluku, lopeta.    (Setelin aitouden verifiointi)
   [4]:=[3]
   V --> B: [4]   (=u^d)    (Setelin toimitus pankkiin)
5. pankki B:
   Jos [4]^e ei ole muodoltaan erityisluku, lopeta.    (Setelin aitouden verifiointi)
   Jos [4]^e on käytettyjen listalla, lopeta.
   Merkitse [4]^e käytettyjen listalle.
   Talleta V:n tilille.

Toisenlainen tavoite on maksun saajan anonymiteetti. Se olisi perusteltu tilanteissa, jossa maksun saaja on yksityinen taho, joka esim. saa sosiaaliavustusta tai yritykseltä palautusta. Harjoitus: Kirjoita seuraava kuvaus auki eo. kaltaiseksi algoritmiksi: Maksun vastaanottaja V muodostaa sokaistun setelin ja lähettää sen maksajalle P, joka toimittaa sen edelleen pankkiin. Pankki tekee noston P:n tililtä, allekirjoittaa setelin ja palauttaa sen P:lle, joka tarkastaa allekirjoituksen ja palauttaa setelin V:lle. Tämä poistaa sokaisun, varmistaa että seteli on oikein allekirjoitettu ja toimittaa sen talletettavaksi pankkiin. Pankki tarkastaa allekirjoituksensa ja sen ettei seteliä ole aiemmin talletettu. Jos asia on kunnossa, pankki tallettaa setelin ja varmistaa ettei sitä voi tehdä uudestaan.

Seuraavassa protokollassa (niinikään Chaumilta) saavutetaan lisäksi huijaavan tahon paljastuminen. [Schn:142-]

1. P valmistaa n kpl nimettömiä maksumääräyksiä tietylle kiinteälle summalle (n on luokkaa 100). Jokainen määräys sisältää myös
   • satunnaisen yksikäsitteisyysluvun X ja
   • n paria yksilöintilukuja (Y1,Z1), ...(Yn,Zn). Kukin pari (Y,Z) on muodostettu seuraavasti P:n yksilöintiin tarvittavasta bittijonosta I:
     1. P valitsee I:n mittaisen satunnaisen bittijonon Y' ja laskee Z' = I XOR Y'. Tämä toimitus on ns. salaisuuden halkaiseminen (secret splitting): kumpikin osa, Y' ja Z' yksin on hyödytön, mutta Y' XOR Z' = I.
     2. P sitoutuu bittijonoihin Y' ja Z' eli muodostaa niistä bit-commitment-viestit Y ja Z esim. yksisuuntaisella funktiolla.
2. P sokaisee maksumääräykset sokeilla allekirjoituksilla ja antaa ne pankille.
3. Pankki pyytää P:tä purkamaan sokaisun (n-1):stä pankin satunnaisesti valitsemasta määräyksestä ja avaamaan myös niiden yksilöintitiedot. Pankki todentaa, että ne on muodostettu oikein: rahamäärä on kaikissa sama, yksikäsitteisyysluku eri ja yksilöintitieto kaikissa sellainen, kuin pankki on edellyttänyt.
4. Jos pankki päätyi uskomaan, että P ei huijaa, pankki allekirjoittaa jäljelle jääneen määräyksen, palauttaa sen P:lle ja vähentää vastaavan summan tämän tililtä.
5. P purkaa sokaisun ja lähettää määräyksen maksuksi myyjälle.
6. Myyjä tarkastaa, että määräyksessä on pankin allekirjoitus.
7. Myyjä lähettää P:lle n:n mittaisen satunnaisen bittijonon.
8. P lähettää myyjälle maksumääräyksen kunkin yksilöintiparin vasemman tai oikean puolen avattuna, siis Y':n tai Z':n - sen mukaan onko bittijonossa 0 vai 1.
9. Myyjä toimittaa maksumääräyksen pankkiin, mukaanlukien vaiheessa 8 saamansa tiedot.
10. Pankki tarkastaa allekirjoituksensa ja sen, ettei tietokannassa ole yksikäsitteisyyslukua. Jos maksumääräys läpäisee nämä tarkastukset, pankki hyvittää myyjän tiliä asianmukaisella summalla ja tallettaa yksikäsitteisyysluvun ja yksilöintitiedon puolikkaat tietokantaan.
11. Mikäli yksikäsitteisyysluku löytyy tietokannasta, pankki ei hyväksy maksumääräystä, vaan vertaa saamiaan yksilöintitiedon puolikkaita niihin, jotka ovat tietokannassa:
    • Jos ne ovat samat, pankki tietää, että myyjä on tallettanut saman maksumääräyksen aiemminkin.
    • Jos ne ovat erilaiset, pankki tietää, että P on maksanut uudestaan samalla maksumääräyksellä. Erityisesti vaihe 7-8 on tapahtunut kaksi kertaa ja bittijonot ovat olleet jossain kohden erilaiset. Siinä kohdassa pankilla on sekä Y' että Z', joten pankki tietää, kuka P oli.

Todistukset tutkinnosta, ajokortti tms. pitäisi voida esittää viranomaiselle, tulevalle työnantajalle tms. ilman, että tämä saa muuta tietoa kuin sen, mitä asiayhteys vaatii. Esimerkiksi mitä tietoja poliisi oikeastaan tarvitsee liikenneratsiassa? Erityisesti tarvitaanko tietoa autoa ajavan henkilöllisyydestä? (Keskustellaan luennolla siitä, mitä väliä tällä on.)

Chaumin esittämän ratkaisun taustalla ovat sokean allekirjoituksen tekniikat yhdessä valenimien kanssa. Yksilöinti perustuu aina vain tällaiseen nimeen ja asiointien linkittämättömyys toteutuu, koska yksilö itse vaikuttaa nimen valintaan ja se on erilainen jokaisen tahon kanssa. Samalla tulee estetyksi se, että muut pääsisivät käyttämään kyseistä valenimeä. Asiointitaho voi olla mukana nimen muodostamisessa, jolloin saavutetaan se, ettei sama yksilö pääse esiintymään (saman asiakassuhteen puitteissa) eri nimillä.

Näitä tekniikoita on sovellettu Chaumin yhtiön DigiCashin tuotteissa, joista tunnetuin on eCash. Yhtiöstä väitetään: "eCash™, as it has been developed by DigiCash, is an important and inevitable payment solution in the world of global electronic commerce." Yhtiön sivuilta löytyy useita HTML-muotoisia selkeitä artikkeleita näistä aiheista (muitakin kuin siis mainoksia). Nimettömyysasiaa löytyy myös mm. artikkelista: M. Reiter, A. Rubin: Crowds: Anonymous web transactions. DIMACS technical report 97-15, April 1997. [ PS]

Sama löytyy myös PS-muodossa (10 sivua).

Hieman tiiviimpi esitys aiheesta (ilman protokollan yksityiskohtia, 1996) on: Computerized polls may save money, protect privacy.