RSA - ENCRYPTION ALGORITHM CRYPTOGRAPHY

RSA - ENCRYPTION ALGORITHM . A public key cryptography. Its Description and Uses .

1. PUBLIC KEY CRYPTOGRAPHY-RSA ENCRYPTION
ALGORITHM


Meenakshi Shetti
GENESYS Receipt No:79
Department Of Computer Science And Engineering
K.L.S.Gogte Institute Of Technology
Belgaum, Karnataka, India.
[email protected]


















Muthu Gomathy V
GENESYS Receipt No:130
Department Of Computer Science And Engineering
K.L.S.Gogte Institute Of Technology
Belgaum, Karnataka, India.
[email protected]

2. Abstract—Practice and study of techniques for secure
communication in the presence of third parties is the
cryptography. In this paper we are explaining about
public key cryptography also called as asymmetric key
cryptography where two different keys are used. No
other key can decrypt the message – not even the
original (i.e. the first) key used for encryption. The
beauty of this scheme is that every communicating
party needs just a key pair for communicating with any
number of other communicating parties. Once some one
obtains a key pair, he /she can communicate with any
one else. Here we explain about the wide used
encryption algorithm the RSA algorithm developed in
1977. Which is developed on the basis of Diffie Hellman
key exchange algorithm due to its shortcoming in one
sender and many receiver. In this paper we discuss
about working of RSA algotithm , its application in
various sectors and its weekness and limitations.

I. INTRODUCTION
Cryptography (from Greek means "hidden, secret"
and ,graphein, "writing",respectively) is the practice
and study of techniques for secure communication in
the presence of third parties (called adversaries).
Cryptography is heavily based on mathematical
theory and computer science practice; cryptographic
algorithms are designed around computational
hardness assumptions, making such algorithms hard
to break in practice by any adversary. It is
theoretically possible to break such a system but it is
infeasible to do so by any known practical means.
These schemes are therefore termed computationally
secure; theoretical advances, e.g., improvements
in integer factorization algorithms, and faster
computing technology require these solutions to be
continually adapted. There exist information-
theoretically secure schemes that provably cannot be
broken even with unlimited computing power—an
example is the one-time pad—but these schemes are
more difficult to implement than the best
theoretically breakable but computationally secure
mechanisms.

More generally, it is about constructing
and analyzing protocols that overcome the influence
of adversaries
[3]
and which are related to various
aspects in information security such as
data confidentiality, data integrity, authentication,
and non-repudiation.
[4]
Modern cryptography
intersects the disciplines of mathematics, computer
science, and electrical engineering. Applications of
cryptography include ATM cards , computer
passwords, and electronic commerce.


fig 1. cryptography

II. PUBLIC KEY CRYPTOGRAPHY(PKC)

Public-key cryptography is used where each user has
a pair of keys, one called the public key and the other
private key. Each user’s public key is published while
the private key is kept secret and thereby the need for
the sender and the receiver to share secret
information (key) is eliminated. The only
requirement is that public keys are associated with
the users in a trusted (authenticated) manner using a
public key infrastructure (PKI) . The public key
cryptosystems are the most popular, due to both
confidentiality and authentication facilities. PKC
depends upon the existence of one-way functions, or
mathematical functions that are easy to compute
whereas their inverse function is relatively difficult to
compute. Generic PKC employs two keys that are
mathematically related although knowledge of one
key does not allow someone to easily determine the
other key. One key is used to encrypt the plaintext
and the other key is used to decrypt the ciphertext.
The important point here is that it does not matter
which key is applied first, but that both keys are
required for the process to work . Because pair of
keys are required, this approach is also called
asymmetric cryptography

fig 2. publickey cryptography

