TUGASAN 1 (40%)

Tugasan 1 melibatkan pengumpulan dapatan daripada pelbagai sumber dan penulisan

laporan dengan pemberatan markah 40% daripada markah keseluruhan kerja kursus. Anda

perlu melengkapkan tugasan ini secara INDIVIDU.

Arahan:

1. Anda dikehendaki meneroka peranan kod dan kriptografi dalam teknologi moden.

2. Bincangkan dengan jelas kegunaan dan kepentingan kod pembetulan kesilapan

dalam teknologi moden. Antara kod pembetulan kesilapan yang biasa digunakan ialah

Kod Semakan Parity dan Kod Hamming. Terangkan dengan terperinci langkah-

langkah untuk mengesan kesilapan dan membuat pembetulan. Seterusnya banding

kedua-dua kod pembetulan kesilapan dan membuat kesimpulan.

3. Senaraikan bahan rujukan / sumber maklumat yang berkaitan.

---------------------------------------------------------------------------------------------------------------------------

Kriptografi sudah digunakan oleh bangsa Mesir sejak 4000 tahun yang lalu oleh raja-

raja Mesir pada saat perang untuk mengirimkan pesan rahasia kepada panglima perangnya

melalui kurir-kurinya. Orang yang melakukan penyandian ini disebut kriptografer, sedangkan

orang yang mendalami ilmu dan seni dalam membuka atau memecahkan suatu algoritma

kriptografi tanpa harus mengetahui kuncinya disebut kriptanalis.

Usaha untuk menjaga kerahasiaan suatu informasi telah ada sejak jaman dahulu.

Julius Caesar, kaisar Romawi, telah menggunakan metoda enkripsi sederhana dengan cara

menggeser setiap karakter dalam pesannya dengan nilai tertentu. Cara ini cukup aman pada

saat itu namun tidaklah mungkin dipakai saat ini karena dengan kemampuan komputasi

komputer sekarang, akan sangat mudah dipecahkan.

Seiring dengan perkembangan teknologi, algoritma kriptografi pun mulai berubah

menuju ke arah algoritma kriptografi yang lebih rumit dan kompleks. Kriptografi mau tidak

mau harus diakui mempunyai peranan yang paling penting dalam peperangan sehingga

algoritma kriptografi berkembang cukup pesat pada saat Perang Dunia I dan Perang Dunia

II. Menurut catatan sejarah, terdapat beberapa algoritma kriptografi yang pernah digunakan

dalam peperangan, diantaranya adalah ADFVGX yang dipakai oleh Jerman pada Perang

Dunia I, Sigaba/M-134 yang digunakan oleh Amerika Serikat pada Perang Dunia II, Typex

1

oleh Inggris, dan Purple oleh Jepang. Selain itu Jerman juga mempunyai mesin legendaris

yang dipakai untuk memecahkan sandi yang dikirim oleh pihak musuh dalam peperangan

yaitu, Enigma.

Di zaman ini, implementasi dari kriptografi banyak ditemui dalam kehidupan sehari-

hari, seperti Automatic Teller Machine (ATM), Penggunaan ATM untuk banking, bahkan

mulai meningkat menjadi Internet Banking, Mobile Banking, Komunikasi elektronik seperti

telepon tetap, cellular, SMS, MMS. 3G, Komunikasi via Internet seperti email, messaging,

chatting, Voice Call dan E-Government , E-Commence.

Kriptografi adalah ilmu dan seni untuk menjaga keamanan pesan ketika pesan di

kirim dari suatu tempat ke tempat yang lain. Kriptografi dapat juga diartikan sebagai ilmu

yang mempelajari mengenai bagaimana cara mengamankan suatu informasi. Pengamanan

ini dilakukan dengan mengenkrip informasi tersebut dengan suatu kunci khusus. Terdapat

empat prinsip yang harus dipenuhi oleh sebuah algoritma kriptografi, yakni kerahasiaan,

keotentikan, keutuhan data, dan terhindar dari penyalahgunaan.

Algoritma kriptografi yang baik tidak ditentukan oleh kerumitan dalam mengolah data

atau pesan yang akan disampaikan. Yang penting, algoritma tersebut harus memenuhi

4 persyaratan berikut :

Confidelity (kerahasiaan), yaitu layanan agar isi pesan yang dikirimkan tetap rahasia

dan tidak diketahui oleh pihak lain (kecuali puhak pengirim, pihak penerima, atau

pihak-pihak yang memiliki ijin). Umumnya hal ini dilakukan dengan cara membuat

suatu algoritma mamtematis yang mampu mengubah data hingga menjadi sulit untuk

dibaca dan dipahami.

Authentication (keotentikan), yaitu layanan yang berhubungan dengan identifikasi.

Baik otentikasi pihak-pihak yang terlibat dalam pengiriman data maupun otentikasi

keaslian data atau informasi.

Data integrity (keutuhan data), yaitu layanan yang mampu mengenali atau

mendeteksi adanya manipulasi (penghapusan, pengubahan atau penambahan) data

yang tidak sah (oleh pihak lain).

2

Non-repudiation (anti-penyalahgunaan), yaitu layanan yang dapat mencegah suatu

