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

Алгоритм шифрования с асимметричным ключом

Криптосистема Блюма–Гольдвассера (BG) — это асимметричный алгоритм шифрования, предложенный Мануэлем Блюмом и Шафи Голдвассером в 1984 году. Блюм–Гольдвассер — это вероятностная , семантически безопасная криптосистема с расширением шифртекста постоянного размера . Алгоритм шифрования реализует потоковый шифр на основе XOR с использованием генератора псевдослучайных чисел Блюма-Блюма-Шуба (BBS) для генерации потока ключей . Расшифровка выполняется путем манипулирования конечным состоянием генератора BBS с использованием закрытого ключа для нахождения начального начального числа и восстановления потока ключей.

Криптосистема BG семантически безопасна на основе предполагаемой неразрешимости целочисленной факторизации ; в частности, факторизации составного значения , где — большие простые числа . BG имеет множество преимуществ по сравнению с более ранними вероятностными схемами шифрования, такими как криптосистема Голдвассера–Микали . Во-первых, ее семантическая безопасность сводится исключительно к целочисленной факторизации, не требуя никаких дополнительных предположений (например, сложности проблемы квадратичного остатка или проблемы RSA ). Во-вторых, BG эффективна с точки зрения хранения, вызывая расширение шифротекста постоянного размера независимо от длины сообщения. BG также относительно эффективна с точки зрения вычислений и хорошо справляется даже по сравнению с криптосистемами, такими как RSA (в зависимости от длины сообщения и выбора экспоненты). Однако BG весьма уязвима для атак с адаптивным выбором шифротекста (см. ниже). ${\displaystyle N=pq}$ ${\displaystyle p,q}$

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

Операция

Криптосистема Блюма–Гольдвассера состоит из трех алгоритмов: вероятностного алгоритма генерации ключей, который создает открытый и закрытый ключ, вероятностного алгоритма шифрования и детерминированного алгоритма дешифрования.

Генерация ключей

Открытый и закрытый ключи генерируются следующим образом:

1. Выберите два больших различных простых числа и такие, что и . ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle p\equiv 3{\bmod {4}}}$ ${\displaystyle q\equiv 3{\bmod {4}}}$
2. Вычислить . ^[1] ${\displaystyle n=pq}$

Тогда это открытый ключ, а пара — это закрытый ключ. ${\displaystyle n}$ ${\displaystyle (p,q)}$

Шифрование

Сообщение шифруется открытым ключом следующим образом: ${\displaystyle M}$ ${\displaystyle n}$

1. Вычислить размер блока в битах . ${\displaystyle h=\lfloor log_{2}(log_{2}(n))\rfloor }$
2. Преобразовать в последовательность блоков , где каждый блок имеет длину бит. ${\displaystyle M}$ ${\displaystyle t}$ ${\displaystyle m_{1},m_{2},\dots ,m_{t}}$ ${\displaystyle h}$
3. Выберите случайное целое число . ${\displaystyle r<n}$
4. Вычислить . ${\displaystyle x_{0}=r^{2}{\bmod {n}}}$
5. Для от 1 до ${\displaystyle i}$ ${\displaystyle t}$
   1. Вычислить . ${\displaystyle x_{i}=x_{i-1}^{2}{\bmod {n}}}$
   2. Вычислите наименее значимые биты . ${\displaystyle p_{i}=}$ ${\displaystyle h}$ ${\displaystyle x_{i}}$
   3. Вычислить . ${\displaystyle c_{i}=m_{i}\oplus p_{i}}$
6. Наконец, вычислите . ${\displaystyle x_{t+1}=x_{t}^{2}{\bmod {n}}}$

Тогда шифрование сообщения представляет собой все значения плюс конечное значение: . ${\displaystyle M}$ ${\displaystyle c_{i}}$ ${\displaystyle x_{t+1}}$ ${\displaystyle (c_{1},c_{2},\dots ,c_{t},x_{t+1})}$

Расшифровка

