Kriptografi RSA

RSA merupakan algoritma kriptografi asimetri, dimana kunci yang digunakan untuk mengenkripsi berbeda dengan yang digunakan untuk mendekripsi. Kunci yang digunakan untuk mengenkripsi disebut dengan kunci public, dan yang digunakan untuk mendekripsi disebut dengan kunci privat. RSA adalah salah satu algoritma kriptografi yang menggunakan konsep kriptografi kunci publik. RSA membutuhkan tiga langkah dalam prosesnya, yaitu pembangkitan kunci, enkripsi, dan dekripsi. Proses enkripsi dan dekripsi merupakan proses yang hampir sama. Jika bilangan acak yang dibangkitkan kuat, maka akan lebih sulit untuk melakukan cracking terhadap pesan. Parameter kuat tidaknya suatu kunci terdapat pada besarnya bilangan acak yang digunakan.

Apa itu RSA?

Algortima RSA dijabarkan pada tahun 1976 oleh tiga orang : Ron Rivest, Adi Shamir dan Len Adleman dari Massachusetts Institute of Technology. Huruf '''RSA''' itu sendiri berasal dari inisial nama mereka (‘R’ivest - ‘S’hamir – ‘A’dleman). Clifford Cocks, seorang matematikawan Inggris yang bekerja untuk GCHQ, menjabarkan tentang sistem equivalen pada dokumen internal di tahun 1973. Penemuan Clifford Cocks tidak terungkap hingga tahun 1997 karena alasan ''top-secret classification''. Algoritma RSA dipatenkan oleh Massachusetts Institute of Technology pada tahun 1983 di Amerika Serikat sebagai US patent 4405829. Paten tersebut berlaku hingga 21 September 2000. Setelah bulan September tahun 2000, paten tersebut berakhir, sehingga saat ini semua orang dapat menggunakannya dengan bebas.

RSA adalah sebuah algoritma berdasarkan skema kriptografi public-key. Lebih jauh, RSA adalah algoritma yang mudah untuk diimplementasikan dan dimengerti. algoritma RSA adalah sebuah aplikasi dari sekian banyak teori seperti extended Euclid algorithm, euler's function sampai fermat theorem.

Konsep fundamental dari Kriptografi Kunci Publik ditemukan oleh Whitfield Diffie dan Martin Hellman, dan secara terpisah oleh Ralph Merkle. Sedangkan konsep dasar Kriptografi Kunci Publik terletak pada pemahaman bahwa kunci selalu berpasangan: kunci enkripsi dan kunci dekripsi. Juga perlu diingat bahwa sebuah kunci tidak dapat dibangkitkan dari kunci lainnya. Pemahaman kunci enkripsi dan dekripsi sering disebut sebagai kunci publik dan kunci privat. Seseorang harus memberikan kunci publiknya agar pihak lain dapat mengenkripsi sebuah pesan. Dekripsi hanya terjadi jika seseorang mempunyai kunci privat.

Dasar Matematika

1. Sifat Pembagian pada Bilangan Bulat

Diberikan dua buah bilangan bulat a dan b dengan syarat a ≠ 0. Dikatakan a habis membagi b (a divides b) jika terdapat bilangan c sedemikian hingga b = ac.

Notasi : a | b jika b = ac, c ϵ Z dan a ≠ 0.

Contoh :

4 | 12 karena 12 = 4 × 3

Teorema Euclidean :

Misalkan m dan b adalah dua buah bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka terdapat dua buah bilangan bulat unik q (quotient) dan r (remainder) sedemikian sehingga m = nq + r dengan 0 ≤ r < n.

Contoh :

1987 = 97 × 20 + 47, yaitu 1987 dibagi dengan 97 memberikan hasil 20 dan sisa 47

2. Pembagi Bersama Terbesar

Diberikan dua buah bilangan bulat tidak nol a dan b. Pembagi bersama terbesar (greatest common divisor atau gcd) dari a dan b adalah bilangan bulat terbesar d sedemikian hingga d | a dan d | b, atau dinyatakan dengan gcd(a,b) = d.

Contoh :

Faktor pembagi 45 adalah : 1, 3, 5, 9, 15, 45

Faktor pembagi 36 adalah : 1, 2, 3, 4, 6, 9, 12, 18, 36

Faktor pembagi bersama dari 45 dan 36 adalah : 1, 3, 9

Sehingga gcd(45, 36) = 9

3. Algoritma Euclidean

Dengan dasar Teorema Euclidean sebelumnya, dikembangkan sebuah algoritma (yang disebut dengan algoritma Euclidean) untuk mencari gcd dari dua buah bilangan bulat.

Definisi :

Diberikan dua buah bilangan bulat tak negative a dan b (a ≥ b). Maka terdapat q_i, r_i ϵ Z sehingga :

 

 

Jadi r_m+1 = gcd(r_m, r_m+1) = gcd(r_m-1, r_m) = gcd(r_m-2, r_m-1) = … = gcd(a, b)

 

Contoh :

a = 80, b = 12, dan dipenuhi syarat a ≥ b

