Primeritat. Construcció de primers
Artur Travesa
(versió 2021-04)

Introducció general

L'origen d'aquestes notes es remunta a diferents cursos d'Aritmètica o de Criptografia, a càrrec de l'autor, per a estudiants de Matemàtiques o d'Informàtica de la Universitat de Barcelona.

La idea bàsica és descriure algunes aplicacions importants de l'Aritmètica bàsica (diguem, de nivell de primer curs) a les transmissions xifrades d'informació.

En cap cas es tracta d'un curs de Criptografia, que caldria encabir en espais més amplis de coneixements, que haurien d'incloure, probablement, parts de teoria de la comunicació, de complexitat algorítmica o computacional, d'aprenentatge automàtic, o d'estudi de teories de compartició de secrets, entre d'altres.

El format triat per a la presentació és el d'un notebook de Mathematica, per la facilitat que té aquest programari per a poder desenvolupar els càlculs no trivials de manera prou senzilla i entenedora, d'una banda, i per a permetre fer una presentació escrita prou raonable des del punt de vista de material escrit, de l'altra. En particular, la possibilitat d'incloure els càlculs dins del text de manera natural en fan una bona eina comunicativa i, alhora, facilita molt el càlcul amb exemples no trivials.

A fi de veure tot el contingut del notebook convé executar-lo. Això es pot fer de cop o bé, més recomanable, cel·la a cel·la a mesura que s'avança en la lectura i comprensió dels diferents continguts. 
Observació: Per al cas en què no es disposi del programari, hi ha la versió executada del notebook en format pdf.

Amb la finalitat doble d'una banda, de no fer textos molt llargs o amb molts continguts, i de l'altra de poder ampliar de manera senzilla els continguts que s'hi tractin, el material s'ha dividit en diferents notebooks, que desrivim a continuació, en l'apartat de referències.

Referències

[Cripto-1]: Criptografia bàsica (1).
Travesa, A.: CriptografiaBasica-1; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una iniciació a la codificació de missatges. El criptosistema de Cèsar. El criptosistema de Vigenère.

[Cripto-2]: Criptografia bàsica (2). 
Travesa, A.: CriptografiaBasica-2; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Els criptosistemes lineals. Els criptosistemes afins. Sufixació de missatges. Farciment de missatges.

[Eratostenes]: Un garbell d'Eratòstenes.
Travesa, A.: Eratostenes; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Un garbell d'Eratòstenes.

[Cripto-3]: Primeritat. Construcció de primers. 
Travesa, A.: ConstruccioDePrimers; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Test de primeritat de Solovay-Strassen. Test de primeritat de Miller-Rabin. Un  certificat congruencial de primeritat. Construcció certificada de nombres primers de mida prefixada. Aplicació al càlcul de claus RSA. Aplicació (exercici) al càlcul de claus ElGamal.

[Cripto-4]: Factorització. 
Travesa, A.: Factoritzacio; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Un garbell d'Eratòstenes. Tests de primeritat de Solovay-Strassen i de Miller-Rabin. Un certificat congruencial de primeritat. Un algoritme bàsic de divisó per nombres primers petits. Un algoritme bàsic de divisó per nombres petits. El mètode de factorització de Fermat. El mètode de factorització p-1 de Pollard. El mètode de factorització rho de Pollard.

[RSA]: Criptosistemes de tipus RSA. 
Travesa, A.: RSA; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/
Contingut: Una descripció bàsica dels criptosistemes de tipus RSA: les claus; xifratge; desxifratge; observacions sobre la seguretat.

[ElGamal]: El criptosistema ElGamal. 
Travesa, A.: ElGamal; accessible en forma notebook o en format pdf des de https://travesa.cat/notes/ 
Contingut: Logaritmes discrets. Una descripció bàsica del criptosistema ElGamal: el grup cíclic; les claus; xifratge i desxifratge.

[Tr-1]: Travesa, A.: Aritmetica. Edicions de la Universitat de Barelona, col·lecció UB, n. 25. Barcelona, 1998. ISBN:84-8338-031-5.

1. Tests de primeritat

Exercici 1 (Test de Solovay-Strassen)

