RSA variant. Let us consider the following variant of the RSA public
RSA variant. Let us consider the following variant of the RSA public
key encryption scheme, named RSA-M1 = (KG1, Enc1, Dec1). The
corresponding key generation and encryption algorithms are detailed
next:
• Key generation KG1(λ)
– Generate two distinct odd primes p and q of same bit-size λ
– Compute N = p · q and ϕ = (p − 1)(q − 1)
– Select a random integer 1 < e < ϕ such that gcd(e, ϕ) = 1
– Compute the unique integer d such that 1 < d < ϕ and
e · d = 1mod ϕ
– The public key is PK = (N, e). The private key is SK =
(N, e, d)
• Encryption Enc1(PK,m) of a message m ∈ Z⋆
N proceeds as follows:
– Generate a random integer r in Z⋆
N
– Compute bm = m · r modN
– Compute c1 = bme modN
– Compute c2 = r−e modN
– Output C = (c1, c2)
(a) Give the corresponding decryption
your decryption algorithm is correct, i.e. given a legitimate key
pair (PK, SK) ← KG1(λ) it holds that Dec1(SK, Enc1(PK,m)) =
m for any admissible plaintext m.
(b) Is the public key encryption scheme RSA-M1 one-way? Justify
your answer.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
