Studiekompasset.dkKlasse: HF 2. år · Fag: SSO, Matematik A
Kryptologi
Side 1
Kryptologi
Kryptologi
Side 2
Indholdsfortegnelse
Indledning 3
Konventionelle kryptosystemer 3
Public Key 3
Introduktion til RSA 5
Talteori 5
Divisorer 5
Modulo 6
Største fælles divisor 7
Euklids algoritme 7
Kongruens 9
Primtal 10
Aritmetikkens fundamentalsætning 10
Eulers φ-funktion 11
Eulers sætning 14
Inverse elementer 16
RSA – kryptosystemet 18
Konstruering af nøgler 18
Enkryptering og dekryptering 18
Eksempel 20
Algoritmer 22
Konklusion 23
Litteraturliste 24
Bilag 1
Kryptologi
Side 3
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
1
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
56
nøglemuligheder. En
udtømmende søgning vil derfor kunne klares på rimelig tid.
Public Key
2
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 (one-
1
[KG] s. 98-99 og [KL] s. 50-54
2
[KG] s. 101-104 og [KL] s. 56-62
Kryptologi
Side 4
way-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. En offentlig tilgængelig
nøgle, P
K
, og en personlig og hemmelig nøgle, S
K
. Det vil se således ud(se også bilag
1, fig. 2):
Afsender: E(M, P
K
) = C
Modtager: D(C, S
K
) = M
Fordelen ved at have 2 forskellige nøgler er i forhold til udvekslingen af nøgler. Det
kun de offentlige nøgler, P
K
, der skal udveksles, og da P
K
ikke kan bruges til at
dekryptere kryptoteksten, er der ingen sikkerhedsrisiko. Hvorimod ved et
konventionelt kryptosystem kan en opponent, der kommer i besiddelse af nøglen, K,
dekryptere kryptoteksten på lige fod med modtageren. (Se bilag 1) Derudover skal en
gruppe på 30 personer kun have 30 offentlige nøgler og 30 hemmelige nøgler for at
alle kan udveksler krypterede beskeder med alle.
Endnu en fordel ved Public Key systemet er muligheden for at lave en digital
signatur. Ved digital signatur menes der en underskrift af et digitalt dokument som har
samme egenskaber som en traditionel underskrift, såsom at den ikke kan forfalskes,
dokumentet ikke kan ændres efter det er underskrevet, og at underskriften er
bindende.
Det digitale dokument underskrives ved at afsenderen enkrypterer det med sin egen
nøgle, S
A
, før der enkrypteres med modtagerens nøgle, P
M
. Når modtageren så får det
signerede og krypterede dokument, dekrypteres det først med modtagerens egen
nøgle, S
M
, og derefter med afsenderens offentlige nøgle, P
A
.
Afsenderens offentlige nøgle, P
A
, kan kun dekryptere kryptoteksten, D, så klarteksten,
M, fremkommer, hvis den er blevet enkrypteret med afsenderens hemmelige nøgle,
S
A
. Det betyder, at underskriften ikke kan forfalskes af en opponent, med mindre at
denne kender afsenderens hemmelige nøgle, S
A
. Det betyder også at signaturen er
bindende, da den kun kan frembringes af indehaveren af S
A
. At et underskrevet
Kryptologi
Side 5
dokument ikke kan ændres giver helt sig selv, da et underskrevet dokument ikke er et
dokument i den forstand, men en krypteret fil. En digital signatur ville se sådan ud:
Afsender: S
A
(M) = D
P
M
(D) = C
D
P
M
(S
A
(M)) = C
D
Modtager: S
M
(C
D
) = D
P
A
(D) = M
P
A
(S
M
(C
D
)) = M
Introduktion til RSA
3
I 1977 opfandt Ronald Rivest, Adi Shamir og Leonard Adelman fra Massachusetts
Institute of Technology (MIT) et kryptosystem som byggede på Diffie og Hellmans
ideer om et Public Key system. De kaldte systemet RSA (efter deres forbogstaver). I
dag er systemet anset for at være det mest sikre Public Key system. Systemet bygger
på primtal, og det beregningsmæssige svære problem at primtalsfaktorisere. For to
givne primtal p og q, p q er det nemt nok at finde n så n = pq, men noget sværere er
det at finde p og q hvis man kender n. Det gælder især hvis p og q (og derved også n)
er af en hvis størrelse. For at en RSA kode er beregningsmæssig svær at bryde, skal n
være på over 100 cifre, og jo større n er, jo sværere er det at bryde koden.
Før jeg kan gå i gang med at forklare, hvordan RSA virker, har jeg brug for at vise
noget af teorien, der ligger bag.
Talteori
I de følgende afsnit vil jeg vise den talteori som ligger til grund for RSA-
kryptosystemet. Der er ikke plads til at bevise det hele, så specielt i første del, hvor
sætninger og beviser er enkle, vil jeg udelade en del.
Divisorer
Definition 1:
4
Et tal, a, går op i et tal, b, hvis følgende er opfyldt:
,,, kba
0a
kab
man skriver også
ba
. a kaldes divisoren og k kaldes kvotienten. Man siger også b er
et multiplum af a.
3
[EC] s. 245-247 og [KG] s. 99-102
4
[TT] s. 7 og [KL] s. 70
Kryptologi
Side 6
Til definition 1 følger nogle regneregler, som jeg ikke vil bevise:
Sætning 2:
5
tscba ,,,,
1.
,babcac
2.
,)( tbsacbcac
0c
Hvis a ikke går op i b, kan divisionen beskrives således:
Definition 3:
6
Ved division mellem to tal, a og b, er følgende opfyldt:
rkba ,,,
,rkab
ar 0
k og r er entydigt bestemte. r kaldes for den principale rest.
Modulo
Den principale rest kan også beskrive på følgende måde:
Definition 4:
7
Hvis r er den principale rest ved division mellem a og b, er følgende opfyldt:
rb,
a
,)(mod rab
Man siger at b modulo a er lig den principale rest af b ved division med a.
Til definition 4 hører 5 hjælpesætninger. Det er almindelige logiske regneregler, som
gælder for modulo på følgende måde. Beviset har jeg udeladt.
Sætning 5:
8
kcb ,,
da,
1.
babab )(mod0
2.
)(mod))(mod( abaakb
5
[KL] s. 70
6
[TT] s. 8 og [KL] s. 71
7
[KL] s. 72
8
[KL] s. 72-73
Kryptologi
Side 7
3.
)))(mod(mod)(mod())(mod( aacabacb
4.
)))(mod(mod)(mod())(mod( aacabacb
5.
)(mod))(mod()(mod aabab
dd
Største fælles divisor
Definition 6:
9
Den største fælles divisor i a og b er det største tal, d, hvorom det gælder at da
db. Den største fælles divisorer i a og b betegnes sfd(a,b).
Eksempel: Den største fælles divisorer mellem 12 og 15 er 3, da ingen tal >3 går op
i både 12 og 15. Vi skriver sfd(12,15) = 3
Prøver vi at finde den største fælles divisorer mellem 14 og 15, finder vi
at den eneste divisorer til både 14 og 15 er 1, dvs. sfd(14,15) = 1
Definition 7:
10
Hvis sfd(a,b) = 1 har a og b ingen fælles divisorer, bortset fra 1, og kaldes derfor for
indbyrdes primiske.
For at kunne bestemme sfd(a,b) for a og b værende ”store” tal indfører jeg:
Euklids algoritme
Sætning 8:
11
For:
,rkab
ar 0
,
rkba ,,,
gælder at:
sfd(a,b) = sfd(a,r)
Bevis:
12
Da
rkab
er
kabr
, dvs. at vi skal vise at sfd(a,b) = sfd(a,b - ka).
Lad c = sfd(a,b) og d = sfd(a,b - ka).
9
[TT] s. 16
10
[TT] s. 17
11
[KL] s. 75
12
[KL] s. 75
Kryptologi
Side 8
Da ca og cb får vi at c(b - ka) ifølge sætning 2.2. Dermed går c op i både a og b -
ka, hvilket medfører at c ≤ a og c ≤ b - ka, som igen medfører at c ≤ d.
Da da og d(b - ka) får vi at d((b - ka) + ka) ifølge sætning 2.2, som igen er lig
db. Dermed går d op i både a og b, hvilket medfører d ≤ a og d ≤ b, som igen
medfører at d ≤ c.
Nu ved vi at c ≤ d og d ≤ c, deraf følger at c = d.
□
I praksis virker algoritmen på følgende måde:
,
,
,
21
1
rkrr
rkra
rkab
12
1
0
0
0
rr
rr
br
(a)
Processen fortsætter på samme måde, indtil
0
s
r
, da vil
),( basfd
=
1s
r
.
Udfra Euklids algoritme kan man udlede følgende vigtige sætning:
Sætning 9:
13
For et givet af a og b findes der et s og t således at:
,,,, tsba
tbsabasfd ),(
Bevis:
Da beviset er temmelig simpelt, men fylder meget vil jeg nøjes med at forklare det i
hovedtræk. Ideen er at anvende (a) til successivt at udtrykke resten, r, ved a og b. Da
1
),(
s
rbasfd
kan man på denne måde udtrykke sfd(a,b) som en lineærkombination
af a og b.
□
Af sætning 9 kommer en række vigtige regler for største fælles divisor:
Sætning 10:
14
tsba ,,,
1. ca cb csfd(a,b),
c
2.
),,(),( basfdccbcasfd
c
13
[TT] s. 20 og [KL] s.77
14
[KL] s. 81-82
Kryptologi
Side 9
3.
1),(1 basfdtbsa
4.
1),(1),(1),( cabsfdcbsfdcasfd
, cZ
5.
acbcsfdabc 1),(
, cZ
Bevis:
15
1. Ifølge sætning 2.2 er
,)( tbsacbcac
og ifølge sætning 9 er
.),( tbsabasfd
2. Bevis udelades
3. Sæt d = (a,b). Så da og db, hvilket medfører at d(sa + tb), ifølge sætning 2.2.
Da sa + tb = 1 må d1. Deraf følger at d = 1.
4. Ifølge sætning 9 er:
vutscba ,,,,,,
1),( tcsacasfd
1),( vcuacbsfd
Ved at multiplicere de 2 ligninger får man:
ctvctubsvaabsutcvctcubsavcsaubvcubtcsa )()())((1
Derved fremkommer en lineær kombination af ab og c, og derved er (ab,c) = 1
ifølge sætning 10.3.
5. Bevis udelades
□
Kongruens
Definition 11:
16
c og b kaldes kongruente modulo a:
,
cba ,,
hvis a(c - b).
15
[KL] s. 81-82
16
[TT] s. 8
Kryptologi
Side 10
Af definition 11 kommer to sætninger, hvoraf jeg beviser den ene:
Sætning 12:
17
kcba ,,,
1.
)(mod)(mod)(mod abacabc
2.
)(mod1),()(mod abckasfdakbkc
Bevis:
18
1. Bevis udelades
2. Ifølge definition 11 er
.)()()(mod bckakbkcaakbkc
At (a,k) = 1
medfører at
,)( bca
hvilket er ensbetydende med at
).(mod abc
□
Primtal
Definition 13:
19
Et tal, p, pN, kaldes er primtal, hvis 1 og p er de eneste divisorer til p.
Nu vil jeg vise aritmetikkens fundamentalsætning, men først en lille regel, som jeg
skal bruge i beviset:
Sætning 14:
20
bpapabp
for p værende et primtal.
Bevis:
21
Hvis pa ikke er sand, er sfd(a,p) =1. Hvilket medfører at pb, ifølge 10.5.
□
Aritmetikkens fundamentalsætning
Sætning 15:
22
Ethvert tal, a, aN, kan skrives som produkt af primtal. Beskrivelsen er entydig, med
undtagelse af faktorernes orden.
17
[TT] s. 9 og [KL] s. 88
18
[KL] s. 88
19
[KL] s. 83
20
[KL] s. 83 og [TT] s. 12
21
[KL] s. 83
22
[KL] s. 84
Kryptologi
Side 11
Bevis:
23
For a, aN, værende et primtal er der ikke noget at vise, men hvis a ikke er et
primtal, dvs. a er et sammensat tal, kan a faktoriseres, så:
21
aaa
,
aaaa
21
11
Hvis a
1
er et primtal fortsættes med næste sammensatte tal, a
2
., men hvis a
1
er et
sammensat tal faktoriseres det, så:
2.11.11
aaa
,
aaaaaa
12.111.1
11
Faktoriseringen fortsætter indtil alle tal er opløst til primtal. At det vil ske følger af at:
aaaaa
r
11.11.1.1
...1
Faktorerne bliver mindre og mindre, og vil til sidst ende som primtal (da de mindste
naturlige tal er primtal).
For at vise entydigheden antager vi, at sætning 15 ikke er entydig, så a har to
primfaktoropløsninger. p og q er primtal således at:
sr
qqqqppppa
321321
,
sr,
(b)
sr
qqqqpppppp
321132
1
1
Ifølge sætning 14 findes der et t, tN, 1 ≤ t < s, så
.
1 t
qp
Da
t
q
er et primtal og
,1
1
p
er
t
qp
1
. Lad os antage at t = 1, så
11
qp
. Hvis vi forkorter (a) med
1
p
får
vi
sr
qqqppp
3232
. Ved at fortage samme manøvre med
2
p
kan man vise at
tallene
r
pppp ,,,,,
321
hver især er lig et af tallene
s
qqqq ,,,,,
321
. Dvs. at
},,,,,{},,,,,{
321321 sr
qqqqpppp
men ikke nødvendigvis i samme rækkefølge, men
da faktorernes orden er ligegyldig er sætningen bevist.
□
Aritmetikken fundamentalsætning gør det muligt at definere en meget vigtig funktion
i RSA systemet.
Eulers φ-funktion
Definition 16:
24
Eulers φ(n), n
N beskriver det antal naturlige tal mindre end n, som
er (indbyrdes) primiske med n.
23
[KL] s. 84
24
[TT] s. 26
Kryptologi
Side 12
For et primtal, p, kan φ(p) skrives som:
1)( pp
da definitionen på primtal er, at det er primisk med alle tal < p.
Sætning 17:
25
For et sammensat tal, n, med følgende primtalsopløsning:
r
k
r
k
kk
ppppn
3
21
321
Nrk ,
kan φ(n) skrives som:
r
pppp
nn
1
1
1
1
1
1
1
1)(
321
Bevis:
26
Jeg vælger at dele beviset op i to dele, da jeg skal bruge en sætning til sidste del, som
jeg endnu ikke har vist.
Jeg starter med at vise φ(n) for n = p
k
. De eneste tal som ikke er primiske med p
k
er
multipla af p. Dem er der
1
k
k
p
p
p
af, så:
p
ppppnn
kkkk
1
1)(
11
(c)
Det var første del af beviset. For at kunne bevise anden del, skal jeg bevise, at φ(n) er
multiplikativ, og for at kunne det, skal jeg lige have en hjælpesætning på plads først.
Sætning 18:
27
Lad a og b være indbyrdes primiske, og r en tilfældig rest. a,b,rN. Ved at dividere
numrene:
rbarbrbrbr )1(,...,3,2,,
(d)
med a, får man følgende rest:
)1(,...,3,2,1,0 a
(e)
25
[KL] s. 89 og [TT] s. 27
26
[TT] s. 27-28 og [ET] s. 246
27
[ET] s. 246
Kryptologi
Side 13
Bevis:
28
Vi antager at overstående ikke er sandt, så der findes to hele tal i og j, 0 ≤ j < i < m, så
ib + r og jb + r har samme rest ved division med a, dvs. kongruente modulo a, så:
jia
basfd
bjiarjbriba
arjbrib
1),(
)()((
)(mod
Den sidste implikation følger af sætning 10.5. Da a ikke kan gå op i i - j, fordi 0 ≤ i - j
< a, er det bevist at ved at dividere (d) med a, får man forskellige rester, og da antallet
af tal i (d) er lig antallet af tal i (e) er sætningen bevist.
□
Sætning 19:
29
Eulers φ-funktion er multiplikativ:
)()()( baab
for
1),( basfd
Bevis:
30
Alle tallene fra 1 - ab kan skrives op på følgende måde:
1
2
3
…
r
…
b
b + 1
b + 2
b + 3
…
b+ r
…
b + b
2b + 1
2b + 2
2b + 3
…
2b + r
…
2b + b
3b + 1
3b + 2
3b + 3
…
3b + r
…
3b + b
…
…
…
…
…
…
…
(a–1)b+1
(a–1)b+2
(a–1)b+3
…
(a–1)b+r
…
ab
φ(ab) er lig antallet af overstående tal, som er primiske med ab, som også er de tal,
der er primiske med både a og b, ifølge sætning 10.4.
28
[ET] s. 246
29
[TT] s. 28 og [ET] s. 246
30
[ET]s. 246-247
Kryptologi
Side 14
Lad rN, r ≤ b. Hvis sfd(r,b) = 1, er alle tallene i den pågældende kolonne primiske
med b. Hvis sfd(r,b) > 1 er ingen af tallene i den pågældende kolonne primiske med b.
Antallet af tal, r, mindre end b som er primiske med b, er φ(b). Dvs. antallet af
kolonner som er primiske med b er φ(b). Hvis vi betragter kolonnen r, b + r, 2b + r,
3b + r, osv. opdager man at den er identisk med (d) fra sætning 18. Ved at dividere
alle tal i kolonnen med a, fremkommer resterne (e) ifølge sætning 18. Antallet af tal i
(e), der er primiske med a, er φ(a).
Derved er der φ(b) kolonner, der er primiske med b, og i hver af de φ(b) kolonner, er
der φ(a) tal, der er primiske med a. Derfor er antallet af tal, der er primiske med både
b og a lig φ(a)φ(b). Dermed er det bevist, at φ(n) er multiplikativ.
□
Nu til anden del af beviset for Eulers φ(n):
31
r
k
r
k
kk
ppppn
3
21
321
)()()()()(
3
21
321
r
k
r
k
kk
ppppn
(f)
Jeg sætter (c), fra første del af beviset, ind i (f):
r
k
r
k
kk
p
p
p
p
p
p
p
pn
r
1
1
1
1
1
1
1
1)(
3
3
2
2
1
1
3
21
r
k
r
k
kk
pppp
pppp
r
1
1
1
1
1
1
1
1
321
321
3
21
r
pppp
n
1
1
1
1
1
1
1
1
321
□
Da Eulers funktion dermed er på plads, vil jeg gå videre til Eulers sætning:
Eulers sætning
Sætning 20:
32
)(mod11),(
)(
ababsfd
a
31
[ET] s. 247
32
[KL] s. 90
Kryptologi
Side 15
Bevis:
33
Jeg definerer
}1),({* rasfdabr
a
så antallet af elementer i
*
a
er lig
φ(a). Lad
},,,,,{*
)(321 aai
rrrrr
. Derved er
1),(
i
rasfd
og på forhånd er
1),( absfd
, så ifølge 10.4 er
1),(
i
brasfd
. Ifølge sætning 18 er tallene
)(mod,,),(mod),(mod),(mod
)(321
abrabrabrabr
a
de samme som tallene
)(321
,,,,,
a
rrrr
, men ikke nødvendigvis i samme rækkefølge, så:
)(mod))(mod())(mod())(mod()(mod
)(21)(321
aabrabrabrarrrr
aa
Ifølge sætning 5.4 kan det reduceres til:
)(mod)(mod)(mod
)(321
)(
)(321)(321
arrrrbabrbrbrbrarrrr
a
a
aa
Da
1),(
i
rasfd
er
)(mod1)(mod
)(
aab
a
, ifølge sætning 12.2, hvilket ifølge 12.1
er
)(mod1
)(
ab
a
.
□
Sætning 21:
34
b
,
sa,
,
1),( basfd
)(mod)(mod
))((mod
abab
ass
Bevis:
35
Ifølge definition 3 kan s udtrykkes således at:
,)( raks
,, rk
).(0 nr
Vi vil vise at
)(mod)(mod abab
rs
, da
rarak ))()(mod)((
,
ifølge sætning 5.1 og 5.2.
Af sætning 5.4, 5.5 og 20 følger at:
)(mod)(mod())(mod)(mod((
)(mod)(mod)(mod
)(
)()(
aabaab
abbabab
rka
rakraks
)(mod
)(mod))(mod()(mod1(
ab
aaba
r
rk
□
33
[KL] s. 90-91
34
[KL] s. 91
35
[KL] s. 91
Kryptologi
Side 16
Inverse elementer
Definition 22:
36
b har et inverst element modulo a,
,, ba
,0 ab
hvis der findes et x,
,x
,0 ax
således at:
)(mod1 abx
det inverse element til
)(mod ab
betegnes
)(mod
1
ab
Sætning 23:
37
1. Hvis
1),( basfd
eksisterer
)(mod
1
ab
.
2. Hvis
)(mod
1
ab
eksisterer, er
1),( basfd
.
3. Det inverse element er entydigt.
Bevis:
38
1. Da
1),( basfd
er
1 tasb
,
ts,
. Det kan omskrives til
atsb )(1
.
Ifølge definition 4 er:
1)(mod abs
ifølge sætning 5.4
1)))(mod(mod)(mod( aasab
Da
ab 0
og
a 10
kan vi med sætning 5.1 omskrive det til:
)(mod1))))(mod(mod(( aaasb
ifølge sætning 12.1
)(mod1))(mod( aasb
Deraf (og af definition 22) kan man se, at det inverse element til b modulo a er
)(mod as
. Dermed er eksistensen af det inverse element bevist, for
1),( basfd
.
□
2. Lad c være det entydige inverse element til b modulo a, således at
)(mod1 abc
.
Ifølge definition 11 kan det også skrives som n(bc - 1), hvilket ifølge definition 1
kan skrives som ka = bc - 1. Dette kan omskrives til 1 = bc + (-k)a. Ifølge sætning
10.3 er det ensbetydende med at
1),( basft
.
36
[KL] s.92
37
[KL] s. 93
38
[KL] s. 93-94
Kryptologi
Side 17
3. Lad
1),( basfd
. Antag at b modulo a har 2 inverse elementer, x og y,
)(mod1 abx
og
)(mod1 aby
. Heraf følger:
)(mod)(mod
)(mod)(mod1)(mod)(mod1)(mod1
ayxabybx
abyaabxabyabx
De 2 første biimplikationer følger af 12.1, den sidste implikation følger af 12.2, da
1),( basfd
.
□
Af sætning 23.1-2-3 kan vi konkludere, at det entydige inverse element til b modulo a
eksisterer hvis og kun hvis
1),( basfd
.
Det inverse element kan også bestemmes ved hjælp af φ(n) på følgende måde:
Sætning 24:
39
)(mod)(mod
1)(1
abab
a
, hvis
1),( basfd
Bevis:
Af sætning 20 ved vi at
)(mod1
)(
ab
a
og fra definition 22 ved vi at
)(mod1 abx
,
af sætning 12.1 følger at:
)(mod
)(mod)(mod1)(mod
)(
)(
abxb
abxaab
a
a
Af 12.2 følger at:
)(mod
)(mod
1)(
)(
axb
abx
b
b
b
a
a
□
39
[KL] s. 94
Kryptologi
Side 18
RSA – kryptosystemet
Nu har vi talteori nok til at kigge på den matematik, der ligger til grund for RSA.
Konstruering af nøgler
40
Når nøglerne skal beregnes forgår det på følgende måde:
1. To store primtal, p og q, på mindst 100 cifre hver, vælges.
2. n beregnes så n = pq.
3. φ(n) beregnes. φ(n) = (p – 1)(q – 1)
4. e vælges, så 0 < e < φ(n) og sfd(e,φ(n)) = 1
5. d beregnes, så ed 1 (mod φ(n)). Dvs. d er det inverse element til e modulo
φ(n).
Derved er nøglerne beregnet:
Offentlige nøgle, P
K
: (n,e)
Hemmelige nøgle, S
K
: (n,d)
For at finde ud af om sfd(e,φ(n)) = 1, (pkt. 4) bruges Euklids algoritme. Er
sfd(e,φ(n)) 1, vælges et nyt e, og det testes igen med Euklids algoritme.
d (pkt. 5) beregnes nemmest ved hjælp af sætning 24. Da d er inverst element til e
modulo φ(n) og e dermed er inverst element til d modulo φ(n), gør det ingen forskel
hvilken nøgle, der er offentlig, og hvilken, der er hemmelig. Vi bestemmer her, at
(n,d) altid er den hemmelige nøgle, for overskuelighedens skyld.
Enkryptering og dekryptering
41
En given klartekst, der skal krypteres med RSA, skal første kodes til tal, og derved
deles i blokke, således at hver blok, m, er et tal, hvorom det gælder at
nm 0
.
Enkrypteringen af tallet m med nøglen (n,e) foregår således:
cnmm
e
)(mod
Dekrypteringen af tallet c med nøglen (n,d) foregår således:
mncc
d
)(mod
40
[KL] s. 101 og [TK] s. 122-123
41
[KL] s. 102 og [TK] s.122-123
Kryptologi
Side 19
Hele processen ser således ud:
RSA-kryptering:
42
mnmnmnccnmm
eddede
)(mod)(mod)()(mod)(mod
Bevis:
43
De første 3 lighedstegn giver sig selv, så det vi vil bevise er:
mnm
ed
)(mod
Vi antager at
1),( nmsfd
, hvorefter vi kan bruge sætning 21, så er:
mnmnmnm
neded
)(mod)(mod)(mod
))((mod
da
1))((mod1))((mod nned
ifølge definition 22.
mnm )(mod
følger af 5.1,
da
nm
.
Dermed er sætningen bevist for m og n værende indbyrdes primiske. Da
sandsynligheden for at
1),( nmsfd
er meget lille, vil jeg, i stedet for at bevise at
RSA virker for
1),( nmsfd
, vise, hvor lille sandsynligheden er:
Vi antager at
1),( nmsfd
, og da n = pq,
nm
, må enten p eller q være divisor til m.
Ved at tælle hvor mange tal mellem 1 og pq, der er divisibel med enten p eller q, kan
jeg udtrykke sandsynligheden for
1),( nmsfd
:
p går op i
pqppp )1(,,,3,2,
og n.
q går op i
qpqqq )1(,,,3,2,
og n.
Selvom både p og q går op i n skal det kun tælles en gang. Det samlede antal tal som
enten p eller q går op i er
11)1()1( qppq
.
Antag at p og q begge har ca. 100 cifre, så er:
100
200
100
10
10
101
)1),((
qp
qp
nmsfd
Deraf ser man at det er meget usandsynligt at sfd(m,n) ≠ 1 vil indtræffe, og selvom det
skulle ske virker RSA alligevel. Det kan bevises ved hjælp af Fermats lille sætning og
Den kinesiske restsætning. Da jeg har valgt ikke at vise disse sætninger, udelades
beviset for at RSA virker for
1),( nmsfd
.
Inden jeg går videre til sikkerheden i RSA, vil jeg give et eksempel på RSA i praksis.
42
[KL] s. 102
43
[KL] s. 105-106 og s. 164
Kryptologi
Side 20
Eksempel:
44
Følgende kode RSA-kode er blevet opfanget:
2362
På forhånd ved jeg:
1. Konverteringen fra bogstaver til tal er sket ved at 00 = mellemrum, 01 = A,
02 = B, 03 = C, ….. 29 = Å
2. Beskeden er krypteret i blokke af 4 cifre (dvs. 2 bogstaver)
3. Den offentlige nøgle er (n,e) = (3953,167)
Jeg finder
3828)3953(
45
. For at tjekke resultatet kan jeg se om e og φ(n) er
indbyrdes primiske:
1)3828,167(1))(,( sfdnesfd
For at dekryptere koden skal jeg bruge det inverse element, d, så ed≡1 (mod φ(n)):
46
2063)3828(mod167)3828(mod167
))((mod))((mod)(mod)(mod
111201
1))((11)(1
nenenana
nn
Den hemmelige krypteringsnøgle, d, er nu udregnet, og jeg kan påbegynde
dekrypteringen af koden, c, på følgende måde:
47
1021)3953(mod0524)3953(mod)(mod
mcmnc
d
Denne funktion bruger jeg på hver af de 13 blokke på 4 cifre, så følgende kode
fremkommer:
1105
Ved at afkode cifrene efter den 2. startoplysning, så 10 = J, 21 = U, 12 = L, osv.,
fremkommer klarteksten:
JULEN VARER LIGE TIL PÅSKE
Dermed er koden brudt, og beskeden dekrypteret.
44
Eksemplet er den stillede opgave fra bilaget.
45
[SC] phi(3953). φ(n) kan også findes ved at finde p og q først vha. [SC] fact(3953)
46
[SC] 167^1119 (mod 3828)
47
[SC] 524^2063 (mod 3953)
Kryptologi
Side 21
Sikkerheden i RSA
48
Da RSA er det mest almindelige Public Key system, er det selvfølge interessant at
vide: ”Hvor sikkert er RSA?”
RSA-koden er blevet brudt adskillige gange, og vil altid kunne brydes. Det er hele
handler om nøglestørrelse, computerkraft, algoritmer og selvfølgelig tid.
For at kunne bestemme den hemmelige nøgle udfra den offentlige, skal man kende
φ(n), som kun kan bestemmes udfra p og q, dvs. at bryde en RSA kode er at
faktorisere n i p og q. Faktoriseringen af n kan udtrykkes ved et antal operationer. De
bedste algoritmer man kender kræver mindst
)ln())ln(ln( nn
e
operationer. Hvis n
10^153, dvs. 154 cifre hvilket svarer til en 512 bits nøgle, ville
det kræve
19
105,5
operationer. Til at beskrive den computerkraft der skal til, bruges
en enhed kaldet mips, som står for millioner instruktioner per sekund. 1 mips år (MY)
er det en computer, der kan udføre 1 mips, kan udføre på et år. Følgende tabel viser
hvor mange MY der har været brugt til at bryde RSA gennem tiden:
49
Årstal
antal cifre
MY
1983
71
0,1
1989
100
7
1992
110
75
1993
120
830
1994
129
5000
1996
130
500
1999
154
8000
Mellem 1994 og 1996 er en ny algoritme taget i brug, hvilket hænger sammen med
faldet i MY. Computerkraften siges at fordobles hver 18. måned,
50
og derfor bør
nøglestørrelsen også vokse, så antallet af oprationer, der skal til at bryde koden, også
mindst fordobles. Der findes mange forskellige beregninger på hvor store nøglerne i
fremtiden skal være før at de er sikre. Følgende tabel er et bud derpå:
51
48
[KL] s. 119-120
49
[KL] s. 120 og [RF] Afsnit 2.6
50
[BK]
51
[RF] Afsnit 2.6
Kryptologi
Side 22
Årstal
Anbefalet nøglestørrelse (i bit)
2000
1280
2005
1536
2010
1536
2015
2048
Disse nøgler skulle være sikre mod angreb fra en enkelt gruppe/sammenslutning, men
ikke mod angreb fra efterretningstjenester. Eksempelvis antages det at NSA (The
National Security Agency (USA)) har rådighed over computerkraft svarende til
10
105,1
MY.
52
Det er nok til at bryde en 1024 bits kode på ganske få dage.
53
Antallet af MY, der skal bruges til at faktorisere et tal, afhænger af hvilken algoritme
der bruges. En god algoritme er mindst lige så vigtig som computerkraften. Jeg vil
ikke komme ind på de nyeste algoritmer, da de er meget avancerede. I stedet vil jeg
vise en af de klassiske algoritmer.
Algoritmer
En af de klassiske algoritmer er Fermats metode, som jeg ikke vil bevise.
Fermats metode:
54
Lad n, nN, være ulige. Da kan n faktoriseres hvis
,
22
yxn
x,yN
Algoritmen:
55
Lad n være tallet der skal faktoriseres. Hvis vi kan bestemme x og y, kan vi derved
bestemme p og q, da
pqyxyxyxn ))((
22
, p = x + y og q = x - y.
x vælges som det mindste tal hvorom der gælder at x
2
> n. Algoritmen kommer til at
se således ud, for
2
yz
og
jkx
,
zjk ,,
:
52
[BK] NB. Kilden er fra 1996, dvs. at computerkraften er blevet fordoblet 4 gange, så:
94
102
10
105,1
53
Ifølge [BK] skal antagelsen antallet af MY til rådighed for NSA på ingen måde regnes for sikkert,
men kun et kvalificeret bud.
54
[KL] s. 128
55
[KL] s. 128-129
Kryptologi
Side 23
znk
znk
znk
znk
2
2
2
2
)3(
)2(
)1(
Algoritmen stopper når z er et kvadrattal. Dette vil senest ske når q = x - y = 1. Da
1 nn
. x - y = 1 kan udtrykkes ved k, j og n på følgende måde:
)1½(
122)1222(2
)()1()1(1
2222
222
njk
jkjkkjjkkjjkn
njkjkzjkyx
Hvis z først er et kvadrattal når
)1½( njk
er n et primtal. Hvis et kvadrattal
dukker op før er n = pq. Derved kan Fermats metode bruges til faktorisering af ”store
tal”.
Konklusion
At RSA kan brydes, vil jeg ikke lægge skjul på, men ved at vælge en tilstrækkelig stor
nøgle, vil det tage uoverskuelig lang tid at bryde koden. Dermed kan vi konkludere at
RSA opfylder de krav, der måtte være til et kryptosystem, hvilket også afspejles i at
RSA er det mest anvendte kryptosystem i verden.
Kryptologi
Side 24
Litteraturliste
[KL] Peter Landrock & Knud Nissen: Kryptologi – fra viden til videskab
© 1997. Forlaget ABACUS
[TT] Jens Carstensen: Talteori
© 1997. Forlaget Systime a/s
[ET] Waclaw Sierpinski: Elementary Theory of Numbers
© 1988. PWN-Polish Scientific Publishers
[EC] David E. Newton: Encyclopedia of Cryptology
© 1997. Instructional Horizons Inc.
[KG] Bo Nilsson: Kryptografering
Artikel i Teleteknik. Årgang 32, nr. 2
© 1981. Tele Danmark
[TK] Tore Herlestam: Talteoretisk kryptologi – att inte kunna invertaera en
inverterbar funktion
Artikel i Normat, Nordisk Matematisk Tidskrift, Årgang 29, nr. 1
© 1981. Universitetsforlaget
[KE] David F. Ogren: A case for 2560 bit keys
http://www.arraydev.com/commerce/JIBC/9605-4.htm
© 1996. JIBC
[RF] Sam Simpson: PGP DH vs. RSA FAQ
http://www.scramdisk.clara.net/pgpfaq.html#SubKeySize
© 1999. S.Simpson
[SC] Simcalc online
http://emmy.math.uni-sb.de/~simath/simcalc_online.html
(C) SIMATH
Kryptologi
Side 25
Bilag 1
Figur 1
Konventionelt kryptosystem:
Figur 2
Public Key kryptosystem:
Afsender
E(M, K) = C
M
C
M
Modtager
D(C, K) = M
Nøgle, K
K
K
Opponent
D(C, K) = M
Afsender
E(M, P
K
) = C
M
C
M
Modtager
D(C, K) = M
Opponent
D(C, P
K
) ≠ M
P
K
S
K
Nøgle, P
K
, S
K
.