RSA

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 MY) 1. X � b; Y � a (where X>Y) 2. If Y=0 return X=gcd(X,Y) 3. R = X mod Y 4. X � Y 5. Y � R 6. goto 2 4.4 Algorithm for Calculating the Value of ‘d’ Following equation is used for calculating the value of ‘d’ ed = k�(n) + 1 Where, e and �(n) are known Also, k is varied from 1 to 100000 Algorithm: Calculate_d 1. k � 1 2. (Float calculation) d = (�(n) x k +1)/e 3. (Integer calculation) d_dash = (�(n) x k +1)/e 4. If d = d_dash then Return d as the calculated value 5. k � k+1 6. If k=100001 goto 8 7. Goto 2 8. Couldn’t find d 8 RSA 4.5 Algorithm for Encrypting Data The algorithm presented in this section describes how data is encrypted in the software using the public key. Basically for any encryption the formula used is given below Plaintext M, where M