Session IVB4

Implementation of the RSA algorithm and its cryptanalysis

Chandra M. Kota and Cherif Aissi1

University of Louisiana at Lafayette, College of Engineering

Lafayette, LA 70504, USA

Abstract
In this paper the implementation of the Rivest-Shamir-Adleman (RSA) encryption algorithm is
presented. The secret key consists of two large prime numbers p and q, and a part of the public
key is their product, n = pq. The RSA cryptosystem security is investigated. It is shown that if
the secret exponent length is approximately one quarter as many bits as the modulus(n), there is a
way to attack the RSA algorithm. The cryptanalysis of the RSA algorithm is also discussed.

Introduction

The RSA is a public key cryptographic algorithm that is used to help ensure data communication
security 1. It is simply based on two main cryptographic processes. First, using a public key it
converts an input data called the plaintext into an unrecognizable encrypted output called cipher
text (encryption process), such that it is impossible to recover the original plaintext without the
encryption password in a reasonable amount of time. Second, using a private key, the RSA then
converts the unrecognizable data back to its original form (decryption process) 2. Today it is used
in web browsers, email programs, mobile phones, virtual private networks and secure shells.
Until recently, the use of RSA was very much restricted by patent and export laws. However, the
patent has now expired and US export laws have been relaxed.

The challenge of RSA is to develop an algorithm in which it is impossible to determine the

private key. This algorithm is based on one-way function. As the name implies, the function is
only one-way i.e. given some input values it is relatively easy to compute the result. However, it
is extremely difficult, nearly impossible to determine the input values given the result .In the
mathematical terms, given x, computing f (x) is relatively easy, but given f (x), computing x is
extremely difficult. The one-way function used by RSA is the multiplication of two very large
prime numbers. It is relatively easy to multiply them but extremely difficult, rather impossible
and time consuming to factorize them.

In this paper, the implementation of the RSA algorithm is presented. Its cryptanalysis is
discussed. It is demonstrated that under a certain condition, a cryptanalytic attack can be
exploited. Several examples to illustrate both the encryption/decryption process are shown.

________________
1
This work was supported by the Louisiana BORSF contract No.LEQSF(1999-2001)-RD-A-47
Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,
The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
 The RSA Model Description
The RSA model is shown in Fig.1.

Encrypted Message
Encryption
Character Process Decryption Original
process Character

Public key Private key

<e,n> <d,n>

Fig 1. RSA Model

The step by step process of the RSA algorithm is as follows

• Generate a public key (e) and a private key (d) by choosing two very large prime
numbers p and q each around 256 bits (75 digits).
• Multiply p and q and let the result be n. n = p • q . Note that the factors p and q remain
secret and n is public. Even if n is known it is not practically feasible to get back p and q
since factorizing a very large number is computationally infeasible.
• Generate a public key by choosing a number e, which is relatively prime to the “totient”
function φ (n) = ( p − 1)(q − 1) .
• Generate a private key by choosing a number d, which is the multiplicative inverse of e
mod φ(n). Note that the public key is <e,n> which is known to everyone and the private
key is <d,n> which is known only to the person who has to decrypt or sign the message.
• Encrypt a message m (< n), raise m to the power e under modulo n .The result is the
cipher text (c).
c = m e mod n
• Decrypt the cipher text, raise the cipher to the power d under modulo n.
m = c d mod n.
• Sign the message by encrypting it with the private key <d, n > and decrypting it with the
public key <e,n>.

The RSA Implementation

In this section, the RSA algorithm implementation using C++ as well as an example of the
encryption and decryption process are shown in Fig.2. Two important issues on how the RSA
works and whether it is secure or not are discussed.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,

The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
 Fig. 2. Implementation of the RSA algorithm

