1. Priemgetallen, de basis van moderne cryptografie

Ieder getal is te ontbinden in priemfactoren. Dit kun je zien als een unieke combinatie. Er is voor ieder getal maar één combinatie van priemfactoren. Priemfactoren zijn priemgetallen die je met elkaar vermenigvuldigt.
Neem bijvoorbeeld 33. Dit is te ontbinden in 3 x 11. Of 24 is te ontbinden in 3 x 2 x 2 x 2

2. Een public en private key

In het filmpje wordt eerst het begin van het internet enigzins uitgelegd en hoe het netwerk is ontstaan. Vervolgens wordt de noodzaak aangegeven om geheime informatie te verzenden zonder de key mee te sturen. Hiervan wordt een voorbeeld gegeven met kleuren. Stel dat er een (kleuren) boodschap moet worden gegeven met wit. Alice en Bob spreken een publieke kleur af. Deze wordt geel. Vervolgens kiezen beiden een geheime kleur uit en mixen deze met het geel en wit. Er ontstaan twee verschillende kleuren. Alice stuurt haar mix op (wat wordt onderschept door Eve maar dat is niet erg). Bob doet hetzelfde. Nu voegen beiden hun geheime kleur toe en wat gebeurt er? Er ontstaat één gezamelijke kleur. Alice en Bob hebben nu dezelfde boodschap.
Het mixen van deze kleuren is gemakkelijk. Het is echter onmogelijk de oorspronkelijke kleuren terug te krijgen. We noemen dit een one-way-function.

3. Modulo rekenen

Modulo rekenen gaat als volgt:

Het getal 3 past 3 keer in 10 en dan hou je 1 over. Dus 10 mod 3 is 1. 28 mod 5 is 3 omdat 5 x 5 = 25 en 28-25=3. Het getal 5 wordt de modulus genoemd. Bij modulo rekenen gaat het alleen om gehele getallen. Modulo rekenen wordt ook wel klokrekenen genoemd.

Je kunt modulo rekenen ook op machten toepassen. 2^6 mod 5 = 4 omdat 2x2x2x2x2x2=64/5=12 rest 4. De macht 6 is nu het geheime getal. Het is lastiger om 2 ^ ? mod 5 = 2 terug te rekenen naar 6.Hoe groter het geheime getal, hoe lastiger het wordt.

4. Het Diffie Hellman uitwisselingsprotocol

Het diffie-hellman-sleuteluitwisselingsprotocol is een cryptografisch protocol, waarmee twee deelnemers een geheime encryptiesleutel kunnen uitwisselen, die daarna kan worden gebruikt om communicatie tussen de deelnemers te versleutelen. Het werkt als volgt:

Alice kiest drie getallen:

priemgetal p = 13
grondgetal g = 6 (geen priemgetal)
geheim getal a = 3

Normaal gesproken zijn deze getallen veel groter maar voor het voorbeeld kiezen we express kleine getallen.

Vervolgens past Alice de volgende berekening toe:

getal A = g^a mod p

Dat is dus: 6 x 6 x 6 = 216 mod 13 = 8

Alice stuurt nu het priemgetal p, het basisgetal g en getal A naar Bob.

Bob kiest nu eerst een geheim getal:

geheim getal b = 5

En voert vervolgens de volgende berekening uit:

getal B = g^b mod p

Dat is dus: (6 x 6 x 6 x 6 x 6) mod 13 = 2

Nu zijn zij in staat om een gezamelijke key te bepalen die gebruikt kan worden als key.

Key van Alice = (A^b) mod p = 8

Key va Bob = (B^a) mod p = 8

De key kan nu ook binair worden gemaakt: 0100 voor bijvoorbeeld toepassing met een XOR-tabel. Bij groter getallen wordt de key groter.

5. Het RSA algoritme, deel 1

Om een bericht van Alice naar Bob te versturen is het nodig dat Alice en Bob identieke keys hebben. Zij kunnen deze verkrijgen door middel van het Diffie-Helman protocol. Hiermee is het dus niet nodig om de key zelf te versturen. Er ontstaat echter een probleem als Alice een bank is en verschillende keys moet sturen aan Bob, Charlie, Dick of Lora. Om dit te kunnen managen moet Alice vele duizenden berichten sturen.
We geven weer het voorbeeld met kleuren. Alice produceert eerst (random) een kleur, bijvoorbeeld rood. Vervolgens mixt ze deze kleur met een geheime kleur. De mix stuurt ze naar Bob, bijvoorbeeld cyaan. Bob heeft een bericht, geel, en mixt dit met cyaan en stuurt dit vervolgens terug naar Alice. Alice' geheime kleur rood maakt hier weer geel van. De uitdaging is om dit wiskundig te vinden.

6. Het RSA algoritme, deel 2

De wiskundige Clifford Cocks probeerde een wiskundige functie te maken die de "trapdoor one-way" functie wordt genoemd. Trapdoor (valkuil) omdat je het makkelijk in een richting kunt berekenen maar niet of erg moeilijk weer terug tenzij je speciale informatie hebt die de trapdoor wordt genoemd.
Het werkt als volgt. Stel dat Bob een bericht heeft in de vorm van een cijfer, genaamd m van message. Hij vermenigvuldigd dat een aantal keren. "Een aantal keren" noemen we e van exponent. Vervolgens neemt hij een random cijfer N en neemt dat als modulus. .
Dus bijvoorbeeld:
7^3 mod 5 = 7 * 7 * 7 = 343 mod 5 = 3. De uitkomst noemen we c. Dit is makkelijk te berekenen. Stel dat we alleen het getal c (7), het getal e (3) en N (3). Hoe kun je dan m weer berekenen? We zullen dit aantonen in de vorm van een opdracht.

