Come funziona un attacco di testo cifrato scelto su RSA da manuale?

Dato che hai il tuo n ed e, dovresti ottenere d e il tuo totiario. che è ϕ(n) .

Ecco l'esempio:

Uso: e(d) mod ϕ(n) ≡ 1 , puoi usare un algoritmo euclideo per risolvere questa equazione per ottenere d.

Come ottenere il n? Di solito prendi i tuoi due grandi numeri primi. ad es. (p = 7 e q = 11) Il tuo n in questo caso sarà p*q-(7*11 = 77) .

Come ottenere ϕ(n)-totient ? Di solito prendi (p-1)*(q-1) = ϕ(n) . Questo è (7-1)*(11-1) = 60 , quindi il tuo totiario è 60: ϕ(n) = 60 .

La tua e deve essere < n e non deve condividere fattori comuni con ϕ(n) , quindi e = 17

Quindi, e(d) mod ϕ(n) ≡ 1 ----------- > e=17, d=? , ϕ(n) = 60

sostituisci 17(d) mod 60 ≡ 1 < ---- in questo caso stai cercando d che è 53, perché 17*53 mod 60 ti darà il resto 1 che soddisfa questa equazione --- > e(d) mod ϕ(n) ≡ 1

Per decrittografare il tuo testo cifrato usa questo:
m=c^e mod n
dove:
m = testo semplice
c = testo crittografato e = chiave di crittografia
n = prodotto di due numeri primi grandi.

• n è il prodotto di due numeri primi grandi, quindi per definizione n è sempre un numero elevato.
• La domanda vuole che tu scriva un programma che decrittografa il cipehertext, che per definizione significa che il programma deve restituire il testo in chiaro.

Vorrei provare un attacco "meet-in-the-middle.

Dato una chiave pubblica (N,e) e il testo cifrato c e conoscendo il suo RSA da manuale su una chiave a 128 bit, puoi recuperare il messaggio originale (la chiave segreta) una buona frazione del tempo nel tempo O (2 ⁶⁸ ).

Fondamentalmente, si presume che il messaggio in chiaro sia ridimensionabile in due valori inferiori a 2 ⁶⁸ - cioè ( m = a*b ), dove a < b < 2 ⁶⁸ . Nota che sappiamo che da m < 2 ¹²⁸ se è fattore il fattore minore è inferiore a 2 ⁶⁴ .

Nota c = m^e (mod N) o c = a^e b^e (mod N) o c / a^e = b^e (mod N) per i valori corretti di a e b .

Costruisci due tabelle - la prima composta da c/a^e mod N per tutti i possibili valori di a (da 1 a 2 ⁶⁴ ), la seconda composta da b^e mod N per tutti i possibili valori di b (da 1 a 2 ⁶⁸ ).

Ora ordina i tuoi due elenchi e vedi se ci sono coppie a, b tali che a^e = C/b^e mod N . Se c'è una corrispondenza, hai preso i valori corrispondenti di a e b e il messaggio originale (la chiave AES 128 bit crittografata) sarà il loro prodotto m = a*b .