Введение

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

Основание

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

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

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

Вычислите xp = x mod p, xq = x mod q. Если и , то x является квадратичным вычетом по модулю N.

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

Модуль, используемый в шифровании GM, генерируется тем же способом, что и в криптосистеме RSA. (См. RSA, генерация ключей для получения подробностей.) Алиса генерирует два различных больших простых числа p и q случайным образом и независимо друг от друга. Алиса вычисляет N = p q. Затем она находит некоторое число x, не являющееся квадратичным остатком, такое, что символы Лежандра удовлетворяют определенному условию, и, следовательно, символ Якоби равен +1. Значение x можно найти, например, путем выбора случайных значений и проверки двух символов Лежандра. Если p и q дают остаток 3 при делении на 4 (то есть N является целым числом Блума), то значение N − 1 гарантированно обладает требуемым свойством. Публичный ключ состоит из пары (x, N). Секретный ключ – это разложение на множители (p, q).

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

Алиса получает (c1, , cn). Она может восстановить m, используя следующую процедуру: для каждого i, используя простое разложение на множители (p, q), Алиса определяет, является ли значение ci квадратичным остатком; если да, то mi = 0, иначе mi = 1. Алиса выводит сообщение m = (m1, , mn).

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

Существует простое сведение задачи взлома этой криптосистемы к проблеме определения, является ли случайное число по модулю N, имеющее символ Якоби +1, квадратичным вычетом. Если алгоритм A взламывает криптосистему, то для определения, является ли заданное значение x квадратичным вычетом по модулю N, мы проверяем, может ли A взломать криптосистему, используя (x, N) в качестве открытого ключа. Если x не является вычетом, то A должен работать корректно. Однако, если x является вычетом, то каждый "шифротекст" будет просто случайным квадратичным вычетом, поэтому A не может давать правильный ответ более чем в половине случаев. Более того, эта задача является саморедуцируемой, что гарантирует, что для заданного N каждый открытый ключ столь же безопасен, как и любой другой. Криптосистема GM обладает гомоморфными свойствами, в том смысле, что если c0 и c1 – шифры битов m0 и m1 соответственно, то c0 * c1 mod N будет шифром. По этой причине криптосистема GM иногда используется в более сложных криптографических примитивах.