ISSN 1410-1335
[NT'f,qML MAJALAHILMIAHMATEMATIKADANILMUPENGETAHUANALAM
VOLUME 7 NO.
1,
APRIL
2OO2
ALAM FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN UNIVERSITAS KATOLIK PARAHYANGAN
lntegral
Vol.7
No.1
Halaman
1-56
Bandung, Aoril 2002
ISSN 1410-1 335
daftar isi Daftar lsi Editorial The Rivest,
Adleman 1 (RS$ PublicShamir, Key Cryptosystem
,Arrum*-ffiu WD/rewffi
And Cyclic Codes Marjono
t7 INTEGRAL adalah majalah
bertujuan menyediakan
yang
sarana
perkembangan Matematika dan llmu Pengetahuan Alam
.r
serta penerapannya, khususnya untuk bidang Matematika, Fisika, Ilmu Komputer, dan bidang interdisiplin yang terkait.
TNTECSAL (rSSN t4l0-1335) diterbitkan dua kali setahun : April dan Oktober oleh Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas
Katolik Parahyangan.
L*".
R. Gunawan Santosa
?? -^
Mengkonstruksi Fungsi Green Persamaan Diferensial Llnler Orde-n lwan Sugiarto
2
j
lntegral Monte Carlo FerryJaya Permana
Penghantaran r?,R \) Mekanisme Dalam Neuron
Fakultas MIPA
Universitas Katolik Parahyangan Jl. Ciumbuleuit 94 Bandung 40141 Telp. (022) 204 1964 ext.707 / ext.70t Fax .022 ?04 2l4l E-mail :
[email protected] Website : http:/ftrome.unpar.ac.idl-integraV
dan
7 tL Dua Metode Pembuktian 5 ' Teorema Cayley
-)A
Alamat redaksi
:
J.J. Siang
komunikasi ilmiah untuk meningkatkan
apresiasi terhadap
Bilangan Prima Perkembangan Aplikasinya
(Neurontransmisi) Adi Gunawan M. S.
++
|,:HJ'"ins
sebasai solusl
Veronica S. Moertini
Editorial
m[Tu@&AL Melalui Vol.
7 No I Edisi April 2002 ini,
II{TBQRAL
mengawali tahun 2002 dengan menyajikan 7 makalah yang ditulis oleh para staf dosen dan mahasiswa dari Universitas
Penanggung Jawab Dekan FMIPA Unpar
Katolik Parahyrngan Bandung, Universitas Duta Wacana Yogya Yogyakarta, Universitas lmmanuel Yogyakarta, dan Universitas Brawijaya Malang. Ketujuh makalah terscbut terdiri dari 5 makalah dalam bidang matematrka, I makalah dalam bidang biofisika dan I makalah dalam brdang llnru Komputer.
Dua makalah pertama dalam II{TEQRAL kali ini membahas
Dewan Penyunting Dr. A. Rusli (Ketua) Prof. B. Supraplo Brotosiswojo Prof. Dr. S. M. Nababan R. M. Suroso, Drs., M.Sc. Dr. dr. Oerip S. Santoso
Penyunting Pelaksana Paulus Cahyono Tjiang, SSi, PhD (Ketua) Ferry Jaya Permana,,lSi, Msi
Sylvia Hastuti Sutanto, SSi, PhD Henry P. Panggabean, ST
sisi yang berbeda dari sistem enkripsi yang diciptakan pada tahun 1978 oleh Ron Rivest, Adi Shamir dan Len Adleman, yang dikenal sebagai system enkripsi RSA. Makalah pertama oleh Marjono membahas aplikasi struktur aljabar pada sistem tersebut, sedangkan makalah ke dua olch J J Siang membahas perkembangan bilangan prima dan aplrkasinya pada sistem enkripsi RSA
Salah satu teorema yang berperan pcnting dalam teori graf adalah Teorema Cayley, yang merupakan teorema yang menggunakan sifat khusus graf yang disebut pohon (tree). R. Gunawan Santosa menyajikan dua pembuktian teorcma ini, yaitu dengan korespondensi l -l antara pohon berlabel (labeled tree) dan barisan, serta dengan Teori Kombinatorial
lwan Sugiarto dalam makalah ke empat memperkenalkan
metoda pembcntukan fungsi
(ireen bagi
persamaan
differensial linear ordc-n, Fungsi Creen ini bcrperan besar dalam menentukan solusi sebuah persamaan differensial linear orde-n.
Tata Usaha Lltalip
Pranyoto Teguh Imanto Yulius Ralu
Makalah ke lima oleh Ferry J. Permana membahas tentang penggunaan Integral Montc Carlo dalam nrenghitLrng integral
tentu sembarang. Metoda ini merupakan pendckatan secara numerik, khususnya bagi integral yang tidak dapat diketahui anti{urunannya secara eksak. Makalah ke enam bertemakan biofisika oleh Adi Cunawan M. S., mengulas tentang mekanisme penghantaran dalam neuron, yang merupakan bagian penting dalam mekanisme saraf.
Dan makalah ke tujuh oleh Veronica S. Moertini membahas tentang teknologi data mining dari segi kegunaan, cara kerja, beberapa metodologi yang berkaitan dengan teknologi ini, serta bagaimana teknologi ini diterapkan untuk menjamln sustainability dari sebuah bisnis,
Akhirnya, kami berharap semoga para pembaca
dapat
menarik manfaat dari makalah-makalah yang disajikan.
Dont*wRel,a*,*
BIIANGAN PRITIA: PENKEMBANGAN DAN APUKASINVA Intisari prima, Dalam tulisan ini dipaparkan mengenai seiarah penemuan bilangan dalam aplikasinya satu salah pengujran bilangai prima besar, serta kriptografi yaitu metode RSA Abstract
This
paper explain about the history and developments of prime numbers'
primitity
testing and irs application in cryptography, RSA method
Diterima:6 Maret2002 Disetujui untuk dipublikasikan : 8 Maret 2002
prima. Cara yang paling efisien untuk mencari bilangan prima kecil (misalkan Bilangan prima adalah bilangan bulat >l yang hanyr habis dibagi I dan bilangan -sendiri. Manusia telah mengenal itu bilangan prima sejak 6500 SM. Tulang lshango yang ditemukan Pada tahun Musee 1960 (sekarang disimPan Brussels) d'Histoire Naturelle tersebut. Tulang membuktikan
hal
di
di
Ishango memiliki 3 baris takik. Salah satu folomnYa memiliki ll, 13, 17, dan 19 takik, Yang meruPakan bilanganbilangan prima antara l0 hingga 20'
Meskipun sedikit sekali manfaat yang
kurang
dari l0')
adalah
manggunakan metode
dengan
Seive
of
Eratosthenes (240 SM) sebagai berikut:
Daftarkanlah semua bilangan bulat antra 2 hingga n, HaPuslah semua bilangan kelipatan bilangan prima yang lebih kecil atau sama dengan
fi ' U"t,
bilangan yang masih tersisa
adalah
bilangan prima. Sebagai contoh, untuk mencari semua didaftarkan semua bilangan bulat antara 2 hingga 30.
diketahui, namun di awal masehi orang tetap mencari dan membuktikan bahwa
sualu bilangan meruPakan
bilangan
ll 12 13 14 15 2 3 4 5 6 7 8 9 lo 26 27 28 29 30 h 18 l9 20 zt 22.'23 24 25
16
bilangan kelipatan 2' Bilangan pertama (= 2) adalah bilangan prima. Hapuskan semua Didapat
ll 13 15 t7 19 21 23 2s 27
tltTf,€RAL vol.
7 no. 1, APril 2002
29
Bilangan prima setelah 2 dalam daftar tersebut adalah 3, yang merupakan bilangan prima kedua. Hapus semua bilangan kelipatan 3 dari daftar. Didapat
ll 13 l7 l9 23 25
29
Bilangan setelah 3 yang belum terhapus adalah 5. Hapus semua bilangan dalah daftar yang merupakan kelipatan 5 sehingga didapat
13 t7 19 23
ll
Bilangan yang tidak terhapus berikutnya adalah 7 yang kuadratnYa : 49 > 30. Maka bilangan yang tersisa dalam daftar merupakan himpunan semua bilangan
29
merupakan bilangan gasal sehingga pada
metode Sieve sangatlah mudah, cepat
jaman dahulu orang percaya bahwa untuk suatu bilangan prima P, maka 2e-1 juga merupakan bilangan prima. Narnun kemudian terbukti hal tersebut tidak benar. Pada tahun 1536, Regius
dan sederhana. Bahkan prosesnya tidak menggunakan operasi pembagian sama
bukanlah bilangan prima karena 2047
prima S
30,
Pencarian bilangan Prima
dengan
sekali, Pencarian sccara langsung dengan menjalankan Pro$am di komputer bahkan lebih cePat
membuktikan
bahwa ztt-l -
2047
*
23r89 Mersenne (1588
-
1648) menemukan
dibandingkan dengan membaca daftar bilangan prima yang tersimpan dalam
bahwa bilangan
disket, Akan tetapi untuk kePerluan enkripsi yang membutuhkan bilangan
7, 13, 17, 19, 31, 67, 127, dan 257,
prima yang besar, metode Sieve dirasa tidak memadai.
Sebelum komputer
ditemukan,
perkembangan penemuan bilangan prima masih lambat karena orang belum
?P-l
meruPakan
bilangan prima hanya untuk P =
2,3,5,
Meskipun ternyata kemudian terbukti bahwa apa yang ditemukan Mersenne ini salah, tapi bentuk 2o-l (Yang kemudian dikenal dengan bilangan Mersenne) tetap menarik perhatian
merasakan manfaatnYa. Tabel 1 menunjukkan daftar Penemu tabel bilangan prima sebelum era komputer. Meskipun sederhana, tabel tersebut menolong ahli matematika lain untuk pertama kali menebak teorema bilangan
Pertanyaan yang terus ingin dijawab adalah : Pada kondisi apakah bilangan
prima.
tahun 1930.
Tahun l 588
t7'12 r
883
l9l I l9l4 Tabel
I
Penemu Cataldi Euler Pervushin
Jumlsh Dlelt
Powers
Powers
Mersenne Mp : 2o-l merupakan bilangan prima ? Lucas menemukan syarat perlu dan cukupnya pada tahun
1870 dan Lehmer mengujinya
Uji Lucas - Lehmer
:
Pada
Untuk bilangan
6
gasal p, bilangan Mersenne 2p-l adalah
t0 27
bilangan pnma bila dan hanya bila 2' *llS(p - 1) dengan S(n+l)
33
(S(n))2
l9
-2
dan
S(l):4.
: Penemu Tabel Bilangan Prima Sebelum Era KomPuter
INTEGRAL vol. 7 no. l, APril 2002
Dengan bantuan komputer, pengujian bilangan prima yang besar dengan uji LucasLehmer menjadi semakin mudah sehingga bilangan-bilangan prima besar ditemukan, seperti yang tampak pada tabel 2. Tahun
Penemu
1952
Robinson Robinson Robinson Robinson Robinson
t952 1952 1952
t952
96l
Rieiel Hurwitz Hurwitz
963 I 963 I 963
Gillies Gillies Gillies
t957
t96t r
I
p
Jumlah Dlglt dalam Mp
s2t
t57
60'l t279
r83 386 664 687
2203 2281 3217
969
l28l
4253 4423
1332 2917
9689
9941 r
2993 3316 6002
l2l3
197 I
Tuckerman
19937
978 1979
Noll & Nickel Noll
21701 23209
r979
Nelson & Slowinski Slowinski
u497
6533 6987 I 3395
86243
25962
I 10503 132049 216091 756839 859433
33265
I
1982 I 988 I 983 r 985 1992 1994
1996 1996 1997
998
I
1999
Colquitt & Welsh Slowinski Slowinski Slowinsk & Gaee Slowinsk & Gaee Slowinski & Gaee Armensaud. Woltman. et al Spence. Woltman. et al Clarkson, Woltrnan, Kurowski, et al Hairatwala. Woltman. Kurowski, et al
t97sl 65050
227832 258716 378632
t257787
42092t
I 398269 2976221
895932 909526
302t17'.t 6972593
2098960
Tabel2 : Penemu Tabel Bilangan Prima Mersenne
Sulitnya menemukan bilangan prima besar menjadi masalah utama bagi praktisi kriptografi karena penggunaan bilangan prima merupakan syarat mutlak dalam implementasinya. Padahal secara
praktis,
kadang-kadang
hanya
dibutuhkan bilangan yang "mendekati" prima, Bilangan semacarn itu disebut bilangan prima semu (pseudo prime). '
aP'= a (mod p). Secara khusus, jika bukan faktor p, rnaka aPr = I (mod p).
Teorema Little Fermat memberikan uji
yang baik untuk
t l, maka n bukan prima. Sebaliknya, jika bilangan Jika hasilnya
hasilnya = l, maka n mungkin bilangan prima sehingga n disebut bilangan prima semu basis a.
dari teorema Little Fermat
Sebagai contoh,
berikut
:
p
adalah bilangan prima dan a adalah sembarang bilangan bulat, maka
Jika
UI"[E€BA|- vol. 7 no. l, April2002
ketidakprimaan.
Dengan diberikan bilangan bulat n > l, pilihlah a > I dan hitung a"-l (mod n),
Bilangan prima semu bisa didapatkan sebagai
a
a: 2 dan n = 341) (2')'o = (2'o mod 341;3a = l3o untuk
341, maka 23ar-r (mod
(mod
341)
mod 341
= l.
Akan tetapi 341 bukan bilangan prima L.r.n" 3+t = ll*31, sehingga l4l 2' adalah bilangan prima semu basis
Terdapat lebih dari lOe buah bilangan lebih kecil dari 25*10e' tapi "t,r.'*rg buah bilangan prima 21.853 iau l"nr.
s.*u
basis
2. Ini
berarti
bahwa
semu oersentase menjadi bilangan prima prima' jauh lebih kecil dari bilangan
KrtPtoirafi Kunci Publik Xriptografi adalah teknik untuk *"nyuiluttun suatu pesan Kriptografr meiiputi enkripsi, yaitu transformasi data' ke bentuic Yang tidak mungkin JiUuru pihak lain tanPa mengetahui
kuncinya, serta dekiPsi, . YTg yaitu
*"-ptk*
kebalikan dari enkripsi,
mengembalikan data Yang ditralsio*-.ti ke bentuk semula. Baik enkripsi maupun dekipsi selalu membutuhkan suatu informaii rahasia yang disebut kunci.
Berdasarkan sifat kuncinya, terdapat 2
ienis kriptografi yaitu
kriptografi
mengolahnYa. Keadaan
ini
simetris (kunci rahasia) dan kriptogafi drng"n kunci publik. Dalam kriptografi sama dipakai dalam simltris, kunciyang 'dekripsi sehingga baik dan enkripsi informasi penerima maupun pengirim 't untuk yang sama kunci memitiki ur.is daPat
digambarkan dalam gambar I '
A Gambar
I
: Skema Enkripsi pada Kriptografi Simetris
m Misalkan A hendak mengirim Pesan
Pesan m dienkriP dengan menggunakun 'kunci e menjadi c' pesan sandi c dikirimkan Selaniutnya -g. ketiga
oada
B.
Ada kemungkinan pihak Lir" *rrnp"rolph pesan sandi c' Tetapi ia tidak blsa membacanya karena tidak yang mengetahui kunci pembukanya' B
pada
,"niri.u
Pesan sandi
c
daPat
d membukanYa dengan kunci Pembuka hal Dalam e)' dari bisa diturunkan
[ang
l0
ini, baik A mauPun B harus sama-sama memiliki kunci L (dan d), dan kunci ini
tidak boleh diketahui pihak
ketiga'
kriptogtlfl
l"lgT
jika A dan Kelemahan metode ini adalah temPat di Yang berlauhan B tinggal dikomunikasikan harus e kunci sehing!-a lewaiiredia (telpon, surat, internet' dls) yang kemungkinan tidak aman' Sebaliknya, dalam
tun"i putlit,
penerima memiliki 2 buah
INTEGRAL, vol. 7 no. 1, APril 2002
kunci yaitu kunci publik dan
kunci
gambar 2. Misalkan A mengirim pesan A mengenkrip pesan asli
rahasia. Kunci publik bisa diketahui oleh banyak orang, tetapi kunci rahasia hanya
pada B, maka
diketahui oleh penerima saja. Bahkan pengirirnpun tidak mengetahui kunci rahasia sehingga tidak bisa mendekrip kembali pesan yang telah dienkripnya.
mengirimkannya pada B. Selanjutnya B mendekrip pesan yang diterimanya dengan kunci rahasia (= d) yang hanya diketahuinya sendiri.
Keadaan
ini
dengan kunci publik
(= e)
dan
dapat digambarkan dalam
d = kuncl rahasia
A
B
Gambar 2 : Skema Enlnipsi pada Kriptografi dengan Kunci Publik
Keuntungan utama metode ini adalah tidak diperlukannya media komunikasi antara A dan B untuk menentukan kunci rahasia sehingga keamanannya dapat lebih terjamin. Jika B hendak membalas
pesan m' pada A, maka ia
4.2
Enkripsi Dengan Metode RSA
Kriptografi kunci publik yang paling terkenal adalah metode RSA (Rivest,
Shamir dan Adleman).
Kuncinya
akan
dibentuk dari sepasang bilangan prima
mengenkripnya dengan menggunakan kunci publik e' yang ditentukan A. A
(dalam prakteknya sering dipakai bilangan prima semu yang besar),
akan mendekripnya dengan rahasia
kunci
d'. Kunci rahasia d tidak sama
dengan d'.
Sebenarnya kunci rahasia d bisa dihitung dari kunci publik e. Tapi tanpa
informasi tambahan yang
hanya
diketahui ofeh B, perhitungan tersebut membutuhkan waktu yang sangat lama
Algoritmanya adalah sebagai berikut
:
Tentukan sembarang 2 bilangan prima p dan q, dan hitung n = pq. 2. Pilih sembarang bilangan bulat positif e yang relatif prima dengan (p-lXq-l). Ini berarti bahwa e harus dipilih sehingga GCD (e, (p-tXq-t)) = l. Pasangan (n, e) merupakan
!.
kunci publik
sehingga secara praktis tidak dapat dilalcukan.
Untuk mengenkripsi, dilakukan langkahlangkah sebagai berikut : L Ubah tiap karakter teks asli menjadi
bilangan bulat 01-26
INTECRAL vol. 7 no. l, April 2002
(A = 01, S
=
ll
,t
I
'., , Z =
02,
untuk memperoleh
26), dan bagi. teks
,rnn
menjadi beberaPa blok b Yang besar tiap-bloknYa lebih kecil darin' z. i.l*rx tiap btok, hitung c = b". (mod n), c menjadi blok teks sandi Yang
iigii
I
pesan dengan menggunakan bilangan bulat 129 digit pada tahun 1977' Pesan
tersebut baru berhasil dipecahkan orang
17 tahun kemudian l2), Ini berarti bahwa secara praktis hanya pemilik
Untuk mendekriPkan kembali teks ,-rndi, dilakukan langkah-langkah sebagai berikut
:
Hl,ung bilangan bulat
kunci rahasia saja Yang
d sedemikian
ae = t (mod (P-l)(q-l))' eutiigun (n, d) meruPakan kunci
p
misalkan secara acak B memilih e = 5 Yang meruPakan bilangan yang relatif prima dengan (prXq-i) = 192. Maka kunci PubliknYa
'Berikutnya,
blok sandi c Yang 2. b = cd (mod n)' hitung Jit.Atnu, Untuk setiaP
2 Bagi pembuat sandi, dengan memjlih q, tidaklah Uuit flfungun prima p dan n-= sulit untuk menghitung kunci publik kembali' no. serta mendekripkannya
adalah (n, e) = (221,5).
Jika A hendak mengirim teks "171Yfi{", maka ia harus mengubahnya menjadi barisan angkaangk*a sebagai (A = 01, B:02 , "'): 20 0l 13 0l 14. Misalkan A mengambil blok dengan
klrulidun dekripsi dengan metode RSA dapat dibuktitcan ;+1' Akan tetapi bagi mendekriPsinYa, '
ia
Yang
mencoba
harus mencart
:
B
memilih 13 dan q = 17. Maka n=Pq = 2?1'
Sebagai contoh, andaikan
rahasia.
lain
mampu
membukanYa.
tinggl
;;;tg
dari
Aileman telah mencoba mengenkripsi
dikirimkan,
i.-
P dan q
sunsaf besar (umumnya dibuat 100 tt"-u lebih)' tuvest, Shamir dan
P
panjang 3 digit, maka ia memiliki 4 blok untut Jisandikan, masing-masing adalah
a;" q daii kunci Publik .n' dapat .Jika berhasii, maka kunci rahasia d dihitung. Akan tetapi sangatlah sulit
200,113,011,4
(mod 200 disandikan menjadi (200)i (mod (l l3)5 113 disandikan menjadi (mod (l l)5 0l I disandikan menjadi (mod (4)5 disandikan meryadi
4
221) 221) 221) 221)
=
200
:
146 163 140
= =
rahasia 200 146 163 140 Maka A mengirimkan 4 blok pesan menerima Pesan sandi dari A B vang -mencari kunci rahasia Yang
harus
didapat dari relasi e.d = 5d 192). DidaPat d= 77. Maka :
(moa Z]f ) blok sandi 200 didekrip menjadi (209): (mod 221) (146).,? menjadi blok sandi la6 dideknp iroli]' i*"9 ??l) blok sandi 163
di;;;;
"'i"ai iio[ runai lao didekrip menjadi
(140)??
"1",
Sffi t--*'t;t "t p"rkemban g an komputer' peranan sernakin terasalah pentingnya
t2
(mod
: ?99 = l13 . ^. (karena 3 disit) : 1l = 011
(mod2zl) = 4
asli 200 I 13 011 4 yang jika dikelompokkan i"t, "TAMAN" seperti pesan semula' ;;,T'di-ia didaoat pesan
=I
dalam 2 digit menjadi 20
bilangan prima. Bilangan prima yang
yang dulunya dianggap sebagai sesuatu
tiAat'memitiki manfaat, kini menjadi
llrffE€RAL vol. 7 no.
1,
APril2002
lebih dari sekedar enlcripsi dan dekripsi'
t4l Menezes, A., P.van Oorschot, Vanstone, 5., A Handbookof Applied Cryptography, CRC Press,
mulai banyak dipakai untuk mencegah
tsl RSA Laboratories, R57
bagian yang tak terPisahkan dallm keamanan data. Kriptografi dewasa ini Tanda tangan digital (digital sigrrature)
pemalsuan dokumen elektronik' Semuanya itu membutuhkan bilangan prima.
Catawetl, C.K., The Largest Known Prime by Year : A Brief History, http i/www. utm. edu/research/prime s/ notesiby-year.html, 2001 C.K., Caldwell, 12) http://www. utm.edu/researctr/prime s/glossary/index.htm, 200 I C.K., Mersenne Primes : Caldwell, t3I History, Theorems and Lisls,
1997
Laboralories' Frequent
lY As ked
Questions About TodaY's Cryptography, Version 4.,1, RSA Security Inc, 2000
ttl
:
J.J. Siang adalah dosen Jurusan Matematika, Fakultas MIPA, Universitas Kristen Immanuel, Yogyakarta
http: //www. utm. edu/researctr/prime s/ mersenne,shtml, 2001
TNTEGRAL vol. 7 no. 1, APril 2002
l3
