Riza Agustiani_rsa

SEMINAR MATEMATIKA

KRIPTOGRAFI KUNCI PUBLIK: SANDI RSA

Oleh: Nama NIM Program Studi Dosen Pembimbing

: Riza Agustiani : 06061008001 : Pendidikan Matematika : Dr. Yusuf Hartono

JURUSAN PENDIDIKAN MIPA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS SRIWIJAYA 2009

KRIPTOGRAFI KUNCI PUBLIK: SANDI RSA

Oleh: Nama NIM Program Studi

: Riza Agustiani : 06061008001 : Pendidikan Matematika

Telah disetujui untuk diseminarkan pada akhir semester genap 2008/2009.

Inderalaya, Mei 2009 Dosen Pembimbing,

Dr. Yusuf Hartono NIP. 131913875

Makalah Koloqium 2009 Riza Agustiani_06061008001

1

KRIPTOGRAFI KUNCI PUBLIK: SANDI RSA Riza Agustiani Mahasiswi Program Studi Pendidikan Matematika e-mail : [email protected]

Abstrak Pembahasan mengenai RSA sudah melebihi dua dekade. Banyak penelitian yang dilakukan untuk menyederhanakan masalah tersebut beberapa tahun belakang ini. Ada yang mencoba untuk ‘menyerang’ atau ‘menerobos’ algoritma yang katanya paling mangkus dalam penyandian tersebut, dan beberapa mencoba untuk menghindarinya. Kekuatan algoritma RSA terletak pada tingkat kesulitan dalam memfaktorkan bilangan non-prima menjadi faktor primanya dan bilangan non-prima yang digunakan dalam enskripsi RSA saat ini umumnya adalah bilangan bulat berukuran besar (long integer). RSA adalah kriptografi yang mempunyai dua jenis kunci, yakni kunci publik dan kunci private (rahasia). Kunci publik adalah kunci yang dikirimkan kepada pengirim pesan dan boleh diketahui oleh orang lain, sedangkan kunci private adalah kunci rahasia yang dibuat oleh si penerima pesan sebelum mengirimkan kunci publik dan hanya diketahui oleh si penerima pesan itu sendiri. Makalah ini berisi penjelasan mengenai algoritma RSA dan pembuktian kebenaran algoritma tersebut, dimana plainteks (pesan) yang dihasilkan pada proses deskripsi sama dengan pesan sebelum proses enskripsi (pesan asli). Tujuan ditulisnya makalah ini adalah untuk memperkenalkan RSA sebagai salah satu kriptografi kunci publik dan membuktikan kebenaran algoritmanya, didalam pembuktiannya digunakan Teorema Euler dan Teorema Fermat. Hasil dari pembuktian algoritma RSA adalah bahwa algoritma RSA menghasilkan plainteks (pesan) yang sama dengan pesan asli, atau dengan kata lain fungsi deskripsi adalah invers dari fungsi enskripsi. Kata Kunci: RSA, algoritma, kunci, enskripsi, deskripsi

Makalah Koloqium 2009 Riza Agustiani_06061008001

2

1. PENDAHULUAN Sebelum

ditemukannya

RSA

Kemudian ubah kembali ke dalam

(dimulai pada massa Julius Caesar),

huruf-huruf, didapat:

untuk menjaga pesan rahasia masih

MDQJDQSHUJL

digunakan metode-metode sederhana untuk menyamarkan pesan.

Dengan membaca hasil penyandian

Contoh: Huruf-huruf dalam pesan

pesan di atas, orang lain tak akan bisa

diubah menjadi angka, sesuai dengan

membaca pesan yang dimaksud tanpa

urutannya dalam abjad, seperti skema

mengetahui metode penyandian/sandi

berikut:

yang digunakan, baik mengenai topik yang sedang dibahas, ruang lingkup

A 0 B 1

pembicaraan, dan sebagainya. Di lain

C2 D3

pihak, metode yang digunakan sangat

dst...

rapi dan dapat dideskripsikan dengan

Kemudian digunakan penyandian

mudah, oleh penerima yang mengetahui

n  n  3 mod 26 ................ (1)

atau

dan angka yang dihasilkan diubah

menyepakati

metode

penyandian/sandi yang digunakan.

