Grote getallen en geheimschrift

Initialisatie

<<Graphics`Graphics`

frequencies={0.074,0.014,0.015,0.061,0.192,0.008,0.038,0.024,0.055,0.001,0.019,0.04,0.018,0.111,0.056,0.016,0,0.059,0.036,0.068,0.014,0.034,0.015,0.001,0.017,0.013};

gedicht={"ONZE BUURMAN BLEEF BEWEREN","DAT HY MATHEMATICI",
"NADER KON CLASSIFICEREN",
"IN DIVISIES EN WEL DRIE",
"",
"WELKE DRIE - KAN MEN NU WEL STELLEN -",
"ONDERSCHEIDDE DEZE MAN?",
"1. DE GROEP DIE GOED KAN TELLEN",
"2. DE GROEP DIE DAT NIET KAN"};

schuif[s_,n_]:=Module[{code,len,k},
code=ToCharacterCode[s];
len=Length[code];
For[k=1,k≤len,k++,
If[(code[[k]]≥65)&&(code[[k]]≤90),
code[[k]]=65+Mod[code[[k]]-65+n,26]
]
];
Return[FromCharacterCode[code]]
]

SetAttributes[schuif,Listable];

printgedicht[p_]:=Module[{len=Length[p],k},
For[k=1,k≤len,k++,Print[p[[k]]]
]
]

gecodeerdgedicht=schuif[gedicht,10];

rep[n_]:=(10^n-1)/9

eerstvolgendepriem[n_]:=Module[{x=n},
While[!PrimeQ[x],x++];
Return[x]
]

SetAttributes[mod,HoldAll]

mod[x_,m_]:=Module[{arg1},
arg1=ReleaseHold[Hold[x]/.Power->List];
If[Length[arg1]>1,
Return[PowerMod[arg1[[1]],arg1[[2]],m]],
Return[Mod[x,m]]
]
]

maaksleutel[e_,p_,q_]:=Module[{},
If[GCD[e,(p-1)*(q-1)]>1,
Print["Geen sleutel mogelijk, probeer andere waarde"];
Return[0]];
Return[PowerMod[e,-1,(p-1)*(q-1)]]
]

willekeuriggetal[n_]:=Random[Integer,{10^(n-1),10^n}]

willekeurigepriem[n_]:=eerstvolgendepriem[willekeuriggetal[n]]

tekstnaargetal[s_]:=FromDigits[ToCharacterCode[s],128]

getalnaartekst[n_]:=FromCharacterCode[IntegerDigits[n,128]]

ontbind[n_]:=Module[{fac,len,k,r,s},
Print["We gaan nu ",n," ontbinden"];
fac=FactorInteger[n];
len=Length[fac];
For[k=1,k≤len,k++,
For[r=1,r≤fac[[k,2]],r++,Print[fac[[k,1]]]
]
];
Return[fac];
]

Modulorekenen

n=rep[23]

mod[2^n,n]

Magische exponenten

Als je een getal eerst tot de zevende macht verheft modulo 111 en daarna tot de 31-e macht dan krijg je altijd het oorspronkelijke getal weer terug.

a=43

b=mod[a^7,111]

mod[b^31,111]

We noemen 31 het magische getal
 dat bij 7 en 111 hoort.

Dit kan ook met heel grote getallen. In de praktijk kiest men twee grote priemgetallen en vermenigvuldigt ze, we krijgen dan een getal dat we n noemen

p=willekeurigepriem[10]
q=willekeurigepriem[10]
n=p*q

Kies nu zelf een macht

openbaar=401

Het magische getal wordt dan

magic=maaksleutel[openbaar,p,q]

Print["We hebben dus: n = ",n,"   openbaar = ",openbaar,"    magic = ",magic]

En het werkt weer:

a=123456789

b=mod[a^openbaar,n]

mod[b^magic,n]

Public Key Cryptografie

We gaan dit idee gebruiken om berichten te versturen!! en te ontvangen!!

p=willekeurigepriem[50]
q=willekeurigepriem[50]
n=p*q

We kiezen de publieke sleutel.

openbaar=101

Vervolgens maken we de magische (geheime) sleutel.

magic=maaksleutel[openbaar,p,q]

De priemgetallen hebben we nu niet meer nodig.
Alleen maar de getallen:  n  openbaar  magic 
De eerste twee stuurt u naar uw kennissen, de laatste bewaart u zorgvuldig

Stel een kennis, genaamd Alice, wil u uitnodigen met de mededeling:
    
Vanavond eten wij spruitjes

Eerst maakt Alice er een getal van:

bericht=tekstnaargetal["Vanavond eten wij spruitjes"]

Dat bericht kan ook weer heel snel ontcijferd worden:

getalnaartekst[bericht]

Zo kan Alice het bericht dus niet op internet versturen. Eerst versleutelt zij het bericht met de publieke sleutel.

codebericht=mod[(bericht^openbaar),n]

Dit getal kan Alice rustig het internet op sturen omdat het onleesbaar is geworden. Immers

getalnaartekst[codebericht]

U ontvangt het gecodeerde bericht en u gebruikt nu de geheime sleutel om te decoderen

gedecodeerd=mod[(codebericht^magic),n]

Dit getal geeft het bericht van Alice weer terug

getalnaartekst[gedecodeerd]

Hoe kan een afluisteraar het bericht ontcijferen? Hij kent alleen maar de getallen publiek en n. De enige manier om hieruit magic te berekenen is als de afluisteraar de factoren p en q van n kent. En daar zit nou juist het probleem, grote getallen zijn practisch niet te ontbinden!!

We noemen bovenstaande procedure RSA-cryptografie, naar de uitvinders Rivest-Shamir-Adleman.

Natuurlijk hoef je je geen zorgen te maken over het uitrekenen van priemgetallen en machtverheffingen. Dit gebeurt allemaal met standaard software die op de achtergrond werkt.

Ontbinden van getallen

n=willekeurigepriem[20]

n=rep[37]

n=101433121

mod[13^n,n]

ontbind[n];

n=willekeuriggetal[40]

ontbind[n];

p=willekeurigepriem[30]
q=willekeurigepriem[30]

n=p*q

ontbind[n].