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

Криптосистема Гольдвассера-Микали (GM) представляет собой алгоритм шифрования с асимметричным ключом, разработанный Шафи Голдвассером и Сильвио Микали в 1982 году. GM отличается тем, что является первой вероятностной схемой шифрования с открытым ключом, которая доказуемо безопасна при стандартных криптографических предположениях. Однако это не эффективная криптосистема, поскольку зашифрованный текст может быть в несколько сотен раз больше исходного открытого текста. Чтобы доказать свойства безопасности криптосистемы, Гольдвассер и Микали предложили широко используемое определение семантической безопасности .

Основа

Криптосистема GM семантически безопасна на основе предполагаемой неразрешимости квадратичной проблемы невязкости по модулю составного N = pq , где p, q — большие простые числа . Это предположение утверждает, что, учитывая ( x , N ), трудно определить, является ли x квадратичным вычетом по модулю N (т. е. x = y ² mod N для некоторого y ), когда символ Якоби для x равен +1. Проблема квадратичных вычетов легко решается с помощью факторизации N , а новые квадратичные вычеты могут быть сгенерированы любой стороной, даже без знания этой факторизации. Криптосистема GM использует эту асимметрию, шифруя отдельные биты открытого текста либо как случайные квадратичные остатки, либо как невычеты по модулю N , все с символом квадратичного остатка +1. Получатели используют факторизацию N в качестве секретного ключа и расшифровывают сообщение, проверяя квадратичную невязкость полученных значений зашифрованного текста.

Поскольку Гольдвассер – Микали дает значение размера примерно | Н | Чтобы зашифровать каждый бит открытого текста, шифрование GM приводит к существенному расширению зашифрованного текста . Чтобы предотвратить атаки факторизации , рекомендуется | Н | быть несколько сотен бит и более. Таким образом, схема служит в основном доказательством концепции, и более эффективные доказуемо безопасные схемы, такие как Эль-Гамаль с тех пор были разработаны .

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

Определение схемы

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

Схема основана на решении, является ли данное значение квадратом по модулю N , учитывая факторизацию ( p , q ) N. x Это можно сделать с помощью следующей процедуры:

Вычислите x _p = x mod p , x _q = x mod q .
Если $x_{p}^{(p-1)/2}\equiv 1{\pmod {p}}$ и $x_{q}^{(q-1)/2}\equiv 1{\pmod {q}}$ , то x — квадратичный вычет по N. модулю

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

Модуль, используемый в шифровании GM, генерируется так же, как и в криптосистеме RSA . (Подробнее см. RSA , генерация ключей.)

Алиса генерирует два различных больших простых числа p и q случайным образом и независимо друг от друга.
Алиса вычисляет N = pq .
Затем она находит некоторый невычет x такой, что символы Лежандра удовлетворяют $\left({\frac {x}{p}}\right)=\left({\frac {x}{q}}\right)=-1$ и, следовательно, символ Якоби $\left({\frac {x}{N}}\right)$ это +1. Значение x можно, например, найти, выбрав случайные значения и протестировав два символа Лежандра. Если p , q = 3 mod 4 (т. е. N — целое число Блюма ), то значение N − 1 гарантированно обладает требуемым свойством.

Открытый ключ состоит из ( x , N ). Секретный ключ — это факторизация ( p , q ).

Шифрование сообщений

Предположим, Боб желает послать сообщение m Алисе:

Боб сначала кодирует m как строку битов ( m ₁ , ..., m _n ).
Для каждого бита $m_{i}$ , Боб генерирует случайное значение $y_{i}$ из группы единиц по модулю N , или $\gcd(y_{i},N)=1$ . Он выводит значение $c_{i}=y_{i}^{2}x^{m_{i}}{\pmod {N}}$ .

Боб отправляет зашифрованный текст ( c ₁ , ..., c _n ).

Расшифровка сообщения

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

Для каждого i , используя простую факторизацию ( p , q ), Алиса определяет, является ли значение c _i квадратичным остатком; если да, то m _i = 0, в противном случае m _i = 1.

Алиса выводит сообщение m = ( m ₁ , ..., m _n ).

Свойства безопасности

Существует простой способ взлома этой криптосистемы к проблеме определения того, является ли случайное значение по модулю N с символом Якоби +1 квадратичным остатком. Если алгоритм А взламывает криптосистему, затем, чтобы определить, является ли данное значение x квадратичным вычетом по модулю N , мы проверяем A , чтобы увидеть, может ли оно взломать криптосистему, используя ( x , N ) в качестве открытого ключа. Если x не является остатком, то A должно работать правильно. Однако если x является остатком, то каждый «зашифрованный текст» будет просто случайным квадратичным остатком, поэтому А не может быть правильным более чем в половине случаев. Более того, эта проблема является случайной саморедуцируемой , что гарантирует, что для данного N каждый открытый ключ так же безопасен, как и любой другой открытый ключ.

Криптосистема GM обладает гомоморфными свойствами в том смысле, что если c0 _. , c1 _битов являются шифрованием битов , _m0 m1 , _m1 то c0c1 _будет N _m0 mod , шифрованием $m_{0}\oplus m_{1}$ . По этой причине криптосистема GM иногда используется в более сложных криптографических примитивах.

Ссылки

С. Гольдвассер, С. Микали (1982). «Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию». Материалы четырнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '82 . стр. 365–377. дои : 10.1145/800070.802212 . ISBN 0897910702 . S2CID 10316867 .
С. Гольдвассер, С. Микали (1984). «Вероятностное шифрование» . Журнал компьютерных и системных наук . 28 (2): 270–299. дои : 10.1016/0022-0000(84)90070-9 .

См. также

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