menjadi huruf sesuai urutan abjad.

Namun, sejalan dengan kemajuan zaman dan teknologi. Maka, keperluan

Misalnya pesan yang akan dikirim:

akan

JANGAN PERGI

rahasia

Terjemahkan ke dalam angka, menjadi:

Diperlukan sebuah metode baru yang

9 0 13 6 0 13 15 4 17 6 8

lebih menjamin bahwa pesan hanya

(Dalam kriptografi dasar, belum

akan

dikenal mengenai tanda baca dan spasi)

diharapkan.

keamanan

pengiriman

menjadi

sampai

lebih

pada Salah

kompleks.

mereka satu

penyandian yang saat

pesan

yang metode

ini mampu

Dengan menggunakan penyandian (1),

memenuhi kebutuhan tersebut adalah

maka didapat angka baru, yakni:

RSA.

12

16 9 3 16 18 7 20 9 11

Makalah Koloqium 2009 Riza Agustiani_06061008001

3

Sandi RSA merupakan algoritma

memenuhi (x,n) = 1, atau banyaknya

kriptografi kunci publik (asimetris).

elemen x ,0  x  n FPB x , n   1 .

Ditemukan pertama kali pada tahun

Teorema:

1977 oleh R. Rivest, A. Shamir, dan L.

Untuk m dan n bilangan bulat dengan

Adleman. Nama RSA sendiri diambil

FPB(m,n) =1, p dan q bilangan prima,

dari

berlaku:

ketiga

penemunya

tersebut.

Sebagai algoritma kunci publik, RSA

i ( mn )  m  n 

mempunyai dua kunci, yaitu kunci

ii ( p )  p  1

publik

dan

kunci rahasia.

Kunci

iii ( pq )   p  1q  1

publik boleh diketahui oleh siapa

iv ( p e )   p  1 p e1

saja, dan digunakan untuk proses enkripsi (penyandian). kunci rahasia tertentu

hanya

saja

Sedangkan B.

pihak-pihak

yang

”Jika m suatu bilangan bulat positif dan

boleh

(a,m) = 1, maka

mengetahuinya, dan digunakan untuk proses

deskripsi

Teorema Euler

a ( m )  1(mod m ) ”

(penerjemahan).

Keamanan sandi RSA terletak pada

C. Teorema Fermat

sulitnya memfaktorkan bilangan yang

”Jika p suatu bilangan prima dan (k,p)

besar. Sampai saat ini RSA masih

= 1, maka

k p 1  1(mod p )

”

dipercaya dan digunakan secara luas di D. Algoritma Euclid

internet.

Algoritma

ini digunakan untuk

2. MATERI PENDUKUNG

mencari

nilai

pembagi persekutuan

A. Fungsi Phi-Euler

terbesar

dari

Definisi:

Algoritma ini

Banyaknya bilangan bulat positif x

pernyataan berikut ini. Diberikan

kurang dari atau sama dengan n yang

bilangan bulat r0 dan r1 dengan r0 ≥ r1.

dua

bilangan

bulat.

didasarkan

pada

Kemudian dihitung dengan algoritma pembagian. Makalah Koloqium 2009 Riza Agustiani_06061008001

4

r0  q1r1  r2

0  r2  r1

Euclid. Jika FPB(r0,r1) = 1, berarti r-1 =

r1  q2 r2  r3

0  r3  r2

tn. Sehingga rn = tnr1 atau 1 = tnr1.

.... rn 2  qn 1rn 1  rn

0  rn  rn 1

E. Metode Fast Exponentation

rn 1  qn rn

Metode ini

Dari pernyataan di atas di dapat

digunakan

untuk

FPB ( r0 , r1 )

menghitung

 FPB ( r1 , r2 )

besar bilangan bulat modulo dengan

 ...

cepat. Metode

 FPB ( rn  1 , rn )

ekspansi biner dari eksponennya dan

 FPB ( rn ,0 )  rn

didasarkan pada pernyataan berikut ini:

D. Extended Euclide Algorithm Algoritma perluasan

ini

dari

(Extended

merupakan

algoritma

Euclidean

digunakan untuk operasi

Algoritma

ini

i1

ini

memanfaatkan

 

 g2

i

2

....... (3)

Euclide F. Aritmatika Modulo

Algorithm),

