SRP: Moderne kryptering, XOR, hashfunktioner og RSA

Moderne kryptering

Forord

I denne rapport bliver der omtrentligt vægtet 60% matematik og 40% IT.

Til udregning af store regnestykker er benyttet online-lommeregneren http://world.std.com/~reinhold/BigNumCalc.html .

Abstract

Encryption is a large part of our lives, more than we think about in our daily lives. Encryption was already used in ancient Egypt thousands of years ago, but it’s primarily used in internet safety today. Two types of encryption exist this day: symmetric and asymmetric encryption. The difference between these is the key functions – Symmetric encryption only has private keys, meaning the same key is used for both encryption and decryption. Asymmetric encryption uses both private and public keys, where the public key is used for encryption, and the private key for decryption.

An example of a symmetric encryption system used today is primarily the AES[1]-cryptosystem, and an asymmetric one used today is the RSA[2]-cryptosystem. These two function best when used together, as the AES private key can be encrypted with the RSA public key, making key exchange safe. Elementary number theory and other aspects in computer science are used in these cryptosystems.

It takes several years for computers nowadays to compromise encryption, but quantum computers will be used in the near future – these computers use an entirely different way of processing data, and their speed will grow exponentially with the amount of bits in them. These will then be able to compromise any encryption, since processing power is the only thing causing safety at this moment.

Indledning

Kryptering fylder mere i vores hverdag end vi tror. Det åbenlyse eksempel er ved brug af netbanker og offentlige instanser, men det bliver brugt utallige andre steder. Der findes certifikat-uddeling på mange hjemmesider, som forklarer computeren at de er en troværdig kilde. Krypteringen har udviklet sig meget fra tidligere tider, fra fysisk kryptering ved brug af bl.a. ’skrivemaskine’-lignende maskiner i anden verdenskrig, til nutidens brug på internettet.

I denne opgave vil jeg kort komme ind på krypteringens historie, samt forklare hvordan nutidens kryptering virker. De matematiske talteoretiske teorier, som anvendes til enkryptering og dekryptering forklares i detaljer, og metoderne i de nuværende krypteringsteknikker AES og RSA gennemgås dybdegående. Efter dette, vil fremtidens teknikker, i form af kvantecomputere, redegøres, og hvordan dette påvirker sikkerheden i vor nuværende krypteringsmetoder. Til sidst vil krypteringens betydning for IT-samfundet gennemgås, og hvordan fremtiden vil se ud på denne front.

Til alle de talteoretiske forklaringer og udregninger, samt RSA-kryptosystemet, tages udgangspunkt i bøgerne ”Kryptologi – Fra Viden til Videnskab”[3] samt ”Kryptering”[4]. Som kilde til moderne kryptering generelt og kvantekrypteringen, benyttes en del kilder fra internettet i form af online-foredrag, samt bogen ”Kodebogen”[5]. De resterende aspekter af opgaven kommer fra diverse hjemmesider, hvor den mest brugte af disse er Wikipedia.

Brugen af kryptering

Historiens anvendelser

Krypteringens historie stammer helt tilbage fra ca. 2500 f.Kr. i Egypten, hvor egypterne indgraverede ualmindelige hieroglyffer ind i deres monumenter. Noget mere konkret var grækernes brug af scytalaen i år ca. 700 f.Kr. – som bestod af en cylinder med en stribe pergament omkring. På dette pergament kunne skrives en række bogstaver, som kun kunne læses efter at pergamentet var foldet omkring en cylinder af den rigtige størrelse. Senere blev der udviklet mono- og polyalfabetiske chifferkoder, som begge fungerer ved at substituere hvert tegn med et andet tegn, og derved gøre teksten uforståelig.[6]

Det var dog først rigtigt i anden verdenskrig, at matematiske metoder blev taget i brug; særligt ved Enigma – en krypteringsmaskine udviklet af den tyske ingeniør Arthur Scherbius. Denne maskine fungerede ved hjælp af rotorer, som substituerede input på tastaturet ved hjælp af substitueringsmetoder.[7]

Kryptering er i vores tid brugt utallige steder, hvor de mest nævneværdige er netbanker og offentlige instanser. Kryptering benyttes ikke kun til at beskytte ens informationer fra at blive stjålet – det bruges også til verificering af den enkelte person, ved hjælp af digitale signaturer.

Alice og Bob

Indenfor moderne kryptologi anvendes ofte en række figurer, som repræsenterer en bestemt funktion indenfor krypteringen – Ud af de 24 figurer nævnes her de 4 vigtigste:

• Alice (fra ’A til B’), der vil sende en krypteret besked
• Bob (fra ’A til B’), der vil modtage Alices krypteret besked
• Eve (fra eavesdropper: en aflytter), der vil opsnappe informationer fra beskeden inden den når frem til Bob
• Mallory (fra malicious: skadelig), der vil både opsnappe beskeden, og direkte ændre den, eller bruge informationen til at sende falske beskeder til Bob

Nøgler

I moderne kryptering benyttes nøgler, som er de informationer der skal bruges, til enkryptering, dekryptering, eller begge. Hvis Alice vil enkryptere en besked, skal hun være sikker på, at Bob ved hvordan den skal dekrypteres igen. Tidligere blev dette gjort ved hemmeligholdt nøgleudveksling, men dette gjorde nøglen sårbar overfor Eve og Mallory, som med kendskab til nøglen kunne læse alle beskeder imellem Alice og Bob.

Senere blev det derfor en nødvendighed at udvikle et mere sikkert system, og dette førte til udviklingen af offentlige nøgler. Dette er systemet, som også benyttes i dag. Essensen i dette består i, at både Alice og Bob har en offentlig nøgle, som er tilgængelig for alle, og en privat nøgle, som de holder hemmelig for hinanden. Når Alice vil sende en besked til Bob, enkrypterer hun beskeden med Bobs offentlige nøgle, og denne besked vil kun Bob kunne dekryptere. På samme vis benytter Bob Alices offentlige nøgle til enkryptering, og Alice dekrypterer denne med sin private nøgle.