Dihitung dengan menggunakan algoritma Euclidean sbb. :

 

Jadi gcd (80, 12) = gcd (12, 8) = gcd (8,4) = 4

4. Algoritma Euclidean yang Diperluas

Algoritma Euclidean yang diperluas dapat digunakan untuk menentukan bilangan bulat positif b < a memiliki invers (terhadap operasi perkalian) modulo a dengan memeriksa jika rm+1 = 1.

Definisi :

Diberikan qj seperti pada Algoritma Euclidean, didefinisikan

 

 

Berdasarkan pada q_j hasil algoritma Euclidean dan pendefinisian t_j dan s_j diperoleh hubungan r_j, t_j, dan s_j yang diberikan oleh :

Teorema :

Jika j = 0, 1, 2, …, m maka r_j = s_ja + t_jb dengan t_j dan s_j seperti yang didefinisikan dan r_j diperoleh di Algoritma Euclidean.
Akibat :
Jika gcd (a, b) = 1, maka b^-1 = t_j

Contoh :

a = 111, b = 25

Dengan menggunakan algoritma Euclidean dicari j dan dihitung apakah gcd (111, 25) = 1.

111 = 4 × 25 + 11  j=1
25 = 2 × 11 + 3      j=2
11 = 3 × 3 + 2        j=3
3 = 1 × 2 + 1          j=4
2 = 1 × 2                j=5

Dari algoritma Euclidean sebelumnya diketahui jika gcd (111, 25) = 1, maka :

t₀ = 0
t₁ = 1
t₂ = t₀ – q₁t₁ = 0 – 4 × 1 = -4
t₃ = t₁ – q₂t₂ = 1 – 2 × (-4) = 9
t₄ = t₂ – q₃t₃ = -4 – 3 × 9 = -31
t₅ = t₃ – q₄t₄ = 9 – 1 × (-31) = 40

Maka 25^-1 terhadap modulo 111 adalah 40.

5. Kekongruenan

Definisi Aritmatika Modulo :
Diberikan dua buah bilangan bulat a dan m yang > 0. Operasi a mod m memberikan sisa jika a dibagi dengan m. Bilangan m disebut modulus atau modulo, dan hasil aritmatika modulo m terletak di himpunan {0, 1, … m-1}
Notasi : a mod m = r, sedemikian sehingga a = mq + r, dengan 0 ≤ r < m.
Contoh :
23 mod 5 = 3
-41 mod 9 = 4
Definisi Kongruen :
Diberikan dua buah bilangan bulat a dan b, dan m adalah bilangan > 0, maka a ≡ b (mod m) jika m habis membagi a – b.
Contoh :

17 ≡ 2 (mod 3)
Kekongruenan a ≡ b (mod m) dapat pula dituliskan dalam hubungan
a = b + km
untuk k adalah sembarang bilangan bulat. Berdasarkan definisi aritmatika modulo,
a mod m = r dapat juga dituliskan sebagai
a ≡ r (mod m)

Teorema :

1. Jika a ≡ b (mod m) dan c adalah sembarang bilangan bulat positif maka
• ( a + c) ≡ (b + c) (mod m)
• ac ≡ bc (mod m)
• a^p ≡ b^p (mod m) untuk suatu bilangan bulat tak negative p.
2. Jika a ≡ b (mod m) dan c ≡ d (mod m), maka
• (a + c) ≡ (b + d) (mod m)
• ac ≡ bd (mod m)

6. Bilangan Prima

Bilangan bulat positif p (p>1) disebut bilangan prima jika pembaginya hanya 1 dan p. Bilangan selain bilangan prima disebut dengan bilangan komposit.

The Fundamental Theorem of Arithmetic :

Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

Contoh :

91 = 7 × 13

100 = 2 × 2 × 5 × 5

Terdapat banyak metode yang dapat digunakan untuk menguji keprimaan sebuah bilangan. Salah satunya adalah Teorema Eratosthenes.

Teorema Eratosthenes :

Untuk setiap bilangan komposit n, pasti ada bilangan prima p dimana p ≤√n sehingga p | n.

Dari teorema tersebut, dapat kita simpulkan jika p tidak membagi habis n, maka n bukan bilangan komposit (dengan kata lain n adalah bilangan prima).

Contoh :

1.  n = 1993 prima?

1993 = 44.6430…

p ≤ 44.6430…. = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, dan 43

Karena tidak ada p yang dapat membagi habis n, maka n bukanlah bilangan komposit. Sehingga 1993 adalah bilangan prima. 

2. n = 121

121 = 11

p ≤ 11 = 2, 3, 5, 7, dan 11

7

Karena 11 | 121 maka n merupakan bilangan komposit. Sehingga 121 bukan bilangan prima.

 

7.  Relatif Prima

Dua buah bilangan bulat a dan b dikatakan relative prima jika gcd (a, b) = 1. Jika a dan b relative prima, maka terdapat bilangan bulat a dan b sedemikian sehingga ma + nb = 1.
Contoh :

gcd (111, 25) = 1
m(111) + n(25) = 1, untuk m = -9 dan n = 40, maka
(-9)(111) + (40)(25) = -999 + 1000 = 1

