Hi,

I plan to code a program to simulate RSA encryption. I am using JAVA but do not want to use the inbuilt Big Integer Class. Could anyone advise me how to store the large integer? (> 100 digits) and how to write the function which do the same as pwoerMod.

thanks a lot!


C

If you change your mind and accept to use the BigInteger class (and its modPow(e,n) method) you may have a look to this web page :
http://homex.coolconnect.com/member2/wailian/QuickStartRSA/

Loading that page you will load a RSA.java file which you may read.

I attached that page, another interesting java source (publickey.java) and a javascript implementation (rsajscript).

Artifex

the problem is that using bigint class will lead java code that i've written can not immigrate to another language in the future, which doesn't have bigint class ready to use. (the code has to be rewritten.)

After tasting Java for your simulation you won't want any other language !

I can hardly understand why you want to use Java, and only a part of the Java language... but it's up to you.

If you want to try to re-invent the wheel (I mean BigInteger methods), you will have to store your long integers in strings and write an addition and a substraction routine. With them you will be able to emulate modpow(e,n). I would understand it 25 years ago, but nowadays... ? In the midtime very smart guies worked for us.

I prefer Java, but you could write your simulation in C and use Freelip or MIRACL libraries.

Artifex

thank you for your reply. i think i can check Java's biginteger class for representing large numbers. but how about mod arithmetic? could you please kindly provide me an effective algorithm to compute mod?

thanks in advance.

The Java BigInteger class has all methods to compute mod arithmetic.

If you don't want to use them (!!!???) you will have to do the following :

A power is a succession of multiplications
a multiplication is a succession of additions
a division (or a modulo) is a succession of substractions.

You know that.

So you store the big integers in strings.
You extract each character (=figure) of the first string and add (or substract it) with the corresponding character (=figure) of the other string, and create a third string with your results.
"123456789...........123456789"
+
"123456789...........123456789"
---------------------------------------
".........................................578"

and so on... and so on...in a loop.

Each compute is a one figure compute.
It is up to you to choose to work in radix-10 or radix-2

I keep it short because we are off topic.
You could get better information on a programmation language forum.
Good luck.

Artifex

thanks for your help, i will try it!

I attached a few lines of C. If you compile them you will be able to compute instantly a two big integers product. The method is not the addition method, but the way we multiply two numbers on a blackboard.

Here are two runs :

First big integer ?
123456789123456789123456789
Second big integer ?
123456789123456789123456789
gave the result :
=15241578780673678546105778281054720515622620750190521
or
First big integer ?
123456789123456789123456789123456789123456789123456789
Second big integer ?
123456789123456789123456789123456789123456789123456789
gave the result :
1524157878067367854610577831153787807696997784240207757735101981191892004648682028105472051562262075 0190521

If it is not correct you may want to debug them !

The division is a bit more tricky.

Smart programmers spent months trying to improve their biginteger routines. With the way you decided to work you will spend more time testing your computation routines than yours rsa simulation ones !

Enjoy yourself !

Artifex

Thank you so much for your great help! I will check the attached source code.

I edited the source in order to make the draft a little bit clearer.

Artifex