Appunti di...

Appunti di CrittografiaGerardo Pelosi

Dipartimento di Elettronica e InformazionePolitecnico di Milano

email: [email protected]

1

Indice

1 Algoritmo di Euclide 31.1 Esercizi sui campi Zp . . . . . . . . . . . . . . . . . . . . . . . 6

1.1.1 Esercizio 1 . . . . . . . . . . . . . . . . . . . . . . . . . 61.2 Algoritmi di Esponenziazione . . . . . . . . . . . . . . . . . . 10

1.2.1 Square and Multiply - Left to Right . . . . . . . . . . 101.2.2 Square and Multiply - Right to Left . . . . . . . . . . 11

1.3 Esercizio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.4 Esercizio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Esercizi sui campi Fpn 152.1 Esercizio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.2 Esercizio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.3 Esercizio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.4 Esercizio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

3 Aritmetica in multipla precisione 213.1 Algoritmi di Addizione e Sottrazione . . . . . . . . . . . . . . 223.2 Algoritmo di Moltiplicazione . . . . . . . . . . . . . . . . . . . 233.3 Rappresentazione di Montgomery . . . . . . . . . . . . . . . . 253.4 Moltiplicazione di Montgomery . . . . . . . . . . . . . . . . . 283.5 Note implementative . . . . . . . . . . . . . . . . . . . . . . . 35

2

Capitolo 1

Algoritmo di Euclide

Sia D un dominio agli ideali principali, cioè un anello dotato di unità in cuivale la legge di annullamento del prodotto e in cui ogni ideale è principale.Esempio: D =< Z,+, · >, D =< F[X],+, · >

Definizione 1.0.1. Dati a, b ∈ D, si definisce Massimo Comun Divisored = MCD(a, b), l’elemento d ∈ D tale che d|a, d|b e ∀y ∈ D : y|a∧y|b⇒ y|D.

Senza pretesa di rigore matematico, ci limitiamo a ricordare come, datia, b ∈ D se d ∈ D è il loro massimo comun divisore allora d divide ancheuna loro qualunque combinazione lineare: d|x · a + y · b con x, y ∈ D. Si puòdimostrare, assieme all’esistenza di d anche l’esistenza di almeno una coppiadi elementi xa, yb ∈ D tali che

d = xaa + ybb

Il precedente risultato permetterà di calcolare l’inverso moltiplicativo in uncampo finito.

Lemma 1.0.1. a, b ∈ D; a > b; se D è un dominio euclideo(es.: Z, F[X])si può definire una nozione di quoziente e si ha q = ba/bc; r = a mod b =a− qb ∈ {0, 1, 2 . . . , b− 1} e vale il seguente:

MCD(a, b) = MCD(b, a mod b)

3

Usando il lemma precedente si possono scrivere le seguenti uguaglianze:

a > b > 0 d = MCD(a, b)r0 = ar1 = b d = MCD(r0, r1)r2 = r0 mod r1 = r0 − br0/r1cr1; 0 ≤ r2 < r1 d = MCD(r1, r2)r3 = r1 mod r2 = r1 − br1/r2cr2; 0 ≤ r3 < r2 d = MCD(r2, r3)r4 = r2 mod r3 = r2 − br2/r3cr3; 0 ≤ r4 < r3 d = MCD(r3, r4)· · · · · ·rn = rn−2 mod rn−1 = rn−2 − brn−1/rn−2crn−2; rn = 0 d = MCD(rn−1, 0)

per un certo intero n si ha:

d = MCD(a, b) = rn−1

Pensiamo ora di riscrivere tutti i passaggi precedenti come combinazionilineari di a, b:

a > b > 0r0 = 1 · a + 0 · br1 = 0 · a + 1 · br2 = r0 mod r1 = (1a + 0b)− b r0

r1c(0a + 1b) = (ξ2a + η2b); 0 ≤ r2 < r1

r3 = r1 mod r2 = (0a + 1b)− b r1r2c(ξ2a + η2b) = (ξ3a + η3b); 0 ≤ r3 < r2

r4 = r2 mod r3 = (ξ2a + η2b)− b r2r3c(ξ2a + η2b) = (ξ4a + η4b); 0 ≤ r4 < r3

· · ·rn−1 = rn−3 mod rn−2 = (ξn−3a + ηn−3b)− b rn−3

rn−2c(ξn−2a + ηn−2b) =

= (ξn−1a + ηn−1b); 0 ≤ rn−1 < rr−2

rn = rn−2 mod rn−1 = (ξn−2a + ηn−2b)− b rn−3

rn−2c(ξn−1a + ηn−1b) =

= (ξna + ηnb); rn = 0

per cui:d = rn−1 = ξn−1a + ηn−1b; ξ, η ∈ D

Formalizzando la precedente costruzione si ottiene l’algoritmo di Euclideesteso per il calcolo del massimo comun divisore.

4

Algorithm 1.0.1: Algoritmo esteso di EuclideInput: a, b ∈ DOutput: d = ξa · a + ηb · b, ξa, ηb

begin1

u← (a, 1, 0)2

v ← (b, 0, 1)3

repeat4

w ← u− bu[0]v[0]c · v5

u← v6

v ← w7

until (w[0] = 0)8

d← u[0], ξa ← u[1], ηb ← u[2]9

return (d, ξa, ηb)10

end11

Esempio 1.0.1. Sia D =< Z, +, · >

d = MCD(11, 5) = 11ξ + 5η;

u← (11, 1, 0);v ← (5, 0, 1);

q = b115 c = 2, w ← (11− 2 · 5, 1− 0 · 2, 0− 1 · 2) = (1, 1,−2);

u← (5, 0, 1);v ← (1, 1,−2);

q = b51c = 5, w ← (5− 1 · 5, 0− 1 · 5, 1− (−2) · 5) = (0,−5, 11);u← (1, 1,−2);v ← (0,−5, 11);

d = 1; ξ = 1; η = −2.

infatti: 1 = 1 · 11 + (−2) · 5.

5

1.1 Esercizi sui campi Zp

1.1.1 Esercizio 1

Si consideri il seguente campo finito: F7∼= Z/7Z.

(1) Determinare le tavole di addizione e di moltiplicazione.

+ 0 1 2 3 4 5 60 0 1 2 3 4 5 61 1 2 3 4 5 6 02 2 3 4 5 6 0 13 3 4 5 6 0 1 24 4 5 6 0 1 2 35 5 6 0 1 2 3 46 6 0 1 2 3 4 5

· 1 2 3 4 5 61 1 2 3 4 5 62 2 4 6 1 3 53 3 6 2 5 1 44 4 1 5 2 6 35 5 3 1 6 4 26 6 5 4 3 2 1

(2) Determinare il numero degli elementi generatori del campo.

Se n = |F∗7| è la cardinalità del gruppo, allora il numero di elementi ge-

neratori è: ϕ(n) = ϕ(6) = 2.

6

N.B.:

Proposizione 1.1.1. In un gruppo ciclico G =< g > di ordine n = |g|, datoh ∈ N si ha:

|gh| = n

MCD(n, h)

Dim. Posto r = |gh|, si ha che ghr = (gh)r = e ⇒ n|hr; questo vuoldire che esiste un intero m tale che rh = mn; dividendo ambo i membri perMCD(n, h) si ottiene:

rh

MCD(n, h)= m

n

MCD(n, h)

hMCD(n,h) e n

