MINISTRY OF EDUCATION

AND TRAINING

MINISTRY OF DEFENCEMILITARY INSTITUTE OF SCIENCE AND TECHNOLOGY HOANG VAN THUC A STANDARD SYSTEM
FOR SECURITY PARAMETERS
OF RSA CRYPTOSYSTEM AND APPLICATION
Speciality: Mathematical foundation for computer
and computing systems
Code: 62 46 35 01

This thesis can be found at:
- Library of Military Institute of Science and Technology.
- National Library of Vietnam

1

INTRODUCTION
As with all other cryptographic primitives, the model and
algorithm structure of RSA cryptosystem are public. However, a
difficult problem is that how selection and use of the system
parameters for this cryptosystem so that it ensures security and
effectiveness.
Thus, security criteria construction for RSA parameters is still
interested by many scientists. Currently, there are many documents
related to this area are published, for example ANSI X9.31, NIST
800-57, FIPS 186-3.
However, along with the development of cryptography science,
cryptanalysis science developed many new attacks to RSA
cryptosystem. Studying the existing security criteria as well as
studying and proposing new security criteria for RSA parameters are
very necessary.
From the above practical requirements, choosing the topic “A
standard system for security parameters of RSA cryptosystem and
application” for studying is reasonable.

Objective of the research
Studying overview to master the knowledge of RSA

transaction using security RSA parameters. 3

CHAPTER 1
OVERVIEW OF RSA PARAMETER CRITERIA
AND WEB SECURITY PROTOCOLS

To explain the necessary and build a foundation for
implementing the thesis contents, this chapter will present some
results of the related publications.

1.1. DEFINITIONS AND SYMBOLS
Trivial Divisor: Divisors 1, -1, N and -N are called trivial
divisors of the integer number N.
Prime Number: Integer N>1 is a prime number if it has trivial
divisors.
Composite number: Integer N>1 is a composite number if it is
not prime number.
Primality Certificate: Mathematic proof that a given number is
really prime number.
Trial Division: Trial division of N is to check all prime numbers
that are smaller than or equal as N
1/2
to see if they divide N.
Secure strength (secure_strength): A value related to the amount
of work (the number of operations) that is required to crack a
cryptographic algorithm or a cryptosystem. Namely, a cryptographic
algorithm with given parameters is said to have the security level

;
Step 3: Select integer e,
1 ( )
e N

 
, such that

gcd( , ( )) 1
e N


;
Step 4: Compute integer d,
1 ( )
d N

 
, such that
1(mod ( ))
ed N


;
Step 5: RSA public key is (N, e); RSA private key is (N, d);
(N, e, d) is called RSA parameters.
1.2.2. RSA public key encryption primitive
B encrypts a message
*
N

 , if m = m' return “valid
signature”, otherwise return “invalid signature”.

1.2.4. RSA-based cryptosystems
Nowadays, in information security applications, they always use
formative RSA public key encryptions and RSA signature schemes.

5

In those schemes, they use set of the message preparation
functions:
* *
{ : }
N N
G g 
 
. Instead of direct calculation on
message m (primitives schemes), they calculate on
( )
x g m

with
gG.
1.2.5. Security of RSA cryptosystem
Security of RSA cryptosystem based on the intractability of the
modulo N factorization problem.

1.3. PRIME NUMBER GENERATION ALGORITHMS
1.3.1. Probabilistic primality tests
The thesis presents two probabilistic primality tests: Miller-

2 2
nlen
e

  .
Criteria for private exponent d
d=e
-1
(mod lcm(p-1, q-1)) and such that
512 128
2
s
d

 .

1.4.2. Criteria for RSA parameters are presented in FIPS 186-3
and NIST 800-57
Minimum length of RSA modulus
NIST 800-57 recommends the minimum length of RSA modulus
in bits that RSA cryptosystem is secure until the years 2010, 2030
and after 2030
Criteria for primes: p, q
FIPS 186-3 presents 06 criteria for primes p and q, to create RSA
modulus.
Criteria for public exponent e
FIPS 186-3 recommends public exponent e shall be selected
prior to generating the primes p, q and e satisfy: 2
16
< e < 2

Session key for communication will be calculated from
elements: ClientHello.random, ServerHello.random, pre_master_secret. In
that pre_master_secret is encrypted under RSA public key
cryptosystem.
1.5.4. RSA cryptology system and secure web service
RSA public key cryptosystem is used in SSL secure protocol
with the aim of authentication and session key establishment.
However, to apply the RSA parameter for high level security of the
web secure protocol, we need to modify some cryptographic
properties of these applications.

8

1.6. CHAPTER 1 CONCLUSIONS
This chapter presented overview of the results of publications in
Viet Nam and on the world related to the contents of thesis that need
to be solved, discussed and evaluated about the advantages and weak
points, proposed the solutions to overcome the weak points to makes
it better than those results, namely:
 Based on studying the existing secure criteria for parameters of
