Bagian 7.7 Sage

Misalkan Alice ingin mengirimkan pesan rahasia kepada Bob, disertai verifikasi pesan (juga dikenal sebagai pesan dengan tanda tangan digital). Kita mulai dengan menyusun pasangan kunci (privat dan publik) bagi Alice maupun Bob. Pertama-tama, kita memerlukan dua bilangan prima besar untuk masing-masing orang beserta hasil kalinya. Dalam praktik, nilai \(n\) akan memiliki ratusan digit, bukan hanya \(21\) digit seperti yang kita gunakan di sini.

p_a = next_prime(10^10)
q_a = next_prime(p_a)
p_b = next_prime((3/2)*10^10)
q_b = next_prime(p_b)
n_a = p_a * q_a
n_b = p_b * q_b
n_a, n_b

(100000000520000000627, 225000000300000000091)

Secara komputasional, nilai fungsi \(\phi\) Euler untuk hasil kali bilangan prima \(pq\) dapat diperoleh dari \((p-1)(q-1)\text{,}\) tetapi kita juga dapat menggunakan fungsi bawaan Sage.

m_a = euler_phi(n_a)
m_b = euler_phi(n_b)
m_a, m_b

(100000000500000000576, 225000000270000000072)

Sekarang kita dapat membuat eksponen enkripsi dan dekripsi. Kita memilih eksponen enkripsi berupa bilangan (kecil) yang relatif prima terhadap nilai \(m\text{.}\) Dengan Sage, kita dapat memfaktorkan \(m\) dengan cepat untuk membantu memilih nilai ini. Dalam praktik, kita tidak ingin melakukan perhitungan tersebut untuk nilai \(m\) yang besar, sehingga lebih mudah memilih nilai secara “acak” dan memeriksa nilai pertama yang relatif prima terhadap \(m\text{.}\) Eksponen dekripsi merupakan invers perkalian, modulo \(m\text{,}\) dari eksponen enkripsi. Jika Anda menyusun eksponen enkripsi yang tidak sesuai (tidak relatif prima terhadap \(m\)), perhitungan invers perkalian akan gagal (dan Sage akan memberi tahu Anda). Kita melakukan hal ini dua kali — untuk Alice dan Bob.

factor(m_a)

2^6 * 3 * 11 * 17 * 131 * 521 * 73259 * 557041

E_a = 5*23
D_a = inverse_mod(E_a, m_a)
D_a

20869565321739130555

factor(m_b)

2^3 * 3^4 * 107 * 1298027 * 2500000001

E_b = 7*29
D_b = inverse_mod(E_b, m_b)
D_b

24384236482463054195

Pada tahap ini, masing-masing orang mengumumkan nilai \(n\) dan \(E\text{,}\) sambil menjaga \(D\) tetap sangat privat dan aman. Dalam praktik, \(D\) pada diska keras pengguna harus dilindungi dengan kata sandi yang hanya diketahui pemiliknya. Demi keamanan yang lebih tinggi, seseorang mungkin hanya menyimpan dua salinan kunci privat: satu pada perangkat memori USB yang selalu dibawanya, dan satu cadangan dalam kotak penyimpanan aman. Setiap kali menggunakan \(D\text{,}\) orang tersebut harus memasukkan kata sandi. Nilai \(m\) dapat dibuang. Sebagai catatan, berikut semua kuncinya:

print("Alice's public key, n:", n_a, "E:", E_a)

Alice's public key, n: 100000000520000000627 E: 115

print("Alice's private key, D:", D_a)

Alice's private key, D: 20869565321739130555

print("Bob's public key, n:", n_b, "E:", E_b)

Bob's public key, n: 225000000300000000091 E: 203

print("Bob's private key, D:", D_b)

Bob's private key, D: 24384236482463054195

Alice akan menyusun pesan berupa kata bahasa Inggris yang terdiri atas empat huruf. Dari keempat huruf ini, kita akan menyusun satu bilangan untuk mewakili pesan dalam bentuk yang dapat digunakan oleh algoritma RSA. Fungsi ord() mengubah satu huruf menjadi nilai kode ASCII-nya, yaitu bilangan antara 0 dan 127. Jika bilangan-bilangan ini digunakan sebagai “digit” modulo 128, kita dapat memastikan bahwa kata empat huruf milik Alice dienkripsi menjadi bilangan bulat yang kurang dari \(128^4=268,435,456\text{.}\) Nilai maksimum tepatnya tidaklah penting, selama lebih kecil daripada nilai \(n\text{,}\) karena semua aritmetika selanjutnya dilakukan modulo \(n\text{.}\) Kita memilih sebuah kata populer yang terdiri atas empat huruf, mengubahnya menjadi ASCII dalam bentuk “digit” dengan komprehensi senarai, lalu menyusun bilangan bulat dari digit-digit tersebut menggunakan basis yang tepat. Perhatikan bahwa kita dapat memperlakukan kata sebagai senarai dan digit pertama pada senarai berada di tempat “satuan” (kita mengatakan bahwa senarai tersebut berurutan “little-endian”).

