Presentasi Rsa Riza

SEMINAR MATEMATIKA

Kriptografi Sandi Kunci Publik: RSA Oleh: RIZA AGUSTIANI (06061008001) [email protected] Dosen Pembimbing:

DR. YUSUF HARTONO

Materi Pendukung ✔ Fungsi Phi Euler ✔ Teorema Euler dan Teorema Fermat ✔ Algoritma Euclid ✔ Algoritma Euclid Diperluas ✔ Aritmatika Modulo (Zn) ✔ Metode Fast Exponentation

A. Fungsi Phi Euler Definisi: Banyaknya bilangan bulat positif x kurang dari atau sama dengan n yang memenuhi (x,n) = 1, atau banyaknya elemen . Teorema: ✔ϕ(p) = p-1, untuk p bilangan prima ✔ϕ (m*n) = ϕ (m)* ϕ(n), dengan FPB(m,n) =1 ✔ϕ(p*q) = (p-1)*(q-1), untuk p dan q bilangan prima ✔ϕ(p^e) = (p-1)*p^(e-1)

B. Teorema Euler dan Teorema Fermat ✔Teorema Euler:

”Jika m suatu bilangan bulat positif dan (a,m) = 1, maka a ϕ( m ) ≡ 1(mod m )” ✔Teorema Fermat:

”Jika p suatu bilangan prima dan (k,p) = 1, maka k p −1 ≡ 1(mod p )

”

C. Algoritma Euclid Algoritma ini digunakan untuk mencari nilai pembagi persekutuan terbesar dari dua bilangan bulat. Diberikan bilangan bulat r0 dan r1 dengan r0 ≥ r1 r0 = q1r1 + r2 0 < r2 < r1 r1 = q2 r2 + r3 0 < r3 < r2 .... rn − 2 = qn −1rn −1 + rn 0 < rn < rn −1 rn −1 = qn rn

D. Algoritma Euclid Diperluas Algoritma ini didasarkan pada pernyataan berikut, diberikan bilangan bulat r0 dan r1 dengan r0 ≥ r1. Jika gcd(r0, r1)= 1, maka r-1 mod r0 ada. Jika gcd(r0, r1)≠ 1, maka r-1 mod r0 tidak ada. Gunakan rumus berikut ini: t0 = 0 , t1 = 1

t j = t j − 2 − q j −1t j −1 , j ≥ 2.......................( 1 ) Ket: q j diperoleh dari perhitungan FPB(r0,r1) menggunakan algoritma Euclid. Jika FPB(r0,r1) = 1, berarti r-1 = tn. Sehingga rn = tnr1 atau 1 = tnr1.

E. Aritmatika Modulo (Zn) Definisi: a ≡ b (mod n) ⇔ n | (b - a) atau, a = qn + b Teorema – a ≡ a (mod n) [Reflesif] – a ≡ b (mod n) ⇒ b ≡ a (mod n) [Simetri] – a ≡ b (mod n) and b ≡ c (mod n) ⇒ a ≡ c (mod n) [Transitif] – ac ≡ bc (mod n) dan (c,n)=1 ⇒ a ≡ b (mod n)

F. Metode Fast Exponentation Metode ini digunakan untuk menghitung operasi pemangkatan besar bilangan bulat modulo dengan cepat. Metode ini memanfaatkan ekspansi biner dari eksponennya dan didasarkan pada pernyataan berikut ini:

g

2 i +1

( )

= g

2i

2

Materi Pokok ✔ Algoritma RSA ✔ Bukti Algoritma RSA

A. Algoritma RSA ✔Pembentukan Kunci

1. Pilih bilangan prima p dan q. 2. Hitung n = pq. 3. Hitung ϕ (n) = ( p − 1)( q − 1) 4. Pilih sembarang bilangan b, 1 < b < ϕ( n ) −1 a = b mod ϕ( n ) dengan 5. Hitung invers dari b,yaitu FPB (b, ϕ(n)) =1. . 6. Kunci publik: (n,b) dan kunci rahasia: a.

✔ Enskripsi

1. Ambil kunci publik (n,b). 2. Pilih plainteks r, dengan 0 ≤ r ≤ n − 1. b 3. Hitung c = r mod n. 4. Diperoleh chiptekers c, dan kirimkan kepada B. ✔ Deskripsi 1. Ambil kunci publik (n,b) dan kunci rahasia a. a r = c mod n. 2. Hitung

B. Bukti Algoritma RSA Misal: Pesan yang akan disampaikan ”R” R dikorespondensi ke dalam angka, kita misalkan r. b c = m mod n. ✔Enskripsi: ✔Deksripsi: m = c a mod n. Sehingga, pesan setelah enskripsi (misal r’) adalah r = c a mod n

(

)

a

= r mod n mod n b

= r ba mod n

ab ≡ 1 ( mod ( p − 1)( q − 1) ) ab ≡ 1 ( mod ϕ( n )) ab ≡ 1 + kϕ( n )

r ' = r ba mod n = r ( 1+ k ϕ ( n ) ) mod n

( ( = (r × ( r = ( r × (1

)) mod n ) mod n ) mod n mod n ) ) mod n

= r × r ϕ ( n ) mod n mod n ϕ (n)

k

k

= ( r × 1) mod n = r TERBUKTI ATAU

m = ( ( m b ) mod n ) mod n ≡ ( m b ) mod n a

c = m b mod n m = c mod n a

Akan dibuktikan

⇔ m ≡ (m

)

b a

mod n

a

⇔ ( m b ) ≡ m mod n ( Simetri ) a

(m )

b a

≡ m mod n

Terdapat tiga kasus, Kasus I, untuk m relatif prima dari n, (m, n) = 1.

(m )

b a

≡ mba ≡ m1+ kϕ ( n )

(

≡ m m kϕ ( n )

)

≡ m1k mod n (Teorema Euler ) ≡ m mod n Kasus II, untuk m ≡ 0 ( mod n ) m ≡ 0 ( mod n ) m

(m )

b a

≡ m mod n ≡ m mod n

Kasus III, untuk a dapat dibagi oleh salah satu bilangan prima p atau q. Asumsikan p membagi m, artinya m relatif prima dari q.

(m )

b a

≡ m ba ≡ m1+k ( p −1)( q −1) ≡ m ( m ( q −1) )

k ( p −1)

;

Teorema Fermat

≡ m 1k ( p −1) mod n ≡ m mod q  (i) Asumsikan q membagi a, artinya a relatif prima dari p.

(m )

b a

≡ m mod q  (ii)

dari (i) dan (ii), didapat ( m b ) ≡ m mod n a

Jadi pesan sebelum enskripsi dan setelah deskripsi adalah sama. Atau dengan kata lain, fungsi (proses) deskripsi adalah invers dari fungsi (proses) enskripsi.

Kesimpulan ✔Dari makalah ini diperoleh kesimpulan bahwa: – Algoritma sandi RSA terdiri dari 3 tahapan, yakni pembentukan kunci, enskripsi dan deskripsi – Algoritma sandi RSA dapat ditembus oleh pihak penyerang cukup memfaktorkan nilai n menjadi p dan q yang sesuai dengan kunci publik. – Pesan sebelum enskripsi dan setelah deskripsi adalah sama. Atau dengan kata lain, fungsi (proses) deskripsi adalah invers dari fungsi (proses) enskripsi.

TERIMA KASIH Semoga Bermanfaat....

[email protected]