APLIKASI RESIDU KUADRATIK PADA SKEMA KRIPTOGRAFI

1APLIKASI RESIDU KUADRATIK PADA SKEMAKRIPTOGRAFI RABINTHE APPLICATION OF QUADRATIC RESIDUEON CRYPTOGRAPHIC SCHEME RABINArman Efendi1, Loeky Haryanto2, Amir Kamal Amir21SMAN 5 Tanralili, Kabupaten Maros, Propinsi Sulawesi Selatan, 2BagianMatematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, UniversitasHasanuddin MakassarAlamat Korespondensi :Arman EfendiFakultas Matematika dan Ilmu Pengetahuan AlamUniversitas HasanuddinMakassar,HP : 085255653937e-mail : armanefendi@gmail.com

2ABSTRAKKriptografi dengan menggunakan skema kripto Rabin adalah salah satu dari sekian banyak pengkodeanyang menggunakan residu kuadratik. Tulisan tugas akhir ini bertujuan mengetahui (1) penurunan dansifat-sifat simbol Jacobi (a/N) apabila N pq, di mana p dan q bilangan prima; (2) aplikasi teori residukuadratik modulo N pq dan simbol Jacobi pada skema kripto Rabin. Bilangan bulat N pq dengan pdan q prima kongruen 3 modulo 4 disebut bilangan Blum. Penulisan terbagi atas dua tahap: (i)melakukan kajian pustaka dan referensi yang berkaitan dengan residu kuadratik, dan simbol Jacobi(a/N) di mana N bilangan Blum; (ii) menurunkan sifat-sifat residu kuadratik modulo bilangan Blum Ndan kaitannya dengan skema kripto Rabin. Hasil yang diperoleh dari penulisan tugas akhir ini adalah:(i) beberapa sifat-sifat residu kuadratik modulo bilangan Blum dan sifat-sifat simbol Jacobi (a/N)dengan N adalah bilangan Blum; (ii) penurunan dan verifikasi langkah-langkah algoritma enskriptsidan deskriptsi skema Rabin berdasarkan teori residu kuadratik dan simbol Jacobi.Kata Kunci : residu kuadratik, simbol Legendre, simbol Jacobi, skema kripto RabinABSTRACTCryptography using the crypto Rabin's scheme is one of the many coding using quadratic resiues.Thisfinal paper aims to (1) derive some properties of Jacobi symbol (a/N) when N pq, where p and q areprimes, (2) applications the notions of quadratic residues modulo N pq and Jacobi symbols onRabin’s cryptographic scheme; The writing is splitted over three stages: (i) bibliographic study onreferences related to the notion of quadratic residues and Jacobi symbol (a/N) where N is a Bluminteger; (ii) deriving the properties of quadratic residues modulo a Blum integer N and theirrelationships with Rabin’s crypto scheme. The output of this thesis are: (i) some properties ofquadratic residues modulo N pq and of Jacobi simbol (a/N) where N is a Blum integer; (ii) somederivations and verifications of steps in the enscription/description algorithms of Rabin’s cryptoscheme based on quadratic residues and Jacobi symbols.Keywords:Quadratic residues, Legendre symbol, Jacobi symbol, Rabin’s crypto scheme

3PENDAHULUANTingkat kesulitan membobol sistem keamanan RSA yang salah satu kuncipubliknya adalah bilangan N pq, dengan p dan q prima berukuran sangat besartetapi tidak diketahui publik (walaupun nilai N diketahui publik), dipercaya samasulitnya dengan mencari kedua faktor p dan q dari N. Sayangnya, tak ada satu orangpun yang bisa membuktikan bahwa sistem RSA provably secure, yaitu tidak ada buktibahwa satu-satunya cara untuk membobol sistem keamanan RSA adalah denganmencari kedua faktor p dan q. Walaupun demikian, dalam praktek belum pernahterbukti adanya sebuah metoda membobol RSA tanpa menggunakan pengetahuankedua faktor prima p dan q (Scheilder dkk, 1994).Dalam komunikasi data secara digital, semua data pada umumnya dikonversi menjadi bilangan, sebagian besar dalam basis 2 (bilangan biner). Hal inimenyebabkan konsep teori bilangan termasuk yang di bahas secara aljabar (algebraicnumber theory) sangat berpotensi sebagai mathematical tool yang sangat ampuh didalam pemodelan dan perancangan sistem yang di buat untuk meningkatkankeamanan data.Komunikasi data di ruang publik (melalui internet misalnya) memerlukansistem keamanan yang memadai. Bidang ilmu yang membahas sistem keamanankomunikasi digital di ruang publik disebut kriptografi. Saat ini, sistem keamananpublik yang paling populer secara komersial adalah sistem kriptografi RSA, namayang diadopsi dari ketiga penemunya: R.L. Rivest, A. Shamir, and L. Adleman(Menez dkk,1996).Pada intinya, RSA hanya menggunakan proses encoding dan decoding yangsangat efisien (karena secara matematis hanya memerlukan Teorema Euler untukproses deskriptsi-nya) sehingga RSA adalah skema kriptografi yang paling diminatisaat ini. Dari lain pihak, residu kuadratis lebih umum, teori bilangan Gauss, seringdigunakan sebagai alat di dalam beberapa skema kriptografi untuk menutupkelemahan dari skema kriptografi RSA (yang tidak provably secure) (Despotovic,2000).Penelitian ini bertujuan untuk menurunkan dan sifat-sifat simbol Jacobi (a/N)apabila N pq, di mana p dan q bilangan prima dan menerapkan teori residukuadratik modulo bilangan Blum N pq pada skema kripto Rabin;

