MINISTRY OF EDUCATION AND TRAINING
MINISTRY OF NATIONAL DEFENCE
ACADEMY OF MILITARY SCIENCE AND TECHNOLOGY
LE QUANG HUY
RESEARCH AND DEVELOPMENT OF
RSA KEY GENERATION BACKDOORS
Major
: Mathematical foundation for informatic
Major code: 9 46 01 10
SUMMARY OF PH.D THESIS
HA NOI - 2018
The dissertation has been accomplished at: Academy of Military
Science and Technology – Ministry of National Defence
Supervisor:
1. Assoc. Prof. Ph.D Bach Nhat Hong
2. Ph.D Tran Duy Lai
Reviewer 1: Prof. Ph.D Nguyen Binh
Reviewer 2: Assoc. Prof. Ph.D Nguyen Linh Giang
Reviewer 3: Ph.D Luu Hong Dung
The thesis will be defended in front of PhD thesis
examination Committee at Academy of Military Science and
Technology in … hour on …....
The thesis could be found at:
- The Library of Academy of Military Science and Technology
- The National Library of VietNam.
1
INTRODUCTION
1. Dissertation's necessity
The development of society leads to the need for information
exchange. Internet development has led to security information
problems. The best solution now is to use cryptography, public key
cryptography to secure network transactions. However, while public key
cryptography has been used, there has had events that cryptography has
used to commit illegal acts, crimes. There is a need to recover or decrypt
encrypted data to protect community.
There are three most common ways to get plaintext from ciphertext:
1. Get decrypted key through people: stealing / bribery: only possible
with some random and specific cases.
2. Exploit vulnerabilities of cryptographic products that are
deliberately created: Using backdoor has the disadvantage of reducing
key space, but has the advantage of speeding up plaintext recover, fixing,
low costs deployment, difficulty to detect when installed in black box
cryptographic products.
3. Cryptanalysis (break cryptosystem by mathematical methods):
Some results have been achieved, but with the development of modern
cryptosystems, it is becoming more and more difficult and not feasible
in terms of cost, effort and time.
In recent years, some government agencies and businesses have been
found to put backdoor into cryptographic products and into
cryptographic standards. In addition, serveral backdoor crypto studies
have been published and focus more on RSA cryptosystems. Nowaday,
cryptographic backdoor studies have been reported or have been detected
in small numbers and quality, but more effort is needed to improve them.
Using cryptography, there are two simultaneous needs: the need to
protect information by cryptosystem and the need to break cryptosystems
to secure for community. The more widely used cryptography is, the
greater the need for security. Currently, cryptographic product using in
the world and in Vietnam have taken place more and more, bringing the
need to ensure the security of the community increasingly urgent.
2
From practical usage, needs, current research, deployment of
cryptographic backdoor, the candidate choosed the topic "Research,
development of RSA key generation backdoor algorithms" to study
security issues for PKI application, against the use of PKI to commit
criminal acts. Specifically, the thesis deals with a narrow issue of " RSA
key generation backdoor algorithms", applied to ensure security of PKI.
2. Objects and scope of the research
2.1. Objects of the research
Seeking effective key generation backdoor algorithms that could be
applied to secure PKI.
2.2. Research duties
- Research models, effective formal tools for analyzing and
evaluating backdoors.
- Search for extracting, embedding backdoor methods, methods of
recovering private key from public key of backdoor.
- Proposes some key generation backdoor algorithms comply
specific standard (eg FIPS 186-4).
- Install, test key generation backdoor algorithms in cryptographic
black box modules.
3. Subjects and scope of study
3.1. Research subjects
- Theoretical model, formal tool, criteria for evaluating backdoor
algorithms in cryptosystems.
- Backdoor creation methods (extract, embed information).
- Method of recovering private key frome backdoor public key.
3.2. Research scope
Key generation, recovering private key on RSA cryptosystem.
4. Theoretical foundation, practice and research methodology
4.1. Theoretical foundation
- Backdoor theory in cryptosystems: to get knowledge of
cryptographic backdoor analysis and evaluation.
- RSA cryptosystem: to study RSA cryptographic algorithms and
3
relevant standards.
- Factoring method: to study methods of searching solution for
modulo polynomial equation to factor the prime p, of the RSA modulus
n.
4.2. Practice
- Demand of public key infrastructure provider re-provides user's
private key without maintaining a private key database.
- The need to recover plaintext from ciphertext by security agencies
(when not aware of user's private key).
- Provides users with insights to identify and prevent backdoor
attacks when using cryptographic black box products.
4.3. Research Methods
Research method: modeling, experiment.
5. The composition of the thesis
In addition to the preamble, conclusions, published scientific works,
reference materials, the thesis focuses on three chapters:
Chapter 1: Backdoor background in key pair generations
Backdoor background presentation: modeling tools, backdoor
assessment criteria; Coppermith's method for factoring; FIPS 186-4
standard, some backdoor research results in RSA key generation.
Chapter 2: Proposal backdoors BD1, BD2
Presentation of two proposed RSA key generation backdoor
algorithms, BD1, BD2, complies to “P1” condition of FIPS 186-4
standard. The BD1, BD2 algorithms were analyzed, evaluated on Arboit
model, tested on a T-Token device with results suitable with the
assessments.
Chapter 3: Proposal backdoor algorithm, BD3
Presented a proposal for a RSA key generation backdoor algorithm,
BD3, comply with "P2" condition of FIPS 186-4 standard. The BD3
algorithm was analyzed, evaluated folowing Arboit’s model, tested on a
T-Token device with results suitable with the assessment.
4
CHAPTER 1. BACKDOOR BACKGROUND
IN KEY PAIR GENERATION
This chapter covers backdoor background for public key generation,
focusing on Arboit's formal tools, Coppermith's factoring method, FIPS
186-4 standard, and some backdoor research results in RSA key
generation backdoor. Based on the analysis and evaluation of the
backdoor research results of previous authors, Chapter 1 presents the
issues that need to be studied and solved by the thesis.
1.1. Introduction to cryptographic backdoor
This section covers general concepts of cryptography backdoor
including concepts, history, common features, and the scope of the
cryptography backdoor.
1.2. Background of backdoor in key pair generation
This part presents backdoor analysis model, backdoor security
definition and criteria for analysing backdoor key generation algorithms
based on Arboit's research results.
1.3. Coppermith's factoring method
This section presents Coppersmith's factoring method. The solution
to the loosed factoring problem, which is factoring n = pq, when knows
half of the bits of the prime number p, using small solution searching
method of a variable modulo equations.
1.4. Results on RSA cryptosystem
This section focuses on RSA key pair condition of FIPS 186-4
standard.
1.5. Backdoor research results in RSA key generation
There are two groups of research results on backdoor. The first group
is formal tools for analyzing and evaluating backdoor and the second is
backdoor algorithms. The first group include: SETUP (Kleptography)
from Young and Yung’s results and Secure Backdoor from Arboit’s
results. The second group contains backdoors of various authors
including: symmetric backdoors and asymmetric backdoors. Some
5
typical symmetric backdoors include: Anderson-Kaliski, HowgraveGraham, Crépeau-Slakmon. Some typical asymmetric backdoors
include: PAP, PAP-2, Primes Private, EC-SETUP, PHP.
Advantages of symmetric backdoor: ciphertext block size of
designer’s cryptosystem is small, easy for reducing backdoor
information; It is possible to choose key length of the designer’s
cryptosystem has equivalent or greater security level than the equivalent
security level of the user's security and vulnerability: key management
issue of designer's cyptosystem.
Advantages of asymmetric backdoor: Only designer can use
backdoor (restore user’s private key) and disadvantage: if using other
non-EC cryptosystem with large code block size, it should be difficult to
shrink backdoor information. The advantages and disadvantages are as
follows:
1.5.1. Advantages
- Arboit’s formal tool for analyzing and evaluating backdoor is more
efficient, comprehensive.
- Some effective backdoor algorithms, with advantages:
+ Backdoor information: a part of prime number p, this is reduced to
a half of prime number p.
+ Embedded location of backdoor information: in modulus n with
different embedding techniques achieving high correlation.
+ Using symmetric cryptosystems for backdoor’s designer will have
small ciphertext block size, easier for reducing backdoor information.
1.5.2. Shortcomming
- The published backdoor algorithms have been designed only for
common RSA cryptosystem. Parameters of key generation algorithm
(RSA cryptosystem) have not been complied with a specific standard.
- No key generation backdoor algorithms have been evaluated well
on all criteria. Some key generation backdoor algorithms have good
cardinality but failing to regenerate a part of key pair.
- Some key generation backdoor algorithms are evaluated for failures
using static memory (NM) to store information between key generation
circle and use sophisticated backdoor information embedding techniques
6
result in algorithm’s complexity was at level 2 or higher.
1.6. The issues that the thesis need to be researched and solved
Based on analysis of the results and the shortcomings of the previous
authors's works on RSA backdoor, the thesis should focus on researching
RSA key generation backdoor algorithms effectively, inherit the
advantages, limitations overcome the shortcomings in backdoor key
generation algorithms has announced to be able to apply to black-box
cryptographic products to ensure the security of the use. Public key
cryptography (PKI) satisfies the following constraints:
- Key pair parameters satisfy FIPS 186-4 standard [26].
- Backdoor information: Half of bits of prime p or less.
- Location for backdoor information embedding: in half bits or whole
bits of modulus n that still achieve high correlation.
- Designer’s cryptosystem would be symmetric cryptosystem or
public key cryptosystem, EC, with small ciphertext block size,
facilitating for backdoor information reduction.
- Backdoor properties (according to the Arboit model and criteria)
are rated as average or higher
- Do not use memory (VN, NM) to store information between key
generation circle and the complexity of the backdoor algorithm is less
than level 2.
1.7. Conclusion of Chapter 1
Chapter 1 presented background needed for analyzing, evaluating
backdoor and restoring private key from corresponding public key. It
focused on presenting knowledge about the efficient Arboit’s formal
model for analyzing, evaluating backdoor and Coppermith's factoring
method to recover private key from corresponding public key. Chapter 1
also presents research results on RSA cryptosystem, FIPS 186-4 standard
and reviews some previous results about RSA key generation. Based on
the previous backdoor research works and backdoor demands to secure
cryptographic usages, Chapter 1 introduce the problem that the thesis
will address. The knowledge presented and the problem set out in
Chapter 1 are basis for solving in Chapter 2 and Chapter 3 of the thesis.
7
CHAPTER 2. THE PROPOSAL BACKDOORS BD1, BD2
Chapter 2 present two RSA key generation backdoor algorithms
BD1, BD2, which have parameters complied with "P1" conditions of
"FIPS 186-4" standard. The BD1, BD2 backdoor algorithms are
analyzed, evaluated in detail following formal model of Arboit, tested on
a T-Token device.
2.1. The BD1 backdoor algorithm
2.1.1. Introducing the BD1 backdoor algorithm
2.1.1.1. Algorithm design
The BD1 backdoor algorithm is an asymmetric backdoor RSA
algorithm based on the idea of the PAP algorithm with parameters
satisfying the "P1" conditions of FIPS 186-4 standard.
Target: construct a backdoor key generation algorithm that generates
key pairs with sufficiently secure parameters for use in common
situations.
Designing ideas:
- Using the idea of the PAP algorithm: Backdoor information is
encrypted and embedded into bits of modulus n (PAP embedded in high
bits).
- The amount of backdoor information is a half bits of prime p (more
advanced: PAP uses the whole prime p).
- The technique of creating and embedding backdoor information
into all bits of modulus n based on Lemma 2.1.
- Parameters conform to the "P1" conditions of FIPS 186-4 standard.
The unique feature of the BD1 algorithm is the technique of creating
and embedding backdoor information into all bits of modulus n. The
spread of backdoor information into whole bits of modulus n makes
statistical properties of modulus n is better, the best in cases of
embedding backdoor information and attackers are hard to look for
backdoor information than embedding backdoor information into part of
modulus n, this also enhances backdoor security. The BD1 algorithm has
the following steps:
- Key generation section: The backdoor information is half of high
8
bits of prime p, encrypted by designer's ECIES encryption scheme and
spread evenly in bits of modulus n.
- Key recovery section: extract backdoor information from a half of
low bits of modulus n. Using Coppermith's factoring method to find the
prime p. Caculate prime q and private exponent d from p.
2.1.1.2. The key generation algorithm
Block diagram of the BD1 backdoor algorithm (Figure 2.3).
Start
e, nlen, B1
No
216 < e < 2256
nlen 2048
Yes
Generate prime p
GCD (p - 1, e) = 1
p is probable prime
(1,41.2nlen/2-1
No
p < 2nlen/2)
Yes
Prepair for backdoor information
Insert backdoor information to modulus n
Return
error
code
Compute q
GCD (q - 1, e) = 1
q is probable prime
(1,41 . 2nlen/2-1
No
Generate
prime
q with
backdoor
information
q < 2nlen/2)
|p – q| > 2nlen/2 – 100
Yes
Compute n, d
2nlen/ 2 < d< LCM (p-1, q-1)
No
Yes
p, q, n, d
Stop
Figure 2.3. Block diagram of the BD1 backdoor algorithm
Pseudocode of the BD1 key generation backdoor algorithm
Input (e, B1)
Output (p, q, n, d)
1: Input (e, B1) ;
2: if(e < 216 or e > 2256 or nlen <2048)then return failure;
// generate p
3: p = RandomPrime() ;
//log2 p = k
𝑛𝑙𝑒𝑛/2−1
4: if (𝑝 < √2. 2
) then goto step 3 ;
9
5: if (gcd(p - 1, e) ≠ 1) then goto step 3 ;
6: if (not (PrimalityTest (p))) then goto step 3 ;
// generate q
7: u = 2k mod p ;
//log2 q =nlen/2
8: v1 = EncECIES(p⌉k/2,Kpub);//Kpub backdoor owner’s key
9: for i = 0 to B1
10:
r = RandomOddInteger() ;
//log2 r = k/2
11:
v = v1.2k/2 + r ;
//v = v1 : r
12:
v0 = v mod p ;
13:
s0 = (v0 + u2).u-1 mod p ;
14:
if (s0 ≤ 2k-1) then
15:
s = 2k – s0 ;
16:
n = s.2k + v ;
// n = s : v
17:
q = n / p ;
//lemma 2.1
18:
if (𝑞 < √2. 2𝑛𝑙𝑒𝑛/2−1 ) then next i ;
nlen/2 – 100
19:
if ( |p – q| ≤ 2
) then next i ;
20:
if (gcd(q - 1, e) ≠ 1) then next i ;
21:
if (PrimalityTest (q))) then break ;
22: endfor ;
23: if not (PrimalityTest (q))) then goto step 3;
24: d = e–1 mod (LCM(p - 1, q - 1)) ;
nlen/ 2
25: if ( d < 2
) then goto step 3 ;
26: return (p, q, n, d) ;
Algorithm 2.2. The BD1 key generation backdoor algorithm.
2.2.1.3. The key recovery algorithm
Pseudocode of the BD1 key recovery backdoor algorithm.
Input (n, e)
Output (p, q, d)
1: Input (n, e) ;
2: v = n mod 2k ;
3: v1 = v div 2k/2 ;
4: p1 = DecECIES(v1, Kpriv);//Kpriv backdoor owner’s key
5: p = S(n, 2k/2, p1) ; //Coppersmith method(1.3.3)
6: q = n / p ;
7: d ≡ e−1 mod φ(n) ;
8: return (p, q, d) ;
Algorithm 2.6. The BD1 key recover backdoor algorithm
2.1.2. Evaluate the BD1 backdoor algorithm
Security: Designer uses the ECIES encryption algorithm with safe
parameter length E ≥ 128 equivalent to security parameter length of
10
RSA user G1 ≥ 2048. Therefore, security property is rated as "good".
Completeness: Following the steps in the key generation algorithm
and key recovery algorithm, designer always computes private key from
corresponding public key. The completeness property is rated as "good".
Cardinality: Consider the ratio between cardinality of G1 and G0,
since prime p is generated in G1 the same way as in G0, then # {p}, #
{e} possible ignore, we have:
1 𝑛𝑙𝑒𝑛
𝑁𝐺 ,𝑞 23𝑛𝑙𝑒𝑛/4+1− 𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛
𝑅𝐺1 = 1 ≈ 𝑛𝑙𝑒𝑛−1−𝑙𝑜𝑔 𝑛𝑙𝑒𝑛 = 22−𝑛𝑙𝑒𝑛/4 = 2−2. 2 +2
2
𝑁𝐺0 ,𝑞
2
Since the constant c = -1/2, so the cardinality of G1 is rated as "good".
Distribution: Backdoor information is encrypted and embedded in a
fixed location of modulus n. However, because backdoor information is
encrypted by ECIES encryption scheme (which output’s distribution is
closer to equilaterial distribution), so embedded backdoor information is
also distributed near equilaterial distribution. Therefore G1 distribution
is rated as "good".
Correlation: According to the algorithm, prime q depends on a part
of prime p and random parameter r. If user fixed p and asked keypair to
be regenerated again, general key regeneration can be performed.
However, if user requests inverse action, ie fixed q and regenerated p is
not feasible. Thus, the G1 correlation is rated as "medium".
Complexity: The complexity of generating n is: tn (G1) = tp + tq + T
(ECIES). Because complexity of ECIES cryptosystem is small compared
to complexity of p, q, then complexity of G1 is rated as "good".
Memory usage: The algorithm does not use NM and VM, so it has
rated as "good".
2.1.3. Summary of the BD1 backdoor algorithm
- Parameters satisfying the "P1" condition of the FIPS 186-4 standard
- The technique of embedding backdoor information into all bits of
modulus n based on the result of Lemma 2.1.
- Designer’s cryptosystem is EC that leads to be better key
management and only designer could uses the backdoor.
- Better than the PAP algorithm, PHP in terms of security, cardinality,
11
backdoor information and complexity.
- The key recovery section, using the Coppersmith’s factoring
method to retrieve private key from corresponding public key, is shorter
and simpler than the key recovery section of PAP and PHP.
- Good evaluation on 06 criteria, 01 criterion (correlation) is rated as
“medium”.
2.2. The BD2 backdoor algorithm
2.2.1. Introducing the BD2 algorithm
2.2.2.1. Algorithm design
The BD2 backdoor algorithm is a symmetric backdoor algorithm
based on the idea of the Hidden Prime Factor algorithm with parameters
satisfying the "P1" conditions of the FIPS 186-4.
Objective: Develop a key generation backdoor algorithm that
generates key pairs with parameters that are sufficiently secure for use in
general cases.
Design ideas:
- Using idea of the Hidden Prime Factor algorithm: Backdoor
information is encrypted and embedded in high bits of modulus n.
- The technique of extracting and embedding backdoor information
into modulus n is based on the subsections of 2.4.1.
- Backdoor parameters conform to the "P1" condition of the FIPS
186-4 standard.
The unique feature of the BD2 algorithm is the technique of
extracting backdoor information that is less than half bits of prime p. The
smaller backdoor information will use less space in public key leading to
increased cardinality. The BD2 algorithm has the following steps:
- Key generator: Backdoor information is part of prime p, encrypted
by symmetric cryptosystem F and embedded in half of high bits of
modulus n. The difference points of the BD2 algorithm is that backdoor
information can be shortened to s - k / 2 bits, so cardinality is greater.
- Key recovery: extract backdoor information from high bits of
modulus n. Decrypt backdoor information and apply the Coppersmith’s
factoring method to retrieve prime p. Caculate q, d from p.
12
2.2.2.2. The key generation algorithm
Start
e, nlen, s
No
216 < e < 2256
nlen 2048
Yes
Generate prime p
GCD (p - 1, e) = 1
p is probable prime
(1,41.2nlen/2-1
No
p < 2nlen/2)
Yes
Prepair for backdoor information
Insert backdoor information to modulus n
Return
error
code
Generate
prime
q with
backdoor
information
Compute q
GCD (q - 1, e) = 1
q is probable prime
(1,41 . 2nlen/2-1
No
q < 2nlen/2)
|p – q| > 2nlen/2 – 100
Yes
Compute n, d
2nlen/ 2 < d< LCM (p-1, q-1)
No
Yes
p, q, n, d
Stop
Figure 2.5. Block diagram of the BD2 backdoor algorithm
Block diagram of the BD2 backdoor algorithm (Figure 2.5)
Pseudocode of the BD2 key generation backdoor algorithm
Input (e, s, nlen)
Output (p, q, n, d)
1: Input (e, s, nlen) ;
2: if(e < 216 or e > 2256 or nlen <2048)then return failure;
// generate p
3: p = RandomOddInteger()//log2 p =nlen/2 ;
4: if (𝑝 < √2. 2𝑛𝑙𝑒𝑛/2−1 ) then goto step 3 ;
5: if (gcd(p - 1, e) ≠ 1) then goto step 3 ;
6: if (not (PrimalityTest (p))) then goto step 3 ;
13
// generate q
7: q’ = RandomOddInteger() ; //log2 q =nlen/2
8: n1 = p.q’ ; //k = nlen/2
9: τ = n1⌉ k/2 ;
10: μ = F K((p⌉k/2)⌋s - k/2);//K, backdoor owner’s key
11: r = RandomOddInteger() ; //log2 r = 3k/2 - s
12: n2 = τ . 23k/2 + μ . 23k/2 –s + r ;//n2 = τ : μ : r
13: q = [n2 / p] ;
14: if (𝑞 < √2. 2𝑛𝑙𝑒𝑛/2−1 ) then goto step 7 ;
15:
16:
17:
18:
19:
nlen/2 – 100
if ( |p – q| ≤ 2
if (gcd(q - 1, e) ≠ 1)
if (not (PrimalityTest
n = p.q ;
d = e–1 mod (LCM(p - 1,
) then go to step 7 ;
then goto step 7 ;
(q))) then goto step 7;
// lemma 2.4
q - 1)) ;
nlen/ 2
20: if ( d < 2
) then go to step 7 ;
21: return (p, q, n, d) ;
Algorithm 2.4. The BD2 key generation backdoor algorithm.
2.2.2.3. The key recovery algorithm
Pseudocode of the BD2 key recovery backdoor algorithm.
Input (n, e, s)
Output (p, q, d)
1: Input (n, e, s) ;
2: μ = ( n⌋3k/2 )⌉s - k/2 ;
3: p1 = ([√𝑛])⌉𝑘−𝑠 ;
4: p2 = F-1K(μ) ;
5: p3 = p1 . 2 s-k/2 + p2 ;
6: p = S(n, 2k/2, p3) ;
7: q = n / p ;
8: d ≡ e−1 mod φ(n) ;
9: return (p, q, d) ;
// lemma 2.4
// lemma 2.2
//p3 = p1 : p2, p3 == p⌉k/2
// Coppersmith method
Algorithm 2.5. The BD2 key recover backdoor algorithm.
2.2.2. Evaluate the BD2 backdoor algorithm
Security: Designer uses a symmetric AES that has a safe parameter
length AES ≥ 128 equivalent to user's security parameter length G1 ≥
2048. The attacker can not break the user’s cryptosystem, so he can not
break the designer’s cryptosystem. Security is rated as "good".
Completeness: Arcording to the key generation algorithm and the key
recovery algorithm, the designer always computes the private key from
the corresponding public key. Completeness are rate as "good".
14
Cardinality: Consider the ratio between the cardinality of G1 and G0,
since p is generated in G1 is the same as in G0, so the # {p} can be
ignored, we have:
𝑘
1 𝑛𝑙𝑒𝑛
𝑁𝐺 ,𝑞 2𝑛𝑙𝑒𝑛+2−𝑠− 𝑙𝑜𝑔2 𝑛𝑙𝑒𝑛
𝑅𝐺1 = 1 ≈ 𝑛𝑙𝑒𝑛−1−𝑙𝑜𝑔 𝑛𝑙𝑒𝑛 = 23−𝑠 < 2−2+3 = 2−2. 2 +3
2
𝑁𝐺0 ,𝑞
2
The constant c <-1/2, so the cardinality of G1 is rated as "good".
Distribution: Backdoor information is encrypted and embedded in a
fixed location in modulus n. Since backdoor information is encrypted
using symmetric cipher (with output’s distribution close to equilateral
distribution), so embedded backdoor information is also distributed close
to equilateral distribution. Thus distribution of modulus n can be close to
equilateral distribution and the statistical gap between the modulus n of
G1 and G0 is approximately zero, DG1 ≈ 0. Thus, the distribution of G1
is rated as "good" .
Correlation: According to the key generation algorithm (from step 7
to step 17), q depends on p, random parameter r, and random parameter
q'. If p is fixed and q is regenerated, generalization of key regeneration
can be performed. However, if user requests for inversion, ie fixed q and
regenerate p is not feasible. Thus, G1’s correlation is rated as "average".
Complexity: The complexity of creating modulus n is: tn (G1) = tp +
tq = tn, the complexity of G1 is rated as "good", linear with G0.
Memory Usage: The algorithm does not use NM and VM, so it has a
memory attribute that is rated as "good".
2.2.3. Summary of the BD2 backdoor algorithm
- Parameters satisfying the "P1" condition of FIPS 186-4 standard.
- Backdoor information is reduced, requiring less than half of bits of
prime p, leading to the largest cardinality in the proposed backdoors.
- The key recovery algorithm uses the Coppersmith’s factoring
method to recover private key from corresponding public key.
- Rated as “good” at 06 attributes and 01 attribute (correlation) is
rated as “medium”.
15
2.3. Testing of the BD1, BD2 backdoor algorithms
2.3.1. Objectives, methods, environment, criteria
Objective of test: to collect quality information, thereby evaluating
the potential deployment of the proposed backdoors.
Test method: black box testing, running backdoor algorithm in
situation (dynamic testing).
Test environment: The backdoor algorithm can be tested in key
generation module of PKI provider and user’s key generation module
(Token device, HSM).
Criteria was tested on T-Token device: completeness, correlation,
complexity; The remaining criteria are not tested.
2.3.2. The BD1 backdoor’s test results
Running time (s)
4
Complexity test result of the BD1 backdoor
2
0
Key generation time of G0
Key generation time of G1
Figure 2.8. Diagram of the BD1 backdoor’s complexity test results
Running time of G1
Running time of G0
Key generation
Key recovery
2.04s
2.38s
0.03s
Table 2.4. Complexity test results of the BD1 backdoor algorithm
2.3.3. Test results of the BD2 backdoor algorithm
Running time of G1
Key generation
Key recovery
2.04 s
2.43 s
0.04 s
Table 2.5. complexity test result of the BD2 backdoor algorithm
Running time of G0
16
Complexity test result of the BD2 backdoor
3
Running time (s)
2.5
2
1.5
1
0.5
0
Key generation time of G0
Key recovery time of G1
Key generation time of G1
Figure 2.9. Diagram of the BD2 backdoor’s complexity test results
2.4. Application of the BD1, BD2 backdoor
From the objective of the BD1, BD2 backdoor algorithms and
algorithm test results. The BD1, BD2 backdoor shows both are fast
implementation algorithms, parameters comply to the “P1” conditions of
FIPS 186-4 standard, so the best application environment for the BD1,
BD2 backdoor is in user's key generation module, PKI-Token device.
2.5. Conclusion Chapter 2
Chapter 2 solved the problems of the thesis: two effective the BD1,
BD2 backdoor algorithms are proposed. Both the backdoor algorithms
have parameters that comply with the "P1" conditions of FIPS 186-4
standard and most of the criteria are well-evaluated. The highlight of the
BD1 backdoor is the technique of creating and embedding backdoor
information into entire of modulus n for optimal distribution and security
improving. The highlight of the BD2 backdoor is the use of backdoor
information less than half bits of prime p that increase the cardinality.
Both the BD1 and BD2 algorithms are tested on T-Token devices with
test results consistent with the evaluations. The BD1, BD2 backdoor are
proposed to apply in key generation module of PKI-Token device.
17
CHAPTER 3. THE PROPOSAL BACKDOOR BD3
This chapter presents a RSA backdoor algorithm containing the BD3
backdoor complying with the "P2" condition of FIPS 186-4, the results
of the BD3 backdoor algorithm was tested on a T-Token device.
3.1. The BD3 backdoor algorithm
3.1.1. Introducting the BD3 backdoor algorithms
3.1.1.1. Algorithm design
The BD3 backdoor algorithm is the RSA key generation backdoor
algorithm compliance with the "P2" condition of FIPS 186-4 standard.
Objective: Develop a backdoor algorithm that generates key pairs
with strong parameters for use in special cases.
Design ideas:
- Based on John Gordon's prime generation algorithm for building
prime (p, q), based on Maurer's provable prime generation algorithm to
generate auxiliary primes.
- Complies with the "P2" condition of the FIPS 186-4 standard.
- Key recovery based on the Coppermith’s factoring method.
The BD3 algorithm’s unique feature is the technique of using
backdoor information derived from public exponent e, random parameter
t and the technique of embedding backdoor information into low bits of
prime p. Embedding backdoor information into prime p increases
backdoor security. Although the BD3 algorithm is public, it is far more
difficult to extract secret parameter (p) from which to extract backdoor
information than extracting backdoor information from modulus n. The
BD3 backdoor algorithm has the following characteristics:
- Key generation: Backdoor information is selected as a random
value t. Seed u is permuted from public exponent, e, through encryption
(or hash) function FK which K is key of designer. Value of C = ut mod
2nlen / 4, is embedded in half of lower bits of prime p.
- Key recovery: Designer calculates value of u, look for bacdoor
information t < m, calculates C value (half of lower bits of prime p).
Value of prime p is recoverd via the Coppermith's factoring method.
18
3.1.1.2. The key generation algorithm
Block diagram of the BD3 backdoor algorithm (Figure 3.2)
Start
e, nlen, n1, n2, n3, n4, m
216 < e < 2256
nlen 1024
No
Yes
Prepare backdoor information
Generate auxiliary prime p1, p2
Min and max length of auxiliary prime p1, p2
Generate
prime
p with
backdoor
information
No
Yes
Generate the prime p
GCD (p - 1, e) = 1
(1,41.2nlen/2-1
No
p < 2nlen/2)
Yes
Generate auxiliary prime q1, q2
Min and max length of auxiliary prime q1, q2
No
Yes
Return
error
code
Generate the prime q
GCD (q - 1, e) = 1
q < 2nlen/2)
(1,41 . 2nlen/2-1
|p – q| > 2
No
nlen/2 – 100
Yes
Compute n, d
2nlen/ 2 < d< LCM (p-1, q-1)
No
Yes
p, q, n, d
Stop
Figure 3.2. Block diagram of the BD3 backdoor algorithm
Pseudocode of key generation backdoor algorithm BD3
Input: e, nlen, n1, n2, n3, n4, m
Output: p, q, n, d
1: Input: e, nlen, n1, n2, n3, n4, m ;
2: if(e < 216 or e > 2256 or nlen <1024)then return failure;
3: u = FK(e); //encryption or hash with key
4: t = Random(m);
// t < m
5: C = ut mod 2nlen/4 ;
// generate p
6: p1 = RandomProvablePrime(2𝑛1−1 , 2𝑛1 ) ;
7: p2 = RandomProvablePrime (2𝑛2−1 , 2𝑛2 ) ;
8: Ap = p1.p2. 2nlen/4 ;
1 𝑚𝑜𝑑 𝑝1
−1
𝑚𝑜𝑑 𝑝2
9: 𝐵𝑝 = {
;
// using CRT
𝐶 𝑚𝑜𝑑 2𝑛𝑙𝑒𝑛/4
- Xem thêm -
.PDF 
27 
81 
115 
