Question

Consider the following 3-person encryption scheme based on RSA. L (can be trusted in this case) generates two large primes p and q, calculates both n and φ(n). L also chooses k1, k2 and k3 such that GCD(ki,n) = 1 and k1k2k3 ≡ 1 mod φ(n). Keys are securely distributed to three others as follows:

G: <n,k1,k2 >

J: < n, k2, k3 >

Z: < n, k3, k1 >

Answer the following questions.

(a) G has a message M1 for J. Give the encryption function for G as well as the decryption function for J, so that the message won’t be seen by anyone else.（Detailed steps）

(b) J has a message M2 for both G and Z. Give the encryption function for J, as well as decryption functions for both G and Z, so that the message won’t be seen by any other person.（Detailed steps）

Answer 1

Given that k1mk2 and k3 are such that gcd(ki,n)=1 and .

since

a. G has a message M1 for J.

Encryption : (the ciphertext) .

Decryption :

Checking the correctness:

Consider as in normal RSA with two keys, where e is the encryption exponent and d is the decryption exponent, here e=k1 and d=k2k3.

Hence

.

Now, if Z wants to decrypt the message , then the only operations Z can do is

Hence Z can not extract the message without knowing k2.

b. Procedure is same as in a. but the encryption and decryption exponents are the only things that change.

Decryption:

As mentioned in part a, the message for G, cannot be decrypted without knowing the value of k2 which is unknown to Z. Hence Z cannot decrypt .

Similarly, the message for Z, cannot be decrypted without knowing the value of k3 which is unknown to G. Hence G cannot decrypt .