Ved digitale signaturer benyttes denne metode også, blot omvendt. Her enkrypterer Alice sin besked med sin private nøgle, og alle kan dekryptere denne med hendes offentlige nøgle. Men netop ved at hendes besked kan dekrypteres med hendes offentlige nøgle, bliver Bob bevidst om, at det kun kan være hende, som har sendt beskeden.

Brugbarhed kontra sikkerhed

I dag bygger sikkerheden i krypteringssystemer på, at det skal være beregningsmæssigt svært at bryde krypteringen – med dette menes det, at det er let at finde en metode til at bryde krypteringen, men selve udregningsprocessen vil tage mange år og derved ikke gøre informationen nyttig. Dette vil bliver gennemgået dybere i næste afsnit.

Jo hurtigere computerne bliver, jo kortere tid vil det derved tage at bryde disse krypteringer – derfor er der et krav om, at krypteringerne skal forbedres løbende. Dog kan nøglerne ikke bare 100-dobles eller mere, da dette vil forårsage at enkrypteringsprocessen vil tage for lang tid til, at det vil være praktisk anvendeligt. Der er således grænser, som krypteringsstandarderne skal ligge indenfor.

Algoritmisk kompleksitet

Beregningsmæssigt svære problemer er nævnt i sidste afsnit, og det dybereliggende problem i dette er måden, som en algoritme løser et problem på. Hvis køretiden i en algoritme vokser eksponentielt med størrelsen af inputtet, og der ikke er fundet nogen anden løsning, vil problemet siges at være beregningsmæssigt svært, da et meget stort input kan give alvorlige komplikationer i udregningen af denne.

Dog kan der også findes problemer, som både kan løses eksponentielt og polynomielt, altså at køretiden kun vokser med en fast eksponent til inputtet. En polynomieltidsløsning vil kunne løse problemer meget hurtigere end eksponentieltidsløsninger.

Et eksempel, ved brug af et polynomium af tredje grad og en eksponentialfunktion med rod 2:

Her kan tydelig ses, at en eksponentieltidsløsning er brugbar ved små inputstørrelser, men bliver kompliceret ved større input. Ved polynomieltidsløsningerne derimod, bliver antallet af processer indenfor en brugbar størrelse.

Dette kan eksemplificeres med et meget relevant problem: at definere om et tal n er et primtal eller ej. Meget ligetil kan man forsøge at reducere n mod x, hvor . Hvis alle disse mulige tal af x er forskellige fra 0, vil n være et primtal.

Denne metode kan dog forbedres, da aritmetikkens fundamentalsætning (forklaret i afsnittet ”Primtal”) fortæller, at alle positive heltal kan skrives som et produkt af primtal. Altså vil det kun være nødvendigt at teste primtalsværdier som værende x, for hvis ingen primtal ”går op i” x, vil x ikke have nogen primfaktorer andre end sig selv og 1, og så vil x netop være et primtal.

Udover dette kan metoden yderligere forbedres, ved at man udelukkende tjekker tal mindre end . Grunden til dette er, at hvis et tal, som ”går op i” x, er større end , vil kvotienten til dette altid være mindre end . Da kvotienten altid også vil ”gå op i” dividenden (x), vil der således til ethvert tal over , som ”går op i” x, være et tal under , som også ”går op i” x. Altså kan det konstateres, at der kun behøves at testes efter tal under .[8]

Alle disse ting har gjort metoden lettere, men det har dog ikke hjulpet på, at metoden stadig benytter sig af en eksponentieltidsløsning – et meget stort input vil stadig give en virkelig lang køretid. Der er dog lavet en polynomieltidsløsning på dette problem, som ikke vil gennemgås i dybere detaljer her grundet niveauet – dog kan nævnes, at ved brug af denne teknik, fik man bragt køretiden ned på et polynomium af 12. grad.[9]

Talteori

Restregning

Nutidens kryptering benytter beregninger med heltal, og dette indebærer således også brug af restregning ved division. At regne med rester er kendt for de fleste, da der blot menes, at hvis divisionen ikke ”går lige op”, skrives resten bagefter. Et eksempel:

Her vil resten altså være 3. En mere korrekt måde at skrive metoden på, ville være at divisionen skal fortsætte indtil resten bliver mindre end divisoren og større eller lig med 0. Hvis den resterende dividend er større end 0, er dette tal resten. Denne rest kaldes også den principale rest.

En anden måde at betegne denne udregning af den principale rest, er ved at benytte notationen mod (læses modulo):

Med brugen af modulo-notationen følger en række regler, hvor her nævnes de nævneværdige i denne sammenhæng:[10]

Den første sætning viser, at det at reducere en sum eller differens modulo n, er det samme som at reducere de enkelte led modulo n, derefter addere/subtrahere, og til sidst igen reducere dette modulo n. Et eksempel på den første sætning:

Den anden sætning viser blot at den første regel også gælder ved multiplikation. Den tredje regel viser, at dét at reducere en potensfunktion modulo n, er det samme som at reducere a modulo n, sætte dette i t’ende, og derefter reducere dette modulo n. Dette kan dog kun lade sig gøre, hvis t er en del af de naturlige tal.

Et eksempel på den anden sætning: 

Fælles divisorer

At kunne finde fælles divisorer betegnes ved at finde tal, som begge ”går op i” en række givne tal, som f.eks. at tallene 4 og 10 har fællesdivisorene 1, -1, 2, og -2. Den største fælles divisor er herefter det største tal blandt disse (tallet 2 i dette eksempel). Denne største fælles divisor kan skrives med notationen gcd(a, b), hvor a og b er de to givne tal (gcd = greatest common divisor), altså gcd(4,10) = 2.

Indenfor de største fælles divisorer findes også en række regneregler. Én af disse vil nævnes her:[11]

Denne sætning betyder at man kan reducere hvert tal modulo det andet tal, og stadig have den samme største fælles divisor. Et eksempel:

Beviset for denne sætning findes i bilag 1. Denne sætning kan bruges algoritmisk til at finde den største fælles divisor imellem 2 tal, ligegyldigt hvor store de er. Denne algoritme kaldes Euklids Algoritme (EA). Metoden lyder på skiftevis at reducere de to tal modulo det andet tal, indtil ét af tallene er 0 – det andet tal forskellig fra 0, vil så være den største fælles divisor. Et eksempel på tallene 1510 og 1208: 

Den modulært inverse

Hvis man har to tal p og q, hvis største fælles divisor er 1, vil der findes et tal t, som opfylder at . Altså t ganget med q, divideret med p, vil resultere i en rest på 1. Dette tal t kaldes den modulært inverse. Et eksempel på dette:

p = 37 og q = 89

At udregne den modulært inverse kan gøres med Euklids Modificerede Algoritme (EMA). Tre kolonner skal udføres med EMA, og udfyldningsproceduren forklares her kolonne for kolonne.[12]

Værdierne fra ovenstående eksempel vil følge forklaringen (p = 37 og q = 89):

I de to øverste felter i den første kolonne, i en tabel med 3 kolonner, startes med at skrive hhv. q i den øverste række, og dernæst p. De resterende felter udfyldes på følgende måde:

1. Kald feltet 2 felter højere oppe, for x
2. Kald feltet 1 felt højere oppe, for y
3. Feltets værdi er da x mod y

I den anden kolonne bliver værdierne indsat fra anden række – disse værdier udregnes på denne måde:

1. Kald feltet 1 felt til venstre, for x
2. Kald feltet ovenover x, for y
3. Feltets værdi er da y/x, rundet ned til det nærmeste hele tal

I den tredje og sidste kolonne indsættes i første række tallet 1, og i anden række

indsættes værdien af feltet til venstre, med negativt fortegn. Herefter udfyldes resten af kolonnen som følger:

1. Kald feltet 2 felter højere oppe, for x
2. Kald feltet 1 felt højere oppe, for y
3. Kald feltet 1 felt til venstre, for z
4. Feltets værdi er da

Disse kolonners værdier bliver herefter gentaget, indtil den nederste værdi i første kolonne er ét (de andre kolonner bliver ikke udfyldt i denne nederste række). Den modulært inverse af da værdien i den anden-nederste række i 3. kolonne, som i dette tilfælde er 5.

Dog bliver brugen af tabeller for bøvlet for computere, og algoritmen er her programmeret i Visual Basic for Applications (VBA), vist bid for bid:

Først defineres nogle variabelværdier. Variablerne brugt her er orign1, n1, n2, r1, r2, r3, r3_1, r3_2 og ModInv. De originale 2 tal defineres som orign1 og n2 – orign1 er defineret fordi at den originale værdi af n1 skal bruges senere, og fordi at n1 og n2 bliver varieret igennem algoritmen. Variablene n1 og n2 symboliserer samtidig de to nederste to tal i kolonne 1. Variablerne r1, r2 og r3 er rækkeværdierne i hhv. kolonne 1, 2 og 3. De to variabler r3_1 og r3_2 er meget lignende n1 og n2 – de symboliserer de nederste to tal i kolonne 3.

Da selve ’repetitionsprocessen’ i algoritmen først starter fra række 3, indsættes variablernes værdier fra række 1 og 2 før selve processen starter:

orign1 = indsæt første tal her

n2 = indsæt andet tal her

n1 = orign1

r2 = WorksheetFunction.RoundDown(n1 / n2, 0)

r3_1 = 1

r3_2 = -r2

Herefter starter den egentlige proces:

Do

r1 = n1 Mod n2

n1 = n2

n2 = r1

r2 = WorksheetFunction.RoundDown(n1 / n2, 0)

r3 = r3_1 – r2 * r3_2

r3_1 = r3_2

r3_2 = r3

End If

Loop Until r1 = 1

Alt hvad denne algoritme gør, er at indsætte kolonners værdier række for række, indtil det nederste tal i kolonne1 er 1. Herefter defineres den modulært inverse:

If r3_1 > 0 Then

ModInv = r3_1

Elseif r3_1 < 0 Then

ModInv = orign1 + r3_1

End If

Da den tidligere proces’ sidste omgang forårsagede at r3_1 = r3_2 og r3_2 = r3, altså at kolonne3’s nederste værdi er r3_2 og anden-nederste værdi er r3_1, benyttes her r3_1, da det netop er den anden-nederste værdi i tredje kolonne, som er den modulært inverse.

Hvis dette tal er større end 0, vil den modulært inverse blot være dette tal. Hvis det er negativt, vil den modulært inverse være det originale første tal plus r3_1.

Og den modulært inverse til de to valgte tal vil være gemt i variablen ModInv. 

Primtal

Et heltal større end 1, som kun har heltalsdivisorerne 1 og sig selv, kaldes et primtal. De første 10 primtal er således 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Disse tal er en vigtig bestanddel af de nuværende krypteringsmetoder, og nogle regler omkring disse vil her gennemgås. En af de vigtigste sætninger omkring primtallene, også kaldet aritmetikkens fundamentalsætning, lyder på at:

• Alle positive hele tal kan skrives som et produkt af primtal [13]

Et eksempel på dette kan være at tallet 567.483 kan primfaktoriseres til

. Dette vil vise sig at være en særdeles nyttig egenskab ved primtallene, til brug indenfor krypteringen.

Udover dette findes en anden vigtig sætning:

• Der findes uendeligt mange primtal [14]

Kendskabet til denne anden sætning er også nyttig indenfor bl.a. RSA-kryptosystemet, som benytter meget store primtal til krypteringsprocessen – og disse primtal bliver kun større, som tiden går (se afsnittet ”Sikkerhed kontra brugbarhed”).

Datalogiske aspekter

Alternative talsystemer

I forklaringen af AES-algoritmen benyttes både det hexadecimale talsystem og det binære talsystem. Skematisk kan disse to systemer sammenlignes med det decimale talsystem – dog skal nævnes at det hexadecimale talsystem har 16 mulige værdier på hver tals plads, og grundet dette indføres værdierne a, b, c, d, e og f, som betyder hhv. 10, 11, 12, 13, 14 og 15.

