Kriptografi RSA Praktis

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.

{\displaystyle (m^{e})^{d}\equiv m{\pmod {n}}}

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:

Private-Key: (32 bit)
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:

 c \equiv m^e \pmod{n}

Sekarang kita bisa menghitung manual apakah benar enkripsi Helo (0x48656c6f) adalah 0x1cfbcad5. Untuk mudahnya kita gunakan Python:

>> 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

{\displaystyle c^{d}\equiv (m^{e})^{d}\equiv m{\pmod {n}}}

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.

Tinggalkan Balasan

This site uses Akismet to reduce spam. Learn how your comment data is processed.