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 digitale.

Si inizierà pertanto con l’illustrare un algoritmo per la risoluzione della congruenza lineare Ax ≡ C (mod B) o dell’equazione lineare diofantea Ax − By = C dove A, B e C sono numeri 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à dell’equazione Ax − By = ±1 e quindi delle equazione più generale Ax − By = C; risoluzione delle equazione.

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, B e C qualsiasi, ma ciascuno in valore assoluto < 10⁵ sia il calcolo della chiave privata nell’algoritmo RSA sempre con valori numerici < 10⁵ 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 for solution of the linear congruence Ax ≡ C (mod B) or linear diophantine equation Ax − By = C 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 conditions; the Ax − By = ±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. The former (Allegato 1) considers either the linear congruences solution with A, B, C, each < 10⁵ or the private key computation in the RSA algorithm with every prime numerical value < 10⁵.

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. Premessa

Per illustrare la realizzazione della chiave privata nell’algoritmo RSA risulta necessario illustrare innanzitutto un algoritmo dedicato alla risoluzione delle equazioni lineari diofantee Ax − By = C dove A, B e C 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 RSA e l’algoritmo DSA (Digital Signature Algorithm) si deve risolvere l’equazione Ax − By = 1 o 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.

Questa nota inizierà illustrando la risoluzione delle equazioni lineari diofantee Ax − By = C.

2. Sviluppo di un numero razionale in frazione continua

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].

Ogni numero razionale è una frazione della forma A/B con A e B interi e B ≠ 0.

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

A/B = a₁ + 1/(a₂ + 1/(a₃ + .......... + 1/(a_n−1 + 1/a_n))) (1)

con un numero limitato di termini (da a₁ ad a_n) dove il termine a₁ può essere sia un intero positivo che negativo o nullo e gli altri valori sono degli interi positivi.

I vari a_i si ricavano eseguendo le seguenti divisioni successive:

A = a₁B + r₁ con a₁ e r₁ rispettivamente quoziente e resto della divisione di A per B e quindi 0 ≤ r₁ < B.

B = a₂r₁ + r₂ con r₂ resto della divisione di B per r₁ e quindi 0 < r₂ < r₁.

r₁ = a₃r₂ + r₃ con r₃ resto della divisione di r₁ per r₂ e quindi 0 < r₃ < r₂.

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

r_n−3 = a_n−1r_n−2 + r_n−1 con resto della divisione di r_n−3 per r_n−2 e quindi 0 < r_n−1 < r_n−2.

r_n−2 = a_nr_n−1 + r_n con r_n = 0.

I resti r₁, r₂, r₃, ……, r_n−1 sono di valore decrescente e costituiscono una successione finita di termini il cui ultimo termine è sempre di valore 0 [Old].

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

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

A/B = [a₁, a₂, a₃, a₄, .........., a_n−1, a_n] (1b)

Esempio

Facciamo un semplice esempio. Sia da sviluppare in frazione continua il numero razionale A/B = 1327/271 ed i seguenti valori:

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

a₁ = 4, r₁ = 243

a₂ = 1, r₂ = 28

a₃ = 8, r₃ = 19

a₄ = 1, r₄ = 9

a₅ = 2, r₅ = 1

a₆ = 9, r₆ = 0

pertanto si ha: A/B = 1327/271 = [4, 1, 8, 1, 2, 9] (1c).

Se si volesse invece sviluppare in frazione continua 1327/271 = [0, 4, 1, 8, 1, 2, 9] che si differenzia dalla (1c) per un quoziente parziale in più: il primo quoziente che 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).

È 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 successione r₁, r₂, r₃, …….. è il loro (A,B).

3. Equazioni e congruenze lineari

3.1 Calcolo delle ridotte

Tenendo presente lo sviluppo di A/B consideriamo ora la seguente successione di grandezze che prendono il nome di ridotte:

c₁ = [a₁]; c₂ = [a₁,a₂]; c₃ = [a₁,a₂,a₃]; c₄ = [a₁,a₂,a₃,a₄];……………………………

…………… c_n−1 = [a₁,a₂,a₃,a₄………….a_n−1]; c_n = [a₁,a₂,a₃,a₄,…..a_n−1, a_n] = A/B.

Esplicitando i due primi termini si ha:

c₁ = a₁ = p₁/q₁ dove si è posto p₁ = a₁ e q₁ = 1.

