An Efficient Implementation of RSA Digital

Signature Algorithm

Chong Fu Zhi-liang Zhu

School of Information Science and Engineering, Software College,
Northeastern University, Northeastern University,
Shenyang 110004, P.R.China Shenyang 110004, P.R.China
E-mail: [email protected] E-mail: [email protected]

Abstract—RSA is the most widely used digital signature flaw of RSA algorithm either for hardware or software
algorithm in E-Commerce and the complexity of large integer implementation, so how to design an effective large number
operation is the main factor that affects the efficiency of a RSA operation scheme is an important question [1-3]. In this paper,
system. In this paper, a n carry array based large integer a n carry array based large number denotation approach is
denotation approach is proposed to speed up the large integer proposed to reduce the complexity of large number operation.
calculation in RSA key generation and data encryption/ The simulation results indicate that the speed of proposed
decryption process, so as to improve the efficiency of a RSA algorithm has an efficient improvement over classic string
system. The RSA digital signature algorithm and its mathematic based large number operation method.
foundation are discussed in detail and the feasibility of RSA
algorithm is proved. An integrated large integer library is built
by using C++ and the implementations of Miller-Rabin, extended II. THE RSA DIGITAL SIGNATURE ALGORITHM AND ITS
Euclid and Montgomery algorithms for complex numeric MATHEMATICAL FOUNDATION
operations in RSA are given.
A. The Mathematical Foundation for RSA Algorithm
Keywords- digital signature; RSA; E-Commerce; n carry The RSA digital signature has precise mathematical
array foundations, which are as follows:

I. INTRODUCTION Theorem 1 (fundamental theorem of mathematics) Any

positive integer a can be denoted as a = p1a1 p 2a2 " p tat , in
The emergence and development of data encryption
which P1 > P2 > P3 " > PT are all prime numbers, ai > 0 .
technology provides an important guarantee for global E-
Commerce, which makes the Internet based electrical trade-off Theorem 2 (Euclid theorem) Any two integers a and b has
be feasible. The main purpose of digital signature technology a greatest common factor d, in which d can be expressed as the
in E-Commerce is guarantees the confidentiality, linear combination of a and b with integer coefficient, namely
authentication, data integrity and undeniable of the information
that transformed in insecurity and unreliable network. Until s, t ∈ Z , which satisfies d = sa + tb .
now, there are many digital signature algorithm established, in Theorem 3 (Fermat theorem) If p is a prime number, then
which the Hash, DSA and RSA are the common ones. The for any positive integer a that prime to p, a p −1 ≡ 1(mod p ) .
main restriction of Hash algorithm is the receiver must have a
copy of the sender’s private key to verify the signature, so the Definition 1 (Euler function ϕ (n) ) When n = 1 , ϕ (1) = 1 ;
encryption system is easy to be attacked and the signature can when n > 1 , the value of ϕ (n) is the amount of positive
be forged. DSA˄Digital Signature Algorithm˅ is another
integer that less than n and prime to n.
common public key algorithm, but it has no data encryption
function, it can only be used for digital signature. Compared Theorem 4 If p and q are all prime numbers and p ≠ q ,
with Hash algorithm, the private key for generating signature in then
RSA system only stores in user’s computer, it is more secure
than Hash algorithm. While compared with DSA algorithm, ϕ ( pq ) = ϕ ( p )ϕ ( q ) = ( p − 1)( q − 1) .
RSA can either be used for data encryption or digital signature,
which makes it be the most widely used public key algorithm. Theorem 5 (Euler theorem) If integer a is prime to integer
In order to guarantee the security of a RSA system, the length b, then a ϕ ( n ) ≡ 1(mod m) .
of public and private keys is usually greater than 1024 bits in
current commerce use, thus the key generation and data Above theorem have the following 3 deductions:
encryption/decryption process are all large number operations, (1) If p is prime number and n = p , then
which makes the speed of a RSA algorithm about 100 times p −1
slower than DES algorithm. The processing speed is a major a ≡ 1(mod p ) , namely the Fermat theorem;

978-1-4244-2108-4/08/$25.00 © 2008 IEEE 1

 (2) a ϕ ( n +1) ≡ a (mod n ) ; Theorem 6 If p and q are prime numbers and p ≠ q ,
rm ≡ 1 ( mod ( p − 1)( q − 1)) , a is any positive integer,
(3) If n = pq ˈp and q are prime numbers and p ≠ q ,
b ≡ a m mod pq , c ≡ b r mod pq , then c ≡ a mod pq .
for 0 < m < n , if ( m , n ) = 1 , then m ϕ (n )+1 ≡ m(mod n) ,
namely m ( p −1)( q −1)+1 ≡ m(mod n) . Proof. Because rm ≡ 1 ( mod ( p − 1)(q − 1)) ,

