Decrittografia di RSA.

Question

Come possiamo decrittografare un messaggio RSA se abbiamo solo la chiave pubblica?

Ad esempio, Messaggio: 21556870,12228498. Chiave pubblica: (e = 15852553, n = 44331583)

So che queste formule esistono:

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

.

Quindi la mia idea era che potessi mettere il valore di E nella prima formula, quindi derivare D che fa parte della chiave privata.Tuttavia, non penso che sia matematicamente possibile trovare φ(n) qui.Quindi, in che altro modo posso decrittporre un messaggio RSA con solo la chiave pubblica?

Answer 1

"Come possiamo decrittografare un messaggio RSA se abbiamo solo la chiave pubblica?"

Bene, dobbiamo trovare la chiave privata dalla chiave pubblica . Questo dovrebbe essere troppo difficile da fare in situazioni pratiche in generale, poiché gli algoritmi RSA sono algoritmi di sicurezza testati dal campo testati dal tempo, e le persone lo utilizzano attentamente con bit a basso consumo in generale.

Tuttavia, l'esercizio assegnato a te è progettato per te per praticare l'algoritmo RSA. I numeri utilizzati non sono abbastanza grandi da impedire di ottenere la chiave privata data la chiave pubblica. Dovresti essere in grado di eseguire tutti i calcoli da parte della semplice programmazione utilizzando il tuo linguaggio di programmazione preferito e il computer.

prova più forte prima di guardare la risposta qui sotto.

---

.

KEY PUBBLICA: (e = 15852553, n = 44331583)

Facciamo il fattore n. Ecco un semplice programma Python.

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

.

Esecuzione di factor(44331583), otteniamo quel 44331583 = 5003 * 8861.

così φ(n) = (5003 - 1) * (8861 - 1) = 44317720

---

.

Trova l'inverso del e Modulo φ(n)Gode. Ecco un semplice programma 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

.

Esecuzione di inverse(15852553, 44317720), otteniamo quel 15852553 * 1951097 = 1 (mod 44317720). Cioè, l'inverso del e Modulo φ(n) è d=1951097.

Quindi, la chiave privata corrispondente è (d = 1951097, n = 44331583).

---

.

Computa m**d (mod n) per decifrare un messaggio RSA (A.k.a. cifratEtext) m. Ecco la popolare funzione modulare-esponenziale.

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

.

Esecuzione di modulo_pow(21556870, 1951097, 44331583) e modulo_pow(71, 15852553, 44331583), Abbiamo ottenuto, rispettivamente,

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

.

Quindi, il messaggio decivinto è 71,111. Riesci a trovare cosa significa?

Answer 2

Dovrai ritenere che la base della chiave pubblica RSA sia in grado di decifrare.Questo è l'intero punto: Cracking RSA è equivalente al factoring e il factoring è (presunto da essere) molto difficile.