RSA key pairs

[Gijs]

Op het moment ben ik bezig met mijn profielwerkstuk over cryptografie, na het lezen van dit stuk documentatie ben ik aardig wat wijzer geworden over de exacte werking van RSA. Nu ben ik bezig dit voor mezelf goed uitgewerkt te krijgen om te checken of ik het ook echt snap.

Nu loop ik echter tegen een probleem aan bij het vinden van de Public en Private key. Zodra je wat grotere getallen pakt als U en V, in dit geval 23 en 31, zie je dat je al gauw lastige getallen gaat krijgen voor R en daardoor voor je P en Q. Deze moeten ook nog eens aan meerdere voorwaarden voldoen, hoe zorg je ervoor dat je hiervoor handige waarden krijgt.

Wat ik kan bedenken is het ontleden van de 1 mod R in priemgetallen, dit betekent echter dat je hiervoor meerdere waarden gaat krijgen die eigenlijk vrij nutteloos zijn, bijvoorbeeld 3, 5 etc. Wat is een handige manier om hiermee om te gaan? Natuurlijk wil ik het wiel natuurlijk niet opnieuw uitvinden dus documentatie of instructies hierover zijn ook zeer gewenst.

Even een tl;dr voor de link
Je pakt 2 priemgetallen, U en V
U*V=R
phi(R)=(U-1)*(V-1) (phi() berekent hoeveel getallen relatief priem zijn tov dit getal.)
vervolgens moet je een P en Q vinden die voldoet aan de volgende eisen:
P * Q = 1 mod (phi(R))
R moet relatief priem zijn tot de klare tekst (dus het ASCII toetsnummer in ons geval)
om veiligheid te kunnen garanderen moet T kleiner zijn dan R (daarom zijn 3 en 5 dus nutteloos.)

Heeft iemand tips of goede bronnen, ik hoor het graag!

[Gerco]

Kijk eens naar deel 6 van deze videoserie: https://class.coursera.org/crypto-010/lecture/preview "Public Key Encryption from trapdoor permutations (week 6)"

Sowieso is deze cursus aan te raden, erg vermakelijk en leerzaam. Het huiswerk kan vrij pittig zijn als je weinig ervaring in deze materie hebt, maar het is het waard.