RSA ALGORITHM
Dony Ariyus, Jurusan Teknik Informatika, STMIK AMIKOM Yogyakarta, Jl. Ring Road Utara, Condong Catur, Sleman, Yogyakarta - Indonesia Sekian banyak algoritma kriptografi kunci-publik yang pernah dibuat, algoritma yang paling populer adalah algoritma RSA. RSA algortima melakukan pemfaktoran bilangan yang sangat besar, oleh karena alasan tersebut RSA dianggap aman. Untuk membangkitkan kedua kunci, yang dipilih dua bilangan prima acak yang besar. Algoritma RSA dibuat oleh 3 orang peneliti dari MIT (Massachussets Institute of Technology) pada tahun 1976, yaitu: Ron (R)ivest, Adi (S)hamir, dan Leonard (A)dleman yang mengekpresikan bahwa plaintext dienkripsi menjasi block-block yang setiap block memiliki nilai bilangan biner yang diberi symbol “n”, plaintext block “M” dan ciphertext block “C”. Melakukan enkripsi pesan “M” pesan dibagi ke dalam block-block numeric yang lebih kecil dari pada “n”(data biner dengan pangkat terbesar), jika bilangan prima yang panjangnya 200 digit dan dapat menambah berberapa bit 0 dikiri bilangan untuk menjaga agar pesan tetap kurang dari nilai “n”.
Pembuat Alogritma RSA
Besaran-besaran yang digunakan pada algoritma RSA: 1. p dan q bilangan prima 2. r = p ⋅ q 3. φ(r) = (p – 1)(q – 1) 4. PK (kunci enkripsi) 5. SK (kunci dekripsi) 6. X (plainteks) 7. Y (cipherteks)
(rahasia) (tidak rahasia) (rahasia) (tidak rahasia) (rahasia) (rahasia) (tidak rahasia)
Algoritma RSA didasarkan pada teorema Euler yang menyatakan bahwa aφ(r) ≡ 1 (mod r) yang dalam hal ini,
(1)
1. a harus relatif prima terhadap r 2. φ(r) = r(1 – 1/p1)(1 – 1/p2) … (1 – 1/pn), yang dalam hal ini p1, p2, …, pn adalah faktor prima dari r. •
φ(r) adalah fungsi yang menentukan berapa banyak dari bilangan-bilangan 1, 2, 3, …, r yang relatif prima terhadap r.
Berdasarkan sifat am ≡ bm (mod r) untuk m bilangan bulat ≥ 1, maka persamaan (1) dapat ditulis menjadi a mφ(r) ≡ 1m (mod r) atau amφ(r) ≡ 1 (mod r) •
Bila a diganti dengan X, maka persamaan (2) menjadi Xmφ(r) ≡ 1 (mod r)
•
(2)
(3)
Berdasarkan sifat ac ≡ bc (mod r), maka bila persamaan (3) dikali dengan X menjadi: Xmφ(r) + 1 ≡ X (mod r)
(4)
yang dalam hal ini X relatif prima terhadap r. •
Misalkan SK dan PK dipilih sedemikian sehingga SK ⋅ PK ≡ 1 (mod φ(r))
(5)
SK ⋅ PK = mφ(r) + 1
(6)
atau
•
Sulihkan (6) ke dalam persamaan (4) menjadi: X SK ⋅ PK ≡ X (mod r)
•
(7)
Persamaan (7) dapat ditulis kembali menjadi (X PK)SK ≡ X (mod r)
(8)
yang artinya, perpangkatan X dengan PK diikuti dengan perpangkatan dengan SK menghasilkan kembali X semula. •
•
Berdasarkan persamaan (8), maka enkripsi dan dekripsi dirumuskan sebagai berikut: EPK(X) = Y ≡ XPK mod r
(8)
DSK(Y) = X ≡ YSK mod r
(9)
Karena SK ⋅ PK = PK ⋅ SK, maka enkripsi diikuti dengan dekripsi ekivalen dengan dekripsi diikuti enkripsi: ESK(DSK(X)) = DSK(EPK(X)) ≡ XPK mod r
•
(10)
Oleh karena XPK mod r ≡ (X + mr)PK mod r untuk sembarang bilangan bulat m, maka tiap plainteks X, X + r, X + 2r, …, menghasilkan cipherteks yang sama. Dengan kata lain, transformasinya dari banyak ke satu. Agar transformasinya satu-ke-satu, maka X harus dibatasi dalam himpunan {0, 1, 2, …, r – 1} sehingga enkripsi dan dekripsi tetap benar seperti pada persamaan (8) dan (9).
Proses Enkripsi dan Dekripsi RSA
Daftar Pustaka Adams, Carlisle M. (May, 1997). The CAST-128 Encryption Algorithm. Canada: Entrust Technologies. Adams, Carlisle M. (1997). Constructing Symmetric Ciphers Using the CAST Design Procedure. Canada: Entrust Technologies. Altman, J. (September 2000). Telnet Encryption: CAST-128 64 bit Cipher Feedback. Ney York: Columbia University. Adams, Carlisle M. (Oktober 2000). Use of the CAST-128 Encryption Algorithm in CMS. Canada: Entrust Technologies. An Introduction to Cryptography. (2002). PGP Corporation Ariyus,Dony,” Computer Security”, andi Offset, Yogyakarta 2005 Ariyus,Dony, “ Kamus Hacker”, Andi Offset, Yogyakarta, 2005 Ariyus, Dony “ Kriptografi: Keamanan Data dan Komunikasi”. Graha Ilmu, Yogyakarta, 2006 Bishop,David, Introduction to Cryptographywith Java Applet, Jones and Bartlet Computer Science, 2003. Bond, Mike dan Piotr Zielinski. Decimalisation Table Attacks for PIN Cracking. University of Cambridge. 2003. Bruce Scheier, “ Applied Cryptography,” Jhon Willey & Son inc Canada, 2001 C. Adams, “Constructing Symmetric Ciphers Using the Procedure,"Designs, Codes and Cryptography, v.12, n.3,Nov 1997
CAST
Design
C. Adams, “Constructing Symmetric Ciphers Using the Procedure,"Designs, Codes and Cryptography, v.12, n.3,Nov 1997
CAST
Design
Callas, J, L Donnerhacke, H Finney, andRThayer. (1998). OpenPGP Message Format. RFC 2440 Edition Cobb, Chey. “Cryptography For Dummies”. John Wiley & Sons, Canada, 2004 Daemen, J., and Rijmen, V. “ Rijndael: The Advanced Encrption Standard” Dr.Dobb’s Journal March 2001 E. Biham, “New Types of Cryptanalytic Attacks Using Related Keys," Journal of Cryptology, v. 7, n. 4, 1994.
Gollmann, Dieter, “Computer Security” Jhon Willey & Son Inc, Canada, 1999 Gutmann, Peter, Cryptography and Data http://www.cs.auckland.ac.nz/~pgut001
Security,
University
of
Auckland.
Hankerson D.R, “ Conding Theory and Cryptography, 2ed Edition” Marcel Dekker, New York, 2000 Istnick, Anna C. dan Emilio Caligaris. ATM Fraud and Security. DIEBOLD. Amerika Serikat.2003 James J. Gillogly. (1995).Cryptologia. http://members.fortunecity.com/ Litan, Avivah. Criminals Exploit Consumer Bank Account and ATM System Weaknesses. Gartner. 2005. M. Bellare, R. Canetti, and H. Karwczyk, \Keying Hash Functions for Message Authentication," Advances in Cryptology |CRYPTO '96 Proceedings, Springer-Verlag, 1996. M. Blaze, W. Diffie, R. Rivest, B. Schneier, T. Shimomura, E. Thompson, and M.Weiner, “Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security," Jan 1996. Nichols, R,” ICSA Guide to Cryptography” McGraw-Hill, New York 1999 Piper, Fred dan Murphy, Sean, “Cryptography: A Very Short Introduction”, Oxford University Press 2002 R. Anderson and E. Biham, “Two Practical and Provably Secure Block Ciphers: BEAR and LION," Fast Software Encryption, Third International Workshop Proceedings, Springer-Verlag, 1996. R. Anderson and E. Biham, ”Tiger: A Fast New Hash Function," Fast Software Encryption, Third International Workshop Proceedings, Springer-Verlag, 1996 R. F. Churchhouse, Code and Ciphers: Julius Caesar, the enigma and the Internet,Cambridge University Press, 2002 Rhee, Man Young, “Internet Security “Cryptographic Principles, Algorithms, and Protocols”, Jhon Wiley & Son Ltd, England, 2003 Schneier, Bruce. 1993. Description of a New Variable-Length Key, 64-Bit Block Cipher (Blowfish). Springer-Verlag.
Schneier, Bruce. 1995. The Blowfish Encryption Algorithm -- One Year Later. Dr. Dobb’s Journal. Schneier, Bruce. 1996. Applied Cryptography, Second Edition: Protocols, Algorithms, and Source Code in C. John Wiley and Sons. Schneier, Bruce. 1998. Twofish: A 128-Bit Block Cipher. Schneier, Bruce. 1999. Performance Comparison of the AES Submission. Schneier, Bruce. 2001. The Twofish Encryption Algorithm - Block encryption for the 21st century. Dr. Dobb’s Journal. Stalling William, “Cryptography and Network Security” Prentice-Hall, USA, 2003 Stalling William, “Network and Internetwork Security” Prentice-Hall, USA, 1995 Sullivan, Geoff and Frode Weierud.(2005). Cryptologia. http://www.tandf.co.uk/journals Steel, Graham. Formal Analysis of PIN Block Attacks. University of Edinburgh. Scotland. 2006. Vellani, Karim H. dan Mark Batterson. Security Solutions for ATM. Threat Analysis Group. 2003.
