Blum-Goldwasser kryptojärjestelmä

Bloom-Goldwasser-salausjärjestelmä  on yksi julkisen avaimen salausjärjestelmistä, joka perustuu suurten kokonaislukujen huomioon ottamista vaikeuteen . Manuel Blum ja Shafi Goldwasser ehdottivat tätä salausalgoritmia vuonna 1984.

Olkoon m 1 , m 2 , … , m m selkeän tekstin  bittien sarja . Salausjärjestelmän parametreiksi valitaan n=pq - Bloom-luku, x 0 - satunnaisluku Z n  : stä koprime N : n kanssa.

Salauksen julkinen avain on n ja pari (p, q) on salauksen purkamisen salainen avain .

Selkeän tekstin salaamiseksi julkisen avaimen haltija valitsee x 0 . BBS-generaattoriin perustuen alustusvektoria x 0 käytetään neliöiden x 1 , x 2 , …, x m sekvenssin saamiseksi, jota käytetään alhaisten bittien b 1 , b 2 , …, b m sekvenssin saamiseksi. . Pelaamalla tällä selvätekstibittien sarjalla saadaan salateksti c i =m i ⊕b i , i=1,2,…,m.

Salaus, joka lähetetään salaisen avaimen omistajalle, on (c 1 ,c 2 ,…,c m , x m+1 ). Salauksen muodostamisen jälkeen sarja x i , i=0,1,…,m tuhotaan ja seuraavassa kommunikaatioistunnossa lähettäjä valitsee uuden x 0 :n .

Salatekstin vastaanottaja palauttaa x m+1 pääjuurien sekvenssin x m , … , x 1 ja niiden vähiten merkitsevien bittien sekvenssin b 1 , b 2 , …, b m ja purkaa sitten salakirjoituksen: m i = c i ⊕b i , i= 1,2,…,m.

Miten viestit salataan

Oletetaan, että Bob haluaa lähettää viestin "m" Alicelle:

1. Bob koodaa ensin bittijonona
2. Bob valitsee satunnaisen elementin , jossa , ja laskee
3. Bob käyttää näennäissatunnaisia ​​lukuja satunnaislukujen luomiseen seuraavasti:
   1. Korkeintaan : _
   2. Rivi on yhtä suuri kuin pienin bittiarvo ;
   3. Kasvata  ;
   4. Laskea
4. Laske salateksti käyttämällä avainvirran pelillistämistä
5. Bob lähettää salatekstin

Miten viestien salaus puretaan

Alice vastaanottaa . Hän voi palauttaa "m":n seuraavalla tavalla:

1. Tekijälaskentaa käyttämällä Alice saa ja .
2. Alkuperäinen lähdelaskenta
3. Alkaen laske bittivektori uudelleen käyttämällä BBS-generaattoria, kuten salausalgoritmissa.
4. Laske teksti käyttämällä salatekstin avainvirran gammaa .

Alice palautti alkuperäisen tekstin

Tehokkuus

Pelkän tekstin koosta riippuen BG voi käyttää enemmän tai vähemmän laskentaresursseja kuin RSA . RSA käyttää optimoitua salausmenetelmää salausajan minimoimiseksi. RSA-salaus on yleensä parempi kuin BG kaikissa paitsi lyhyimmissä viesteissä. Koska RSA-salauksen purkuaika ei ole vakaa, eksponentiomoduuli saattaa vaatia saman määrän resursseja kuin samanpituisen BG-salatekstin salauksen purkaminen. BG on tehokkaampi pidempiin salateksteihin, joissa RSA vaatii useita erillisiä salauksia. Näissä tapauksissa BG on tehokkaampi.

Muistiinpanot

Linkit

• M. Blum, S. Goldwasser, "Tehokas todennäköisyyspohjainen julkisen avaimen salausjärjestelmä, joka piilottaa kaikki osittaiset tiedot", Proceedings of Advances in Cryptology - CRYPTO '84, s. 289-299, Springer Verlag, 1985.
• Menezes, Alfred; van Oorschot, Paul C.; ja Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, lokakuu 1996. ISBN 0-8493-8523-7