La funció següent és una implementació del test de primeritat de Solovay-Strassen. Es demana esbrinar i explicar com funciona; en particular, a quins nombres es pot aplicar, en quants passos acaba el càlcul, què podem dir d'un nombre segons la sortida de l'algoritme, ...

SolovayStrassen[nn_,ff_]:=Module[{n=Abs[nn],f,g,x,y},
If[Not[IntegerQ[n]],Print["Cal que n sigui un nombre enter."];Return[Null],Null];
If[ff<1,Print["Cal fer alguna prova."];Return[Null],Null];
If[n==2||n==3||n==5||n==7, Return[True ],Null];
If[n==1|| EvenQ[n],Return[False],Null];
f=0;
While[f<ff,
g=Random[Integer,{2,n-2}];
x=PowerMod[g,(n-1)/2,n];
If[x==1 || x== n-1,y=Mod[JacobiSymbol[g,n],n];If[x≠y,Return[False],Null],Return[False]];
f++];
Return[Indeterminate]
]

S'aplica a un nombre enter nn i un nombre ff com a fita per al nombre de passos d'algoritme.

Proporciona 
True, si nn és un dels nombres primers 2, 3, 5, o bé 7;
False, si nn és o bé 1 o bé és parell >2; o bé per a algun valor de g triat a l'atzar entre 2 i nn-2 és g^((nn-1)/2) != + - 1 (mod nn); per tant, nn és compost amb tota seguretat;
Indeterminate, si per a ff nombres g triats a l'atzar se satisfà que g^((nn-1)/2) = (g / nn) = +-1 (mod nn); és a dir, si nn es comporta com si fos primer per a ff valors g triats a l'atzar.

Si la sortida és Indeterminate, el fet és que si nn és compost, la probabilitat que el test no ho hagi detectat és menor que 1/ (2^ff) .
De fet, si el nombre nn és compost, el test ho detecta en pocs passos (i probabilitat alta).

Exercici 2 (Test de Miller-Rabin)

La funció següent és una implementació del test de primeritat de Miller-Rabin. Es demana esbrinar i explicar com funciona; en particular, a quins nombres es pot aplicar, en quants passos acaba el càlcul, què podem dir d'un nombre segons la sortida de l'algoritme, ...

MillerRabin[nn_,ff_]:=Module[{n=Abs[nn],v,m,f,g,x,k},
If[Not[IntegerQ[n]],Print["Cal que n sigui un nombre enter."];Return[Null],Null];
If[ff<1,Print["Cal fer alguna prova."];Return[Null],Null];
If[n==2||n==3||n==5||n==7, Return[True],Null];
If[n==1|| EvenQ[n],Return[False],Null];
v=0;m=n-1;While[EvenQ[m],v++;m=m/2];
f=0;
While[f<ff,
g=Random[Integer,{2,n-2}];
x=PowerMod[g,m,n];
If[x≠1 && x≠n-1,
k=1;
x=PowerMod[x,2,n];
While[x≠n-1 && k<v-1,x=PowerMod[x,2,n];k++];
If[k≥v-1 && x≠n-1,Return[False],Null],Null];
f++];
Return[Indeterminate]
]

S'aplica a un nombre enter nn i un nombre ff com a fita per al nombre de passos d'algoritme.

Proporciona 
True, si nn és un dels nombres primers 2, 3, 5, o bé 7;
False, si nn és o bé 1 o bé és parell >2; o bé per mitjà d'algun valor de g triat a l'atzar entre 2 i nn-2 el test demostra que nn és compost.
Indeterminate, si per a ff nombres g triats a l'atzar el nombre nn es comporta com si fos primer.

Si la sortida és Indeterminate, el fet és que si nn és compost, la probabilitat que el test no ho hagi detectat és menor que 1/ (4^ff) .
De fet, si el nombre nn és compost, el test ho detecta en pocs passos (i probabilitat alta).

Exercici 3

Es demana aplicar els tests de primeritat dels dos exercicis anteriors: d'una banda, a una llista de 10000 nombres enters aleatoris i comparar-ne els resultats; i, de l'altra, a una llista de 10000 nombres naturals primers aleatoris i comparar-ne els resultats. Podem dir que algun dels mètodes és millor que l'altre? Per què? Quin tarda més? (Es pot provar amb una fita ff=2 en tots els casos...)

