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 A screen capture of the RSA video I am getting the RSA variables from

Artjom B. · Accepted Answer · 2015-05-29T17:31:29.453

3

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.

edited May 29 '15 at 17:31

answered May 29 '15 at 16:54

Artjom B.

61,146
24
125
222

Thank you for your answer! I tried with m=5, but again, I am not getting the result right, I get c = Math.pow(m,e)%n = 25, and the message decrypted md = Math.pow(c,d)%n = 27, do you know why? – Juan Camilo Guarin P May 29 '15 at 17:05
The problem is that you're doing this in JavaScript and some operations exceed the maximum safe integer. I extended my answer and added the explanation. – Artjom B. May 29 '15 at 17:32
1

@JuanCamiloGuarinP, for clear understanding about message length of RSA encryption, watch this [RSA Encryption Problem Size of payload data](http://stackoverflow.com/questions/5866129/rsa-encryption-problem-size-of-payload-data) – mazhar islam May 29 '15 at 20:03
Thank you both for your answers. I didn't know about that floating point problem in Javascript. As I only wanted to test that simple operation, my first reaction was to make it in the browser console, now I am going to make the test in python :) – Juan Camilo Guarin P May 30 '15 at 07:56
@juan Python provides a pow function that optionally takes a modulus which uses a far more optimized method of calculating the powmod. – Artjom B. May 30 '15 at 08:47

score 0 · Answer 2 · answered May 31 '15 at 14:50

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.

RSA Simple example with Javascript?

2 Answers2