Зашифрованное сообщение можно расшифровать с помощью закрытого ключа следующим образом: ${\displaystyle (c_{1},c_{2},\dots ,c_{t},x)}$ ${\displaystyle (p,q)}$

1. Вычислить . ${\displaystyle d_{p}=((p+1)/4)^{t+1}{\bmod {(p-1)}}}$
2. Вычислить . ${\displaystyle d_{q}=((q+1)/4)^{t+1}{\bmod {(q-1)}}}$
3. Вычислить . ${\displaystyle u_{p}=x^{d_{p}}{\bmod {p}}}$
4. Вычислить . ${\displaystyle u_{q}=x^{d_{q}}{\bmod {q}}}$
5. Используя расширенный алгоритм Евклида , вычислите и такие, что . ${\displaystyle r_{p}}$ ${\displaystyle r_{q}}$ ${\displaystyle r_{p}p+r_{q}q=1}$
6. Вычислить . Это будет то же самое значение, которое использовалось при шифровании (см. доказательство ниже). Затем можно использовать для вычисления той же последовательности значений, которая использовалась при шифровании для расшифровки сообщения, как показано ниже. ${\displaystyle x_{0}=u_{q}r_{p}p+u_{p}r_{q}q{\bmod {n}}}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{i}}$
7. Для от 1 до ${\displaystyle i}$ ${\displaystyle t}$
   1. Вычислить . ${\displaystyle x_{i}=x_{i-1}^{2}{\bmod {n}}}$
   2. Вычислите наименее значимые биты . ${\displaystyle p_{i}=}$ ${\displaystyle h}$ ${\displaystyle x_{i}}$
   3. Вычислить . ${\displaystyle m_{i}=c_{i}\oplus p_{i}}$
8. Наконец, соберите значения в сообщение . ${\displaystyle (m_{1},m_{2},\dots ,m_{t})}$ ${\displaystyle M}$

Пример

Пусть и . Тогда и . Чтобы зашифровать шестибитное сообщение , мы разбиваем его на два 3-битных блока , так что . Мы выбираем случайное и вычисляем . Теперь мы вычисляем значения следующим образом: ${\displaystyle p=19}$ ${\displaystyle q=7}$ ${\displaystyle n=133}$ ${\displaystyle h=\lfloor log_{2}(log_{2}(133))\rfloor =3}$ ${\displaystyle 101001_{2}}$ ${\displaystyle m_{1}=101_{2},m_{2}=001_{2}}$ ${\displaystyle t=2}$ ${\displaystyle r=36}$ ${\displaystyle x_{0}=36^{2}{\bmod {1}}33=99}$ ${\displaystyle c_{i}}$

${\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad c_{1}=101_{2}\oplus 100_{2}=001_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad c_{2}=001_{2}\oplus 101_{2}=100_{2}\\x_{3}&=85^{2}{\bmod {1}}33=43\end{aligned}}}$

Итак, шифрование такое . ${\displaystyle (c_{1}=001_{2},c_{2}=100_{2},x_{3}=43)}$

Для расшифровки мы вычисляем

${\displaystyle {\begin{aligned}d_{p}&=5^{3}{\bmod {1}}8=17\\d_{q}&=2^{3}{\bmod {6}}=2\\u_{p}&=43^{17}{\bmod {1}}9=4\\u_{q}&=43^{2}{\bmod {7}}=1\\(r_{p},r_{q})&=(3,-8){\text{ since }}3\cdot 19+(-8)\cdot 7=1\\x_{0}&=1\cdot 3\cdot 19+4\cdot (-8)\cdot 7{\bmod {1}}33=99\\\end{aligned}}}$

Видно, что имеет то же значение, что и в алгоритме шифрования. Расшифровка, следовательно, выполняется так же, как и шифрование: ${\displaystyle x_{0}}$

