Appunti di crittografia*

Indice:

1. PREFAZIONE ..............................................................2 2. DIVISIBILITÀ E NUMERI PRIMI ....................................3 3. CONGRUENZE ............................................................9 4. I TEOREMI DI FERMAT E DI EULERO.........................14 5. IL PROBLEMA DELLA DISTRIBUZIONE DELLE CHIAVI 17 6. CRITTOGRAFIA A CHIAVE PRIVATA ..........................18 7. CRITTOGRAFIA A CHIAVE PUBBLICA ........................21 8. FIRME AUTENTICATE ...............................................24 9. N È PRIMO ?.............................................................25 10. QUALI SONO I FATTORI DI N ?.................................27

BIBLIOGRAFIA ..........................................................31

* Alberto Zorzi – 26/02/2002 . Ringrazio i professori Elio Canestrelli , Andrea Ellero e Marco Li Calzi per i

commenti e le correzioni.

2

1. Prefazione Si supponga di dover inviare un messaggio e di volere la garanzia che solo il destinatario lo possa comprendere; si desidera cioè nascondere il significato del messaggio in modo che risulti incomprensibile a chiunque altro all ’ infuori del destinatario. Le tecniche utili zzate a questo scopo costituiscono la crittografia che si può definire come la “scienza che ha per oggetto l’occultamento del significato di un messaggio” . Per rendere occulto il significato di un messaggio la crittografia lo trasforma in un altro messaggio che dovrebbe (ma vedremo che non sempre se ne ha la garanzia assoluta) essere incomprensibile a chiunque all ’ infuori delle persone autorizzate a leggerlo; il messaggio così trasformato è detto crittato o cifrato. Le tecniche adottate dalla crittografia sono naturalmente numerose (non è diff icile immaginare qualche modo per cambiare l’ordine delle lettere dell ’alfabeto) ed a volte anche vecchie di parecchi secoli (ad esempio già gli antichi greci adottavano dei sistemi per crittare i messaggi). Con lo sfruttamento sempre maggiore delle reti informatiche la crittografia ha assunto un ruolo cruciale; si pensi ad esempio all ’e-commerce (la possibilit à di comprare e pagare via rete): gli estremi del pagamento (ad esempio il numero della carta di credito) devono essere intelli gibili solo alla ditta venditrice e non ad eventuali “malintenzionati“ . Il procedimento di crittografia qui ill ustrato è il sistema a chiave pubblica RSA che attualmente è il più diffuso; per arrivare al nocciolo del sistema RSA occorre conoscere almeno alcuni aspetti della matematica che tratta i numeri interi (in genere nota come teoria dei numeri). La presente dispensa ha appunto lo scopo di fornire alcune conoscenze minime di teoria dei numeri per poter affrontare gli aspetti essenziali del sistema di crittografia RSA. Nel seguito si fa riferimento alle seguenti notazioni:

- { }�,2,1,0=N è l’ insieme dei numeri naturali - { }�� ,2,1,0,1,2, −−=Z è l’ insieme dei numeri interi

-

≠∈= 0,: beZba

b

aQ è l’ insieme dei numeri razionali, cioè tutte le frazioni di

numeri interi (naturalmente con denominatore non nullo) - se Qa ∈ , allora: a è il massimo degli i nteri x tali che ax ≤ ed è detto pavimento di

a o parte intera di a; ad esempio: 27.210

27 ==

e 22 =

- se Qa ∈ , allora: a è il minimo degli i nteri x tali che ax ≥ ed è detto soffitto di a; ad

esempio: 37.210

27 ==

e 22 =

3

2. Divisibili tà e numeri primi Teorema (la divisione tra interi): se Zba ∈, e b > 0, allora esiste un’unica coppia di interi q ed r tali che: rqba += e br <≤0 q ed r sono detti rispettivamente il quoziente ed il resto della divisione di a per b. Il resto della divisione di a per b è indicato con ba mod .

Dim. - esistenza: dimostriamo innanzi tutto che una tale coppia di interi esiste. Si consideri

l’ insieme { }0: ≥−∈−= nbaeZnnbaA . A è non vuoto: se 0≥a per n = 0 si ha Aa∈ ; se invece a < 0 allora basta prendere n abbastanza grande in valore assoluto e con

segno negativo per avere Anba ∈− . Dunque, essendo A un insieme non vuoto di numeri naturali , deve contenere un elemento minimo qbar −= ; si verifica immediatamente che q ed r soddisfano l’enunciato.

- unicità: se esistesse un’altra coppia q’ ed r’ di interi che soddisfa l’enunciato, allora oltre ad avere rqba += con br <≤0 , si avrebbe '' rbqa += con br <≤ '0 . Sottraendo membro a membro le due equazioni si ha ')'(0 rrbqqaa −+−=−= e se fosse 'qq > allora l’ultima espressione sarebbe maggiore di zero essendo bbqq ≥− )'( e

brr <−≤ '0 , dunque non può essere 'qq > . In modo analogo si dimostra che non può

accadere che sia qq >' e dunque qq =' e '' rbqaqbar =−=−= . Osservazioni: - vediamo come cambiano il quoziente ed il resto della divisione se si cambia il segno di a: se

ad esempio a = 15 e b = 3 si ha 3515 ⋅=q

che moltiplicando per 1− diventa 3515 ⋅−=− ,

dunque la divisione di –15 per 3 dà 5−=q e 0=r .

Se invece a = 17 e b = 3 si ha rq23517 +⋅= e moltiplicando per 1− si ottiene

23517 −⋅−=− , ma certamente 2− non è il resto della divisione di –17 per 3 (che dev’essere ≥ 0); sommando e sottraendo 3 si ha ( ) ( )

rq

2331517 −+⋅−−=− , cioè 6−=q e

1=r sono il quoziente ed il resto di –17 diviso 3. Quindi, in generale, se 0≥a , 0>b e q e r sono rispettivamente il quoziente ed il resto della divisione tra a e b, allora rqba += e rqba −+−=− ; perciò se 0=r il quoziente ed il resto della divisione di a− per b sono rispettivamente q− e 0. Se invece 0>r si ha

(sommando e sottraendo b) ( ) rbbqa −+−−=− 1 , e dunque quoziente e resto sono 1−− q e rb − .

- il quoziente della divisione di a per b coincide con

b

a: se 0≥a è evidente perché

b

a

dà il numero di volte che “b sta in a” , se invece a < 0 si procede come al punto precedente

osservando che

b

a coincide rispettivamente con

−−

b

a se il resto della divisione di a−

per b è zero e con 1−

−−

b

a altrimenti.

Def.: un intero a divide un intero b (o b è multiplo di a) se acbZc =∈∃ : e si scrive ba | , mentre per indicare che a non divide b si scrive ba |/ . Inoltre a è detto un divisore di b; se a

4

divide b ed è minore di b allora a è detto divisore proprio, se è anche a > 1 a è un divisore non banale. Per indicare che a divide b e c si scrive: cba ,| . Esempi: - per indicare che 1 divide ogni intero si può scrivere: Zaa ∈∀|1 - evidentemente si ha: 4,4|2 − e in generale se ba | si ha anche ba −| , cioè bba −,| Osservazioni: - ogni intero ha come divisori 1 e sé stesso - dato che la definizione di divisibilit à è stata data in termini di “prodotto” , e non di

“divisione”, ha senso affermare che zero divide un intero (e questo intero deve essere lo zero stesso). Viceversa, qualsiasi intero divide lo zero

- se a > 0 allora ba | se e solo se il resto della divisione di b per a è zero, cioè 0mod =ab

- se 0>b e ba | allora ab ≥ Def.: il massimo comune divisore tra due numeri interi a e b non entrambi nulli è il più grande intero che li divide entrambi e si indica con ( )baMCD , o con ( )ba, . Se due interi hanno massimo comune divisore 1 sono detti coprimi. Il minimo comune multiplo di a e b è il più piccolo intero positivo multiplo di entrambi e si indica con mcm(a,b). Le estensioni delle definizioni di MCD e mcm a più di due interi sono ovvie e si usano le notazioni:

( )naaaMCD ,,, 21 � e ( )naaamcm ,,, 21 � .

Esempi: - ( ) 214,12 =MCD mentre ( ) 113,12 =MCD e quindi 12 e 13 sono coprimi

- ogni numero naturale a è coprimo con 1, infatti si ha sempre ( ) 1,1 =aMCD Osservazioni: - per ogni coppia di interi (non entrambi nulli ) si ha: ( ) ( )abMCDbaMCD ,, = e

( ) 1, ≥baMCD

- poiché ogni intero non nullo divide zero si ha: ( ) 00, ≠∀= aaaMCD

- se ba | allora ( ) abaMCD =,