Hvis der som eksempel skrives 141 med det decimale talsystem, kan dette skrives som . Dette tal skrives i det binære talsystem som 10001101, da , og de tomme felter erstattes med nuller, præcis som i det decimale system. Tallet skrives i det hexadecimale talsystem som 8d, da .

Vi indfører her en notation, som vi vil bruge i denne opgave. Hvis et tal er skrevet i decimalsystemet (10-talssystemet), skrives det som . Tallet 100 i det decimale talsystem skrives altså som . Tilsvarende skrives hexadecimale tal som og binære som . Det skal dog nævnes, at denne notation kun benyttes dér, hvor der veksles imellem talsystemerne.

XOR

XOR er en forkortelse for eXclusive OR, og er en meget simpel procedure. Hvis der er givet to tal, som kan indtage værdierne 1 eller 0 (sandt eller fask), lyder reglerne for XOR:[15]

Altså sagt med ord, hvis inputstørrelserne er ens, returnér falsk. Hvis de er forskellige, returnér sand. Denne form for ’udregning’ bruger notationen Å – eksempelvis . Ved flere led udføres der bare XOR på hvert led for sig.

Hashfunktioner

En metode Alice kan lave digitale signaturer på, som er mindre krævende end at enkryptere hele klarteksten med hendes private nøgle, er at benytte hashfunktioner. En hashfunktion fungerer som et digitalt fingeraftryk, da den omdanner hele klarteksten til en lille størrelse på mellem 100-1000 bits.

Et eksempel på brugen af en hashfunktion kaldet SHA1 (Standard Hash Algorithm), på 160 bits:[16]

• Klartekst: ”The quick brown fox jumps over the lazy dog”

Hash: 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12

Denne hash, med denne SHA1 algoritme, vil altid være på 160 bits, ligemeget hvor stor input er. Denne hash kan herefter krypteres med Alices private nøgle, og derefter krypteres beskeden og den krypterede hash med Bobs offentlige nøgle. Når Bob modtager kryptoteksten, kan han dekryptere teksten med hans private nøgle, og dekryptere hashen med Alices offentlige nøgle. Han benytter herefter samme hashfunktion som Alice, til at udtrække en hash fra klarteksten. Hvis denne hash er den samme som den krypterede hash, er dette en sikkerhed for at Mallory ikke har ændret på klarteksten.

Hashfunktioner opererer med et begreb kaldet hash-kollisioner, som betyder, at flere forskellige typer input kan give samme hash. Dette skal naturligvis minimeres, og for at gøre dette har nyere hashfunktioner ’domino’-effekter, som kan illustreres ved tidligere klartekst-eksempel, med en minimal ændring:

• Klartekst: ”The quick brown fox jumps over the lazy dog”

Hash: 2fd4e1c6 7a2d28fc ed849ee1 bb76e739 1b93eb12

• Klartekst: ”The quick brown fox jumps over the lazy cog”

Hash: de9f2c7f d25e1b3a fad3e85a 0bd17d9b 100db4b3

Krypteringsteknikker

Advanced Encryption Standard

En krypteringsalgoritme, som ofte er brugt i øjeblikket, er Advanced Encryption Standard, som er forløberen til Data Encryption Standard (DES) og 3DES (udtales triple-DES)[17]. Denne algoritme benytter ikke offentlige nøgler, og nøgleudvekslingen imellem Alice og Bob er derfor problemet ved benyttelse af denne. AES bliver dog stadig brugt i sammenkædning med RSA-algoritmen, som forklaret i afsnittet ”RSA-kryptosystemet”.

I forklaringen af AES-algoritmen vil klarteksten blive anset i blokke a’ 16 tegn, opskrevet i en 4×4 matrix. Udover dette skrives tegnene i matricen som deres hexadecimalværdier. Hvis vi ville kryptere meddelelsen ”Hej med dig man!” (som er på præcis 16 tegn, så det passer i en enkelt blok, for simplificering), ændrer vi den først til hexadecimale værdier og opstiller den i en 4×4 matrix:

En AES-kryptering er en lang og kompliceret proces, men her prøves at forenkle de enkelte processer, og overskueliggøre det med relevante illustrationer. Overordnet set skal klarteksten først igennem en initialiseringsfase, derefter igennem 4 forskellige faser 9 gange, og til sidst 3 afsluttende faser, som illustreret på tegningen.

Altså findes der følgende 4 typer af faser:[18]

1. SubBytes
2. ShiftRows
3. MixColumns
4. AddRoundKey

SubBytes

I denne fase bliver de enkelte værdier i matricen erstattet af andre værdier. Dette foregår alt sammen ved hjælp af følgende tabel:

Hver celle i den tidligere 4×4 matrix ændres med denne tabel, hvor x-værdien repræsenterer første hexadecimale tegn i hver celle, og y repræsenterer det andet. F.eks. vil første celle i matricen 48 være 52, da x=4 og y=8. Resten af cellerne ændres:

ShiftRows

I anden fase bliver rækkerne i matricen ”skubbet” – forstået på den måde at anden, tredje og fjerde rækkes felter rykkes hhv. 1, 2 og 3 felter til venstre. Hvis feltet bliver rykket udenfor matricen, placeres det blot i 4. kolonne. Her vist række for række:

Her bliver << notationen benyttet til at indikere det antal gange, som rækken skal ”skubbes”. 

MixColumns

Dette tredje trin er hvor det begynder at blive mere krævende. Her skal hver kolonne ”ganges” på en fast bestemt matrix, bestående af 1-, 2- og 3-taller, som vist her med første kolonne i vores matrix:

En anden måde at skrive denne udregning op på, er som følger:

Altså at alle tal i første kolonne i første matrix, skal ganges med øverste tal i den anden matrix, alle tal i anden kolonne i første matrix skal ganges med andet øverste tal i den anden matrix, og så fremdeles. Summen af de enkelte rækker i første matrix bliver herved lagt sammen til en én-kolonne matrix.

