topik 3 kod dan_kriptografi
TRANSCRIPT
MTE3143 APLIKASI MATEMATIK
60
TOPIK 3 KOD DAN KRIPTOGRAFI
3.1 Sinopsis
Topik 3 dalam kursus ini bertujuan mengkaji aplikasi matematik dalam kod
dan kriptografi. Antara aspek yang diliputi ialah pelbagai jenis kod pembetulan
kesilapan dan juga kod linear yang merangkumi ruang penyelesaian bagi
sistem persamaan linear dan penggunaannya dalam kod pembetulan
kesilapan. Pelajar akan juga mempelajari kriptografi kekunci umum yang,
termasuk penggunaan teori asas nombor untuk menghasilkan sistem kod
penghitungan yang tidak boleh diceroboh dan algorithm RSA.
3.2 Hasil Pembelajaran Pada akhir tajuk ini, pelajar dijangka dapat:
mendemonstrasikan kefahaman terhadap kod dan kriptografi;
menerangkan tentang kod pembetulan kesilapan, kod ulangan, dan kod
semakan pariti, kod linear dan kod Hamming.
menerangkan tentang kriptografi kekunci awam dan melakukan enkripsi
dan dekripsi dengan menggunakan algoritma RSA.
3.3 Kerangka Tajuk
Kod dan Kriptografi
Kod linear dan
kod hamming
Kekunci umum kriptografi & algoritma
RSA
Mariner Spacecraft, kod
pembetulan kesilapan, kod
ulangan & kod semakan pariti
MTE3143 APLIKASI MATEMATIK
61
3.4 Mariner Spacecraft 1969
Pada tahun 1965, Amerika Syarikat telah melancarkan kapal angkasa
Mariner 4 untuk mengambil gambar planet Marikh. Transmisi setiap gambar
mengambil masa 8 jam. Misi Mariner selanjut, seperti Mariner 6 telah
menghasilkan gambar yang lebih jelas dengan menggunakan kod
pembetulan ralat.
. Kaedah transmisi gambar oleh Mariner 6 dari Marikh ke Bumi yang
digunakan pada tahun 1969 melibatkan penggunaan grid halus yang
diletakkan ke atas gambar yang dikirim. Setiap “petak” atau piksel, diberi
“darjah kehitaman” antara julat 0 hingga 63.
MTE3143 APLIKASI MATEMATIK
62
Setiap nombor ditulis sebagai urutan enam 0 dan 1. Contoh cara penulisan
dalam sistem binari (nombor asas 2) adalah seperti di bawah:
0 000000
1 000001
2 000010
3 000011
4 000100
5 000101
6 000110
7 000111
8 001000
9 001001
…
43 101011
…
63 111111 Jadi, darjah kehitaman = 43 → 101011. Dalam kes Mariner 6, setiap gambar dipecahkan kepada 700 x 832 petak,
di mana setiap petak dikodkan oleh 6 digit binari, setiap gambar akan
mengandungi satu urutan 6 x 700 x 832 = 3 494 400 digit binari.
Walau bagaimana pun, darjah kehitaman setiap petak mengandungi enam
digit binari manakala mesej yang dikirim sebenarnya menggunakan lebih
banyak digit bagi setiap darjah kehitaman – sebenarnya 32 digit binari
digunakan bagi setiap petak, oleh yang demikian gambar akan
mengandungi urutan 32 x 700 x 832 = 18 636 800 digit binari.
MTE3143 APLIKASI MATEMATIK
63
Proses Transmisi Mesej
Sungguhpun saluran transmisi mesej yang ditunjukkan di atas mudah,
kadang-kadang mesej yang dikirim akan diganggu oleh ralat tertentu.
Sama ada saluran transmisi yang digunakan merupakan pautan satelit,
tanpa wayar atau wayar telefon, biasanya saluran tersebut mungkin akan
menambah unsur gangguan (noise) yang menyebabkan ralat. Kejadian ini
serupa dengan gangguan suara yang kita alami semasa panggilan telefon
di kawasan isyarat lemah.
Dalam contoh di atas, mesej 01101 dikirim tetapi mesej yang diterima
kurang jelas. Jadi, adalah sukar untuk menterjemahkan digit tengah dan
digit terakhir yang diterima 01?0?
MTE3143 APLIKASI MATEMATIK
64
Apakah yang si penerima patut buat apabila menerima mesej tersebut?
Jawapannya bergantung kepada situasi. Misalnya, adalah mungkin mesej
tersebut diminta dikirim sekali lagi – semasa panggilan telefon, minta
disebut sekali lagi ataupun semasa menggunakan kad kredit, kad kredit
dilalui mesin kad kredit sekali lagi jika nombor yang diterima kurang jelas
sebab sukar diteka. Dalam kes misi angkasa lepas Mariner, gambar
tersebut tidak dapat dihantar sekali lagi dan adalah lebih praktikal untuk
menyahkod mesej seberapa tepat yang mungkin (oleh komputer bukan
oleh manusia).
Secara am, kesan gangguan dalam saluran komunikasi akan
mengakibatkan ralat yang menyebabkan mesej yang diterima berlainan
daripada apa yang dikirim. Oleh demikian, dalam contoh Mariner 6 di atas,
kita dapat lihat situasi di mana 43 yang ditransmisikan oleh kapal angkasa
diterima dan diterjemahkan sebagai 11 di Bumi.
3.4.1 Kod Pembetulan Kesilapan Kod pembetulan kesilapan (ralat) menangani masalah ralat dengan
menggunakan konsep lebihan (redundancy) – menggunakan lebih banyak
simbol yang diperlukan untuk mesej.
Dalam bahasa biasa, lebihan kerap berlaku, di mana pengetahuan
bahasa dan konteks ianya digunakan – membantu kita mengenal pasti
ralat tipografikal (ejaan) dan membetulkannya apabila dibaca.
MTE3143 APLIKASI MATEMATIK
65
Misalnya, jika perkataan ‘cetakan’ dikirim, ia mungkin diterima sebagai
‘cetekan’ atau ‘cetakau’. Dalam konteks topik ini, memang dapat dikenal
pasti dengan mudah bahawa ralat tipografikal (ejaan) telah berlaku dan
perkataan yang betul diteka dengan tepat sebagai ‘cetakan’.
Misi Mariner 6 telah menggunakan 6 digit binari untuk mengekod setiap
petak kecil (piksel) dalam gambar Marikh. Apabila mengirim isyarat balik
ke Bumi, Mariner 6 mengirim 32 digit dengan 26 (iaitu 32 – 6) digit lebihan.
Yang lebih mengkagumkan ialah terjemahan betul bagi setiap rantaian yang
mengandungi kurang daripada 8 ralat.
Jadi:
Setiap rantaian mengandungi enam 0 dan 1 → rantaian tiga puluh
dua 0 dan 1 → rantaian dengan < 8 ralat dinyahkodkan dengan
betul
Bagaimanakah ini boleh berlaku? Proses mengekod mesej bermula dengan penukaran teks biasa kepada
satu rantaian nombor dengan menggunakan abjad digital berikut. Dalam
kod ini, setiap huruf (dan juga tanda baca) diwakili oleh urutan 0 dan 1
sepanjang 5-digit. Oleh yang demikian, urutan-urutan tersebut merupakan
nombor antara 0 dan 32 yang ditulis dalam sistem binari (asas 2).
MTE3143 APLIKASI MATEMATIK
66
Dalam kes Mariner 6, satu kod Reed-Muller yang kuat telah digunakan
untuk pembetulan kesilapan. Seperti yang dinyatakan, mesej 6 digit binari
telah ditukar kepada mesej 32 digit binari yang digelar sebagai katakod
(codewords).
Misalnya, mesej yang dikirim mengandungi 3 digit binari. Oleh yang
demikian, terdapat 8 mesej yang mungkin, yang boleh diwakili oleh integer 0
hingga 7. Dalam contoh ini, 5 digit lebihan akan ditambah kepada setiap
mesej untuk menghasilkan katakod yang panjangnya 8.
0 = 000
1 = 001
2 = 010
3 = 011 →
4 = 100
5 = 101
6 = 110
7 = 111
000
001
010
011
100
101
110
111
00000
10110
10101
00011
10011
00101
00110
10000
MTE3143 APLIKASI MATEMATIK
67
Katakod 00110110 mewakili integer 1. Jika dibandingkan dengan katakod
00000000 yang mewakili integer 0, mudah dilihat bahawa kedua-dua
katakod ini berbeza di empat tempat (ketiga, keempat, keenam dan
ketujuh). Dengan cara yang sama, jika dibandingkan 00110110 dengan
katakod 01010101, dapat dilihat sekali lagi bahawa kedua-dua katakod ini
berbeza di empat tempat – kali ini di tempat kedua, ketiga, ketujuh dan
kelapan.
Perhatikan bahawa hanya ada 8 mesej, iaitu 8 katakod daripada 28 = 256
rantaian lapan digit binari yang mungkin. Hal ini bukan sahaja dapat
membantu pengesanan ralat tetapi juga pembetulan ralat yang tunggal.
Jika 00111110 diterima, memang mudah untuk menyemak bahawa ini
bukan katakod dan ralat telah berlaku – biasanya tidak pasti hanya satu
ralat berlaku tetapi yang pasti adalah sekurang-kurangnya satu ralat telah
berlaku.
Sungguhpun sukar untuk mengetahui mesej asal, prinsip kemungkinan
maksimum (principle of maximum likelihood) boleh digunakan untuk
menyahkod mesej yang diterima. Ini boleh dilakukan dengan
membandingkan mesej yang diterima dengan 8 katakod dan lihat yang mana
satu katakod paling rapat dengan mesej yang diterima.
Apabila ini dilakukan, dapat dilihat yang katakod yang paling rapat dengan
00111110 ialah 00110110. Ia hanya berbeza di satu tempat – tempat kelima
(yang digariskan).
Oleh sebab setiap katakod berbeza daripada yang lain dalam tepat empat
tempat, mesej yang diterima 00111110 akan berbeza daripada yang lain
dalam sekurang-kurangnya tiga tempat.
MTE3143 APLIKASI MATEMATIK
68
Jadi, dapat diandaikan yang ralat jarang-jarang berlaku, jadi katakod yang
mungkin ditransmisikan ialah 00110110. Dalam kes ini, selagi ada satu
ralat (dan ini adalah kes yang paling mungkin) ianya dapat diperbetulkan.
Ini memang benar untuk semua kes di mana satu ralat berlaku – jadi ia
digelarkan sebagai kode pembetulan ralat tunggal (single-error-correcting
code).
Dalam contoh ini,
8 digit katakod
3 digit maklumat dan
5 digit lebihan.
Kadar maklumat = 8
3
Secara am,
n digit
}
– – – … – – – … – – }
}
k digit mesej
r digit semakan (lebihan)
Kadar maklumat = n
k
Bagi Mariner 6, kadar maklumat R = 32
6
MTE3143 APLIKASI MATEMATIK
69
3.4.2 Kod Ulangan
Satu cara yang mudah untuk memperkenalkan lebihan adalah untuk
mengulang semua digit. Sebagai contoh, sesuatu mesej boleh dikodkan
dengan mengulang setiap digit n kali.
Jika n = 5, panjang kod ulangan ialah 5.
Contoh :
S → 10011 → 11111 00000 00000 11111 11111
U → 10101 → 11111 00000 11111 00000 11111
S → 10011 → 11111 00000 00000 11111 11111
I → 01001 → 00000 11111 00000 00000 11111
E → 00101 → 00000 00000 11111 00000 11111
Jika dikirim S = 10011 sebagai 11111 00000 00000 11111 11111, ia akan
diterima sebagai urutan 0 dan 1 yang panjangnya 25 digit.
Kita perlu peraturan (algoritma) untuk menyahkod mesej yang diterima.
Dengan bantuan komputer menyahkod mesej, tekaan mengikut konteks
tidak dilakukan tetapi peraturan yang tepat perlu digunakan.
Misalnya, apabila mesej 11011 00110 11000 10000 10111 diterima,
bagaimanakah ianya dinyahkod?
Algoritma Nyahkod bagi Kod Ulangan Panjang 5
1. Perhatikan bilangan digit 1.
2. Jika bilangan digit 1 ≥ 3 , tulis 11111.
3. Jika bilangan digit 1 ≤ 2 , tulis 00000.
MTE3143 APLIKASI MATEMATIK
70
Perhatikan bahawa kod ini boleh membetulkan 2 ralat tetapi ia mempunyai
kadar maklumat yang sangat rendah, iaitu 5
1.
Jika n = 4 (setiap digit diulang 4 kali), apakah yang berlaku jika terima
0011?
Saluran Simetri Binari
Kebarangkalian menerima simbol yang silap adalah serupa sama ada simbol
0 atau simbol 1 dikirim.
Kebarangkalian menerima simbol yang silap = p
Sebagai contoh, sekiranya p = 100
1 , iaitu kebarangkalian satu digit tunggal
diterima secara silap ialah 100
1 = 0.01, maka kebarangkalian satu digit
tunggal diterima secara betul ialah 100
99 = 0.99.
Dianggap bahawa semua ralat berlaku secara rawak, iaitu secara tidak
bersandar antara satu sama lain.
Untuk memudahkan pengiraan, kod ulangan panjang 3 digunakan.
Bolehkah kebarangkalian 100
99 = 0.99 diperbaiki jika satu katakod satu digit
diterima?
MTE3143 APLIKASI MATEMATIK
71
Mesej dikirim
Mesej dikodkan
Mesej mungkin diterima
Mesej dinyahkod
0 → 000 → 000 001
010 100 → 0
1 → 111 → 101 011
110 111 → 1
Jika 000 dikirim,
Pengiraan kebarangkalian mesej yang mungkin diterima:
Pr (000) = 100
99 x
100
99 x
100
99 = 0.970299
Pr (001) = 100
99 x
100
99 x
100
1 = 0.009801
Pr (010) = 100
99 x
100
1 x
100
99 = 0.009801
Pr (100) = 100
1 x
100
99 x
100
99 = 0.009801
Jadi kebarangkalian mengdekod mesej sebagai 0: Pr (0) = Pr (000) + Pr (001) + Pr (010) + Pr (100)
= 0.970299 + 3 x 0.009801
= 0.999702
Jadi, secara purata, kesilapan mengdekod mesej yang dikirim 0 sebagai 1
berlaku hanya sekali setiap 100 kali, kita akan dapat ralat kurang daripada 3
setiap 10 000 (atau 1/3000)! Ini merupakan kemajuan yang hebat.
MTE3143 APLIKASI MATEMATIK
72
Bagi kod ulangan panjang n,
n digit
}
– – – … – –
} }
1 digit mesej
n – 1 digit semakan
Maka kadar maklumat, R = n
1. Ini sangat kecil!
Kod ulangan dapat membetulkan ralat tetapi kadar maklumatnya sangat rendah! Latihan 1. Anda telah menerima mesej berikut yang ditulis dengan kod ulangan
panjang 5.
a) Tukar mesej ini kepada kod 5 digit binari.
b) Tukarkan kepada abjad biasa.
00000 10010
11110 01010
00111 10000
01000 11111
01111 00010
11011 11000 01111 01000 01011 00001 01100 11100 00000 00111 10111 11101 01000 10111 10000
MTE3143 APLIKASI MATEMATIK
73
2. Anda telah menerima mesej berikut yang ditulis dengan kod ulangan
panjang 5.
00000 11011 01111 00100 11111
01000 11111 00100 00001 11101
11101 00100 00000 11110 01111
11111 10000 01000 00000 00100
10111 00010 10000 00111 01100
01100 10001 01010 00011 11001
01010 10111 01111 11111 00000
11111 00010 11011 01000 00000
a) Tukar mesej ini kepada kod 5 digit binari.
b) Tukarkan kepada abjad biasa.
c) Apakah mesej yang sebenar?
3. Kod ulangan panjang 3 digunakan untuk transmisi mesej. Jika
kebarangkalian membuat kesilapan dalam satu digit ialah 0.01 dan
kita anggap kesilapan berlaku secara tak bersandar satu sama lain,
kirakan kebarangkalian mesej 000 yang dikirim diterima sebagai 111.
3.4.3 Kod Semakan Pariti Kod semakan pariti tunggal merupakan ekstrem daripada kod ulangan.
Berbanding dengan kod ulangan, kod semakan pariti tunggal hanya ada
satu digit semakan.
Digit semakan ini diperolehi daripada jumlah digit maklumat (mod 2).
Sebagai contoh, lihat bagaimana digit semakan dikira
MTE3143 APLIKASI MATEMATIK
74
A
000001 1
} ←
5 digit
mesej 1digit semakan
B
000010 1
C
000011 0
D
000100 1
…
Secara am katakod ditulis sebagai c1 c2 c3 c4 c5 c6 di mana
c6 = c1 + c2 + c3 + c4 + c5 (mod 2).
Bagi kod semakan pariti tunggal,
n digit
-- … - -
k = n – 1 1 digit semakan digit mesej
Maka kadar maklumat ialah n
k =
n
n 1 , iaitu sangat tinggi!
Akan tetapi, kod semakan pariti tunggal hanya boleh mengesan bilangan
ralat yang ganjil tetapi tidak dapat membetulkannya.
Latihan 1. Cari katakod yang mewakili huruf berikut dalam kod semakan pariti
tunggal di atas : J , L , Q , S , G , X.
2. Tulis mesej NO ERRORS dengan kod semakan pariti tunggal.
}
}
←
MTE3143 APLIKASI MATEMATIK
75
3. Mesej berikut telah diterima dalam kod semakan pariti tunggal:
000011 000000 001111 011110 010110 001001
000000 100100 001010 100111 101001 011000 101000
a) Kesan di mana ralat telah berlaku.
b) Nyahkod semua huruf yang lain.
c) Cuba teka mesej yang dikirim.
3.5 Kod Linear
Perhatikan kod linear panjang 6 berikut ada 3 digit mesej dan 3 digit
semakan boleh ditulis semula sebagai persamaan linear untuk mentakrifkan
digit-digit semakan.
Katakod panjang 6
}
c1 c2 c3 c4 c5 c6
} }
3 digit mesej
3 digit semakan
Apabila diberi mesej c1 c2 c3,
c4 = c1 + c2
c5 = c1 +
c6 = c2 +
(mod 2) c3 (mod 2) c3 (mod 2)
untuk memperolehi katakod C= [c1 c2 c3 c4 c5 c6].
Iaitu
6
5
4
c
c
c
=
110
101
011
3
2
1
c
c
c
.
Sebagai contoh, mesej 010 akan ditransmisikan sebagai [010101].
MTE3143 APLIKASI MATEMATIK
76
Latihan Tuliskan katakod yang sepadan dengan mesej:
(i) 111 (ii) 101 (a) Berapakah mesej tiga digit yang dibentukkan? (b) Senaraikan semua katakod bagi kod ini. Persamaan Semakan Pariti Katakod C = [c1 c2 c3 c4 c5 c6 ] menyempurnakan persamaan semakan
pariti
c1 + c2 + c4 = 0 (mod 2)
c1 + c3 + c5 = 0 (mod 2)
c2 + c3 + c6 = 0 (mod 2) Persamaan-persamaan ini dinamakan sebagai persamaan semakan pariti
sebab menyemak pariti atau kegenapan hasil tambah digit-digit dalam
katakod – untuk memperolehi 0 di sebelah kanan, kita perlu dapat
bilangan 1 yang genap pada sebelah kiri setiap persamaan.
Persamaan semakan pariti juga boleh ditulis sebagai
100110
010101
001011
6
5
4
3
2
1
c
c
c
c
c
c
=
0
0
0
,
atau H CT = 0,
di mana H ialah matriks semakan pariti.
[CT
= transpos menegak bagi vektor C]
MTE3143 APLIKASI MATEMATIK
77
Apakah yang berlaku semasa transmisi katakod? Apabila katakod C = [c1 c2 c3 c4 c5 c6] dikirim, saluran transmisi akan
menambah gangguan (ralat) E = [e1 e2 e3 e4 e5 e6], mengakibatkan katakod
diterima sebagai
R = [r1 r2 r3 r4 r5 r6]
di mana ri = ci + ei (mod 2) .
Latihan 1. Jika C = [100110] , E = [000101], cari R. 2. Jika R = [001000], E = [000011], cari C. 3. Jika R = [010000], C = [111000], cari E. Biasanya, kita hanya tahu katakod yang diterima, R. Jadi masalah
adalah untuk mengetahui katakod yang dikirim C jika kita terima katakod
R. Ini boleh dilakukan dengan mencari E dahulu.
3.5.1 Mengira Sindrom Bagi katakod yang diterima, R = [r1 r2 r3 r4 r5 r6], kita mentakrifkan sindrom,
s = [s1 s2 s3] bagi R dengan
s1 = r1 + r2 + r4
s2 = r1 + r3 + r5
s3 = r2 + r3 +
(mod 2)
(mod 2) r6 (mod 2).
MTE3143 APLIKASI MATEMATIK
78
3
2
1
s
s
s
=
100110
010101
001011
6
5
4
3
2
1
r
r
r
r
r
r
atau
sT = H R
T
. Oleh kerana digit-digit sindrom ditakrifkan oleh persamaan semakan
pariti yang sama dengan katakod, digit sindrom akan mendedahkan pola
kegagalan semakan pariti.
s dinamakan sebagai sindrom R sebab ia mempamerkan “simptom khas”
ralat tanpa mengenal pasti sebabnya, seperti cara kita mengenal pasti
sesuatu penyakit daripada simptomnya dan bukan sindrom (sebabnya yang
sebenar) – contoh SIDS = Sudden Infant Death Syndrome.
Semua katakod mempunyai sindrom 0 = [000] sebab H CT = 0 .
Sindrom katakod yang diterima serupa dengan sindrom ralat. Katakod yand diterima R merupakan hasil tambah katakod C dan ralat E.
R = C + E.
Jadi C = R – E dan
0 =
Oleh itu
H CT = H (R – E)
T
= H (RT
– ET
)
= H RT – H E
T
sT = H RT = H E T.
Jadi katakod yang diterima R mempunyai sindrom yang sama dengan ralat E.
MTE3143 APLIKASI MATEMATIK
79
Maklumat ini sangat berguna sebab ini bermakna jika R merupakan
katakod yang diterima, set ralat yang mungkin juga merupakan set vektor
yang sama dengan sindrom R.
Dari atas, jika R dan E mempunyai sindrom yang sama, kita boleh
guna akas penghujahan untuk menunjukkan bahawa jika H RT = H E
T
,
jadi R – E = C, di mana C adalah katakod.
Bilangan perkataan dengan sindrom yang sama adalah bersamaan dengan
bilangan katakod.
Dalam kes ini, kita ada 23 = 8 sindrom yang mungkin dan setiap satu selaras
tepat dengan 88
64
8
2 6
perkataan.
Oleh itu, sebagai contoh, 8 katakod selaras tepat dengan 8 perkataan
dengan sindrom [000].
Mencari perkataan selaras dengan sindrom yang diberi
Oleh sebab sindrom katakod yang diterima R sama dengan sindrom ralat E,
satu perkara yang perlu dilakukan untuk menyahkod katakod yang
diterima adalah dengan mencari semua perkataan yang mempunyai sindrom
yang sama dengan R.
Misalnya, kita akan mencari semua perkataan dengan sindrom [001] apabila
kita menggunakan kod linear yang ditakrifkan. Oleh itu,
r1 + r2 + r4
r1 + r3 + r5
r2 + r3 +
= 0 (mod 2)
= 0 (mod 2) r6 = 1 (mod 2).
MTE3143 APLIKASI MATEMATIK
80
100110
010101
001011
6
5
4
3
2
1
r
r
r
r
r
r
=
1
0
0
,
atau H RT =
1
0
0
= sT.
Dengan cara yang sama, kita akan dapat mencari semua perkataan yang
selaras dengan sindrom [001] dengan cara menyenaraikan semua 8 pilihan
yang mungkin bagi 0 dan 1 bagi ketiga-tiga pembolehubah yang pertama
dan mencari nilai baki tiga pembolehubah tersebut. Misalnya, jika kita mula
dengan r1 = 0, r2 = 0, r3 = 0, kita dapat lihat daripada persamaan ini, kita
dapatkan tiga persamaan di mana r4 = 0, r5 = 0, r6 = 1.
Jadi salah satu daripada 8 perkataan yang selaras dengan sindrom [001]
ialah [000001].
Kita boleh memperolehi semua 8 perkataan dengan cara yang sama.
Misalnya, jika r1 = 0, r2 = 0, r3 = 1, kita dapat r4 = 0, r5 = 1, r6 = 0, yang
membentuk perkataan [001010].
Latihan 1. Cari 6 perkataan lagi yang selaras dengan sindrom [001]. 2. Senaraikan semua perkataan dengan sindrom a) [010]. b) [111].
MTE3143 APLIKASI MATEMATIK
81
Tatasusunan Piawai Slepian menyenaraikan semua perkataan yang selaras
dengan setiap sindrom bagi kod linear.
Set perkataan { [r1 r2 r3 r4 r5 r6] di mana ri = 0 atau 1, bagi i = 1, 2, …, 6}
membentuk ruang vektor dimensi 6 di atas Medan Galois GF(2).
Sebab semua katakod merupakan penyelesaian bagi H CT = 0, semua
katakod membentuk subruang bagi ruang vektor yang mengandungi
semua perkataan. Dimensi sub ruang ini ialah 6 – 3 = 3.
Khasnya, ini bermakna set katakod akan membentuk kumpulan di
bawah penambahan (mod 2) dan juga hasil tambah mana-mana dua
katakod merupakan satu katakod.
Latihan Berkumpulan
1. Semak bahawa hasil tambah mana-mana dua katakod merupakan
katakod.
2. Pilih sindrom yang tidak sama dengan [000] – pastikan semua ahli
dalam kumpulan anda memilih sindrom yang berlainan.
a) Pilih satu katakod dan tambah kepadanya setiap daripada perkataan
dalam baris yang selaras dengan sindrom pilihan anda. Apakah yang
anda dapati?
MTE3143 APLIKASI MATEMATIK
82
b) Dengan menggunakan sindrom yang sama, pilih katakod yang
berlainan dan ulang (a).
c) Dengan menggunakan sindrom yang sama, semak bahawa setiap
perkataan yang selaras dengan sindrom dalam Tatasusunan Piawai
Slepian boleh diperolehi sebagai hasil tambah perkataan pertama
dalam baris (pemimpin koset) dan katakod dalam lajur yang sama.
d) Banding jawapan a), b) dan c) dengan ahli kumpulan lain.
Dalam Tatasusunan Piawai Slepian, semua katakod disenaraikan
sebagai baris pertama bermula dengan katakod [000000].
Setiap baris berikut dalam tatasusunan mengandungi satu koset katakod.
Dalam setiap koset, perkataan disusun dalam setiap baris di mana
perkataan pertama dalam setiap baris mempunyai bilangan 1 yang paling
kurang. Perkataan pertama dalam setiap baris Tatasusunan Piawai Slepian
dinamakan pemimpin koset.
Dalam baris pertama, selaras dengan sindrom [000], perkataan dalam baris
tiada 1; perkataan pertama dalam setiap daripada enam baris berikut
mempunyai hanya satu 1 sahaja; manakala perkataan pertama dalam baris
terakhir merupakan salah satu daripada tiga perkataan dalam baris tersebut
yang ada tepat dua 1.
Berat sesuatu perkataan ditakrifkan sebagai bilangan 1 dalam perkataan
tersebut.
Tatasusunan Piawai Slepian boleh dibina bagi kod linear dengan langkah-
langkah berikut:
1. Dalam baris pertama, senaraikan semua katakod yang bermula dengan
0.
MTE3143 APLIKASI MATEMATIK
83
2. Pilih mana satu perkataan, W, yang berat minimum weight yang bukan
katakod (tidak disenaraikan pada baris pertama) dan senaraikannya
sebagai unsur pertama dalam baris berikut.
3. Bermula dengan W, senaraikan semua unsur koset W + C, di mana C
adalah katakod, dalam urutan yang sama seperti senarai katakod dalam
baris pertama.
4. Ulangi langkah 2 dan 3 dengan menggunakan perkataan baru X,
di mana X tiada dalam dua baris yang pertama.
5. Ulangi langkah 4 dengan menggunakan perkataan baru yang tiada
dalam baris-baris sebelumnya sehingga semua perkataan telah
disenaraikan.
Pengdekodan Perkataan yang diterima R
R = [r1 r2 r3 r4 r5 r6] boleh didekodkan dengan langkah-langkah berikut:
1. Kirakan sindrom s = [s1 s2 s3] bagi R. Ini merupakan sindrom bagi E.
2. Guna Tatasusunan Piawai Slepian untuk mencari perkataan dengan
sindrom s dengan bilangan 1 yang paling sedikit. Pilih perkataan ini
sebagai E.
3. Kirakan C di mana C = R – E.
Latihan 1. Cari C jika R = [101110].
[Nota: Apabila menggunakan tatasusunan ini, kita tidak perlu
mengira sindrom. Sebab R dan E mempunyai sindrom yang sama,
kita hanya cari R dalam sifir ini. E merupakan perkataan dalam baris
yang mengandungi R. ]
2. Cari C jika (i) R = [111111], (ii) R = [111011], (iii) R = [110011].
MTE3143 APLIKASI MATEMATIK
84
3. Bekerja secara berpasangan dan jalankan langkah-langkah
berikut:
[1] Pilih katakod C untuk dikirim sebagai mesej.
[2] Pilih ralat E.
[3] Kirakan R = C + E dan kirimkan kepada pasangan anda.
[4] Dekod perkataan pasangan anda.
[5] Ulang ini sebanyak tiga kali: sekali pilih E yang berat 1
(hanya satu 1 dalam perkataan); sekali dengan E = 0; dan
sekali dengan E yang berat 2 (dengan dua 1 dalam
perkataan).
Dalam kes yang manakah anda dapat mengenal pasti katakod?
3.5.2 Kod Linear secara Am
Satu kod merupakan kod linear atau kod kumpulan jika katakodnya
merupakan set vektor C yang memuaskan persamaan H CT = 0, di mana H
adalah matriks semakan pariti.
Dalam kod semakan pariti tunggal, digit-digit c1, c2, c3, c4, c5, dan c6 dalam
katakod [c1 c2 c3 c4 c5 c6] memuaskan persamaan semakan pariti
c6 = c1 + c2 + c3 + c4 + c5 (mod 2),
yang serupa dengan
c1 + c2 + c3 + c4 + c5 + c6 = 0 (mod 2).
Ini ditulis sebagai H CT = 0, di mana H = [111111].
MTE3143 APLIKASI MATEMATIK
85
Kod ulangan panjang 5 juga boleh ditakrifkan dengan menggunakan
persamaan semakan pariti berikut:
c1 + c2 = 0 (mod 2)
c1 + c3 = 0 (mod 2)
c1 + c4 = 0 (mod 2)
c1 + c5 = 0 (mod 2)
Kita boleh tulis sebagai
H CT = 0, di mana H =
10001
01001
00101
00011
.
Secara am, jika kod ulangan panjang n, kita akan dapat matriks semakan
pariti H yang (n – 1) x n
Kod blok merupakan kod di mana setiap katakod merupakan urutan
bilangan tetap, n, simbol. Bagi kes kod linear, panjang bloknya ialah
bilangan lajur dalam H
Sindrom, s, katakod yang diterima R diberi sebagai sT = H R
T
.
Koset terdiri daripada semua perkataan yang mempunyai sindrom tertentu.
Berat perkataan merujuk kepada bilangan 1 dalam perkataan tersebut.
Dalam satu koset, perkataan yang mempunyai berat yang minimum dipilih
sebagai pemimpin koset (coset leader).
Untuk menyahkod R:
1. Kirakan sindrom s;
2. Cari pemimpin koset E; dan
3. Kirakan C = R – E.
MTE3143 APLIKASI MATEMATIK
86
3.5.3 Kod Hamming Teori kod pembetulan ralat telah bermula dengan usaha Richard Hamming
pada tahun 1947. Sebagai seorang ahli matematik, Hamming dapat
menggunakan kemudahan komputer di Bell Telephone Laboratories untuk
menjalankan pengiraan matematik. Ketika itu, masa untuk melaksanakan
program sangat lama dan apabila Hamming datang bekerja pada hujung
minggu beliau kerap menemui situasi di mana program pengiraan terhenti
kerana menemui ralat. Oleh yang demikian, Hamming memikirkan tentang
kebolehan komputer bukan sahaja untuk mengesan ralat tetapi
membetulkannya!
Pada 1950 Richard Hamming telah memperkembangkan kod Hamming
yang merupakan kod linear yang dapat membetulkan ralat tunggal.
H =
100110
010101
001011
sT = H R
T = H ET
. Jika ralat E = [e1 e2 e3 e4 e5 e6], persamaan boleh ditulis semula sebagai
3
2
1
s
s
s
= e1
0
1
1
+ e2
1
0
1
+ e3
1
1
0
+ e4
0
0
1
+ e5
0
1
0
+ e6
1
0
0
.
Sindrom ialah hasil tambah lajur-lajur H di mana ralat-ralat saluran berlaku.
Oleh yang demikian, jika mana:
satu lajur H adalah 0, ralat pada kedudukan tersebut tidak dapat
dikesan; dan
MTE3143 APLIKASI MATEMATIK
87
dua lajur H serupa, kita tidak dapat membezakan ralat tunggal
yang berlaku pada kedua-dua kedudukan tersebut
Kod linear hanya dapat membetulkan semua pola ralat tunggal jika lajur-
lajur H berbeza dan bukan sifar.
Sebaliknya, jika semua lajur H berbeza dan bukan sifar, ralat tunggal
pada kedudukan berbeza akan menghasilkan sindrom yang berbeza.
Kod binari linear mampu membetulkan semua pola yang tiada lebih
daripada satu ralat saluran jika dan hanya semua lajur dalam matriks
semakan pariti H berbeza
dan bukan sifar.
Penyahkodan Perkataan
Untuk menyahkodkan perkataan yang diterima R, sindrom s dikira. Jika s
ialah sifar, andaikan tiada ralat.
Jika s bukan sifar dan sama dengan salah satu lajur dalam H, andaikan ralat
tunggal telah berlaku pada kedudukan tersebut.
Jika s bukan sifar dan tidak sama dengan mana satu lajur dalam H,
prosedur penyahkodan ini gagal.
Kegagalan penyahkodan dan ralat hanya berlaku jika dua atau lebih ralat
saluran berlaku.
MTE3143 APLIKASI MATEMATIK
88
Misalnya, biarkan H =
101000111
011001110
101011100
011111000
.
Jika diterima perkataan R = [101000101], jadi kita dapat mengira s = [1100].
Sebab sT merupakan lajur kelima dalam H , kita andaikan E = [000010000].
Oleh itu C = R – E = [101010101].
Walau bagaimana pun jika R = [101000101], kita perolehi s = [1101], dan
dalam kes ini di mana sT bukan salah satu lajur dalam H, ini bermakna
terdapat ≥ 2 ralat dan prosedur penyahkodan gagal.
Latihan Bagi matriks semakan pariti H di atas, cuba nyahkodkan perkataan-
perkataan berikut yang diterima:
(i) R = [101001101] (ii) R = [111000101] (iii) R = [101000111]
Bagi kod pembetulan ralat tunggal, bilangan maksimum lajur bukan sifar
matriks binari yang berbeza dan bukan sifar 2r – 1.
MTE3143 APLIKASI MATEMATIK
89
Kod Hamming
Lajur-lajur dalam matriks semakan pariti H, Kod Hamming terdiri daripada
2r–1 lajur bukan sifar r–tuple (non-zero binary r-tuples) yang tersusun dalam
mana-mana satu urutan.
Jika A merupakan matriks m × n dengan pangkat r, dimensi ruang
nol A adalah n − r.
Sebab H mengandungi semua lajur bukan sifar yang mungkin, ia
mengandungi setiap satu daripada lajur-lajur matriks identiti r x r dan
mempunyai pangkat r.
Jadi H merupakan matriks r x n dengan pangkat r dan dimensi subruang
yang memenuhi syarat H CT = 0 iaitu n − r = k.
Oleh itu, bilangan digit mesej = k = n − r = 2r – 1 – r.
Bagi setiap integer positif, wujud Kod Hamming dengan digit semakan r,
panjang blok n = 2r – 1 dan k = n − r = 2
r
– 1 – r.
Kod ini boleh membetulkan ralat tunggal pada mana-mana satu digit. Sebab
setiap r-tuple bukan sifar wujud sebagai lajur, kegagalan pengdekodan tidak
akan berlaku. Jadi prosedur pengdekodan ralat tunggal lengkap.
Walau bagaimana pun kod ini tidak dapat mengesan lebih daripada 2
ralat. Kadangkala digit semakan pariti yang lain akan ditambah untuk
mengesan (tetapi tidak dapat membetulkan) 2 ralat. Lajur-lajur dalam
matriks semakan pariti H boleh disusun dalam mana-mana satu urutan.
MTE3143 APLIKASI MATEMATIK
90
Kadar maklumat Kod Hamming
R = n
k =
12
12r
r
r = 1 –
12r
r.
Bila r → ∞, R→1.
Dengan membina Kod Hamming yang mempunyai panjang blok yang
besar, kita akan dapat kadar maklumat yang sangat tinggi. Sungguh pun
Kod Hamming merupakan perkembangan hebat berbanding dengan kod
semakan pariti tunggal, kod ini tidak dapat membetulkan lebih daripada dua
ralat.
Sekitar 1960, Bose, Changhuri and Hocquenghan telah menemui
kod pembetulan dwi-ralat Kod BCH (double-error-correcting codes)
yang lebih kompleks. Seterusnya, kod-kod ini diperkembangkan
sehingga menjadi kod pembetulan t ralat.
Latihan 1. (a) Yang mana satu daripada matriks semakan pariti ini merupakan
kod pembetulan ralat tunggal? Beri sebab jawapan anda.
(i) H =
0111011100
0001000101
1100110011
1010101010
(ii) H =
110110000
000110110
000011011
011011000
MTE3143 APLIKASI MATEMATIK
91
(b) Yang mana satu daripada kedua matriks di atas merupakan Kod
Hamming? Beri sebab mengapa atau mengapa tidak.
2. Guna matriks (ii) daripada soalan 1 di atas untuk menyahkod setiap
daripada perkataan yang diterima berikut:
(a) R = [111101000] (b) R = [110101011] (c) R = [100010001] (d) R = [010010010].
3. Pertimbangkan Kod-Kod Hamming yang ditakrifkan oleh tiga matriks
semakan pariti di bawah.
(i) H =
1010101
1100110
1111000
(ii) H =
1001011
0101101
0011110
(iii) H =
1010101
0110011
0001111
(a) Bagi setiap kod, nyahkodkan perkataan-perkataan berikut yang diterima:
R1 = [1110000] , R2 = [1111000] .
(b) Tunjukkan yang dua daripada tiga matriks di atas mentakrifkan kod-
kod yang serupa (identical codes). Panduan: Tunjukkan bahawa
baris-baris mana satu merupakan kombinasi linear yang lain.
MTE3143 APLIKASI MATEMATIK
92
3.6 Algoritma RSA
Masalah Penyebaran Kunci (Key-Distribution Problem)
Dalam sistem tradisional, kunci yang diguna oleh si-pengirim untuk
mengekod mesej diguna juga oleh si-penerima untuk menyahkodnya.
Oleh yang demikian, kunci tunggal ini mesti dijaga dengan baik dan
dirahsiakan agar hanya dapat digunakan oleh pihak tertentu.
Dalam masyarakat moden, terdapat jumlah data yang banyak yang
perlu dirahsiakan dan ini mengakibatkan keperluan penggunaan kunci
bagi pengguna-pengguna kod.
Masalah penyebaran kunci ini diterangkan oleh Simon Singh dalam
bukunya The Codebook (2002) seperti berikut:
a classic catch-22 situation. If two people want to exchange a secret
message over the phone, the sender must encrypt it. To encrypt the
secret message the sender must use a key, which is itself secret, so
then there is the problem of transmitting the secret key to the receiver
in order to transmit the secret message. In short, before two
people can exchange a secret (an encrypted message) they must
already share a secret (the key). (pp. 189–190)
Pada pertengahan tahun 70-an, Whitfield Diffie, Martin Helman dan
Ralph Merkle telah mencadangkan penggunaan cipher asimetrik
(asymmetric cipher) untuk mengatasi masalah penyebaran kunci.
Mereka mencadangkan penggunaan kunci berlainan untuk mengekod dan
menyahkod mesej.
MTE3143 APLIKASI MATEMATIK
93
3.6.1 Peranan Pemfaktoran
Aktiviti: Faktorkan 518 940 557
Darabkan 15 107 dengan 34 351 Aktiviti di atas menunjukkan betapa sukarnya untuk mencari faktor-
faktor hasildarab dua nombor perdana. Oleh yang demikian, konsep ini
diguna untuk menjanakan sistem pengkodan yang baru yang dinamakan
sebagai Kriptografi Kunci Umum (Public Key Cryptography).
Dalam kriptografi kunci umum, kunci untuk menyahkod mesej tidak
dapat diperolehi dengan mudah daripada kunci yang diguna untuk
mengekodnya. Ini membolehkan pengiriman mesej secara elektronik secara
selamat ke destinasi di mana kunci umum boleh dihebahkan secara umum.
3.6.2 Penggunaan Aritmetik Modular Aritmetik modular digunakan dalam banyak kriptosistem untuk
menyamarkan maklumat dengan mudah kerana fungsinya yang sukar
diramalkan.
Jadual berikut menunjukkan bagaimana nilai P dapat dirahsiakan
melalui pengiraan C = P3 dalam modulo 11.
P 0 1 2 3 4 5 6 7 8 9 10
C = P3
0 1 8 27 64 125 216 343 512 729 1000
C = P3 modulo 11 0 1 8 5 9 4 7 2 6 3 10
Aritmetik modular juga dikenali sebagai ‘aritmetik jam’ dan diperkenalkan oleh
K.F.Gauss (1777 - 1855).
MTE3143 APLIKASI MATEMATIK
94
Bagi sebarang nombor asli n, aritmetik modulo n berasaskan kepada
pembahagian set integer Z = {…, −3,−2, −1, 0, 1, 2, 3, …} ke dalam n kelas
yang berasingan yang selaras dengan n baki yang mungkin apabila dibahagi
oleh n.
Misalnya, jika n =2, baki yang mungkin jika integer dibahagi oleh 2 adalah 0
atau 1.
Kelas integer dengan baki 0 merupakan set nombor genap = {..., – 6, – 4, –
2, 0, 2, 4, 6, ...} manakala kelas integer dengan baki 1 merupakan set
nombor ganjil = {..., – 5, – 3, – 1, 1, 3, 5, 7, ...}.
Secara umum, semua integer dalam kelas yang sama mempunyai baki
yang sama apabila terbahagi oleh modulus. Ini bermakna terdapat
perbezaan antara dua integer dalam kelas yang sama juga merupakan
gandaan modulus.
Jadi, dalam contoh di atas, apabila kita memerhatikan perbezaan antara dua
nombor genap kita akan memperolehi gandaan 2 (8 – 2 = 6 = 3 x 2) dan
apabila kita lihat perbezaan antara dua nombor ganjil kita juga akan
mendapat gandaan 2 (7 – (– 1) = 8 = 4 x 2).
Sifat Kongruen Modulo
Dua integer a dan b dikatakan sebagai kongruen modulo jika a – b
merupakan gandaan n dan ini ditulis sebagai
a ≡ b (mod n) .
Oleh yang demikian, semua nombor genap ≡ 0 (mod 2) dan semua nombor
ganjil ≡ 1 (mod 2).
MTE3143 APLIKASI MATEMATIK
95
Dengan perkataan lain, kita boleh mewakili setiap nombor genap (mod 2)
dengan integer 0 dan setiap nombor ganjil (mod 2) dengan 1.
Aktiviti 1. (a) Apakah baki yang mungkin bila integer dibahagi dengan 3?
(b) Bagi setiap integer berikut, tulis baki yang diperolehi selepas
dibahagi dengan 3:
(i) 7; (ii) 301; (iii) 963; (iv) –31; (v) –5; (vi) –1.
(c) Pasangan integer yang manakah yang kongruen mod 3?
2. Bekerja secara berkumpulan.
(a) Pilih mana-mana dua integer a dan b – pastikan semua orang
menggunakan pasangan integer yang berbeza. Cari integer bukan
negatif terkecil a′ dan b′ di mana a ≡ a′ (mod 7) dan b ≡ b′ (mod 7).
(b) Kirakan nilai, dengan bantuan kalkulator saintifik jika perlu:
(i) ab ; (ii) ab (mod 7) ; (iii) a′b′ ; (iv) a′b′ (mod 7) .
(c) Berdasarkan pengiraan kumpulan anda, apakah kesimpulan yang
anda dapati tentang apa yang berlaku dengan hasil darab aritmetik
modulo?
Jika a ≡ a′ (mod n) dan b ≡ b′ (mod n), maka ab ≡ a′ b′ (mod n).
Contoh:
Cari X = 36 * 53 * 91 * 17 * 22 (mod 29).
Penyelesaian :
36 ≡ 7 (mod 29), 53 ≡ 24 (mod 29), 91 ≡ 4 (mod 29), 17 ≡ 17 (mod 29), dan
22 ≡ 22 (mod 29).
MTE3143 APLIKASI MATEMATIK
96
Ini boleh ditulis semula sebagai
X = 36 * 53 * 91 * 17 * 22 (mod 29)
= 7 * 24 * 4 * 17 * 22 (mod 29)
= 168 * 68 * 22 (mod 29)
= 23 * 10 * 22 (mod 29)
= 230 * 22 (mod 29)
= 27 * 22 (mod 29)
= 594 (mod 29)
= 14.
Semak 36 * 53 * 91 * 17 * 22 = 64 936 872 dan 64 936 872 (mod 29) = 14.
[Nota: Kalkulator saintifik komputer anda juga boleh melakukan pengiraan
aritmetik modulo]
Aktiviti Cari X = 73 * 29 * 102 * 14 * 87 (mod 31) dan semak jawapan anda.
Contoh pengiraan aritmetik modulo secara berperingkat-peringkat:
Cari X = 1143 (mod 13).
Perhatikan bahawa 112 (mod 13) = 121 (mod 13) = 4.
Jadi 114 (mod 13) = 4
2 (mod 13) = 16 (mod 13) = 3.
118 (mod 13) = 3
2 (mod 13) = 9 (mod 13) = 9, dan
1116 (mod 13) = 9
2 (mod 13) = 81 (mod 13) = 3.
1132 (mod 13) = 3
2 (mod 13) = 9 (mod 13) = 9.
Tidak perlu cari kuasa yang lebih tinggi bagi 11 sebab 1164 > 11
43
.
Perhatikan bahawa
1143 = 11
32 * 1111 = 11
32 * 118
* 113 = 11
32 * 118
* 112
* 11
MTE3143 APLIKASI MATEMATIK
97
Oleh itu, 1143 (mod 13) = 11
32 * 118
* 112 * 11 (mod 13)
= 9 * 9 * 4 * 11 (mod 13)
= 81 * 44 (mod 13)
= 81 * 44 (mod 13)
= 3 * 5 (mod 13)
= 15 (mod 13)
= 2
3.6.3 Teorem Kecil Fermat
Fungsi Euler φ bagi integer m ditakrifkan sebagai bilangan integer positif yang
kurang atau sama dengan m dan perdana relatif (relatively prime) kepada m.
Aktiviti
Cari φ(n) bagi n = 1, 2, 3, …, 20.
Semak bahawa n = p x q bagi dua nombor perdana p dan q,
φ(n) = (p – 1) (q – 1)
Teorem Kecil Fermat menyatakan bahawa bagi setiap integer yang
perdana relatif kepada n,
aφ(n) ≡ 1(mod n).
Aktiviti Bekerja secara berkumpulan, pilih satu nilai n antara 10 dan 20. (a) Cari φ(n)
(b) Semak bahawa aφ(n) ≡ 1(mod n).
MTE3143 APLIKASI MATEMATIK
98
3.6.4 Sistem Rivest-Shamir-Adleman (RSA)
Salah satu kriptosistem kunci umum yang paling awal adalah sistem
RSA yang dicipta oleh Ted Rivest, Adi Shamir dan Leonard Adleman.
Sistem RSA bergantung kepada kesukaran memfaktorkan nombor yang
besar dan penggunaan aritmetik modular serta teori nombor.
Sistem RSA boleh diterangkan seperti berikut:
Menyediakan Sistem
Pilih dua nombor perdana yang besar, p dan q, di mana panjang setiap satu
100 digit. Nombor perdana ini dirahsiakan.
Biar n = p x q. Nombor n dihebahkan secara umum tetapi pengetahuan
n tidak memungkinkan anda menentukan nilai p dan q kerana kesukaran
memfaktorkan nombor ini.
Fungsi Euler φ(n) = (p – 1)(q – 1) merupakan bilangan integer antara 1 dan
n yang perdana relatif kepada n – iaitu, bilangan nombor integer yang faktor
sepunya dengan n adalah 1. Fungsi Euler φ(n) mempunyai ciri bagi sebarang
integer a antara 0 dan n – 1 di mana
a 1 + k.φ(n) = a mod n .
Pilih integer positif rawak E < φ(n) , di mana E perdana relatif kepada
φ(n). E, seperti n, diumumkan – E bersama n menjadi kunci umum.
Sebab pihak yang menyediakan kod ketahui rahsia nombor perdana p dan q,
mereka juga ketahui nilai φ(n) = (p – 1)(q – 1), tetapi nilai ini dirahsiakan
daripada orang ramai. Jadi bagi pihak yang menyediakan kod, adalah
mudah untuk mencari songsang E modulo φ(n) – iaitu nombor D di mana
D.E ≡ 1 mod φ(n)
MTE3143 APLIKASI MATEMATIK
99
Iaitu nombor D yang memberikan
D.E = 1 + k.φ(n) , bagi sebarang integer k.
Nombor D ini juga dirahsiakan.
Secara ringkas,
Kunci rahsia: p, q, φ(n), D Kunci umum: n, E.
Enkripsi
Langkah pertama adalah untuk mewakili sebarang mesej sebagai urutan
integer. Setiap mesej dipecahkan kepada beberapa blok digit, setiapnya
merupakan nombor yang kurang daripada n. Setiap blok boleh dikodkan
secara berasingan.
Biarkan P sebagai blok dalam mesej – iaitu integer antara 0 dan n – 1.
Sekarang biarkan C = P E
mod n,
Iaitu, kita naikkan kuasa P ke kuasa E dan mencari bakinya selepas dibahagi
dengan n.
Dengan cara demikian, C dienkripkan atau mesej berkod yang selaras
denga mesej asal P, dan C ialah mesej yang ditransmisikan dengan apa
jua kaedah (mungkin kurang selamat) yang digunakan.
Dekripsi
Untuk menyahkodkan mesej C, kita cari P secara mengira
P = C D mod n
.Oleh kerana C = P E mod n,
MTE3143 APLIKASI MATEMATIK
100
Kita akan dapat
C D mod n = P
E.D mod n
= P 1 + k.φ(n) mod n
= P mod n , sebab 0 < P < n.
Keberkesanan Kod RSA
Semasa kod RSA diperkembangkan, adalah dijangka yang masa
untuk memfaktorkan nombor 200 digit n = p x q akan mengambil masa sejuta
tahun dengan bantuan algoritma komputer terpantas di dunia ketika itu.
Kini, dengan komputer yang cepat dan canggih, kaedah pengkodan sebegini
mungkin akan ditewaskan pada satu masa. Oleh yang demikian, sistem-
sistem kriptografi yang baru sentiasa dicipta demi menampung keperluan
keselamatan dan kerahsiaan ketika menyimpan data dan transmisi
maklumat digital. Minat dalam penggunaan Kriptografi Kunci Umum telah
memesatkan lagi penyelidikan dan perkembangan teknik pemfaktoran
nombor dan teori nombor secara umum.
Contoh Pengiraan Algoritma RSA
#1: Pilih nilai p dan q (nombor perdana)
p= 7, q =11 iaitu n = 7 x 11 = 77
#2: Cari nilai Φ(n) =(p-1)(q-1)
Φ(n) = (7-1)(11-1) = 6 x 10 =60
#3: Pilih nilai e (nombor yg relatif perdana)
e = 13
MTE3143 APLIKASI MATEMATIK
101
#4: Cari nilai d di mana d·e = 1 mod Φ(n) - Kaedah Euler
d·13 = 1 mod 60 1 = 3 – 1 x 2
60 = 4 x 13 + 1 x 8 = 3 – 1 x (5 – 1 x 3)
13 = 1 x 8 + 1 x 5 = 2 x 3 – 1 x 5
8 = 1 x 5 + 1 x 3 = 2 x (8 – 1 x 5) – 1 x 5
5 = 1 x 3 + 1 x 2 = 2 x 8 – 3 x 5
3 = 1 x 2 + 1 x 1 = 2 x 8 – 3 (13 – 1x 8)
2 = 2 x 1 + 0 = 5 x 8 – 3 x 13
= 5 (60 – 4 x 13) – 3 x 13
= 5 x 60 – 23 x 13
Maka, d = – 23
Nilai d negatif, maka perlu ditukar kepada yang positif, iaitu d = 60 – 23 = 37
#5: Jika diberi M = 26, cari C
C = Me
mod n 261 mod 77 = 26
= 2613 mod 77 26
2 mod 77 = 676 mod 77 = 60
= 268 26
4 261
mod 77 264 mod 77 = 60
2 mod 77 = 58
= 53 x 58 x 26 mod 77 268 mod 77 = 58
2 mod 77 = 53
= 71 x 26 mod 77
= 75
#6 : Semakan – guna M = Cd
mod n
M = 7537
mod 77 751 mod 77 = 75
= 7532
754 75
1 mod 77 752 mod 77 = 5625 mod 77 = 4
= 4 x 16 x 75 mod 77 754 mod 77 = 4
2 mod 77 = 16
= 64 x 75 mod 77 758 mod 77 = 16
2 mod 77 = 25
= 26 7516 mod 77 = 25
2 mod 77 = 9
7532 mod 77 = 9
2 mod 77 = 4
102