1. Inleiding

Deze webpagina en de MCR-software zijn ontwikkeld voor gebruik bij het boek Elementaire Getaltheorie en Asymmetrische Cryptografie door Benne de Weger (Epsilon-Uitgaven deel 63, Utrecht, 1e druk: juli 2009, 2e druk: eind 2010, ISBN 978-90-5041-108-0), maar kunnen natuurlijk ook los van dit boek gebruikt worden.

In de eerste plaats bevat deze webpagina een modulaire rekenmachine, een (priem)getalfabriek en een tekst-getal-omzetter. Daarmee kunt u onder andere: Bij diverse voorbeelden en opgaven in het boek staat het icoontje van een computer afgebeeld. Bij die voorbeelden en opgaven kunt u nuttig gebruik maken van deze software, met name van de modulaire rekenmachine.

De software biedt alle bouwstenen die u nodig hebt om zelf enkele cryptografische algoritmen uit te kunnen voeren. Zo kunt u bijvoorbeeld, door dit programma op de goede manier te gebruiken, de volgende dingen doen: Dat gaat allemaal niet vanzelf. U moet de wiskunde achter RSA en Diffie-Hellman eerst bestudeerd hebben, en u moet er wel goed bij nadenken om de juiste stappen te zetten.

Komt u er niet uit, dan kunt u inspiratie opdoen bij een aantal gebruiksvoorbeelden.

De publieke RSA- en Diffie-Hellman-sleutels die u met dit programma maakt kunt u opslaan in bestanden, en dan uitwisselen met anderen die met hetzelfde programma kunnen omgaan. Gebruik hiervoor bijvoorbeeld e-mail of een chat-programma. Zo kunt u behoorlijk veilig korte berichten uitwisselen.

In de tweede plaats bevat de software drie onderdelen waarmee u enkele andere getaltheoretische algoritmen uit het boek stap voor stap kunt doorlopen. Het gaat om: Deze onderdelen kunt u bij het bestuderen van de theorie gebruiken om de werking van deze algoritmen voor uzelf te demonstreren. Ook deze onderdelen kunnen grote getallen van honderden cijfers makkelijk aan.

2. Handleiding (invul)velden

De invulvelden kunt u bewerken zoals in een gewone editor. Klik in een veld, let op de cursor, en typ cijfers of letters.

U kunt "copy-en-paste" met de muis gebruiken om een getal van het ene veld naar het andere te kopiëren. Dat gaat als volgt:
Ook kunt u geselecteerde stukken kopiëren (CTRL-C), knippen (CTRL-X) en plakken (CTRL-V), en kunt u het hele veld selecteren (CTRL-A, of dubbelklik).
Er zijn ook velden waar alleen het programma iets kan zetten. In die velden kunt u niet editen, wel kunt u het hele veld selecteren (CTRL-A, of dubbelklik) en kopiëren (CTRL-C).

U kunt op deze manier met (CTRL-A), (CTRL-C), (CTRL-V) en (CTRL-X) de inhoud van het ene veld naar het andere transporteren. Ook kunt u zo de inhoud verplaatsen van en naar een ander programma, zoals een tekstverwerker, een e-mail-programma of een chatprogramma.

Om getallen tijdelijk op te kunnen slaan bevat het programma een "kladblok", waar u met een enkele muisbeweging getallen naar toe kunt verplaatsen of vandaan kunt halen.
De inhoud van het kladblok kunt u, gedeeltelijk of geheel, ook meteen naar een bestand schrijven, of uit een bestand inlezen.
Deze bestanden gebruiken een voor deze software specifiek formaat. Op die manier kunt u de inhoud (tijdelijk of permanent) bewaren, of uitwisselen met anderen die ook de MCR-software (in de vorm van een applet of van een java application) gebruiken.

Als de inhoud te groot is om in een veld te passen, dan hoeft u niet bang te zijn dat de computer het onzichtbare deel vergeten is. U krijgt de inhoud alleen niet helemaal te zien. Het verborgen deel kunt u te zien krijgen door met de pijltjestoetsen (of met HOME of END) de cursor in het veld ver genoeg naar links of rechts te bewegen.

3. De Modulaire Rekenmachine

