1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

    Galileo

    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:
    [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
     
    Last edited: Dec 5, 2006
  2. jcsd
  3. Dec 5, 2006 #2

    Galileo

    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

Have something to add?



Similar Discussions: RSA: decoding problem
  1. A problem (Replies: 24)

  2. A problem (Replies: 15)

  3. RSA Algorithm Help (Replies: 7)

Loading...