RSA, è davvero così semplice? Selezione dei parametri di cifratura RSA e possibili conseguenze Crittografia utilizzando l'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 attuale e aperto, anche se pochi 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 lunghe da cento a 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 – più grande è la chiave, più difficile sarà hackerare il documento – dovrebbe essere applicabile assolutamente a tutti i dati che non sono destinati all'uso pubblico.

La crittografia RSA è uno dei primi sistemi crittografici pratici a chiave pubblica ed è ampiamente utilizzata per la trasmissione sicura dei dati. La differenza principale rispetto a servizi simili è che la chiave di crittografia è pubblica e si differenzia dalla chiave di decrittografia, che viene mantenuta segreta. La tecnologia RSA si basa sulla difficoltà pratica di fattorizzare due grandi numeri primi (il problema della fattorizzazione).

Storia della creazione

Il nome RSA è composto dalle lettere iniziali dei cognomi di Rivest, Shamir e Adleman, gli scienziati che per primi li descrissero pubblicamente nel 1977. Clifford Cox, un matematico inglese che lavorò per i servizi segreti britannici, sviluppò per primo un sistema equivalente nel 1973, ma non fu declassificato fino al 1997.

L'utente RSA crea e quindi pubblica una chiave pubblica basata su due grandi numeri primi insieme a un valore ausiliario. deve essere tenuto segreto. Chiunque può utilizzare una chiave pubblica per crittografare un messaggio, ma se è abbastanza grande, solo qualcuno con conoscenza dei numeri primi può decodificare il messaggio. È noto che violare la crittografia RSA rappresenta un grosso problema: oggi è in corso un dibattito aperto su quanto sia sicuro il meccanismo.

RSA è un algoritmo relativamente lento, motivo per cui non è ampiamente utilizzato dall'utente diretto. L'uso più comune di questo metodo è trasmettere chiavi condivise crittografate per una chiave di crittografia simmetrica, che a sua volta può eseguire operazioni di crittografia e decrittografia in blocco a velocità molto più elevate.

Quando è apparso il crittosistema nella sua forma moderna?

L'idea di un sistema crittografico a chiave asimmetrica è attribuita a Diffie e Hellman, che pubblicarono il concetto nel 1976, introducendo le firme digitali e tentando di applicare la teoria dei numeri. La loro formulazione utilizza una chiave segreta condivisa creata dall'esponente di un numero modulo un numero primo. Tuttavia, lasciarono aperto il problema dell'implementazione di questa funzione, poiché all'epoca i principi del factoring non erano ben compresi.

Rivest, Adi Shamir e Adleman del MIT hanno fatto diversi tentativi nel corso di un anno per creare una funzione unidirezionale difficile da decodificare. Rivest e Shamir (come scienziati informatici) hanno proposto molte potenziali funzioni, mentre Adleman (come matematico) ha cercato i punti deboli dell'algoritmo. Adottarono molti approcci e alla fine svilupparono il sistema finale nell'aprile 1977, oggi noto come RSA.

Firma digitale e chiave pubblica

Una firma digitale elettronica, o EDS, è parte integrante dei documenti elettronici. È formato da un certo cambiamento crittografico nei dati. Utilizzando questo attributo è possibile verificare l'integrità di un documento, la sua riservatezza e anche determinare chi è il suo proprietario. Si tratta essenzialmente di un'alternativa alla solita firma standard.

Questo sistema crittografico (crittografia RSA) offre una chiave pubblica, diversa da quelle simmetriche. Il principio del suo funzionamento è che vengono utilizzate due chiavi diverse: privata (crittografata) e pubblica. Il primo serve per generare una firma elettronica e successivamente poterne decriptare il testo. Il secondo riguarda l'effettiva crittografia e verifica della firma digitale.

L'uso della firma ci permette di comprendere meglio la crittografia RSA, un esempio del quale può essere dato da un normale documento classificato “chiuso a occhi indiscreti”.

Qual è l'essenza dell'algoritmo?

L'algoritmo RSA è composto da quattro fasi: generazione della chiave, distribuzione della chiave, crittografia e decrittografia. Come già affermato, la crittografia RSA comprende una chiave pubblica e una chiave privata. Open può essere conosciuto da tutti e viene utilizzato per crittografare i messaggi. La sua essenza è che i messaggi crittografati utilizzando la chiave pubblica possono essere decrittografati solo entro un certo periodo di tempo utilizzando la chiave privata.

