Decoding RSA Problem: How to Crack Public Exponent and Modulo N

[Galileo]

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:

$$N = 15241578753238836751577503665157706318489955952973821$$

$$e = 31$$

$$c = m^e = 861510404336695227251078663863347293625350352438927$$

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

$$q=12345678901234567891$$
From which I find the totient:

$$\phi(N)=(p-1)(q-1)=15241578753238836750342935775034237183798709039504700$$

Then I found 'd' such that $$ed \equiv 1 \bmod \phi(N)$$:

$$d = 11799931937991357484136466406478119110037710224132671$$

So now that I've found the private key d, I should just compute c^d and I should get m. However, Maple finds
$$c^d=861510404336695227251078663863347293625350352438927^{11799931937991357484136466406478119110037710224132671} \bmod N$$ 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: $$d=(11)(17)^2(20116367)(99732718879652629)(1850127955377590503746343)$$
Then raised c to the power 11, than to the power 17^2, all mod N ofcourse.
What I was left with is then:

$$m=10629575215834074693129969195052025048670006092854912^{(1850127955377590503746343)(99732718879652629)(20116367)}=x^{abc}$$
with

$$x=10629575215834074693129969195052025048670006092854912$$

$$a = 20116367 = 1+(2)(1193)(8431)$$

$$b = 99732718879652629 = 13+(8)(3)(59)(73)(21863)(2143)(20593)$$

$$c = 1850127955377590503746343 = 31+(8)(3)(1223)(3313)(19025787016433837)$$

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.

$$y = x^a = 1610044581396706062621617218007597816610136362872871$$

$$z = y^b = 8295213403069483304303211306255358878287773906357859$$

$$m = z^c = (z^13)(2882470640844826906680249819845717295058993606788553)^(19025787016433837)$$

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

 

[Galileo]

Doh!

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.

 

[tacman]

It seems like you have put a lot of effort into trying to crack the RSA problem and have made some progress. However, it is important to note that RSA is a widely used and secure encryption algorithm, so it is not easy to crack. It is also designed to be difficult to decode without the private key.

In your approach, you have correctly calculated the private key d using the public exponent and the totient. However, the issue may lie in the calculation of m. In the RSA encryption process, the message m is first converted into a number and then encrypted using the public key. So when decrypting, you need to convert the encrypted number back into the original message.

It seems like you have used Maple to do the calculations, which may not be the most efficient way. It may be helpful to break down the exponent into smaller pieces and use a calculator to do the calculations manually.

Overall, it is commendable that you have attempted to crack the RSA problem, but it is a complex and secure algorithm that may not be easy to decode without the private key. I would suggest exploring other areas of cryptography and number theory to further your understanding and skills.