# Cracking RSA — A Challenge Generator

Do you have what it takes to be a cipher cracker? Well here is a challenge for you [here]:

RSA Encryption parameters. Public key: [e,N].

e: 65537

N: 498702132445864856509611776937010471

Cipher: 96708304500902540927682601709667939

We are using 60 bit primesCan you find the value of the message?

With this we are using the RSA encryption method, and we have the encryption key (e,N). We must find the two prime numbers which create the value of N (p and q), and must use a factorization program to find them. Once we find the factors it is easy to then determine the decryption key (d,N).

## Example

Here is an example:

`Encryption parameters`

e: 65537

N: 1034776851837418228051242693253376923

Cipher: 582984697800119976959378162843817868

We are using 60 bit primes

Now we have to crack N by finding the primes that make up the value.

If we use this [link], we get:

`Factors`

-------

1,034,776,851,837,418,228,051,242,693,253,376,923 = 1,086,027,579,223,696,553 x 952,809,000,096,560,291

p=1,086,027,579,223,696,553 q=952,809,000,096,560,291

Now we work out PHI, which is equal to (*p*−1)×(*q*−1):

`>>>p=1086027579223696553`

>>>q=952809000096560291

>>> print (p-1)*(q-1)

1034776851837418226012406113933120080

Now we find *e⁻¹* (mod *PHI) *(and where (*d*×*e*) (mod *PHI)*=1), such as using [here]:

`Inverse of 65537 mod 1034776851837418226012406113933120080`

Result: 568411228254986589811047501435713

This is the decryption key. Finally we decrypt with *Message*=*Cipherᵈ (*mod *N)*:

`>>> d=568411228254986589811047501435713`

>>> cipher=582984697800119976959378162843817868

>>> N=1034776851837418228051242693253376923

>>> print pow(cipher,d,N)

345

The message is 345

Finally, let’s check the answer. So we can re-cipher with the encryption key and we use *Cipher*=*Mᵉ *(mod *N)*:

`>>> m=345`

>>> e=65537

>>> N=1034776851837418228051242693253376923

>>> print pow(m,e,N)

582984697800119976959378162843817868

This is the same as the cipher, so the encryption and decryption keys have worked. Thus the encryption key is [65537, 1034776851837418228051242693253376923] and the decryption key is [568411228254986589811047501435713, 1034776851837418228051242693253376923]

## Conclusions

This is fairly simple to compute as the prime numbers are fairly small. In real-life these will be 1,024 bit prime numbers, and N will have 2,048 bit numbers, which will be extremely difficult to factorize.

If you want here’s some challenges:

- Challenge with 60-bit primes:

RSA Encryption parameters. Public key: [e,N].

e: 65537

N: 911844725340031776516886332975892441

Cipher: 801127314512167104045686292190207406

We are using 60 bit primesCan you find the value of the message?

2. Challenge with 80-bit primes:

RSA Encryption parameters. Public key: [e,N].

e: 65537

N: 1157170973102575683016736411062049761643292045397

Cipher: 398616441584847118291875619819339172891325623639

We are using 80 bit primesCan you find the value of the message?

3. Challenge with 128-bit primes:

RSA Encryption parameters. Public key: [e,N].

e: 65537

N: 49141939931137261116843775362783398673931258031923895283286320973486872970729

Cipher: 14199123787046830048066972290052136769415356824981695836360604590953658335413

We are using 128 bit primesCan you find the value of the message?

— — — — — — — — — -

— — — — — — — — — -

## Answers

— — — — — — — — — -

1. Answer is: 1497

2. Answer is: 427

2. Answer is: 145