Per essere sicuri, i numeri interi dovrebbero essere selezionati casualmente ed avere le stesse dimensioni, ma variare in lunghezza di alcune cifre per rendere più difficile la fattorizzazione. I numeri identici possono essere trovati efficacemente utilizzando un test per la loro primalità, quindi la crittografia delle informazioni deve necessariamente diventare più complicata.

Una chiave pubblica è costituita da un modulo e da un esponente pubblico. Private è composto da un modulo e da un indicatore privato che deve essere mantenuto segreto.

Crittografia dei file RSA e punti deboli

Tuttavia, esistono numerosi meccanismi per violare il semplice RSA. Quando si crittografa con velocità basse e numeri piccoli, la cifra può essere facilmente decifrata se si trova la radice del testo cifrato sui numeri interi.

Poiché la crittografia RSA è un algoritmo deterministico (ovvero non ha componenti casuali), un utente malintenzionato può lanciare con successo un attacco di testo in chiaro scelto contro un sistema crittografico crittografando testi in chiaro plausibili con la chiave pubblica e controllando se sono uguali al testo cifrato. Un sistema crittografico si dice semanticamente sicuro se un aggressore non riesce a distinguere due crittografie l'una dall'altra, anche se conosce i testi corrispondenti in forma chiara. Come descritto sopra, RSA, senza integrarlo con altri servizi, non è semanticamente sicuro.

Algoritmi aggiuntivi di crittografia e sicurezza

Per evitare i problemi di cui sopra, le implementazioni pratiche di RSA in genere prevedono una qualche forma di riempimento strutturato e randomizzato prima della crittografia. Ciò garantisce che il contenuto non rientri nell'ambito del testo in chiaro non sicuro e che il messaggio non possa essere compromesso accidentalmente.

La sicurezza del sistema crittografico RSA e la crittografia delle informazioni si basano su due problemi matematici: il problema della fattorizzazione di grandi numeri e il problema RSA stesso. La completa divulgazione del testo cifrato e della firma digitale in RSA è considerata inaccettabile sul presupposto che entrambi questi problemi non possano essere risolti insieme.

Tuttavia, grazie alla capacità di recuperare i fattori primi, un utente malintenzionato può calcolare l'esponente segreto dalla chiave pubblica e poi decrittografare il testo utilizzando una procedura standard. Sebbene oggi non sia stato trovato alcun metodo per fattorizzare grandi numeri su un computer classico, non è stato dimostrato che non esista.

Automazione

Uno strumento chiamato Yafu può essere utilizzato per semplificare questo processo. L'automazione in YAFU è una funzionalità all'avanguardia che combina algoritmi di fattorizzazione in una metodologia intelligente e adattiva che riduce al minimo il tempo necessario per trovare fattori di numeri di input arbitrari. La maggior parte delle implementazioni dell'algoritmo sono multi-thread, consentendo a Yafu di sfruttare appieno il multi o molti (inclusi SNFS, SIQS ed ECM). Prima di tutto, è uno strumento da riga di comando gestito. Il tempo impiegato per cercare un fattore di crittografia utilizzando Yafu su un normale computer può essere ridotto a 103,1746 secondi. Lo strumento produce una capacità di elaborazione di 320 bit o più. Si tratta di un software molto complesso che richiede una certa competenza tecnica per l'installazione e la configurazione. Pertanto, la crittografia RSA C potrebbe essere vulnerabile.

Tentativi di hacking nei tempi moderni

Nel 2009, Benjamin Moody, utilizzando una chiave RSA-512 bit, ha lavorato per decrittografare il crittotesto per 73 giorni utilizzando solo software comune (GGNFS) e un computer desktop medio (dual-core Athlon64 a 1900 MHz). Come ha dimostrato questa esperienza, per il processo di “vagliatura” sono stati necessari poco meno di 5 gigabyte di disco e circa 2,5 gigabyte di RAM.

Nel 2010, il numero RSA fattorizzato più grande era lungo 768 bit (232 cifre decimali o RSA-768). La sua implementazione è durata due anni su diverse centinaia di computer contemporaneamente.

In pratica, le chiavi RSA sono più lunghe, solitamente da 1024 a 4096 bit. Alcuni esperti ritengono che le chiavi a 1024 bit potrebbero diventare insicure nel prossimo futuro o addirittura essere già violate da un utente malintenzionato ragionevolmente ben finanziato. Tuttavia, pochi sostengono che nel prossimo futuro potranno essere rivelate anche chiavi a 4096 bit.

Prospettive

