Cryptografie – peterypma.nl

Toetsen cryptografie

Op deze pagina vind je de uitwerkingen van de oefentoets die je hier kunt downloaden. Op de volgende pagina staan oude toetsen die ik in het verleden gegeven heb.

Opdracht 1: (Python, 4 punten)
Als input krijg je op de eerste regel een $x$ -coördinaat en op de tweede regel een $y$ -coördinaat. Beide inputs zijn gehele getallen ongelijk aan nul. Als output moet je geven in welk kwadrant het punt met dit $x$ – en $y$ -coördinaat zit. In het diagram hieronder zie je welke kwadranten er zijn.
Voorbeeld input:
3
-4
Voorbeeld output:
4

Uitwerking:

Een voorbeeld van een correct antwoord is:

x = int(input())
y = int(input())
if x>0 and y>0:
    print(1)
elif x<0 and y>0:
    print(2)
elif x<0 and y<0:
    print(3)
else:
    print(4)

Dit kun je ook met geneste if-statements doen:

x = int(input())
y = int(input())
if x>0:
    if y>0:
        print(1)
    else:
        print(4)
else:
    if y>0:
        print(2)
    else:
        print(3)

De punten krijg je voor de volgende elementen:

Punt 1: Het correct inlezen van de input en deze omzetten naar integers.
Punt 2: De juiste syntax bij if-statements (denk aan: eindig met dubbele punt, ingesprongen regels, etcetera).
Punt 3: Correcte output van 1 als de input in kwadrant 1 zit.
Punt 4: De andere kwadranten zijn allemaal ook correct gedaan.

Je kunt een ander antwoord controleren bij de opdracht Quadrant selection op Kattis.

Opdracht 2: (Python, 4 punten)
Als input krijg je een getal van precies zeven cijfers. Als output moet je 1 geven als dit getal begint met 555. Als output moet je 0 geven in alle andere gevallen.
Voorbeeld input:
5552314
Voorbeeld output:
1

Uitwerking:

Je kunt dit op twee manieren oplossen. De meest voorkomende manier is om eerst te delen door 10000 (naar beneden afgerond) om alleen de eerste drie cijfers over te houden en dan te controleren of dit getal 555 is.

getal = int(input())
eerste3 = getal // 10000
if eerste3 == 555:
    print(1)
else:
    print(0)

Een alternatieve manier is om te controleren of het begingetal tussen (en met) 5550000 en 5559999 zit. Een manier om dit te programmeren is als volgt:

getal = int(input())
if getal >= 5550000 and getal <= 5559999:
    print(1)
else:
    print(0)

Voor het eerste alternatief krijg je punten voor de volgende stappen:

Punt 1: Het idee dat je de laatste vier cijfers moet verwijderen.
Punt 2: Dit correct uitvoeren met // 10000
Punt 3: De correcte syntax bij het if-statement (let op ==, de dubbele punt en dat de volgende regel ingesprongen is)
Punt 4: Het programma geeft het juiste antwoord.

Voor het tweede alternatief krijg je de punten als volgt:

Punt 1: Het idee dat de input minstens 5550000 en maximaal 5559999 moet zijn.
Punt 2 en 3: Dit correct implementeren in een if-statement (met and en juiste syntax)
Punt 4: Het programma geeft het juiste antwoord.

Je kunt een ander antwoord controleren bij de opdracht FYI op Kattis.

Opdracht 3: (Python, 6 punten)
Op de eerste regel van de input staat een getal. Dit geeft het aantal getallen op de volgende regel aan (al deze getallen zijn geheel en gescheiden met een spatie). Als output moet je op de eerste regel het aantal getallen printen dat groter is dan alle vorige getallen in de rij. Op de tweede regel print je al deze getallen (die groter zijn dan alle vorige in de rij) van klein naar groot met steeds een spatie ertussen.
Voorbeeldinput:
9
3 5 2 6 1 4 8 7 9
Voorbeeldoutput:
5
3 5 6 8 9

Uitwerking:

Een voorbeeld van een goed antwoord is:

aantal = int(input())
getallen = input().split()
grootsteGetal = int(getallen[0])
antwoord1 = 1
antwoord2 = getallen[0]
for i in range(1, aantal):
    getal = int(getallen[i])
    if getal > grootsteGetal:
        antwoord1 += 1
        antwoord2 += " " + getallen[i]
        grootsteGetal = getal
print(antwoord1)
print(antwoord2)

Hierbij krijg je de punten als volgt:

Punt 1: Correct inlezen van de variabelen, waarbij je de getallen uit je array later nog omzet naar integers.
Punt 2: Je houdt correct bij wat het grootste getal is dat tot nu toe in de lijst voorgekomen is.
Punt 3: Je lijst begint met het eerste element van de lijst van de input. Dit element tel je ook mee bij het antwoord wat op de eerste regel van de output komt.
Punt 4: Je doet een for-loop waarin je met een if-statement controleert of alle getallen groter zijn dan de grootste die eerder in de lijst stond.
Punt 5: De for-loop en het if-statement hebben een correcte syntax.
Punt 6: Binnen het if-statement pas je de antwoorden op de juiste manier aan en je print deze op het eind van het programma op de juiste manier.

Bonus:
Dit probleem is geïnspireerd op de opdracht Greedily Increasing Subsequence op Kattis. Aangezien de getallen daar groot zijn en werken met grote strings langzaam is, wordt dit antwoord echter niet goed gerekend. Een snellere manier is om in een lijst bij te houden wat de antwoorden zijn. Daarvoor heb je echter wel een paar methodes nodig die je nog niet gehad hebt:

lijst.append(3)
Dit voegt het element 3 aan het einde van de lijst toe.
print(*lijst)
Het sterretje zorgt ervoor dat de lijst zonder [] en met alleen spaties tussen de elementen geprint wordt.

Als uitdaging kun je proberen of je hiermee het probleem op Kattis kunt oplossen. Een correcte oplossing staat hieronder.

Antwoord probleem Kattis:

aantal = int(input())
getallen = input().split()
grootsteGetal = int(getallen[0])
antwoord = [grootsteGetal]
for i in range(1, aantal):
    getal = int(getallen[i])
    if getal > grootsteGetal:
        antwoord.append(getal)
        grootsteGetal = getal
print(len(antwoord))
print(*antwoord)

Opdracht 4: (3 punten)
Bereken met het algoritme van Euclides de grootst gemene deler van 2796 en 3528.

Uitwerking:

Hieronder staat het algoritme van Euclides uitgewerkt. Merk op dat je gewoon de MOD-functie op de CASIO (onder OPTN -> Numeric) of de Remainder-functie op de TI (onder Math -> Num) kunt gebruiken voor de modulo berekeningen:

$\text{ggd}(2796,3528)=\text{ggd}(2796, 3528\text{ mod }2796)=\text{ggd}(2796, 732)$
$\text{ggd}(2796,732)=\text{ggd}(2796\text{ mod }732, 732)=\text{ggd}(600, 732)$
$\text{ggd}(600,732)=\text{ggd}(600, 732\text{ mod }600)=\text{ggd}(600, 132)$
$\text{ggd}(600, 132)=\text{ggd}(600\text{ mod }132, 132)=\text{ggd}(72, 132)$
$\text{ggd}(72, 132)=\text{ggd}(72, 132\text{ mod }72)=\text{ggd}(72, 60)$
$\text{ggd}(72, 60)=\text{ggd}(72\text{ mod }60, 60)=\text{ggd}(12, 60)$
$\text{ggd}(12, 60)=\text{ggd}(12, 60\text{ mod }12)=\text{ggd}(12, 0)=12$
Uit de bovenstaande rekenstappen volgt $\text{ggd}(2796,3528)=12$ .

De punten krijg je op de toets voor de volgende zaken:

Punt 1 krijg je voor het toepassen van de regel $\text{ggd}(a,b)=\text{ggd}(a \text{ mod } b,b)$ .
Punt 2 en 3 krijg je voor het proces correct doorlopen tot $\text{ggd}(2796,3528)=12$ . Bij het maken van één rekenfout of schrijffout krijg je hiervan nog één punt. Bij het maken van twee of meer rekenfouten krijg je hiervan geen enkel punt.

