I just read up a bit on RSA and tried to do a problem I have in my algebra book. The goal is to crack/decode the message c=m^e mod N, obtained with public exponent e and modulo N.(adsbygoogle = window.adsbygoogle || []).push({});

I just puzzled away and tried a few things. I`m not a number theorist so my method may not be the most efficient, but it should work. However, my final answer doesn't match. When I compute m^e mod N it's not the same as I started with. Hopefully someone can spot the error.

Given is:

[tex]N = 15241578753238836751577503665157706318489955952973821[/tex]

[tex]e = 31[/tex]

[tex]c = m^e = 861510404336695227251078663863347293625350352438927[/tex]

I just let Maple grind for a few minutes and it found the prime factorisation of N = pq:

[tex]p=1234567890123456789012345678901231[/tex]

[tex]q=12345678901234567891[/tex]

From which I find the totient:

[tex]\phi(N)=(p-1)(q-1)=15241578753238836750342935775034237183798709039504700[/tex]

Then I found 'd' such that [tex]ed \equiv 1 \bmod \phi(N)[/tex]:

[tex]d = 11799931937991357484136466406478119110037710224132671[/tex]

So now that I've found the private key d, I should just compute c^d and I should get m. However, Maple finds

[tex]c^d=861510404336695227251078663863347293625350352438927^{11799931937991357484136466406478119110037710224132671} \bmod N[/tex] a bit hard to swallow (well, me too). So I thought about breaking d up into smaller pieces that Maple can handle and compute the parts manually. It goes fine as long as the exponent is not much larger than in the order of 50000.

I did: [tex]d=(11)(17)^2(20116367)(99732718879652629)(1850127955377590503746343)[/tex]

Then raised c to the power 11, than to the power 17^2, all mod N ofcourse.

What I was left with is then:

[tex]m=10629575215834074693129969195052025048670006092854912^{(1850127955377590503746343)(99732718879652629)(20116367)}=x^{abc}[/tex]

with

[tex]x=10629575215834074693129969195052025048670006092854912[/tex]

[tex]a = 20116367 = 1+(2)(1193)(8431)[/tex]

[tex]b = 99732718879652629 = 13+(8)(3)(59)(73)(21863)(2143)(20593)[/tex]

[tex]c = 1850127955377590503746343 = 31+(8)(3)(1223)(3313)(19025787016433837)[/tex]

So I've broken up a,b and c into smaller pieces again and repeated the scheme. The answer is below, I've introduced some symbols for clarity. Everything is assumed to be taken modulo N.

[tex]y = x^a = 1610044581396706062621617218007597816610136362872871[/tex]

[tex]z = y^b = 8295213403069483304303211306255358878287773906357859[/tex]

[tex]m = z^c = (z^13)(2882470640844826906680249819845717295058993606788553)^(19025787016433837)[/tex]

For the last step I hacked up 19025787016433837 into 10+(49)(349)(25447)(21937)(1993) and putting it all together gave me:

m = 1632801515822720824329177013717453486198256157145735

But when I calculate m^e (mod N) I do not get the original c. So something is wrong, but I've doublechecked the whole thing a few times and I can't find a mistake. It may be something elementary, but I'd appreciate any help.

Ciao

**Physics Forums - The Fusion of Science and Community**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# RSA: decoding problem

Loading...

Similar Threads - decoding problem | Date |
---|---|

I A problem in combinatorics | Jan 17, 2018 |

B Optimisation problem | Jan 11, 2018 |

I Math papers and open problems | Dec 11, 2017 |

**Physics Forums - The Fusion of Science and Community**