La generazione della chiave privata nell'algoritmo RSA

Cristiano Teodoro

cristianoteodoro@virgilio.it

GENERAZIONE della CHIAVE PRIVATA

La

nell’algoritmo crittografico RSA a chiave pubblica

Chiave Privata : 215848789810065513208302874205921122935334449334942657295536075214506868195979917314395792274

353168956274124986211114596913065463429612455215420383072827555777122991700187967008591109257601820645413373

921927977000310981480265384701404949044705674957052534439113216316015300413232895718188959262368760601426187

Sommario: scopo di questo articolo è quello di descrivere la realizzazione della CHIAVE PRIVATA

nell’algoritmo RSA a chiave pubblica con l’utilizzo delle congruenze lineari. In effetti l’uso delle congruenze

lineari viene impiegato non solo nel suddetto algoritmo ma anche in diversi altri metodi crittografici, come ad

esempio nell’algoritmo DSA e nell’algoritmo di El Gamal per la generazione e la verifica della firma

Si inizierà pertanto con l’ illustrare un algoritmo per la risoluzione della congruenza lineare

digitale. ⋅ − ⋅ =

Ax ≡ C (mod B) o dell’equazione lineare diofantea dove A, B e C sono numeri

A x B y C

interi qualsiasi positivi o negativi. Come caso particolare si prenderà in considerazione la

congruenza del tipo Ax≡1 (mod B) per il calcolo della Chiave Privata. Dopo una breve premessa

viene descritto lo sviluppo di un numero razionale in frazione continua arrivando al calcolo del MCD

di due numeri. Si passa quindi ad introdurre l’algoritmo riguardante la risoluzione di questo tipo di

equazioni o congruenze attraverso i seguenti passi: calcolo delle ridotte; condizioni di risolvibilità

⋅ − ⋅ = ±

A x B y 1 e quindi delle equazione più generale

dell’equazione; risoluzione delle equazione

.

⋅ − ⋅ =

A x B y C Viene data poi una concisa panoramica dell’impiego negli algoritmi crittografi citati di

questo tipo di congruenza, illustrando poi in dettaglio una sua applicazione riguardante il calcolo della Chiave

Privata nell’algoritmo RSA .Per avere dei risultati concreti si sono realizzati due programma in linguaggio

Qbasic.Il primo (Allegato 1) riguarda sia soluzioni della congruenza lineare generica con valori numerici di A,

5

10 sia il calcolo della chiave privata nell’algoritmo RSA

B e C qualsiasi, ma ciascuno in valore assoluto <

5

10

sempre con valori numerici < per ogni primo impiegato, in quanto ci si limita nei calcoli di questo

programma all’uso della doppia precisione. I risultati ottenibili per la generazione della chiave privata sono

quindi da ritenersi di significato unicamente dimostrativo..

Il secondo programma (Allegato 2), è dedicato espressamente per l’RSA al calcolo di chiavi private , costituite

anche da centinaia di cifre decimali. Con l’impiego pertanto di quest’ultimo programma, in cui si utilizza una

aritmetica a precisione multipla, si possono ottenere valori di Chiavi Private riguardanti un loro effettivo e reale

impiego nel campo della Crittografia.

Abstract: the aim of this paper is to illustrate the PRIVATE KEY implementation in the RSA public key

cryptographic method by using linear congruence. Indeed their employment is used not only in the

aforesaid algorithm, but also in other important cryptographic systems, such as the DSA and the

ElGamal, regarding the Digital Signature generation and verification. So we start explaining an algorithm

⋅ − ⋅ =

A x B y C

for solution of the linear congruence Ax ≡ C (mod B) or linear diophantine equation

where A, B, C are whole positive or negative numbers. After a concise introduction we explain the continued

fraction expansion of rational number, attaining the GCD of two number. Then we illustrate the algorithm for

the solution of the linear congruences by the next steps: the convergents computation; the equation resolvability

⋅ − ⋅ ⋅ − ⋅ =

A x B y A x B y C

conditions; the = ± 1 and solutions.

We give also a short survey of the linear congruences employed in the mentioned cryptographic methods and

then we explain the particular computation regarding the private key of the RSA algorithm. We have implemented

two programs in Qbasic language. 5

10

The former (Allegato 1) considers either the linear congruences solution with A, B, C, each < or the private

5

10

key computation in the RSA algorithm with every prime numerical value < . The private key values in this

case are only demonstrative values.

The second program (Allegato 2) considers expressly the private keys computation, composed by several tens or

