Mencari Kurva Eliptik pada GF(p) yang tahan Pohlig-Hellman,Smart dan Weil-Tate Pairing Attack

Berikut adalah cara untuk mencari kurva eliptik pada GF (p) yang tidak rentan terhadap serangan Pohlig-Hellman, Smart dan Weil-Tate Pairing.

Sebuah kurva eliptik akan rentan terhadap serangan Pohlig-Hellman jika orde dari titik basepoint yang digunakan bukan bilangan prima, sehingga order-nya dapat difaktorkan. Sedangkan kurva eliptik akan rentan terhadap serangan Smart jika orde dari basepoint yang digunakan sama dengan integer modulo p (orde lapangan hingga kurva eliptiknya). Dan kurva eliptik akan rentan terhadap serangan Weil-Tate Pairing jika orde % (p-1) == 0.

Kardinalitas (cardinality) adalah jumlah titik yang dimiliki oleh kurva eliptik GF(p) biasa ditulis sebagai #GF(p). Dengan integer modulo p adalah orde lapangan hingga kurva tersebut. Orde sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P. Orde ini biasanya dinotasikan dengan n. Kofaktor adalah #GF(p)/n. Sebuah kurva eliptik tidak rentan terhadap serangan Smart jika memiliki kofaktor 1.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Jika ingin memastikan hasilnya sesuai dengan kriteria, maka cek kurvanya di bawah ini. Masukkan modulo integer p yang diperoleh di bawah ini.

Mengecek kerentanan Kurva Eliptik yang dipilih (Masukkan parameter a, b, titik basis dan integer modulo p), nilai a pada kolom a4 dan nilai b pada kolom a5.

Plotting Jumlah Titik R Keluaran Pollard's Rho vs Order (n) pada sebuah ECC

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi sendiri agar dapat mengeluarkan hasil intermediate dari algoritma Pollard's Rho sehingga hasilnya dapat dianalisis lebih mendalam.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Grafik di bawah ini contoh Jumlah titik R keluaran dari Pollards Rho pada sebuah ECC, dengan order berubah-ubah (n < = order max).

Plotting Jumlah Titik Pollard's Rho vs Cardinality (Jumlah titik sebenarnya) pada ECC Parameter Brainpool

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi sendiri agar dapat mengeluarkan hasil intermediate dari algoritma Pollard's Rho sehingga hasilnya dapat dianalisis lebih mendalam.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Plotting Keluaran Titik-Titik Pollard's Rho

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi sendiri agar dapat mengeluarkan hasil intermediate dari algoritma Pollard's Rho sehingga hasilnya dapat dianalisis lebih mendalam.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Pollard's Rho on Sagemath (real version)

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi sendiri agar dapat mengeluarkan hasil intermediate dari algoritma Pollard's Rho sehingga bisa dilakukan analisis lebih mendalam.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Pollard's Rho on Sagemath (own version)

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi sendiri agar dapat mengeluarkan hasil intermediate dari algoritma Pollard's Rho sehingga bisa dilakukan analisis lebih mendalam.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Plot Parameter Modulo (p) dan Order (n) dari Kriptografi Kurva Eliptik

Berikut adalah cara untuk plotting parameter p (modulo) dan n (order) dari kriptografi kurva eliptik.

Hasil dari pencarian parameter kriptografi kurva eliptik yang standar Brainpool atau NIST atau NSA atau CERTICOM akan tetapi dengan modulo yang kecil dapat di-plot untuk menganalisis karakteristik dari kriptografi kurva eliptik..

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.
Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).
Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Jika ingin mem-plotting nilai n vs p dan (p-n) vs p.

Jika ingin plotting dalam satu grafik

Mencari Bilangan Prima

Pohlig-Hellman Attack pada ECDLP GF(p)

Bahan untuk analisis ECC (ECDLP).
Berikut contoh programnya: 

Bahan Analisis ECDH

Bahan untuk analisis ECC (ECDLP) yang digunakan untuk Key Exchange (ECDH).
Berikut contoh programnya: 

Bahan Analisis ECDSA

Public key generation, signature generation dan signature verification

Skenarionya adalah sebagai berikut: 

• Alice ingin menandatangani pesan dengan kunci pribadinya (privKey), dan Bob ingin memvalidasi tanda tangan menggunakan kunci publik Alice (publicKey). Alice harus bisa menghasilkan tanda tangan digital yang sah. Dan setiap orang termasuk Bob harus bisa memeriksa keabsahan tanda tangan yang dibuat Alice.

