SSO om Kryptologi i Matematik

Indledning

I den følgende opgave vil jeg beskrive ideerne bag Public Key systemet, talteorien bag RSA-kryptosystemet, RSA-kryptosystemet, og sikkerheden i RSA, derunder også primtalsfaktorisering. Jeg har valgt at lægge hovedvægten på talteori-delen, men da opgaven skal holde sig indenfor en vis længde, har jeg ikke kunnet bevise alle sætninger. Ligeledes har jeg i afsnittet om faktorisering ikke kunnet vise så mange metoder til at faktorisere, som jeg gerne ville, igen grundet pladsmangel. Jeg har derfor valgt de sætninger og beviser ud, som jeg fandt mest relevante. Siden oldtidens Grækenland, har der været behov for sende hemmelige beskeder mellem mennesker, og i næsten lige så lang tid har der været forsøg på at bryde dem. Derfor har der hele tiden været interesse i at udvikle nye og bedre kryptosystemer.

Konventionelle kryptosystemer

Helt frem til 1970’erne var alle kryptosystemer konventionelle. De byggede på at afsender og modtager havde aftalt en fælles nøgle på forhånd. Da hele enkrypteringen og dekrypteringen byggede på den enkelte nøgle, stillede det store sikkerhedsmæssige krav til nøgleudvekslingen. Derudover skulle man have en hemmelig nøgle for hver person, man skulle udveksle beskeder med. F.eks. skulle en gruppe på bare 30 personer have 30(30-1)/2 = 435 nøgler, for at alle kunne udveksle beskeder med alle. Det mest almindelige konventionelle kryptosystem i dag hedder Data Encryption Standard (DES). Systemet bygger på 16 transpirationer og 8 substitutioner af teksten, som deles op i 64-bit (8 tegn) blokke. Kombinationen af transpiration og substitution gør, at DES kun kan brydes ved udtømmende søgning. Svagheden ligger i, at det kun er en 56-bit nøgle der benyttes, hvilket gør at der kun er 2 nøglemuligheder. En udtømmende søgning vil derfor kunne klares på rimelig tid.

Public Key

I 1976 præsenterede Whitfield Diffie og Martin Hellman et helt nyt forslag til, hvordan man kunne konstruere et kryptosytem, hvor afsender og modtager havde forskellige nøgler. Deres ideer byggede på det, man kalder en envejsfunktion (oneway-function). Det er en funktion, der forholdsvis nemt lader sig beregne, men det giver et beregningsmæssigt svært problem at bestemme dens inverse funktion. Ved et konventionelt kryptosystem ville enkrypteringen, E, af klarteksten, M, med nøglen, K, og dekrypteringen, D, af kryptoteksten, C, med samme nøgle, K, se således ud (se også bilag 1, fig. 1): Afsender: E(M, K) = C Modtager: D(C, K) = M Med Public Key systemet vil nøglerne være forskellige.