- tra MCD e mcm di due interi vale la seguente relazione: ( ) abbaMCDbamcm =⋅ ,),( , la

cui giustificazione risulta ovvia se si rappresentano a e b come prodotti di numeri primi (vedi il teorema fondamentale dell ’aritmetica)

- due interi consecutivi sono sempre coprimi, cioè ( ) ZaaaMCD ∈∀=+ 11, ; infatti, se due interi distinti non sono coprimi allora devono avere come MCD almeno 2, perciò devono essere multipli di uno stesso fattore ≥ 2 e quindi differire almeno di 2 (essendo distinti), cioè non possono essere consecutivi. Questa osservazione consente di dimostrare un facile risultato sui numeri interi: se 0>n è un intero e si scelgono 1+n interi compresi tra 1 e n2 , allora almeno 2 degli i nteri scelti sono coprimi (infatti almeno due devono essere consecutivi).

5

- vale la seguente proprietà che consente il calcolo del MCD tra più di due interi calcolando ripetutamente il MCD tra due interi:

( ) ( )( )( )��� nnn aaMCDaMCDaMCDaaaMCD ,,,,,, 12121 −=

ad esempio: ( ) ( )( ) ( ) 1050,40300,350,40300,350,40 === MCDMCDMCDMCD . Una proprietà analoga vale per il mcm.

Teorema (algoritmo di Euclide): se Nba ∈, e 0>b , allora la seguente successione:

≠>==

=−−−

altrimenti

xensexx

nseb

nsea

xnnn

n

0

01mod

1

0

112

ha un numero finito di termini non nulli e l’ultimo termine non nullo è ( )baMCD , ; inoltre

( ) babaMCDZ βαβα +=∈∃ ,:, . Dim. - dividendo a per b si ha: rqba += . Allora bad ,| (cioè d divide a e b) se e solo se

rbd ,| e quindi ( ) ( )rbMCDbaMCD ,, = - siccome br <≤0 , i termini della successione > 0 sono strettamente decrescenti e in

numero finito. Quindi, se 0>nx e 01 =+nx :

( ) ( ) ( ) nnn xxxMCDxxMCDxxMCD ==== +12110 ,,, �

- dalle relazioni: 2110 xxqx += , nnn xqxxxqx =+= −13221 ,, �

si ottiene: 1102 xqxx −= , ( ) 1011023 ,,1 xxxxqxqx n βα −=++−= �

Esempio: per determinare il MCD di 91 e 25 si costruisce la successione in cui i primi due termini sono 91 e 25 e ogni nuovo termine è il resto della divisione dei due precedenti; ci si arresta quando si ottiene 0 e l’ultimo termine ≠ 0 è il MCD cercato. Si ottiene così:

91 , 25 , 16 , 9 , 7 , 2 , 1 , 0 e dunque ( ) 125,91 =MCD . Osservazioni: - nell ’applicazione dell ’algoritmo di Euclide non è necessario iniziare dall ’ intero più grande, si

arriva cioè allo stesso risultato (con un passaggio in più) anche iniziando dal più piccolo; ad esempio per il calcolo di ( )25,91MCD iniziando da 25 si ha:

25 , 91 , 25 , 16 , 9 , 7 , 2 , 1 , 0 - il numero di passi dell ’algoritmo (cioè il numero di termini > 0) può essere diminuito

riducendo i termini della successione (ma mantenendo comunque costante il MCD tra due termini consecutivi), ad esempio: - si può sostituire il resto della divisione di a per b con la differenza tra il più piccolo

multiplo di b maggiore o uguale ad a, ed a. Indicando tale numero con ba∇ , si ha:

babbaa ∇−⋅= / ; quindi, ad esempio: 3301111

301130 =−⋅

=∇ , mentre

811mod30 = . Se ad ogni passo dell ’esempio precedente si sostituisce l’operatore “mod” con l’operatore “ ∇ ” si ottiene:

91 , 25 , 9 , 2 , 1 , 0.

6

In effetti, ad ogni passo dell ’algoritmo si può calcolare il nuovo termine scegliendo tra gli operatori mod e ∇ quello che dà un “ resto” minore

- siccome: ( )

=⇒/

k

baMCDbaMCDbkak ,,|,| , allora per calcolare ( )25,91MCD si

può sostituire 25 con 5, perché 5 divide 25 ma non 91, ottenendo: 91 , 5 , 1 , 0

Def.: un numero naturale p > 1 è detto pr imo se i suoi unici divisori sono 1 e p, altrimenti è detto composto.

Osservazioni: - vediamo un procedimento per ottenere tutti i numeri primi fino ad un valore stabilit o n;

innanzi tutto si scrivono di seguito gli i nteri > 1 e ≤ n. Il primo intero della sequenza è 2 e si eliminano tutti i multipli di 2 successivi al 2; il secondo intero della sequenza restante è 3 e si eliminano tutti i multipli di 3 successivi al 3, e così via. Alla fine del procedimento gli interi restanti sono tutti i numeri primi ≤ n. Questo procedimento è detto crivello di Eratostene. E’ evidente che la sequenza di interi presa all ’ inizio del procedimento non può iniziare da 1 (dato che qualsiasi intero è multiplo di 1).

- per verificare se un dato intero n è primo si può (banalmente) controllare se la definizione è verificata, se cioè non esistono divisori di n tra 2 ed 1−n . In effetti è suff iciente arrestarsi a

n , dato che se nab = allora non può accadere che sia nba >, , e inoltre (se n è

dispari) basta considerare solo gli i nteri dispari, dato che l’unico primo pari è 2 . La verifica se un intero con poche cifre, ad esempio 4, è primo si effettua con facilit à (anche senza l’ausili o di una calcolatrice), ma al crescere del numero delle cifre la verifica diventa sempre più diff icile. Più avanti saranno descritti dei procedimenti per affrontare tale verifica anche per numeri con qualche decina di cifre.

- attualmente non si conoscono delle formule che forniscano tutti i numeri primi oppure solo numeri primi (salvo naturalmente i procedimenti che richiedono la preventiva conoscenza di tutti i primi)

Teorema: p primo e bpoapabp ||| ⇒

Dim. - ( ) ( ) bpbbcpbpbabpapaMCDap |1:,1,| ⇒=+⇒=+⇒=+∃⇒=⇒/ βαβαβαβα

nel penultimo passaggio si tiene conto del fatto che p divide ab e che quindi esiste un intero c per cui pcab = .

Teorema (fondamentale dell ’ar itmetica): ogni intero n > 1 si può rappresentare in modo unico come prodotto di primi (si dice anche che ogni intero ha un’unica fattorizzazione in primi).

Dim. - esistenza: se n è primo è già fattorizzato. Se invece n è composto può essere rappresentato

come il prodotto di due interi a e b tali che nba << ,1 . A loro volta a e b sono o primi o composti e se sono composti … . E così via, il procedimento dovrà evidentemente terminare (trattandosi di numeri interi > 0 e sempre più piccoli ) e alla fine fornisce la fattorizzazione richiesta di n.

7

- unicità: l’unicità va intesa nel senso che non possono esserci due prodotti di primi con

almeno un primo diverso che diano lo stesso risultato. Se si ha: ∏∏==

=m

jj

n

ii qp

11

, dove i ip

ed i jq sono numeri primi, allora, applicando ripetutamente il teorema precedente, si

dimostra immediatamente che i due prodotti contengono gli stessi primi: 1p divide

∏=

m

jjqq

21 , quindi o 1p divide 1q (e quindi 11 qp = ) , oppure divide ∏

=

m

jjq

2

, e così via.

Osservazioni: - purtroppo il teorema precedente garantisce che n può essere scritto come prodotto di fattori

primi ma non dice come trovarli . Il problema di “ fattorizzare” un intero, cioè di scriverlo come prodotto di suoi divisori non banali , assume un ruolo centrale nella crittografia e alcuni procedimenti di fattorizzazione saranno presentati più avanti. Ne anticipiamo uno piuttosto eff iciente che si basa sull ’algoritmo di Euclide. Si supponga di dover fattorizzare un intero composto n: si calcolano i numeri 1021 ,,, PPP � , dove 1+mP è

il prodotto dei primi compresi tra 100⋅m e ( ) 1001 ⋅+m (ad esempio 1P è il prodotto dei primi fino a 100), e successivamente con Euclide si calcolano:

( ) ( ) ( )1021 ,,,,,, PnMCDPnMCDPnMCD � che forniscono i fattori di n minori di 1000.

Questo metodo ha almeno due inconvenienti: la necessità di conoscere preventivamente tutti i primi che potrebbero essere fattori di n e le dimensioni degli i nteri mP . Come esempio

cerchiamo i fattori primi di 132302413=n ; i numeri 1021 ,,, PPP � ed i relativi MCD con n

sono: 17560705310214733945518424723055679631 =P ( ) 1, 1 =PnMCD

16218364806707718979876079296917481133830805092 =P ( ) 1, 2 =PnMCD

9844774412813071883544703343826202566473 =P ( ) 263, 3 =PnMCD

952980119541385980827393622875049766523394 =P ( ) 1, 4 =PnMCD

18894191819579038761565110237014997812274535405 =P ( ) 1, 5 =PnMCD

9813819592244562196930378400925305630696 =P ( ) 571, 6 =PnMCD

1469369111200933065306274189788049387903189287 =P ( ) 1, 7 =PnMCD

729319108812439071676565377612716866467818 =P ( ) 1, 8 =PnMCD

768152901629918525520021460672395883623435739 =P ( ) 881, 9 =PnMCD

81294139003169330273891630553069500139990710 =P ( ) 1, 10 =PnMCD

dunque 132302413881571263 =⋅⋅=n Teorema: i numeri primi sono infiniti

Dim.

- se per assurdo nppp ,,, 21 � fossero tutti i primi, allora 11

+∏=

n

iip sarebbe un intero non

divisibile per nessun primo (infatti la divisione per qualsiasi primo darebbe resto 1), in contraddizione col teorema fondamentale dell ’aritmetica.

Osservazioni:

8

- se nppp ,,, 21 � sono i primi n numeri primi non è detto che 11

+∏=

n

iip sia primo; ad

esempio: 50959113117532 ⋅=+⋅⋅⋅⋅⋅

9

3. Congruenze Def.: un intero a è congruo ad un intero b modulo un intero 0>m se e solo se bam −| , e si scrive:

)(modmba ≡ . La notazione )(modmba ≡ è detta una congruenza e si legge: “a è congruo a b modulo m” . L’ intero m è detto il modulo della congruenza, mentre b è detto un residuo di a (e, viceversa, a un residuo di b). Per indicare che a non è congruo a b modulo m si scrive: )(modmba ≡/ . Si raccomanda di non confondere questo “mod” con quello utili zzato per indicare il resto della divisione tra due interi, anche se le diverse caratteristiche di utili zzo dovrebbero escludere qualsiasi equivoco.

Esempi: - )11(mod830 ≡ perché 112830 ⋅=− e quindi 8 è un residuo di 30 (e 30 è un residuo di 8)

modulo 11; sommando e sottraendo 11 ad 8 si ottengono anche i residui 19 e -3: )11(mod1930 ≡ e )11(mod330 −≡

Osservazioni: - se )(modmba ≡ allora sommando un multiplo di m a b, si ottiene un nuovo residuo di a

modulo m e dunque i residui di a sono infiniti

- se a è un intero, allora dividendo a per m si ha: mamm

aa mod+

= e dunque:

)(modmod mmaa ≡ e ma mod è il minimo residuo ≥ 0 di a modulo m. Inoltre )(modmba ≡ se e solo se le divisioni di a e b per m danno gli stessi resti, cioè

mbma modmod = - evidentemente esistono al massimo m valori interi non congrui a due a due modulo m; un tale

insieme di interi è detto un sistema completo di residui modulo m; ad esempio: 0 , 1 , … , 1−m costituiscono un sistema completo di residui modulo m

- per le congruenze valgono le seguenti ovvie proprietà (analoghe a quelle dell ’uguaglianza) per qualsiasi Zcba ∈,, : - )(modmaa ≡

- )(mod)(mod mabmba ≡⇒≡

- )(mod)(mod)(mod mcamcbemba ≡⇒≡≡

(ciò implica che una congruenza modulo m è una relazione di equivalenza e, come tale, individua una partizione di Z. Gli i nsiemi della partizione sono le classi di equivalenza della relazione che in questo caso sono detti classi di congruenza modulo m; l’ insieme delle classi di congruenza modulo m è indicato con Z/mZ ).

Teorema: per le congruenze valgono le seguenti proprietà: i) )(modmba ≡ e )(mod)(mod mdbcamdc ±≡±⇒≡ ii ) )(modmba ≡ e )(mod)(mod mbdacmdc ≡⇒≡

iii ) )(modmba ≡ e ( )

≡⇒=

d

m

d

b

d

ambaMCDd mod,,

10

iv) )(modmbcac ≡ e ( )

≡⇒=

d

mbamcMCDd mod,

Dim.: ovvia Esempi: a) dato che: )11(mod830 ≡ e )11(mod740 ≡ , per le proprietà i) e ii ) si ha:

)11(mod478403070 ≡+≡+= e )11(mod17840301200 ≡⋅≡⋅= b) nella congruenza )7(mod5085≡ , 85 e 50 sono entrambi multipli di 5 e si sarebbe tentati

di semplificare ottenendo: )7(mod1017 ≡ . E’ consentito ? La risposta è si (in questo caso) e

la giustificazione è data dalla proprietà iv) essendo: ( ) ( ) 17,5, === MCDmcMCDd . Quindi, in generale, si possono sempli ficare i fattori che sono coprimi col modulo (e si parla di regola di cancellazione). Non si può invece sempli ficare per 5 ad esempio nella congruenza

)10(mod5585≡ , dato che 5 in questo caso non è coprimo col modulo 10. c) risolvere: )13(mod?7100 ≡ .

Si osservi innanzi tutto che esiste una soluzione banale (il numero stesso) e che le soluzioni sono infinite (sono tutti i residui di 1007 modulo 13). Se a è una soluzione allora lo sono anche gli i nteri ottenuti sommando un multiplo di 13 ad a, cioè gli i nteri del tipo

Zkka ∈+ ,13 per semplicità ci interessa determinare la soluzione compresa tra 0 e 12, cioè il minimo residuo ≥ 0. Vediamo dunque come realizzare il conto, anche perché calcoli del genere sono abbastanza frequenti in crittografia. Per calcolare 1007 modulo 13, invece di calcolare la potenza e quindi il resto della sua divisione per 13 (conto troppo impegnativo!), conviene sfruttare la proprietà ii ) e procedere ad esempio nel seguente modo:

( ) ( ) )13(mod99279398191001010777 412122525252522100 ≡⋅=⋅≡⋅=≡=⋅≡⋅= dato che: 1049 ≡ , 9100≡ , 381≡ e )13(mod127 ≡ . Già meglio, ma si può ancora migliorare; il procedimento indicato sempli fica i conti ma non è generalizzabile: come si procede se ad esempio l’esponente non è un multiplo di 4 ? Esaminiamo prima il caso in cui l ’esponente sia una potenza di 2, ad esempio 8:

( )( ) ( ) ( ) )13(mod391001049777 22222222228 3

≡≡=≡=== , perciò per calcolare il residuo

di k27 basta elevare al quadrato (modulo m) il residuo di

127−k

. Se invece l’esponente n non è una potenza di 2, si può comunque esprimere come somma di

potenze di 2: ∑=

=r

k

kkan

0

2 (dove i coeff icienti ka sono le cifre di n in base 2 e valgono 0

oppure 1) e dunque se b è un intero si ha: r

r

r

k

kk aaaa

an bbbbbb 2222

2 22

11

000

�==∑= .

Perciò per determinare il minimo residuo di 1007 modulo 13 si può procedere nel modo seguente: si determina la rappresentazione binaria di 100: 652

2 2221100100 ++= e quindi si calcolano le potenze di 7 (modulo 13) utili zzando come esponenti le potenze di 2 fino a

62 :

7702 ≡ , 107

12 ≡ , 9107 222

≡≡ , 397 223

≡≡ , 22 374

≡ , 397 225

≡≡ , 9762 ≡ e

finalmente si ottiene: )13(mod993977777652652 222222100 ≡⋅⋅≡⋅⋅== ++

11

d) il numero n = 782751397396832732980088834365153327678152 è un quadrato perfetto ?

* Esiste cioè un intero a che moltiplicato per sé stesso dia il numero dato ? Procedere per tentativi sarebbe decisamente laborioso (anche per un computer). Si può invece osservare che un tale intero a (se esistesse) dovrebbe certamente essere congruo modulo 10 ad uno tra gli i nteri: 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , e quindi 2a (cioè n) dovrebbe certamente essere congruo modulo 10 ad uno tra gli i nteri: 0 , 1 , 4 , 5 , 6 , 9 per la proprietà (ii ). Quindi, in generale, se un intero è un quadrato perfetto allora la sua cifra meno significativa (che è l’ultima a destra) deve essere una tra le seguenti: 0 , 1 , 4 , 5 , 6 , 9. Nel nostro caso n è congruo a 2 modulo 10 (il resto della divisione di un intero per 10 è la cifra meno significativa) e quindi non è un quadrato. Non vale però il viceversa: ad esempio 21 ha 1 come cifra meno significativa ma non è un quadrato

e) il numero n dell ’esempio precedente è un multiplo di 3 ? *

Si potrebbe verificare se è nullo il resto della divisione di n per 3. Ma anche in questo caso la strada più ovvia non è la più agevole e perciò ne cerchiamo una meno faticosa. Se indichiamo le cifre di n con: 011 ,,,, aaaa nn �− , allora essendo 10 congruo ad 1 modulo

3, si ha: )3(mod1000

∑∑==

≡=n

ii

n

ii

i aan , per le proprietà i) ed ii ). Quindi, un intero è multiplo

di 3 se e solo se lo è la somma delle sue cifre. Nel nostro caso specifico si può verificare che il numero n dato è multiplo di 3 (esercizio). Naturalmente nel fare i conti conviene ricordarsi che si sta lavorando con le congruenze e quindi è più sbrigativo sommare non le cifre ma i loro resti modulo 3.

In modo analogo si può, ad esempio, dimostrare che ∑=

=n

ii

i an0

10 è multiplo di 11 se e solo

se lo è �−+− 210 aaa .

