RSA
Implementation of RSA Algorithm
Name Bhaskar Bora
Date March 2, 2003
Place Bangalore, India
1
RSA
1 Introduction................................................................................................................ 3
2 Description of The Algorithm.................................................................................... 4
3 RSA Software ............................................................................................................. 5
3.1 Software Usage Guidelines............................................................................... 5
4 Algorithms used in RSA software.............................................................................. 7
4.1 Main Key Generation Algorithm .................................................................... 7
4.2 Prime Number Generation Algorithm............................................................ 7
4.3 Algorithm for Selecting the Value of ‘e’ ......................................................... 8
4.4 Algorithm for Calculating the Value of ‘d’ .................................................... 8
4.5 Algorithm for Encrypting Data ....................................................................... 9
4.6 Algorithm for Decrypting Data ..................................................................... 10
5 Example of RSA encryption and decryption........................................................... 11
6 Appendix-A (RSA Software Screen Snap-Shots).................................................... 12
6.1 Main Screen..................................................................................................... 12
6.2 Screen Shot Showing Key Generation .......................................................... 13
6.3 Abstract Screen ............................................................................................... 13
7 Appendix-B (Source Files) ...................................................................................... 14
2
RSA
1 Introduction
This assignment is to study and implement RSA algorithm in software. Implementation
includes private and public key (32-bit) generation and support of text file encryption and
decryption. This document contains the algorithms and information required to design
and implement RSA algorithm in VC++. This software is only for text data encryption
and decryption. Document also contains the software usage guidelines and screen-shots.
RSA algorithm is mainly a public key encryption technique used widely in network
communication like in Virtual Private Networks (VPNs). In public key encryption
technique, a key is split into two keys and they are called as public and private keys.
Public key is advertised to the world and private key is kept secret. It is not possible to
generate private key using the public key. So, someone who knows the public key cannot
decrypt a message after it has been encrypted using the public key.
A diagrammatic representation of public key encryption is shown below
Encrypted Msg
A B
B’s
Public
Key
Encrypt
Key Generator
for B
Decrypt
B’s
Private
Key
Message Message
Let us take a case where A needs to send a message to B using a public key encryption
algorithm. Key generator generates the keys for B and distributes the public key to each
person who needs to send a message to B. The private key is kept secret and only B has
it. In this case, key generator gives the public key to A so that A can send message to B.
In RSA algorithm decryption is possible only through private key. And there is no way
by which private key is generated using public key. So the message transmitted from A to
B using RSA encryption is secure even though others know B’s public key. For two-way
communication between A and B there will be another set of keys for A.
3
RSA
2 Description of The Algorithm
The paper by Diffie and Hellman introduced a new approach to cryptography. This, in
effect, challenged cryptologists to come up with a cryptographic algorithm that met the
requirements of public-key systems. Ron Rivest, Adi Shamir and Len Adleman
developed the algorithm and gave the implementation details in the year 1978. Since
then, Rivest-Shamir-Adleman (RSA) scheme it is considered as the only widely accepted
and implemented general-purpose approach to public-key encryption.
RSA algorithm is a block cipher technique in which plain text and cipher text are integers
between ‘0’ and ‘n-1’ from some ‘n’. In RSA algorithm encryption and decryption are of
following form, for some plain text M and cipher text C:
C = M^e mod n
M = C^d mod n
Both sender and receiver must know the value of ‘n’. The sender knows the value of ‘e’
and only receiver knows the value of ‘d’. Thus, this is a public-key encryption algorithm
with a public key of KU={e, n} and private key of KR={d, n}. For the algorithm to be
satisfactory for public-key encryption, the following requirement must be met
1. It is possible to find values of e, d, n such that M^ed = M mod n for all M<n.
2. It is relatively easy to calculate M^e and C^d for all values of M<n.
3. It is infeasible to determine d given e and n.
The key generation process is as follows
Select p and q p and q are prime numbers
Calculate n = p x q
Calculate F(n) = (p-1) x (q-1)
Select integer e gcd(F(n),e)=1; 1<e<F(n); e and F(n) are relative prime
Calculate d d = e-1 mod F(n)
Public key KU = {e,n}
Private key KR = {d,n}
Encryption process
Plaintext M<N
Ciphertext C = M^e (mod n)
Decryption process
Plaintext C
Ciphertext M = C^d (mod n)
4
RSA
3 RSA Software
RSA software is a prototype software to demonstrate key generation using RSA
cryptography algorithm. Software is capable of generating 32-bit long keys. It has the
following features.
1. RSA software can generate two prime numbers randomly. Also, user can specify
one or both prime numbers.
2. Software calculates and displays the value of ‘n’.
3. It calculates and displays the value of ‘e’.
4. It generates and displays the value of ‘d’ using ‘e’ and ‘n’.
5. Displays both public and private keys for analysis.
6. User can encrypt a text file using the public key.
7. User can decrypt the encrypted file using the private key.
8. User can compare the original text file and decrypted text file.
An example is shown below to describe the key generation process
1. Selecting two prime numbers, p=13 and q=19
2. Calculate n = p x q = 13 x 19 = 247
3. Calculate F(n) = (p-1) x (q-1) = 216
4. Select ‘e’ such that e is relatively prime to F(n)=216 and less than F(n); in this
case, e = 5
5. Determine d such that
d x e º1 mod 216 and d<216.
Where, d x e = kF(n)+1
The correct value of d = 173
6. Thus, the resulting public key KU = {5, 247} and private key KR = {173, 247}
3.1 Software Usage Guidelines
Guidelines for using RSA software to generate public and private keys
1. Select two distinct prime numbers and enter in the edit box provided.
Also, user can selectively ask the software to generate ether or both the
prime numbers. Software generated primes numbers will always be
distinct. Note that even if two prime numbers provided are same, software
will go ahead and do the key generation. This provision is kept for study
purpose, just to see what happens when primes numbers are same.
Typically, RSA algorithm will not work if two prime numbers are same.
5