pihak untuk menyangkal aksi yang dilakukan sebelumnya (menyangkal bahwa pesan

tersebut berasal darinya).

Kriptografi pada dasarnya terdiri dari dua proses penting, yaitu proses enkripsi dan

proses dekripsi. Proses enkripsi adalah proses penyandian pesan terbuka menjadi pesan

rahasia (ciphertext). Ciphertext inilah yang nantinya akan dikirimkan melalui saluran

komunikasi terbuka. Pada saat ciphertext diterima oleh penerima pesan, maka pesan

rahasia tersebut diubah lagi menjadi pesan terbuka melalui proses dekripsi sehingga pesan

tadi dapat dibaca kembali oleh penerima pesan. Dalam sistem komputer, pesan terbuka

(plaintext) diberi lambang M, yang merupakan singkatan dari Message. Plaintext ini dapat

berupa tulisan, foto, atau video yang berbentuk data biner.

ELEMEN-ELEMEN KRIPTOGRAFI

Dalam kriptografi, terdapat beberapa elemen-elemen yang secara langsung berhubungan

dengan kriptografi. Antaranya adalah :

§ Pesan, Plainteks dan Cipherteks

Pesan adalah data atau informasi yang dapat dibaca dan dimengerti maknanya.

Nama lain untuk pesan adalah plainteks. Agar pesan tidak bisa dimengerti maknanya

oleh pihak lain, maka pesan perlu disandikan ke bentuk lain yang tidak dapat

dipahami. Bentuk pesan yang tersandi disebut cipherteks

§ Pengirim dan Penerima

Pengirim adalah entitas yang mengirim pesan kepada entitas lainnya. Penerima

adalah entitas yang menerima pesan. Entitas di sini dapat berupa orang, mesin

(komputer), kartu kredit dan sebagainya.

§ Enkripsi dan dekripsi

Proses menyandikan plainteks menjadi cipherteks disebut enkripsi. Sedangkan

proses mengembalikan cipherteks menjadi plainteks semula dinamakan dekripsi.

§ Cipher

Algoritma kriptografi disebut juga cipher yaitu aturan untuk enciphering dan

deciphering, atau fungsi matematika yang digunakan untuk enkripsi dan dekripsi.

Konsep matematis yang mendasari algoritma kriptografi adalah relasi antara dua

3

buah himpunan yaitu himpunan yang berisi elemen-elemen plainteks dan himpunan

yang berisi cipherteks. Enkripsi dan dekripsi adalah fungsi yang memetakan elemen-

elemen antara kedua himpunan tersebut.

§ Sistem kriptografi

Sistem kriptografi merupakan kumpulan yang terdiri dari algoritma kriptografi, semua

plainteks dan cipherteks yang mungkin dan kunci.

§ Penyadap

Penyadap adalah orang yang berusaha mencoba menangkap pesan selama

ditransmisikan dengan tujuan mendapatkan informasi sebanyak-banyaknya

mengenai sistem kriptografi yang digunakan untuk berkomunikasi dengan maksud

untuk memecahkan cipherteks.

4

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.

Misalnya, jika perkataan ‘cetakan’ dikirim, ia mungkin diterima sebagai ‘cetekan’ atau

‘cetakau’. Dalam konteks topik ini, memang dapat dikenal pasti dengan mudah yang ralat

tipografikal (ejaan) telah berlaku dan perkataan yang betul diteka dengan tepat sebagai

‘cetakan’.

Misi Mariner6 telah menggunakan 6 digit binari untuk mengenkod setiap petak kecil

(piksel) dalam gambar Marikh. Apabila mengirim isyarat balik ke Bumi, Mariner6 mengirim

32 digit dengan 26 (=32-6) digit lebihan. Yang lebih mengkagumkan ialah terjemahan betul

bagi setiap rantaian yang mengandungi kurang daripada 8 ralat.

Proses mengenkod mesej bermula dengan penukaran teks biasa kepada satu

rantaian nombor dengan menggunakan abjad digital berikut. Dalam kod ini, setiap huruf

(dan juga tanda isyarat) diwakili oleh urutan 0 dan 1 sepanjang 5-digit. Oleh itu, urutan-

urutan tersebut merupakan nombor antara 0 dan 32 yang ditulis dalam sistem binari (asas

2).

5

Dalam kes Mariner6, 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.

6

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.

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,

Akan tetapi, kod semakan pariti tunggal hanya boleh mengesan bilangan ralat yang ganjil

tetapi tidak dapat membetulkannya.

7

KOD HAMMING

Teori kod pembetulan ralat telah bermula dengan usaha Richard Hamming dalam

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 tahun 1950, Richard Hamming telah memperkembangkan kod Hamming yang

merupakan kod linear yang dapat membetulkan ralat tunggal.

Jika ralat E = [e1 e2 e3 e4 e5 e6], persamaan boleh ditulis semula sebagai

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;

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.

8

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.

Pengedekodan Perkataan

Untuk mengdekodkan 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 pengdekodan

ini gagal.

Kegagalan pengdekodan dan ralat hanya berlaku jika dua atau lebih ralat saluran berlaku.

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

pengdekodan gagal.

9

Kod Hamming

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.

Kadar maklumat Kod Hamming

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.

10

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.

11