aplikasi aljabar linear pada kriptografi makalah …ini pokok-pokok aljabar linear, seperti sistem...

i

APLIKASI ALJABAR LINEAR PADA KRIPTOGRAFI

Makalah

Diajukan untuk Memenuhi Salah Satu Syarat

Memperoleh Gelar Sarjana Matematika

Program Studi Matematika

Oleh:

Lyawati

NIM: 153114025

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS SANATA DHARMA

YOGYAKARTA

2020

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

APPLICATION OF LINEAR ALGEBRA IN CRYPTOGRAPHY

Paper

Presented as Partial Fulfillment of the

Requirements to Obtain the Degree of Sarjana Matematika

Mathematics Study Program

Written by:

Lyawati

Student ID: 153114025

MATHEMATICS STUDY PROGRAM DEPARTMENT OF MATHEMATICS

FACULTY OF SCIENCE AND TECHNOLOGY

SANATA DHARMA UNIVERSITY

YOGYAKARTA

2020


vi

MOTTO

“Berusaha, kerja keras, tidak mudah menyerah serta selalu bersyukur”


vii

HALAMAN PERSEMBAHAN

Karya ini kupersembahkan untuk:

Kedua orang tuaku, keluargaku, serta sahabat-sahabatku


ix

ABSTRAK

Kriptografi adalah ilmu dan seni untuk menjaga keamanan pesan

ketika pesan dikirim dari suatu tempat ke tempat lain. Dalam tugas akhir

ini pokok-pokok aljabar linear, seperti sistem persamaan linear, matriks,

operasi matriks, operasi baris elementer, eliminasi Gauss-Jordan, matriks

invers, determinan matriks, matriks adjoin, dan aritmetika modular diap-

likasikan pada kriptografi dalam proses enkripsi dan dekripsi sandi dengan

menggunakan algoritma sandi Hill.

Kata kunci: Aljabar Linear, aritmetika modular, kriptografi, algoritma

sandi Hill


x

ABSTRACT

Cryptography is the science and art of maintaining message securi-

ty when messages are sent from one place to other place. In this final paper

topics of linear algebra, such as system of linear equations, matrices, ma-

trix operations, elementary row operations, Gauss-Jordan elimination, in-

verse of matrices, determinant of a matrix, adjoin matrices, and modular

arithmetic are applied to cryptography in the cipher encryption and decryp-

tion processes using Hill cipher algorithm.

Keywords: Linear algebra, modular arithmetic, cryptography, Hill cipher

algorithm


xiii

DAFTAR ISI

HALAMAN JUDUL ................................................................................................ i

HALAMAN JUDUL DALAM BAHASA INGGRIS ............................................ ii

HALAMAN PERSETUJUAN PEMBIMBING .................................................... iii

HALAMAN PENGESAHAN ................................................................................ iv

PERNYATAAN KEASLIAN KARYA .................................................................. v

MOTTO ................................................................................................................. vi

HALAMAN PERSEMBAHAN ........................................................................... vii

LEMBAR PERNYATAAN PERSETUJUAN .................................................... viii

ABSTRAK ............................................................................................................. ix

ABSTRACT ............................................................................................................. x

KATA PENGANTAR ........................................................................................... xi

DAFTAR ISI ........................................................................................................ xiii

BAB I PENDAHULUAN ........................................................................................ 1

A. Latar Belakang ............................................................................................. 1

B. Rumusan Masalah ........................................................................................ 1

C. Batasan Masalah ........................................................................................... 2

D. Tujuan Penulisan .......................................................................................... 2

E. Manfaat Penulisan ........................................................................................ 2

F. Metode Penulisan ......................................................................................... 2

G. Sistematika Penulisan ................................................................................... 2

BAB II ALJABAR LINEAR ELEMENTER .......................................................... 4

A. Sistem Persamaan Linear ............................................................................. 4

B. Matriks ......................................................................................................... 5

C. Sifat-sifat Operasi Matriks ........................................................................... 6


xiv

D. Matriks Transpos ........................................................................................ 14

E. Operasi Baris Elementer ............................................................................. 17

F. Bentuk Eselon Baris ................................................................................... 18

G. Eliminasi Gauss dan Eliminasi Gauss-Jordan ............................................ 19

H. Matriks Invers ............................................................................................ 21

I. Determinan Matriks .................................................................................... 29

J. Matriks Adjoin ........................................................................................... 43

BAB III APLIKASI ALJABAR LINEAR PADA KRIPTOGRAFI ..................... 45

A. Aritmetika Modular .................................................................................... 45

B. Kriptografi .................................................................................................. 56

C. Sandi Hill .................................................................................................... 56

D. Penguraian Sandi ........................................................................................ 60

BAB IV PENUTUP ............................................................................................... 68

A. Kesimpulan ................................................................................................. 68

B. Saran ........................................................................................................... 70

DAFTAR PUSTAKA ............................................................................................ 71


1

BAB I

PENDAHULUAN

A. Latar Belakang

Kriptografi merupakan suatu studi tentang membuat kode (encoding) dan

menerjemahkan kode (decoding) atas pesan-pesan rahasia. Kriptografi telah

digunakan sejak empat abad yang lalu dan berkembang pesat hingga

sekarang. Pada zaman dahulu kriptografi digunakan untuk mengirimkan pe-

san-pesan yang bersifat rahasia dan hanya penerima yang memiliki kunci

yang dapat menerjemahkan pesan rahasia tersebut. Namun, seiring berkem-

bangnya informasi dan teknologi di dunia, kegunaan kriptografi semakin

berkembang. Misalnya, untuk pengamanan pada ATM (Automatic Teller Ma-

chine) dengan mencegah terjadinya serangan terhadap ATM, internet bank-

ing, pay TV, dll.

Dalam bahasa kriptografi, sandi disebut cipher, pesan yang belum

disandikan disebut plaintext, dan pesan yang telah disandikan disebut cipher-

text. Proses mengubah plaintext menjadi ciphertext disebut encipher, dan se-

baliknya proses mengubah ciphertext menjadi plaintext disebut decipher. Sa-

lah satu bidang matematika yang digunakan dalam proses kriptografi adalah

aljabar linear. Dalam tugas akhir ini, penulis akan membahas bagaimana ap-

likasi aljabar linear dalam kriptografi dengan menggunakan algoritma Sandi

Hill.

B. Rumusan Masalah

Berdasarkan pembahasan di atas, penulis dapat merumuskan masalah da-

lam tugas akhir sebagai berikut :

1. Bagaimana penerapan aljabar linear pada kriptografi ?

2. Bagaimana menentukan kunci yang tepat untuk menerjemahkan pesan

rahasia agar tidak diketahui oleh orang lain ?


2

C. Batasan Masalah

Algoritma yang dibahas pada tugas akhir ini adalah algoritma Sandi

Hill yang menggunakan aritmetika modular untuk membuat dan mener-

jemahkan sandi atau pesan rahasia.

D. Tujuan Penulisan

Tujuan penulisan tugas akhir ini adalah untuk:

1. Mengetahui cara membuat pesan rahasia dan cara menerjemahkan pe-

san rahasia tersebut.

2. Menemukan kunci yang tidak dapat dipecahkan oleh orang lain selain

penerima pesan.

E. Manfaat Penulisan

Manfaat penulisan tugas akhir ini adalah:

1. Mendapatkan pengetahuan mengenai kriptografi.

2. Mendapatkan pengetahuan mengenai penerapan aljabar linear dalam

kriptografi.

F. Metode Penulisan

Metode penulisan yang digunakan dalam tugas akhir ini adalah metode

studi pustaka, yaitu dengan membaca serta mempelajari buku-buku yang

berhubungan dengan aljabar linear dan penerapannya pada kriptografi.

G. Sistematika Penulisan

BAB I PENDAHULUAN

A. Latar Belakang

B. Rumusan Masalah

C. Batasan Masalah

D. Tujuan Penulisan

E. Manfaat Penulisan

F. Metode Penulisan

G. Sistematika Penulisan


3

BAB II ALJABAR LINEAR

A. Sistem Persamaan Linear

B. Matriks

C. Sifat-sifat Operasi Matriks

D. Matrik Transpos

E. Operasi Baris Elementer

F. Bentuk Eselon Baris

G. Eliminasi Gauss dan Eliminasi Gauss-Jordan

H. Matriks Invers

I. Determinan Matriks

J. Matriks Adjoin

BAB III ALJABAR LINEAR PADA KRIPTOGRAFI

A. Aritmetika Modular

B. Kriptografi

C. Sandi Hill

