Crittografia a chiave pubblica

A differenza della crittografia a chiave simmetrica, non troviamo un uso storico della crittografia a chiave pubblica. È un concetto relativamente nuovo.

La crittografia simmetrica era adatta per organizzazioni come governi, militari e grandi società finanziarie coinvolte nella comunicazione riservata.

Con la diffusione di reti di computer più insicure negli ultimi decenni, si è sentita una reale necessità di utilizzare la crittografia su scala più ampia. La chiave simmetrica è risultata non pratica a causa delle sfide che ha dovuto affrontare per la gestione delle chiavi. Ciò ha dato origine ai crittosistemi a chiave pubblica.

Il processo di crittografia e decrittografia è illustrato nella figura seguente:

Le proprietà più importanti dello schema di crittografia a chiave pubblica sono:

Per la crittografia e la decrittografia vengono utilizzate chiavi diverse. Questa è una proprietà che imposta questo schema in modo diverso dallo schema di crittografia simmetrica.
Ogni destinatario possiede una chiave di decrittazione univoca, generalmente denominata chiave privata.
Il destinatario deve pubblicare una chiave di crittografia, denominata chiave pubblica.
In questo schema è necessaria una certa garanzia dell'autenticità di una chiave pubblica per evitare lo spoofing da parte dell'avversario come destinatario. In generale, questo tipo di sistema crittografico coinvolge una terza parte fidata che certifica che una particolare chiave pubblica appartiene solo a una persona o entità specifica.
L'algoritmo di crittografia è abbastanza complesso da impedire a un utente malintenzionato di dedurre il testo in chiaro dal testo cifrato e dalla chiave di crittografia (pubblica).
Sebbene le chiavi private e pubbliche siano correlate matematicamente, non è possibile calcolare la chiave privata dalla chiave pubblica. In effetti, una parte intelligente di qualsiasi sistema crittografico a chiave pubblica sta nel progettare una relazione tra due chiavi.

Esistono tre tipi di schemi di crittografia a chiave pubblica. Ne discuteremo nelle sezioni seguenti:

RSA Cryptosystem

Questo sistema crittografico è uno dei sistemi iniziali. Rimane il sistema crittografico più utilizzato anche oggi. Il sistema è stato inventato da tre studiosiRon Rivest, Adi Shamir, e Len Adleman e quindi, è definito come sistema crittografico RSA.

Vedremo due aspetti del sistema crittografico RSA, in primo luogo la generazione della coppia di chiavi e in secondo luogo gli algoritmi di crittografia-decrittografia.

Generazione della coppia di chiavi RSA

Ogni persona o parte che desidera partecipare alla comunicazione utilizzando la crittografia deve generare una coppia di chiavi, ovvero chiave pubblica e chiave privata. Il processo seguito nella generazione delle chiavi è descritto di seguito:

Generate the RSA modulus (n)
- Seleziona due numeri primi grandi, p e q.
- Calcola n = p * q. Per una crittografia forte e indistruttibile, lascia che n sia un numero elevato, in genere un minimo di 512 bit.
Find Derived Number (e)
- Numero e deve essere maggiore di 1 e minore di (p - 1) (q - 1).
- Non deve esserci alcun fattore comune per e e (p - 1) (q - 1) eccetto 1. In altre parole due numeri e e (p - 1) (q - 1) sono coprimi.
Form the public key
- La coppia di numeri (n, e) forma la chiave pubblica RSA e viene resa pubblica.
- È interessante notare che, sebbene n faccia parte della chiave pubblica, la difficoltà di fattorizzare un numero primo grande assicura che l'attaccante non possa trovare in tempo finito i due numeri primi (p & q) usati per ottenere n. Questa è la forza di RSA.
Generate the private key
- La chiave privata d viene calcolata da p, q ed e. Per n ed e, c'è un numero univoco d.
- Il numero d è l'inverso di e modulo (p - 1) (q - 1). Ciò significa che d è il numero minore di (p - 1) (q - 1) tale che, moltiplicato per e, è uguale a 1 modulo (p - 1) (q - 1).
- Questa relazione è scritta matematicamente come segue:

ed = 1 mod (p − 1)(q − 1)

L'algoritmo euclideo esteso accetta p, q ed e come input e fornisce d come output.

Esempio

Di seguito viene fornito un esempio di generazione di una coppia di chiavi RSA. (Per facilità di comprensione, i numeri primi p & q presi qui sono valori piccoli. In pratica, questi valori sono molto alti).

Siano due numeri primi p = 7 eq = 13. Quindi, modulo n = pq = 7 x 13 = 91.
Seleziona e = 5, che è una scelta valida poiché non esiste un numero che sia un fattore comune di 5 e (p - 1) (q - 1) = 6 × 12 = 72, tranne 1.
La coppia di numeri (n, e) = (91, 5) costituisce la chiave pubblica e può essere resa disponibile a chiunque desideriamo possa inviarci messaggi crittografati.
Immettere p = 7, q = 13 ed e = 5 nell'algoritmo euclideo esteso. L'output sarà d = 29.
Verificare che la d calcolata sia corretta calcolando -