Dette er dog hverken multiplikation eller prikprodukt, men bliver kaldt for en ”modulo multiplikation indenfor Rijndael’s Galois felt i en given matrix”[19] (Rijndael er en sammentrækning af skaberne af AES-algoritmen; Vincent Rijmen og Joan Daemen[20]). For at kunne forklare hvad multiplikation med tallene 1, 2 og 3 betyder, omskrives vores kolonnes værdier til binære tal:

Herefter kan vi opstille 4 regler, for ”multiplikation”:[21] [22]

• ”Multiplikation” med 1 efterlader lader blot input, som det er
• ”Multiplikation” med 2 ”skubber” det binære til venstre, så alle 1-taller rykker en plads til venstre. Tallets længde bevares, og i højre side indsættes derfor et nyt 0. Dette medfører også, at det ciffer mest til venstre bliver ”skubbet ud” af tallet, og forsvinder.
• ”Multiplikation” med 3 er det samme som med 2, bortset fra, at efter tallet er blevet ”skubbet” til venstre, udføres XOR med det originale tal (før det blev ”skubbet”)
• En sidste regel siger, at hvis et 1-tal ”skubbes” ud af tallet, skal der udføres XOR med tallet 00011011.

Hvis vi igen bruger tidligere matrix, og indsætter de binære værdier i stedet for de hexadecimale, får vi:

Og vi kan se at den udregnede første række vil kunne udregnes som:

Første multiplikation er med 2, og der skal tallet altså ”skubbes” en gang til venstre:

(<< 1 bliver betragtet som ”skub” én gang til venstre)

Her var det et 0, som blev skubbet ud, og der skal således ikke gøres andet.

Den anden multiplikation med 3 er som følger:

Da reglen for multiplikation med 3 sagde at man, udover at ”skubbe” tallet en gang til venstre, også skulle udføre XOR med det originale tal, får vi derfor tallet 11010111. Den anden og tredje multiplikation er blot med tallet 1, og der ændres tallene ikke. Til sidst skal de 4 tal summeres, og dette gøres i det binære talsystem ved XOR:

Og den første række lyder altså på værdien 11001101. Dette gøres ved alle 4 rækker, og denne nye 1×4 matrix erstatter første kolonne i den originale matrix. Herefter gøres samme proces på 2., 3. og 4. kolonne.

AddRoundKey

Denne sidste procedure er hvad der gør den enkelte AES-kryptering unik. Ud fra en nøgle, angivet som en 4×4 matrix, bliver der flere gange i løbet af AES-krypteringen lavet rundenøgler, som er nøgler, lavet udfra den første nøgle. Disse rundenøgler bliver herefter brugt til at kryptere klarteksten yderligere.[23]

Første nøgle er ikke udregnet, men er blot givet eller vilkårligt valgt. Et eksempel:

Når de efterfølgende rundenøgler skal laves (bliver i alt lavet 10 rundenøgler), bruges først sidste kolonne i nøglen (med værdierne 09, cf, 4f og 3c), og denne køres igennem en RotWord proces, som meget simpelt flytter den øverste værdi ned i bunden:

Herefter køres denne igennem førnævnte SubBytes proces (forklaret i afsnittet ”SubBytes”):

Derefter udføres der XOR på denne med den første kolonne i nøglen (med værdierne 2b, 7e, 15 og 16) og derefter XOR med første kolonne i rundekonstanten Rcon. Rcon er er en 10×4 matrix med konstante værdier – en kolonne til hver rundenøgle.

Rcon ser ud som følger:[24]

Altså ser XOR-udregning ud til den første kolonne i første rundenøgle:

For at udføre denne udregning, skal alle cellerne konverteres til binære tal, og derefter XOR enkeltvis. Dette leder til følgende 1×4 matrix:

Dette er herved første kolonne i den første rundenøgle. De resterende 3 kolonner i nøglen udregnes blot ved at XOR kolonnen én gang til venstre med kolonnen 4 gange til venstre. Hvis vi beskuer hvordan nøglen, og den første kolonne i rundenøglen ser ud:

Altså skal kolonnen til venstre for den første tomme kolonne (med værdier a0, fa, fe og 17) XOR med kolonnen 4 gange til venstre (med værdier 28, ae, d2 og a6):

Nøglen og rundenøglen ser herefter ud således, efter processen er udført på de resterende 3 kolonner:

De resterende rundenøgler udregnes på samme vis (dog bruges 2. kolonne af Rcon i kreationen af 2. rundenøgle osv.). Disse rundenøgler bliver herefter brugt til at kryptere klarteksten yderligere, ved at XOR klarteksten med rundenøglen (ved at XOR første kolonne i klarteksten med første kolonne i rundenøglen, så anden nøgle, tredje og fjerde).

I starten af dette afsnit kan ses i hvilken rækkefølge alle disse processer skal udføres, og alt i alt er der tale om en masse processer, der skal udføres for hver eneste blok af tekst til en samlet kryptering.

Ved dekryptering bruges samme nøgle, og alle processerne laves ’inverst’, som blot er det processen bagfra. Rækkefølgen, som processerne skal køres i, er dog ikke omvendte, men er i følgende rækkefølge:[25]

• KeyExpansion[26]
• InvAddRoundKey
• InvShiftRow

• InvSubBytes
• InvAddRoundKey
• InvMixColumn
• InvShiftRow
• InvSubBytes
• InvAddRoundKey

Og med kryptoteksten som input, får man herefter klarteksten som output.

RSA-kryptosystemet

RSA algoritmen blev opfundet i 1977 af Ron Rivest, Adi Shamir og Len Adleman – hvorfra navnet RSA også kommer.[27] Sikkerheden i RSA algoritmen ligger i det beregningsmæssig svære problem at primfaktorisere store tal. RSA kan både bruges til enkryptering og til digital signering.

Systemet fungerer således:[28]

1. Vælg to store primtal p og q (i praksis er de på 100+ cifre). Sæt n = pq.
2. Beregn
3. Vælg et tal e, så og
4. Beregn tallet d, som den modulært inverse til e modulo k. Altså at

