Русская Википедия:Криптосистема Блюма — Гольдвассер
Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 1984 году.
Пусть m1, m2, … , mm — последовательность бит открытого текста. В качестве параметров криптосистемы выбираем n=pq — число Блюма, x0 — случайное число из Zn, взаимно простое с N.
В качестве открытого ключа для шифрования выступает n, в качестве секретного ключа для расшифрования — пара (p, q).
Для того, чтобы зашифровать открытый текст, обладатель открытого ключа выбирает x0. На основе BBS-генератора по вектору инициализации x0 получают последовательность квадратов x1, x2, … , xm, по которой получают последовательность младших бит b1, b2, …, bm. Путём гаммирования с этой последовательностью битов открытого текста и получают шифрованный текст ci=mi⊕bi, i=1,2,…,m.
Шифрограмма, которая пересылается обладателю секретного ключа, есть (c1,c2,…,cm, xm+1). После формирования шифрограммы последовательность xi, i=0,1,…,m уничтожается, и при следующем сеансе связи отправитель выбирает новое x0.
Получатель шифрограммы восстанавливает по xm+1 последовательность главных корней xm, … , x1 и последовательность их младших бит b1, b2, …, bm, а затем расшифровывает шифрограмму: mi=ci⊕bi , i=1,2,…,m.
Как происходит шифрование сообщений
Предположим, что Боб хочет послать сообщение «m» Алисе:
- Боб сначала кодирует <math>m</math> в виде строки из <math>L</math> бит<math>(m_0, \dots, m_{L-1})</math>
- Боб выбирает случайный элемент <math>r</math>, где <math>1 < r < N</math>, и вычисляет <math>x_0 = r^2~mod~N</math>
- Боб использует псевдослучайные числа для генерации случайных чисел <math>L</math>, следующим образом:
- Для <math>i=0</math> до <math>L-1</math>:
- Ряд <math>b_i</math> равен наименьшему значению бита <math>x_i</math>;
- Увеличиваем <math>i</math> ;
- Вычисляем <math>x_i = (x_{i-1})^2~mod~N</math>
- Вычисляем зашифрованный текст с помощью гамирования ключевого потока <math>{\vec c} = {\vec m} \oplus {\vec b}, y=x_{L}=x_{L-1}^{2}~mod~N</math>
- Боб отправляет зашифрованный текст<math>(c_0, \dots, c_{L-1}), y</math>
Как происходит расшифрование сообщений
Алиса получает <math>(c_0, \dots, c_{L-1}), y</math>. Она может восстановить «m», используя следующую процедуру:
- Используя разложение на множители <math>(p, q)</math> Алиса получает <math>r_p = y^{((p+1)/4)^{L}}~mod~p</math> и <math>r_q = y^{((q+1)/4)^{L}}~mod~q</math>.
- Вычисление начального источника <math>x_0=q(q^{-1}~{mod}~p)r_p + p(p^{-1}~{mod}~q)r_q~{mod}~N</math>
- Начиная с <math>x_0</math> повторно вычисляем битовый вектор <math>{\vec b}</math> используя генератор BBS, как в алгоритм шифрования.
- Вычисляем текст с помощью гаммирование ключивым потоком с зашифрованным текстом <math>{\vec m} = {\vec c} \oplus {\vec b}</math>.
Алиса восстановила исходный текст <math>m=(m_0, \dots, m_{L-1})</math>
Эффективность
В зависимости от размера обычного текста 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
Шаблон:Криптосистемы с открытым ключом