## 14.5 Complexe berekeningen

De berekening die Alice uit moet voeren op de klare tekst 171 800 met sleutel (5183,17) leidt onmiddelijk tot een probleem omdat het rekenblad en de rekenmachine de berekeningen niet aan kunnen.
Een mogelijkheid is om de volgende rijtjes uit te rekenen:
1712 mod 5183; 8002 mod 5183
1714 mod 5183; 8004 mod 5183
1718 mod 5183; 8008 mod 5183
17116 mod 5183; 80016 mod 5183
Merk op dat elk volgende getal steeds het kwadraat is van de voorgaande en dat een rekenblad daarbij goede dienst kan bewijzen.

Opmerking:
Als je de bovenstaande berekeningen volgt, merk je dat het vercijferen van een bericht door Alice en het ontcijferen door Bob geen pretje is. Op de sub-pagina Euler en Fermat leer je dat er ook shortcuts zijn om dit soort berekeningen uit te voeren.

Invuloefening

Opgave 1

Vercijfer het tweede blok van de boodschap van Alice.

In de invuloefening zie je dat de lengte van de blokken in de cijfertekst niet hetzelfde is als de lengte van de blokken in de originele boodschap. In de praktijk zul je gewoonlijk niet een heel bericht met RSA vercijferen. De rekentijd is hiervoor te lang. RSA wordt meestal gebruikt om een sleutel te versturen van een symmetrisch cryptosysteem waarbij vercijfering minder tijd kost. Naast de sleutel wordt eventueel wat aanvullende informatie verstuurd om te zorgen dat je zeker weet dat niemand wijzigingen in je bericht heeft aangebracht. De lengte l van de boodschap die je wilt versturen is hierdoor korter. Het is dan niet nodig de boodschap op te splitsen in blokken en je hoeft dus ook niet een aantal blokken afzonderlijk te vercijferen. Hierdoor maakt het niet uit als de originele tekst en de cijfertekst niet even lang zijn.

Reflectie

Hoe belangrijk is het dat de blokken van de cijfertekst even lang zijn als de blokken van de klare tekst?

klik hier

De boodschap van Alice wordt ontvangen door Bob, die het nu met zijn privé-sleutel zal proberen te ontcijferen.

Opgave 2

Ontcijfer het bericht 3685 2677 met de privé-sleutel {5183,593}.

In de volgende opgave controleren we hoe veilig de sleutel van Bob is:

Opgave 3

De publieke sleutel van Bob is (209,13).
Achterhaal de geheime sleutel van Bob.

Opgave 4

Wijzer geworden door opgave 3 kiest Bob de publieke sleutel (1040257,1361). De geheime sleutel van Bob vinden, zal je nu niet zo snel lukken zonder computer.
Wat is er zo moeilijk aan?

Voor kleine p en q is het niet moeilijk om de geheime sleutel uit de publieke sleutel af te leiden, voor (hele) grote p en q wel. Daarom gebruikt men voor p en q getallen van ongeveer 150 cijfers. Het getal n bestaat dan uit ongeveer 300 cijfers. Een getal dat zo groot is, is momenteel zelfs met de allersnelste computers niet binnen een mensenleven te ontbinden. Hierop berust de veiligheid van RSA. Wanneer je de getallen p en q zou kunnen vinden, zou je K eenvoudig kunnen berekenen en de inverse van e met het uitgebreide algoritme van Euclides kunnen berekenen. Je zou dan de vercijferde boodschap kunnen ontcijferen door hem tot de macht d te verheffen mod n.

Dit is een geschikt moment om de tekst onder het kopje Machtsverheffen modulo m door te nemen.

Machtsverheffen modulo m

Onder het kopje (a div m) en (a mod m) van les 12 heb je de somregel en de productregel voor het modulo-rekenen geleerd. We herhalen ze nog even:

Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt: als amod m = bmod m en c mod m = d mod m dan Somregel: (a+ c)modm = (b+d)modm Productregel: (a*c)modm = (b*d)mod m

Op deze subpagina richten we onze aandacht op het machtsverheffen.

Opgave 1

a) Leg uit dat we voor kwadrateren geen aparte regel nodig hebben.
b) Leg uit dat als je kunt kwadrateren en twee getallen kunt vermenigvuldigen,
dat je dan ook weet hoe je tot de derde en de vierde macht moet verheffen.
c) Leg uit dat je dan dus ook weet hoe je getallen tot een hogere macht kunt verheffen.

Na het maken van opgave 1 voel je de juistheid van de machtenregel wel aan:

Voor gehele getallen x en y en positieve gehele getallen k en d geldt: als x(mod d)= y(mod d) dan xk(mod d)= yk(mod d).

Opgave 2

Vul de tabel in Z5 in. Met het teken "^" bedoelen we "tot de macht", dus 1^2=12.
Voorbeeld : In Z5 is 2^4 = 16(mod 5) = 1

^ | 0 | 1 | 2 | 3 | 4
0 |  |  |  |  |
1 |  |  |  |  |
2 |  |  |  |  | 1
3 |  |  |  |  |
4 |  |  |  |  |

Met behulp van de somregel, de productregel en vooral de machtenregel kunnen we berekeningen die erg moeilijk lijken toch vrij eenvoudig uitvoeren.

We kijken nog eens hoe de regels voor machtsverheffen zijn:
Je weet dat 46 betekent 4*4*4*4*4*4
Leg daarmee uit dat: 34*35=39
Laat ook zien dat (52)3=56
Algemeen: ap*aq=ap+q en (ap)q=ap*q

Voorbeeld:
Bereken 1725 in Z26.

(1) 1725 = 1724 * 17 = (172)12 * 17 (2) 172 = 289, dus 172 (mod 26) = 289(mod 26) = 3 (3) (172)12 * 17 =312 * 17 (4) 312 * 17 = (33)4 * 17 (5) 33 (mod 26) = 27(mod 26) = 1 (6) 312 * 17 = (33)4 * 17 = 14 * 17 = 17(mod 26) (7) Dus 1725 = 17 in Z26. | herschrijven om machtenregel toe te passen. volgt uit (1) en (2). zie stap (1). volgt uit stap (4 en 5)

Opgave 3

a) Bereken 225 in Z31.
b) Bereken 3301 in Z25.
c) Bereken 1896 in Z325.

Opgave 4

a) Bereken 1733 in Z553.
b) Bereken 1240 in Z1000.
c) Bereken 73843 in Z640.

Opgave 5

a) Bepaal de rest van 247 bij deling door 47.
b) Bepaal het laatste cijfer van 381. (Tip: reken modulo 10)
c) Onderdeel b kan ook anders. Hoe?

Ga nu verder met het gedeelte over Digitale handtekeningen (14.6)