8. Fungsi Euler (ϕ)

Fungsi Euler mendefinisikan ϕ(n) untuk n ≥ 1 yang menyatakan banyaknya bilangan bulat positif < n yang mempunyai invers terhadap operasi perkalian.
Contoh :

Z8 = {0, 1, 2, 3, 4, 5, 6, 7}
ϕ(8) = 4, karena yang memiliki invers hanya 1, 3, 5, 7.

Teorema (untuk mencari ϕ(n)) :

 

 

 

 Contoh :

n = 8
m = 1, p1 = 2, e1 = 3
ϕ(8) = (23 - 22) = 8 – 4 = 4

Teorema 1 :
Jika n = pq adalah bilangan komposit dengan p dan q prima, maka ϕ(n) = ϕ(p) ϕ(q) = (p-1) (q-1).
Teorema 2 :
Diberikan dua buah bilangan bulat a dan n, dengan n ≥ 2 sedemikian sehingga gcd(a, n) = 1, maka
a^ϕ(n) ≡ 1 (mod n)

Algoritma RSA

RSA merupakan algoritma kriptografi asimetri, dimana kunci yang digunakan untuk mengenkripsi berbeda dengan yang digunakan untuk mendekripsi. Kunci yang digunakan untuk mengenkripsi disebut dengan kunci public, dan yang digunakan untuk mendekripsi disebut dengan kunci privat.
Algoritma RSA didasarkan pada teorema Euler yang menyatakan bahwa

a_ϕ(n) ≡ 1 (mod n)

dengan syarat a harus relative prima terhadap n.

Berdasarkan teorema-teorema yang ada pada bahasan kekongruenan sebelumnya, bisa kita peroleh :

a^ϕ(n) ≡ 1 (mod n)
Berdasarkan a^p ≡ b^p (mod m) :

≈ ak^ϕ(n) ≡ 1k (mod n)
a diganti dengan m :

≈ mk^ϕ(n) ≡ 1k (mod n)
Kedua ruas dikalikan dengan m :

≈ mk^ϕ(n)+1 ≡ m (mod n) (kedua ruas dikali dengan m)
(pers. 1)
Misal e dan d dipilih sedemikian hingga ed = 1 (mod n) atau ed = k^ϕ(n) + 1.
Maka disubsitusikan ke pers.1 :
med ≡ m (mod n)
(me)d ≡ m (mod n)
Persamaan diatas dapat diartikan perpangkatan m dengan e diikuti dengan perpangkatan dengan d menghasilkan kembali m semula. Maka berdasarkan persamaan tersebut, enkripsi dan dekripsi pada RSA dapat dirumuskan sebagai berikut :

E_e(m) = m^e (mod n) = cD_d(c) = c^d (mod n)

1. Algoritma Pembangkitan Kunci pada RSA

Kelebihan RSA terletak pada pasangan kunci yang digunakan untuk mengenkripsi dan mendekripsi pesan. Berikut langkah-langkah yang digunakan untuk membangkitkan pasangan kunci di RSA :

1. Pilih dua buah bilangan prima sembarang p dan q.
2. Hitung n = p * q, dengan p ≠ q.
3. Hitung ϕ(n) = (p-1)(q-1)
4. Pilih kunci public e, yang relative prima terhadap ϕ(n).
5. Bangkitkan kunci privat d = 1+ k ϕ(n) / e atau d = e^-1 (1 + k.ϕ(n)).

Hasil dari algoritma diatas adalah :
1. Kunci public (n, e)
2. Kunci privat (d)

2. Algoritma Enkripsi dan Dekripsi

Algoritma enkripsi pada RSA adalah sebagai berikut :

1. Ambil kunci public milik penerima pesan (n dan e).
2. Pecah plainteks menjadi blok-blok m₁, m₂, …, sedemikian sehingga setiap blok merepresentasikan nilai di dalam selang [0, n-1].
3. Setiap blok mi dienkripsi menjadi blok c_i dengan rumus c_i = m_i^e mod n

Untuk mendapatkan plainteks kembali, blok cipherteks ci didekripsi menjadi blok m_i dengan rumus m_i = c_i^d mod n.

 

Kriptanalisis

Sisi keamanan pada sistem RSA terletak pada sulitnya memfaktorkan sebuah bilangan besar n yang dihasilkan dari perkalian dua buah bilangan prima p dan q. nilai n yang dihasilkan bersifat tidak rahasia, sementara nilai bilangan prima p dan q harus bersifat rahasia, sehingga hampir mustahil bagi seorang penyerang untuk mendapatkan nilai ϕ (n) (totien (n)atau disebut juga phi(n)) yang merupakan nilai bilangan dasar yang digunakan untuk menghasilkan pasangan kunci publik e dengan kunci privat d.

Secara umum, tipe serangan yang mungkin untuk algoritma RSA adalah:

1. Brute Force
2. Mathematical Attack
3. Man-In-The-Middle Attack
4. Choosen Ciphertext Attack

Related Posts:

Tweet