Гольдвасер-Микали (ГМ) криптосистема представляет собой алгоритм асимметричного ключа шифрования , разработанный Гольдвассером и Микал в 1982 году ГМ имеет честь быть первой вероятностной открытым ключом схемой шифрования , которая доказуемо обеспечить при стандартных криптографических предположениях. Однако это неэффективная криптосистема, поскольку зашифрованные тексты могут быть в несколько сотен раз больше, чем исходный открытый текст. Чтобы доказать свойства безопасности криптосистемы, Голдвассер и Микали предложили широко используемое определение семантической безопасности .
Основа
Криптосистема GM семантически безопасна на основе предполагаемой неразрешимости проблемы квадратичной остаточности по модулю составного N = pq, где p, q - большие простые числа . Это предположение утверждает, что при заданном ( x , N ) трудно определить, является ли x квадратичным вычетом по модулю N (т. Е. X = y 2 mod N для некоторого y ), когда символ Якоби для x равен +1. Проблема квадратичных вычетов легко решается с учетом факторизации N , в то время как новые квадратичные вычеты могут быть сгенерированы любой стороной, даже без знания этой факторизации. Криптосистема GM использует эту асимметрию, шифруя отдельные биты открытого текста как случайные квадратичные остатки или не-остатки по модулю N , все с квадратичным символом остатка +1. Получатели используют факторизацию N в качестве секретного ключа и дешифруют сообщение, проверяя квадратичную остаточность полученных значений зашифрованного текста.
Поскольку Голдвассер-Микали дает значение размера приблизительно | N | Чтобы зашифровать каждый бит открытого текста, шифрование GM приводит к значительному расширению зашифрованного текста . Чтобы предотвратить атаки факторизации , рекомендуется | N | быть несколько сотен бит или больше. Таким образом, схема служит в основном для подтверждения концепции, и с тех пор были разработаны более эффективные схемы с доказуемой безопасностью, такие как ElGamal .
Поскольку шифрование выполняется с использованием вероятностного алгоритма, данный открытый текст может создавать очень разные зашифрованные тексты при каждом шифровании. Это имеет значительные преимущества, поскольку не позволяет злоумышленнику распознать перехваченные сообщения, сравнивая их со словарем известных зашифрованных текстов.
Определение схемы
Голдвассер-Микали состоит из трех алгоритмов: вероятностного алгоритма генерации ключей, который создает открытый и закрытый ключи, вероятностного алгоритма шифрования и детерминированного алгоритма дешифрования.
Схема основана на решении , является ли данное значение х представляет собой квадрат по модулю N , учитывая разложение ( р , д ) из N . Это можно сделать с помощью следующей процедуры:
- Вычислить x p = x mod p , x q = x mod q .
- Если а также , То х есть квадратичный вычет по модулю N .
Генерация ключей
Модуль, используемый в шифровании GM, генерируется так же, как в криптосистеме RSA . (Подробнее см. RSA , генерация ключей.)
- Алиса генерирует два различных больших простых числа p и q случайным образом и независимо друг от друга.
- Алиса вычисляет N = pq .
- Затем она находит некоторый невычет x такой, что символы Лежандра удовлетворяюти, следовательно, символ Якоби +1. Значение x можно, например, найти, выбрав случайные значения и проверив два символа Лежандра. Если p , q = 3 mod 4 (т. Е. N является целым числом Блюма ), то значение N - 1 гарантированно будет иметь требуемое свойство.
Открытый ключ состоит из ( х , N ). Секретный ключ - это факторизация ( p , q ).
Шифрование сообщений
Предположим, Боб хочет отправить сообщение m Алисе:
- Боб сначала кодирует m как строку битов ( m 1 , ..., m n ).
- Для каждого бита , Боб генерирует случайное значение из группы единиц по модулю N , или. Он выводит значение.
Боб отправляет зашифрованный текст ( c 1 , ..., c n ).
Расшифровка сообщения
Алиса получает ( c 1 , ..., c n ). Она может восстановить m, используя следующую процедуру:
- Для каждого i , используя разложение на простые множители ( p , q ), Алиса определяет, является ли значение c i квадратичным остатком; в таком случае m i = 0, в противном случае m i = 1.
Алиса выводит сообщение m = ( m 1 , ..., m n ).
Свойства безопасности
Существует простое сокращение от взлома этой криптосистемы к проблеме определения того, является ли случайное значение по модулю N с символом Якоби +1 квадратичным вычетом. Если алгоритм A нарушает работу криптосистемы, то, чтобы определить, является ли данное значение x квадратичным остатком по модулю N , мы проверяем A, чтобы увидеть, может ли он взломать криптосистему, используя ( x , N ) в качестве открытого ключа. Если x не является остатком, то A должен работать правильно. Однако, если x является остатком, тогда каждый «зашифрованный текст» будет просто случайным квадратичным остатком, поэтому A не может быть правильным более чем в половине случаев. Кроме того, эта проблема является случайной самовосстанавливающейся , что гарантирует, что для данного N каждый открытый ключ будет таким же безопасным, как и любой другой открытый ключ.
Криптосистема GM имеет гомоморфные свойства в том смысле, что если c 0 , c 1 являются шифрованием битов m 0 , m 1 , то c 0 c 1 mod N будет шифрованием. По этой причине криптосистема GM иногда используется в более сложных криптографических примитивах.
Рекомендации
- С. Гольдвассер, С. Микали (1982). «Вероятностное шифрование и как играть в мысленный покер, сохраняя в секрете всю частичную информацию». Proc. 14-й симпозиум по теории вычислений : 365–377. DOI : 10.1145 / 800070.802212 .
- С. Гольдвассер, С. Микали (1984). «Вероятностное шифрование». Журнал компьютерных и системных наук . 28 (2): 270–299. DOI : 10.1016 / 0022-0000 (84) 90070-9 .