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

Криптосистема Блюма — Гольдвассер — одна из схем шифрования с открытым ключом, основанная на сложности факторизации больших целых чисел. Этот алгоритм шифрования был предложен Мануэлем Блюмом и Шафи Гольдвассер в 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 {displaystyle m} в виде строки из L {displaystyle L} бит ( m 0 , … , m L − 1 ) {displaystyle (m_{0},dots ,m_{L-1})}

Боб выбирает случайный элемент r {displaystyle r} , где 1 < r < N {displaystyle 1<r<N} , и вычисляет x 0 = r 2 m o d N {displaystyle x_{0}=r^{2}~mod~N}

Боб использует псевдослучайные числа для генерации случайных чисел L {displaystyle L} , следующим образом:

Для i = 0 {displaystyle i=0} до L − 1 {displaystyle L-1} :

Ряд b i {displaystyle b_{i}} равен наименьшему значению бита x i {displaystyle x_{i}} ;

Увеличиваем i {displaystyle i} ;

Вычисляем x i = ( x i − 1 ) 2 m o d N {displaystyle x_{i}=(x_{i-1})^{2}~mod~N}

Вычисляем зашифрованный текст с помощью гамирования ключевого потока c → = m → ⊕ b → , y = x L = x L − 1 2 m o d N {displaystyle {vec {c}}={vec {m}}oplus {vec {b}},y=x_{L}=x_{L-1}^{2}~mod~N}

Боб отправляет зашифрованный текст ( c 0 , … , c L − 1 ) , y {displaystyle (c_{0},dots ,c_{L-1}),y}

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

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

Используя разложение на множители ( p , q ) {displaystyle (p,q)} Алиса получает r p = y ( ( p + 1 ) / 4 ) L m o d p {displaystyle r_{p}=y^{((p+1)/4)^{L}}~mod~p} и r q = y ( ( q + 1 ) / 4 ) L m o d q {displaystyle r_{q}=y^{((q+1)/4)^{L}}~mod~q} .

Вычисление начального источника x 0 = q ( q − 1 m o d p ) r p + p ( p − 1 m o d q ) r q m o d N {displaystyle x_{0}=q(q^{-1}~{mod}~p)r_{p}+p(p^{-1}~{mod}~q)r_{q}~{mod}~N}

Начиная с x 0 {displaystyle x_{0}} повторно вычисляем битовый вектор b → {displaystyle {vec {b}}} используя генератор BBS, как в алгоритм шифрования.

Вычисляем текст с помощью гаммирование ключивым потоком с зашифрованным текстом m → = c → ⊕ b → {displaystyle {vec {m}}={vec {c}}oplus {vec {b}}} .

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

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

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