mencari

terhadap

g2

operasi pemangkatan

Definisi: a  b (mod n)  n | (a - b)

invers

atau , a = qn + b

pergandaan.

didasarkan

Sifat-sifat:

pada

pernyataan berikut. Diberikan bilangan

i a  a (mod n)

bulat r0 dan r1 dengan r0 ≥ r1. Jika

[Refleksif]

gcd(r0, r1)= 1, maka r -1 mod r0 ada. Jika

ii a  b (mod n)  b  a (mod n)

gcd(r0, r1)≠ 1, maka r-1 mod r0 tidak

[Simetri] iii jika a  b (mod n) dan

ada. Gunakan rumus berikut ini t0  0 , t1  1

b  c (mod n) maka, a  c (mod n)

t j  t j  2  q j 1t j 1 , j  2.......... .......... ...( 2 )

[Transitif] iv jika ac  bc (mod n) dan (c,m)=1,

Ket: q j FPB(r0,r1)

diperoleh dari perhitungan menggunakan

Makalah Koloqium 2009 Riza Agustiani_06061008001

maka a  b (mod n)

algoritma

5

(2) Pilih plainteks m, dengan

3. Materi Pokok

0  m  n  1.

A. Algoritma RSA A.1 Pembentukan Kunci Proses

pembentukan

(3) Hitung c  m b mod n. ............ (6) kunci

ini

(4) Diperoleh chiptekers c, dan

dilakukan oleh pihak penerima, dalam

kirimkan kepada B.

hal ini adalah B. (1) Pilih bilangan prima p dan q.

A.3 Deskripsi

(2) Hitung n = pq.

Deskripsi adalah proses yang

(3) Hitung

dilakukan

( n )   p  1q  1 ................ (4)

oleh

cipherteks,

(4) Pilih sembarang bilangan b,

pihak

yaitu

penerima B

untuk

menerjemahkan cipherteks, ke bentuk

1  b  ( n ) , dengan FPB( b , ( n ))  1.

pesan

sesungguhnya

(asli)

menggunakan kunci private (rahasia).

(5) Hitung invers dari b, yaitu

(1) Ambil kunci publik (n,b) dan kunci

a  b 1 mod ( n ) ...... .........(5)

rahasia a.

(6) Kunci publik: (n,b) dan kunci

(2) Hitung m  c a mod n. ............... (7)

rahasia: a.

Contoh:

A.2 Enskripsi

Agar

Enskripsi atau disebut juga proses

mempermudah

dalam

penyandian adalah proses penyamaran

memahami sandi RSA, pada tulisan

pesan yang akan dikirimkan ke bentuk

ini, plainteks

sandi (chiptekers).

berupa

Enskripsi RSA

yang digunakan hanya

bilangan

0

s/d

29

yang

dilakukan oleh pihak pengirim, dalam

berkorespondensi dengan huruf a s/d z,

hal ini adalah A. Seluruh perhitungan

spasi ( ), koma(,), dan titik (.). Akan

pemangkatan

tetapi

bilangan

modulo

pada

penggunaan

yang

dilakukan menggunakan metode fast

sebenarnya, digunakan korespondensi

exponentiation.

khusus

(1) Ambil kunci publik (n,b).

bilangan-bilangan yang sangat besar.

Makalah Koloqium 2009 Riza Agustiani_06061008001

6

seperti kode ASCII, serta

Tabel 1. Tabel Korespondensi

B memilih p = 7 dan q = 11, maka n = 77. Kemudian, di hitung nilai

Karakater

Bil

Karakater Bil

A

0

P

15

fungsi phi euler dengan persamaan (4).

B

1

Q

16

( 77 )  7  111  1  6 10   60

C

2

R

17

selanjutnya, dapat dipilih 17,

D

3

S

18

karena (17,60)=1.

E

4

T

19

Persamaan (5) diselesaikan dengan

F

5

U

20

menggunakan

G

6

V

21

diperluas, sehingga didapat:

H

7

W

22

a  b 1 mod ( n )

I

8

X

23

J

9

Y

24

Sehingga didapat kunci publik (n,b) =

K

10

Z

25

