MATEMATIKA MATEMATIKA PERSANDIANPERSANDIAN

HendraHendra GunawanGunawan, Ph.D., Ph.D.CBSED CBSED -- ITBITB

Saya menerima pesan dari seorang Saya menerima pesan dari seorang teman berupa rangkaian bilangan teman berupa rangkaian bilangan sebagai berikut:sebagai berikut:

64, 43, 82, 55, 133, 95, 140, 97, 3, 2, 64, 43, 82, 55, 133, 95, 140, 97, 3, 2, 46, 31, 95, 65, 46, 31, 123, 85, 40, 2746, 31, 95, 65, 46, 31, 123, 85, 40, 27

AdakahAdakah yang yang bisabisa membantumembantu sayasayamengartikanmengartikan pesanpesan tersebuttersebut??

TemanTeman sayasaya telahtelah melakukanmelakukan pepe--nyandiannyandian atauatau pengkodeanpengkodean terter--hadaphadap pesanpesan yang yang inginingin disampaidisampai--kannyakannya kepadakepada sayasaya, , daridari rangkairangkai--an an hurufhuruf keke rangkaianrangkaian bilanganbilangansepertiseperti didi atasatas, , supayasupaya pesanpesan terter--sebutsebut tidaktidak dapatdapat ((dengandengan mudahmudah) ) dimengertidimengerti oleholeh orangorang lain.lain.

PenyandianPenyandian atauatau pengkodeanpengkodean meme--rupakanrupakan suatusuatu bentukbentuk penyimpanpenyimpan--an an dan/ataudan/atau pengirimanpengiriman data/ data/ informasiinformasi secarasecara rahasiarahasia. .

Julius CaesarJulius Caesar telahtelah melakukanmelakukanpengkodeanpengkodean untukuntuk keperluankeperluan suratsuratmenyuratmenyurat padapada jamannyajamannya ((lebihlebihdaripadadaripada 2000 2000 tahuntahun yang yang lalulalu).).

Yang Yang iaia lakukanlakukan adalahadalah menggesermenggesersetiapsetiap hurufhuruf dalamdalam suratsurat yang yang akanakandikirimnyadikirimnya, , misalnyamisalnya 5 5 langkahlangkah kekedepandepan::

A A menjadimenjadi F, F, B B menjadimenjadi G,G,

. . . , . . . , dandanZ Z menjadimenjadi E.E.

UntukUntuk mengirimmengirim pesanpesan yang yang berkataberkata

SAYA AKAN PULANG LUSASAYA AKAN PULANG LUSA

Julius Caesar akan menulisJulius Caesar akan menulis

XFDF FPFS UZQFSL QZXF.XFDF FPFS UZQFSL QZXF.

Untuk memahaminya, geser kembali Untuk memahaminya, geser kembali setiap huruf 5 langkah ke belakang.setiap huruf 5 langkah ke belakang.

Untuk dapat memecahkan suatu Untuk dapat memecahkan suatu pesan yang telah disandikan kita pesan yang telah disandikan kita harus mengetahui sistem persandiharus mengetahui sistem persandi--an yang dipakai. Jika sistemnya an yang dipakai. Jika sistemnya adalah mengggeser setiap huruf 5 adalah mengggeser setiap huruf 5 langkah ke depan, maka untuk langkah ke depan, maka untuk memahami pesan yang telah dimemahami pesan yang telah di--sandikan kita harus menggeser sesandikan kita harus menggeser se--tiap huruf 5 langkah ke belakang.tiap huruf 5 langkah ke belakang.

Kembali ke pesan yang saya terima, Kembali ke pesan yang saya terima, saya dan teman saya telah menyesaya dan teman saya telah menye--pakati sebelumnya bahwa kami pakati sebelumnya bahwa kami akan menggunakan sebuah matriks akan menggunakan sebuah matriks untuk penyandian. untuk penyandian. MatriksMatriks yang yang kamikami pakaipakai adalahadalah

M = M = ⎥⎦

⎤⎢⎣

⎡5273

BagaimanaBagaimana temanteman sayasaya melakukanmelakukanpenyandianpenyandian dengandengan matriksmatriks iniini? ?

PertamaPertama iaia ubahubah pesanpesan yang yang inginingindisampaikannyadisampaikannya menjadimenjadi rangkaianrangkaianbilanganbilangan dengandengan aturanaturan::

spasispasi=0, A=1, B=2, C=3,. . ., Z=26.=0, A=1, B=2, C=3,. . ., Z=26.

