Consideriamo il funzionamento di un asimmetrico RSA . È stato proposto da tre matematici Ronald Rivest ( R. Rivest), Adi Shamir ( A. Shamir) e Leonard Adleman ( L. Adlemann) nel 1978.

Sotto numero primo Comprenderemo un numero divisibile solo per 1 e per se stesso. Euclide nei suoi Elementi dimostrò che per ogni numero primo esiste un numero primo maggiore, cioè il numero dei numeri primi è infinito.

Prova. Supponiamo che esista un numero primo più grande P, definiamo il prodotto di tutti i numeri primi P=2∙3∙5∙7∙…∙P.

Considera il numero P+1. O esso stesso è un numero primo grande P ovvero il prodotto dei numeri primi maggiori P. Siamo arrivati ​​ad una contraddizione, il che significa che il numero dei numeri primi è infinito.

2∙3+1=7; 2∙3∙5+1=31; 2∙3∙5∙7+1=211;

2∙3∙5∙7∙11+1=2311; 2∙3∙5∙7∙11∙13+1=30031=59∙509.

Numeri reciprocamente primi nomineremo i numeri che non hanno un solo divisore comune tranne 1 .

Infine, sotto il risultato dell'operazione ho mod j calcoleremo il resto di una divisione intera io SU J. Per utilizzare l'algoritmo RSA, devi prima generare una chiave pubblica e privata seguendo questi passaggi.

1. Scegli due numeri primi molto grandi R E Q.

2. Definiamo N come risultato della moltiplicazione R SU q (n=p·q).

3. Scegliamo un numero casuale grande, che chiameremo D. Questo numero deve essere coprimo rispetto al risultato della moltiplicazione (p – 1) · (q – 1).

4. Definiamo tale numero e, per cui vale la seguente relazione (ed) mod ((p – 1) (q – 1)) = 1.

5. Chiamiamo i numeri della chiave pubblica e E N e la chiave segreta sono i numeri D E N.

Ora, per crittografare i dati utilizzando una chiave nota ( e, n), è necessario effettuare le seguenti operazioni:

– dividere il testo crittografato in blocchi, ognuno dei quali può essere rappresentato come un numero Mi);

– crittografare il testo considerato come una sequenza di numeri Mi) secondo la formula С(i) = (M(i) e) mod n. Per decrittografare questi dati utilizzando la chiave segreta (d, n),è necessario eseguire i seguenti calcoli: M(i)=(C(i)d) mod n. Il risultato saranno tanti numeri Mi), che rappresentano il testo di partenza.

Algoritmo RSA si basa su uno dei teoremi dimostrati di Eulero, un caso speciale del quale afferma che se un numero N rappresentabili come due numeri primi P E Q, quindi per qualsiasi X c'è uguaglianza

x(p-1)(q-1) mod n = 1.

Per decrittografare i messaggi RSA utilizzeremo questa formula. Per fare ciò eleviamo entrambe le sue parti a una potenza (- sì):

(x (- y)(p-1)(q-1)) mod n= 1 (- y) = 1.

Ora moltiplichiamo entrambi i lati per x:

(x (-y)(p-1)(q-1)+1) mod n = 1· x = x.

Ricordiamo ora come sono state create le chiavi pubblica e privata. Abbiamo scelto D tale che

e d+(p-1)(q-1) y = 1,

e·d = (-y)(p-1)(q-1)+1.

Pertanto nell'ultima espressione del paragrafo precedente possiamo sostituire l'esponente con un numero (ndr). Noi abbiamo (x e d) mod n = x. Per leggere il messaggio c i = ((mi) e)mod nè sufficiente elevarlo a potenza D modulo M:

((c i) d)mod n = ((m i) e · d) mod n = m i .

Ecco un semplice esempio di utilizzo del metodo RSA per crittografare un messaggio "CAB". Per semplicità utilizzeremo numeri molto piccoli (in pratica si usano numeri grandi).

1. Scegliamo p= 3i q= 11.

2. Definiamo n= 3· 11=33.

3. Troviamo (p–1) (q–1)= 20. Come D scegli un numero qualsiasi che sia coprimo con 20, ad esempio d= 3.

