Blum-Goldwasser kryptosystém

Šifrovací systém Bloom-Goldwasser  je jedním ze schémat šifrování s veřejným klíčem založeným na obtížnosti faktorizace velkých celých čísel . Tento šifrovací algoritmus navrhli Manuel Blum a Shafi Goldwasser v roce 1984.

Nechť m 1 , m 2 , ... , m m je posloupnost  bitů otevřeného textu . Jako parametry kryptosystému zvolíme n=pq - Bloomovo číslo, x 0 - náhodné číslo  ze Z n spojené s N.

Veřejný klíč pro šifrování je n a pár (p, q) je tajný klíč pro dešifrování.

Pro zašifrování otevřeného textu zvolí držitel veřejného klíče x 0 . Na základě generátoru BBS je inicializační vektor x 0 použit k získání sekvence čtverců x 1 , x 2 , … , x m , která se používá k získání sekvence nízkých bitů b 1 , b 2 , …, b m . Hraním s touto posloupností bitů otevřeného textu získáte šifrový text c i = m i ⊕b i , i=1,2,…,m.

Šifrogram, který je zaslán vlastníkovi tajného klíče, je (c 1 ,c 2 ,…,c m , x m+1 ). Po vytvoření šifry je sekvence x i , i=0,1,…,m zničena a při další komunikační relaci si odesílatel zvolí nové x 0 .

Příjemce šifrového textu obnoví x m+1 posloupnost hlavních kořenů x m , … , x 1 a posloupnost jejich nejméně významných bitů b 1 , b 2 , …, b m a poté šifrovaný text dešifruje: m i = c i ⊕b i , i= 1,2,…,m.

Jak jsou zprávy šifrovány

Předpokládejme, že Bob chce poslat zprávu „m“ Alici:

1. Bob nejprve zakóduje jako řetězec bitů
2. Bob vybere náhodný prvek , where a vypočítá
3. Bob používá pseudonáhodná čísla ke generování náhodných čísel následovně:
   1. Až pro :
   2. Řádek je roven nejmenší bitové hodnotě ;
   3. zvýšit  ;
   4. Vypočítat
4. Vypočítejte šifrovaný text pomocí gamifikace klíčového proudu
5. Bob posílá šifrovaný text

Jak se dešifrují zprávy

Alice přijímá . Může obnovit "m" pomocí následujícího postupu:

1. Pomocí faktorizace Alice získá a .
2. Počáteční výpočet zdroje
3. Začněte přepočítáním bitového vektoru pomocí generátoru BBS, jako v šifrovacím algoritmu.
4. Vypočítejte text pomocí gama klíčového proudu šifrovaného textu .

Alice obnovila původní text

Účinnost

V závislosti na velikosti prostého textu může BG využívat více nebo méně výpočetních zdrojů než RSA . RSA používá optimalizovanou metodu šifrování pro minimalizaci doby šifrování, šifrování RSA obecně překoná BG ve všech zprávách kromě nejkratších. Protože čas dešifrování RSA není stabilní, umocnění modulo může vyžadovat stejné množství zdrojů jako dešifrování šifrovaného textu BG stejné délky. BG je efektivnější pro delší šifrované texty, kde RSA vyžaduje více samostatných šifrování. V těchto případech je BG účinnější.

Poznámky

Odkazy

• M. Blum, S. Goldwasser, "Efektivní pravděpodobnostní schéma šifrování veřejného klíče, které skryje všechny dílčí informace", Proceedings of Advances in Cryptology - CRYPTO '84, pp. 289-299, Springer Verlag, 1985.
• Menezes, Alfred; van Oorschot, Paul C.; a Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, říjen 1996. ISBN 0-8493-8523-7