D. Penguraian Sandi

BAB IV PENUTUP

A. Kesimpulan

B. Saran

DAFTAR PUSTAKA


4

BAB II

ALJABAR LINEAR ELEMENTER

A. Sistem Persamaan Linear

Persamaan linear dalam variabel adalah persamaan dalam ben-

tuk polinomial yang variabelnya berderajat satu atau nol dan tidak terjadi

perkalian antara variabelnya,

.

Sedangkan sistem persamaan linear adalah himpunan berhingga

banyak persamaan linear. Sistem persamaan linear disebut konsisten jika

sistem persamaan tersebut mempunyai penyelesaian. Jika sistem tak

mempunyai penyelesaian, maka sistem itu disebut tak konsisten. Contoh

sistem persamaan linear dua variabel dengan dua persamaan, yaitu

{

dengan adalah bilangan real.

Definisi 2.1.1

Sistem persamaan linear yang ruas kanannya semuanya sama dengan 0

disebut sistem persamaan linear homogen.

Contoh 2.1.2

{


5

B. Matriks

Matriks merupakan susunan bilangan berbentuk persegi panjang.

Bentuk atau ukuran matriks ditentukan oleh banyaknya baris dan kolom.

Matriks yang mempunyai baris dan kolom dikatakan berukuran

Matriks biasanya dinyatakan dengan huruf besar seperti dll.

Bilangan yang terdapat pada matriks disebut elemen matriks. Ele-

men yang terletak pada baris ke- dan kolom ke- dari matriks dinya-

takan dengan

( ) .

Dua matriks dikatakan sama jika kedua matriks tersebut mempunyai uku-

ran yang sama dan elemen-elemen yang bersesuaian di dalam matriks juga

sama.

Definisi 2.2.1

Jika matriks dan keduanya berukuran maka adalah

matriks berukuran yang elemen-elemennya memenuhi

dengan dan .

Definisi 2.2.2

Jika adalah matriks dan adalah skalar, maka hasil kali ada-

lah matriks yang diperoleh dengan mengalikan setiap elemen dari

dengan dan dinotasikan dengan

( ) ( )

Definisi 2.2.3

Jika adalah matriks berukuran dan adalah matriks berukuran

, maka hasil kali adalah matriks berukuran yang ele-

men-elemennya adalah

∑ .


6

Contoh 2.2.4

Diberikan matriks [

] dan matriks 0

1.

[

] 0

1

[

( ) ( )

]

[

].

Karena matriks berukuran dan matriks berukuran , maka

matriks berukuran

C. Sifat-sifat Operasi Matriks

Operasi matriks memiliki beberapa sifat sebagai berikut:

Teorema 2.3.1

Jika , dan adalah matriks dan adalah skalar, maka berla-

ku

a. (sifat komutatif pada penjumlahan)

b. ( ) ( ) (sifat asosiatif pada penjumlahan)

c. ( ) ( ) (sifat asosiatif untuk perkalian dengan skalar)

d. ( ) (sifat distributif)

e. ( ) (sifat distributif)

f. (sifat identitas perkalian)

Bukti :

a. Misalkan dan adalah matriks :


7

[

]

[

]

[

] [

]

[

]

[

]

[

] [

]

Jadi terbukti bahwa .

b. Misalkan , dan adalah matriks :

[

]

[

]

[

]


8

( ) ([

] [

],

[

]

([

], [

]

[

( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( )

]

[

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

]

[

]

([

] [

],

( )

Jadi terbukti bahwa ( ) ( )

c. Misalkan matriks dan sebarang skalar ,

[

]

( )


9

[

]

[

( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( )

]

[

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

]

[

]

( [

],

( )

Jadi terbukti ( ) ( )

d. Misalkan matriks dan sebarang skalar :

( ) ([

] [

],

[

( ) ( ) ( )

( ) ( ) ( )

( ) ( ) ( )

]

[

]

[

] [

]


10

[

] [

]

e. Misalkan matriks dan sebarang skalar ,

Misalkan ( ) dan , maka

( ) dan untuk dan

Karena dan adalah bilangan real dan

( ) maka untuk dan

Jadi, atau ( )

f. Misalkan adalah matriks :

[

]

= 1 [

] [

]

Jadi terbukti bahwa ■

Teorema 2.3.2

Jika dan adalah matriks dengan operasi penjumlahan dan perkalian

yang terdefinisi dan sebarang skalar , maka berlaku

a. ( ) ( ) (sifat asosiatif perkalian)

b. ( ) (sifat distributif kiri)

c. ( ) (sifat distributif kanan)

d. ( ) ( ) ( )


11

Bukti:

a. Misalkan matriks , matriks , dan matriks

Misalkan dan . Berdasarkan definisi perkalian

matriks:

∑

∑

Elemen ke- dari adalah ∑ ∑ (∑

)

dan elemen ke- dari adalah

∑ ∑

(∑

).

Karena

∑ (∑ )

∑ ∑

∑

(∑

),

maka ( ) ( )

b. Misalkan matriks dan matriks .

( ( )) ( ) ( ) (

) ( )

( ) ( ) (

)

( ) (

)

( ) ( ) ; .

Jadi terbukti ( )

c. Misalkan dan matriks matriks :


12

(( ) ) ( ) ( ) (

) ( )

( ) ( ) ( )

( ) (

)

( ) ( )

; .

Jadi terbukti ( ) .

d. Misalkan matriks dan matriks dan

( ) (∑ )

∑ ( )

(( ) )

Jadi terbukti ( ) ( )

( ) (∑ )

∑ ( )

∑ ( )

( ( ))

Jadi terbukti ( ) ( ). ■

Definisi 2.3.3

Matriks yang jumlah baris dan kolomnya sama disebut matriks persegi.

Elemen-elemen baris ke- dan kolom ke- merupakan diagonal utama

matriks persegi

Matriks persegi yang elemen-elemen pada diagonal utamanya adalah 1 dan

elemen-elemen lainnya adalah 0 disebut matriks identitas. Matriks identi-

tas dinotasikan dengan dan berbentuk sebagai berikut:


13

[ ]

.

Teorema 2.3.4

Jika adalah matriks , maka .

Bukti:

[

]

[ ]

[

]

[ ]

[

]

.

[ ]

[

]

[

]

. ■


14

Teorema 2.3.5

Jika adalah matriks , maka dan jika adalah matriks

, maka

Bukti:

[

]

[ ]

[

]

.

[ ]

[

]

[

]

■

D. Matriks Transpos

Matriks yang diperoleh dengan mengganti baris menjadi kolom

dan kolom menjadi baris disebut dengan matriks transpos. Lebih lanjut

akan dibahas pada subbab berikut ini.

Definisi 2.4.1

Jika adalah matriks , maka transpos (dinotasikan dengan )

adalah matriks yang diperoleh dengan menukar baris menjadi ko-

lom dari . Jika


15

[

]

maka

[

]

Teorema 2.4.2

Jika dan adalah matriks-matriks dengan operasi penjumlahan dan

perkalian yang terdefinisi dan sebarang skalar , maka berlaku

a. ( )

b. ( )

c. ( )

d. ( )

Bukti:

a. Misalkan adalah matriks .

Karena matriks maka berukuran dan

( ) berukuran . Misalkan adalah elemen ke- dari

maka adalah elemen ke- dari dan elemen ke- dari

( ) Jadi ( )

b. Misalkan dan adalah matriks , dan .

Misalkan adalah elemen ke- dari Elemen

ke- dari adalah yang merupakan elemen

ke- dari .

Jadi, ( ) .

c. Misalkan matriks dan ( ) Maka ( ( ))

(( ) ) .

Jadi, ( )


16

d. Misalkan matriks dan matriks .

Maka adalah matriks dan adalah matriks

sehingga adalah matriks berukuran . Misalkan

( ) dan ( ) Menurut definisi perkalian

matriks, elemen ke- dari adalah

∑

yang merupakan elemen ke- dari ( ) . Dengan

menggunakan definisi perkalian matriks, elemen ke- dari

adalah

∑ ( ) ( ) ∑

di mana adalah elemen ke- pada dan adalah ele-

men ke- pada

Jadi, ( ) . ■

Teorema 2.4.3

Jika adalah matriks yang mempunyai invers, maka juga mempunyai

invers dan

( ) ( )

Bukti:

Akan dibuktikan bahwa ( ) ( ) .

Dari Teorema 2.4.2 bagian d dan fakta bahwa , didapat

( ) ( )

( ) ( )


17

E. Operasi Baris Elementer

Terdapat tiga operasi yang dapat dilakukan pada sistem persamaan

linear tanpa mengubah penyelesaiannya. Ketiga operasi tersebut adalah

menukar urutan persamaan, mengalikan suatu persamaan dengan bilangan

taknol, dan mengganti suatu persamaan dengan persamaan tersebut dit-

ambah dengan kelipatan dari persamaan lain. Ketiga operasi ini disebut

operasi baris elementer.

Definisi 2.5.1

Operasi baris elementer pada suatu matriks adalah salah satu operasi:

a. Menukar elemen-elemen baris ke- dengan elemen-elemen baris

ke- , yang dinotasikan dengan

b. Mengalikan elemen-elemen baris ke- dengan konstanta taknol

yang dinotasikan dengan

c. Mengganti suatu baris ke- dengan elemen-elemen baris ke- dit-

ambah dikalikan dengan elemen-elemen baris ke- , yang

dinotasikan dengan

Contoh 2.5.2

Diberikan matriks [

]

a. Menukarkan baris kedua dengan baris ketiga:

[

] → [

] .

b. Mengalikan baris kedua dengan

:

[

]

→ [

]

c. Mengganti baris ketiga dengan elemen pada baris ketiga ditambah

dikalikan dengan baris pertama:


18

[

] ( ) → [

].

F. Bentuk Eselon Baris

Dengan melakukan operasi baris elementer, dapat mengubah

matriks lengkap dari system persamaan linear menjadi suatu matriks dari

sistem persamaan linear yang mudah dicari jawabnya. Matriks ini disebut

dengan matriks eselon baris.

Definisi 2.6.1

Suatu matriks disebut matriks eselon baris jika mempunyai sifat-sifat

berikut.

a. Setiap baris yang hanya terdiri dari bilangan nol terletak sesudah

baris yang memuat elemen taknol.

b. Pada setiap baris yang mempunyai elemen taknol, elemen taknol

yang pertama harus terletak di kolom sebelah kanan elemen taknol

dari baris sebelumnya.

Definisi 2.6.2

Elemen taknol yang pertama dari suatu baris dalam suatu matriks eselon

baris disebut elemen utama.

Definisi 2.6.3

Suatu matriks disebut matriks eselon baris tereduksi jika mempunyai sifat-

sifat berikut.

a. Merupakan matriks eselon baris.

b. Setiap elemen utamanya adalah satu.

c. Setiap elemen utama merupakan satu-satunya elemen taknol pada

kolom tersebut.


19

G. Eliminasi Gauss dan Eliminasi Gauss-Jordan

Sebarang matriks dapat diubah menjadi matriks eselon dengan

menggunakan operasi baris elementer. Dengan demikian jika sistem

mempunyai penyelesaian, maka akan selalu dapat mencari penyelesaiann-

ya. Algoritma untuk mengubah sebarang matriks menjadi matriks eselon

dengan menggunakan operasi baris elementer disebut eliminasi Gauss.

Proses untuk mengubah suatu matriks menjadi matriks eselon tereduksi

disebut eliminasi Gauss-Jordan

Algoritma Eliminasi Gauss

a. Jika elemen pertama baris pertama sama dengan nol, tukarlah baris

pertama dari matriks dengan baris lain yang elemen pertamanya

taknol.

b. Setelah elemen pertama baris pertama tidak sama dengan nol,

dengan operasi baris elementer elemen-elemen di bawahnya dibuat

menjadi nol.

c. Kemudian elemen utama pada baris kedua harus terletak di sebelah

kanan elemen utama baris pertama, dan dengan operasi baris ele-

menter elemen-elemen di bawahnya dibuat menjadi nol.

d. Setiap elemen utama pada baris ke- terletak di sebelah kanan ele-

men utama baris sebelumnya, dan dengan operasi baris elementer

elemen-elemen di bawahnya dibuat menjadi nol, sehingga

menghasilkan matriks eselon baris.

Contoh 2.7.1

Diberikan matriks [

]

[

] ( ) → [

] ( ) → [

]

[

]

→ [

] ( ) → [

]


20

[

] → [

]

Algoritma Eliminasi Gauss-Jordan

a. Ubah matriks menjadi matriks eselon baris.

b. Bagilah elemen pada baris yang mempunyai elemen utama dengan

besarnya nilai elemen utama tersebut.

c. Dengan operasi baris elementer, elemen di atas elemen utama

dibuat menjadi nol.

Contoh 2.7.2

Diberikan matriks [

]

[

] → [

] ( ) → [

]

[

] → [

]

→ [

]

→ [

]

[

] → [

] ( ) → [

] ( ) → [

].

Teorema 2.7.3

Jika adalah matriks eselon baris tereduksi dari matriks berukuran

, maka mempunyai baris nol atau adalah matriks identitas

Bukti:

Dengan eliminasi Gauss-Jordan matriks eselon baris tereduksi dari matriks

berukuran adalah

[

]


21

Dapat terjadi bahwa baris (baris-baris) terakhir matriks seluruhnya ada-

lah nol. Jika tidak, matriks tidak mengandung baris nol, dan akibatnya

setiap baris mempunyai elemen utama 1. Karena elemen-elemen lain yang

berada di kolom yang sama dengan elemen utama 1 adalah nol, maka

Jadi mempunyai baris nol atau . ■

H. Matriks Invers

Jika adalah matriks persegi, dan ada matriks dengan ukuran

yang sama sedemikian sehingga , maka dikatakan

mempunyai invers dan disebut invers dari Jika matriks tidak

ditemukan, maka disebut matriks singular.

Teorema 2.8.1

Jika dan adalah invers dari matriks maka . Dengan kata lain

matriks invers dari suatu matriks adalah tunggal.

Bukti:

Karena dan adalah invers dari maka dan sehingga

( ) . Tetapi ( ) ( ) sehingga ■

Jadi, jika mempunyai invers, maka inversnya tunggal. Invers dari di-

notasikan dengan

Definisi 2.8.2

Jika adalah matriks persegi, maka didefinisikan pangkat bilangan bulat

taknegatif dari yaitu

dan ⏟

. ( bilangan bulat positif)


22

Jika mempunyai invers, maka didefinisikan pangkat bilangan bulat

negatif dari , yaitu

⏟

( bilangan bulat negatif)

Teorema 2.8.3

Jika matriks mempunyai invers, dan skalar , maka berlaku

a. ( )

b. ( )

c. ( )

d. ( ) ( )

Bukti:

a. Karena merupakan matriks invers dari maka

.

Dengan demikian adalah matriks invers dari yaitu

( )

b. ( )( ) ( ) ( )

( )( ) ( )

( )( ) ( ) ( )

( )( ) ( )

Jadi, adalah invers dari yaitu ( ) .

c. ( )( )= ( )

dan ( )( ) ( )

Jadi, merupakan invers dari yaitu ( )

.

d. Untuk

Langkah awal: Pernyataan tersebut benar untuk karena

( ) ( ) .

Jadi ( ) ( ) .


23

Langkah induksi: Misalkan pernyataan tersebut benar untuk

yaitu

( ) ( )

maka untuk diperoleh:

( ) ( )

( )

( )

( )

yang memperlihatkan bahwa pernyataan tersebut juga benar

untuk

Jadi, terbukti bahwa pernyataan tersebut benar untuk setiap

Untuk .

Langkah awal: Pernyataan tersebut benar untuk kare-

na

( )

Langkah induksi: Misalkan pernyataan tersebut benar untuk

yaitu

( ) ( )

Maka untuk diperoleh:

( ) ( )

( ) ( )

( ) ( )

( )

( )

yang memperlihatkan bahwa pernyataan tersebut juga benar

untuk

Jadi, terbukti bahwa pernyataan tersebut benar untuk setiap

■


24

Definisi 2.8.4

Matriks berukuran disebut matriks elementer jika matriks tersebut

dapat diperoleh dari matriks identitas dengan melakukan satu kali

operasi baris elementer.

Contoh 2.8.5

[

] ( )→ [

]

[

] → [

]

[

] → [

]

Definisi 2.8.6

Dua matriks disebut ekivalen baris jika salah satu matriks dapat diperoleh

dengan melakukan operasi baris elementer sebanyak berhingga kali pada

matriks yang lain.

Definisi 2.8.7

Matriks yang semua elemennya adalah 0 disebut matriks nol.

Teorema 2.8.8

Jika satu operasi baris elementer dilakukan pada matriks berukuran

maka hasilnya adalah matriks dengan adalah matriks ele-

menter yang diperoleh dengan melakukan satu operasi baris elementer

yang sama pada matriks identitas


25

Bukti:

Misalkan matriks [

] Dengan melakukan satu

kali operasi baris elementer didapat

[

] → [

]

[

] → [

]

[

] → [

]

Misalkan [

] Dengan melakukan satu kali operasi baris

elementer yang sama seperti pada di atas didapat

[

] → [

]

[

] → [

]

[

] → [

] .


26

Maka

[

] [

]

[

].

[

] [

]

[

]

[

] [

]

[

]. ■

Teorema 2.8.9

Setiap matriks elementer mempunyai invers, dan inversnya adalah matriks

elementer.

Bukti:

a. Misalkan matriks elementer diperoleh dengan melakukan

operasi baris elementer dengan . Matriks invers dari

matriks elementer ini adalah matriks elementer yang diperoleh


27

dengan melakukan operasi baris elementer

pada matriks iden-

titas.

b. Misalkan matriks elementer yang diperoleh dengan melakukan

operasi baris elementer Matriks invers dari matriks ele-

menter ini adalah matriks elementer yang diperoleh dengan

melakukan operasi baris elementer ( ) pada matriks

identitas.

c. Misalkan matriks elementer yang diperoleh dengan menukar ba-

ris ke- dan ke- Matriks invers dari matriks elementer tersebut

adalah matriks elementer yang diperoleh dengan melakukan

operasi baris elementer yang sama pada matriks identitas. Dengan

kata lain ■

Teorema 2.8.10

Jika adalah matriks , maka pernyataan-pernyataan berikut ekiva-

len:

a. mempunyai invers.

b. hanya mempunyai penyelesaian trivial, di mana vektor

( ) dan vektor ( ).

c. ekivalen baris dengan

Bukti:

( ) Misalkan mempunyai invers dan misalkan adalah

penyelesaian dari yaitu . Dengan mengalikan kedua ruas

dengan didapat

( )

( )

.


28

Jadi hanya mempunyai penyelesaian trivial.

( ) Misalkan yaitu sistem persamaan linear homogen:

{

hanya mempunyai penyelesaian trivial, yaitu

Maka matriks koefisien dari sistem persamaan linear homogen tersebut

adalah

[

]

sehingga dapat disimpulkan bahwa matriks ekivalen baris dengan

( ) Misalkan ekivalen baris dengan matriks identitas . Berarti

dengan mengoperasikan sejumlah kali operasi baris elementer pada akan

diperoleh matriks . Menurut Teorema 2.8.8, hal tersebut berarti

dengan adalah matriks elementer.

Menurut Teorema 2.8.9, matriks-matriks elementer tersebut mempunyai

invers, yaitu

. Maka

(

)( )

sehingga , yaitu matriks A mempunyai invers. ■

Dengan demikian, matriks dapat diperoleh dengan mengerjakan

operasi-operasi baris elementer pada dengan operasi-operasi baris ele-

menter yang digunakan untuk mengubah menjadi .


29

Contoh 2.8.11

Diberikan matriks [

]

(

|

+ → (

|

+

(

|

+ ( ) → (

|

+

(

|

+

→ (

|

⁄

⁄

⁄)

(

|

⁄

⁄

⁄) ( ) → (

|

⁄

⁄

⁄

⁄

⁄

⁄

,

(

|

⁄

⁄

⁄

⁄

⁄

⁄

, →

(

||

⁄

⁄

⁄

⁄

⁄

⁄

⁄

⁄

⁄ )

Jadi,

[

⁄ ⁄

⁄

⁄

⁄

⁄

⁄

⁄

⁄ ]

I. Determinan Matriks

Fungsi yang mengaitkan setiap matriks persegi dengan sebuah

bilangan yang memenuhi sifat tertentu disebut determinan matriks. De-

terminan memiliki beberapa sifat, yang lebih lanjut akan dibahas sebagai

berikut.


30

Definisi 2.9.1

Determinan dari matriks 0

1 berukuran adalah

( ) |

| .

Teorema 2.9.2

Matriks 0

1 mempunyai invers, yaitu

0

1 ji-

ka dan hanya jika .

Bukti:

( ) Diketahui matriks 0

1 mempunyai invers, yaitu

0

1. Akan ditunjukkan

Karena invers dari matriks adalah

0

1, maka harus-

lah , karena jika maka

0

1

tidak terdefinisi.

( ) Karena maka

terdefinisi, sehingga

.

|

/ ( ) → .

|

/

.

|

/

→ (

|

)

(

|

) ( ) → (

|

+

(

|

+

→ (

|

+.

Jadi [

]


31

0

1. ■

Teorema 2.9.3 (untuk matriks berukuran )

a. Jika matriks diperoleh dari matriks dengan mengalikan suatu

baris dari matriks dengan konstanta maka ( ) ( )

Bukti:

Misalkan 0

1 dan 0

1 maka

( ) 0

1 ( )

0

1 ( ).

b. Jika matriks diperoleh dari matriks dengan menukar dua baris

maka

( ) ( )

Bukti:

Misalkan 0

1 dan 0

1, maka

( ) ( ) ( )

c. Jika dua baris dari matriks sama, maka ( ) .

Bukti:

Misalkan matriks mempunyai dua baris yang sama. Dengan me-

nukar kedua baris itu diperoleh matriks juga. Tetapi karena pe-

nukaran baris itu diperoleh ( ) ( ), sehingga

( ) Jadi ( )

d. Jika dan adalah tiga matriks yang baris pertama (atau ba-

ris keduanya) sama tetapi elemen baris kedua (atau baris pertaman-

ya) dari matriks merupakan jumlah elemen seletak dari matriks

, maka

( ) ( ) ( ).


32

Bukti:

Misalkan [

] [

] dan

[

], maka

( ) [

] ( ) ( )

( ) ( ) [

] [

]

( ) ( ).

e. Jika matriks diperoleh dari matriks dengan menambah suatu

baris dengan kali baris yang lain, maka ( ) ( )

Bukti:

Misalkan 0

1 dan 0

1 maka

( ) ( ) ( )

( ) .

f. Determinan matriks identitas adalah 1.

Bukti:

( ) 0

1 .

g. ( ) ( )

Bukti:

Misalkan 0

1 dan 0

1, maka

( ) ( ). ■

Definisi 2.9.4

Determinan matriks berukuran adalah fungsi yang mengaitkan

matriks itu ke bilangan real ( ) dengan sifat:


33

a. Jika matriks diperoleh dari matriks dengan cara mengalikan

sebuah baris dengan bilangan maka ( ) ( ).

b. Jika matriks diperoleh dari matriks dengan cara menukar dua

baris, maka ( ) ( ).

c. Jika diketahui tiga matriks dan yang mempunyai elemen

sama kecuali pada baris ke- , yaitu elemen baris ke- dari matriks

merupakan jumlah dari elemen baris ke- dari matriks dan

maka ( ) ( ) ( ).

d. Determinan matriks identitas adalah 1.

e. ( ) ( )

Teorema 2.9.5

Jika matriks mempunyai dua baris yang elemennya sama, maka

( ) .

Bukti:

Misalkan matriks mempunyai dua baris yang elemennya sama dan

matriks yang diperoleh dari matriks dengan cara menukar dua baris yang

elemennya sama tersebut. Dengan demikian . Oleh karena itu

( ) ( ). Tetapi berdasarkan sifat b, ( ) ( ), sehing-

ga ( ) ( ). Akibatnya ( ) sehingga ( ) ■

Teorema 2.9.6

Jika matriks diperoleh dari matriks dengan cara mengganti sebuah

barisnya dengan baris itu ditambah kali baris lain dari , maka ( )

( )

Bukti:

[

]


34

[

]

Kemudian dengan sifat c (Definisi 2.9.4) diperoleh

( ) [

] [

]

Dengan sifat a (Definisi 2.9.4), determinan yang kedua dapat diganti men-

jadi

( )

[

] [

]

Karena determinan kedua adalah determinan matriks yang mempunyai dua

baris yang sama yaitu baris pertama dan baris ke- , maka nilainya sama

dengan nol (Teorema 2.9.5). Oleh karena itu, ( ) ( )

Definisi 2.9.7

Elemen-elemen baris ke- dan kolom ke- dalam suatu matriks persegi

disebut elemen diagonal. Matriks persegi yang semua elemennya di bawah

elemen diagonalnya adalah nol disebut matriks segitiga atas, sedangkan

matriks persegi yang semua elemennya di atas elemen diagonalnya adalah

nol disebut matriks segitiga bawah.

Contoh 2.9.8

Berikut contoh matriks segitiga atas

[

]

dan matriks segitiga bawah

[

]


35

Contoh 2.9.9

Menghitung determinan matriks segitiga atas

[

]

Dengan sifat a (Definisi 2.9.4)

( ) [

] *

+

kemudian dengan Teorema 2.9.6, yaitu mengganti baris kedua dengan ba-

ris kedua ditambah kali baris ketiga diperoleh

( ) *

+.

Dengan sifat a (Definisi 2.9.4) diperoleh

( ) *

+

kemudian dengan Teorema 2.9.6, yaitu mengganti baris pertama dengan

baris pertama ditambah kali baris kedua diperoleh

( ) [

]

dengan Teorema 2.9.6, yaitu mengganti baris pertama dengan baris per-

tama ditambah kali baris ketiga diperoleh

( ) [

]

Dengan sifat a dan sifat d (Definisi 2.9.4) diperoleh

( ) [

] .

Jadi, determinan matriks segitiga atas adalah hasil kali dari elemen-elemen

diagonalnya.

Contoh 2.9.10

Menghitung determinan matriks segitiga bawah


36

[

].


( ) [

] [

]

Kemudian dengan Teorema 2.9.6, yaitu mengganti baris kedua dengan ba-

ris kedua ditambah kali baris pertama diperoleh

( ) [

]


( ) [

]

Kemudian dengan Teorema 2.9.6, yaitu mengganti baris ketiga dengan ba-

ris ketiga ditambah kali baris pertama diperoleh

( ) [

]

Kemudian dengan Teorema 2.9.6, yaitu mengganti baris ketiga dengan

baris ketiga ditambah kali baris kedua diperoleh

( ) [

]

Dengan sifat a dan sifat d (Definisi 2.9.4) diperoleh

( ) [

]

Jadi, determinan matriks segitiga bawah adalah hasil kali dari elemen-

elemen diagonalnya.

Definisi 2.9.11

Misalkan matriks berukuran . Minor adalah determinan dari

matriks berukuran ( ) ( ) yang diperoleh dari matriks


37

dengan menghapus baris ke- dan kolom ke- . Sedangkan kofaktor

( )

Contoh 2.9.12

Menghitung determinan matriks

[

].

Dengan sifat c (Definisi 2.9.4),

( ) [

]

[

] [

] [

]

( ) ( ) ( )


( ) [

] [

]

Kemudian dengan Teorema 2.9.6,

( ) [

] [

].

Dengan Teorema 2.9.6, yaitu mengganti baris ketiga dengan baris ketiga

ditambah dengan

kali baris kedua dengan asumsi diperoleh

( ) *

+

( .

/) ( )

0

1


38

Jika , maka ( ) [

], dengan sifat b

(Definisi 2.9.4) yaitu menukar baris kedua dan ketiga diperoleh

( ) [

] ( )

[

]

Dengan sifat e (Definisi 2.9.4) diperoleh

( ) [

] [

]

Dengan sifat b (Definisi 2.9.4), yaitu menukar baris pertama dengan baris

kedua diperoleh

( ) [

] [

]

dengan sifat e (Definisi 2.9.4) diperoleh

( ) [

] [

]


( ) [

] [

]

Kemudian dengan Teorema 2.9.6, determinan ini dapat diubah menjadi

( ) [

]


ditambah



39

( ) [

]

( (

*) ( )

0

1

Jika , maka ( ) [

], dengan sifat b

(Definisi 2.9.4), yaitu menukar baris kedua dan ketiga diperoleh

( ) [

] ( )

0

1


( ) [

] [

]

Dengan sifat b (Definisi 2.9.4), yaitu menukar baris ketiga dan pertama di-

peroleh

( ) [

] [

]


( ) [

] [

]


( ) [

] [

]

Kemudian dengan Teorema 2.9.6, determinan ini dapat diubah menjadi

( ) [

] [

]


40


ditambah


( ) *

+

( ) 0

1 0

1.

Jika , maka ( ) [

], dengan sifat b

(Definisi 2.9.4), yaitu menukar baris kedua dan ketiga diperoleh

( ) [

] ( )

[

].

Dengan sifat a (Definisi 2.9.4) dan Teorema 2.9.6, yaitu mengganti baris

kedua dengan baris kedua ditambah dengan kali baris ketiga di-

peroleh diperoleh ( ) [

]

Dengan demikian

( ) 0

1 0

1 0

1

( ) ( )

( )

Bentuk terakhir ini disebut perluasan kofaktor determinan sepanjang baris

pertama. Dengan cara yang sama determinan di atas dapat ditulis sebagai

perluasan kofaktor sepanjang baris atau kolom yang lain serta akan mem-

berikan nilai yang sama. Perluasan kofaktor determinan matriks ter-

sebut dapat diperluas untuk perluasan kofaktor determinan matriks


41

Teorema 2.9.13

Jika matriks berukuran , maka

a. Perluasan kofaktor determinan sepanjang baris ke- adalah

( )

b. Perluasan kofaktor determinan sepanjang kolom ke- adalah

( ) .

Contoh 2.9.14

Diberikan matriks [

].

Dengan menggunakan perluasan kofaktor sepanjang baris pertama di-

peroleh

( ) ( ) |

| ( ) |

|

( ) ( )

.

Teorema 2.9.15

Misalkan matriks elementer .

a. Jika hasil dari mengalikan baris pada dengan bilangan taknol

maka ( )

b. Jika hasil dari menukar dua baris pada maka ( ) .

c. Jika hasil dari mengganti sebuah baris dengan baris itu ditambah

kali baris lain pada , maka ( )

Bukti:

a. Berdasarkan Definisi 2.9.4 bagian a, maka ( ) ( ) dan

berdasarkan Definisi 2.9.4 bagian d, yaitu ( ) maka

( ) ( )


42

b. Berdasarkan Definisi 2.9.4 bagian b, maka ( ) ( ) dan

berdasarkan Definisi 2.9.4 bagian d, yaitu ( ) maka

( ) ( )

c. Karena matriks elementer yang diperoleh dari matriks identitas

dengan mengganti suatu baris dengan baris itu ditambah kali baris

lain, maka berdasarkan Teorema 2.9.6, ( ) ( ) dan ber-

dasarkan Definisi 2.9.4 bagian d, yaitu ( ) maka ( )

. ■

Teorema 2.9.16

Jika elemen-elemen dalam baris (atau kolom) matriks persegi berukuran

dikalikan dengan kofaktor dari elemen-elemen yang sesuai dalam

baris (atau kolom) yang berbeda, maka jumlahan dari perkalian tersebut

adalah nol.

Bukti:

Misalkan adalah matriks yang diperoleh dari dengan menambahkan

baris ke- ke baris ke- pada matriks , maka ( ) ( ). Perlua-

san kofaktor sepanjang baris ke- dari matriks adalah

( ) ( ) ∑( )

∑ ∑

( ) ∑ .

Dari Teorema 2.9.13, penjumlahan pertama pada ruas sebelah kanan ada-

lah ( ), sehingga ∑ untuk ■


43

J. Matriks Adjoin

Matriks adjoin merupakan transpos dari matriks kofaktor. Adjoin dari

matriks dinotasikan dengan adj ( )

Definisi 2.10.1.

Misalkan matriks dan adalah kofaktor dari , maka matriks

[

]

disebut matriks kofaktor dari .

Transpos matriks kofaktor dari disebut adjoin dan dinotasikan dengan

adj ( ),

adj ( ) [

].

Contoh 2.10.2

Tentukan adjoin dari matriks [

].

Penyelesaian:

Kofaktor dari adalah

( ) |

|

( ) |

|

( )( )

( ) |

|

( ) |

|

( )( )

( ) |

|

( ) |

|

( )( ( ))


44

( ) |

|

( ) |

|

( )( ( ))

( ) |

|

Jadi, adj ( ) [

]

[

].


45

BAB III

APLIKASI ALJABAR LINEAR PADA KRIPTOGRAFI

A. Aritmetika Modular

Aritmetika modular adalah sistem aritmetika untuk bilangan bulat, yang

dapat didefinisikan secara matematis dengan menggunakan relasi kongru-

ensi pada bilangan bulat. Jika n adalah suatu bilangan bulat positif, maka

bilangan bulat dan dikatakan kongruen modulo jika adalah

bilangan bulat kelipatan Aritmetika modular digunakan dalam kripto-

grafi dan akan dibahas pada subbab berikut ini.

Definisi 3.1.1

Jika dan adalah bilangan bulat dan maka dikatakan habis

dibagi oleh (dilambangkan dengan ) jika dan hanya jika terdapat

bilangan bulat sedemikian sehingga Jika habis dibagi oleh

maka juga dikatakan bahwa adalah faktor atau pembagi dari , atau

adalah kelipatan

Prinsip Terurut Baik (Well Ordering Principle)

Jika adalah himpunan bagian takkosong dari himpunan semua bilangan

asli, maka mempunyai elemen terkecil, yaitu ( )( )

Contoh 3.1.2

Jika diberikan * +, maka elemen terkecil dari adalah , sebab

dan

Teorema 3.1.3 (Algoritma Pembagian)

Untuk setiap bilangan bulat dan bilangan bulat positif , terdapat dengan

tunggal bilangan bulat dan sedemikian sehingga

dan


46

Bukti:

Misalkan adalah himpunan semua bilangan bulat taknegatif dengan ben-

tuk

di mana adalah bilangan bulat. Himpunan ini takkosong karena

a. Jika taknegatif, maka sehingga (

) .

b. Jika negatif, maka ( ) se-

hingga

( ) . .

Berdasarkan prinsip terurut baik, mempunyai elemen terkecil yaitu

ada bilangan bulat sedemikian sehingga

.

Kemudian dengan menambahkan pada kedua ruas persamaan tersebut

diperoleh

.

Andaikan , maka

( )

.

Bilangan bulat ( ) dan ( ) . Tetapi adalah

bilangan bulat terkecil di sehingga pengandaian tidak benar. Ter-

bukti bahwa ada bilangan bulat dan sedemikian sehingga

dan

Untuk membuktikan ketunggalan dan dimisalkan terdapat bilangan

bulat dan sedemikian sehingga

(1)

(2)

Karena salah satunya akan lebih besar atau sama dengan yang

lainnya, misalkan . Dari (1) diperoleh dan dari (2) di-

peroleh . Kemudian


47

( )

( )

Di sisi lain dan kurang dari dan sudah dimisalkan maka

. Dengan demikian,

( )

( ) .

Tetapi ( ) merupakan bilangan bulat. Jadi ketidaksamaan ini berlaku

hanya jika Dengan kata lain, sehingga mengakibatkan

■

Definisi 3.1.4

Jika adalah bilangan bulat positif serta dan adalah sebarang bilangan

bulat, maka dikatakan kongruen modulo , ditulis

( )

jika dan hanya jika adalah bilangan bulat kelipatan

Contoh 3.1.5

a. ( ), karena yang merupakan kelipatan dari

4.

b. ( ) karena yang merupakan kelipatan dari

5.

Definisi 3.1.6

Jika dan adalah bilangan bulat dengan , maka ( ) adalah

sisa taknegatif kurang dari n yang diperoleh jika dibagi oleh Him-

punan bilangan bulat * + disebut himpunan bilangan

bulat modulo


48

Contoh 3.1.7

a. ( ) 11.

b. ( ) 16.

Definisi 3.1.8

Misalkan dan bilangan bulat taknol. Pembagi persekutuan terbesar

dari dan , yang dinotasikan dengan ( ) adalah bilangan bulat

dengan sifat berikut:

a. adalah pembagi persekutuan dari dan , yaitu dan

b. Untuk semua bilangan bulat , jika adalah pembagi perseku-

tuan dari dan maka Dengan kata lain, untuk semua

bilangan bulat , jika dan , maka .

Teorema 3.1.9

Untuk setiap bilangan bulat positif dan jika adalah pembagi dari ,

maka

Bukti:

Misalkan dan bilangan bulat positif dan adalah pembagi dari

Maka terdapat bilangan bulat jadi Bilangan bulat haruslah

positif karena dan positif, sehingga karena setiap bilangan bulat

positif lebih besar atau sama dengan satu. Dengan mengalikan kedua sisi

pertidaksamaan tersebut dengan diperoleh

Jadi ■

Definisi 3.1.10

Bilangan bulat dan dikatakan relatif prima jika dan hanya jika

( ) Bilangan-bilangan bulat adalah pasangan


49

relatif prima jika dan hanya jika ( ) untuk setiap dan

dengan

Definisi 3.1.11

Bilangan bulat dikatakan merupakan kombinasi linear dari bilangan bu-

lat dan jika dan hanya jika terdapat bilangan bulat dan sedemikian

sehingga

Teorema 3.1.12

Untuk semua bilangan bulat taknol dan jika ( ) maka

merupakan kombinasi linear dari dan

Bukti:

Diberikan bilangan bulat taknol dan dan misalkan ( ) dan

* +.

adalah himpunan takkosong karena

a. Jika maka ( ) .

b. Jika maka ( ( ) )

Berdasarkan prinsip terurut baik, terdapat elemen terkecil . Dari defin-

isi ,

untuk bilangan bulat dan

Akan ditunjukkan bahwa

1)

Karena ( ), maka menurut Definisi 3.1.8, dan

yaitu dan untuk bilangan bulat dan se-

hingga

( ) ( )

( ).


50

Tetapi adalah bilangan bulat karena merupakan jumlahan

dan perkalian bilangan-bilangan bulat (Teorema 3.1.9).

2)

Gunakan Algoritma pembagian untuk memperoleh di

mana dan bilangan bulat dengan sehingga

.

Karena maka

( )

( ) ( )

Jadi adalah kombinasi linear dari dan . Jika maka

dan . Pernyataan tersebut kontradiksi dengan pern-

yataan bahwa adalah elemen terkecil di . Jadi sehingga

dan oleh karena itu

Kemudian di mana dan bilangan bulat dengan

sehingga

Karena maka

( )

( ) ( )

Jadi adalah kombinasi linear dari dan . Jika maka

dan . Pernyataan tersebut kontradiksi dengan pern-

yataan adalah elemen terkecil di . Jadi sehingga

dan oleh karena itu

Karena dan berarti adalah pembagi persekutuan dari

dan . Karenanya karena ( ).

Dari 1) dan 2) dapat disimpulkan sehingga

untuk bilangan bulat dan , yaitu merupakan kombinasi linear

dari dan ■


51

Akibat 3.1.13

Jika dan adalah bilangan bulat relatif prima, maka ada bilangan bulat

dan sedemikian sehingga

Bukti:

Karena ( ) maka berdasarkan Teorema 3.1.12, ada bilangan

bulat dan sedemikian sehingga ■

Definisi 3.1.14

Invers (mod n) dari bilangan bulat a adalah bilangan bulat sedemikian

sehingga ( )

Teorema 3.1.15

Untuk semua bilangan bulat dan jika ( ) dan maka

Bukti:

Diketahui dan adalah bilangan bulat, ( ) dan

Akan dibuktikan bahwa

Berdasarkan Teorema 3.1.12, terdapat bilangan bulat dan sedemikian

sehingga

Kemudian dengan mengalikan kedua ruas persamaan tersebut dengan

diperoleh

Karena , berdasarkan definisi pembagian terdapat bilangan bulat

sedemikian sehingga

sehingga didapat

( )

( )


52

Misalkan maka adalah bilangan bulat (karena dan

adalah bilangan-bilangan bulat), dan , yang berarti ■

Contoh 3.1.16

Karena 9 dan 26 relatif prima, maka 9 mempunyai invers (mod 26). Invers

(mod 26) dari 9 adalah 3 karena ( )

Definisi 3.1.17

Misalkan ( ) dan ( ) adalah matriks berukuran

dengan elemen-elemen bilangan-bilangan bulat dan adalah bilangan bu-

lat positif. Matriks dikatakan kongruen dengan matriks modulo , di-

notasikan

(mod )

jika dan hanya jika (mod ) untuk setiap pasangan ( ) dengan

dan

Contoh 3.1.18

Jika matriks 0

1 dan 0

1 maka (mod ),

sebab (mod ), (mod ) (mod ),

(mod ).

Definisi 3.1.19

Jika dan adalah matriks-matriks berukuran dengan elemen-

elemen bilangan bulat dan adalah bilangan bulat positif, maka ada-

lah invers dari (mod ) jika (mod )

Contoh 3.1.20

Jika matriks 0

1 maka 0

1 adalah invers dari A (mod

) sebab 0

1 0

1 0

1 0

1 ( )


53

0

1 0

1 0

1 0

1 ( )

Teorema 3.1.21

Jika adalah bilangan bulat positif dan adalah bilangan bulat modulo ,

maka mempunyai invers ( ) jika dan hanya dan relatif prima.

Bukti:

(⇐) Diketahui dan relatif prima, maka berdasarkan Akibat 3.1.13 ter-

dapat bilangan bulat dan sedemikian sehingga sehingga

( ) .

Dari Definisi 3.1.4 didapat ( ). Berdasarkan definisi 3.1.14,

adalah invers ( ) dari Jadi mempunyai invers ( ).

( ) Diketahui mempunyai invers ( ). Misalkan adalah invers

( ) dari sehingga ( ), dan misalkan ( ).

Akan dibuktikan bahwa dan misalkan adalah

bilangan prima pembagi Karena d adalah pembagi a dan n, maka ju-

ga pembagi dari dan Karena ( ) maka berdasarkan

Definisi 3.1.4 sehingga untuk suatu bilangan

bulat Karena dan maka ( ), sehingga Ini kontra-

diksi dengan adalah bilangan prima, yaitu . Jadi yaitu

( ) sehingga berdasarkan Definisi 3.1.10, dan relatif prima.

■

Teorema 3.1.22

Jika adalah matriks persegi dengan elemen-elemen bilangan bulat dan

adalah bilangan bulat positif sedemikian sehingga ( ) ( ) dan

relatif prima, maka A mempunyai invers ( ) yaitu

( ( )) ( ) ( ).


54

Bukti:

Karena ( )( ) dan relatif prima, maka berdasarkan Teorema

3.1.21, ( )( ) mempunyai invers (mod n),

ga ( )( ) Selanjutnya, elemen baris ke- dan kolom ke-

dari ( ) adalah

(1)

Jika , maka jumlahan (1) adalah perluasan kofaktor dari matriks

sepanjang baris ke- sehingga jumlahan (1) sama dengan det( ) (Teorema

2.9.13).

Jika , maka jumlahan (1) sama dengan nol (Teorema 2.9.16). Jadi

adj ( ) [

( ) ( ) ( )

] ( )

Demikian pula, elemen baris ke- dan kolom ke- dari adj ( ) adalah

(2)

Jika , maka jumlahan (2) adalah perluasan kofaktor dari matriks

sepanjang baris ke- sehingga jumlahan (2) sama dengan det( ) (Teorema

2.9.13).

Jika , maka jumlahan (2) sama dengan nol (Teorema 2.9.16). Jadi

adj ( ) [

( ) ( ) ( )

] ( )

maka adj ( ) adj ( ) ( ) .

Berdasarkan Teorema 3.1.21 karena ( ) ( ) dan relatif prima,

maka ( ) ( ) mempunyai invers (mod ), yaitu

( ( )) ( )

Dengan demikian

,( ( )) ( )- ( ( )) ( ) ( ( )) ( )

(mod )


55

dan

,( ( )) ( )- ( ( )) ( ) ( ( )) ( )

(mod ).

Ini menunjukkan bahwa ( ( )) ( ) ( ) adalah invers

( ) dari

Teorema 3.1.23

Matriks persegi dengan elemen-elemen di mempunyai invers (mod

) jika dan hanya jika ( )( ) mempunyai invers di .

Bukti:

( ) Diketahui matriks persegi dengan elemen-elemen di mempu-

nyai invers (mod n), yaitu . Maka (mod n), sehingga

( ) ( ) (mod n). Jadi

, ( )( )-,( ( )) ( )- .

Berarti ( )( ) mempunyai invers di .

( ) Diketahui ( )( ) mempunyai invers di . Berdasarkan

Teorema 3.1.21, ( )( ) dan relatif prima, dan berdasarkan Te-

orema 3.1.22, karena ( )( ) dan relatif prima, maka matriks

mempunyai invers (mod n). ■


56

B. Kriptografi

Kriptografi berasal dari bahasa Yunani, crypto dan graphia. Crypto be-

rarti rahasia dan graphia berarti tulisan. Menurut terminologinya, kripto-

grafi adalah ilmu dan seni untuk menjaga keamanan pesan ketika pesan

dikirim dari suatu tempat ke tempat lain.

Di masa lalu, kriptografi digunakan oleh pemerintahan dan militer.

Banyak sistem untuk mengirim pesan rahasia membutuhkan pengirim dan

penerima untuk mengetahui prosedur enkripsi dan dekripsi.

Dalam mengirim pesan, pengirim terlebih dahulu harus mengubah pe-

san tersebut agar tidak diketahui oleh orang lain, sehingga pesan tersebut

dapat aman hingga sampai ke penerima. Proses mengubah teks-biasa men-

jadi teks-sandi disebut enkripsi. Kemudian penerima yang telah menerima

pesan rahasia tersebut harus dapat membuka pesan tersebut agar menjadi

pesan yang dapat dimengerti. Proses dalam mengubah teks-sandi menjadi

teks-biasa disebut dekripsi.

C. Sandi Hill

Sandi Hill merupakan salah satu algoritma kriptografi yang diciptakan

pada tahun 1929 oleh Lester S. Hill. Algoritma Sandi Hill menggunakan

matriks persegi sebagai kunci untuk mengubah teks-biasa, yaitu teks yang

belum dikodekan menjadi teks-sandi dan sebaliknya. Persamaan sandi Hill

adalah

( )

di mana adalah pesan yang sudah disandikan (teks-sandi), adalah

kunci berbentuk matriks persegi dengan elemen-elemen bilangan bulat

dan mempunyai invers (mod n), adalah pesan yang belum

disandikan (teks biasa), dan adalah bilangan bulat positif yang menya-

takan banyaknya huruf atau lambang yang digunakan.


59

d. Masing-masing kelompok nilai numerik teks-biasa tersebut disusun

menjadi vektor-vektor kolom

[ ] [

] [

] [

] [

]

[ ] [

] [

] [

].

e. Lakukan perkalian (mod ), yang menghasilkan vektor-vektor

kolom yang memuat nilai-nilai numerik teks-sandi.

(mod ) =

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

[

] [ ] ( ) [

]

f. Konversikan masing-masing nilai numerik teks-sandi tersebut ke hu-

ruf/lambang sesuai dengan tabel yang telah ditentukan.

4 11 20 20 23 17 21 24 28

28 29 29 23 11 11 4 13 25

21 7 16 25 1 22 14 6 11

D,U K?G T?P TWY WKA QKV UDN XMF ,YK

Maka didapat teks-sandi sebagai berikut:


60

D,UK?GT?PTWYWKAQKVUDNXMF,YK

D. Penguraian Sandi

Dalam proses penguraian sandi, penerima yang menerima teks-sandi

harus mengubah teks-sandi itu menjadi teks-biasa.

Pada algoritma Sandi Hill, penguraian sandi dilakukan dengan

menggunakan matriks invers ( ) sebagai kunci penguraian. Jika

adalah sebuah bilangan bulat > 1, maka matriks persegi dengan elemen-

elemen di dikatakan mempunyai invers ( ) jika terdapat matriks

dengan elemen-elemen di sedemikian sehingga

( )

Persamaan yang digunakan dalam penguraian sandi dalam algoritma

Sandi Hill adalah

( )

di mana adalah pesan yang belum disandikan (teks-biasa), adalah

matriks invers (mod n) dari matriks A sebagai matriks kunci untuk men-

guraikan sandi, dan adalah pesan yang sudah disandikan (teks-sandi).

Teorema 3.4.1

Misalkan vektor-vektor kolom nilai numerik teks-biasa dan

vektor-vektor kolom nilai numerik teks-sandi dalam sandi

Hill. Jika adalah matriks persegi dengan vektor-vektor kolom

dan adalah matriks persegi dengan vektor-vektor kolom

maka barisan operasi baris elementer yang mereduksi

menjadi mereduksi menjadi ( )

Bukti:

Misalkan , adalah matriks-matriks elementer dari operasi ba-

ris elementer untuk mereduksi menjadi , yaitu

.


61

Karena untuk setiap , maka

sehingga

.

Kemudian dengan mengalikan kedua ruas persamaan tersebut dengan

diperoleh

( )

Hal ini menunjukkan bahwa mempunyai invers, yaitu ( ) . Menurut

Teorema 2.4.3, ( ) ( ) sehingga

( )

Artinya operasi baris elementer yang bersesuaian dengan

mereduksi menjadi ( ) ■

Contoh 3.4.2

Teks-sandi: AHQ.KHEYKQ

Diketahui teks-biasa diawali dengan kata HOWA.

a. Kelompokkan huruf/lambang dari teks-sandi dan teks-biasa, masing-

masing kelompok terdiri dari 2 huruf/lambang, karena jumlah hu-

ruf/lambang dalam teks-sandi dan teks-biasa adalah genap.

Pengelompokan huruf/lambang dari teks-sandi:

AH Q. KH EY KQ

Pengelompokan huruf/lambang dari teks-biasa:

HO WA

b. Konversikan huruf/lambang dalam tiap kelompok tersebut ke nilai

numeriknya sesuai dengan tabel yang telah ditentukan.

Nilai numerik teks-sandi:

AH Q. KH EY KQ

1 17 11 5 11


62

8 27 8 25 17

Nilai numerik teks-biasa:

HO WA

8 23

15 1

c. Masing-masing kelompok nilai numerik teks-sandi dan teks-biasa

tersebut disusun menjadi vektor-vektor kolom.

Vektor-vektor kolom teks-sandi:

0 1, 0

1, 0

1, 0

1, 0

1

Vektor-vektor kolom teks-biasa:

0 1, 0

1

Dengan menggunakan Teorema 3.4.1, operasi baris elementer yang

mereduksi menjadi akan mereduksi menjadi ( )

*

+ 0

1

*

+ 0

1

( ) .

|

/ Bentuk matriks ( )

.

|

/ Kalikan baris kedua dengan

( )

.

|

/ Ganti baris kedua dengan 30

.

|

/ ( )

.

|

/ Kalikan baris kedua dengan

( )

.

|

/ Ganti baris kedua dengan 30


63

( ) 0

1

sehingga

0

1.

d. Lakukan perkalian ( ) untuk menghasilkan vektor-

vektor kolom [

] yang memuat nilai-nilai numerik teks-

biasa.

( )

0

1 0 1 ( ) 0

1

0

1 0 1 ( ) 0

1

0

1 0 1 ( ) 0

1

0

1 0 1 ( ) 0

1

0

1 0 1 ( ) 0

1

e. Konversikan masing-masing nilai numerik teks-biasa tersebut ke hu-


8 23 18 25 21

15 1 5 15 29

HO WA RE YO U?

.

|

/ ( )

.

|

/

= ( ( ) ).

Maka diperoleh:

Ganti baris pertama dengan mod 30


64

Jadi huruf/lambang hasil penguraian teks-sandi menjadi teks-biasa

adalah HOWAREYOU?

Contoh 3.4.3

Diberikan teks-sandi: D,UK?GT?PTWYWKAQKVUDNXMF,YK

dan matriks kunci: [

]

Untuk mengubah teks-sandi menjadi teks-biasa dilakukan langkah-langkah

berikut:

a. Kelompokkan huruf-huruf dan lambang-lambang teks-sandi tersebut

secara terurut, tiap kelompok terdiri dari 3 huruf/lambang sesuai

dengan ukuran matriks kunci yang dipilih.


b. Konversikan huruf/lambang dalam tiap kelompok tersebut ke nilai

numerik sesuai dengan tabel yang telah ditentukan.


4 11 20 20 23 17 21 24 28

28 29 29 23 11 11 4 13 25

21 7 16 25 1 22 14 6 11

c. Masing-masing kelompok nilai numerik teks-sandi tersebut disusun

menjadivektor-vektor kolom.

[ ] [

] [

] [

] [

]

[ ] [

] [

] [

].

d. Mencari matriks invers (mod ) dari matriks A sebagai matriks kunci

untuk menguraikan sandi dengan menggunakan Teorema 3.1.22, yaitu

( ( )) adj ( )( ).


65

Terlebih dahulu akan ditunjukkan bahwa ( )( ) dan ada-

lah relatif prima.

Menghitung ( ) ( ) dengan

[

]

dengan menggunakan perluasan kofaktor sepanjang baris pertama:

( ) ( ) ( )( ) 0

1 ( )( ) 0

1

( )( ) 0

1 ( )

( ) ( )( ) ( ) ( )

( )

( )

Karena ( ) maka berdasakan Definisi 3.1.10,

( ) ( ) adalah relatif prima.

Menghitung ( )( )

Kofaktor dari adalah

( )( ) [

]

[

]

( ( )) adj ( )( )

[

] ( ) [

]


66

e. Lakukan perkalian ( ), yang menghasilkan vektor-vektor

kolom

[

] yang memuat nilai-nilai numerik teks-biasa.

( )

[

] [ ] ( ) [

] [

] [ ] ( ) [

]

[

] [ ] ( ) [

] [

] [ ] ( ) [

]

[

] [ ] ( ) [

] [

] [ ] ( ) [

]

[

] [ ] ( ) [

] [

] [ ] ( ) [

]

[

] [ ] ( ) [

]

f. Konversikan masing-masing nilai numerik teks-biasa tersebut ke hu-


1 25 7 4 7 4 5 1 14

16 1 19 1 1 1 18 11 29

1 14 5 14 14 11 10 1 16

APA YAN GSE DAN GAN DAK ERJ AKA N?P

Maka didapat teks-biasa, yaitu: APAYANGSEDANGANDAKERJAKAN?


68

BAB IV

PENUTUP

A. Kesimpulan

Kriptografi merupakan ilmu dan seni dalam sistem penyandian, dari

mengubah teks-biasa menjadi teks-sandi ataupun sebaliknya. Ada banyak

algoritma yang dapat dipakai dalam kriptografi. Namun, pada makalah ini

penulis hanya membahas mengenai algoritma Sandi Hill, yang dikem-

bangkan oleh Lester S. Hill dengan menggunakan teori-teori dalam aljabar

linear, yaitu sistem persamaan linear, matriks, operasi matriks, matriks

transpos, operasi baris elementer, eliminasi Gauss, eliminasi Gauss-Jordan,

matriks invers, determinan matriks, matriks adjoin, dan aritmetika modu-

lar. Persamaan yang digunakan untuk mengubah teks-biasa menjadi teks-

sandi adalah sebagai berikut:

( )

di mana adalah pesan yang sudah disandikan, adalah kunci berbentuk

matriks persegi dengan elemen-elemen bilangan bulat dan

mempunyai invers (mod n), adalah pesan yang belum disandikan, dan

adalah bilangan bulat positif yang menyatakan banyaknya huruf atau lam-

bang yang digunakan.

Persamaan yang digunakan untuk mengubah teks-sandi menjadi teks-

biasa adalah sebagai berikut:

( )

di mana adalah pesan yang belum disandikan, adalah matriks invers

(mod n) dari matriks A sebagai matriks kunci untuk menguraikan sandi,

dan adalah pesan yang sudah disandikan.

Teks-biasa dalam kriptografi dapat berupa kalimat yang dilengkapi

dengan tanda baca, seperti titik, koma, tanda seru, tanda tanya, spasi dan

lain sebagainya. Untuk mengubah teks-biasa menjadi teks-sandi digunakan

kunci berupa matriks persegi yang mempunyai invers. Ukuran matriks


69

yang digunakan ditentukan oleh pengirim. Kunci hanya diketahui oleh

pengirim dan penerima untuk menjaga keamanan pesan rahasia tersebut.


70

B. Saran

Pada makalah ini, penulis hanya membahas aplikasi aljabar linear

pada kriptografi dalam algoritma Sandi Hill. Proses enkripsi dan dekripsi

pada kriptografi dapat diperluas dengan berbagai algoritma lain, seperti al-

goritma RSA dan Elgamal, yang merupakan algoritma asimetri, dengan

kunci yang digunakan untuk mengenkripsi dan mendekripsi berbeda. Al-

goritma RSA menggunakan konsep bilangan prima dan aritmetika modu-

lar, sedangkan algoritma Elgamal menggunakan konsep logaritma diskret.


71

DAFTAR PUSTAKA

Anton, H and Busby, R. C. (2003). Contemporary Linear Algebra. New

York: John Wiley and Sons.

Anton, H. and Rorres, C. (2000). Elementary Linear Algebra. Applications

Version. (8th Edition). New York: John Wiley and Sons.

Ariyus, Dony. (2008). Pengantar Ilmu Kriptografi. Teori, Analisis, dan

Implementasi. Yogyakarta: ANDI.

Budhi, Wono Setya. (1995). Aljabar Linear. Jakarta: Gramedia Pustaka

Utama.

Epp, Susanna. S. (2011). Discrete Mathematics with Applications (4th

Edition). Boston: Brooks/Cole Cencage Learning.

Leon, Steven J. (2001). Aljabar Linear dan Aplikasinya. Jakarta: Erlangga.

Mullen, Gary L. and James A. Sellers. (2016). Abstract Algebra: A Gentle

Introduction. (1st Edition). New York: CRC Press.

Sukirman. (2013). Teori Bilangan. Yogyakarta: UNY Press.


aplikasi aljabar linear pada kriptografi makalah …ini pokok-pokok aljabar linear, seperti sistem...

Documents