Computer Security and Cryptography

12.4 ATTACK ON RSA [SIMMONS, 1983; DELAURENTIS, 1984]

A conceivable network implementation of the RSA algorithm uses a system public key table as in Figure 12.1.

The maintenance of the table, in particular certifying that it is free from malicious entries, is the responsibility of the system manager. It was even suggested that a simplification would result if a single pair of primes p, q could be used throughout the network.

Figure 12.1 A system's RSA parameter table.

Proposition 12.7: [Simmons, 1983]:  If p_i = p, q_i = q, N = pq for all i, knowledge of two public keys e_i and e_j with 1 = gcd{e_i, e_j} permits the decipherment of all messages of every user.

Proof: Suppose a single common pair of primes (p, q) is used, then

and

As 1 = gcd{e_i, e_j}, there exist integers a, b (by the Euclidean algorithm) such that

One of the two integers a, b must be negative (the other positive). Suppose b < 0. If gcd{C_j, N} ≠ 1, C_j has a factor in common with N, which must equal p or q. In this case many ...