27.12.17

phi of n over 2 is just a number after all

Some people seem to have a hard time visualizing why my previous post is interesting. While proving the existence of a second private key does not break the RSA encryption algorithm, it does present a second attack vector especially for a certain subset of the set of products of safe primes.

Clearly, phi(n)/2 can be found if phi(n) is known. However, as I stated previously in this blog, for certain products of safe primes phi(n)/2 can be found without prior knowledge of phi(n).

In general, if n belongs to the set of these certain products of primes, then there exists an integer k mod n such that 2*k = n-1 and k^k = phi(n)/2 where phi(n) is Euler's Totient Function

One such product is the product of the 2 smallest safe primes, namely 5 and 7.

Example:

Given n = 35 then (n-1)/2 = 17 and 17^17 = 12, which is phi(35)/2