Pertanto, si presume generalmente che RSA sia sicuro se i numeri sono sufficientemente grandi. Se il numero di base è pari o inferiore a 300 bit, il testo cifrato e la firma digitale possono essere scomposti in poche ore su un personal computer utilizzando un software già disponibile gratuitamente. È stato dimostrato che le chiavi a 512 bit sono decifrabili già nel 1999 utilizzando diverse centinaia di computer. Al giorno d'oggi, ciò è possibile entro poche settimane utilizzando l'hardware disponibile pubblicamente. Pertanto, è del tutto possibile che in futuro la crittografia RSA venga facilmente violata con le dita e il sistema diventi irrimediabilmente obsoleto.

Ufficialmente, nel 2003, la sicurezza delle chiavi a 1024 bit venne messa in discussione. Attualmente si consiglia una lunghezza minima di 2048 bit.

Sotto il taglio sono riportati esempi di scelta di parametri di crittografia RSA "errati".

“Va sottolineato che occorre prestare attenzione nella scelta del modulo RSA (num N) per ciascuno dei corrispondenti di rete. A questo proposito si può dire quanto segue. Il lettore può verificarlo autonomamente conoscendo una delle tre quantità P, Q O φ(n), puoi facilmente trovare la chiave privata RSA...".

Aggiungiamo a questo testo. Se la scelta del modulo di cifratura RSA non va a buon fine, come è stato fatto nell'esempio del manuale riportato di seguito, è possibile decriptare il testo senza la presenza di una chiave segreta, ovvero senza conoscere nessuna delle tre quantità nominate.

Per fare ciò è sufficiente avere il testo cifrato specificato dal modulo di cifratura N, chiave pubblica e cifrare ed eseguire solo tre passaggi di un attacco di lettura senza chiave. Dopo la quarta fase di attacco viene accertato che il testo di partenza è stato ottenuto nella fase precedente e può essere letto. Mostriamo quanto è facile da fare.

Per prima cosa diamo l'esempio stesso dalle pp. 313-315 del suddetto manuale.

Esempio

Crittografia breve messaggio di testo iniziale: RSA.
Il destinatario imposta la cifra con le caratteristiche n=pq=527, Dove p=17, q=31 E φ(n)=(ð –1)(q – 1)=480. Come chiave pubblica e viene scelto un numero coprimo rispetto a φ(n), e=7. Gli interi vengono trovati per questo numero utilizzando l'algoritmo euclideo esteso tu E v, soddisfacendo la relazione e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Perché il –137≡343(mod480), Quello d=343.

Visita medica: 7∙343=2401≡1(mod480).

Il messaggio di testo si presenta come una sequenza di numeri contenuti nell'intervallo . Lettere per questo R, S E UN sono codificati come numeri binari a cinque bit. I numeri seriali di queste lettere nell'alfabeto inglese sono usati nella loro rappresentazione binaria:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Poi RSA=(100101001100001) 2. Suddividere il testo in blocchi di lunghezza limitata produce una presentazione a due blocchi: RSA=(100101001), (100001)=(M1 =297, M2 =33).

I blocchi di testo sorgente vengono crittografati in sequenza M1=297, M2=33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Qui abbiamo approfittato del fatto che:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 e ≡33 7 (mod527)=407.

Il testo cifrato, come quello originale, è ottenuto sotto forma di due blocchi: y1 =474; y2 =407.

Decodifica sembra essere una sequenza di azioni D k (y i)=(y i) d =(y i) 343 (mod 527), io=1,2.

Calcoli di esponenziazione Dè più conveniente eseguirlo rappresentando prima l'esponente come la somma delle potenze del numero 2 , vale a dire: 343=256+64+16+4+2+1 .

Utilizzando questa rappresentazione esponenziale d=343, noi abbiamo:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
e infine 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Il valore viene calcolato in modo simile 407 343 (mod527)=33.

Passando alla rappresentazione letterale del messaggio decriptato si ottiene: RSA.

Dopo aver esaminato l'esempio, il manuale discute la robustezza del sistema RSA. Viene sottolineata la necessità di cautela nella scelta del modulo di cifratura RSA (numeri). N) per ciascuno dei corrispondenti di rete. Si indica che è inammissibile ignorare i requisiti per le caratteristiche selezionate del sistema di crittografia. Tra questi requisiti, purtroppo, non è indicata la violazione dei quali è illustrata dall'esempio fornito.

Attacco al cifrario RSA

Consideriamo un esempio di attacco al codice RSA. Usiamo i dati dell'esempio fornito alle pagine 313-315 nel libro di testo "Fundamentals of Cryptography" di A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Ceremushkin, Mosca. "Helios ARV", 2001.

