23.3.1 Un po’ di matematica

La teoria crittografica si basa sullo studio di funzioni matematiche non lineari, per poter così sfruttare il loro andamento non facilmente prevedibile. In particolare le funzioni utilizzate sono quelle modulari, ovvero quelle che utilizzano i resti delle divisioni intere. Si farà riferimento pertanto all’insieme dei numeri naturali = {1,2,3,4,5,6,7,...}. Sui concetti matematici di seguito esposti si basano i sistemi crittografici descritti nelle sezioni successive.

23.3.1.1 I moduli

Dati tre numeri a,b,n con n > 0, si dice che a e b sono congruenti modulo n e si scrive a b(modm), se a - b è divisibile per n, ovvero se |a-b| n .

Alcuni esempi
360(mod4)
233(mod20)
161(mod5)

È facile dimostrare le seguenti proprietà

~ a+ b= c + d(mod m)

(23.1)

ab ~= cd (mod m)

(23.2)

Dati a,n

,n > 0, si definisce classe di congruenza di a modulo n, l’insieme C_n (a)

{...,a - 2n,a - n,a,a + n,a + 2n,...}

Per le relazioni 23.1 e 23.2, l’addizione e la moltiplicazione tra le classi di congruenza è ben definita

C_n(a) + C_n(b) = C_n(a + b)

C_n(a) ^.C_n(b) = C_n(ab)

Si è soliti rappresentare C_n(a) con il minimo valore appartenente all’insieme. Tale valore definisce l’operatore modulo mod che restituisce il resto della divisione intera tra due numeri, ovvero amodn = . La scrittura amodn = b equivale a ab(modn), ovvero significa che il resto della divisione intera a/n è b.

Di seguito sono riportati alcuni esempi
25 mod44 = 25
73 mod7 = 3
56 mod56 = 0
27 mod26 = 1

Si definisce Z_n come l’insieme delle classi di equivalenza rispetto ad un certo modulo, cioè Z_n {0,1,2,3,4,5,...,n - 1}. Ad esempio Z₅ = {0,1,2,3,4}

Per la generica relazione xmodm = r valgono le seguenti proprietà

• 0 < r < m x
• xmodm = x x < m
• xmodx = 0 x
• (x + 1)modx = 1 x
• xmod1 = 0 x
• 0modm = 0 m
• (x + y)modm = (xmodm + y modm)modm x,y
• xy modm = (xmodm)(y modm)modm x,y

Le ultime due relazioni indicano il fatto che trattandosi di resti, se uno dei due membri di un’equivalenza risulta maggiore di m, deve essere ulteriormente diviso per m per rispettare l’uguaglianza.

In particolare, dall’ultima proprietà deriva la proprietà del resto di un quadrato

xmodm = r ==> x² modm = r² x

Un numero n ,n > 0 è detto primo quando è divisibile solo per se stesso e per 1, ovvero se nmodm = 0 <==> m {1,n} Z_n . Se n è divisibile per altri valori, è detto composto.

È facile verificare che 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 31 sono numeri primi.

Dunque, escluso il numero 2 (che è primo perché divisibile solo per 1 e per 2, cioè se stesso), tutti i numeri primi sono dispari.

L’insieme dei numeri primi sarà indicato con il simbolo P.

Verificare la primalità di un numero n significa verificare se n P, e questo può essere fatto abbastanza velocemente sfruttando il piccolo teorema di Fermat, che afferma quanto segue

Sia p P. Allora si ha