word = 'Sage'
digits = [ord(letter) for letter in word]
digits

[83, 97, 103, 101]

message = ZZ(digits, 128)
message

213512403

Mula-mula, Alice menandatangani pesannya untuk menyediakan verifikasi pesan. Untuk itu, ia menggunakan kunci privatnya, karena tindakan ini seharusnya hanya dapat dilakukan olehnya.

signed = power_mod(message, D_a, n_a)
signed

47838774644892618423

Kemudian Alice mengenkripsi pesannya agar hanya Bob yang dapat membacanya. Untuk itu, ia menggunakan kunci publik Bob. Perhatikan bahwa ia bahkan tidak harus mengenal Bob — misalnya, ia dapat memperoleh kunci publik Bob dari situs webnya, atau mungkin Bob mengumumkan kunci publiknya dalam iklan di New York Times.

encrypted = power_mod(signed, E_b, n_b)
encrypted

111866209291209840488

Komunikasi Alice sekarang siap dikirim melalui jaringan komunikasi apa pun, betapapun tidak amannya jaringan tersebut, dan berapa pun banyaknya penyadap yang mungkin memantau jaringan itu.

Sekarang anggap bahwa nilai encrypted telah sampai kepada Bob. Ingat bahwa Bob mungkin tidak mengenal Alice, dan belum tentu percaya bahwa apa yang diterimanya benar-benar berasal dari Alice. Seorang lawan dapat mencoba membingungkan Bob dengan mengirimkan pesan yang mengaku berasal dari Alice. Pertama, Bob harus membuka enkripsi yang dibuat oleh Alice. Hanya Bob, sebagai penerima yang dituju, yang seharusnya dapat melakukan tindakan ini. Ia melakukannya dengan menggunakan kunci privat yang hanya diketahui olehnya dan telah dijaganya dengan aman.

decrypted = power_mod(encrypted, D_b, n_b)
decrypted

47838774644892618423

Pada tahap ini, hasil tersebut belum banyak berarti bagi Bob. Siapa pun dapat mengirimkan pesan terenkripsi kepadanya. Namun, pesan ini telah ditandatangani oleh Alice. Mari kita buka tanda tangan pesannya. Perhatikan bahwa langkah ini menggunakan kunci publik Alice. Bob tidak perlu mengenal Alice — misalnya, ia dapat memperoleh kunci Alice dari situs webnya, atau mungkin Alice mengumumkan kunci publiknya dalam iklan di New York Times.

received = power_mod(decrypted, E_a, n_a)
received

213512403

Bob perlu mengubah representasi bilangan bulat ini kembali menjadi kata yang terdiri atas huruf. Fungsi chr() mengubah nilai kode ASCII menjadi huruf, dan kita menggunakan komprehensi senarai untuk melakukannya berulang kali.

digits = received.digits(base=128)
letters = [chr(ascii) for ascii in digits]
letters

['S', 'a', 'g', 'e']

Jika menginginkan hasil yang sedikit lebih mudah dikenali, kita dapat menggabungkan huruf-huruf tersebut menjadi sebuah untai.

''.join(letters)

'Sage'

Bob senang memperoleh pesan yang begitu informatif dari Alice. Apa yang akan terjadi jika seorang penyamar mengirimkan pesan yang seolah-olah berasal dari Alice, atau jika seorang lawan menyadap pesan asli Alice lalu menggantinya dengan pesan yang telah diubah? (Kasus terakhir dikenal sebagai serangan “man-in-the-middle”.)

Dalam kedua kasus tersebut, pihak jahat tidak akan mampu meniru tindakan pertama Alice — menandatangani pesannya. Jika seorang lawan entah bagaimana menandatangani pesan itu atau mengubahnya, langkah ketika Bob membuka tanda tangannya akan menghasilkan data yang sama sekali tidak bermakna. (Cobalah!) Karena Bob menerima kata yang sah dengan kapitalisasi yang tepat, ia yakin bahwa pesan yang tanda tangannya dibuka sama dengan pesan yang ditandatangani Alice. Dalam praktik, jika Alice mengirimkan beberapa ratus kata sebagai pesannya, peluang bahwa pesan palsu akan menghasilkan teks yang koheren setelah tanda tangannya dibuka sangatlah kecil.

Apa yang telah kita peragakan?

Tentu saja, tanpa membuat kunci baru, Anda dapat menukar peran Alice dan Bob. Jika Carol membuat sepasang kunci, ia dapat berkomunikasi dengan Alice maupun Bob dengan cara yang sama.

Jika Anda ingin menggunakan enkripsi kunci publik RSA secara serius, pelajarilah perangkat lunak sumber terbuka GNU Privacy Guard, yang juga dikenal sebagai GPG dan tersedia secara bebas di www.gnupg.org/. Perhatikan bahwa masuk akal untuk hanya menggunakan program enkripsi yang memungkinkan Anda memeriksa kode sumbernya.