RSA cryptosystem to find out the necessary of carrying out, to
improve quantification for the exist criteria, build new criteria to
improve the secure for RSA cryptosystem.
(The building and proposing secure criteria for the RSA
parameters will be presented in chapter 2)
 Introduce some prime number generation algorithms and their
properties, choose a reasonable algorithm to build RSA
parameters generation algorithm.
 Study SSL/TLS protocol and the role of RSA cryptosystem in
the above secure protocols, evaluate the application ability of

with the given length of modulus
nlen secure_strength(nlen)
1024 bits 89
1536 bits 106
1792 bits 113
2048 bits 120
Definition 2.2. RSA cryptography system with nlen bit modulus
is secure againsts a given attack if the complexity of this attack is
bigger than 2
secure_strength(nlen)
.
2.1.2. A criterion for the length of RSA modulus
This thesis recommends the minimum length of RSA modulus
with ensuring security until the years 2015, 2020 and 2025 as shown
in Table 2.3 10
Table 2.3: Criteria for the minimum length of RSA modulus
Year nlen
2015 1536 bits
2020 1792 bits
2025 2048 bits
Basis of recommend:
To ensure that RSA cryptosystem can resist a generic attack that
uses NFS algorithm to factorize N.

2.1.3. Criteria for primes p, q
2.1.3.1. Criteria for the prime number generation methods
Primes number p, q and auxiliary primes p

, n
4

1536 bits 212 bits
1792 bits 226 bits
2048 bits 240 bits
Basis of proposal:
To prevent attacks based on properties of primes p, q: Pollard’s

11
p-1 factoring attack, Williams’ p1 factoring attack and William p1
factoring modification attack.
2.1.3.3. Criteria for the length of the primes p, q
p and q shall be selected randomly and satisfy:

  
( / 2) 1 / 2
( 2)(2 ) , (2 1)
nlen nlen
p q
Basis of proposal:
To ensure that RSA cryptosystem can resist the attacks based on
factoring algorithms those complexities depend on the length of
prime factors, and improve the effect of the RSA public key
encryption and signature scheme.

2.1.3.4. Criteria for the length of |p-q|
Table 2.5: Criteria for the minimum length of |p-q|
nlen minimum length of |p-q|
1536 bits 668 bits

Similar to the public exponent, to minimize the computation in
decryption and signature generation, we can select the small private
exponent. However, RSA cryptosystem is easy to be broke through
the attacks such as Wiener’ attack, Boneh and Durfee’s attack.
Boneh and Durfee’s attack is successful if satisfy the following
inequality:
 
1 2
7 1
1 6
6 3
 
   , with
e N

 and
d N

 .
2.1.4.3. Criteria for e and d
The length of public exponent e at least 32 bit.
The private exponent satisfies
0.82
d N .

13
Basis of proposal:
To prevent the attacks mentioned in 2.1.4.1 and 2.1.4.2.
2.2. NEW CRITERIA AGAINST CYCLING ATTACS
2.2.1. RSA period and its properties

Property 2.2. let M divides N. When with all
*
N
m

we
have: |
M N
ord m ord m

Provableness of the Properties 2.1, 2.2 and Lemma 2.2 presented
detail in the thesis.

2.2.2. New criteria against cycling attack
Cycling attack
Input:
*
N
m

;
Output: c satisfy (mod )
e
c N m

;
Algorithm:
Step1: z

m;

are prime factors of
1
p

và
1
q

;
11
p

and
11
q
are prime fators of
1
1
p

and
1
1
q

;and
11
p
,
11

criteria to assure that RSA public key encryption can prevent the
cycling attack.
Criteria for the minimum length of p
11
, q
11

The minimum length of primes factors p
11
, q
11
of p
1
-1, and q
1
-1
as shown in table 2.7.

Table2.7:The minimum length of p
11
, q
11

nlen n
5
, n
6

1536 bits 106 bits
1792 bits 113 bits

, p
2
, q
1
, q
2
are
provable primes.
Criterion PQ2 (the second criterion for the primes p, q):
The minimum length of auxiliary primes p
1
, p
2
, q
1
, q
2as shown
in table 2.4
Criterion PQ3 (the third criterion for the primes p, q):
p and q are selected randomly and satisfy:

  
( / 2) 1 / 2
( 2)(2 ) , (2 1)
nlen nlen
p q
Criterion PQ4 (the fourth criterion for the primes p, q):

1
p
ord e
is multiple of
11
p
and
1
q
ord e
is multiple of
11
q
.

2.4. CHAPTER 2 CONCLUSIONS
In this chapter researched and proposed the criteria for RSA
parameters to improve the security and effectiveness in using RSA
cryptosystem. Criteria were built based on:
 Researching and evaluating the secure of RSA cryptosystem
with the related attacks to propose the existing criteria (08
criteria). Especially, thesis proposed four new quality criteria:
N1, PQ2, D1 and E1.
 Building new criteria, a criterion for primes p, q (PQ6) and a
