1 Om bitcoin og kryptovaluta

Kommentarer/spørgsmål?

1.1 Oplæg om kryptovaluta og matematik

Dette oplæg fortæller om de matematiske principper bag kryptovalua og blockchain. Der er afsæt i følgende tre matematiske temaer.

Kryptografiske hash-funktioner og proof of work.
Lidt sandsynlighedsregning omkring den geometriske fordeling.
Digital signatur og det diskrete logaritmeproblem.

1.1.1 Diskret matematik i det supplerende stof

Oplægget kan benyttes som inspiration til det supplerende stof omkring diskret matematik i gymnasieskolen. I denne kontekst er indfaldsvinklen et forløb i Euklids algoritme og regning med kongruenser med formålet at forstå den digitale signatur i RSA kryptosystemet. Alt efter niveau kan man vælge omfanget af talteorien.

Denne vinkel er skitseret i afsnittet Justerbar talteori. For at få en fornemmelse for nogle af elementerne i forløbet kan man kigge på Khan Academys online forløb om modulær aritmetik (med indbyggede opgaver).

Den drivende motivation i forløbet kan feks være nødvendigheden af digital signatur i Bitcons blockchain, hvor sidstnævnte kan forklares til eleverne i overordnede termer evt med referencer til de adskillige YouTube videoer, der findes om blockchain.

Mantraet er at eleverne skal undervises i tal for at have en overordnet forståelse for hvordan deres penge er beskyttet online.

Oplægget kan også bruges som eksempel på anvendelser af sandsynlighedsregning i kernestoffet. Her er motivationen mining algoritmen i bitcoin.

1.1.2 SRP

Oplægget kan også benyttes som inspiration til et SRP forløb i gymnasiet, hvor man går dybere ind i den reelle kryptering, som bruges i bitcoin herunder det diskrete logaritmeproblem.

1.1.3 Interaktiv feedback

Jeg vil meget gerne have feedback på denne version af mit oplæg om bitcoin. Det er muligt at annotere dette interaktive kapitel. Se videoen nedenfor for yderligere instruktioner.

Kommentarer/spørgsmål?

1.2 Introduktion

I December 1998 blev PayPal oprettet som et medium til online betaling for e-handel på nettet. Stifterne inkluderede veritable kendisser som Elon Musk og Peter Thiel. For at kunne hæve beløb fra PayPal er det nødvendigt at have sin egen bankkonto tilknyttet mht overførsler.

Det har længe været en drøm i det kryptografiske samfund at kunne lave sikre internetpenge uden at involvere en tredjepart som PayPal eller en bank. En person på nettet uden en bankkonto skal have mulighed for at modtage og sende penge til en hvilken som helst anden person på nettet uden at en tredjepart er involveret.

1.3 Om bitcoins historie

Denne drøm blev realiseret i et berømt white paper af Satoshi Nakamoto i 2008. Her blev det teoretiske fundament for den første kryptovaluta, bitcoin, lanceret.

Bitcoins historie frem til 2014 er glimrende illustreret på http://historyofbitcoin.org/.

Som en god introduktion til bitcoin kan anbefales Morgan Spurlocks dokumentarfilm om bitcoin nedenfor.

Kommentarer/spørgsmål?

Interessen for bitcoin er vokset eksplosivt det sidste stykke tid og fra at være kurssat til omkring 650 USD for et år siden ligger kursen nu (1/11/2017) omkring 6000 USD.

Det estimeres at den illusoriske Satoshi Nakamoto ejer en million bitcoins, hvilket i dag svarer til 6 milliarder dollars (nummer ca 239 over verdens rigeste og rigere end Donald Trump, som angives til en net worth på 3,1 milliarder dollars på Forbes listen over verdens dollarmilliardærer).

Kursudviklingen på bitcoin (BTC) kan udforskes via nedenstående interaktive graf.

