Modul Kriptografi PDF

Preview

Summary

TEORI&APLIKASI KRIPTOGRAFI Sentot Kromodimoeljo 101111 111101 100001 011110 SPK IT Consulting Teori dan Aplikasi Kriptografi Sentot Kromodimoeljo Desember 2009 ii Teori dan Aplikasi Kriptografi Penulis: Sentot Kromodimoeljo Desember 2009 ISBN 978-602-96233-0-7 453 halaman, 14.85 x 21 cm Penerbit...

Description

TEORI&APLIKASI

KRIPTOGRAFI Sentot Kromodimoeljo

101111 111101 100001 011110

SPK IT Consulting

Teori dan Aplikasi Kriptografi Sentot Kromodimoeljo Desember 2009

ii Teori dan Aplikasi Kriptografi Penulis: Sentot Kromodimoeljo Desember 2009 ISBN 978-602-96233-0-7 453 halaman, 14.85 x 21 cm

Penerbit: SPK IT Consulting c °2009 SPK IT Consulting. Dilarang mereproduksi buku ini sebagian atau seluruhnya tanpa izin dari SPK IT Consulting.

Typesetting menggunakan LATEX.

Sentot Kromodimoeljo Consultant, SPK IT Consulting Information Technology, Cryptography, Mathematical Logic [email protected]

iii Untuk anak-anakku yang tercinta, Kelsey dan Zakrie.

iv

Kata Pengantar Sangat banyak buku dalam bahasa Indonesia mengenai ilmu dan teknologi komputer yang telah diterbitkan, namun hampir semua bersifat kontemporer. Buku kontemporer memang berharga dan diperlukan, tetapi untuk pembaca yang ingin belajar teori ilmu komputer secara mendalam, diperlukan buku yang dapat memberi motivasi dan arahan untuk studi lanjut. Buku ini mencoba menjelaskan teori dan praktek kriptografi dan ditujukan terutama kepada pembaca yang ingin memperdalam pengetahuannya mengenai kriptografi. Banyak orang yang enggan membaca buku yang berisi matematika karena presentasi matematika biasanya hambar tanpa motivasi. Kriptografi tidak bisa dipisahkan dari matematika, jadi buku ini juga berisi matematika, akan tetapi penulis mencoba menggunakan bahasa yang sederhana dan memberi motivasi dan penjelasan untuk setiap rumus matematika agar mudah dipahami dan tidak membosankan. Memang untuk mendalami ilmu kriptografi tidak ada jalan pintas dan diperlukan ketekunan yang luar biasa. Tetapi buku ini dapat juga dibaca untuk mendapatkan pengetahuan superficial mengenai ilmu kriptografi, dengan melewatkan atau membaca secara sepintas saja bagian-bagian yang sukar matematikanya. Tentunya teori tanpa aplikasi adalah sia-sia, oleh sebab itu aplikasi kriptografi juga dibahas. Mudah-mudahan buku ini berguna bagi pembaca yang ingin memperdalam pengetahuan di bidang kriptografi. Kalau ada kesalahan dalam buku ini, mohon maaf sebelumnya. Selamat membaca! Sentot Kromodimoeljo.

v

vi

KATA PENGANTAR

Terima kasih Penulis ingin mengucapkan terima kasih yang sebesarnya kepada Dr. Laksana Tri Handoko dari Pusat Penelitian Fisika LIPI, Prof. Chan Basaruddin, Dr. Lim Yohanes Stefanus dan Dr. Setiadi Yazid dari Fakultas Ilmu Komputer UI, dan Dr. Budi Susilo Soepandji dari Departemen Pertahanan, atas komentar, saran dan dukungannya. Penulis juga ingin mengucapkan terima kasih yang sebesarnya kepada semua teman di KINDO 21 atas komentar, saran dan dukungan yang telah diberikan, terutama kepada Kemal Surianegara, Neni Sintawardani, Arnold Soetrisnanto, E.T. Sari, Ardi Sutedja, Hartojo Wignjowijoto, Hidayat Brata dan Yandri Susanto.

vii

viii

TERIMA KASIH

Daftar Isi Kata Pengantar

v

Terima kasih

vii

1 Pendahuluan

1

2 Konsep-konsep Dasar 2.1 Konsep Acak . . . . . . . . . . 2.2 One-Time Pad . . . . . . . . . 2.3 Cryptanalysis . . . . . . . . . . 2.3.1 Known Plaintext Attack 2.3.2 Analisa Statistik . . . . 2.3.3 Brute Force Search . . . 2.4 Manajemen Kunci . . . . . . . 2.5 Operasi dasar . . . . . . . . . . 2.6 Ringkasan . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

5 6 7 9 9 11 13 14 16 18

