Topik kriptografi RSA sudah dibahas di banyak artikel dan video oleh orang lain, jadi di sini saya hanya ingin memberikan mengenai topik RSA secara praktis. Praktis di sini artinya saya akan memakai tool openssl dan kode Python untuk melakukan enkripsi.
Prinsip RSA adalah: bahwa kita bisa mencari 3 bilangan: n, e, dan d sedemikian hingga relasi ini terpenuhi.
Jika diketahui e dan n, kita tidak bisa dengan mudah mencari tahu nilai d. Dalam RSA: public key adalah n dan e, sedangkan private key adalah d dan n.
Saya tidak akan menjelaskan secara matematis bagaimana menghasilkan key RSA ini. Penjelasannya bisa dibaca di Wikipedia, tapi ada beberapa hal dasar yang perlu diketahui:
- n adalah perkalian dari dua buah bilangan prima p dan q.
- Jika kita bisa memfaktorkan n, maka kita bisa mencari nilai private key.
- Saat ini tidak ada algoritma efisien untuk memfaktorkan n
Mari kita coba hasilkan key RSA yang kecil . openssl minimum bisa menghasilkan key sangat kecil, sampai 16 bit, tapi tidak bisa melakukan enkripsi dengan key 16 bit karena adanya pengecekan security ekstra (nilai e > n). Jadi untuk contoh ini saya gunakan ukuran key 32 bit:
openssl genrsa -out private.pem 32
Nanti kita akan mendapatkan key yang sangat kecil dalam format base64 , seperti ini.
-----BEGIN RSA PRIVATE KEY----- MCwCAQACBQDLlcMZAgMBAAECBQCZk2iBAgMA7bsCAwDbOwICcwcCAjUFAgJMcw==
-----END RSA PRIVATE KEY-----
Ini hanya contoh, ketika dijalankan ulang, perintah ini akan menghasilkan key baru. Karena hanya 32 bit, ada kemungkinan key yang dihasilkan bisa sama.
Catatan penting: RSA key yang disarankan saat ini adalah 2048 bit atau lebih. Penggunaan key 32 bit di sini hanya untuk penjelasan, supaya mudah diikuti dan dihitung manual.
Kita bisa mendapatkan public keynya dengan cara seperti ini:
openssl rsa -in private.pem -pubout -out public.pem
Contoh hasilnya seperti ini:
-----BEGIN PUBLIC KEY-----
MCAwDQYJKoZIhvcNAQEBBQADDwAwDAIFAMuVwxkCAwEAAQ==
-----END PUBLIC KEY-----
Di dasar teori RSA kita diberi tahu tentang bilangan p, q, N dsb. Tapi kenapa disimpan dalam bentuk teks seperti itu? Salah satu format standar penyimpanan key adalah PEM, di mana data diencode dengan menggunakan ASN.1. Mungkin lain kali saya akan membahas detail berbagai format key, certificate, dsb, tapi untuk saat ini saya akan membahas hal praktisnya saja.
Format ASN1 bisa diparse dengan asn1parse seperti ini:
$ cat private.pem | openssl asn1parse
0:d=0 hl=2 l= 44 cons: SEQUENCE
2:d=1 hl=2 l= 1 prim: INTEGER :00
5:d=1 hl=2 l= 5 prim: INTEGER :CB95C319
12:d=1 hl=2 l= 3 prim: INTEGER :010001
17:d=1 hl=2 l= 5 prim: INTEGER :99936881
24:d=1 hl=2 l= 3 prim: INTEGER :EDBB
29:d=1 hl=2 l= 3 prim: INTEGER :DB3B
34:d=1 hl=2 l= 2 prim: INTEGER :7307
38:d=1 hl=2 l= 2 prim: INTEGER :3505
42:d=1 hl=2 l= 2 prim: INTEGER :4C73
Tapi itu sulit dimengerti, kita bisa mengekstrak berbagai nilai dengan lebih jelas seperti ini:
$ cat private.pem | openssl rsa -text RSA Private-Key: (32 bit, 2 primes) modulus: 3415589657 (0xcb95c319) publicExponent: 65537 (0x10001) privateExponent: 2576574593 (0x99936881) prime1: 60859 (0xedbb) prime2: 56123 (0xdb3b) exponent1: 29447 (0x7307) exponent2: 13573 (0x3505) coefficient: 19571 (0x4c73) writing RSA key -----BEGIN RSA PRIVATE KEY----- MCwCAQACBQDLlcMZAgMBAAECBQCZk2iBAgMA7bsCAwDbOwICcwcCAjUFAgJMcw== -----END RSA PRIVATE KEY-----
Di sana bisa terlihat bahwa n (modulus) adalah 34155896571. Nilai e (public exponent) adalah 65537 dan nilai d (private exponent) adalah 2576574593. Dua bilangan prima p dan q ada di prime1 (p=60859) dan prime2 (q=56123). Nilai exponent1 adalah d mod (p-1) dan exponent2 adalah d mod (q-1) sedangkan coefficient adalah (inverse of q) mod p.
Berbagai nilai disimpan untuk memudahkan perhitungan walaupun redundan. Contoh: nilai exponent 1 adalah d mod (p-1) = 2576574593 mod (60859-1) = 29447, jadi sebenarnya jika exponent1 tidak disimpan, bisa dihitung dari nilai p dan q yang sudah ada. Bahkan untuk enkripsi/dekripsi saja, nilai d, e dan n sudah cukup. Nilai redundan ini kadang memudahkan atau mempercepat perhitungan tertentu dan ini merupakan hal standar yang diatur di RFC 3447 (Section A.1.2 RSA Private Key Syntax).
Supaya lengkap, ini isinya jika kita periksa isi public key di atas:
$ cat public.pem | openssl rsa -pubin -text
Public-Key: (32 bit)
Modulus: 3415589657 (0xcb95c319)
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MCAwDQYJKoZIhvcNAQEBBQADDwAwDAIFAMuVwxkCAwEAAQ==
-----END PUBLIC KEY-----
Sekarang kita bisa mengenkrip sebuah kata pendek. Contohnya saya buat file ini (parameter -n agar tidak ada karakter \n di file hasil):
echo -n Helo > input.txt
Atau jika dilihat representasi heksadesimalnya:
hexdump -C input.txt
00000000 48 65 6c 6f |Helo|
00000004
Atau dalam bentuk bilangan: 0x48656c6f
Sekarang inputnya kita enkrip
cat input.txt | openssl rsautl -encrypt -pubin -raw -inkey public.pem >message.encrypted
Karena key sangat kecil (32 bit) kita hanya bisa mengenkrip data yang sangat kecil. Di sini saya memakai format “raw” (dengan adanya parameter -raw), alias tanpa padding sama sekali dan hasil datanya adalah “mentah” apa adanya tanpa header apapun. Sekarang mari kita lihat hasilnya:
$ hexdump -C message.encrypted
00000000 1c fb ca d5 |….|
00000004
Hanya 4 byte (32 bit), atau dalam bentuk bilangan adalah: 0x1cfbcad5 atau 486263509 desimal. Rumus enkripsi RSA adalah:
Sekarang kita bisa menghitung manual apakah benar enkripsi Helo (0x48656c6f) adalah 0x1cfbcad5. Untuk mudahnya kita gunakan Python . Di Python operator dua asterisk (**) adalah perpangkatan dan persen(%) adalah modulus :
>> print(hex(0x48656c6f**(65537) % (3415589657)))
0x1cfbcad5L
Hasilnya sesuai harapan, sama dengan hasil enkripsi openssl. Operasi perpangkatan lalu mod akan butuh waktu lama jika dilakukan pada bilangan yang lebih besar. Python punya fungsi built in untuk perpangkatan dengan modulus, seperti ini:
>> print(hex(pow(0x48656c6f, 65537, 3415589657)))
0x1cfbcad5L
Sekarang mari kita dekrip kembali message.encrypted
cat message.encrypted | openssl rsautl -decrypt -raw -inkey private.pem > result.txt
Bisa dicek bahwa output result.txt adalah Helo. Kita juga bisa mendekrip secara manual dengan Python
Atau dalam kode Python:
>> print(hex(pow(0x1cfbcad5, 2576574593, 3415589657)))
0x48656c6fL
Atau jika ingin dalam bentuk teks:
print(bytearray.fromhex("%08x" % (pow(0x1cfbcad5, 2576574593, 3415589657))))
Helo
Demikian artikel perkenalan RSA yang praktis. Dalam artikel ini belum dibahas mengenai hal yang penting yaitu: padding, proteksi password (key di atas tidak dienkrip) dan beberapa kelemahan RSA di kasus tertentu. Hal-hal tersebut rencananya akan saya bahas di tulisan lain.