Blum-Goldwasser kriptorendszer

A Bloom-Goldwasser kriptorendszer  az egyik nyilvános kulcsú titkosítási séma, amely a nagy egész számok faktorálásának nehézségén alapul . Ezt a titkosítási algoritmust Manuel Blum és Shafi Goldwasser javasolta 1984-ben.

Legyen m 1 , m 2 , … , m m egyszerű szöveges  bitek sorozata . A kriptorendszer paramétereiként n=pq - a Bloom-számot választjuk, x 0 -  egy véletlenszámot a Z n - ből N-vel együtt.

A titkosítás nyilvános kulcsa n, a pár (p, q) pedig a titkos kulcs a visszafejtéshez.

A nyílt szöveg titkosításához a nyilvános kulcs birtokosa az x 0 értéket választja . A BBS generátor alapján az x 0 inicializálási vektort használjuk az x 1 , x 2 , … , x m négyzetek sorozatának előállítására , amelyet a b 1 , b 2 , … , b m alacsony bitek sorozatának előállítására használunk . . Ezzel az egyszerű szöveg bitsorozattal játszva kapjuk meg a c i =m i ⊕b i titkosított szöveget , i =1,2,…,m.

A titkos kulcs tulajdonosának elküldött titkosítás (c 1 ,c 2 ,…,c m , x m+1 ). A titkosítás létrejötte után az x i , i=0,1,…,m sorozat megsemmisül, és a következő kommunikációs szekcióban a küldő új x 0 -t választ .

A rejtjelezett szöveg címzettje visszaállítja x m+1 az x m , … , x 1 fő gyökök sorozatát és azok legkevésbé jelentős bitjeinek sorozatát b 1 , b 2 , …, b m , majd visszafejti a rejtjelezett szöveget: m i = c i ⊕b i , i= 1,2,…,m.

Az üzenetek titkosítása

Tegyük fel, hogy Bob "m" üzenetet szeretne küldeni Alice-nek:

1. Bob először bitsorként kódol
2. Bob kiválaszt egy véletlenszerű elemet , ahol , és kiszámítja
3. Bob pszeudo-véletlen számokat használ véletlen számok generálásához , az alábbiak szerint:
   1. Legfeljebb : _
   2. A sor egyenlő a legkisebb bitértékkel ;
   3. Növekedés  ;
   4. Kiszámítja
4. Számítsa ki a rejtjelezett szöveget a keystream gamification segítségével
5. Bob elküldi a titkosított szöveget

Az üzenetek visszafejtése

Alice fogadja . Az "m"-t a következő eljárással tudja helyreállítani:

1. A faktorizáció segítségével Alice megkapja és .
2. Kezdeti forrásszámítás
3. Kezdve a bitvektor újraszámításával a BBS generátor segítségével, mint a titkosítási algoritmusban.
4. Számítsa ki a szöveget a titkosított szöveges kulcsfolyam gamma használatával .

Alice visszaállította az eredeti szöveget

Hatékonyság

Az egyszerű szöveg méretétől függően a BG több vagy kevesebb számítási erőforrást használhat, mint az RSA . Az RSA optimalizált titkosítási módszert használ a titkosítási idő minimalizálása érdekében, az RSA-titkosítás általában a legrövidebb üzenetek kivételével minden esetben felülmúlja a BG-t. Mivel az RSA visszafejtési ideje nem stabil, a hatványozás modulo ugyanannyi erőforrást igényelhet, mint az azonos hosszúságú BG titkosítási szöveg visszafejtése. A BG hatékonyabb a hosszabb titkosított szövegeknél, ahol az RSA több külön titkosítást igényel. Ezekben az esetekben a BG hatékonyabb.

Jegyzetek

Linkek

• M. Blum, S. Goldwasser, "Efficient Probabilistic Public Key Encryption Scheme, amely elrejti az összes részleges információt", Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.
• Menezes, Alfred; van Oorschot, Paul C.; és Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, 1996. október. ISBN 0-8493-8523-7