4. Scegli un numero e. Qualsiasi numero per il quale la relazione è soddisfatta può essere preso come tale (e· 3)mod 20 = 1,
ad esempio 7.

5. Immagina il messaggio crittografato come una sequenza di numeri interi nell'intervallo 0...32. Lasciamo la lettera UN rappresentato dal numero 1, lettera IN– il numero 2 e la lettera CON– il numero 3. Quindi il messaggio può essere rappresentato come una sequenza di numeri 312. Criptiamo il messaggio utilizzando la chiave (7, 33):

С(1)=(З 7) mod 33 = 2187 mod 33 = 9,

С(2) = (1 7) mod 33 = 1 mod 33 = 1,

C(Z) = (2 7) mod 33 = 128 mod 33 = 29.

6. Proviamo a decifrare il messaggio (9, 1, 29), ottenuto come risultato della crittografia utilizzando una chiave nota, basata sulla chiave segreta (3, 33):

M(1) = (9 3) mod 33 = 729 mod 33 = 3,

M(2) = (1 3) mod 33 = 1 mod 33 = 1,

M(Z) = (29 3) mod 33 = 24389 mod 33 = 2.

Pertanto, come risultato della decrittografia del messaggio, è stato ricevuto il messaggio originale "CAB".

La forza crittografica dell'algoritmo RSA si basa sul presupposto che sia estremamente difficile determinare la chiave segreta da una chiave pubblica nota, poiché ciò richiede la risoluzione del problema dell'esistenza di divisori interi. Questo problema non consente attualmente una soluzione efficace (polinomiale). A questo proposito, per chiavi composte da 200 cifre binarie (e questi sono i numeri che si consiglia di utilizzare), i metodi tradizionali per trovare i divisori richiedono l'esecuzione di un numero enorme di operazioni (circa 10 23).

Il sistema crittografico RSA viene utilizzato in un'ampia varietà di piattaforme e settori. È integrato in molti prodotti commerciali, il cui numero è in costante crescita. È utilizzato dai sistemi operativi Microsoft, Apple, Sun e Novell. Nell'hardware, l'algoritmo RSA viene utilizzato nei telefoni sicuri, sulle schede di rete Ethernet, sulle smart card ed è ampiamente utilizzato nelle apparecchiature crittografiche di Zaxus (Rasal). Inoltre, l'algoritmo è incluso in tutti i principali protocolli per le comunicazioni Internet sicure, inclusi S/MIME, SSL e S/WAN, ed è utilizzato anche in molte istituzioni, come agenzie governative, gran parte delle aziende, laboratori governativi e università.

La tecnologia di crittografia RSA BSAFE è utilizzata da oltre 500 milioni di utenti in tutto il mondo. Poiché nella maggior parte dei casi viene utilizzato l’algoritmo RSA, può essere considerato il sistema crittografico a chiave pubblica più comune al mondo e questo numero ha una chiara tendenza ad aumentare con la crescita degli utenti di Internet.

Algoritmo di crittografia a chiave pubblica RSA fu uno dei primi proposti alla fine degli anni '70 del XX secolo. Il suo nome è composto dalle prime lettere dei cognomi degli autori: R. Rivest, A. Shamir e L. Adleman. L'algoritmo RSA è probabilmente il più popolare e ampiamente utilizzato algoritmo asimmetrico nei sistemi crittografici.

L'algoritmo si basa sul fatto che il problema di scomporre un gran numero in fattori primi è difficile. Il sistema crittografico RSA si basa sui seguenti due fatti della teoria dei numeri:

1. il compito di verificare la primalità di un numero è relativamente facile;
2. il problema della scomposizione dei numeri della forma n = pq (p e q sono numeri primi); la fattorizzazione è molto difficile se sappiamo solo che n, p e q sono numeri grandi (questo è il cosiddetto problema della fattorizzazione, per maggiori dettagli vedere "Fondamenti di teoria dei numeri utilizzati nella crittografia a chiave pubblica").

