Вероятностное шифрование. 
Система Блюма — Гольдвассер

Асимметричная криптография, и в частности, криптосистема RSA решает проблему распределения ключей, позволяя свободно публиковать открытый ключ. Однако этот факт дает противнику возможность выяснить значение открытого текста методом подбора. Обладая открытым ключом получателя к и имея в своем распоряжении перехваченный шифротекст С = Е_к(М), противник может генерировать различные открытые тексты М', зашифровывать их и затем сравнивать со значением С. Если получено Е_к(М') = С, значит, противник угадал открытый текст М' = М. Даже учитывая трудоемкость такого подбора, приходится признать, что возможна некоторая частичная утечка информации об М. Кроме того, два одинаковых сообщения, отправленные одному получателю, будут зашифрованы одинаково.

Таким образом, криптосистема RSA не позволяет скрыть некоторую априорную информацию о шифруемых сообщениях. Поэтому если содержание сообщений ограничивается всего несколькими вариантами (простые инструкции из конечного набора, ответы «да"/"нет», имя из списка), шифрование RSA не сможет обеспечить его достаточно надежное скрытие.

Избежать этого недостатка помогает вероятностное шифрование (Probabilistic Encryption). Первая система вероятностного шифрования с открытым ключом была предложена Ш. Гольдвассер (Shafi Goldwasser) и С. Микали (Silvio Micali) в 1982 г. Авторы ввели понятие семантической стойкости, которой данная система обладает. Семантическая стойкость означает, что шифротекст нс допускает никакой утечки полезной информации об исходном тексте.

Формально свойство семантической стойкости определяется следующим образом^[1]: все элементы открытого текста, которые эффективно (с полиномиальной сложностью) вычисляются по заданному шпфротексту, можно эффективно вычислить и без него.

Свойство семантической стойкости не обеспечивает защиту от атак на основе выбранного шифротекста.

Идея вероятностного шифрования с открытым ключом оказала существенное влияние на развитие современной криптографии, за что авторы были удостоены премии Тыоринга за 2012 г. (аналог Нобелевской премии в области информатики). Система Гольдвассср — Микали (GM) представляет безошибочный рандомизированный алгоритм, позволяющий получать для каждого открытого текста довольно большое количество шифротекстов при сохранении однозначности расширования. Система GM не нашла практического применения, поскольку обладала рядом недостатков, в частности многократно увеличивала размер криптограммы по сравнению с открытым текстом.

Однако сразу после публикаций о семантически стойких криптосистемах рядом авторов были предложены усовершенствования системы GM с использованием криптографически сильных генераторов псевдослучайных чисел. Наиболее эффективной оказалась система Блюма — Гольдвассер.

Система Блюма — Гольдвассер основана на применении криптографически сильного BBS-генератора, который был рассмотрен в параграфе 2.13. Напомним, что параметрами генератора являются два случайных больших простых числар и q, таких, что p = q = 3 (mod 4). Числа pwq являются личным ключом системы и держатся в секрете, а число Блюма п = pq является открытым ключом и может публиковаться свободно.

Отправитель сообщения М представляет его в виде битовой последовательности длины т, выбирает случайное число s, взаимно простое с п, 1 < s < п, и генерирует псевдослучайную битовую последовательность ps = b₀b_{b₂…b_m_, длины т, пользуясь формулами.

Полученная псевдослучайная битовая последовательность накладывается на сообщение (с помощью операции побитового XOR) и отправляется получателю вместе с подсказкой — значением следующего члена ряда.*, т. е. х_т. Таким образом, в качестве криптограммы выступает пара (х_т, М © ps), причем х_т не участвовал в формировании последовательности ps.

Получатель должен восстановить последовательность ps, а затем наложить ее на М © ps (М © ps © ps = М).

Стойкость криптосистемы базируется на непредсказуемости влево BBS генератора, определяемой однонаправленностью функции f (pc) = я² mod п, п — число Блюма, и трудности факторизации числа п.

В самом деле, зная значение х_т и открытый ключ п, противник может легко продолжить последовательность ps, но для того, чтобы узнать ее начало, он должен уметь эффективно вычислять значения х-__х = yfx^modn. Сложность таких вычислений эквивалентна сложности факторизации числа п. В предположении, что факторизация числа п является трудной задачей, оказывается практически невозможно не только определить квадратный корень по модулю, но даже с вероятностью, большей 0,5, получить информацию о его первом бите.

В то же время законный получатель сообщения, зная значения/? и q, может легко восстановить последовательность ps. Для этого сначала с помощью расширенного алгоритма Евклида он получает целые числа а и b, такие, что ар + bq = 1. Затем вычисляет.

Значение х₀ позволяет вычислить любой член последовательности х- с той же эффективностью, как это может сделать отправитель.

Пример 3.27.

Пусть отправитель хочет зашифровать сообщение М = 5 = 101₂ и для шифрования использованы параметры BBS-генератора, приведенные в примере 2.11: р = 31, q = 23, п = 713, s = 16, х₀ = 256, х_х = 653, х₂ = 35, х₃ = 512, ps = 011.,. Тогда M®ps= 101₂Ф011₂ = 110₂ = 6.

Отправитель посылает криптограмму (512, 6).

Получатель, зная значения р и q:

1) использует расширенный алгоритм Евклида (рис. 3.9) и получает числа а = 3, Ь = -4, ар + bq = 1,3? 31 — 4? 23 = 93 — 92 = 1;

Рис. 3.9. Расчет значений аЬ с, помощью расширенного алгоритма Евклида.

2) вычисляет:

3) восстанавливает последовательность ps:

4) получает значение М:

Временная и емкостная сложность вычислений системы Блюма — Гольдвассер сопоставима со сложностью криптосистем RSA и Эль-Гамаля. Криптосистема Эль-Гамаля также обладает семантической стойкостью при соответствующем выборе начальных параметров^[2]. Таким образом, эффективность вероятностной системы Блюма — Гольдвассер сопоставима с эффективностью шифра RSA, а за счет побитового шифрования может быть даже быстрее в случае длинных сообщений (которые RSA должен зашифровывать по частям).

Быстродействие вероятностной системы шифрования Блюма — Гольдвассер может быть повышено за счет использования не одного младшего бита, а не более log₂r| младших битов чисел x_jy где г| — количество двоичных разрядов числа Блюма п (т.е. примерно log₂log₂п младших битов). Это не ослабит результирующую последовательность ps_f а само шифрование будет эффективнее RSA в log₂r| раз^[3].

• [1] Мао В. Современная криптография: теория и практика: пер. с англ. М.: Издательскийдом «Вильямс», 2005.
• [2] Мао В. Современная криптография: теория и практика.
• [3] Брассар Ж. Современная криптология.