c₂ = a₁ + 1/a₂ = (a₁a₂ + 1)/a₂ = p₂/q₂ avendo posto p₂ = a₂p₁ + p₀ e q₂ = a₂q₁ + q₀.

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

c₃ = a₁ + 1/(a₂ + 1/a₃) = (a₃p₂ + p₁)/(a₃q₂ + q₁) = p₃/q₃ con p₃ = a₃p₂ + p₁ e q₃ = a₃q₂ + q₁.

Analogamente per c₄ e c₅, dopo opportuni passaggi e manipolazioni, si potrà pervenire anche qui rispettivamente ai seguenti risultati:

c₄ = p₄/q₄ avendo posto p₄ = a₄p₃ + p₂ e q₄ = a₄q₃ + q₂.

c₅ = p₅/q₅ avendo posto p₅ = a₅p₄ + p₃ e q₅ = a₅q₄ + q₃.

E così via per tutti le altre ridotte sino a quella in corrispondenza della quale il valore del resto risulta di valore nullo (r_n = 0):

c_n = p_n/q_n = (a_np_n−1 + p_n−2)/(a_nq_n−1 + q_n−2) = A/B (2).

In generale si dimostra per induzione [Old] che i numeratori p_i e q_i delle ridotte relative alla frazione continua [a₁, a₂, a₃, a₄,........., a_n−1, a_n] soddisfano le uguaglianze:

p_i = a_ip_i−1 + p_i−2 (5)

q_i = a_iq_i−1 + q_i−2 (6)

per i = 3, 4, 5,………n con i valori iniziali p₁ = a₁; q₁ = 1; p₂ = a₂a₁ + 1; q₂ = a₂ (7).

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:

i = 2; p₁ = a₁; q₁ = 1; p₂ = a₁a₂ + 1; q₂ = a₂.

Inizio loop: i = i + 1

r = N − a_iD

a_i = [N/D]

p_i = a_ip_i−1 + p_i−2

q_i = a_iq_i−1 + q_i−2

Se r_i = 0 esci dal loop.

N = D

D = r_i

p_i−2 = p_i−1

p_i−1 = p_i

q_i−2 = q_i−1

q_i−1 = q_i

Torna a inizio loop.

i = n: REM = 0

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

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

4. Risoluzione della equazione Ax − By = C

4.1 Condizioni di risolvibilità

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

L’equazione può essere scritta così: Ax = By + C, mettendo con ciò in evidenza che y e C rappresentano rispettivamente il quoziente ed il resto della divisione di Ax per B.

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

Ax ≡ C (mod B) (3b)

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

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

Questa espressione può essere anche messa sotto la seguente forma: x = A⁻¹C (mod B).

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

Portando C nel primo membro di (3b) si ha Ax − C ≡ 0 (mod B): si dice allora che Ax − C è congruo a 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.

4.2 Risoluzione della equazione Ax − By = 1

Rivolgiamo ora l’attenzione all’equazione Ax − By = 1 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.

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

p_iq_i−1 − p_i−1q_i = (−1)ⁱ.

Applicando l’algoritmo iterativo che è esposto nel riquadro, si esce dal ciclo alla iterazione per cui si ha resto r_i = 0; in quest’ultima iterazione che chiameremo iterazione n-esima si sono acquisiti i valori di p_n−1, q_n−1, p_n, q_n e per cui vale la relazione p_nq_n−1 − p_n−1q_n = (−1)ⁿ.

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

p_nq_n−1 − q_np_n−1 = A q_n−1 − B p_n−1 = (−1)ⁿ (5).

Se n è pari si ottiene A q_n−1 − B p_n−1 = 1. Si può allora vedere immediatamente dal confronto con la (4) che i valori q_n−1 e p_n−1 sono i valori interi rispettivamente di x e di y che soddisfano l’equazione.

Tuttavia, per tenere conto che A e B possono essere sia positivi che negativi e quindi anche di segno opposto, gli effettivi valori soddisfacenti l’equazione sono dati dalle seguenti formule: x = q_n−1/(A,B) e y = p_n−1/(A,B) con (A,B) = 1 se A e B sono dello stesso segno e (A,B) = −1 se A e B sono di segno opposto.

Si può mostrare [Old] poi che anche valori di x del tipo x₀ + B ⋅ k e i corrispondenti valori di y del tipo y₀ + A ⋅ k dove k è un intero positivo o negativo qualsiasi soddisfano anch’essi l’equazione (4).