L'algoritmo RSA è un algoritmo di crittografia a blocchi in cui i dati crittografati e non crittografati devono essere rappresentati come numeri interi compresi tra 0 e n -1 per alcuni n.

Crittografia

Quindi, diamo un'occhiata all'algoritmo stesso. Supponiamo che l'utente A voglia inviare un messaggio crittografato all'utente B. In questo caso, l'utente B deve preparare una coppia (chiave pubblica; chiave privata) e inviare la sua chiave pubblica all'utente A.

Il primo passo è generare chiavi pubbliche e private. Per fare ciò, seleziona prima due numeri primi grandi P e Q. Quindi si calcola il prodotto N:

Successivamente, viene determinato il numero ausiliario f:

f = (P - l)(Q - 1).

Quindi il numero d viene selezionato casualmente< f и взаимно простое с f .

I numeri d e N saranno la chiave pubblica dell'utente e il valore e sarà la chiave privata.

Quindi a questo punto l’utente dovrebbe avere le informazioni elencate nella tabella seguente:

Poiché l'utente B desidera ricevere un messaggio crittografato dall'utente A, l'utente B deve inviare la sua chiave pubblica (d, N) all'utente A. I numeri P e Q non sono più necessari, ma non possono essere condivisi con nessuno; È meglio dimenticarli del tutto.

A questo punto, la fase di preparazione della chiave è completata ed è possibile utilizzare il protocollo RSA principale per crittografare i dati.

Seconda fase: crittografia dei dati. Se l'utente A vuole inviare dei dati all'utente B, deve rappresentare il suo messaggio in forma digitale e suddividerlo in blocchi m 1, m 2, m 3, ..., dove m i< N . Il messaggio crittografato sarà composto da blocchi con i .

L'abbonato A crittografa ogni blocco del suo messaggio utilizzando la formula

c io = m i d mod N

utilizzando parametri pubblici utente B e invia il messaggio crittografato C=(c 1, c 2, c 3, ...) su una linea aperta.

L'abbonato B, che ha ricevuto un messaggio crittografato, decrittografa tutti i blocchi del messaggio ricevuto utilizzando la formula

Tutti i blocchi decrittografati saranno esattamente uguali a quelli provenienti dall'utente A.

Un utente malintenzionato che intercetta tutti i messaggi e conosce tutte le informazioni pubbliche non sarà in grado di trovare il messaggio originale per grandi valori di P e Q.

Esempio di calcoli di algoritmi

Consenti all'utente A di inviare un messaggio all'utente B. In questo caso, l'utente B deve prima preparare le chiavi pubblica e privata. Lascia che selezionino, ad esempio, i seguenti parametri:

P = 3, Q = 11, N = 3x11 = 33.

Poi f = (P - l)(Q - 1) = (3-1)(11-1) = 20.

Successivamente l'utente B sceglie un qualsiasi numero d che non ha divisori comuni con f (questo è necessario affinché il messaggio crittografato possa poi essere recuperato in modo univoco). Sia d = 13. Questo numero sarà uno dei componenti della chiave pubblica.

Nella seconda parte esamineremo il popolare algoritmo RSA, in cui per la crittografia viene utilizzata una chiave pubblica. Ma prima voglio avvisarti di nuovo. Il codice presentato in questo articolo è solo a scopo didattico. La crittografia è un campo molto ampio e complesso e, per evitare qualsiasi problema, non consiglio di crittografare le informazioni utilizzando il mio hack.

Nella seconda parte esamineremo il popolare algoritmo RSA, in cui per la crittografia viene utilizzata una chiave pubblica. Ma prima voglio avvisarti di nuovo. Il codice presentato in questo articolo è solo a scopo didattico. La crittografia è un campo molto ampio e complesso e, per evitare qualsiasi problema, non consiglio di crittografare le informazioni utilizzando il mio hack.

Algoritmo RSA

Crittografia utilizzando una chiave pubblica

