## h0pe one year ago The House of Lilliput is using RSA encryption to receive secret messages from all the realms. They have published their public encoding exponent e = 37 and their public modulus M = pq = 527. Break the code: Find their secret decoding exponent d.

1. ybarrap

Here's a worked example http://en.wikipedia.org/wiki/RSA_(cryptosystem)#A_worked_example

2. h0pe

I still don't understand...

3. ganeshie8

Your goal is to find the inverse of $$37$$ in mod $$\phi(527)$$

4. ganeshie8

Solve $37x \equiv 1 \pmod{\phi(527)}$

5. h0pe

What is $ϕ$?

6. ganeshie8

not familiar with euler totient function ?

7. h0pe

nope

8. ybarrap

For example, if your message is 2 then d is 2=mod((mod(2^37, 527))^(d) ,527) Here's why: Since c is your encrypted message c=2^37 mod 527 Then since your original message was "2" then the decrypted message is 2 = c^d mod 527 Combine both to get the 1st equation http://www.wolframalpha.com/input/?i=2%3Dmod%28%28mod%282%5E37%2C+527%29%29%5E%28y%29+%2C527%29