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 formula_1, missä formula_2 ja formula_3
ovat suuria alkulukuja. Olettamuksen mukaan annetuilla formula_4 on hyvin vaikeata määrätä, onko jokin luku formula_5 neliönjäännös modulo formula_6 (ts. onko olemassa sellaista lukua formula_7, että formula_8 mod formula_6), kun Jacobin symboli luvulle formula_5 saa arvon +1. Neliönjäännösprobleema on helppo ratkaista, kun luvun formula_6 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 formula_6, joilla kaikilla Jacobin symboli saa arvon +1. Viestin vastaanottaja käyttää tuntemaansa luvun formula_6 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 formula_14 olevalla luvulla, GM salaus johtaa koodin oleelliseen laajentumiseen. Tekijöihinjakoon perustuvien hyökkäysten estämiseksi suositellaan nimittäin, että luku formula_6 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.
Goldwasser-Micali koostuu kolmesta algoritmista:
Järjestelmä perustuu siihen, että pystytään päättelemään, onko annettu luku formula_5 neliönjäännös mod formula_6, kun luvun formula_6 tekijöihinjako formula_19 tunnetaan. Jos nimittäin formula_20 (mod formula_2) ja formula_22 (mod formula_3), niin formula_5 on neliönjäännös modulo formula_6, muussa tapauksessa kysymyksessä on epäneliö.
GM-järjestelmän moduuliluku generoidaan samalla tavalla kuin RSA-järjestelmässä.Julkinen avain muodostuu lukuparista formula_36. Salaisen avaimen muodostaa puolestaan tekijöihinjako formula_37.
Oletetaan, että Roope haluaa lähettää Liisalle viestin "m":Roope lähettää Liisalle salakielisen viestin formula_45.
Liisa vastaanottaa salakieliviestin formula_46. Hän pystyy palauttamaan viestin formula_38 seuraavalla tavalla:Liisa saa näin selville selväkieliviestin formula_53.