3. III. RSA ALGORITHM
The Rivest-Shamir-Adleman (RSA) cryptosystem is
one of the best known publickey cryptosystems for
key exchange or digital signatures or encryption of
blocks of data. RSA uses a variable size encryption
block and a variable size key. The key-pair is derived
from a very large number, n, that is the product of
two prime numbers chosen according to special rules;
these primes may be 100 or more digits in length
each, yielding an n with roughly twice as many digits
as the prime factors. The public key information
includes n and a derivative of one of the factors of n;
an attacker cannot determine the prime factors of n
(and, therefore, the private key) from this information
alone and that is what makes the RSA algorithm so
secure. RSA's safety is due to the difficulty in
factoring large prime numbers. The main arithmetic
operation in the RSA Cryptosystem is modular
exponentiation defined as
C = Me mod n for encryption and
M = Cd mod n for decryption,
where C is the cipher,
M is the message,
e is the public key,
d is the private key and
n is the modulus.
RSA algorithm has some important parameters
affecting its level of security and speed. By
increasing the modulus length plays an important role
in increasing the complexity of decomposing it into
its factors.This will increase the length of private key
and hence difficult to be decrypted without knowing
the decryption key.When the length of message is
changed then the length of encrypted message will
proportionally change, hence larger chunks are
selected to obtained larger encrypted message to
increase the security of the data in use[5]. RSA -1024
bits is good for last 20 years but now Bernstain
described circuitry for fast factorization. It is entirely
possible that an organization with suffientely deep
pockets can build a large scale version of his circuits
and effectively crack an RSA 1024 bit message in a
relatively short period of time, which could range any
where from a number of minutes to some days [7,8].
Time analysis of RSA algorithm performed by varing
its parametes[9].We use natural numbers in pair of
keys in addition to existing parametes of RSA.Then
after simulations of results on basis of speed and
security we compare the RSA and new algorithm .
We use fast modulation method in RSA for big
exponential calculation.
The RSA algorithm is described here


fig 3. how RSA works

fig 4.encryption and decryption
When n is a product of two primes, in arithmetic
operations modulo n, the exponents behave modulo
the totient φ(n) of n.
For example, consider arithmetic modulo
15. since 15 = 3 × 5,
for the totient of 15, we have φ(15) = 2 × 4 = 8. We
can easily verify the following:
5
7
.5
4
?????????????????? 15 = 5
(7+4)��� 8
?????????????????? 15 = 5
3
?????????????????? 15
=125 ?????????????????? 5
(4
3
)
5
?????????????????? 15 = 4
(3∗5)��� 8
?????????????????? 15=4
7
mod 15=4
Considering arithmetic modulo n, let’s say that e is
an integer that is coprime to the totient φ(n) of n.
Further, say that d is the multiplicative inverse of e

4. modulo φ(n). These definitions of the various
symbols are listed below for convenience:
n = a modulus for modular arithmetic
φ(n) = the totient of n
e = an integer that is relatively prime to φ(n)
[T his guarantees that e will possess a
multiplicative inverse modulo φ(n)]
d = an integer that is the multiplicative
inverse of e modulo φ(n)
Now suppose we are given an integer M, M < n, that
represents our message, then we can transform M
into another integer C that will represent our cipher
text by the following modulo exponentiation:
C = ??????
&#3627408466;
mod n
At this point, it may seem rather strange that we
would want to represent any arbitrary plaintext
message by an integer. But, it is really not that
strange. Let’s say you want a block cipher that
encrypts 1024 bit blocks at a time. Every plaintext
block can now be thought of as an integer M of value
0 ≤ M ≤ 2
102 4
−1.
We can recover back M from C by the following
modulo operation
M = ??????
&#3627408465;
mod n
since
(??????
&#3627408466;
)
&#3627408465;
(mod n) = ??????
&#3627408466;&#3627408465;(&#3627408474;&#3627408476;&#3627408465; φ(&#3627408475;))
≡ M (mod n)
1. The RSA Algorithm — Putting To Use The
Basic Idea
The basic idea described in the previous subsection
can be used to create a confidential communication
channel in the manner described here.
An individual A who wishes to receive messages
confidentially will use the pair of integers {e, n} as
his/her public key. At the same time, this individual
can use the pair of integers {d, n} as the private key.
The definitions of n, e, and d are as in the previous
subsection.
Another party B wishing to send a message M to A
confidentially will encrypt M using A’s public key
{e, n} to create cipher text C. Subsequently, only A
will be able to decrypt C using his/her
private key {d, n}.
If the plaintext message M is too long, B may choose
to use RSA as a block cipher for encrypting the
message meant for A. When RSA is used as a block
cipher, the block size is likely to be half the number
of bits required to represent the modulus n. If the
modulus required, say, 1024 bits for its
representation, message encryption would be
based on 512-bit blocks. [While, in principle, RSA
can certainly be used as a block cipher, in practice it
is more likely to be used just for exchanging a secret
session key and, subsequently, the session key used
for content encryption using symmetric-key
cryptography based on, say, AES.]

2. How To Choose The Modulus For The Rsa
Algorithm?
With the definitions of d and e, the modulus n must
be selected in such a manner that the following
is guaranteed:
(??????
&#3627408466;
)
&#3627408465;
≡ ??????
&#3627408466;&#3627408465;
≡ M (mod n)
We want this guarantee because C = ??????
&#3627408466;
mod m is the
encrypted form of the message integer M and
decryption is carried out by
??????
&#3627408465;
mod n.
It was shown by Rivest, Shamir, and Adleman that
we have this guarantee when n is a product of two
prime numbers:

n = p × q for some prime p and prime q
(1)

The above factorization is needed because the proof
of the algorithm, presented in the next subsection,
depends on the following two properties of primes
and coprimes:

1. If two integers p and q are coprimes (meaning,
relatively prime to each other), the following
equivalence holds for any two integers a and b:

{a ≡ b (mod p) and a ≡ b (mod q)} ⇔ {a ≡ b (mod
pq)} (2)

This equivalence follows from the fact a ≡ b (mod p)
implies a − b = k1p for some integer??????
1. But since we
also have a ≡ b (mod q) implying a−b = ??????
2??????, it must
be the case that ??????
1= ??????
3× q for some ??????
3. Therefore,
we can write
a−b = ??????
3×p×q, which establishes the equivalence.
(Note that this argument breaks down if p and q have
common factors other than 1.)

2. In addition to needing p and q to be coprimes, we
also want p and q to be individually primes. It is only
when p and q are individually prime that we can

5. decompose the totient of n into the product of the
totients of p and q. That is

φ (n) = φ (p) × φ (q) = (p − 1) × (q − 1)
(3)


So that the cipher cannot be broken by an exhaustive
search for the prime factors of the modulus n, it is
important that both p and q be very large primes.
Finding the prime factors of a large integer is
computationally harder than determining its
primality.

We also need to ensure that n is not factorizable by
one of the modern integer factorization algorithms.

IV. APPLICATIONS
When it comes to assymetric cryptography the most
popular and widely used application that comes to
anyone's mind is PGP. PGP stands for “Pretty Good
Privacy” and is the standard public key cryptography
application used today. In the examples of this
project we chose to use PGP Desktop. The reason for
this choice is that PGP Desktop is easier to use than
other text-based versions of PGP such as gnuPGP.
PGP Desktop provides us with a very intuitive GUI
accessible from the Windows Start Menu ,the PGP
taskbar icon and from Windows explorer (shell
integration). So from now on, every time we mention
PGP, we will be referring to the PGP Desktop
version.

V. ADVANTAGES
1. Convenience: It solves the problem of
distributing the key for encryption.Everyone
publishes their public keys and private keys
are kept secret.
2. Provides for message authentication: Public
key encryption allows the use of digital
signatures which enables the recipient of a
message to verify that the message is truly
from a particular sender.
3. Detection of tampering: The use of digital
signatures in public key encryption allows
the receiver to detect if the message was
altered in transit. A digitally signed message
cannot be modified without invalidating the
signature.
4. Provide for non-repudiation: Digitally
signing a message is akin to physically
signing a document. It is an
acknowledgement of the message and thus,
the sender cannot deny it.
VI. Disadvantages
1. Public keys should/must be
authenticated: No one can be absolutely
sure that a public key belongs to the person
it specifies and so everyone must verify that
their public keys belong to them.
2. Slow: Public key encryption is slow
compared to symmetric encryption. Not
feasible for use in decrypting bulk messages.
3. Uses up more computer resources: It
requires a lot more computer supplies
compared to single-key encryption.
4. Widespread security compromise is
possible: If an attacker determines a person's
private key, his or her entire messages can
be read.
5. Loss of private key may be irreparable: The
loss of a private key means that all received
messages cannot be decrypted.

VII. CONCLUSION
We have proposed a method for implementing a
public-key cryptosystem whose security rests in part
on the difficulty of factoring large numbers. If the
security of our method proves to be adequate, it
permits secure communications to be established
without the use of couriers to carry keys.
The security of this system needs to be examined in
more detail. In particular, the difficulty of factoring
large numbers should be examined very closely.
Once the method has withstood all attacks for a
sufficient length of time it may be used with a
reasonable amount of confidence.
VIII. REFERENCES
1. Frederick J. Hirsch. "SSL/TLS Strong
Encryption: An Introduction". Apache HTTP
Server. Retrieved 2013-04-17.. The first two
sections contain a very good introduction to
public-key cryptography.
2. N. Ferguson; B. Schneier (2003). Practical
Cryptography. Wiley. ISBN 0-471-22357-3.

6. 3. J. Katz; Y. Lindell (2007). Introduction to
Modern Cryptography. CRC Press. ISBN 1-
58488-551-3.
4. A. J. Menezes; P. C. van Oorschot; S. A.
Vanstone (1997). Handbook of Applied
Cryptography. ISBN 0-8493-8523-7.
5. IEEE 1363: Standard Specifications for
Public-Key Cryptography