Il fallimento (irricevibilità) dei parametri di sistema selezionati in questo esempio è facilmente dimostrato da calcoli che implementano un attacco alla lettura senza chiave del testo sorgente. L'essenza di un tale attacco è la seguente. Viene specificata la chiave pubblica di cifratura RSA ( e=7, n=527) e testo cifrato. Nell'esempio, il testo cifrato è rappresentato in due blocchi
y=(y1 =474, y2 =407).

Ogni blocco crittografato viene attaccato individualmente, prima attacchiamo y1 =474, dopo averlo decrittografato, attacchiamo un altro blocco y2 =407.

Successivamente, viene formata una sequenza di valori numerici mediante crittografia ripetuta, memorizzando i risultati di due passaggi successivi dell’algoritmo di attacco e utilizzando una chiave pubblica. sì io, y1 =y testo cifrato disponibile.

Nell'algoritmo di attacco del testo cifrato, viene determinato il seguente numero di passaggi: J, per cui y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Dall'ultima relazione vediamo che quando viene elevato a potenza e valori (y i e j–1 (mod n)) si ottiene il testo cifrato iniziale y io = y 1.

Ma ciò significa che in questa fase il testo in chiaro era crittografato. Mediante calcoli diretti (ce ne sono pochissimi) utilizzando una calcolatrice su schermo, troviamo quel valore J, in cui il ciclo di crittografia termina con il valore sì 1, da cui ha avuto inizio il ciclo.

Attacco al primo blocco y1 =474 testo cifrato.
Passo 1: 474 7 (mod527)=382;
Passo 2: 382 7 (mod527)=423;
Passaggio 3: 423 7 (mod527)=297;
Passaggio 4:   in questo passaggio il testo sorgente già trovato viene crittografato, ma è necessario farlo poiché l'aggressore non conosce il testo sorgente. Un segno del completamento dell'attacco è la coincidenza del valore iniziale del testo cifrato ( 474 ) e il risultato del quarto passaggio di crittografia. È proprio questa la coincidenza che avviene.

297 7 (mod527)=474 ha ricevuto il (primo) blocco iniziale di testo cifrato. L'attacco al primo blocco è stato completato con successo y1 =474. Il risultato precedente del passaggio 3 è uguale al testo in chiaro M1=297.

n=527 r=297 modulo n=527. E' scritto così y io = 1 =297. Formare residui di potere
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Attacco al secondo blocco y2 =407 testo cifrato.
Passo 1: 407 7 (mod527)=16;
Passo 2:  16 7 (mod527)=101;
Passaggio 3:  101 7 (mod527)=33;
Passaggio 4:  33 7 (mod527)=407.

Ancora una volta, nella terza fase, è stato ottenuto un blocco di testo sorgente ( M2=33), ma l'attaccante non lo sa ed esegue il successivo (quarto passo), il cui risultato è ( 407 ) corrisponde al testo cifrato iniziale y2 =407.

Essenzialmente nell'anello dei residui modulo n=527è stato implementato un breve ciclo di elaborazione della detrazione r=33 modulo n=527. E' scritto così y io = y 2 = 33.
Formare residui di potere ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Risultato dell'attacco (testo originale M1=297, M2=33) si ottiene crittografando tre volte il testo cifrato specificato. È difficile immaginare un successo più grande per un aggressore di testi cifrati.

Continuando la discussione sulla scelta del modulo e di altri parametri di cifratura, possiamo aggiungere che il modulo di cifratura ( n=527) alcuni testi di origine non possono essere affatto crittografati. In questo caso la scelta del valore della chiave pubblica non gioca un ruolo importante. Esistono valori del testo di origine che generalmente non possono essere crittografati con la cifra selezionata con il modulo n=527.

Nessuno di quelli indicati può crittografare i testi di origine rappresentati da numeri
187 , 341 , 154 E 373 .

Esempio (impossibilità di crittografare i valori di alcuni testi di origine)

Lasciamo che i testi di partenza siano rappresentati da quattro blocchi y=(y1 =154, y2 =187, y3 =341, y4 =373). espositore e la chiave pubblica del cifrario può essere qualsiasi numero coprimo con la funzione di Eulero φ(n)=φ(527)=480. Tuttavia, per il caso in esame, la chiave pubblica e può essere impostato arbitrariamente. Anzi, lasciamo e=2, 4, 7, 9, 17, 111 Poi:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

Dall’esempio considerato segue una semplice conclusione. In effetti, la scelta dei parametri per il processo di crittografia deve essere affrontata con molta attenzione e deve essere effettuata un'analisi preliminare approfondita di tali parametri. Come farlo è una questione separata e non rientra nell'ambito di questo lavoro.

