Algorithm Information | 128-bit key generator | Official 512-bit Challenge keys


Welcome to the challenge home page. On this page you will find information on the hidden small exponent method and how it can be used to create keys that appear to be genuine RSA keys. However, it is a simple matter to decrypt messages that have been encrypted using pseudo keys generated by the hidden exponent algorithm.

We invite you to learn about this algorithm, try out the 128-bit key generator (details on implementation provided) and try the official challenge yourself.

First, here's a review of the standard RSA algorithm:

REPEAT pick a random number P of STRENGTH bits UNTIL Rabin-Miller primality test claims it is a prime
REPEAT pick a random number Q of STRENGTH bits UNTIL Rabin-Miller primality test claims it is a prime
Let N:=P*Q, PHI:=(P-1)*(Q-1)
REPEAT
 pick a random number D mod PHI
UNTIL gcd(D,PHI)=1
using the extended Euclidean algorithm find E such that D*E=1 mod PHI.
output Private Key: = (D,P,Q), Public Key := (E,N).


Pseudo RSA keys are generated using the hidden small exponent method proposed by Claude Crepeau and Alain Slakmon:

Let M := a STRENGTH bit even constant fixed in the program.
REPEAT pick a random number P of STRENGTH bits UNTIL Rabin-Miller primality test claims it is a prime
REPEAT pick a random number Q of STRENGTH bits UNTIL Rabin-Miller primality test claims it is a prime
Let N:=P*Q, PHI:=(P-1)*(Q-1)
REPEAT
 REPEAT
  pick a random number D such that |D|<|N|/4
 UNTIL gcd(D,PHI)=1
 using the extended Euclidean algorithm find E such that D*E=1 mod PHI.
 let E' := E (+) M
UNTIL gcd(E',PHI)=1
using the extended Euclidean algorithm find D' such that D'*E'=1 mod PHI.
Output Private Key := (D',P,Q), Public Key := (E',N).


If you are the pseudo RSA algorithm implementer and know the secret constant, M, you can backdoor the encrypted message:

Given the public key (E',N), compute the related public key (E,N) where E := E' (+) M. Using the Wiener algorithm solve the instance (E,N) for the corresponding D such that |D|<|N|/4, factor N as P,Q, given E,D.

We believe that it may be very difficult or impossible to detect the malevolence of keys generated using this method. Hence the open challenge. Now that the RSA algorithm is public domain, companies no longer need to license it from RSA, leaving the purity of the implementation open to "interpretations".


original proposal is broken...

Back to top