Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел . Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 1984 году.

Пусть m ₁ , m ₂ , … , m _m — последовательность бит открытого текста . В качестве параметров криптосистемы выбираем n=pq — число Блюма, x ₀ — случайное число из Z _n , взаимно простое с N.

В качестве открытого ключа для шифрования выступает n, в качестве секретного ключа для расшифрования — пара (p, q).

Для того, чтобы зашифровать открытый текст, обладатель открытого ключа выбирает x ₀ . На основе BBS-генератора по вектору инициализации x ₀ получают последовательность квадратов x ₁ , x ₂ , … , x _m , по которой получают последовательность младших бит b ₁ , b ₂ , …, b _m . Путём гаммирования с этой последовательностью битов открытого текста и получают шифрованный текст c _i =m _i ⊕b _i , i=1,2,…,m.

Шифрограмма, которая пересылается обладателю секретного ключа, есть (c ₁ ,c ₂ ,…,c _m , x _m+1 ). После формирования шифрограммы последовательность x _i , i=0,1,…,m уничтожается, и при следующем сеансе связи отправитель выбирает новое x ₀ .

Получатель шифрограммы восстанавливает по x _m+1 последовательность главных корней x _m , … , x ₁ и последовательность их младших бит b ₁ , b ₂ , …, b _m , а затем расшифровывает шифрограмму: m _i =c _i ⊕b _i , i=1,2,…,m.

Как происходит шифрование сообщений

Предположим, что Боб хочет послать сообщение «m» Алисе:

1. Боб сначала кодирует ${\displaystyle m}$ в виде строки из ${\displaystyle L}$ бит ${\displaystyle (m_{0},\dots ,m_{L-1})}$
2. Боб выбирает случайный элемент ${\displaystyle r}$ , где ${\displaystyle 1<r<N}$ , и вычисляет ${\displaystyle x_{0}=r^{2}~mod~N}$
3. Боб использует псевдослучайные числа для генерации случайных чисел ${\displaystyle L}$ , следующим образом:
   1. Для ${\displaystyle i=0}$ до ${\displaystyle L-1}$ :
   2. Ряд ${\displaystyle b_{i}}$ равен наименьшему значению бита ${\displaystyle x_{i}}$ ;
   3. Увеличиваем ${\displaystyle i}$ ;
   4. Вычисляем ${\displaystyle x_{i}=(x_{i-1})^{2}~mod~N}$
4. Вычисляем зашифрованный текст с помощью гамирования ключевого потока ${\displaystyle {\vec {c}}={\vec {m}}\oplus {\vec {b}},y=x_{L}=x_{L-1}^{2}~mod~N}$
5. Боб отправляет зашифрованный текст ${\displaystyle (c_{0},\dots ,c_{L-1}),y}$

Как происходит расшифрование сообщений

Алиса получает ${\displaystyle (c_{0},\dots ,c_{L-1}),y}$ . Она может восстановить «m», используя следующую процедуру:

1. Используя разложение на множители ${\displaystyle (p,q)}$ Алиса получает ${\displaystyle r_{p}=y^{((p+1)/4)^{L}}~mod~p}$ и ${\displaystyle r_{q}=y^{((q+1)/4)^{L}}~mod~q}$ .
2. Вычисление начального источника ${\displaystyle x_{0}=q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q}~{mod}~N}$
3. Начиная с ${\displaystyle x_{0}}$ , повторно вычисляем битовый вектор ${\displaystyle {\vec {b}}}$ используя генератор BBS, как в алгоритм шифрования.
4. Вычисляем текст с помощью гаммирования ключевым потоком с зашифрованным текстом ${\displaystyle {\vec {m}}={\vec {c}}\oplus {\vec {b}}}$ .

Алиса восстановила исходный текст ${\displaystyle m=(m_{0},\dots ,m_{L-1})}$

Эффективность

В зависимости от размера обычного текста BG может задействовать больше или меньше вычислительных ресурсов чем RSA . RSA использует оптимизированный способ шифрования, чтобы минимизировать время шифрования, шифрование RSA будет как правило выигрывать у BG во всём, кроме самых коротких сообщений. Поскольку время расшифрования RSA нестабильно, то возведение в степень по модулю может потребовать столько же ресурсов как для расшифровки BG зашифрованного текста той же самой длины. BG более эффективно к более длинным зашифрованным текстам, в которых RSA требует многократного отдельного шифрования. В этих случаях BG более эффективно.

Примечания

Ссылки

• M. Blum, S. Goldwasser, «An Efficient Probabilistic Public Key Encryption Scheme which Hides All Partial Information», Proceedings of Advances in Cryptology — CRYPTO '84, pp. 289—299, Springer Verlag, 1985.
• Menezes, Alfred; van Oorschot, Paul C.; and Vanstone, Scott A. Handbook of Applied Cryptography. CRC Press, October 1996. ISBN 0-8493-8523-7