Matematikkenbagkrypteringogsignering NemID–RSA ForedragiUNFpure.au.dk/portal/files/48444947/NemID_ver.2_.pdf · PKI - Public Key Infrastructure Regning med rester Kryptering via

PKI - Public Key Infrastructure Regning med rester Kryptering via RSA Elliptiske kurver - ElGamal PKI

Matematikken bag kryptering og signeringNemID – RSAForedrag i UNF

Johan P. Hansen

Institut for Matematik

segla1sA A R H U S U N I V E R S I T E T

Institut for Matematik Johan P. Hansen


Disposition

1 PKI - Public Key InfrastructureSymmetrisk kryptografiAsymmetrisk kryptografi

2 Regning med resterIndbyrdes primiske talModulo - regning med resterEuler-Fermats sætning

3 Kryptering og signering ved hjælp af et offentligt nøglekryptosystem RSA

4 Elliptiske kurver - ElGamal PKI




Oversigt








Public Key Infrastructure (PKI)

Public Key Infrastructure (PKI) er en teknologi, der gør detmuligt for to parter at identificere sig entydigt over for hinanden.Begge parter skal have sikkerhed for:

at den anden part er entydigt identificeretat meddelelsen kommer fra den, der påstår at have sendt denat meddelelsen ikke er blevet ændret eller læst undervejs

NemID er baseret på PKI.




Symmetrisk kryptografi - Cæsar

Kryptografiske teknikker er anvendt siden det antikke Ægyptenog af Julius Cæsars regime (Julius Cæser omkom ved etattentat 15. marts 44 f. Kr.)Cæsars navn er endda knyttet til en krypteringsmetode, hvorman blot forskyder alfabetets bogstaver 3 pladser henholdsvisfrem (ved kryptering) og tilbage (ved dekryptering)Der er symmetri mellem krypterings- og dekrypteringsmetode




Symmetrisk kryptografi - styrke og svaghed

Oprindelig kendte man blot symmetrisk kryptografi, hvor de topartnere, der skulle kommunikere, delte en fælles hemmeligkrypteringsnøgle, der blev anvendt ved både kryptering ogdekryptering.Symmetriske krypteringssystemer anvendes stadig i storudstrækning, de er hurtige; men lider af en stor praktisksvaghed, nemlig kravet til sikker udveksling af den fælleshemmelige nøgle.




Asymmetrisk kryptografi

Det var et gennembrud, at man indså, at man kan lavehemmelig kommunikation, selvom transmissionen overvågesomhyggeligt, og selvom der ikke forinden var udvekslet enfælles hemmelig nøgleDenne ved første tanke helt umulige opgave løses vedasymmetrisk kryptografi – et begreb, der opbygges omkringikke blot en nøgle; men et nøglepar




Nøglepar

Kunsten er, at lave et nøglepar.Den ene nøgle er offentlig (public key) og udveksles i fuldoffentlighedDen anden nøgle er privat (private key), og den skal ikkeudvekslesDe to nøgler i parret har asymmetriske funktioner: Låses dermed en nøgle, kan den anden nøgle (og kun den) låse op ogvise versaDet skal være umuligt/vanskeligt at konstruere den ene nøgleud fra den anden




Hemmelig kommunikation i PKI

Hemmelig kommunikation foretages ved, at afsender låserdokumentet med den offentlige nøgle i modtagerens nøglepar.Modtageren kan nu låse dokumentet op ved at anvende sinmodsvarende private (hemmelige) nøgle i sit nøglepar.Han – og kun han – kan låse dokumentet op, for blotmodtageren besidder den hemmelige nøgle i nøgleparret, dermatcher den offentlige nøgle.




Digital underskift i PKI - signering

Digital underskrift - signering af et dokument laves, ved atafsender låser dokumentet med sin private (hemmelige) nøgleEnhver kan nu låse dokumentet op med afsenders offentligenøgle og derved overbevise sig om, at afsender besidder dentilsvarende hemmelige nøgle og dermed er den, han udgiver sigforForudsætter, at nøgleparret er udstedt af en troværdigautoritet




PKI historie

Offentlig-nøgle-kryptering (PKI) blev opfundet i 1969 af Ellis,Williamson og Cocks, der arbejdede ved British GovernmentCommunications Headquarters. Deres opfindelser blevimidlertid hemmeligholdt af den britiske regering indtil 1997I mellemtiden blev offentlig-nøgle-kryptering (PKI)genopfundet af Adleman samt Diffie, Rivest og Shamir, der i1978 skabte offentlig-nøgle-kryptosystemet RSA




PKI - RSA

Kunsten ved at lave et offentlig-nøgle-kryptosystem er altså atgive en metode til at konstruere nøglepar, således at kendskabtil den offentlige nøgle ikke gør det muligt at bestemme dentilhørende private (hemmelige) nøgle.RSA-kryptosystemet er en sådan metode, hvor sikkerhedenhviler på den erfaring, at det er umuligt effektivt at faktorisereet helt tal i et produkt af primtal.




Oversigt








Indbyrdes primiske hele tal

DefinitionTo hele tal m, n kaldes indbyrdes primiske, hvis de ingen fællesdivisorer har, når vi ser bort fra 1 og -1. Med φ(m) betegner viantallet af positive hele tal mindre end m, der er indbyrdes primiskemed m (Euler’s φ-funktion).

Opgave

Vis, atφ(12) = 4

Lad p, q være forskellige primtal. Vis at

φ(p) = p − 1 , φ(pq) = (p − 1)(q − 1).




Euler’s φ-funktion er tidskrævende at beregne