7. Het RSA algoritme, deel 3

Stel dat we twee cijfers hebben, P1 en P2. Deze twee cijfers produceren een getal wat meer dan 300 cijfers lang is. Het berekenen van een dergelijk getal neemt niet meer dan een seconde zolang je maar een goede rekenmachine of computer hebt.
Kun je ook terug? Kun je de cijfers P1 en P2 weer terug rekenen? Jazeker, maar het is moeilijk. We zullen dat aantonen met een opdracht. Bekijk eerst het filmpje.

8. De grootste gemene deler

Om Eulers phi-functie te begrijpen zullen we eerst 2 onderwerpen behandelen. De grootste gemene deler en relatief priem.

Wat zijn de delers van 12? Deze zijn 1, 2, 3, 4, 6, 12. Wat zijn de delers van 30?. Deze zijn 1, 2, 3, 5, 6, 10, 15, 30. Het getal 12 en 30 hebben gemeenschappelijke delers. Deze zijn. 1, 2, 3 en 6 (ga dit na!). We zeggen nu dat de grootste gemene deler van 12 en 30 is 6. We schrijven dit als volgt op: ggd(12,30) = 6.

De grootste gemene deler is ook met priemfactoren te berekenen.
priemfactoren van 12: 2x2x3
priemfactoren van 30: 2x3x5

Je kunt nu kijken naar de gelijke priemfactoren.
priemfactoren van 12: 2x2x3
priemfactoren van 30: 2x3x5

2x3 is precies 6. Dat hadden we ook al handmatig gevonden.

Nog een voorbeeld:
priemfactoren van 64: 2x2x2x2x2x2
priemfactoren van 72: 2x2x2x3x3

De gelijke priemfactoren zijn 2x2x2 dus ggd(64,72)=8.

9. Relatief priem

Twee gehele getallen worden ten opzichte van elkaar relatief priem wanneer er geen positief geheel getal groter dan 1 bestaat dat beide getallen deelt.

Het is vrij simpel om te bepalen of twee getallen relatief priem zijn namelijk ggd(x,y)=1. De grootste gemene deler van die twee getallen is 1.
Neem de getallen 6 en 35.
priemfactoren van 6: 2x3
priemfactoren van 35: 5x7

Deze hebben geen gezamelijke priemfactoren dus ggd(6,35)=1 en we zeggen dan dat deze getallen relatief priem zijn.

10. Eulers phi-functie

In de getaltheorie is de indicator of qotiënt van een positief natuurlijk getal n, genoteerd als φ(n) (spreek uit phi-n), het aantal positieve natuurlijke getallen kleiner dan of gelijk aan n die onderling ondeelbaar zijn met n.

φ(8) = 4. Waarom?

We berekenen dit als volgt. We kijken eerst naar alle getallen die kleiner of gelijk zijn aan n. Dit zijn de getallen 1 t/m 8. Nu gaan we kijken welke getallen ggd(x,8)=1 waarbij x staat voor alle getallen kleiner of gelijk aan n.

We vinden hierbij de volgende uitkomsten

ggd(1,8)=1
ggd(2,8)=2
ggd(3,8)=1
ggd(4,8)=4
ggd(5,8)=1
ggd(6,8)=2
ggd(7,8)=1

We vinden nu de getallen 1,3,5,7 omdat al deze getallen ggd(x,8)=1 opleveren. We zeggen nu φ(8)=4 en we noemen dit een indicator. Deze indicator wordt veelal in verband gebracht met de Zwitserse wiskundige Leonhard Euler, die deze functie uitgebreid bestudeerde.

Wat gebeurt er nu als we voor n een priemgetal invullen? Wat is bijvoorbeeld φ (13)? Kijk hiervoor eerst het filmpje en maak dan de opdracht hierover.

11. Het RSA algoritme

public key

Alice, de ontvangster, moet een public key maken. Zij kiest 2 priemgetallen: p en q. Ze maakt daar het getal n van door n=pq toe te passen. Ze kiest ook nog een getal k wat als voorwaarde heeft dat het relatief priem moet zijn met φ(n).
Dus bijvoorbeeld:
p=3
q=11
n=pq=33

φ(n) = phi(p-1)(q-1) = 20 (zie deel 10 hoe je dit uitrekent)

Nu moet ze een getal e kiezen wat relatief priem is met 20. Dat kan bijvoorbeeld 3 zijn.

We zeggen nu dat de public key (n,e) wordt dus (33,3). Alice publiceert deze key ergens op internet, voor iedereen te lezen.

private key

Alice maakt ook een private key. Om een private key te kunnen maken moeten we zeker weten dat we kunnen modulo rekenen (zie lesonderdeel 3).
De berekening van d is als volgt

ed mod (p − 1)(q − 1) = 1 .

Als we hiervoor getallen gaan invullen dan krijgen we:

(3 * d) mod 20 = 1

We kunnen nu zien dat d=7 want 21 mod 20 = 1.

We zeggen nu dat de private key = (33,7). De getallen p en q worden nu vernietigd.

versleuteling

Stel dat dat de message 4 is. De formule voor het versleutelen is

m^e mod n

Kan Bob nu een message naar Alice versleutelen? Jazeker. Dat doet hij met de volgende berekening.

4³=4x4x4=64

64 mod 33 = 31

De vercijferde tekst is dus 31. We zeggen c (crypted) = 31. Bob stuurt dit op naar Alice. Alice is de enige die dit met haar private key kan ontcijferen.