=Paper=
{{Paper
|id=Vol-2081/paper16
|storemode=property
|title=Vulnerability of RSA Algorithm
|pdfUrl=https://ceur-ws.org/Vol-2081/paper16.pdf
|volume=Vol-2081
|authors=Aleksandra V. Markelova
}}
==Vulnerability of RSA Algorithm==
<pdf width="1500px">https://ceur-ws.org/Vol-2081/paper16.pdf</pdf>
<pre>
                            Vulnerability of RSA Algorithm
                                                      Aleksandra V. Markelova
                                                 Information Security Department
                                             Bauman Moscow State Technical University
                                                         Moscow, Russia
                                                    markelova_bmstu@mail.ru



    Abstract—This paper is dedicated to ROCA-vulnerability that            Google, HP, Lenovo and Fujitsu released updates for their
was detected by scientists from Masaryk University, Czech. Their           software products susceptible to this attack.
investigation offers low-cost algorithm of factorization of RSA
module for special type of keys generated by some widely used                  Recall that the public key of the RSA algorithm is a pair
cryptographic library. They proposed a practical factorization             (n, e), where n is the product of two large primes and gcd(e,
method for various key lengths including 1024 and 2048 bits.               (n))=1. Private key is number d such that ed=1(mod (n)).
This attack requires no additional information except for the              Some implementations also store prime divisors of n as part of
value of the public key and does not depend on a weak or a faulty          the private key.
random number generator. We examine the possibility of
modification of type of keys to embed the trapdoor with universal             Thus, RSA requires two large random primes p and q, that
protection into key generator. In some cases we can design                 can be obtained by generating a random candidate number
Secretly Embedded Trapdoor with Universal Protection in the                (usually with half of the bits of n) and then testing it for
generator of RSA key. This problem is serious and relevant for             primality. If the candidate is found to be composite, the
all closed (so-called black-box) implementations of cryptographic          process is repeated with a different candidate.
algorithm in user’s library or device. The first section of this
                                                                               Since the RSA algorithm is very popular, many researches
article (“Introduction”) is devoted to the history of the issue. It
also describes the damage caused by vulnerability ROCA. The
                                                                           are devoted to its reliability [2, 3, 4, 5, 6, 7].
second section (“Fingerprint of weak keys”) describes the                     RSA security is based on the integer factorization problem.
criterion that the key pair is vulnerable to ROCA. The third
section (“Factorization”) is dedicated to the attack ROCA. It also             The most effective modern factorization algorithms (such
estimates the running time of the algorithm. In the fourth section         as quadratic sieve [8], number field sieve [9], special number
(“The trapdoor with universal protection”) we will consider the            field sieve [10, 11]) have subexponential complexity [12] and
possibility of using SETUP mechanism in the implementation of              in the general case do not allow hacking RSA with large key
RSA.                                                                       lengths.

    Keywords— information security, cryptanalysis, vulnerability,             However, if the numbers p and q are a special type, then the
ROCA, RSA, Coppersmith’s algorithm, factorization, weak keys,              time of factorization of the number n = pq can be reduced.
kleptography, trapdoor with protection, backdoor, SETUP
                                                                                    II.      FINGERPRINT OF WEAK KEYS
                       I.    INTRODUCTION                                      There is no common practice for developers of
    On November, 2017 Estonian government made a                           cryptographic library how to generate RSA key pair. But there
