Verband Priemgetallen en RSA

Algemene info over deze site. Suggesties e.d. kunnen hier ook geplaatst worden.

Verband Priemgetallen en RSA

Berichtdoor michelhubert » 18 Mrt 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
michelhubert
Nieuw lid
Nieuw lid
 
Berichten: 10
Geregistreerd: 30 Okt 2012, 15:53

Re: Verband Priemgetallen en RSA

Berichtdoor David » 19 Mrt 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)
David
Moderator
Moderator
 
Berichten: 4935
Geregistreerd: 14 Mei 2009, 16:22

Re: Verband Priemgetallen en RSA

Berichtdoor arie » 20 Mrt 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: Alles selecteren
{
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
arie
Moderator
Moderator
 
Berichten: 3014
Geregistreerd: 09 Mei 2008, 09:19


Terug naar Algemeen

Wie is er online?

Gebruikers in dit forum: Geen geregistreerde gebruikers en 1 gast

cron

Wie is er online?

Er is in totaal 1 gebruiker online :: 0 geregistreerd, 0 verborgen en 1 gast (Gebaseerd op de gebruikers die actief waren gedurende 5 minuten)
De meeste gebruikers ooit tegelijkertijd online was 649 op 31 Okt 2014, 18:45

Gebruikers in dit forum: Geen geregistreerde gebruikers en 1 gast
Copyright © 2009 Afterburner - Free GPL Template. All Rights Reserved.