${\displaystyle {\begin{aligned}x_{1}&=99^{2}{\bmod {1}}33=92=1011100_{2};\quad p_{1}=100_{2};\quad m_{1}=001_{2}\oplus 100_{2}=101_{2}\\x_{2}&=92^{2}{\bmod {1}}33=85=1010101_{2};\quad p_{2}=101_{2};\quad m_{2}=100_{2}\oplus 101_{2}=001_{2}\end{aligned}}}$

Доказательство правильности

Мы должны показать, что значение, вычисленное на шаге 6 алгоритма дешифрования, равно значению, вычисленному на шаге 4 алгоритма шифрования. ${\displaystyle x_{0}}$

В алгоритме шифрования по построению есть квадратичный вычет по модулю . Следовательно, он также является квадратичным вычетом по модулю , как и все остальные значения, полученные из него возведением в квадрат. Следовательно, по критерию Эйлера , . Тогда ${\displaystyle x_{0}}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}^{(p-1)/2}\equiv 1\mod {p}}$

${\displaystyle x_{t+1}^{(p+1)/4}\equiv (x_{t}^{2})^{(p+1)/4)}\equiv x_{t}^{(p+1)/2}\equiv x_{t}(x_{t}^{(p-1)/2})\equiv x_{t}\mod {p}}$

Сходным образом,

${\displaystyle x_{t}^{(p+1)/4}\equiv x_{t-1}\mod {p}}$

Возводя первое уравнение в степень, получаем ${\displaystyle (p+1)/4}$

${\displaystyle x_{t+1}^{((p+1)/4)^{2}}\equiv x_{t}^{(p+1)/4}\equiv x_{t-1}\mod {p}}$

Повторяя это раз, мы имеем ${\displaystyle t}$

${\displaystyle x_{t+1}^{(p+1)/4)^{t+1}}\equiv x_{0}\mod {p}}$

${\displaystyle x_{t+1}^{d_{p}}\equiv u_{p}\equiv x_{0}\mod {p}}$

И с помощью аналогичного рассуждения мы можем показать, что . ${\displaystyle x_{t+1}^{d_{q}}\equiv u_{q}\equiv x_{0}\mod {q}}$

Наконец, поскольку , мы можем умножить на и получить ${\displaystyle r_{p}p+r_{q}q=1}$ ${\displaystyle x_{0}}$

${\displaystyle x_{0}r_{p}p+x_{0}r_{q}q=x_{0}}$

откуда , по модулю и , и , следовательно . ${\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle u_{q}r_{p}p+u_{p}r_{q}q\equiv x_{0}\mod {n}}$

Безопасность и эффективность

Схема Блюма–Гольдвассера является семантически безопасной на основе сложности предсказания битов потока ключей, учитывая только конечное состояние BBS и открытый ключ . Однако шифртексты формы уязвимы для атаки с адаптивным выбранным шифртекстом , в которой противник запрашивает расшифровку выбранного шифртекста . Расшифровка исходного шифртекста может быть вычислена как . ${\displaystyle y}$ ${\displaystyle N}$ ${\displaystyle {\vec {c}},y}$ ${\displaystyle m^{\prime }}$ ${\displaystyle {\vec {a}},y}$ ${\displaystyle m}$ ${\displaystyle {\vec {a}}\oplus m^{\prime }\oplus {\vec {c}}}$

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

Ссылки

1. RFC  4086, раздел «6.2.2. Генератор последовательности Blum Blum Shub»

1. М. Блюм, С. Голдвассер, «Эффективная вероятностная схема шифрования с открытым ключом, которая скрывает всю частичную информацию», Труды конференции « Достижения в криптологии – CRYPTO '84 » , стр. 289–299, Springer Verlag, 1985.
2. Менезес, Альфред; ван Ооршот, Пол К.; и Ванстоун, Скотт А. Справочник по прикладной криптографии . CRC Press, октябрь 1996 г. ISBN 0-8493-8523-7 

Внешние ссылки

• Менезес, Ооршот, Ванстоун, Скотт: Справочник по прикладной криптографии (бесплатные загрузки в формате PDF), см. Главу 8