RSA Simple example with Javascript?

Question

I know this may be kind of basic but I am having an exam on the next week and I wanted to test my knowledge of RSA.

I have a very simple problem that I am working on to see the mechanics of RSA, and I want to test if I can encrypt and decrypt a message in my browser console.

The RSA variables are:

var p = 11 //the first prime number
var q = 5 //the second prime number
var m=72 // the message
var n=55 // the RSA modulus, n = p*q
var e=7 // so (e,n) are the public key
var d=23 //so (d,n) are the private key
var fi_of_n=40 //the totient, fi_of_n = (p-1)*(q-1) = 40

To encrypt, I am doing:

var c = Math.pow(m,e)%n // m^e mod(n); c=8

I get c to be equals to 8

Then I want to decrypt, using d as follows:

var m2 = Math.pow(c,d)%n // c^d mod(n)

But the result is 17! not 72 as I expected. I don't know what I am doing wrong and I think it is a very simple example.

The values of my public and private key are the ones obtained in this video: https://www.youtube.com/watch?v=kYasb426Yjk

Answer 1

I am answering my own question with the solution I found thanks to the comments of @Artjom B. and @rakeb.void.

Due to the limitations of limitations of Javascript with the Number.MAX_SAFE_INTEGER the test cannot be done with the variables presented.

One of the solutions is to use a multiple precision library, and the other is to go with Python to make the same test.

I went with Python because I didn't want to learn how to use a multiple precision library only to test. The program I made is the following:

import math
p = 11
q = 5
m = 39
n = 55
e = 7
d = 23
fi_of_n = 40

print ("original: "+str(m))

cipher= pow(m,e)%n
print("cipher: "+str(cipher))

m2 = pow (cipher,d)%n
print("decrypted: "+str(m2))


print("----")
print("Are they equal? " + str(m == m2))

And it works as long as the message is lower than the modulus operator n.

Answer 2

RSA has a limitation that only messages strictly smaller than the modulus can be encrypted. Your message of 72 is too big for your modulus of 55. You can see that the encryption and decryption basically work, because 17 = 72 (mod 55).

In JavaScript all numbers are floating point numbers. There is a maximum number that can be safely represented as an integer: Number.MAX_SAFE_INTEGER = 9007199254740991. If the result of a power operation exceeds this value, the nature of floating point operation cannot ensure that you get the correct value back. During encryption and decryption such a cutoff can happen twice.

Let's take m = 5 for example. pow(5, 7) = 78125 which is smaller than 9007199254740991. There is no cutoff here. Now, with c = 25 we get Math.pow(25, 23) = 1.4210854715202004e+32 which is far bigger than the safe integer. When we now apply the modulo operator, it won't give a correct result, because the floating point resolution is not 1 anymore.

The message 8 for example produces a small enough pow(m,e) value that is smaller that this maximum safe integer value and the resulting ciphertext also produces a small enough pow(c,d) value that it isn't cut off.

You should either use a big number (multiple precision) library to do those operations or use Python which can represent any integer as long as you have enough memory. If you want to keep doing this in JavaScript, there is jsbn which also implements RSA in addition to a big number library.