Public Key Encryption & Signatures Flashcards
Argue the security of Goldwasser Micali Encryption.
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.
What is the biggest issue with Goldwasser Micali encryption?
Each bit is individually encrypted, meaning large computation time and large cipher texts.
Explain ElGamal Encryption
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)
Explain ElGamal decryption
c2/(c1^x) = m.
(write proof on cheatsheet)
Argue the security of ElGamal.
IND CPA secure, as random key k makes it a probabilistic scheme.
not IND CCA secure as it is malleable: multiplicitive homomporphic
Argue the security of Paillier encrypion
IND CPA, because it is probabilistic. It is not IND CCA secure, as it reamins additive homomorphic.
c1 * c2 = enc( m1 + m2)
What is OAEP?
Optimized Asymmetric Encryption Padding
What is solved in RSA-OAEP (compared to RSA).
The probabilistic behaviour of OAEP solved the deterministic character of RSA, the padding solves the homomorphic character of RSA.
How does OAEP work?
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|.
Argue the security of OAEP. And that of RSA-OAEP
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.
Explain what the Fujisaki-Okamoto Transform does and how it achieves this.
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.
What does KEM/DEM stand for?
Key Encapsulation Mechanism / Data encapsulation Mechanism.
How does KEM/DEM work?
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.
Argue the security of KEM and DEM.
Given the individual schemes for KEM and DEM are secure, The hybrid system is secure as well. This paradigm is used often in practise.
Explain how RSA-KEM works.
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.
Argue the security of RSA-KEM
It is IND-CCA secure under ROM.
What does RSA-FDH stand for and what is it’s purpose?
RSA-Full Domain Hash, it is theoretically a secure signature scheme.
Explain how RSA-FDH works.
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.
Argue the security of the RSA-FDH
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.
What does RSA-PSS stand for?
RSA Probabilisitc Signature Scheme
Breifly explain how RSA PSS works.
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)
What are the largest concerns of RSA based signatures?
- RSA based schemes are costly in terms of signature generation
- RSA based signatures are large,
- RSA might be broken soon
What does DSA stand for?
Digital Signature Algorithm.
On what asymmetric scheme is DSA based?
ElGamal
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.
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.
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