statement about blocking 760 000 certificate of ID cards issued            are many recommendations regarding how to select suitable
after October 16, 2014. The reason for this statement was the              primes p and q [13, 14, 15, 16] to be later used to compute the
vulnerability ROCA (Return of Coppersmith's Attack)                        private key and public moduli.
discovered by scientists from Masaryk University, Czech [1].                  In 2016, scientists from Masaryk University analyzed
    Toomas Ilves, the former president of Estonia, said that he            implementations of RSA algorithm and key pairs from 22
believed millions of people in countries had been affected by              open- and closed- source libraries and from 16 different smart
the ROCA flaw, but their authorities were remaining "silent".              cards [17]. In particular, the library RSALib used in Estonian
In particular, according to the researchers of the Enigma                  ID cards was investigated. This library utilizes an acceleration
Bridge, similar problems are possible with ID card of Spain.               algorithm called “Fast Prime”.
    There is a fast detection algorithm to verify whether a                   The foundations of “Fast Prime” date back to the year
particular key is vulnerable to attack. This verification is based         2000. According to its developers, its use started around ten
on the properties of the public moduli.                                    years later after thorough reviews. As a sub-part of one
                                                                           cryptographic software library which is supplied to customers
   Vulnerable keys were also found in some authentication                  as a basis for their own development, this software function
tokens, in the TPM (Trusted Platform Modules), in PGP.                     was certified by the BSI (Federal Office for Information
                                                                           Security) in Germany.




                                                                      74
   When compared to other implementations and theoretical                                               TABLE II.
expectations on distribution of prime numbers, the keys from
                                                                                 Key size                    Size of M                 ordM65537
RSALib exhibited a non-uniform distribution of (p mod x) and
(n mod x) for small primes x.                                             512                   2   219,19
                                                                                                                          2   62,09


                                                                                                    474,92
    Further studies have shown that all RSA primes generated              1024                  2                         2134,73
by the RSALib have the following form [1]:                                2048                  2970,96                   2255,78
                                                                          3072                  2970,96                   2255,78
                                      a
                      p=k*M + (65537 mod M)                   (1)         4096                  21962,19                  2434,69

    The integers k and a are unknown, and RSA primes differ
only in their values of a and k for keys of the same size. The               Online and offline versions of this test are already
integer M is fixed for each key size (table I) and equal to the           developed. They are freely available on the Internet.
product of the first successive primes:
                                                                                    III.    FACTORIZATION
                M = Pm =  pi = 2*3*5*7*…*pm                (2)            Algorithm ROCA iterates over values of a in (1) and use
                                                                          Coppersmith’s algorithm [19] to attempt to find k. To reduce
                                                                          the search, the modulus M is replaced by its divisor M', for
                           TABLE I.                                       which ordM'65537 is small and log2M'>log2n/4. The number M'
                                                                          is selected once for each RSA key size (table III).
           Key size                           M
512                          P39#=167#                                                                  TABLE III.
1024                         P71#=353#
                                                                                 Key size                    Size of M'               ordM'65537 /2
2048                         P126#=701#
                                                                          512                   2140,77                   219,20
3072                         P126#=701#                                                             474,92
                                                                          1024                  2                         229,04
4096                         P225#=1427#
                                                                          2048                  2970,96                   234,29
                                                                          3072                  2552,50                   299,29
      In this case the following comparison takes place:
                                                                          4096                  21098,42                  255,05

                        n = 65537c mod M                     (3)
                                                                              The size of M' (condition log2M'>log2n/4) is chosen to
    The existence of the discrete logarithm c = log65537n mod             apply the modification of the Coppersmith’s attack [19], which
M is used as the fingerprint of weakness of the key pair. In              is successful in case of knowing l/4 the least significant bits of
general, verification of solvability of the comparison (3) can            the number p, where l is the key size.
be difficult [18]. But if M is of the form (2) then the problem               Coppersmith’s attack was repeatedly modified. Now there
is easily solved.                                                         are various attacks on RSA based on Coppersmith’s algorithm.
   The number of residues modulo M for which there exists a               For example, factorization algorithms have been developed for
logarithm at base 65537 is equal to ordM65537. For randomly               cases when the lowest bits of the number p are known or when
generated prime numbers, the remainders from dividing their               primes p and q share bits in the middle ([20, 21, 22, 23]).
product by M are distributed uniformly in the multiplicative                  In attacks of this class, we choose a polynomial f(x)
group of residues modulo M. Therefore, the probability for the            having a small root x0 in the residue field:
number n to satisfy the comparison (3) is ordM65537/(M).
      For the M used, the value of ordM65537 is much less than                                       f(x0) = 0 mod p                                 (4)
