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}\).

Eksperimen Pollard's Rho New Collision dengan Contoh 1

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}\).

Berikut ini adalah perhitungan deteksi dan kinerjanya

Pollard's Rho on Sagemath (new collision version)

Berikut adalah contoh Pollard's Rho Attack yang dibuat dengan versi new collision Neamah. Keluarannya dapat menghasilkan nilak k yang dicari dan banyaknya iterasi yang dibutuhkan.

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}\).

Aplikasi Alat Bantu Tesis - Mengecek orde kurva eliptik (Contoh 2)

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

Aplikasi Alat Bantu Tesis - Mengecek Orde Kurva Eliptik (Contoh 1)

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