de = 29 × 5 = 145 = 1 mod 72

Quindi, la chiave pubblica è (91, 5) e le chiavi private è (91, 29).

Crittografia e decrittografia

Una volta generata la coppia di chiavi, il processo di crittografia e decrittografia è relativamente semplice e computazionalmente facile.

È interessante notare che RSA non opera direttamente su stringhe di bit come nel caso della crittografia a chiave simmetrica. Opera sui numeri modulo n. Quindi, è necessario rappresentare il testo in chiaro come una serie di numeri inferiori a n.

Crittografia RSA

Supponiamo che il mittente desideri inviare un messaggio di testo a qualcuno la cui chiave pubblica è (n, e).
Il mittente rappresenta quindi il testo in chiaro come una serie di numeri inferiori a n.
Per crittografare il primo testo in chiaro P, che è un numero modulo n. Il processo di crittografia è un semplice passaggio matematico in quanto:

C = P^e mod n

In altre parole, il testo cifrato C è uguale al testo in chiaro P moltiplicato per se stesso e volte e poi ridotto modulo n. Ciò significa che C è anche un numero inferiore a n.
Ritornando al nostro esempio di Key Generation con testo in chiaro P = 10, otteniamo testo cifrato C -

C = 10⁵ mod 91

Decrittografia RSA

Anche il processo di decrittografia per RSA è molto semplice. Supponiamo che il destinatario della coppia di chiavi pubbliche (n, e) abbia ricevuto un testo cifrato C.
Il destinatario eleva C al potere della sua chiave privata d. Il risultato modulo n sarà il testo in chiaro P.

Plaintext = C^d mod n

Tornando di nuovo al nostro esempio numerico, il testo cifrato C = 82 verrebbe decriptato al numero 10 usando la chiave privata 29 -

Plaintext = 82²⁹ mod 91 = 10

Analisi RSA

La sicurezza di RSA dipende dai punti di forza di due funzioni separate. Il crittosistema RSA è il più popolare sistema di crittografia a chiave pubblica di cui si basa sulla difficoltà pratica di fattorizzare i numeri molto grandi.

Encryption Function - È considerata una funzione unidirezionale per convertire il testo in chiaro in testo cifrato e può essere invertita solo con la conoscenza della chiave privata d.
Key Generation- La difficoltà di determinare una chiave privata da una chiave pubblica RSA equivale a fattorizzare il modulo n. Un utente malintenzionato quindi non può utilizzare la conoscenza di una chiave pubblica RSA per determinare una chiave privata RSA a meno che non possa fattorizzare n. È anche una funzione unidirezionale, passare dai valori p & q al modulo n è facile ma non è possibile invertire.

Se una di queste due funzioni viene dimostrata non unidirezionale, la RSA verrà interrotta. Infatti, se una tecnica per il factoring viene sviluppata in modo efficiente, la RSA non sarà più sicura.

La forza della crittografia RSA diminuisce drasticamente contro gli attacchi se il numero peq non sono numeri primi grandi e / o la chiave pubblica scelta e è un numero piccolo.

ElGamal Cryptosystem

Insieme a RSA, vengono proposti altri sistemi crittografici a chiave pubblica. Molti di loro sono basati su diverse versioni del problema del logaritmo discreto.

Il sistema crittografico ElGamal, chiamato Variante della curva ellittica, si basa sul problema del logaritmo discreto. Deriva la forza dall'assunzione che i logaritmi discreti non possono essere trovati in un intervallo di tempo pratico per un dato numero, mentre l'operazione inversa della potenza può essere calcolata in modo efficiente.

Vediamo una semplice versione di ElGamal che funziona con i numeri modulo p. Nel caso delle varianti della curva ellittica, si basa su sistemi numerici abbastanza diversi.

Generazione della coppia di chiavi ElGamal

Ogni utente del sistema crittografico ElGamal genera la coppia di chiavi come segue:

Choosing a large prime p. Generalmente viene scelto un numero primo di lunghezza compresa tra 1024 e 2048 bit.
Choosing a generator element g.
- Questo numero deve essere compreso tra 1 ep - 1, ma non può essere un numero qualsiasi.
- È un generatore del gruppo moltiplicativo di numeri interi modulo p. Ciò significa che per ogni intero m co-primo in p, esiste un intero k tale che g ^k = a mod n.
  
  Ad esempio, 3 è il generatore del gruppo 5 (Z ₅ = {1, 2, 3, 4}).

N	3 ⁿ	3 ⁿ mod 5
1	3	3
2	9	4
3	27	2
4	81	1

Choosing the private key. La chiave privata x è un numero qualsiasi maggiore di 1 e minore di p − 1.
Computing part of the public key. Il valore y viene calcolato dai parametri p, ge la chiave privata x come segue:

y = g^x mod p

Obtaining Public key. La chiave pubblica ElGamal è composta dai tre parametri (p, g, y).

