Cryptology - FME (UPC)
Jorge L. Villar, 2024
Describe a variant of ElGamal encryption in which the encryption function is Enc(pk,m)=(grm,yr) instead of the original one Enc(pk,m)=(gr,yrm). Show how can it be used to encrypt a message once for two different recipients as Enc2(pkA,pkB,m).
The so-called linear encryption scheme is a variant of ElGamal encryption scheme with a “double” secret key (x1,x2) and public key (param,y1=gx1,y2=gx2) such that Enc(pk,m)=(gr1+r2m,y1r1,y2r2).
Describe the decryption function.
Show that given only one of the secret values (say x2) one can transform the ciphertext into a modified ElGamal ciphertext (described in the previous exercise) for the public key y1 and the same message m.
Observe that, in this way, linear encryption is a two-party ElGamal encryption: A ciphertext can only be decrypted with the collaboration of two parties A and B, holding each one one of the two secret values.
Using plain RSA to send exactly the same message to several users can be completely insecure. Show how a message m<2λ can be efficiently recovered from three independent encryptions with public exponent e=3 using public keys n1, n2, n3.
Hint: Use the Chinese Remainder Theorem with the product n=n1n2n3.
Why cannot you encrypt very short messages with plain RSA and small public exponent?
Show that if c is an encryption of m∈Zn using Paillier encryption scheme with g=n+1, then for any u∈Zn, cu mod n2 is an encryption of mu mod n.
Use this to find a way to compute the encryption of P(u) mod n, given u∈Zn and the ciphertexts c0,...,cd encrypting the coefficients of the polynomial P of degree at most d.
Show how to compute the tally in a electronic voting scheme in which every voter generates its encrypted ballot as an ElGamal encryption of the generator g (for “yes”), or 1 (for “no”).
Hint: If the number of voters n is limited, the discrete logarithm of gx for 0≤x≤n can be efficiently computed with a precomputed table.
Discuss why the random number k generated in the DSA signing algorithm is critical for the security of the scheme. In particular, show that if k is leaked for a particular message / signature pair, then the attacker learns the secret signing key.
Similarly, the same value of k cannot be used for more than one signature. Show that from two message / signature pairs generated with the same k, an attacker learns k and the secret signing key. Show that the same attack still works if the value of k comes from a counter (and then k2=k1+1 for two consecutive DSA signatures).
Hint: In the second part, consider the linear system of equations obtained from kt-xr = H(m), for a message m, the corresponding DSA signature (r,t), and the secret key x.
Consider the following 3-moves identification protocol based on RSA: A prover P proves its knowledge of x such that xe=y mod n, where the public RSA key (n,e) and y are common inputs given to both parties. First, P sends the commitment a=re mod n to V, for a random r. Next, V sends a random challenge c to P. Then, P answers the challenge by sending t=rxc mod n. Finally, V verifies whether te = ayc mod n.
Describe a Schnorr-like signature scheme based on the previous identification scheme.
Describe the information needed by a user A to send a message to another user B with confidentiality guarantees, assuming that A and B uses two different certification authorities CAA and CAB, and these authorities depend on a common root certification authority CAroot. Specify all the public keys and the necessary fields in every certificate, and indicate all the verification operations performed by A before sending an encrypted message to B.