some hundreds of digit. .So this program permits, by using a multiple – precision arithmetic, the achievement of

numeric value for private keys , that can be of actual utilization in the cryptographic field.

1

1. Premessa

Per illustrare la realizzazione della chiave privata nell’algoritmo RSA risulta necessario illustrare innanzitutto

⋅ − ⋅ =

A x B y C A, B C

dove e

un algoritmo dedicato alla risoluzione delle equazioni lineari diofantee

sono numeri interi qualsiasi positivi o negativi.

Risolvere queste equazioni significa trovare per le incognite x e y dei valori numerici interi che la soddisfano.

Ma perché la risoluzione di questo tipo di equazione può interessare il campo della crittografia?

Basterà per ora accennare che in diversi importanti algoritmi crittografici a chiave pubblica quali l’algoritmo

⋅ − ⋅ =

A x B y 1 o

RSA e l’algoritmo DSA (Digital Signature Algorithm) si deve risolvere l’equazione

l’equivalente congruenza lineare Ax ≡ 1 (mod B) con A e B interi positivi per il calcolo di alcune grandezze o

parametri riguardanti sia la generazione della chiave privata nell’algoritmo RSA, sia la generazione e la

verifica della Firma Digitale nell’algoritmo DSA. Si rimanda nel seguito a maggiori dettagli sull’ impiego

dell’equazione in questo campo. Sotto il titolo è riportato un esempio di valore numerico di chiave privata

relativo all’algoritmo RSA, valore che può considerarsi di effettivo e reale utilizzo. ⋅ − ⋅ =

A x B y C

Questa nota inizierà illustrando la risoluzione delle equazioni lineari diofantee .

2. Sviluppo di un numero razionale in frazione continua

⋅ − ⋅ =

A x B y C

Per poter risolvere l’equazione lineare in questione occorre venire a conoscenza di alcuni

argomenti essenziali riguardanti lo sviluppo di un numero razionale in frazione continua, che sono qui di seguito

illustrati.

Per i vari tipi di notazioni e simboli utilizzati come pure per la validità delle formule e delle relazioni impiegate

si fa riferimento a [Old]. A A B B

con e interi e ≠ 0

Ogni numero razionale è una frazione della forma B

Si dimostra [Old] che ogni frazione, cioè ogni numero razionale lo si può esprimere nella forma

seguente: 1

A +

= a (1)

1 1

B +

a 2 1

+

a 2 1

+

a 3 + ..........

..........

..........

..........

........

a 4 1

+ 1

+

a −

1

n a n

a a

a a

con un numero limitato di termini ( da a ) dove il termine può essere sia un intero positivo che

i n

1 1

a

negativo o nullo e gli altri valori sono degli interi positivi.

i

a

I vari si ricavano eseguendo le seguenti divisioni successive:

i r

A + 1 a r

a

= con e rispettivamente quoziente e resto della divisione di A per B

1 1

1

B B r < B

e quindi 0 < 1

r

B = + 2

a r r r r

con resto della divisione di B per e quindi 0 < <

2 2 1 2 1

r

r

1 1

r

r = + 3

1 r r

r r r

a con resto della divisione di per e quindi 0 < <

3 1 2 3 2

3

r r

2 2

………………………………………………………………………………

2

r r

= +

− −

n 3 n 1 r r r r r

a con resto della divisione di per e quindi 0 < <

− − − − − −

n 1 n 1 n 3 n 2 n 1 n 2

r r

− −

n 2 n 2

r 0 =

= + =

−

n 2 r 0

a a con

n n n

r r

− −

n n

1 1

r r r

r r

, , ,……. , sono di valore decrescente e costituiscono una successione finita di

I resti −

n n

1 2 3 1 r

termini il cui ultimo termine è sempre di valore 0 [Old] .

n a

Sarà pertanto finita anche la successione dei termini che prendono il nome di quozienti parziali.

i

La formula (1) si pone per convenzione sotto la seguente forma più pratica e concisa :

A a a a a a a

, , , .......... ..... ,

= [ ] (1b)

−

n n

1 2 3 4 1

B

Facciamo un semplice esempio. A 1327

=

Sia da sviluppare in frazione continua il numero razionale B 271 a r

ed i seguenti valori:

Eseguendo le divisioni successive come si è sopra indicato si ottengono per i diversi i i

= =

a r

4 243

1 1

= =

a r

1 28

2 2

= =

a r

8 19

3 3

= =

a r

1 9

4 4

= =

a r

2 1

5 5

= =

a r

9 0

6 6

A 1327

