RSA

Notebook by P.Suzzi

Prerequisiti

Import

Si importa la funzionePrimeQ,del pacchettoNumberTheory,la quale permette di testare se un numero siaprimo.

<< NumberTheory`PrimeQ`

Definizione di funzioni

Si costruisce una funzione GenerateRandomPrime ( n_ ) che genera un primo a caso di n_ cifre.
Per funzionare la funzione precedente ha bisogno di un metodo che prende il primo successivo ad uno dato.

\(GetNextPrime[num_] := 
      Module[{n}, 
		If[EvenQ[num], n = num + 1, 
          n = num]; 
		While[\(! PrimeQ[n]\), 
          n = n + 2]; 
		n]\)
GenerateRandomPrime[n_] := 
      GetNextPrime[Random[Integer, {(10^(n - 1)), (10^n)}]]

Altre Funzioni

Serve anche due funzioni che, dato il modulo n,  
(a) convertano il testo in chiaro in blocchi di numeri minori di n
(b) dati blocchi di numeri minori di n ritornino il testo in chiaro
Per questo si sono utilizzate le seguenti funzioni ( prese da un notebook trovato in rete )

\(BreakUpMessage[cds_, blen_] := 
      Module[{c = cds}, 
		 (*\ 
          Riempie\ la\ frase\ di\ spazi\ *) 
		While[
          Mod[Length[c], blen] != 0, 
			c = Join[c, {32}]]; 
		Table[
          Take[c, {i, i + blen - 1}], {i, 1, Length[c] - 1, blen}]]\)
\(\(\(ListToNumber[l_] = ListToNumber[l, 0];\)\(
\)
    \)\)
\(\(\(ListToNumber[l_, num_] := 
	
      If[Length[l] == 0, 
        num, 
		ListToNumber[
          Rest[l], \((num*256)\) + First[l]]]\)\(	\)\(
\)
    \)\)