Quelli ill ustrati sono due esempi di criteri di divisibili tà. Purtroppo non si conoscono dei criteri di divisibilit à per qualsiasi numero primo, alcuni di quelli noti sono: - un intero è divisibile per 2 se e solo se la cifra meno significativa è pari (perché ogni

intero è congruo modulo 2 all ’ intero rappresentato dalla propria cifra meno significativa) - un intero è divisibile per 3 se e solo se la somma delle cifre è divisibile per 3 - un intero è divisibile per 4 se e solo se le due cifre meno significative rappresentano un

multiplo di 4 - un intero è divisibile per 5 se e solo se la cifra meno significativa è 0 o 5 - un intero è divisibile per 9 se e solo se la somma delle cifre è divisibile per 9

f) verificare il risultato della moltiplicazione: 65421020801163992797493841960373911570270594831220598634215943830900 =×

Ci risiamo. Un conto esagerato, se si sceglie la strada usuale. Esiste invece un procedimento di verifica dei calcoli aritmetici detto prova del 9 che sfrutta le congruenze e che (come negli esempi precedenti) riduce drasticamente il l avoro (anche se in questa circostanza la risposta non dà, come si vedrà più avanti, piena garanzia). Tale prova si basa sull ’osservazione che ogni intero è congruo alla somma delle sue cifre modulo 9 (procedendo come nell ’esempio precedente), dunque se cab = e

12

)9(mod',',' ccbbaa ≡≡≡ , allora si deve avere: )9(mod''' cba ≡ , sempre per la proprietà ii ). Cioè la somma delle cifre di a moltiplicata per la somma delle cifre di b dev’essere congrua modulo 9 alla somma delle cifre del prodotto c. Nel caso specifico si ottiene: )9(mod7≡a , )9(mod2≡b e )9(mod5≡c , e in effetti )9(mod572 ≡⋅ . La regola può essere estesa anche alle operazioni + e - , ma non garantisce sempre il successo: non funziona quando il risultato errato è congruo modulo 9 a quello corretto.

g) n5 - n è sempre multiplo di 30 ?

Ad esempio è vero per 7=n perché 16800775 =− ; si vuole sapere se è vero anche per tutti gli altri interi. Evidentemente effettuare la verifica per ciascun valore di n non è possibile dato che gli i nteri sono infiniti . Anche in questo caso l’aritmetica dei moduli ci viene in aiuto offrendoci la possibilit à di effettuare i controlli solo in un numero finito di casi. Innanzi tutto osserviamo che, siccome 53230 ⋅⋅= , basta verificare se nn −5 è multiplo di 2, di 3 e di 5. Per controllare ad esempio se nn −5 è multiplo di 5, conviene lavorare con le congruenze modulo 5: n può essere congruo a 0, 1, 2, 3 o 4 modulo 5 ed è facile verificare che tutti i numeri:

005 − , 115 − , 225 − , 335 − , 445 − sono congrui a 0 modulo 5; perciò nn −5 è sempre un multiplo di 5. Analogamente si verifica che nn −5 è anche multiplo di 2 e di 3.

Osservazioni: - da i) e ii ) consegue che se f(x) è un polinomio (a coeff icienti interi), allora:

( ) ( ) )(mod)(mod mbfafmba ≡⇒≡

- le proprietà i) e ii ) sostanzialmente suggeriscono (e si è visto anche negli esempi) che con le congruenze i conti si possono fare in modo più spiccio rispetto all ’aritmetica usuale: invece di svolgere i calcoli con gli operandi originali , si svolgono coi loro residui.

Teorema (di Lagrange): se p è primo e ∑=

=n

k

kk xaxf

0

)( è un polinomio a coeff icienti interi (con

)(mod0 pan ≡/ ), allora la congruenza )(mod0)( pxf ≡ ha al più n soluzioni distinte modulo

p. Dim.

- se 1x è una soluzione, allora sostituendo 1x ad x si ha: )(mod00

1 pxan

k

kk ≡∑

=

; sottraendo

membro a membro questa congruenza con )(mod00

pxan

k

kk ≡∑

=

si ottiene:

( ) ( ) )(mod)()()(0 11

11 pxgxxxxaxfxfn

k

kkk −=−=−≡ ∑

=

dato che ( ) ( )( )11

21

31

2111

−−−− ++++−=− kkkkkk xxxxxxxxxx � e dove g(x) è un polinomio di grado n<

- dunque si ha: ( ) )(mod)()( 1 pxgxxxf −≡ , essendo ( ) )(mod01 pxf ≡ ; se 2x è

un’altra soluzione di f(x) distinta da 1x modulo p, allora sostituendo 2x ad x si ottiene:

( ) )(mod0)( 212 pxgxx ≡− e dunque )(mod0)( 2 pxg ≡ dato che p è primo e

pxx <−< 120

13

- ora si applicano a g(x) le stesse considerazioni fatte per f(x) e così via. Siccome ad ogni passo del procedimento il grado del nuovo polinomio g(x) ottenuto si riduce ed essendo n il grado del polinomio iniziale, allora il procedimento termina (quando si ottiene un polinomio privo di soluzioni, eventualmente costante) ed il numero di soluzioni di f(x) è al più n.

Osservazioni: - il teorema non vale se p non è primo. Ad esempio: )8(mod012 ≡−x ha grado 2 ma ha 4

soluzioni )8(mod7,5,3,1≡x , essendo soddisfatta per ogni valore dispari di x

14

4. I teoremi di Fermat e di Eulero Nella crittografia un tipo di calcolo ricorrente è l’esponenziazione (all ’ interno delle congruenze), vediamo perciò ora due teoremi che offrono delle informazioni essenziali su questa operazione. Teorema (piccolo teorema di Fermat): p è primo e )(mod1| 1 paap p ≡⇒/ −

Dim. - se 121 ,,,,0 −pxxx � è un sistema completo di residui modulo p, allora anche

121 ,,,,0 −paxaxax � lo è perché gli i nteri iax sono a due a due non congruenti modulo

p. Infatti, se per assurdo fosse ad esempio )(mod21 paxax ≡ allora

)(mod021 paxax ≡− e perciò ( )2121 xxaaxax −=− sarebbe multiplo di p, ma p ed

a sono coprimi (cioè privi di fattori comuni >1) e quindi )(mod21 pxx ≡ contro l’ ipotesi

- essendo i due insiemi di residui identici devono coincidere i prodotti dei loro elementi

non congruenti a zero, e dunque: )(mod1

1

11

1

1

1

pxaaxxp

ii

pp

ii

p

ii ∏∏∏

−

=

−−

=

−

=

=≡ e, dato che ∏−

=

1

1

p

iix

è coprimo con p , si può sempli ficare ottenendo: )(mod11 pa p ≡− Esempi: - qual’è il minimo residuo non negativo di 10000003 modulo 13 ?

Invece di procedere come ill ustrato nel paragrafo delle congruenze (scrivere l’esponente come somma di potenze di 2, eccetera) vediamo di applicare il teorema di Fermat; siccome 1000000 diviso 11312 −= dà resto 4 (e un certo quoziente q che non ci interessa) si ha:

( ) )13(mod333333 44124121000000 ≡≡== + qq . Si può generalizzare il risultato: se a è un qualsiasi intero coprimo con p allora il minimo residuo di na modulo p è congruente a )1(mod −pna ed il residuo trovato rappresenta la cifra meno significativa (cioè quella più a destra) di na in base p.

Osservazioni: - il teorema fornisce un criterio per verificare se un intero non è primo:

n non è primo se Za ∈∃ : ( ) 1, =naMCD e )(mod11 na n ≡/− .

Se però )(mod11 na n ≡− e ( ) 1, =naMCD , non è detto che n sia primo; ad esempio se

91=n e 3=a allora ( ) 191,3 =MCD e )91(mod1390 ≡ , ma 91 non è primo: 13791 ⋅= .

I numeri composti e dispari n che, come 91, soddisfano la relazione )(mod11 na n ≡− per qualche a coprimo con n, sono detti pseudoprimi (di base a). Attenzione: se n è pseudoprimo rispetto ad una base non è detto che lo sia per qualsiasi base, cioè non è detto che la relazione )(mod11 na n ≡− valga per qualsiasi a coprimo con n; se ad

esempio 91=n è vera per a = 3, ma non per a = 2 perché )91(mod164290 ≡/≡ . Quindi per verificare se un dato intero n non è primo si può cercare un intero a (coprimo con n), per cui la tesi del teorema di Fermat non valga; purtroppo esistono degli i nteri n composti per i quali la relazione )(mod11 na n ≡− vale per qualsiasi intero a coprimo con n (si osservi che esistono al più n – 1 scelte di a, modulo n). Tali i nteri sono detti numeri di Carmichael; ad esempio il più piccolo numero di Carmichael è 17113561 ⋅⋅= .

15

Per verificare (con maggiore speranza di successo) la primalità di un intero occorrerà perciò imporre delle condizioni più restrittive (vedi il paragrafo “n è primo ?”).

Def.: il numero di interi coprimi con un numero naturale n > 0 e compresi tra 1 ed n è indicato con )(nΦ , cioè: ( ){ }1,1:)( =≤≤∈=Φ mnMCDenmNmn .

Φ è detta la funzione di Eulero o funzione toziente. Esempi: - 2)6( =Φ perché gli i nteri coprimi con 6 compresi tra 1 e 6 sono due: 1 e 5. Invece 6)7( =Φ ,

infatti l ’unico intero compreso tra 1 e 7 e non coprimo con 7 è 7 stesso. Osservazioni: - siccome 1 è un divisore coprimo di qualsiasi intero si ha: 1)( ≥Φ n per ogni n > 0 - dato che l’unico divisore > 1 di un numero primo è il numero stesso, per ogni primo p si ha:

1)( −=Φ pp

Teorema: per la funzione di Eulero valgono le seguenti proprietà: i) se p è primo ed m > 0 allora: ( ) ( ) 11 −−=Φ mm ppp

