Author Topic: Implementation of RSA Cryptosystem Using Verilog  (Read 6462 times)

0 Members and 1 Guest are viewing this topic.

IJSER Content Writer

  • Sr. Member
  • ****
  • Posts: 327
  • Karma: +0/-1
    • View Profile
Implementation of RSA Cryptosystem Using Verilog
« on: August 20, 2011, 06:13:07 am »
Quote
Author : Chiranth E, Chakravarthy H.V.A, Nagamohanareddy P, Umesh T.H, Chethan Kumar M
International Journal of Scientific & Engineering Research, Volume 2, Issue 5, May-2011
ISSN 2229-5518
Download Full Paper : PDF

Abstract-The RSA system is widely employed and achieves good performance and high security. In this paper, we use Verilog to implement a 16-bit RSA block cipher system. The whole implementation includes three parts: key generation, encryption and decryption process. The key generation stage aims to generate a pair of public key and private key, and then the private key will be distributed to receiver according to certain key distribution schemes. Data security is achieved after the 64-bit input data are block encrypted by RSA public key. The cipher text can be decrypted at receiver side by RSA secret key. These are simulated in NC LAUNCH and hardware is synthesized using RTL Compiler of CADENCE. Netlist generated from RTL Compiler will be used to generate IC.
Index Terms - Cadence, Cryptosystem, Decryption, Encryption, Implementation, Key Generation, Modular Exponentiation, Modular Multiplication, RSA, Verilog.

1   INTRODUCTION

THE first public key scheme was developed in 1977 by Ron Rivest, Adi Shamir, and Len Adleman at MIT. Now Rivest-Shamir-Adleman (RSA) is the most widely accepted and implemented public key cryptosystem. The public key system is based on using different keys, one key for encryption and a different but related key for decryption. The whole process involves computing the remainder after exponential and modular operation of large number. Encryption and decryption have the following form, for some plaintext block M and cipher text block C:

C = M e mod n.
M = C d mod n.

Generally, it includes a third party to generate a pair of public key and to distribute keys to transmitter and receiver. Transmitter and receiver should both know the value of n. The transmitter has the knowledge of public key e, and only the receiver knows the private key d. Thus, a public key of (e, n) and secret key (d, n) generated by third party is distributed to transmitter and receiver separately. For this algorithm to be satisfactory for public-key encryption, the following requirements must be met:

    1. It is possible to find values of e, d, n that M^d*e mod n = M1 for all M < n.
    2. It is relatively easy to calculate M^e mod n and Cd for all values of M < n.
    3. It is infeasible to determine d given e and n.

Steps involved in Implementation of RSA:


The following step is taken to implement the RSA public key scheme:

1. Choose two large prime numbers, p and q. Let n=p*q, Let Ф(n) = (p-1)*(q-1).
2. Randomly choose a value e (1< e < Ф(n)), which is relative prime to Ф(n) that gcd (e, Ф(n)).
3. Calculate d≡e-1 mod Ф(n), send public key (e, n) to transmitter and secret key (d, n) to receiver.
4. Transmitter encrypt the original message, C = M e mod n, then send cipher text to receiver.
5. Receiver decrypt cipher text by
M = C d mod n and retrieve the original message.

The rest of the paper is organized as follows: Section 2 gives an overview of RSA Implementation. Section 3 gives the simulation results. Section 4 gives the conclusion. The final section gives the references used.

2   RSA Implementation

The RSA algorithm was inverted by Rivest, Shamir, and Adleman in 1977 and published in 1978. It is one of the simplest and most widely used public-key cryptosystems. Fig.1 summarizes the RSA algorithm.

The system architecture for key generation is shown in Fig.2. A random number generator generates 16-bit pseudo random numbers and stores them in the rand FIFO. Once the FIFO is full, the random number generator stops working until a random number is pulled out by the primality tester. The primality tester takes a random number as input and tests if it is a prime. Confirmed primes are put in the prime FIFO. Similarly to the random number generator, primality tester starts new test only when prime FIFO is not full. A lot of power is saved by using the two FIFOs because computation is performed only when needed. When new key pair is required, the down stream component pulls out two primes from the prime FIFO, and calculates n and (n). N is stored in a register. (n) is sent to the Greatest Common Divider (GCD), where public exponent e is selected such that gcd((n), e) = 1, and private exponent d is obtained by inverting e modulo (n). E and d are also stored in registers.
Once n, d, and e are generated, RSA encryption/decryption is simply a modular exponentiation operation. Fig.3 shows the RSA encryption/decryption structure in hardware implementation.
   
The core of the RSA implementation is how efficient the modular arithmetic operations are, which include modular addition, modular subtraction, modular multiplication and modular exponentiation. The RSA also involves some regular arithmetic operations, such as regular addition, subtraction and multiplication used to calculate n and (n), and regular division used in GCD operation

2.1   Random Number Generator

Linear Feedback Shift Register (LFSR) is used to generate random numbers. In theory, an n-bit linear feedback shift register can generate a (2n - 1)-bit long  random sequence before repeating. However, an LFSR with a maximal period must satisfy the following property: the polynomial formed from a tap sequence plus the constant 1 must be a primitive polynomial modulo 2. We are unable to find the primitive polynomial for a 16-bit LFSR, so we implemented a 16-bit LFSR and used its least significant 16 bits to generate 16-bit  random numbers. Fig.4 shows the structure of the 16-bit LFSR.

Read More: Click here...