Cipher 7: Generalised RSA

The RSA cryptosystem is named after Rivest, Shamir and Adleman, who rediscoved it at MIT. It was created earlier by Clifford Cocks at GCHQ, but that information was classified. It is an example of a trapdoor cipher (others include elliptic curve cryptography), where different keys are required for encoding and decoding information.

Specifically, one encrypts some plaintext x into ciphertext y by using the formula y = x^e (mod N), where e and N are parts of the public key called the encoding exponent and modulus, respectively. By Euler’s extension of Fermat’s little theorem, it is possible to reverse this process if you have a number d (the decoding exponent); specifically, x = y^d (mod N). It is difficult to obtain d from e unless you know the prime factorisation of N.

I’m going to tell you that in this case the encoding exponent e = 65537 and the modulus N = 2^1024+1. The ciphertext y is the 308-digit integer given below:

70384453163117591654769573028818627011176266
85961097044944482079622303100714997743084870
17845889673059891358758676310163683929666686
34263955516926021379735957361166115633684498
03685254214632580655687518190933128197638060
14654501856631139244507713583948331391422982
45376589754270166865399155271952021664938169

Once you recover x, you’ll have to find some way of converting the integer into a message. The password for the secret area, by the way, is entirely in lower-case.

Advertisements
This entry was posted in Ciphers. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s