Elliptic Curve Cryptography

Welcome

“Belajar dan Berbagi Ilmu” itulah yang menginspirasi saya untuk lebih mempermudah orang lain untuk saling berbagi dan belajar bersama. Meski karya ini sederhana, semoga bisa membantu siapapun yang membutuhkan referensi untuk “Belajar dan Berbagi Ilmu” khususnya yang berkaitan dengan Matematika, Keamanan Informasi (Information Security) yang berkaitan dengan Kriptografi (cryptography), terutama Kriptografi atau Kriptosistem Kurva Elliptic (Elliptic Curve Cryptosystems), salah satunya adalah ElGamal Elliptic Curve Cryptography.

All about: Matematika (Mathemathics), Kriptografi (Cryptography), Kurva Elliptic (Ellptic Curve), ElGamal, Kriptosistem Kurva Elliptik (Elliptic Curve Cryptosystems), ElGamal Elliptic Curve Cryptography, Field, Finite Field serta topik lain yang relevan dengan Kriptografi dan Matematika.

Kriptografi Kurva Elliptic

Tahun 1985, Koblitz dan Miller mengenalkan kriptografi kurva elliptic (elliptic curve cryptography) yang menggunakan masalah logaritma diskrit pada titik kurva elliptic. Kriptografi kurva elliptic dapat digunakan untuk beberapa keperluan seperti skema enkripsi (contohnya ElGamal ECC), tanda tangan digital (contohnya ECDSA) dan protokol pertukaran kunci (contohnya Diffie-Hielman ECC).

Stallings [13] mendefinisikan kurva elliptic sebagai suatu kurva yang dibentuk oleh persamaan kubik dan memiliki persamaan umum
$\large y^{2}+Axy\: =\: x^{3}+Cx^{2}+Dx+E\; \; \; (4.1)$
$\large y^{2}+Axy\: =\: x^{3}+Cx^{2}+Dx+E\; \; \; (4.1)$

dengan A,B,C,D dan E adalah konstanta bilangan real. Domain x dan y adalah bilangan real ( $\large \mathbb{R}$ ). Dalam penulisan ini, tidak dibahas mengenai persamaan (4.1). Untuk mendukung tujuan penulisan ini, penulis akan menjelaskan bentuk kurva yang lebih sederhana dari persamaan (4.1), yaitu

$\large y^{2}\: =\: x^{3}+Ax+B\; \; \; (4.2)$

dengan A dan B dalam $\large \mathbb{R}$ serta x, y $\large \in$ $\large \mathbb{R}$ .

Gambar 4.1 merupakan salah satu contoh bentuk geometri dari kurva elliptic dengan persamaan $\large y^{2}\: =\: x^{3}+x+1$ . Setiap kurva elliptic akan berbentuk simetris terhadap sumbu x atau garis y=0. Karena untuk setiap nilai x $\large \in$ $\large \mathbb{R}$ , terdapat sepasang nilai y $\large \in$ $\large \mathbb{R}$ yang memenuhi persamaan (4.2), yaitu

$\large y_{1}=+\sqrt{x^{3}+Ax+B}$ dan $\large y_{2}=-\sqrt{x^{3}+Ax+B}$ .

Kurva elliptic juga dapat dipandang sebagai suatu himpunan yang terdiri dari titik-titik (x,y) yang memenuhi persamaan (4.2). Himpunan tersebut dinotasikan dengan E(A,B). Untuk setiap nilai A dan B yang berbeda, dihasilkan himpunan E(A,B) yang berbeda pula. Sebagai contoh, kurva dalam Gambar 4.1 dan Gambar 4.2.

gbr-4-1
Gambar 4.1. Kurva Elliptic $\large y^{2}\: =\: x^{3}+x+1$

gbr-4-2
Gambar 4.2. Kurva Elliptic $\large y^{2}\: =\: x^{3}-x$

Source:
wan.khudri.com

Jenis-Jenis Kriptografi

