RSA cryptografie wiskundig gezien

[dudek]

Ik ben een boek aan het lezen over cryptografie. Tijdens het lezen van het stuk over RSA kwam ik met een aantal vragen te zitten waar ik na lang nadenken geen antwoord op kon vinden.

Allereerst zal ik RSA even kort toelichten voor de mensen die wel wiskundig zijn, maar geen cryptografie-kennis in huis hebben:

dit is kort samengevat wat in het hoofdstuk staat:

RSA is een public-key cryptosysteem dat werkt op basis van het feit dat 2 priemgetallen gemakkelijk te vermenigvuldigen zijn, maar dat het zeer lastig is het produkt te ontbinden in 2 priemfactoren.
Wat men doet is het volgende.
-Eerst worden er 2 priemgetallen gegenereerd, nl. p en q.
-Er wordt een n gegenereerd door p en q te vermenigvuldigen.
-Dan wordt er een groep bepaald waarin wordt gerekend. Daarvoor wordt er een K berekend: (p-1)(q-1). Voor sommigen van jullie wel bekend als de Euler totient-functie met priemgetallen.
-Daarna wordt er een e gekozen waarbij GGD(e,K)=1
-Tenslotte wordt er een d gekozen waarvoor geldt: ed=1(mod K) (ed delen door K geeft een rest van 1)

Hiermee kan een plaintext M versleuteld worden to teen ciphertext C:
C = M^e (mod n)
En andersom:
M = C^d (mod n)

Het eerste waar ik vast kwam te zitten is deze zin:

Dan wordt er een groep bepaald waarin wordt gerekend.

Ik snap niet precies wat ermee bedoeld wordt.
Het gaat hier dus om (p-1)(q-1). Ik dacht dat het ging om de mogelijke waarden van e, die worden immers bepaald door p en q. D zou dus ook afhankelijk zijn van die groep.
Ik ben hier alleen niet zeker van.


Het volgende probleem lag in de keuze van e. Wat is het precies het nut van het feit dat e en K relatief priem aan elkaar zijn?
En hoe zit dat met de n? Ik heb gelezen dat e en d elkaars inverse zijn, daarbij stond ook dat het volgende geldt:
d = e^(-1)(mod((p-1)*(q-1))).

Is er een wiskundige die mij dit helder kan uitleggen?

alvast bedankt

[Verwijderd]

In het boek van Simon Singh getiteld "The codebook" stand een uitleg over de wiskunde van RSA die ik kon volgen. Ik moet toegeven dat ik het niet met pen en papier na heb zitten rekenen maar toch?!

Het boek gaat overigens niet waanzinnig diep in op de wiskunde maar wie weet kom je er verder mee??

Boek is overigens ook in vertaling verschenen.

[Mastermind]

Stel in het RSA-algoritme wordt gewerkt met de priemgetallen
11 en 13 en nog een openbare sleutel: 7

Openbaar zijn dus 11*13 en 7 dus 143 en 7
De phi van 143 is 10*12 dus 120
Dan bereken je de inverse 7 mod 120 en dat is 103
1=(-17)*7+120 dat levert -17 als inverse, de kleinst positieve is -17+120 = 103
De geheime sleutel is dus 103.

[Tupolev]

Op maandag 26 november 2001 17:02 schreef dudek het volgende:

Het volgende probleem lag in de keuze van e. Wat is het precies het nut van het feit dat e en K relatief priem aan elkaar zijn?

e wordt zo gekozen dat deze kleiner is dan pq, en dat e en K relatief priemgetallen zijn.
Dat wil zeggen dat ze geen gemeenschappelijke priemfactoren hebben, dat zou het kraken namelijk een stuk vergemakkelijken

En hoe zit dat met de n? Ik heb gelezen dat e en d elkaars inverse zijn, daarbij stond ook dat het volgende geldt:
d = e^(-1)(mod((p-1)*(q-1))).

Dit wil zeggen dat ze een getal d bereken zo dat (de-1) een geheel aantal keer deelbaar is door (p-1)(q-1).
Hiervoor moet je een integer x zoeken die voor d=(x(p-1)(q-1)+1)/E een integer oplevert, en dan die waarde van d gebruiken.

Is er een wiskundige die mij dit helder kan uitleggen?

alvast bedankt

Ik ben dan wel geen wiskundige, maar ik hoop dat je mijn uitleg ook accepteerd