3 Matematika I - Aritmatika Modular 3.1 Group, Monoid, Ring dan Field . . . 3.2 Prinsip Induksi . . . . . . . . . . . . 3.3 GCD . . . . . . . . . . . . . . . . . . 3.4 Algoritma Euclid . . . . . . . . . . . 3.5 Aritmatika Modular . . . . . . . . . 3.6 Ringkasan . . . . . . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

19 19 21 23 25 30 36

4 Kriptografi Simetris Sederhana 4.1 Enkripsi Affine . . . . . . . . . 4.2 Transformasi Digraph . . . . . 4.3 Matrik Enkripsi . . . . . . . . . 4.4 Ringkasan . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

37 37 41 44 50

ix

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . .

x

DAFTAR ISI

5 Matematika II - Polynomial Field 5.1 Integral Domain . . . . . . . . . 5.2 Homomorphism dan Ideal . . . . 5.3 Principal Ideal Domain . . . . . . 5.4 Prime Ideal dan Maximal Ideal . 5.5 Polynomial Ring . . . . . . . . . 5.6 Euclidean Domain . . . . . . . . 5.7 Polynomial Field . . . . . . . . . 5.8 Ringkasan . . . . . . . . . . . . .

. . . . . . . .

51 52 53 61 63 68 72 77 78

6 Kriptografi Stream Cipher 6.1 RC4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79 81 89

7 Kriptografi Block Cipher 7.1 DES . . . . . . . . . . . 7.2 Mode Operasi DES . . . 7.3 3DES . . . . . . . . . . 7.4 AES . . . . . . . . . . . 7.5 Ringkasan . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

. . . . . . . .

. . . . .

8 Analisa Block Cipher 8.1 Differential Cryptanalysis . . . . . . . . . . 8.1.1 Analisa 1 Putaran . . . . . . . . . . 8.1.2 Mekanisme n-round Characteristic . 8.1.3 Penggunaan n-round Characteristic 8.1.4 Differential Cryptanalysis DES . . . 8.2 Linear Cryptanalysis . . . . . . . . . . . . . 8.2.1 Perkiraan Linear untuk S-boxes . . . 8.2.2 Perkiraan Linear untuk DES . . . . 8.2.3 Known Plaintext Attack DES . . . . 8.3 Pelajaran dari Cryptanalysis DES . . . . . 8.4 Ringkasan . . . . . . . . . . . . . . . . . . . 9 Cryptographically Secure Hashing 9.1 MD5 . . . . . . . . . . . . . . . . . . 9.2 SHA . . . . . . . . . . . . . . . . . . 9.3 Hash Message Authentication Code . 9.4 Ringkasan . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . . . . .

. . . . .

. . . . . . . . . . .

. . . .

. . . . .

91 92 99 102 103 110

. . . . . . . . . . .

113 115 116 118 123 124 125 126 127 130 131 132

. . . .

133 135 141 144 145

DAFTAR ISI

xi

10 Matematika III - Dasar untuk PKC 10.1 Fermat’s Little Theorem . . . . . . . 10.2 Chinese Remainder Theorem . . . . 10.3 Fungsi Euler . . . . . . . . . . . . . 10.4 Group of Units . . . . . . . . . . . . 10.5 Homomorphism Theorem . . . . . . 10.6 Field Extension . . . . . . . . . . . . 10.7 Finite Field . . . . . . . . . . . . . . 10.8 Ringkasan . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

147 147 148 150 153 159 165 170 177

11 Matematika IV - Kuadrat 179 11.1 Quadratic Residue . . . . . . . . . . . . . . . . . . . . . . . . . 179 11.2 Akar Kuadrat Modulo Bilangan Ganjil . . . . . . . . . . . . . . 194 11.3 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 12 Matematika V - Algebraic Number 12.1 Ruang Vektor dan Module . . . . . 12.2 Separable Field Extension . . . . . 12.3 Norm, Trace . . . . . . . . . . . . . 12.4 Algebraic Number Theory . . . . . 12.5 Ringkasan . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

199 199 201 206 213 231

13 Matematika VI - Test Bilangan Prima 13.1 Pseudoprime dan Bilangan Carmichael 13.2 Metode Solovay-Strassen . . . . . . . . 13.3 Metode Miller-Rabin . . . . . . . . . . 13.4 Test Deterministik . . . . . . . . . . . 13.5 Ringkasan . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

233 233 239 241 251 252

14 Matematika VII - Penguraian Bilangan Bulat 14.1 Metode Rho . . . . . . . . . . . . . . . . . . . . 14.2 Fermat Factorization . . . . . . . . . . . . . . . 14.3 Metode Dixon . . . . . . . . . . . . . . . . . . . 14.4 Metode Continued Fraction . . . . . . . . . . . 14.5 Metode Quadratic Sieve . . . . . . . . . . . . . 14.6 Metode Number Field Sieve . . . . . . . . . . . 14.7 Ringkasan . . . . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

253 254 258 259 263 272 277 288

. . . .

289 289 292 293 295

. . . . .

