Question

(a) In the Plain RSA encryption scheme, the two primes were chosen to be p=23 and q=17, and the public parameter e=3 was chosen. The sender wants to send the message "HELLO" character by character. Since 'H'is 72 in ASCII, the sender first wants to send the message m=72. Provide a description of the (Gen, Enc, Dec) algorithms in the plain RSA encryption scheme for the above parameters.

(b) For the RSA parameters: primes p=29,q=37, modulus N=p⋅q, how many possible values of the RSA parameter e are there in the range {1,…,ϕ(N)} ?
(c) One of the attacks on Plain RSA involves a sender who encrypts two related messages using the same public key. Formulate an appropriate definition of security ruling out such attacks, and show that any CPA-secure public-key encryption scheme satisfies the definition.

Answer 1

In the Plain RSA encryption scheme with given parameters, we identify the encryption and decryption processes using mathematical operations on the message, modulus, and keys. The number of possible RSA parameters e relates to integers coprime to ϕ(N). A CPA-secure public-key encryption scheme prevents attackers from gaining information even when analysing related ciphertexts encrypted with the same key.

Step-by-step explanation:

The RSA encryption scheme comprises three algorithms: Gen, Enc, and Dec. Utilizing the parameters p=23, q=17, and e=3, the RSA modulus N is calculated as N=p*q, resulting in 23*17=391. The totient ϕ(N) is computed as (p-1)*(q-1), giving 22*16=352. The encryption process for the message m=72 is conducted by calculating the ciphertext c as c = me mod N, resulting in c = 723 mod 391.

For the RSA parameters p=29 and q=37, we calculate N as 29*37 and ϕ(N) as 28*36. The number of possible values of e in the set {1, …, ϕ(N)} is the count of integers within this range that are coprime to ϕ(N), which can be determined using a Euclidean algorithm or similar method for finding the greatest common divisor (GCD).

In the context of a Chosen Plaintext Attack (CPA) on Plain RSA, security can be enhanced by ruling out the ability of an attacker to effectively analyze and decrypt ciphertexts of related messages encrypted with the same public key.

A CPA-secure public-key encryption scheme is one where an attacker cannot gain any advantage in distinguishing ciphertexts, even when given access to a decryption oracle, thus satisfying our definition and protecting against this attack vector.