Goldwasser-Micali

Goldwasser-Micali kryptosysteemi (GM) on epäsymmetrinen julkisen avaimen salaamisalgoritmi, jonka ovat kehittäneet Shafi Goldwasser ja Silvio Micali vuonna 1982. GM oli ensimmäinen satunnaistava (probabilistinen) julkisen avaimen salakirjoitusjärjestelmä, joka on kryptografisten standardioletusten ollessa voimassa todistettavasti turvallinen. Se ei kuitenkaan ole tehokas kryptosysteemi, koska salakielinen viesti voi olla alkuperäistä viestiä satoja kertoja pitempi. Todistaakseen kryptosysteemin turvallisuusominaisuudet Goldwasser ja Micali esittelivät laajaan käyttöön levinneen semanttisen turvallisuuden käsitteen.

GM salakirjoitusjärjestelmä on semanttisesti turvallinen olettaen, että ns. neliönjäännösprobleema on ratkeamaton modulo yhdistetty luku $N=pq$, missä $p$ ja $q$ ovat suuria alkulukuja. Olettamuksen mukaan annetuilla $(x,N)$ on hyvin vaikeata määrätä, onko jokin luku $x$ neliönjäännös modulo $N$ (ts. onko olemassa sellaista lukua $y$, että $x=y^{2}$ mod $N$), kun Jacobin symboli luvulle $x$ saa arvon +1. Neliönjäännösprobleema on helppo ratkaista, kun luvun $N$ tekijöihinjako tunnetaan. Toisaalta uusia neliönjäännöksiä pystyy kuka tahansa tuottamaan vaikka ei tuntisi tätä tekijöihinjakoa. GM-salakirjoitusjärjestelmä hyödyntää tätä epäsymmetriaa salakirjoittamalla tietyn selväkielisen viestin joko jonoksi neliönjäännöksiä tai epäneliöitä modulo $N$, joilla kaikilla Jacobin symboli saa arvon +1. Viestin vastaanottaja käyttää tuntemaansa luvun $N$ tekijöihinjakoa salaisena avaimenaan ja desiferoi viestin testaamalla, ovatko vastaanotetun salakieliviestin luvut neliöitä vai epäneliöitä.

Koska Goldwasser-Micali korvaa jokaisen selväkielisen koodin bitin suuruusluokkaa $|N|$ olevalla luvulla, GM salaus johtaa koodin oleelliseen laajentumiseen. Tekijöihinjakoon perustuvien hyökkäysten estämiseksi suositellaan nimittäin, että luku $N$ olisi useiden satojen bittien mittainen. Siten järjestelmä epäkäytännöllisenä palvelee lähinnä teoreettista tutkimusta. Käytännön sovellutuksia varten on myöhemmin kehitetty tehokkaampia todistettavasti turvallisia salakirjoitusjärjestelmiä. Esimerkki tällaisesta järjestelmästä on Elgamal-järjestelmä.

Koska salauksessa käytetään satunnaistavaa algoritmia, sama selväkieliteksti tuottaa yleensä erilaisia salakieliviestejä joka salauskerralla. Tästä on järjestelmän turvallisuuden kannalta merkittävää etua, sillä se estää sen, että viestien sisältöä voitaisiin arvata vertailemalla salakieliviestejä aikaisemmin tunnettuihin.

Järjestelmän määrittely

Goldwasser-Micali koostuu kolmesta algoritmista:

• satunnaistava avaimen generointialgoritmi, joka tuottaa julkisen ja salaisen avaimen,
• satunnaistava salausalgoritmi ja
• deterministinen purkualgoritmi.

Järjestelmä perustuu siihen, että pystytään päättelemään, onko annettu luku $x$ neliönjäännös mod $N$, kun luvun $N$ tekijöihinjako $(p,q)$ tunnetaan. Jos nimittäin $x^{(p-1)/2}\equiv 1$ (mod $p$) ja $x^{(q-1)/2}\equiv 1$ (mod $q$), niin $x$ on neliönjäännös modulo $N$, muussa tapauksessa kysymyksessä on epäneliö.

Avaimen generointi

GM-järjestelmän moduuliluku generoidaan samalla tavalla kuin RSA-järjestelmässä.

1. Liisa generoi satunnaisesti ja toisistaan riippumatta kaksi sellaista suurta alkulukua $p$ ja $q$, että $p\neq$.
2. Liisa laskee luvun $N=pq$.
3. Tämän jälkeen hän etsii jonkin epäneliön $z$ modulo $N$, jolle Jacobin symboli saa arvon +1. Tämän hän voi tehdä valitsemalla satunnaislukuja ja testaamalla tuntemansa tekijöihinjaon avulla, ovatko ne neliönjäännöksiä. Jos $(p,q)\equiv 3$ (mod $4$) (ts. $N$ on Blumin kokonaisluku), niin luvulla $N-1$ on varmasti tämä ominaisuus.

Julkinen avain muodostuu lukuparista $(N,z)$. Salaisen avaimen muodostaa puolestaan tekijöihinjako $(p,q)$.

Viestin salaaminen

Oletetaan, että Roope haluaa lähettää Liisalle viestin m:

1. Roope koodaa viestin $m$ bittijonoksi $(m_{0},m_{1},\dots ,m_{n})$ käyttäen jotain yksinkertaista ja tunnettua koodaustapaa, esimerkiksi ASCII-koodia.
2. Jokaista bittiä $m_{i}$ kohti Roope generoi satunnaisluvun $y$, joka on pienempi kuin $N$. Hän laskee arvon $c_{i}\equiv y^{y}z^{m_{i}}$ (mod $N$).

Roope lähettää Liisalle salakielisen viestin $(c_{0},c_{1},\dots ,c_{n})$.

Viestin avaaminen

Liisa vastaanottaa salakieliviestin $(c_{0},c_{1},\dots ,c_{i})$. Hän pystyy palauttamaan viestin $m$ seuraavalla tavalla:

1. Käyttämällä tuntemaansa tekijöihinjakoa $(p,q)$ Liisa tutkii, mitkä salakieliviestin luvut $c_{i}$ ovat neliönjäännöksiä. Jos luku $c_{i}$ on neliönjäännös, $m_{i}=1$, muuten $m_{i}=0$.

Liisa saa näin selville selväkieliviestin $m=(m_{0},m_{1},\dots ,m_{n})$.