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...