Numeri primi e messaggi cifrati

applet

: concetti base

[<] [>] [O] [.]

Introduzione: Fino al 1978 i numeri primi erano solo una curiosita' matematica. In quell'anno fu inventaro un algoritmo di cifratura detto RSA dal nome degli autori, che ora assicura, con l'uso dei numeri primi, la comunicazione sicura di informazioni in tutto il mondo.

Cose da fare: Il programma fa la cifratura di un messaggio e la decodifica dello stesso. Cliccate prima su "Generate keys".Vengono generati 3 numeri. Supponiamo che sono le chiavi di una persona a cui volete inviare un messaggio cifrato.Allora dovete copiare "Public key" e "Modulus key" nelle apposite finestre sopra cliccando su "Enter" per caricare i nuovi valori. A questo punto potete scrivere il messaggio nella finestra grande. Cliccate su "Encrypt" e il messaggio si trasforma in una serie di numeri che costituiscono il messaggio cifrato.
Provate a decifrare il messaggio riportato nella figura assumendo che e' stato crittato con le chiavi riportate sotto.
Per corrispondere in cifrato con un'altra persona dovete scegliere ognuno una diversa tripla di chiavi con "Generate keys". Quindi scambiarvi le "chiavi pubbliche" cioe' le coppie di numeri (public key,modulus key). Per cifrare basta usare la coppia di numeri dell'altra persona e inviare il testo cifrato copiandolo dalla finestra e incollandolo in un mail. Per decifrare i messaggi dell'altra persona usate la vostra chiave privata.

Cosa succede: Ecco l'algoritmo della crittografia RSA inventato nel 1978 da Ron Rivest, Adi Shamir, and Leonard Adleman.

1. Trova P and Q, due numeri primi grandi (ad esempio 1024-bit).

2. Scegli E tale che E sia minore di PQ, e tale che E e (P-1)(Q-1) siano primi tra di loro . E puo' non essere primo ma deve essere dispari. (P-1)(Q-1) non puo' essere primo perche' e' un numero pari.

3. Calcola D tale che (DE - 1)sia divisibile per (P-1)(Q-1).
   
4. La funzione di crittazione e' encrypt(T) = (T^E) mod PQ, dove T e' il testo in chiaro (un intero positivo).

5. La funzione di decrittazione e' decrypt(C) = (C^D) mod PQ, dove C e' il testo cifrato (un intero positivo) .

La chiave pubblica e' la coppia (PQ, E). La chiave privata e' il numero D. Nell'applet non sappiamo quali sono i 2 primi P e Q mentre la chiave pubblica e' modulus key=PQ cioe' il prodotto dei due numeri primi base dell'algoritmo ed public key = E.
Nella realta' i numeri primi P e Q sono molto grandi (di circa 100 cifre ciascuno). Trovare dal loro prodotto PQ (che fa parte della chiave pubblica) il loro valore comporta una ricerca attraverso un numero grandissimo di possibilita' che e' impossibile portare a termine anche con computer molto veloci e in tempi lunghissimi(l'eta' dell'universo). Ovviamente, piu' grandi sono P e Q e piu' difficile e' risalire ad essi. Questo e' un compito che puo' essere usato per mettere alla prova un supercomputer o una rete di migliaia di computer. Una rete di computer su Internet e' infatti riuscita a ricavare P e Q da una chiave pubblica (si dice in gergo fattorizzare) con P e Q di circa ottanta cifre decimali.

Commenti:

Argomenti trattati ed altri materiali disponibili online
I numeri puntano a schede nel museo, le scritte An a materiali in rete sullo stesso argomento non inclusi nel museo

• Crittografia  A1 A2 A3
• Numeri primi 84  A1
• Altri applet di concetti base