1
$\begingroup$

Sorry if this is asked a lot, I just don't know if there's a specific word for it.

I'm at uni and have a codebreaking exam in a few days, I don't have to do well in it but I want to do as well as I can, but this is really making me struggle.

Here is my work so far, everything's going alright:

screenshot

Obviously when I try to do the bottom part, any calculator I use says it's invalid or infinite, I understand it's a crazy big number, but I have no idea how to work it out otherwise.

$\endgroup$
  • $\begingroup$ There is no crazy big number involved in this example, your tool must be able to do modular exponentiation. I would use a programming language, but most likely a math environment can also do it. Isn there one recommended by the course? $\endgroup$ – eckes Apr 30 '17 at 13:31
  • $\begingroup$ @eckes it's in the screenshot, but if you can't see it, it's 41754^247543 which a calculator refuses, can't even get to the modulus part because of it. :/ $\endgroup$ – P Carr Apr 30 '17 at 13:35
  • 2
    $\begingroup$ @PCarr, See crypto.stackexchange.com/q/31559/30150 please. $\endgroup$ – Meysam Ghahramani Apr 30 '17 at 21:03
  • $\begingroup$ Please don't post text as an image. Instead, please copy the text itself and paste it into the edit box. If you're having trouble getting the text formatted like you want, see this help page. $\endgroup$ – Ilmari Karonen May 18 '17 at 17:20
1
$\begingroup$

The efficient calculation of a modular exponentiation is part of the implementation of RSA. I bet this will be part of the course.

You can use a programming language which has a primitive for that, or you can use math packages. The company behind Mathematica offers a online version under the name WolframAlpha:

enter image description here

$\endgroup$
  • $\begingroup$ I'll look on WolframAlpha then, we did look at it in the course but I'm not very good at maths and it's not an essential module, I still wanna do as well as I can in it, won't be very well though haha. $\endgroup$ – P Carr Apr 30 '17 at 13:47
3
$\begingroup$

If you want to do it with hand calculator, you can use exponentiation by squaring, and compute the remainder after each multiplication. (instead of first computing huge powers and only then taking the remainder)

$\endgroup$
1
$\begingroup$

If you have just a simple calculator to do solve this question, you could use the Square-And-Multiply algorithm. I also had exams where I had to use it, using a simple calculator. Have a look here: Square-And-Multiply

$\endgroup$
1
$\begingroup$

For efficient Encryption and decryption in RSA, method of “exponentiation by repeated squaring and multiplication” is used. Please read Section A(page 8) of the paper in which RSA was proposed. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems

Another approach is to use Chinese Remainder Theorem with RSA. You can find more details at

  1. Using CRT with RSA
  2. CRT example in RSA
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.