Pagina 1 van 1

Verband Priemgetallen en RSA

Geplaatst: 18 mar 2016, 09:13
door michelhubert
Hoi,

Ik las laatst dit artikel:
http://www.volkskrant.nl/wetenschap/wis ... n~a4265097

En ik vroeg me af of deze ontdekking invloed heeft op de moeilijkheidsgraad van het kraken van RSA-versleuteling?

Kan iemand mij uitleggen waarom wel of niet?


Alvast bedankt,
Michel

Re: Verband Priemgetallen en RSA

Geplaatst: 19 mar 2016, 15:56
door David
Niet veel, hoogstens. RSA-versleuteling leunt op dat ontbinden in factoren tijdrovend is. Twee verschillende priemfactoren zijn vermenigvuldigd en voor het ontsleutelen is ontbinding nodig. De ontdekking gaat over twee opeenvolgende priemgetallen, ofwel twee priemgetallen waartussen geen priemgetal ligt. Bij RSA-ontbinding worden niet noodzakelijk zulke priemgetallen gebruikt.

P.S. In het artikel wordt 1 een priemgetal genoemd. 1 is dat niet (meer). 1 is niet priem en niet samengesteld. Dit bijvoorbeeld zodat elk getal een unieke priemontbinding heeft. Een definitie die je kan hanteren voor een priemgetal (anders dan die uit het artikel) is 'een priemgetal is een getal met precies twee delers'. 1 heeft een deler, namelijk zichzelf.

Re: Verband Priemgetallen en RSA

Geplaatst: 20 mar 2016, 12:50
door arie
RSA blijft met deze bevinding net zo veilig als het was, zie David hierboven.
de Volkskrant schreef: ... de eerste miljoen priemgetallen blijkt namelijk wel degelijk een patroon.
Zo wordt een priemgetal dat eindigt op een 9 in 65 procent van de gevallen gevolgd door een priemgetal met eindcijfer 1
Die 65% lijkt me sterk overdreven, ik kom uit op 33.8% met deze Pari/GP code (binnen 6 seconden):

Code: Selecteer alles

{
M=matrix(9,9);  \\ M[i,j] = aantal sprongen van priem *i naar priem *j
nmax=1000000;

p=2;
for(n=2,nmax,
  q=nextprime(p+1);
  M[p%10, q%10]+=1;
  p=q;
  );

print("priem *9 gevolgd door priem *1: ",M[9,1]/sum(i=1,9,M[9,i])+0.);
print("\naantal sprongen vanaf:");
for(j=1,9,print("priem *",j,": ",sum(i=1,9,M[j,i])));
print("\npriem ",nmax," = ", p);
M
}
Hier een link naar het bron-artikel, het ligt genuanceerder:
http://arxiv.org/pdf/1603.03720v2.pdf