Найти оригинальное сообщение в RSA, если задано 2 шифра, а открытые ключи отличаются на 1 бит - PullRequest
Новая
       8

Найти оригинальное сообщение в RSA, если задано 2 шифра, а открытые ключи отличаются на 1 бит

0 голосов
/ 04 марта 2019

Используя RSA, Известно, что:

  • K_1 - открытый ключ
  • K_2 - открытый ключ
  • C_1 = E(M,K_1) - зашифрованный текст
  • C_2 = E(M,K_2) - зашифрованный текст
  • Ключи K_1 и K_2 отличаются только одним битом (мы нене знаю, какой бит).

Как мне найти оригинальный текст M? Примечание: перебор нельзя использовать.

Я где-то читал, что r*K_1 + s*K_2 = 1 modN, и r (или s) тоже могут быть отрицательными.

Таким образом, M можно найти следующим образом: : ((C_1 )^-1)^-r * (C_2)^s = M

Примечание: ((C_1 )^-1) может быть вычислено из C_1, поэтому M может быть

Вопросы: Кто сказал, что gcd(K_1,K_2) = 1,, тогда как может быть правдой, что r*K_1 + s*K_2 = 1 modN?

Во-вторых, если это решение не соответствует действительности, любой может сказать мне, как он могесть подход к этому вопросу?

1 Ответ

0 голосов
/ 04 марта 2019

Если предположить, что K_1 и K_2 являются допустимыми ключами, должно существовать следующее:

gcd(K_1, φ(φ(N))=1 и gcd(K_2, φ(N))=1, где φ - это функция Эйлера.

Учитывая, чтомы знаем, что K_1 и K_2 должны быть нечетными .С информацией о том, что эти ключи отличаются только на 1 бит, мы знаем, что gcd(K_1, K_2)=1.Это означает, что существует r s, например rK_1 + sK_2 = 1 (определение gcd).

Мы знаем, что C_1 = E(M,K_1) и C_2 = E(M,K_2).

Давайте умножим C_1^r на C_2^s и посмотрим, что мы получим: 

C_1^r * C_2^s = (M^K_1)^r * (M^K_2)^s = M^(rK_1 + sK_2) = M^1 = M

Мы нашли оригинальное сообщение M.

...