Herefter er den offentlige nøgle n og e, og den private nøgle er d. Et eksempel i meget lille målestok:

Her vælges p = 43 og q = 79. Herefter er , og k udregnes:

Herefter skal vælges et tal e, større end 0 og mindre end k, og som ingen fælles divisorer har med k (andet end 1). I dette tilfælde vælges tallet 1901.

Til sidst skal d beregnes som den modulært inverse til e = 1901 mod k = 3276. Dette tal kan udregnes med EMA med algoritmen, nævnt i afsnittet ”Den modulært inverse”, og udregnes til at være 2921.

Altså er den offentlige nøgle i dette tilfælde , og den private er 2921.

Hvis en person ville forsøge at bryde krypteringen, med de givne informationer at n = 3397 og e = 1901, bliver han først nødt til at primfaktorisere tallet n, hvorefter han kan udregne k, og derefter også d. I dette lille eksempel vil det ikke være det store problem at primfaktorisere 3397, men problemet indtræder ved at prøve at primfaktorisere tal såsom:

8128012729552260747003229233330579069530397449644798954279936517323903753134219266537670968121334659187283971517871992808649401899318894981662046583900539[29]

Da der ikke er opfundet en måde at primfaktorisere i polynomiel tid, vil dette tage adskillige år at løse. Når der skal enkrypteres en tekst, laves teksten om til tal (ved brug af ASCII eller andet), og disse tal opdeles i blokke, så hver bloks værdi m, er mindre end n og større end 0.

Den enkelte blok m enkrypteres til den krypterede tekst c således:[30]

Den enkelte blok c dekrypteres til klarteksten m, således:³⁰

Så ved det tidligere simple eksempel, hvis tallene 123456789 skulle enkrypteres, skulle de først inddeles i blokke, som er mindre end n = 3397. Dette kan gøres ved at opdele dem i 3 blokke a’ 3 tal: 123 456 789. Disse blokke skal herefter enkeltvis enkrypteres med ovenstående formel:

Altså ser den krypterede tekst således ud: 1770 2384 1579. Udover dette kan man så yderligere bruge blok-chifferkoder til at ”blande” blokkene rundt, som så komplicerer problemet yderligere.

Hvis man skal dekryptere denne kryptotekst, foregår det så ved brug af den anden formel:

Og herefter har man sin originale klartekst 123456789.

Sammenhængen mellem AES og RSA

Hvis man sammenligner AES og RSA’s forhold imellem nøglelængde og sikkerhed, kan man se en klar forskel:[31]

Her kan altså ses, at RSA-nøglen skal være betydeligt længere end AES-nøglen, for samme sikkerhedsniveau. Derfor er det er en krævende proces for store inputstørrelser at RSA-enkryptere hele meddelelser, og derfor bliver RSA-algoritmen i stedet benyttet til at løse problemet med privat nøgleudveksling i AES:[32]

1. Alice krypterer sin klartekst med et regulært kryptosystem såsom Advanced Encryption Standard (AES)
2. Nøglen til AES-krypteringen bliver herefter RSA-enkrypteret med Bobs offentlige nøgle
3. kan Alice også uddrage en hash af klarteksten, og RSA-enkryptere den sammen med nøglen til AES-krypteringen, med Bobs offentlige nøgle.
4. Alice sender både den AES-enkrypterede kryptotekst og den RSA-enkrypterede AES-nøgle og hash.
5. Bob RSA-dekrypterer AES-nøglen og hashen med sin private nøgle, og bruger denne nøgle til at AES-dekryptere kryptoteksten, og får herefter klarteksten. Herefter kan han uddrage en hash (med samme hashfunktion som Alice) af klarteksten, og se om denne hash er identisk med den dekrypterede hash fra Alice.

På en sådan måde, vil det være meget svært for Eve eller Mallory at kunne gøre noget som helst med nogen af tingene. Alt de kan opsnappe er to kryptotekster, krypteret med hhv. AES og RSA.

Kvantecomputere

Introduktion

Fremtiden indenfor computerverdenen ser meget anderledes ud end nu, i hvert fald i forhold til computerkraft. Kvantecomputeren opererer med såkaldte kvantebits, som kan udføre et eksponentielt antal af processer på samme tid, i modsætning til de regulære computere, som kun fungerer lineært på den front. Indtil videre er de nuværende kvantecomputere langsommere end normale computere, da de kun har 12 kvantebits og da disse kvantebits ikke kan kobles sammen ligetil, som med normale bits.[33] [34]

Grundet denne eksponentielle stigning i antallet af samtidigt udførte processer, vil kvantecomputere være i stand til at løse beregningsmæssigt svære problemer indenfor en rimelig tid. Dette kan give en masse problemer indenfor bl.a. kryptologien, som er forklaret i afsnittet ”Fremtidens krypteringssikkerhed”. 

Kvantebits – QuBits

Kvantebits, eller QuBits, som de også kaldes, adskiller sig fuldstændigt fra normale bits. Hvor normale bits kan have 2 positioner, 0 og 1, kan kvantebits have positionerne 0, 1 og en superposition af 0 og 1 – denne superposition betyder, at kvantebits kan have værdierne 0 og 1 på samme tid. [35] [36] Grunden til hvordan dette kan lade sig gøre, ligger indenfor kvantefysikken, og vil ikke gennemgås her.

Dog kan man opstille et eksempel, som viser den klare forskel på bits og kvantebits – her vist med hhv. 4 bits og kvantebits:

• 4 bits vil kunne have én værdi på et givet tidspunkt, som f.eks. 1001.
• 4 kvantebits vil kunne have følgende værdier på et givet tidspunkt, på samme tid:

Her kan tydeligt ses den massive forskel der er, imellem de 2 former for bits. Antallet af processer, som kvantebits kan udføre på én gang, defineres som:

, hvor n er antallet af kvantebits. Denne kan her illustreres – og her kan nævnes at der i 2007 blev lavet en kvantecomputer med 16 kvantebits[37]: 