Berdasarkan jenis kuncinya, algoritma kriptografi dapat dibagi menjadi dua kelompok yaitu algoritma simetri (konvensional / private key algorithm) dan algoritma asimetri (public key algorithm). Menurut Kurniawan [9], algoritma simetri adalah algoritma yang menggunakan kunci enkripsi yang sama dengan kunci dekripsinya. Pada algoritma ini, pengirim dan penerima harus menyetujui suatu kunci tertentu yang dinamakan kunci rahasia (secret key). Contohnya adalah DES (Data Encryption Standard), Rijndael, Blowfish dan lain-lain. Sedangkan algoritma asimetri didesain sedemikian sehingga kunci yang digunakan untuk enkripsi berbeda dengan kunci untuk dekripsi. Kunci yang digunakan untuk enkripsi disebut kunci publik (public key) dan dapat diketahui oleh orang lain. Sedangkan kunci untuk dekripsi dinamakan kunci rahasia atau sering disebut sebagai private key dan hanya diketahui oleh pemiliknya. Contohnya adalah ElGamal, RSA (Rivest-Shamir-Adleman), ECC (Elliptic Curve Cryptography) dan lain-lain.

Istilah “kunci rahasia” pada algoritma simetri digunakan untuk menyatakan kunci enkripsi sekaligus kunci dekripsi dan disebut secret key. Sedangkan pada algoritma asimetri, kunci rahasia hanya digunakan untuk menyatakan kunci dekripsi dan sering disebut sebagai private key. Hal ini dapat mengakibatkan kesalahan penafsiran pada istilah “kunci rahasia”. Karena itu, untuk pernyataan-pernyataan berikutnya digunakan istilah aslinya.

Menurut Purbo dan Wahyudi [11], saat ini terdapat tiga macam public key algorithm yang aman dan efisien berdasarkan permasalahan matematis, yaitu Integer Factorization Problem (IFP), Discrete Logarithm Problem (DLP) dan Elliptic Curve Discrete Logarithm Problem(ECDLP).

Jika diberikan bilangan bulat n yang merupakan hasil kali dua buah bilangan prima p dan q sehingga n=p.q, maka permasalahan matematis dalam IFP adalah mencari faktor dari n , yaitu p dan q. Contohnya adalah RSA.

DLP merupakan masalah yang didefinisikan pada aritmetika modular. Misalkan dipilih bilangan prima p dan diberikan bilangan bulat g (0<g<p-1) serta y merupakan pemangkatan dari g, sehingga $y=g^{x}\;(mod\; p)$ . Permasalahan matematis dalam DLP adalah mencari x, jika diberikan pasangan bilangan g dan y. Contohnya adalah ElGamal, Diffie-Hellman, DSA (Disgital Signature Algorithm).

Jika F_p himpunan lapangan berhingga ( finite field ) , p bilangan prima,

P(x_P,y_P) titik pada kurva elliptik, dipilih V secara random sehingga Q=V.P. Permasalahan matematis dalam ECDLP adalah mencari V, jika diketahui titik P dan Q. Contohnya adalah ElGamal ECC (ElGamal Elliptic Curve Cryptography), ECDSA (Elliptic Curve Digital Signature Algorithm).

Algoritma ECC menggunakan ECDLP dan dikenalkan pertama kali oleh Koblitz dan Miller pada tahun 1985. ECC dapat digunakan untuk beberapa keperluan seperti skema enkripsi (contohnya ElGamal ECC), tanda tangan digital (contohnya ECDSA) dan protokol pertukaran kunci (contohnya Diffie Hellman ECC). Salah satu hal yang menarik mengenai ECC terletak pada tingkat keamanannya. ECC dapat menggunakan ukuran kunci yang lebih kecil dibandingkan dengan kriptografi lainnya dan memiliki tingkat keamanan yang sama. Kemampuan ini membuat ECC mempunyai keamanan yang terkuat dengan panjang kunci terpendek. Sebagai perbandingan, 160 bit ECC mempunyai tingkat keamanan yang sama dengan 1024 bit RSA atau DSA dan 224 bit ECC memiliki tingkat keamanan yang sama dengan 2048 bit RSA atau DSA [6,9,11].

Kemampuan dan keamanan ECC ini yang membuat penulis tertarik untuk mengkaji lebih dalam tentang salah satu skema enkripsinya, yaitu ElGamal ECC (ElGamal Elliptic Curve Cryptography) dan membuat program aplikasinya.

Source:
wan.khudri.com