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.

This entry was posted in Ciphers. Bookmark the permalink.

Leave a Reply