criterion for the public exponent e (E2), ensuring that for RSA
public key encryption can resist cycling attack. 17
CHAPTER 3

+ n
3
+ n
4
 qlen -
log
2
(qlen) - 2.
 n
0
< nlen - dlen.
3.1.1. The constants and functions are used in the algorithms
 SS[3] = {106; 113; 120}.
 Dlen[3] = {1260; 1470; 1680}.
 PQlen[3] = {768; 896; 1024}.
 random(x) generate random integer y  (0, x-1].
3.1.2. SinhP algorithm (the first prime generation algorithm)
3.1.2.1. Algorithm 3.1
Input: level;
Output: p, p
0
, p
1
, p
11
;
Return value: generates p successful return 1, otherwise return 0.
Algorithm:
Step1: Set plen = PQlen[level]; s = SS[level]; dlen =
Dlen[level]; condlen=log

0
bit;
Step 6: Generate prime
1
p
with the length n
1
bit and
1
1
p

has
prime factor such that
11 1
p
p  ;
Step 7: Generate prime
2
p
with the length n
2
bit;
Step 8: Generate an random integer:




1
2 2 1,2 1


2 0 1
2( ) 1 2
plen
tp y p p   then get
1
0 1 0 1 2
(2 ( 2)(2 ) ) /(2 )
plen
t yp p p p p

 
 
 
 
 
;
Step 12: Compute
2 0 1
2( ) 1
p tp y p p
  
; counter = counter+1
Step 13: Generate random integer
2, 2
a p
 
 
 
;

z

then
get res = 1 and goto step 17;
Step 16: If counter<8plen then get t = t + 1, goto step 11;
Step 17: output (q, q
1
, q
11
) and return res;

3.1.2.2. Algorithm 3.1 analysis
With detailed algorithm 3.1 analysis we have following decision:

19
 Interger p in output of algorithm is prime.
 p
1
is prime factor of p-1 and p
2
is prime factor of p+1
3.1.3. SinhQ algorithm (the second prime generation algorithm)
3.1.3.1. Algorithm 3.2
Input: level, p, p
0
;
Output: q, q
1
, q
11

3
- condlen - 1)
Step 4: Generate prime
1
q
with the length n
3
bit and
1
1
q

has
prime factor is
11 1
q q
 ;
Step5: Gemerate prime
2
q
with the length n
4
bit;
Step 6: Generate a random integer:




1
2 2 1,2 1



2 0 1
2( ) 1 2
qlen
tq y p q   get
1
0 1 0 1 2
(2 ( 2)(2 ) ) /(2 )
qlen
t yp p
q q q

 
 
 
 
 
;
Step 10: counter=counter + 1;
2 0 1
2( ) 1
q tq y p q
  
; if |p-q|


dist to implement:
a. If counter > 8qlen jump to step 15;
b. Set t = t + 1 and return step 9;

tq y q p
z a q

 ;
Step 13: If gcd(u – 1 , q) = 1 and gcd(v – 1 , q) = 1 and
1
z


get res = 1 and goto step 15;
Step 14: If counter

8qlen get t = t + 1 and goto step 9;
Bước 15: give output (q, q
1
, q
11
) and return res;
3.1.3.2. Algorithm 3.2 analysis
Algorithm 3.2 analysis the same with algorithm 3.1 analysis, we
have following affirmation:
 Integer q generated by algorithm 3.2 is prime number.
 q
1
is prime factor of q - 1 and q
2
is prime factor of q +1.
3.1.4. Properties of primes p, q
Using algorithms 3.1 and 3.2 to generate primes p, q, these
primes will satisfy 06 criteria (from PQ1 to PQ6) as presented in

( 1)/
1
mod 1
q q
e q


goto step
2;
Step 4: Compute d = e
-1
mod lmc((p-1),(q-1));

21
Step 5: If
2
log ( )
d dlen

goto step 6, otherwise goto step 2;
Step 6: Output e, d;
3.1.5.2. Algorithm 3.3 analysis
Public exponent e and private exponent d are generated by
algorithm 3.3 satisfy E2 and D1 criteria.
3.1.6. SinhThamSo algorithm
3.1.6.1. Algorithm 3.4
Input: level, elen;
Output: N, e, d;
Algorithm:
Step 1: If

3.2.2. Results
The program runs on PC desktop Dell Optiplex 2100L with the
configuration: CPU Intel Pentium IV 3 GHz, 256 Mb RAM. To
generate each modulus length is 100 set, the running time shown in
Table 3.2.

Table 3.2: security RSA parameters generating runtime
Generating time (second) Modulus
length
(bit)
Fastest Slowest

Total Average
1536 8 234 8234 82,34
1792 11 530 14493 144,93
2048 20 641 29447 294,47 23
3.2.3. Primality evidences
The program store primes p, q p
0
, p
1
, p
2
, q
1
, q
2