Finalmente è giunto il momento di iniziare a descrivere il crittosistema RSA. Oltre a spiegare come funziona, dobbiamo discutere nel dettaglio della sua sicurezza; in altre parole, perché è così difficile decifrare un messaggio crittografato con il sistema crittografico RSA?

§ 12.1. Circa l'inizio e la fine

Per implementare un sistema di crittografia RSA per utente singolo, è necessario selezionare due diversi numeri primi p e q e calcolarne il prodotto. I numeri primi p e q vengono mantenuti segreti mentre il numero diventa parte della chiave pubblica. Nel § 12.5 discutiamo in dettaglio il metodo per selezionare i numeri primi chiave e come questa scelta si collega all'affidabilità del sistema.

Un messaggio (che può essere considerato un numero intero) viene crittografato elevandolo a una certa potenza modulo Pertanto, prima dobbiamo trovare un modo per rappresentare il testo del messaggio come un elenco di classi modulo. In realtà, non è ancora possibile il processo di crittografia, ma solo preparando il messaggio in modo che possa essere crittografato.

Per semplicità supponiamo che il testo del messaggio contenga solo parole scritte in maiuscolo. Quindi il messaggio è in definitiva una sequenza di lettere e spazi. Il primo passaggio consiste nel sostituire ciascuna lettera del messaggio con un numero selezionato dalla seguente tabella:

(vedi scansione)

Lo spazio tra le parole viene sostituito con il numero 99. Effettuata questa procedura otterremo un numero, possibilmente molto grande se il messaggio era lungo. Tuttavia, questo non è il numero finale a cui miriamo, ma solo un insieme di classi modulo. E ora dobbiamo suddividere la rappresentazione numerica del messaggio in pezzi, ognuno dei quali è un numero naturale che non supera questi pezzi. blocchi di messaggi.

Ad esempio, la rappresentazione numerica del motto “CONOSCI TE STESSO” è simile a questa:

Scegliendo quelli semplici, otteniamo il prodotto. Pertanto, la rappresentazione numerica del messaggio scritto sopra deve essere divisa in blocchi inferiori a 23.393. Presentiamo una di queste divisioni.

Naturalmente la scelta dei blocchi non è univoca, ma non è nemmeno del tutto arbitraria. Ad esempio, per evitare ambiguità sul palco

la decrittazione non dovrebbe evidenziare i blocchi che iniziano con zero.

Quando si decrittografa un messaggio crittografato con il sistema di crittografia RSA, si ottiene una sequenza di blocchi. Vengono quindi collegati insieme per produrre una rappresentazione numerica del messaggio. E solo dopo aver sostituito i numeri con lettere secondo la tabella sopra sarà possibile leggere il messaggio originale.

Tieni presente che ogni lettera nella tabella è codificata con un numero a due cifre. Questo viene fatto per evitare confusione. Supponiamo di numerare le lettere in ordine, iniziando da 1, cioè A corrisponde a 1, B a 2 e così via. In questo caso non potremo dire con certezza se il blocco 12 rappresenta una coppia di lettere oppure una sola lettera, la dodicesima lettera dell'alfabeto. Naturalmente, per la rappresentazione numerica di un messaggio, è possibile utilizzare qualsiasi corrispondenza biunivoca tra lettere e numeri, ad esempio -encoding, in cui la traduzione del messaggio in forma digitale viene eseguita automaticamente da un computer.

§ 12.2. Crittografia e decrittografia

Un messaggio preparato per la crittografia utilizzando il metodo del § 12.1 è costituito da una sequenza di blocchi, ciascuno dei quali è un numero inferiore a Ora parliamo di come viene crittografato ciascun blocco. Per fare ciò, abbiamo bisogno di un numero uguale al prodotto di numeri primi e di un numero naturale, modulo invertibile, cioè numero che soddisfa la condizione

Ricordiamo che da p e q noti il ​​numero può essere facilmente calcolato. Veramente,

La coppia è chiamata chiave pubblica, o di codifica, del crittosistema RSA che stiamo descrivendo. Lasciamo bloccare il messaggio, cioè un numero intero che soddisfi la disuguaglianza. Utilizzeremo il simbolo per denotare il blocco del messaggio crittografato corrispondente a Si calcola secondo la seguente regola:

Tieni presente che ciascun blocco di messaggi viene crittografato separatamente. Pertanto, un messaggio crittografato è in realtà costituito da blocchi crittografati separati. Inoltre, non possiamo combinare questi blocchi in un unico grande numero, poiché ciò renderebbe impossibile decrittografare il messaggio. Presto ne vedremo il motivo.

Torniamo all'esempio che abbiamo iniziato a considerare nel primo paragrafo. Abbiamo fissato in modo che Ora dobbiamo scegliere un numero Ricordiamo che deve essere coprimo con Il più piccolo numero primo che non divide 23088 è uguale a 5. Impostiamo Per codificare il primo blocco del messaggio del § 12.1, abbiamo per determinare la sottrazione del numero 25245 modulo 23393. Utilizzando un programma di calcolo simbolico (o una calcolatrice, se avete pazienza) otteniamo che la detrazione richiesta è 22.752 Quindi, il messaggio criptato è rappresentato dalla seguente sequenza di blocchi :

Vediamo come vengono decodificati i blocchi di un messaggio crittografato. Per iniziare la decrittazione, dobbiamo conoscere l'elemento inverso del modulo. L'ultimo di essi è un numero naturale, che denoteremo con La coppia è chiamata segreto, o chiave di decodifica del sistema di crittografia RSA. Se a è un blocco di un messaggio crittografato, la sua decrittografia corrispondente

Il risultato dell'operazione è:

Prima di ritornare all’esempio sono necessarie alcune osservazioni. Innanzitutto, è molto facile da calcolare se lo sai. In effetti, la chiave segreta viene determinata utilizzando l'algoritmo euclideo esteso. In secondo luogo, se il blocco è il messaggio originale, allora abbiamo il diritto di aspettarci l'uguaglianza. In altre parole, quando decodifichiamo un blocco di un messaggio crittografato, speriamo di scoprire il blocco corrispondente di quello originale. Il fatto che ciò avvenga non deriva direttamente dall'algoritmo sopra descritto, ma parleremo di tutto in dettaglio nel prossimo paragrafo.

Infine, come abbiamo sostenuto nell'introduzione e in tutto il libro, per violare un sistema crittografico RSA è necessario fattorizzarlo perché è necessario sapere come decrittografare il messaggio. Tuttavia, una volta descritto in dettaglio il funzionamento del sistema, è chiaro che quest'ultima affermazione non è del tutto accurata. Per leggere la crittografia, oltre all'elemento stesso, è necessario conoscere solo il modulo inverso dell'elemento. Pertanto, per hackerare il sistema, è sufficiente calcolare con il noto. Si scopre che questo calcolo equivale a fattorizzare un numero , come vedremo nel § 12.4.

Nell'esempio in discussione applichiamo l'algoritmo euclideo esteso ai numeri e 5 da determinare.

(vedi scansione)

Pertanto, l'inverso di 5 modulo sarebbe -9235 e

Il più piccolo numero naturale paragonabile a -9235 modulo Quindi, per decodificare un blocco di un messaggio crittografato, dobbiamo elevarlo alla potenza di 13.853 modulo 23.393 Nel nostro esempio, il primo blocco codificato è 22.752 Calcolando la sottrazione del numero 22 75213853 modulo 23.393 , otteniamo Nota che anche con numeri così piccoli, i requisiti per il funzionamento del crittosistema RSA superano le capacità della maggior parte delle calcolatrici tascabili.

§ 12.3. Perché funziona?

Come abbiamo notato in precedenza, i passaggi sopra descritti portano ad un sistema crittografico funzionante solo se la decodifica di ciascun blocco del messaggio crittografato ripristinerà il blocco corrispondente di quello originale. Supponiamo di avere a che fare con un sistema RSA che ha una chiave pubblica e una chiave privata. Usando la notazione del § 12.2, dobbiamo mostrare che per ogni intero che soddisfa la disuguaglianza vale l'identità.

In effetti, è sufficiente dimostrarlo

Infatti, sia gli interi 6 che quelli non negativi sono più piccoli, pertanto sono confrontabili in valore assoluto se e solo se sono uguali. Questo, in particolare, spiega perché suddividiamo la rappresentazione numerica del messaggio in blocchi più piccoli. Inoltre, da questo si vede che si blocca

Il messaggio codificato va scritto a parte: altrimenti il ​​nostro ragionamento non funziona.

Dalle ricette di crittografia e decrittografia ne consegue questo

Poiché gli elementi sono reciprocamente inversi in modulo, esiste un k naturale tale che Inoltre, per condizione, i numeri sono maggiori Pertanto, sostituendo invece il prodotto nell'equazione (3.1), otteniamo