(M). For example, ordM65537=262,09, (M)=2215,98 for RSA-
512. Thus, the probability of the false positive result does not
exceed 262–216=2–154. This probability is even smaller for larger                                             |x0|<X                                  (5)
keys (table II).
    So the existence of the discrete logarithm is the strong                  Then we construct a polynomial g(x) satisfying the
fingerprint of the weak keys.                                             following conditions:


                                                                                                      g(x) =  aifi(x),                               (6)




                                                                     75
                             ai is integer,                                    will take about 17 days to find the 2048-bit key. At the same
                                                                               time the cost of the attack will not increase, because it is
                                                                               calculated based on the price of one processor hour.
            fi(x) and f(x) have the same roots modulo p,            (7)
                                                                                                        TABLE V.

                                |g(x0)|<p.                          (8)                    Key size             Factorization on 2x Intel E5-2666
                                                                                                                 v3@2.90GHz (Amazon AWS, c4
                                                                                                                instance) and resource rental cost
    The coefficients ai are chosen by the LLL-lattice method
[24]. It follows from (6) and (7) that g(x) has the same roots                 512                             0,63 hours, $0,063
modulo p as f(x). Well then g(x0)=0 mod p. Taking into                         1024                            31,71 days, $76
account (8), we see that g(x0)=0. Thus x0 can be found by
standard methods for finding the roots of a polynomial (e.g.,                  2048                            45,98 years, $40 305
the Berlekamp-Zassenhaus algorithm [25, 26]).                                  3072                            9,28*1024 years, $8,13*1027
   We denote the process of finding x0 as Coppersmith(f(x), n,                 4096                            4,18*108 years, $3,66*1011
, m, t, X), where n is RSA-modulus,  is the upper bound for
the ratio of log2p and log2n, m and t are optimization
parameters of Coppersmith algorithm, X is from (5).                               Note that 4096-bit RSA key is not practically factorizable
                                                                               now, but may become so, if the attack is improved.
      Algorithm ROCA works as follows:
                                                                                  This is very possible, since the Coppersmith’s algorithm
      1. c'= log65537n mod M'                                                  and the lattice-based method are constantly improving [27]
      2. =0.5, X=2*n/M'
                                                                                        IV.    THE        TRAPDOOR         WITH       UNIVERSAL
      3. For all a' in [c'/2; (c'+ ordM'65537)/2]:
                                                                                       PROTECTION
                                                                                   Did the developers of the RSALib library know about the
                              –1                   a'
           3.1 f(x) = x + (M' mod n)*(65537 mod M')(mod n)                     vulnerability of their key generator? If they knew, then such
                                                                               an implementation could be considered as an implementation
           3.2. k' = Coppersmith(f(x), n, , m, t, X)                          with a trapdoor (or a backdoor). But in this case the special
                                                                               form (2) of the number M makes it possible for any observer to
           3.3. p=k'*M' + (65537a' mod M')
                                                                               restore the prime numbers (1). Because of this, an access to the
           3.4 If p is a nontrivial divisor of n, then finish.                 backdoor is provided not only for developers or authorized
                                                                               special agency, but also for attacker.
                                                                                    The difference between a trapdoor and a backdoor is the
    The running time of this algorithm is shown in tables IV                   degree of protection from a third-party offender [28]. The
and V. Two time values were explicitly checked by the                          science of trapdoors is called "kleptography" [29]. It was
scientists from Masaryk University on the university cluster.                  shown that a cryptosystem, when implemented as a black-box
                                                                               (i.e., when the user has only input/output access to the
                            TABLE IV.                                          hardware or software cryptographic facility), can be designed
                                                                               such that it gives a unique advantage to the attacker. This is
              Key size                 Factorization on Intel Xeon E5-         accomplished using SETUP (Secretly Embedded Trapdoor
                                          2650 v3 @3GHz Q2/2014
                                                                               with Universal Protection) mechanisms. SETUP is a system,
512                                  1,93 hours (verified)                     hacking which will be available only to the developer.
1024                                 97,1 days (verified)                         This topic was examined in detail by Young A. and Yung
2048                                 140,8 years                               M. [30]. In particular, they considered a number of
                                                                               kleptographic attacks on the RSA algorithm [30, 31, 32].