ii ) ( ) ( ) ( ) ( )baabbaMCD ΦΦ=Φ⇒= 1, (e si dice che la funzione Φ è moltiplicativa)

iii ) se npp ,,1 � sono primi e 0,,1 >nmm � , allora: ( )∏∏=

−

=

−=

Φ

n

i

mii

n

i

mi

ii ppp1

1

1

1

Dim. si dimostra solo il punto i); la dimostrazione di ii ) richiederebbe di affrontare altri argomenti (ad esempio il teorema cinese dei resti o la formula di inversione di Möbius) che vanno oltre gli obiettivi della presente dispensa; il punto iii ) discende immediatamente da i) e ii ). i) gli i nteri compresi tra 1 e mp che non sono coprimi con mp sono i multipli di p e sono

esattamente 1−= mm

pp

p; dunque gli i nteri coprimi con mp sono i rimanenti e sono

( ) 11 1 −− −=− mmm pppp

Esempi: - il punto iii ) del teorema consente di calcolare la funzione di Eulero per qualsiasi intero di cui

si conosca la fattorizzazione in numeri primi. Ad esempio: ( ) ( ) ( ) 80515313212)532()300( 10122 =⋅−⋅⋅−⋅⋅−=⋅⋅Φ=Φ

Teorema (di Eulero): Zma ∈, , 0>m e ( ) ( ) )(mod11, mamaMCD m ≡⇒= Φ

Dim. - la dimostrazione procede in modo analogo a quella di Fermat. Siano ( )mxxx Φ,,, 21 �

degli i nteri coprimi con m ed a due a due non congruenti modulo m (ad esempio gli i nteri compresi tra 1 ed m e coprimi con m, che sono a due a due non congruenti modulo m

perché jimxx ji ,0 ∀<−< )

- allora i numeri ( )maxaxax Φ,,, 21 � coincidono (modulo m) con i precedenti salvo una

permutazione (salvo cioè l’ordine in cui sono scritti ); infatti sono due a due non

16

congruenti (se fosse )(modmaxax ji ≡ allora si avrebbe )(modmxx ji ≡ , essendo a

coprimo con m) e sono coprimi con m (perché lo è a) - dunque i due insiemi di numeri danno lo stesso prodotto (modulo m) e si ha:

( ) ( )( )

( ))(mod

111

mxaaxxm

ii

mm

ii

m

ii ∏∏∏

Φ

=

ΦΦ

=

Φ

=

=≡ , essendo inoltre il prodotto ( )

∏Φ

=

m

iix

1

coprimo con m

lo si può sempli ficare (per la regola di cancellazione) e si ottiene: ( ) )(mod1 ma m ≡Φ Esempio: per ill ustrare il modo di operare della dimostrazione supponiamo che sia 10=m ed 13=a (coprimo con m); gli i nteri compresi tra 1 ed m e coprimi con m sono ( ) 410 =Φ e sono:

9,7,3,1 e moltiplicando per a si ottiene una permutazione dei residui: )10(mod313131 ≡=⋅ , )10(mod939133 ≡=⋅ , )10(mod191137 ≡=⋅ ,

)10(mod7117139 ≡=⋅ Osservazioni: - il teorema di Fermat è evidentemente il caso particolare di quello di Eulero per m primo

17

5. Il problema della distribuzione delle chiavi Terminato il preambolo matematico entriamo dunque nel vivo degli aspetti crittografici. Riprendiamo brevemente quanto detto nell ’ introduzione:

desideriamo crittare un messaggio in modo che solo il destinatario lo possa decrittare, ne desideriamo cioè “nascondere” il contenuto in modo che risulti i ncomprensibile a chiunque tranne che al destinatario.

Bene, nascondere il messaggio è piuttosto facile: ad esempio scambiando di posto le lettere in modo che la A diventi la T, la B diventi la Z, la C diventi la Y, e così via. Quindi, la parola BACCA diventerà ZTYYT e per complicare ulteriormente le cose (per impedire che qualcuno decritti il messaggio analizzando le frequenze delle lettere) potremmo cambiare diverse volte i tipi di sostituzioni delle lettere (una volta la A è sostituita con la T, la volta successiva con la H e così via) all ’ interno del testo. Sorge ora un problema: come garantiamo la comprensione del testo da parte del destinatario ? Evidentemente dobbiamo comunicare al destinatario la chiave di lettura del testo, spiegargli cioè come abbiamo “scombinato” le lettere. Insomma, crittando il messaggio è come se lo avessimo chiuso con un lucchetto, il messaggio può essere letto solo da chi possiede la chiave: come facciamo a fornire la chiave del lucchetto solo alle persone autorizzate ? Questo problema è detto problema della distribuzione delle chiavi. Evidentemente il problema sta nel rischio che comunicando in un qualsiasi modo la chiave qualcuno (non autorizzato !) la intercetti: come comunicare dunque, in modo sicuro la chiave per la crittazione ? Come stabili re cioè una chiave per scambiare messaggi con l’ interlocutore, senza comunicarla esplicitamente, evitando quindi il rischio dell ’ intercettazione ?

18

6. Crittografia a chiave privata Vediamo una soluzione al problema precedente. La soluzione è descritta prima in modo generale e successivamente formalizzandola matematicamente (nel seguito si utili zzano dei nomi fitti zi per la descrizione dei sistemi crittografici: Bob ed Alice sono i due interlocutori che desiderano scambiarsi messaggi in modo sicuro, mentre Eva rappresenta il terzo incomodo impegnato a scoprire i messaggi dei primi due). Una soluzione con scatole e lucchetti Personaggi: Bob, Alice ed una scatola; l’obiettivo di Bob è di inviare una scatola chiusa ad Alice che solo Alice possa aprire. Supponiamo inoltre che Bob non possa fare una copia della chiave e consegnarla personalmente ad Alice (ad esempio perché i due abitano lontani): spedire una copia della chiave è troppo pericoloso; come fare ? L’ idea è la seguente:

- Bob invia la scatola chiusa mediante un proprio lucchetto - Alice riceve la scatola e aggiunge un proprio lucchetto a quello di Bob, quindi restituisce

la scatola (che ora ha perciò due lucchetti) - Bob toglie il proprio lucchetto e restituisce a sua volta la scatola (che ha ora solo il

lucchetto di Alice) - infine Alice toglie il proprio lucchetto ed apre la scatola

L’ idea è perciò, sostanzialmente, quella di fornire sia Bob che Alice di una propria chiave segreta detta chiave privata. Una soluzione matematica (Diffie-Hellman-Merkle) Vediamo ora una realizzazione matematica dell ’ idea precedente. Innanzi tutto il messaggio che Bob intende inviare ad Alice è trasformato in un numero intero x, ad esempio associando un intero a ciascun carattere (proprio come si fa in informatica per consentire ai computer di trattare, oltre che i numeri, anche i caratteri). Il messaggio potrebbe essere una chiave concordata tra Bob e Alice per scambiarsi successivamente dei messaggi in modo sicuro senza ripetere ogni volta il procedimento sotto descritto. Ora il problema è quello di simulare matematicamente il funzionamento di un lucchetto, cioè di un dispositivo che sia facile da chiudere, ma diff icile da aprire per chi non ne possiede la chiave. Il lucchetto è rappresentato dall ’operazione di esponenziazione effettuata con l’aritmetica dei moduli (descritta nel par. 3): la sicurezza di un tale lucchetto risiede nella grande diff icoltà (come accennato più avanti) di eseguire operazioni di estrazione della radice modulo un intero. Il procedimento è il seguente:

- Bob ed Alice concordano un intero primo P molto grande (pubblico) e tutte le operazioni sono realizzate modulo P

- Bob ed Alice scelgono come rispettive chiavi private gli i nteri a e b (scelti coprimi con 1−P per garantire l’unicità del risultato nelle operazioni di estrazione della radice)

- Bob eleva x alla a e lo invia ad Alice; Alice eleva il messaggio ricevuto alla b e lo restituisce a Bob che ne estrae la radice a-esima e spedisce il risultato ad Alice; infine Alice estrae la radice b-esima del messaggio ricevuto ed ottiene il messaggio originale x.

19

Quindi schematicamente si ha:

Bob Alice

sceglie come propria chiave privata un intero a tale che:

( ) 11, =−PaMCD

sceglie come propria chiave privata un intero b tale che:

( ) 11, =−PbMCD

x

ax

( )bax

bx x

I messaggi ax , ( )bax e bx sono quelli che viaggiano in rete e sono perciò intercettabili . Ma anche se la nostra malintenzionata ideale Eva li conoscesse non potrebbe risali re al messaggio x perché gli algoritmi per estrarre radici modulo un intero hanno tempi di esecuzione elevati (dello stesso ordine degli algoritmi di fattorizzazione). Si osservi inoltre che l’ordine in cui i lucchetti

sono aperti o chiusi è indifferente dato che ( ) ( )ababba xxx == (essendo l’operazione di prodotto commutativa). Questo procedimento possiede due difetti sostanziali (che saranno superati col metodo RSA): il primo è che è necessaria una doppia codifica e decodifica prima di ottenere il messaggio originale. Il secondo problema risiede nel fatto che entrambi gli i nterlocutori devono essere presenti; se ad esempio Alice volesse inviare un e-mail a Bob dovrebbe prima concordare con lui una chiave: e se Bob non c’è ? Una soluzione matematica inefficiente Cosa accadrebbe se invece dell ’esponenziazione si utili zzasse un’altra operazione, ad esempio il prodotto ? Uno spiacevole effetto: Eva riuscirebbe a decifrare il messaggio inviato da Bob ad Alice. Vediamo come mai. Supponiamo che Bob ed Alice concordino un intero N molto grande (pubblico) e che x sia l’ intero rappresentante il messaggio; tutte le operazioni saranno realizzate modulo N e si ha:

Bob Alice

sceglie come propria chiave privata un intero a tale che:

( ) 1, =NaMCD

sceglie come propria chiave privata un intero b tale che:

( ) 1, =NbMCD

x xa

xab

xb x

20

ora, se Eva ha intercettato tutti i messaggi xa , xab e xb trasmessi (cosa ammissibile), è in grado di scoprire il messaggio segreto x operando nel seguente modo:

- se ( ) 1, =NxMCD allora la congruenza ( ) ( )Nxaxbzxab mod≡ ha un’unica soluzione

rispetto a z modulo N, che è: ( )( )

xxab

xbxaz == . Questo è il caso più probabile perché

diff icilmente il messaggio x ed N avranno un fattore comune. - se invece ( ) 1, >NxMCD allora x si può determinare procedendo per tentativi

sommando ripetutamente ( )Nx

N

, a

( )( )xab

xbxa.

Infatti, in generale, la congruenza ( )Nz modβα ≡ ha soluzioni (rispetto a z) se e solo se

( ) βα |, NMCD (facile da dimostrare); inoltre il numero delle soluzioni è ( )NMCD ,α e se 'z

è una soluzione, lo è anche ( )NMCD

Nz

,'

α+ (un po’ meno facile).

Quindi, nel nostro caso, la congruenza è ( ) ( )Nxaxbzxab mod= ; si ha inoltre

( ) ( )NxMCDNxabMCD ,, = (essendo a e b coprimi con N) e ( )( )

xab

xbxaz = è certamente

una soluzione.

21

7. Crittografia a chiave pubblica Il metodo RSA (Rivest-Shamir-Adleman) Questo procedimento crittografico ha il vantaggio di eliminare i difetti del sistema a chiave privata: se cioè Alice vuole inviare un messaggio a Bob può farlo anche se Bob non c’è e con un solo invio. Per realizzare il metodo RSA ciascun utente, ad esempio Bob, non è dotato più di una sola chiave, ma di due:

- una chiave pubblica: è la chiave utili zzata da Alice per crittare i messaggi da inviare a Bob

- una chiave privata: è la chiave che Bob utili zza per decrittare i messaggi ricevuti (i sistemi crittografici in cui, come in questo caso, ogni utente ha 2 chiavi sono detti di crittografia asimmetrica). Ora potrebbe sorgere spontanea una domanda: se la chiave pubblica è nota a tutti, anche ad Eva, com’è possibile che quest’ultima non riesca a decifrare i messaggi inviati da Alice ? La risposta sta nel fatto che la chiave pubblica consente solo di cifrare (e non di decifrare), mentre per decifrare si può utili zzare solo la chiave privata (che soltanto Bob conosce); quindi nemmeno Alice potrebbe decifrare il proprio messaggio una volta completata la cifratura. Il procedimento è il seguente:

Bob Alice

- sceglie p e q primi grandi che costituiscono la chiave privata; sia

pqN =

- sceglie e tale che: 1))(,( =Φ NeMCD

- pubblica N ed e; quindi N ed e costituiscono la chiave pubblica

- trasforma il messaggio in un numero M tale che:

1),( =NMMCD - cifra M nel seguente modo

ottenendo il crittogramma C: )(modNMC e≡

C

- calcola ))((mod1))(( Net N Φ≡ −ΦΦ che è l’ inverso di e modulo )(NΦ perché per il teorema di Eulero:

))((mod1))(( Nete N Φ≡≡ ΦΦ

- determina il messaggio M: )(mod1)( NMMMC Nkett ≡=≡ +Φ

per il teorema di Eulero ed essendo 1),( =NMMCD

22

I vantaggi di questo metodo rispetto a quello a chiave privata sono che Alice non deve preventivamente concordare una chiave con Bob prima di inviarle un messaggio e che deve fare un solo invio. Lo svantaggio del sistema RSA sta invece nel fatto che non offre una sicurezza assoluta: chi può garantire che non sia stato scoperto qualche algoritmo “veloce” per fattorizzare numeri anche di 1000 cifre ? O che non esista un super computer (forse quantistico ?) in grado di effettuare i calcoli i n tempi estremamente ridotti ? Tali garanzie di totale sicurezza non può darle nessuno e questo limite è in definitiva il limit e di tutti i sistemi crittografici (tranne che per la crittografia quantistica, ma questa è un’altra storia). Esaminiamo ora le scelte che Bob deve fare ed alcune raccomandazioni. La scelta di p e q Chi conosce i valori di p e q può decifrare il messaggio M, quindi p e q devono essere scelti abbastanza grandi per rendere praticamente impossibile la fattorizzazione di pq (e per rendere improbabile che M non sia coprimo con N). Attualmente si ritiene suff iciente che p e q abbiano un centinaio di cifre e perciò la sicurezza del metodo RSA si basa sulla diff icoltà di fattorizzare grandi numeri interi. Ancora sulla scelta di p e q: Bob deve calcolare l’esponente t e per farlo deve conoscere

))1)(1(())(( −−Φ=ΦΦ qpN , deve quindi fattorizzare 1−p e 1−q , che però sono stati scelti grandi. Bob deve perciò affrontare una diff icoltà simile a quella di Eva; per aggirare il problema si potrebbero prima costruire 1−p e 1−q come prodotti di primi noti, e successivamente verificare se p e q sono primi. Dovendo invece fattorizzare 1−p e 1−q può essere di conforto

sapere che il valore medio dei fattori primi di n è 5.0)81.2/(ln

5.0nep ≈ e perciò, ad esempio, per

5010=n la media dei fattori primi è 600. Si osservi, per inciso, che per p e q grandi solo Bob può calcolare ( )( )11)( −−=Φ qpN e può quindi determinare t e decrittare il messaggio di Alice. Il numero t, che è quindi segreto, è detto chiave di decifrazione. Altra (ovvia) raccomandazione, è che p e q non siano scelti tra primi già noti (perché ad esempio presi da una tabella o generati con procedimenti conosciuti), perché potrebbero essere conosciuti anche da chi cerca di intercettare i messaggi. La scelta di e Supponiamo che Eva, da brava hacker, le provi tutte e che ad esempio faccia la cifratura del messaggio cifrato (sia il messaggio cifrato che l’esponente sono pubblici): essendo eM il messaggio cifrato, la sua cifratura si ottiene elevandolo alla e (modulo N) e dunque

( ) 2eee MM = . Se poi effettua la cifratura del risultato ottiene 3eM (che è perciò la cifratura

della cifratura) e continuando così dopo 1−k cifrature otterrà keM (questo modo di procedere è

detto cifratura ripetuta). Sorpresa: dopo al massimo )(NΦ tentativi otterrà il messaggio

originale, cioè MMke = (sempre modulo N): infatti il messaggio M è coprimo con N e di

coprimi con N ce n’è esattamente )(NΦ . Il minimo numero di cifrature necessarie a ritrovare M è detto ordine della cifratura: evidentemente tale ordine dev’essere abbastanza grande per evitare una decifrazione accidentale.

23

Vediamo ora un valore specifico di k per cui MMke = : essendo 1))(,( =Φ neMCD , per Eulero

si ha ))((mod1))(( Ne N Φ≡ΦΦ e dunque ( )( ) ( ) )(mod)()(1 NMMMMM

uNNue N

≡== ΦΦ+ΦΦ

. Perché N non dev’essere pr imo Abbiamo già stabilit o che N dev’essere il prodotto di due primi e perciò non è certamente primo. Si potrebbe supporre che se fosse primo la sicurezza sarebbe comunque garantita (o forse maggiore ?), ma non è così. Vediamo come si può ricostruire il messaggio M se N è primo, conoscendo N, C ed e. I dati sono quindi:

- un intero primo N rispetto a cui calcolare il modulo - l’esponente e scelto in modo che: ( )( ) ( ) 11,, =−=Φ NeMCDNeMCD - il messaggio M tale che: NM <<1 e 1),( =NMMCD

- sia infine )(modNMC e≡ il crittogramma inviato Allora il procedimento per determinare il messaggio M noti N , C ed e è il seguente:

- si calcola )1(mod1)1( −≡ −−Φ Net N , che è l’ inverso di e modulo 1−N , infatti:

)1(mod1)1( −≡≡ −Φ Nete N per il teorema di Eulero - dunque il messaggio è (sempre per il teorema di Eulero):

)(mod1)1( NMMMC Nkett ≡=≡ +−

24

8. Firme autenticate Supponiamo che Bob riceva un messaggio da Alice: come fa ad essere certo dell ’ identità del mittente ? Infatti, per crittare il messaggio Alice ha utili zzato la chiave pubblica di Bob che è disponibile a tutti. Per avere la certezza che ad inviarlo sia stata proprio Alice, occorre che il messaggio contenga un’ informazione che sia indiscutibilmente solo di Alice, questa informazione deve evidentemente essere legata alla chiave privata di Alice che solo lei conosce. Più precisamente Alice aggiunge al messaggio la crittazione dei propri dati personali , ottenuta mediante la propria chiave di decifrazione t (segreta e calcolabile solo conoscendo la chiave privata). Utili zzando la solita notazione si ha:

Bob Alice

- chiave privata: 11, qp

- chiave pubblica: )( 111 Nqp = ed 1e con 1))(,( 11 =Φ NeMCD

- chiave privata: 00 , qp

- chiave pubblica: )( 000 Nqp = ed

0e con 1))(,( 00 =Φ NeMCD

- M messaggio: 1),( 1 =NMMCD

- I identificazione del mittente (nome, cognome,…) tale che:

1),( 0 =NIMCD

- 0t chiave di decifrazione:

))((mod1 000 Net Φ≡

- calcola: )(mod 00 NIS t≡

- S e M costituiscono il messaggio

1M - cifra 1M ottenendo il

crittogramma C:

)(mod 111 NMC e≡

C

- determina M ed S (nel solito modo)

- determina l’ identificazione I del mittente a partire da S:

)(mod 01)( 0000 NIIIS Nkete ≡=≡ +Φ

25

9. n è primo ? In diverse occasioni si pone il problema di verificare se un dato intero è primo, ad esempio quando si deve scegliere una chiave privata. Come si è già accennato, per effettuare tale verifica (detta anche verifica della primalità) per un intero di parecchie cifre non è conveniente applicare la definizione, ma occorrono dei procedimenti più sofisticati se si desidera ottenere una risposta in tempi ragionevoli . Descriveremo di seguito un algoritmo di verifica della primalità che può dare due tipi di risposte: “ il numero è certamente primo” oppure “il numero è probabilmente primo” Evidentemente il secondo tipo di risposta non è completamente soddisfacente e potrebbe richiedere un’ulteriore verifica che garantisca la certezza della primalità, anche se in effetti l’algoritmo proposto è in grado di fornire una probabilit à di errore (la risposta è “probabilmente primo”, ma invece il numero è composto) piccola quanto si vuole. Il procedimento si basa sui teoremi di Fermat e di Lagrange; entrambi forniscono delle condizioni necessarie aff inché un dato intero sia primo. Se dunque un intero non verifica almeno una delle tesi dei due teoremi, allora non è primo. Viceversa, se le verifica entrambe, potrebbe essere primo. Nel test che segue il teorema di Lagrange è applicato al polinomio 12 −x che ha solo le radici

1− e 1 se il modulo è primo.

Test di Miller-Rabin: consente di verificare se un dato intero n > 0 è primo. - si sceglie a tale che sia: ( ) 1, =naMCD e ( )na mod1,1 −≡/

- sia mn l21=− con m|2 / ; dunque: ( ) lmn aa

21 =−

- si calcolano modulo n le potenze mk

a2 per lk ,,1,0 �= e ci si arresta al primo valore di k

per cui ( )na mk

mod12 ≡ oppure se lk = . Quando ci si arresta si esaminano, nell ’ordine, i seguenti casi: a) se 0=k allora n è probabilmente primo perché né Fermat né Lagrange sono violati

b) altrimenti se: ( )na mk

mod12 ≡ e ( )na mk

mod112 −≡

−

allora, come al punto precedente, n è probabilmente primo

c) altrimenti se: ( )na mk

