RSA (Cryptosystem)

Dodi Pran March 29, 2019

What is RSA Cryptography?

RSA adalah salah satu Public-key pertama (asimetris) cryptosystems dan banyak digunakan untuk transmisi data yang aman. RSA singkatan dari Rivest-Shamir-Adleman, huruf awal dari nama belakang penciptanya. Asimetri ini didasarkan pada kesulitan praktis dari faktorisasi produk dari dua bilangan prima besar, yang "masalah Factoring ".

Berikut adalah cara kerja key generation:

Pilih dua bilangan prima yang berbeda, p, dan q.
Compute n = p * q. n digunakan sebagai modulus untuk kedua kunci public dan private. Panjangnya, biasanya dinyatakan dalam bit, adalah panjang kunci.
Compute λ (n) = least_common_multiple (p − 1, q − 1). Nilai ini bersifat private.
Pilih bilangan bulat e sedemikian rupa sehingga 1 < e < λ (n), e dan λ (n) adalah coprime.
Tentukan d dari d * e ≡ 1 (mod λ (n)).

e dilepaskan sebagai eksponen public key.
d disimpan sebagai eksponen private key.

Key pair
public key: (e, n)
private key: (d, n)

Saat ini, ukuran standar untuk RSA Key adalah sebagai berikut:

512 bits - Low-strength key
1024 bits - Medium-strength key
2048 bits - High-strength key
4096 bits - Very high-strength key

Misalkan Bob ingin mengirim informasi ke Alice. Jika mereka memutuskan untuk menggunakan RSA, Bob harus tahu Public key Alice untuk mengenkripsi pesan dan Alice harus menggunakan kunci pribadinya untuk mendekripsi pesan. Untuk memungkinkan Bob mengirimkan pesan terenkripsi, Alice mentransmisikan kunci publik (n, e) ke Bob melalui saluran yang dapat diandalkan (tidak selalu rahasia). Kunci privat Alice (d) tidak pernah didistribusikan.

Mari kita coba untuk menghasilkan Key pair yang sangat sederhana:

1. p = 61 dan q = 53

2. n = 61 * 53 = 3233

3. λ(n) = lcm(p-1, q-1) = lcm(60, 52) = 780

4. e = 17 (1 < e < λ(n), e dan λ(n) adalah coprime)

5. d = 413 (d * e mod λ(n) = 1)

public key: (n = 3233, e = 17)

private key: (n = 3233, d = 413)

Kita menghasilkan Key pair. Kita membutuhkan Public key (n, e) untuk mengenkripsi plaintext. Mari kita tetapkan plaintext ke m dan ciphertext ke c; kemudian ciphertext akan menjadi:

c = m ^ e mod n

Misalnya, jika plaintext m = 65, maka:

c (m) = 65 ^ 17 mod 3233 = 2790

Untuk mendekripsi ciphertext dengan kunci privat (n, d), kita harus menggunakan ini:

m (c) = c ^ d mod n = 2790 ^ 413 mod 3233 = 65