A Project Report

On

Implementation of RSA Algorithm

by
Md Saif H2016124031
Mounesh H2016124024

BIRLA INSTITUTE OF TECHNOLOGY AND SCIENCE, PILANI (RAJASTHAN)

Hyderabad Campus
(NOV 2016)
 ABSTRACT
This paper focuses on asymmetric Public key cryptographic method
called RSA. RSA is one of the first practical public-key cryptosystems
and is widely used for secure data transmission. In such a cryptosystem,
the encryption key is public and differs from the decryption key which is
kept secret. In RSA, this asymmetry is based on the practical difficulty of
factoring the product of two large prime numbers, the factoring problem.
RSA is made of the initial letters of the surnames of Ron Rivest, Adi
Shamir, and Leonard Adleman, who first publicly described the algorithm
in 1977.
A user of RSA creates and then publishes a public key based on two
large prime numbers, along with an auxiliary value. The prime numbers
must be kept secret. Anyone can use the public key to encrypt a message,
but with currently published methods, if the public key is large enough,
only someone with knowledge of the prime numbers can feasibly decode
the message. Hence second half of the paper discusses on security
enhancement of RSA where two ciphers are generated which makes it
difficult to decrypt the, message as to decrypt the message attacker now
need, not only the private key but also random numbers k and s from
which new ciphers are calculated.
 CONTENTS
Cryptography
Basic RSA
Modified RSA
Implementation of Modified RSA
Flow chart showing Modified RSA Encryption
Flow chart showing Modified RSA Decryption
Simulation Results
Discussion on Results
References
Appendix
Cryptography:[1]
Is the practice and study of techniques for secure communication in the
presence of third parties called adversaries. More generally, cryptography
is about constructing and analyzing protocols that prevent third parties or
the public from reading private messages. Modern cryptography exists at
the intersection of the disciplines of mathematics, computer science, and
electrical engineering. Applications of cryptography include ATM cards,
computer passwords, and electronic commerce.
Modern 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 (Attacker)
The modern field of cryptography can be mainly divided into two
cryptographic procedures.
1) Symmetric Cryptography
2) Asymmetric Cryptography [public key algorithm]

Symmetric-key cryptography:
Symmetric-key cryptography refers to encryption methods in which both
the sender and receiver share the same key (or, less commonly, in which
their keys are different, but related in an easily computable way). This was
the only kind of encryption publicly known until June 1976.
Symmetric key ciphers are implemented as either
Block ciphers
Stream ciphers
A block cipher enciphers input in blocks of plaintext.
A stream cipher enciphers input as individual characters.
The Data Encryption Standard (DES) and the Advanced Encryption
Standard (AES) are block cipher designs that have been designated
cryptography standards by the US government. DES remains quite
popular; it is used across a wide range of applications, from ATM
encryption to e-mail privacy and secure remote access.

Asymmetric Cryptography [Public key cryptography]

Is any cryptographic system that uses pairs of keys: public keys which
may be disseminated widely, and private keys which are known only to
the owner.
This accomplishes two functions: authentication, which is when the
public key is used to verify that a holder of the paired private key sent the
message, and encryption, whereby only the holder of the paired private
key can decrypt the message encrypted with the public key.
In a public key encryption system, any person can encrypt a message
using the public key of the receiver, but such a message can be decrypted
only with the receiver's private key. For this to work it must be
computationally easy for a user to generate a public and private key-pair
to be used for encryption and decryption. The strength of a public key
cryptography system relies on the degree of difficulty (computational
impracticality) for a properly generated private key to be determined from
its corresponding public key. Security then depends only on keeping the
private key private, and the public key may be published without
compromising security.
Public key cryptography systems often rely on cryptographic algorithms
based on mathematical problems that currently admit no efficient
solutionparticularly those inherent in certain integer factorization,
discrete logarithm etc. unlike symmetric key algorithms, asymmetric do
not require a secure channel for the initial exchange of one (or more)
secret keys between the parties. Because of the computational complexity
of asymmetric encryption, it is usually used only for small blocks of data,
typically the transfer of a symmetric encryption key. This symmetric key
is then used to encrypt the rest of the potentially long message sequence.
The symmetric encryption/decryption is based on simpler algorithms and
is much faster.
Public key cryptography finds application in, among others, the
information technology security discipline, information security.
Information security (IS) is concerned with all aspects of protecting
electronic information assets against security threats storage.

RSA:[2]
At present, the best known and most widely used public key system is
RSA. It is considered secure when sufficiently long keys are used. The
security of RSA depends on the difficulty of factoring large integers.

The RSA algorithm involves four steps:

1. Key generation
2. Key distribution
3. Encryption
4. Decryption.
RSA involves a public key and a private key. The public key can be
known by everyone and is used for encrypting messages. The intention is
that messages encrypted with the public key can only be decrypted in a
reasonable amount of time using the private key.

