3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 1 af 23
Indholdsfortegnelse
INDHOLDSFORTEGNELSE .......................................................................................................... 1
INDLEDNING .................................................................................................................................... 2
KRYPTOLOGI .................................................................................................................................. 2
KLASSISKE KRYPTERINGSMETODER .................................................................................................. 4
PUBLIC KEY KRYPTERING .................................................................................................................. 6
RSA-KRYPTOSYSTEMET ............................................................................................................. 8
TALTEORI......................................................................................................................................... 8
SÆTNING 1 (PRIMTAL – ENTYDIG FAKTORISERING). ......................................................................... 8
SÆTNING 2 (DIVISION MED REST). .................................................................................................... 9
DEFINITION 2.1 ............................................................................................................................... 10
SÆTNING 3 ...................................................................................................................................... 10
BEVIS 3.1: ....................................................................................................................................... 10
SÆTNING 4 ...................................................................................................................................... 11
BEVIS 4.1: ....................................................................................................................................... 11
SÆTNING 5 (EULERS SÆTNING) ....................................................................................................... 12
BEVIS 5.1 ........................................................................................................................................ 12
ALGORITMEN BAG RSA ............................................................................................................. 13
ET RSA EKSEMPEL ...................................................................................................................... 14
BEVISET: ......................................................................................................................................... 17
SIKKERHEDEN BAG RSA – KAN DET BRYDES? .................................................................. 18
DIGITAL SIGNATUR .................................................................................................................... 19
HF 2. år
LITTERATURLISTE: .................................................................................................................... 21
BØGER, ALMENT OM KRYPTOLOGI .................................................................................................. 21
ARTIKLER MV. OM KRYPTOLOGI ...................................................................................................... 21
TALTEORI MV. BAG KRYPTOLOGI .................................................................................................... 21
INTERNET ADRESSER: ...................................................................................................................... 21
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 2 af 23
Indledning
I takt med den teknologiske udvikling er kravet om forbedre datasikkerhed også vokset. Ser vi fx på
Internettet, der med sin åbenhed gør det let for andre at opsnappe meddelelser, der rejser gennem
det – hvilket betyder at det er svært sende fortrolige meddelelser eller økonomiske oplysninger, som
fx informationer om kreditkort. For at løse dette problem har man været nødt til at udvikle
kryptosystemer, hvilket jeg finder interessant og derfor har jeg valgt at skrive min tredjeårsopgave
herom.
Et af de mest kendte/anvendte kryptosystemer der er, er systemet RSA, jeg har derfor i
min opgave især lagt vægt på at belyse dette system. Før jeg gør dette, vil jeg først kort gennemgå
nogle klassiske krypteringssystemer – de såkaldte konventionelle kryptosystemer, formålet dette
med er, udover at være en indledning til emnet også, at man skal kunne se forskellen i måden
hvormed der krypteres på i forhold til konventionelle systemer og systemer som RSA. Fra de
konventionelle kryptosystemer vil jeg bevæge mig over til Public Key-kryptering, som vil lægge op
til det opgaven hovedsageligt vil bygge på – nemlig RSA-systemet. RSA anskueliggøres ved først
at gennemgå den væsentligste talteori bag, derefter vises hvordan det fungerer bl.a. ved et eksempel,
hvorefter et bevis følger for at vise, at man må gøre som man gør.
Herefter vil jeg komme ind på sikkerheden bag RSA-systemet. Jeg vil bl.a. give et
eksempel hvor systemet er blevet brudt. Herudfra forklares, hvordan det kan lade sig gøre, og om
eksemplet i det hele taget er realistisk.
Jeg vil slutte ved at vise, hvad RSA-systemet også kan benyttes til udover at hemmeligholde en
besked, idet jeg vil komme ind på begrebet Digital Signatur, hvad det er og hvad det kan bruges til.
Kryptologi
Kryptologi er læren om, hvordan man kan forvandle en normal læselig tekst, der fx er skrevet på
almindelig dansk (klartekst), til en tekst der bliver uforståelig for uvedkommende (kryptotekst),
men læsbar for indviede. Et kryptosystem er altså med andre ord en metode, hvormed en tekst kan
sendes mellem en modtager og en afsender, uden at andre kan læse denne. Processen hvormed
teksten ændres fra klartekst til kryptotekst kaldes enkryptering. Den omvendte proces, hvor
kryptoteksten ændres til klartekst, kaldes for dekryptering
1
.
1
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 12
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 3 af 23
En traditionel model, kan skitseres således:
Fig.1. Konventionelt kryptosystem – secret- key system
På figuren ses modellen over et konventionelt kryptosystem
2
. Det essentielle ved et konventionelt
kryptosystem er, at dens sikkerhed er baseret på en fælles hemmeligholdt nøgle, som kun afsender
og modtager er i besiddelse af
3
. Ser vi igen på figuren, har vi altså en afsender, vi kalder hende for
Alice, og en modtager, som vi kalder for Bob. Vi forstiller os nu, at Alice vil sende en meddelelse,
som vi kalder M til Bob. Da den meddelelse som Alice ønsker at sende, er meget fortrolig,
enkrypterer hun først sin klartekst, så denne bliver ulæselig. Dette gør hun ved hjælp af en algoritme
og en nøgle, som både hun og Bob på forhånd er blevet enige om. For at kunne fremkalde Alices
klartekst igen, skal Bob have kendskab til samme nøgle som Alice og bruge denne til dekryption.
Meddelelsen som Alice sender, sendes via en ubeskyttet telefonlinje, brevpost, e-mail eller
lignende. Det betyder, at der er mulighed for, at den krypterede meddelelse bliver afluret af en
spion, som vi kalder Oscar. Oscar har til hensigt at bryde systemet og afsløre meddelelsens
hemmelighed, men for at kunne gøre dette, er han naturligvis nødt til at bryde koden eller kende til
nøglen. Traditionelt har lineære kryptosystemer været brugt. Metoden til at bryde denne slags kan
fx være ved at ”gætte” en løsning ved hjælp af en kryptoanalyse, hvilket der dog kræver, at
kryptoteksten er tilstrækkelig lang. I så fald ville han, ved at sammenligne bogstavfrekvensfordeling
2
P. Lefton ”Number Theory and Public-Key Cryptography” (Tidsskrift: Mathematics Teacher) side 54
3
K. Nissen ”Kryptologi – læren om hemmelig skrift I”. (Tidsskriftet Veritas) side 7
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 4 af 23
i det almindelige sprog med bogstavfrekvensfordeling i kryptoteksten, se en sammenhæng i
frekvensfordelingen, hvilket kan betyde, at han kan bryde koden
4
(Se bilag 1).
Klassiske krypteringsmetoder
3 klassiske metoder inden for kryptologien er: steganografi ,transposition og substitution. Fælles
for de tre er, at det er en nødvendighed at afsender og modtager, mødes inden for at udveksle
nøgler.
Ved steganografi skjules meddelelsen, den krypteres altså ikke direkte. Et eksempel
herpå kunne være Histiaeus’s metode, hvor meddelelsen bliver tatoveret i hovedbunden på et
sendebud. Et andet og mere nutidig eksempel er kodehuskeren nede fra banken, hvor koden
gemmes blandt en mængde tal.
Ved transposition er enkrypteringen sket ved, at rækkefølgen af klarteksten er blevet
ændret, hvilket nødvendigvis også betyder, at symbolerne (bogstaverne) i klarteksten og
symbolerne i kryptoteksten er de samme.
Et eksempel:
Enkrypteringen fungerer på den måde, at man skriver meddelelsen vandret på kvadreret papir,
naturligvis uden mellemrum og andre tegn, hvorefter man aflæser den krypterede tekst lodret, og
skriver teksten op i blokke af fx 4. Hvis vi krypterer sætningen ”HER KRYPTERES VED
TRANSPOSITION” vil denne først skrives vandret således:
H E R K R Y P T
E R E S V E D T
R A N S P O S I
T I O N
Derefter aflæses den krypterede tekst lodret, og skrives i blokke a 4 bogstaver. Kryptoteksten vil
altså komme til at se ud således:
HERT ERAI RENO KSSN RVPY EOPD STTI
4
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 26
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 5 af 23
Modtagerne af den krypterede tekst er nødt til at vide, hvor lange rækkerne er, for at kunne
dekryptere meddelelsen. I vores eksempel var længden på rækkerne 8, dvs. nøgle til kryptoteksten
er her 8. Hvis modtageren kender dette tal, vil han være i stand til at læse teksten, ved først at tælle
antallet af bogstaver (28), og derefter dividere med 8. Han ser derved, at der skal laves tre hele
rækker, idet
48328
samt at der i fjerde række kun skal benyttes de fire første rækker.
Modtageren kan nu dekryptere beskeden ved, at opskrive den horisontalt som vi gjorde, da vi
krypterede beskeden. Et krypteringssystem som dette er naturligvis ikke særlig sikkert, idet at
uvedkommende blot skal forsøge sig frem med forskellige gæt på længden af rækkerne, indtil et
forståeligt ord fremkommer. Derfor avancerede man da også systemet en smule. Det var bl.a. et
sådant udvidet system, som blev anvendt i den amerikanske borgerkrig
5
. Her foretog man en
ombytning af søjlerne, før kryptoteksten blev udskrevet. Dette kunne gøres fordi man på forhånd
havde valgt et nøgleord, hvori hvert bogstav repræsenterede et kolonnenummer.
Ved substitution enkrypteres teksten på den måde, at man sætter et nyt bogstav i stedet
for det almindelige fx, kunne der dannes et ”nyt” alfabet, hvor det var rykket tre pladser, således at
A blev til D osv.. Et eksempel hvor enkrypteringen er sket ved substitution, kunne i så fald være:
”hej” forskydes 3 pladser i alfabetet, herved fremkommer ”khm” i stedet.
Disse krypteringsmetoder er som sagt alle en smule gammeldags og meget upraktiske,
idet afsender og modtager først skal mødes inden og udveksle nøgler. Derudover er sikkerheden
heller ikke stor i de klassiske krypteringsmetoder. Der er dog også moderne udgaver af
konventionel kryptering. Det mest kendte her indenfor er DES-kryptosystemet, der blev udviklet i
1977
6
. DES anvendes specielt inden for bankverden fx i Dankort. DES er en bladning af
substitution og transposition, hvilket gør, at sikkerheden kommer op på et niveau, hvor det er
acceptabelt. Faktisk er den eneste mulighed for at bryde en DES en udtømmende søgning – altså
undersøge alle mulige løsninger. Jeg vil ikke nærmere komme ind på algoritmen bag DES-systemet,
da dette vil være for omfattende, men blot henvise til bogen ”Cryptography – Theory and practice”
kapitel 3.
Vi har altså her set eksempler på nogle kryptosystemer, der alle har det tilfælles, at de er baseret på
secret-key begrebet, altså hvor en hemmeligholdt nøgle bruges til at låse med og til at låse op med.
5
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 19
6
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 50
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 6 af 23
Derfor er det altså nødvendigt at der udveksles nøgler først, hvilket som sagt er meget besværlig og
upraktisk. Man havde derfor et behov om få løst problemet med nøgle-distribution.
Det var derfor lidt af en sensation i 1976, da Whitfield Diffie og Martin Hellman
præsenterede et kryptosystem der blev kaldt: ”One of the most significant cryptographic ideas of all
time” (Smith 1983)
7
. Kryptosystemet, der i opbygning lignede en smæklåseorganisme, fungerede på
den måde at Bob konstruerer en smæklås. Denne er tilgængelig for alle, den kunne for eksempelvis
ligge på Internettet. Når folk så vil sende en besked til Bob slår de blot hans smæklås op (metoden
til at enkrypterer med), og enkrypterer deres meddelelse. Denne sendes nu til Bob som en slags
sikkert konvolut som kun han har mulighed for åbne i det han er den eneste, der kender nøglen til
smæklåsen (udfra sit kendskab til konstruktionen af smæklåsen)
8
. Denne nye form for kryptosystem
som Diffie og Hellman præsenterede kaldes for et Public-key kryptosystem
9
.
Public key kryptering
I et public key kryptosystem anvendes 2 nøgler: en public key og en private key, hvorimod der i
secret key kryptografi, som sagt, kun anvendes én nøgle til at enkryptere med og dekryptere med.
Der er ikke i public key systemet krav om at Alice og Bob skal mødes inden og udveksle nøgler, det
essentielle er som sagt, at alle kan enkryptere meddelelsen, mens det kun er personen med
hemmelige nøgle der kan dekrypterer meddelelsen. Dette kan skitseres således:
Fig.2. Diffie og Hellmans public key kryptosystem
10
7
P. Lefton ”Number Theory and Public-Key Cryptography” (Tidsskrift: Mathematics Teacher) side 55
8
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 56
9
P. Lefton ”Number Theory and Public-Key Cryptography” (Tidsskrift: Mathematics Teacher) side 55
10
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 56
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 7 af 23
På figuren ser vi altså igen afsenderen Alice, der ønsker at sende en meddelelse til Bob uden at
uvedkommende skal kunne læse den. Derfor enkrypterer hun først sin klartekst M ved hjælp af
Bobs offentlige nøgle, som han har offentliggjort, fx Internettet. Kryptoteksten sendes herefter til
Bob via en ubeskyttet kanal, krypoteksten kan altså risikerer at blive afluret. Når Bob modtager
kryptoteksten anvender han sin hemmelige nøgle til dekryptering, hvorefter han nu er i stand til at
læse meddelelsen. Vi ser altså her, at ved denne metode kan man blive helt fri for, at nogen
hemmelig nøgle skal udveksles. Desuden er det værd at bemærke, at enkrypteringsalgoritmen og
dekrypteringsalgritmen er offentlig kendte
11
For at kalde et public key kryptosystem for godt stilles visse krav til systemet. Her er bl.a. nogle af
de krav Diffie og Hellman satte til et public key system (bemærk de er ændret en smule).
1) Det skal være forholdsvist simpelt at konstruere den hemmelige nøgle samt den offentlige)
2) Det skal være let for afsenderen Alice, at krypterer klarteksten ved brug af den offentlige
nøgle.
3) Det skal være let for modtageren Bob, at dekryptere kryptoteksten ved brug af sin
hemmelige nøgle.
4) Det skal være beregningsmæssigt svært for spionen Oscar, at finde den hemmelige nøgle
udfra sit kendskab til den offentlige.
5) Det skal være beregningsmæssigt svært for spionen at retablerer klarteksten udfra et
kendskab til den offentlige samt og en kryptotekst.
12
Alle disse krav til public key systemer bunder altså i, at det skal være nemt for den indviede at
enkryptere og dekryptere, mens det derimod skal være meget vanskeligt for uvedkommende at
bryde kryptoteksten. Et kryptosystem hvor der kræves mange beregninger for at enkrypterer og for
at dekrypterer meddelelsen vil altså ikke være et godt system, idet det vil være alt for tidskrævende.
For at vende tilbage til ideen om en smæklås-system, har vi altså her et system hvor alle kan låse,
men kun én kan låse op igen.
11
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 57
12
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 58
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 8 af 23
RSA-kryptosystemet
I 1977 udvikles et kryptosystem, bygget på Diffie og Hellmans public key system, af Ronald L.
Rivest, Adi Shamir og Leonard Adleman. Deres metode blev kaldt for ”The RSA Public-Key
Cryptography System”
13
. For at skabe et bedre indblik i RSA krypteringen vil vi først se nærmere
på centrale dele af den talteori der ligger bag RSA-kryptosystemet.
Talteori
Talteorien beskæftiger sig med egenskaber ved de hele tal Z. Den første sætning vi vil se på, er den
der omhandler division med rest, idet den er væsentlig for at forstå RSA-systemet.
Sætning 1 (primtal – Entydig faktorisering).
Et primtal er et helt tal p større end 1, hvor op i kun tallet selv og 1 går op i. Eksempelvis er
2,3,5,7,11,13,… primtal. Primtal fungerer som byggesten for de hele tal, idet der at:
Ethvert helt, positivt tal større end 1 på entydig vis kan faktoriseres i primtal.
14
Et eksempel hvor vi faktoriserer 100 i primtal:
5522100
Et lille tal som 100 med kun 3 cifre er altså rimelig nemt at faktorisere, men meget svære bliver hvis
tallet eksempelvis har 174 cifre eller måske 308 cifre, selv ved hjælp af en enorm datakraft vil det
tage meget lang tid at faktorisere – jævnført afsnittet om sikkerheden i RSA, hvor vi ser
faktorisering af et tal på 129 cifre tager 8 måneder vha. 1600 computere. Faktisk er det så svært at
faktorisere tal på 174 cifre at der er en hjemmeside www.rsasecurity.com som udlover en præmie
på 10.000$ for at faktorisere tallet:
13
P. Lefton ”Number Theory and Public-Key Cryptography” (Tidsskrift: Mathematics Teacher) side 56
14
J. Stillwell ”Elements of Algebra – Geometry, Numbers, Equations” side 33
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 9 af 23
257056
Der er uendelige mange primtal, hvilket vi senere ser vil have betydning for om man kan kalde
RSA-krypteringen for eviggyldig.
Spørgsmålet er så bare om man kan tale om det største primtal. Svaret og beviset til dette vil jeg
blot henvise til i bogen ”Rings, Fields and Groups” side 23.
Sætning 2 (Division med rest).
For alle positive, hele tal m og b findes præcis et helt tal q og et helt tal r således
15
0 ; drrbqm
Udfører vi en heltalsdivision på en almindelig lommeregner, så vil vi opdage at resultats kommer i
decimaler – med minder tallet divisionen sker med går op. Kvotienten q finder man ved at afrunde
tallet ned til nærmeste helt tal. Resten r finder man ved at trække kvotienten fra resultatet, hvorefter
man ganger med divisoren. Hvis dette ikke er helt bliver man nødt til at afrunde op eller ned.
Et eksempel er division af m = 454 med n = 15.
30at fås Heraf,30
15
454
q
Resten r finder man nu således:
4at fås Heraf667,7,667,30 r
Altså, en division af 454 med 15 giver en rest på 4, hvilket vil sige at
.
For at forenkle regnestykket indfører vi betegnelsen for den principale rest:
16
15
J. Stillwell ”Elements of Algebra – Geometry, Numbers, Equations” side 23
16
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 71-72
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 10 af 23
Definition 2.1
For vilkårlige hele tal m og n med n < 0 defineres m (mod n)(Læses m modulo n eller m reduceret
modulo n) ved
m (mod n) = den principale rest af m ved division med n
Idet jeg vil introducere Eulers φ-funktion, finder jeg det nødvendigt først at gennemgå centrale
sætninger bag.
Sætning 3
Antag at a,b og n er hele, positive tal. Lad a’ = a mod n og b’ = b mod n. Da gælder
nbanba mod mod
Bevis 3.1:
Fra sætning 2 ved vi, at der findes
Zrrqq
2121
,,,
således at:
nrr
nqrrqnqqnrr
nrnqrnqnqnqrr
nrnqrnqnba
mod
mod
mod
mod mod
21
2211
Idet
atgælder så mod og mod
21
rnbrna
:
nnbnanba mod mod mod mod
17
Et eksempel hvor vi anvender sætningen er:
2017 mod 5471 mod 7675
Vi ser altså med denne sætning at det er ligegyldigt hvornår modulo tages af tallet.
17
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab”. side 72-74
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 11 af 23
Sætning 4
ax ≡ ay (mod n) og (a,n) = 1
a≡ y (mod n)
Hvor ≡ er kongruensrelation
18
, og (a,n) er den største fælles divisor mellem a og n. man taler om at
de er er indbyrdes primiske, hvilket skrives det således
1),( na
.
Bevis 4.1:
Lad
mn
betyde at n går op i m.
Pr. definition vil
.)( dermed og )( yxanayaxn
Da a og n er indbyrdes primiske med 1 gælder, at
)( yxn
, hvilket også betyder, at
) (mod nyx
. ڤ
lader Z og N, lader Vi
n
n
betegne mængden
1,...,3,2,1,0Z n
n
Et eksempel:
x mod 6
5,4,3,2,1,0Z
6
Denne består af alle de n forskellige rester, der kan forekomme ved division med n. Idet m (mod n)
er entydigt bestemt, vil et hvert helt tal m være kongruent (mod n) med præcist et element i Z
n
. Vi
lader endvidere
1),(0ZZ
*
naaa
nn
Z
n
*
består altså af alle de tal i Z
n
som er indbyrdes primiske med n.
Et eksempel:
5,1Z
*
6
Antallet af elementer i Z
n
*
betegnes φ(n). I vores eksempel betyder det så, at φ(6) = 2. Andre
eksempler er φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(2520) = 576 og φ(p) = p –1 for hver primtal
p.
19
Funktionen φ kaldes Eulers φ-funktion.
18
J. Carstensen ”Talteori” side 7-10
19
R.B.J.T Allenby ”Rings, Fields og Groups – An Introduction to Abstract Algebra” side 70
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 12 af 23
Sætning 5 (Eulers sætning)
Hvis (a,n) = 1 gælder, at a
φ(n)
≡ 1 (mod n)
Bevis 5.1
Lad
)(321
*
,....,,,
nni
rrrrZr
. Idet (a,n) = 1 så er
1, nar
i
Note20
. Dvs. at
*
)(mod
ni
Znar
.
Vi ønsker nu at vise, at
*
)(1
)(mod),...,(mod
nn
Znarnar
. Det kan man se ved at antage at
ji
rr
og
)(mod)(mod narnar
ji
. Af vores sætning 4 så vil
)(mod)(mod nrnr
ji
, hvilket er det
samme som
ji
rr
, idet
nrr
ji
,
. Men idet vi antog at
ji
rr
må vi derfor konkludere at
)(mod)(mod narnar
ji
. Og hermed
*
)(1
)(mod),...,(mod
nn
Znarnar
)(mod))(mod(...))(mod())(mod()(mod...
)(21)(21
nnarnarnarnrrr
nn
og af regnereglen fra
sætning 3 får vi
)(mod...)(mod...
)(21)(21
narararnrrr
nin
)(mod...
)(21
)(
nrrra
n
n
Da (r
i
,n) = 1 følger det af sætning 4, at vi kan forkorte r
i
’erne væk. Tilbage er nu
)(mod1)(mod
)(
nna
n
, hvilket er det samme som
)(mod1
)(
na
n
note21
.
ڤ
Vi har nu set på den væsentligste talteori bag RSA, og vi skal nu se på hvordan og ikke mindst
hvorfor det så virker.
20
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” sætning 4.19 side 82
21
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” sætning 4.30 side 88
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 13 af 23
Algoritmen bag RSA
Vi vil nu se på algoritmen bag RSA - hvad Bob skal gøre for at Alice kan sende sikre meddelelser
til ham.
1. Bob vælger to (store) primtal p og q, hver på ca.100 cifre.
2. Bob beregner n = pq, og φ(n) = (p – 1)(q – 1).
3. Bob finder et helt tal e hvor
)(0 ne
så e og φ(n) er uden fælles divisor.
4. Bob beregner tallet d, således ed ≡ 1 (mod φ(n)) dvs. d ≡ e
-1
(mod φ(n)).
5. Bob offentliggør n og e, mens han selv beholder den hemmelig nøgle d.
Offentlige nøgle: (n, e)
Hemmelig nøgle: d
Tallene p,q og φ(n) smides væk efter nøgleberegningen da de nu har tjent deres formål.
22
Enkrypteringen med RSA sker således:
Den klartekst, der skal krypteres, kodes først som tal og inddeles i blokke, således at hver blok
repræsenterer et tal m hvor
nm 0
. For at kryptere tallet m opløftets dette til e’te potens og
reduceres modulo n.
cnmm
e
)(mod
Dekryptering med RSA sker således:
Tallet c dekrypteres ved at opløfte c til d’te potens og reducere modulo n
mnmc
e
) mod(
Altså har vi at:
22
Douglas R. Stinson. ”Cryptography – Theory and Practice” side 126
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 14 af 23
))( mod(1 ; ) mod(
) mod(
) mod()() mod(
*)) (mod(
nd enm
nm
nmnc
nde
ed
ded
= m
Note23
* kræver naturligvis et bevis, hvilket behandles senere. Først skal vi se på hvordan RSA-
krypteringen virker. Til at illustrere dette, laver vi et eksempel, hvor vi igen har afsenderen Alice,
der ønsker at udveksle en fortrolig meddelelse med Bob (se figur 2).
Et RSA eksempel
I dette eksempel regnes der med meget små primtal, for at udregningerne skal kunne foretages med
en lommeregner. Men som tidligere beskrevet vil et realistisk eksempel kræve primtal på ca. 100
cifre, pga. at det skal være vanskeligt at faktorisere primtallene, jævnført Diffie og Hellmans krav til
et public key system. Men alt dette med sikkerheden bag RSA-systemet vil jeg behandler senere i
opgaven.
Jeg konstruerer et RSA-system:
1. Vælger primtallene p = 59 og q = 97
2. Beregner n= pq = 5723, og φ(n) = (p-1)(q-1) = 5568
3. Finder e, hvor
)(0 ne
og e og φ(n) er uden fælles divisor. Fx e = 7
4. Beregner tallet d, vha. Euklids udvidede algoritme
24
således at d=1591
5. Offentliggør nu (n,e) = (5723,7)
Jeg vil nu prøve at kryptere ordet ”hemmelighed”
klarteksten: ”HEMMELIGHED” kodes først ved nummerering af alfabetet hvor ” ” = 00, ”A” = 01,
”B” = 02, (se endvidere bilag 2). Derefter opdeles i blokke á 4:
23
K. Nissen ”Kryptologi – læren om hemmelig skrift II” (Tidsskriftet Veritas) side 8
24
Douglas R. Stinson. ”Cryptography – Theory and Practice” side 116-119
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 15 af 23
H E MM E L I G H E D
Bemærk: At blokstørrelsen vælges sådan at tallene er mindre end n
Enkryptering:
Vi ser først på blokken ”HE”. Denne krypteres ved at udregne:
)5723(mod
7
For at beregne dette er vi nødt til at fortage nogle omskrivninger:
2
22
3
267
mmmmmmmm
Beregningen af
)5723(mod0805
7
kan nu foretages således:
)5723(mod0805)(
)5723(mod1326)(
)5723(mod
)5723(mod
2
22
2
22
2
2
2
22
mmm
mm
m
m
Dvs. kryptoteksten for ”HE” er 1686
Hvis dette gentages på hele ordet fås kryptoteksten:
Dekryptering:
For at dekryptere ordet igen skal man igen først opdele i blokke og derefter anvende:
mnc
d
) mod(
Dvs. i vores eksempel med kryptoteksten c = 1686 vil dekrypteringen foregå ved:
805)5723(mod1686
1591
Da eksponenten er for stor, er direkte indtastning på lommeregneren ikke mulig. Det er derfor
nødvendigt at benytte samme metode som ved enkryption. Ved omskrivning fås at:
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 16 af 23
591
)))))))))((((((((())))))))(((((((())))(((()))((()( cccccccc
Udregninger herefter kræver meget plads, så for at spare på dette benytter jeg mig af notation
eks:
3
2222
))( cc
. Videre udregning kan nu fortages således:
)5723(mod1419520
)5723(mod520546
)5723(mod5463333
)5723(mod
)5723(mod
)5723(mod1878715
)5723(mod7155329
)5723(mod
)5723(mod
)5723(mod
22
22
22
22
22
22
22
22
22
22
10
9
8
7
6
5
4
3
2
c
c
c
c
c
c
c
c
c
c
Hvorefter omskrivningen fra før benyttes. Heri sættes fundne værdier.
)5723(mod805
)5723(mod3828
)5723(mod3133
)5723(mod23
)5723(mod3754
)5723(mod4966
109542
9542
542
42
2
222222
22222
2222
222
22
2
ccccccc
cccccc
ccccc
cccc
ccc
cc
Herved er dekryptering næsten færdig, idet man nu blot skal benytte bogstavstabellen (se bilag 2)
for at få det tilbage til klartekst igen. Vi har nu dekrypteret bogstaverne ”HE” og samme proces
benyttes til resten af ordet. Som vi ser i dette eksempel, er udregningerne mange, og man burde
derfor lave en form for computerprogram til at lave udregningerne.
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 17 af 23
Beviset:
Vi skal nu se på hvorfor RSA-systemet fungerer. Vi ser på et m hvor 0 < m < n så virker RSA-
algoritmen ved:
)(mod)(mod)(mod
..
nnmnmm
d
e
Dekrypt
e
Inkrypt
Dvs. at hvis der gælder:
mnnm
d
e
)(mod)(mod
så vil enkryptionen og dekryptionen ophæve hinanden.
Lad e og d være fundet som tidligere beskrevet. Vi antager, at (m,n) = 1 og da det som en
konsekvens af Eulers sætning
25
, gælder at:
)(mod)(mod
))((mod
nmnm
nss
altså for vi:
)(mod)(mod)(mod)(mod
))((mod
nmnmnnm
neded
d
e
;
Idet
))((mod1 ned
,er
mnm
ed
)(mod
opfyldt, hvis (m,n) =1.
Beviset er dog ikke helt klaret endnu, idet vi stadig mangler en lille detalje - nemlig tilfældet hvor
1),( nm
. Dette tilfælde indtræffer dog yderst sjældent, idet man skal være så uheldig at enten p
eller q dividerer m. Men er primtallene blot tilstrækkelig store(ca.100 cifre), vil chancen for at opnå
dette tilfælde, svare til sandsynligheden for at tippe 13 rigtige 12 uger i træk på tipskuponen.
26
Det
vil derfor være for specifikt at komme ind på beviset herfor
27
.
Vi har nu set et eksempel, der blev foretaget med forholdsvist små primtal. Det betyder alt andet
lige, at det ikke vil tage lang tid, før vores spion Oscar har fundet de to primtal ved en utømmende
25
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 91 sætning 4.37
26
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 105-106
27
Beviset vises i P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” på Side 164
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 18 af 23
søgning og derved også fundet nøglen. Vi kan altså udfra det konstatere, at sikkerheden i RSA
baseres på store primtal.
28
Sikkerheden bag RSA – kan det brydes?
Svaret til dette kom den 26. april 1994, her kunne CNN i 21.30-nyhederne nemlig meddele, at RSA
var blevet brudt ved hjælp af 1600 computers arbejde i 8 måneder. Kunne det virkelig passe? Nej
ikke helt for det system der var brudt hedder RSA-129 og var en opgave der blev stillet alverdens
kodebrydere. Deres opgave var at faktorisere n, altså beregne de to primtal p og q, som n er et
produkt af, hvorefter de skulle beregne den hemmelige nøgle d. De eneste oplysninger de fik var
kryptoteksten c der lød således:
35693
375c
Derudover fik de også oplyst at krypteringen var sket med en offentlig nøgle der lød således:
5971
816257
9007
n
e
Et stort verdensomspændende computernetværk blev nu etableret af de 4 forskere Atkins, Graff,
Lenstra og Leylandfra MIT (Massachusetts Institute of Technology), for at løse opgaven. De 4
forskere fik hjælp fra 600 personer, der stillede deres computer til rådighed, således af man nåede
op en datakraft bestående af 1600 computere. Denne enorme datakraft fra de 1600 computere,
skulle stå for de indledende undersøgelser af tallene – dette tog 8 måneder. Hvorefter de mange
delresultater blev samlet på én kæmpe computer, der nu skulle regne det sidste. Efter 45 timer
lykkedes det, computeren gav de to primtal:
9
q
p
28
B. Johnson ”Kryptografi, primtal og Riemanns hypotese” (Tidsskrift: Normat) side 4
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 19 af 23
Ved at benytte føromtalte dekrypteringsalgoritme, og ved at oversætte 01 = A, 02 = B, ovs., og 00
som mellemrum, lykkedes det at dekryptere den hemmelige meddelelse c. Resultatet var denne
sætning: ”THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE”
29
. Dette var altså et eksempel
på, at et tal med 129 cifre er blevet faktoriseret i to primtal, der medførte at kryptoteksten kunne
tydes. Betyder det så at RSA er et usikkert system? Nej absolut ikke for i den opgave der her blev
stillet var φ(n) = pq blot på 129 cifre (derfra navnet RSA-129). Førhen når man anvendte RSA
benyttede man nøgler med ca. 154 cifre (512 bits nøgler) og i moderne systemer anvendes nøgler
med ca.308 cifre( i 1994). Idet antallet af udregninger vokser eksponentielt som en funktion af
antallet af cifre i primtallet, vil en stigning i primtallets cifre altså betyde, at der skal fortages mange
flere udregninger.
30
Digital signatur
Jeg vil nu slutte min opgave ved at vise anden smart ting ved Public key krypteringen, som udover
hemmeligholdelse af en meddelelse, også har muligheden for digital signatur. Digital signatur er en
underskrift i elektronisk format. Den kan bruges af Alice til signere fx en e-mail, således at Bob kan
være sikker på, at den er fra Alice og ikke en anden som bare udgiver sig for at være Alice.
Algoritmen for en digital signatur ser således ud:
1. Alice underskriver sin meddelelse m ved at ”kryptere” med sin private nøgle først og
derefter kryptere med Bobs offentlige nøgle.
BobAlice
ed
m )(
2. Alice sender den enkrypterede meddelelse til Bob
3. Bob dekrypterer først med sin egen nøgle og derefter med Alices offentlige nøgle
mmm
AliceAliceAliceBobBobAlice
ededed
)()))(((
; herved kan Bob altså være sikker på at meddelelsen er
fra Alice idet kun Alice kender til d
Alice
Da vi stadig går ud fra at beskeden sendes via en ubeskyttet kanal, må vi også antage at en enhver
kan tappe en sådan krypterede meddelelse, derfor skal følgende krav være opfyldt:
29
Douglas R. Stinson. ”Cryptography – Theory and Practice” side 155-156
30
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab”. Side 118-120
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 20 af 23
Det er en nødvendighed at signaturen gøres unik, dette kan eksempelvis gøres ved at tilføje
et tidsstempel.
Da risikoen er for at flere personer har modtaget signaturen er det vigtigt at det klart fremgår
af klarteksten hvem den er henvendt til.
Hvis disse krav ikke er opfyldt, kan det ende helt galt, tænk blot hvis Alice sender en underskrevet
check til Bob uden at fremgår hvem den er til.
Det er værd at bemærke, at der er en vis forskel fra den kryptering, der har til formål at lave en
digital signatur og den kryptering man ellers anvender på meddelelser. For godt sker der en
kryptering af meddelelsen men denne har ikke til formål at skjule noget, da alle i princippet skal
have mulighed for at checke signaturen. Det specielle ved digital signatur er altså i forhold til
almindelige underskrifter at der ikke følger et eller andet med meddelelsen, som vi kender fra
traditionelle underskrifter med kuglepen. Ved digital signatur ligger selve signaturen i krypteringen
af klarteksten
31
.
Afslutning
Idet jeg nu finder min problemformulering besvaret, vil jeg afslutte min opgave her. Jeg håber, at
opgaven har været lige så spænende at læse, som den var at skrive.
[navn fjernet] 3.z
31
P.Landrock & K.Nissen ”Kryptologi – fra viden til videnskab” side 60-62
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 21 af 23
Litteraturliste:
Bøger, alment om kryptologi
”Kryptologi – fra viden til videnskab”. Landrock, Peter – Nissen, Knud. Forlaget ABACUS,
1997 1. udgave, 1. oplag.
”Cryptography – Theory and Practice”. Stinson, Douglas R.. Forlaget CRC Press, 1995
1.udgave 2. oplag.
”Internet – lær med billeder” ?????. Forlaget Preston Gralla, 1997.
Artikler mv. om kryptologi
”Number Theory and Public-Key Cryptography”. Lefton, Phyllis. Tidsskrift: Mathematics
Teacher, 1991 udgave nr. 84
”Kryptografi, primtal og Riemanns hypotese”. Johnson, Ben. Tidsskrift: Normat, 1986
udgave nr. 34.
”Kryptologi – læren om hemmelig skrift I”. Nissen, Knud. Tidsskriftet Veritas 1994 udgave
nr. 1.
”Kryptologi – læren om hemmelig skrift II”. Nissen, Knud. Tidsskriftet Veritas 1994 udgave
nr. 2.
Talteori mv. bag kryptologi
”Rings, Fields og Groups – An Introduction to Abstract Algebra”. Allenby, R.B.J.T..
Forlaget Edward Arnold,1991 2. udgave 1.oplag.
”Talteori”. Carstensen, Jens. Forlaget. Systime, 1993 1.udgave 1.oplag.
”Elements of Algebra – Geometry, Numbers, Equations”. Stillwell, John. Forlaget Springer,
1994 1. udgave 2. oplag
Internet adresser:
www.cse.iitd.ernet.in/~suban /cs120rsa/node9.html
www.mat.dk/uvmidler/skr-opg/opgaver/tala2134.html
www.net-faq.dk/faq.pl?get=pubkey
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 22 af 23
Bilag 1
Bilag 2
B o g s t a v e r
T i l s v a r e n d e n u m m e r
" m e l l e m r u m "
00
A
01
B
02
C
03
D
04
E
05
F
06
G
07
H
08
I
09
J
10
K
11
L
12
M
13
N
14
O
15
P
16
Q
17
R
18
S
19
T
20
U
21
V
22
X
23
Y
24
Z
25
Æ
26
Ø
27
Å
28
3.-Årsopgaven Matematik – Kryptologi
RSA-kryptosystemet
[navn fjernet] 3.z
Nørresundby Gymnasium og HF Side 23 af 23
Bilag 3
Program:
:Disp ” A*B MOD N”
:Input ”N=”,N
:While 1
:Input ”A=”,A
:Input ”B=”,B
:A*B/N-int(A*B/N)
D
:round(D*N,0)
C
:Disp “Giver”,C
:END
Dette er et simpelt lommeregnerprogram, som jeg har konstrueret for at gøre udregningerne med
modulo lettere.