Opdracht 5: (3 punten)
Je wilt een RSA wachtwoordpaar $(d,e)$ maken en kiest hiervoor $p=29$ , $q=59$ en $e=5$ . Bereken de waarde van $d$ .

Uitwerking:

We hebben $\phi(N)=28\cdot 58=1624$ . We moeten nu $d$ zo berekenen dat $d\cdot 5\text{ mod } 1624 = 1$ . We zien dat $d=1625/5=325$ werkt (het is met zo’n kleine $e$ dus niet nodig om het algoritme van Euclides te gebruiken).

Je krijgt de punten voor de volgende stappen:

Het eerste punt voor het correct berekenen van $\phi(N)=1624$ .
Het tweede punt voor de observatie dat $d\cdot 5\text{ mod } 1624 = 1$ .
Het derde punt voor hieruit $d=325$ berekenen.

Opdracht 6: (3 punten)
In het jaar dat ik deze oefentoets maakte, zaten de volgende leerlingen in de wiskunde D-klas: Anne, Bart, Elis, Evan, Imre, Koen, Lars, Loek, Paul, Stef, Joris, Marte, Merel, Reyer, Roman, Yasin, Hannah, Jochem, Liesje, Marius, Nathan, Pepijn, Thomas, Eulalia, Florice, Kirstin, Maurits, Vivienne, Giamingga en Christiaan (geordend op lengte van naam en vervolgens op alfabet). Twee van deze namen zijn met dezelfde encryptiefunctie versleuteld die iedere letter telkens op dezelfde manier versleuteld. Uit de encryptiefunctie komt ABST en XAGAD. Welke namen zijn dit? Leg uit hoe je zeker kan weten dat er geen andere mogelijkheid is.

Uitwerking:

Er zijn maar twee vijfletterige namen waarvan de tweede en de vierde letter hetzelfde zijn. Dat zijn Merel en Reyer. Bij Reyer is de vijfde letter echter ook hetzelfde als de eerste letter. Dat is niet het geval bij XAGAD. Dit moet dus wel voor Merel staal. We weten dus dat ABST met een E begint. Dit moet dus Elis of Evan zijn. Aangezien Elis echter een l gemeenschappelijk heeft met Merel en er geen andere letters overeenkomen uit ABST en XAGAD moet het wel Evan zijn.

Je krijgt de punten voor de volgende stappen:

Punt 1 krijg je voor het hebben van de naam Merel.
Punt 2 krijg je voor het hebben van de naam Evan.
Punt 3 krijg je voor een sluitende uitleg dat het alleen deze twee namen kunnen zijn. De uitleg hierboven is een voorbeeld van een correcte uitleg.

Opdracht 7: (3 punten)
We ordenen alle positieve getallen in het 3-tallig stelsel die geen 2 bevatten van klein naar groot. Zet het honderste getal uit deze lijst om naar het tientallig stelsel. Geef dit getal en ligt toe hoe je hieraan komt.

Uitwerking:

Als je de lijst maakt, zie je dat dit precies de binaire getallen zijn. honderd in binair is 64+32+4 en dus 1100100. Dit weer terug omzetten naar het tientallig stelsel is $3^6+3^5+3^2=981$ .

De punten krijg je voor de volgende stappen:

Punt 1 krijg je voor als duidelijk uit je uitwerking te zien is dat je honderd moet omzetten naar een binair getal.
Punt 2 krijg je als je op het getal 1100100 uitkomt (als je dit anders doet dan met binaire getallen, krijg je punt 1 ook).
Punt 3 krijg je als je het gevonden getal in het drietallig stelsel weer correct omzet naar het tientallig stelsel.

Pagina's: 12

Cryptografie les 11: RSA

In de vorige les hebben we gezien dat het mogelijk is om een geheim wachtwoord af te spreken, terwijl anderen meeluisteren. Een vereiste van deze techniek is echter wel dat je een kanaal hebt waar je informatie kunt delen zonder dat iemand halverwege de berichten kan aanpassen (dat was de man in the middle attack die we vorige keer gezien hebben).

In deze les gaan we naar RSA kijken waarmee je zowel kunt zorgen dat voor iedereen duidelijk is dat het bericht van jou afkomstig is als dat je kunt zorgen dat het bericht alleen voor de ontvanger te lezen is.

Stelling van Euler

RSA maakt gebruik van de zogenaamde stelling van Euler. Deze stelling heeft te maken met de functie $\phi(n)$ die telt hoeveel getallen $m$ kleiner of gelijk dan $n$ er zijn waarvoor geldt $\text{ ggd }(m, n)=1$ . Zo is bijvoorbeeld $\phi(6)=2$ , want alleen voor 1 en 5 geldt dat $\text{ ggd }(6, 1)=\text{ ggd }(6, 5)=1$ .

Opdracht 1:
Bereken $\phi(n)$ voor $n=1$ t/m $n=10$ .

Uitwerking:

$\phi(1)=1$
$\phi(2)=1$
$\phi(3)=2$
$\phi(4)=2$
$\phi(5)=4$
$\phi(6)=2$
$\phi(7)=6$
$\phi(8)=4$
$\phi(9)=6$
$\phi(10)=4$

In de antwoorden van $\phi(n)$ zitten mooie patronen. Voor deze les is het alleen belangrijk om te weten wat $\phi(p)$ en $\phi(p\cdot q)$ is, waarbij zowel $p$ als $q$ priemgetallen zijn.

Opdracht 2:
a) Bereken $\phi(p)$ voor een aantal priemgetallen $p$ . Geef dan een formule voor $\phi(p)$ , waarbij je het antwoord uitdrukt in $p$ .
b) Bereken $\phi(2\cdot p)$ voor een aantal priemgetallen $p>2$ . Geef dan een formule voor $\phi(2\cdot p)$ , waarbij je het antwoord uitdrukt in $p$ .
c) Bereken $\phi(3\cdot p)$ voor een aantal priemgetallen $p>3$ . Geef dan een formule voor $\phi(3\cdot p)$ , waarbij je het antwoord uitdrukt in $p$ .
d) Probeer nu een algemeen formule te vinden voor $\phi(p\cdot q)$ voor verschillende priemgetallen $p$ en $q$ . Je kunt hierbij natuurlijk nog wat meer proberen.

Uitwerking a:

Voor een priemgetal $p$ geldt dat $\text{ ggd }(a,p)=1$ voor ieder getal $a<p$ . Dat geeft dus $\phi(p)=p-1$

Uitwerking b:

Bij het uitrekenen van een aantal voorbeelden ga je wellicht patronen zien:

$\phi(2\cdot 3) = 2 = \phi(3)$
$\phi(2\cdot 5) = 4 = \phi(5)$
$\phi(2\cdot 7) = 6 = \phi(7)$

Het antwoord lijkt dus ook hier $\phi(2\cdot p) = p-1$ te zijn. De reden is dat alle oneven getallen behalve $p$ kleiner dan $2p$ werken. Dat zijn er precies $p-1$ .

Uitwerking c:

Bij het uitrekenen van een aantal voorbeelden ga je wellicht patronen zien:

$\phi(3\cdot 5) = 8 = 2\cdot \phi(5)$
$\phi(3\cdot 7) = 12 = 2\cdot \phi(7)$
$\phi(3\cdot 11) = 20 =2\cdot \phi(11)$

Het antwoord lijkt hier dus $\phi(2\cdot p) = 2\cdot \phi(p)=2p-2$ te zijn. De reden is dat alle drievouden afvallen. Van de getallen die één meer dan een drievoud zijn, zijn er $p-1$ die ook geen factor $p$ hebben. Dat geldt ook voor de getallen die twee meer zijn dan een drievoud. Voor deze $2(p-1)$ getallen $m$ geldt dus $\text{ggd}(3p,m)=1$ .

Uitwerking d:

De formule is $\phi(p\cdot q)=(p-1)(q-1)$ . De reden is dat van de $pq-1$ tot en met $pq-1$ er $p-1$ deelbaar zijn door $q$ en $q-1$ deelbaar zijn door $p$ . Voor alle andere getallen $m$ geldt $\text{ggd}(pq,m)=1$ . Dat zijn er $\phi(p\cdot q)=pq-1-(p-1)-(q-1)=pq-p-q+1=(p-1)(q-1)=\phi(p)\cdot\phi(q)$ .

De formule $\phi(n)$ is voor ons heel nuttig, omdat Euler bewezen heeft dat $a^{\phi(n)} \text{ mod } n=1$ als $\text{ggd}(a,n)=1$ . Deze stelling die de stelling van Euler heet, zullen we in deze cursus niet bewijzen, maar alleen gebruiken.

Opdracht 3:
a) Controleer de formule van Euler door met je rekenmachine $5^{\phi(7)} \text{ mod } 7$ en $3^{\phi(8)} \text{ mod } 8$ .
b) Bereken ook $2^{\phi(12)} \text{ mod } 12$ . Leg uit waarom dit geen tegenspraak is voor de stelling van Euler.

Uitwerking a:

Als je het goed berekent hebt, krijg je $5^{\phi(7)} \text{ mod } 7=1$ en $3^{\phi(8)} \text{ mod } 8=1$ .

Uitwerking b:

$2^{\phi(12)} \text{ mod } 12=2^4 \text{ mod } 12=16\text{ mod } 12=4$
Dit is geen tegenspraak, omdat de stelling van Euler alleen geldt als $\text{ggd}(a,n)=1$ en dat is niet waar, omdat $\text{ggd}(2,12)=2$ .

Opdracht 4:
Maak de opdracht Euler’s Totient op CryptoHack. Je moet daarbij uitzoeken wat $\phi(857504083339712752489993810777\cdot 1029224947942998075080348647219$ is waarbij zowel 857504083339712752489993810777 als 1029224947942998075080348647219 priemgetallen zijn.

Hint:

We hebben in opdracht 2d geleerd dat $\phi(p\cdot q)=(p-1)(q-1)$ als $p$ en $q$ priemgetallen zijn.

Pagina's: 123

Cryptografie les 10: Diffie-Hellman

In de vorige les hebben we gezien dat we met XOR een bericht veilig kunnen versleutelen. Hiervoor moet je echter wel een zeer lange string van enen en nullen afgesproken hebben. In deze les gaan we zien hoe je zonder vooraf afgesproken string toch een geheime boodschap aan elkaar kan sturen. Hiervoor gaan we het zogenaam Diffie-Hellman protocol gebruiken. Dit maakt gebruik van het machtsverheffen van een grote klassen bij modulo rekenen. Daar gaan we op deze pagina daarom mee beginnen.

Modulair machtsverheffen

Als je modulo rekent, mag je op ieder moment een getal vervangen door een getal uit dezelfde moduloklassen. Zo hebben alle onderstaande sommen dezelfde uitkomst:

$13 \cdot 75 \text{ mod } 7$
$13 \cdot 5 \text{ mod } 7$
$6\cdot 5 \text{ mod } 7$

Deze truc kunnen we gebruiken door als we een grote som modulo een getal willen uitrekenen we ook steeds tussendoor de getallen kunnen verkleinen. Zo wordt $101\cdot 123\cdot 109 \text{ mod } 99$ na vereenvoudigen
$100\cdot 123\cdot 109 \text{ mod } 99 = 2\cdot 24\cdot 10\text{ mod } 99 = 480 \text{ mod } 99 = 84$ .

Opdracht 1:
a) Bereken uit je hoofd $14\cdot 27 \text{ mod } 11$ .
b) Bereken uit je hoofd $323572834723 \cdot 29387423 \cdot 23948123431 \text{ mod } 10$ .

Uitwerking a:

$14\cdot 27 \text{ mod } 11= 3\cdot 5 \text{ mod } 11 = 4$

Uitwerking b:

$323572834723 \cdot 29387423 \cdot 23948123431 \text{ mod } 10 = 3\cdot 3\cdot 1\text{ mod } 10 = 9$

Op de rekenmachine kun je ook modulo berekenen. Op de TI doe je dit met de Remainder-functie onder math->num->remainder (optie 0). Daarbij is remainder(5,2) hetzelfde als $5 \text{ mod } 2$ .
Op de CASIO (GR) kun je dit doen met OPTN -> NUMERIC -> pijltje naar rechts -> MOD.

De onderstaande opgave is te groot voor je rekenmachine om meteen uit te rekenen. Je kunt echter een paar slimme tussenstappen doen (op de manier uit opdracht 1) waarmee dat wel kan.

Opdracht 2:
Bereken $9^{256} \text{ mod } 103$ . Je mag een rekenmachine gebruiken, maar geen Python-programma.

Hint:

Bereken achtereenvolgens $9^2 \text{ mod } 103$ , $9^4 \text{ mod } 103$ , $9^8 \text{ mod } 103$ , $9^{16} \text{ mod } 103$ , enzovoorts. Hierbij kun je $9^{2n}\text{ mod } 103 = 9^n \cdot 9^n \text{ mod }103$ .

Uitwerking:

$9^2 \text{ mod } 103 = 9\cdot 9 \text{ mod 103} = 81$
$9^4 \text{ mod } 103 = 9^2\cdot 9^2 \text{ mod 103} = 81\cdot 81 \text{ mod 103} = 72$
$9^8 \text{ mod } 103 = 9^4\cdot 9^4 \text{ mod 103} = 72\cdot 72 \text{ mod 103} = 34$
$9^{16} \text{ mod } 103 = 9^8\cdot 9^8 \text{ mod 103} = 34\cdot 34 \text{ mod 103} = 23$
$9^{32} \text{ mod } 103 = 9^{16}\cdot 9^{16} \text{ mod 103} = 23\cdot 23 \text{ mod 103} = 14$
$9^{64} \text{ mod } 103 = 9^{32}\cdot 9^{32} \text{ mod 103} = 14\cdot 14 \text{ mod 103} = 93$
$9^{128} \text{ mod } 103 = 9^{64}\cdot 9^{64} \text{ mod 103} = 93\cdot 93 \text{ mod 103} = 100$
$9^{256} \text{ mod } 103 = 9^{128}\cdot 9^{128} \text{ mod 103} = 100\cdot 100 \text{ mod 103} = 9$

De methode die in de hint en uitwerking hierboven uitgevoerd wordt, kun je veralgemeniseren zodat hij voor iedere macht werkt. Daarbij schrijf je de macht eerst als een product van machten met een tweemacht als exponent. Dit kun je snel doen door 12 te schrijven als een som van tweemachten. Aangezien 12 gelijk is aan 8+4 geldt dus $3^{12} \text{ mod } 7 = 3^{8}\cdot 3^4 \text{ mod } 7$ . In het algemeen kun je de som van tweemachten vinden met behulp van de binaire schrijfwijze van 12 (1100 geeft dus aan dat $12 =8\cdot 1+4\cdot 1+2\cdot 0+1\cdot 0$ ).

Vervolgens reken je net als in opdracht 1 de machten uit met een tweemacht als exponent en vermenigvuldig je op het eind nog de juiste tweemachten. Dat ziet er bij $3^{12} \text{ mod } 7$ als volgt uit:

$3^{2} \text{ mod } 7 = 3\cdot 3 \text{ mod } 7 = 2$
$3^4 \text{ mod } 7 = 3^2\cdot 3^2 \text{ mod } 7 = 2\cdot 2 \text{ mod } 7 = 4$
$3^8 \text{ mod } 7 = 3^4\cdot 3^4 \text{ mod } 7 = 4\cdot 4 \text{ mod } 7 = 2$
$3^{12} \text{ mod } 7 = 3^8\cdot 3^4 \text{ mod } 7 = 2\cdot 4 \text{ mod } 7 = 1$