15 Matematika VIII - Logaritma Diskrit 15.1 Metode Silver-Pohlig-Hellman . . . . . 15.2 Metode Baby Steps - Giant Steps . . . 15.3 Metode Index Calculus . . . . . . . . . 15.4 Ringkasan . . . . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

xii

DAFTAR ISI

16 Kriptografi Public Key 16.1 RSA . . . . . . . . . . . . . . . . . . 16.2 Diffie-Hellman . . . . . . . . . . . . . 16.3 DSA . . . . . . . . . . . . . . . . . . 16.4 ElGamal . . . . . . . . . . . . . . . . 16.5 Knapsack . . . . . . . . . . . . . . . 16.6 Zero-Knowledge Protocol . . . . . . 16.7 Penggunaan Kriptografi Public Key 16.8 Ringkasan . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

297 298 301 302 304 306 309 313 313

17 Kriptografi Elliptic Curve 315 17.1 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 18 Quantum Key Distribution 323 18.1 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 19 Kebutuhan Akan Kriptografi 19.1 Informasi Sensitif . . . . . . 19.2 Mencegah Penyadapan . . . 19.3 Mencegah Penyamaran . . . 19.4 Ringkasan . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

329 329 331 333 334

20 Aplikasi - Pengamanan Sesi 20.1 SSL/TLS . . . . . . . . . . . 20.1.1 Standard SSL/TLS . . 20.1.2 Penggunaan SSL/TLS 20.2 SSH . . . . . . . . . . . . . . 20.2.1 Standard SSH . . . . . 20.2.2 Penggunaan SSH . . . 20.3 IPsec . . . . . . . . . . . . . . 20.3.1 Standard IPsec . . . . 20.3.2 Penggunaan IPsec . . 20.4 Ringkasan . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

335 335 336 339 340 341 342 343 344 350 350

21 Aplikasi - Pengamanan Email 353 21.1 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 22 Aplikasi - Authentication 357 22.1 Kerberos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 22.2 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

DAFTAR ISI

xiii

23 Aplikasi - PKI 361 23.1 PGP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 23.2 X.509 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364 23.3 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 24 Aplikasi - Cryptographic Library 24.1 OpenSSL . . . . . . . . . . . . . 24.2 RSA BSafe . . . . . . . . . . . . 24.3 Cryptlib . . . . . . . . . . . . . . 24.4 Ringkasan . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

371 372 373 374 383

25 Analisa Protokol Kriptografi 385 25.1 Ringkasan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 26 Kendala Penggunaan Kriptografi 26.1 Manajemen Kunci . . . . . . . . 26.2 Sistem Terlalu Rumit . . . . . . 26.3 Sistem Tidak Sesuai Kebutuhan 26.4 Ringkasan . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

399 399 400 401 402

27 Masa Depan Kriptografi 27.1 Perkembangan Matematika 27.2 Perkembangan Hardware . . 27.3 Quantum Computing . . . . 27.4 Ringkasan . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

403 403 404 405 410

. . . .

. . . .

. . . .

A Daftar Notasi, Singkatan dan Istilah

411

B Tabel untuk cipher f DES

417

C Tabel S-box AES

421

D Tabel untuk algoritma MD5

423

xiv

DAFTAR ISI

Daftar Gambar 2.1

Proses enkripsi dan dekripsi . . . . . . . . . . . . . . . . . . . .

5

6.1 6.2

Linear feedback shift register . . . . . . . . . . . . . . . . . . . Kombinasi non-linear LFSR . . . . . . . . . . . . . . . . . . . .

80 81

7.1 7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9

Enkripsi DES . . . . . . . . . Algoritma Key Schedule DES Fungsi Cipher f . . . . . . . . DES dengan mode ECB . . . DES dengan mode CBC . . . DES dengan mode CFB . . . DES dengan mode OFB . . . Enkripsi dan Dekripsi 3DES . Enkripsi AES . . . . . . . . .

. . . . . . . . .

93 95 98 99 100 101 101 102 104

8.1 8.2

1 Putaran DES . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Putaran DES . . . . . . . . . . . . . . . . . . . . . . . . . . .

113 114

18.1 Contoh Sesi Protokol Bennett-Brassard . . . . . . . . . . . . .

327

. . . . . . . . .

xv

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

xvi

DAFTAR GAMBAR

Daftar Tabel 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8

Proses enkripsi one-time pad . . . . . . . . . . . . Proses dekripsi one-time pad . . . . . . . . . . . . Tabel operasi xor . . . . . . . . . . . . . . . . . . . Enkripsi dengan Caesar cipher . . . . . . . . . . . Hasil analisa frekuensi . . . . . . . . . . . . . . . . Mencoba semua kemungkinan kunci Caesar cipher Tabel untuk S1 . . . . . . . . . . . . . . . . . . . . Tabel Initial Permutation . . . . . . . . . . . . . .

. . . . . . . .

7 7 8 10 12 15 17 18

3.1

Contoh aritm...