3072                                 2,84*1025 years
                                                                                   Issues of the implementation of SETUP-mechanisms are
4096                                 1,28*109 years
                                                                               an actual direction of modern cryptography. Bellare, Paterson,
                                                                               and Rogaway initiated a formal study of such attacks on
   Others were extrapolated based on known algorithm                           symmetric key encryption algorithms, demonstrating that
properties and processing power.                                               kleptographic attacks can be mounted in broad generality
                                                                               against randomized components of cryptographic systems
    The algorithm is well suited for parallel computations,                    [33]. Russell, Tang, Yung and Zhou enlarged the scope of
since the approbation of different values of a' can pass                       work on the problem by permitting adversarial subversion of
independently of each other.                                                   (randomized) key generation; in particular, they initiated the
                                                                               study of cryptography in the complete subversion model,
    For example, you can rent 1000 cores on Amazon AWS.
                                                                               where all relevant cryptographic primitives are subject to
In this case it will take 45 minutes to find the 1024-bit key. It
                                                                               kleptographic attacks [34].




                                                                          76
    Obviously, the most effective attack for the intruder and                The set (C, , l) specifies the parameters for selecting the
the greatest danger to the user are backdoors and trapdoors              numbers M and w. If you know this set, M and w then you can
into the key pair generator. The simplest attack on RSA key              restore the user’s private key from the public key applying the
generator is using a fixed prime number p [30]. But this attack          ROCA analog.
is detectable and it is breakable without reverse engineering.
                                                                             If M has a large prime divisor, then it is not possible to
    The problem of detectability in the attack can be avoided            estimate the distribution (p mod x) and (n mod x) for all
by using pseudorandom values instead of random values and                numbers x of this size. Then an attacker will not receive any
having the initial seed known only to the device and the                 additional information about the key.
attacker. This type of the backdoor is similar to the
implementation of the key generator in the RSALib library.                          V.        CONCLUSIONS
   The fundamental weakness in the pseudorandom number                      The vulnerability of ROCA once again recalled the
generator backdoor attack is that once an intermediate seed is           importance of analyzing the used cryptographic libraries. In
exposed, the future operation of the device is compromised               some cases, problems can be identified by evaluating the
[30]. Modern methods of protection against backdoor in                   specificity of the generated keys.
pseudorandom generators assume randomness checking at any
time without any notification, so the device is forced to behave             However, the RSA algorithm allows you to build in the
honest [35].                                                             key generator secretly embedded trapdoor with universal
                                                                         protection. The feature of this trapdoor is that it is not
    Degabriele, Paterson, Schuldt and Woodage conducted a                detectable for the analyst (it is impossible even to prove its
full-scale study of pseudorandom number generators [36] and              presence in the implementation), but it allows the developer to
give efficient constructions of BPRGs (backdoored                        calculate the user's private keys.
pseudorandom number generators) for which, given a single
generator output, Big Brother can recover the initial state and,
                                                                                                  REFERENCES
therefore, all outputs of the BPRG. They give an impossibility
result: they provide a bound on the number of previous phases            [1]  Nemec M., Sys M., Svenda P., Klinec D., Matyas V. The Return of
                                                                              Coppersmith's Attack: Practical Factorization of Widely Used RSA
that Big Brother can compromise as a function of the state-size               Moduli. 2017. CCS'17 Proceedings of the 2017 ACM SIGSAC
of the generator: smaller states provide more limited                         Conference on Computer and Communications Security, p. 1631-1648.
backdooring opportunities for Big Brother.                                    DOI: 10.1145/3133956.3133969.
                                                                         [2] Nitaj A. (2012) A New Attack on RSA and CRT-RSA. In: Mitrokotsa
    Leaving aside the moral and legal aspects of the issue, we                A., Vaudenay S. (eds) Progress in Cryptology – AFRICACRYPT 2012.