Der er de sidste år kommet adskillige børser for kryptovalutaer i verden. Så vidt jeg ved er der endnu ikke en i Danmark, selvom det er muligt at købe feks bitcoins i Danmark (København).

Der er livlig handel med bitcoins 24/7: https://www.gdax.com/trade/BTC-USD.

Bitcoin var den første decentraliserede kryptovaluta, men siden er over 1000 kryptovalutaer kommet til.

Hele maskineret drives af open source software (skrevet i C++), som kan hentes på GitHub af enhver med netadgang.

1.4 Principperne bag

I kryptovaluta og specielt bitcoin er regnskabet decentraliseret. Der er tale om en slags distribueret netbank, som i princippet ejes af alle på internettet, men med matematisk veldefinerede regler for bogføring af transaktioner.

Det traditionelle finansielle system er afbildet i (A). Her er der en central instans (en bank), som holder øje med pengene. Afbildet i (C) er det distribuerede system, hvor alle med adgang til nettet kan agere bank og bogføre transaktioner.

Regnskabsbogen kaldes for the blockchain. Navnet skyldes at transaktioner organiseres i blokke, som er kædet sammen.

Udfordringen er at få alle de distribuerede banker til at bogføre konsistent i en fælles veldefineret regnskabsbog. Lad os en gang for alle slå fast: Alle knuderne i netværket har adgang til hele blokkæden, alle transaktioner foretaget tilbage til den såkaldte genesis block.

1.4.1 Transaktioner er krypteret med digital signatur

Bitcoin benytter et offentligt nøgle kryptosystem til brug ved digital signatur af transaktioner.

Som bruger på bitcoin netværet har man en 160 bit adresse som feks

${\tt 1BvBMSEYstWetqTFn5Au4m4GFg7xJaNVN2}$ En bitcoin adresse er genereret ud fra den offentlige nøgle, som er på 256 bits.

Opgave

Den offentlige nøgle er konstant. Bitcoin adressen er associeret med den offentlige nøgle og kan (bør) genereres på ny for hver transaktion. Hvordan hænger det sammen? Er det usikkert at nøjes med en konstant bitcoin adresse?

Konsulter evt følgende artikel.

Denne adresse bruges af folk, der sender penge til en. En mere teknisk beskrivelse kan findes her. Der er tale om en 160 bit hash af ens offentlige nøgle i ECDSA nøgleparret. Den private nøgle benyttes til digital signatur af ens transaktion, når man sender bitcoins over netværket. Nedenstående kan ikke indskærpes kraftigt nok!

Hvis man mister eller får stjålet sin private nøgle har man tabt alle sine bitcoins.

En af de forhenværende større bitcoin børser Mt Gox fik stjålet 850.000 bitcoins og gik konkurs i 2014.

I bitcoin protokollen benyttes elliptisk kurve kryptografi. En af de smukkeste anvendelser af moderne algebraisk geometri. Det er kritisk at denne digitale signatur implementeres korrekt. Fejlagtige implementationer har ledt til tyveri af bitcoins.

Transaktioner underskrives af afsenderen med hans/hendes private nøgle, organiseres med tidsstempel i blokke og kædes sammen.

Hvordan holder hele verden styr på dette? Hvordan bliver de enige om den samme blokkæde? Hvordan undgår man at en ondsindet person bruger den samme bitcoin to gange?

Svarene på disse spørgsmål er det nyskabende i Nakamotos artikel. For at få godkendt en blok i blokkæden kræves at den er afsluttet med et såkaldt proof of work, som er arbejdet med at løse et tidskrævende matematisk problem hvis løsning nemt kan verificeres.

Processen med at løse dette matematiske problem kaldes mining, fordi man får (miner) bitcoins ved at løse det. Faktisk er dette måden bitcoins bliver født på.

Bitcoin protokollen siger at minere tjener 50 BTC for hver af de første 210.000 blokke, 25 BTC for de næste 210.000 blokke etc. Pt er belønningen 12.5 BTC for at mine en blok.

