Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

RSA: decoding problem

  1. Dec 5, 2006 #1


    User Avatar
    Science Advisor
    Homework Helper

    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.
    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:

    From which I find the totient:


    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]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.

    Last edited: Dec 5, 2006
  2. jcsd
  3. Dec 5, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    Doh! :grumpy:

    I did z^13 instead of z^31. Silly me. After a few hours of checking I didn't notice that. And if I didn't make that Latex error I probably still missed it.

    So with z^31 it does give the right answer:
    m = 14210805021005040520182103202305120205071805160514

    If you group the digits in pairs and let A=01, B=02, etc, it says
    NUHEBJEDETRUCTWELBEGREPEN, which is (apart from spacebars and a spelling error) dutch for 'You've understood the trick by now'.
    I hoped it would contain some ancient wisdom, but oh well.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

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