La crittografia a chiave pubblica viene utilizzata ovunque. Se almeno una volta hai pagato qualcosa online, hai già utilizzato questo metodo (spero!). Sorge subito la domanda su come funziona questa protezione. Se inserisco il numero della mia carta di credito per acquistare qualcosa, perché nessuno tranne il destinatario può vedere queste informazioni? Lasciate che vi dia una metafora. Per aprire una cassaforte ci vuole una chiave (o un martello, ma per fortuna casseforti e serrature sono resistenti a questo tipo di persone). Nella crittografia a chiave pubblica accade più o meno la stessa cosa. Mostri la serratura affinché tutti possano vederla, ma solo pochi eletti hanno la chiave di questa serratura ed è quasi impossibile aprire la porta usando altri metodi.

RSA è uno degli algoritmi che implementa lo schema sopra. Inoltre, possiamo utilizzare questo algoritmo per verificare l'autenticità della nostra identità. Se invii un messaggio crittografato a qualcuno utilizzando una chiave privata, il destinatario può decrittografare il tuo messaggio utilizzando la chiave pubblica. Questa tecnologia consente di firmare i messaggi, confermando così l'autenticità del mittente.

Programma demo basato sull'algoritmo RSA

Non tutti gli utenti di apparecchiature informatiche personali sanno e comprendono cos'è la crittografia RSA e sono sorpresi quando sentono questo termine. Ma non c'è nulla di complicato nascosto in questo concetto. La crittografia RSA è solo un sistema crittografico che consente di utilizzare in modo sicuro tutti i dati elettronici creati sulla tecnologia informatica. Non si tratta di decrittografia dei dati, in cui i file non possono essere letti senza conoscere un determinato codice. La crittografia RSA implica che le chiavi siano aperte.

La crittografia RSA funziona secondo il principio del factoring. Come questo? E questo è il factoring
riproduzione di due grandi dati numerici.

Chi ha creato il sistema di crittografia RSA?

L'algoritmo di crittografia RSA è stato creato nel 1977, i suoi creatori sono gli scienziati Rivest, Shamir, Adleman, un'abbreviazione delle lettere iniziali dei loro cognomi costituisce il termine RSA. Un algoritmo precedente è stato sviluppato da Clifford Cox, un matematico inglese che ha lavorato per i servizi di intelligence del paese. Nel 1973 riuscì a creare un sistema equivalente, ma fu utilizzato esclusivamente da individui classificati e la tecnica non fu distribuita al livello degli utenti ordinari di apparecchiature informatiche personali.

Come funziona la crittografia RSA?

L'utente del sistema prima crea e poi pubblica una chiave pubblica, che si basa su due grandi numeri, solo con un valore ausiliario. I numeri più semplici vengono tenuti segreti. Per leggere, ad esempio, un'e-mail è sufficiente utilizzare la chiave pubblica del documento, ma se la chiave è lunga allora diventa difficile accedere alle informazioni.

Oggi la crittografia RSA è caratterizzata come un metodo poco affidabile di crittografia dei dati. Questo è un algoritmo lento, quindi non è così comune tra gli utenti comuni di computer. Allora perché allora è stato creato questo sistema se i comuni scienziati informatici praticamente non lo usano?

Il fatto è che ha trovato la sua applicazione nella trasmissione crittografata di chiavi pubbliche per una chiave di crittografia simmetrica, progettata per la crittografia e la decrittografia di massa ad alta velocità.

Il moderno sistema crittografico a chiave asimmetrica è emerso grazie al lavoro di Diffie e Hellman. Svilupparono il concetto nel 1976 e lo presentarono al pubblico come registrazioni digitali. Sono stati in grado di creare una chiave pubblica basata sul principio di esponenziare un certo numero modulo un numero primo. Ma il loro principio rimase sospeso nell'aria, poiché a quel tempo i principi stessi del factoring non erano ancora stati ben studiati.

Rivest, Adim Shamir, Adleman non si sono fermati a ciò che avevano ottenuto in precedenza e hanno elaborato a fondo il meccanismo di una funzione unidirezionale, che non è così facile da decodificare. Rivest e Shamir hanno lavorato direttamente sulle funzioni stesse e Adleman ha cercato i punti deboli negli algoritmi creati. Alla fine, sono riusciti a creare il sistema a chiave asimmetrica RSA.

Firma digitale e comunicazione a chiave pubblica