Quiz

Med protokollen for udbetalingen af bitcoins for mining er der en øvre grænse for hvor mange bitcoins der vil være i fremtiden. Hvor stor er denne (mindste) øvre grænse?

42.000.000 BTC

21.000.000 BTC

84.000.000 BTC

100.000.000 BTC

Bitcoin er en levende organisme og transaktioner bliver foretaget hvert sekund og sat ind i the blockchain. Nedenfor vises transaktioner og mining live fra hjemmesiden https://blockexplorer.com.

1.4.2 Udforskning af the blockchain

Man kan udforske alle blokke via følgende link: https://live.blockcypher.com.

1.5 Mining

Bitcoin skal svare til digitalt guld. En guldmønts værdi svarer til værdien af guldet, som indgår i den. En bitcoins værdi svarer til den mængde strøm, der medgår til at mine (lave) den. I dette afsnit kommer vi ind på hvad det vil sige at mine bitcoins.

Ideen kommer fra en artikel fra 1993, hvor temaet er en protokol for at forhindre junk mail. Computeren skal løse et matematisk problem for at sende en email til modtageren (eller kontakte en server). En email har en standard header $h$ , som består af en streng taget fra mængden $T$ af strenge over et alfabet, som typisk er computerens synlige tegn. Headeren $h$ kunne feks være

${\tt 2017:11:1:13:20:niels@math.au.dk}$

Antag nu vi har en uforudsigelig (hash) funktion

$f: T \rightarrow \{0, 1, 2, \ldots, N\},$ hvor $N$ er et stort tal (oftest $256$ bits).

En uforudsigelig eller kryptografisk hash funktion er en hash-funktion, som er sværd at invertere. I forhold til bitcoin er SHA-256 den interessante kryptografiske hash-funktion. Det skal være umanerligt svært at finde to forskellige strenge $x$ og $y$ med $f(x) = f(y)$ (et sådant par kaldes en kollision for $f$ ). Prøv selv nedenfor ved at indtaste forskellige strenge for $x$ og $y$ !

x :

e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

y :

e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

Opgaven går nu ud på at beregne en streng $\sigma$ , så

$f(h\sigma) < M,$ hvor $M < N$ er et givet tal. Jo mindre $M$ er, jo sværere er opgaven. Den svære matematiske opgave går ud på at finde $\sigma$ så

$f({\tt 2017:11:1:13:20:niels@math.au.dk:}\sigma)$ starter med et nærmere angivet antal nuller i hex-notation.

Nedenfor et interaktivt element, hvor proof of work illustreres i eksemplet ovenfor. Tryk på knappen for at starte arbejdet med at finde $\sigma$ . Strengen markeret med blåt angiver den aktuelle rekord mht antal nuller i hash-funktionen $f$ . Nullerne i hash-funktion er angivet med rødt i sidste linje.

Antal hashes: ---

2017:11:1:13:20:niels@math.au.dk:------------------------------

---------------------------------------------------------------

I det nuværende globale bitcoin mining netværk benyttes specialiseret hardware. Bitcoin mining er ikke længere for den almindelige borger, som det var tiltænkt fra starten. Nyere kryptovalutaer som Monero og Ethereum benytter andre mining algoritmer så almindelige GPUer kan benyttes. Så sent som 24/10/2017 blev den alternative bitcoin gold indført, som en fork fra den originale blockchain. Målet med bitcoin gold er at gøre mining mere tilgængeligt.

Javascript applikationen ovenfor har en meget langsom hash rate sammenlignet med feks det globale bitcoin mining netværk, som pt hasher

${\tt 13.000.000.000.000.000.000}$ gange i sekundet. Bitcoin parametrene justeres løbende så man opnår at det tager i gennemsnit 10 minutter at mine en blok.

Quiz

Hvad er sandsynligheden for at output fra SHA-256 starter med $k$ nuller ?