mod12 ≡ e ( )na mk

mod112 −≡/

−

allora n non è primo perché è

violato il teorema di Lagrange. Infatti mk

a12 −

è una radice quadrata di 1 che non è congrua né a 1 né a –1 modulo n.

Inoltre n si può fattorizzare calcolando: ( )naMCD mk

,112 −

−

e ( )naMCD mk

,112 +

−

; infatti

posto mk

au12 −

= , si ha ( )nu mod12 ≡ , cioè ( )( ) ( )nuuu mod0111 2 ≡−=+− e

dunque n divide ( )( )11 +− uu . Inoltre ( )nuMCD ,1− e ( )nuMCD ,1+ sono divisori

propri di n essendo ( )nu mod1,1−≡/

d) altrimenti rimane il caso lk = e ( )na ml

mod12 ≡/ , dunque n non è primo perché è violato il teorema di Fermat. In questo caso però non si ottiene una fattorizzazione di n come in c).

26

Esempio: verificare se 561=n (il minimo numero di Carmichael) è primo. Scelto 2=a si ha 3521 4 ⋅=− ⋅n e inoltre:

,( )561mod12,672,1662,2632 2801407035 ≡≡≡≡

u

, dunque n non è primo, caso c).

Inoltre n si può fattorizzare: ( )nu mod12 ≡ , allora ( )( )111| 2 +−=− uuun ; essendo ( ) ( ) 33561,66,1 ==− MCDnuMCD