MCD(n,h) sono co-primi per costruzione, quindi si può concludere:

n

MCD(n, h)|r

Viceversa si può osservare che

(gh)n

MCD(n,h) = (gn)h

MCD(n,h) = e⇒ r| n

MCD(n, h)

da cui la tesi. �

Teorema 1.1.1. Dato n ∈ N+, la funzione τ(n), definita come il numerodei divisori positivi di n:

τ(n) = |{d ∈ N+ : d|n}| =∑d|n

1

è una funzione moltiplicativa. Dati n, m ∈ N+ tali che MCD(n, m) = 1allora

τ(n ·m) = τ(n) · τ(m)

Il gruppo F∗7 è ciclico, quindi ammete almeno un generatore g0 = g ∈ F∗

7,cioè: < g0 >= F∗

7.Gli altri generatori saranno gli elementi gi = gi

0 tali che MCD(n, i) = 1 coni ∈ {2, 3, ..., n− 1}, il calcolo del numero di generatori coincide quindi con ilvalore della funzione di Eulero, valutata in n:

ϕ(n) = |{i ∈ Z, 0 < i < n : MCD(n, i) = 1}|

Valgono i seguenti:

Teorema 1.1.2. Siano n, m ∈ N+ con n > m, se MCD(n, m) = 1 alloraϕ(n ·m) = ϕ(n) · ϕ(m)

7

Teorema 1.1.3. Dato n ∈ N+, la funzione τ(n), definita come il numerodei divisori positivi di n:

τ(n) = |{d ∈ N+ : d|n}| =∑d|n

1

è una funzione moltiplicativa. Dati n, m ∈ N+ tali che MCD(n, m) = 1allora

τ(n ·m) = τ(n) · τ(m)

Lemma 1.1.1. Siano p un numero primo e k ∈ N+, allora

ϕ(pk) = pk − pk−1

τ(pk) = k + 1

Dim. Cerchiamo tutti i numeri interi minori di pk che abbiano unn fattorein comune con pk. Osserviamo che tali interi saranno tutti multipli di p,pertanto della forma h · p con h ∈ {1, . . . , pk−1}. Il numero di interi minoridi pk che hanno un fattore in comune con pk è: pk−1. Il numero di intericoprimi con pk è dunque immediato: ϕ(pk) = pk − pk−1.Per dimostrare che τ(pk) = k + 1 basta osservare che i divisori di pk sono:1, p, p2, . . . , pk. �

Lemma 1.1.2. Dato n ∈ N+ e la sua scomposizione in fattori primi n =∏sj=0 p

ej

j con s, ej ∈ N allora

ϕ(n) =s∏

j=0

pej

j − pej−1j = n

s∏j=0

(1− 1pj

).

τ(n) =s∏

j=0

(1 + ej).

Dim. È un’applicazione immediata delle proprietà enunciate precedente-mente. �

(3) Determinare gli elementi generatori del campo.

Procedendo per tentativi, iniziamo a verificare se g = 2 è un generatore:21 = 2, 22 = 4, 23 = 8 = 1, quindi l’elemnto g = 2 ha ordine 3 e non è un ge-neratore. Proviamo quindi con g = 3: 31 = 3, 32 = 2mod7, 33 = 6mod7 6= 1,osservando la fattorizzazione dell’ordine del gruppo n = |F∗

7| = 6 = 2 · 3 sideduce l’esistenza di soli elementi di ordine 1, 2, 3 o 6 e quindi dai calcolifatti possiamo concludere, senza ulteriori conti, che g0 = 3 è un elementogeneratore del campo F7.L’altro generatore sarà: g1 = g5

0 = 35 = 5 mod 7.

8

(4) Determinare l’inverso moltiplicativo dei seguenti elementi:

x = 4, y = 3

Abbiamo due modi per calcolare l’inverso di un elemento e precisamente:

• il Piccolo Teorema di Fermat: p primo, a ∈ F ∗p , a−1 = ap−2 mod p.

• l’Algoritmo Esteso di Euclide per il calcolo del massimo comun divisore:p primo, a ∈ F ∗

p , essendo MCD(p, a) = 1 = ξ · p + η · a per oppor-tuni interi ξ, η ∈ Z. Prendendo il modulo p di ambo i membri dellaprecedente uguaglianza si trova come: η ·a = 1modp⇒ η ≡ a−1modp.

Utilizzando il primo metodo si ha:

p = 7, x = 4, x−1 mod 7 ≡7 45 ≡7 (42 · 42 · 4) ≡7 22 · 4 ≡7 2

p = 7, y = 3, y−1 mod 7 ≡7 35 ≡7 (32 · 32 · 3) ≡7 22 · 3 ≡7 5

Utilizzando invece l’algoritmo di Euclide:

p = 7, x = 4⇒ 1 = MCD(7, 4) = 7ξ + 4η