$\left(\frac{1}{16}\right)^k$

$\left(\frac{1}{32}\right)^k$

$\left(\frac{1}{64}\right)^k$

$\left(\frac{1}{8}\right)^k$

1.5.1 Den geometriske fordeling anvendt på mining tid

Betragt et stokastisk eksperiment, hvor sandsynligheden for succes er $p$ . Antag nu at eksperimentet udføres indtil man får succes sammenfattet i den stokastiske variabel $X$ .

Sandsynligheden for at eksperimentet stopper efter $k$ trin er så

$\Pr(X = k) = (1-p)^{k-1} p \tag{1.1}$ svarende til ikke succesrigt udfald i de første $k-1$ trin efterfulgt af succes i det $k$ -te trin. Denne fordeling kaldes den geometriske fordeling med sandsynlighed $p$ .

Middelværdien for $X$ er

$\begin{aligned} E(X) &= \sum_{k=1}^\infty k\, \Pr(X= k) = p \sum_{k=1}^\infty k\, (1-p)^{k-1}\\ &= p\, \frac{1}{(1 - (1-p))^2} = \frac{1}{p} \end{aligned}$ Dette fortolkes som den gennemsnitlige ventetid på succes. Hvis man feks slår plat og krone med en fair mønt skal man gennemsnitligt vente to slag på krone.

Formlen (1.1) giver også sandsynligheden for at man skal vente mere end $m$ trin på succes som

$\Pr(X > m) = \sum_{k > m} (1-p)^{k-1} p = (1-p)^m.$ Bemærk at

$(1-p)^m = e^{m \log(1-p)}\approx e^{-m p}.$ Sidste approksimation holder for små $p$ pga rækkeudviklingen

$\log(1-p) = -p - \frac{p^2}{2} - \frac{p^3}{3} - \cdots$ Sandsynligheden for at vente længere end forventet ligger altså omkring

$e^{-1} \approx 0.367879\ldots$ for små $p$ .

Opgave

Hvor mange hashes kræves i gennemsnit for at ramme $4$ nuller?
Find den seneste blok på https://blockexplorer.com. Tæl antallet af ledende nuller i BlockHashen. Hvis vi antager at det tog 10 minutter at lave BlockHashen som proof of work, hvor mange hashes per sekund har nettet så formentlig gennemført?
Hvad sandsynligheden for at en mining tager 20 minutter?

1.6 Bitcoin forklaret af 3Blue1Brown

YouTuberen 3Blue1Brown producerer fremragende videoer om matematik generelt. Nedenfor en video, hvor han forklarer bitcoin og blockchain meget pædagogisk.

Kommentarer/spørgsmål?

1.7 Justerbar talteori

Et forløb i diskret matematik kan som overordnet motivation have sikkerhed af penge online og man kan skrue på forløbet ud fra C, B og A-niveau. Man kan feks vælge at stoppe ved Euklids algoritme og ikke give den fulde underbygning for digital signatur.

1.7.1 Primtal

Talteori er den del af matematikken, som beskæftiger sig med de naturlige tal $1, 2, 3, \ldots$ . Her kan primtal passende uddybes i starten af forløbet som en appetitvækker, måske med visualisering i form af Eratosthenes si (fra Wikipedia):

Man kan illustrere Euklids vidunderlige bevis for at der er uendeligt mange primtal, skitsere primfaktorisering og antyde at store primtal benyttes i kryptografi.

1.7.2 Største fælles divisor og Euklids algoritme

Største fælles divisor $\mathrm{sfd}(m, n)$ af to naturlige tal $m$ og $n$ introduceres på den enkleste måde, som det største naturlige tal, der går op i både $m$ og $n$ . Efter nogle indledende eksempler omkring største fælles divisor, kan man guide eleverne i retning af

$\mathrm{sfd}(m, n) = \mathrm{sfd}(m-n, n)$ for $m > n$ for at ende med

$\mathrm{sfd}(m, n) = \mathrm{sfd}(m-q n, n), \tag{1.2}$ hvor

$m = q n + r \tag{1.3}$ er division af $m$ med $n$ med rest $r$ . Dette er hjørnestenen i Euklids algoritme.

Man bør måske nævne at to tal er primiske, hvis deres største fælles divisor er $1$ og nævne (vise ud fra Euklids algoritme) at et primtal går op i et produkt hvis og kun hvis det går op i en af faktorerne.

1.7.3 Euklids udvidede algoritme

Her kommer den første større pædagogiske udfordring: At forklare at Euklids algoritme faktisk giver mere end blot største fælles divisor $d$ af $m$ og $n$ , men også to hele tal (som kan være negative) $a$ og $b$ , så

$a m + b n = d. \tag{1.4}$

Man kan vælge at opstille Euklids algoritme i tabelform ud fra trin og skitsere, hvordan $a$ og $b$ bliver opdateret fra gang til gang. Et helt præcist bevis føler jeg ikke er nødvendigt her. Jeg tror de færreste gymnasieelever vil kunne forstå notationen i det.

1.7.4 Kongruensregning og endelig aritmetik

Den oprindelige definition, som Gauss skrev ned er meget kortfattet: To tal (nu hele) $a$ og $b$ er kongruente modulo $n$ , hvis $n$ går op i $a - b$ . Dette skrives

$a \equiv b\, (\mathrm{mod\, } n) \qquad \Leftrightarrow \qquad n \mid a - b.$ En første opgave kunne her være at se ud fra (1.3) at

$m \equiv r\, (\mathrm{mod\, } n).$ Ethvert tal er kongruent med sin rest modulo $n$ . Dette leder så frem til endelig aritmetik med kun $n$ tal, hvor man indfører addition og multiplikation modulo $n$ .

Multiplikation modulo $13$ .

Hovedeksemplet skal her være algoritmen til at udregne $a^M$ modulo $n$ , hvor $a^M$ er et meget stort tal. Interessen kan skærpes ved først at spørge: Er der en god ide til at løse følgende problem, når man kun må bruge en enkel lommeregner og ikke Maple: Hvad er resten af

$12^{11}$ divideret med $21$ ?

Khan Academy har et forløb omkring modulær aritmetik, som også kommer ind på hurtig eksponentiering.

1.7.5 Fermats lille sætning

Fermats lille sætning siger at hvis $p$ er et primtal, så gælder

$a^{p-1} \equiv 1\, (\mathrm{mod\, } p)$ for alle tal $a$ , som $p$ ikke går op i. Dette resultat er adgangsbilletten til at forstå den digitale signatur i RSA. Man kan lade eleverne eksperimentere (som i tabellen nedenfor) og undres over dette resultat.

Fermats lille sætning for $a=5$ og $p=23$ fra cryptofundamentals.

Et bevis kan gennemføres (hvis klassen er til det) ved at benytte at et primtal går op i et produkt hvis og kun hvis det går op i en af faktorerne.

Nu er vi endelig fremme, hvor vi kan forklare den digitale signatur via talteori.

1.8 Digital signatur i RSA

Begynd med at generere to meget store primtal $p$ og $q$ og lad $N = p q$ .

Det er ikke muligt at gå i detaljer med det i gymnasiet, men primtallene bliver kun genereret probabilistisk i.e., de er kun primtal med en vis sandsynlighed (dog meget, meget tæt på $1$ ).

Meddelelser som skal krypteres oversættes til tal $X$ så $0\leq X < N$ .

Talteorien, som gør at krypteringssystemet RSA virker er gemt i følgende resultat.

Lad $X$ være et (helt) tal og $m$ et naturligt tal. Så gælder

$X^{m (p-1)(q-1) + 1} \equiv X\, (\mathrm{mod\, } N),$

Bevis

