Определение частного показателя RSA

Question

Мой вопрос касается подписания RSA.

В случае подписания RSA:

шифрование -> y = x ^ d mod n, расшифровка -> x = y ^ e mod n

• x -> исходное сообщение
• y -> зашифрованное сообщение
• n -> модуль (1024 бит)
• e -> открытый показатель
• d -> частный показатель

Я знаю x, y, n и e. Зная это, я могу определить, д?

Answer 1

Если вы можете множить n = p * q, то d * e ≡ 1 (mod m), где m = φ (n) = (p-1) * (q-1), (φ (m) равно общая функция Эйлера ), в этом случае вы можете использовать расширенный евклидов алгоритм для определения d по e.(d * e - k * m = 1 для некоторого k)

Все это очень легко вычислить, за исключением факторинга, который спроектирован так, чтобы быть невероятно сложным, так что шифрование с открытым ключом является полезным методомэто не может быть расшифровано, если вы не знаете секретный ключ.

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

---

Шифрование и дешифрование с открытым ключом являются обратными операциями:

x = y ^e mod n = (x ^d ) ^e mod n = x ^de mod n = x ^{kφ (n) + 1} mod n = x * (x ^{φ (n)} ) ^k mod n = x mod n

где (x ^{φ (n)} ) ^k = 1 mod n из-за теорема Эйлера .

Answer 2

Ответ - да при двух условиях. Один, кто-то фактор н. Во-вторых, кто-то подсовывает алгоритм Микки и убеждает подписывающего использовать одно из нескольких возможных специальных значений для x.

Прикладная криптография Страницы 472 и 473 описывают две такие схемы. Я не совсем понимаю, как именно они будут работать на практике. Но решение состоит в том, чтобы использовать x, который не может полностью контролироваться кем-то, кто хочет определить d (он же злоумышленник).

Есть несколько способов сделать это, и все они включают хеширование x, изменение значения хэша предсказуемым образом, чтобы удалить некоторые нежелательные свойства, и затем подписывание этого значения. Рекомендуемые методы для этого называются «заполнением», хотя есть один очень превосходный метод, который не считается методом заполнения, который можно найти в практической криптографии.

Answer 3

Нет.В противном случае закрытый ключ был бы бесполезен.