BAB V ECESA DAN ASPEK-ASPEK KEAMANAN ECC SEBAGAI PENGAMAN DATA PADA ECESA 5.1
Algorifiile Peiialdaan ElGgiiial KiiiSia Elipfik Pengonstruksian ECC pada algoritme penandaan ElGamal dititikberatkan
pada perubahan operasi-operasi dari grup Z i (grup multiplikatif) pada algoritme penandaan ElGamal ke operasi grup dari kurva eliptik E(Z,) (grup penjumlahan) pada algoritme penarid-
EIG&mal berbasis ECC, sesuai dengari Tabel 11
(berdasarkan ANSI ~ 9 . 6 2 ) . Utltuk u
t
y Blgoritme peritr5uisformi5ui ECC ke algorit~iie
penandaan ElGamal disebut sebagai algoritme Penandaan ElGamal Kurva Eliptik (ECESA) d a proses-proses pentri%isfoniiasii%ri diperliliirtkSui dalam tabel-tabel berikut ini.
rElemen Gmp
GNp kurva eliptik E(Z,)
Himpuuan intejer {l, 2, ...,p-1}
Perkaliau mcdulop Elemen: g, h
I
Notasi
MLD
Perkalian: g x h
Pemangkam:&
E&
g E Z;
dan
h = 8 modp. Cari intejer a!
Diberikan P e E ( i p )dan p a p . Cari intejer a!
Tntrel12. Notas.1 Pmradm EIGnma dm ECESA
Penandaan ElGamal
ECESA
P
n
Keterangan: p . bilangan prima pada Z',
n : order prima dari titilt G pada E(Z,)
a . kunci rahasla pada
d :kunci -a
Z;
g : elemen generator dari
y : kunci pubr* pada
pada E(Z,)
P : titik generator pada E(&)
Zi
Q: kunci publik pada E ( q )
z;
Tabel 13. Pengesetan Algoritme Penandaan ElOamal d m ECESA Setup dari PenandaanE l G W Setup dari ECESA 1. p adalah bilangan prima
1 . E adalah kurva eliptik atasjeldZp 2. P adalah titik generator berorder n pada
2. g adalah elemen generatorberorderp
I
3. Grup yang digunakan: (go,
F(Z.1
...,
nT1l Tnbel14. Pembangkltan Kuncl Penandaan ElGamal d m ECESA Pembanekitan Kunci Penandaan ElGamal I Pembanektan Kunci ECESA
I
1 . Pilih intejer acak a dalam [ l ,p 2 ]
I 1. Pilih intejer d dalam [ l ,n-l]
2. Hitungy=fmodp
-
1
Z.HitungQ=dP
1 3. Kunci rahasia adalah a
1 3. Kunci rahasia adalah d
1
4. Kunci publik adalahy
4. Kunci pub& adalah Q
I
I
Tabel 16. Pemverifiknsian Tmda dari Penmdaan ElGun.4 dan ECESA
Pemv-an
Tanda ElGamal
I
Pemverifikasian Tanda ECESA
1. Menghitungvl =y: r " m o d p
l.Hitungvl =rQ+sr',paiksss&r'di [I,n-11. Jika gagal, maka tolak tanda
2.Hitungh(M)=e
2. Hitung h(M) = e
3. Hitungv2=gemcdp.
3. Hitungv2=eP
4. Taima tan& jib v, = v2
4. Taima tan&jika vl = v2
I
CONTOH ECESA a. Pengesetan ECESA Misalkan E(Z17) dan .$
=
x 3 + b + 2 atas Z17 dengan a=2 dan b=2 Solusi-
solusi atas Z17 untuk persamaan kurva eliptik tersebut adalah
Grup E(Z17) mempunyai 19 titik (termasuk titik infinity 0). Solusi-solusi ini diperoleh dari p e ~ ~ bd am kesalahan (tiial and error), namun untuk bilangan yang besar adalah tidak efektif dalam penghitungan secaa maliuat. Contoh: M i d h r i dipilih secara a&& titik (0,6). Kemudian cek titik tersebut memeriuhi atau tidak persamaan atas z 2 3 , yaitu :
~ = ~ + i r + 2 + 6 2 m o d 1 4 = ~ + ~ + i + 2 =dmemenuhi. 1 Jika yang dipilih titik (2,3), maka: Y Z = 2 + i r + 2 ~ 9 = 8 + 4 + 2 ~ 9 = 1*tidakmemenuhi, 4 dan seterusnya. Pilih
sdah
satu
titik
generator P P a i
misalkan P
=
pc%juml&n
2 titik (yang s m a dan berbda)
solusi-solusi tersebut,
(3,l). Grup yang digunakan yang dihasilkan dari proses pada k u ~ aeliptik y a g
dijelaskan pada bab sebelumnya adalah: P=(3,1),
2P-<13,7),
7P=(7,6), 8+(16,4),
3P=(0,1 I), 9+(5,14),
4P=(10,11), 10+(6,3),
5P=(5,1),
6P=(9,16),
llP=(16,13), 12Z'==7,11),
13P=(9,1), 14P<5,16), 15P<10,6), 16P=(0,6), 17P=(13, lo), 18&(3,16), 19H. Kareria 19P = 0, mdca P mempunyrli order n = 19.
b. Pembangkitan Kunci ECESA Entitas A melakukan beberapa hal, yaitu:
i. PiBR d = 3 dati imemal [I, 181:
ii. HitungQ=dP=3.(3,1)=(0,11); iii. Jadi kunci rahasia d = 3 dan kunci publik Q = (0,ll). C.
Peiiibaiigkitsn Taada ECESA Entitas A menandai berita M = 11100011010111100. Misalkan representasi desimal d e nilai haSh h(M) Ilddali e = 6. i. Pilih k = 5 dari interval [I, 181 ; ii. Hitungr = kP = 5.(3,1) = (5,l)
+ r'= xl mod n
= 5 mod
19 = 5;
iii. Hitung h(M)=e=6;
iv. Stung s = k-'(e-dr') mod n
= 4(6-15)
mod 19 = -36 mod 19 = 2;
v. Tanda M adalah (rY,s) = (5,2). d. Vefifihsi Taada ECESA Entitas B memeriksa tanda (r', s) = (3,l) pada Msebagai berikut: i. Hitwig vl = r'Q+ Si = 5.(0,11) +2.(5,1)
= (10,6)
+ (6,3)=(9,16);
ii. Hitung h(M) = e = 6 (dimisalkan); iii. Hituxig v z = eP = 6.(3,1)= (9,16); iv. Terima tanda karena vl = vz. 5.2 Aspelt-Aspelt Keamanaa ECC Sebagai Peagaitiaa Data Pada ECESA
Algoritme Elliptic Curve ElGamal Signatare (ECESA) belum ada staiidafdisasinya sepefti lialnya dengaii stsridafdi%%i ECDSA yaiig sudah ad% sehingga panduan tentang pengamanan algoritme ini mengacu pada standardisasi ECDSA, y & u ANSI X9.62-1998. Hal irii dikiiremkan algoritiiie pentuidflan ElGamal merupakan algoritme dasar dari DSA, dimana telah diketahui bahwa kedumya mempuriyai basis keamanari yaiig Sma, yaitu bergaiitutig pada masdali logaritma diskret (Tilborg, 2005). ANSI X9.62-1998 mendefinisikan suatu teknik ulituk
me
&,liiefi&b8
pfiwd-
b,jitel:l. Stari&diSaSi iIii me*jelas&
metode untuk penandaan dijitel dengan menggunakan kurva eliptik yang analog derigw DSA. Tidak seperti perrnasalahan logaritma diskret biasa dan pmasalahan f&o~miint6ef, sub-eksP6neriSial dikaatiu untuk pem&Jam kurva logarima diskrit. Untuk alasan ini, strength-pr-&-bit
pa& intinya akan
menjadi lebili b e W &dam suatu dgoritdie yang mengguriakari kuna eliptik. Bab
ini membahas tenttuig ECESA dan mendiskusikan keamanan dan implementasi yang berhubungan. 5.2.1 Parameter-parameter doiilain ECESA
Parameter-parameter domain untuk ECESA terdiri dari suatu kurva eliptik E yang dipilih tepat, didefinisikan atas lapangan berhirigga m i t e field) Fp y a g berkarakteristikp, dan sebuah titik dasar P E E(Fp).Parameter-parameter domain dapat dipakai bersama-sama oleli @up entitas atau khuius urituk seoratig pemdcai tunggal. Parameter - parameter domain ECESA yang dimaksud addah
D = (p, 4 b, P,n , h ) q e f t i yang telirli dijelasktui pada bab III. Sub-bab 5.2.1.1 berikut ini menggambarkan syarat-syarat apa saja yang diperlukan seliiligga teidapat pafameter-parBniaei domain ymg tepat. Sub-bab 5.2.1.2, menunjukkan suatu metode untuk menghasilkan parameter-parameter
domi% sdangkan sub-bab 5.2.1.3 menunjukktui sebuali prosedui ditentukw untuk menghasilkan kurva eliptik yang diuji random. 5.2.1.1
Paramefesparametep Doaaia
Dengan tujuan untuk memfasilitasi kemampuan operasi internal, beberapa batam ditetiipathn ukufafield yang dan repiesentasi digu&an untuk elemen-elemen F,.
Lebih jauh lagi, untuk menghindari beberapa
%r?iarigan/pemecblian(attack) khusus yang dikaahui, batasan-batasan ditempatktui pada kurva eliptik dan order dari titik dasar.
Syaiat-syfiat Field (fieldrequireiiiem). Orda darifinitejeld adalah p p d a F,, modulo intejerp.
Syarat-iyaMt kuwa eliptik (Ell$f!c ciinte requiieiWiifi).Den@ tujutui urituk menghindari serangan-serangan Pollard Rho d m Pohlig-Hellman pada MLDKE, m a h pentkg bdiwa jumldi dmi titik-titik rasioml Fp pada E &pat didibagi dengali
n prima yang cukup besar. ANSI X9.62 memberikan mandat bahwa n > 2Ifi0. Untuk melientukan suatu $eld Fp, n hatus dipilih sebesai murigkii yaitu seseorang hams mempunyai n
w
p ,sehingga #E (Fp) addah hampir prima. Kita
mengasumsikan bahwa n >216'
dan
n > 4&.
Kofaktor
didefinisikan
sebagai h = #E(F,)ln. 5.2.1.2
Pembuatan dan Validasi Parameter Domain
Algofitme A adalali cara untuk membuat pariunaer domain kriptografi ymg aman, artinya semua serangan keamanan dapat diatasi. Suatu parameter domain dapat divalidasi secara jelas dengan Algoritme B . Pioses validasi membuktikan bahwa k ~ N aeliptik mempunyai order yang diklaim dan tahan terhadap semua swmgali p d a MLDKE. Seseorruig yang menggun&ri k u ~ eliptik a yang dibuat oleh software atau pihak-pihak yang tidak dipercaya dapat menggunakan validasi a secwa kriptog'afi. (lihat Algoritma A, B, untuk menyakinkan bahwa k u ~ aman C, D, E, dan P di Lampiran 1)
Bat.tum-batasm untuk
ii
d m L pada algontme A dan B adalah sebagai
berikut: a. Karena n dipilih untuk memenuhi n >
y, kondisi L
2
160 pada input
Algoritme a memastikan bahwa n > 216'. b. Kondisi L l [log,
memastikan bahwa 2Ll p dimana suatu kuwa eliptik E
atas F p dengan order #E(Fp) dapat dibagi dengan prima L-bit yang ada (ingat kembali bahwa #E(Fp) = p). Dan juga, jika p
L i [logi
= Zm, maka
L hatus memenuhi
1 karena # E(F,.) addah genap.
c. Kondisi n > 4&
menjamin bahwa E f i ) mempunyai sebuah subgrup unik
berorder n karena #E&)
5 (&+I),
dengan Teorema Husse, sehingga
demikian nZ tidak membagi #E(Fp). Selanjutnya, karena hn = #E&) berada pada interval Hasse, maka hanya ada satu kemungkinan intejer h, sehingga
#E(Fp)= hn, yaitu h =
[(a+
1)' In].
Order-order #E(F,,) dapat ditentukan dengan beberapa teknik, yaitu: a) Penghitungan Titik
Pada tdiun 1985, Schoof mempresentasikan algontme polynomiciltime untuk menghitung #E(Fp) pada kurva eliptik sembarang E. Algoritme
ini menghitung #E(Fp) mod I untuk bilangan-bilangan prima kecil I, dan kemudian menentukan #E(F,) dengan menggunakan Teorema Sisa Cina
(Chinese Remiilder Theorem). Algoritme Schoof adalah kurang efisien dalam prakteknya untuk nilai-nilai p > 216',
tetapi setelah itu dibuktikan oleh beberapa orang,
termasuk hasil dari Atkin dan Elkies yang disebut dengan algoritme Schoof-Elkies-Atkiri (SEA). Algoritme ini adalah algofitme yatig diketahui terbaik untuk penghitungan titik dari kurva eliptik sembarang gm-lap@gflnpfima ymg membutuhkm beberapa urituk
Mas
nilai-nilai p tersebut. Oleh karena itu, algoritme ini dapat menentukan jumlah titik modulo p r i m kecil I yarig -gat
cepat d m dapat d i g u d a n
dalam suatu strategi penggagalan awal dalam mengeliminasi calon kurva y&ig mempunyai order dapat dibagi dengan bilangan prima k s i l secara cepat.
b) Mwoda perltaliail komplelts (CM). Metoda lain untuk menghasilkan kurva eliptik
yang sesuai
st.ci%a kriptograf! adal;lh m&oda CM. M&oda CM at% F,, juga disebut metoda Atkin-Morain. Dalam metode ini, seseorang pertama kali memilih suatu order N yatig memenuhi keridala-kendala keammm yang diperluktin dan kemudian mengonstruksikan suatu kurva eliptik dengan order tasebut. Metode ini sangat efisien karenafinite field berorder q dan kuwa eliptik berorda N=@l-t ywg dipilili, sehingga perkdim kompleksfield
e(=)
kecil. Secara kriptografi, kurva eliptik yang tepat atasfield-
j?eH 160 bit &pat dibibadgkitkibad Manisatu m e ~pada t mirtu worKEtatiori. Metode CM pada khususnya adalah sangat lebih cepat daripada algoritme yalig terbaik untuk melighitung titik-titik k u ~ aeliptik ymg dipilih secara random atas Fp. Kurva eliptik yang dibangkitkan dengan menggu,&& tiiaod CM mp& memli&h k-ywg sama dengan kurva yang dibangkitkan secara random.
e) Kurva KablifZ. K U N ini ~ dikenal dengan kurva biner menyimpang adalah pertama kali diusulkan untuk penggunaan kritografik oleh Koblitz Kurva Koblitz adalah kurva eliptik atas F,.
yang pendefinisian persamaannya
mempunyai koefisien d a l m FL Jadi ada dua kunra Koblitz at& F,. ,yaitu:
3 + xy
=
x3+ 1 dan
3 + xy
=
x3
+ 2 + 1. Solinas menunjukkan
bagaimana $&s&rang dapat menghitung kP y ~ sangat g efiten untuk sembarang k, dimana P adalah sebuah titik pada kurva Koblitz. Karena pembentukari lieberapa pt%kali&i skalw add& larigkah komputasiotid yang dominan pada pembentukan dan verifikasi tan& ECESA (lihat subbab 5.2.3 di bawah), kuiva Koblitz addah sarigat dctrtiktif urituk penggunaan dalam penandaan dijitel (seperti balnya dengan ECDSA).
domain mempunyai syarat-syarat aritrnatika yang diperlukan. Alasan untuk melhkari valid& parmeter domairi, pada prakteluiya meliputi: 1) Pencegahan dari penyusupan parameter domain yang tidak benar dari pihak lawan yang
memuli&&afi
bebefapa sefatig&i; da 2) penemu&ippengkdean ymg ti,j&
sengaja atau kesalahan transmisi. Penggunaan himpunan parameter domain yang tid& hen* dapat riiembatabn seluiuh syuat-sywat k m a i a r n yiuig dihwapkan. Sebuah contoh serangan nyata (Albeit Far-Fetched) yang dapat dilancarkan jika vdidui patmeter domain utituk seliuah skema tiilida tidak dilakukan adaltdi telah didemonstrasikan oleh Black-Wilson dan Menezes. Serangan itu pada suatu kol kutic .. 1 persetujuan, ydtu pada skema penalidan ElGamal. ~
Met&metode
nntuk metnvalihi parameter &mmmmn.
Kepastian bahwa D = @, a, b, P, n, h) dari parameter domain EC yang valid dapat diberikan ke seseorang yang menggunakan salah satu dari metode-metode berikut ini: a. A
riielw valid&i
(lampiran). b, A membuatD Dfi&iii
doriiain defigm mengguniaksn
ae
sbu~
tm
y&ig dipercaya,
c. A menerima jaminan dari kelompok T yang dipercaya (misalnya, Certification Authority), bahwa. T telah melakukan validasi parameter domain D dengan jelas menggunakan Ngoritme B.
d. A menerima jaminan dari kelompok T yang dipercaya, bahwa D telah dibuat derigari mengguridcari sistem yang dipercaya. Membuktikan order dari kurva eliptik
Mengingat kembali interval Hasse, yaitu itu n > 4 & , maka
6-1' <# E(F,) < (&+l)2.Karena
tidak membagi #E(Fp), dan jadi E(Fp) mempunyai
sebuah
sugroup
yang
(fi+
-(&-I)*
= 4&, maka
unik
berorder
n.
Dan
juga,
karena
ada intejer h yang unik, sehingga p
+ 1-2&_< nh < p + 1 + 2&, sebut saja h =
k& +1)2/nJ.
Jadi langkah 9, 10,
11 dari algoritme B memeriksa bahwa # E&) sesungguhnya sama denga nh. Pembiiafaa Kiiwa Elipfik Seeam Random
5.2.1.3
Sub-bab ini menjelaskan metode yang digunakan untuk menghasilkan suatu kuma e]iptik s@lu;i falidom. Pedefinisim p&meter-p&fmetw dwi
eliptik
didefinisikan sebagai output dari hngsi hash. Input yang ditempatkan pada hngsi hash kemudian digumkan sebagai pembuktian (di bawah asumsi bahwa hrigsi hash tidak dapat diinversikan) bahwa kurva eliptik benar-benar dihasilkan secara rmdsm. Irii memb&hn beberapa j-nan untuk penggum kuiva eliptik bahwa orang yang membuat kurva eliptik yang tanpa sengaja mengonstruksikan sebuah kuma yang lemah dan htd itu dapat dimmfiiatkiui untuk menemukan kembtdi kunci-kunci pribadi pengguna itu. Penggunaan dari metode pembuatan ini dapat
memBantu
pwwalm-pwso&ti m e n g e ~ kettiungkiriari
penemuan kelas-kelas kurva eliptik lemah yang baru dan aneh di masa yang akan datmg, yaig p d a dasamya tidak pemdi diha~ilkari. Sebagai catatan, penghitungan jumlah titik-titik pada kurva eliptik yang
silh
a dddisuatu Pek&jm
i8ktis.
ymuig mliiit dm
prakteknya, orang mungkin membeli sowme dari seorang penjual untuk nghitungari titik. Paddial, sejak order ymg diduga c
h i
kurva
eliptik dapat dibuktihn secara efisien dengan kepastiati loo%, maka software tersebut tidak dapat dipercaya. Algoritme-algoritme pembuatm dan pemefiksm kurva eliptik random atas F, berturut-turut adalah Algoritme C dan D. 5.2.2 Pasangar-pasamgait Kiirci ECESA
Pasangan kunci ECDSA dihubungkan dengan sebuah himpunan khusus dari paameter-ptirmeter domain EC, yaitu D = @, a, 8, P,n, h). Kunci publik adalah suatu perkalian dari titik dasar P yang dipilih acak, sebut Q dalam grup (P), se;merit*a itu kunci r a h i a adalah intejer digun8km untuk merighasilkan perkalian tersebut, sebut d = lo&. 5.2.2.1
Pembuatan Pasangan Kunci (Kq P&i Geri&atiori)
Entitas A yang membuat pasangan kunci harus mempunyai kepastian bahwa
p s a m ~ e r - p m e t e rdomain addah lien* (lihdr 5.2.1.2). Hubungan
antara parameter-paremeter domain dan suatu kunci publik hams diverifikasi oleh semua erititas yang menggunakari kunci publik A setelah itu. Pada praktekriya, asosiasi ini dapat dicapai dengan cara kriptografik (misalnya, suatu Certrfication Autho@~ywg membuat sebmh seitifiht yang menunjukkan asosiasi i d ) atau dengan konteks (misalnya, semua entitas menggunakan parameter-parameter doliiaiti yang sama). Algoritme yam digunakan adalah Algoritme E (Impifan). 5.2.2.2
Validasi Kunci Publik (fiblic Kq, Validah'on) Validasi kunci publik, pertarna diumumkan oleh Johnson yang menjamin
bahwa suatu kunci publik mempunyai syarat-syarat aritmatika yang diperlukan. Pengesahan kunci publik yang berhasil ini menunjukkan bahwa sebuah kunci f&sia yarig ecaia Ild& meskipun pengedari irii tid& menunjukkan bahwa seseorang benar-benar menghitung kunci rahasia maupun
pemilikdya bem-be "ai memilib kudci
ia tmebut. Ala m-al
untuk melakukan validasi kunci umum pada prakteknya meliputi: (I) pencegahan t & W p pe@usupan pihak l a w a pada kunci publik y a g tidak vdid memungkbkan beberapa serangan; (2) pendeteksian pengkodean yang tidak
disengaja (kuraiig hati-Bati) atau kesalahan tiirnsmisi. Pengguni%%nkunci publik yang tidak valid dapat membatalkan seluruh syarat keamanan yang diharapkan. Sebuah contoh dari serangan konkrit yang dapat dilancarkan jika validasi kunci publik tidak dilakukan adalah serangan pada protokol persetujuan kunci Diffie-Hellman. Metoda untuk validasi kunci umum
Jaminan bahwa kunci umum Q adalah valid dapat diberikan oleh suatu entitas A yang menggunakan salah satu dari metoda-metode yang digunakan: a) A melakukan validasi kunci umum secara eksplisit (jelas) dengan merigguriakan algoritme F (lampiiirn). b) A membuat Q itu sendiri dengan menggunakan sistem yang dipercaya. c) A meneiima j m i n m d&i pihak yag dipwcaya T (niisalhn, Certzf7catioii AuthoritylCA) bahwa T telah melakukan validasi eksplisit kunci publik A detigirn metiggunakan algoritme F. d) A menerima jaminan dari pihak T yang dipercaya bahwa Q telah dibuat dengan menggudan sisteiii yang dipercaya. 5.2.2.3
Bukti Dan Kepemilikan Kunci Rahasia
Jika entitas C mampu menjamin kunci publik A, yaitu Q sebagai kunci publik miliknya, maka C dapat menegaskan bahwa pesan A yang ditandai berasal dari C. Untuk menghindari ini, CA harus memerlukan seluruh entitas A untuk m e m b u k t i kepemilikan kunci raiirsia yang berhubuxigirn deiiga kunci publik, sebelum CA menjamin kunci umum sebagai milik A. Bukti kepemilikrin idi dapat diselesaikm dengm variasi m a . Sebagai contoh dengan memerlukan A untuk menandai sebuah pesan pilihan CA. Catatan b h a bukti kqemilika kutici iahrrsia membwiW jaminan yang beibeda dilii validasi kunci publik. Yang dulu menunjukkan kepemilikan suatu kunci rahasia sekdipun itu murigkin bwhubuiigan dengan suatu kurici publik yang tidak bedili walaupun yang terakhir menunjukkan kebenaran kunci publik tetapi bukan kepemilikan kunci i W i a y&ig berhubungaii. Melakukad kedua-du&iya memberikan suatu tingkat jaminan tinggi.
5.2.3
Pembiiataa dail Pemeriltsaair Taada ECESA Bagian ini menggambarkan prosedur untuk membuat dan memverifikasi
tanda dengan ECESA. Algoritme ini melibatkm suatu fkngsi hash kriptogafi H yang output-nya mempunyai panjang bit tidak lebih dari n (jika kondisi ini tidak tqenuhi, m& artput d&i H dapat dippcong). Setiap entitas membuat sebuah kunci publik d m kunci rahasia. Setiap entitas A melakukan: Pembangkitan Kunci ECESA 1. Pilih inteja d & l m [l,n-11. 2. Hitung Q =dP.
3. Kunci pfiljadi adalali d 4. Kunci publik adalah Q.
U~ituk menmdai pestui m ddegtui panjang sembwang, entitas A dengan parameter domain D = @, a, b, P,n,h) dan diasosiasikan pasangan kunci (d, Q) rneldmkan hal-hl sebagai berikut: Pembangkitan Tanda ECESA 1. Pilih intejer k d a l m [l,n-I]. 2. Hitung r = kP
3. Hitung h(M)
= (XITI)
=e
+ rubah r menjadi intejer r'= xl mod n.
+ fkngsi Hash d m rubah string bit ke suatu intejer e.
4. Hitung s = ~ ' ( e clr') mod n.
5. T a d a M d a l & (i,s). Beberapa entitas B dapat memverifikasi tanda tersebut dengan menggunakan kunci publik A. Pemeriksaan Tanda ECESA 1. Hitwig v, = r'Q +ST= (xlyl).
2. Hitung h(M) = e. 3. Hitulig vz = eP = (.%lyl).
4. Terima tanda jika vl
=
4.
dain' Ymyk&peiimdriiin
-
Jika tanda (r, s) untuk pesan M telah dibuat oleh A, maka vl = rQ + sr = rdP + skP
P (id + sk) = P (td+ k-l(e - &).k)
-= eP, maka vl = vz yang diperlukan.
PCitgkonvmiair
data
ANSI X9.62 menentukan suatu metode untuk merubah elemenfield XI ke sebuah intejer pada larigkah 2 dari pembangkitm tmda. ANSI X9.62 juga menentukm suatu metode untuk merubah string bit ke intejer-intejer. Metode ini digunakan mtuk merubah ouput e dafi suatu tungsi hash ke sebuah imejer sebelum penggunaannya dalam komputasi modular pada langkah 5 pembangkitan tanda d~ langkali 2 pada pemverifikasian tarida.
Sebelum memverifikasi tanda A pada suatu pesan, B perlu memperoleh salinan otentik dari parameter-parameter domain A, yaitu D dan kunci umum yang diasosiasikan, yaitu Q. ANSI X9.62 tidak menetapkan suatu mekanisme untuk menmpai ini. Pada prakteknya, kunci umum otwtik b i m y a didistribusikan melalui sertifikat-sertifikat. Sertifikat kunci publik A yang seharusnya mellga~iduligsebuah string irifoimasi yang merigidentifikasi A s e w a unik (sepefti nama dan alamat A), parameter-parameter domainnya D, kunci publik Q-nya, dan sebuah tarida CA at& i n f o m s i ini. B kemudim dapat menggunakari salinan otentik kunci publik CA untuk memverifikasi sertifikat A, dengan demikian diperoleh suatu sdinan otmtik kudci uliium statis A. Perbandingan antiua algoritmepenanda Elgamal dan ECESA . Konsepnya, algoritme ECESA diperoleh dari algorltme Penandaan ElGamal dengan mengganti subgrup dari Fp berorder p yang dibangkitkan oleh g dengan subgrup dari titik-titik pada kurva eliptik dibangkitkan oleh G. Perbedaan yang signifikari m t a a dgontme-algontme Peliaddaan E l g m d dai ECESA d d a h hanya pada pembangkitan r. Algoritme Penandaan Elgamal melakukan ini dengan mengambil elemen secara acak r = $ mod p secara acak, jadi perolehan suatu integer dalam interval [I, p-21. Algoritme ECESA membangkitkan r pada interval
[l, ii-1] dt?ngari iiiengabil kootbiriat x pada titik KG
r modulo n ini.
mats a&
d m mengutaligi
Tujuan keamanan dari algoritme ECESA adalah untuk melawan serangan berita ymg dipilih (chosen-message attack). Tujuan seormg lawan yang melancarkan serangan terhadap suatu entitas A yang sah adalah untuk memperoleh tmda yatig valid pada ebuah pesan in, setelah me~iiperolehtmda A pada suatu kumpulan pesan (tidak termasuk rn) dari pilihan lawan. Sermgan-serangan yarig
mungkin
pada
algoritme ECESA
dapat
diklasifikasikan sebagai berikut: a) Sermgan-serarigan pada liiasalah logaritma diskrit kuwa eliptik. b) Serangan-serangan pada fungsi hash yang digunakan.
c) Sermgan-serangan lainnya. Selanjutnya akan dijelaskan ringkasan tentang pengetahuan penyerangan saat ini d m bagaiman serangm-sertuigan ini dapat dihindari pada prakteknya. 5.2.4.1
Serangan-seranganpada MLDKE
Satu cara seorang lawan berhasil mencari kunci rahasia A, yaitu d dari parameterparameter domain A, yaitu @, a, b, P, n, h), dan kunci publik Q. Setelah itu, lawan tersebut dapat memalsukan tanda A pada beberapa pesan pilihannya. Definisi masalal: lihat Definisi 41 Bab II. Serangan-serangan yang diketahui Bagirn isii meniperlihatkm bebeapa algoritme yang diketahui dapat mexiiecahkari suatu penyerangan.
a)
Ndve Ejrhaiisri~eS e m k Pada metode ini, sesmimg dengm sederbtia
menghitung perkalian-perkalian dari P, ZP, 3P, ... sampai Q diperoleh. Metode illi dapat membutulikm n lmgkah pada h a s terbutuk. b)
Algoritme Pohlig-HeIlm Algoiitme yang diperkmalkan
deli Pohlig d m Hellman srdalah
mengeksploitasi faktorisasi n, order dari titik P. Algoritme ini mereduksi m a d a h dari peolehatl 1 meajadi m w l a b d x i penernurn kembali 1 modulo setiap faktor-faktor prima dari n. Bilangan 1 yang diinginkan kemudian dapat dip@olelidengari menggudakan Teorem Sisa Cina.
Implikasi dari algoritme ini adalah sebagai behkut: untuk mengkontruksi contoh yang paling sulit dari MLDKE, seseorang hams memilih k u ~ a eliptik yang ordemya dapat dibagi oleh prima besaj n. Ymg lebih d i s u k ~ , order ini prima atau hampir prima (yaitu, sebuah prima besar n kali suatu integer kecil h). Untuk selanjutnya, diasumsikari bahwa order
4
ii
dari P
adalah prima. A Bilby Sle;pGidiltStq (Algo.ritme tiihripkei.il-fiihap esm). Algoritme ini adalah suatu penukaran memori waktu dari metoda pwyelidikan
yarig
mendalaii
(exhaustive seiach). Algoritme ini
memerlukan tempat penyimpanan kira-kira kia-kira d)
& titlk, dan running time-nya
& langkah pada kasus paling buruk (worst case).
AIgmmrtmeRho Pollard Algoritme yang diperkenalkan oleh Pollard adalah suatu versi randomisasi dari algoritme Baby Step-Giant Step. Algoritme ini mempunyai kira-kira running time yang diharapkan
(mlangkah) sama dengan algoritme
Baby Step-Giant Step, tetapi algoritme ini adalah lebih ulung (superior), yaitu memerlukan ejumlah tempat peIiyimpmm ymg dapat dirrtiaikan. Gallant,
Lambert,
dan
Vanstone,
serta Wiener
dan Zaccherato
menggambarkm bagaimma algoritme Rho Pollajd dapat dipercepat dmgm faktor
f i . Jadi running time yang diharapkan dari metoda Rho Pollard ini
dengan kecepatan ini adalah (zn)/2 langkah 5.2.4.2
Serarigan-sewngari pada Fungsi Hmh
Definisi Fungsi Hash: lihat Definisi 44 Bab 11. ym.clf-MKecsmd FiiiigsfHiirk
*
Berikut ini akan menjelaskan bagaimana menyerang algoritme ECESA yang dilrmcarkm dengan baik jika suatu kngsi hash tidak mempunyai sifat ketahman preimej atau ketahanan tumbukan.
a) J i i a a t u kligsi hash tidak memenuhi sifat Defillisi
44c Bab 11, maka
seorang lawan E mungkin mampu memalsukan tanda A seperti berikut ini.
E meiiiilih sernbumg iaejer 1 dan dienghitung i sebagai koordiiat-j~dari Q+lP modulo n. E memasang s
=
r dan e
=
rl mod n. Jika E dapat
memperoleh pesan m, sehingga e=h(m), maka (r,s) adalah tarida valid untuk m. b) Jika suatu fungsi hilsh tidak tahan tethadap tumbukan, maka suatu entitas
A mungkin dapat tidak mengakui tanda-tanda seperti berikut ini. Pertama kali A membaligkitkan dua pesan m dan m', sehingga h(m) = h(m'); seperti sepasang pesan yang disebut tumbukan (collision) untuk fimgsi hash. A kemudim menandai
m dan kemudian menyatakan telah menaridai in'
(catat bahwa setiap tanda untuk m adalah juga sebuah tanda umtuk m').
Serangan-serangan lainnya Syarat-syarat Keamanan untuk setiap Pesan Rahasia 5.2.4.3
Setiap p e m tahasia k pada pembmgkitan tmda algoritme ECESA mempunyai syarat-syarat keamanan yang sama dengan kunci rahasia d Hal ini karena jika
smtang lawan E mempelajari setiap pesm rahasia s t u per sfltu k yarig digunakali oleh A untuk membangkitkan sebuah tanda (r, s) pada beberapa pesan m, maka E dapat menemukan kembali kunci rahasia A karena d = i l ( h - e) mod n dimana e = h(m) (lihat step 4 pada pembangkitan tanda algoritme ECESA). Oleh karena
itu setiap pesm rahasia h a s dibangkitkaa dengan attiail, disirtipaa dengan mail, dan dihancurkan dengan aman setelah digunakan.
Penggiiaiiiiii yarrg Beriilahg dm' s&'q Pesan Rdimia Setiap pesan rahasia k digunakan untuk menandai dua atau lebih pesan-pesan yang hams dibangkitkm secata bebas dengan laimya. Khususriya, setiap pesan raliasia k hams dibangkitkan untuk setiap pesan yang berbeda, dengan kata lain, kunci
tahuia d dapat ditemukan kembali. Catat bahwa jika sebuah generator bilangan pseudorandom atau random yang aman yang digunakan, maka kesempatan untuk membangkitkiw riilai k yang behllang adalah diabaikan. Udtuk melihat bagaimma kunci-kunci rahasia dapat ditemukan kembali jika setiap pesan rahasia diulang, misalkan bahwa setiap pesan rahasia yang sama digunakm untuk membangkitkan tanda- tanda algoritme ECESA, yaitu (r,
sl)
dan (r, sz) pada dua pesan yang
berbeda m~ dan mz. Kernudian sl= E'(el - &) mod n o ksl = el - dr mod
n
dan
1
sz = k- (ez - dr) mod n o & = el - dr mod n, diiana el = h(ml) dan
e2 = h(m2). Pengurmgan dua persamaan tefsebut memberikan k(sl-sz) = el-e2 (mod n). Jika sl
# sz
(mod n), maka terjadi probabilitas yang besar, sehingga k = (sl-sz)-'
(el-ez) (mod n). Jadi seorang lawan dapat menentukan k dan lalu menggunakan ini untuk menemukan d kembdi. 5.2.5
PERTIMBANGAN IMPLEMENTASI
Sebelum penggunaan ECESA, beberapa pilihan dasar harus diperhatikan, yaitu : a) Tentukan lapangan berhingga F, (F, atau F2"). Ada 15 kurva eliptik yang direkomendasikan (tetapi tidak diperintahkan) oleh MST untuk Pemerintalim Federasi h e r i k a Serikat, yaitu sebagai berikut:
-
i. untuk F, adalahp=2192-264-l,p;2724-296+l,p=2256-2224+2192+2%-l,p=2 384
2128-2- %+2-32-1, danp=2521-1; ii. untuk Fzmadalah ~
F z~~~ ~ ', ~.
2 FzU3, ~ ~ ~ 2 ~~ ~ 2 ,dan ~~
,
Faktot-faktoi yang mempengaiuhi pemililian lapangan adalah: i. Lapangan-lapangan akan dipilih, sehingga panjang bit dari order adalah dua kali panjmg kunci d u i penymdian-penyandian blok kunci simevik biasa. Hal ini dikarenakan exhaustive key search dari penyandian blok k bit yang diharapkan memeflukan kifa-kita waktunya sama dengan mlusi dari suatu contoh MLDKE yang menggunakan algoritme Pollard rho mtuk kurva eliptik ymg diseleksl dengan tepat atas lapangm berhingga yang ordernya mempunyai panjang kunci 2k. Hubungan antara panjang kurici petryandian simetrik Ban ukutan lapangan dibefikm pada Tabel 17.
-
Tabel 17. Ukuran lapangan yanp:direkomendasi oleh NIST Panjang bit darip Dimensi m dari Paojang kunci Contoh algoritme penyandhsim& pads FP Fz"' 80 SKlPJACK 192 163 112 Triple-DES 224 233 128 AES Small 256 283 192 AES Medium 384 409 2% AES Large 52 1 571
ii. Untuk lapangan prima F, modular prima p adalah sebuah tipe khusus (disebut bilangan Mamenfie yang digeneralisasi) dimana multiplikasi
modular dapat diselesaikan lebih efisien dilripada yang biasanya. @IPS PUB 186-2, halaman 49).
iii. Untuk lapangan biner Fz", m dipilih sehingga ada sebuah kurva Koblitz yang berorder hampir prima atas Fzm.Karena # E ( F ~membagi #E(Fzm), diiana 1 membagi m, syarat itii menentukai kondisi bahwa m addah prima. b) Representasi Lapangan (misalkan, polinomial atau basis normal untuk Fzm, tidak dibahas dalam tesis ini)
c) Tentukan kurva eliptik E atas F, Kurva yang direkomendasikan oleh NIST adalah i
kurva eliptik tandom atas F,,
ii. kurva eliptik Koblitz atas Fzm; iii. kurva eliptik random atas F2". d) Representasi titik kurva eliptik (misalkan, koordinat @ne atau proyektit). Banyak faktor yaig dapat mempeligrriuhi pilihari yang dibuat. Semua ini hams dipertimbangkan secara keseluruhan dengan tujuan untuk mencapai hasil yang terbaik untuk aplikasi khusus. FWktsr-faktoi tetst:but meliputi: a) Pertimbangan-pertimbangan keamanan. b) Kesesuaian dari metoda-metode yarig tersedia untuk mengoptimalkm aritmatika lapangan berhingga Tujuan keamanan dari dgoritme ECESA
adalah u m k melawan semgan betita yang dipilih (chosen-message atfdck) Tujuan seorang lawan yang melancarkan serangan terhadap suatu entitas A yaag sah adalah untuk memperoleh tanda yang valid pada sebuah p e m m, setelah memperoleh tanda A pada suatu kumpulan pesan (tidak termasuk m) dari pilihan lawan (penjumlahan, petkaliaxi, pemmgkatan, d m kebalikan). c) Kesesuaian dari metodemetoda yang tersedia untuk mengoptimalkan aritmatika k w a eliptik (penjumlahan titik, penggandm titik, dan perkalian skalar). d) Aplikasiplarftm (soylwme, hdwdrt?, atau gabwigan keduanya)
e) Kendala-kendala dari suatu perhitungan khusus (seperti kecepatan prosessor, penyimpaian, ukurm kode, penghitungan gerbang, konsumsi daya).
f) Kendala-kendala dari suatu komunikasi khusus (seperti 1eb:bar pita / bandwidth, waktu tanggapan). 5.2.6
PERTIMBANGAN KEMAMPUAN BEROPERASI Tujuan-tujuan dari standar-standar kriptograft adalah
a) Untuk memfasilitasi penggunaan teknik-teknik kriptografi $ecara luas b) Untuk mempromosikan kemampuan pengoperasian antara implementasiimplementasi yang berbeda Faktor--&tor yang mempengaruhi Kenuunpuan Beroperasi
Kemampuan beroperasi yang dianjurkan adalah dengan menentukan langkahlangkah yang lengkap pada skema kriptografi dan format-format untuk data bersama seperti parameter-parameter domain, kunci-kunci, dan pesan-pesan yang ditubah, serta dengan membatasi jumlah pilihan untuk implementor Untuk ECC dan khususnya ECESA, faktor-faktor yang dapat mempengaruhi dengan h a t kemampuan betoperasi adalah meliputi a) Jumlah dan tipe-tipe dari lapangan berhingga yang disetujui b) JumIah representasi yang disetujui uatuk elemen-elemen dad lapatlgan berhingga yang disetujui c) Jumlah dari kurva eliptik yang disetujui atas lapangan berhingga d) Format-fonnat untuk menentukan elemen-elemen lapangan, titik-titik kufva eliptik, parameter-parameter domain, kunci-kunci publik, dan tandatanda
