Software Implementation of Long Integer Modular Arithmetic
Penggunaan algoritma kriptografi terkadang
dibutuhkan untuk dapat diimplementasikan pada sebuah hardware. diperlukan
performa system kriptografi public
utamanya dengan implementasi perhitungan aritmetika yang efisien. Dari sudut
pandang matematika, algoritma kriptografi public selalu menggunakan perhitungan
modulus eksponen long integer.
Algoritma kriptografi public seperti RSA
membutuhkan perhitungan bilangan besar yang cukup cepat, penggunaan memori yang
kecil, dan membutuhkan konsumsi daya yang cukup rendah serta kebal terhadap
side chanel attack.
Untuk itu diperlukan sebuah cara
untuk mempercepat perhitungan eksponensiasi modular. Berikut ini dibahas
beberapa teknik yang biasa digunakan dalam mendesain program perhitungan
bilangan besar. Pembahasan dimulai dari algoritma sederhana seperti perhitungan
cara Sekolah Dasar (schoolbook), cara Comba, cara Karatsuba dan yang paling
pupular dalam perhitungan modular, Montgomery Multiplication. Ketiga pertama
merupakan dasar perhitungan Montgomery Multiplication. Dari ketiga cara
tersebut terdapat kelebihan maupun kekurangan masing – masing tergantung pada
bagaimana tujuan perancang dalam mendesain program perhitungan bilangan besar.
Sebelum kita membahas metode
tadi lebih detail, terlebih dahulu mari kita sepakati terlebih dahulu notasi
yang akan mempermudah pemahaman algoritma. Kita representasikan long integer
sebagai array w-bit digit. Sebagai contoh w biasanya dipilih sesuai dengan
arsitektur prosesor, dengan w = 32 bit
untuk prosesor yang kenal saat ini. Panjang bit Integer dinotasikan dengan n
dan s adalah jumlah digit yang dibutuhkan untuk menyimpannya, sehingga s = ceil
(n/w). sebagai contoh, 256 bit integer (n = 256) membutuhkan s = 8 digit untuk
arsitektur 32 bit (w = 32). Dinotasikan long integer sebagai huruf besar dan
huruf kecil untuk menunjukkan nilai w bit digit. seperti A = (a a a … a)
dengan nilai 0 <= a <= 2^w.
——————————————————————————————–
rangkuman =
w = menentukan
arsitektur
n = Panjang
bit integer
s = Jumalh
digit untuk menyimpan integer
Hrf Bsr = Bilangan long
integer
Hrf Kcl = Nilai individu
setiap w bit (ex nilai individu tiap word)
——————————————————————————————–
Metode
Schoolbook
Metode schoolbook merupakan
penjabaran ulang perhitungan yang telah kita pelajari dalam sekolah dasar.
Secara program metode ini memerlukan dua loop bersarang dengan setiap loop
melibatkan setiap digit dari satu operand. Pada loop paling luar setiap digit
bi dari operand B akan dikalikan dengan operand A, dan hasilnya berupa (n+w)
bit yang ditambahkan sesuai dengan nilai urutannya. metode ini disebut juga
metode operand scanning method karena loop luar bergerak pada setiap digit
operand.
Pasangan nilai (u,v) merupakan
representasi 2w bit (ex double precision) integer u.2^w + v. Nilai ini
dihasilkan karena perkalian tiap bit selalu menghasilkan nilai minimal
berukuran 2^w. Schoolbook memproses tiap nilai hasil dengan rumusan umum berupa
a x b + p + u pada loop dalam, dimana setiap nilai a, b, p, dan u semuanya
berukuran w bit. sehingga nilai dari hasil inner loop (loop dalam) akan selalu
berukuran 2W bit. Hal ini yang menyebabkan metode schoolbook cukup mudah untuk
diimplementasikan pada bahasa pemprograman tingkat tinggi yang menyediakan tipe
data berukuran presisi ganda (double precision). Contohnya bahasa C dan bahasa
C++ yang menyediakan tipe data long long
untuk bilangan integer berukuran 64 bit. Dan pada bahasa Java, tipe data long memiliki
tingkat presisi 64 bit pada semua platform.
Perpangkatan long integer dapat
dihitung hampir duakali sama cepat dengan perkalian dua integer yang berbeda
yang dapat dikaji seperti pada persamaan berikut ini :
Perpangkatan long integer
biasanya dilakukan dalam dua langkah. Pada langkah pertama semua loop dalam
dilakukan dengan bentuk aj . ai dengan j<>i yang dihitung dan ditambahkan
seperti pada persamaan diatas. Langkah kedua mengulangi hasil pada langkah
pertama dan ditambahkan perkalian dalam dari diagonal utama. contoh ai^2.
