+0

# Number theory

0
328
6
+736

The House of Lilliput is using RSA encryption to receive secret messages from all the realms. They have published their public encoding exponent 37 and their public modulus M=pq=527.

Break the code: Find their secret decoding exponent d

Jun 21, 2018

#1
+985
+2

Hey Guest

We first need to factor the public modulus $$M = pq = 527 \Rightarrow 527 = 17 \cdot 31.$$

Therefore $$p =17 \ \&\ q=31$$

The definition of a secret decryption exponent is the multiplicative inverse of the public encoding exponent, in modulo $$(p-1)(q-1)$$.

Therefore $$d= 37^{-1} \pmod{480}. \Rightarrow d=\boxed{13}$$

I hope this helped,

Gavin

Jun 21, 2018
#6
+736
0

Thank you so much!! That really helped!

MIRB16  Jun 22, 2018
#2
0

Gavin It would help more if you would show how to do this.

When I type input 37^-1 mod 480 into the calculator I get 0.027027027

Jun 21, 2018
#3
0

Go online to this page which gives a detailed numerical example on how to break the RSA encryption.

Look under: A working example:

https://simple.wikipedia.org/wiki/RSA_algorithm

Jun 21, 2018
#4
0

Thanks. This shows how to encrypt and decrypt but not how to “crack” the key.

Do you know of a website where it shows the steps on how to do this?

Jun 21, 2018
#5
0

Play around with this "RSA calculator"

https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html

Jun 21, 2018