[¯|¯] Crittografia a chiave pubblica e la congettura di Riemann

Aprile 18th, 2017 | by Marcello Colozzo |

crittografia a chiave pubblica,rsa,congettura di Riemann

Crittografia a chiave pubblica

Ipotesi. Bob e Alice sono due amanti che scambiano messaggi utilizzando il sistema crittografico a chiave pubblica RSA. A grandi linee, tale sistema di cirfratura funziona nel seguente modo:

Alice genera un terna ordinata di interi (p,q,e), dove p,q sono numeri primi >100, mentre e < pq è un esponente. La coppia di primi è nota esclusivamente ad Alice, che però rende pubblico e ed n=pq. Tramite un canale pubblico (si pensi agli sms) Bob invia un messaggio m codificato come me modulo n. Per decodificare il messaggio, Alice deve eseguire l'operazione (me)d dove d=1/e modulo (p-1)(q-1). Alice può eseguire agevolmente tale operazione poiché è l'unica ad avere accesso a d.

La robustezza dell'algoritmo RSA deriva dal fatto che essendo ignota la funzione di distribuzione dei numeri primi, riesce estremamente costoso dal punto di vista computazionale, fattorizzare numeri interi molto grandi. Viceversa, la conoscenza della predetta distribuzione renderebbe vulnerabile l'algoritmo. Esiste un legame profondo tra la funzione di distribuzione dei primi e gli zeri non banali della funzione zeta di Riemann

La funzione di distribuzione degli zeri della zeta di Riemann

Abbiamo visto nei numeri precedenti che una buona approssimazione della funzione di distribuzione dei numeri primi (f.d.p da qui in poi) è:

crittografia a chiave pubblica,rsa,congettura di Riemann

Questa è l'approssimazione di Gauss. Legendre trovò, invece, quest'altra relazione approssimata:

crittografia a chiave pubblica,rsa,congettura di Riemann








Nel 1896 venne dimostrato il teorema dei numeri primi. Nel 1859 Riemann trovò la seguente funzione approssimante

crittografia a chiave pubblica,rsa,congettura di Riemann

i cui argomenti sono stati studiati nei numeri precedenti. Più precisamente

crittografia a chiave pubblica,rsa,congettura di Riemann

Tale formula venne dimostrata nel 1895 da von Mangoldt. La funzione f si scrive come:

crittografia a chiave pubblica,rsa,congettura di Riemann

dove fc(x) riproduce la continuità della f.d.p., mentre fd(x) genera le discontinuità di prima specie. Tra l'altro, esaminando l'andamento della f.d.p. si capisce subito che una possibile f.d.p. non è elementarmente esprimibile (non esiste, cioè, alcuna funzione dotata di espressione elementare avente quel particolare diagramma cartesiano). Per inciso, l'andamento a gradini è generato via software, e un qualunque ambiente di calcolo utilizza vari certificati di primalità per tracciare il grafico. Ne consegue che per x»1 l'elaborazione del grafico diviene progressivamente più lenta.
Esaminiamo ora le componenti della funzione f. Abbiamo:

crittografia a chiave pubblica,rsa,congettura di Riemann

L'espressione analitica della fd(x) è invece data da:
crittografia a chiave pubblica,rsa,congettura di Riemann

dove la sommatoria è estesa agli zeri non banali della funzione zeta di Riemann:
crittografia a chiave pubblica,rsa,congettura di Riemann

mentre Ei è la funzione esponenziale integrale estesa al campo complesso. In definitiva troviamo la formula illustrata al top di questa pagina.
Ne concludiamo che per conoscere la funzione π0(x) occorre conoscere la funzione di distribuzione degli zeri non banali della zeta di Riemann.

No TweetBacks yet. (Be the first to Tweet this post)

Tags: , ,

Articoli correlati

Commenta l'esercizio