{u← (7, 1, 0);v ← (4, 0, 1);q = b74c = 1, w ← (7− 4, 1− 0, 0− 1) = (3, 1,−1);u← (4, 0, 1);v ← (3, 1,−1);q = b43c = 1, w ← (4− 3 · 1, 0− 1 · 1, 1− (−1) · 1) = (1,−1, 2);u← (3, 1,−1);v ← (1,−1, 2);q = b31c = 3, w ← (3− 1 · 3, 1− (−1) · 3,−1− 2 · 3) = (0, 4, 7);u← (1,−1, 2);v ← (0, 4, 7);

d = 1; ξ = −1; η = 2⇒ x−1 = 4−1 mod 7 = 2

9

p = 7, y = 3⇒ 1 = MCD(7, 3) = 7ξ + 3η{u← (7, 1, 0);v ← (3, 0, 1);q = b73c = 2, w ← (7− 6, 1− 0, 0− 2) = (1, 1,−2);u← (3, 0, 1);v ← (1, 1,−2);q = b31c = 3, w ← (3− 1 · 3, 0− 1 · 3, 1− (−2) · 3) = (0,−3, 7);u← (1, 1,−2);v ← (0,−3, 7);

d = 1; ξ = −2; η = −2⇒ y−1 = 3−1 mod 7 ≡7 −2 ≡7 5

1.2 Algoritmi di Esponenziazione

In questa sezione descriveremo due varianti dell’algoritmo più conosciuto pereffettuare l’operazione di esponenziazione in maniera efficiente. Il problema èformulato nel modo seguente: dati a, n ∈ N, si vuole calcolare l’intero c = an

effettuando un numero di moltiplicazioni minore di n.Indicando con t il numero di cifre binarie necessarie per rappresentare l’interon, cioè:

t = dlg2 ne, n = (nt−1, . . . , n1, n0) con ni ∈ {0, 1}, i ∈ {0, 1, . . . , t− 1}

possiamo scrivere:

c = an = aPt−1

j=0 nj2j

= ant−12t−1+nt−22t−2+...+n121+n0 (1.1)

A seconda del modo in cui è possibile leggere l’ultimo membro della catenadi uguaglianze appena scritte si esibiscono diverse formalizzazioni dell’algo-ritmo noto come Square and Multiply(S&M).

1.2.1 Square and Multiply - Left to Right

Pensando di scandire l’esponente dell’eq. (1.1) da sinistra verso destra, valela seguente uguaglianza:

c = an = ((· · · ((ant−1)2 · ant−2)2 · · · )2 · an1)2 · an0

Esempio 1.2.1. Si supponga di voler applicare il metodo precedente al cal-colo di c = 56; allora a = 5, t = 3, n = 6 = 1102 = 1 · 22 + 1 · 21 + 0 · 20, sipuò scrivere:

c = 51102 = ((51)2 · 51)2 · 50 = (52 · 5)2 = 15625.

Il costo computazionale del metodo appena illustrato, espresso in numero dimoltiplicazioni e quadrati necessari per portare a termine la computazione èuguale a: dlg2 ne quadrati + 1

2dlg2 ne moltiplicazioni (caso medio).

10

Algorithm 1.2.1: S&M Left to RightInput: a, n, t = dlg2 ne, n = (nt−1, . . . , n1, n0), n ≥ 0Output: c = an

begin1

if n = 0 then2

return 13

c← a4

for i← t− 2 down-to 0 do5

c← c26

if ni = 1 then7

c← c · a8

return c9

end10

1.2.2 Square and Multiply - Right to Left

Pensando di scandire l’esponente dell’eq. (1.1) da destra verso sinistra, valela seguente uguaglianza:

c = an = (a20)n0 · (a21

)n1 · (a22)n2 · · · (a2t−1

)nt−1

Esempio 1.2.2. Si supponga di voler applicare il metodo precedente al cal-colo di c = 56; allora a = 5, t = 3, n = 6 = 1102 = 1 · 22 + 1 · 21 + 0 · 20, sipuò scrivere:

c = 51102 = (520)0 · (521

)1 · (522)1 = (5 · 52 · 54) = 15625.

Si osservi come i fattori tra parentesi possano essere calcolati come quadratidel fattore precedente.

Il costo computazionale del metodo appena illustrato, espresso in numero dimoltiplicazioni e quadrati necessari per portare a termine la computazione èuguale a: dlg2 ne quadrati + 1

2dlg2 ne moltiplicazioni (caso medio).

11

Algorithm 1.2.2: S&M Right to LeftInput: a, n, t = dlg2 ne, n = (nt−1, . . . , n1, n0), n ≥ 0Output: c = an

begin1

if n = 0 then2

return 13

b← a4

if n0 = 1 then5

c← a6

else7

c← 18

for i← 1 to t− 1 do9

b← b210

if ni = 1 then11

c← c · b12

return c13

end14

1.3 Esercizio 2

Si consideri il campo: F11∼= Z/11Z ∼= Z11, si chiede di:

1. determinare il numero di generatori del gruppo moltiplicativo;

2. esibire il valore di tutti i generatori del campo;

3. elencare tutti i sottogruppi di F∗11 con la loro cardinalità;

4. calcolare l’inverso moltiplicativo di x = 7;

5. descrivere il gruppo additivo del campo < F11,+ >;

(1) Determinare il numero di generatori del gruppo moltiplicativo.

F∗11 = {1, 2, . . . , 10}; n = |F∗

11| = 10;

numero generatori = ϕ(n) = ϕ(10) = ϕ(2 · 5) = 4

o anche

numero generatori = |{0 < i < n : MCD(i, n) = 1}| = |{1, 3, 7, 9}| = 4.

(2) Esibire il valore di tutti i generatori del campo.

Tenendo presente la scomposizione in fattori primi dell’ordine del gruppo

12

n = 2 · 5, assumendo come g = 2 come potenziale generatore, si ha:22 ≡11 4, 23 ≡11 8, 24 ≡11 5, 25 ≡11 10, dunque concludiamo che effetti-vamente g0 = g = 2 è un generatore del gruppo moltiplicativo del campoassegnato. Gli altri 3 generatori sono:

g1 = g30 = 23 ≡11 8;

g2 = g70 = 27 ≡11 7;

g3 = g90 = 29 ≡11 6.

Come verifica, si può provare ad elencare tutti gli elementi del sottogruppogenerato da g3: < g3 >= {g3 = 6, g2

3 = 3, g33 = 7, g4

3 = 9, g53 = 10, g6

3 =5, g7

3 = 8, g83 = 4, g9

3 = 2, g103 = 1}.

(3) Elencare tutti i sottogruppi di F∗11 con la loro cardinalità;

F∗11 = {1, 2, . . . , 10}; n = |F∗

11| = 10

Conoscendo la scomposizione in fattori primi dell’ordine del gruppo: n = 2·5possiamo dire che esisteranno soltanto 2 sottogruppi propri H1, H2 aventicardinalità rispettivamente n1 = 2 e n2 = 5.H1 =< h1 > con h1 elemento di F∗

11 di ordine n1 = 2, h1 = gn/n1

0 ≡11 10;H2 =< h2 > con h2 elemento di F∗

11 di ordine n2 = 5, h2 = gn/n2

0 ≡11 4;Tutti i sottogruppi di F∗

11 sono dunque:

H0 = {1}, n0 = 1

H1 = {10, 1}, n1 = 2

H2 = {4, 5, 9, 3, 1}, n2 = 5

F∗11 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, n = 10

(3) Calcolare l’inverso moltiplicativo di x = 7;

Impiegando l’algoritmo di Euclide si trova:

p = 11, x = 7⇒ 1 = MCD(7, 4) = 7ξ+4η dove ξ = 2, η = −3⇒ x−1 ≡11 8

Analogamente, utilizzando il Piccolo di Fermat e l’algoritmo di esponenzia-zione S&M Left to Right si ha:

x−1 ≡11 79 ≡11 710012 ≡11 ((72)2)2 · 7 ≡11 (52)2 · 7 ≡11 32 · 7 ≡11 8

13

(4) descrivere il gruppo additivo del campo: < F11,+ >;

< F11,+ >= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, | < F11,+ > | = 11, è un grup-po ciclico (∼= Z11) in cui tutti gli elementi ( 6= 0) sono generatori (ordineprimo), pertanto non ammette sottogruppi propri.

numero generatori = ϕ(11) = 10

Assumendo, ad esempio, g = 10 come generatore, si ha:

g ≡11 10, 2g ≡11 9, 3g ≡11 84g ≡11 7, 5g ≡11 6, 6g ≡11 5,

7g ≡11 4, 8g ≡11 3, 9g ≡11 2,

10g ≡11 1, 11g ≡11 0

1.4 Esercizio 3

Si consideri il campo: F13∼= Z/13Z ∼= Z13, si chiede di descrivere completa-

mente il gruppo moltiplicativo di tale campo elencando tutti i suoi sottogruppicon le coro cardinalità e i loro generatori nonché le eventuali relazioni tra isottogruppi trovati.

Sol: n = 12, numero di sottogruppi = 6;

n0 = 1, H0 =< 1 >= {1};

n1 = 4, H1 =< 8 >=< 5 >= {1, 5, 8, 12};

n2 = 2, H2 =< 12 >= {1, 12};

n3 = 3, H3 =< 3 >=< 9 >= {1, 3, 9};

n4 = 6, H4 =< 8 >=< 5 >= {1, 3, 4, 9, 10, 12};

n5 = 12, H5 =< 2 >=< 6 >=< 7 >=< 9 >= F∗13;

H0 < H2 < H1 < H5; H0 < H3 < H4 < H5.

14

Capitolo 2

Esercizi sui campi Fpn

2.1 Esercizio 1

Dopo aver verificato che il polinomio f(x) = x2−x−1 ∈ F3[X] è irriducibile,scrivere le tavole di addizione e moltiplicazione del campo:

F32∼= F3[X]/ < f(x) >∼= F3(α) con α ∈ F32\F3 : f(α) = 0.

Il polinomio f(x) ∈ F3[X] non ammette radici in F3 (f(0) = 2, f(1) =1, f(2) = 1), ed essendo deg(f(x)) = 2 si può concludere che è irriducibile.

+ 0 1 2 α α+1 α+2 2α 2α+1 2α+20 0 1 2 α α+1 2+α 2α 2α+1 2α+21 1 2 0 α+1 α+2 α 2α+1 2α+2 2α2 2 0 1 α+2 α α+1 2α+2 2α 2α+1α α α+1 α+2 2α 2α+1 2α+2 0 1 2α+1 α+1 α+2 α 2α+1 2α+2 2α 1 2 0α+2 α+2 α α+1 2α+2 2α 2α+1 2 0 12α 2α 2α+1 2α+2 0 1 2 α α+1 α+22α+1 2α+1 2α+2 2α 1 2 3 α+1 α+2 α2α+2 2α+2 2α 2α+1 2 0 1 α+2 α α+1

· 1 2 α α+1 α+2 2α 2α+1 2α+21 1 2 α α+1 α+2 2α 2α+1 2α+22 2 1 2α 2α+2 2α+1 α α+2 α+1α α 2α α+1 2α+1 1 2α+2 2 α+2α+1 α+1 2α+2 2α+1 2 α α+2 2α 1α+2 α+2 2α+1 1 α 2+2α 2 α+1 2α2α 2α α 2α+2 α+2 2 α+1 1 2α+12α+1 2α+1 α+2 2 2α α+1 1 α+2 α2α+2 2α+2 α+1 α+2 1 2α 2α+1 α α+1

(1) Determinare: gli elementi primitivi del campo; indicare tutti i possibilipolinomi irriducibili e polinomi primitivi che permettono di costruire il campoassegnato.

F32∼= F3(α) = θ0 + αθ1 : θ0, θ1 ∈ F3;α ∈ F32\F3 : f(α) = α2 − α− 1 = 0.

15

Il numero di polinomi irriducibili di grado 2: N2(3) = (32 − 3)/2 = 3; Pertrovare i tre polinomi, viste le ridotte dimensioni del campo procediamo nelseguente modo: f(x) = x2 + θ1x + θ0; f(0) 6= 0 ⇒ θ0 6= 0 ⇔ θ0 = 1, 2;dividiamo i due casi:(1◦caso): f(x) = x2+θ1x+1, dobbiamo imporre: f(2) = 2+2θ1 6= 0⇒ θ1 6=2; f(1) = 2 + θ1 6= 0 ⇒ θ1 6= 1; abbiamo così trovato un primo polinomioirriducibile:

f1(x) = x2 + 1

(2◦caso): f(x) = x2 + θ1x + 2, dobbiamo imporre: f(1) = θ1 6= 0; f(2) =6 + 2θ1 6= 0⇒ θ1 6= 0; abbiamo così individuato gli altri due polinomi:

f2(x) = x2 + x + 2f3(x) = x2 + 2x + 2 = x2 − x− 1

Sia n = |F∗32 | la cardinalità del gruppo moltiplicativo, allora il numero di

elementi primitivi del campo è: ϕ(n) = ϕ(8) = 4; il numero di polinomiprimitivi di grado 2 è invece: M2(3) = ϕ(8)/2 = 2. Si sono individuati 3polinomi irriducibili, due di questi saranno primitivi.Iniziamo con il trovare un elemento generatore di F∗

32 , usando il polinomioirriducibile f(x) = x2 − x− 1 per fare i calcoli (f(α) = 0⇔ α2 = α + 1).

α1 = α; α2 = α + 1; α3 = 2α + 1; α4 = 2⇒ α è primitivo.

(Oss.: i divisori dell’ordine n sono 1,2,4,8. )Trovato un elemento primitivo β0 = α, gli altri elementi primitivi sarannodunque: β1 = α3 = 2α + 1, β2 = α5 = 2α, β3 = α7 = α + 2.Per calcolare i polinomi primitivi richiesti, applichiamo la definizione e tro-viamo:

g1(x) = (x− α)(x− α31) = x2 + 2x + 2 = x2 − x− 1

g2(x) = (x− β1)(x− β31

1 ) = (x− α5)(x− α15) = x2 + x + 2

(2) Calcolare l’inverso dei seguenti elementi in F32∼= F3[X]/ < x2−x−1 >.

g(x) = x + 1 h(x) = 2x

Impiegando il Piccolo di Fermat si trova:

(g(x))−1 = (x + 1)8−1 mod f(x) = (x + 1)1112 mod f(x) == ((x + 1)2(x + 1))2(x + 1) mod f(x) = · · · = 2x + 2.

(h(x))−1 = (2x)8−1 mod f(x) = (2x)1112 mod f(x) == ((2x)2(2x))2(2x) mod f(x) = · · · = 2x + 1.

16

Analogamente volendo utilizzare l’algoritmo esteso di Euclide si ha:

f(x) = x2−x−1, g(x) = x+1⇒ 1 = MCD(f(x), g(x)) = f(x)ξ(x)+g(x)η(x)

{u← (x2 − x− 1, 1, 0);v ← (x + 1, 0, 1); q = bx2−x−2

x+1 c = x− 2, w ← (x2 − x− 1− (x + 1)(x− 2), 1,−(x− 2));u← (x + 1, 0, 1);v ← (1, 1,−x + 2);q = bx+1

1 c = x + 1, w ← (x + 1− (x + 1), 0− (x + 1), 1− (−x + 2)(x + 1));u← (1, 1, 2x + 2);v ← (0, 2x + 2, 1);

d(x) = 1; ξ(x) = 1; η(x) = 2x + 2⇒ (g(x))−1 mod f(x) = 2x + 2

f(x) = x2−x−1, h(x) = 2x⇒ 1 = MCD(f(x), g(x)) = f(x)ξ(x)+g(x)η(x)

{u← (x2 − x− 1, 1, 0);v ← (2x, 0, 1); q = bx2−x−1

2x c = 2x + 1, w ← (−1, 1, x− 1);u← (2x, 0, 1);v ← (−1, 1, x− 1);q = b 2x

−1c = x, w ← (0, 2x, 2x2 + x + 1);u← (−1, 1, x− 1);v ← (0, 2x, 2x2 + x + 1);

d(x) = ξ(x)f(x) + η(x)h(x), d(x) = −1; ξ(x) = 1; η(x) = x− 1⇒−1 = (1)f(x) + (x− 1)h(x)⇔1 = (−1)f(x) + (2x + 1)h(x)⇒

η(x) = (h(x))−1 mod f(x) = 2x + 1 mod f(x)

2.2 Esercizio 2

Descrivere il campo: F23 .

Detto f(x) il polinomio irriducibile utilizzato per rappresentare il campo siha: F23

∼= F2(α) = {θ0 + αθ1 + α2θ2 : θ0, θ1, θ2 ∈ F2; f(α) = 0}.

Il numero di elementi generatori del campo = ϕ(|F∗23 |) = ϕ(7) = 6, quindi

17

tutti gli elementi 6= 0, 1 sono generatori.Il numero di polinomi irriducibili di grado 3 = N3(2) = (23 − 2)/3 = 2.Il numero di polinomi primitivi di grado 3 = M3(2) = ϕ(7)/3 = 2. risultatoscontato, dopo aver osservato che tutti gli elementi del gruppo moltiplicativosono generatori.Per esibire i polinomi primitivi/irriducibili, essendo l’estensione del campouguale a 3, i polinomi per essere irriducibili non devono ammettere comeradici 0 o 1, cioè devono avere un numero dispari di coefficienti e un terminenoto non nullo:

f1(x) = x3 + x2 + 1; f2(x) = x3 + x + 1

2.3 Esercizio 3

Descrivere il campo: F25 .

Il numero di polinomi irriducibili di grado 5 = N5(2) = (25 − 2)/5 = 6.Il numero di elementi generatori del campo = ϕ(|F∗

25 |) = ϕ(31) = 30, quinditutti gli elementi 6= 0, 1 sono generatori; il numero di polinomi primitivi digrado 5 coincide con il numero dei polinomi irriducibili.Per esibire i 6 polinomi primitivi del campo, iniziamo con l’elencare tutti ipossibili trinomi e pentanomi a coefficienti in F2 (Condizione necessaria perl’irriducibilità, è che i polinomi in oggetto non ammettano radici nel campobase F2):

f1(x) = x5 + x4 + x3 + x2 + 1f2(x) = x5 + x4 + x3 + x + 1f3(x) = x5 + x4 + x2 + x + 1f4(x) = x5 + x3 + x2 + x + 1f5(x) = x5 + x4 + 1f6(x) = x5 + x3 + 1f7(x) = x5 + x2 + 1f8(x) = x5 + x + 1

Applicando il seguente test di irriducibilità, ai polinomi adesso elencati, sitrova che f5(x) e f8(x) NON sono irriducibili.

Teorema 2.3.1 (Test di irriducibilità). Sia f(x) ∈ Fp[X] un polinomiomonico di grado m, allora f(x) è irriducibilie se e soltanto se:

MCD(f(x), xph − x) = cost ∀h ≤ [m/2]

18

2.4 Esercizio 4

Considerato il campo F34∼= F3[X]/ < f(x) >:

(1) indicare il numero di elementi generatori;(2) il numero di polinomi irriducibili;(3) il numero dei polinomi primitivi;(4) verificare che il polinomio f(x) = x4 + x− 1 ∈ F3[X] è irriducibile.(5) verificare che l’elemento α ∈ F34\F3 : f(α) = 0 è un elemento primitivodel campo.(6) Sapendo che f(x) = (x − α)(x − α3)(x − α9)(x − α27) = x4 + x − 1 èprimitivo, determinare un altro polinomio primitivo del campo, giustificandoil procedimento. (Sugg.: considerare l’elemento β = α7)

Sol: n = 80, numero generatori = 32; numero pol. irriducibili = 18;numero pol. primitivi = 8.Condizione necessaria perchè il polinomio f(x) = x4 + x− 1 sia irriducibile:f(0) = 2 6= 0, f(1) = 1 6= 0, f(2) = 2 6= 0, quindi il polinomio dato nonammette fattori di primo grado a coefficienti in F3, quello che rimane daverificare, essendo il polinomio di quarto grado è che non ammetta fattori disecondo grado:

(x4 + x + 1) = (x2 + ax + b)(x2 + cx + d) a, b, c, d ∈ F3

eseguendo i prodotti si imposta il sistema:a + c = 0d + ac + b = 0ad + bc = 0bd = −1

osservando la prima e l’ultima equazione si vede come i valori possibili pera,b,c,d ∈ F3 siano: a = 1, d = −1 oppure a = −1, d = 1; mentre a = 1, c =−1 oppure a = −1, c = 1; e per ognuna di queste combinazioni di valorisi vede come la seconda equazione non sia mai soddisfatta. Si può dunqueconcludere che il polinomio f(x) = x4 + x− 1 ∈ F3[X] è irriducibile.Fissando per i calcoli il polinomio f(x) = x4 + x − 1, un altro polinomioprimitivo del campo è: g(x) = x4 + x3 − x2 − x− 1

19

Nota:

α4 = −α + 1;α5 = −α2 + α

α6 = −α3 + α2;α7 = α3 + α− 1α8 = α2 + α + 1;α9 = α3 + α2 + α

α10 = α3 + α2 − α + 1α16 = −α3 + α− 1α20 = −α3 − α2 + α

α40 = 2;

20

Capitolo 3

Aritmetica in multiplaprecisione

Gli algoritmi presentati nel seguito del capitolo sono descritti per l’uso congrandi interi non-negativi espressi in notazione posizionale in base b, doveb può essere un qualunque intero ≥ 2. Sebbene le descrizioni siano comple-tamente generali e indipendenti dalla particolare piattaforma di calcolo, lascelta ottimale per il valore di b dipenderà dalla particolare implementazionedegli algoritmi. In particolare, b dovrebbe essere scelto in modo tale chemoltiplicazioni, divisioni e riduzioni modulo bk (k > 0) siano semplici. Nelseguito sia N il modulo

N =n−1∑i=0

Nibi, 0 < Nn−1 < b e 0 ≤ Ni < b, i = 0, 1, . . . , n− 2

e sia x ≥ N il numero che deve essere ridotto modulo N

x =l−1∑i=0

xibi, 0 < xl−1 < b e 0 ≤ xi < b, i = 0, 1, . . . , l − 2, 0 < l ≤ 2n− 1

21

3.1 Algoritmi di Addizione e Sottrazione

Addizioni e sottrazioni tra interi espressi in notazione multipla sono eseguiteseguendo lo schema di calcolo mostrato negli algoritmi 3.1.1 3.1.2. Gli ope-randi coinvolti devono avere entrambi la stessa lunghezza. L’operazione diriduzione in modulo dovrà essere eseguita successivamente confrontando ilrisultato della somma con il valore di N . Si osservi come per poter gestire

Algorithm 3.1.1: Addizione in multipla precisioneInput: A = An−1b

n−1 + . . . + A1b + A0,B = Bn−1b

n−1 + . . . + B1b + B0

Output: x = A + B = xnbn + . . . + x1b + x0

begin1

x← 02

k ← 03

for j ← 0 to n− 1 do4

xi = Ai + Bi + k mod b5

if (Ai + Bi + k < b) then6

k ← 07

else8

k ← 19

xn = k10

return x11

end12

i risultati intermedi Ai + Bi + k si necessiti di due cifre in precisione singolada gestire opportunamente per valutare correttamente gli assegnamenti e iconfronti. L’algoritmo di sottrazione è analogo a quello di somma, anzichèaversi la propagazione di un carry si ha la propagazione di un borrow. Per ilcorretto funzionamento dell’algoritmo si suppone che il primo operando siasempre maggiore o uguale al secondo.

22

Algorithm 3.1.2: Sottrazione in multipla precisioneInput: A = An−1b

n−1 + . . . + A1b + A0,B = Bn−1b

n−1 + . . . + B1b + B0

Output: x = A + B = xnbn + . . . + x1b + x0

begin1

x← 02

k ← 03


xi = Ai −Bi + k mod b5

if (Ai −Bi + k < b) then6

k ← 07

else8

k ← −19

xn = k10

return x11

end12

3.2 Algoritmo di Moltiplicazione

Esistono diverse metodologie per eseguire velocemente ed efficientemente lamoltiplicazione fra numeri interi in precisione multipla.Le tecniche asintoticamente (nella dimensione degli operandi) più efficientisono quelle basate sulla FFT (Fast Fourier Transform). Per dimensioni deglioperandi di qualche migliaio di bit risulta però più vantaggioso non ricorrerea simili tecniche ma far uso di metodi più elementari. Nel seguito vengonopresentate due implementazioni, a differenti livelli di dettaglio, dell’algorit-mo di moltiplicazione school-book.Nell’ eseguire operazioni in modulo la strategia sottointesa è quella del mol-tiplica e riduci per cui oltre agli algoritmi mostrati di seguito è necessariodisporre anche di un metodo efficiente per eseguire le riduzioni modulo N .

23

Algorithm 3.2.1: Moltiplicazione in multipla precisioneInput: A = An−1b

n−1 + . . . + A1b + A0,B = Bn−1b

n−1 + . . . + B1b + B0

Output: x = A ·B = x2n−1b2n−1 + . . . + x1b + x0

begin1

x← 02

for i← 0 to n− 1 do3

x← x + AiBbi4

return x5

end6

Dettagliando tutte le operazioni a livello di cifre in precisione singola, unapossibile versione ottimizzata dell’algoritmo precedente è quella mostrata nelseguito. Per sommare una cifra in precisione singola k, al numero in preci-sione doppia (u, v)b occorre eseguire la somma sulla cifra meno significativav = v + k e gestire la creazione di un eventuale carry come u = u + (v < k);la cifra v è sicuramente corretta poichè si suppone che tutte le operazioni inprecisione singola agiscano modulo b.

Algorithm 3.2.2: Moltiplicazione in multipla precisione OttimizzataInput: A = An−1b

n−1 + . . . + A1b + A0,B = Bn−1b

n−1 + . . . + B1b + B0

Output: x = A ·B = x2n−1b2n−1 + . . . + x1b + x0

begin1

x← 02


k ← 04


(u, v)b = AiBj6

v = v + k7

u = u + (v < k)8

v = v + xi+j9

u = u + (v < xi+j)10

xi+j = v11

k = u12

xj+n = k13

return x14

end15

24

3.3 Rappresentazione di Montgomery

Eseguire moltiplicazioni modulari, facendo uso di una strategia del tipo mol-tiplica e riduci presuppone l’utilizzo di un algoritmo di riduzione sufficinte-mente efficiente che non faccia uso di divisioni nè in precisione singola nèin precisione multipla. La tecnica di Montgomery permette di eseguire unamoltiplicazione modulare con un costo computazionale quasi uguale a quellodi una moltiplicazione tra interi in precisione multipla. Detto n il nume-ro di cifre dei fattori, il costo della moltiplicazione di Montgomery è pari a2n(n + 1) moltiplicazioni in precisione singola a fronte di un costo per ese-guire una moltiplicazione in precisione multipla pari a n2.Dato un intero positivo N ∈ N+ si consideri l’anello ZN = {0, 1, 2, . . . , N−1}.Si definisce trasformazione di Montgomery una particolare permutazione tragli elementi di ZN , cioè una funzione biunivoca:

µ : < ZN ,+, · > → < ZN ,+, ∗ >

La trasformazione di Montgomery è quindi un omomorfismo dall’anello ZN

con le tradizionali definizioni delle operazioni di somma e moltiplicazione traelementi mod N , ad un insieme numerico ZN (dominio di Montgomery) cheè ancora un anello di classi di resto modulo N con la medesima definizioneper l’operazione di somma, ma che presenta una diversa definizionedell’operazione di moltiplicazione.La moltiplicazione nel dominio ZN deve poter essere svolta in maniera piùefficiente rispetto all’operazione definita in ZN . In tal modo, se un certoalgoritmo prevede una lunga successione di moltiplicazioni modulari suglistessi operandi in ZN , lo schema di calcolo da adottare è quello di tradurre glioperandi nel dominio di Montgomery, effettuare le moltiplicazioni e soltantoal termine della computazione esprimere nuovamente il valore degli operandinell’anello ZN . Siano:

x ∈ ZN = {0, 1, . . . , N − 1}R ∈ N+ con R > N, MCD(R,N) = 1 = RR′ −NN ′

R′ ≡ R−1 mod N con 0 ≤ R′ < N

N ′ ≡ −N−1 mod R con 0 ≤ N ′ < R

allora la definizione delle funzioni di trasformazione è la seguente:

x = µ(x) = x ·R mod N

x = µ−1(x) = x ·R′ mod N

La biunivocità delle funzioni µ, µ−1 è garantita dalla condizione di co-primalità tra R e N .Le condizioni sulla scelta del valore del parametro R, denominato Radicedi Montgomery, non risultano molto stringenti, quindi generalmente non c’è

25

nessun motivo per non scegliere R uguale ad una potenza di 2, tanto più che,generalmente, nelle implementazioni di algoritmi crittografici asimmetrici ilmodulo N è un numero primo > 3 o è fattorizzabile nel prodotto di numeriprimi grandi (e.g.: RSA) e quindi MCD(2n, N) = 1. Le operazioni di divi-sione e di modulo che impiegano un dividendo uguale ad una potenza di 2sono in assoluto le più semplici ed efficienti da implementare.Come già anticipato, le operazioni di somma e differenza (mod N) traelementi nella rappresentazione di Montgomery coincidono con le consueteoperazioni tra elementi di ZN , infatti:

x± y = xR mod N ± yR mod N = (x± y)R mod N = ˜(x± y)

Riguardo alla moltiplicazione, siano x, y ∈ ZN due elementi che vogliamomoltiplicare e x, y ∈ ZN le immagini corrsiponedenti secondo la trasforma-zione di Montgomery, allora

x · y mod N = xyR2 mod N = xyR mod N 6= xy

si osserva come l’operazione di moltiplicazione ∗ sia sostanzialmente diversadal semplice prodotto in ZN .Prima di poter esibire una descrizione operativa dell’operazione di moltipli-cazione (∗) tra elementi del dominio di Montgomery, affrontiamo la questionedello svolgere efficientemente e correttamente il seguente calcolo:

x ∈ ZN , x← x

R mod Nmod N.

Affinché la divisione (x/R)modN possa essere eseguita in maniera efficiente,è necessario che l’espansione di x in base R, riporti uno zero come ciframeno significativa, se così non è, l’idea del metodo di Montgomery è quelladi aggiungere ad x un opportuno intero t ∈ N e calcolare

x← x + t

Rmod N.

La correttezza del procedimento è garantita se sono rispettate le seguenticondizioni:{

x + t ≡N xx + t ≡R 0

⇒{

t ≡N 0⇒ t = t′N, t′ ∈ N+

x + t′N ≡R 0⇒

{t = t′N, t′ ∈ N+

t′ ≡R (−N−1)x = N ′x mod R

La formulazione operativa dei precedenti ragionamenti consente quindidi definire la così-detta Riduzione di Montgomery come indicato dall’algo-ritmo 3.3.1.

26

Algorithm 3.3.1: MRed(.) - Riduzione di MontgomeryInput: 0 < x ≤ RN

N,R con R > N , MCD(R,N) = 1 = RR′ −NN ′

Output: xR−1 mod Nbegin1

t′ ← xN ′ mod R2

x← x + Nt′3

x← x/R4

if x ≥ N then5

x← x−N6

return x7

end8

Per giustificare l’ultimo passaggio dell’algoritmo facciamo le seguenti osser-vazioni: t′ < R, x + Nt′ < RN + RN , (x + Nt′)/R < 2N .

Facendo uso dell’operazione di riduzione secondo Montgomery anchel’operazione di moltiplicazione tra elementi del dominio trasformato ZN puòessere formalizzata operativamente come mostrato dall’algoritmo 3.3.2.

Algorithm 3.3.2: MMul(.,.) - Moltiplicazione di MontgomeryInput: x = xR, y = yR ∈ ZN

Output: z = xyR mod Nbegin1

return z ←MRed(x · y)2

end3

Partendo da elementi che sono nel dominio di Montgomery, l’applicazionedell’operazione ∗ comporta un risultato che è ancora nella forma di Montgo-mery:

x ∗ y mod N = (xR · yR) ·R−1 mod N = (xyR2) ·R−1 mod N = xy mod N

Alla luce della precedente definizione, osserviamo come, la descrizioneoperativa delle due funzioni di trasformazione:

µ : ZN → ZN : x = µ(x) = xR mod N

µ−1 : ZN → ZN : x = µ−1(x) = xR′ mod N

necessiti della costante R2 mod N , infatti utilizzando l’algoritmo3.3.2 si ha:

x = µ(x) = xR mod N = MMul(x,R2 mod N)

x = µ−1(x) = xR′ mod N = MMul(x, 1)

27

3.4 Moltiplicazione di Montgomery

Per scrivere un algoritmo che effettui contemporanemente la riduzione e lamoltiplicazione di due numeri in precisione multipla è necessario adattarel’algoritmo di Riduzione di Montgomery per trattare numeri in precisionemultipla, così come mostrato nell’algoritmo 3.4.1.

N = (Nn−1Nn−2 . . . N1N0); x = (xn−1xn−2 . . . x1x0); x < N

x← x

RmodN =

x

bnmodN = (· · · ((x

bmod N)︸︷︷︸

i=0

1b

mod N)

︸︷︷︸i=1

· · · 1b

mod N)

︸︷︷︸i=n−1

, n− volte

i = 0

x← x

bmod N ⇔ x← x + t′

bmod N{

x + t′ ≡N xx + t′ ≡b 0

⇒{

t′ ≡N 0⇒ t′ = tN, t ∈ N+

x + tN ≡b 0⇒ x0 + tN0 ≡b 0⇒{

t′ = tN, t′ ∈ N+

t ≡b (−N−10 )x0 ≡b N ′

0x0⇒

x← x + t′

bmod N ⇔ x← x + (N ′

0x0 mod b)Nb

mod N

Supponendo di effettuare la divisione per b e successivo modN in un secondomomento si ottiene:

x← x + (N′0x0 mod b)Nb0 ⇒ x = (xnxn−1 . . .x2x10)

Oss: il numero x è ora rappresentato con n+1 cifre con la meno significativauguale a 0;i = 1 {

xb + t′ ≡N

xb

xb + t′ ≡b 0

⇒{

t′ ≡N 0⇒ t′ = tN, t ∈ N+

xb + tN ≡b 0⇒ x1 + tN0 ≡b 0

⇒

{t′ = tN, t′ ∈ N+

t ≡b (−N−10 )x1 ≡b N ′

0x1⇒

x←xb + t′

bmod N ⇔ x←

xb + (N ′

0x1 mod b)Nb

mod N

Supponendo di effettuare le divisioni per b e successivi modN in un secondomomento si ottiene:

x← x + (N′0x1 mod b)Nb1 ⇒ x = (xn+1xn . . .x3x200)

28

Oss: il numero x è ora rappresentato con n + 2 cifre con le due meno signi-ficative uguali a 0.....i = n− 1{

xbn−1 + t′ ≡N

xbn−1

xbn−1 + t′ ≡b 0

⇒{

t′ ≡N 0⇒ t′ = tN, t ∈ N+

xbn−1 + tN ≡b 0⇒ xn−1 + tN0 ≡b 0

⇒

{t′ = tN, t′ ∈ N+

t ≡b (−N−10 )xn−1 ≡b N ′

0xn−1⇒

x←x

bn−1 + t′

bmod N ⇔ x←

xbn−1 + (N ′

0xn−1 mod b)Nb

mod N

Supponendo di effettuare le divisioni per b e successivi modN in un secondomomento si ottiene:

x← x + (N′0xn−1 mod b)Nbn−1 ⇒ x = (x2nx2n−1 . . .xn00 . . .0)

Oss: il numero x è ora rappresentato con 2n cifre con le n meno significativeuguali a 0.

Algorithm 3.4.1: Riduzione di Montgomery in multipla precisioneInput: N = Nn−1b

n−1 + . . . + N1b + N0, R = bn,MCD(R,N) = 1 = RR′ −NN ′

Output: xR−1 mod Nbegin1


t← N ′0xi mod b3

x← x + tNbi4

x← x/bn5

if x ≥ N then6

x← x−N7

return x8

end9

29

Mettendo insieme l’algoritmo 3.4.1 con l’algoritmo 3.2.1 di moltiplicazio-ne tra interi in precisione multipla si ottiene l’algoritmo di Montgomery permoltiplicazione modulare tra due numeri interi in precisione multipla.

Algorithm 3.4.2: Moltiplicazione di Montgomery in precisionemultipla

Input: A = An−1bn−1 + . . . + A1b + A0,

B = Bn−1bn−1 + . . . + B1b + B0,

N = Nn−1bn−1 + . . . + N1b + N0,

R = bn, MCD(R,N) = 1 = RR′ −NN ′,N ′

0 = (−N−1 mod N) mod bOutput: x = ABR−1 mod Nbegin1

x← 02


x← x + AiBbi4

t← N ′0xi mod b5

x← x + tNbi6

x← x/bn7

if x ≥ N then8

x← x−N9

return x10

end11

Osservazione 3.4.1. Ad ogni iterazione, la cifra meno significativa dell’ac-cumulatore x viene resa uguale a 0.

Osservazione 3.4.2. In entrambi gli algoritmi 3.4.2, 3.4.3 la scelta dellaRadice di Montgomery R può essere fatta cercando di ottimizzare ulterior-mente gli algoritmi. In particolare quando si effettua la computazione di unaesponeneziazione modulare è possibile evitare il controllo e l’eventuale sot-trazione finale ad ogni passo intermedio e rimandare un unico controllo coneventualmente un’unica sottrazione soltanto al termine del calcolo. Se R èscelta tale che R > 4N (R ≥ 4bn) anziché R > N (R ≥ bn), applicando glialgoritmi di moltiplicazione ad operandi A,B < 2N rimane comunque garan-tita la condizione che tutti i risultati parziali risultino < 2N . Sia w = A ·B,allora:

(w + N(R− 1))R

≤ (2N − 1)2 + N(R− 1)R

<4N2 + NR

R< 2N.

La presente osservazione risulta essere particolarmente utile in realizzazionihardware di dispositivi crittografici.

30

Algorithm 3.4.3: Moltiplicazione di Montgomery OttimizzataInput: A = An−1b

n−1 + . . . + A1b + A0,B = Bn−1b

n−1 + . . . + B1b + B0,N = Nn−1b

n−1 + . . . + N1b + N0,R = bn, MCD(R,N) = 1 = RR′ −NN ′,N ′


x← 02


x← x + AiB4

t← N ′0x0 mod b5

x← (x + tN)/b6

if x ≥ N then7

x← x−N8

return x9

end10

Osservazione 3.4.3. L’algoritmo 3.4.3 di moltiplicazione e riduzione con-giunti, ammette complessità computazionale pari a (2n + 1)n moltiplicazionitra cifre espresse in base b che confrontata con il costo computazionale dellasola moltiplicazione in precisione multipla: n2 (algoritmo 3.2.2), permettedi cogliere i vantaggi di questo tipo di rappresentazione.

31

Algorithm 3.4.4: Moltiplicazione di Montgomery(Menezes et al., HandBook of Applied Cryptography, Algorithm 14.36)

Input: A = An−1bn−1 + . . . + A1b + A0,

B = Bn−1bn−1 + . . . + B1b + B0,

N = Nn−1bn−1 + . . . + N1b + N0,

R = bn, MCD(R,N) = 1 = RR′ −NN ′,N ′


x← 02


t← N ′0(x0 + AiB0) mod b4

x← (x + AiB + tN)/b5

if x ≥ N then6

x← x−N7

return x8

end9

32

Esempio 3.4.1. Siano:

b = 2, n = 4, N = 11, R = 2n = 16

ZN = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

R ZN = {0, 5, 10, 4, 9, 3, 8, 2, 7, 1, 6}

MCD(R,N) = RR′ −NN ′ ⇔MCD(16, 11) = 1

Utilizzando l’algoritmo esteso di Euclide si trovano i due parametri R′ e N ′:

u = (16, 1, 0) v = (11, 0, 1) q = [16/11] = 1w = (5, 1,−1)u = (11, 0, 1) v = (5, 1,−1) q = [11/5] = 2w = (1,−2, 3)u = (5, 1,−1) v = (1,−2, 3) q = [5/1] = 5w = (0, 11,−16)u = (1,−2, 3) v = (0, 11,−16)

R′ = −2, N ′ = −3, N ′0 = 1 mod 2

Supponiamo, quindi, di voler moltiplicare i seguenti numeri:

A = 4, B = 8, AB mod N = 32 mod 11 = 10, ABR mod N = 6

A = 9, B = 7, (AB) = ABR−1 mod N = 63(−2) mod 11 = 6

A = 9 = 10012, B = 7 = 01112, N = 10112, N ′0 = 1

33

0000 +0111 A0B = 01110111 +1011 t = N ′

0X0N = 101110010 right shift

1001 +0000 A1B = 00001001 +1011 t = N ′


1010 +0000 A2B = 00001010 +0000 t = N ′


0101 +0111 A3B = 01111100 +0000 t = N ′


(AB) = 01102 = 6

34

3.5 Note implementative

Nelle implementazioni reali dell’algoritmo di Montgomery vengono impiegatialcuni altri accorgimenti per semplificare ulteriormente le operazioni eseguitedall’algoritmo 3.4.4. L’osservazione fondamentale è la seguente, se:

R = bn, A = (0, An−1, An−2, . . . , A1, A0), B = (Bn−1, Bn−2, . . . , B1, B0)

allora

MMul(A,B) = ABR−1 mod N ≡ A(bB)(bR)−1 mod N

La precedente relazione permette di modificare il ciclo dell’algoritmo diMontgomery. Infatti, eseguendo un’ ulteriore iterazione (che è equivalen-te a pensare di aver assunto un nuovo R1 = R · b = bn+1) si vede come ilcalcolo del parametro t possa essere ulteriormente semplificato, visto che lacifra meno signidficativa del fattore (bB) sarà sempre nullo.

Algorithm 3.5.1: Moltiplicazione di Montgomery: nota 1Input: A = (0, An−1, . . . , A1, A0), B = (Bn−1, . . . , B1, B0),

N = (Nn−1, . . . , N1, N0),R = bn, MCD(R,N) = 1 = RR′ −NN ′,N ′


x← 02

for i← 0 to n do3

t← N ′0x0 mod b4

x← (x + (Ai(bB)) + tN)/b5

if x ≥ N then6

x← x−N7

return x8

end9

Ri-arrangiando il codice dell’algoritmo si arriva all’algoritmo 3.5.2:

35

Algorithm 3.5.2: Moltiplicazione di Montgomery: nota 2Input: A = (0, An−1, . . . , A1, A0), B = (Bn, . . . , B1, B0),

N = (Nn−1, . . . , N1, N0),R = bn, MCD(R,N) = 1 = RR′ −NN ′,N ′


x← 02

for i← 0 to n do3

if N ′0x0 mod b 6= 0 then4

x← x + tN5

x← x/b + AiB6

if x ≥ N then7

x← x−N8

return x9

end10

Scegliendo come base di rappresentazione degli elementi, quella binaria b = 2,la formulazione del metodo di Montgomery secondo la variante dell’algoritmo3.5.2, assume un aspetto particolarmente interessante, poiché l’intera ope-razione risulta essere eseguibile utilizzando esclusivamente un sommatore.L’algoritmo 3.5.3 è quindi spesso implementato per la realizzazione delle pri-mitive del crittosistema RSA in cui il modulo N = p · q (primi) è un numerodispari.

36

Algorithm 3.5.3: Radix-2 Montgomery ProductInput: A = (0, An−1, . . . , A1, A0), B = (Bn, . . . , B1, B0),

N = (Nn−1, . . . , N1, N0),R = 2n, MCD(R,N) = 1 = RR′ −NN ′,N ′

0 = (−N−1 mod N) mod 2 = −N−10 mod 2 = 1

Output: x = ABR−1 mod Nbegin1

x← 02

for i← 0 to n do3

if x0 == 1 then4

x← x + N5

x← x/2 + AiB6

if x ≥ N then7

x← x−N8

return x9

end10

Infine facendo riferimento all’osservazione 3.4.2: R ≥ 4N = 2n+2, n =dlg2Ne, ammettendo operandi e risultati parziali minori di 2N ad ogni ite-razione, A,B < 2N cioè A = An2n+. . .+A12+A0, B = Bn2n+. . .+B12+B0,N = Nn−12n−1 + . . . + N12 + N0 si ha:

Algorithm 3.5.4: RSA - Radix-2 Montgomery ProductInput: A = (0, An, An−1, . . . , A1, A0), B = (Bn, . . . , B1, B0)

R = 2n+2, N = (Nn−1, . . . , N1, N0)Output: x = ABR−1 < N oppure x = ABR−1 + N < 2Nbegin1

x← 02

for i← 0 to n + 1 do3

t← x0 + AiB0 mod 24

x← (x + (AiB) + tN)/25

return x6

end7

L’algoritmo 3.5.4 può essere ri-scritto impiegando l’osservazione ABR−1modN ≡A(2B)(2R)−1modN ; così aggiungendo un ulteriore ciclo (fino all’ n+2-esimo)si arriva alla formulazione dell’algoritmo 3.5.5.

37

Algorithm 3.5.5: RSA - Radix-2 Montgomery ProductInput: A = (0, 0, An, An−1, . . . , A1, A0), B = (Bn, . . . , B1, B0),

R = 2n+2, N = (Nn−1, . . . , N1, N0)Output: x = ABR−1 < N oppure x = ABR−1 + N < 2Nbegin1

x← 02

for i← 0 to n + 2 do3

if x0 == 1 then4

x← (x + N)5

x← x/2 + AiB6

return x7

end8

38

Appunti di...

Documents

Transcript of Appunti di...