Расшифровка RSA

Question

Как мы можем расшифровать сообщение RSA, если у нас есть только открытый ключ?

Например, сообщение:21556870,12228498Открытый ключ: (e = 15852553, n = 44331583)

Я знаю, что существуют такие формулы:

gcd(e, φ(n)) = 1
ed mod φ(n) = 1

поэтому моя идея заключалась в том, что я мог бы поместить значение e в первую формулу, а затем получить d, которое является частью закрытого ключа.Однако я не думаю, что математически возможно найти φ(n) здесь.Итак, как еще я могу расшифровать сообщение RSA, используя только открытый ключ?

Answer 1

«Как мы можем расшифровать сообщение RSA, если у нас есть только открытый ключ?»

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

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

Попробуйте больше, прежде чем смотреть на ответ ниже.

---

Открытый ключ: (e = 15852553, n = 44331583)

Давайте фактор n.Вот простая программа на Python.

def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

Бег factor(44331583), мы получаем, что 44331583 = 5003 * 8861.

Так φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

Найдите обратную величину e по модулю φ(n).Вот простая программа на Python.

def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

Бег inverse(15852553, 44317720), мы получаем, что 15852553 * 1951097 = 1 (mod 44317720).То есть, обратное e по модулю φ(n) является d=1951097.

Итак, соответствующий закрытый ключ (d = 1951097, n = 44331583).

---

Вычислить m**d (mod n) для расшифровки сообщения RSA (также известного какзашифрованный текст) m.Вот популярная функция модульного возведения в степень.

def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

Бег modulo_pow(21556870, 1951097, 44331583) и modulo_pow(71, 15852553, 44331583), мы получили соответственно

21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

Следовательно, расшифрованное сообщение 71,111.Сможете ли вы найти, что это значит?

Answer 2

Вам нужно будет учитывать основу открытого ключа RSA, чтобы быть в состоянии расшифровать.То есть весь смысл: растрескивание RSA эквивалентно факторингу, а факторинг (предполагается быть) очень жестким.