e ( ) ( ) 17561,68,1 ==+ MCDnuMCD , si ha: 1733⋅=n .

Def.: gli i nteri n dispari e composti che superano il test di Mill er-Rabin (che sono cioè “probabilmente primi” ) per qualche a coprimo con n, sono detti pseudoprimi forti (di base a).

Teorema(di Rabin): se n è composto allora utili zzando il test di Mill er-Rabin al più 4

1 dei

possibili valori di a dà la risposta “n è probabilmente primo” Osservazioni: - il teorema misura perciò la probabilit à di ottenere una risposta fuorviante (n è “probabilmente

primo” quando è invece composto). Ripetendo però la verifica per diverse basi a tale probabilit à può essere ridotta: se per k diversi (modulo n) valori di a la risposta è sempre “n è

probabilmente primo”, allora la probabilit à che sia comunque composto è k4

1. Ad esempio

la probabilit à che n non sia primo con 10 diverse scelte di a è: 1048576

1

4

110

= e con 20:

7761099511627

1

4

120

=

- nella pratica non è necessario provare molte basi per essere “quasi” certi che un dato intero sia primo, dato che i numeri pseudoprimi forti sono piuttosto rari. Ad esempio, è stato calcolato che esiste un unico intero n composto 10105.2 ⋅< che sia pseudoprimo forte per le basi 2 , 3 , 5 e 7 ( )3215031751=n

- ma per quante basi occorre ripetere il test per ottenere la certezza della primalità di un intero? La risposta ancora non è stata data, ma si congettura che: se n è intero composto e dispari allora il test di Mill er-Rabin falli sce per almeno una base

na 2log2<

27

10. Quali sono i fattori di n ? Se il problema di chi deve scegliere una chiave privata è stabili re se un intero molto grande è primo, il problema di chi intende scoprire una chiave privata (partendo da quella pubblica) è invece la scomposizione in fattori primi di un intero molto grande. La verifica della primalità di un intero è un’operazione molto più veloce (a parità di cifre) che non la fattorizzazione di un numero composto, ed è proprio su questa differenza di diff icoltà che si basa la protezione del sistema di crittografia RSA. Attualmente, ad esempio, gli i nteri di circa 100 cifre sembrano essere il limit e massimo di scomposizione; è stato valutato che un computer con processore Pentium Intel da 100 MegaHertz e 8 Giga Byte di memoria, impiegherebbe circa 50 anni per scomporre in fattori primi un intero dell ’ordine di grandezza di 13010 . Naturalmente questi limiti sono destinati ad essere superati sia dall ’evoluzione della matematica che dell ’ informatica (sia hardware che software). In questo paragrafo ci porremo dunque nell ’ottica di un “pirata informatico” : dato un intero trovare due suoi fattori (naturalmente non banali ). Saranno descritti alcuni dei procedimenti più elementari per fattorizzare un intero composto (la verifica se l’ intero è composto potrà essere fatta ad esempio col test di Mill er-Rabin, che purtroppo non sempre dà anche la fattorizzazione dell ’ intero dato). Metodo di Fermat E’ uno dei più elementari tra i metodi di fattorizzazione. Sia n composto e dispari; allora esistono a e b dispari tali che abn = ; si possono inoltre determinare due interi x ed y in modo che si abbia yxa += e yxb −= : infatti sommando e sottraendo membro a membro si ottiene

2

bax

+= e 2

bay

−= , con x e y interi dato che a e b sono dispari. Dunque 22 yxn −= e

nxy −= 22 ; inoltre essendo 02 >y , dev’essere nx > .