Above five theorems will be used in the feasibility proof of so rm = k ( p − 1)( q − 1) + 1 , k ∈ N ,

RSA digital signature algorithm in the following section.
thus c ≡ b r ≡ a m ≡ a rm ≡ a k ( p −1)( q −1) +1 mod pq .
r

B. RSA digital signature algorithm There are four conditions to be discussed in the followings.
RSA digital signature algorithm is described as follows:
(1) a is not multiple of both p and q.
(I) Selecting two prime number p and q. In practice E-
commerce application, the length of p and q should be the same According to Fermat theorem,
and greater then 1024 bits in order to guarantee the security. a ( p −1) ≡ 1 (mod p ) , a
( q −1)
≡ 1 (mod q) ,
Calculating the product
n = pq . so a k ( p −1)( q −1) ≡ 1 (mod q) , pq | a k ( p −1)( q −1) − 1 .

(II) Selecting a stochastic key e for data encryption, in thus a k ( p−1)( q −1) ≡ 1 (mod pq) ,
which e is prime to ( p − 1)(q − 1) .
c ≡ a k ( p −1)( q −1) +1 ≡ a (mod pq )
(III) Calculating out the key d for data decryption by using
Euclid algorithm, in which d satisfies (2) a is multiple of p but not q.

ed ≡ 1 ( mod( p − 1)( q − 1)) . According to Fermat theorem,

a ( q −1) ≡ 1 (mod q ) ,
So d = e −1 (mod( p − 1)( q − 1)) , in which d is also prime to
n. so a k ( p −1)( q −1) ≡ 1 (mod q ) , c ≡ a k ( p−1)(q−1) +1 ≡ a (mod q) .
(IV) e and n are the public key and should be published,
thus q | c − a .
while d as the private key should be keep secret strictly. The
two prime number p and q are no longer needed and should be because p | a ,
discarded right now, the leak out will lead to the whole
signature system out of use. so c ≡ a k ( p−1)(q −1) +1 ≡ 0 (mod p) , p | c − a ,
The private key e is used to encrypt the plaintext when
sending information to others. If the receiver can decrypt the thus pq | c − a ˈ c ≡ a (mod pq) .
ciphertext by using the public key d, then it proves the (3) a is multiple of q but not p.
information is from you, which implements the signature
mechanism. The public key d is used when others sending The proof process is the same as (2).
information to you, and only you that have the private key e (4) a is multiple of both p and q.
can decrypt the information. When encrypt information m, it
should be disassembled to binary groups smaller than n bits Because pq | a ,
long. Namely, if the length of p and q are k, then the length of n
is 2k, it requires the length of each information fragment mi so c ≡ a k ( p−1)( q−1) +1 ≡ 0 (mod pq) ,
smaller than 2k. The encrypted ciphertext is composed of the
same length fragments ci. The encryption process can be thus pq | c − a , c ≡ a (mod pq) .
described as:
Theorem 6 indicates that when the message mi encrypts to
c i = mi (mod n) .
e
ci, the decrypted message from ci satisfies xi mod pq ≡ mi . So
the encryption and decryption process require 0 ≤ mi < n and
When decrypting the ciphertext, select each encrypted
fragment ci and calculates 0 ≤ xi < n , which guarantees xi ≡ mi .
The security of RSA algorithm depends on the fact that for
xi = ci (mod n) ≡ mi .
d
a very large number n, we have no efficient method to divide it
until now. So the private key e can not be calculated out from n
The feasibility of RSA digital signature algorithm is proved and d. Similarly, d also can not be calculated from n and e. The
as follows, namely xi ≡ mi . attack difficulty equivalence to the division of the product of
two large prime numbers, therefore the RSA algorithm has
high security.

978-1-4244-2108-4/08/$25.00 © 2008 IEEE 2

 III. AN EFFICIENT IMPLEMENTATION OF RSA ALGORITHM t = 5 , the probability that N is a prime number is 99.99%. The