Opdracht 3:
a) Bereken met bovenstaand algoritme $7^{74} \text{ mod } 29$ . Je mag een rekenmachine gebruiken, maar geen Python-programma.
b) Waarom zul je met het bovenstaande algoritme wel $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999$ met Python kunnen uitrekenen, terwijl dit met herhaald vermenigvuldigen niet gaat?

Uitwerking a:

$7^{2} \text{ mod } 29 = 7\cdot 7 \text{ mod } 29 = 20$
$7^4 \text{ mod } 29 = 7^2\cdot 7^2 \text{ mod } 29 = 20\cdot 20 \text{ mod } 29 = 23$
$7^8 \text{ mod } 29 = 7^4\cdot 7^4 \text{ mod } 29 = 23\cdot 23 \text{ mod } 29 = 7$
$7^{16} \text{ mod } 29 = 7^8\cdot 7^8 \text{ mod } 29 = 7\cdot 7 \text{ mod } 29 = 20$
$7^{32} \text{ mod } 29 = 7^{16}\cdot 7^{16} \text{ mod } 29 = 20\cdot 20 \text{ mod } 29 = 23$
$7^{64} \text{ mod } 29 = 7^{32}\cdot 7^{32} \text{ mod } 29 = 23\cdot 23 \text{ mod } 29 = 7$
$7^{74} \text{ mod } 29 = 7^{64}\cdot 7^{8}\cdot 7^2\text{ mod } 29 = 7\cdot 7\cdot 20\text{ mod } 29 = 23$

Uitwerking b:

Het aantal keer dat je moet vermenigvuldigen is maximaal $2\cdot{}^2\!\text{log}(x)$ als $x$ de grootte van de exponent is. Dat zijn bij 1111111111111111111111777777755555333221 ongeveer 266 vermenigvuldigingen. Dat is goed te doen, terwijl 1111111111111111111111777777755555333221 keer vermenigvuldigen met 2 niet gaat lukken binnen realistische tijd.

De ingebouwde functie pow in Python rekent met het bovenstaande algoritme machten modulo een getal uit. Om $3^7\text{ mod } 37$ uit te rekenen, type je pow(3,7,37).

Opdracht 4:
Bereken $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999$

Kopieerbare versie van de getallen:

g = 2
exponent = 1111111111111111111111777777755555333221
moduloklasse = 1111111112223333333344455566777777779999

Uitwerking a:

Je kunt het volgende programma gebruiken:

print(pow(2,1111111111111111111111777777755555333221,1111111112223333333344455566777777779999))

Het antwoord is dus $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999 = 1021207380999906245135905479721960323317$

Bonusopdracht:
Schrijf een programma die zonder gebruik te maken van de pow-functie de som uit opdracht 4 berekent.

Hint 1:

Je wilt eigenlijk de exponent schrijven als een binair getal. Hier heb je in opdracht 12b van les 8 al een programma voor geschreven. Dit programma kun je als basis gebruiken.

Hint 2:

Als er een 1 staat op plaats $k$ van achteren in de binaire schrijfwijze van 1111111111111111111111777777755555333221 moet het antwoord vermenigvuldigd worden met een factor $2^{k}$ . Als er een 0 staat in de binaire schrijfwijze hoef je met niets te vermenigvuldigen.

Uitwerking:

Zie allereerst de hints hierboven. Bij iedere stap in het algoritme houden we bij wat $2^A\text{ mod } 1111111112223333333344455566777777779999$ is in de variabele macht. Bij de volgende stap kunnen we dan de nieuwe macht $2^{2A}$ berekenen met (macht*macht) % moduloklasse.
In het algoritme vermenigvuldigen we al deze machten die op een plek staan waar in de binaire schrijfwijze van de exponent 1111111111111111111111777777755555333221 een 1 staat.

g = 2
exponent = 1111111111111111111111777777755555333221
moduloklasse = 1111111112223333333344455566777777779999

antwoord = 1
macht = g
while exponent > 0:
    if exponent % 2 == 1:
        antwoord = antwoord * macht % moduloklasse
    macht = (macht * macht) % moduloklasse
    exponent //= 2
print(antwoord)

Het antwoord is dus $2^{1111111111111111111111777777755555333221} \text{ mod } 1111111112223333333344455566777777779999 = 1021207380999906245135905479721960323317$

Pagina's: 1234

Cryptografie les 9: XOR

In de vorige les hebben we binaire getallen geleerd. In deze les gaan we die toepassen om teksten te versleutelen die geheel veilig is, zolang je een lang genoeg wachtwoord van tevoren hebt afgesproken (wat je moet doen als je dit niet van tevoren hebt kunnen afspreken leren we komende lessen).

Schakelaar

Veel lampen werken met een schakelaar met een knop waarmee je de lamp aan of uit kunt zetten. Het elektrisch schema ziet er dan uit zoals in het plaatje hieronder.

Er zijn ook lampen die je met twee knoppen aan en uit kunt zetten. Dit noem je een hotelschakelaar. Bij veel huizen kan dit bijvoorbeeld met het ganglicht op de eerste verdieping. Er zit dan een knop op de begane grond en één op de eerste verdieping.

Opdracht 1:
a) Teken hoe het elektrisch schema van een hotelschakelaar eruit ziet.

Uitwerking:

De schakelaar ziet er zo uit:

In het schema hierboven zien we dat er alleen energie loopt als beide schakelingen op 0 staat of beide schakelingen op 1. Als 0 staat voor “licht aan” en 1 voor “licht uit” krijgen we dus de samenvoegingen die hieronder te zien zijn. Als symbool voor het op deze manier samenvoegen van twee getallen gebruiken we $\oplus$ (spreek uit: X-OR).

$0\oplus 0 = 0$
$0\oplus 1 = 1$
$1\oplus 0 = 1$
$1\oplus 1 = 0$

Bij versleutelingen gaan we dezelfde operatie gebruiken die we XOR noemen. Hierbij doen we de optelling componentsgewijs. Dat betekent dat we het eerste cijfer van het eerste getal XOR eerste cijfer van tweede getal en hetzelfde met de tweede cijfers, derde cijfers, enzovoort. Merk op dat dit alleen kan als de getallen evenveel cijfers hebben.

Opdracht 2:
a) Bereken $101\oplus 011$ .
b) Bereken $11010 \oplus 10100$

Uitwerking a:

Eerste cijfer: $1\oplus 0 = 1$
Tweede cijfer: $0\oplus 1 = 1$
Derde cijfer: $1\oplus 1 = 0$
In totaal krijgen we dus $101\oplus 011 = 110$ .

Uitwerking b:

Eerste cijfer: $1\oplus 1 = 0$
Tweede cijfer: $1\oplus 0 = 1$
Derde cijfer: $0\oplus 1 = 1$
Vierde cijfer: $1\oplus 0 = 1$
Vijfde cijfer: $0\oplus 0 = 0$
In totaal krijgen we dus $11010 \oplus 10100=01110$ .

Vaak zullen we in praktijk ook de $\oplus$ -operator tussen twee getallen van andere talstelsels dan binaire getallen zetten. In dat geval zet je de getallen eerst om naar binaire getallen, doe je dan XOR en zet je de getallen dan weer terug naar de getallen van het talstelsel van de oorspronkelijke getallen. Als de binaire getallen niet even lang zijn, zet je nullen voor het kortste binaire getal totdat ze wel even lang zijn.

Opdracht 3:
a) Bereken $37 \oplus 44$ .
b) Bereken $73 \oplus 23$ .

Uitwerking a:

37 is binair 100101
44 is binair 101100
$100101 \oplus 101100 = 001001$
1001 is in het tientallig stelsel het getal 9.

Uitwerking b:

73 is binair 1001001
23 is binair 0010111
$1001001 \oplus 0010111 = 1011110$
1011110 is in het tientallig stelsel het getal $64+16+8+4+2=94$ .

Er gebeurt iets bijzonders als je $(b\oplus a)\oplus a$ uitrekent.