pertanto si ha: = = [ 4, 1, 8, 1, 2, 9 ] (1c)

B 271 271

Se si volesse invece sviluppare in frazione continua è facile vedere che si ha:

1327

271 = [0, 4, 1, 8, 1, 2, 9] che si differenzia dalla(1c) per un quoziente parziale in più: il primo quoziente che

1327

risulta di valore 0.

Questo procedimento delle divisioni successive sopra illustrato viene notoriamente utilizzato con efficacia per il

calcolo del Massimo Comun Divisore di due numeri A e B che sarà indicato nel seguito nella seguente maniera:

(A,B). E’ questo infatti il ben noto algoritmo Euclideo (Euclidean algorithm) per il calcolo del Massimo Comun

Divisore fra due numeri.

In effetti considerati due numeri interi A e B si può dimostrare [Old ] che il più piccolo resto non nullo della

r

r r

successione , , ,…….. è il loro (A,B).

1 2 3

Equazioni e Congruenze lineari

3.

3.1 Calcolo delle ridotte A c

Tenendo presente lo sviluppo di consideriamo ora la seguente successione di grandezze che prendono il

i

B

nome di ridotte:

c1 = [a1]; c2= [a1,a2]; c3=[a1,a2,a3]; c4=[a1,a2,a3,a4];……………………………

A

……………cn-1=[a1,a2,a3,a4………….an-1]; cn = [a1,a2,a3,a4,…..an-1, an] = B

Esplicitando i due primi termini si ha:

p

= =

1

c a p a q

= dove si è posto e = 1

1 1 1 1 1

q

1 3

⋅ + p

a a 1

1 = = ⋅ + =

= + 1 2 2 1

p a a q a

c a = avendo posto e

2 1 2 2 2

2 1 q

a

a 2 2

2

Per la successiva ridotta dopo opportuni passaggi e manipolazioni si perviene alle seguente espressione

⋅ ⋅ + + ⋅ ⋅ + + ⋅ +

a a a a a a (

a a 1

) a a p p p

1 = ⋅ + = ⋅ +

= + 1 2 3 1 3 3 1 2 1 3 2 1 3 p a p p q a q q

c a = = = = con e

3 3 2 1 3 3 2 1

3 1 ⋅ + ⋅ + ⋅ +

1 a a 1 a a 1 a q q q

+

a 2 3 3 2 3 2 1 3

2 a

3 c

c

analogamente per e dopo opportuni passaggi e manipolazioni, si potrà pervenire anche qui

4 5

rispettivamente ai seguenti risultati:

⋅ +

a p p p ⋅ + ⋅ +

4 3 2 4 a p p a q q

c p q

= = avendo posto = e =

4 4 4 3 2 4 4 3 2

⋅ +

a q q q

4 3 2 4

⋅ +

a p p p = ⋅ + = ⋅ +

5 4 3 5 p a p p q a q q

= avendo posto e

c5 = 5 5 4 3 5 5 4 3

⋅ +

a q q q

5 4 3 5

e così via per tutti le altre ridotte sino a quella in corrispondenza della quale il valore del resto risulta di valore

=

r 0

nullo ( ):

n ⋅ −

a p p p

A − −

= = ⋅ − = ⋅ −

n n 1 n 2 n

c p a p p q a q q

= = con A = e B = (2)

− − − −

n n n n n n n n n

1 2 1 2

⋅ −

a q q q

B − − n

n n 1 n 2

In generale si dimostra per induzione [Old] che:

p q c a , a , a , a ,.........

...

a , a

i numeratori e delle ridotte relative alla frazione continua [ ]

−

i i i n n

1 2 3 4 1

soddisfano le uguaglianze:

= ⋅ +

p a p p (5)

− −

i i i 1 i 2

= ⋅ +

q a q q (6)

− −

i i i 1 i 2

per i = 3, 4, 5,………n = = = ⋅ + =

p a q p a a q a

1

e con i valori iniziali ; 1; ; (7)

1 1 1 2 2 1 2 2

Da quanto illustrato si vede pertanto che si può impostare un algoritmo di tipo iterativo, ad esempio con il loop

riportato nel riquadro, una volta posti N = A; D = B e le condizioni iniziali

:

= = = ⋅ + =

p a q p a a q a

1

i = 2; ; 1; ;

1 1 1 2 2 1 2 2

Inizio loop : i = i + 1

 

N : = − ⋅

r N a D

=

a   i i

i D

 

= ⋅ +

p a p p

− −

i i i i

1 2

= ⋅ +

