Damgård-Jurik криптосистема [1] является обобщением криптосистемы Paillier . Он использует вычисления по модулю где является модулем RSA и(положительное) натуральное число . Схема Пайе - частный случай с. Приказ( Функция Эйлера ) можно разделить на . Более того,может быть записана в виде прямого произведения из. цикличен и имеет порядок , пока изоморфен . Для шифрования, сообщение преобразуется в соответствующий класс смежности из группы фактора а безопасность схемы зависит от сложности различения случайных элементов в разных смежных классах . Это семантически безопасно, если трудно решить, принадлежат ли два заданных элемента к одному классу смежности. Как и Пайе, безопасность Дамгарда-Юрика может быть доказана в рамках допущения о композитной остаточности, основанной на принятии решений .
Генерация ключей
- Случайным образом и независимо друг от друга выбираем два больших простых числа p и q .
- Вычислить а также .
- Выберите элемент такой, что для известного относительное простое число с а также .
- Используя китайскую теорему об остатках , выберите такой, что а также . Например может быть как в оригинальной схеме Пайе.
- Открытый (шифровальный) ключ .
- Секретный ключ (дешифрования) .
Шифрование
- Позволять быть сообщением, которое нужно зашифровать, где .
- Выбрать случайный где .
- Вычислить зашифрованный текст как: .
Расшифровка
- Зашифрованный текст
- Вычислить . Если c - допустимый зашифрованный текст, то.
- Примените рекурсивную версию механизма дешифрования Пайе, чтобы получить . В виде известно, можно вычислить .
Упрощение
Ценой отказа от классической криптосистемы Пайе в качестве экземпляра, Дамгарда-Юрика можно упростить следующим образом:
- База g фиксируется как.
- Показатель расшифровки d вычисляется таким образом, что а также .
В этом случае расшифровка производит . Используя рекурсивную дешифровку Пайе, мы получаем прямой текст m .
Смотрите также
- В Damgård-Jurik криптосистемы интерактивный тренажер демонстрирует применение голосования.
Рекомендации
- ^ Иван Дамгард , Мадс Юрик: обобщение, упрощение и некоторые приложения вероятностной системы открытых ключей Пайе . Криптография с открытым ключом 2001: 119-136