RSA Encryption Flashcards
Advantages of Asymmetric Encryption
- No pre-shared secret
- Key Independent of Sender
- Anyone who wants to encrypt can do so
- Only a single private key to keep secret
Disadvantages of Asymmetric Encryption
- Risk of impersonation attacks
- Runs in order 2/3 slower than symmetric algos
- No authentication or integrity
Chosen Plain Text Attack
Chosen-Plaintext Attack (CPA) Security:
Setup: Create a pair of keys for encryption.
Adversary’s Role: The adversary gets the public key and access to an encryption tool.
Adversary’s Task: Pick any two different messages.
Challenge: A message is randomly chosen from the two and encrypted.
Adversary’s Guess: Try to guess which message was encrypted.
Winning the Game: If the adversary guesses right, they win.
Main Idea: If the adversary can only guess as good as flipping a coin, the encryption is considered secure against this type of attack.
Deterministic Public Key Encryption
Deterministic Public-Key Encryption is a type of encryption that always produces the same ciphertext for a given plaintext and key, regardless of how many times the encryption is performed. Examples include the RSA cryptosystem without padding and block ciphers in ECB mode with a constant initialization vector
Is Deterministic Public Key Encryption Secure?
No deterministic encryption can be CPA-secure.
Public-key encryption must be randomized.
Deterministic encryption schemes cannot achieve semantic security, which is the property that a ciphertext does not reveal any information about the plaintext.
Hybrid Encryption
- Generate a fresh random symmetric key k
- Used the public key pk to encrypt creating c1
- Encrypt the message m with k to produce c2
- Send both encrypted key c1 and message c2 to the receiver.
Advantages of Hybrid Encryption
- Faster than public key encryption
- Eliminates the need for shared key encryption
RSA Assumption
- Basis: RSA’s security relies on the difficulty of factoring large numbers.
- Setup: Setup: RSA parameters (N, e, d) are generated, with d being the inverse of e modulo the totient of N.
- Challenge: An adversary is given N (the modulus), e (the public exponent), and y (a number).
- Goal: The adversary tries to find x such that x^e is congruent to y modulo N.
- Security: RSA is considered secure if no efficient algorithm can solve this for x in a polynomial amount of time. The success of an adversary should be negligible.
RSA Key Generation
Step 1: Choose two large prime numbers, p and q.
Step 2: Calculate N by multiplying p and q.
Step 3: Find the totient of N (represented by φ(N)) as (p-1)(q-1).
Step 4: Select a public exponent e that is coprime with φ(N).
Step 5: Calculate the private exponent d as the multiplicative inverse of e modulo φ(N).
Output: Public key (N, e) and private key (N, d).
Tip: The key length determines how secure the RSA setting will be. Longer keys are typically more secure.
RSA Encryption and Decryption
KeyGen: pk=(N, e), sk=(N, d) ß GenRSA(1 n )
Enc: Given pk=(N, e) and message m:
c = m^e (mod N)
Dec: Given sk=(d, N) and ciphertext c:
m = c^d (mod N)
How Secure is textbook RSA?
Textbook RSA is not secure at all and not even a
proper encryption. There are several reasons:
- Homorphic properties: Ciphertext operations lead to Plaintext alterations
- Lack of Padding
- Deterministic Encryption - Given plaintext will always produce the same ciphertext. Can be exploited in Chosen Plaintext Attacks
RSA’s characteristics as a pseudo-random trapdoor permutation
The slide notes that the only known method to compute the eth root (essentially decrypt without the private key) is by factoring N, which is considered hard.
There is no known reduction to other problems, and there’s evidence suggesting that no such reduction exists, meaning the RSA problem may be intrinsically difficult without factoring N. Essentially, without private exponent the only way to decrypt message is factoring N which is hard in polynomial time.
Common Modulus Attack
Common Modulus Attack in RSA:
- Occurs when RSA pairs use the same modulus N
- Two messages encrypted with different public exponents but same N can be exploited.
- Using modular arithmatic, an attacker can find the original message without the private key.
- Avoid by using unique moduli for each key pair.
Key Point: Never reuse the modulus N in multiple RSA key pairs.
Common Modulus Expanded
The common modulus attack in textbook RSA can occur when the same modulus ( N ) is used with different public exponents. Here’s a simplified explanation of the attack:
- Two public keys have the same modulus N but different exponents e_1 and e_2
- The attacker gets two ciphertexts that are encrypted from the same message m using these public keys.
- With some clever math (the Extended Euclidean Algorithm), the attacker finds two numbers a and b that relate e_1 and e_2.
- These numbers are then used to combine the ciphertexts in a special way to cancel out the exponents and reveal the original message m.
This attack is a reminder that each RSA key pair should have a unique modulus to prevent such vulnerabilities.
What is Padding
Process of adding additional data to the plaintext before encrypting it