Usiamo ora il teorema di Eulero, il quale afferma che Quindi, cioè

e avremmo ottenuto completamente la dimostrazione se in essa non si fosse insinuato un piccolo errore.

Se rivedi attentamente il nostro ragionamento, noterai che non abbiamo tenuto conto delle condizioni del teorema di Eulero. Infatti, prima di applicare il teorema, è necessario assicurarsi che i numeri siano primi tra loro. Questo, a quanto pare, deve essere monitorato quando si prepara un messaggio per la crittografia, ad es. Quando si divide la rappresentazione numerica di un messaggio in blocchi, è necessario assicurarsi che tutti i blocchi risultanti siano coprimi. Fortunatamente questo non è necessario, perché in realtà il confronto viene effettuato per qualsiasi blocco. E l’errore non sta nel risultato che vogliamo dimostrare, ma solo nella dimostrazione stessa. L'approccio corretto si basa sul ragionamento utilizzato per dimostrare il teorema di Corcelt nel Capitolo 7.

Ricordiamo dove sono i diversi numeri primi. Definiamo i residui di un numero modulo Since

i calcoli per entrambi i numeri primi sono simili, tratteremo solo il caso in dettaglio, quindi questo lo abbiamo già visto

per qualche numero intero Pertanto,

Vorremmo ora applicare il teorema di Fermat, ma abbiamo il diritto di farlo solo se non divide. Lascia che questo requisito sia soddisfatto. Allora lo capiamo

Sostituendo il teorema di Fermat con il teorema di Eulero non abbiamo risolto il problema che si poneva: il confronto vale solo per alcuni, ma non per tutti i blocchi. Adesso però i blocchi per i quali il ragionamento non funziona devono essere divisi per Ulteriore, se divide allora entrambi 6 e sono paragonabili a 0 in modulo e quindi paragonabili tra loro. Pertanto il paragone in esame vale anche in questo caso. Pertanto, il confronto è vero per qualsiasi numero intero. Nota che non lo facciamo. avrebbe potuto usare un ragionamento simile applicando il teorema di Eulero a In effetti, disuguaglianza non significa confronto perché il numero è composto.

Quindi, abbiamo dimostrato che Il confronto è dimostrato in modo simile. In altre parole, divide sia per che Ma sono numeri primi diversi, così che Quindi, il lemma del § 3.6 ci garantisce che divide A poiché abbiamo per qualsiasi intero In altre parole, As. abbiamo notato all'inizio del paragrafo, questo è sufficiente per dimostrare l'uguaglianza poiché entrambe le sue parti sono interi non negativi minori di Per riassumere, possiamo dire che

l'algoritmo del paragrafo precedente porta ad un crittosistema pratico. Ora devi assicurarti che sia affidabile.

§ 12.4. Perché il sistema è affidabile?

Ricordiamo che RSA è un sistema di crittografia con una chiave pubblica costituita dal prodotto di vari numeri primi e un numero naturale invertibile modulo. Vediamo attentamente cosa si può fare per decifrare RSA se tutto ciò che si conosce è una coppia

Per decodificare un blocco crittografato con RSA, dobbiamo conoscere l'inverso del modulo k. Il problema è che praticamente l'unico modo conosciuto per farlo si basa sull'applicazione dell'algoritmo euclideo esteso. Tuttavia, per calcolare utilizzando la formula del § 9.4, dobbiamo. è necessario sapere cosa conferma l'affermazione originale: la rottura di RSA richiede la fattorizzazione. E poiché le difficoltà di decomposizione sono fondamentali, il sistema RSA è sicuro.

Naturalmente si può presumere che un giorno qualcuno scoprirà un algoritmo che calcola senza informazioni sui fattori di un numero. Ciò che, ad esempio, accadrà se qualcuno troverà un modo efficace per determinare direttamente da In effetti, questo è giusto un metodo di espansione mascherato Più precisamente, se

sono noti, allora possiamo facilmente calcolare Infatti,

quindi la somma dei divisori primi richiesti è nota. Ulteriore,

quindi anche la differenza è nota. Ora, risolvendo un semplice sistema di equazioni lineari, possiamo facilmente trovare la fattorizzazione.

Ciò significa che l’algoritmo che calcola in realtà scompone il numero in fattori, quindi è un uccello di una piuma. Ma è troppo presto per calmarsi. Puoi andare oltre nelle tue fantasie e supporre che qualcuno abbia inventato un algoritmo che determina direttamente da Ma Quindi, se lo sappiamo, allora conosciamo il numero che è un suo multiplo. Si scopre che tale informazione è sufficiente anche per la scomposizione. Un algoritmo probabilistico che porta a tale scomposizione può essere trovato V . L'esercizio 7 mostra un algoritmo di scomposizione simile (ma più semplice) partendo dal presupposto che il crittosistema Rabin possa essere violato. Ti darà un'idea dell'algoritmo probabilistico di .

