» Esercizi svolti di Matematica e Fisica

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

Aprile 18th, 2017 | by Marcello Colozzo |

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 m^e modulo n. Per decodificare il messaggio, Alice deve eseguire l'operazione (m^e)^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) è:

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

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

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

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

dove f_c(x) riproduce la continuità della f.d.p., mentre f_d(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:

L'espressione analitica della f_d(x) è invece data da:

dove la sommatoria è estesa agli zeri non banali della funzione zeta 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 π₀(x) occorre conoscere la funzione di distribuzione degli zeri non banali della zeta di Riemann.

Tags: congettura di riemann, crittografia a chiave pubblica, RSA

Articoli correlati