I opgaven har vi set, at det et let at bestemme φ(n), hvis vi kenderfaktoriseringen af n i 2 primfaktorer. Kendes faktorisering af n ikke,er det imidlertid MEGET tidskrævende af bestemme φ(n). Har nfor eksempel 100 cifre vil det, at forsøge sig frem med et tal1, 2, 3, . . . , n ad gangen tage

10100

1012 sekunder ∼ 1061 år

på en maskine, der i 1 sekund kan foretage 1012 (en million million)undersøgelser af om et tal er primisk med n. (Universets alderanslås til 15 · 1012 år).Det er det store tidsforbrug, der fordres til bestemmelse af φ(n),der er sikkerheden i RSA-kryptosystemet, som vi vender tilbage tilsenere.




Modulo - regning med rester

Gauss indførte en notation, som letter omgangen medheltalsdivision med rest.

DefinitionGivet hele tal a, b og m > 0. Vi siger, at a er kongruent med bmodulo m og skriver

a ≡ b mod m

hvis a og b har samme rest ved division med m, altså hvis m går opi forskellen a − b. Når m fremgår af sammenhængen, skriver vi blota ≡ b.

Eks. 19 ≡ 7 mod 12, 1 ≡ −1 mod 2 og 32 ≡ −1 mod 5.




Regneregler

Lemma

Lad m > 0 være givet. Hvis a1 ≡ b1 og a2 ≡ b2, så er

a1 + a2 ≡ b1 + b2 , a1a2 ≡ b1b2




Euler-Fermat

Sætning

Antag at k ,m er indbyrdes primiske. Så er

kφ(m) ≡ 1 mod m.




OpgaveEftervis, at

kφ(12) ≡ 1 mod 12.

for alle k , der er primiske med 12.




Oversigt








Kryptering og signering - nøglepar

En person A, der ønsker at lave et kryptosystem med henblik påmodtagelse gør følgende:

vælger 2 store primtal p, q og beregner n = pqberegner φ(n), hvilket er let for A; men tidskrævende forandre, der blot kender n og ikke p, qvælger et e > 0 primisk med φ(n)beregner positivt f (og negativt g), så 1 = ef + φ(n)g(Euklids algoritme)offentligør n, e - det er den offentlige nøgle

Krypteringssystemet har n, e er som offentlig nøgle og φ(n) og fsom hemmelig nøgle.




Kryptering

En vilkårlig person B ønsker at sende tallet k > 0 til personen A. Bindkoder tallet k ved brug af den offentlige nøgle n, e - nemlig vedat beregne og sende:

h ≡ ke mod n




Dekryptering

Personen A modtager h og beregner ved hjælp af sin hemmeligeviden om φ(n) og f

hf ≡ (ke)f ≡ kef ≡ k1−φ(n)g ≡ k · (kφ(n))−g ≡ k mod n

ifølge sætningen Euler-Fermat.




Opgave

Lad p = 89 og q = 97. Bestem n og φ(n). Lad e=71. Bestemf > 0 og g så

1 = ef + φ(n)g

Indkod k = 3 ved at beregne h = 3e og dekrypter ved at beregne(3e)f .




RSA praksis og NemID

Effektiv konstruktion af mange par af store primtal er centralfor en praktisk udrulning af RSA-kryptosystemet i stor skala.Firmaet Cryptomathic har eksempelvis et produkt Cardink,http://www.cryptomathic.dk/products/emv/cardink,hvorom de skriver:

1 CardInk is very scalable and is currently running in a liveproduction environment generating data for 180 000 cards perhour

2 CardInk is used by more than 100 customers across the globeto issue +200 million EMV cards annually. Our customersinclude prominent issuers and service providers such as ArabNational Bank, First Data, Credit Agricole.

Bag NemID anvendes RSA-nøglepar med mindst 1024 bits,altså med over 300 decimale cifre. Dit nøglepar ligger på encentral server, som du kommunikerer med via dit NemID kort.



http://www.cryptomathic.dk/products/emv/cardink


Oversigt








Elliptiske kurver

Elliptiske kurver er en speciel klasse af kurver E , hvor det er muligtat addere punkter (meget lig, hvordan vi adderer tal):

P,Q ∈ E ⇒ P + Q ∈ E

og dermed addere et punkt med sig et helt antal gange n:

P ∈ E ⇒ nP =

n︷︸︸︷P + · · ·+ P ∈ E




ElGamal

1 Hemmelig nøgle: et tal s2 Offentlig nøgle: et punkt P ∈ E og punktet B = sP ∈ E .3 Sikkerhed beror på, at man ikke kan bestemme s (den

hemmelige nøgle) udfra kendskab til P og B (den offentligenøgle)




ElGamal

1 Vil sende beskeden M ∈ E2 Vælger et tilfældigt tal k og krypterer ved hjælp af den

offentlige nøgle P,B

M1 = kP , M2 = M + kB

som sendes.3 Modtageren beregner ved hjælp af den hemmelige nøgle s:

M2 − sM1 = (M + kB)− s(kP) = M + kB − k(

B︷︸︸︷sP ) = M

og har dermed dekrypteret.




Elliptiske kurver og digitale frimærker




Information

Johan P. Hansen: Tal og mængder, Aarhus Universitetsforlag,2012Adr.: Institut for Matematik, Ny Munkegade, 8000 Aarhus,DENMARKe-mail: [email protected]: (+45) 2899 2449

homepage: http://home.imf.au.dk/matjph/homepage:http://pure.au.dk/portal/da/[email protected]



http://home.imf.au.dk/matjph/

http://pure.au.dk/portal/da/[email protected]

Documents

Matematikkenbagkrypteringogsignering NemID–RSA ForedragiUNFpure.au.dk/portal/files/48444947/NemID_ver.2_.pdf · PKI - Public Key Infrastructure Regning med rester Kryptering via