Opdracht 4:
a) Bereken $(11011010\oplus 01010011)\oplus 01010011$ .
b) Wat is de uitkomst van $(b\oplus a)\oplus a$ ? Leg uit waarom dat altijd zo is.
c) Denk na waarom dit handig is voor het versleutelen van berichten.

Uitwerking a:

$(11011010\oplus 01010011)\oplus 01010011 = [latex]10001001 \oplus 01010011 = 11011010$

Uitwerking b:

Er geldt $(b\oplus a)\oplus a = b$ . Als een cijfer in $a$ 0 is, zal bij beide operaties er niets aan het cijfer van $b$ veranderen.
Als een cijfer in $a$ 1 is, zal bij beide operaties het cijfer van $b$ veranderen. Na twee keer veranderen is die dus weer hetzelfde.

Uitwerking c:

Als wij allebei dezelfde sleutel van enen en nullen hebben, kunnen we het volgende doen:

Jij doet $\text{versleutelde tekst}=\text{leesbare tekst} \oplus \text{sleutel}$ .
De versleutelde tekst stuur je naar mij op.
Ik doe $\text{leesbare tekst}=\text{versleutelde tekst} \oplus \text{sleutel}$ om het oorspronkelijke bericht weer leesbaar te krijgen.

Pagina's: 123

Cryptografie les 8: Binaire getallen

In de vorige les hebben we gezien dat het niet veilig is om iedere letter op dezelfde manier te versleutelen. We hebben dus een manier nodig hoe we letters op verschillende manieren kunnen versleutelen. In les 9 gaan we een van de belangrijke manieren hiervoor leren. Deze techniek maakt gebruik van het feit dat de computer letters en getallen opslaat als een binair getal. Daarom zullen we in deze les eerst uitgebreider naar binaire getallen kijken.

Getallenstelsels

Ik wil deze les starten met een antwoord van de Engelse onderzoekster Becky Allen op de vraag wat haar favoriete getal is:

I’m going to pick the number 10. 10 is the number that separates my youngest child who is four from my eldest who is eight, and it divides my oldest from me. You see, my youngest knows the number 10. He knows it is the one that comes after 9 and before 11. He can show it on his hands. But my oldest understands how special 10 is in our number system. She knows the 10ness of 10 and I think it is one of the most transformational things that happens around year 1 (groep 3) in the math curriculum. So, she thinks 10 is a really special number, however I know 10 is not intrinsically special and it is us as humans that have made it so.

Als je op het eind van deze les op de manier van Becky naar het getal 10 kijkt, is deze les geslaagd!

De reden dat 10 zo bijzonder voor ons voelt, is omdat wij rekenen in het decimale talstelsel (in simpeler Nederlands: tientallig stelsel). Dit betekent dat we 10 verschillende cijfers (0, 1, 2, 3, 4, 5, 6, 7, 8 en 9) hebben en dat we met de positie waarop deze cijfers staan, kunnen aangeven hoeveel we van iedere macht van 10 hebben. Zo betekent 3428 eigenlijk $3\cdot 10^3+4\cdot 10^2+2\cdot 10^1 + 8\cdot 10^0$ .

Er zijn volkeren geweest die vroeger met andere talstelsels gewerkt hebben, zoals een 12, 20 of 60-tallig stelsel.

Opdracht 1:
Aan wat voor dingen kun je nu nog zien dat er vroeger andere talstelsels gebruikt zijn?

Uitwerking:

Je ziet het 60-tallig stelsel bijvoorbeeld terug in dat er 60 minuten in een uur zitten en 60 seconden in een minuut. Ook bij hoeken zie je het 60-tallig stelsel terug. Op een wereldkaart is een graad nog altijd ingedeeld in 60 (graad-)minuten en een minuut weer in 60 seconden. Daarnaast komt de 360 graden van een mooi veelvoud van 60 waarbij een dag ongeveer een graad is.

Het 12-tallig stelsel zie je nog in woorden terug. Bijvoorbeeld in een dozijn (12 stuks) en een gros (een dozijn dozijnen, dus 144) en het feit dat er 24 uur in een dag zitten, heeft hier ook mee te maken (vroeger werden alleen de uren overdag geteld – toen zaten er dus 12 uren in een dag die niet allemaal even lang duurde). Ook twintig zie je nog wel in het taalgebruik terug. Zie bijvoorbeeld het Franse woord voor 80: quatre-vingts (letterlijk vier twintig

Opdracht 2:
De volgende getallen staan in het achttallig stelsel. Schrijf ze om naar het decimaal stelsel.
a) 53
b) 213
c) 1067

Uitwerking a:

53 in het achttallig stelsel is $5\cdot 8+3=43$ in het decimaal stelsel.

Uitwerking b:

213 in het achttallig stelsel is $2\cdot 8^2+1\cdot 8+3=139$ in het decimaal stelsel.

Uitwerking c:

1067 in het achttallig stelsel is $1\cdot 8^3+0\cdot 8^2+6\cdot 8+7=567$ in het decimaal stelsel.

Opdracht 3:
De volgende getallen staan in het decimaal stelsel. Schrijf ze om naar het achttallig stelsel.
a) 42
b) 67
c) 250

Uitwerking a:

$42 = 5\cdot 8+2$ . In het achttallig stelsel wordt het dus $52$ .

Uitwerking b:

$67 = 1\cdot 8^2+0\cdot 8+3$ . In het achttallig stelsel wordt het dus $103$ .

Uitwerking c:

$250 = 3\cdot 8^2+7\cdot 8+2$ . In het achttallig stelsel wordt het dus $372$ .

Als je een talstelsel gebruikt met meer dan 10 cijfers gebruiken we tegenwoordig vaak letters voor de volgende cijfers. Dus $A=10$ , $B=11$ , $C=12$ , enzovoort. In de tabel hieronder zie je de waarde van iedere letter.

Op die manier stelt iedere naam in het 36-tallig stelsel dus ook een getal voor die je kunt omrekenen naar onze normale getallen. Zo is het getal “AB” in het 36-tallig stelsel gelijk aan $10\cdot 36^1+11=371$ bij onze normale getallen. Dit, omdat de $A$ voor 10 staat en de $B$ voor 11 en we nu in plaats van tien 36 cijfers hebben (en dus moeten rekenen met machten van 36).

Opdracht 4:
a) Reken uit wat de naam “GIA” wordt als je die omzet van het 36-tallig stelsel naar het 10-tallig stelsel.
b) Schrijf een Python-programma dat een naam in het 36-tallig stelsel omzet naar het 10-tallig stelsel. Reken daarmee uit naar welk getal “VIVIENNE” wordt omgezet.

Uitwerking a:

De G heeft waarde 16, de I heeft waarde 18 en de A heeft waarde 10.
We krijgen dus $16\cdot 36^2+18\cdot 36+10=21394$ .

Uitwerking b:

De belangrijke stappen in het algoritme zijn:

Je moet de letters omzetten naar een getal. Eerder hebben we al gezien dat we van de ‘A’ een 0, ‘B’ een 1, ‘C’ een 2, enzovoort kunnen maken met ord(letter)-ord(“A”). Nu willen we dat ‘A’ een 10 is, ‘B’ een 11 is, enzovoort. We moeten dus om een letter om te zetten in zijn juiste waarde 10 bij dit getal optellen.
De waarde van de posities zijn van rechts naar links 1, 36, $36^2$ , $36^3$ , enzovoort. We moeten de waarde van de letters met die positiewaarde vermenigvuldigen. Dit kunnen we in deze volgorde doen door de letters van rechts naar links te lezen. Dat doet het onderstaande programma:

naam = "VIVIENNE"
getal = 0
for i in range(len(naam)):
    waardeletter = ord(naam[len(naam)-i-1]) - ord('A') + 10
    waardepositie = 36**i
    getal += waardeletter * waardepositie
print(getal)

Je kunt de loop ook over de letters van voor naar achter doen. Dan moet je bij iedere stap nadenken keer welke macht van 36 je moet doen. De eerste letter moet keer 36 tot de macht aantal letters min één. Iedere volgende letter moet een factor 36 minder hebben. Dit is in de code hieronder verwerkt.

