What are the pros and cons of asymettric encryption?
Pros
-No preshared secret
- Keys independent of sender
- Anyone who wants to encrypt to Alice can do so
- Only a single private key to keep secret
Cons
- 2-3 orders of magnitude slower than symmetric
-No data orgin authentication or integrity
- risk of impersonation attacks
What are some characteristics of asymmetric encryption?
- Goal: confidentiality
- Keep private key sk absolutely secret.
- Public key pk is inadvertently public. (also known by the adversary)
- The private key sk cannot be deduced from pk.
- Publish pk by distributing it with integrity
What is the weakest point for asymmetric encryption? whatt cand be done to solve that issue?
The weakest point is the public key (Integrity/ Authenticity problem), can be solved with digital signatures
What is the security property for the chosen-plaintext attack security?
Adversary gets the public key so he can encrypt and also gets access to the encryption routine which means the adversary can do arbitrary encryptions
the adversary can choose two arbitrary messages
we are encrypting one of the two messages and giving it back to the adversary The adversary has to decide which of the ones we encrypted in the ciphertext
How does hybrid encryption work?
The disadvantage of symmetric encryption is that you need a pre-shared secret key and with asymmetric encryption the disadvantage is that it is highly inefficient
Two primitives involved here:
one asymmetric enc scheme under some public key to get the benefits of key distribution
one symmetric cipher which takes the bits string as the key as input
We have the asymmetric encryption scheme setup with its key material. We chose an ephemeral random symmetric key. We encrypt the symmetric key with the asymmetric encryption scheme. We use the symmetric cipher with the ephemeral symmetric key to encrypt the plaintext message.
Correct. The freshly generated random symmetric key in encrypted with the asymmetric encryption. The Symmetric cipher encrypts the plaintext.
What is the encryption and decryption formula for Textbook RSA?
Enc: c=m^e (mod N)
Dec: m = c^d (mod N)
How do you generate keys for textbook RSA? given p and q
Compute
N = p.q
phi(N) = (p-1) . (q-1)
choose a random integer e that gcd(e, phi(N)) = 1
compute e’s inverse d: d.e = 1 (mod phi(N))
Output:
Pk = (N, e)
Sk = (N, d)
Given
p = 2357
q = 2551
e = 3674911
m = 5234673
find the RSA private key and secret key. Perform textbook RSA Encryption and check if its correct.
phi_n = 6007800
d = 422191
c = 3650502
m = 5234673
from sympy import mod_inverse
p = 2357
q = 2551
e = 3674911
m = 5234673
N = p * q
phi_n = (p-1) * (q-1)
print(phi_n)
d = mod_inverse(e, phi_n)
print(d)
c = (me) % N
m1 = (cd)% N
print(c)
print(m1)
Is textbook RSA Secure?
Textbook RSA is not secure at all and not even a proper encryption. Why? Its not an encryption scheme its a Pseudo-Random Trapdoor Permutation
Why is textbook RSA flawed? What are the attacks?
- Encrypting with small e
If the modulus is small, the cube of the message might be smaller than the modulus size, which means this operation doesnt wrap around the modulus. - Common modulus attack
Using same modulus is a really bad idea
Whenever you have the modulus and a keypair, you can break the entire system
We know that the public and private exponent are multiplicative inverses of one another, intimately related once you a have a keypair and N you have enough information to calculate the group order. - Mangling Ciphertext
RSA is homomorphic: if i multiply two ciphertexts together, im getting an encryption of the two plaintext that were encrypted
as an adversary, I could invent any multiplier, encrypt it and multiply the users ciphertext and this will increase the bid(mangle the ciphertext) - Small Decryption exponent
If the decryption exponent (d) is less than N^(0.3) one can compute d from e and N so choose d large enough d> N^(1/2) - RSA itself is deterministic
Cannot fulfil CPA security because if you’re encrypting the same message twice, you’re raising the same message to the same public exponent which leads to the same ciphertext. So an adversary encrypt two ciphertexts and check
How does introducing padding to textbook RSA help?
- Pad message to modulus length
- Introduce randomization (Makes it not deterministic)
- Create structure (detects mangling)
What are the 4 pillars of public key encryption?
- Key distribution must be authentic
- c indistinguishable from random (CPA-secure)
- Must be randomized
- Efficient with hybrid encryption
What are the three factors that lead to the attacks on textbook RSA?
- Plaintext is too short, not using full modulus length
- Textbook RSA is not random, need to infuse with fresh random bits
- RSA is homophorbic, you can manipulate ciphertexts
What is the structure of RSA with PKCS #1 v1.5 Padding? What are the benefits?
(2 (16 bit) Random padding r 0 (8 bit) m)^e (mod N)
Benefits
- always be the size of the modulus
- introduces randomness
- creating structure, not homophorbic anymore
(CPA secure)
Briefly describe RSA OAEP encryption and decryption
Encryption:
What we need: Choose random r in {0,1}^; Hash functions G and H; and XOR
we get the message and introduce structure by padding with lots of zeros and get the message m’. We XOR that m’ with G(r) and obtain m1. The final output is m1 || r xor H(m1). We get this and (m1 || r xor H(m1))^e = c
Decryption:
What we need: m1 || r xor H(m1) we get this after we c^d
First we hash m1 and xor it with (r xor H(m1)) to get r. After we get r we do G(r) XOred with m1 to obtain m’ and from that we can obtain m after removing the zero paddings
Briefly explain blinding with multiplication and exponentiation
-> Choose a random g in G. Then g’ = m.g is a random element of g again.
-> Choose a random x in Zq, Then g’ = g^x is a random element of G again
How do you generate keys for elgamal encryption?
- Create a cyclic group G with order q and generator g
- Choose random x in Z_q
Compute h = g^x (mod p)
pk = (G, q, g, h)
sk = (G, q, g, x)
How do you encrypt and decrypt with elgamal encryption?
Encryption:
Given pk = (G, q, g, h) and a message m. Choose random y in Zq.
Ciphertext: (c1 = g^y, c2 =h^y.m)
Decryption:
Given sk = (G, q, g, x) and ciphertext (c1, c2):
m = c2 . (c1^x)^(-1)
How do you prove the correctness of El Gamal?
m = c2 . (c1^x)^(-1)
essentially when you substitute in all the values,
c1 = g^y
c2 =h^y.m
c1 becomes the multiplicative inverse of c2 so it cancels out and were left with the message
Given
p = 2357
g = 2 of (Z_2357)*
x = 1751
m= 2035
y = 1520
Calculate the encryption and decryption using elgamal
p = 2357
g = 2
x = 1751 # private key
h = (g**x)%p
m = 2035
y = 1520
Encryption
c1 = (gy)% p
c2 = ((hy)*m) % p
print(c1)
print(c2)
Decryption
m1 = (c2 * (c1x)(-1)) % p
print(m1)
How does El Gamal encryption employ forms of blinding?
Public information: g, h
if you raise both of these to y we get c1 and g^xy we’re actually employing forms of blinding
g^xy: is a Diffie-Helman key
multiplying m with g^xy is multiplicative blinding
The messages are hidden perfectly based on blinding
Why is El Gamal encryption CPA Secure?
- the ciphertext introduces randomness so the adversaries advantage is negligible
- By using the Diffie-Helman key, we’re using the decisional diffie helman assumption that the adversary cannot distinguish between the actual key we used for the encryption against a random number
- we’re also using the district logarithm assumption that the adversary cannot extract x from h
With El Gamal encryption it is critical to use different y in each encryption. Why?
You can have collisions in two ways:
1. same messages, same outputs
2. C2/C2 = (h^y)m /(h^y)m
you can take the second part of the ciphertexts and divide them which would cancel each other out (division does not mean integers, it means we’re computing multiplicative inverse)
Compare between RSA and El Gamal encryption
RSA is deterministic which means it is insecure against chosen plaintext attacks because the adversary can distinguish which messages have been encrypted
Elgamal has a strong randomization that guarantees blinding
RSA: we have composite modulus groups which means a modulus that is a product of two prime numbers
we need to keep confidential factors and group order efficiency: enc: 1 exp: dec: 1 exp
needs a lot of padding and creating structure
Elgamal: we have prime modulus, gives us the finite field, this gives us advantage, so we now the structure, order is not hidden
it takes an additonal encryption so less efficient
