Public Key Encryption & Signatures Flashcards

1
Q

Argue the security of Goldwasser Micali Encryption.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the biggest issue with Goldwasser Micali encryption?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain ElGamal Encryption

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Explain ElGamal decryption

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Argue the security of ElGamal.

A

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

not IND CCA secure as it is malleable: multiplicitive homomporphic

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Argue the security of Paillier encrypion

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is OAEP?

A

Optimized Asymmetric Encryption Padding

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

How does OAEP work?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does KEM/DEM stand for?

A

Key Encapsulation Mechanism / Data encapsulation Mechanism.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

How does KEM/DEM work?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Argue the security of KEM and DEM.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Explain how RSA-KEM works.

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Argue the security of RSA-KEM

A

It is IND-CCA secure under ROM.

17
Q

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

A

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

18
Q

Explain how RSA-FDH works.

A

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.

19
Q

Argue the security of the RSA-FDH

A

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.

20
Q

What does RSA-PSS stand for?

A

RSA Probabilisitc Signature Scheme

21
Q

Breifly explain how RSA PSS works.

A

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)

22
Q

What are the largest concerns of RSA based signatures?

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

What does DSA stand for?

A

Digital Signature Algorithm.

24
Q

On what asymmetric scheme is DSA based?

25
Analyse the speed of DSA (compared to RSA based signatures).
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.
26
How does EC-DSA compare to DSA or RSA?
EC-DSA still slower than RSA. But, Key Size is smaller and implementation is easier for EC-DSA.
27
Explain how EC-DSA works.
* 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
28