Ad esempio, supponiamo che p = 17 e che g = 6 (Si può confermare che 6 è un generatore del gruppo Z ₁₇ ). La chiave privata x può essere qualsiasi numero maggiore di 1 e minore di 71, quindi scegliamo x = 5. Il valore y viene quindi calcolato come segue:

y = 6⁵ mod 17 = 7

Quindi la chiave privata è 62 e la chiave pubblica è (17, 6, 7).

Crittografia e decrittografia

La generazione di una coppia di chiavi ElGamal è relativamente più semplice del processo equivalente per RSA. Ma la crittografia e la decrittografia sono leggermente più complesse di RSA.

Crittografia ElGamal

Supponiamo che il mittente desideri inviare un testo in chiaro a qualcuno la cui chiave pubblica ElGamal è (p, g, y), quindi -

Il mittente rappresenta il testo in chiaro come una serie di numeri modulo p.
Per crittografare il primo testo in chiaro P, che è rappresentato come un numero modulo p. Il processo di crittografia per ottenere il testo cifrato C è il seguente:
- Genera casualmente un numero k;
- Calcola due valori C1 e C2, dove -

C1 = g^k mod p
C2 = (P^*y^k) mod p

Invia il testo cifrato C, costituito da due valori separati (C1, C2), inviato insieme.
Facendo riferimento al nostro esempio di generazione di chiavi ElGamal fornito sopra, il testo in chiaro P = 13 è crittografato come segue:
- Genera casualmente un numero, diciamo k = 10
- Calcola i due valori C1 e C2, dove -

C1 = 6¹⁰ mod 17
C2 = (13^*7¹⁰) mod 17 = 9

Invia il testo cifrato C = (C1, C2) = (15, 9).

Decrittografia ElGamal

Per decrittografare il testo cifrato (C1, C2) utilizzando la chiave privata x, vengono eseguiti i due passaggi seguenti:
- Calcola l'inverso modulare di (C1) ^x modulo p, che è (C1) ^-x , generalmente indicato come fattore di decrittografia.
- Ottieni il testo in chiaro utilizzando la seguente formula:

C2 × (C1)^-x mod p = Plaintext

Nel nostro esempio, per decrittografare il testo cifrato C = (C1, C2) = (15, 9) utilizzando la chiave privata x = 5, il fattore di decrittografia è

15^-5 mod 17 = 9

Estrai testo in chiaro P = (9 × 9) mod 17 = 13.

Analisi ElGamal

Nel sistema ElGamal, ogni utente ha una chiave privata x. e hathree components di chiave pubblica - prime modulus p, generator g, and public Y = g^x mod p. La forza dell'ElGamal si basa sulla difficoltà del problema del logaritmo discreto.

La dimensione della chiave sicura è generalmente> 1024 bit. Oggi vengono utilizzati anche 2048 bit di chiave lunga. Sul fronte della velocità di elaborazione, Elgamal è piuttosto lento, viene utilizzato principalmente per i protocolli di autenticazione delle chiavi. A causa della maggiore efficienza di elaborazione, le varianti Elliptic Curve di ElGamal stanno diventando sempre più popolari.

Crittografia a curva ellittica (ECC)

Elliptic Curve Cryptography (ECC) è un termine usato per descrivere una suite di strumenti e protocolli crittografici la cui sicurezza si basa su versioni speciali del problema del logaritmo discreto. Non utilizza numeri modulo p.

ECC si basa su insiemi di numeri associati a oggetti matematici chiamati curve ellittiche. Esistono regole per sommare e calcolare multipli di questi numeri, proprio come per i numeri modulo p.

ECC include una variante di molti schemi crittografici inizialmente progettati per numeri modulari come la crittografia ElGamal e l'algoritmo di firma digitale.

Si ritiene che il problema del logaritmo discreto sia molto più difficile se applicato a punti su una curva ellittica. Ciò richiede il passaggio dai numeri modulo p ai punti su una curva ellittica. Anche un livello di sicurezza equivalente può essere ottenuto con chiavi più brevi se utilizziamo varianti basate su curve ellittiche.

I tasti più corti comportano due vantaggi:

Facilità di gestione delle chiavi
Calcolo efficiente

Questi vantaggi rendono le varianti dello schema di crittografia basate sulla curva ellittica molto interessanti per le applicazioni in cui le risorse di elaborazione sono limitate.

Schemi RSA ed ElGamal: un confronto

Confrontiamo brevemente gli schemi RSA ed ElGamal sui vari aspetti.

RSA	ElGamal
È più efficiente per la crittografia.	È più efficiente per la decrittografia.
È meno efficiente per la decrittazione.	È più efficiente per la decrittografia.
Per un particolare livello di sicurezza, in RSA sono richieste chiavi lunghe.	Per lo stesso livello di sicurezza, sono necessarie chiavi molto brevi.
È ampiamente accettato e utilizzato.	È nuovo e non molto popolare nel mercato.