Presto

Ipotesi di Riemann e Internet - IV


Lo sviluppo di un sistema di crittografia sicuro nell'era dei supercomputer non è facile. Tuttavia, gli scienziati R. Rivest, A. Shamir e L. Adleman hanno sviluppato un sistema crittografico a chiave pubblica chiamato "RSA" che è stato inviolabile. Questo sistema crittografico dipende dalla conoscenza matematica dei numeri primi e delle loro proprietà.

Come abbiamo visto nelle colonne precedenti, il lavoro della comunità matematica era molto importante nell'elaborazione di questo sistema. Il matematico tedesco C. F. Gauss ha formulato la nozione di congruenze, che è fondamentale nella codifica e decodifica delle chiavi nel sistema RSA. D'altra parte, il metodo proposto è giustificato dal teorema del matematico svizzero L. Euler, che è una generalizzazione di un risultato di congruenza del matematico francese P. de Fermat, noto come "Piccolo teorema di Fermat". Come per l'ultimo teorema di Fermat, il matematico francese dichiarò solo questo risultato ed Eulero dimostrò e generalizzò il piccolo teorema di Fermat. Questo risultato afferma che:

"Se p è un numero primo e m è un numero intero che non è divisibile per p,

poi m p - 1 ≡ 1 (mod p), ovvero il resto della divisione di m p - 1 da cugino p é 1.”

Ad esempio, il resto della divisione di 1.024 = 210 = 211 - 1 per 11 è 1.

La generalizzazione di Eulero di questo teorema si applica a qualsiasi modulo. Pertanto, utilizzeremo la versione richiesta per giustificare il sistema RSA, in cui il modulo è costituito dal prodotto di due numeri primi.

Teorema di Euler-Fermat:

"Se p e q sono numeri primi e m è un numero intero che non è divisibile nemmeno per p e non per q,

poi m (p-1)×(q-1) ≡ 1 (mod pq), ovvero il resto della divisione di m (p-1)×(q-1) da pq é 1.”

Ad esempio, il resto della divisione di 256 = 28 = 22.4 di 15 = 3.5 è 1.

Come abbiamo visto in precedenza, per codificare un testo, secondo il sistema RSA, è necessario:

(1) un numero elevato Nche è il prodotto di due cugini distinti p e q, cioè N = pq.

(2) un numero intero e, noto come chiave di codifica, che soddisfa le seguenti proprietà: il più grande divisore comune (MDC) tra e e il prodotto (p - 1)•(q -1) è 1 e l'MDC tra e e N è anche 1.

Per decodificare un testo, secondo il sistema RSA, è necessario:

(3) un numero intero D, noto come chiave di decrittazione, che soddisfa la condizione:

eD ≡ 1(mod (p -1)•(q - 1)).

La relazione tra e e D è simmetrico, cioè se D è la chiave di decrittazione per epoi e è la chiave di decrittazione per D.

Nelle colonne precedenti abbiamo codificato il messaggio CHIAVE PUBBLICA utilizzando il sistema RSA dove scegliamo

N = 2.537 = 43•59, p = 43, q = 59 e chiave di codifica e = 13.

Innanzitutto, notiamo che il numero N = 2.537 ha 4 cifre e quindi suddividiamo il testo in coppie di lettere:

PU BL IC KE Y

e completa l'ultimo blocco con la lettera C ottenendo:

<>

PU BL IC KE YC<>

.

Utilizzando la tabella di conversione che associa le lettere dell'alfabeto dei numeri naturali, i blocchi di messaggi convertiti sono:

1520 0111 0802 1004 2402.

In questo modo, il destinatario riceverà il messaggio crittografato:

0095 1648 1410 1299 0811.

Per decrittografare questo messaggio è necessaria la chiave di decrittazione pubblica, D. Nella colonna precedente abbiamo ottenuto D = 937 come chiave di decrittazione.

Codifichiamo ogni blocco, P, del messaggio in un blocco crittografato Qusando la relazione

<>

Q<>

P13 (mod 2.537).

Per decodificare il blocco Q di questo messaggio crittografato dobbiamo usare la relazione

PQ 937 (mod 2.537), 0 ≤ P < 2.537.

Notiamo che questa relazione è valida perché

QP13 (mod 2.537) implicain

<>

Q <>

937<>

≡ (P13)937 (mod 2.537) ≡ P12.181 (mod 2.537).

<>

Come 13۰937 = 12.181 = 5۰2.436 + 1, otteniamo

<>

Q <>

937<>