• Alice dan Bob menggunakan parameter domain yang sama. Algoritma yang digunakan adalah ECDSA (Elliptic Curve Digital Signature Algorithm) yang merupakan varian dari Digital Signature Algorithm yang diterapkan pada Elliptic Curve.

ECDSA bekerja pada hash pesan, bukan pada pesan itu sendiri. Pilihan fungsi hash terserah kita, tapi harus jelas bahwa fungsi hash kriptografi yang dipilih harus aman. Hash dari pesan harus dipotong sehingga panjang bit dari hash sama dengan panjang bit n (n adalah urutan subgroup dari order fungsi Elliptic Curve yang digunakan). Hash terpotong adalah bilangan bulat dan akan dinotasikan sebagai z.

Adapun algoritma yang dilakukan oleh Alice untuk menandatangani pesan adalah sebagai berikut:

• Public key dan signature generation:

1. Pilih sebuah bilangan integer random k (1,...,n-1)
2. Hitung titik P dimana P = k*G (G adalah titik Generator yang dipilih)
3. Hitung r = xP mod n  (xP adalah koordinat x dari titik P)
4. Jika r = 0 maka pilih k yang lain dan ulangi kembali
5. Hitung \(s =k^{-1}\left(z+ r*privKey\right)\bmod n\) dimana privKey  adalah Private Key Alice, \(k^{-1}\) adalah invers perkalian dari k mod n
6. Jika s = 0 maka pilih nilai k yang lain dan ulangi kembali.

Pasangan (r,s) adalah Signature-nya.

• Signature verification. Untuk memverifikasi tanda tangan digital Alice, kita memerlukan kunci publik Alice , hash dan tanda tangan digitalnya (signature) yaitu (r, s)

1. Hitung nilai \(u_{1}=s^{-1}z \bmod n\)
2. Hitung nilai \(u_{2}=s^{-1}r \bmod n\)
3. Hitung nilai titik P dengan cara  \(P = u_{1}G+u_{2}publicKey\)
4. Signature valid jika r = xP mod n

Pembuktian kebenaran algoritma tersebut sebagai berikut :

\(P = u_{1}G+u_{2}publicKey\) dan,

publicKey = privKey*G

sehingga:

\(P = u_{1}G+u_{2}publicKey\)

\(P = u_{1}G+u_{2}*privKey*G\)

\(P = (u_{1}+u_{2}*privKey)G\)

Dengan nilai \(u_{1}=s^{-1}z \bmod n\) dan \(u_{2}=s^{-1}r \bmod n\), kita dapatkan:

\(P = (u_{1}+u_{2}*privKey)G\)

\(P = (s^{-1}z+s^{-1}*r*privKey)G\)

\(P = s^{-1}(z+r*privKey)G\)

Dari nilai  \(s =k^{-1}\left(z+ r*privKey\right)\bmod n\) di atas, kalikan persamaan tersebut dengan k dan bagi dengan s sehingga didapat:
 \(k =s^{-1}\left(z+ r*privKey\right)\bmod n\) lalu substitusikan persamaan ini dengan persamaan P di atas sehingga didapatkan:
\(p = s^{-1}(z+r*privKey)G\)
\(P=kG\)

Berikut contoh programnya: 

Mencari nilai k pada ECC GF(p) menggunakan Pollard's Rho

• ECC adalah Elliptic Curve Cryptography.  Kurva yang digunakan di sini yaitu y^2 = x^3 + ax + b.
• GF adalah Galois Field.
• p adalah Bilangan Prima (Prime)

Pada Kriptografi ECC, sebuah titik base P akan digunakan sebagai dasar untuk membangkitkan titik-titik yang lain. Q = k.P

Q (x,y) adalah titik-titik lain tersebut. koordinat x dari titik Q biasanya akan dipilih menjadi kunci publik sedangkan k adalah bilangan skalar (integer positif) akan menjadi kunci privat. Untuk menghitung Q yaitu dengan mengalikan k dengan P sangat mudah, akan tetapi jika titik Q diketahui dan P juga diketahui maka sangat susah sekali untuk mencari berapa nilai k. Inilah yang disebut sebagai ECDLP (Elliptic Curve Discrete Logarithm Problem).

Gunakan program di bawah ini untuk mencari contoh Kurva yang tepat

Mencari nilai k pada ECC GF(p) menggunakan Brute Force

Dalam ilmu komputer, brute-force search, juga dikenal sebagai exhaustive search, adalah teknik pemecahan masalah yang sangat umum dan paradigma algoritmik yang terdiri dari penghitungan secara sistematis semua kandidat k yang mungkin menjadi solusi dan memeriksa apakah masing-masing kandidat merupakan solusi dari permasalahan tersebut atau bukan.

• ECC adalah Elliptic Curve Cryptography.  Kurva yang digunakan di sini yaitu y^2 = x^3 + ax + b.
• GF adalah Galois Field.
• p adalah Bilangan Prima (Prime)

Pada Kriptografi ECC, sebuah titik base P akan digunakan sebagai dasar untuk membangkitkan titik-titik yang lain. Q = k.P

Q (x,y) adalah titik-titik lain tersebut. koordinat x dari titik Q biasanya akan dipilih menjadi kunci publik sedangkan k adalah bilangan skalar (integer positif) akan menjadi kunci privat. Untuk menghitung Q yaitu dengan mengalikan k dengan P sangat mudah, akan tetapi jika titik Q diketahui dan P juga diketahui maka sangat susah sekali untuk mencari berapa nilai k. Inilah yang disebut sebagai ECDLP (Elliptic Curve Discrete Logarithm Problem).

Mencari Bilangan Prima

Mencari k dari ECC GF(p) menggunakan Algoritma Baby Step Giant Step

ECC adalah Elliptic Curve Cryptography. Kurva yang digunakan di sini yaitu y^2 + a1*xy + a3*y = x^3 + a2*x^2 + a4*x + a5. GF adalah Galois Field. p adalah Bilangan Prima (Prime).

Pada Kriptografi ECC, sebuah titik base P akan digunakan sebagai dasar untuk membangkitkan titik-titik yang lain. Q = k.P

Q (x,y) adalah titik-titik lain tersebut. koordinat x dari titik Q biasanya akan dipilih menjadi kunci publik sedangkan k adalah bilangan skalar (integer positif) akan menjadi kunci privat. Untuk menghitung Q yaitu dengan mengalikan k dengan P sangat mudah, akan tetapi jika titik Q diketahui dan P juga diketahui maka sangat susah sekali untuk mencari berapa nilai k. Inilah yang disebut sebagai ECDLP (Elliptic Curve Discrete Logarithm Problem).

Mencari Bilangan Prima

Mencari Orde Base Point Pada ECC GF(p)

ECC adalah Elliptic Curve Cryptography.  Kurva yang digunakan di sini yaitu y^2 = x^3 + ax + b.
GF adalah Galois Field.
p adalah Bilangan Prima (Prime)

Pada Kriptografi ECC, sebuah titik base P akan digunakan sebagai dasar untuk membangkitkan titik-titik yang lain. Q = k.P
Q (x,y) adalah titik-titik lain tersebut. koordinat x dari titik Q biasanya akan dipilih menjadi kunci publik sedangkan k adalah bilangan skalar (integer positif) akan menjadi kunci privat. Untuk menghitung Q yaitu dengan mengalikan k dengan P sangat mudah, akan tetapi jika titik Q diketahui dan P juga diketahui maka sangat susah sekali untuk mencari berapa nilai k. Inilah yang disebut sebagai ECDLP (Elliptic Curve Discrete Logarithm Problem).

Orde (Order) adalah banyaknya jumlah titik-titik (misal kita sebut titik Q)  yang dihasilkan dari perkalian bilangan skalar k dengan titik base (misal. titik P digunakan sebagai base point)  yang  termasuk titik 0 (infinity). Jika orde dikalikan dengan titik base (P) maka akan menghasilkan titik infinity. Jadi bisa juga disebut, orde adalah bilangan skalar yang membuat titik Q = 0 (tapi bilangan skalar tersebut bukan bilangan 0). Besarnya order ini akan menentukan tingkat keamanan dari kunci private (k). Berikut adalah cara mencari Orde dari sebuah titik pada ECC GF(p) dengan kurva elips y^2 = x^3 + ax + b.

Mencari Bilangan Prima

Mencari Nilai k pada ECDLP (Q = kP)

Eksperimen Pollard's Rho New Collision dengan Contoh 4 p(211)

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi new collision paper Neamah.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Eksperimen Pollard's Rho New Collision dengan Contoh 3 p(1303)

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi new collision paper Neamah.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).

Eksperimen metode Pollard's Rho new collision contoh 2

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi new collision paper Neamah.

Order sebuah titik P pada kurve eliptik GF(p) adalah banyaknya jumlah titik yang dapat dibangkitkan dari titik P sebagai basepoint. Q = k*P.

Q adalah titik-titik yang dibangkitkan (akan menjadi publik key) sedangkan P adalah titik basis-nya. Lalu k adalah bilangan skalar (integer) yang akan menjadi private key  (0 < k < p).

Kurva eliptik yang digunakan  \(y^2 + a_{1}xy + a_{3}y = x^3 + a_{2}x^2 + a_{4}x + a_{5}\).