Question

In the RSA cryptosystem, it is possible that M = C, that is, the plaintext and the ciphertext may be identical.

Is this a security concern in practice?

For modulus N = 3127 and encryption exponent e = 17, find at least one non trivial message M (i.e. M > 1) that encrypts to itself

Answer 1

Part A:

Yes, it is a security concern in the practice.

Explanation:

The purpose of encryption is to make plaintext hard to understand but if the plaintext and ciphertext are same then it is considered as a flaw or hole in the system. On constructing the table for ciphertext and plaintext if any value has M equals to C then it is the flaw.

Part B:

Given:

N = 3127

p = 53

q = 59

e = 17

Φ(n) = (p-1)(q-1) = (53-1)(59-2) = 52*58 = 3016

de = 1 mod(Φ(n))

de = 1 mod(3016)

de = 1mod(3016)             

d*17 = 1 mod (3016)                [replace d*e by the values (3016* n) +1 where n is 1,2….]

36193 = 1 mod(3016)               [(3016*12) + 1 = 36192 + 1 = 36193]

d = 36193/17

d = 2129

In order to find M = C put M and C values in range 2 to 3126.

Encrypt:

For M = 235:

C = M^e mod n

C =( 235^17) mod 3127 = 1

C = ((235^16)*235) mod 3127                 [235^4 mod 3127 = 1]

C = 235

Decrypt:

For C = 235:

M = C^d mod N

M = (235^2129) mod 3127 = 1            [532*4 = 2128 and 235^532 mod 3127 =1 ]

M = (235*(235^532) *(235^532)* (235^532) *(235^532))mod 3127

M = (235*1*1*1*1)mod 3127

M =235

Thus, M = C = 235

The non-trivial message that encrypts to itself is M =235