Verband Priemgetallen en RSA

Algemene info over deze site. Suggesties e.d. kunnen hier ook geplaatst worden.
Plaats reactie
michelhubert
Nieuw lid
Nieuw lid
Berichten: 11
Lid geworden op: 30 okt 2012, 15:53

Verband Priemgetallen en RSA

Bericht door michelhubert » 18 mar 2016, 09:13

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

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Verband Priemgetallen en RSA

Bericht door David » 19 mar 2016, 15:56

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.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

arie
Moderator
Moderator
Berichten: 3909
Lid geworden op: 09 mei 2008, 09:19

Re: Verband Priemgetallen en RSA

Bericht door arie » 20 mar 2016, 12:50

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

Plaats reactie