Il sistema RSA per la crittografia a chiave pubblica

Giulio C. Barozzi
CIRAM-Università di Bologna

[Revisione: febbraio 2003]

Aritmetica modulare

Costruiamo le "tavole pitagoriche" dell'addizione e della moltiplicazione modulo m:

pitAdd[n_] :=  
      Module[{tabella  =  
            Table[Mod[i + j, n],  {i, 0, n - 1}, {j, 0, 
                n - 1}]}, 
tabella  =  
          Map[(Prepend[#, First[#]] &), 
            tabella]; 
tabella =  
          Join[{Prepend[Range[0, n - 1],  "+"]}, 
            tabella]; 
GridBox[tabella,  
            RowLines -> True,   ColumnLines -> True] // 
          DisplayForm]

pitAdd[7]

\(pitMolt[n_] := \ 
      Module[{tabella\  = \ 
            Table[Mod[i*j, n], \ {i, 0, n - 1}, {j, 0, 
                n - 1}]}, 
tabella\  = \ 
          Map[\((Prepend[#, #[[2]]] &)\), tabella]; 
tabella = \ 
          Join[{Prepend[Range[0, n - 1], \ "*"]}, 
            tabella]; 
GridBox[tabella, \ 
            RowLines -> True, \ \ ColumnLines -> True] // 
          DisplayForm]\)

pitMolt[7]

Scegliamo come modulo un numero composto, e determiniamo innanzitutto i numeri minori di esso e primi rispetto allo stesso.

coprimi[m_] := 
      Select[Range[1, m - 1],  (GCD[#, m] == 1) &]

Ad esempio:

cp  =  coprimi[14]

Costruiamo la tabella del gruppo moltiplicativo degli elementi invertibili modulo m:

\(grMolt[m_] := 
      Module[{cp\  = \ coprimi[m], lcp, \ 
          tabella}, 
lcp\  = \ 
          Length[cp]; 
tabella\  = \ 
          Table[Mod[
              cp[[i]]*
                cp[[j]], m], \ {i, 
              lcp}, {j, lcp}]; 
tabella\  = \ 
          Map[\((Prepend[#, #[[1]]] &)\), tabella]; 
tabella = \ 
          Join[{Prepend[cp, \ "*"]}, tabella]; 
GridBox[
            tabella, \ RowLines -> True, \ \ ColumnLines -> True] // 
          DisplayForm]\)

grMolt[14]

Ovviamente, se m è primo si ritrova quanto avevamo già calcolato con la funzione pitMolt, salvo la soppressione della prima riga e della prima colonna.

grMolt[7]

Cerchiamo i generatori del gruppo appena considerato:

generatori[m_] :=  
      Module[{cp  =  coprimi[m],  lcp}, 
lcp  =  
          Length[cp]; 
Do[
          If[Length[
                Union[Table[
                    Mod[cp[[k]]^
                        Range[lcp], m]]]] < lcp, 
            cp[[k]] = 0], {k, 1, 
            lcp}]; 
cp]

generatori[13]

Il piccolo Teorema di Fermat  ( ... e l'estensione di Eulero)

fermatUno[n_] :=  
      Module[{tabella  =  
            Table[{k,  k^EulerPhi[n],  Mod[k^EulerPhi[n], n]},  {k, 1, 
                n - 1}]}, 
GridBox[tabella,  
            RowLines -> True,   ColumnLines -> True,  
            ColumnAlignments -> Right,  ColumnsEqual -> True] // 
          DisplayForm]

fermatUno[5]

fermatUno[6]

fermatUno[12]

fermatDue[n_] :=  
      Module[{tabella  =  
            Table[{k,  k^(EulerPhi[n] + 1),  
                Mod[k^(EulerPhi[n] + 1), n]},  {k, 1, 
                n - 1}]}, 
GridBox[tabella,  
            RowLines -> True,   ColumnLines -> True,  
            ColumnAlignments -> Right,  ColumnsEqual -> True] // 
          DisplayForm]

fermatDue[7]

fermatDue[8]

fermatDue[15]

fermatDue[30]

Pierre de Fermat (1601-1665)

Leonhard Euler (1707-1783)

Il teorema di Dirichlet: ricerca di un primo in una progressione aritmetica

Ricerca di un primo nella successione k -> a + b * k, con MCD(a, b) = 1:

dir[a_,b_,k_] :=
 	Block[{n = a + k b, i},
	While[!PrimeQ[n], n = n+b];
n]

Ad esempio:

p = dir[3,7,100!]

Verifica:

PrimeQ[%]

Costruiamo due numeri primi "abbastanza grandi" congrui a 3 e 4 modulo 7:

p = dir[3,7,1000]

q = dir[4,7,2000]

Facciamo un controllo:

PrimeQ[{p, q}]

P . G .  Lejeune - Dirichlet (1805 - 1859)

Costruzione di un sistema RSA

Verifichiamo che  (p - 1)(q - 1) + 1, se p e q sono i numeri trovati, è multiplo di 7:

Mod[(p-1)(q-1) + 1, 7]

Poniamo:

n = p q

... questa è la chiave pubblica lunga; b = 7 è la chiave pubblica corta e

c = ((p-1)(q-1) + 1)/7

è la chiave segreta. Per spedire il "messaggio"  ( ≤ n)

mess = 123456

... si calcola mess^7 mod n, cioè

PowerMod[mess, 7, n]

Questo è il messaggio "criptato". Il ricevente utilizza la sua chiave segreta e calcola  
			messcriptato^c mod n, 
cioè

PowerMod[%, c, n]

... ritrovando il messaggio originale.

Manipolazione di stringhe

Precodifica del messaggio:

messaggio = "La vispa Teresa avea tra l'erbetta   "

Characters[messaggio]

Partition[%,3]

Map[StringJoin,%]

messnumuno = Map[ToCharacterCode,%]

Impacchettamento dei tre numeri di ciascuna terna:

codnum[{a_, b_, c_}] := 10^6 a + 10^3 b + c

Ad esempio:

messnumdue = Map[codnum, messnumuno]

Tutti i passaggi precedenti in una sola funzione di codifica da caratteri a numeri (si utilizza la funzione codnum):

precod[messaggio_] :=
	Block[{a,b,c, messalfa, messnum},
		messalfa = Partition[Characters[messaggio], 3];
		messalfa = Map[StringJoin, messalfa];
		messnum = Map[ToCharacterCode, messalfa];
		messnum = Map[codnum, messnum]
	]

Ad esempio:

precod["La vispa Teresa avea tra l'erbetta   "]

Inversione della precodifica:

decodnum[n_]:= 
	Block[{a, b, c, nn = n},
	c = Mod[nn,10^3];
	nn =(nn-c)/10^3;
	b = Mod[nn,10^3];
	nn =(nn-b)/10^3;
	a = Mod[nn,10^3];
	{a,b,c}]

Esempio:

Map[decodnum, messnumdue]

Map[FromCharacterCode,%]

MapAll[StringJoin, %]

Il tutto in una sola funzione di decodifica da numeri a caratteri (si utilizza la funzione decodnum):

decod[messnum_] :=
	Block[{messalfa, ternenum},
 		ternenum = Map[decodnum, messnum];
 		messalfa = Map[FromCharacterCode, ternenum];
 		messalfa = MapAll[StringJoin, messalfa]
 ]

Ad esempio:

decod[messnumdue]

Altro esempio:

precod["Nel mezzo del cammin di nostra vita  "]

decod[%]

... ancora:

precod["mi ritrovai per una selva oscura  "]

decod[%]

Adesso costruiamoci un esempio con numeri più grandi, in modo che n abbia almeno 10 cifre:

p = dir[3,7,10000]

q = dir[4,7,12000]

Controllo:

PrimeQ[{p,q}]

n = p q

Ridefiniamo la chiave segreta c :

c = ((p-1)(q-1)+1)/7

Costruiamo una funzione per criptare una sequenza di cifre:

pmod[k_] := PowerMod[k,7,n]

invpmod[k_]:= PowerMod[k,c,n]

cript[seqnum_] := Map[pmod, seqnum]

Funzione di decriptazione:

decript[seqnum_] := Map[invpmod, seqnum]

Ricordiamo i nomi delle quattro funzioni di base:

-- precod: per passare dalla stringa alfanumerica alla sequenza di numeri
-- cript: per criptare la sequenza di numeri
-- decript: per decriptare la sequenza di numeri
-- decod: per ricostruire la sequenza alfanumerica.

Esempio finale:

messaggio = "Sempre caro mi fu quest'ermo colle  "

precod[%]

cript[%]

decript[%]

decod[%]

messaggio = "Gaudeamus igitur, juvenes dum sumus  "

precod[%]

cript[%]

decript[%]

decod[%]