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

• Galileo
In summary, the conversation discussed the RSA encryption method and the process of trying to decode a message using a public exponent and modulo. The individual had trouble with their method not producing the correct answer, but eventually realized their mistake and successfully decoded the message. The message did not contain any profound wisdom.
Galileo
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:

$$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

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

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.

## 1. What is RSA decoding problem?

The RSA decoding problem is a mathematical problem that involves decrypting a message that has been encrypted using the RSA algorithm. This problem is considered difficult to solve, as it is based on the difficulty of factoring large numbers.

## 2. How does the RSA algorithm work?

The RSA algorithm is a public-key encryption method that uses two keys - a public key and a private key - to encrypt and decrypt messages. The public key is used to encrypt the message, while the private key is used to decrypt it. The algorithm relies on the mathematical difficulty of factoring large numbers to ensure the security of the encrypted message.

## 3. Why is the RSA decoding problem important?

The RSA decoding problem is important because it is the basis of modern secure communication. It is used in various applications, such as online banking, e-commerce, and secure messaging, to protect sensitive information from being intercepted and read by unauthorized parties.

## 4. Is the RSA algorithm unbreakable?

As of now, the RSA algorithm is considered unbreakable if the keys are large enough. However, with the advancement of technology and the discovery of new mathematical algorithms, it is possible that the RSA algorithm may be broken in the future. That is why it is important to regularly update the key size used in the RSA algorithm to ensure its security.

## 5. What are the limitations of the RSA algorithm?

One limitation of the RSA algorithm is that it is computationally intensive, which means it can be slow when encrypting and decrypting large amounts of data. Another limitation is that it is vulnerable to attacks if the key size is not large enough. Additionally, the RSA algorithm does not provide authentication, so it is possible for an attacker to intercept and modify the encrypted message without being detected.

Replies
1
Views
1K
Replies
7
Views
2K
Replies
1
Views
730
Replies
2
Views
791
Replies
3
Views
3K
Replies
1
Views
1K
Replies
2
Views
1K
Replies
17
Views
5K
Replies
4
Views
385
Replies
1
Views
1K