L’algoritmo RSA e altri algoritmi

 

Il più conosciuto e utilizzato algoritmo a chiavi asimmetriche è stato proposto da Rivest, Shamir e Andleman nel 1978 e porta come nome la sigla dei cognomi dei suoi inventori. L’algoritmo sfrutta l’approccio di Diffie/Hellman e si basa sulla fattorizzazione di numeri interi grandi.
 
[adsense:block:adcontenuto]
 
Un destinatario Y di messaggi sicuri, per poter generare la propria coppia di chiavi, effettua i seguenti passaggi:
  • 1. Sceglie due grandi numeri interi p e q, entrambi numeri primi; il valore N = p*q verrà utilizzato per le operazioni di modulo durante la cifratura.
  • 2. Sceglie un intero e<N che sia primo rispetto al valore b = (p-1)*(q-1) (cioè e non ha fattori comuni diversi da 1 sia con (p-1) che con (q-1)).
  • 3. Trova il più piccolo intero d per il quale il valore (e*d-1) è divisibile per b, cioè (e*d) mod b = 1
  • 4. La chiave pubblica è pari a Kyp = [N, e], la chiave privata Kys = [N, d]; i fattori p e q possono essere distrutti o mantenuti segreti assieme alla chiave privata.

[adsense:block:adcontenuto]

L’algoritmo di cifratura richiede che il messaggio venga suddiviso in blocchi di m bit con m £ log2 N (cioè il valore numerico espresso da ciascun blocco deve essere £ N); detto mi un generico di questi blocchi, la versione cifrata mi’ è ottenuta come:
 
mi’ = mi
e mod N
 
Per la decifratura, si applica un calcolo analogo, ma con l’altro esponente, a ciascun blocco cifrato per riottenere quello in chiaro:
 
mi = mi’d mod N
 
Esempio (con numeri piccoli):
 
p=5, q=11 N = p*q = 55 b = 4*10 = 40
 
(poiché p e q sono sempre dispari, b è sempre divisibile per 4) e = 13 (13*d) mod 40 = 1 il più piccolo intero d che soddisfa l’eguaglianza è d = 37
 
Kyp = [55, 13] Kys = [55, 37]
 
se M = $3A90256C ($ sta per esadecimale) si può decidere di cifrare blocchi di 4 bit, corrispondenti a 1 cifra esadecimale (infatti 4 < log2 55 = 5.7; si poteva arrivare fino a 5 bit, mentre il cifrato ha necessariamente blocchi di 6 bit per rappresentare valori nell’intervallo [0,54])
 
m0’ = ($C)13 mod 55 = (12)13 mod 55 = 12 = $0C m1’ = (6)13 mod 55 = 51 = $33
m2’ = (5)13 mod 55 = 15 = $0F m3’ = (2)13 mod 55 = 52 = $34
m4’ = (0)13 mod 55 = 0 m5’ = (9)13 mod 55 = 14 = $0E
m6’ = ($A)13 mod 55 = (10)13 mod 55 = 10 = $0A m7’ = (3)13 mod 55 = 38 = $26
 
[adsense:block:adcontenuto]
 
Il valore cifrato che si ottiene è una sequenza di 6*8=48 bit ottenuti giustapponendo i blocchi di 6 bit cifrati:
 
M’ = $26 | $0A | $0E | 0 | $34 | $0F | $33 | $0C = (binario) %100110 001010 001110 000000110100 001111    110011 001100 =
= $98A380D0FCCC
 
Per la decifratura si ottiene:
 
m0 = ($0C)37 mod 55 = (12)37 mod 55 = 12 = $C m1 = ($33)37 mod 55 = (51)37 mod 55 = 6
m2 = ($0F)37 mod 55 = (15)37 mod 55 = 5 m3 = ($34)37 mod 55 = (52)37 mod 55 = 2
m4 = (0)37 mod 55 = 0 m5 = ($0E)37 mod 55 = (14)37 mod 55 = 9
m6 = ($A)37 mod 55 = (10)37 mod 55 = 10 = $A m7 = ($26)37 mod 55 = (38)37 mod 55 = 3
 
La sicurezza dell’algoritmo è basata sulla elevata difficoltà computazionale a ricavare i fattori p e q da un valore N grande, essendo quest’ultimo noto perché parte della chiave pubblica: il problema della fattorizzazione di un valore grande in due fattori primi, in particolare se questi sono grossomodo della stessa grandezza ma non così prossimi l’un l’altro, è ritenuto un problema difficile.
 
[adsense:block:adcontenuto]
 
In base a recenti ricerche che, in merito al problema della fattorizzazione con chiavi di 512 bit, hanno ottenuto risultati di quest’ordine: hardware del costo inferiore a 1 M$, 7-8 mesi di calcolo, oggi si può affermare che chiavi di 1024 o più bit sono ragionevolmente sicure per la maggior parte delle esigenze. Occorre tener però presente, come si evince dalla formula per la cifratura e decifratura, che più grandi sono le chiavi in gioco, maggiore è il tempo necessario per queste operazioni a parità di messaggio.
 
Sono stati proposti anche altri algoritmi come quello di ElGamal (1985) ancor più vicino rispetto a RSA al metodo di Deffie/Hellman, e quello delle curve ellittiche (il corpo numerico di base è in questo caso rappresentato dai punti di una curva ellittica definita su un campo finito) che ha un livello di sicurezza superiore a quello basato sulla fattorizzazione intera.

 

Risorse per sviluppo: 

Ti potrebbero anche interessare:

Personalizzare la vista Catalog dell'Ubercart con views

Tra i tanti limiti che il catalogo dell'ubercart si porta con se, chi di noi non avrà pensato almeno una volta come diamine personalizzare la visualizzazione a griglia o a tabella del catalogo di ubercart? Troppo poche le opzioni disponibili nelle impostazione del catalogo, perchè non posso aggiungere/rimuovere un campo ad esempio?
 
Drupal: 

Configurare Comment Notify

Il modulo comment notify notifica gli utenti dei commenti inseriti sulle pagine dove hanno lasciato un commento o una risposta ad un loro commento. Tuttavia dalle varie segnalazioni ricevute, non pochi hanno difficoltà a far funzionare questo utile modulo per Drupal. Ecco una guida per l'installazione e la configurazione guidata del Comment Notify.

Direct Marketing ed Email Marketing: Differenza e confronto

I pionieri del direct marketing (DM) Bob Stone, Martin Baier e Henry J. Hoke Jr parlavano della disciplina del direct marketing come un sistema interattivo di marketing che usa uno o più mezzi pubblicitari per scaturire una risposta misurabile e quantificabile e una transazione in qualsiasi luogo, con in più la possibilità non indifferente che tutta questa attività sia conservata in un apposito archivio (database).

Internet Marketing: 

PGP (Pretty Good Privacy)

 

Questa applicazione, pensata all’inizio degli anni ’90 da Philip Zimmermann e freeware, include sostanzialmente tutte le funzionalità descritte sopra e agevola la gestione delle chiavi. È disponibile per molte piattaforme (Windows, OS/2, Mac, Amiga, Unix/Linux, Vms, ecc.) e per Unix anche in formato sorgente modificabile. Esiste come plug-in di alcuni diffusi client di posta elettronica.
Risorse per sviluppo: