Elliptic Curve Digital Signature Algorithm használata a Bitcoin világában Dunai Alexandra Matematika BSc
Szakdolgozat
Témavezet® Villányi Viktória Adjunktus Operációkutatási Tanszék
Eötvös Loránd Tudományegyetem Természettudományi Kar Budapest, 2017
Köszönetnyilvánítás Ezúton szeretnék köszönetet mondani témavezet®mnek, Villányi Viktóriának, a sok segítségért és türelemért, illetve a sok konzultációért, a témáért és a hasznos tanácsokért. Hálával tartozom még családomnak, akik egyetemi éveim alatt mindvégig mellettem álltak.
Tartalomjegyzék 1. Bevezetés
2
2. Bitcoin
3
2.1.
Mértékegysége
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.2.
Bányászata
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.3.
Wallet (Pénztárca) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.4.
Bitcoin gazdasága
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.5.
Bitcoin biztonsága
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
2.6.
Bitcoin el®nyei és hátrányai
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3. Blokkok és blokkláncok 3.1.
Blokkok struktúrája
3.2.
A blokk fejléce
5
6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
3.3.
Tranzakciók . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
3.4.
A blokkok beazonosítása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
4. Elliptikus görbék és az ECC 4.1.
4.2.
10
M¶veletek geometriai és algebrai megközelítése
. . . . . . . . . . . . . . . . . . . . .
12
4.1.1.
Ellentett . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.1.2.
Két különböz® pont összeadása . . . . . . . . . . . . . . . . . . . . . . . . . .
12
4.1.3.
Egy pont kétszerese
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
Elliptikus görbék véges test felett . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.2.1.
14
Diszkrét logaritmus
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. A digitális aláírás
15
5.1.
A digitális aláírás felépítése
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
5.2.
Az Elgamal Digitális aláírás algoritmusa . . . . . . . . . . . . . . . . . . . . . . . . .
16
5.2.1.
A kulcs generálása
16
5.2.2.
Az aláírás és a veri káció
5.2.3.
Egy példa egyszer¶ számokkal . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
5.2.4.
A rövid életciklusú kulcs többszöri használata . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
III
16
TARTALOMJEGYZÉK
5.3.
1
Digitális Aláírás séma (DSA)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
18
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
5.3.1.
A kulcs generálása
5.3.2.
Az aláírás és a veri káció
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19
5.3.3.
Egy példa egyszer¶ számokkal . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
6. Az elliptikus görbéken alapuló digitális aláírási algoritmus és használata a bitcoin világában 22 6.1.
6.2.
Az Elliptic Curve Digital Signature Algorithm . . . . . . . . . . . . . . . . . . . . . .
22
6.1.1.
Kulcsgenerálás
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
6.1.2.
Az aláírás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.1.3.
A veri káció
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
6.1.4.
Egy példa egyszer¶ számokkal . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
Az ECDSA és a bitcoin találkozása . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
6.2.1.
26
A DSA és ECDSA elleni támadások
7. Összefoglalás Irodalomjegyzék
. . . . . . . . . . . . . . . . . . . . . . .
28 28
1. fejezet
Bevezetés A digitális zet®eszköz, egy olyan internet alapú zet®eszköz, amely hasonló tulajdonságokkal rendelkezik mint a zikai zet®eszközök, például a papír valuta vagy érme, viszont azonnali tranzakciós és limit nélküli átruházási lehet®séget biztosít. A kriptovaluta egy olyan valuta fajta amely kriptográ át használ a tranzakciók biztosítására és az új valuta egységek létrehozására.
2
2. fejezet
Bitcoin A Bitcoin lényegében egy, most már nyílt forráskódú digitális zet®eszköz. Ez az els® olyan decentralizált peer-to-peer rendszer amely m¶ködését nem felügyeli semmilyen pénzügyi szervezet. A Bitcoin az els® implementációja Wei Dei kriptovaluta ötletének, amelynek lényege, hogy a kriptográ a irányítsa a létrehozását és tranzakcióit egy központi felügyelet helyett.
Feltalálója
egy ismeretlen programozó vagy programozói csoport akik Satoshi Nakamoto név alatt futnak. A Bitcoint
2008.
2009-ben
október
30-án mutatták be el®ször egy zárt kriptográ ai email listának, viszont csak
lett nyílt forráskódú rendszer.
A rendszer lényege, hogy a Bitcoin hálózat egy nyilvános lajstromot oszt meg, amelyet blokk láncnak hívnak. Ez tartalmazza az összes valaha végbement tranzakciót úgy, hogy a felhasználók számítógépeit használja fel a tranzakciók validációjához.
2.1. Mértékegysége A bitcoin rendszer mértékegysége a bitcoin, jelei: BTC, XBT vagy Kicsi bitcoin bet¶. Milibitcoin (mBTC), microbitcon (µBTC) illetve satoshi ami a legkisebb mértékegysége ennek a pénznemnek :
0.00000001
bitcoin.
2.2. Bányászata A bitcoin bányászat alapja, a számítási kapacitás felhasználása a bitcoin tranzakciók feldolgozására. A bányászok a bitcoinban használt Block chain konzisztenciájáról és teljességér®l gondoskodnak. A bitcoin bányászathoz egy softwaret kell futtatni specializált hardwaren. A bányászatra használt számítógépeknek nagyon er®s videokártyával kell rendelkezniük, legalább
1000
watt teljesítmény¶
táppal, illetve olyan alaplappal, amelynek legalább három videokártya foglalata van. A program várja a beérkez® tranzakciókat a peer-to-peer hálózaton keresztül, és megcsinálja az elvárt mate-
1
matikai feladatokat (Hash-cash proof-of-work feladatokat ), hogy feldolgozza és meger®sítse ezeket
1 https://en.bitcoin.it/wiki/Hashcash
3
2. FEJEZET. BITCOIN
a megkapott tranzakciókat.
4
Ezen feladatok elvégzéséért a bányászok pénzt kapnak, amelyeket a
felhasználó zet a tranzakciók gyorsabb feldolgozásáért. Ahhoz, hogy az új tranzakció biztosítva legyen, egy blokkban kell legyenek a matematikai proof-of-work-kel. Ezek a proof-ok nagyon nehezen generálhatóak, mert kézzel megoldhatatlanok, mivel több milliárd kalkuláció elvégzése szükséges hozzá másodpercenként. A bányászok ezeket a számításokat elvégzik, miel®tt a blokkjaikat elfogadja a hálózat és miel®tt bármilyen zetést kapnának érte. Minél több bányász lesz a hálózatban, automatikusan állítódik a feladatok nehézsége a hálózat által, azért hogy egy blokk megszerzési ideje átlagosan
10
len®rizhet®ek.
A proof-of-work rendszer úgy lett megtervezve, hogy kötelezze a blokkokat hogy
perc maradjon. Ezek a feladatok, habár nehezen megoldhatóak, könnyen leel-
kronológikus sorrendben álljanak a blokk listában. Ez az oka annak, hogy szinte lehetetlen visszafordítani egy már megtörtént tranzakciót, mivel ez az összes, a módosítást követ® blokkokban lev® proof-of-work újrakiszámítását követeli meg.
2.3. Wallet (Pénztárca) A bitcoin wallet, vagy magyarul pénztárca a tranzakciókhoz szükséges információkat tartalmazza. Neve megtéveszt®, mert nem a tényleges bitcoinokat tárolja - azok a blokk láncban lev® tranzakciós lajstromból nem elválaszthatóak - hanem inkább egy digitális személyi igazolványként funkcionál. A bitcoin egy nyílt kulcsú titkosítást használ, amelyben két titkosítási kulcs van, egy titkos és egy nyílt kulcs. Ezeket mind a bitcoin pénztárcánk tárolja. Többfajta pénztárca létezik. Sotfware wallets amelyek hozzákapcsolódnak a hálózathoz ahol megengedik bitcoinjaink elköltését, és tartalmazzák a digitális adatainkat amelyek ezen tranzakciók létrejöttéhez szükségek.
2.4. Bitcoin gazdasága Pénzt a bitcoin bányászok a tranzakciók feldolgozásáért szerezhetnek, illetve a hálózat biztonságossá tételéért speciális hardware használatával. A Bitcoin protocol úgy lett megtervezve, hogy egy új bitcoint a hálózat csak x id®közönként tudjon létrehozni. Ett®l válik ez egy nagyon versenyszer¶ üzletté, mivel minél több bányász van a hálózatban, annál nehezebb új bitcoint szerezni, azaz sokkal kevesebb lesz az egy f®re jutó haszon. Az új bitcoinok létrehozása egy csökken® és el®relátható ráta szerint történik. amíg pontosan
A létrehozható bitcoinok száma minden évben megfelez®dik, addig a pillanatig
21
millió bitcoin lesz a piacon.
A bitcoinnak meg van minden tulajdonsága, amely ®t egy pénznemé teszi, viszont inkább matematikai alapokon nyugszik, mint természeti alapokon, mint például az arany és az ezüst.
A
bitcoinok árát, mint minden más piacon, a kereslet és a kínálat határozza meg. Amikor a bitcoinok iránti kereslet megn®, akkor az áruk megemelkedik, amikor a kereslet csökken, akkor az áruk is.
2. FEJEZET. BITCOIN
5
2.5. Bitcoin biztonsága A Bitcoin által használt protocol és kriptográ a nagyon megbízható. A legnagyobb kockázatot a felhasználói hiba okozza. A bitcoin pénztárcákat tároló leok amelyek a szükséges privát kulcsot tartalmazzák könnyen kitörölhet®ek, elveszíthet®ek illetve ellophatóak.
2.6. Bitcoin el®nyei és hátrányai A bitcoinnak nagyon sok el®nye van. Az év akármelyik napján lehet bitcoint küldeni és fogadni a világ bármelyik pontján. A tulajdonosnak teljes irányítása van a pénze felett, nincsen sem banki, sem bármilyen bürokráciai szerv, amely a pénzét felügyeli.
Ezen kívül a bitcoin fogadásnál nin-
csen semmiféle díj, ilyen díjakat csak akkor kell zetni, ha gyorsabban szeretnénk meger®sítést a tranzakció végbemenésér®l. Ahogy el®nye, úgy hátránya is van a Bitcoinnak. Nagyon sok ember még nem is tud a Bitcoin létezésér®l, és sok helyen nem fogadják el ezt a fajta zetési módot.
Egy másik nagy hátránya,
hogy a bitcoin még fejl®dés alatt áll, azaz nagyon sok új alkalmazást és szolgáltatást még csak most fejlesztenek ki.
3. fejezet
Blokkok és blokkláncok A blocklánc adat struktúra egy olyan rendezett lista, amelyben a tranzakció blokkok visszafele vannak linkelve.
Ezek az adatok egy fájl-ban vagy akár adatbázisban is tárolhatóak.
Például a
Bitcoin Core kliens a Google LevelDB adatbázisát használja a blockchainek meta-adatjai tárolására. Minden block visszafele van linkelve, azaz a láncban a közvetlenül el®tte létrejött blockra mutat, amelyet szül® vagy parent blokknak hívnak. Ezek az adatok a blokkok fejlécében kerülnek tárolásra.
Ha szeretnénk megváltoztatni a listában egy el®z® elemet, emiatt a linkelés miatt, az
összes többi utána lev® blokk is megváltozik. Ez hatalmas számítási kapacitást igényel minél régebbi blokkot szeretnénk megváltoztatni, amely nagyon fontos biztonsági szempont. Ha vizualizálni szeretnénk ezeket a blokkokat, akkor függ®leges, egység méret¶ kockákat képzelhetnénk el, amelyben minden kocka egy blokk. Ekkor értelmezhet®vé válik a lista magassága amely az legels® létrejött blokk és az aktuális blokk távolsága. A blokkok beazonosítása egy SHA256 hash-el történik, amely a blokk fejlécében található.
3.1. Blokkok struktúrája A bitcoinban használt blokkok egy fejléccel kezd®dnek, melyet egy tranzakciós lista követ. Minden blokk tartalmazza az el®tte végbement tranzakciók listáját.
Egy nehezen megoldható számtani
feladat is van benne, amely minden blokkban különbözik és új blokk nem vihet® fel a listába a megfelel® válasz nélkül.
Jelen pillanatban
433615
blokk van a rendszerben, és nincs megkötés a
maximális blokkok számáról, még ha az összes bitcoin létre is jönne, a tranzakciók miatt a blokkok száma egészen addig n®ni fog, amíg bitcoinnal kereskedik valaki.
3.2. A blokk fejléce A fejléc mindig
80 byte hosszú, amely három f® metadata halmazból áll.
Az els® rész tartalmazza a
szül® blokkra mutató értéket, amely biztosítja, hogy ® a soron következ® blokk a listában. A második rész olyan adatokat tartalmaz, amely leginkább a bányászati versenyben fontosak.
6
A harmadik
3. FEJEZET. BLOKKOK ÉS BLOKKLÁNCOK
7
halmaz a merkle gyökér, amely egy olyan adat struktúra, amely a blokkban tárolt tranzakciókat tartalmazza. Ezekb®l az információkból a következ®képpen épül fel maga a fejléc:
•
A blokk verzió száma, amely megmutatja hogy melyik validációs szabályokat kell használni, ez összesen
•
4
byte hosszú.
Az el®z® blokk fejlécének hash-e, amely azért fontos, hogy ne lehessen visszamen®leg változtatni a blokkokon. Ha a lista valamely korábbi elemét szeretnék változtatni, akkor emiatt a
32
byte-os tárolt hash függvény miatt az összes utána következ® blokkot is meg kell változ-
tatni, ezzel kizárva a visszaéléseket.
•
A Merkle gyökér hash-t, amely szintén
32
byte-nyi helyet foglal el.
Ez az összes blokkban
lev® tranzakciók hash-éb®l számolódik ki, így biztosítva azt, hogy ne lehessen a tartalmat úgy megváltoztatni, hogy ne változzon meg a hash kód a fejlécben.
•
Unix Epoch id® (4 byte), amely megadja hogy a bányász mikor kezdte el hash-elni a fejlécet. Ennek nagyobbnak kell lennie, mint az el®z®
11
blokk mediánja.
•
nBits(4 byte) , az az enkódolt szám, amelynél a hash nagyobb vagy egyenl®nek kell legyen.
•
nonce (4 byte), egy tetsz®leges szám, amelyet a bányászok változtatnak meg a fejléc hashében, hogy az nBits dekódolt számánál kisebb legyen.
A blokk legnagyobb része a tranzakciós lista, általában tranzakciót tárol. Egy teljes blokk
1000-szer
250
byte nagyságú, és több mint
500
nagyobb, mint maga a blokk fejléce.
3.3. Tranzakciók Egy tranzakció alatt egy Bitcoin mennyiség átvitelét értjük, ami ki van közvetítve a hálózatba, amelyet utána blokkokba foglalnak.
Egy tranzakció tipikusan az el®z® tranzakciós kimeneteket
összef¶zi az új tranzakciós bemenetekkel, és minden bemen® Bitcoin értéket dedikálja az új kimenetekhez. Ezek a tranzakciók nem titkosítottak, tehát egészen az els® tranzakciókig végig nézhet®k egy hex editor segítségével.
A tranzakciók a következ® struktúrát követik:
•
Version no. (4 byte) Ez a verziószám.
•
In-counter
•
List-of-inputs a bemenetek összessége
•
Out-counter
•
List-of-outputs A kimenetek összessége
•
Lock time
1-9
4
byte - a bemenetek száma
1-9
byte a kimenetek száma
byte Azt az id®pontot jelöli amikor a tranzakció véglegessé válik.
3. FEJEZET. BLOKKOK ÉS BLOKKLÁNCOK
8
A következ® példában láthatjuk, hogy hogy is néz ki egy bitcoin tranzakció:
1 Az input ebben a tranzakcióban ezt az
50
50
BTCt importál az fd58ee tranzakcióból. Az output ezután,
BTC-t egy adott Bitcoin címre fogja áthelyezni.
Mint láthatjuk, a tranzakció két f® részböl áll: Az Egy tranzakció több inputot is tartalmazhat. tranzakció outputja fogja ®ket felhasználni.
Input az el®z® tranzakcióhoz egy referencia.
Ilyenkor az input értékek összeadódnak, és az új
A previoustx a el®z® tranzakció hash-e.
Az Index
a hivatkozott tranzakció egy bizonyos outputja. A scriptSig a script els® része, ami összesen két részb®l áll: az aláírásból és a publikus kulcsból. A publikus kulcsnak meg kell egyeznie az outputban lev® script hashe-vel. A publikus kulcs az aláírás veri kációjához szükséges. A második része az ECDSA aláírás hash értéke. Ez, a publikus kulccsal együtt bebizonyítja, hogy a kérdéses Bitcoin cím tulajdonosa hozta létre a tranzakciót. Az információkat tartalmazza.
Output lényegében a bitcoin küldéséhez szükséges
A Value az átküldött pénz értékét jelenti.
A ScriptPubkey a script
második része.
3.4. A blokkok beazonosítása A blokk els®dleges azonosítója a blokk hash, ami egy kriptográ a hash, amelyet a blokk fejlécéb®l kapunk, miután kétszer lefutattuk rajta az SHA256 algoritmust.
A blokk hash ténylegesen nem
tartozik a blokk adat struktúrájába, tehát nincsen elküldve a hálózaton, illetve nincs eltárolva a blokk lánc más részén sem. A blokk hash minden csomóponton ki van számítva, viszont eltárolható bizonyos adatbázisokban, mert ez megkönnyíti az indexelést, ezzel könnyebbé és gyorsabbá teszi a blokk el®keresését az adattároló lemezr®l. A blokk beazonosításának egy másik módja a blokk magassága.
Ez azt jelzi, hogy az adott
blokk éppen melyik eleme a láncnak. A láncolt lista els® elemének, a genesis blokknak a magassága
0.
A blokk lánc, amely
2009-ben
került megalkotásra,
2014-re
már
278000
blokk magassággal
rendelkezett. A genesis blokk egy reprezentációja:
2
GetHash() = 0x000000000019d6689c085ae165831e934763ae46a2a6c172b3f1b60a8ce26f hashMerkleRoot = 0x4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b txNew.vin[0].scriptSig = 486604799 4 0x736B6E616220726F662074756F6C69616220646E6F636 57320666F206B6E697262206E6F20726F6C6C65636E61684320393030322F6E614A2F33302073656D 695420656854
txNew.vout[0].nValue
= 5000000000
1 https://en.bitcoin.it/wiki/Transaction 2 https://en.bitcoin.it/wiki/Genesis_block
3. FEJEZET. BLOKKOK ÉS BLOKKLÁNCOK
9
txNew.vout[0].scriptPubKey = 0x5F1DF16B2B704C8A578D0BBAF74D385CDE12C11EE5045 5F3C438EF4C3FBCF649B6DE611FEAE06279A60939E028A8D65C10B73071A6F1671927485 5FEB0FD8A6704 OP_CHECKSIG
block.nVersion = 1 block.nTime = 1231006505 block.nBits = 0x1d00 block.nNonce = 2083236893 CBlock (hash=000000000019d6, ver=1, hashPrevBlock=00000000000000, hashMerkleRoot=4a5e1e, nTime=1231006505, nBits=1d00, nNonce=2083236893, vtx=1)
CTransaction(hash=4a5e1e, ver=1, vin.size=1, vout.size=1, nLockTime=0) CTxIn(COutPoint(000000, -1), coinbase 04001d0104455468652054696d65732030332f4a616e2f323030392043686 16e63656c6c6f72206f6e206272696e6b206f66207365636f6e64206261696c6f757420666f7 22062616e6b73)
CTxOut(nValue=50.00000000, scriptPubKey=0x5F1DF16B2B704C8A578D0B) vMerkleTree: 4a5e1e
4. fejezet
Elliptikus görbék és az ECC Ahhoz, hogy megértsük az Elliptic Curve Digital Signature Algoritmust (ECDSA) elengedhetetlen hogy megismerkedjünk az elliptikus görbe fogalmával. Az ECC (angolul Elliptic Curve Cryptosystem) egy nyilvános kulcsú kriptográ ai rendszer, amelyet manapság egyre gyakrabban használnak egyre több helyen. Az elliptikus görbéket csak kb gálni.
15
éve kezdték el kriptográ ai szempontból vizs-
Ez az elliptikus görbéken alapuló rendszer a gyors m¶ködésének, kis tárigényének, kisebb
tanúsítvány méretének és kisebb kulcsméretének köszönheti népszer¶ségét. ECC modulus
AES
RSA modulus
RSA:ECC
112
56
512
5:1
161
80
1024
6:1
256
128
3072
12 : 1
384
192
7680
20 : 1
512
256
15630
30 : 1
1 látható a két legismertebb nyílt kulcsú titkosítási algoritmus, illetve az ECC.
A táblázatban
Közelebbi vizsgálat során észrevehet®, hogy az ECC kulcsmérete, amely ugyanakkora biztonságot nyújt, mint a másik két algoritmus, lényegesen kisebb, mint a többi.
17.
Az elliptikus görbékre a
század végén gyeltek fel a tudósok, amikor olyan zikai problémát szerettek volna megolda-
ni/modellezni, amelyek komoly geometriai tudást igényeltek.
4.0.1. De níció.
Legyen
K
egy olyan test, melynek a karakterisztikája nem kett®, és nem három,
és legyen
y 2 = x3 + ax + b olyan harmadfokú polinom, melynek nincsenek többszörös gyökei. görbe egy olyan
1 Virasztó,
P (x, y)
Tamás:
pontok halmaza ahol
x, y ∈ K
K
test feletti elliptikus
koordináták kielégítik az el®bbi egyenletet,
Titkosítás és adatrejtés, NetAcademia Kft., 2004
10
Egy
4. FEJEZET. ELLIPTIKUS GÖRBÉK ÉS AZ ECC
11
Y 2 = X 3 +X+1
10 8
8
6
6
4
4
2
2
0
0
-2
-2
-4
-4
-6
-6
-8 -10 -10
-8
-8
-6
-4
-2
0
2
4
4.1. ábra. Elliptikus görbe
6
8
-10 -10
10
D = −496
-8
-6
-4
-2
0
2
4
4.2. ábra. Elliptikus görbe
Y2 = X3
10
8
6
6
4
4
2
2
0
0
-2
-2
-4
-4
-6
-6
6
8
10
D = 208
Y 2 = X 3 -3X+2
10
8
-8
-8 -10 -10
Y 2 = X 3 -10*X+1
10
-8
-6
-4
-2
0
2
4.3. ábra. Elliptikus görbe
4
6
D=0
8
10
és
a=0
és a görbéhez hozzá tartozik egy úgynevezett
-10 -10
-8
-6
-4
-2
0
2
4.4. ábra. Elliptikus görbe
O-val
4
6
D=0
jelölt "végtelen távoli pont".
8
10
és
a 6= 0
Az elliptikus
2 görbék ezen formáját Weierstrass formulának hívják.
4.0.2. De níció.
Az fenti elliptikus görbe diszkriminánsán a
D = −16(4a3 +27b2 ) kifejezést értjük.
Az egyszer¶ség és ábrázolhatóság kedvéért, tegyük fel hogy K valós számtest. A diszkrimináns értéke az alábbi módon változtatja a görbe alakját:
• D 6= 0
akkor az elliptikus görbe nem szinguláris. Ilyenkor lehet
• D=0
és
a=0
a szinguláris pontban egy érint® van, a görbe csúcsként végz®dik.
• D=0
és
a 6= 0
egy szinguláris pont van, más néven csomópont, amelybe 2 különböz® érint®t
D<0
illetve
D > 0.
lehet húzni, és a görbe elmetszi saját magát. Kriptográ ai szempontból csak és kizárólag olyan görbékkel foglalkozunk melyek nem rendelkeznek szingularitással, azaz
2 Liptai,
Kálmán:
D 6= 0.
Kriptográ a, Eszterházi Károly F®iskola, 2011
4. FEJEZET. ELLIPTIKUS GÖRBÉK ÉS AZ ECC
12
4.1. M¶veletek geometriai és algebrai megközelítése
4.1.1. Ellentett P (x, y)
Egy
pont ellentettje az az
R
pont, amely a
P (x, y)
pont
x
tengelyre tükrözött képe, ami
szintén rajta van a görbén. Algebrailag kifejezve :
xR = xP
és
yR = −yP .
4.1.2. Két különböz® pont összeadása Legyen
P
és
Q
két különböz® pont a görbén, és
R = P + Q.
A két pont összeadásának geometriai
módja a következ®:
•
Kössük össze egy egyenessel a
•
hosszabbítsuk meg ezt az egyenest, amíg nem metszi a görbét egy harmadik ponton. Ezt a pontot nevezzük el
•
Tükrözzük amely
P
és
R0 -t Q
P
és
Q
pontokat.
R0 -nek.
az x tengelyre. Ez a pont is rajta lesz az elliptikus görbénken. Ez lesz
R,
pontok összege.
Az összeget az alábbi módon írhatjuk fel:
Legyen
P = (xP , yP )
és
Q = (xQ , yQ ).
Ekkor
R
a
következ® módon áll el®:
s = (yP − yQ )/(xP − xQ ) xR = s2 − xP − xQ
és
yR = s · xP − s · xQ − yP
4.1.3. Egy pont kétszerese Legyen a pontunk
P.
A
2P
meghatározása hasonló módon történik mint a két különböz® pont
összeadása, annyi különbséggel, hogy nem két pontot kötünk össze, hanem a
P
pont érint®jét
húzzuk be. Ez az érint® metszeni fogja valahol a görbét, és ennek a metszéspontnak az tükrözött képe lesz a
2P
pont. Algebrai módon a következ®képpen írható fel:
xR = s2 − 2xP
. Megjegyzés.
4.1.1
mod p
és
Ha a kiválasztott pont az
yR = s(xP − xR ) − yP x-tengelyen
• 2E = O • 3E = E + 2E = E • 4E = E + 3E = E + E = O Tamás:
mod p.
helyezkedik el, akkor de níció szerint a
3 pont kétszerese a végtelenben van. Ennek jelölése: 0.
3 Virasztó,
x-tengelyre
Titkosítás és adatrejtés, NetAcademia Kft., 2004
4. FEJEZET. ELLIPTIKUS GÖRBÉK ÉS AZ ECC
13
4.2. Elliptikus görbék véges test felett Legyen
Fq
egy véges test. Ezentúl vizsgáljuk az E elliptikus görbéket ezen test felett. Láthatjuk,
hogy az ilyen elliptikus görbének maximum
2q + 1
pontja lehet:
pont. Továbbá tudjuk azt is, hogy minden lehetséges hat.
Fq
x
2q
darab
(x, y)
pont és a végtelen
értékhez maximum kett®
x
érték tartoz-
felett bizonyos algoritmusok segítenek megállapítani, hogy pontosan hány pontja van a
görbénknek, mint például a schoof algoritmus, illetve, Hasse tétele nagyon jó alsó, és fels® becslést ad rá.
4.2.1. Tétel. Legyen
N az Fq pontok száma az Fq véges test feletti E elliptikus görbén. Ekkor √ | (N − (q + 1)) |≤ 2 q . Innent®l a már megismert görbénkkel a
tika szabályai szerint:
Zq
y 2 ≡ x3 + ax + b(modp)
véges test felett fogunk számolni a moduláris aritmeahol
p
prím szám. A pontokra legyenek a következ®
feltételek érvényesek:
• 0≤x≤p−1
és
0≤y ≤p−1
• (4a3 + 27b2 ) 6= 0(modp) Az test közötti áttérés mellett nagyon fontos érvek szólnak.
A moduláris aritmetika csak egész
számokkal dolgozik, sokkal gyorsabb és pontosabb így a számítás mint a valós számok halmazával. A moduláris görbének véges számú pontja van, a pontok száma biztosan Vegyük a
p = 9, a = 1, b = 0
görbét. Ábrázoljuk az
xy
0
és
p−1
közé esik.
síkon:
Mint látjuk, nem kapunk ugyanolyan "folytonos" görbét mint amikor valós számok teste felett ábrázoltuk a görbénket. Az elliptikus görbe pontjainak halmaza a következ®:
(0, 0),(0, 3),(0, 6),(2, 1),(2, 8),(5, 2),(5, 7),(8, 4),(8, 5) A görbének
9
pontja van, ebb®l egy az origóban helyezkedik el. A pontok ránézésre véletlensze-
r¶en helyezkednek el a síkon, de ha közelebbr®l megnézzük, az
y = 4.5
egyenesre szimmetrikusak
4. FEJEZET. ELLIPTIKUS GÖRBÉK ÉS AZ ECC
(kivéve a
(0, 0)
pontot) és minden
. Megjegyzés.
4.2.2
x
értékhez
2
darab
14
y
érték tartozik.
Az olyan görbéket, amelyeknek a pontjainak száma megegyezik a modulusként
használt prím számmal (mint a példánkban) tilos használni kriptográ ai szempontból, mivel hatékonyan támadható.
. Megjegyzés.
4.2.3
csak mod
p-vel
A m¶veletek algebrai módon ugyanúgy végezhet®ek el, mint véges test felett,
számolunk.
4.2.1. Diszkrét logaritmus A nyilvános kulcsú kriptorendszerek alapja mindig egy olyan probléma, amelynél a megfejtéshez szükséges id® nagyon hosszú. Az elliptikus görbén alapuló kriptorendszereknek is egy ilyen probléma adja meg az alapját: A Elliptic Curve Discrete Logarithm Problem (ECDLP).
4.2.4. De níció. Ekkor az
E -n
Legyen
értelmezett
és keressük azt az
n
E
egy
Zp
véges test feletti elliptikus görbe és
diszkrét logaritmusos
R
egy pont a görbén.
problémáról beszélünk, ha adott egy
természetes számot, melyre
nR = Q
Q∈E
pont
egyenl®ség teljesül. Ebben az esetben
n
4 diszkrét logaritmusa Q-nak. Azon rendszerek, amelyek az ECDLP-n alapulnak, leginkább kulcscserél® vagy aláíró rendszerek, mert ez a módszer alkalmatlan a gyors titkosításra.
4 Liptai,
Kálmán:
Kriptográ a, Eszterházi Károly F®iskola, 2011
5. fejezet
A digitális aláírás A digitális aláírás feladata az aláíró személyazonosságának tanúsítása, és annak biztosítása, hogy az általa aláírt üzenetet nem változtatták meg az aláírás megtörténte után.
Míg egy hagyomá-
nyos aláírás kis gyakorlással másolható és máshova átvihet®, addig a digitális aláírást nem lehet áthelyezni másik dokumentumra. Ennek oka, hogy a digitális aláírás függ a dokumentum akkori tartalmától, amikor a feladó hitelesítette a dokumentumot aláírásával. Fontos különbség még, hogy a digitális aláírás nem zikailag, hanem logikailag kapcsolódik, az aláírt dokumentumhoz. Nagyon fontos kiemelni, hogy mivel a digitális aláírás a dokumentum egészéhez kapcsolódik, így ha azon változás megy végbe az aláírás után, az ellen®rzésnél rögtön kiderül, hogy hamisítva lett a dokumentumunk. A digitális aláírásunk akkor és csak akkor hamisítható, ha a titkos kulcsunkat a hamisító valamilyen módon megszerzi. A digitális aláírásoknak technológia függetlennek kell lennie, azaz akármilyen platformon kreáljuk meg az aláírást, azt bármilyen másik eszköz használatával le kell tudjuk ellen®rizni. Nagyon fontos hogy könnyen létrehozható és könnyen ellen®rizhet® legyen, viszont ne lehessen hamisítani, sem letagadni az aláírást. Az aláírásnak valamilyen módon hitelesítenie kell az aláíró személyét és a dokumentum tartalmát is. Ezen okok miatt lett nagyon elterjedt a digitális aláírás a hitelesítést igényl® informatikai területek világában.
5.1. A digitális aláírás felépítése A digitális aláírásnak két elengedhetetlen része van, az aláírás és az ellen®rzés. Az aláírás funkciója el®állítani az adott üzenethez tartozó aláírást, amely általában tartalmazza a dátumot, az aláírás id®pontját, és egyéb fontos, az aláíróra vonatkozó adatokat. Az ellen®rzés az üzenet és az aláírás kapcsolatát vizsgálja az aláíróra nézve. Ez az ellen®rzés általában logikai: igaz, ha az üzenet és az aláírás összetartozik, és hamis, ha nem. A digitális aláírás egyszer¶en összefoglalva a következ®képpen néz ki. Legyen m (message) az üzenet és s (signature) az aláírás. Ha az aláíró szeretné eljuttatni az
m
üzenetet az 's' aláírással a célszemélynek, akkor a követ-
kez®képpen jár el:
15
5. FEJEZET. A DIGITÁLIS ALÁÍRÁS
16
1. Az aláíró kiszámolja valamilyen módon az 's' értékét 2. Az 'm' és az 's' értékpárt továbbítja a célszemélynek. A két érték külön-külön nem hordoz értékes információt, csak ha a célszemélynek mindkét érték rendelkezésre áll.
A célszemély a következ®képpen tudja ellen®rizni az aláírás validitását: 1. A dokumentumot aláíró személyhez tartozó ellen®rz® függvénnyel megvizsgálja az 'm' és az 's' értékpárt. 2. Ha az ellen®rzés kimenete igaz, azaz az 's' és az 'm' összetartozik, akkor elfogadja az aláírást. A digitális aláírás nyílt kulcsos kriptorendszert használ, azaz az aláíró és az ellen®rz® algoritmusok nyilvánosak, az ellen®rzéshez publikus kulcs tartozik, az aláírónak pedig titkos kulcsa van. A következ® alfejezetekben megismerkedünk az Elgamal digitális aláírás sémával, a Digital Signature Algorithmmel (DSA), amely az Elgamal egy olyan továbbfejlesztése amely sokkal jobban elterjedt mint el®dje, illetve az Elliptic Curve Digital Signature Algorithmmel az utána lev® fejezetben, amely a DSA egy olyan verziója, amely elliptikus görbéken alapul. Ahhoz hogy megértsük hogyan m¶ködik az ECDSA, elengedhetetlen hogy megismerjük, hogy melyik algoritmusokból ered.
5.2. Az Elgamal Digitális aláírás algoritmusa Az Elgamal digitális aláírás sémának az alapja a diszkrét logaritmus problémán alapul.
5.2.1. A kulcs generálása Az Elgamal digitális aláírás kulcsgenerálása a következ® módon történik: 1. Válasszunk egy nagy 2. Válasszunk egy
p
α ∈ Z∗p
prím számot. számot.
3. Válasszunk egy random számot 4. Számítsuk ki
d ∈ 2, 3, ..., p − 2.
β = αp mod p.
Ekkor a publikus kulcsunk a
kpub = (p, α, β)
lesz, a titkos kulcsunk pedig
kpr = d
5.2.2. Az aláírás és a veri káció Az aláírás a következ® képpen néz ki:
sigkpr (m, kE ) = (r, s)
ahol az
m
az üzenetünk. Az
egész számokat a következ®képpen számítjuk ki: 1. Választunk egy random rövid életciklusú kulcsot (kE ), hogy
(kE , p − 1) = 1.
kE ∈ 0, 1, 2, ..., p − 2
és
r
és
s
5. FEJEZET. A DIGITÁLIS ALÁÍRÁS
17
2. Kiszámoljuk az aláírás paramétereit:
r ≡ αkE mod p, −1 s ≡ (m − d · r)kE mod p − 1 A veri káció a
verkpub (m(r, s))-el
történik, amely a publikus kulcsot, az aláírást és az üzenetet
használja a következ® módon: Legyen
t ≡ β r · rs mod p.
akkor az aláírás érvényes, tehát elfogadjuk, viszont ha
Abban az esetben, ha
t ≡ αm mod p,
t 6≡ αm mod p, akkor az aláírás érvénytelen,
tehát elutasítjuk. Tehát a fogadó akkor fogadja el az aláírást, ha a
Bizonyítás.
β r · rs ≡ αm mod p
feltétel teljesül.
A bizonyításban megmutatjuk, hogy a veri kációs folyamat hogyan jut el az igaz ágba,
hogy ha a veri kátor a megfelel® nyílt kulcsot és üzenetet használja a hozzá tartozó
r
és
s
paramé-
terekkel. Tudjuk, hogy
β = αd
r = αkE .
és
Ekkor
t ≡ β r · rs ≡ (αd )r (αkE )s
mod p ≡ αdr+kE s
mod p.
Ha az aláírásunk valid, akkor a következ®nek kell teljesülnie:
t ≡ αm ≡ αdr+kE s mod p. A kis-Fermat tétel alapján tudjuk hogy ez ekvivalens azzal, hogy ha a kitev®k egyenl®k modulo
p − 1-re m ≡ dr + kE s mod p − 1. Amelyb®l következik:
−1 s ≡ (x − d · r)kE mod p − 1.
5.2.3. Egy példa egyszer¶ számokkal Végezzük el a lépéseket a bemutatott Elgamal digitális aláírás sémánál! 1.
p = 41
2.
α=2
3.
d=7
4.
β = αd ≡ 5
Ekkor a publikus kulcsunk a következ® lesz:
(p, α, β) = (41, 2, 5).
5. FEJEZET. A DIGITÁLIS ALÁÍRÁS
Legyen az üzenetünk hogy
(40, 9) = 1.
m = 42,
és
kE = 9.
18
Ne felejtsük el, hogy ezeket a számokat ugy választjuk,
Ekkor
r = αkE ≡ 29 ≡ 20
mod 41,
s = (42 − 7 · 20) · 9 ≡ 38
mod 40.
A veri kációnál használt üzenet, aláírás és publikus kulcs :
(x(r, s)) = (42(20, 38))
A veri káció a
következ®képpen néz ki:
t = 520 · 2038 ≡ 4 mod 41, αm ≡ 224 ≡ 4 mod 41, t ≡ αm . Azaz az aláírás valid, elfogadjuk.
5.2.4. A rövid életciklusú kulcs többszöri használata A digitális aláírás biztonságossága nagyban függ a diszkrét logaritmus problémától. Ha a támadónk tud diszkrét logaritmusokat számolni, meg tudja szerezni a privát kulcsunkat és a rövid életciklusú kulcsunkat is. legalább
Egy nagyon fontos kikötése a kulcsoknak, hogy a prím szám, amit felhasználunk
1024; bit
hosszú legyenek.
Ha egy rövid életciklusú kulcsot többször használunk, akkor
a támadó nagyon könnyen ki tudja számítani a privát kulcsunkat. Tegyük fel, hogy két üzenetet küldünk
(x, (r, s))
alakban. Ha a két üzenet aláírásánál ugyanazt a
látszódni fog hogy a két
r
kE
kulcsot használjuk, akkor
érték megegyezik, mert ugyanaz a felépítésük:
r1 = r2 = αkE .
Ezután a
következ® két egyenletet fel tudjuk írni:
−1 s1 ≡ (m1 − d · r)kE
mod p − 1,
−1 s2 ≡ (m2 − d · r)kE
mod p − 1.
Ez egy két ismeretlenes egyenletrendszer, ahol az egyik ismeretlen a rövid életciklusú kulcs, a másik viszont a privát kulcsunk. Ha mindkét egyenletet megszorozzuk
kE -vel,
akkor egy könnyen
megoldható lineáris egyenletrendszerré válik:
−1 s1 − s2 ≡ (x1 − x2 ) · kE mod p − 1,
kE ≡
x1 −x2 s1 −s2
mod p − 1.
Ebb®l már behelyettesítéssel ki is számolható a kulcsunk.
5.3. Digitális Aláírás séma (DSA) Az Elgamal aláírási sémát alig használják a gyakorlatban, helyette inkább a sokkal népszer¶bb variánsát a Digital Signature Algorithm-t (DSA). A f® el®nyei közé tartozik, hogy az aláírás csak 320 bit hosszú, és azok a támadások amik hamisítani tudják az Elgamal sémával generált aláírást, azok itt hatástalanok.
5. FEJEZET. A DIGITÁLIS ALÁÍRÁS
19
5.3.1. A kulcs generálása Ahhoz hogy megértsük a DSA algoritmust, de niálnunk kell a ciklikus csoportokat.
5.3.1. De níció.
Egy
5.3.2. De níció.
Legyen
G
csoportot
ciklikusnak
nevezünk, ha egy alkalmas
g
elemének az egész
1 kitev®j¶ hatványaiból áll.
száma. A
g
G
csoport és
g ∈ G.
A
g
elem
rendje
g
különböz® hatványainak a
Z∗p
ciklikus csoport, amelynek
a
2 elem rendjének jele o(g).
A DSA alapja az, hogy van két ciklikus csoportunk. Az egyik a rendjének hossza
1024
bit hosszú. A másik csoport egy
160
bites alcsoportja
Z∗p
-nek. Ez egy sokkal
rövidebb aláírást eredményez mint a másik algoritmus. 1. Generáljunk egy 2. Keressünk
p
prímet, úgy hogy
p − 1-nek
3. Ha nincs megfelel® 4. Keressünk egy
5. Válasszunk egy 6. Számoljuk ki :
d
egy prím osztóját, legyen ez
q,
α-t,
21023 < p < 21024 q,
akkor generálunk egy másik
amelyre teljesül hogy
random egészet
β ≡ αd
mod
p
úgy hogy
2159 < q < 2160 .
prímet.
ord(α) = q
0
p.
Ekkor a kulcsaink a következ®ek:
kpub = (p, q, α, β), kpr = (d).
5.3.2. Az aláírás és a veri káció Úgyanúgy mint az Elgamal aláírás sémánál, a DSA aláírás és két egész számból áll; Mivel mindkét paraméter
160
bit hosszú, ezért az aláírás teljes hossza
320
r
és
s-b®l.
bit.
1. Válasszunk egy random egész számot, ez lesz a rövid életciklusú kulcs (kE ) és legyen
0 < kE < q . 2. Számítsuk ki az
r ≡ (αkE mod p) mod q .
3. Számítsuk ki az
−1 s ≡ (SHA(m) + d · r)kE mod q .
Egyb®l látszik, hogy ez az aláírási mód sokkal összetettebb mint az Elgamalban megismert aláírás. Az aláíráshoz szükséges az, hogy az m üzenetünket hasheljük az SHA családból származó hash függvénnyel.
1 Kiss 2 Kiss
Emil - Bevezetés az algebrába Emil - Bevezetés az algebrába
5. FEJEZET. A DIGITÁLIS ALÁÍRÁS
1. Számítsuk ki az 2. Számísuk ki az
w ≡ s−1 mod q
20
segédváltozót.
u1 ≡ w · SHA(x) mod q
3. Számítsuk ki az
u2 ≡ w · r mod q
segédváltozót.
segédváltozót.
v ≡ (αu1 · β u2 ) mod q .
4. Legyen
A veri káció a
verkpub (x, (r, s))
használatával a következ®képpen történik:
•
Ha
v ≡ r mod q ,
akkor az aláírás valid, és elfogadjuk.
•
Ha
v 6≡ r mod q ,
akkor az aláírás invalid, azaz elutasítjuk az aláírást.
Az aláírás valódiságának veri kációjának bizonyítása sokat segíthet abban hogy megértsük jobban ezen folyamat m¶ködését.
Bizonyítás. feltételt. Az
Ebben a bizonyításban, megmutatjuk, hogy az
s
Az egyenletet beszorozva
−1 kE -vel
s−1 -el,
és
mod q .
a következ® egyenletet kapjuk:
−1 kE ≡ s−1 SHA(x) + d · s−1 r Felhasználva az
u1 ≡ q · SHA(x) mod q
és az
Ekkor, ha modulo
p-vel
egyszer¶sítünk, és
−1
α kE
α-adik
segédváltozókat:
mod q .
hatványra emelünk:
mod p ≡ αu1 +du2
mod p.
α kE
mod p ≡ αu1 β u2
mod p.
mod p)
mod q ≡ (αu1 β u2
ezért:
−1
Ezt modulo
mod q .
u2 ≡ w · r mod q
−1 kE ≡ u1 + d · u2
β ≡ αd ,
aláírás kielégíti a
egyenletéb®l indulunk ki:
−1 s ≡ (SHA(x) + d · r)kE
Mivel
(r, s)
q -ra
egyszer¶sítve:
−1
(αkE
mod p)
mod q .
Tudjuk, hogy
−1
r ≡ (αkE 0
mod p)
mod q
és
v ≡ (αu1 · β u2 )
Ezt behelyettesítve kapjuk, hogy:
r≡v
mod q .
mod q .
v ≡ r mod q
5. FEJEZET. A DIGITÁLIS ALÁÍRÁS
21
5.3.3. Egy példa egyszer¶ számokkal Végezzük el a lépéseket a bemutatott DSA sémánál! 1.
p = 41
2.
q=5
3.
α=3
4.
d=4
5.
β = αd ≡ 40 mod 41
A publikus kulcsunk a következ® lesz:
(p, q, α, β) = (41, 5, 3, 40), és a titkos kulcsunk
kpr = (4). Legyen az üzenetünk hashelt értéke
SHA(m) = 22,
és
kE = 2.
Ekkor
r = αkE ≡ (32
mod 41)
s = (22 + 16) · 3
mod 5 ≡ 4 mod 5,
s≡4
mod 5.
w≡4
mod 5,
u1 ≡ 3
mod 5,
u2 ≡ 1
mod 5,
A veri káció a következ®képpen néz ki:
v ≡ (33 · 401
mod 41)
v≡r
mod 5,
4≡4
mod 5.
mod 5,
mod 5,
6. fejezet
Az elliptikus görbéken alapuló digitális aláírási algoritmus és használata a bitcoin világában Az el®z® fejezetben láthattuk, hogy az elliptikus görbék alapú kriptográ ai rendszereknek nagyon sok pozitívuma van a nem elliptikus görbéken alapuló rendszerekkel szemben, mint például az Elliptic Curve Cryptosystem elleni támadások hiánya. Mint láthattuk, az ECC ságban nyújt olyan biztonságot mint az RSA
1024-3072
160-256
bit hosszú-
biten. Ez ugye rövidebb számítási id®ket és
kisebb méreteket eredményez. Az ECDSA lépései nagyon hasonlóak az el®z®ekben megismert DSA algoritmusához, viszont az alapul szolgáló diszkrét logaritmus probléma egy elliptikus görbék csoportjára lett konstruálva. Ebb®l kifolyólag a számítás, amelyet az ECDSA aláíráshoz használunk, teljesen eltér a DSA során megismertekkel. Az ECDSA olyan elliptikus görbéket használ amelyek
Zp
prím test felett vannak, illetve Galois testek (2
m
) felett. Gyakorlatban inkább a
Zp
prím test
felett de niált görbéket használják.
6.1. Az Elliptic Curve Digital Signature Algorithm Most ismerkedjünk meg az Elliptic Curve Digital Signature Algorithmmel általánosan, majd a bitcoinban testre szabottan.
6.1.1. Kulcsgenerálás Az ECDSA digitális aláírás kulcsgenerálása a következ® módon történik: 1. Használjunk egy E elliptikus görbét amelynek modulusa
p,
együtthatói
pontja, amely olyan ciklikus csoportot generál, melynek rendje 2. Válasszunk egy
d
random egészet:
0 < d < q. 22
q.
a
és
b,
illetve
A
olyan
6. FEJEZET. AZ ECDSA ÉS HASZNÁLATA A BITCOIN VILÁGÁBAN
3. Számítsuk ki
23
B = d · A.
Ekkor a kulcsaink a következ®ek lesznek:
kpub = (p, a, b, q, A, B), kpr = (d).
6.1.2. Az aláírás Ugyanúgy mint a DSA, az ECDSA aláírása is az
m
(r, s)
egészekb®l áll. Az
r
és
s-et
felhasználva, az
üzenethez tartozó aláírást a következ® módon számolhatjuk ki. 1. Válasszunk egy
kE
egész számot, hogy
0 < kE < q ,
amely a random rövid életkciklusú
kulcsunk lesz. 2. Számítsuk ki 3. Legyen
R = kE · A
r = xR
4. Számítsuk ki az
−1 s ≡ (h(m) + d · r) · kE mod q .
A harmadik lépésben az
h(m)
R
x-koordinátája hozzá lett rendelve az
hash függvénnyel hashelve lett, hogy ki tudjuk
s-t
legalább olyan nagyságúnak kell lennie, mint a választott
r
változóhoz. Az
m
üzenet a
számolni. A lehashelt üzenet hosszának
q
szám.
6.1.3. A veri káció 1. Számítsuk ki a
w ≡ s−1 mod q
2. Számítsuk ki az
u1 ≡ w · h(m) mod q
3. Számítsuk ki az
u2 ≡ w · r mod q
4. Számítsuk ki 5. A
mP
el az
segédváltozót.
segédváltozót.
P = u1 A + u2 B .
verpub (x, (r, s)) Veri kációja a következ®képpen néz ki:
és elfogadjuk. Ha
Az
segádváltozót.
itt a
(r, s)
P
pont
xP 6≡ r
mod
q,
P
xP ≡ r mod q , az aláírás valid,
az aláírás invalid, azaz elutasítjuk.
x-koordinátájára vonatkozik.
aláírást, ha
Ha
Tehát, aki veri kálja, akkor és csak akkor fogadja
pont x koordinátája ugyanannyi maradékot ad
q -val
osztva, mint
r.
Ahhoz hogy jobban megértsük az algoritmus m¶ködését, nézzük meg a veri káció bizonyítását Ugyanúgy mint az el®z® két algoritmusnál, megmutatjuk, hogy veri kációs feltételt.
(r, s)
kielégíti az
r ≡ mP mod q
6. FEJEZET. AZ ECDSA ÉS HASZNÁLATA A BITCOIN VILÁGÁBAN
Bizonyítás.
Tudjuk, hogy:
− s ≡ (h(m) + d · r) · kE 1
s−1 -el
Átszorozva
24
és
kE -el,
mod q .
a következ®t kapjuk:
kE ≡ s−1 h(m) + d · s−1 · r
mod q .
Felhasználva, hogy
u1 ≡ w · h(m)
mod q
és
u2 ≡ q · r
mod q ≡ s−1 · r,
akkor kapjuk, hogy
kE ≡ u1 + d · u2 Mivel
Aq
mod q .
rend¶ ciklikus csoportot generál, ezért mindkét oldalt megszorozhatjuk
A-val:
kE · A ≡ (u1 + du2 )A. Tudjuk, hogy a csoport m¶velet asszociatív, ezért:
kE A ≡ u1 A + du2 A. A
B = dA
egyenl®séget felhasználva:
kE = u1 A + u2 B . Ez pontosan az a feltétel, amelyet leellen®rzünk a veri kációnál, azaz megnézzük, hogy a
u1 A + u2 B
és az
R = kE · A
maradékosan megegyeznek modulo
P =
q.
6.1.4. Egy példa egyszer¶ számokkal Végezzük el a lépéseket a bemutatott ECDSA sémánál! Legyen az E elliptikus görbénk a bitcoin rendszerében használt
y 2 = x3 + 7 .
1.
p = 11
2.
q = 11
3.
a=0
4.
b=7
5.
A = (3, 1)
6.
d=2
7.
B = d · A = (6, 2)
6. FEJEZET. AZ ECDSA ÉS HASZNÁLATA A BITCOIN VILÁGÁBAN
25
A publikus kulcsunk a következ® lesz:
(p, q, a, b, A, B) = (11, 11, 0, 7, (3, 1), (6, 2)), és a titkos kulcsunk
kpr = (2).
Legyen az üzenetünk hashelt értéke
SHA(m) = 22,
és
kE = 3.
Az aláírásunk a következ®képpen néz ki:
R = 3 · (3, 1) = (9, 3), r ≡ 9text, s ≡ (22 + 18) · 4 s≡6
mod 11text,
mod 11text.
A veri káció a következ®képpen néz ki:
w≡2
mod 11,
u1 2 · 22 ≡ 0
mod 11,
u2 ≡ 9 · 2 ≡ 7
mod 11,
P ≡ 0 + 7 · (6, 2) ≡ (42, 14) ≡ (9, 3)
mod 11,
P ≡r
mod 11,
9≡9
mod 11.
6.2. Az ECDSA és a bitcoin találkozása Egy adott protokoll, ahogy a bitcoin is, el®re meghatározza az elliptikus görbe és a véges test paramétereit. Ezek x értékek, melyet minden felhasználó használ. Ezekbe a paraméterekbe beletartoznak az elliptikus görbe egyenlete, a test prím modulusa, és az alappont, amit el®z®ekben
A-val
jelöltünk, ami a görbére esik. Az alappont rangja nincs el®re meghatározva, de a többi para-
méter egy függvénye. Minden ECDSA-t használó rendszer hatalmas paramétereket használ, ezen múlik a rendszer biztonságossága, mivel így nagyon nehéz ezeket feltörni. A bitcoin a következ® el®re megadott paraméterekkel dolgozik:
• p = 11579208923731619542357098500868790785326998466564056403945758400790883 4671663 = 2256 − 232 − 29 − 28 − 27 − 26 − 24 − 1, melynek hexadecimális értéke:
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF F F F F F F F EF F F F F C2F • a = 0, b = 7 • A = (2, 5506626302227734366957871889516853432625060345377759417550018736038911672 9240),
amely hexadecimális számrendszerben:
0279BE667EF 9DCBBAC55A06295CE870
B07029BF CDB2DCE28D959F 2815B16F 81798
.
6. FEJEZET. AZ ECDSA ÉS HASZNÁLATA A BITCOIN VILÁGÁBAN
26
• q = 115792089237316195423570985008687907852837564279074904382605163141518161494 337,
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
melynek hexadecimális értéke :
F EBAAEDCE6AF 48A03BBF D25E8CD0364141. A tranzakció aláírása az ECDSA-val egy nagyon komplikált folyamat, amely két részre bontható: az aláíratlan tranzakcióra és az aláírt tranzakcióra. A "nyers" tranzakció a már megismert inputokat tartalmazza (mint például az el®z® tranzakció hashet és indexét). Az aláírás folyamata az el®z®ekben megismert algoritmus alapján történik, a bemutatott paraméterekkel.
6.1. ábra. A digitális aláírás folyamata
1.
El®ször titkos és nyilvános kulcsot generálunk, majd az aláíratlan adatra kétszer lefuttatjuk a SHA256-os hash függvényt. Ezek után legeneráljuk az aláírást, a már kétszer hashelt tranzakcióra. A végleges scriptSig az aláírás hosszát, az aláírás egy byte hosszú típusát, és a titkos és publikus kulcsok hosszát fogja tartalmazni. A veri káció nagyon egyszer¶ az aláírás folyamatához képest, lényegében az ECDSA algoritmusnál megismert veri kációs folyamattal történik.
6.2.1. A DSA és ECDSA elleni támadások Minden rendszer igyekszik a legbiztonságosabb módszereket illetve algoritmusokat használni, hogy elkerülje az ®t érhet® támadásokat. Viszont nincs olyan rendszer amely támadhatatlan. Az ECDSAnál használt pont választásánál az
A
pont y koordinátáját nem használjuk fel. Ekkor létezik még
egy pont a görbén, amely ugyanazzal az tott pontunk.
−s mod q -t
Ha
kE -t
kicseréljük
használva akármelyik
x1
koordinátával rendelkezik, mint az eredetileg válasz-
−kE mod q (r, s)
len®rzéskor szintén valid aláírás lesz.
-ra, ugyanazt az
r
aláírás pár lecserélhet® egy
értéket fogjuk kapni.
(r, −s mod q)
Ekkor
amely az el-
Tehát így egy véletlenszer¶ rövid életciklusú kulccsal, két
különböz® dokumentumot írhatunk alá. Szintén biztonsági problémát jelenthet a DSA algoritmusnál a pseudorandom generátor, amellyel a
kE
értéket generáljuk. Ebben a sémában ez a
egy egyszer¶ 160 bites pseudorandom számnak a az ilyen módon generált
k
q
kE
érték
szerint vett modulusa. Meg gyelések alapján,
kétszer olyan valószín¶séggel esik a
[0, 2160 − q]
halmazba, mint azon
kívül, így, az aláírásnál használt titkos kulcs elég jól approximálható. Másik gyengesége a DSA és ECDSA rendszernek a
p
és
q
változók megválasztásánál fordulhat el®. Ha egy random
következ® alakban állítjuk el®:
1 www.nicolascourtois.com/bitcoin/thesis i ang.pdf D W
q
változót a
6. FEJEZET. AZ ECDSA ÉS HASZNÁLATA A BITCOIN VILÁGÁBAN
27
q = SHA(m1 ) − SHA(m2 ) úgy, hogy prím szám legyen, illetve, ha ehhez a
q -hoz
keresünk olyan
p = aq + 1 számot, amely szintén prím, akkor az
m2
üzenet aláírását meg tudjuk hamisítani az
m1 -es
üzenetnél használt aláírással. A veri kátori oldalon ért támadás lényege, hogy a veri kátor számítógépének a memóriájában megváltoztatjuk az akkor minden
r=0
értéket viszont hogy a
β
1re
α
értékét. Ha ezt a változót sikerül átírni
α = 1-ra,
paraméterrel rendelkez® aláírást validnak fog értékelni a rendszer. Ha ezt az
α
módosítjuk, akkor akármelyik dokumentumra tudunk aláírást hamisítani úgy,
publikus kulcs paraméteréhez keresünk egy
r = (β z
mod p)
mod q
random számot, és hozzá egy
s= számot.
r z
mod q
Ez szintén mindig valid aláírást fog eredményezni.
Ezek a támadások csak akkor
eredményesek, ha az aláírási sémánkat nem megfelel®en használjuk, implementáljuk, illetve ha a titkos paramétereinket olyan mód tároljuk, hogy azok könnyen elérhet®ek más emberek számára.
7. fejezet
Összefoglalás A szakdolgozatom a bitcoint mutatja be. Ez egy decentralizált peer-to-peer kriptovaluta rendszer amely Satoshi Nakamoto nevéhez köthet®. keresni.
Mértékegysége a bitcoin, amelyet bányászattal lehet
Ez nagyon er®s hardwaret igényel amely arra szükséges hogy a program fel tudja dol-
gozni a tranzakciókat a peer-to-peer hálózaton keresztül illetve hogy minél gyorsabban meg tudja oldani az elvárt matematikai feladatokat. Ezt a pénznemet digitális tárcában tárolhatjuk, amely a számítógép merevlemezén helyezkedik el. sága, ami ®t egy pénznemmé teszi.
A bitcoin biztonságos és megvan minden tulajdon-
A bitcoin blokkláncból áll amely blokkokból épül fel.
Az
els® ilyen blokkot genesis blokknak nevezzük, és minden blokk egy fejléccel kezd®dik, amelyet egy tranzakciós lista követ. A blokkok visszafele vannak linkelve, minden blokk fejlécében megtalálható az el®tte elhelyezked® blokkra mutató érték.
A bitcoinban a tranzakció aláírásához elliptikus
görbén alapuló digitális aláírás sémát használnak. Ehhez szükséges volt megismerkednünk az elliptikus görbékkel és az elliptikus görbéken alapuló kriptográ ai rendszerrel. Ezen rendszerek által használt görbék nagyon speciális elliptikus görbék, csak és kizárólag olyan görbékkel foglalkozunk kriptográ ai szempontból, amelynek diszkriminánsa nem nulla. Az elliptikus görbéken de niáltuk az összeadást, pont duplázást, és a végtelen pontokat is, amely szükséges az elliptikus görbéken alapuló digitális aláírás séma kulcsgenerálásához. Ezek után megismerkedtünk háromféle digitális aláírási sémával, az ElGamal-al, amely a diszkrét logaritmus problémán alapul, és nagyon egyszer¶ a kulcs generálása, aláírása és veri kációja. Ezek után bemutattam a Digitális Aláírás sémát, amely az ElGamal egy sokkal gyakoribb variánsa, ahol szükségünk volt ciklikus csoportokra is a kulcsgeneráláshoz. Végezetül bemutattam az elliptikus görbéken alapuló digitális aláírás sémát, amely már a kulcsgenerálásnál és aláírásnál is elliptikus görbéket használ, illetve a bitcoinban használt egyedi paramétereket amellyel implementálták az aláíró algoritmust.
28
Irodalomjegyzék [1] Liptai, Kálmán:
Kriptográ a, Eszterházy Károly F®iskola Matematikai és Informatikai Intézet,
2001. [2] Antonopoulos, Andreas M.:
Mastering Bitcoin, O'Reilley Media,Inc , 2015.
[3] Buttyán, Levente; Vajda, István :
Kriptográ a és alkalmazásai, Typotex, 2004.
Understanding Cryptography - A Textbook for Students and Prac-
[4] Paar,Christof; Pelzl, Jan :
titioners, Springer, 2010. [5] Pass, Rafael; Shelat,Abhi : [6] Smart, Nigel:
A Course in Cryptography, Printed online, 2010.
Cryptography: An Introduction (Third Edition), Mcgraw-Hill College , 2004.
[7] Virasztó, Tamás:
Titkosítás és adatrejtés, NetAcademia Kft., 2004
[8] Washington, Lawrence C.:
Elliptic Curves Number Theory and Cryptography (second edition),
Taylor and Francis Group, 2008 [9] Wang, Di :
Secure Implementation of ECDSA Signature in Bitcoin,
Information Security at
University College of Longon, 2014
http://davidederosa.com/ basic-blockchain-programming/elliptic-curve-digital-signatures/, 2015
[10] De
Rosa,
[11] Rylwaéder.
Davide:
Eric:
math-behind-bitcoin/,
Elliptic-curve
digital
The
Behind
Math
signatures
Bitcoin
http://www.coindesk.com/
2014
https://blog. cloudflare.com/ecdsa-the-digital-signature-algorithm-of-a-better-internet/,
[12] Sullivan. Nick: ECDSA: The digital signature algorithm of a better internet
2014
29
