In een Public Key System heeft elke deelnemer twee sleutels, een openbare sleutel (die bv. in een soort telefoonboek kan staan) en een strikt geheime. Deze twee sleutels maken elkaars werk ongedaan. Stel bijvoorbeeld dat $O_A$ de openbare sleutel is van Anouk en $G_A$ haar geheime sleutel, dan zou voor elke boodschap $x$ (een getal) gelden dat $G_A(O_A(x)) = x$ en $O_A(G_A(x)) = x$. Als Bart ook een paar dergelijke sleutels $O_B$ en $G_B$ heeft, dan zou Anouk Bart de mededeling $x$ kunnen doorgeven door hem $O_B(x)$ te mailen. Door $G_B$ te gebruiken, kan Bart $x$ terugvinden. Iemand die de boodschap onderschept, kan $x$ niet vinden: daarvoor heeft hij/zij de geheime sleutel van Bart nodig en die heeft hij/zij niet...

Opgave 1

Anouk kan haar openbare en geheime sleutels ook anders gebruiken, bijvoorbeeld om te garanderen dat zij de mededeling $x$ heeft verstuurd. Hoe?

We gaan één van de bekende Public Key Systems bekijken: het RSA-systeem, genoemd naar de bedenkers, Rivest, Shamir en Adleman (zie de foto in figuur 1).

Figuur 1: v.l.n.r. Shamir, Rivest en Adleman

Dit systeem werkt dankzij wiskunde. Hoe? Dat zullen we gaan zien.

Opgave 2

Het getal $n = 7305247$ is het product van twee priemgetallen van elk vier cijfers. Kun je de twee priemgetallen vinden?

Heb je de twee priemgetallen gevonden? Misschien is het je gelukt door een handig programmaatje te schrijven of door systematisch de priemgetallen van vier cijfers uit een lijst priemgetallen te proberen. Maar het heeft je waarschijnlijk wel wat tijd gekost. Stel je nu eens voor dat $n$ een getal van ruim tweehonderd cijfers is en een product van twee priemgetallen van elk ruim honderd cijfers. Dan is het vinden van de twee priemgetallen weliswaar niet geheel onmogelijk, maar in de praktijk wel: het kost met de snelste computers en de meest slimme methoden die nu bekend zijn op zijn minst vele tientallen jaren. Hierin schuilt de werking van het RSA-systeem. Voor we met dit systeem kennis gaan maken hebben we wat ingrediënten nodig: modulo rekenen en de functie en de stelling van Euler.

Modulorekenen

Eigenlijk weet je al lang wat modulorekenen is. Als je bijvoorbeeld $9$ uur moet slapen en je gaat om $10$ uur naar bed, hoe laat moet je dan je wekker zetten? Om die vraag te beantwoorden gebruik je modulo rekenen: $10 + 9 = 19$, dus zet je de wekker om $19 - 12 = 7$ uur. Je hebt dan ${\rm\ modulo\ }12$ gerekend. Bij rekenen ${\rm\ modulo\ }12$ zet je elk antwoord om in een getal van $0$ tot en met $11$ door er net zo vaak als mogelijk $12$ vanaf te halen. Zo is $7 \cdot 9 = 63 \equiv 3{\rm\ modulo\ }12$. Met het $\equiv$ teken geef je aan dat je modulo rekent.

Je kunt modulo elk positief geheel getal rekenen op eenzelfde manier. Je GR heeft daarvoor ook een optie. Bij de TI kun je deze vinden via $\rm MATH-NUM-remainder$, bij de Casio gebruik je $\rm OPTN-NUMERIC-MOD$. $\rm Remainder(7*9,12)$ en $\rm MOD(7 \times 9,12)$ geven beiden het antwoord $3$.

In de cryptografie worden grote machten modulo grote getallen berekend. Je kunt dat met je GR ook doen, doordat je onderweg al modulo kunt rekenen. Bijvoorbeeld $63 \cdot 26 = 1638 \equiv 6\ ({\rm modulo\ }12)$ had je ook kunnen vinden door eerst de factoren $63$ en $26{\rm\ modulo\ }12$ te nemen en vervolgens het product te berekenen: $63 \equiv 3; 26 \equiv 2{\rm\ en\ }3 \cdot 2 = 6$.

Stel je wilt $129^{27}{\rm\ modulo\ }200$ berekenen. Rechtstreeks gaat niet, je GR geeft voor $129^{27}$ als antwoord $9{,}681043646\times 10^{56}$ en vervolgens een foutmelding bij bv. $\rm MOD(Ans, 200)$.

Maar via een omweggetje lukt het wel, bijvoorbeeld door telkens te kwadrateren en je GR te gebruiken:

$129^{2} \equiv 41;\\
129^4 = (129^2)^2 \equiv 41^2 \equiv 81;\\
129^8 = (129^4)^2 \equiv 81^2 \equiv 161;\\
129^{16} = (129^8)^2 \equiv 161^2 \equiv 121,$

