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 , missä  ja 
ovat suuria alkulukuja. Olettamuksen mukaan annetuilla  on hyvin vaikeata määrätä, onko jokin luku  neliönjäännös modulo  (ts. onko olemassa sellaista lukua , että  mod ), kun Jacobin symboli luvulle  saa arvon +1. Neliönjäännösprobleema on helppo ratkaista, kun luvun  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 , joilla kaikilla Jacobin symboli saa arvon +1. Viestin vastaanottaja käyttää tuntemaansa luvun  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  olevalla luvulla, GM salaus johtaa koodin oleelliseen laajentumiseen. Tekijöihinjakoon perustuvien hyökkäysten estämiseksi suositellaan nimittäin, että luku  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  neliönjäännös mod , kun luvun  tekijöihinjako  tunnetaan. Jos nimittäin  (mod ) ja  (mod ), niin  on neliönjäännös modulo , muussa tapauksessa kysymyksessä on epäneliö.

Avaimen generointi

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

Liisa generoi satunnaisesti ja toisistaan riippumatta kaksi sellaista suurta alkulukua  ja , että . 
Liisa laskee luvun .
Tämän jälkeen hän etsii jonkin epäneliön  modulo , 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  (mod ) (ts.  on Blumin kokonaisluku), niin luvulla  on varmasti tämä ominaisuus.

Julkinen avain muodostuu lukuparista . Salaisen avaimen muodostaa puolestaan tekijöihinjako .

Viestin salaaminen 

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

Roope koodaa viestin  bittijonoksi  käyttäen jotain yksinkertaista ja tunnettua koodaustapaa, esimerkiksi ASCII-koodia.
Jokaista bittiä  kohti Roope generoi satunnaisluvun , joka on pienempi kuin . Hän laskee arvon  (mod ).

Roope lähettää Liisalle salakielisen viestin .

Viestin avaaminen 

Liisa vastaanottaa salakieliviestin . Hän pystyy palauttamaan viestin  seuraavalla tavalla:

Käyttämällä tuntemaansa tekijöihinjakoa  Liisa tutkii, mitkä salakieliviestin luvut  ovat neliönjäännöksiä. Jos luku  on neliönjäännös, , muuten .

Liisa saa näin selville selväkieliviestin .

Salakirjoitustekniikka