- #1

- 1,995

- 7

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

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: