Décryptage du RSA

Question

Comment décrypter un message RSA si l’on ne dispose que de la clé publique ?

Par exemple, message:21556870,12228498Clé publique: (e = 15852553, n = 44331583)

Je sais que ces formules existent :

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

donc mon idée était que je pouvais mettre la valeur de e dans la première formule, puis dériver d qui fait partie de la clé privée.Cependant, je ne pense pas qu'il soit mathématiquement possible de trouver φ(n) ici.Alors, comment puis-je décrypter un message RSA avec uniquement la clé publique ?

Answer 1

"Comment pouvons-nous décrypter un message RSA si nous ne disposons que de la clé publique ?"

Bien, nous devons trouver la clé privée à partir de la clé publique.Cela devrait être trop difficile à faire dans des situations pratiques en général, car les algorithmes RSA sont des algorithmes de sécurité éprouvés sur le terrain, et les gens les utilisent avec précaution avec des bits suffisamment longs en général.

Cependant, l’exercice qui vous est assigné est conçu pour que vous puissiez pratiquer l’algorithme RSA.Les nombres utilisés ne sont pas suffisamment grands pour vous empêcher d'obtenir la clé privée étant donné la clé publique. Vous devriez être capable d'effectuer tous les calculs par programmation simple en utilisant votre langage de programmation et votre ordinateur préférés.

Essayez plus fort avant de regarder la réponse ci-dessous.

---

Clé publique: (e = 15852553, n = 44331583)

Prenons en compte n.Voici un programme Python simple.

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

En cours d'exécution factor(44331583), on obtient que 44331583 = 5003 * 8861.

Donc φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

Trouver l'inverse de e module φ(n).Voici un programme Python simple.

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

En cours d'exécution inverse(15852553, 44317720), on obtient que 15852553 * 1951097 = 1 (mod 44317720).C'est-à-dire l'inverse de e module φ(n) est d=1951097.

La clé privée correspondante est donc (d = 1951097, n = 44331583).

---

Calculer m**d (mod n) pour décrypter un message RSA (a.k.a.texte chiffré) m.Voici la fonction d'exponentiation modulaire populaire.

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) + ")")

En cours d'exécution modulo_pow(21556870, 1951097, 44331583) et modulo_pow(71, 15852553, 44331583), nous avons obtenu respectivement

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

Le message déchiffré est donc 71,111.Pouvez-vous trouver ce que cela signifie ?

Answer 2

Vous devrez prendre en compte la base de la clé publique RSA pour pouvoir déchiffrer.C'est tout l'intérêt :craquer RSA équivaut à l'affacturage, et l'affacturage est (présumé être) très difficile.