q a q q

− −

i i i i

1 2

r

se = 0 esci dal loop

i N = D

=

D r

i

= =

p p p p

:

− − −

i i i i

2 1 1

= =

q q q q

:

− − −

i i i i

2 1 1

torna a inizio loop

r

n = i: REM = 0

n

fine r

M.C.D.(A,B) = −

n 1 r

p q

Algoritmo per il calcolo dei valori e fino alla iterazione i = n in corrispondenza della quale si ha resto = 0

n

i i 4

⋅ − ⋅ =

A x B y C

Risoluzione della equazione (3a)

4 -

4.1 Condizioni di risolvibilità

Si vogliono trovare per x e y i valori interi soddisfacenti la suddetta equazione.

⋅ = ⋅ +

A x y B C

L’equazione può essere scritta così: mettendo con ciò in evidenza che y e C rappresentano

⋅

A x

rispettivamente il quoziente ed il resto della divisione di per B.

Tale equazione si può esprimere anche come congruenza assumendo in tal caso la seguente forma:

⋅

A x ≡ C (mod B) (3b)

⋅

A x

e si enuncia dicendo che è congruo a C modulo B.

Quando si trattano congruenze il valore del modulo B è da considerarsi di valore positivo.

−

⋅ 1

A

C (mod B);

Questa espressione può essere anche messa sotto la seguente forma: x =

− 1

A

per C = 1 si ha x = (mod B); in questo caso x viene chiamato inverso moltiplicativo di A.

⋅ ⋅

A x A x

– C ≡ 0 (mod B): si dice allora che – C è congruo a

Portando C nel primo membro di (3b) si ha

0 modulo B.

La prima cosa da appurare è vedere se la (3a) o la (3b) ammettono soluzioni.

L’equazione e quindi la corrispondente congruenza sono risolvibili solo se sussiste la seguente condizione[Old ]:

C è divisibile per (A,B)

Questa condizione equivale ad una qualsiasi di queste due condizioni:

A e B sono primi tra loro.

A e B non sono primi tra loro, ma un loro divisore comune è anche divisore di C.

⋅ − ⋅ =

A x B y 1

4.2 Risoluzione della equazione (4)

⋅ − ⋅ = 1

A x B y

Rivolgiamo ora l’attenzione all’equazione dove A e B possono essere degli interi sia positivi

che negativi.

Innanzitutto perché l’equazione sia risolvibile tenendo presenti le condizioni dette sopra, occorre che

A e B siano primi tra loro e che quindi sia (A,B ) = 1 per A e B dello stesso segno e (A,B) = −1 per

A e B di segno opposto. p q

Per i valori generici di e di si dimostra sempre per induzione (vedi [Old]) che sussiste la seguente

i i

⋅ − ⋅ = − i

p q p q ( 1

)

relazione : − −

1 1

i i i i

Applicando l’algoritmo iterativo che è esposto nel riquadro, si esce dal ciclo alla iterazione per cui si ha resto

r p q

= 0; in quest’ultima iterazione che chiameremo iterazione n-esima si sono acquisiti i valori di , ,

− −

i n n

1 1

⋅ − ⋅ n

p q p q p q (−

1

)

e per cui vale la relazione = .

− −

n n n n n n

1 1

p q

Ma dalla (2) si osserva che A = e B = , per cui si perviene alla seguente relazione:

n n

⋅ − ⋅ ⋅ − ⋅ n

p q p q A q B p (−

1

)

= = (5)

− − − −

n n n n n n

1 1 1 1

⋅ − ⋅

A q B p

Se n è pari si ottiene = 1. Si può allora vedere immediatamente dal confronto con la (4) che

− −

n n

1 1

q p

i valori e sono i valori interi rispettivamente di x e di y che soddisfano l’equazione. Tuttavia, per

− −

n n

1 1

tenere conto che A e B possono essere sia positivi che negativi e quindi anche di segno opposto, gli effettivi

q p

= =

n− n−

1 1

x y

valori soddisfacenti l’equazione sono dati dalle seguenti formule : e con (A,B) = 1

0 0

( A

, B ) ( A

, B )

se A e B sono dello stesso segno e (A,B) = −1 se A e B sono di segno opposto.

+ ⋅

x B k

Si può mostrare [Old] poi che anche valori di x del tipo e i corrispondenti valori di y del tipo

0

+ ⋅

y A k dove k è un intero positivo o negativo qualsiasi soddisfano anch’essi l’equazione (4). Pertanto tutti

0

gli infiniti valori r