SetelahSetelah ituitu iaia menyusunmenyusun rangkaianrangkaianbilanganbilangan yang yang diperolehnyadiperolehnya menjadimenjadisebuahsebuah matriksmatriks dengandengan duadua barisbaris, , duadua bilanganbilangan pertamapertama disimpandisimpan didikolomkolom pertamapertama, , dandan seterusnyaseterusnya. . SebutlahSebutlah matriksmatriks yang yang diperolehnyadiperolehnyaX. X. LaluLalu, , iaia hitunghitung hasilhasil kali MX. kali MX. BilanganBilangan--bilangan dalam matriks MX bilangan dalam matriks MX ini diuraikan kembali menjadi rangini diuraikan kembali menjadi rang--kaian bilangan yang ia kirimkan.kaian bilangan yang ia kirimkan.

IntermezoIntermezo: : PerkalianPerkalian duadua MatriksMatriks

HasilHasil perkalianperkalian barisbaris keke--1 1 padapadamatriksmatriks pertamapertama dandan kolomkolom keke--1 1 padapada matriksmatriks keduakedua samasama dengandenganelemenelemen padapada barisbaris keke--1 1 kolomkolom keke--1 1 padapada matriksmatriks didi ruasruas kanankanan::

3(1) + 7(2) = 17.3(1) + 7(2) = 17.

⎥⎦

⎤⎢⎣

⎡=⎥

⎦

⎤⎢⎣

⎡⎥⎦

⎤⎢⎣

⎡4057

26123717

65

43

21

.5273

BerbedaBerbeda dengandengan perkalianperkalian duaduabilanganbilangan, , perkalianperkalian duadua matriksmatriks tidaktidakbersifatbersifat komutatifkomutatif. . SecaraSecara umumumum,,

M.N M.N ≠≠ N.M.N.M.

UntukUntuk meyakinkanmeyakinkan diridiri, , cobalahcobalahambilambil duadua matriksmatriks 2 x 2, 2 x 2, sebutsebut M M dandanN, N, lalulalu hitunghitung M.N M.N dandan N.M.N.M.

MatriksMatriks bujursangkarbujursangkar, , sepertiseperti M =M =33 7722 5 5

mempunyaimempunyai inversinvers MM--11 ==5 5 --77

--22 33yang yang berbersifatsifat: M.M: M.M--11 = I = M= I = M--11.M,.M,didi manamana I I adalahadalah matriksmatriks identitasidentitas

11 0000 11

LaluLalu bagaimanabagaimana sayasaya dapatdapat meme--mecahkanmecahkan pesanpesan taditadi? ? MudahMudah sajasaja. . SayaSaya tinggaltinggal melakukanmelakukan kebalikankebalikandaridari apaapa yang yang telahtelah temanteman sayasayalakukanlakukan, , daridari langkahlangkah terakhirterakhirsampaisampai langkahlangkah pertamapertama. . PertamaPertama, , sayasaya susunsusun rangkaianrangkaian bilanganbilangan didiatasatas menjadimenjadi sebuahsebuah matriksmatriks (yang (yang tddtdd 2 2 barisbaris), ), sebutlahsebutlah

64 82 133 140 364 82 133 140 3 46 95 46 123 4046 95 46 123 4043 55 95 97 243 55 95 97 2 31 65 31 85 2731 65 31 85 27

KemudianKemudian sayasaya kalikankalikan Y Y dengandengan MM--11

daridari kirikiri ((janganjangan daridari kanankanan karenakarenaperkalianperkalian matriksmatriks tidaktidak komutatifkomutatif):):

5 5 --77 64 82 133 140 3 46 95 46 123 4064 82 133 140 3 46 95 46 123 40--2 3 43 55 95 97 2 31 65 31 85 272 3 43 55 95 97 2 31 65 31 85 27

Y=

19 25 0 19 25 0 21 1 13 20 13 20 1121 1 13 20 13 20 111 1 191 1 19 11 0 1 5 1 9 111 0 1 5 1 9 1

Lalu saya susun bilanganLalu saya susun bilangan--bilangan bilangan dalam matriks di atas menjadi dalam matriks di atas menjadi rangkaian bilangan di bawah inirangkaian bilangan di bawah ini

19, 1, 25, 1, 0, 19, 21, 11, 1, 0, 13, 1, 19, 1, 25, 1, 0, 19, 21, 11, 1, 0, 13, 1, 20, 5, 13, 1, 20, 9, 11, 1.20, 5, 13, 1, 20, 9, 11, 1.