npmod p = n A n (- [1,p - 1] < N

Ad esempio, il numero 5 è primo ed infatti

1⁵ mod5 = 1, 2⁵ mod5 = 2, 3⁵ mod5 = 3 e 4⁵ mod5 = 4

Il teorema permette così, dato un numero, di stabilire se esso è composto. Infatti è sufficiente trovare un valore b [1,p - 1] per cui risulti b^p modpb per poter affermare che il numero è composto. Ma se il numero soddisfa il piccolo teorema di Fermat, non è detto che sia un numero primo: il piccolo teorema di Fermat pone soltanto una condizione necessaria, ma non sufficiente per la verifica della primalità di un numero.

Infatti, per il numero 4, che non è primo, si ha

1⁴ mod4 = 1, 2⁴ mod4 = 0 e 3⁴ mod4 = 1

ma anche 561 (= 3 × 11 × 17) e 1729 (= 7 × 13 × 19), ad esempio, pur essendo composti, soddisfano il piccolo teorema di Fermat.

I numeri composti che soddisfano il piccolo teorema di Fermat sono detti numeri di Charmichael (o pseudoprimi) e sono meno densi rispetto ai numeri primi.

Due numeri n ed m, con nm si dicono primi tra loro se non hanno nessun divisore comune, eccetto il numero 1.

23.3.1.2 Le funzioni modulari

Le funzioni modulari sono funzioni y = f(x) : --> che hanno la forma seguente

y = Ex mod m

dove E ed m sono dei valori costanti che definiscono la specifica funzione modulare considerata.

Poiché y è un resto, esso sarà un valore compreso tra 0 e m- 1. Ad esempio, y = 4xmod7 è una funzione modulare, della quale alcuni valori di x ed y sono riportati nella tab. 23.1.

Tabella 23.1:

Esempi dei valori assunti da una funzione modulare.

Si noti l’andamento “disordinato” dei valori assunti da y in corrispondenza di quelli di x.

Le funzioni modulari hanno varie proprietà, tra cui

x mod m = zmod m ==> kx mod m = kzmod m A k (- N

(23.3)

xmod m = zmod m ==> (k +x) mod m = (k+ z)mod m A k (- N

(23.4)

La relazione 23.3 è evidente dal fatto che

kx mod m = (k mod m)(xmod m) = (kmod m)(z mod m) = kzmod m

mentre la 23.4 si ottiene da

(k+ x)mod m = (k mod m)+ (xmod m) = (kmod m) + (zmod m) = (k+ z)mod m

Nel caso in cui E ed m siano primi tra loro, una funzione modulare y = Exmodm è invertibile, ovvero esiste una funzione inversa x = Dy modm. Quindi

y = Exmod m ==> Dy mod m = DEx mod m = x(DE mod m) mod m

cioè è sufficiente trovare un valore D : DE modm = 1 affinché la relazione precedente diventi

Dy mod m = xmod m

Per determinare il valore D che dà la funzione modulare inversa, si può procedere con un algoritmo iterativo. Infatti, indicando con Q il quoziente della divisione intera tra DE ed m si può scrivere DE = Qm + 1, pertanto si può procedere facendo partire Q da 1 e calcolando il valore D = Qm+1 E incrementando di volta in volta il valore di Q. Il processo può essere arrestato non appena D sarà un valore intero.

Ad esempio, la funzione y = 11xmod10800 è invertibile poiché 11 e 10800 sono primi tra loro e la funzione inversa è x = 5891y mod10800 (ottenuta con Q = 6).

La funzione di Eulero N(m) : --> dato un valore m fornisce il numero di valori in [1,m - 1] che non hanno fattori in comune con m.

Ad esempio N(9) = 6, infatti sono 1, 2, 4, 5, 7, ed 8, ovvero 6 valori nell’intervallo [1,8] che non hanno fattori in comune con 9. Ed ancora N(12) = 4, infatti sono 1, 5, 7, ed 11, ovvero 4 valori nell’intervallo [1,11] che non hanno fattori in comune con 12.

Tale funzione gode delle seguenti proprietà

• N(m) = m - 1 m P
• N(m) = _{i = 1}ⁿ(p_i - 1) m = _{i = 1}ⁿp_i con p_i P

Ad esempio 10 = 2 × 5 ==>

N(10) = (2 - 1)(5 - 1) = 1 × 4 = 4, infatti i numeri che non hanno divisori in comune con 10 nell’intervallo [1,9]

sono 4 (1, 3, 7 e 9).

Le funzioni modulari esponenziali sono funzioni y = f(x) : --> che hanno la forma seguente

E y = x mod m

dove E ed m sono dei valori costanti che definiscono la specifica funzione modulare esponenziale considerata.

Anche in questo caso, trattandosi di un resto, y assumerà valori comprsi tra 0 e m - 1.

Le funzioni modulari esponenziali sono invertibili soltanto se E ed N(m) sono primi fra loro.

Dalla 23.3 si ha che

k k x mod m = r ==> x mod m = r mod m

e tenendo conto di un teorema della teoria dei numeri si può scrivere che

y = xE mod m = xE modN(m)mod m

quindi

yD mod m = xED modN(m)mod m

Per trovare la funzione inversa è sufficiente trovare un valore D tale che DE modN(m) = 1, ovvero DE = QN(m) + 1 (dove Q è il quoziente della divisione intera tra DE ed N(m)). Quindi, analogamente a quanto descritto per le funzioni modulari semplici, si può procedere con moltiplicazioni successive, calcolando D = QN(m)+1 E con Q che vale inizialmente 1 ed incrementandolo ogni volta di una unità, fintantoché D non risulta essere un numero intero.

Ad esempio, la funzione modulare esponenziale inversa di y = x¹¹⁸³ mod2867 è x = y⁷ mod2867.

23.3.1.3 Le curve ellittiche

Esistono sistemi di cifratura che si basano sui problemi connessi con le curve ellittiche, proposti per la prima volta da V. Miller e N. Koblitz, verso la metà degli anni ’80. Come per gli algoritmi che si basano sulle funzioni modulari, gli algortmi basati sulle curve ellittiche basano la loro robustezza sulla complessità operazionale nella ricerca di una funzione matematica inversa. In particolare, dati due punti G e Y su una curva ellittica tale che Y = kG non è banale trovare il valore intero k. Tale problema è noto come il problema del logaritmo discreto delle curve ellittiche.

Al momento attuale i metodi per il calcolo dei logaritmi discreti delle curve ellittiche sono molto meno efficienti rispetto a quelli per la fattorizzazione dei numeri o per il calcolo dei logaritmi discreti standard. Quindi per avere la stessa sicurezza degli algoritmi basati sul calcolo modulare, sono sufficienti chiavi di lunghezza inferiore.

[da completare ...]

[Avanti] [Indietro] [Su] [Indice]