naam = "VIVIENNE"
getal = 0
waarde = 36 ** (len(naam) - 1)
for letter in naam:
    getal += (ord(letter) - ord('A') + 10) * waarde
    waarde //= 36
print(getal)

De naam “VIVIENNE” wordt dus 2470376537402.
De truc van dit algoritme is dat je de waarde van iedere letter moet doen keer $36^{\text{hoeveel letters er nog komen}$ . Van de eerste letter is dat dus $36^{\text{aantal letters min één}$ en voor iedere volgende letter is dat een factor 36 minder.

Opdracht 5:
a) Ik heb ooit een T-shirt gekregen met het getal 42681699 erop (zie de afbeelding). De bedoeling van de gevers was dat dit getal omgezet moet worden naar het 36-tallig stelsel. Welke tekst staat er eigenlijk achterop mijn T-shirt?

Uitwerking:

We zien dat $42681699 \text{//} 36^4 = 25$ . De eerste letter is dus een $P$ .
Er is dan nog $42681699-25\cdot 36^4 =691299$ over. Er geldt $621299 \text{//} 36^3 = 14$ . De tweede letter is dus een $E$ .
Er is dan nog $621299-14\cdot 36^3=38115$ over. Er geldt $38115 \text{//} 36^2 = 29$ . De derde letter is dus een $T$ .
Er is dan nog $38115 - 29\cdot 36^2=531$ over. Er geldt $531 \text{//} 36 = 14$ . De vierde letter is dus een $E$ .
Tot slot hebben we $531-14\cdot 36=27$ over. De laatste letter is daarmee een R.

Op mijn T-shirt staat dus mijn voornaam PETER op de achterkant.

Pagina's: 123

Cryptografie les 7: Letterfrequenties

Deze les gaan we onderzoeken hoe we teksten kunnen ontcijferen waarbij iedere letter met dezelfde encryptiefunctie versleuteld is. Dit vertelt ons dat we op een andere manier teksten moeten versleutelen. Voor we daarmee van start gaan, maken we nog het CryptoHack-stuk van vorige les af.

CryptoHack

Voordat we naar het doel van de les gaan, ronden we nog een paar dingen af van vorige les aan de hand van enkele opdrachten van CryptoHack. In opdracht 1 komt de basis terug van vorige les.

Opdracht 1:
a) Maak de opdracht Modular Arithmetic 1 op CryptoHack. Je moet het kleinste antwoord van $11 \text{ mod } 6$ en $8146798528947 \text{ mod } 17$ geven.
b) Maak de opdracht Greatest Common Divisor op CryptoHack. Je moet de grootst gemene deler van 66528 en 52920 geven.
c) Maak de opdracht Extended gcd op CryptoHack. Je moet met het algoritme van Eulcides de $u$ en $v$ vinden, zodat $26513\cdot u + 32321 v = 1$ . Geef als antwoord de kleinste van $u$ en $v$ .
d) Maak de opdracht Modular Inverting op CryptoHack. Je moet dan het getal $d$ vinden, zodat $3\cdot d \text{ mod } 13=1$ .

In opdracht 2 zul je zelf nog iets meer moeten nadenken.

Opdracht 2:
Maak de opdracht Modular Arithmetic 2 op CryptoHack. Je moet $273246787654^{65536} \text{ mod } 65537$ berekenen.

Hint:

Bereken bij iedere keer dat je vermenigvuldigd met 273246787654 de uitkomst modulo 65537 om niet met te grote getallen te werken.

Weetje:

Lees na het beantwoorden van de vraag de pagina op CryptoHack. De stelling die hier genoemd wordt, gaan we in een latere les nog gebruiken.

Pagina's: 1234

Cryptografie les 6: Algoritme van Euclides

In opdracht 3 van de vorige les probeerden we decryptiefuncties te vinden bij encryptiefuncties als $E(x)=(3x+5) \text{ mod } 26$ en $E(x)=5x \text{ mod } 26$ . Het doel van deze les is om een snellere manier te vinden om deze decryptiefuncties te bepalen. Hiervoor gaan we het algoritme van Euclides gebruiken. Dit is in eerste instantie een algoritme om de grootst gemene deler te bepalen, maar we gaan zien dat die ook voor andere vraagstukken nuttig is.

Delers

We beginnen met het begrip deler. We zeggen dat $a$ een deler is van $b$ als $\frac{b}{a}$ een geheel getal is.

Opdracht 1:
a) Is 5 een deler van 45?
b) Is 45 een deler van 5?
c) Is 17 een deler van 17?
d) Is 1 een deler van 3?
e) Is 12 een deler van 0?
f) Is 0 een deler van 12?

Uitwerking:

a) Ja, want $\frac{45}{5}=9$ en dat is geheel.
b) Nee, want $\frac{5}{45}=\frac{1}{9}$ is niet geheel.
c) Ja, want $\frac{17}{17}=1$ en dat is geheel.
d) Ja, want $\frac{3}{1}=3$ en dat is geheel.
e) Ja, want $\frac{0}{12}=0$ en dat is geheel.
f) nee, want $\frac{12}{0}$ kan niet.

Opdracht 2: (Bron: Project Euler probleem 1)
De lijst van alle positieve gehele getallen onder de 10 die veelvouden van 3 of 5 zijn, zijn 3, 5, 6 en 9. Deze getallen hebben een som van 23. Schrijf in Python een programma die de som van alle positieve gehele getallen onder de 1000 vindt die een veelvoud van 3 of 5 zijn.

Uitwerking:

In Python kunnen we met $b\%a==0$ controleren of $a$ een deler is van $b$ . Het onderstaande programma test dus voor ieder getal onder de 1000 of die een deler is van $a$ of $b$ en als dat het geval is, wordt die bij de uitkomst opgeteld.

som = 0
for n in range(1,1000):
    if n % 3 == 0 or n % 5 == 0:
        som += n
print(som)

Het antwoord is dan 233168.

Pagina's: 12345

Cryptografie les 5: Encryptiefunctie

Bij de encryptie van een tekst gebruiken we altijd de volgende stappen:

Zet de tekst om in een serie getallen
Voer een encryptiefunctie $E(x)$ uit.
Zet de getallen om in de versleutelde tekst.

Bij de decryptie van een tekst maak je de stappen in omgekeerde volgorde ongedaan:

Zet de versleutelde tekst om in getallen.
Voer de decryptiefunctie $D(x)$ uit ( $D(x)$ is de inverse functie van $E(x)$ )
Zet de getallen om in een leesbare tekst.

Op deze pagina zullen we dit illustreren aan de hand van een voorbeeld. Hierbij gebruiken we de volgende omzetting van letters naar getallen:

Daarnaast gebruiken we in dit voorbeeld de encryptiefunctie $E(x)=3x \text{ mod } 26$ . Hierbij betekent modulo 26 (kortweg mod 26) dat we de rest nemen na deling door 26 (de %-operator in Python).

Opdracht 1:
a) Laat zien dat $E(10)=4$ .
b) Leg uit waarom uit het antwoord van opdracht a volgt dat de encryptiefunctie $E(x)=3x \text{ mod } 26$ de letter K op de letter E afbeeldt.
c) Op welke letter wordt de X afgebeeld door deze encryptiefunctie?

Uitwerking 1a:

$E(10)=3\cdot 10 \text{ mod } 26 = 30 \text{ mod } 26 = 4$

Uitwerking 1b:

Bij het versleutelen van de letter K worden drie stappen gedaan:
1. De letter K wordt omgezet in het getal 10.
2. De encryptiefunctie zet 10 om in het getal $E(10)=4$ .
3. De 4 wordt weer omgezet in de letter E met behulp van de tabel.

Uitwerking 1c:

De letter X wordt eerst omgezet in het getal 23.
Het getal 23 wordt versleuteld naar het getal $E(23)=3\cdot 23 \text{ mod } 26 = 69 \text{ mod } 26 = 17$
Het getal 17 wordt omgezet in de letter R.

