Public Key Encryption & Signatures

Question 1

Argue the security of Goldwasser Micali Encryption.

Answer 1

It is probibilistic, as randomness is introduced with each encryption: IND CPA secure. However, it is malleable, (additive homomorphic) so it is not IND CCA secure.

Question 2

What is the biggest issue with Goldwasser Micali encryption?

Answer 2

Each bit is individually encrypted, meaning large computation time and large cipher texts.

Question 3

Explain ElGamal Encryption

Answer 3

You have public factorization p = sq + 1. And value g = r ^ s mod p for r in Z/pZ.

Private key x from Z/qZ.

Then we can construct public key h = g^x mod p and choose random k from Z/qZ.

c1 = g^k
c2 = m* h^k
c <- (c1, c2)

Question 4

Explain ElGamal decryption

Answer 4

c2/(c1^x) = m.
(write proof on cheatsheet)

Question 5

Argue the security of ElGamal.

Answer 5

IND CPA secure, as random key k makes it a probabilistic scheme.

not IND CCA secure as it is malleable: multiplicitive homomporphic

Question 6

Argue the security of Paillier encrypion

Answer 6

IND CPA, because it is probabilistic. It is not IND CCA secure, as it reamins additive homomorphic.
c1 * c2 = enc( m1 + m2)

Question 7

What is OAEP?

Answer 7

Optimized Asymmetric Encryption Padding

Question 8

What is solved in RSA-OAEP (compared to RSA).

Answer 8

The probabilistic behaviour of OAEP solved the deterministic character of RSA, the padding solves the homomorphic character of RSA.

Question 9

How does OAEP work?

Answer 9

It uses two rounds of feistel to add padding and randomness to the the message. In each round, the f function is a (different) Hashing function. The result is a cipher of the length |m| + pad + |R|.

Question 10

Argue the security of OAEP. And that of RSA-OAEP

Answer 10

In the Random Oracle Model:”OAEP is concidered IND CCA secure if G and H are secure Hash functions.
This is the case for RSA-OAEP.

Question 11

Explain what the Fujisaki-Okamoto Transform does and how it achieves this.

Answer 11

It converts any IND-CPA secure scheme to a IND-CCA secure scheme. It does this by destroying the homomorphism.
Asume encrytion relies on a message and a randomness: E(m, r) then we can replace these with E(m||r , H(m||r) ) which makes homomorphism not possible any more.

Question 12

What does KEM/DEM stand for?

Answer 12

Key Encapsulation Mechanism / Data encapsulation Mechanism.

Question 13

How does KEM/DEM work?

Answer 13

key k is newly generated for every transaction. This key is encapsulated using asymmetric encryption. Then, key k is used to encrypt data m using symetric encryption. These two ciphers are communicated to the second party. Who now can decapsulate the key (k) with its private key and us it to decipher c and obtain m.

Question 14

Argue the security of KEM and DEM.

Answer 14

Given the individual schemes for KEM and DEM are secure, The hybrid system is secure as well. This paradigm is used often in practise.

Question 15

Explain how RSA-KEM works.

Answer 15

We use RSA protocol (public/private key based) to communicate a symmetric key to the other party. Random message x is encrypted using RSA and then the other party can decipher this value for x.
Key value k is obtain (by both parties) by hasing x.

Question 16

Argue the security of RSA-KEM

Answer 16

It is IND-CCA secure under ROM.

Question 17

What does RSA-FDH stand for and what is it’s purpose?

Answer 17

RSA-Full Domain Hash, it is theoretically a secure signature scheme.

Question 18

Explain how RSA-FDH works.

Answer 18

A sender can decrypt the hash of a message using RSA private key, such that it obtains the signature.

The receiver can than **encrypt ** the signature with the public key to match the resulting hash, and to verify it could only have been sent by the sender.

Question 19

Argue the security of the RSA-FDH

Answer 19

It is secure, but only if the codomain of the hash function is equal to the domain of RSA. Otherwise too much risk for collisions. This is often not possible in practise.

Question 20

What does RSA-PSS stand for?

Answer 20

RSA Probabilisitc Signature Scheme

Question 21

Breifly explain how RSA PSS works.

Answer 21

message m is concattenated with r, and hashed to obtain w.
w is converted (short expl. here) to y, which is signed using d (RSA).
signature s can then be verified by “signing” the message again, and see if your results match. (randomness can be reverted as well)

Question 22

What are the largest concerns of RSA based signatures?

Answer 22

• RSA based schemes are costly in terms of signature generation
• RSA based signatures are large,
• RSA might be broken soon

Question 23

What does DSA stand for?

Answer 23

Digital Signature Algorithm.

Question 24

On what asymmetric scheme is DSA based?

Answer 24

ElGamal

Question 25

Analyse the speed of DSA (compared to RSA based signatures).

Answer 25

DSA contains many expensive operations: inverses, exponentials and almost all values need to be reduced (modulo)
This is emphasised by the bit size of DSA, namely 2048 bits, which is the same for RSA.

Question 26

How does EC-DSA compare to DSA or RSA?

Answer 26

EC-DSA still slower than RSA.
But, Key Size is smaller and implementation is easier for EC-DSA.

Question 27

Explain how EC-DSA works.

Answer 27

• Choose a random integer a and point P, a is the secret key
• Compute Q=aP, Q is the public key
• Signing:
• Chose a random number k
• Compute kP = (x 1,y 1)
• Compute s = k -1 [H(M) + ax1 ]
• Signature (x 1,s)
• Verification:
• Compute u 1 = H(M)s -1 and u2 = x1 s-1
• Compute u 1P + u2 Q = (x0,y 0)
• Check x1 = x0 ?

Directly from slides, see how much you can remember xp