1)Key generation:
a) Select any two prime numbers p, q, where p and q should be large.
Typical values for these primes are 512 to 4096bits.
b) Compute
=
c) Compute totient function (n). Totient function counts the positive
integers up to a given integer n that are relatively prime n.
() = ( ) ( )
d) Then public Key e is selected as follows
< < () ((), ) =

e) Private key is is calculated

( ) () =
2) Key Distribution:
Prior to the encryption and decryption, user needs generate public and
private key as mentioned above.
Public key is known to everyone. Anybody who wants to send the
message uses the public key for encryption.
Private key is unique and is known only to intended receiver. Private key
is used to decrypt the cipher and therefore should not be shared with
anyone.
3)Encryption:
To encrypt the message public key is required. The length of message
signal that can be encrypted is bounded by the constraint
<<
In order to increase the length of message to be encrypted large values of
prime number p and q should be chosen.
The encryption of message is
= ^ ( )
4)Decryption: To decrypt the message private key is required.
The decryption of cipher will be
= ( )
RSA explained with Example:
Key generation:
Choose two prime numbers
= =
Compute the product
= = =
Compute totient function
() = ( ) ( ) = =
Choosing Public key
Choose a number e such that
< < () .
=
Compute a value for private key such that it satisfies
( ) % () = .
[( ) % = ]
One of the solutions satisfying above condition is
=

Key Distribution:
Public key is (, ) => (, ) known to everyone
Private key is (, ) => (, ) intended receiver
Encryption:
= ^ ( )
If we want encrypt letter h. ASCII value of h is 104. It is encrypted as
follows
= ( )
comes out as =

Decryption:
= ( )
= ( )
=
Advantages and Disadvantages of RSA
Advantages:
RSA relies on the fact that it is easy to multiply two large prime numbers
together but extremely hard [time consuming] to factor them back to
result.
for ex: the product of 3391 and 23279 can be calculated easily its
78939089 but its extremely difficult to factorize the same number to get
back factors 3391 23279

Disadvantages:
1. If factorization of n [p*q] is possible then whole RSA algorithm is
compromised.
2. Encryption and Decryption takes a long time for large p and q.
Hence we have to bring some modifications which increases the security
of existing algorithm but not at the cost of time

POSSIBLE SOLUTIONS
For Enhancing the security
1. Use of fake modulus i.e. instead of sending n , Fake modulus Fn is
sent over the channel.
2. Instead of using Two prime to calculate n, we can use three prime
there by making factorization more complex.
For Enhancing the Speed
1. Offline key generation
2. Montgomery Multiplication
3. Improving Modular Exponentiation
4. Many more mathematical improvements using concepts of number
theory.
 PROPOSED DESIGN
RSA algorithm can be improved in two areas as mentioned
1)Security
2)Time

We aim to increase the security of Basic RSA algorithm by introducing

randomness in encryption process
In proposed scheme we will be sending two ciphers
One cipher is calculated using random number
The other cipher will contain the information about the message text
1 : from random number selected
2 : from the message text
Attacker has to break two ciphers to retrieve the message
 IMPLIMENATAION
Generation of keys
As compared to basic RSA where 2 keys are generated we will generating
three keys thus increasing the security
Generation of public key e
Choose two large prime numbers p and q find n and totient function (n)
=
() = ( ) ( )

Next we compute "e " as

[, () ] = < < ()
Generation of Private key d
Private key d is calculated using
( ) % () =

Generation of random key k [ Modified part]

we compute k " as
[, ] = < < <
Encryption:
In our modified RSA Encryption is two step process
1) In first step we calculate first cipher using and public key
=
2) In second step we encrypt our message using and public key
= (. )
Final cipher that will sent to receiver is
= [ ]

Decryption:
In our modified RSA decryption is three step process
1) First cipher is decrypted to get random number using private key

= ( )
2) In second step we calculate unique integer using random number
(. ) = such that < <
3) In third step we decrypt cipher using
= ( . )
 Flow Chart Modified RSA Encryption

Input any two large prime

numbers

Whether Input any number Input any number

Prime
e in the range 1<e<() K in the range 1<e<()

n=p*q Whether e Whether k

and () are and () are
() = (p-1)*(q-1) coprime coprime

Plain text

Calculate private key d

Cipher 2
Cipher 1
 Flow Chart Modified RSA Decryption

Receive 1, 2 Input number s

No
Calculate from 1 ( ) = 1

yes

From s and 2 decrypt message

Plain Text
 SIMULATED RESULTS

Basic RSA results

Modified RSA results Example 1:
Modified RSA results Example 2:
Modified RSA results Example 3:
Modified RSA results Example 4:

Discussion on results

Basic version RSA lacks randomization component and if attacker

succeeds in factorizing prime numbers. Then whole system is
compromised.
As we have seen from the results we have increased security by
multilevel encryption and decryption. To decrypt the message attacker,
need, not only private key but also random numbers k and s
 REFERENCES