Dengan mudah saya dapat membaca Dengan mudah saya dapat membaca rangkaian bilangan ini sebagairangkaian bilangan ini sebagai

SAYA SUKA MATEMATIKA.SAYA SUKA MATEMATIKA.

Mungkin ada yang bertanya, bagaiMungkin ada yang bertanya, bagai--mana kalau kita menerima sebuah mana kalau kita menerima sebuah pesan yang telah disandikan tetapi pesan yang telah disandikan tetapi kita tidak tahu sistem persandian kita tidak tahu sistem persandian yang digunakan oleh si pengirim?yang digunakan oleh si pengirim?

Mungkin kita dapat mengutakMungkin kita dapat mengutak--atik atik dan memecahkan sandi tersebut. dan memecahkan sandi tersebut. Seandainya kita tidak tahu apa yang Seandainya kita tidak tahu apa yang telah dilakukan oleh Julius Caesar telah dilakukan oleh Julius Caesar sebelum ia mengirim pesan tadi, sebelum ia mengirim pesan tadi, tidak terlalu sulit bagi kita (yang tidak terlalu sulit bagi kita (yang hidup di era komputer) untuk mehidup di era komputer) untuk me--mecahkan maksud pesan tersebut.mecahkan maksud pesan tersebut.

Sistem persandian yang kita pakai Sistem persandian yang kita pakai tentunya harus sedemikian rupa tentunya harus sedemikian rupa sehingga jika informasi yang kita sehingga jika informasi yang kita simpan atau kirim jatuh ke tangan simpan atau kirim jatuh ke tangan orang lain, maka sulit bagi orang orang lain, maka sulit bagi orang tersebut untuk memahaminya. tersebut untuk memahaminya. Untuk sistem persandian menggunaUntuk sistem persandian mengguna--kan matriks, semakin besar ukuran kan matriks, semakin besar ukuran matriks yang digunakan, semakin matriks yang digunakan, semakin sulit sandi untuk dipecahkan.sulit sandi untuk dipecahkan.

Selain menggunakan matriks, masih Selain menggunakan matriks, masih banyak perangkat lain yang dapat banyak perangkat lain yang dapat digunakan untuk persandian. digunakan untuk persandian.

Persandian yang cukup canggih dan Persandian yang cukup canggih dan banyak dipakai di kalangan agen banyak dipakai di kalangan agen rahasia sekarang ini biasanya merahasia sekarang ini biasanya me--manfaatkan bilanganmanfaatkan bilangan--bilangan bilangan primaprimayang besar sekali.yang besar sekali.

Gagasannya sederhana: Jika kita Gagasannya sederhana: Jika kita punya dua buah bilangan prima, punya dua buah bilangan prima, maka mudah bagi kita untuk mengmaka mudah bagi kita untuk meng--hitung hasil kalinya. Tetapi sebalikhitung hasil kalinya. Tetapi sebalik--nya, jika kita punya sebuah bilangan nya, jika kita punya sebuah bilangan komposit (yang merupakan hasil kali komposit (yang merupakan hasil kali dari sejumlah bilangan prima), maka dari sejumlah bilangan prima), maka sulit bagi kita untuk memfaktorkansulit bagi kita untuk memfaktorkan--nya, apalagi jika bilangan tersebut nya, apalagi jika bilangan tersebut besar sekali. besar sekali.

SebagaiSebagai contohcontoh, , dengandengan mudahmudah kitakitadapatdapat menghitungmenghitung

257 x 65.537 = 16.843.009.257 x 65.537 = 16.843.009.

TetapiTetapi cobacoba faktorkanfaktorkan bilanganbilangan didibawahbawah iniini::

4.294.967.297.4.294.967.297.

JawabJawab: 4.294.967.297 = 641 x 6.700.417: 4.294.967.297 = 641 x 6.700.417..

Jadi,Jadi, dengan menggunakan fakta ttg dengan menggunakan fakta ttg bilangan prima tsb, mudah bagi kita bilangan prima tsb, mudah bagi kita untuk membuat sandi, namun sulit untuk membuat sandi, namun sulit bagi orang untuk memecahkan sandi bagi orang untuk memecahkan sandi kita, kecuali bila mereka tahu sistem kita, kecuali bila mereka tahu sistem persandian yang kita pakai. Gagasan persandian yang kita pakai. Gagasan ini dicetuskan oleh Ron ini dicetuskan oleh Ron RivestRivest, Adi , Adi ShamirShamir, dan Len , dan Len AdlemanAdleman. Sistem . Sistem persandian mereka dikenal sebagai persandian mereka dikenal sebagai teknik RSAteknik RSA..