will consider whether it is possible to construct a trapdoor                  AFRICACRYPT 2012. Lecture Notes in Computer Science, vol 7374, p.
with universal protection based on the same idea as the                       221-233. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-31410-
vulnerability of ROCA.                                                        0_14.
                                                                         [3] Nitaj A. A new attack on RSA with two or three decryption exponents.
   Let’s choose numbers M and w satisfying the following                      Journal of Applied Mathematics and Computing (2013) Vol. 42, Issue 1-
conditions:                                                                   2, p. 309–319. DOI: 10.1007/s12190-012-0618-0.
                                                                         [4] Peng L., Hu L., Lu Y., Xu J., Huang Z.. Cryptanalysis of Dual RSA
   1) the decomposition of the number M into prime factors is                 Designs, Codes and Cryptography. (2017) Vol. 83, Issue 1, p. 1-21.
known                                                                         DOI: 10.1007/s10623-016-0196-5.
    2) (M) is decomposed into small primes:                             [5] Barbu G. et al. (2013) Combined Attack on CRT-RSA. In: Kurosawa K.,
                                                                              Hanaoka G. (eds) Public-Key Cryptography – PKC 2013. Lecture Notes
                                                                              in Computer Science, vol 7778, p. 198-215. Springer, Berlin,
                                                                              Heidelberg. DOI: 10.1007/978-3-642-36362-7_13.
                       pi | (M): pi < C                    
                                                                         [6] Bunder M., Nitaj A., Susilo W., Tonien J. (2016) A New Attack on
                                                                              Three Variants of the RSA Cryptosystem. In: Liu J., Steinfeld R. (eds)
    3) value ordMw is small:                                                  Information Security and Privacy. ACISP 2016. Lecture Notes in
                                                                              Computer Science, vol 9723, p. 258-268. Springer, Cham. DOI: 978-3-
                                                                              319-40367-0_16.
                          ordMw                                 [7] Bauer A., Jaulmes E., Lomné V., Prouff E., Roche T. (2014) Side-
                                                                              Channel Attack against RSA Key Generation Algorithms. In: Batina L.,
                                                                              Robshaw M. (eds) Cryptographic Hardware and Embedded Systems –
   4) the size of M approximately equal to optimal                            CHES 2014. CHES 2014. Lecture Notes in Computer Science, vol 8731,
Coppersmith’s algorithm parameters:                                           p. 223-241. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-
                                                                              44709-3_13.
                                                                         [8] Pomerance C., Analysis and Comparison of Some Integer Factoring
                    l = log2M ~ log2n / 4                 (11)               Algorithms, in Computational Methods in Number Theory, Part I, H.W.
                                                                              Lenstra, Jr. and R. Tijdeman, eds., Math. Centre Tract 154, Amsterdam,
    5) there are many primes of the form                                      1982, p. 89-139.
                                                                         [9] Lenstra A.K., Lenstra H.W., Jr., Manasse M.S., Pollard J.M. (1990). The
                                                                              number field sieve. STOC '90 Proceedings of the twenty-second annual
                   p=k*M + (wa mod M)                     (12)              ACM symposium on Theory of computing, p. 564-572, ISBN 0-89791-
                                                                              361-2. DOI: 10.1145/100216.100295.
  The last condition ensures that the generator will construct           [10] Lenstra A.K., Lenstra H.W., Jr., Manasse M.S., Pollard J.M. (1993).
                                                                              The Factorization of the Ninth Fermat Number. Mathematics of
many different prime numbers.




                                                                    77
     Computation Т. 61 (1993): p. 319–349, DOI: 10.1090/S0025-5718-                  [24] Lenstra A.K., Lenstra H.W., Lovász L. Factoring polynomials with
     1993-1182953-4.                                                                      rational coefficients. Math. Ann. 261, 4 (1982), p. 515–534. DOI:
[11] Buhler J.P., Lenstra H.W., Pomerance C. (1993) Factoring integers with               10.1007/BF01457454.
     the number field sieve. In: Lenstra A.K., Lenstra H.W. (eds) The                [25] Berlekamp E.R. Factoring Polynomials Over Large Finite Fields. Math.
     development of the number field sieve. Lecture Notes in Mathematics,                 Comp. 24 (1970), p. 713-735. DOI: 10.1090/S0025-5718-1970-
     vol 1554, p. 50-94. Springer, Berlin, Heidelberg. DOI:                               0276200-X.
     10.1007/BFb0091539.                                                             [26] Cantor D.G. and Zassenhaus H. A New Algorithm for Factoring
[12] Pomerance C. A tale of two sieves. Notices Amer. Math. Soc. 43 (1996),               Polynomials Over Finite Fields. Math. Comp. 36, 154 (1981), p. 587–
     p. 1473-1485.                                                                        592. DOI: 10.2307/2007663.
[13] Gordon J.(1985) Strong Primes are Easy to Find. In: Beth T., Cot N.,            [27] Lu Y., Peng L., Kunihiro N. (2018) Recent Progress on Coppersmith’s
     Ingemarsson I. (eds) Advances in Cryptology. EUROCRYPT 1984.                         Lattice-Based Method: A Survey. In: Takagi T., Wakayama M., Tanaka
     Lecture Notes in Computer Science, vol 209, p. 216-223. Springer,                    K., Kunihiro N., Kimoto K., Duong D. (eds) Mathematical Modelling
     Berlin, Heidelberg. DOI: 10.1007/3-540-39757-4_19.                                   for Next-Generation Cryptography. Mathematics for Industry, vol 29, p.
[14] Loebenberger D., Nusken M.. Notions for RSA Integers. In International               297-312. Springer, Singapore. DOI: 10.1007/978-981-10-5065-7_16
     Journal of Applied Cryptography, Vol. 3, No. 2 (2014), p. 116–138.              [28] Zhukov A.E. Cryptosystems with embedded trapdoors. BYTE Russia,
     DOI: 10.1504/IJACT.2014.062723.                                                      2007 (№101), p.45-51.
[15] Maurer U.M.. Fast generation of prime numbers and secure public-key             [29] Young A., Yung M. (1997) Kleptography: Using Cryptography Against
     cryptographic parameters. Journal of Cryptology, Vol. 8, Issue 3 (1995),             Cryptography. In: Fumy W. (eds) Advances in Cryptology —
     p. 123–155. DOI: 10.1007/BF00202269.                                                 EUROCRYPT ’97. EUROCRYPT 1997. Lecture Notes in Computer
[16] Benhamouda F., Ferradi H., Géraud R., Naccache D. (2017) Non-                        Science, vol 1233, p. 62-74. Springer, Berlin, Heidelberg. DOI:
     interactive Provably Secure Attestations for Arbitrary RSA Prime                     10.1007/3-540-69053-0_6.
     Generation Algorithms. In: Foley S., Gollmann D., Snekkenes E. (eds)            [30] Young A., Yung M. Malicious Cryptography. Exposing Cryptovirology.
     Computer Security – ESORICS 2017. ESORICS 2017. Lecture Notes in                     Wiley Publishing, Inc. 2004.
     Computer Science, vol 10492, p. 206-223. Springer, Cham. DOI: 978-3-            [31] Young A., Yung M. (2006) A Space Efficient Backdoor in RSA and Its
     319-66402-6_13.                                                                      Applications. In: Preneel B., Tavares S. (eds) Selected Areas in
[17] Svenda P., Nemec M., Sekan P., Kvasnovskyy R., Formanek D.,                          Cryptography. SAC 2005. Lecture Notes in Computer Science, vol
     Komarek D., Matyas V.. 2016. The Million-Key Question –                              3897,    p     .128-143.   Springer,    Berlin,   Heidelberg.    DOI:
     Investigating the Origins of RSA Public Keys. In The 25th USENIX                     10.1007/11693383_9.
     Security Symposium (USENIX Security’16). USENIX, p. 893–910.                    [32] Young A., Yung M. (2016) Cryptography as an Attack Technology:
     DOI: 10.13140/rg.2.1.3759.3848.                                                      Proving the RSA/Factoring Kleptographic Attack. In: Ryan P., Naccache