zodat tenslotte $129^{27} = 129^{16} \cdot 129^8 \cdot 129^2 \cdot 129 \equiv 121 \cdot 161 \cdot 41 \cdot 129 \equiv 9$. In dit geval kan het overigens ook handiger door derdemachten te gebruiken: $129^3 \equiv 89; 129^9 = (129^3)^3 \equiv 89^3 \equiv 169 {\rm\ en\ } 129^{27} = (129^9)^3 \equiv 169^3 \equiv 9$. Eventueel moet het vermenigvuldigen aan het eind ook in een paar stappen worden gedaan als de getallen te groot zijn voor de GR, maar het lukt zeker!

Opgave 3

Bereken $87^{87}{\rm\ modulo\ }101$.

Opgave 4

Bereken de laatste drie cijfers van $19^{19}$.

De Eulerindicator

De Eulerindicator $\varphi(n)$ van een positief geheel getal $n$ is het aantal positieve gehele getallen $k \le n$ met de eigenschap dat $k$ en $n$ geen gemeenschappelijke delers $\neq 1$ hebben. We zeggen dat ze als grootste gemene deler $1$ hebben: ${\rm ggd}(k, n) = 1$.

Voor de getallen $n$ waar wij naar kijken, namelijk de getallen $n = p \cdot q$ met $p$ en $q$ priemgetallen, is $\varphi(n)$ snel te berekenen. Met een voorbeeld is te zien hoe dit gaat.

Neem bijvoorbeeld eens $n = 35 = 5 \cdot 7$ en bepaal het aantal getallen $k \le 35$ met ${\rm ggd}(k, 35) = 1$. We kijken daartoe welke getallen $k \le 35$ niet mee doen: dit zijn de veelvouden van $5$ (7 stuks) en de veelvouden van $7$ (5 stuks). Je hebt nu wel het getal $35$ dubbelgeteld. Die moet er weer een keer bij, dus $\varphi(35) = 35 - 5 - 7 + 1$.

In het algemeen gaat het net zo: $\varphi(p\cdot q) = p \cdot q - p - q + 1 = (p - 1) \cdot (q - 1)$.

Je kunt ook voor getallen $n$ die niet het product van twee priemgetallen zijn formules voor $\varphi(n)$ vinden, maar omdat we die niet nodig hebben in het vervolg doen we dat hier niet.

De stelling van Euler

We nemen $n = 21 = 3 \cdot 7$. Dan is $\varphi(21) = 2 \cdot 6 = 12$. Voor het getal $5$ geldt ${\rm ggd}(5, 12) = 1$. De getallen $k \le 21$ met ${\rm ggd}(k, 21) = 1$ zijn de getallen $1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19 {\rm\ en\ } 20$. We vermenigvuldigen al deze getallen met $5$ en berekenen de producten ${\rm\ modulo\ }21$:

$5 \cdot 1 = 5 \equiv 5;\\
5 \cdot 2 = 10 \equiv 10;\\
5 \cdot 4 = 20 \equiv 20;\\
5 \cdot 5 = 25 \equiv 4;\\
5 \cdot 8 = 40 \equiv 19;\\
5 \cdot 10 = 50 \equiv 8;\\
5 \cdot 11 = 55 \equiv 13;\\
5 \cdot 13 = 65 \equiv 2;\\
5 \cdot 16 = 80 \equiv 17;\\
5 \cdot 17 = 85 \equiv 1;\\
5 \cdot 19 = 95 \equiv 11;\\
5 \cdot 20 = 100 \equiv 16.$

Het rijtje antwoorden is hetzelfde rijtje getallen als waar we mee begonnen zijn, alleen in een andere volgorde! Maar dan zijn $\rm modulo 21$ de producten $G = 1 \cdot 2 \cdot 4 \cdot 5 \cdot 8 \cdot 10 \cdot 11 \cdot 13 \cdot 16 \cdot 17 \cdot 19 \cdot 20$ en $5 \cdot 1 \cdot 5 \cdot 2 \cdot 5 \cdot 4 \cdot 5 \cdot 5 \cdot 5 \cdot 8 \cdot 5 \cdot 10 \cdot 5 \cdot 11 \cdot 5 \cdot 13 \cdot 5 \cdot 16 \cdot 5 \cdot 17 \cdot 5 \cdot 19 \cdot 5 \cdot 20 = 5^{12} \cdot G$ gelijk: $G \equiv 5^{12} \cdot G$, zodat $5^{12} \equiv 1\ ({\rm modulo\ }21)$.

Een berekening als hierboven kunnen we maken voor elke $n$ en elke $a$ met ${\rm ggd}(a, n) = 1$, altijd geldt dan $a^{\varphi(n)} \equiv 1\ ({\rm modulo\ }n)$: de stelling van Euler.