≡ (P13)937 (mod 2.537) ≡ P12.181 (mod 2.537) ≡ (P2.436)5 P (mod 2.537).

Dal teorema di Euler-Fermat, poiché 13 e 59 sono numeri primi, otteniamo

<>

P<>

(13 - 1) (59 -1) = P 2.436 ≡ 1 (mod 2.537)

e poi

<>

(P2.436)5 PP (mod 2.537).

Pertanto, per transitività, otteniamo

<>

Q<>

937<>

P (mod 2.537), 0 ≤ P < 2.537

quando MDC (P, 2.537) = 1.

Si noti che la relazione

<>

Q<>

937<>

P (mod 2537), 0 ≤ P <2.537, MDC (P, 2.537) = 1

è vero per tutti i blocchi in questo esempio.

Adesso prendiamo Q come il blocco 0095. Quindi dobbiamo risolvere la congruenza

95 937P (mod 2.537),

cioè, determinare il resto della divisione di 95937 per 2.537.

Innanzitutto, notiamo che questa congruenza è più facile da risolvere se prendiamo 937 come la somma dei poteri di base 2:

937 = 512 + 256 + 128 + 32 + 8 + 1 = 29 + 28 + 27 + 25 + 23 + 1.

Pertanto, abbiamo:

952 = 9.025 = 3<>

۰2.537 + 1.414 ≡ 1.414 (mod 2.537);

logo,

954 ≡ (1.414)2 (mod 2.537).

Come (1.414)2 = 1.999.396 = 788<>

372.537 + 240, ne consegue

954 ≡ 240 (mod 2.537).

Allo stesso modo otteniamo:

958 ≡ 1.786 (mod 2.537);

9516 ≡ 787 (mod 2.537);

9532 ≡ 341 (mod 2.537);

9564 ≡ 2.116 (mod 2.537);

95128 ≡ 2.188 (mod 2.537);

95256 ≡ 25 (mod 2.537);

95512 ≡ 625 (mod 2.537);

quindi:

(95)937 =

(95)512 <>

۰ (95)256<>

۰(95)128<>

۰(95)32<>

۰ (95)8<>

۰(95)

625<>

۰25<>

۰2188<>

۰341<>

۰1786<>

۰95 (mod 2.537).

Prendendo i prodotti due per due, otteniamo:

625<>

۰25 = 15.625 = 6<>

۰2.537 + 403 ≡ 403(mod 2.537)

2.188<>

۰341 = 746.108 = 294<>

۰2.537 + 230 ≡ 230(mod 2.537)

1.786<>

۰95 = 169.670 = 66<>

۰2.537 + 2.228 ≡ 2.228(mod 2.537).

presto,

625<>

۰25<>

۰2.188<>

۰341<>

۰1.786<>

۰95 (mod 2.537) ≡

403<>

۰ 230<>

۰ 2.228 (mod 2.537).

come

403<>

۰230 =

92.690 =

36<>

۰2.537 + 1.358 ≡

1.358(mod 2.537)

segue quello

1.358۰ 2.228 = 3.025.624 = 1.192۰2.537 + 1.520 ≡ 1.520 (mod 2537).

Concludiamo quello

625<>

۰25<>

۰2.188<>

۰341<>

۰1.786<>

۰95 =

1.358۰ 2.228 =

3.025.624 =

1.192۰2.537 + 1.520 ≡

1.520 (mod 2.537).

di conseguenza, Q corrisponde al blocco 1.520.

La ricerca sull'ipotesi di Riemann fornisce informazioni così preziose sul modello dei numeri primi che i progressi in questa indagine potrebbero portarci a progressi sostanziali nelle tecniche di factoring e, di conseguenza, a una violazione della sicurezza della trasmissione dei dati su Internet.

Sottolineiamo che lo sviluppo del sistema crittografico RSA rappresenta un altro esempio eccezionale della necessità della ricerca matematica, in quanto rappresenta il lavoro di innumerevoli generazioni di matematici. In effetti, vale la pena ricordare che fu Euclide, più di duemilatrecento anni fa, a dimostrare geneticamente che ci sono infiniti numeri primi.

Nonostante tutto il potere e il potere che la matematica mostra, esiste ancora un'idea piuttosto scarsa e incoerente che lo identifica solo con un linguaggio al servizio della scienza ...

La matematica è una delle più grandi creazioni dello spirito umano e chiudiamo con le parole di uno dei creatori del calcolo differenziale e integrale, il matematico tedesco Leibniz:

"La matematica è l'onore dello spirito umano".

Torna alle colonne

<

Video: La sfera e il punto (Settembre 2020).