Senin, 08 Juli 2013

Modulo (Teori Bilangan)

Teori Bilangan
  • Teori bilangan (number theory) adalah teori yang mendasar dalam memahami algoritma kriptografi.
  • Bilangan yang dimaksudkan adalah bilangan bulat (integer).
       Aritmatika Modulo
Aritmatika modulo (modular arithmethic) memainkan peran yang penting dalam komputasi integer, khususnya pada aplikasi kriptografi. Operator yang digunakan pada aritmatika modulo adalah mod. Operator mod, jika digunakan pada pembagian bilangan bulat memberikan sisa pembagian sebagai kembaliannya. Sebagai contoh 53 mod 5 memberikan hasil = 10 dan sisa = 3. Maka 53 mod 5 = 3.
Defenisi : Misalkan  adalah bilangan bulat dan  adalah bilangan bulat > 0. Operasi  mod  memberikan sisa jika  dibagi .


Algoritma Euclidean

  • Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat.
  • Euclid, penemu algoritma Euclidean, adalah seorang matematikawan Yunani yang menuliskan algoritmanya tersebut dalam bukunya yang terkenal, Element.
  • Diberikan dua buah bilangan bulat tak-negatif m dan n (m ³ n). Algoritma Euclidean berikut mencari  pembagi bersama terbesar dari m dan n.
     Relatif Prima
Definisi:  Dua buah bilangan bulat  dan  dikatakan relatif prima jika FPB/GCD (x,y)=1
Contoh :
      7 dan 11 adalah relatif prima karena FPB/GCD (7,11) = 1
      31 dan 268 adalah relatif prima karena FPB/GCD (31,268) = 1.
      9 dan 132 bukan relatif prima karena FPB/GCD (9, 132) = 3.
Jika  dan  relatif prima, maka dapat ditemukan bilangan bulat  dan  sedemikian sehingga .
Contoh: Bilangan 20 dan 3 adalah relatif prima karena FPB (20, 3)=1, atau dapat ditulis  dengan  dan .
    Balikan Modulo (Modulo Invers)
jika a dan m relatif prima dan m > 1, maka kita dapat menemukan balikan (invers) dari a modulo m. Balikan dari a modulo m adalah bilangan bulat  (a invers) sedemikian sehingga a (a invers) kongruen 1 (mod m).
Kekongruenan Lanjar
  • Kekongruenan lanjar adalah kongruen yang berbentuk ax º b (mod m) dengan m adalah bilangan bulat positif, a dan b sembarang bilangan bulat,  dan x adalah peubah bilangan bulat.
  • Nilai-nilai x dicari sebagai berikut: ax = b + km yang dapat disusun menjadi x = (b+km)/a dengan k adalah sembarang bilangan bulat. Cobakan untuk k = 0, 1, 2, … dan k = –1, –2, … yang menghasilkan x sebagai bilangan bulat.
TEOREMA (Chinese Remainder Theorem) Misalkan m1, m2, …, mn adalah bilangan bulat positif sedemikian sehingga PBB(mi, mj) = 1 untuk i <> j. Maka sistem kongruen lanjar x kongruen ak (mod mk) mempunyai sebuah solusi unik modulo m = m1 × m2 × … × mn.

Aritmetika Modulo dan Kriptografi
Penggunaan Teori Bilangan Pada Sistem Kriptografi Merkle-Hellman (Knapsack)
Kriptografi Merkle Hellman merupakan sistem kunci asimetri, yang berarti bahwa dalam sistem komunikasi diperlukan dua kunci yaitu kunci publik dan kunci privat.
Sudah dijelaskan pada pembahasan sebelumnya bahwa algoritma superincreasing knapsack adalah algoritma yang lemah, karena chiperteks dapat didekripsi menjadi plainteksnya secara mudah dalam waktu lanjar. Sedangkan algoritma non-superincreasing knapsack atau normal knapsack adalah kelompok algoritma knapsack yang sulit (dari segi komputasi) karena membutuhkan waktu dalam orde eksponensial untuk memecahkannya. Namun, Martin Hellman dan Ralph Merkle menemukan cara untuk memodifikasi superincreasing knapsack menjadi non-superincreasing knapsack dengan menggunakan kunci publik (untuk enkripsi) dan kunci privat (untuk dekripsi). Kunci publik merupakan barisan non-superincreasing  sedangkan kunci privat tetap merupakan barisan superincreasing. Modifikasi dilakukan dengan menggunakan perhitungan aritmatika modulo.

 Aritmetika modulo cocok digunakan untuk kriptografi karena dua alasan:
  1. Oleh karena nilai-nilai aritmetika modulo berada dalam himpunan berhingga (0 sampai modulus m – 1), maka kita tidak perlu khawatir hasil perhitungan berada di luar himpunan.
  2. Karena kita bekerja dengan bilangan bulat, maka kita tidak khawatir kehilangan informasi akibat pembulatan (round off) sebagaimana pada operasi bilangan riil.
Teorema 3. (The Fundamental Theorem of Arithmetic). Setiap bilangan bulat positif yang lebih besar atau sama dengan 2 dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Teorema 4 (Teorema Fermat). Jika p adalah bilangan prima dan a adalah bilangan bulat  yang tidak habis dibagi dengan p,  yaitu PBB(a, p) = 1, maka ap–1 kongruen 1 (mod p)
Fungsi Euler f
Fungsi Euler f medefinisikan f(n) untuk n >= 1 yang menyatakan jumlah bilangan bulat positif < n yang relatif prima dengan n.
Teorema 5. Jika n = pq adalah bilangan komposit dengan p dan q prima, maka f(n) = f(p) f(q) = (p – 1)(q – 1).
Teorema 6. Jika p bilangan prima dan k > 0, maka f(pk) = pkpk-1 = pk-1(p – 1) .
      Algoritma Knapsack
Algoritma Knapsack adalah salah satu algoritma kriptografi kunci publik yang berguna untuk menjaga kerahasiaan pesa. Disebut kriptografi kunci publik (publik-key cryptography) karena kunci untuk enkripsi tidak rahasia dan dapat diketahui oleh siapapun (diumumkan ke publik), sementara kunci untuk dekripsi hanya diketahui oleh penerima pesan (karena itu rahasia).
a.       General Knapsak
Bentuk umum knapsack :
b.      Superincreasing Knapsack
Barisan superincreasing adalah suatu barisan dimana setiap nilai di dalam barisan lebih besar daripada jumlah semua nilai sebelumnya.
Contoh:  adalah barisan superincreasing, tetapi  bukan.
 
    Penggunaan Aritmatika Modulo dan Relatif Prima pada Knapsack
Pada kriptografi Merkle-Hellman, kunci yang digunakan terdiri knapsack. Kunci publik merupakan ‘hard’ knapsack, sedangkan kunci privat merupakan ‘mudah’ (superincreasing knapsack), yang dikombinasikan dengan dua bilangan tambahan, yaitu pengali (multiplier) dan modulus yang digunakan untuk mengubah superincreasing knapsack menjadi hard knapsack. Bilangan-bilangan yang sama digunakan untuk mengubah jumlah dari himpunan bagian dari hard knapsack  menjadi jumlah dari himpunan bagian dari superincreasing knapsack yang dapat dipecahkan dalam orde waktu polinomial.
 

0 komentar:

Poskan Komentar