BAB II LANDASAN TEORI 2.1 Definisi Matriks
Matriks adalah susunan sekelompok bilangan dalam bentuk persegi atau persegi panjang yang diatur menurut baris dan kolom. Matriks yang mempunyai m baris dan n kolom disebut matriks m × n (yaitu ‘m kali n’) atau matriks berordo m × n. Suatu matriks ditunjukkan dengan menuliskan elemennya diantara kurung 5 7 2 besar, misalnya adalah matriks 2 × 3, yaitu matriks ‘2 kali 3’, dengan 5, 6 3 8 7, 2, 6, 3, 8 adalah elemen-elemennya. Perhatikan bahwa dalam menyatakan matriks, yang pertama disebutkan adalah banyaknya baris dan yang kedua adalah banyaknya kolom. Matriks merupakan susunan sekumpulan bilangan; tidak ada hubungan aritmatik antar elemen-elemennya. Matriks berbeda dengan determinan, karena tidak ada harga numeris suatu matriks yang diperoleh dari perkalian antar elemennya. Juga, pada umumnya baris dan kolom tidak dapat dipertukarkan seperti dalam determinan. 1
2.1.1 Pengertian Ordo Suatu Matriks
Untuk memahami pengertian ordo atau jenis sebuah matriks perhatikan contoh 11 12 berikut ini: A = . Banyak baris 2 dan banyak kolom 2, dikatakan matriks 9 10 A berordo atau berjenis 2 × 2 (dibaca: 2 kali 2). Matriks A yang berordo 2 × 2 ini dituliskan sebagai: A2×2. Angka 2 × 2 ditulis agak ke bawah sebagai subskrip. Banyak elemen matriks A sama dengan 4 = 2 × 2, yaitu merupakan perkalian antara banyak baris dengan banyak kolom dari matriks A.
1
Howard Anton and Christ Rorres, Elementary Linear Algebra Application Version, hal 25
Universitas Sumatera Utara
2.1.2 Operasi Pada Matriks
Terdapat beberapa operasi aritmatika pada matriks seperti: 1.
Perkalian Matriks. Perkalian matriks A dengan matriks B (ditulis A • B) ada hasilnya, jika banyak kolom matriks A (matriks yang kiri) sama dengan banyak baris matriks B (matriks yang kanan). Mengalikan tiap elemen pada baris matriks sebelah kiri dengan kolom matriks sebelah kanan, lalu hasilnya dijumlahkan. a b p ap + bq = A• B = c d q cp + dq
2.
Invers matriks. Jika A dan B masing-masing adalah matriks persegi dan mempunyai ordo yang sama, serta berlaku hubungan: A • B = B • A = I Maka B adalah invers A dan A adalah invers B (A dan B saling invers) a b Jika matriks A = dengan det A = (ad − bc) maka invers dari matriks c d A ditentukan oleh: A−1 =
d −b 1 dengan syarat bahwa: ad − bc −c a
det A = (ad − bc) ≠ 0 Sedangkan untuk perhitungan invers dari matriks berukuran 3 × 3 adalah sebagai berikut: Untuk itu maka langkah pertama adalah mencari nilai determinan untuk matriks 3 × 3 di atas terlebih dahulu dengan menggunakan aturan Sarrus. K11 Det K = K 21 K 31
K12 K 22 K 32
K13 K 23 = K 33
(K11 * K22 * K33) + (K12 * K23 * K31) + (K13 * K21 * K32) − (K31 * K22 * K13) − (K32 * K23 * K11) − (K33 * K21 * K12)
Untuk matriks 4 x 4 maka perhitungannya adalah: K11 K Det K = 21 K 31 K 41
K12 K 22 K 32 K 42
K13 K 23 K 33 K 43
K14 K 24 K 34 K 44
Universitas Sumatera Utara
Det K =
(K11 * Determinan3x3 (K22, K23, K24, K32, K33, K34, K42, K43, K44)) – (K12 * Determinan3x3 (K21, K23, K24, K31, K33, K34, K41, K43, K44)) + (K13 * Determinan3x3 (K21, K22, K24, K31, K32, K34, K41, K42, K44)) (K14 * Determinan3x3 (K21, K22, K23, K31, K32, K33, K41, K42, K43))
Jika elemen-elemen pada baris ke-i dan kolom ke-j dari matriks A itu dihapuskan maka akan diperoleh matriks persegi berordo 2. Determinan dari matriks persegi berordo 2 itu disebut minor dari determinan matriks A, dilambangkan dengan |Mij|. Minor dari determinan matriks A sering disebut sebagai minor aij. Sebagai contoh jika baris pertama dan kolom pertama dari matriks A dihapuskan:
a11 a21 a 31
a12 a22 a32
a13 a23 a33
Baris yang dihapuskan
Kolom yang dihapuskan
a Sehingga 22 a32
a23 a22 sehingga minornya | M11 | = a33 a32
a23 dan M11 disebut a33
dengan minor a11. Jika | Mij | adalah minor aij dari matriks A, maka bentuk (−1)i+j | Mij | disebut kofaktor dari aij. Kofaktor dari aij dilambangkan dengan αij. Jadi, kofaktor aij dapat ditentukan dengan rumus: αij = (−1)i + j | M ij | . Sebagai contoh: Kofaktor dari a11 adalah α11 = (−1)1+1 |M11| = + |M11| Kofaktor dari a12 adalah α12 = (−1)1+2 |M12| = − |M12| Kofaktor dari a13 adalah α13 = (−1)1+3 |M13| = + |M13| Kofaktor dari a21 adalah α21 = (−1)2+1 |M21| = − |M21| Kofaktor dari a22 adalah α22 = (−1)2+2 |M22| = + |M22| Kofaktor dari a23 adalah α23 = (−1)2+3 |M23| = − |M23| Kofaktor dari a31 adalah α31 = (−1)3+1 |M31| = + |M31| Kofaktor dari a32 adalah α32 = (−1)3+2 |M32| = − |M32| Kofaktor dari a33 adalah α33 = (−1)3+3 |M33| = + |M33|
Universitas Sumatera Utara
Sedangkan untuk adjoin misalkan A adalah matriks persegi berordo 3 dalam a11 bentuk: A= a21 a 31
a12 a22 a32
a13 a23 dengan αij adalah kofaktor dari aij maka adjoin matriks a33
α11 A (disingkat: adj A) ditentukan oleh: adj A = α12 α 13
α 21 α 22 α 23
α31 α32 α33
Untuk mencari invers dari matriks ini maka digunakan persamaan berikut K−1 =
2.2
1 adj K . 2 det K
Pengertian Citra
Citra adalah representasi atau deskripsi tentang suatu objek. Citra juga dapat diartikan sebagai objek pada bidang dua dimensi. Citra dapat direpresentasikan ke dalam citra analog dan citra digital. Citra analog dihasilkan dari sistem optik, misalnya mata manusia, kamera, sedangkan citra digital dihasilkan dari hasil digitisasi citra analog. Gambar 2.1 merupakan contoh citra analog.
Gambar 2.1 Citra Analog
Citra digital adalah representasi numerik dari objek-objek. Citra digital dibentuk oleh sekumpulan angka dalam array dua dimensi. Tiap angka menggambarkan warna dari tiap titik dalam gambar sesuai dengan mode warna yang digunakan. Titik-titik ini disebut pixel yang merupakan singkatan dari picture element (elemen gambar). Gambar 2.2 menunjukkan citra digital.
2
Ibid, Howard Anton and Christ Rorres, hal 30.
Universitas Sumatera Utara
Citra Digital
Pixel Citra 24-bit 8-bit
8-bit
8-bit
R
G
B
Pixel
Gambar 2.2 Citra Digital Gambar di atas menunjukkan citra digital yang menggunakan 24-bit warna tiap pixel-nya. 24-bit warna dibagi ke dalam tiga bagian sebesar 8-bit, tiap bagian merupakan representasi intensitas warna dasar yaitu merah, hijau, dan biru (RGB). 3
2.2.1 Mode Warna
Menampilkan sebuah citra pada layar monitor diperlukan lebih informasi mengenai letak dari pixel-pixel pembentuk citra. Untuk memperoleh gambaran yang tepat dibutuhkan juga informasi tentang warna-warna yang dipakai untuk menggambarkan sebuah citra digital. Beberapa mode warna yang sering digunakan: 1.
Bitmap Mode, memerlukan 1-bit data untuk menampilkan warna dan warna yang dapat ditampilkan hanya warna hitam dan putih (monokrom)
2.
Indexed Color Mode, mengurutkan warna dalam jangkauan 0-255 (8-bit)
3.
Grayscale Mode, menampilkan citra dalam 256 tingkat keabuan
4.
RGB Mode, menampilkan citra dalam kombinasi tiga warna dasar (red, green, dan blue), tiap warna dasar memiliki intensitas warna 0-255 (8-bit)
5.
CMYK Mode, menampilkan citra dalam kombinasi empat warna dasar (cyan, magenta, yellow dan black), tiap warna memiliki intensitas 0-255 (8-bit)4
2.2.2 Penyimpanan Citra
Menyimpan citra ke dalam media penyimpanan dalam bentuk digital memiliki bentuk yang beragam. Ada dua cara penyimpanan yang biasa dilakukan oleh 3 4
A. Munir, Pengantar Pengolahan Citra, hal 10 Paul Bourke, Bicubic Interpolation for Image Scaling, http:// astronomy.swin.edu.au/~pbourke/bitmap/
Universitas Sumatera Utara
perangkat lunak yaitu bitmap dan vector. Dalam hal ini sering juga digunakan istilah program paint dan program draw. Program paint atau program berbasis bitmap menyimpan citra sebagaimana ditampilkan di layar yaitu sebagai array dari pixel-pixel. Perubahan yang dilakukan pada citra dengan menggunakan program ini akan mengubah langsung tiap titik atau pixel pada citra. Kelebihan cara ini adalah kemudahannya untuk menampilkan gambar secara rinci dengan pola-pola yang kompleks atau gambar fotorealistik, yang tidak dapat dengan mudah direpresentasikan sebagai model matematika. Program draw atau program berbasis vector menyimpan citra sebagai model matematika, dan setiap elemen citra disimpan secara terpisah. Perubahan yang dilakukan pada citra menggunakan program ini akan mengubah deskripsi matematika yang menyusun gambar dan program menghitung perubahan yang perlu pada warnawarna pixel secara tidak langsung. Kelebihan cara ini adalah kemampuannya untuk menciptakan gambar dalam resolusi yang berbeda tanpa kehilangan mutu gambar yang berarti.
2.2.2.1 Format File Citra BMP
Format file BMP merupakan format standar sistem operasi Windows dan IBM OS/2. Format ini mendukung mode warna dari Bitmap Mode hingga RGB Mode. BMP mudah dibuka dan disimpan, tetapi ada beberapa aturan khusus yang harus dicermati, diantaranya: 1.
Format file ini menyimpan datanya secara terbalik, yaitu dari bawah ke atas
2.
Citra dengan resolusi warna 8-bit, lebar citra harus merupakan kelipatan dari 4, bila tidak maka pada saat penyimpanan akan ditambahkan beberapa byte pada data hingga merupakan kelipatan dari 4.
3.
Citra dengan resolusi warna 24-bit, urutan penyimpanan tiga warna dasar adalah biru, hijau, merah (B, G, R). Lebar citra dikalikan dengan 3 harus merupakan kelipatan dari 4, bila tidak maka pada saat penyimpanan akan ditambahkan beberapa byte pada data hingga merupakan kelipatan dari 4.
4.
BMP mendukung pemampatan run length encoding (RLE) Format file BMP secara jelas dapat dilihat pada Tabel 2.1 berikut ini:
Universitas Sumatera Utara
Tabel 2.1 Format File BMP 5 Name Header
Size
Description
14 bytes
Signature
2 bytes
‘BM’
File Size
4 bytes
File Size in bytes
Reserved
4 bytes
Unused (= 0)
Data Offset
4 bytes
File Offset to Raster
40 bytes
Windows Structure:
Info Header
BITMAPINFOHEADER
Size
4 bytes
Size of Info Header = 40
Width
4 bytes
Bitmap Width
Height
4 bytes
Bitmap Height
Planes
2 bytes
Number of planes ( = 1)
BitCount
2 bytes
Bits per Pixel 1 = monocrome palette, NumColors = 1 4 = 4 bit palletized, NumColors = 16 8 = 8 bit palletized, NumColors = 256 16 = 16 bit RGB, NumColors = 65536 24 = 24 bit RGB, NumColors = 16 M
Compression
4 bytes
Types of Compression 0 = BI_RGB (no compression) 1 = BI_RLE8 (8 bit RLE encoding) 2 = BI_RLE4 (4 bit RLE encoding)
ImageSize
4 bytes
(compressed) Size of Image It is valid to set this = 0 if compressed = 0
XpixelsPerM
4 bytes
Horizontal Resolution: Pixels/meter
YpixelsPerM
4 bytes
Vertical Resolution: Pixels/meter
ColorsUsed
4 bytes
Number of actually used colors
ColorImportant 4 bytes Color Table 5
4
*
Number of important colors = 0 all NumColors Present only if info. BitsPerPixel ≤ 8
Ibid, Paul Bourke.
Universitas Sumatera Utara
(bytes)
Color should be ordered by importance
Red
1 byte
Red Intensity
Green
1 byte
Green Intensity
Blue
1 byte
Blue Intensity
Reserved
1 byte
Unused ( = 0)
Repeated NumColors Times Raster Data
Info.ImageSize
The Pixel Data
(bytes)
2.2.2.2 Format File Citra GIF
Format file GIF ( Graphics Interchange Format) merupakan hasil rancangan CompuServe Incorporated. Format ini dirancang untuk memudahkan pertukaran citra bitmap antarkomputer. GIF hanya mendukung resolusi warna sampai 256 warna (8bit). Format file GIF memiliki dua versi yaitu GIF 87a dan GIF89a. Versi GIF89a diperkenalkan pada bulan Juli 1989 merupakan perbaikan dari versi GIF87a. Pada GIF89a ditambahkan kemampuan untuk menampilkan citra dengan latar belakang transparan ( background transparency), penyimpanan data citra secara interlaced dan kemampuan untuk menampilkan citra animasi. GIF menggunakan variable-length code yang merupakan modifikasi dari algoritma LZW (Lemple-Ziv Wetch) untuk memampatkan data citra. Teknik pemampatan data ini mampu menghasilkan pemampatan yang baik dan merupakan teknik pemampatan yang mampu mengembalikan data sama persis dengan aslinya (lossless data comperssion). Format lengkap file citra GIF dapat dilihat pada Tabel 2.2 berikut ini. Tabel 2.2 Format File GIF 6 Name
Size
Description
Signature
6 bytes
‘GIF87a’ or ‘GIF89a’
Global Descriptor
7 bytes
Always present
6
D. C Kay, & J. R Levine, Graphics File Formats 2nd Edition, hal 35
Universitas Sumatera Utara
Width
2 bytes
Width in pixels
Height
2 bytes
Height in pixels
Flags
1 bytes
Global descriptor flags =1 if Global ColorMap exists (should be
Global Color Map
true in almost all cases)
Bit 7
=0 if default map is used. Or if every image has a Local Color Map
Color Resolution
Bit 6-4
+1 = significant bits per color in Global
Bits Reserved Pixel Bits
Background Color Aspect Ratio
Color Map Bit 3
=0
Bit 2-0
+1 = Color Depth, Number of Global Colors := 2colordepth
1 byte
Color Map or default map) 1 byte Number
Global Color Map
Red
Green
Blue
Background color number (from Global
Usually =0 of Global color table, present only when
Global Colors * Global Descriptor Flags Global Color Map 3
=1
1 byte
Red intensity of color (not necessarily 8 significant bits)
1 byte
Green intensity of color (not necessarily 8 significant bits)
1 byte
Blue intensity of color (not necessarily 8 significant bits)
Repeated Number Of Global Colors Times Extension Blocks
Cannot be pre Optional, may be repeated any number of calculated
times. Read first byte to check its precense
Header
1 byte
= $21
Function Code
1 byte
There is a list of known function codes
1 byte
>0 !
Length bytes
Interpretation of this data depends on its
Length Data
function code
Universitas Sumatera Utara
Repeated any number of times. Read first byte to check for terminator Terminator Local Descriptor Header Pos X
1 byte
=0
10 bytes
Local descriptor, always present
1 bytes
=$2C
2 bytes
Horizontal position of image in global image
Pos Y
2 bytes
Vertical position of image in global image
Width
2 bytes
Width of image
Height
2 bytes
Height of image
Flags
1 bytes
Local descriptor Flags
Bit 7
=1 if Local Color Map exists
Local Color Map
=0 if Global Color Map (or default map) is used
Interlaced Image Sorted Reserved Pixel Bits
Bit 6
=1 Interlaced! =0 Non Interlaced
Bit 5
Usually =0
Bit 4-3
=0
Bit 2-0
-1= Color Depth, Number of Local Colors := 2color depth
Number of
Local color table, present only when local
Local Color * 3
Descriptor Flags. Local Color Map =1
Red
1 byte
Red intensity of color
Green
1 byte
Green intensity of color
Blue
1 byte
Blue intensity of color
Local Color Map
Repeated number of Local Color times Rasted DataBlock
Initial Code Size Length Data
Cannot be pre Always present calculated 1 byte
Usually = Color Depth, except for balck & white, where it is 2!
1 byte
>0
Length bytes
The
pixel
data
bit
stream.
See
decompression and compression schemes
Universitas Sumatera Utara
Repeated any number of times, read first byte to check for terminator Terminator
1 byte
=0!
Cannot be pre Optional. Read first byte to check its
Extension Blocks
calculated
presence
Format is identical to the Extension Block above 1 byte
Terminator
=$3B
2.2.3.3 Format File Citra JPEG
Format file Joint Photographic Experts Group (JPEG) atau yang biasa disingkat JPG meningkat pesat penggunaannya. Format ini terkenal karena ukurannya yang mini dibandingkan dengan format-format lainnya. JPEG mendukung mode warna RGB, CMYK dan Grayscale, tetapi tidak mampu menampilkan citra dengan latar belakang transparan. Format JPEG menterjemahkan informasi tersebut menjadi komponen luminance (komponen cahaya) dan dua komponen chromatic (komponen perubahan warna dari hijau ke merah dan dari biru ke kuning). Untuk kompresinya format file citra ini menggunakan kompresi JPEG. Format lengkap dari JPEG dapat dilihat pada Tabel 2.4 berikut ini. Tabel 2.3 Format File JPEG7 Name
Size
Description
SOI marker
2 bytes
(FF D8)
APP0 marker
2 bytes
(FF E0)
Length
2 bytes
Identifer
5 bytes
(“JFIF” or “JFXX”) + terminator (00)
Version
2 bytes
Ex. (01 02) → ver.1.02
Units
1 byte
Units for the X and Y densities, units =0: no units , S and Y specify the pixel aspect ratio Units = 1: X and Y are dots per inch
7
Ibid, D. C Kay, & J. R Levine, hal 40
Universitas Sumatera Utara
Units =2: X and Y are dots per cm Xdensity
2 bytes
Horizontal pixel density
Ydensity
2 bytes
Vertical pixel density
Xthumbnail
1 byte
Thumbnail horizontal pixel count
Ythumbnail
1 byte
Thumbnail vertical pixel count
(RGB)n
3n bytes
Packed (24-bit) RGB values for the thumbnail pixels, n = Xthumbnail * Y thumbnail
Data
x bytes
EOI marker
2 bytes
2.3
(FF D9)
Pengertian Kriptografi
Kriptografi adalah seni dan ilmu pengetahuan untuk memproteksi pengiriman data dengan mengubahnya menjadi kode tertentu dan hanya ditujukan untuk orang yang hanya memiliki sebuah kunci untuk mengubah kode itu kembali. Kata kriptografi berasal dari bahasa Yunani, “kryptos” yang berarti rahasia, dan “graphos” yang berarti menulis. Kriptografi mencakup dua buah proses yaitu melakukan enkripsi pada tulisan atau pesan yang bersifat rahasia ataupun melakukan proses kebalikannya yaitu dekripsi pesan rahasia (kode atau cipher) dengan menggunakan kunci. Hasil pesan atau data yang diacak atau dikenal sebagai ciphertext atau kriptogram. Proses enkripsi biasanya melibatkan sebuah algoritma dan sebuah kunci. Algoritma enkripsi adalah suatu metode pengacakan yang merupakan suatu program komputer dalam bentuk kumpulan-kumpulan perintah. Data yang akan dienkripsi dapat berupa pesan broadcast ataupun data digital. Pesan rahasia dapat disembunyikan atau disamarkan dengan berbagai cara. Enkripsi atau pengkodean, suatu pesan berarti mengubah pesan tersebut dari bentuk yang dapat dibaca dan dimengerti oleh setiap orang menjadi sekumpulan simbol atau kode yang hanya diketahui oleh beberapa orang. Cara menyembunyikan pesan seperti ini adalah bentuk kriptografi yang sederhana, karena pesan yang ditulis secara normal hanya disembunyikan dengan teknik yang sederhana. Meskipun pesan tersebut agak sulit untuk dipecahkan cara ini mudah diterapkan karena kata-kata dan
Universitas Sumatera Utara
simbol telah ditetapkan atau dibuat terlebih dahulu. Alasan kode-kode tersebut sulit untuk dipecahkan adalah tidak ada suatu cara untuk memecahkan kode-kode tersebut secara logis. Gambar 2.3 di bawah ini merupakan beberapa teknik dalam menyembunyikan pesan. Teknik-teknik tersebut merupakan teknik yang sederhana dan mudah diterapkan.
Gambar 2.3 Beberapa Teknik Enkripsi Sederhana
Pada gambar di atas terlihat teknik pertama dengan menuliskan pesan rahasia dengan menggunakan tinta khusus seperti tinta dari asam dari jeruk. Pesan dapat dibaca jika menggunakan lilin yang diterangi pada bagian tersebut. Pada teknik substitusi cipher, pesan secara lengkap ditulis kembali. Kumpulan dari huruf-huruf baru diatur secara alphabet (kanan atas) atau berdasarkan pada nilai numerik dari huruf. Cara mudah dipecahkan karena terjadi pengulangan huruf. 8 Dalam pengertian luasnya, kriptografi juga mencakup penggunaan untuk menyembunyikan pesan, cipher, dan kode-kode. Penyembunyian pesan, seperti ini menyembunyikan teks asli seperti ditulis dengan tinta yang tidak dapat terlihat, tingkat keberhasilan bergantung pada apakah tinta yang tidak terlihat ini dicurigai atau tidak. Sekali ditemukan, maka biasanya sudah sangat mudah untuk dipecahkan. Penggunaan kode, berupa kata-kata, angka-angka, atau simbol yang mewakili huruf 8
Microsoft Encarta Encyclopedia 2005 Premium Edition, 2004
Universitas Sumatera Utara
atau frase, biasanya tidak mungkin untuk dibaca tanpa adanya kunci dari buku kode. Kriptografi juga mencakup penggunaan komputer sebagai alat untuk memproses enkripsi dan melindungi transmisi data dan pesan. Saat ini kebanyakan sistem komunikasi meninggalkan beberapa data dan informasi yang direkam atau disimpan. Sebagai contoh, komunikasi melalui saluran telepon, termasuk faksimile dan pesan melalui e-mail, menghasilkan suatu rekaman dari nomor telepon yang dipanggil pada saat panggilan dilakukan. Transaksi finansial, data medis, pilihan pada jenis film-film yang disewa, dan bahkan pilihan atas menu makanan yang dipesan sewaktu melakukan jamuan pada restoran mungkin dapat dilakukan pelacakan pada kartu kredit penerima atau untuk rekaman bagi pihak asuransi. Setiap waktu seorang menggunakan telepon atau kartu kredit, perusahaan telepon atau institusi finansial menyimpan suatu rekord atas nomor yang dipanggil atau jumlah transaksi, lokasi dan tanggal. Pada masa yang akan datang, jaringan telepon menjadi sistem digital, bahkan percakapan biasa dapat direkam dan disimpan. Semua data yang disimpan tersebut mungkin akan dilakukan proses pengiriman dari satu tempat ke tempat lain bagi pihak yang membutuhkan. Untuk menghindari data tersebut jatuh ke tangan yang tidak berkepentingan maka biasanya data tersebut akan dilakukan proses enkripsi untuk menjamin kerahasiaan data itu sendiri. Kriptografi sangat penting tidak hanya sebagai privasi saja. Kriptografi melindung sistem perbankan dunia dengan baik. Banyak bank dan institusi finansial melakukan transaksi bisnis pada jaringan yang terbuka, seperti Internet. Tanpa adanya kemampuan untuk memproteksi transaksi bank dan komunikasi, para kriminal dapat mengganggu atau menyadap transaksi tersebut dan mencuri uang tanpa dapat dilacak.
2.3.1 Jenis-Jenis Pengamanan Data
Ada beberapa jenis pengamanan data, termasuk pengkodean, steganografi (menulis secara tersembunyi dan rahasia), dan cipher. Pengkodean berdasarkan buku kode. Steganografi adalah cara lain untuk menyembunyikan atau menyamarkan tulisan. Cipher mencakup penggunaan komputer untuk menghasilkan cipher (teks yang telah diacak) dan ini dihasilkan dengan menggunakan metode enkripsi. Jenis-jenis cipher
Universitas Sumatera Utara
yang berbeda tergantung pada huruf alphabet, numerik, metode pengacakan dan penggunaan komputer.9
2.3.1.1 Pengkodean Dan Buku Kode
Sebuah kode yang dikonstruksi atau disusun dengan baik dapat mewakili frase dan kalimat secara keseluruhan dengan simbol tertentu, seperti grup dengan lima huruf, sering dipakai karena lebih ekonomis daripada kerahasiaannya. Kode yang disusun dengan baik dapat memberikan tingkat sekuritas yang tinggi, tetapi kesulitan dalam mencetak dan mendistribusi buku kode (buku yang berisi simbol-simbol atau kode) dengan kondisi yang secara mutlak rahasia membatasi orang untuk menggunakannya kecuali buku kode tersebut dapat terjaga secara efektif. Sebagai tambahan, semakin banyak buku kode yang dipakai, maka tingkat keamanan semakin berkurang. Bayangkan sebuah buku kode yang terdiri atas dua kolom. Pada kolom pertama terdiri atas sekumpulan daftar dari kata yang dipakai oleh komandan militer yang mungkin perlu dan dipakai dalam berkomunikasi. Sebagai contoh, daftar tersebut terdiri dari semua kemungkinan area geografis dari suatu daerah, semua kemungkinan waktu, dan semua istilah militer. Pada kolom berikutnya adalah sekumpulan dari daftar yang terdiri atas kata-kata biasa. Untuk membentuk sebuah pesan yang dikodekan, encoder (orang yang menerjemahkan bentuk pesan asli ke bentuk kode atau simbol)
menuliskan semua pesan yang asli. Kemudian
menggantikannya dengan kata yang tercantum pada buku kode dengan mencocokkan pada kolom kedua untuk kata-kata dalam pesan dan menggunakan kata baru untuk menggantikannya. Sebagai contoh misalkan terdapat pesan “Serang Vladivostok pada waktu subuh” dan buku kode terdiri atas pasangan untuk kata-kata tersebut: serang = beruang, Vladivostok = bola, pada = kalender, waktu = pintu, dan subuh = jeruk. Maka bentuk pesan yang dikodekan menjadi: Beruang bola kalender pintu jeruk. Jika pesan yang dikodekan tersebut jatuh ke tangan musuh, musuh hanya dapat mengetahui bahwa itu pada pesan yang dikodekan, tanpa buku kode musuh tidak mempunyai cara untuk mendekripsi pesan tersebut. Buku kode mempunyai beberapa kelemahan. Sebagai contoh, jika pesan yang dikodekan tersebut jatuh ke 9
Ibid, Microsoft Encarta Encyclopedia 2005 Premium Edition.
Universitas Sumatera Utara
tangan musuh dan hari berikutnya Vladivostok diserang pada waktu subuh, musuh dapat menghubungkan peristiwa tersebut dengan pesan yang dikodekan ini. Jika pesan yang lain terdiri atas kata “bola” berhasil didapatkan, maka pada hari berikutnya, jika terjadi sesuatu hal di Vladivostok, musuh dapat mengasumsikan bahwa bola = Vladivostok dalam buku kode. Dengan bertambahnya waktu, musuh dapat menempatkan lebih banyak pasangan kata yang ada pada kode buku, dan bahkan suatu saat dapat memecahkan pesan. Untuk alasan ini, salah satu caranya adalah sering mengganti pasangan kata dalam buku kode. 10
2.3.1.2 Steganografi
Steganografi adalah suatu metode untuk menyembunyikan keberadaan dari pesan dengan menggunakan alat seperti tinta yang tidak terlihat, tulisan mikroskopik, atau menyembunyikan kode kata dalam kalimat dari suatu pesan (seperti membuat hilang kata kelima dalam suatu teks yang merupakan bagian dari pesan). Kriptografi dapat mengaplikasikan steganografi pada komunikasi elektronik. Aplikasi ini disebut dengan sekuritas transmisi. Steganografi atau tulisan rahasia, kelihatannya telah dikembangkan sejak adanya tulisan. Bahkan pada masa Mesir kuno, dimana tulisan merupakan suatu misteri bagi rata-rata orang, dua bentuk yang jelas dari tulisan dipakai. Tulisan sakral atau hieratik dipakai sebagai komunikasi rahasia oleh para kaum paderi, dan tulisan demotik dipakai oleh masyarakat biasa. Yunani dan Romawi kuno, begitu juga dengan peradaban yang lain berkembang dalam waktu yang sama, menggunakan bentuk steganografi. Penemuan sistem menulis singkat (steno) yang pertama mungkin ditujukan untuk tulisan rahasia. Steno berkembang dan dipakai secara luas pada masa Romawi kuno dengan Tironian notes, suatu sistem yang ditemukan oleh Marcus Tullius Tiro pada tahun 63 sebelum masehi. 11
10 11
Ibid, Microsoft Encarta Encyclopedia 2005 Premium Edition http://www.wikipedia.org/steganografi
Universitas Sumatera Utara
2.3.1.3 Ciphers
Cipher populer karena mudah dalam pemakaiannya. Ada dua jenis cipher secara umum. Cipher substitusi memerlukan satu cipher alphabet untuk menggantikan plaintext dengan huruf atau simbol yang lain. Cipher transposisi menggunakan pergeseran huruf dalam satu kata untuk membuat kata tersebut tidak mempunyai arti. Cipher adalah kode rahasia yang dipakai untuk enkripsi pesan berupa plaintext. Cipher dengan variasi tipe telah ditemukan, tetapi semuanya kebanyakan berupa cipher substitusi atau cipher transposisi. Cipher komputer adalah cipher yang dipakai pada pesan digital. Cipher komputer berbeda dari cipher substitusi atau transposisi biasa dimana pada cipher komputer memakai aplikasi komputer untuk melakukan enkripsi data. Istilah kriptografi kadang-kadang dibatasi pada penggunaan cipher atau metode yang dilibatkan untuk menggantikan huruf yang lain atau simbol pada huruf asli dari pesan. Salah satu contoh bentuk dari pesan cipher adalah pada masa perang dunia pertama,
yaitu
yang
dikenal
sebagai
Zimmermann
Telegram
(Telegram
Zimmermann). Sebelum Amerika Serikat memasuki Perang Dunia I, pemerintah Jerman mencoba untuk menghasut perang antara Amerika Serikat dan Meksiko. Pada tanggal 19 Januari 1917, sekretaris luar negeri Jerman, Arthur Zimmermann, mengirimkan sebuah telegram yang telah di-encode pada perwakilan diplomatiknya di Meksiko, meminta mereka untuk menyetujui aliansi rahasia dengan pemerintah Meksiko. Tetapi inteligen Inggris berhasil mencegat dan dengan cepat men-decode pesan tersebut, dan mengirimkannya pada Presiden Woodrow Wilson. Protes keras dari publik Amerika menyebabkan deklarasi perang oleh Amerika melawan Jerman. Telegram yang di-encode, seperti terlihat pada di bawah ini dan teks yang berhasil di-decipher. German Legation Jan. 19,1917 via Galveston
MEXICO CITY
130 13042 13401 8501 115 3528 416 17214 6491 11310 18147 18222 21560 10247 11518 23677 13605 3494 14936 98092 5905 11311 10392 10371 0302 21290 5161 39695
Universitas Sumatera Utara
23571 17504 11269 18276 18101 0317 0228 17694 4473 22284 22200 19452 21589 67893 5569 13918 8958 12137 1333 4725 4458 5905 17166 13851 4458 17149 14471 6706 13850 12224 6929 14991 7382 15857 67893 14218 36477 5870 17553 67893 5870 5454 16102 15217 22801 17138 21001 17388 7446 23638 18222 6719 14331 15021 23845 3156 23552 22096 21604 4797 9497 22464 20855 4377 23610 18140 22260 5905 13347 20420 39689 13732 20667 6929 5275 18507 52262 1340 22049 13339 11265 22295 10439 14814 4178 6992 8784 7632 7357 6926 52262 11267 21100 21272 9346 9559 22464 15874 18502 18500 15857 2188 5376 7381 98092 16127 13486 9350 9220 76036 14219 5144 2831 17920 11347 17142 11264 7667 7762 15099 9110 10482 97556 3569 3670
BERNSTORFF.
Charge German Embassy.
TELEGRAM RECEIVED.
FROM 2nd from London # 5747.
“We intend to begin on the first of February unrestricted submarine warfare. We shall endeavor in spite of this to keep the United States of America neutral. In the event of this not succeeding, we make Mexico a proposal of alliance on the following basis: make war together, make peace together, generous financial support and an understanding on our part that Mexico is to reconquer the lost territory
in
Texas,
New
Mexico,
and
Arizona.
The
settlement
in
detail is left to you. You will inform the President of the above most secretly as soon as the outbreak of war with the United States of America is certain and add the suggestion that he should, on his own initiative, invite Japan to immediate adherence and at the same time
mediate
between
Japan
and
ourselves.
Please
call
the
President's attention to the fact that the ruthless employment of our submarines now offers the prospect of compelling England in a few months to make peace.” Signed, ZIMMERMANN. 12
12
Op. Cit, Microsoft Encarta Encyclopedia 2005 Premium Edition
Universitas Sumatera Utara
A.
Substitution Ciphers
Pada cipher substitusi sederhana, sejumlah huruf atau simbol digantikan pada tiap huruf. Huruf-huruf yang disubstitusi pada urutan normal, biasanya dengan pembagian normal untuk tiap kata. Cipher seperti ini dapat dikenali dengan kemunculan dari sekumpulan huruf normal yang berulang-ulang ditempatkan pada huruf yang salah. Jenis cipher ini dapat dipecahkan dengan menggunakan analisis yang berulang-ulang dan memperhatikan karakteristik pada sejumlah huruf, seperti kecenderungan bentuk ganda, kata umum seperti awalan dan akhiran, huruf pertama dan terakhir pada kata, dan kombinasi yang umum, seperti “qu”, “th”, “er”, dan “re”. Cipher substitusi dipakai dengan menyusun kembali huruf-huruf dalam alphabet. Sebagai contoh, suatu cipher yang ditemukan pada masa lalu oleh Julius Caesar. Cipher tersebut didapat dengan menggeser (shift) semua huruf dalam alphabet dengan tiga tempat. Jadi, ketika huruf diperlukan, huruf “a” yang ingin dipakai maka ditulis dengan huruf “d”, dan huruf “b” ditulis dengan huruf “e”. Huruf-huruf tersebut bersambung kembali pada awal huruf jika sampai pada akhir dari alphabet. Jadi, jika seseorang ingin melakukan cipher huruf “z”, maka huruf tersebut ditulis sebagai huruf “c”. Begitu juga dengan huruf “y” ditulis sebagai huruf “b”. Cipher secara keseluruhan dinyatakan dalam dua baris huruf. Baris-baris ini disebut dengan lookup table. ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC Ketika seseorang ingin mengenkripsi sebuah kata, dia harus melihat pada huruf asli pada baris atas dan menggunakan huruf ciphertext yang berkorespondensi pada baris bawah. Jadi sebagai contoh, kata “HELLO” akan dituliskan sebagai “KHOOR”. Untuk melakukan dekripsi pada kata yang dikodekan, seseorang harus mencari pada huruf pada baris atas dan menuliskan kembali berdasarkan pada huruf yang koresponden pada baris atas. Jadi, kata “KHOOR” didekripsi balik menjadi “HELLO” Cipher substitusi di atas mudah untuk diingat dan juga mudah dipecahkan. Untuk membuat cipher substitusi lebih kompleks, beberapa substitusi (multiplesubstitution) dan kadang-kadang angka juga ditambahkan pada cipher.
Universitas Sumatera Utara
Pada multiple-substitution atau polyalphabetic cipher, sebuah kata kunci atau angka ditambahkan. Huruf pada pesan pertama boleh dienkripsi dengan menambahkannya dengan nilai numerik dari huruf pertama dari kata kunci; huruf kedua dari pesan juga dilakukan proses yang sama, menggunakan kata kunci pada huruf kedua, dan seterusnya, perulangan kata kunci sering dan perlu untuk mengenkripsi seluruh pesan. Ketika menambahkan pada angka numerik dari huruf dari kata kunci pada huruf di pesan, dimulai dengan menghitung dengan huruf pada pesan. Jadi, untuk melakukan enkripsi pada kata “TODAY” dengan kata kunci “DIG”, huruf “T” menjadi “W”,
karena “D” merupakan huruf keempat dari
alphabet; “O” menjadi “W”, karena “I” adalah huruf kesembilan dari alphabet; dan “D” menjadi “J”, karena “G” adalah huruf ketujuh dari alphabet. Sisa dari huruf tersebut di-encode dengan cara yang sama, dan kata “TODAY” dikodekan menjadi “WWJDG”. Dengan memakai kombinasi dari jenis cipher dasar tersebut, cipher dapat dibentuk hingga beberapa tingkat kompleksitas. Kata kunci bagaimana pun juga harus mudah diingat atau dipergunakan, tanpa kata kunci tersebut cipher tidak mungkin dibalik menjadi pesan asli. Dengan sedikit waktu, kebanyakan cipher dapat dipecahkan jika kata kunci mereka diketahui, tetapi untuk tujuan khusus yang memerlukan kompleksitas yang tinggi maka semakin tinggi juga tingkat keamanannya. Perintah-perintah dalam militer harus dijaga secara rahasia untuk beberapa jam saja, sebagai contoh dapat dienkripsi dalam bentuk cipher.
B.
Transposition Cipher
Pada cipher transposisi, urutan huruf pada plaintext diganti untuk diturunkan menjadi ciphertext. Pesan biasanya ditulis tanpa adanya pembagian kata dalam baris huruf yang disusun dalam bentuk blok persegi panjang. Huruf-huruf kemudian ditranspos dalam urutan yang telah diatur, seperti dalam bentuk vertikal, diagonal, atau spiral, atau dengan bentuk yang lebih kompleks, seperti knight’s tour, yang berdasarkan arah perpindahan biji knight pada catur. Pengaturan huruf-huruf dalam pesan yang dienkripsi bergantung pada ukuran dari kode blok pada kata yang dipakai dan pada rute yang diikuti dengan huruf-huruf yang ditransisi.
Universitas Sumatera Utara
Suatu cipher pada tiap pasang huruf dipertukarkan sebagai contoh dalam cipher transposisi. Dalam kasus ini, sebagai contoh, cipher teks dari kata “elephant” menjadi “lepeahtn”. Huruf pertama dan kedua akan dipertukarkan, dan huruf ketiga dan keempat juga dipertukarkan, dan seterusnya. Cipher transposisi dapat dikombinasikan dengan cipher substitusi untuk menghasilkan suatu pesan yang dikodekan agar lebih kompleks. 13
2.4
Hill Cipher
Sejak kekaisaran Romawi, kriptosistem yang lebih rumit dikembangkan oleh orang seperti oleh ahli Matematika Italia Leon Battista Alberti (lahir pada tahun 1404), Matematikawan Jerman Johannes Trithernius (lahir pada tahun 1492), seorang kriptographer dan diplomat Perancis Blaise de Vigenére (1523−1596), Lester S. Hill, yang menemukan Hill Cipher (Hill Cipher) pada tahun 1929. Hill Cipher merupakan jenis lain dari polygraphic cipher. Sandi ini mengenkripsi suatu string huruf menjadi bentuk string yang lain dengan panjang yang sama. Teknik Hill Cipher dikembangkan oleh Lester S. Hill pada Hunter College dan dipublikasikan pada Americian Mathematical Monthly, Volume 36, Issue 6 (Juni−Juli, 1929) halaman 306 − 312. Hill Cipher menggunakan matriks untuk mentransformasi string berupa blok huruf.
14
Hill Cipher berdasarkan pada aljabar linier dan seperti sandi Vigenére, Hill Cipher merupakan block cipher. Sandi ini dapat dipecahkan dengan known-plaintext attacks tetapi tahan melawan ciphertext-only attack. Cara kerja sandi ini berdasarkan atas perkalian matriks dengan menggnakan sebuah kunci K.
Penjelasan mengenai Hill Cipher ini dapat diuraikan sebagai berikut: Misalkan m adalah bilangan bulat positif dan P = C = (Z26)m dan misalkan K = { m × m merupakan matriks yang nilai elemennya terdiri dari Z26}, maka untuk suatu kunci K, dapat didefinisikan sebagai eK(x) = K x Mod 26 dan dK(y) = K−1 y Mod 26 dimana semua operasi dilakukan dalam matriks Z26.
13 14
http://www.mjidor.com/lektion8.shtml Paal Schiefloe, Cryptography:Hill-ciphers an application of Linear Algebra, http://students.washington.edu/paalsch/math/cryptography.htm
Universitas Sumatera Utara
Karena K−1 dengan mudah dapat dihitung dari K, maka Hill Cipher merupakan suatu kriptosistem asimetrik. Hill Cipher juga merupakan blok cipher linier umum. Suatu blok cipher linier dapat dengan mudah dipecahkan yang dikenal cara known-plaintext attacks. Maka bagi penyerang yang mengetahui beberapa contoh plaintext dengan enkripsi yang berhubungan, tidaklah sulit baginya untuk mencari kunci yang dipakai untuk mengenkripsi plaintext tersebut. Bahkan enkripsi dengan teks yang tidak diketahui dapat didekripsi tanpa harus memerlukan usaha yang sulit. Metode dari perhitungan frekuensi sering dipakai untuk usaha ini. Metode ini mengeksplorasi perulangan (redundancy) dari bahasa alami yang dipakai sebagai plaintext pada pesan. Sebagai contoh, pada banyak bahasa huruf “E” sering muncul dengan persentasi dalam bahasa Inggris mencapai 12,31%, 15,87% untuk bahasa Perancis, dan bahkan 18,46% dalam bahasa Jerman. Penjelasan cara kerja dari Hill Cipher dapat disederhanakan dengan cara seperti ini. Misalkan K merupakan sebuah matriks kunci m × m yang merupakan representasi dari suatu persamaan linier. Ciphertext (C) dan plaintext p merupakan matriks m × 1. Maka didapat persamaan untuk menghasilkan ciphertext sebagai berikut: C = K . P (mod 26)
C1 k11 C2 = k21 C k 3 31
k12 k22 k32
k13 P1 k23 P2 mod 26 k33 P3
Dekripsi memerlukan kunci K yang bersifat invertible. Contohnya K . K−1 (mod 26) = I dimana I merupakan matriks identitas. Karena C = K . P Mod 26 maka K = C . P−1 Mod 26 Tidak semua plaintext bersifat invertible (dapat dibalik kembali). Sandi Caesar, Hill Cipher, dan sandi Playfair semua bekerja dengan sebuah alphabet tunggal saat disubstitusi.
Universitas Sumatera Utara
2.4.1 Pengenkripsian Hill Cipher
Langkah-langkah untuk proses enkripsi plaintext dengan Hill Cipher adalah sebagai berikut: 1. Pilih suatu matriks kunci K yang berupa matriks bujur sangkar yang dipakai sebagai kunci. 2. Transformasikan tiap huruf dalam teks ke bilangan bulat yang sesuai (A = 1; B = 2; … Z = 26) 3. Kelompokkan barisan angka yang didapat ke dalam beberapa blok vektor P yang panjangnya sama dengan ukuran matriks K. 4. Hitung C = K . P (mod 26) untuk tiap vektor P. 5. Kembalikan tiap angka dalam vektor sandi C ke huruf yang sesuai untuk mendapatkan teks sandi.
Input Matriks Kunci K
Plaintext
Transformasi ke Bentuk Nilai
Ciphertext
Transformasi ke Bentuk Huruf
Susun Hasil dalam Bentuk Matriks P
C = K . P (Mod 26)
Gambar 2.4 Ilustrasi Proses Enciphering Hill Cipher
Bagian ini akan menjelaskan enkripsi dengan Hill Cipher dengan memberikan contoh. Hill Cipher menggunakan matriks untuk mentransformasikan string plaintext menjadi ciphertext. Untuk mentransformasikan plaintext maka pertama sekali semua huruf alphabet dinyatakan dalam nilai seperti berikut:
A
B
C
D
E
F
G
H
I
H
K
L
M
1
2
3
4
5
6
7
8
9
10
11
12
13
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
14
15
16
17
18
19
20
21
22
23
24
25
26
Universitas Sumatera Utara
Misalkan terdapat pesan berikut yang akan dienkripsi dengan Hill Cipher:
Herbert Yardley wrote The American Black Chamber.
Selanjutnya adalah membagi pesan tersebut menjadi bentuk pasangan yang terdiri atas dua huruf (digraph)
he rb er ty ar dl ey wr ot et he am er ic an bl ac kc ha mb er
Jika pesan tidak terdiri atas jumlah huruf dalam nilai genap, maka harus ditambahkan sebuah karakter null pada akhir pesan. Setelah itu tiap pasangan dikonversi ke bentuk nilai berdasarkan ekivalen dari huruf pada tabel di atas.
8
5
18 2
5 18
20 25
1 18
4
12
5 25
23 18
15 20
5 20
8
1 13
5
18
9 3
1
2
1 3
11 3
8 1
13 2
14
12
5
5 18
Tiap pasangan string di atas akan di-encipher dengan menggunakan matriks
3 7 . 5 12
kunci 2 × 2
Lakukan encipher pada pasangan pertama dan dinyatakan sebagai vektor kolom (h(8) e (5)), kemudian dikalikan dengan matriks kunci.
3 7 8 59 5 12 5 = 100
Hasil yang didapat perlu dimodulokan dengan bilangan 26 karena jumlah maksimum alphabet sebanyak 26 buah.
59 7 mod 26 ≡ 100 22 mod 26
Universitas Sumatera Utara
Didapat ciphertext G(7) V(22)
Untuk pasangan berikutnya r (18) b (2)
3 7 18 16 5 12 2 mod 26 ≡ 10 mod 26
dan hasil 16 berkorespondensi dengan P dan 10 berkorespondensi dengan J. Lakukan cara di atas untuk setiap pasangan huruf sehingga diperoleh. 15 GVPJKGAJYMRHHMMSCCYEGVPEKGVCWQLXXOBMEZAKKG
2.4.2 Pendekripsian Hill Cipher
Algoritma proses pendekripsian Hill Cipher dapat diuraikan dalam bentuk langkahlangkah sebagai berikut: 1. Hitung matriks K−1 (mod 26) sebagai kunci pembuka. K−1 ada jika FPB ((det(K), 26) = 1. 2. Lakukan langkah-langkah 2−5 pada enkripsi dengan mengganti: (i)
Matriks K dengan matriks K−1.
(ii) Blok vektor teks asli P dengan blok vektor sandi C dan sebaliknya. Hitung K-1
Ciphertext
Transformasi ke Bentuk Nilai
Plaintext
Transformasi ke Bentuk Huruf
Susun Hasil dalam Bentuk Matriks C
P = K-1 . C (Mod 26)
Gambar 2.5 Ilustrasi Proses Deciphering Hill Cipher
15
Chris Christensen, The Hill Cipher, 2003, hal 2-13
Universitas Sumatera Utara
Sebagai contoh untuk memgembalikan hasil yang didapat di atas maka hal yang harus dilakukan adalah menghitung invers dari matriks kunci di atas. Untuk membentuk plaintext menjadi ciphertext pada contoh di atas dilakukan dengan:
3 7 8 7 mod 26 ≡ ≡ 5 12 5 22 mod 26
Untuk membalikkan persamaan di atas maka perlu dicari nilai invers dari matriks kunci.
3 7 8 7 mod 26 ≡ 5 12 5 22 mod 26
? ? maka: ? ?
Jika akan dicari matriks
8 5
untuk mendapatkan
Dengan persamaan ini
3 7 dan 5 12
Matriks yang akan dicari disebut dengan invers dari −1
3 7 dinyatakan dengan . 5 12 Untuk mencari nilai invers dari suatu matriks maka dapat dengan mudah menggunakan cara seperti ini.
Universitas Sumatera Utara
d ad − bc a b = c d −c ad − bc −1
−b ad − bc . a ad − bc
−b d a b a b ad − bc ad − bc a b 1 0 Produk dari = = a c d 0 1 c d c d −c ad − bc ad − bc −1
yang mana hasil terakhir tersebut disebut dengan matriks identitas karena efek perkalian matriks identitas dengan suatu matriks akan menghasilkan matriks itu sendiri. Ini sama halnya dengan mengkalikan sebuah bilangan real dengan 1. Perhatikan bahwa agar dapat dibagi oleh ad – bc, maka harus terdapat sebuah invers perkalian untuk ad − bc yang merupakan salah satu dari 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, atau 25. Jika tidak maka proses enciphering tidak dapat dibalik.
a b nilai ad−bc disebut dengan determinan dari c d
Pada matriks
a b c d .
Perhatikan bahwa ini merupakan hasil perkalian antara nilai kiri atas dengan kanan bawah secara diagonal dikurangi dengan perkalian antara nilai kiri bawah dengan nilai kanan atas secara diagonal. Nilai determinan tersebut harus berupa nilai 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, atau 25 modulo 26.
3 7 adalah 3 × 12 − 5 × 7 = 1 ≡ 1mod 26 . 5 12
Jadi determinan dari
3 7 adalah 5 12
Jadi invers dari
−1
3 7 12 −7 12 19 5 12 = −5 3 mod 26 ≡ 21 3 mod 26
Contoh di atas merupakan kasus spesial karena determinannya adalah 1.
Universitas Sumatera Utara
Sebagai catatan matriks 3 × 3 dapat dipakai untuk mengenkripsi trigraph. Dan matriks 4 × 4 dapat dipakai untuk meng-encipher string yang terdiri dari empat huruf dan seterusnya. 16
2.4.3 Memecahkan Hill Cipher
Seperti diketahui Hill Cipher dapat dipecahkan dengan cara known plaintext attacks. Berikut ini merupakan penjelasan dari cara memecahkan Hill Cipher. 5 15 8 2 0 10 Misalkan = K = , K = , K 17 16 3 5 24 20 Dari dua pasangan pertama didapat:
5 8 15 2 = 17 3 16 5
K
−1
5 8 9 2 Perhitungan invers dari: = 17 3 1 15 Perhitungan matriks kunci:
15 2 9 2 7 8 = 16 5 1 15 19 3
K =
7 8 0 10 Lakukan pengecakan kunci K dengan pasangan ketiga: = 19 3 24 20 7 8 Jika hasilnya sama maka matriks kuncinya adalah . 19 3
2.4.4 Kriptanalisis Hill Cipher Kriptanalisis dari 2 × 2 matriks Hill Cipher berdasarkan analisis dari frekuensi digraph. Hanya terdapat 26 frekuensi pada karakter tunggal, tetapi terdapat 26 × 26 = 262 = 676 frekuensi digraph yang harus diperhitungkan. Untuk matriks 3 × 3 maka terdapat trigraph dan terdapat kemungkinan 263 = 17.576 trigraph untuk dianalisis. Matriks 4 × 4 dipakai untuk meng-encipher string empat huruf; terdapat 264 = 456.976 kemungkinan untuk string empat huruf ini. Matriks 5 × 5 dipakai untuk meng-encipher string lima huruf, terdapat 265 = 11.881.376 kemungkinan dan 16
Ibid, Chris Christensen.
Universitas Sumatera Utara
seterusnya. Beberapa sistem kriptografi modern dapat meng-encipher lebih satu pesan panjang dalam satu blok. Para ahli matematika mengenal matriks. Matriks sering dipakai untuk aplikasi matematika. Dari contoh memecahkan Hill Cipher di atas dengan matriks kunci 2 × 2 dapat dengan mudah dipecahkan. Secara umum, mengetahui n plain-ciphertext digraph yang saling berkorespondensi maka Hill Cipher dengan kunci n × n dapat dipecahkan. 17
2.4.5 Dasar Matematika Penyandian Citra pada Hill Cipher
Penyandian dengan Hill Cipher pada citra seperti halnya dengan teks juga menggunakan matriks dimana ketentuannya menggunakan matriks bujur sangkar. Matriks bujur sangkar adalah matriks dengan jumlah baris = jumlah kolom. Matriks bujur sangkar disebut matriks identitas (I) jika semua elemen diagonal utamanya sama dengan satu dan elemen lainnya sama dengan nol. Invers suatu matriks A adalah matriks B sedemikian hingga A . B = I. Invers matriks A ada jika determinan (A) ≠ 0. Misal a dan b adalah bilangan-bilangan bulat. Bilangan bulat c disebut faktor persekutuan a dan b jika c|a dan c|b. Bilangan bulat tak negatif d disebut faktor persekutuan terbesar (FPB) a dan b jika d adalah faktor persekutuan a dan b dan untuk setiap c, jika c|a dan c|b maka d|c. 18 Sebagai contoh, faktor persekutuan 12 dan 18 adalah {±1, ±2, ±3, ±6}, dan FPB(12,18) = 6. Dua buah bilangan bulat a dan b dikatakan relatif prima jika FPB (a, b) = 1. Syarat ini tidak mengharuskan a dan b merupakan bilangan prima. Sebagai contoh, FPB (9,26) = 1 sehingga 9 dan 26 merupakan bilangan-bilangan yang relatif prima, meskipun masing-masing bilangannya bukan bilangan prima. Misalkan n adalah bilangan bulat positif, a dan b adalah bilangan-bilangan bulat, a dikatakan kongruen terhadap b modulo n (ditulis a ≡ b (mod n)) jika (a − b)|n. Bilangan-bilangan bulat modulo n (simbol Zn) adalah himpunan bilangan17 18
http://www.prenhall.com/divisions/esm/app/ph-linear/kolman/html/proj6.html http://www.math.umass.edu/~murray/Hillciph.pdf
Universitas Sumatera Utara
bilangan bulat {0, 1, 2, …, n − 1}. Operasi aritmatika pada Zn dilakukan terhadap modulo n. Sebagai contoh, dalam Z26, maka 13 + 16 = 3 karena 13 + 16 = 29 Mod 26 ≡ 3 (mod 26). Misalkan a ∈ Zn. Invers a modulo n adalah suatu bilangan bulat x ∈ Zn. Sehingga a . x ≡ 1 (mod n). Jika x ada, maka x tunggal, dan a dikatakan memiliki invers, yang ditulis sebagai a−1. a ∈ Zn memiliki invers bila dan hanya bila FPB(a, n) = 1. Dalam Z26, semua elemen ganjil kecuali 13 memiliki invers. Dalam Z256, semua elemen ganjilnya mempunyai invers karena semua faktor 256 merupakan bilangan genap.
2.4.6 Algoritma Enkripsi dan Dekripsi Hill Cipher
Adapun algoritma enkripsi dari Hill Cipher dapat diuraikan sebagai berikut: a. Input matriks kunci K. b. Ubah pesan dalam bentuk teks menjadi nilai integer. c. Susun nilai integer pesan dalam bentuk matriks P. d. Lakukan perhitungan cipher C = K . P (Mod 26). e. Ubah hasil nilai integer hasil perkalian menjadi huruf kembali. f. Tampilkan hasil ciphertext.
Adapun algoritma dekripsi dari Hill Cipher dapat diuraikan sebagai berikut: a. Input matriks kunci K b. Lakukan invers matriks terhadap K. c. Ubah cipher dalam bentuk teks menjadi nilai integer. d. Susun nilai integer cipher dalam bentuk matriks C. e. Lakukan perhitungan plaintext P = K−1 . C (Mod 26). f. Ubah hasil nilai integer hasil perkalian menjadi huruf kembali. g. Tampilkan hasil plaintext.
Universitas Sumatera Utara