(77,17) dan kunci rahasia a = 53.

L

11

spasi

26

Kemudian kunci publik dikirim oleh B

M

12

?

27

ke A.

N

13

,

28

O

14

.

29

euclid

a  17 1 mod 60  53

Proses Enskripsi (Oleh A) Misalkan pesan yang akan dikirimkan

Pada pemilihan p dan q harus

berisi:

memenuhi n = pq ≥ 29, karena nilai

”PENYERANGAN DIMULAI

maksimum adalah 29.

JAM TIGA SORE”

A akan memngirim pesan dengan

Hasil korespondensi menggunakan

B. B sebagai penerima pesan akan

Tabel 1, diperoleh:

membuat 2 kunci, kunci pertama adalah

m1 = 15, m2 = 4, m3 = 13, m4 = 24,

kunci publik yang akan dikirimkan ke

m5 = 4, m6 = 17, m7 = 0, m8 = 13,

A (sehingga boleh jadi diketahui orang

m9 = 6, m10 = 0, m11 = 13, m12=26,

lain) untuk proses enskripsi pesan,

m13=3, m14 = 8, m15 =12, m16 = 20,

sedang kunci kedua adalah kunci private yang hanya diketahui oleh B.

Makalah Koloqium 2009 Riza Agustiani_06061008001

algoritma

7

m17 = 11, m18 = 0, m19 = 8, m20 = 26,

Proses Deskripsi (Oleh B)

m21=9, m22=0, m23=12, m24=26,

Setelah

m25=19, m26=8, m27=6, m28=0,

dari A, yaitu : 71-16-62-40-16-19-0-

m29=26, m30=18, m31=14, m32=17,

62-41-0-62-38-75-57-45-48-44-0-57-

m33=4.

38-4-0-45-38-24-57-41-0-38-72-42-19-

Selanjutnya dihitung chiptekers (c)

16, maka diambil kunci rahasia a =

dengan persamaan (6) menggunakan

53,

metode fast exponentation.

menggunakan persamaan (7), masih

B

dan

memperoleh

dilakukan

cipherteks

perhitungan

dengan metode fast exponentiation. Chiptekers M 15 4 13 24 4 17 0 13 6 0 13 26 3 8 12 20 11 0 8

c  m b mod n. 71 16 62 40 16 19 0 62 41 0 62 38 75 57 45 48 44 0 57

Chiptekers m 26 9 0 12 26 19 8 6 0 26 18 14 17 4

c  m b mod n.

massage c

38 4 0 45 38 24 57 41 0 38 72 42 19 16

71 16 62 40 16 19 0 62 41 0 62 38 75 57 45 48 44 0 57

Jadi, chiptekers yang akan dikirim

m  c a mod n. 15 4 13 24 4 17 0 13 6 0 13 26 3 8 12 20 11 0 8

massage c 38 4 0 45 38 24 57 41 0 38 72 42 19 16

m  c a mod n. 26 9 0 12 26 19 8 6 0 26 18 14 17 4

adalah Sehingga, B menerima plainteks :

71-16-62-40-16-19-0-62-41-0-62-3875-57-45-48-44-0-57-38-4-0-45-38-2457-41-0-38-72-42-19-16

Makalah Koloqium 2009 Riza Agustiani_06061008001

8

15-4-13-24-4-17-0-13-6-0-13-26-3-8-

akhir algoritma RSA (setelah enskripsi

12- 20-11-0- 8- 26-9-0-12-26-19-8-6-0-

dan deskripsi),

26-18-14-17-4.

r ' c a mod n

Jika dikorespondensikan sesuai Tabel 1





a

 r b mod n mod n

didapat pesan asli yang dikirmkan:

 r ba mod n Sehingga pesan setelah enskripsi

”PENYERANGAN DIMULAI

(dimisalkan r’) adalah

JAM TIGA SORE”

r ' r ba mod n ....... (10) Akan dibuktikan bahwa:

B. Bukti Algoritma RSA

r '  r ba mod n  r

Dalam pembuktian algoritma RSA ini, akan ditunjukkan bahwa pesan

Untuk mencari nilai ba, digunakan

sebelum enskripsi dan setelah deskripsi

persamaan (5):

adalah sama.

a  b 1 mod  (n)

Cara I:

b 1  a mod  (n)

Misalkan salah satu huruf dalam

misalkan r, kemudian pesan setelah

b  b 1  b  a mod  (n) 1  ba mod  (n)  1  ba mod  (n)  ba  1  k (n).........(11)

enskripsi kita misalkan r’.

Substitusi

Proses Enskripsi (Persamaan 6)

persamaan (10):

c  m b mod n

r'  r ba mod n

pesan yang akan disampaikan adalah R. R dikorespondensi ke dalam angka, kita

   r  r  r  1

m  c a mod n a

r  c mod n.............( 9 ) persamaan

( n ) k

 r  1 mod n

(8)

ke

r

persamaan (9) untuk mendapatkan hasil

Makalah Koloqium 2009 Riza Agustiani_06061008001

 mod n mod nmod n mod n mod n

 r  r ( n) mod n mod n

Proses Desksripsi (Persamaan 7)

Substitusikan

(11)

 r 1k ( n ) mod n

c  r b mod n..............(8)

'

persamaan

9

k

ke

Didapat, bahwa pesan setelah deskripsi

Kasus III, untuk m dapat dibagi oleh

(r’) sama dengan pesan sebelum

salah satu bilangan prima p dan q (n = p

enskripsi (r).

q). Asumsikan m dapat membagi p, artinya m relatif prima q.

Cara II: m  c a mod n

Enskripsi (6) Deskripsi (7)

Substitusikan

persamaan

c  m b mod n

(6)

m 

b a

 mba  m1 k  p 1q 1

ke





k p  1

persamaan (7) untuk mendapatkan hasil

 m mq 1

akhir algoritma RSA (setelah enskripsi

 m 1k  p 1 (Teorema Fermat)  m mod q

dan deskripsi)

m 

b a

 m mod q.......(13) Asumsikan q membagi m, artinya m relatif prima dari p.

     mod n  m  m  mod n  m   m mod n......(12) Akan dibuktikan: m   m mod n a

b

b a

m  m mod n mod n  m b a

b a

m 

b a

 m mod p.......(14) dari (12) dan (13), didapat

b a

m 

b a

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

m 

b a

(Terbukti)

 m ba m

Jadi pesan sebelum enskripsi

1  k ( n )



 m m k ( n )

dan setelah deskripsi adalah sama. Atau



dengan kata

 m1k mod n (Teorema Euler )

4. Kesimpulan Dari

 m mod n

Makalah Koloqium 2009 Riza Agustiani_06061008001

fungsi (proses)

(proses) enskripsi.

Kasus II, untuk m  0 mod n  m  0 mod n  m  m mod n b a

lain,

deskripsi adalah invers dari fungsi

 m mod n

m 

 m mod n

makalah

kesimpulan bahwa:

10

ini

diperoleh

1. Algoritma sandi RSA terdiri dari

3

tahapan,

.pdf. Diakses tanggal 26 januari 2009.

yakni

pembentukan kunci, enskripsi

Sukarman, Herry. 1994. ”Teori Bilangan”. Jakarta: Depdikbud.

dan deskripsi

Zaki.2008. Kriptografi Kunci Publik: Sandi RSA. http://sandi.math. web.id/kssyalgoritma_sandi_rsa.p df. Diakses tanggal 22 Januari 2009.

2. Algoritma sandi RSA dapat ditembus oleh pihak penyerang cukup

memfaktorkan nilai n

menjadi p dan q yang sesuai

.”RSA Made Simple”. http://accu.org/index.php/journals /1495.html. Diakses tanggal 26 Maret 2009.

dengan kunci publik.

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

5. Daftar Pustaka Gunes, Mehmet. “Theory behind RSA”.http://lyle.smu.edu/~rewini/ 5-7339/Mehmet_RSA.ppt. Diakses tanggal 26 Maret 2009. Joyce D.2008. “Cryptography and the number theory behind it”. http://aleph0.clarku.edu/~djoyce/ ma114/crypto.pdf. Diakses tanggal 26 Maret 2009. Krantz, Steven G. 2007.” Zero Knowledge Proofs”. http://www.math.wustl.edu/~sk/sj

Makalah Koloqium 2009 Riza Agustiani_06061008001

11