Fremtidens krypteringssikkerhed

De beregningsmæssigt svære problemer munder alle ud i, at antallet af processer der skal udføres, stiger eksponentielt med inputtet. [38] [39] Dette er et problem for de nuværende computere, da deres processorkraft stiger lineært med antallet af bits. Men da kvantebits’ særlige egenskab netop er, at antallet af processer udført samtidigt er eksponentielt stigende med antallet af kvantebits, vil udviklingen af større kvantecomputere blot følge udviklingen af krypteringsstørrelserne.

Dette vil forårsage, at kvantecomputerne vil være i stand til at bryde krypteringer, selvom der ikke findes en polynomieltidsløsning til disse problemer, som krypteringen bygger på.^{38 39} Altså vil der være krav efter helt nye former for krypteringsmetoder, som umiddelbart ikke vil kunne løses vha. bruteforce (at teste alle mulige løsninger) – for alternativet vil i værste tilfælde være, at internettet bliver så usikkert, at systemer som netbanker og digitale signaturer ikke vil kunne eksistere.

Vurdering af krypteringens betydning

Kryptering er en essentiel del af moderne IT-samfund, og dens betydning er kun blevet endnu større, med stigningen af antallet af hackere. Med implementeringen af netbanker og offentlige online-tjenester såsom skat og SU, er det kun blevet endnu vigtigere at kunne vedligeholde en sikker linje.

Og det ser ikke ud til at antallet af tjenester over nettet er faldende. Tværtimod, så bliver flere og flere aspekter af vores liv overført til en netløsning. Dette lægger et yderligere større pres på krypteringsniveauet.

Med den fremtidige implementering af kvantecomputere indenfor den nærmeste fremtid, vil alle disse net-tjenester, som vil fylde mere i vores liv end nu, blive usikre. Dette betyder i værste tilfælde, at størstedelen af de ting, som der bliver gjort i vores liv, let vil kunne blive udsat for angreb. For at undgå alt dette, bliver en alternativ krypteringsmetode et krav til at vedligeholde det nuværende sikkerhedsniveau.

Konklusion

I denne rapport er krypteringens historie samt nuværende brug, forklaret. Grundteorien indenfor den talteoretiske gren af matematikken er redegjort, og ligeledes visse datalogiske elementer, som er relevante for kryptologien. AES- og RSA-kryptosystemet er forklaret dybdegående, hvori der er blevet brugt den foregående teori. Sammenspillet imellem brugen af AES- og RSA-algoritmen er forklaret, og hvorfor netop denne kombination er sikker.

Fremtidens udsigter indenfor kryptologiens- og computerens verden, med et særligt fokus på implementeringen af kvantecomputere, er blevet vurderet. Kvantecomputerens særlige funktioner er i denne sammenhæng blevet redegjort, dog med udeladelse af de rent kvantefysiske aspekter af disse. Til sidst er krypteringens vigtige betydning for det moderne IT-samfund blevet forklaret, og hvordan fremtidens udsigter vil påvirke den stigende indflydelse, som krypteringen har på samfundet i dag.

Bilag

Bilag 1 – Bevis for Euklids Algoritme[40]

Påstanden er:

En alternativ måde at opstille den første ligning på, er:

, hvor , og r er resten af b ved division med a.

Denne division b/a opstilles således, hvor q er kvotienten og r er resten:

, hvor og

Denne opstilling er sand, for hvis a ”går op i” b, vil resten være nul, og ligningen vil kunne skrives på følgende måde:

Hvis a ikke ”går op i” b, vil der være en rest r, som lægges til højre side af ligningstegnet. Vi isolerer r i ligningen:

Denne værdi af r indsætter i vores originale sætning, og vi skal bevise at:

Vi sætter og . Dette betyder så, at f₁ ”går op i” både a og b. Disse opstilles i ligningerne:

Herefter ganges hver af disse sider med :

Herefter kan disse to ligninger indsættes i en fælles ligning, og omskrives til følgende:

Denne viser, at xa + yb divideret med f₁ giver os en heltallig kvotient, da x, y, q₁ og q₂ er en del af de hele tal Z. Altså er vist at f₁ ”går op i” enhver linearkombination af a og b. Dette betyder derfor også at f₁ ”går op i” (b – qa). Altså er vist at både f₁ og f₂ er fælles divisorer i (a, b – qa), og da f₂ er den største fælles divisor må:

På samme måde som med f₁, kan vises at f₂ ”går op i” b. Vi viste før, at hvis et heltal h ”går op i” to andre forskellige heltal i og j, vil h også ”gå op i” enhver linearkombination af i og j. I tilfældet med f₂ er h = f₂ , i = a og j = (b – qa). Herefter kan der altså skrives linear kombinationen qa + (b – qa), som kan omskrives til b. Da f₂ ”går op i” linearkombinationen, ”går den også op i” b. Dette betyder at både f₁ og f₂ er fælles divisorer i a og b, og da f₁ er største fælles divisor, må:

Disse to resultaterog, må derfor betyde at . Dette betyder så samtidigt at er sand, da de to største fælles divisorer er lig med hinanden. Dette medfører så også at er sand, og altså også ligningen benyttet i Euklids Algoritme: .

Litteraturliste