TeknikTeknik RSA RSA menggunakanmenggunakan sebuahsebuahbilanganbilangan kompositkomposit N (N (besarbesar) ) dandanbilanganbilangan kuncikunci penyandipenyandi r. r. PasanganPasanganbilanganbilangan N N dandan r r dikenaldikenal sebagaisebagaipublic keypublic key. .

SelainSelain keduakedua bilanganbilangan tersebuttersebut, , terter--dapatdapat bilanganbilangan kuncikunci pemecahpemecah s s untukuntuk memecahkanmemecahkan sandisandi. . BilanganBilanganiniini tergantungtergantung padapada r.r.

SebagaiSebagai ilustrasiilustrasi, , kitakita gunakangunakan N = N = 33 (= 3 x 11) 33 (= 3 x 11) dandan r = 7. [r = 7. [BilanganBilangan r r dipilihdipilih didi antaraantara 1, 1, ……, 20. , 20. DiDi sinisini 20 20 = (3 = (3 –– 1) x (11 1) x (11 –– 1).]1).]

UntukUntuk menyandikanmenyandikan hurufhuruf B (= 2), B (= 2), kitakita hitunghitung 2277 mod(33) = 29.mod(33) = 29.JadiJadi sandisandi untukuntuk hurufhuruf B B adalahadalahbilanganbilangan 29.29.

BilaBila kitakita menerimamenerima sandisandi 29, 29, makamakapesanpesan aslinyaaslinya adalahadalah 2 (= B). 2 (= B). TetapiTetapibagaimanabagaimana kitakita bisabisa mendapatkanmendapatkanbilanganbilangan 2 2 daridari 29, 29, dengandengan mengmeng--gunakangunakan bilanganbilangan N = 33 N = 33 dandan r = 7?r = 7?(N (N dandan r r diketahuidiketahui sbgsbg public keypublic key.).)DalamDalam halhal iniini, , kitakita harusharus mengetahuimengetahuibilanganbilangan kuncikunci pemecahpemecah s.s.

BilanganBilangan kuncikunci pemecahpemecah s s didi sinisiniadalahadalah bilanganbilangan yang yang memenuhimemenuhi

rsrs = 1 mod (20).= 1 mod (20).

UntukUntuk r = 7, r = 7, kitakita dapatkandapatkan s = 3.s = 3.Sandi 29 Sandi 29 kitakita terjemahkanterjemahkan sebagaisebagai

292933 mod(33) = 2.mod(33) = 2.

DenganDengan menggunakanmenggunakan N = 33 N = 33 dandanr = 7 (r = 7 (dandan, , tentutentu sajasaja, s = 3), , s = 3), cobacobapecahkanpecahkan sandisandi berikutberikut::

7, 1, 26, 2, 0, 15, 13, 0, 30, 21, 20.7, 1, 26, 2, 0, 15, 13, 0, 30, 21, 20.

RangkaianRangkaian bilanganbilangan iniini harusharus diterditer--jemahkanjemahkan sbgsbg rangkaianrangkaian bilanganbilangan didi{0, 1, {0, 1, …… , 32}. , 32}. DiDi sinisini 0 = 0 = spasispasi, 1 = , 1 = A, A, dstdst (27 (27 s/ds/d 32 32 tidaktidak terpakaiterpakai).).

SekadarSekadar informasiinformasi, , cabangcabang ilmuilmumatematikamatematika yang yang mempelajarimempelajaripersandianpersandian adalahadalah kriptografikriptografi((to to encriptencript = = membuatmembuat sandisandi).).

DiDi negaranegara kitakita, , terdapatterdapat LembagaLembagaSandi NegaraSandi Negara yang yang menanganimenanganipersandianpersandian untukuntuk keperluankeperluan negaranegara. . LembagaLembaga iniini bernaungbernaung didi bawahbawahDepartemenDepartemen PertahananPertahanan..

28, 1, 19, 4, 1, 3, 0,28, 1, 19, 4, 1, 3, 0,11, 26, 14, 26, 19, 21, 0,11, 26, 14, 26, 19, 21, 0,

12, 1, 13, 3, 0,12, 1, 13, 3, 0,14, 1, 17, 21, 5, 0,14, 1, 17, 21, 5, 0,

31, 26, 4, 1, 5.31, 26, 4, 1, 5.