RSA Encryption Algorithm in Java: No BigIntegers

Question

I need to implement the RSA algorithm in Java. I found a better solution using BigIntegers, the problem is that I only need to work with ints or longs. Encryption is performed as follows: M[i]^e mod nwhere M [i] is the input of char, and e is the key value. I tried using ASCII character codes, and with codes such as 115 and 116, I quickly go out of range. How can i solve the problem? Thanks in advance.

Answer 1

You can take a look at modular exponentiation . Thus, you overcome most of the overflows in your calculations.

Answer 2

To clarify a bit ...

(a * b) mod m == ((a mod m) * (b mod m)) mod m

If you recall the basic math,

a ^ 10 = (a ^ 5) * (a ^ 5)

So, you can divide your crazy higher forces into lower forces, and then take their value modulo (thereby keeping the value small), and then recombine them later:

Too Big!         = Just Right!
(2 ^ 20) mod 113 = (((2 ^ 10) mod 113) * ((2 ^ 10) mod 113)) mod 113

I don’t know if this is considered a "distribution", but my students had problems with it once, and I had no problems showing them this trick. In addition, I believe this is more of a recursion exercise than anything else.