Search

RSA

Last updated Aug 8, 2022 Edit Source

A form of asymmetric cryptography.

Full name is the Rivest, Shamir, Adelson Algorithm

• Relies on modular arithmetic
• Unfortunately, also really slow :((
• Encryption/decryption are computation-heavy. Ok for occasional communication but too slow for extensive data transfer
• Good for establishing initial secure connection
• Hard to crack because to determine $d$ from $(n, e)$ requires computing factors of $n$ which is a hard problem
• Choose two large primes $p$ and $q$ (1024-bits each)
• Compute $n = pq, z = (p-1)(q-1)$
• Choose $e < n$ that has no common factors with $z$ (commonly 3)
• Choose $d < n$ such that $ed \mod z = 1$
• Public key: $K^+_B=(n,e)$
• Private key: $K^-_B = (n,d)$
• Encrypting is then $encrypt(m) = m^e \mod n$
• Decrypting is then $decrypt(c) = c^d\mod n$

Key exchange can also be performed using RSA

• If Alice and Bob both know the other’s public key, how can they agree on a shared “session” key?
• Alice chooses key $K_S$ and encrypts it with Bob’s public key and Alice’s private key $K_A^-(K_B^+(K_S))$
• Bob decrypt’s the message using his private key and Alice’s public key $K_B^-(K_A^+(K_A^-(K_B^+(K_S)))) = K_S$