Rimane l'ultima possibilità per l'hacking: un tentativo di ripristinare il blocco direttamente tramite i residui del modulo. Se è sufficientemente grande, l'unica via d'uscita è una ricerca sistematica di tutti i possibili candidati per la ricerca. Nessuno ha ancora inventato niente di meglio. Abbiamo elencato gli argomenti principali che spiegano perché rompere il sistema crittografico RSA è considerato equivalente alla fattorizzazione, sebbene non vi sia ancora una prova rigorosa di questa affermazione.

§ 12.5. Selezionando quelli semplici

Dalla discussione precedente ne consegue che per la sicurezza del crittosistema RSA è importante scegliere i numeri primi giusti. Naturalmente, se sono piccoli, il sistema viene facilmente hackerato. Tuttavia non basta sceglierne di grandi. Infatti, anche se p e q sono enormi, ma la differenza è piccola, il loro prodotto può essere facilmente fattorizzato utilizzando l'algoritmo di Fermat (vedi § 3.4).

Queste non sono chiacchiere. Nel 1995, due studenti di un'università americana riuscirono a decifrare una versione pubblica di RSA. Ciò è diventato possibile a causa della scarsa scelta dei fattori primi del sistema.

D'altronde l'RSA è utilizzato da molto tempo e, se si scelgono con attenzione i fattori primi, il sistema risulta effettivamente abbastanza affidabile. Pertanto, qualsiasi programmatore di crittografia RSA necessita di un metodo efficace per scegliere con successo i numeri primi.

Supponiamo di voler creare un sistema crittografico RSA con una chiave pubblica in cui l'intero ha circa cifre. Per prima cosa scegliamo un numero primo il cui numero di caratteri sia compreso tra. Attualmente, la dimensione della chiave consigliata per uso personale è 768 bit, ovvero dovrebbe essere lungo circa 231 cifre. Per costruire un numero del genere, ne abbiamo bisogno di due semplici, diciamo di 104 e 127 cifre. Si noti che i numeri primi scelti in questo modo sono abbastanza distanti tra loro, cioè Usare l'algoritmo di Fermat per la decomposizione in questa situazione non è pratico. Inoltre, dobbiamo assicurarci che non solo i fattori piccoli, ma anche quelli grandi siano coinvolti nella fattorizzazione dei numeri in fattori primi. Altrimenti, infatti, il numero diventa facile preda di alcuni noti algoritmi di scomposizione (vedi). Consideriamo ora un metodo mediante il quale si trovano i numeri primi che soddisfano le condizioni elencate.

Per prima cosa abbiamo bisogno di un semplice risultato sulla distribuzione dei numeri primi. Ricordiamo cosa denota il numero di numeri primi non superiori a x. Dato il teorema dei numeri primi, vediamo che per x grande il numero è approssimativamente uguale a dov'è il logaritmo naturale

sulla base (vedi § 4.5). Lascia che sia un numero molto grande, positivo. Vogliamo stimare il numero di numeri primi compresi tra e stimare la differenza Grazie al teorema dei numeri primi e alle proprietà del logaritmo, la differenza è approssimativamente uguale a

Supponendo che sia molto piccolo, possiamo assumere che il valore sia uguale a 0 e ottenere una stima ragionevole della differenza. Quindi, il numero di numeri primi racchiusi tra è approssimativamente uguale. Naturalmente, la stima è più accurata, maggiore è x e minore. Per un'introduzione più dettagliata a tale stima si veda ([D. 10]).

Supponiamo di dover scegliere un numero primo nell'intorno di un intero x. Per chiarezza, assumeremo che x sia di ordine , e stiamo cercando un primo nell'intervallo da x a. Sarebbe utile sapere in anticipo quanti numeri primi ci sono in questo intervallo. Per stimare il numero di primi si può utilizzare il risultato appena ottenuto. Nel nostro esempio, il valore è di un ordine di grandezza molto piccolo: quindi, utilizzando la formula scritta sopra, concludiamo che l'intervallo tra è di circa

numeri primi. Alla fine del secondo paragrafo del capitolo 11, abbiamo formulato una strategia progettata per dimostrare l'eccellenza di un dato numero dispari. Consiste in tre passaggi.