Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 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» Алисе:
- Боб сначала кодирует в виде строки из бит
- Боб выбирает случайный элемент , где , и вычисляет
- Боб использует псевдослучайные числа для генерации случайных чисел , следующим образом:
- Для до :
- Ряд равен наименьшему значению бита ;
- Увеличиваем ;
- Вычисляем
- Вычисляем зашифрованный текст с помощью гамирования ключевого потока
- Боб отправляет зашифрованный текст
Как происходит расшифрование сообщений
правитьАлиса получает . Она может восстановить «m», используя следующую процедуру:
- Используя разложение на множители Алиса получает и .
- Вычисление начального источника
- Начиная с , повторно вычисляем битовый вектор используя генератор BBS, как в алгоритм шифрования.
- Вычисляем текст с помощью гаммирования ключевым потоком с зашифрованным текстом .
Алиса восстановила исходный текст
Эффективность
правитьВ зависимости от размера обычного текста 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