A Java Implementation of the
RSA Algorithm.
Radhika Reddy(2009)
CS6520-01 Summer 2004
Ping Wah Wong
Last Updated: August 19, 2004
TABLE OF CONTENTS
I. INTRODUCTION................................................................................................. 3
II. RSA BACKGROUND....................................................................................... 3
H
ISTORY...................................................................................................................... 3
CURRENT STATUS ........................................................................................................ 3
KNOWN ISSUES WITH THIS ALGORITHM ........................................................................ 3
III. THE ALGORITHM.......................................................................................... 4
IV. MY IMPLEMENTATION................................................................................ 5
OVERVIEW OF CLASSES................................................................................................ 5
KNOWN ISSUES WITH THIS VERSION OF THE IMPLEMENTATION....................................... 5
ACTUAL IMPLEMENTATION DETAILS OF THE RSA ALGORITHM (RSA.JAVA).................. 6
TESTING ...................................................................................................................... 6
V. REFERENCES/ACKNOWLEDGEMENTS ....................................................... 7
VI. APPENDIX........................................................................................................ 8
CODE FOR DEMO.JAVA................................................................................................. 8
CODE FOR ENCRYPT.JAVA............................................................................................ 9
CODE FOR DECRYPT.JAVA.......................................................................................... 12
CODE FOR RSA.JAVA................................................................................................. 15
CODE FOR IO.JAVA .................................................................................................... 17
VII. SAMPLE OUTPUT......................................................................................... 23
SCREEN SHOT OF PROGRAM RUN................................................................................. 23
INPUT.TXT ................................................................................................................. 23
DECRYPT.TXT............................................................................................................. 23
ENCRYPT.TXT............................................................................................................. 24
I. Introduction
This project aims at creating a Java implementation of the RSA algorithm. A Demo class
is provided to read a predefined plaintext file and create both the encrypted and decrypted
files.
II. RSA Background
RSA is a widely used and well document algorithm in Cryptography. It is a public key
algorithm (i.e. two different keys are used to encrypt and decrypt the data). However
these two keys are related. More details will be provided later regarding the relationship
between the keys.
History
The acronym RSA comes from the three people that created the algorithm. The ‘R’
stands for Dr. Ronald L. Rivest who is currently a professor at the Department of
Electrical Engineering and Computer Science at MIT. He is the founder of RSA Data
Security[1]. The ‘S’ stands for Dr. Adi Shamir is currently at the Weizmann Institute of
science in Israel [2]. The ‘A’ stands for Leonard Adleman [3]. He is currently at the
University of Southern California. He is currently working with DNA encoding. All three
professors were at MIT when they discovered the RSA algorithm in 1977.
The patent for the RSA algorithm expired September 06, 2004 [4]. I can now be freely
replicated and used for applications.
Current Status
RSA is currently used for many applications like RSA SecurID, Digital Certificates,
Smart Cards, etc. This algorithm is considered computationally unbreakable. i.e. it would
take a very long time to break the code. Especially if we use large keys (1024 bits at
least), it is almost impossible to find the private key to decode the ciphertext. This is
because the algorithm requires factoring two very large numbers. The RSA site has more
information in this regard [5].
Known Issues with this Algorithm
- Mathematical: If anybody finds a way to factor numbers quickly, then this
algorithm will become weak.
- Timing attacks: A hacker might time key generation process to determine the
actual keys.
- Brute force: One might simply try various keys to see if any match the private
key.
- Bad keys: If a user picks a small prime number for the private key, it would be
easier for a hacker to break their code.
III. The Algorithm
The following are the steps involved in determining the public and private keys using the
RSA algorithm:
1.
At this stage we should discard p, q, and m values.
Now we have the private key d, and the public keys e and n.
If we want to encrypt text, we will need to first represent it in some numeric form (say
P). Then we simply apply the formula:
If we want to decrypt the ciphertext C to P`, we apply the formula:
pick p & q
p,q
- Are large randomly
generated prime numbers.
Calculate:
n = pq
phi = (p-1)(q-1)
n
– One of the public keys. It is
used as the modulus.
phi - Or φ(n) is used to find ‘e’.
phi is an Euler Totient [6] .
pick e
e
– Is the other public key. It
should be relatively prime to phi.
i.e. gcd(e, phi) = 1
Calculate:
d such that
d*e mod phi = 1
d
– Is the private key. It is
relatively prime to phi and a
multiplicative inverse of e. It is
calculated using Extended
Euclid’s Algorithm.
C = P
e
mod n.
P` = C
d
mod n
(Where C is the ciphertext)
(P` is usually the same as the original
plaintext P).
IV. My Implementation
My programs were implemented using Java library functions. It was very hard to not
have code that is very similar to other available implementations of RSA using Java. I
have included any websites I used in the References/Acknowledgements
.
Overview of Classes
I have divided my implementation into 5 programs as listed below:
Demo.java – This class facilitates testing all the other programs. It first generates
the keys (calling RSA.java), then it encodes a plaintext with the public keys
(Encrypt.java), and finally it decodes the cipher text with the private and public
keys (Decrypt.java).
Link to Code in Appendix - Link to Demo.java – Link to Javadoc
Encrypt.java – This class can be run as a standalone program. It takes either no
parameters or three parameters. If no parameters are entered, it uses predefined
public keys and input/output files to encrypt the text. The default input filename is
“input.txt”. The default output filename is “cipher.txt”.
If parameters (within braces) are entered, they should be of the form:
Encrypt <input filename> <public key = e> <public key = n>
Link to Code in Appendix - Link to Encrypt.java – Link to Javadoc
Decrypt.java – This class can be run as a standalone program. It takes either no
parameters or three parameters. If no parameters are entered, it uses predefined
public and private keys and input/output files to decrypt the text. The default input
filename is “cipher.txt”. The default output filename is “decrypt.txt”.
If parameters (within braces) are entered, they should be of the form:
Decrypt <ciphertext filename> <private key = d> <public key = n>
Link to Code in Appendix - Link to Decrypt.java – Link to Javadoc
RSA.java – This class randomly generates the n and d values. I use 70001 as my
e value. I check to ensure that this number is relatively prime to phi.
Link to Code in Appendix - Link to RSA.java – Link to Javadoc
IO.java – This class facilitates opening and closing the necessary files and
reading from them a line at a time.
Link to Code in Appendix - Link to IO.java – Link to Javadoc
Known issues with this version of the implementation
1. The final decoded text does not have line feeds that the original plaintext had.
2. The program errors out if the ASCII value of the message is greater than the
public key n. It must be lower to perform modulus operations.