Conclusie: De X wordt afgebeeld op de R.

Bij deze encryptiefunctie hoort de decryptiefunctie $D(x)=9x \text{ mod } 26$ . De reden is dat $D(E(x))=9(3x) \text{ mod } 26 = 27x \text{ mod } 26= (26x+x) \text{ mod } 26= x$ .
De bovenstaande berekening laat zien dat als je de encryptiefunctie en decryptiefunctie na elkaar uitvoert het oorspronkelijke woord er weer uitkomt.

Opdracht 2:
a) Versleutel een woord met de encyryptiefunctie $E(x)$ en geef het versleutelde woord aan de persoon naast je.
b) Ontcijfer het woord dat degene naast je versleuteld heeft.

Bovenstaande is zeker voor lange teksten best veel werk. Daarom gaan we op de volgende pagina dit laten automatiseren met Python. Eerst heb ik hieronder nog een paar andere encryptiefuncties staan. Kijk of het je lukt om bij iedere functie een decryptiefunctie te vinden.

Opdracht 3:
a) Verzin een decryptiefunctie bij $E(x)=x+5 \text{ mod } 26$ .
b) Verzin een decryptiefunctie bij $E(x)=(3x+5)\text{ mod } 26$ .
c) Verzin een decryptiefunctie bij $E(x)=5x\text{ mod } 26$ .

Uitwerking 3a:

$D(x)=x-5 \text{ mod } 26$ werkt, omdat $D(E(x))=((x+5)-5)\text{ mod } 26 = x \text{ mod } 26$

Manier om op het antwoord te komen:
Je wilt 5 optellen ongedaan maken. Dat kun je doen door juist 5 af te trekken.

Uitwerking 3b:

$D(x)=9(x-5)\text{ mod } 26$ werkt, omdat $D(E(x))=9((3x+5)-5) \text{ mod } 26 = 27x \text{ mod } 26= (26x+x) \text{ mod } 26= x$

Manier om op het antwoord te komen:
Eigenlijk bestaat de encryptiefunctie $E(x)=(3x+5)\text{ mod } 26$ uit twee stappen. Eerst keer 3 en dan plus 5. Bij het maken van een inverse wil je die in omgekeerde functie ongedaan maken. Dat is eerst 5 aftrekken (om de plus 5 ongedaan te maken) en dan keer 9 doen (om de keer 3 ongedaan te maken).

Uitwerking 3c:

$D(x)=21x \text{ mod } 26$ werkt, omdat $D(E(x))=21(5x)\text{ mod } 26 = 105x \text{ mod } 26 =(104x + x) \text{ mod } 26 = x$

Manier om op het antwoord te komen:
De truc is om een getal $a$ te vinden, zodat $5a$ één meer is dan een 26-voud. Als dat namelijk het geval is, geldt $5a \text{ mod } 26 = 1$ en daarom ook $5ax \text{ mod } 26 = 1\cdot x = x$ . Als we die gevonden hebben, tonen deze berekeningen dat $D(x)=ax$ een inverse is van $E(x)=5x$ .

Om de bovenstaande $a$ te vinden, kun je gewoon veelvouden van 26 noteren, totdat het getal dat erboven zit een vijfvoud is. Dat gebeurt bij $4\cdot 26=104$ en dan is de gezochte $a$ dus $\frac{105}{5}=21$ .

Bonusopdracht:
Op de volgende pagina staat een Python-programma die bij een invoer van een woord met alleen hoofdletters als uitvoer het versleutelde woord na uitvoeren van de encryptie met $E(x)=3x \text{ mod } 26$ geeft. Als uitdaging kun je proberen of het je lukt om zo’n programma te schrijven voordat je op de volgende pagina spiekt.

Hint:

Zoek op internet op wat de ord– en de chr-functie doen.

Pagina's: 1234

Voorbereiden toets deel 1: Python

Op de toets krijg je drie Python-vragen. Het niveau hiervan zal één vraag van niveau 1.1 à 1.2 zijn, één vraag van niveau 1.3 à 1.4 en één vraag van niveau 1.5 tot 1.6. Zeker voor de moeilijkere vragen zul je echt moeten oefenen met het op papier opschrijven. Let er daarbij op dat je ook de witruimte (bij het inspringen van for-loops en if-loops) duidelijk doet.

Hieronder staat een overzicht van de functies die je in Python geleerd hebt. Zorg dat je deze functies kent en kunt toepassen.

a+b            a plus b
a-b            a min b
a*b            a keer b
a**b           a tot de macht b
a/b            a gedeeld door b
a//b           a gedeeld door b naar beneden afgerond op gehelen
a%b            a modulo b (de rest bij deling van a door b)
a,b = b, a     Verwisseld a en b
a^b            a XOR b

a == b         Dit test of a en b dezelfde waarde hebben.
a > b          Dit test of a een grotere waarde dan b heeft.
a >= b         Dit test of a groter of gelijk is aan b.
a < b          Dit test of a kleiner dan b is.
a <= b         Dit test of a kleiner of gelijk aan b is.
a != b         Dit test of a ongelijk aan b is.
A or B         Uitkomst is waar als A en/of B waar is.
A and B        Uitkomst is waar als zowel A als B waar is.

print(a)       Dit print a op het scherm van de gebruiker.
print(a,b)     Print a en b met een spatie ertussen.
input()        Dit leest een input in.
range(a,b,c)   Dit maakt een lijst van a tot b met steeds c verschil.
range(a,b)     Dit maakt een lijst van alle getallen vanaf a tot b.
range(b)       Dit maakt een lijst van alle getallen vanaf 0 tot b.
int()          Dit maakt van een waarde een geheel getal.
float()        Dit maakt van een waarde een kommagetal.
str()          Dit maakt van een waarde een stukje tekst.
for a in b:    Dit herhaalt de ingesprongen regels voor iedere waarde a uit de lijst b.
break          Dit zorgt dat de loop eindigt.
while a:       Dit herhaalt de ingesprongen regels zolang a waar is
if a:          Als a True is, worden de ingesprongen regels uitgevoerd. 
else:          Als de if False is, worden de ingesprongen regels uitgevoerd.
elif a:        Een else- en if-statement ineen
or and         Je kunt de logische operatoren "or" en "and" ook gebruiken in een loop.

.split()       Splitst een regel in een lijst.
input().split() Splitst de input in een lijst
a[3]           Geeft waarde die op plek 3 van de lijst a staat.    
len(a)         Geeft het aantal elementen in lijst a.

def ja(a):     Start van de functie met de naam ja met inputvariabele a.
return True:   Als het programma op deze regel komt, eindigt de functie. De regel waar de functie aangeroepen werd, krijgt als waarde "True" terug
ord("A")       Geeft de ASCII-waarde van het symbool A.
chr(65)        Geeft het symbool met ASCII-waarde 65.
pow(3,7,13)    Berekent 3^7 modulo 13

Mijn advies is verder om in jouw Python-programma niet te veel op één regel te willen doen. Op papier geldt nog meer als op de computer dat het beter is om meer regels te gebruiken als dat voor jezelf en/of de lezer meer overzicht geeft.

Een laatste advies is om altijd te beginnen met de problemen. Zelfs als je geen idee hebt, krijg je het eerste punt bij een vraag voor het inlezen van de input-variableen in het juiste type (integer, float of string) en dat kun je ook als je nog niet precies weet hoe je de opgave moet oplossen.

We gaan dit oefenen door de les te starten met 5 problemen van niveau 1.1 t/m 1.5 die je op papier gaat programmeren. Over 30 minuten bespreken we de oplossingen.

Opdracht 1: (niveau 1.1)
Schrijf een programma op papier dat drie getallen na elkaar inleest. De output moet het derde getal min de som van de twee andere getallen zijn.
Voorbeeld input:
17
39
100
Voorbeeld output:
44

Je kunt je antwoord controleren door hem over te typen bij de opdracht A leid i bio op Kattis.

Uitwerking:

Je begint met het inlezen van de drie getallen:

a = int(input())
b = int(input())
c = int(input())

Nadat je de getallen ingelezen hebt, doe je het sommetje $c-a-b$ en print dat op het scherm.

print(c-a-b)

Opdracht 2: (niveau 1.2)
Schrijf een programma dat één getal van 1 t/m 12 inleest. Dit staat voor de hoeveelste maand van 2025 het is. Geef als output het aantal dagen dat deze maand duurt.
Voorbeeld input:
2
Voorbeeld output:
28
Hint: April, Juni, September en November hebben 30 dagen.

Je kunt je antwoord controleren door hem over te typen bij de opdracht Dagatal op Kattis.

Uitwerking:

Allereerst moet je natuurlijk het maandnummer inladen.:

maand = int(input())

Vervolgens controleer je eerst of dit de maand februari is (en het antwoord dus 28 is). Als dat niet zo is, controleer je of het een maand met 30 dagen is en als dat ook niet zo is, moet het wel een maand van 31 dagen zijn.

if maand == 2:
    print(28)
elif maand == 4 or maand == 6 or maand == 9 or maand == 11:
    print(30)
else:
    print(31)

Opdracht 3: (niveau 1.3)
Op regel één van het programma staat hoeveel regels met getallen er volgen. Ieder van de volgende getallen staat voor de moeilijkheid van de problemen. Geef als output hoeveel van deze problemen een oneven getal als moeilijkheid hebben.
Voorbeeld input:
3
2
1
5
Voorbeeld output:
2

Je kunt je antwoord controleren door hem over te typen bij de opdracht Call for problems op Kattis.

Uitwerking:

Als eerste zet je de input van de eerste regel in de variabele aantal (die noem ik zo, omdat hierin het aantal opdrachten staat). Vervolgens maak je een variabele aan waarin je gaat tellen hoeveel opdrachten er met een oneven moeilijkheidsgraad zijn. In het begin heb je er nog nul geteld en daarom zet je het getal 0 in deze variabele.

aantal = int(input())
antwoord = 0

Vervolgens laad je de moeilijkheid van ieder probleem in en controleer je steeds of dit aantal oneven is. Voor ieder probleem dat een oneven moeilijkheid heeft, verhoog je het antwoord met één.

for i in range(aantal):
    moeilijkheid = int(input())
    if moeilijkheid % 2 == 1:
        antwoord += 1

Tot slot print je het antwoord.

print(antwoord)

Opdracht 4: (niveau 1.4)
Op regel één van het programma staat hoeveel regels met getallen er volgen. Alle volgende getallen waren oorspronkelijk machten met een ééncijferige exponent waarbij de exponent naar beneden is gevallen. Zo staat $235$ voor de som $23^5$ . De vraag is om de som van de oorspronkelijke machten te geven als output. Het antwoord van de voorbeeldinput is dus $2^3+1^7+4^3+5^2+2^2=102$ .
Voorbeeld input:
5
23
17
43
52
22
Voorbeeld output:
102

Je kunt je antwoord controleren door hem over te typen bij de opdracht Pot op Kattis.

Uitwerking:

Je kunt op dezelfde manier beginnen als bij het vorige probleem.

aantal = int(input())
antwoord = 0

Nu willen we steeds (dus een for-loop) een getal inlezen. Hiervan is het laatste cijfer de exponent. Deze krijgen we door het getal modulo 10 te doen. Het stuk voor het laatste cijfer is het grondtal. Die krijgen we door het getal te delen door 10 en naar beneden af te ronden. Dat doet de operator //. Vervolgens tellen we $\text{grondtal}^{\text{exponent}}$ op bij ons antwoord.

for i in range(aantal):
    getal = int(input())
    exponent = getal % 10
    grondtal = getal // 10
    antwoord += grondtal ** exponent

Tot slot hoeven we alleen nog het antwoord te printen.

print(antwoord)

Opdracht 5: (niveau 1.5)
Op regel één van het programma staan twee getallen gescheiden door een spatie. Deze getallen staan voor het aantal zijden van de twee dobbelstenen die je hebt. Je gooit met beide dobbelstenen en telt de uitkomsten op. Als output geef je het getal wat de grootste kans heeft om de som van de twee dobbelstenen te zijn. Als dit er meerdere zijn, print je deze één voor één van klein naar groot op verschillende regels.
Voorbeeld input:
6 4
Voorbeeld output:
5
6
7

Je kunt je antwoord controleren door hem over te typen bij de opdracht Dice Cup op Kattis.

Uitwerking:

Met 6 en 4 zien alle combinaties die we kunnen gooien er als volgt uit:

We zien dat 5 t/m 7 op iedere rij voorkomt. Vijf is de eerste, omdat je minstens één groter moet zijn dan het aantal ogen (4) op de viervlakkige dobbelsteen om in de laatste rij voor te komen. Zeven is de laatste omdat je maximaal 1 groter dan het aantal ogen (6) op de zesvlakkige dobbelsteen mag zijn om in de eerste rij voor te komen.

In het algemeen moeten we dus alle getallen printen van het kleinste aantal ogen plus één tot het grootste aantal ogen plus één. Dat is wat de volgende code doet:

getallen = input().split()
a = int(getallen[0])
b = int(getallen[1])
if a < b:
    a,b = b,a
for c in range(b+1,a+2):
    print(c)

Pagina's: 1234567

Cryptografie les 4: Lijsten

In de afgelopen lessen hebben we de volgende methodes in python geleerd:

a+b            a plus b
a-b            a min b
a*b            a keer b
a**b           a tot de macht b
a/b            a gedeeld door b
a//b           a gedeeld door b naar beneden afgerond op gehelen
a%b            a modulo b (de rest bij deling van a door b)

a == b          Dit test of a en b dezelfde waarde hebben.
a > b           Dit test of a een grotere waarde dan b heeft.
a >= b          Dit test of a groter of gelijk is aan b.
a < b           Dit test of a kleiner dan b is.
a <= b          Dit test of a kleiner of gelijk aan b is.
a != b          Dit test of a ongelijk aan b is.
A or B          Uitkomst is waar als A en/of B waar is.
A and B         Uitkomst is waar als zowel A als B waar is.

print(a)       Dit print a op het scherm van de gebruiker.
print(a,b)     Print a en b met een spatie ertussen.
input()        Dit leest een input in.
range(a,b,c)   Dit maakt een lijst van a tot b met steeds c verschil.
range(a,b)     Dit maakt een lijst van alle getallen vanaf a tot b.
range(b)       Dit maakt een lijst van alle getallen vanaf 0 tot b.
int()          Dit maakt van een waarde een geheel getal.
float()        Dit maakt van een waarde een kommagetal.
str()          Dit maakt van een waarde een stukje tekst.
for a in b:    Dit herhaalt de ingesprongen regels voor iedere waarde a uit de lijst b.
if a:          Als a True is, worden de ingesprongen regels uitgevoerd. 
else:          Als de if False is, worden de ingesprongen regels uitgevoerd.
elif a:        Een else- en if-statement ineen
or and         Je kunt de logische operatoren "or" en "and" ook gebruiken in een loop.

Met deze methodes kun je de meeste belangrijke algoritmes programmeren. Voor veel van deze algoritmes is het echter wel fijn als je een lijst gemakkelijker kan bewerken. Daarom zullen we in deze les leren hoe je in Python met lijsten kunt werken. Voor we daarmee beginnen, starten we al met het nadenken over sorteringsalgoritmes.

Opdracht 1:
Over drie minuten krijg je een geschud spel kaarten zonder jokers. De opdracht is om zo snel mogelijk de kaarten te sorteren. Bovenop moeten alle schoppen komen dan de harten, dan de ruiten en dan de klaveren. Hierbij moeten de kaarten van iedere kleur in de volgorde 2-3-4-5-6-7-8-9-10-Boer-Vrouw-Heer-Aas komen te liggen. Degene die dit als snelste voor elkaar krijgt, wint deze wedstrijd.

Pagina's: 12345