4BAHAN DAN METODELokasi dan Rancangan PenelitianPenelitian ini bertempat di Jurusan Matematika FMIPA UniversitasHasanuddin. Rancangan penelitian ini berbentuk penelitian kualitatif denganmelakukan studi kepustakaan, dengan mengumpulkan dan mengkaji materi-materiyang berkaitan dengan residu kuadratik .AnalisisPenelitian matematika pada umumnya adalah penelitian secara deduktif, tanpamenggunakan data. Penelitian dilakukan dengan melalui tahapan perumusan beberapadefinisi secara deduktif, diawali dari residu kuadratik, simbol Legendre, simbol Jacobidan seterusnya dan dari setiap konsep yang didefinisikan, diturunkan beberapa sifatsifat dari konsep tersebut. Langkah selanjutnya adalah merumuskan skema kriptoRabin: enskriptsi dan deskriptsi skema kripto tersebut, termasuk analisis danpembuktian bahwa skema kripto tersebut bisa diimplementasikan dan diverifikasikebenarannya.Dalam penelitian tugas akhir, dihasilkan juga program Maple dan Mapletuntuk simulasi skema kripto Rabin, tetapi untuk mempersingkat penulisan, tidakdisajikan di sini.

5HASILHasil yang dibahas di sini terfokus pada salah satu subgroup (disebut grupresidu kuadratis) dari grup bilangan-bilangan bulat ZN {x Z 1 x N ; FPB(x,N) 1}. Banyak unsur dari ZN dinyatakan melalui simbol (N).Teorema 1 (Teorema Euler): Untuk setiap a ZN berlaku a (N) 1 (modN). Bukti teorema ini ditiadakan karena bisa dijumpai di semua buku teks pengenalanaljabar abtrak. Pada khususnya, jika N p prima, maka berlaku (Teorema Fermat)ap 1 1 (mod p).Definisi 1 (Residu kuadratik) : Unsur a ZN disebut unsur residukuadratik modulo N jika kongruensi x2 a (mod N) memiliki sebuah solusi x ZN .Jika kongruesni ini tidak memiliki solusi maka a disebut unsur nonresidu kuadratikmodulo NContoh 1: Untuk Z7 dengan anggota himpunan {1,2,3,4,5,6}. Unsur yangtermasuk residu kuadratik adalah {1,2,4} . Untuk Z15 dengan anggota himpunan{1,2,3,4,5,6,7,8,9,10,11,12,13,14}. Unsur yang termasuk residu kuadratik adalah{1,2,4,5,6,9,10} .Teorema 2 : Jika p 2 adalah bilangan prima maka terdapat sebanyak (p 1)/2 unsur-unsur residu kuadratik dan sebanyak (p 1)/2 unsur nonresidu kuadratikdi dalam Zp . Bukti. Pemetaan α: Zp Zp dengan α(x) x2 adalah homomorfismadengan sifat, setiap dua unsur (x dan x) di dalam Zp dipetakan ke tepat 1 unsur (x2)juga di dalam Zp . Jadi daerah sekawan Zp terbagi dua: di luar daerah hasil (range)dan di dalam daerah hasil. Jelas semua unsur di dalam daerah hasil adalah unsurresidu kuadratik yang membentuk subgrup yang banyaknya ½ dari Zp p 1.Contoh 2: Untuk Z11 dengan anggota himpunan {1,2,3,4,5,6,7,8,9,10}. Unsuryang termasuk residu kuadratik adalah {1,3,4,5,9} sedangkan {2,6,7,8,10} bukanresidu kuadratik sehingga unsur residu kuadratik yang membentuk subgrupbanyaknya ½ dari Z11 11 1 yaitu ½.(11- 1) 5

6 Definisi 2 (Simbol Legendre) : Jika 2 adalah prima, makadandidefinisikan symbol 0, jika c kelipatan pc 1, jika c adalah kuadratik residu modulo pp 1, jika c adalah nonkuadratik residu modulo p Simbol cp di sebut simbol Legendre dari c modulo p .Jelas untuk setiap c yang kongruen dengan suatu unsur x Zp berlaku cp 1.Teorema berikut adalah teorema standard dalam teori bilangan yang pembuktiannyabisa dijumpai di semua buku pengenalan teori bilangan.Teorema 3 : Jika 2 adalah prima, maka () modDefinisi 3 (Simbol Jacobi) : Misalkan b adalah bilangan bulat ganjil positif dan aadalah bilangan bulat. Jika adalah faktorisasi prima dari dimanatidak harus berbeda, maka didefinisikan Simbol .disebut simbol Jacobi.Definisi 4 (Bilangan Blum) : Bilangan bulat positif N dengan N pq dengan p dan qadalah bilangan prima yang masing-masing kongruen dengan 3 modulo 4 disebutbilangan Blum.Apabila x adalah solusi dari kongruensix2 c mod N,(1)maka x sering disebut akar dari c modulo N. Tentu saja negatif dari akar c juga akardari c modulo N sehingga akar ini biasa ditulis sebagaix c mod N.(2)Jika N pq dengan p dan q prima, maka dari Chinese Remainder Theorem bisadisimpulkan bahwa kongruensi (2) ekuivalen dengan kongruensix c mod p,x c mod q.(3)

7Dengan kata lain, sebuah kongruensi (1) ekuivalen dengan dua kongruensix2 c mod p,x2 c mod q.(4)Tetapi mencari c mod N (atau mencari c mod p dan c mod q) tidakselalu mudah, kecuali pada kasus N adalah bilangan Blum, seperti yang dinyatakandalam teorema berikut.Teorema 4 : Jika N pq dan c x 2 mod N maka (1). x c(p 1)/4 mod Nmemenuhi kongruensi pertama di dalam ekspresi (4); (2). x c(q 1)/4 mod Nmemenuhi kongruensi kedua di dalam ekspresi (4). Bukti. Cukup dibuktikanpernyataan (1) karena bukti pernyataan (2) serupa. Jika x c(p 1)/4 mod N maka x2 c(p 1)/2 mod p dan x2 c(p 1)/2 mod p c(p 1)/2 1 mod p c(p 1)/2c mod p (c·c(p 1)/2mod p). Karena diketahui c x 2 mod N , maka c adalah residu kuadratis sehinggajika hasil terakhir dilanjutkan, diperoleh x2 (c·c(p 1)/2 mod p) (c mod p)(1 mod p) c mod p.Untuk selanjutnya, nilai-nilai ke-4 akar yang diperoleh dari Teorema 6 masingmasing diberi nama sebagai berikut:mp c(p 1)/4 mod Ndan negatifnya: mp N mp.mq c(q 1)/4 mod Ndan negatifnya: mq N mq.Karena ke-4 nilai mp, mp, mq dan mq adalah solusi dari ekspresi (4) yang ekuivalendengan ekspresi (3) dan karena ekspresi (3) bisa ditulis ulang dan diuraikan sebagai 4kongruensii.x mp mod p,x mq mod q;ii.x mp mod p,x mq mod q;(5)iii. x mp mod p,x mq mod q;iv. x mp mod p,x mq mod q;maka karena ekspresi (3) ekuivalen dengan ekpresi (1) dan juga dengan ekspresi (2),ke-4 solusi dari kongruensi i, ii, iii dan iv adalah solusi dari (1) dan (2). Untukselanjutnya, solusi dari i, ii, iii dan iv masing-masing disebut Akar-1, Akar-2, Akar-3dan Akar-4.

8PEMBAHASAN SKEMA KRIPTO RABINPada penelitian ini terlihat bahwa residu kuadratik yang diselesaikan denganmetode Rabin menghasilkan empat buah nilai akar, namun untuk menentukan nilaiyang tepat digunakan cara Elia Michele dengan menambahkan parameter lain yaitunilai b0 dan b1.Jika 2 adalah prima, maka didefinisikan symboldan 0, jika c kelipatan pc 1, jika c adalah kuadratik residu modulo pp 1, jika c adalah nonkuadratik residu modulo p Simbol cp di sebut simbol Legendre dari c modulo p .(Hassan dkk,2011). Bentuk() modadalah hubungan antara simbol legendredengan residu kuadratik dalam bentuk bilangan modulo. (Sorin,2012).Penggunaan simbol jacobi merupakan perluasan dari simbol legendre yang berbentuk: Di mana adalah simbol legendre dengan 1 i m (Giovani dkk,2007)Penggunaan bilangan bulat positif N dengan N pq dengan p dan q adalahbilangan prima yang masing-masing kongruen dengan 3 modulo 4 disebut bilanganBlum. (Hard,1997).(Residu kuadratik) : Unsur a ZN disebut unsur residu kuadratik moduloN jika kongruensi x2 a (mod N) memiliki sebuah solusi x ZN . Jika kongruesni initidak memiliki solusi maka a disebut unsur nonresidu kuadratik modulo N(Mollin,2008).Jika N pq dan c x 2 mod N maka (1). x c(p 1)/4 mod N memenuhikongruensi pertama yaitux2 c mod p.; (2). x c(q 1)/4 mod N memenuhikongruensi kedua x2 c mod q. (Tsung dkk,2010). Dengan hasil akhir adalah empatbuah akar seperti berikut ini : mp c(p 1)/4 mod Nmq c(q 1)/4 mod Ndan negatifnya: mp N mp.dan negatifnya: mq N mq. (Rabin,1979).