2
$\begingroup$

$d = 27, e = 3, n = 40$

For encryption, I have the letter T converted to 084 by the ASCII table, which encrypts to $24$ by $84^3\bmod 40$, for example.

To decrypt, I believe it would be $24^{27}\bmod40$ however this gives me 4.4342649e+38 which clearly does not fit into my ASCII table.

How does one decrypt using the RSA algorithm in relation to ASCII?

Further question: Is ASCII converter the best way to convert plaintext to numerical value?

EDIT: this is purely for a high school maths project; thank you for all the answers

$\endgroup$
3
  • 1
    $\begingroup$ What kind of programming language do you use? Because there seems to be one problem with the calculation of (24^27)mod40. That should return the result 24: wolframalpha.com/input/?i=(24%5E27)mod40 $\endgroup$ Jul 9 '18 at 13:20
  • 6
    $\begingroup$ Typically n is the product of two primes - 40 equals 2*2*2*5. Also the message m (84 in your example) should be less than n. $\endgroup$ Jul 9 '18 at 13:24
  • 1
    $\begingroup$ No. This is textbook RSA. Textbook RSA is NOT secure. $\endgroup$ Jul 9 '18 at 15:46
2
$\begingroup$

You have two problems. The first is that you tried encrypting a value which is too large. If you are doing all your math mod n you have no hope of ever getting a result larger than n.

The second is in tthe implementation. You seem to be working in an environment which treats large numbers as floating points (JavaScript? ) and are not using efficient modular exponentiation. https://en.m.wikipedia.org/wiki/Modular_exponentiation

24^27 is a fairly large number. It doesn't fit in a normal int or long variable. So you need to either have a special big integer to handle such large numbers. Or Preferably avoid them in the first place by applying the moduls in intermediate steps while calculating the power operation, preventing the nunbers you are handling from getting out of hand.(In full size implementations you need both).

$\endgroup$
2
$\begingroup$

For encryption, I have the letter T converted to 084 by the ASCII table, which encrypts to $24$ by $84^3\bmod 40$, for example.

The first problem (that hasn't surfaced yet for you) is already here. $84>40$ and as the decryption is $\bmod 40$ you can only get number $<40$ back, meaning there's no chance you're getting $84$ back after decryption. The fix is to either pick a smaller message or to pick a larger modulus.

To decrypt, I believe it would be $24^{27}\bmod40$ however this gives me 4.4342649e+38

You probably naively implemented this as 24**27%40 or similarly, that is you asked your computer first to compute the full power and then perform the modular reduction. However it appears you have done so in a programming language which doesn't use 128-bit or larger (possibly unbounded) integers by default meaning at some point during the computation of $24^{27}$ (which takes about 124 bits to represent) the integer you used over-flowed and wrapped around to either 0 or some big negative number at which point the computation became wrong and yielded the nonsensical result you are seeing. Fixes are to either use a big-integer library, unbounded integers if supported by the language or implement an algorithm like repeated-square-and-multiply to keep the intermediate values low and representable using 32 or 64 bits.

Is ASCII converter the best way to convert plaintext to numerical value?

It will work if you only ever encode ASCII characters, otherwise you probably want to use UTF-8 and encode whole groups of characters at once. Also please don't use your own RSA implementation for production / important purposes, because it will most likely be insecure.

$\endgroup$
0
$\begingroup$
  1. As Eugene Styer mentioned above, the number to encrypt has to be less than n, i.e. less than 40.

  2. How to get $X^{27}\bmod 40$? For non-industrial purpose you can use any of following rules:

$(A*B)\bmod C = ((A\bmod C) * (B\bmod C))\bmod C$

$(A*B)\bmod C = ((A\bmod C) * B)\bmod C$

$(A*B)\bmod C = (A * (B\bmod C))\bmod C$

For the degree 27 repeat following 27 times:

$R[i+1] = (R[i] * X)\bmod 40$

Example: Your value 84 is greater than 40. So your example is not quite correct. Let's take a correct number less than 40. Let's take 7.

$7^3\mod 40 = 23$

It means, after using your key value 7 is encrypted to 23.

Now let's check if we get 7 after decryption of 23.

$23^{27}$ can lead to the lost of precision depending on your programming language. But if you apply $\bmod$ on each step as I described above, you will always have small numbers:

  1. $23^1\bmod 40 = 23$
  2. $23^2\bmod 40 = (23 * 23)\bmod 40 = 9$
  3. $23^3\bmod 40 = (9 * 23)\bmod 40 = 7$
  4. $23^4\bmod 40 = (7 * 23)\bmod 40 = 1$

...

  1. $23^{27}\bmod 40 = (9 * 23)\bmod 40 = 7$

Voilà! We have got the original value that we have encrypted, 7.

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