Met de Modulaire Rekenmachine kunt u modulair rekenen (modulo m), en u kunt er ook gewoon (niet-modulair) mee rekenen, maar alleen met gehele getallen. U kunt behoorlijk grote getallen gebruiken, zeker tot enkele honderden cijfers groot.

niet modulairmodulair (mod m)




+
optellen: c = a + b ca + b (mod m)
-
aftrekken: c = a - b ca - b (mod m)
×
vermenigvuldigen: c = a × b ca × b (mod m)
/
delen: c = gehele deel van a / b ca b-1 (mod m)
rest
rest bij deling: c = rest van a / b
ggd
grootste gemene deler: c = ggd(a,b)
wortel
wortel: c = gehele deel van wortel(a)
^
machtsverheffen: cab (mod m)
mod m
reduceren:
als alleen a ingevuld:
ca (mod m);
als a en b ingevuld:
a wordt a (mod m),
b wordt b (mod m)

De invulvelden a, b en m kunt u zelf bewerken zoals in een gewone editor. Het antwoord van een berekening komt in het veld c. In het veld c kan alleen het programma schrijven.
Als u modulair rekent, moet de modulus m positief zijn.
Een modulaire inverse kunt u op twee manieren berekenen: als 1 / a (mod m), en als a-1 (mod m).

wis
   Klik hierop om alle velden te wissen.

4. Het Kladblok

Het kladblok kunt u gebruiken om getallen of teksten tijdelijk in op te slaan. Er zijn tien velden beschikbaar. U kunt er naartoe en vanuit kopiëren op de hier boven beschreven manieren.
De velden kunnen een label hebben (bv. "p ="). Daar zijn suggesties ingevuld voor wat u in het veld zou kunnen bewaren. Maar u hoeft zich van die labels niets aan te trekken.
Ook hebben de velden elk een selectievakje. Ze geven aan welke velden weggeschreven dan wel ingelezen worden.
Met de knoppen "publiek", "prive", "bericht", "RSA" en "DH" worden bepaalde velden geselecteerd, volgens onderstaande tabel. Maar u kunt ze ook met de hand aan of uit zetten, naar behoefte.
RSADHbericht
labelpubliekprivelabelpubliekprivelabelpubliekprive









pp
qg
nx
fiy
es
d
dp
dq
BBB
GGG

Als u DH selecteert verschijnt er ook een keuzelijst "parameters" waarmee u de grootte van ingeprogrammeerde DH-systeemparameters p, g kunt zetten, die worden dan in de juiste velden klaargezet. U kunt natuurlijk altijd uw eigengekozen DH-systeemparameters gebruiken, als u dat wilt.

In alle velden van het kladblok kunt u ook met de hand editen, kopiëren, knippen en plakken, en met de muis kopiëren.

schrijf weg
   Alle gegevens uit de aangevinkte velden in het kladblok worden naar een bestand geschreven.
lees in
   Gegevens uit een bestand worden ingelezen in de aangevinkte velden in het kladblok.
wis
   Klik hierop om alle velden van het kladblok te wissen.

5. De (Priem)getallenfabriek

Met de (Priem)getallenfabriek kunt u willekeurige oneven getallen maken, en ook willekeurige priemgetallen, tot een grootte van 400 cijfers.

Geef het aantal cijfers op dat het te maken getal groot moet zijn, tenminste 1 cijfer, en ten hoogste 400.

maak willekeurig oneven getal
   Maak een willekeurig oneven getal. Dit moet razendsnel gaan, ook voor hele grote getallen.
maak willekeurig priemgetal
   Maak een willekeurig (oneven) priemgetal. Dit kan enige seconden tot enige minuten duren, zeker voor grote priemgetallen. De rekentijd hangt niet alleen van het aantal opgegeven cijfers en de snelheid van uw computer af, ook voor een vast aantal cijfers en op een vaste computer kan de rekentijd sterk variëren.
zoek volgende priemgetal
   Als er een getal in het veld (priem)getal staat, dan wordt dit vervangen door het eerstvolgende priemgetal. Ook dit kan even duren.
wis
   Klik hierop om alle velden te wissen.

6. De Tekst-Getal-omzetter

Met de Tekst-Getal-omzetter kunt u korte leesbare teksten in getallen omzetten volgens de onderstaande tabel, en omgekeerd getallen in teksten omzetten.

lettergetal lettergetal lettergetal lettergetal cijfergetal symboolgetal












a10 n23 A40 N53 070   (spatie)80
b11 o24 B41 O54 171 , (komma)81
c12 p25 C42 P55 272 . (punt)82
d13 q26 D43 Q56 373 ! (uitroepteken)83
e14 r27 E44 R57 474 ? (vraagteken)84
f15 s28 F45 S58 575 ( (haakje openen)85
g16 t29 G46 T59 676 ) (haakje sluiten)86
h17 u30 H47 U60 777 - (min)87
i18 v31 I48 V61 878 + (plus)88
j19 w32 J49 W62 979 = (is)89
k20 x33 K50 X63
l21 y34 L51 Y64
m22 z35 M52 Z65

Andere tekens zijn niet toegestaan.
Voorbeeld: "Hallo daar!" wordt "4710212124801310102783".
Ook kunt u terug: een getal kunt u weer omzetten naar de tekst. Alle hierboven niet-genoemde combinaties van twee cijfers (00-09, 36-39, 66-69, 90-99) worden teruggezet naar spaties. Van een getal met een oneven aantal cijfers wordt het eerste cijfer genegeerd.

v v v tekst ==> getal v v v
   Zet de tekst in het bovenste invulveld om in een getal, dat in het onderste invulveld getoond wordt.
^ ^ ^ getal ==> tekst ^ ^ ^
   Zet het getal in het onderste invulveld om in een tekst, die in het bovenste invulveld getoond wordt.
wis
   Klik hierop om alle velden te wissen.

7. Euclides

Met Euclides kunt u stap voor stap door het (uitgebreide) algoritme van Euclides lopen.
Het gewone algoritme van Euclides berekent voor gegeven a en b de grootste gemene deler ggd(a,b). Het uitgebreide algoritme van Euclides berekent naast ggd(a,b) ook u en v zodat ggd(a,b) = u x a + v x b.

Voer getallen in in de velden voor a en b, en druk op start.
Het uitgebreide algoritme van Euclides wordt stap voor stap uitgevoerd door telkens op volgende te drukken. De (nog resterende) stappen kunnen ook in één keer worden uitgevoerd door op antwoord te drukken. Het programma meldt het als de berekening klaar is, en vermeldt het aantal uitgevoerde stappen.

start
   Het algoritme wordt gestart.
volgende
   Een volgende stap van het algoritme wordt uitgevoerd.
antwoord
   Alle (volgende) stappen van het algoritme worden in één keer uitgevoerd.
wis
   Klik hierop om alle velden te wissen.

8. Miller

Met Miller kunt u stap voor stap door de priemtest van Miller lopen.

Voer een getal m in waarvan u wilt weten of het vermoedelijk priem is of samengesteld.
Voer ook een grondtal a in waarmee u de priemtest van Miller wilt uitvoeren.
Door telkens op volgende te drukken wordt de priemtest stap voor stap uitgevoerd.

voer m in
   Van de ingevulde waarde voor m worden de s, t berekend zodat m-1 = 2s x t, met oneven t.
voer a in
   Het algoritme wordt gestart met het ingevoerde grondtal. Telkens worden twee opeenvolgende machten van at getoond.
volgende
   Een volgende stap van het algoritme wordt uitgevoerd.
nieuwe a
   U krijgt gelegenheid een nieuwe a in te voeren, bij dezelfde m.
nieuwe m
   U krijgt gelegenheid een nieuwe m in te voeren.
wis
   Klik hierop om alle velden te wissen.

9. De Chinese Reststelling

Met het onderdeel Chinese Reststelling kunt u een stelsel congruentievergelijkingen oplossen.

U moet eerst aangeven hoeveel vergelijkingen uw stelsel heeft. Dat aantal moet minstens 2 en hoogstens 8 zijn.
Dan voert u getallen bi en moduli mi in, om het stelsel xbi (mod mi) (i = 1, 2, ...) aan te geven.
De moduli moeten allemaal positief en relatief priem zijn. Als dat niet zo is geeft het programma de eerste modulus aan die een probleem heeft.
Het antwoord komt in de vorm van een congruentie x (mod m), waarbij m het product van de moduli mi is. U krijgt ook tussenresultaten te zien: Mi is het product van alle moduli behalve mi, en yiMi-1 (mod mi).

los op
   Los het ingevoerde stelsel op.
wis
   Klik hierop om alle velden te wissen.