Een RSA-systeem

Anouk gaat haar sleutels maken. Ze begint met het kiezen van twee priemgetallen, $p = 43$ en $q = 17$ (in dit voorbeeld nemen we kleine getallen zodat je met je GR mee kunt rekenen). Ze berekent $n = 43 \cdot 17 = 731$ en de functie van Euler $\varphi(731) = 42 \cdot 16 = 672$. Anouk kiest nu een getal $c$ zodanig dat ${\rm ggd}(c, \varphi(n)) = 1$, zij kiest $c = 19$.

De openbare sleutel van Anouk is dan het getallenpaar $n = 731$ en $c = 19$.

De geheime sleutel van Anouk bestaat ook uit twee getallen, te weten $\varphi(n)$ en een getal $d$, de deciphering exponent,  zodanig dat $d \cdot e = 1 + k \cdot \varphi(n)$, waarbij $k$ een geheel getal moet zijn. Dit getal $d$ is te berekenen door $\varphi(n)$ te delen door $c$ met rest, vervolgens $c$ door de rest en zo door te gaan tot rest 1 (dit is het algoritme van Euclides)  en daarna terug te gaan rekenen door de antwoorden van de vorige berekeningen te vervangen door de “opgave”:

$672-35\cdot 19=7$

$19-2 \cdot 7=5$

$7-1\cdot 5=2$

$5-2 \cdot 2=1$

Nu gaan we terugrekenen:
$1 = 5 - 2 \cdot {}$			$2$	${}=5 - 2 \cdot {}($			$7-1\cdot {}$	$5$	$)$
$=3\cdot {}$	$5$	${} - {}$	$2$	${} \cdot 7=3\cdot {}($		$19-2\cdot 7$			$){} - 2\cdot 7$
$=3\cdot 19-8\cdot {}$				$7$	${} = 3\cdot 19$	${}-8\cdot {}($		$672$	${}-35\cdot 19$		$)$

$=283\cdot 19-8\cdot 672.$

Je ziet nu dat $283 \cdot 19 = 1 + 8 \cdot 672$, dus $d = 283$. (Mocht de berekende $d$ negatief zijn, tel er dan een of meerdere keren $\varphi(n)$ bij op tot $d$ positief is).

De geheime sleutel van Anouk is nu het getallenpaar $\varphi(n) = 672$ en $d = 283$. Ook moet zij de priemgetallen $p$ en $q$ geheimhouden, zie je waarom?

Bart stuurt een mededeling

Bart leest nu de openbare sleutel van Anouk af en wil haar de mededeling $m = 365$ sturen. Hij berekent daartoe eerst $\rm modulo 731$:

$365^{19} = 365^{16} \cdot 365^2 \cdot 365 \equiv 613 \cdot 183 \cdot 365 \equiv 563$

en stuurt Anouk vervolgens de boodschap $x = 564$.

Anouk kan de boodschap weer ontcijferen tot de oorspronkelijke mededeling door $563^{283} {\rm\ modulo\ }731$:

$563^{283} = 563^{256} \cdot 563^{16} \cdot 563^8 \cdot 563^2 \cdot 563 \equiv 256 \cdot 188 \cdot 477 \cdot 446 \cdot 563 \equiv 365$:

de oorspronkelijke mededeling van Bart!

Zie je ook waarom dit werkt?

De stelling van Euler en de keuze van d garanderen dat Anouk altijd de oorspronkelijke mededeling terugvindt:

$x^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1+k\varphi(n)} \equiv m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k \equiv m{\rm\ modulo\ }n$.

Opgave 5

Anouk heeft $p = 97, q = 79$ en $e =11$ gekozen. Wat moet haar $d$ zijn? Ze heeft $1324$ ontvangen. Wat was de mededeling?

Opgave 6

Anouk stuurt Bart een boodschap. Hij gebruikt de openbare sleutel $n = 19673$ en $c = 7013$. Jij onderschept de mail: de boodschap luidt $x = 6034$. Kun jij de mededeling die Anouk voor Bart had vinden?

O ja, Anouk moet natuurlijk de priemgetallen $p$ en $q$ geheimhouden omdat anders een afluisteraar (zoals jij in opgave 6) $\varphi(n)$ en daarmee ook $d$ kan berekenen....

Meer weten over cryptografie? De Vakantiecursus Wiskunde voor leraren in de exacte vakken in havo, vwo en hbo en andere belangstellenden is een initiatief van de Nederlandse Vereniging van Wiskundeleraren, en wordt georganiseerd door het Platform Wiskunde Nederland. Het thema van de PWN Vakantiecursus 2018 is Cryptografie: de wiskunde van het beveiligen van gegevens door middel van versleuteling en authenticatie. Voor meer informatie: www.platformwiskunde.nl/vakantiecursus

Bekijk oplossing