4

В книге "Прикладная криптография" Шнайера, в разделе посвященном "Ментальному покеру" предлагается использовать для шифрования RSA с идентичными модулями. В этом случае процедура становится коммутативной, это в данном случае важно:

Т.е. для расшифровки карт последовательно зашифрованных двумя ключами, можно применять эти ключи в произвольном порядке.

А я вот что-то не могу сообразить - как у двух игроков могут быть ключи с идентичными модулями? Если модуль в RSA это произведение двух простых чисел - то существует единственный вариант его разложения на эти числа. И идентичными модули могут быть только если у обоих одинаковые пары ключей - а это лишает всю процедуру шифрования смысла.

Или тут имеется в виду что-то другое? Шнайер. Прикладная криптография

2
  • Укажите страницу книги, или вставьте цитаты с книги, что было понятно о чем вопрос.
    – Zergatul
    9 ноя 2017 в 23:55
  • добавил в вопрос всю страницу картинкой. 10 ноя 2017 в 8:11

1 ответ 1

4

И идентичными модули могут быть только если у обоих одинаковые пары ключей - а это лишает всю процедуру шифрования смысла.

Здесь вы неправы, для одного модуля существует очень много разных пар ключей. Обратите внимание на процедуру генерации ключей RSA: публичная экспонента e выбирается случайным образом (на практике всегда берут 65537). Мы можем выбрать любое e, и получим уникальную пару ключей.

В описанной в книге схеме не совсем тот RSA, который привычно видеть в других криптосхемах. Стороны генерируют разные ключи для одного модуля, и обе стороны знают его разложение на простые числа. Факторизация дает возможность вычислить приватный ключ с публичного ключа, но в приведенной схеме они не знают даже публичные ключи друг друга.

Только на шаге 7 они раскрывают свои ключи, что бы убедится в отсутствии мошенничества.

5
  • Насколько я понял, из описания RSA - е обычно выбирается небольшое и первое попавшееся. И тогда, при равных модулях остается возможность его подобрать. Насколько важно небольшое значение е, или это чисто для удобства? И тогда для целей данного алгоритма его можно выбирать случайно в более широком диапазоне? 10 ноя 2017 в 10:27
  • Да, e выбирают небольшое для того, что бы шифрование (или проверка подписи) выполнялись очень быстро.
    – Zergatul
    10 ноя 2017 в 10:29
  • Еще один момент - насколько я понял, в типовых случаях применения RSA такие нюансы скрыты от пользователя и нет готовых библиотек которые позволят мне сгенерировать ключи с одинаковым модулем и случайное e в большем диапазоне чем принято? 10 ноя 2017 в 10:35
  • т.е. с практической точки зрения мне нужно сгенерировать стандартными средствами общий для игроков ключ публичный+приватный, извлечь из него p,q,m, затем каждый игрок создаст по ним своё собственное случайное e. Так? 10 ноя 2017 в 10:44
  • Тут уже надо смотреть на конкретные реализации RSA, но я думаю во многих такой возможности нет. Но если есть поддержка длинной арифметики вместе с возведением в степень по модулю, то такую генерацию можно легко самому сделать, имея p, q, n.
    – Zergatul
    10 ноя 2017 в 10:46

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.