Asymmetric Encryption

Question 1

What are the pros and cons of asymettric encryption?

Answer 1

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

Question 2

What are some characteristics of asymmetric encryption?

Answer 2

• 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

Question 3

What is the weakest point for asymmetric encryption? whatt cand be done to solve that issue?

Answer 3

The weakest point is the public key (Integrity/ Authenticity problem), can be solved with digital signatures

Question 4

What is the security property for the chosen-plaintext attack security?

Answer 4

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

Question 5

How does hybrid encryption work?

Answer 5

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.

Question 6

What is the encryption and decryption formula for Textbook RSA?

Answer 6

Enc: c=m^e (mod N)
Dec: m = c^d (mod N)

Question 7

How do you generate keys for textbook RSA? given p and q

Answer 7

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)

Question 8

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.

Answer 8

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)

Question 9

Is textbook RSA Secure?

Answer 9

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

Question 10

Why is textbook RSA flawed? What are the attacks?

Answer 10

1. 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.
2. 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.
3. 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)
4. 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)
5. 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

Question 11

How does introducing padding to textbook RSA help?

Answer 11

• Pad message to modulus length
• Introduce randomization (Makes it not deterministic)
• Create structure (detects mangling)

Question 12

What are the 4 pillars of public key encryption?

Answer 12

• Key distribution must be authentic
• c indistinguishable from random (CPA-secure)
• Must be randomized
• Efficient with hybrid encryption

Question 13

What are the three factors that lead to the attacks on textbook RSA?

Answer 13

1. Plaintext is too short, not using full modulus length
2. Textbook RSA is not random, need to infuse with fresh random bits
3. RSA is homophorbic, you can manipulate ciphertexts

Question 14

What is the structure of RSA with PKCS #1 v1.5 Padding? What are the benefits?

Answer 14

(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)

Question 15

Briefly describe RSA OAEP encryption and decryption

Answer 15

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

Question 16

Briefly explain blinding with multiplication and exponentiation

Answer 16

-> 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

Question 17

How do you generate keys for elgamal encryption?

Answer 17

• 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)

Question 18

How do you encrypt and decrypt with elgamal encryption?

Answer 18

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)

Question 19

How do you prove the correctness of El Gamal?

Answer 19

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

Question 20

Given
p = 2357
g = 2 of (Z_2357)*
x = 1751
m= 2035
y = 1520

Calculate the encryption and decryption using elgamal

Answer 20

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)

Question 21

How does El Gamal encryption employ forms of blinding?

Answer 21

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

Question 22

Why is El Gamal encryption CPA Secure?

Answer 22

• 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

Question 23

With El Gamal encryption it is critical to use different y in each encryption. Why?

Answer 23

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)

Question 24

Compare between RSA and El Gamal encryption

Answer 24

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

Question 25

Parameters:
p = 1000033; q = 1000037 e = 1999
Create a key generation function KeyGenRSA() to generate an RSA keypair and outputs: pk = (N, e), sk = (N, d) Establish two functions, RSAencrypt(pk, m) and RSAdecrypt(sk, c)
Encrypt m = 1337 and perform the decryption on the ciphertext to convince yourself of
correctness.

Answer 25

from sympy import mod_inverse
p = 1000033;
q = 1000037;
e = 1999;
N = p * q;
def KeyGenRSA():
phi_N = (p-1) * (q-1);
d = mod_inverse(e, phi_N);
print(d)
pk = (N, e);
sk = (N, d);
return pk, sk;
def RSAencrypt(pk, m):
N, e = pk
c = power_mod(m, e, N)
return c;
def RSAdecrypt(sk, c):
N, d = sk
print (d)
x = power_mod(c, d, N)
return x;
pk, sk = KeyGenRSA()
m = 1337;
c = RSAencrypt(pk, m);
m1 = RSAdecrypt(sk, c)
print(c)
print(m1)

Question 26

Which statements are true about public key encryption?
The private key sk must be kept confidential
The public key can be distributed widely.
The private key can be computed from the public key.
The public key pk should only be distributed to intended communication partners.
It does not matter if an adversary can intercept and exchange a public key.

Answer 26

→ The private key sk must be confidential
→ The public key can be distributed widely
Correct:
Private key must be kept confidential.
The public key can be distributed widely, but must be distributed with integrity. thus the statement “It does not matter if an adversary can intercept and exchange a public key” is wrong.
It is intractable to compute the private key from the public key.

Question 27

What are consequences of security against chosen-plaintext attacks?
-> Deterministic encryption is insecure.

-> Ciphertexts must be randomized.

-> Each message can only be encrypted one.

-> The adversary cannot discern a single bit of information to distinguish between the two possible cipher texts.

Answer 27

→ Deterministic encryption is insecure
→ Ciphertexts must be randomised
→ The adversary cannot discern a single bit of information to distinguish between the two possible cipher texts.
Key takeaway is that all public-key encryption schemes seeking to be CPA secure must be randomised. CPA security yields semantic security, that is, that the adversary cannot discern any information to give him an advantage.

Question 28

We are establishing an RSA encryption system. Given a key generation with a composite modulus of N=pq=67591 with primes p=257 and q=263, compute the corresponding private key exponent d for the public exponent e:
e=31
What is the private exponent d?

Answer 28

28127

from sympy import mod_inverse
N = 67591
p = 257
q = 263
e =31
phi_N = (p-1) * (q-1)
d = mod_inverse(e, phi_N)
print(d)

Question 29

How secure is the textbook RSA crypto system?

Answer 29

→ Textbook RSA is not secure at all and not even a proper encryption.

Question 30

How secure is an RSA system in which multiple users use the same modulus N?

Answer 30

→ The system is not secure and subject to the common modulus attack. An adversary can compute the group order.

Question 31

We are considering the RSA OAEP padding. Which of the following statements is correct?

-> OAEP asks the user to choose a fresh random number as input.

-> The padding consists of 16 bits encoding the number 2.

-> The OAEP padding is like a Feistel network with two hash functions and bitwise XOR.

-> The padding consists of all zeros (0) with fixed length.

-> The randomness can be recovered in the decryption by XORing the hash of the first cipher text part with the second one.

Answer 31

-> OAEP asks the user to choose a fresh random number as input.
-> The OAEP padding is like a Feistel network with two hash functions and bitwise XOR.
-> The padding consists of all zeros (0) with fixed length.
-> The randomness can be recovered in the decryption by XORing the hash of the first cipher text part with the second one.

Question 32

During an El Gamal encryption, which number-theoretic blinding principles are used to hide the plaintext?
->The plaintext is multiplied with a random factor.

->The blinding is achieved by the discrete logarithm problem.

->An exponentiation of a generator with a random exponent creates a random blinding.

-> The blinding is rooted in drawing the e-th root

Answer 32

-> The plaintext is multiplied with a random factor.

-> An exponentiation of a generator with a random exponent creates a random blinding
.
Correct. The blinding is achieved by two operations, exponentiation with a random exponent and multiplication with a random group element.