Attualmente molte aziende utilizzano un elemento elettronico come firma digitale nelle loro attività lavorative. I documenti elettronici creati contenenti la cosiddetta firma digitale sono documenti ufficiali riconosciuti a livello legale. Una firma digitale elettronica viene creata quando i dati vengono modificati crittograficamente.

Questa alternativa alla firma convenzionale consente di rendere riservato un documento, garantirne l'integrità e avere sempre informazioni sul suo creatore e proprietario.

La firma elettronica è strettamente correlata alla crittografia RSA in questione. Questo sistema, come accennato in precedenza, presuppone la presenza di una chiave pubblica. Oggi vengono utilizzate in pratica due chiavi: pubblica - nota a tutti e privata - crittografata per impedire l'accesso alle informazioni a persone non autorizzate.

Pertanto, la chiave pubblica consente di accedere a un documento con sigillo elettronico e la chiave privata consente di decrittografare la firma e verificarla. In altre parole, la crittografia RSA consente di nascondere i documenti da occhi indiscreti, mantenendoli segreti, ma con la possibilità di accedervi al momento giusto.

Scopriamo qual è l'essenza dell'algoritmo inventato?

La crittografia RSA funziona in quattro fasi:
generazione di chiavi;
distribuzione delle chiavi;
crittografia a chiave;
decrittazione delle chiavi.

Il principio della crittografia RSA combina la creazione di chiavi pubbliche e private. Soffermiamoci di nuovo su questo. Aperto – noto a tutti, può essere utilizzato per crittografare i messaggi. Questi dati elettronici possono essere decrittografati utilizzando una chiave privata. Quando si creano chiavi pubbliche, i numeri vengono scelti in modo casuale e hanno le stesse dimensioni, ma diversi nella durata del record, quindi la fattorizzazione è più difficile.

I numeri identici vengono trovati testando la loro semplicità. Pertanto, la crittografia è diventata gradualmente più complessa. In cosa consiste una chiave pubblica? Ed è composto da un modulo regolare e da un cosiddetto esponente pubblico. Ma quello chiuso include un modulo e un indicatore privato, che non viene fornito a nessuno tranne al creatore.

Debolezze della tecnica di crittografia RSA

Nonostante il principio di crittografia ben congegnato, può essere facilmente violato. Questo può essere fatto se per creare le chiavi vengono utilizzati piccoli numeri; la chiave può essere rivelata mediante una semplice selezione di semplici numeri interi.

La stessa crittografia RSA è un algoritmo che elimina componenti casuali, il che rende più facile per i truffatori della rete di computer rompere il meccanismo deterministico confrontandolo con il testo in chiaro degli attacchi Dos, che controllano se i testi in esecuzione sono costantemente uguali in lunghezza alle chiavi generate.

E questo, innanzitutto, spiega che la crittografia RSA non è lo stesso crittosistema sicuro sotto tutti gli aspetti per preservare i dati elettronici dagli attacchi di persone indesiderate. A meno che non acquisisca tali proprietà quando viene aggiunto a server più avanzati.

Componenti aggiuntivi che garantiscono la sicurezza dell'utilizzo della crittografia RSA

Per prevenire la possibilità di hackerare la crittografia del formato RSA, i programmatori vi incorporano una forma di riempimento strutturato, cosiddetto randomizzato, che viene eseguito prima dell'effettiva crittografia delle informazioni elettroniche. Questo punto garantisce che il contenuto dei documenti elettronici non venga presentato a tutti e che le informazioni riservate non possano essere visualizzate quando ai documenti viene applicato un meccanismo di selezione casuale delle chiavi.

La crittografia RSA scompone i numeri matematici in fattori, ma il meccanismo non è mai stato perfezionato. Pertanto, al momento, gli aggressori hanno ancora la possibilità e molte scappatoie per selezionare i metodi per violare la crittografia dei dati. E riescono a farlo proprio attraverso il meccanismo di ripristino dei fattori primi.