It is important to understand how the RSA algorithm works. When the message m is raised to the
power e under modulo n and the result is again raised to the power d under modulo n. Since e
and d are the multiplicative inverses of each other under modulo φ(n), the original message is
retrieved.
During Encryption: c = m e mod n
During Decryption: m= (c d mod n = ((m e ) d )mod n = (m ed mod φ (n) ) mod n
e.d mod to (n) = 1 since e and d are the multiplicative inverse of each other under modulo φ (n).
(m ed mod φ (n) ) mod n = m.

In the case of signature generation, the message is first raised to the power d and the result is
again raised to the power e, which results in the original message.

Next the RSA security is discussed. The RSA’s security is based on the assumption that factoring
a very large number (150 digits) is very difficult. The best-known factoring methods are slow.
With the best available techniques, factoring a 150 digit number would take about thirty
thousand MIPS –years. So u can assume that this algorithm will survive for the next few years
until a better technique is found. Presumably, RSA can be considered as a secured algorithm.

There are various attacks on RSA that require, among other conditions, either the public or secret
exponent to be short. The shorter secret or public exponent is generally used in order to reduce
the decryption or encryption time. When there is a large difference in the computing power
between two-communication devices use of short RSA exponents is highly advantageous. This
paper discusses the attack on short key exponents using the continued fraction algorithm.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,

The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
 RSA Cryptanalysis

It is thought that breaking the RSA is almost impossible, however several cryptanalytic attacks
have been successful 3. Some of these attacks are known as “common modulus attack”, “small
constant e”, “signing an unknown message”, and “timing attack” 4. In this section, we discuss an
attack where it is shown that if the user is not careful enough in choosing the secret key, i.e. if
the secret key is approximately, one quarter as many bits as the modulus, then there is a way to
attack the RSA algorithm which is based on continued fractions.

Continued Fraction Algorithm 5

Let f and f ' be the fractions and let f ' be an underestimate of f

f ' = f (1 − δ ) for some δ ≥ 0
If δ is small enough then the numerator and the denominator of f can be found using the
continued fraction algorithm.
1
And the sufficient condition to guarantee the success of the algorithm is δ < (A)
3 n d
2 m m
where nm and d m are the numerator and denominator of f .

Applying the algorithm to RSA

The public exponent e and the private exponent d are related by the equation
ed ≡ 1(mod LCM ( p − 1, q − 1)) (1)
where p and q are very large prime numbers.
The public exponent and the secret exponent are inverses of each other. From the above equation
there should exist an integer K such that

ed = K • LCM (( p − 1)(q − 1)) + 1 (2)

Let G = GCD(p-1,q-1) and since LCM (( p − 1)(q − 1)) =
( p − 1)(q − 1) we have
GCD(( p − 1)(q − 1))
K
ed = ( p − 1)(q − 1) + 1 (3)
G
K G
Let k = and g =
GCD(K , G ) GCD( K , G )

Hence ed =
k
( p − 1)(q − 1) + 1 (4)
g
The above equation eliminates the common factors of K and G so that GCD(k , g ) = 1
Dividing the above equation by dpq gives

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,

The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
 g
p + q −1−
e k k
= (1 − δ ) Where δ = (5)
pq dg pq
In the above equation the LHS term is a known term. It consists of public information known to
all.

Also GCD(K , d ) = 1 and since k is a factor of K we have GCD(k , d ) = 1 .

Also GCD(k , g ) = 1 by definition. So GCD(k , dg ) = 1 and hence the continued fraction algorithm
k
can be applied to the above (5) to determine the numerator and denominator of the fraction
provided the value of δ is small enough. dg

Considering the restriction imposed on δ the continued fraction algorithm can be applied, given
that
pq
kdg < (6) from (A)
3
( p + q)
2

Tests to know whether the guess of k and dg are correct:

From (4) we have edg = k ( p − 1)(q − 1) + g

Which says that dividing edg by k yields ( p − 1)(q − 1) as quotient and g as remainder (Assuming
that k > g).

If the guess of ( p − 1)(q − 1) is zero then the guess of k and dg are wrong and hence this case
should be eliminated.
p+q
If the guess of ( p − 1)(q − 1) is not zero then using this we can guess the value of using the
2
following equation

pq − ( p − 1)(q − 1) + 1 p + q
= . (7)
2 2

p+q
If the guess of ( p − 1)(q − 1) is correct then should yield an integer. If not then the original
2
guess of k and dg are wrong.

p+q
If the guess of is correct then we can use this identity
2
2 2
 p+q  p−q
  − pq =   (8)
 2   2 
2
 p−q
to guess the value of   .
 2 
Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,
The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
 2
 p−q
If the guess of   is a perfect square then the original guess of k and dg are correct. If not
 2 
they are wrong and this case should be discarded.
If the guess is correct then the value p and q can be found using the (7) and (8).

Once k and dg are guessed correctly, then d can be calculated using the equation

dg
d= (9)
g
Example

Using the continued fraction algorithm we shall find the private key given the values of n and the
public key e. Let n=1013119 and e = 237905 .
If we want to find d, we can find it only if d is less than n0.25 i.e. if d < 31.725

Calculated Reference i=0 i=1 i=2

Quantity
q' 0 4 3
i
From the 0 1 3
ni '
definition of
Continued
fraction
algorithm
From the 1 4 13
di '
definition of
Continued
fraction
Algorithm
Guess of k From the 1 1 4
dg definition of 1 4 17
Continued
fraction
Algorithm
Guess of edg edg 237905 951620 4044385
Guess of(p-1)(q-1) edg 237905 951620 1011096
k
Guess of g edg mod k 0 0 1
Guess of ( p + q )
(7) NIL NIL 1012
2
D dg 17
g
P (7) & (8) 1117
Q (7) & (8) 907

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,

The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
The above table shows how we arrived at the private key 17 and the two prime numbers P and Q
we have chosen. The table follows the Continued fraction algorithm to find the key. The key is
obtained for i=2.

Combating the continued fraction attack on RSA

There is a way to reduce the maximum size of the secret exponent that can be found using this
attack. From equation 6 it can be seen that by increasing the values of k and g the value of d can
be lowered.
To increase the value of k raise the value of the public exponent e. Let e = ( pq )1.5 then from
the equations 5 and 6 it can be inferred that d < 1. i.e. for e = ( pq )1.5 the continued fraction
algorithm is not guaranteed to work.

Discussion on improvements to the attack on RSA

• The first improvement is to proceed with the continued fraction algorithm beyond the
restriction imposed on d. The algorithm may work slightly beyond the limit. This may
help us to find a bit or more about the secret key.
• The expression giving the limit for the maximum size of the secret key that could be
found using the continued fraction algorithm is an approximation. If taken accurately
then the expression is
2
2  pq − 1 
kdg <
3  p − q 

• The third improvement is to perform on many guesses of k/dg.

Conclusions
In this paper the implementation of the RSA is presented. Its cryptanalysis using the continuous
fraction algorithm to find the short RSA secret key exponents in polynomial time is discussed. It
is shown that it is possible to find the key if it is less than n0.25 . It is worthwhile to mention that
if e is chosen to be greater than ( pq )1.5 then this attack algorithm is not guaranteed to work.

References

1. R. L. Rivest. A. Shamir and L. Adleman, “A method for obtaining digital signatures and public key
cryptosystems,” Commun. ACM, Vol. 21, No. 2, pp. 158-164, Feb 1978.
2. C. Kaufman, R. Perlman, ,M. Speciner, “Network security,” Prentice Hall 1995.
3. M. J. Wiener, “Cryptanalysis of short RSA secret exponents,” IEEE Transaction on Information Theory,
Vol.36, No.3, pp. 553-558, May 1990.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,

The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education
4. Susan Landau, Sun Microsystems. “ A Brief Summary of Attacks on RSA”,
http://www.math.duke.edu/~holden/Math65S/attacks-rsa/
5. D.E.Knuth, Art of Computer Programming Vol. 2/Seminumerical algorithms, New York: Addison
Wesley,1969.

CHANDRA M KOTA
Mr. Kota is currently a graduate student in the center for advanced computer studies (CACS) at the University of
Louisiana at Lafayette. His research interests are in the field of cryptography and cryptanalysis, Networking,
Developing software applications and databases.

CHERIF AISSI
Dr. Aissi currently serves as an Associate Professor of Electronics in the Industrial Technology Department at the
University of Louisiana at Lafayette. His research interests are in the areas of design of microprocessors-based
systems, intelligent microcontrollers, and analysis of nonlinear dynamics of complex systems and design of chaotic
circuits.

Proceedings of the 2002 ASEE Gulf-Southwest Annual Conference,

The University of Louisiana at Lafayette, March 20 – 22, 2002.
Copyright © 2002, American Society for Engineering Education