04-10-2012, 04:21 PM
RSA CRYPTOSYSTEM :IMPLEMENTATION & ATTACKS
RSA CRYPTOSYSTEM.pdf (Size: 686 KB / Downloads: 55)
ABSTRACT
This Project Report gives a description of the famous RSA cryptosystem and
also discusses some of the attacks made on the same. As a part of this project I
have implemented the RSA algorithm in C language. The attacks are also
implemented in C1. As RSA deals with large numbers and that C has a limit of
around 109 for integers, I have used the GNU MULTIPLE PRECISION2(GMP)
library in order to deal with large numbers. GMP chooses algorithms based on the
size of numbers used. Hence,an effective and efficient implementation of RSA is
possible.
RSA requires that we generate large primes p&q(essentially unequal and are
private).Efficient and probabilistic algorithm “MILLER-RABIN TEST FOR
PRIMALITY” is used for this purpose. Euclidean algorithm is used for some modular
calculations. I have implemented Wiener's attack and attacks when the two primes are
close. Wiener's attack uses concept of continued fractions,with some constraint to the
decryption exponent it can be shown using Wiener's theorem that n=pq can be factorized
in polynomial time,detailed explanation of which follows in the later part of the report.
Two cases under close primes have been explored. Here the property that the arithmetic
mean of two positive integers is greater than or equal to their geometric mean
is used. Similar cases can be derived based on these cases.
INTRODUCTION
ABOUT PUBLIC-KEY CRYPTOGRAPHY:
One of the oldest and still prevailing model of encryption-decryption scheme is
symmetric key cryptography. In this model there is a message 'm' which belongs to a message
space M,there are two algorithms called encryption algorithm which uses a key 'k' from key
space K to encrypt the message and decryption algorithm which uses the same key or some
variant of the key 'k' to decrypt the message. Security of this method depends on the
algorithm used for encryption and decryption. One of the problems related to this method is
that the key which is private should be shared secretly.
This is where public-key cryptography plays its role. In public-key cryptography the
encryption and decryption key used are not the same. Say there is some message transfer
taking place between Alice and Bob. There is a key pair (eb , db) for Bob and pair (ea , da) for
Alice. Now consider the case where Bob wants to send a message to Alice. Alice publishes
her public key(ea). Bob uses this key to encrypt the message. To decrypt the message Alice
uses her private key(da). Bottom line is that the message is safely transmitted and there was
no problem of information about the key being leaked. Credits goes to Whitefield Diffie and
Martin Hellman of Stanford University(1976) who found this kind of a system .
Diffie-Hellman Key exchange
Assume now that, Alice and Bob, want to exchange a secret key 'k'.Alice computes
the value ga mod p and sends it to bob. Here, g is a generator of an abelian,cyclic group G(In
fact,G Zp,*)) and 'p' is a prime. a ε Zp-1.Now Bob computes a value gb mod p and sends it to
Alice. Again here b ε Zp-1.Now both Bob and Alice compute the value gab mod p.This is their
secret key 'k'. Now consider a third person who wants to know the key. He has access to
values ga and gb from which he is supposed to calculate the value of gab.. This computationally
a hard problem to solve. Hence the security of the system.
APPLICATIONS
The RSA cryptosystem is currently used in a wide variety of products, platforms,
and industries around the world. It is found in many commercial software products and
is planned to be in many more. In hardware, the RSA algorithm can be found in secure
telephones, on Ethernet network cards, and on smart cards. In addition, the algorithm is
incorporated into all of the major protocols for secure Internet communications,
including S/MIME, SSL, and S/WAN.
ABOUT GMP [1]:
GMP is a free library for arbitrary precision arithmetic, operating on signed
integers, rational numbers, and floating point numbers. There is no practical limit to the
precision except the ones implied by the available memory in the machine GMP runs on.
GMP has a rich set of functions, and the functions have a regular interface.
The main target applications for GMP are cryptography applications and research,
Internet security applications, algebra systems, computational algebra research, etc.
GMP is carefully designed to be as fast as possible, both for small operands and for
huge operands. The speed is achieved by using fullwords as the basic arithmetic type, by
using fast algorithms, with highly optimized assembly code for the most common inner
loops for a lot of CPUs, and by a general emphasis on speed.
GMP is faster than any other big number library. The advantage for GMP increases
with the operand sizes for many operations, since GMP uses asymptotically faster
algorithms.
The first GMP release was made in 1991. It is continually developed and
maintained, with a new release about once a year.
RUN-TIME ANALYSIS:
The RSA cryptosystem involves generation of large primes and large modular
exponentiation. For prime generation MILLER-RABIN test is used. This test runs in
time O((log n)3),n being the product of primes. For large modular exponentiation an
efficient algorithm called square and multiply is used. This also runs in O((log n)3). This
algorithm has to be run (log n) times and each time it runs, under the worst case
scenario, it requires 2 log n modular multiplications and each multiplication takes (log
n)2 time. Hence, it requires (log n)3 time.