I truffatori calcolano l'indicatore segreto contenuto nella chiave pubblica e decrittografano la documentazione utilizzando un metodo standard. Quindi il campo d’azione per chi vuole davvero danneggiare un’azienda è decisamente ampio. Diciamo solo che il problema della sicurezza della crittografia RSA rimane ancora rilevante e aperto, anche se poche persone ne parlano pubblicamente.

Processo automatizzato di crittografia dei dati elettronici

Nonostante il basso livello di sicurezza, la crittografia RSA in questione è applicabile in molti settori. È particolarmente gradito quando c'è un'ampia circolazione di documentazione elettronica. Diciamo solo che la crittografia RSA viene utilizzata per proteggere i documenti con un livello medio di responsabilità.

Il software Yafu consente di crittografare automaticamente i dati elettronici. Questo programma consente di trovare rapidamente i dati per la creazione di chiavi asimmetriche, osservando le regole dell'affidabilità del factoring. È compatibile con processori come SIQS, ECM, SNFS. Viene avviato tramite la riga di comando. L'immissione di questo comando in una riga consente di ridurre di più volte il tempo necessario per la ricerca dei dati per la creazione delle chiavi.

L'utente medio di apparecchiature informatiche personali non può far fronte a questo software. La sua installazione e configurazione richiede determinate conoscenze e spesso vengono eseguite da programmatori e specialisti IT.

La crittografia RSA è seriamente vulnerabile, e questo nonostante il fatto che per creare chiavi pubbliche e private vengano utilizzati grandi numeri, pari a diverse migliaia di bit sui dischi.

Benjamin Moody ha dimostrato nel 2009 che il processo di cracking delle chiavi pubbliche e private è possibile. Sebbene ciò possa richiedere due o più anni, resta il fatto che molti dei sistemi informatici del mondo potrebbero essere a rischio di essere hackerati.

Ad esempio, questo specialista non aveva bisogno di nulla di speciale per vagliare gli script chiave: il computer di un utente normale e il software GGNFS. Anche la pratica di chiavi di crittografia di diversi millesimi di bit non protegge le informazioni dal lasciare il campo riservato e inaccessibile ad altri utenti.

Naturalmente, violare la crittografia RSA richiede tempo. Molti hacker impiegano anni per ottenere un risultato positivo. Si tratta spesso di prospettive ben remunerate che alimentano l’interesse nel continuare a cercare la chiave giusta. Nella maggior parte dei casi, l'hacking di chiavi lunghe viene abbandonato alla ricerca di prospettive più semplici. Ma questo non significa che nessuno stia cercando di creare un meccanismo di cracking delle chiavi più semplificato.

La principale protezione contro gli attacchi intrusivi da parte dei truffatori è la creazione di chiavi grandi e lunghe di oltre duemila bit. Sono già noti casi di hacking di chiavi di lunghezza compresa tra cento e cinquecento bit. Quindi devi tenere le orecchie affilate. Se esiste un meccanismo per decifrare le chiavi brevi, probabilmente il lavoro è in pieno svolgimento da qualche parte dalla parte dei malvagi per decifrare le combinazioni più lunghe di crittografia dei dati elettronici.

Conclusione

Sulla base di quanto sopra, la crittografia RSA è un metodo sicuro per mantenere la riservatezza dei dati elettronici, a condizione che vengano create chiavi lunghe e ricche di informazioni.

È difficile selezionarli manualmente, quindi viene utilizzato il prodotto software automatizzato Yafu. Viene installato e configurato da specialisti IT. Farlo da soli potrebbe danneggiare il sistema operativo del tuo computer.
Questo software è progettato per funzionare in tandem con i processori per computer multi-core di moderna generazione.

Gli obiettivi principali degli attacchi fraudolenti sono le grandi aziende industriali e finanziarie, quindi senza la crittografia RSA la gestione dei documenti elettronici non funziona. Anche la firma elettronica dei documenti è soggetta a crittografia e ad essa si applicano gli stessi standard di sicurezza degli altri dati informativi. Il principio – quanto più grande è la chiave, tanto più difficile sarà hackerare il documento – dovrebbe essere applicabile assolutamente a tutti i dati che non sono destinati all'uso pubblico.

A seconda della struttura delle chiavi utilizzate, i metodi di crittografia si dividono in:

• simmetrico: gli estranei possono conoscere l'algoritmo di crittografia, ma una piccola parte delle informazioni segrete è sconosciuta: la chiave, che è la stessa per il mittente e il destinatario del messaggio; Esempi: DES, 3DES, AES, Blowfish, Twofish, GOST 28147-89
• crittografia asimmetrica: gli estranei possono conoscere l'algoritmo di crittografia, ed eventualmente la chiave pubblica, ma non la chiave privata, nota solo al destinatario. I sistemi crittografici a chiave pubblica sono attualmente ampiamente utilizzati in vari protocolli di rete, in particolare nei protocolli TLS e nel suo predecessore SSL (sottostante HTTPS), nonché SSH, PGP, S/MIME, ecc. Standard russo, utilizzando la crittografia asimmetrica - .

Al momento, la crittografia asimmetrica a chiave pubblica RSA (sta per Rivest, Shamir e Aldeman, i creatori dell'algoritmo) viene utilizzata dalla maggior parte dei prodotti nel mercato della sicurezza delle informazioni.

La sua forza crittografica si basa sulla difficoltà di fattorizzare grandi numeri, vale a dire sull'eccezionale difficoltà del compito di determinare una chiave segreta basata su una chiave pubblica, poiché ciò richiederebbe la risoluzione del problema dell'esistenza dei divisori di un numero intero. I sistemi più sicuri utilizzano numeri a 1024 bit e superiori.

Diamo un'occhiata all'algoritmo RSA da un punto di vista pratico.

Per prima cosa devi generare le chiavi pubblica e privata:

• Prendiamo due grandi numeri primi p e q.
• Definiamo n come il risultato della moltiplicazione di p su q (n= p*q).
• Scegliamo un numero casuale, che chiameremo d. Questo numero deve essere relativamente primo (non avere divisore comune diverso da 1) con il risultato della moltiplicazione (p-1)*(q-1).
• Definiamo un numero e per il quale è vera la seguente relazione (e*d) mod ((p-1)*(q-1))=1.
• Chiamiamo la chiave pubblica con i numeri e e n, e la chiave segreta con i numeri d e n.

Per crittografare i dati utilizzando una chiave pubblica (e,n), è necessario quanto segue:

• dividere il testo crittografato in blocchi, ciascuno dei quali può essere rappresentato come un numero M(i)=0,1,2..., n-1 (cioè solo fino a n-1).
• crittografare il testo, considerato come una sequenza di numeri M(i) utilizzando la formula C(i)=(M(I)^e)mod n.

Per decriptare questi dati utilizzando la chiave segreta (d,n), è necessario eseguire i seguenti calcoli: M(i) = (C(i)^d) mod n. Di conseguenza, si otterrà un insieme di numeri M(i), che rappresentano il testo originale.

L'esempio seguente dimostra chiaramente l'algoritmo di crittografia RSA:

Crittifichiamo e decodifichiamo il messaggio "CAB" utilizzando l'algoritmo RSA. Per semplicità, prendiamo piccoli numeri: questo accorcerà i nostri calcoli.

• Scegliamo p=3 e q=11.
• Definiamo n= 3*11=33.
• Troviamo (p-1)*(q-1)=20. Pertanto d sarà uguale, ad esempio, a 3: (d=3).
• Scegliamo il numero e utilizzando la seguente formula: (e*3) mod 20=1. Ciò significa che e sarà uguale, ad esempio, a 7: (e=7).
• Immaginiamo il messaggio criptato come una sequenza di numeri compresa tra 0 e 32 (ricordiamo che termina con n-1). Lettera A = 1, B = 2, C = 3.

Ora crittifichiamo il messaggio utilizzando la chiave pubblica (7.33)

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Ora decodifichiamo i dati utilizzando la chiave privata (3.33).

M1=(9^3) mod 33 =729 mod 33 = 3(C);
M2=(1^3) mod 33 =1 mod 33 = 1(A);
M3=(29^3) mod 33 = 24389 mod 33 = 2(B);

Dati decifrati!