• Landrock, Peter og Knud Nissen: Kryptologi – fra viden til videnskab. Side 50-133. 1. udg. ABACUS, 1997. (Bog)
• Singh, Simon: Kodebogen – Videnskaben om hemmelige budskaber – fra oldtidens Ægypten til kvantekryptering. På dansk ved Jan Teuber. Side 331-364. 1. udg. Gyldendal, 2001. (Bog)
• Riber, Peter: Kryptering. 2. udg. Systime, 2007. (Bog)
• YouTube: Theory and Practice of Cryptography. Udgivet af GoogleTechTalks. Sidst opdateret: 30.11.2007. Internetadresse: http://www.youtube.com/watch?v=IzVCrSrZIX8 – Besøgt d. 26.11.2010 (Internet)
• DR: Fremtidens Kvantecomputer. Udgivet af DR. Sidst opdateret: 02.03.2010. Internetadresse: http://www.dr.dk/DR2/Danskernes+akademi/IT_teknik/Fremtidens_kvantecomputer.htm – Besøgt d. 26.11.2010 (Internet)
• YouTube: QuBit: Introducing Quantum Superpositions. Udgivet af fosdemtalks. Sidst opdateret: 14.02.2010. Internetadresse: http://www.youtube.com/watch?v=bxC8__H2Yg8 – Besøgt d. 26.12.2010 (Internet)
• Wikipedia: History of Cryptography. Sidst opdateret: 11.11.2010. Internetadresse: http://en.wikipedia.org/wiki/History_of_cryptography – Besøgt d. 27.11.2010 (Internet)
• Wikipedia: Enigma (Machine). Sidst opdateret: 30.11.2010. Internetadresse: http://en.wikipedia.org/wiki/Enigma_(machine) – Besøgt d. 27.11.2010 (Internet)
• A Polynomial-Time Algorithm. Sidst opdateret: ca. 2003. Internetadresse: http://primes.utm.edu/prove/prove4_3.html – Besøgt 02.12.2010 (Internet)
• CSEE: 128-bit AES decryption. Sidst opdateret: 05.2008. Internetadresse: http://www.cs.columbia.edu/~sedwards/classes/2008/4840/reports/AES.pdf – Besøgt 03.12.2010 (Internet)
• Understanding AES Mix-Columns Transformation Calculation. Sidst opdateret: Ukendt. Internetadresse: http://www.angelfire.com/biz7/atleast/mix_columns.pdf – Besøgt 03.12.2010 (Internet)
• Wikipedia: Rijndael mix columns. Sidst opdateret: 17.08.2010. Internetadresse: http://en.wikipedia.org/wiki/Rijndael_mix_columns – Besøgt 03.12.2010 (Internet)
• Wikipedia: Advanced Encryption Standard. Sidst opdateret: 01.12.2010. Internetadresse: http://en.wikipedia.org/wiki/Advanced_Encryption_Standard – Besøgt 03.12.2010 (Internet)
• Rijndael Cipher. Sidst opdateret: Ukendt. Internetadresse: http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf – Besøgt 03.12.2010 (Internet)
• Big Number Calculator Applet. Sidst opdateret: 07.01.2007. Internetadresse: http://world.std.com/~reinhold/BigNumCalc.html – Besøgt 03.12.2010 (Internet)
• Wikipedia: SHA. Sidst opdateret: 30.11.2010. Internetadresse: http://da.wikipedia.org/wiki/SHA – Besøgt 04.12.2010 (Internet)
• RSA Algorithm. Sidst opdateret: 20.11.2010. Internetadresse: http://www.di-mgt.com.au/rsa_alg.html – Besøgt 04.12.2010 (Internet)
• : Kvantecomputer. Sidst opdateret: 20.10.2010. Internetadresse: http://da.wikipedia.org/wiki/Kvantecomputer – Besøgt 04.12.2010 (Internet)
• Ingeniøren: Kommerciel kvantecomputer taget i brug. Sidst opdateret: 30.03.2007. Internetadresse: http://ing.dk/artikel/77550 – Besøgt 04.12.2010 (Internet)
• Wikipedia: Exclusive Or. Sidst opdateret: 24.11.2010. Internetadresse: http://en.wikipedia.org/wiki/Exclusive_or – Besøgt 06.12.2010 (Internet)

[1] Advanced Encryption Standard

[2] Ron Rivest, Adi Shamir and Len Adleman – the creators of the RSA-algorithm

[3] Landrock, Peter og Nissen, Knud: ”Kryptologi – fra viden til videnskab”. 1. udg.

[4] Riber, Peter: ”Kryptering”. 2. udg.

[5] Singh, Simon: ”Kodebogen – Videnskaben om hemmelige budskaber – fra oldtidens Ægypten til kvantekryptering”. 1. udg. På dansk ved Jan Teuber.

[6] http://en.wikipedia.org/wiki/History_of_cryptography

[7] http://en.wikipedia.org/wiki/Enigma_(machine)

[8] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 86

[9] http://primes.utm.edu/prove/prove4_3.html

[10] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 73

[11] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 75

[12] Peter Riber: ”Kryptering”, s. 35-37

[13] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 84

[14] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 85

[15] http://en.wikipedia.org/wiki/Exclusive_or

[16] http://da.wikipedia.org/wiki/SHA

[17] http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

[18] http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

[19] http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf

[20] http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

[21] http://en.wikipedia.org/wiki/Rijndael_mix_columns

[22] http://www.angelfire.com/biz7/atleast/mix_columns.pdf

[23] http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

[24] http://www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf

[25] http://www.cs.columbia.edu/~sedwards/classes/2008/4840/reports/AES.pdf

[26] KeyExpansion er bare den originale AddRoundKey, bortset fra at den laver alle 10 rundenøgler i træk.

[27] http://www.di-mgt.com.au/rsa_alg.html

[28] Peter Riber: ”Kryptering”, s. 41 & Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 101

[29] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 111

[30] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 102

[31] http://www.di-mgt.com.au/rsa_alg.html

[32] Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 112

[33] http://da.wikipedia.org/wiki/Kvantecomputer

[34] http://www.dr.dk/DR2/Danskernes+akademi/IT_teknik/Fremtidens_kvantecomputer.htm

[35] http://da.wikipedia.org/wiki/Kvantecomputer

[36] http://www.dr.dk/DR2/Danskernes+akademi/IT_teknik/Fremtidens_kvantecomputer.htm

[37] http://ing.dk/artikel/77550

[38] http://da.wikipedia.org/wiki/Kvantecomputer

[39] http://www.dr.dk/DR2/Danskernes+akademi/IT_teknik/Fremtidens_kvantecomputer.htm

[40] Sammentrækning af beviset for 4.1, 4.6(4) og 4.11. Peter Landrock og Knud Nissen: ”Kryptologi – Fra viden til videnskab”, s. 70-75.