n=10000

nr=RandomInteger[10^20,n];

t=Table[{a=SolovayStrassen[nr[[i]],2],b=MillerRabin[nr[[i]],2],a==b},{i,1,n}];

Select[t, #[[1]] ≠ #[[2]] &]

Timing[Table[SolovayStrassen[nr[[i]],2],{i,1,n}];]

Timing[Table[MillerRabin[nr[[i]],2],{i,1,n}];]

Timing[Table[SolovayStrassen[nr[[i]],4],{i,1,n}];]

pr=RandomPrime[10^20,n];

tp=Table[{a=SolovayStrassen[pr[[i]],2],b=MillerRabin[pr[[i]],2],a==b},{i,1,n}];

Select[tp, #[[1]] ≠ #[[2]] &]

Timing[Table[SolovayStrassen[pr[[i]],2],{i,1,n}];]

Timing[Table[MillerRabin[pr[[i]],2],{i,1,n}];]

Timing[Table[SolovayStrassen[pr[[i]],4],{i,1,n}];]

Per a nombres naturals triats a l'atzar, ha trigat més el test de Miller-Rabin, fins i tot en el cas d'aplicar el de Solovay-Strassen amb una fita doble a fi de millorar la probabilitat d'aquest fins a la probabilitat de Miller-Rabin.
En canvi, si passem els tests només a nombres primers, en tots els casos funciona millor el test de Miller-Rabin.
Això suggereix que, per a fer servir el test com a garbell per a determinar nombres primers d'entre nombres naturals arbitraris, sembla millor usar el test de Solovay-Strassen; en canvi, si es tracta de "confirmar" que certs nombres "són" primers, sembla millor usar el test de Miller-Rabin.

Notem que en tots els casos ens referim a aquestes implementacions dels tests; per a altres implementacions, els resultats poden ser diferents.

2. Certificats de primeritat

Exercici 4 (Un certificat congruencial de primeritat)

La funció següent és una implementació d'un certificat de primeritat. Es demana esbrinar i explicar com funciona; en particular, a quins nombres es pot aplicar, en quants passos s'acaba, què podem dir d'un nombre segons la sortida de l'algoritme, ...

Certificat[pp_,f_,n_]:=Module[{p=Abs[pp],fppmu,l,m,g,mm,s},
If[IntegerQ[p],Null,Print["Cal que p sigui un nombre enter."];Return[Null]];
If[n<1,Print["Cal fer alguna prova."];Return[Null],Null];
If[p==2 || p==3,Return[{True,p-1,{p-1}}],Null];
If[p==1 ||EvenQ[p],Return[{False,2}],Null];
If [f=={},fppmu=Transpose[FactorInteger[p-1]][[1]],fppmu=Sort[f]];l=Length[fppmu];m=0;While[m<n,g=Random[Integer,{2,p-2}];If[(s=PowerMod[g,(p-1)/2,p])==p-1,i=2;While[i≤l && PowerMod[g,(p-1)/fppmu[[i]],p]≠ 1,i++];If[i==l+1,Return[{True,g,fppmu}],Null],If[s≠1,Return[{False,g}],Null]];m++];
Return[Indeterminate]
]

S'aplica un nombre màxim n de vegades a un nombre pp i la llista f dels divisors primers de pp-1. Si la llista és buida, intenta calcular-la.

Proporciona llistes de la forma
{True,  g, lta},  si pp és primer, on g és una arrel primitiva mòdul p, i lta és la llista dels divisors primers de pp-1;
{False, g}, si pp és compost i on g detecta que pp és compost; per exemple, proporciona g=2 si pp és un nombre parell diferent de 2; en general, proporciona un valor de g d'ordre no divisor de de pp-1, si pp és compost;
Indeterminate, si no pot certificar que pp és primer en el nombre de passos demanat.

Notem que l'algoritme pot no acabar si no proporcionem la llista dels divisors primers de pp-1, perquè intenta calcular-la.
D'altra banda, si la llista és no buida, suposa que és la llista dels divisors primers de p-1; si no ho és, el resultat pot ésser erroni. (No es fa cap intent de comprovar la llista.)

Exercici 5

La funció següent és una implementació d'una funció per a la comprovació del certificat de primeritat que proporciona l'exercici anterior. Es demana esbrinar i explicar com funciona.

Comprova[pp_,cert_]:=Module[{p=pp,g=cert[[2]],lta=cert[[3]],x,q,d},
If[p==2,Return[cert=={True,1,{1}}],Null];
If[p==3,Return[cert=={True,2,{2}}],Null];
x=Product[lta[[i]],{i,1,Length[lta]}];
If[Mod[p-1,x],Return[False],Null];
q=(p-1)/x;
d=GCD[q,x];
While[d>1,q=q/d;d=GCD[q,x]];
If[q≠ 1,Return[False],Null];
If[PowerMod[g,p-1,p]≠1,Return[False],Null];
If[MemberQ[Table[PowerMod[g,(p-1)/lta[[i]],p ],{i,1,Length[lta]}],1],Return[False],Return[True]]
]

La funció s'aplica a un nombre pp i una llista cert.

Proporciona 
True, si cert és un certificat que pp és primer;
False, en cas contrari (o bé pp no és primer, o bé ho és però cert no n'és un certificat).

Exercici 6

Es demana modificar les funcions SolovayStrassen i MillerRabin dels exercicis anteriors a fi que proporcionin un certificat que el nombre és compost, si ho és i el test ho detecta.

SolovayStrassenCert[nn_,ff_]:=Module[{n=Abs[nn],f,g,x,y},
If[Not[IntegerQ[n]],Print["Cal que n sigui un nombre enter."];Return[Null],Null];
If[ff<1,Print["Cal fer alguna prova."];Return[Null],Null];
If[n==2||n==3||n==5||n==7, Return[True ],Null];
If[n==1,Return[{False,1}],Null];
If[EvenQ[n],Return[{False,2}],Null];
f=0;
While[f<ff,
g=Random[Integer,{2,n-2}];
x=PowerMod[g,(n-1)/2,n];
If[x==1 || x== n-1,y=Mod[JacobiSymbol[g,n],n];If[x≠y,Return[{False,g}],Null],Return[{False,g}]];
f++];
Return[Indeterminate]
]

MillerRabinCert[nn_,ff_]:=Module[{n=Abs[nn],v,m,f,g,x,k},
If[Not[IntegerQ[n]],Print["Cal que n sigui un nombre enter."];Return[Null],Null];
If[ff<1,Print["Cal fer alguna prova."];Return[Null],Null];
If[n==2||n==3||n==5||n==7, Return[True],Null];
If[n==1,Return[{False,1}],Null];
If[EvenQ[n],Return[{False,2}],Null];
v=0;m=n-1;While[EvenQ[m],v++;m=m/2];
f=0;
While[f<ff,
g=Random[Integer,{2,n-2}];
x=PowerMod[g,m,n];
If[x≠1 && x≠n-1,
k=1;
x=PowerMod[x,2,n];
While[x≠n-1 && k<v-1,x=PowerMod[x,2,n];k++];
If[k≥v-1 && x≠n-1,Return[{False,g}],Null],Null];
f++];
Return[Indeterminate]
]

Exercici 7

Es proposa la implementació d'una funció per a comprovar els certificats que proporcionin les funcions de l'exercici anterior. No en donarem solució.

3. Construcció certificada de nombres primers de mida prefixada

Es tracta de construir nombres primers (i certificar que ho són) de la mida que vulguem; per exemple, una parella de nombres primers, d'entre 508 i 512 bits cadascun, a fi que el seu producte sigui un nombre natural d'entre 1016 i 1024 bits.

Exercici 8

Suposem que la funció PrimeQ de Mathematica certifica els nombres primers de 15 xifres binàries o menys.
Es demana construir una taula amb 10 nombres primers de 112 bits i certificar-los. (No cal escriure els certificats.)

lp112=Table[Module[{n,q,fita=500},n=0;While[SolovayStrassen[q=2*Random[Integer,{2^110,2^111-1}]+1,25]==False && n<fita,n++];If[n<fita && Certificat[q,{},50][[1]]==True,q,0]],{i,1,10}]

Observació

Notem que el producte de quatre d'aquests nombres primers és un nombre d'aproximadament 448 bits, posem n1. Llavors, per a nombres naturals k en un cert interval, que s'ha de calcular, tots els nombres p=2 k n1 +1 són senars i del nombre de bits que es desitja.
Ara, donat un d'aquests nombres p, per a saber si és primer, es pot utilitzar un test de primeritat, de manera que si p és compost, no passarà el test.
Finalment, com que el nombre k és prou petit, es pot calcular fàcilment la seva descomposició en factors primers, de manera que podem conèixer fàcilment la llista de divisors primers de p-1 i, en conseqüència, serà senzill certificar els nombres p que siguin primers.

Exercici 9

Es demana construir, amb alguns dels nombres primers calculats a l'exercici anterior, una parella de nombres primers, p, q, de 512 bits cadascun, i de manera que p-1 i q-1 siguin divisibles per algun nombre primer de 480 bits (diferent per a p-1 i q-1). Es demana, també, certificar tots els nombres primers que es facin servir.
(Notem que cal usar l'observació anterior un mínim de dues vegades per a cadascun dels nombres primers p que es volen construir; una, per a construir un nombre primer de més de 480 bits que cal que divideixi p-1; i una altra per a la construcció de p.)
Es poden usar (o no) les indicacions posteriors.)

Començarem per calcular nombres primers de 480 bits.

Calculem dos productes de quatre dels nombres anteriors (més endavant necessitarem saber quins fem servir per a cada producte).

{n1=Product[lp112[[i]],{i,1,4}],n2=Product[lp112[[i]],{i,7,10}]}

Calculem els intervals on hem de cercar els valors de k a fi de trobar nombres de 480 bits. Notem que els nombres que hem calculat són de 448 bits, aproximadament.

{x11=Floor[2^478/n1]+1,x12=Floor[(2^479-1)/n1],x21=Floor[2^478/n2]+1,x22=Floor[(2^479-1)/n2]}

Calculem valors aleatoris de k.

{kq1=Random[Integer,{x11,x12}],kq2=Random[Integer,{x21,x22}]}

Calculem les llistes dels divisors primers dels nombres k que, com que són petits, podem factoritzar.

{f1kq1=Transpose[FactorInteger[kq1]][[1]],f1kq2=Transpose[FactorInteger[kq2]][[1]]}

Calculem la llista dels divisors primers de q-1, per als dos nombres que cerquem.

{f0q1=Table[lp112[[i]],{i,1,4}],f0q2=Table[lp112[[i]],{i,7,10}]};

{fq1=Union[{2},f1kq1,f0q1],fq2=Union[{2},f1kq2,f0q2]}

Calculem els dos nombres q.

{q1=2* kq1* n1+1,q2=2* kq2* n2+1}

Mitjançant el test de Solovay-Strassen o el de Miller-Rabin, determinem si els nombres són o no primers; si no ho són (com probablement serà el cas), caldrà repetir la tria del valor de k, el càlcul dels seus factors primers, i el càlcul del nou valor de q, fins a trobar-ne un que sigui primer (d'acord amb el test).

SolovayStrassen[q1,50]

No podem passar-vos la vida amb aquest càlcul; per tant, provarem un màxim de 500 valors aleatoris de k.

fita=500

Ara, iterem el càlcul de k a fi que q sigui primer.

While[fita>0 && SolovayStrassen[q1,25]==False, kq1=Random[Integer,{x11,x12}];q1=2 *kq1 *n1+1;fita=fita-1];
If[fita==0,0,q1]

Mirem si el valor de q sembla primer. (Com que hauria de ser-ho, passarem el test de Miller-Rabin en comptes del de Solovay-Strassen.)

MillerRabin[q1,50]

Ara, ho repetim tot per a trobar el segon valor de q.

SolovayStrassen[q2,50]

fita=500

While[fita>0 && SolovayStrassen[q2,25]==False, kq2=Random[Integer,{x21,x22}];q2=2 *kq2 *n2+1;fita=fita-1];
If[fita==0,0,q2]

MillerRabin[q2,50]

Escrivim els valors de k.

{kq1,kq2}

Calculem els factors primers dels nombres k.

{fkq1=Transpose[FactorInteger[kq1]][[1]],fkq2=Transpose[FactorInteger[kq2]][[1]]}

Calculem les llistes de divisors primers de q-1, per als dos valors de q.

{fq1=Union[{2},Transpose[FactorInteger[kq1]][[1]],f0q1],fq2=Union[{2},Transpose[FactorInteger[kq2]][[1]],f0q2]}

Certifiquem els nombres primers q. Notem que coneixem les llistes dels divisors primers de q-1.

{Certificat[q1,fq1,500],Certificat[q2,fq2,500]}

Comprovem que, efectivament, els nombres q són de la mida adequada (de fet, no caldria...).

2^479<q1 && q1< 2^480-1 && 2^479<q2 && q2< 2^480-1

Amb aquests nombres q, construïm els p de la mateixa manera que abans hem fet els q. Comencem per calcular els intervals adequats per als nous valors de k.

{y11=Floor[2^510/q1]+1,y12=Floor[(2^511-1)/q1],y21=Floor[2^510/q2]+1,y22=Floor[(2^511-1)/q2]}

Calculem els valors de k.

{kp1=Random[Integer,{y11,y12}],kp2=Random[Integer,{y21,y22}]}

Calculem la llista dels divisors primers de k.

{fkp1=Transpose[FactorInteger[kp1]][[1]],fkp2=Transpose[FactorInteger[kp2]][[1]]}

Calculem la llista dels divisors primers dels valors de p-1.

{fp1=Union[{2},fkp1,{q1}],fp2=Union[{2},fkp2,{q2}]}

Calculem els valors dels p.

{p1=2 *kp1* q1+1,p2=2 *kp2* q2+1}

Són primers?

SolovayStrassen[p1,50]

Iterem el càlcul.

fita=1000

While[fita>0 && MillerRabin[p1,25]==False, kp1=Random[Integer,{y11,y12}];p1=2 *kp1 * q1+1;fita=fita-1]

fita

Tenim el valor d'un dels nombres primers. (Excepte si fita val 0, cas en què hem de repetir el càlcul anterior i la iteració.)

p1

Calculem la llista de divisors primers de p-1.

fp1=Union[{2},Transpose[FactorInteger[kp1]][[1]],{q1}]

Escrivim un certificat per a p.

Certificat[p1,fp1,500]

Comprovem que p és de la mida adequada (no caldria...).

2^511<p1 && p1< 2^512-1

Ara, repetim el mateix per a trobar un segon valor de p.

SolovayStrassen[p2,50]

fita=1000

While[fita>0 && MillerRabin[p2,25]==False, kp2=Random[Integer,{y21,y22}];p2=2 *kp2 * q2+1;fita=fita-1]

fita

p2

fp2=Union[{2},Transpose[FactorInteger[kp2]][[1]],{q2}]

Certificat[p2,fp2,500]

Exercici 10

A partir de la parella de nombres primers p, q que hem calculat a l'exercici anterior, es demana construir una parella de claus (privada-pública) per a un criptosistema RSA de 1024 bits.

e=2*Random[Integer,{2^1022,2^1023-1}]+1

d=PowerMod[e,-1,(p1-1)(p2-1)/GCD[p1-1,p2-1]]

Observació: Si e no és invertible, cal repetir la tria fins que ho sigui.

{ClauRSAPublica={p1*p2,e}, ClauRSAPrivada={p1*p2,d}}

4. Claus ElGamal

Definició

Una parella de claus privada pública per a un criptosistema ElGamal consta de nombres naturals p, q, g, x, h, de manera que:
p és un nombre primer;
q és un nombre primer que divideix p-1;
g és un nombre natural invertible mòdul p i d'ordre exactament q en G(p);
x és un nombre natural;
h és la potència x-èsima de g mòdul p.
La clau privada és la llista {p, q, g, x } i la clau pública és la llista {p, q, g, h}.

Exercici

Es demana construir un nombre primer p de 1024 bits tal que p-1 sigui divisible per un nombre primer q de 1000 bits.

(Cal certificar tots els nombres primers que es facin servir i que siguin de més de 15 xifres binàries.)

Es demana utilitzar aquesta parella de nombres primers p, q per a construir una parella de claus privada-pública per al criptosistema ElGamal.