Ora, si fanno assumere ad x i valori �,3,2,1 +++ nnn ; se nx −2 non è

un quadrato perfetto si continua, altrimenti ci si arresta ed i fattori cercati sono yx − e yx + . Esempi: - quali sono i fattori primi di n = 43423 ?

Supponendo di aver già verificato che n è composto, si ha: �3.20843423==n e

quindi 2091=+n ; applicando il metodo di Fermat per i successivi valori di x a partire

da 209 si ottiene: 4368120922 ==x , 25843423436812 =−=− nx non è un quadrato 4410021022 ==x , 67743423441002 =−=− nx non è un quadrato 4452121122 ==x , 109843423445212 =−=− nx non è un quadrato 4494421222 ==x , 22 15214342344944 ynx ==−=− è il quadrato di 39

dunque: x = 212 , y = 39 e ( )( ) 25117343423 ⋅=+−== yxyxn

- quali sono i fattori primi di n = 290519 ? In questo caso il numero di iterazioni è decisamente maggiore che nell ’esempio precedente.

Procedendo come sopra si ha: 5391=+n e:

29052153922 ==x , 22905192905212 =−=− nx non è un quadrato

28

29160054022 ==x , 10812905192916002 =−=− nx non è un quadrato e così via fino a:

34574458822 ==x , 22 55225290519345744 ynx ==−=− è il quadrato di

235 e si ha: x = 588, y = 235 e ( )( ) 823353290519 ⋅=+−== yxyxn ; dunque in questo caso sono state necessarie 50 iterazioni dell ’algoritmo

Osservazioni: - se i fattori yx + e yx − non sono “vicini” , allora y è piuttosto grande, ma quanto

maggiore è y tanto maggiore è il numero delle iterazioni del procedimento. Dunque il metodo di Fermat diviene tanto meno eff iciente quando maggiore è la differenza tra i due fattori che si intendono determinare; vediamo perciò una versione modificata per ovviare a questo inconveniente.

Metodo di Fermat (versione modificata) Se i fattori di n non sono vicini per ridurre il numero delle iterazioni è conveniente aumentare i valori che si assegnano ad x (e quindi aumentare y).

Ad esempio si prova coi valori �,2,1 ++= knknx dove k è un intero piccolo. Ci

si arresta quando knx −2 è un quadrato perfetto. Allora, se 22 yknx =− , si ha che

( )( )yxyxn +−| è dunque due fattori di n sono dati da ( )nyxMCD ,− e ( )nyxMCD ,+ . Da un punto di vista “informatico” il metodo di Fermat è sostanzialmente una ricerca sequenziale (al variare di x); in questa versione, se si sa preventivamente che il quadrato cercato (cioè 2y ) non sta tra i primi valori di x, lo si cerca iniziando un po’ più avanti. Esempio: quali sono i fattori primi di n = 290519 ? Si è già visto che con la versione originale dell ’algoritmo di Fermat (quindi con k = 1) erano state

necessarie 50 iterazioni; proviamo con k = 3, si ha: 9341=+kn .

Per 9418 =+= knx si ottiene: 222 11813924===− yknx , dunque knyx =− 22 cioè

2905193118941 22 ⋅=− . Infine: ( ) ( ) 823290519,118941, =−=− MCDnyxMCD ,

( ) ( ) 353290519,118941, =+=+ MCDnyxMCD e perciò 823353290519 ⋅= . Metodo rho (detto anche metodo di Monte Carlo) Sia n composto e dispari; si scelgono una funzione )(xf dall ’ insieme dei residui modulo n in sé

stesso, ed un valore iniziale 0x . Quindi si calcolano (modulo n) i valori )( 01 xfx = ,

)(,,)( 112 −== kk xfxxfx � ; ci si arresta quando si trova una coppia di valori kj xx , tali che

( ) nnxxMCD jk <−< ,1 e ciò avviene quando ( )dxx jk mod≡ (con d > 1 divisore di n) e

( )nxx jk mod≡/ .

Esempio: quali sono i fattori primi di n = 91 ?

29

Prendendo 1)( 2 += xxf e 10 =x si ottiene: 26,5,2 321 === xxx e

( ) ( ) 791,21,23 ==− MCDnxxMCD che è infatti un fattore di 91.

Osservazioni: - la scelta di )(xf deve garantire che i valori kx vengano generati in modo piuttosto

“casuale”; è perciò importante che )(xf non sia lineare, mentre, ad esempio, la scelta

1)( 2 += xxf è considerata soddisfacente

- per ogni nuovo valore di kx si devono calcolare i massimi comun divisori ( )nxxMCD jk ,−

per ogni jx precedente, cioè per ogni j < k. Vediamo dunque una versione modificata che

consenta di calcolare un solo MCD ad ogni iterazione del procedimento Metodo rho (versione modificata) La modifica si basa sull ’osservazione che se )(xf è un polinomio e se ( )dxx sr mod≡ allora

( )dxxfxfx ssrr mod)()( 11 ++ =≡= , e perciò si ha in generale che: ( )dxx msmr mod++ ≡ per

ogni m >0 (dove d è sempre un divisore non banale di n). Per ogni nuovo valore kx si calcola soltanto il massimo comune divisore ( )nxxMCD jk ,− ,

dove 12 −= hj e 1+h è il numero di bit (cioè cifre in base 2) di k, e perciò: 122 +<≤ hh k

(ovvero kh 2log= ) .

Osservazioni: - in questa versione si ha il vantaggio di calcolare un solo MCD ad ogni iterazione, ma si ha lo

svantaggio che in genere non ci si accorgerà subito di avere raggiunto un kx conveniente

(cioè, la cui differenza con un elemento precedente contenga un fattore non banale di n), ma si procederà oltre effettuando alcune iterazioni in più. Diamo ora una maggiorazione al numero di iterazioni in più: sia ( ) 1,

00>− nxxMCD jk , si

supponga che 0k abbia h + 1 bit e che sia 12 1 −= +hj ; allora se )( 00 jkjk −+= si ha

( ) 1, >− nxxMCD jk perché 00 jjkk −=− e 02

0 4242 kkjk hh ⋅≤⋅=<+< + .

- il procedimento funziona ugualmente se si sostituisce la base 2 con una qualsiasi altra base Esempio: quali sono i fattori primi di n = 7081 ? Prendendo 1)( 3 +−= xxxf e 20 =x , si ottiene:

20 =x

71 =x e ( ) 1,01 =− nxxMCD

3372 =x e ( ) 1,12 =− nxxMCD

( )nx mod66933 ≡ e ( ) 1,13 =− nxxMCD

( )nx mod4864 ≡ e ( ) 1,34 =− nxxMCD

( )nx mod6805 ≡ e ( ) 1,35 =− nxxMCD

( )nx mod65976 ≡ e ( ) 1,36 =− nxxMCD

30

( )nx mod15537 ≡ e ( ) 1,37 =− nxxMCD

( )nx mod3898 ≡ e ( ) 97,78 =− nxxMCD , dunque 7397⋅=n

Metodo p-1 di Pollard Sia n composto e p un suo divisore primo; il metodo consente di determinare un fattore di n se i divisori primi di p – 1 sono abbastanza piccoli . L’algoritmo è il seguente: 1. scegliere un intero B e sia k un multiplo di tutti gli i nteri B≤ ; ad esempio !Bk = oppure k

è il minimo comune multiplo degli i nteri non maggiori di B 2. scegliere un intero a tale che: ( ) 1, =naMCD

3. calcolare na k mod (ad esempio utili zzando il metodo dei successivi elevamenti al quadrato, ill ustrato nel paragrafo delle congruenze)

4. calcolare ( )naMCDd k ,1−= , utili zzando l’algoritmo di Euclide ed il risultato del passo precedente

5. si possono avere i seguenti casi: - se 1=d allora si ricomincia provando con un valore più grande di B (e in questo caso il

valore necessario potrebbe essere molto grande) - se invece nd = si prova a cambiare il valore di a - se infine nd <<1 allora un fattore non banale di n è stato trovato e restano da

fattorizzare d e d

n

Osservazioni: - quando funziona: se ∏=−

i

mi

ipp 1 è la fattorizzazione in primi e iBp imi ∀≤ allora

kp |1− . Inoltre per il piccolo teorema di Fermat, se ap |/ si ha )(mod11 pa p ≡− e

dunque )(mod1 pa k ≡ e ( )naMCDp k ,1| − . Non si ottiene un fattore proprio di n se

)(mod1 na k ≡ - quando non funziona: il fattore p di n non viene determinato se i fattori primi di 1−p non

sono abbastanza piccoli , cioè se non sono minori o uguali a B Esempio: quali sono i fattori primi di n = 719501 ? Prendendo 13=B , 360360)13,,4,3,2( == �mcmk e 2=a si ottiene:

399087mod =na k , ( ) 521,1mod =− nnaMCD k e infine: 1381521⋅=n

31

Bibliografia 1] H. Davenport Aritmetica superiore Zanichelli, 1994 2] N. Koblitz A course in number theory and criptography Springer, 1988 3] M. R. Schroeder La teoria dei numeri Muzzio, 1986 4] S. Singh Codici & Segreti Rizzoli, 1999