worst case is that N contains smaller prime factor. In this
A. A n carry array storage structure for large number function, 600 small prime numbers is used for testing, so the
The most import stage in RSA application is the key reliability is guaranteed.
generation process, the selection of large prime number p and q (2) Extended Euclid Function
to construct modulo n is crucial. In practice application, n must
be large enough in order to guarantee the security of a RSA Function: calculation the multiplicative inverse of integer
system. So the efficiency of a RSA system depends on the N.
large number calculation speed. Most compilers support 64 bits Invoking method: N.Euc(A).
integer operation at present, the integers calculated must equal
or less than 64bits, namely 0xffffffffffffffff Return value: Y2, which satisfies NY2 mod A = 1 .
(18446744073709551615), which is far short than the RSA
algorithm requires. The classic large number storage method is Algorithm description:
string based, a large number is stored in a character type array, ķ Let c = gcd( a, b) denotes the greatest common factor of
then we can construct the corresponding function to perform
add, subtract, multiply and divide operation based on the array. a and b;
But the efficiency of this scheme is very low because for a ĸ ( X 1 , X 2 , X 3 ) ← (1,0, A) ; (Y1 , Y2 , Y3 ) ← (1,0, N ) ;
1024 bits number, the length of decimal form is about several
hundreds, any numeric operation should do multiple nested Ĺ If Y3 = 0 then return X 3 = gcd( A, N ) ; no inverse;
loop on two long character array, besides a large extra space is
needed to store the carry flag and middle results, which leads to ĺ If Y3 = 1 then return Y3 = gcd( A, N ) ; Y2 = N −1 mod A ;
the heavy system resource occupy and low efficiency [4-6].
This paper proposes an n carry array beads large number Ļ Q = «X3 »;
storage scheme. For a 32 bits system, n can be 2 powers of 32, « »
¬ Y3 ¼
namely 0x10000000. If a 1024 bits large number converts to
0x10000000 carry, its length should be 32, the range of each ļ (T1 , T2 , T3 ) ← ( X 1 − QY1 , X 2 − QY2 , X 3 − QY3 ) ;
digit is 0~0xffffffff rather than 0~1 or 0~9. Each digit of a n
carry number just can be stored in a unsigned long integer type Ľ ( X 1 , X 2 , X 3 ) ← (Y1 , Y2 , Y3 ) ;
unit, so a 1024 bits large number can be stored in a unsigned
long array with 32 elements. Then we can implement numeric ľ (Y1 , Y2 , Y3 ) ← (T1 , T2 , T3 ) ;
operation on the array, the loop time is reduced to 32, the
calculation speed is greatly improved. Ŀ goto ĸ.
The variables used in the algorithm have the following
B. Complex numeric operation function relationships:
In order to deal with the complex numeric mathematical
operation efficiently, the following 3 functions are constructed AT1 + NT2 = T3 ; AX 1 + NX 2 = X 3 ; AY1 + NY2 = Y3 .
in RSA system implemented. (3) Montgomery Function
(1) Miller-Rabin Function Function: calculation the modulo of power.
Function: prime number judgment. Invoking method: N.Mon(A, B).
Invoking method: N.Rab().
Return value: X = N A mod B .
Return value: if N is prime, return 1, else return 0.
Algorithm description:
Algorithm description:
ķ X = 1;
ķ Calculating M, which makes N = (2 r ) M + 1 ;
ĸ If A is odd, then A = A − 1 , X = X * N mod B ;
ĸ Selecting a random number A < N ;
Ĺ If A is even, then A = A / 2 ˈ N = N * N mod B ;
Ĺ If A M mod N = 1 or for any i < r ,
i ĺ Repeating step (2) and (3) to reduce the order A, until
A 2 M
mod N = N − 1 , then N passes the testing of random A= 0;
number A;
Ļ The final calculated X is the result we want.
ĺ Testing N 5 times, each time with different A, if all the 5
times testing are passed, then N is prime.
IV. CONCLUSION
If N passes one testing, then the probability that N is not a The random RSA public and private key pair with arbitrary
prime number is 25%. If t times testing are passed, then the
length can be generated effectively by using the C++ large
probability that N is not a prime number is (1 / 4) t . When number library design by the algorithm proposed in this paper.

978-1-4244-2108-4/08/$25.00 © 2008 IEEE 3

A 1024 bits RSA key can be generated within 2 minutes on [2] Y Frankel, PD MacKenzie, M Yung, STOC. (1998), “Robust Efficient
common PC platform, while the encryption/decryption Distributed RSA-Key Generation”, Proceedings of the thirtieth annual
ACM symposium on Theory of computing, pp 663-672.
operation on data less than 1024 bits can be done within 2
[3] R Gennaro. (2000), “RSA-Based Undeniable Signatures”, Journal of
seconds, the efficiency of RSA system is greatly improved, Cryptology, Vol 13, No. 4, pp 397-416.
which provides important guarantees for implementation high [4] R Cramer, V Shoup. (2000), “Signature schemes based on the strong
security RSA algorithm with long keys on PC platform. RSA assumption”, ACM Transactions on Information and System
Security, Vol 3, No 3, pp 161-185.
REFERENCES [5] R Gennaro. (2000), “Robust and Efficient Sharing of RSA Functions”,
Journal of Cryptology, Vol 13, No 2, pp 273-300.
[1] MJ Wiener. (1990), “Cryptanalysis of short RSA secret exponents”,
[6] D Boneh, M Franklin. (2001), “Efficient generation of shared RSA
IEEE Transactions on Information Theory, Vol 36, No 3, pp 553-558.
keys”, Journal of the ACM, Vol 48, No. 4, pp 702-722.

978-1-4244-2108-4/08/$25.00 © 2008 IEEE 4