[1]Ranjan Bose Information theory, coding and cryptography, 2014,

pp. 283-294.
[2]Xin Zhou , Xiaofei Tang, Research and Implementation of RSA
Algorithm for Encryption and Decryption , The 6th International Forum
on Strategic Technology, China,2011
[3]Alaa Hussein Al-Hamami, Ibrahem Abdallah Aldariseh , Enhanced
Method for RSA Cryptosystem Algorithm Advanced Computer Science
Applications and Technologies (ACSAT), 2012 International Conference,
Jordan, 2012
[4]Enhancing Security Features in RSA Cryptosystem, IEEE
Symposium on Computers & Informatics,2012
[5]M. Bahadori, M. R. Mali, O. Sarbishei, M. Atarodi and M. Sharifkhani
A novel approach for secure and fast generation of RSA public and
private keys on SmartCard NEWCAS Conference (NEWCAS), 2010 8th
IEEE International, 2010, pp. 265-268.
[6]H. Ge and S. R. Tate Efficient Authenticated Key-Exchange for
Devices with a Trusted Manager Information Technology: New
Generations, 2006 (ITNG2006). Third International Conference on, 2006,
pp.198-203
 Appendix
MODIFIED RSA:
Main Program
clc;
clearvars;

p=input('enter the value of prime no p\n');

q=input('enter the value of prime no q\n');
[phi,n,d,e,k]=INIT_MOD(p,q);
disp( sprintf( 'The value of n is n= %d\n', n ) );
disp( sprintf( 'The value of Totient function is phi(n)= %d\n', phi ) );
disp ( sprintf( 'The value public key is e= %d\n', e ) );
disp( sprintf( 'The value private key is d= %d\n', d ) );
disp( sprintf( 'The value random number in range (i<k<n) satisfying GCD(n,k)
=1 is k=%d\n', k ) );

[c1]=encryption_MOD(k,e,n);
%m=input('enter the message to be encrypted');
m=input('enter the message to be encrypted\n','s');
x=length(m);
for i=1:x

[c(i)]=text2ascii_MOD(m(i));
[c2(i)]=encryption_MOD_1(k,c(i),e,n);
end
disp( sprintf( 'The value of first cipher is c1= %d\n', char(c1) ) );
disp( sprintf( 'The value cipher Corresponding to message is c2 = %s\n', c2 )
);
[k]=decryption_MOD(c1,d,n);
%disp(k);
[s]=random_MOD(k,n);
disp('the value of number S is');
disp(s);
for j=1:x
Fn(j)=c2(j)*s;
[m(j)]=decryption_MOD(Fn(j),d,n);
end
disp ( sprintf( 'The encrypted message is = %s\n', char(c2) ) );
disp ( sprintf( 'The decrypted message is = %s\n', char(m)) );
Function for Calclation of phi,n,d,e,k
function[phi,n,d,e,k]=INIT(p,q)
n=p*q;
phi=(p-1)*(q-1);
e=1;
i=2;
while i>1

e=e+1;
i=gcd(phi,e);

end

d=1;
j=2;
while j>1

if rem(d*e,phi)~=1
d=d+1;
j=rem(d*e,phi);

end
end
k=5;
i=2;
while i>1

k=k+5;
i=gcd(n,k);

end

end

Function for Encryption

function[en]=encryption_MOD_1(z,c,e,n)
[e]=dtob(e);
k = 65535;
c = c;
cf = 1;
cf=mod(z*c*cf,n);
for i=k-1:-1:1
c = mod(c*c,n);
j=k-i+1;
if e(j)==1
cf=mod(c*cf,n);
end
end
en=cf;
Function for text to ASCII conversion
function[c]=text2ascii(m)
x=length(m);
c=0;
for j=1:x
for i=0:122
if strcmp(m(j),char(i))
c(j)=i;
end
end
end

Function for decimal to binary

function[a]=dtob(d)
i=1;

a=zeros(1,65535);

while d >= 2

r=rem(d,2);

if r==1

a(i)=1;

else

a(i)=0;

end

i=i+1;

d=floor(d/2);

end

if d == 2

a(i) = 0;

else

a(i) = 1;

end
Function for Decryption
function[en]=decryption_MOD(c,e,n)
[e]=dtob(e);
k = 65535;
c = c;
cf = 1;
cf=mod(c*cf,n);
for i=k-1:-1:1
c = mod(c*c,n);
j=k-i+1;
if e(j)==1
cf=mod(c*cf,n);
end
end
en=cf;

Function for generation of random number k

function[d]=random_MOD(e,n)
d=1;
j=2;
while j>1

if rem(d*e,n)~=1
d=d+1;
j=rem(d*e,n);

end
end

end

Function for calculation of s

function[s]=random_MOD(k,n)
s=1;
j=2;
while j>1

if rem(s*k,phi)~=1
d=d+1;
j=rem(s*k,phi);
end
end