\(\(\(convertMessage[mes_, L_] := 
 (*\ 
        n\ is\ the\ public\ modulus\ *) 

      Module[{blklen, bitlen, l, blocks}, 
		bitlen = 
          Length[IntegerDigits[L, 2]] - 1; 
		blklen = 
          Quotient[bitlen, 8]; 
		l = ToCharacterCode[mes]; 
		blocks = 
          BreakUpMessage[l, blklen]; 
		Map[ListToNumber[#] &, 
          blocks]]\)\(
\)
    \)\)
\(\(\(restoreCharacterCode[l_]\  := \ 
      Flatten[
			Map[IntegerDigits[#, 256] &, l]]\)\(
\)
    \)\)
\(restoreMessage[
        l_] := 
		FromCharacterCode[
		Flatten[
			Map[
            IntegerDigits[#, 256] &, l]]]\)

Generazione delle chiavi

Setup dei parametri

Per prima cosa si ottengono due numeri primi grandi detti  p e q, se ne calcola il prodotto n. Poi si calcola la funzione phi di Eulero del numero n: ϕ(n) = numero di interi ≤ n coprimi con n stesso. Noto che n è il prodotto di due primi grandi, si sa che ϕ(n) = (p-1)(q-1).
RSA si basa appunto sulla difficoltà di fattorizzare n nei due primi p e q, in modo che il calcolo di ϕ risulti infattibile.

p = GenerateRandomPrime[10]
q  =  GenerateRandomPrime[10]
n  =  p*q
phi = (p - 1)*(q - 1)

Chiave Pubblica <e,n>

A questo punto si sceglie un intero e, che diverrà parte della chiave pubblica, in maniera tale che sia coprimo con ϕ(n), in modo che 
	mcd(e,ϕ) = 1 = e × d + k × ϕ , ovvero l'equazione d = (e^(-1)) (mod ϕ) ha una sola soluzione.

e = Random[Integer,  {1,  phi - 1}]
\(While[GCD[e, phi] ≠ 1, \ 
	
      e = Random[
          Integer, \ {1, \ 
            phi - 1}]
]\)
e;

Chiave Privata <d,n>

La chiave pubblica è stata così definita dalla coppia <e,n> mentre la chiave privata è costituita dalla coppia <d,n>, dove d è appunto l'inverso moltiplicativo di e in GF( ϕ ). Per calcolare d si ricorre all'algoritmo esteso di euclide, il quale calcola il masimo comun divisore di due numeri, fornendo come risultato anche i valori intermedi: MCD(e,ϕ)=1=ed + ϕk.

d = ExtendedGCD[e, phi][[2, 1]]

[1] fact 2.119 : Preso d = MCD(a,n) ;  l'equazione di congruenza ax=b(mod n) ha soluzioni se e solo se d divide b , nel qual caso ci sono esattamente d soluzioni tra 0 ed n-1; queste soluzioni sono congruenti a modulo n/d.
Da cui risulta che d è l'unica soluzione all'equazione di congruenza ed=1(mod ϕ).
La prova è la seguente:

Mod[e*d, phi] == 1

Encryption e Decryption

Funzioni Semplici

Le funzioni di cifratura e decifratura sono semplici esponenziazioni modulari in base n=p*q. Nel criptare si eleva il messaggio m alla potenza e, mentre nel decriptare si eleva il testo cifrato c alla potenza d.
NOTA: usando queste funzioni si assume che e, d, n siano già definiti e coerenti all'interno dell ambiente.

encrypt[ M_Integer ]  :=  
      PowerMod[ M,  e,  n ]
decrypt[ C_Integer ]  :=  PowerMod[ C, d, n ]

Funzioni per trattare gruppi di valori

Oltre alle precedenti è necessario aggiungere due funzioni che operino lo stesso trattamento su una lista di numeri, poichè il plaintext diventa una serie di numeri, ed il ciphertext a sua volta è composto da una sequenza di numeri.

encrypt[L_List]  :=  Map[encrypt,  L]
decrypt[L_List]  :=  Map[decrypt,  L]

Encryption

Una volta definito il messaggio lo si converte in un numero intero compreso nell'intervallo (1,p-1). Ottenuto tale numero lo si cifra con la chiave pubblica, in modo che solo l'utente che ha la corrispondente chiave privata possa decifrarlo.

plaintext = "RSA NON FA UNA PIEGA"
ToCharacterCode[plaintext]
m  =  convertMessage[plaintext,   n]
c = encrypt[m]

Decryption

Il proprietario della chiave privata riceve il testo cifrato C e lo decripta con la sua chiave privata <d,n>. Il messaggio ottenuto è identico all'originale.

m1 = decrypt[c];
restoreCharacterCode[m1];
restoreMessage[m1]

Signature & Verify

Firma e comunicazione

Le funzioni di firma e verifica sono molto semplici: per la firma è sufficiente utilizzare l'esponenziazione usando come parametro d: il dato segreto; ovviamente non è garantita la segretezza del messaggio.
autenticazione: (Subscript[S, SU])(H(m)) = (((H(m)))^SU) mod n
comunicazione: M  ||  (Subscript[S, SU])(H(m))

messg  =  "ACQUISTARE FIAT"
HashMessg = Hash[messg]
SsuHm = decrypt[HashMessg]
comunicazione = {messg,  SsuHm}

Ricezione e verifica

calcolo di H(m)
calcolo di ((((Subscript[S, SU])(H(m))))^PU) mod n
confronto

ricezione = comunicazione
messg1 = ricezione[[1]]
SsuHm1 = ricezione[[2]]
Hm1 = Hash[messg1];
toVerify = encrypt[SsuHm1];

La verifica è fatta utilizzando una funzione hash sicura sia sul messaggio spedito da colui che firma,sia sul messaggio decriptato dal ricevente. In questo caso, per la difficoltà di realizzare una funzione hash, si usa la funzione identità su una lista di parametri.

Ecco la verifica vera e propria

verify = Hm1 == toVerify

Firma ad occhi chiusi

Autenticazione di un messaggio oscurato

Supposto che l'utente X debba farsi autenticare da un'autorità U un messaggio m ( voto elettronico, cifra pagata, .. etc ), e supposto che il messaggio debba essere verificato da una controparte Y si procederà così:
1. X: sceglie a caso un numero r
2. X->U: testo cifrato c1 = m*(r^eU) mod nU
3. U->X: testo firmato c2 = (c1^dU)mod nU = ( (m^dU)*(r^(eU*dU)) ) mod nU  =  ( 
                  (m^dU)*r ) mod nU
4. X->Y: moltiplica per l'inverso moltiplicativo ed invia  c3 = c2*(r^(-1)) mod nU =(  (m^dU)* (r^(-1)) * 
                    r )  mod nU  =   (m^dU) mod nU
5. Y: verifica che (c3^eU) mod nU = m ; cioè che il messaggio m sia stato firmato da U.

Esecuzione passo-passo

X sceglie messaggio, genera r e spedisce c1 ad U

plaintext = "HO VOTATO BERLUSCONI?"
ToCharacterCode[plaintext]
m  =  convertMessage[plaintext,   n]
r = Random[Integer, {(10^2), (10^10)}]
c1 = m*encrypt[r]

U firma con la propria chiave privata

c2 = decrypt[c1]

X svela il messaggio  e spedisce c3 ad Y

rinv = ExtendedGCD[r, n][[2, 1]]
c3 = Mod[c2*rinv,  n]

Y riceve c3 e verifica che sia firmato con SU grazie a PU; se il messaggio è firmato lo utilizza

verify = m == encrypt[c3]
messaggioricevuto = restoreCharacterCode[m];
restoreMessage[m]

Riferimenti

Bibliografia

[1] Handbook Of Applied Cryptography