[18] Markelova A.V. Solvability of the problem of taking the discrete                     D., Quisquater JJ. (eds) The New Codebreakers. Lecture Notes in
     logarithm. Moscow University Mathematics Bulletin, Vol. 63, Issue 6                  Computer Science, vol 9100, p. 243-255. Springer, Berlin, Heidelberg.
     (2008), p. 225-228. DOI: 10.3103/S0027132208060016.                                  DOI: 978-3-662-49301-4_16.
[19] Coppersmith D. (1996) Finding a Small Root of a Bivariate Integer               [33] Bellare M., Paterson K.G., Rogaway P. (2014) Security of Symmetric
     Equation; Factoring with High Bits Known. In: Maurer U. (eds)                        Encryption against Mass Surveillance. In: Garay J.A., Gennaro R. (eds)
     Advances in Cryptology — EUROCRYPT ’96. EUROCRYPT 1996.                              Advances in Cryptology – CRYPTO 2014. Lecture Notes in Computer
     Lecture Notes in Computer Science, vol 1070, p. 178–189. Springer,                   Science, vol 8616, p. 1-19. Springer, Berlin, Heidelberg. DOI:
     Berlin, Heidelberg. DOI: 10.1007/3-540-68339-9_16.                                   10.1007/978-3-662-44371-2_1.
[20] Lu Y., Zhang R., Lin D. (2013) Factoring RSA Modulus with Known                 [34] Russell A., Tang Q., Yung M., Zhou HS. (2016) Cliptography: Clipping
     Bits from Both p and q: A Lattice Method. In: Lopez J., Huang X.,                    the Power of Kleptographic Attacks. In: Cheon J., Takagi T. (eds)
     Sandhu R. (eds) Network and System Security. NSS 2013. Lecture                       Advances in Cryptology – ASIACRYPT 2016. Lecture Notes in
     Notes in Computer Science, vol 7873, p. 393-404. Springer, Berlin,                   Computer Science, vol 10032, p. 34-64. Springer, Berlin, Heidelberg.
     Heidelberg. DOI: 10.1007/978-3-642-38631-2_29.                                       DOI: 10.1007/978-3-662-53890-6_2.
[21] Akchiche O., Khadir O.. Factoring RSA moduli with primes sharing bits           [35] Hanzlik L., Kluczniak K., Kutyłowski M. (2017) Controlled
     in the middle. AAECC (2017), p. 1–15. DOI: 10.1007/s00200-017-                       Randomness – A Defense Against Backdoors in Cryptographic Devices.
     0340-0.                                                                              In: Phan RW., Yung M. (eds) Paradigms in Cryptology – Mycrypt 2016.
[22] Nitaj A. (2013) An Attack on RSA Using LSBs of Multiples of the                      Malicious and Exploratory Cryptology. Mycrypt 2016. Lecture Notes in
     Prime Factors. In: Youssef A., Nitaj A., Hassanien A.E. (eds) Progress               Computer Science, vol 10311, p 215-232. Springer, Cham. DOI:
     in Cryptology – AFRICACRYPT 2013. AFRICACRYPT 2013. Lecture                          10.1007/978-3-319-61273-7_11.
     Notes in Computer Science, vol 7918, p. 297-310. Springer, Berlin,              [36] Degabriele J.P., Paterson K.G., Schuldt J.C.N., Woodage J. (2016)
     Heidelberg. DOI: 10.1007/978-3-642-38553-7_17.                                       Backdoors in Pseudorandom Number Generators: Possibility and
[23] May A. (2009) Using LLL-Reduction for Solving RSA and                                Impossibility Results. In: Robshaw M., Katz J. (eds) Advances in
     Factorization Problems. In: Nguyen P., Vallée B. (eds) The LLL                       Cryptology – CRYPTO 2016. Lecture Notes in Computer Science, vol
     Algorithm. Information Security and Cryptography, p. 315–348.                        9814, p. 403-432. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-
     Springer, Berlin, Heidelberg. DOI: 0.1007/978-3-642-02295-1_10.                      662-53018-4_15.




                                                                                78

</pre>