Her skal man dreje beviset for at komme til at benytte Fermats lille sætning. Første observation er at $N$ går op i et tal hvis og kun hvis $p$ og $q$ gør det. Så vi kan nøjes med at bevise at

$X^{m (p-1)(q-1) + 1} \equiv X\, (\mathrm{mod\, } p).$ ( $q$ behandles analogt). Hvis $p\mid X$ er dette rigtigt. Hvis $p\nmid X$ følger dette fra Fermats lille sætning på formen

$X^{m (p-1)(q-1)} = \left(X^{m (q-1)}\right)^{p-1} \equiv 1\, (\mathrm{mod\, } p).$

RSA krypteringssystemet er et offentligt nøgle krypteringssystem. Den offentlige nøgle vælges som et tal $e$ primisk med $(p-1)(q-1)$ dvs

$\mathrm{sfd}(e, (p-1)(q-1)) = 1.$ Vi kan så benytte Euklids udvidede algoritme til at finde tallene $d>0$ og $k<0$ så

$d e + k (p-1)(q-1) = 1, \tag{1.5}$ jvf (1.4). Den hemmelige nøgle er nu $d$ .

1.8.1 Kryptering

Krypteringen af meddelelsen $X$ , hvor $0\leq X < N$ finder sted med den offentlige nøgle $e$ :

$X\mapsto X^e \quad(\textrm{mod}\, N).$

1.8.2 Dekryptering

Dekryptering finder sted med den hemmelige nøgle $d$ :

$X\mapsto X^d \quad(\textrm{mod}\, N).$

1.8.3 Hvorfor virker det?

Pga (1.5) er

$(X^e)^d = X^{d e} = X^{-k (p-1)(q-1)+1} \equiv X \quad(\textrm{mod}\, N)$ ud fra Sætning 1.6. Dvs modtageren af en meddelelse krypteret med vedkommendes offentlige nøgle $e$ kan læses ud fra kendskab til den hemmelige nøgle $d$ .

Kryptering og dekryptering kan som sagt udregnes effektivt via exponentiation by squaring.

1.8.4 Digital signatur via RSA

Digital signatur går ud på at underskrive et dokument elektronisk. Der er ikke tale om en almindelig underskrift. Underskriften afhænger af det underskrevne!

I offentlig nøgle kryptografi skal alle have mulighed for at kunne checke at jeg er den retmæssige underskriver ved at benytte den offentlige nøgle.

Princippet bag digital signatur via RSA er nogenlunde ligetil: En meddelelse $X$ underskrives ved hjælp af den hemmelige nøgle $d$ som parret $(X, S)$ , hvor

$S = X^d\,(\mathrm{mod\, } N)$ Alle kan nu verificere med den offentlige nøgle $e$ at underskriveren er den rette (kun underskriveren har kendskab til den hemmelige nøgle) ved at checke om

$S^e = X\, (\mathrm{mod\, } N).$

Man plejer ikke at underskrive den (ofte lange) oprindelige meddelelse, men versionen som er blevet kørt gennem en kryptografisk hash funktion som SHA-256.

Nem ID anvender pt digital signatur med SHA-256 og RSA med mindst 2048 bits (dvs tallet $N$ er $\geq 2^{2048}$ ). Du har som borger dog ikke direkte adgang til din private nøgle, som opbevares på en central server. Adgangen til nøglen er sikret gennem den velkendte to-faktor autentifikationsløsning med nøgleviser/kort.

Her er det lidt interessant at bemærke at krypteringen af bitcoin via det diskrete logaritmeproblem og elliptisk kurve kryptografi anses for at være stærkere end Nem IDs kryptering.

Man kan evt illustrere i klassen at RSA og digital signatur går ud fra enorme tal i praksis ved at inddrage computere (CAS) som nedenfor.

Programmeringssproget python er frit tilgængeligt for alle platforme og har et væld af nyttige biblioteker, som feks ${\tt rsa}$ :

Python 2.7.12 (default, Nov 19 2016, 06:48:10) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import rsa
>>> (pub, priv) = rsa.newkeys(512)
>>> pub
PublicKey(773210119200510362244948221013384369395793712975685405379287359770670046558601102610
1511729442512782385132059910405865820157668463435425587867747433155067, 65537)
>>> priv
PrivateKey(77321011920051036224494822101338436939579371297568540537928735977067004655860110261
01511729442512782385132059910405865820157668463435425587867747433155067, 65537, 75125391077119
3338515789903737556847363269000220329643910027952465892333386570357824688709264287340055431300
5220241264198438070170490991336173806251072161, 4948461313383035895125571010215329187890541505
284523843836126989339364176784221743, 15625263495733021897191462443560828458083733841982069207
76444667133063669)

Den offentlige nøgle har formen ${\tt PublicKey(N, e)}$ . Den private nøgle har formen ${\tt PrivateKey(N, e, d, p, q)}$ . Vi kan underskrive et dokument via den kryptografiske hash funktion SHA-256 og verificere den digitale signatur efterfølgende:

>>> transaktion = 'Overfør 1 bitcoin til Niels'
>>> signature = rsa.sign(transaktion, priv, 'SHA-256')
>>> rsa.verify(transaktion, signature, pub)
True
>>> transaktion = 'Overfør 2 bitcoins til Niels'
>>> rsa.verify(transaktion, signature, pub)
Traceback (most recent call last):
  File "", line 1, in 
  File "/usr/local/lib/python2.7/dist-packages/rsa/pkcs1.py", line 315, in verify
    raise VerificationError('Verification failed')
rsa.pkcs1.VerificationError: Verification failed

1.9 Det diskrete logaritmeproblem

Meget overordnet er det diskrete logaritme problem mht en given abelsk gruppe $G$ at løse ligningen

$g^n = a \tag{1.6}$ med $n\in \mathbb{N}$ for givne $g, a\in G$ . Hvis gruppen $G$ er de positive reelle tal med multiplikation, så kan (1.6) løses som

$n = \frac{\log(a)}{\log(g)}.$

Hvis $G$ er en endelig abelsk gruppe er der oftest ingen analog til den klassiske logaritme og løsningen af (1.6) anses for at være svær specielt for den multiplikative gruppe

$\left(\mathbb{Z}/p\mathbb{Z}\right)^* = \mathbb{Z}/p\mathbb{Z} \setminus \{0\},$ hvor $p$ er et stort primtal og som i bitcoins tilfælde for gruppen af punkter

$E(\mathbb{Z}/p\mathbb{Z})$ over $\mathbb{Z}/p\mathbb{Z}$ for en nøjere valgt elliptisk kurver $E$ . For en endelig abelsk gruppe $G$ kaldes (1.6) det diskrete logaritmeproblem i $G$ .

I ovenstående formulering er den diskrete logaritme strengt taget ikke veldefineret, når gruppen $G$ er endelig. Med $m = |G|$ har vi nemlig $g^m = 1$ og dermed

$g^n = g^{n + m} = g^{n + 2 m} = \cdots = a.$ Den diskrete logaritme er det mindste $n$ , som opfylder (1.6). Dette mindste $n$ betegnes $\log_g(a)$ .

Lad os helt konkret kigge på gruppen $G = \mathbb{Z}/p \mathbb{Z}\setminus\{0\}$ , hvor $p$ er primtallet $56509$ . Her er $G$ en gruppe mht multiplikation af restklasser og den er cyklisk med frembringer $g = 2$ . Hvad er

$\log_2(38679)?$

I princippet er der ikke andre metoder end at prøve sig frem med $2, 3, 4, \ldots$ . Det glædede mig at opdage at problemet kan løses i WolframAlpha som

${\tt MultiplicativeOrder[2, 56509, {38679}]}$ Prøv selv i WolframAlpha.

Hvad giver

${\tt MultiplicativeOrder[2, 56509]}$ som resultat?

Grunder til at det diskrete logaritmeproblem er svært at løse kan man måske ane ved at kigge på potenser af $g$ i gruppen $\mathbb{Z}/p\mathbb{Z}\setminus\{0\}$ for et mindre primtal $p$ . Nedenfor et snapshot taget fra bogen An Introduction to Mathematical Cryptography, Hoffstein et al.

Ren Kaos! Dog er den såkaldte Shanks baby-step giant-step algoritme en hurtigere metode til at finde den diskrete logaritme gennegået i videoen nedenfor.

Kommentarer/spørgsmål?

Lad os se hvordan det diskrete logaritmeproblem kan bruges i kryptografi.

1.9.1 Elgamal kryptering

El Gamal krypteringssystemet blev indført af Taher Elgamal i 1985. Det bygger på det diskrete logaritmeproblem.

En bruger Bob vælger en hemmelig nøgle, som er et stort naturligt tal $a$ . Dernæst offentliggøres $(g, B)$ som den offentlige nøgle, hvor

$B = g^a.$ Kryptosystemet bygger på at det er svært at finde $a$ ud fra $B$ i.e., det diskrete logaritmeproblem er svært i gruppen $G$ .

Alice sender en meddelelse $m\in G$ til Bob ved først at generere et tilfældigt tal $k$ (det er her yderst vigtigt at de genererede tal er naturligt tilfældige) og sender så parret

$(g^k, m B^k)$ til Bob, som kan dekryptere det modtagne par $(S, T)$ og finde den sendte meddelelse som

$T S^{-a} = m g^{a k} g^{-a k} = m.$

Opgave

Lad $G = \mathbb{Z}/p\mathbb{Z}\setminus \{0\}$ , hvor $p = 467$ og $g=2$ . Hvis den hemmelige nøgle er $a = 153$ , hvad er da

den offentlige nøgle?
indkodningen af meddelelsen $331$ hvis det tilfældige tal er $k = 197$ ?

Check også at dekrypteringen af den krypterede meddelelse ovenfor giver det rigtige.

1.9.2 Elgamal digital signatur

Digital signatur mht det diskrete logaritmeproblem er en anelse mere kompliceret end for RSA. Udgangspunktet er stadig en hemmelig nøgle $a$ og en offentlig nøgle $B = g^a$ . Vi vil her tage udgangspunkt i gruppen

$G = \mathbb{Z}/p\mathbb{Z}\setminus\{0\}.$ Hvis $G$ er punkter på en elliptisk kurve modulo $p$ som i bitcoins signeringsalgoritme er algoritmen en anelse mere kompliceret. De fleste moderne browsere har ECDSA indbygget.

For flere detaljer omkring elliptisk kurve kryptografi er her et link til Cloudfares blog.

Hvad vil det sige at underskrive en meddelelse $D$ med en digital signatur, som kommer fra den hemmelige nøgle $a$ ?

Her er meddelelsen et tal $D$ , som opfylder $1 < D < p$ . Bob underskriver meddelelsen $D$ med sin hemmelige nøgle som

$(g^k, (D - a g^k) k^{-1}),$ hvor $k$ igen er et kryptografisk sikkert tilfældigt tal. Den digitale signatur $(S_1, S_2)$ kan nu verificeres gennem identiteten

$B^{S_1} S_1^{S_2} = g^{a S_1} g^{k (D - a S_1) k^{-1}} = g^D,$ hvor $B = g^a$ er Bobs offentlige nøgle.

Opgave

Lad $p = 21739$ , $g = 7$ og $a = 15140$ . Udregn først den offentlige nøgle $B$ hørende til disse oplysninger. Underskriv dernæest meddelelsen $D = 5331$ ud fra det tilfældige tal $k = 10727$ .

Verificer til sidst at den digitale signatur er korrekt.