Криптосистема Блюма — Гольдвассер

Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 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» Алисе:

  1. Боб сначала кодирует в виде строки из бит
  2. Боб выбирает случайный элемент , где , и вычисляет
  3. Боб использует псевдослучайные числа для генерации случайных чисел , следующим образом:
    1. Для до :
    2. Ряд равен наименьшему значению бита ;
    3. Увеличиваем  ;
    4. Вычисляем
  4. Вычисляем зашифрованный текст с помощью гамирования ключевого потока
  5. Боб отправляет зашифрованный текст

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

Алиса получает . Она может восстановить «m», используя следующую процедуру:

  1. Используя разложение на множители Алиса получает и .
  2. Вычисление начального источника
  3. Начиная с , повторно вычисляем битовый вектор используя генератор BBS, как в алгоритм шифрования.
  4. Вычисляем текст с помощью гаммирования ключевым потоком с зашифрованным текстом .

Алиса восстановила исходный текст

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

В зависимости от размера обычного текста 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