Gabrielle De Micheli

Nadia Heninger

Recovering cryptographic keys from partial information, by example

Side-channel attacks targeting cryptography may leak only partial or indirect information about the secret keys. There are a variety of techniques in the literature for recovering secret keys from partial information. In this tutorial, we survey several of the main families of partial key recovery algorithms for RSA, (EC)DSA, and (elliptic curve) Diffie-Hellman, the public-key cryptosystems in common use today. We categorize the known techniques by the structure of the information that is learned by the attacker, and give simplified examples for each technique to illustrate the underlying ideas.

Introduction

You are dangling in a rope sling hung from the ceiling of a datacenter in an undisclosed location, high above the laser tripwires criscrossing the floor. You hold an antenna over the target's computer, watching the bits of their private key appear one by one on your smartwatch display. Suddenly you hear a scuffling at the door, the soft beep of keypad presses. You'd better get out of there! You pull your emergency release cable and retreat back to the safety of the ventilation duct. Drat! You didn't have time to get all the bits! Mr. Bond is going to be very disappointed in you. Whatever are you going to do?

In a side-channel attack, an attacker exploits side effects from computation or storage to reveal ostensibly secret information. Many side-channel attacks stem from the fact that a computer is a physical object in the real world, and thus computations can take different amounts of time [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], cause changing power consumption [START_REF] Paul | Differential power analysis[END_REF], generate electromagnetic radiation [START_REF] Quisquater | Electromagnetic analysis (ema): Measures and counter-measures for smart cards[END_REF], or produce sound [START_REF] Daniel Genkin | RSA key extraction via low-bandwidth acoustic cryptanalysis[END_REF], light [START_REF] Ferrigno | When AES blinks: Introducing optical side channel[END_REF], or temperature [START_REF] Hutter | The temperature side channel and heating fault attacks[END_REF] fluctuations. The specific character of the information that is leaked depends on the high-and low-level implementation details of the algorithm and often the computer hardware itself: branch conditions, error conditions, memory cache eviction behavior, or the specifics of capacitor discharges.

The first work on side-channel attacks in the published literature did not directly target cryptography [START_REF] Van Eck | Electromagnetic radiation from video display units: An eavesdropping risk?[END_REF], but since Kocher's work on timing and power analysis in the 90s [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF][START_REF] Paul | Differential power analysis[END_REF], cryptography has become a popular target for side-channel work. However, it is rare that an attacker will be able to simply read a full cryptographic secret through a side channel. The information revealed by many side channel attacks is often indirect or incomplete, or may contain errors.

Thus in order to fully understand the nature of a given vulnerability, the sidechannel analyst often needs to make use of additional cryptanalytic techniques. The main goal for the cryptanalyst in this situation is typically: "I have obtained the following type of incomplete information about the secret key. Does it allow me to efficiently recover the rest of the key?" Unfortunately there is not a onesize-fits-all answer: it depends on the specific algorithm used, and on the nature of the information that has been recovered.

The goal of this work is to collect some of the most useful techniques in this area together in one place, and provide a reasonably comprehensive classification on what is known to be efficient for the most commonly encountered scenarios in practice. That is, this is a non-exhaustive survey and a concrete tutorial with motivational examples. Many of the algorithmic papers in this area give constructions in full generality, which can sometimes obscure the reader's intuition about why a method works. Here, we aim to give minimal working examples to illustrate each algorithm for simple but nontrivial cases. We restrict our focus to public-key cryptography, and in particular, the algorithms that are currently in wide use and thus the most popular targets for attack: RSA, (EC)DSA, and (elliptic curve) Diffie-Hellman.

Throughout this work, we will illustrate the information known for key values as follows:

Most significant bits Least significant bits Known bits 3

The organization of this survey is given in Table 1.

Motivation

While this tutorial is mostly operating at a higher level of mathematical abstraction than the side-channel attacks that we are motivated by, we will give a few examples of how attackers can learn partial information about secrets.

Modular exponentiation. All of the public-key cryptographic algorithms we discuss involve modular exponentiation or elliptic curve scalar addition operating on secret values. For RSA signatures, the victim computes s = m d mod N where d is the secret exponent. For DSA signatures, the victim computes a per-signature secret value k and computes the value r = g k mod p, where g and p are public parameters. For Diffie-Hellman key exchange, the victim generates a secret exponent a and computes the public key exchange value A = g a mod p, where g and p are public parameters. Naive modular exponentiation algorithms like square-and-multiply operate bit by bit over the bits of the exponent: each iteration will execute a square operation, and if that bit of the exponent is a 1, will execute a multiply operation. More sophisticated modular exponentiation algorithms precompute a digit representation of the exponent using non-adjacent form (NAF), windowed non-adjacent form (wNAF) [START_REF] Möller | Improved techniques for fast exponentiation[END_REF], sliding windows, or Booth recoding [START_REF] Booth | A signed binary mutiplication technique[END_REF] and then operate on the precomputed digit representation. [START_REF] Daniel | A survey of fast exponentiation methods[END_REF].

Cache attacks on modular exponentiation. Cache timing attacks are one of the most commonly exploited families of side-channel attacks in the academic literature [Pag02, TTMH02, TSS + 03, Per05, Ber05, OST06]. There are many variants of these attacks, but they all share in common that the attacker is able to execute code on a CPU that is co-located with the victim process and shares a CPU cache. While the victim code executes, the attacker measures the amount of time that it takes to load information from locations in the cache, and thus deduces information about the data that the victim process loaded into those cache locations during execution. In the context of the modular exponentiation or scalar addition algorithms discussed above, a cache attack on a vulnerable implementation might reveal whether a multiply operation was executed at a particular bit location if the attacker can detect whether the code to execute the multiply instruction was loaded into the cache. Alternatively, for a precomputed digit representation of the number, the attacker may be able to use a cache attack to observe the digit values that were accessed [ASK07, [START_REF] Aciiçmez | A vulnerability in RSA implementations due to instruction cache analysis and its demonstration on OpenSSL[END_REF][START_REF] Benger | aah... just a little bit": A small amount of side channel can go a long way[END_REF].

Other attacks on modular exponentiation. Other families of side channels that have been used to exploit vulnerable modular exponentiation implementations include power analysis and differential power analysis attacks [START_REF] Paul | Differential power analysis[END_REF][START_REF] Kocher | Introduction to differential power analysis[END_REF], electromagnetic radiation [START_REF] Quisquater | Electromagnetic analysis (ema): Measures and counter-measures for smart cards[END_REF], acoustic emanations [START_REF] Daniel Genkin | RSA key extraction via low-bandwidth acoustic cryptanalysis[END_REF], raw timing [START_REF] Paul | Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems[END_REF], photonic emission [START_REF] Ferrigno | When AES blinks: Introducing optical side channel[END_REF], and temperature [START_REF] Hutter | The temperature side channel and heating fault attacks[END_REF]. These attacks similarly exploit code or circuits whose execution varies based on secrets. . While these attacks may reveal incomplete information, and thus serve as theoretical motivation for some of the algorithms we discuss, most of the vulnerabilities in this family of attacks can simply be used to read arbitrary memory with near-perfect precision, and cryptanalytic algorithms are rarely necessary.

Length-dependent operations. A final vulnerability class is implementations whose behavior depends on the length of a secret value, and thus variations in the behavior may leak information about the number of leading zeros in a secret. A simple example is copying a secret key to a buffer in such a way that it reveals the bit length of a secret key. In another example, the Raccoon attack observes that TLS versions 1.2 and below strips leading zeros from the Diffie-Hellman shared secret before applying the key derivation function, resulting in a timing difference depending on the number of hash input blocks required for the length of the secret. [MBA + 20]

Mathematical background

Lattices and lattice reduction algorithms Several of the algorithms we present make use of lattices and lattice algorithms. We will state a few facts about lattices, but try to avoid being too formal.

For the purposes of this tutorial, we will specify a lattice by giving a basis matrix B which is a n × n matrix of linearly independent row vectors with rational (but in our applications usually integer) entries. The lattice generated by B, written as L(B), consists of all vectors that are integer linear combinations of the row vectors of B. The determinant of a lattice is the absolute value of the determinant of a basis matrix: det

L(B) = | det B|.
Geometrically, a lattice resembles a discrete, possibly skewed, grid of points in n-dimensional space. This discreteness property ensures that there is a shortest vector in the lattice: there is a non-infinitesimal smallest length of a vector in the lattice, and there is at least one vector v 1 that achieves this length. For a random lattice, the Euclidean length of this vector is approximated using the Gaussian heuristic: |v 1 | 2 ≈ n/(2πe)(det L) 1/n . We often don't need this much precision; for lattices of very small dimension we will often use the quick and dirty approximation that

|v 1 | 2 ≈ (det L) 1/n .
The shortest vector in an arbitrary lattice is NP-hard to compute exactly, but the LLL algorithm [START_REF] Klaas Lenstra | Factoring polynomials with rational coefficients[END_REF] will compute an exponential approximation to this shortest vector in polynomial time: in the worst case, it will return a vector b 1 satisfying ||b 1 || 2 ≤ 2 (n-1)/4 (det L) 1/n . In practice, for random lattices, the LLL algorithm obtains a better approximation factor ||b 1 || 2 ≤ 1.02 n (det L) 1/n [START_REF] Nguyen | LLL on the average[END_REF]. In fact, the LLL algorithm will return an entire basis for the lattice whose vectors are good approximations for what are called the successive minima for the lattice; for our purposes the only fact we need is that these vectors will be fairly short, and for a random lattice they will be close to the same length. Current implementations of the LLL algorithm can be run fairly straightforwardly on lattices of a few hundred dimensions.

To compute a closer approximation to the shortest vector than LLL, one can use the BKZ algorithm [START_REF] Schnorr | A hierarchy of polynomial time lattice basis reduction algorithms[END_REF][START_REF] Schnorr | Lattice basis reduction: Improved practical algorithms and solving subset sum problems[END_REF]. This algorithm runs in time exponential in a block size, which is a parameter to the algorithm that determines the quality of the approximation factor. The theoretical guarantees of this algorithm are complicated to express; for our purposes we only need to know that for lattices of dimension below around 100, one can easily compute the shortest vector in the heuristically random-looking lattices we consider using the BKZ algorithm, and often can often find the shortest vector, or a "good enough" approximation to it, by using smaller block sizes. Theoretically, the LLL algorithm is equivalent to using BKZ with block size 2.

4 Key recovery methods for RSA

RSA Preliminaries

Parameter Generation.

To generate an RSA key pair, implementations typically start by choosing the public exponent e. By far the most common choice is to simply fix e = 65537. Some implementations use small primes like 3 or 17. Almost no implementations use public exponents larger than 32 bits. This means that attacks that involve brute forcing values less than e are generally feasible in practice.

In the next step, the implementation generates two random primes p and q such that p -1 and q -1 are relatively prime to e. The public modulus is N = pq. The private exponent is then computed as d = e -1 mod (p -1)(q -1).

The public key is the pair (e, N ). In theory, the secret key is the pair (d, N ), but in practice many implementations store keys in a data structure including much more information. For example, the PKCS#1 private key format includes the fields p, q, d p = d mod (p -1), d q = d mod (q -1), and q inv = q -1 mod p to speed encryption using the Chinese Remainder Theorem.

Encryption and Signatures. In textbook RSA, Alice encrypts the message m to Bob by computing c = m e mod N . In practice, the message m is not a "raw" message, but has first been transformed from the content using a padding scheme. The most common encryption padding scheme in network protocols is PKCS#1v1.5, but OAEP [START_REF] Bellare | Optimal asymmetric encryption[END_REF] is also sometimes used or specified in protocols. To decrypt the encrypted ciphertext, Bob computes m = c d mod N and verifies that m has the correct padding.

To generate a digital signature, Bob first hashes and pads the message he wishes to sign using a padding scheme like PKCS#1v1.5 signature padding (most common) or PSS (less common); let m be the hashed and padded message of this form. Then Bob generates the signature as s = m d mod N . Alice can verify the signature by computing the value m = s e mod N and verifying that m is the correct hashed and padded value.

Since encryption and signature verification only use the public key, decryp-tion and signature generation are the operations typically targeted by sidechannel attacks.

RSA-CRT. To speed up decryption, instead of computing c d mod N directly, implementations often use the Chinese remainder theorem (CRT). RSA-CRT splits the exponent d into two parts d p = d mod (p -1) and d q = d mod (q -1).

To decrypt using the Chinese remainder theorem, Alice would compute m p = c dp mod p and m q = c dq mod q. The message can be recovered with the help of the pre-computed value q inv = q -1 mod p by computing m = m p qq p + m q (1 -qq p ) = (m p -m q )qq inv + m q mod N. This is called Garner's formula [START_REF] Harvey | The residue number system[END_REF].

Relationships Between RSA Key Elements. For the purpose of secret key recovery, we typically assume that the attacker knows the public key.

RSA keys have a lot of mathematical structure that can be used to relate the different components of the public and private keys together for key recovery algorithms. The RSA public and private keys are related to each other as ed ≡ 1 mod (p -1)(q -1)

The modular equivalence can be removed by introducing a new variable k to obtain an integer relation

ed = 1 + k(p -1)(q -1) = 1 + k(N -(p + q) + 1)
We know that d < (p -1)(q -1), so k < e. The value of k is not known to the attacker, but since generally e ≤ 65537 in practice it is efficient to brute force over all possible values of k.

For attacks against the CRT coefficients d p and d q , we can obtain similar relations:

ed p = 1 + k p (p -1) and ed q = 1 + k q (q -1)

for some integers k p < e and k q < e. Brute forcing over two independent 16-bit values can be burdensome, but we can relate k p and k q as follows:

Rearranging the two relations, we obtain ed p -1-k p = k p p and ed q -1-k q = k q q. Multiplying these together, we get

(ed p -1 + k p )(ed q -1 -k q ) = k p k q N
Reducing the above modulo e, we get

(k p -1)(k q -1) ≡ k p k q N mod e (2)
Thus given a value for k p , we can solve for the unique value of k q mod e, and for applications that require brute forcing values of k p and k q we only need to brute force at most e pairs. [IGA + 15] The multiplier k also has a nice relationship to these values. Multiplying the relations from Equation 1 together, we have (ed p -1)(ed q -1) = k p (p -1)k q (q -1) Substituting (p -1)(q -1) = (ed -1)/k and reducing modulo e, we can relate the coefficients as k ≡ -k p k q mod e Any of the secret values p, q, d, d p , d q , or q inv suffices to compute all of the other values when the public key (N, e) is known.

From either p or q, computing the other values is straightforward.

For small e, N can be factored from d by computing

ed = 1 + k(p -1)(q -1) = 1 + k(N -(p + q) + 1) (3)
The integer multiplier k can be recovered by rounding (ed -1)/N . Once k is known, then Equation 3 can be rearranged to solve for s = p + q. Once s is known, we have (p+q) 2 = s 2 = p 2 +2N +q 2 and s 2 -4N = p 2 -2N +q 2 = (p-q) 2 . Then N can be factored by computing gcd((p + q) -(p -q), N ).

When e is small, p can be computed from d p as p = gcd((ed p -1)/k p + 1, N )

where k p can be brute forced from 1 to e. If k p is not known and is too large to brute force, with high probability for a random a, p = gcd(a edp-1 -1, N ).

Factoring from q inv is more complex. As noted in [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF], q inv satisfies q inv q 2 -q ≡ 0 mod N , and q can be recovered using Coppersmith's method, described below.

RSA Key Recovery with Consecutive bits known

This section covers techniques for recovering RSA private keys when large contiguous portions of the secret keys are known. The main technique used in this case is lattice basis reduction.

For the key recovery problems in this section, we can typically recover a large unknown chunk of bits of an unknown secret key value (p, d mod (p -1), or d). We typically assume that the attacker has access to the public key (N, e) but does not have any other auxiliary information (about q or d mod (q -1), for example.

Knowledge of large contiguous portions of secret keys is unlikely to arise in side channels that involve noisy measurements, but could arise in scenarios where secrets are being read out of memory that got corrupted in an identifiable region. They can also help make attacks more efficient if a high cost is paid to recover known bits. 4.2.1 Warm-up: Lattice attacks on low-exponent RSA with bad padding.

The main algorithmic technique used for RSA key recovery with contiguous bits is to formulate the problem as finding a small root of a polynomial modulo an integer, and then to use lattice basis reduction to solve this problem.

In order to introduce the main tool of using lattice basis reduction to find roots of polynomials, we will start with an illustrative example for the concrete application of breaking small-exponent RSA with known padding. In later sections we will show how to modify the technique to cover different RSA key recovery scenarios.

The original formulation of this problem is due to Coppersmith [START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF]. Howgrave-Graham [START_REF] Howgrave-Graham | Finding small roots of univariate modular equations revisited[END_REF] gave a dual approach that we find easier to explain and easier to implement. May's survey [START_REF] May | Using LLL-reduction for solving RSA and factorization problems[END_REF] contains a detailed description of the Coppersmith/Howgrave-Graham algorithm.

To set up the problem, we have an integer N , and a polynomial f (x) of degree k that has a root r modulo N , that is, f (r) ≡ 0 mod N . We wish to find r. Finding roots of polynomials can be done efficiently modulo primes [START_REF] Klaas Lenstra | Factoring polynomials with rational coefficients[END_REF], so this problem is easy to solve if N is prime or the prime factorization of N is known. The Coppersmith/Howgrave-Graham methods are generally of interest when the prime factorization of N is not known: it gives an efficient algorithm for finding all small roots (if they exist) modulo N of unknown factorization. Cast the problem as finding roots of a polynomial. Let a = 0x01FFFFFFFFFFFFFFFF0000 be the known padding string, offset to the correct byte location. We also know the length of the message; in this case m < 2 16 . Thus we have that c = (a + m) 3 mod N , for unknown small m. Let f (x) = (a + x) 3 -c; we have set up the problem so that we wish to find a small root m satisfying f (m) ≡ 0 mod N for the polynomial

f (x) =x 3 + 0x5fffffffffffffffd0000x 2 + 0x6f1c485f406ba1c069460efex + 0x203211880cdc43afe1c5c5f9
(We have reduced the coefficients modulo N so that they will fit on the page.)

Construct a lattice. Let the coefficients of f be f (x) = x 3 + f 2 x 2 + f 1 x + f 0 .
Let M = 2 16 be an upper bound on the size of the root m. We construct the matrix

B =     M 3 f 2 M 2 f 1 M f 0 0 N M 2 0 0 0 0 N M 0 0 0 0 N    
We then apply the LLL lattice basis reduction algorithm to the matrix. The shortest vector of the reduced basis is

v =(-0x66543dd72697M 3 , -0x35c39ac91a11c04M 2 , 0x3f 86f 973d67d25eae138M, -0x10609161b131f d102bc2a8)
Extract a polynomial from the lattice and find its roots. We then construct the polynomial

g(x) = -0x66543dd72697x 3 -0x35c39ac91a11c04x 2 + 0x3f 86f 973d67d25eae138x -0x10609161b131f d102bc2a8
The polynomial g has one integer root, 0x42, which is the desired solution for m. This specific 4 × 4 lattice construction works to find roots up to size N 1/6 . For the small key size we used in our example, this is only 16 bits, but since it scales directly with the modulus size, this same lattice construction would suffice to learn 170 unknown bits of message for a 1024-bit RSA modulus, or 341 bits of message for a 2048-bit RSA modulus. Lattice reduction on a 4 × 4 lattice basis is instantaneous. More detailed explanation. Why does this work? The rows of this matrix correspond to the coefficient vectors of the polynomials f (x), N x 2 , N x, and N . We know that each of these polynomials evaluated at x = m will be 0 modulo N . Each column is scaled by a power of M , so that the 1 norm of any vector in this lattice is an upper bound on the value of the corresponding (un-scaled) polynomial evaluated at r. For a vector

v = (v 3 M 3 , v 2 M 2 , v 1 M, v 0 ) in the lattice, |f (m)| = |v 3 m 3 + v 2 m 2 + v 1 m + v 0 | ≤ |v 3 M 3 | + |v 2 M 2 | + |v 1 M | + |v 0 | = |v| 1 for any |m| ≤ M .
We have constructed the lattice so that every polynomial g we extract from it has the property that g(m) ≡ 0 mod N . We have also constructed our lattice so that the length of the shortest vector in a reduced basis will be less than N . The only integer multiple of N less than N is 0, so by construction the polynomial corresponding to this short vector satisfies g(m) = 0 over the integers, not just modulo N . Since finding roots of polynomials over the integers, rationals, reals, and complex numbers can be done in polynomial time, we can compute the roots of this polynomial and check which of them is our desired solution.

This method will always work if the lattice is constructed properly. That is, we need to ensure that the reduced basis will contain a vector of length less than N . For this example, det B = M 6 N 3 . Heuristically, the LLL algorithm will find a vector of 2 norm |v| 2 ≤ 1.02 n (det B) 1/ dim B . We ignore the 1.02 n factor, and the difference between the 2 and 1 norms for the moment. Then the condition we wish to satisfy is

g(m) ≤ |v| 2 ≤ (det B) 1/n < M
For our example, we have (det B) 1/ dim L = (M 6 N 3 ) 1/4 < N . Solving for M , this will be satisfied when M < N 1/6 . In this case, N has 96 bits, and m is 16 bits, so the condition is satisfied.

This can be extended to N 1/e , where e is the degree of the polynomial f by using a larger dimension lattice. Howgrave-Graham's dissertation [HG] and May's survey [START_REF] May | Using LLL-reduction for solving RSA and factorization problems[END_REF] give detailed explanations of this method and improvements.

Factorization from consecutive bits of p.

In this section we show how to use lattices to factor the RSA modulus N if a large portion of contiguous bits of one of the factors (without loss of generality p) is known. Coppersmith solves this problem in [START_REF] Coppersmith | Finding a small root of a bivariate integer equation; factoring with high bits known[END_REF] but we find the reformulation from Howgrave-Graham as "approximate integer common divisors" [START_REF] Howgrave-Graham | Approximate integer common divisors[END_REF] simpler to apply, and will give that construction here.

Problem setup. Let N = pq be an RSA modulus with equal-sized p and q.

Choosing an example with numbers small enough to fit on the page, we have a 240-bit RSA modulus

N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5.
We assume N is known. Assume we know a large contiguous portion of the most significant bits b of p, so that p = a + r, where we do not know r but do know the value a = 2 b. Here = 30 is the number of unknown bits, or equivalently the left shift of the known bits.

In our example, we have

a = 0x68323401cb3a10959e7bfdc0000000
Cast the problem as finding the roots of a polynomial. Let f (x) = a+x.

We know that there is some value r such that f (r) = p ≡ 0 mod p. We do not know p, but we know that p divides N and we know N . We know that the unknown r is small, and in particular |r| < R for some bound R that is known. Here, R = 2 30 . Construct a lattice. We can form the lattice basis

B =   R 2 Ra 0 0 R a 0 0 N  
We then run the LLL algorithm on our lattice basis

B. Let v = (v 2 R 2 , v 1 R, v 0 )
be the shortest vector in the reduced basis. In our example, we get the vector

v =(-0x0x17213d8bc94R 2 , -0x1d861360160a4f86181R, 0xf9decdc1447c3f3843819a5d)
Extract a polynomial and find the roots. We form a polynomial f (x) = v 2 x 2 + v 1 x + v 0 . For our example,

f (x) =-0x17213d8bc94x 2 -0x1d861360160a4f86181x + 0xf9decdc1447c3f3843819a5d
We can then calculate the roots of f . In this example, f has one integer root, r = 0x873209. We can then reconstruct a + r and verify that gcd(a + r, N ) factors N .

This 3 × 3 lattice construction works for any |r| < p 1/3 , and directly scales as p increases. In our example, we chose p and q so that they have 120 bits, and r has 30 bits. However, this same construction will work to recover 170 bits from a 512-bit factor of a 1024-bit RSA modulus, or 341 bits from a 1024-bit factor of a 2048-bit RSA modulus. More detailed explanation. The rows of this matrix correspond to the coefficient vectors of the polynomials x(x + a), x + a, and N . We know that each of these polynomials evaluated at x = r will be 0 modulo p, and thus every polynomial corresponding to a vector in the lattice has this property. As in the previous example, each column is scaled by a power of R, so that the 1 norm of any vector in this lattice is an upper bound on the value of the corresponding (un-scaled) polynomial evaluated at r.

If we can find a vector in the lattice of length less than p, then it corresponds to a polynomial g that must satisfy g(r) < p. Since by construction, g(r) = 0 (mod p), this means that g(r) = 0 over the integers.

We compute the determinant of the lattice to verify that it contains a sufficiently small vector. For this example, det B = R 3 N . This means we need (det B) 1/ dim L = (R 3 N ) 1/3 < p. Solving for R, this gives R < p 1/3 . For an RSA modulus we have p ≈ N 1/2 , or R < N 1/6 . This method works up to R < p 1/2 at the limit by increasing the dimension of the lattice. This is accomplished by taking higher multiples of f and N . See Howgrave-Graham's dissertation [HG] and May's survey [START_REF] May | Using LLL-reduction for solving RSA and factorization problems[END_REF] for details on how to do this.

RSA key recovery from least significant bits of p

It is also straightforward to adapt this method to deal with a contiguous chunk of unknown bits in the least significant bits of p: if the chunk begins at bit position , the input polynomial will have the form f (x) = 2 x + a. This can be multiplied by 2 -mod N and solved exactly as above.

RSA key recovery from middle bits of p

RSA key recovery from middle bits of p is somewhat more complex than the previous examples, because there are two unknown chunks of bits in the most and least significant bits of p. Problem setup. Assume we know a large contiguous portion of the middle bits of p, so that p = a + r + 2 t r m , where a is an integer representing the known bits of p, r and r m are unknown integers representing the least and most significant bits of p that we wish to solve for, and t is the starting bit position of the unknown most significant bits. We know that |r | < R and |r m | < R for some bound R.

As a concrete example, let N =0x3ab05d0c0694c6bd8ee9683d15039e2f738558225d7d37f4a601bcb9 29ccfa564804925679e2f3542b be a 326-bit RSA modulus. Let a = 0xc48c998771f7ca68c9788ec4bff9b40b80000 be the middle bits of one of its factors p; there are 16 unknown bits in the most and least significant bit positions. Thus we know that R = 2 16 in our concrete example. We wish to recover p.

Cast the problem as finding solutions to a polynomial. In the previous examples, we only had one variable to solve for. Here, we have two, so we need to use a bivariate polynomial. We can write down f (x, y) = x + 2 t y + a, so that f (r , r m ) = p.

In our concrete example, p has 164 bits, so we have f (x, y) = x+2 148 y+a. We hope to construct two polynomials g 1 (x, y) and g 2 (x, y) satisfying g 1 (r , r m ) = 0 and g 2 (r , r m ) = 0 over the integers. Then we can solve the system for the simultaneous roots.

Construct a lattice. As before, we will use our input polynomial f and the public RSA modulus N to construct a lattice. Unfortunately for the simplicity of our example, the smallest polynomial that is guaranteed to result in a nontrivial bound on the solution size for our desired roots has degree 3, and results in a lattice of dimension 10.

As before, each column corresponds to a monomial that appears in our polynomials, and each row corresponds to a polynomial that evaluates to 0 mod p at our desired solution. In our example, we will use the polynomials f 3 , f 2 y, f y 2 , y 3 N, f 2 , f y, y 2 N, f, yN , and N ; the monomials in the columns are x 3 , x 2 y, xy 2 , y 3 , x 2 , xy, y 2 , x, y, and 1. Each column is scaled by the appropriate power of R.

B =                 R 3 3 • 2 t R 3 3 • 2 2t R 3 2 3t R 3 3aR 2 6 • 2 t aR 2 3 • 2 2t aR 2 3a 2 R 3 • 2 t a 2 R a 3 0 R 3 2 • 2 t R 3 2 2t R 3 0 2aR 2 2 • 2 t aR 2 0 a 2 R 0 0 0 R 3 2 t R 3 0 0 aR 2 0 0 0 0 0 0 R 3 N 0 0 0 0 0 0 0 0 0 0 R 2 2 • 2 t R 2 2 2t R 2 2aR 2 • 2 t aR a 2 0 0 0 0 0 R 2 2 t R 2 0 aR 0 0 0 0 0 0 0 R 2 N 0 0 0 0 0 0 0 0 0 0 R 2 t R a 0 0 0 0 0 0 0 0 RN 0 0 0 0 0 0 0 0 0 0 N                
We reduce this matrix using the LLL algorithm, and reconstruct the bivariate polynomials corresponding to each row of the reduced basis. Unfortunately, these are too large to fit on a page.

Solve the system of polynomials to find common roots. Heuristically, we would hope to only need two sufficiently short vectors and then compute the resultant of the corresponding polynomials or use a Gröbner basis to find the common roots, but in our example the two shortest vectors are not algebraically independent. In this case it suffices to use the first three vectors. Concretely, we construct an ideal over the ring of bivariate polynomials with integer coefficients whose basis is the polynomials corresponding to the three shortest vectors in the reduced basis for L(B) above, and then call a Gröbner basis algorithm on it. For this example, the Gröbner basis is exactly the polynomials (x -0x339b, y -0x5a94), which reveals the desired solutions for x = r and y = r m .

In this example, the nine shortest vectors all vanish at the desired solution, so we could have constructed our Gröbner basis from other subsets of these short vectors. More detailed explanation. The determinant of our lattice is det B = R 20 N 4 , and the lattice has dimension 10. We hope to find two vectors v 1 and v 2 of length approximately det B 1/ dim B ; this is not guaranteed to be possible, but for random lattices we expect the lengths of the vectors in a reduced basis to have close to the same lengths. The 1 norms of the vectors v 1 and v 2 are upper bounds on the magnitude of the corresponding polynomials f v1 (x, y), f v2 (x, y) evaluated at the desired roots r , r m . In order to guarantee that these vanish, we want the inequality

|f vi (r , r m )| ≤ |v i | 1 < p ≈ √ N to hold.
Thus the desired condition for success is

det B 1/ dim B < √ N (R 20 N 4 ) 1/10 < N 1/2
R 20 < N

In our example, N was 326 bits long, and we chose R to have 16 bits. This attack was applied in [BCC + 13] to recover RSA keys generated by a faulty random number generator that generated primes with predictable sequences of bits.

RSA key recovery from multiple chunks of bits of p

The above idea can be extended to handle more chunks of p at the cost of increasing the dimension of the lattice. Each unknown "chunk" of bits introduces a new variable in the linear equation that will be solved for p. At the limit, the algorithm requires 70% of the bits of p divided into at most log log N blocks [START_REF] Herrmann | Solving linear equations modulo divisors: On factoring given any bits[END_REF].

Open problem: RSA key recovery from many nonconsecutive bits of p

The above methods scale poorly with the number of chunks of known bits.

It is an open problem to develop a subexponential-time method to recover an RSA key or factor the RSA modulus N with more than log log N unknown chunks of bits, if these bits are only known about, say, one factor p of N . If information is known about both p and q or other fields of the RSA private key, then the methods of Section 4.3.1 may be applicable.

Partial recovery of RSA d p

Recovering the CRT coefficient d p = d mod (p -1) from a large contiguous bits can be done using the approach given in Sections 4.2.2, 4.2.3 and 4.2.4. We illustrate the method in the case of known most significant bits.

d q d p 2 b r N Recovering RSA d p = d mod (p -1)
given many contiguous bits of d p .

Problem setup. Let N = 0x4d14933399708b4a5276373cb5b756f312f023c43d60b323ba24cee670f5 be a 240-bit RSA modulus. We will use public exponent e = 65537.

In this problem, we are given some of the most significant bits b of d p , and we want to recover the rest. As before, let be the number of least significant bits of d p we need to recover, so that there is some value a = 2 b with a + r = d p for some r < 2 . For our concrete example, we have a = 0x25822d06984a06be5596fcc0000000.

Cast the problem as finding the roots of a polynomial We start with the relation ed p ≡ 1 mod (p -1) and rewrite it as an integer relation by introducing a new variable k p :

ed p = 1 + k p (p -1). (4)
The integer k p is unknown, but we know that k p < e since d p < (p -1). In our example, and typically in practice, we have e = 65537, so we will run the attack for all possible values of 1 ≤ k p < 65537. With the correct parameters, we are guaranteed to find a solution for the correct value of k p . For other incorrect guesses of k p , in practice the attack is unlikely to result in any solutions found, but any spurious solutions that arise can be eliminated because they will not result in a factorization of N .

We can rearrange Equation 4, with e -1 computed modulo N :

e(a + r) -1 + k p ≡ 0 mod p a + r + e -1 (k p -1) ≡ 0 mod p Let A = a+e -1 (k p -1
). Then we wish to find a small root r of the polynomial f (x) = A + x modulo p, where |r| < R.

For our concrete example, we have R = 2 30 and k p = 23592, so

A = 0x8ffe9143aa4c189787058057a0784576848f3f28d79a83169f72a0550699112
Construct a lattice. Since the form of the problem is identical to the previous section, we use the same lattice construction:

B =   R 2 RA 0 0 R A 0 0 N  
We apply the LLL algorithm to this basis and take the shortest vector in the reduced basis. For our example, this is

v = (-1306dd0a37ecR 2 , 52955e433295de64273R, -31db63ed6f29f4d8f4d1501c47)
We construct the corresponding polynomial

f (x) = -1306dd0a37ecx 2 +52955e433295de64273x-31db63ed6f29f4d8f4d1501c47
Computing the roots of f , we discover that r = 0x39d9b141 is among them, and that gcd(A + r, N ) = p.

At the limit, this technique can work up to R < p 1/2 [BM03] by increasing the dimension of the lattice with higher degree polynomials and higher multiplicities of the root.

Partial recovery of RSA d from most significant bits is not possible

Partial recovery for d varies somewhat depending on the bits that are known and the size of e. Since e is small in practice, we will focus on that case here. Most significant bits of d. When e is small enough to brute force, the most significant half of bits of d can be recovered easily with no additional information. This implies that if full key recovery were possible from only the most significant half of bits of d, then small public exponent RSA would be completely broken. Since small public exponent RSA is not known to be insecure in general, this unfortunately means that no such key recovery method is possible for this case.

Consider the RSA equation ed = 1 mod (p -1)(q -1)

ed = 1 + k(p -1)(q -1) ed = 1 + k(N -(p + q) + 1) d = kN/e -(k(p + q -1) -1)/e
Since p + q ≈ √ N , the second term affects only the least significant half of the bits of d, so the value kN/e shares approximately the most significant half of its bits in common with d.

On the positive side, this observation allows the attacker to narrow down possible values for k if the attacker knows any most significant bits of d for certain. See Boneh, Durfee, and Frankel [START_REF] Boneh | The decision Diffie-Hellman problem[END_REF] for more details.

Partial recovery of RSA d from least significant bits

For low-exponent RSA, if an adversary knows the least significant t bits of d, then this can be transformed into knowledge of the least significant t bits of p, and then the method of Section 4.2.3 can be applied. This algorithm is due to Boneh, Durfee, and Frankel [START_REF] Boneh | The decision Diffie-Hellman problem[END_REF]. Assume the adversary knows the t least significant bits of d; call this value d 0 . Then ed 0 ≡ 1 + k(N -(p + q) + 1) mod 2 t Let s = p + q. The adversary tries all possible values of k, 1 < k < e to obtain e candidate values for the t least significant bits of s.

Then for each candidate s, the least significant bits of p are solutions to the quadratic equation

p 2 -sp + N ≡ 0 mod 2 t .
Let a be a candidate solution for the least significant bits of p. Putting this in the context of Section 4.2.3, the attacker wishes to solve f (x) = a + 2 t x ≡ 0 mod p. This can be multiplied by 2 -t mod N and the exact method of Section 4.2.3 can be applied to recover p. Since at the limit, the methods of Section 4.2.3 work to recover N 1/4 bits of p, this method will work when as few as N 1/4 bits of d are known.

There are more sophisticated lattice algorithms that involve different tradeoffs, but for very small e, which is typically the case in practice, they require nearly all of the least significant bits of d to be known [START_REF] Blömer | New partial key exposure attacks on RSA[END_REF].

Non-consecutive bits known with redundancy

This section covers key recovery in the case that many non-consecutive bits of secret values are known or need to be recovered. The lattice methods covered in the previous section can be adapted to recover multiple chunks of unknown key bits, but at a high cost: the lattice dimension increases with the number of chunks, and when a large number of bits is to be recovered, the running time can be exponential in the number of chunks.

In this section, we explore a different technique that allows a different tradeoff. In this case, the attacker has knowledge of many non-contiguous bits of secret key values, and knows these for multiple secret values of the key. The attacker might have learned parts of both p and q, or d mod (p -1) and d mod (q -1), for example. We begin by analyzing a case that is less likely to arise in practice, the case of random erasures of bits of p and q, in order to give the main ideas behind the algorithm in the simplest setting.

The main technique used for these cases is a branch and prune algorithm. The idea behind the branch and prune algorithm is to write down an integer relationship between the elements in the secret key and the public key, and progressively solve for unknown bits of the secret key, starting at the least significant bits. This produces a tree of solutions: every branch corresponds to guesses for one or more unknown bits at a particular solution, and branches are pruned if the guesses result in incorrect relationships to the public key.

This algorithm is presented and analyzed in [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF].

Problem setup. Let N = 899. Imagine we have learned some bits of p and q, in an erasure model: for each bit position, we either know the bit value, or we know that we do not know it. For example, we have p = 11 1, and q = 1 0 .

Defining an integer relation. The integer relation that we will take advantage of for this example is N = pq.

4.3.2

Random known bits of the Chinese remainder coefficients d mod (p -1) and d mod (q -1)

The description in Section 4.3.1 can be extended to recover the Chinese remainder exponents d p = d mod (p -1) and d q = d mod (q -1) using the same technique as the previous section. This is the most common case encountered in RSA side channel attacks.

d q d p
Factorization of N = pq given non-consecutive bits of d p , d q .

Problem setup. Let N = 899 be the RSA public modulus, and e = 17 be the public exponent. Imagine that the adversary has recovered some bits of the secret Chinese remainder exponents d p = d mod (p -1) and d q = d mod (q -1).

d p = 0 1, d q = 0
We wish to recover the missing unknown bits of d p and d q , which will allow us to recover the secret key itself.

Define integer relations. We know that ed p ≡ 1 mod (p -1) and ed q ≡ 1 mod (q -1). We rewrite these as integer relations ed p = 1 + k p (p -1), ed q = 1 + k q (p -1).

We have no information about the values of p and q, but their values are uniquely determined from a guess for d p or d q .

We also know that pq = N.

The values k p and k q are unknown, so we must brute force them by running the algorithm for all possible values. We expect it to fail for incorrect guesses, and succeed for the unique correct guess. Equation 2 in Section 4.1 shows that there is a unique value of k q for a given guess for k p . Since k p < e we need to brute force at most e pairs of values for k p and k q .

In our example, we have k p = 13 and k q = 3, although this won't be verified as the correct guesses until the solution is found.

Iteratively solve for each bit. With our integer relations in place, we can then use them to iteratively solve for each bit of the unknowns d p , d q , p, and q, starting from the least significant bit. We check guesses for each value against our three integer relations, and at bit i we prune those that do not satisfy the relations mod 2 i . We have three relations and four unknowns, so we generate at most two new branches at each bit.

ed p -1 + k p ≡ k p p mod 2 i , ed q -1 + k q ≡ k q q mod 2 i , pq ≡ N mod 2 i .
Since the values of p and q up to bit i are uniquely determined by our guess for d p and d q up to bit i, the algorithm prunes solutions based on the relation pq ≡ N mod 2 i . The analysis of this case is then identical to the case of learning bits of p and q at random.

For incorrect guesses for the values of k p and k q , we expect the equations to act like random constraints, and thus to quickly become unsatisfiable. Once there are no more possible solutions in a tree, the guess for k p and k q is known to be incorrect. This is illustrated by Figure 11.

Recovering RSA keys from indirect information

For this type of key recovery algorithm, it is not always necessary to have direct knowledge of bits of the secret key values with certainty. It can still be possible to apply the branch-and-prune technique to recover secret keys even if only "implicit" information is known about the secret values, as long as this implicit information implies a relationship that can be checked to prioritize or prune candidate key guesses from the least significant bits. Examples in the literature include [BBG + 17], which computes partial sliding window square-and-multiply sequences for candidate guesses and compares them to the ground truth measurements, and [MVH + 20], which compares the sequence of program branches in a binary GCD algorithm implementation computed over the cryptographic secrets to a ground truth measurement.

Open problem: Random known bits without redundancy

As mentioned in Section 4.2.6, it is an open problem to recover an RSA secret key when many nonconsecutive chunks of bits need to be recovered, and the bits known are from only one secret key field, with no additional information from other values. Applying the branch-and-prune methods discussed in this secction to a single secret key value, say a factor p of N , where random bits are known, would result in a tree with exponentially many solutions unless additional information were available to prune the tree.

5 Key recovery methods for DSA and ECDSA

DSA and ECDSA preliminaries

From the perspective of partial key recovery, DSA and ECDSA are very similar, and we will cover them together. We will use slightly nonstandard notation to describe each signature scheme to make them as close as possible, so that we can use the same notation to describe the attacks simultaneously.

DSA

The Digital Signature Algorithm [START_REF]Digital Signature Standard (DSS)[END_REF] (DSA) is an adaptation of the ElGamal Signature Scheme [START_REF] El | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] that reduces the amount of computation required and the resulting signature size by using Schnorr groups [START_REF] Schnorr | Efficient identification and signatures for smart cards[END_REF].

Parameter Generation. A DSA public key includes several global parameters specifying the group to work over: a prime p, a subgroup of order n satisfying n | (p -1), and an integer g that generates a group of order n mod p, where n is typically much smaller than p, for example 256 bits for a 2048-bit p. A single set of group parameters can be shared across many public keys, or individually generated for a given public key.

To generate a long-term private signing key, an implementation starts by choosing the secret key 0 < d < n and computing y = g d mod p. The public key is the tuple (y, g, p, n) and the private key is (d, g, p, n).

Signature Generation.

To sign a message m, implementations apply a collision-resistant hash function H to m to obtain a hashed message h = H(m). To generate the signature, the implementation generates an ephemeral secret integer 0 < k < n, and computes the integers r = g k mod p mod n, and s = k -1 (h + dr) mod n. The signature is the pair (r, s).

ECDSA

The Elliptic Curve Digital Signature Algorithm (ECDSA) is an adaptation of DSA to use elliptic curves instead of Schnorr groups.

Parameter Generation. An ECDSA public key includes global parameters specifying an elliptic curve E over a finite field together with a generator point g of a subgroup over E of order n.

To generate a long-term private signing key, an implementation starts by choosing a secret integer 0 < d < n, and computing the elliptic curve point y = dg on E. The public key is the elliptic curve point y together with the global parameters specifying E, g, and n. The private key is the integer d together with these global parameters.

Signature Generation.

To sign a message m, implementations apply a collision-resistant hash function H to m to obtain a hashed message h = H(m). To generate the signature, the implementation generates an ephemeral secret 0 < k < n. The implementation computes the elliptic curve point kg and sets the value r to be the x-coordinate of kg. The implementation then computes the integer s = k -1 (h + dr) mod n. The signature is the pair of integers (r, s).

Nonce recovery and (EC)DSA security.

The security of (EC)DSA is extremely dependent on the signature nonce k being securely generated, uniformly distributed, and unique for every signature. If the nonce for one or more signatures is generated in a vulnerable manner, then an attacker may be able to efficiently recover the long-term secret signing key. Because of this property, side channel attacks against (EC)DSA almost universally target nonce generation.

Key recovery from signature nonce. For a DSA or ECDSA key, if the nonce k is known for a single signature, it is simple to compute the long-term private key. Rearranging the expression for s, the secret key d can be recovered as d = r -1 (ks -h) mod n (5)

(EC)DSA key recovery from most significant bits of the nonce k

There are two families of techniques for (EC)DSA key recovery from most significant bits of the nonce k. Both techniques require knowing information about the nonce used in multiple signatures from the same secret key. We assume that the attacker knows the long-term public signature verification key, and has access to multiple signatures generated using the corresponding secret signing key. The attacker also needs to know the hash of the messages that the signatures correspond to. The first technique is via lattices. This is generally considered more straightforward to implement, and works well when more nonce bits are known, and information from fewer signatures is available: we would need to know at least two most significant bits from the nonces of dozens to hundreds of signatures. We cover this technique below.

k 1 k 2 . . .
The second technique is via Fourier analysis. This technique can deal with as little as one known most significant bit from signature nonces, but empirically appears to require an order of magnitude or more signatures than the lattice approach. Recent works report using 2 23 [ANT + 20], 2 35 [ANT + 20], and 2 26 [TTA18] signatures for record computations. We leave a more detailed discussion of this technique to a future version of this survey. Nice descriptions of the algorithm can be found in [START_REF] Mulder | Using Bleichenbacher's solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA[END_REF][START_REF] Takahashi | New Bleichenbacher records: Fault attacks on qDSA signatures[END_REF].

Lattice attacks

The main idea behind lattice attacks for (EC)DSA key recovery is to formulate the (EC)DSA key recovery problem as an instance of the Hidden Number Problem and then compute the shortest vector of a specially constructed lattice to reveal the solution.

Below we give a simplified example that shows how to recover the key from a small number of signatures when many of the most significant bits of the nonce are zero, and then we will show how to extend the attack to more signatures with fewer bits known from each nonce, and cover the case of arbitrary bits known from the nonce.

Problem setup. Let p = 0xffffffffffffd21f be a 64-bit prime, and let E : y 2 = x 3 + 3 be an elliptic curve over F p . Let g = (1, 2) be our generator point on E, which has order n = 0xfffffffefa23f437.

We have two ECDSA signatures (r 1 , s 1 ) =(6393e79fbfb40c9c, 621ee64e65d1e938)

on message hash h 1 = ae0f1d8cd0fd6dd1 and (r 2 , s 2 ) =(3ea8720afa6d03c2, 16fc6aa65bf241ea)
on message hash h 2 = 8927e246fe4f3941

These signatures both use 32-bit nonces k; that is, we know that their 32 most significant bits are 0.

Cast the problem as a system of equations. Our signatures above satisfy the equivalencies

s 1 ≡ k -1 1 (h 1 + dr 1 ) mod n s 2 ≡ k -1 2 (h 2 + dr 2 ) mod n
The values k 1 , k 2 , and d are unknown; the other values are known. We can eliminate the variable d and rearrange terms as follows:

k 1 -s -1 1 s 2 r 1 r -1 2 k 2 + s -1 1 r 1 h 2 r -1 2 -s -1 1 h 1 ≡ 0 mod n Let t = -s -1 1 s 2 r 1 r -1 2 and u = s -1 1 r 1 h 2 r -1 2 -s -1 1 h 1 .
We can then simplify the above as

k 1 + tk 2 + u ≡ 0 mod n (6)
We wish to solve for k 1 and k 2 , and we know that they are both small. Let |k 1 |, |k 2 | < K. For our example, we have K = 2 32 .

Construct a lattice. We construct the following lattice basis:

B =   n 0 0 t 1 0 u 0 K   The vector v = (k 1 , k 2 , K
) is in this lattice by construction, and we expect it to be particularly short.

Calling the BKZ algorithm on B results in a basis that contains this short vector v = (-0x270feca3, 0x4dbd2db0, 0x100000000)

as the third vector in the reduced basis. We can verify that the value r 1 in our example matches the x-coordinate of k 1 g, and we can use Equation 5 to compute the private key d.

More detailed explanation. In our example, we have constructed a lattice that is guaranteed to contain our target vector. In order for this method to work, we hope that it is the shortest vector, or close to the shortest vector in the lattice, and we solve the shortest vector problem in the lattice in order to find it. The vector v = (k 1 , k 2 , K) has length |v| 2 ≤ √ 3K by construction. Our lattice has determinant det B = nK. Ignoring constants for the moment, if our lattice were truly random, we would expect the shortest vector to have length

≈ det B 1/ dim B . Thus if |v| 2 < det B 1/ dim B ,
we expect it to be the shortest vector in the lattice, and to be found by a sufficiently good approximation to the shortest vector problem.

For our example, we expect this to be satisfied when K < (nK) 1/3 , or when K < √ n. The way we have presented this method may remind the reader of the flavor of the methods in Section 4.2.1. The specific lattice construction used here is a sort of "dual" to the constructions from Section 4.2.1, in that the target vector is the desired solution to our system of equations. However, in contrast to Section 4.2.1, we are not guaranteed to find the solution we desire once we find a sufficiently short vector: this method can fail with probability that decreases the shorter our target vector d is compared to the expected shortest vector length.

The Hidden Number Problem

The lattice-based algorithms we describe for solving these problems are based on the Hidden Number Problem introduced by Boneh and Venkatesan [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[END_REF]. They applied the technique to show that the most significant bits of a Diffie-Hellman shared secret are hardcore. Nguyen and Shparlinski showed how to use this approach to break DSA and ECDSA from information about the nonces [START_REF] Phong | The insecurity of the Digital Signature Algorithm with partially known nonces[END_REF][START_REF] Phong | The insecurity of the Elliptic Curve Digital Signature Algorithm with partially known nonces[END_REF]. Various extensions of the technique can deal with different numbers of bits known per signature [START_REF] Benger | aah... just a little bit": A small amount of side channel can go a long way[END_REF] or errors [DDME + 18].

There is another algorithm to solve this problem using Fourier analysis [Ble98, DHMP13] originally due to Bleichenbacher; it requires more samples than the lattice approach but can handle fewer bits known.

Scaling to many signatures to decrease the number of bits known.

To decrease the number of bits required from each signature, we can incorporate more signatures into the lattice. If we have access to many signatures (r 1 , s 1 ), . . . , (r m , s m ) on message hashes h 1 , . . . , h m , we use the same method above to write down equivalencies s i ≡ k -1 i (h i + dr i ) mod n, then as above we rearrange terms and eliminate the variable d to obtain

k 1 + t 1 k m + u 1 ≡ 0 mod n k 2 + t 2 k m + u 2 ≡ 0 mod n . . . k m-1 + t m-1 k m + u m-1 ≡ 0 mod n (7)
We then construct the lattice

B =          n n . . . n t 1 t 2 . . . t m 1 u 1 u 2 . . . u m 0 K         
In order to solve SVP, we must run an algorithm like BKZ with block size dim L(B) = m + 1. Using BKZ to look for the shortest vector can be done relatively efficiently up to dimension around 100 currently; beyond that it becomes increasingly expensive. In practice, one can often achieve a faster running time for fixed parameters by using more samples to construct a larger dimension lattice, and applying BKZ with a smaller block size to find the target vector. This method can recover a secret key from knowledge of the 4 most significant bits of nonces from 256-bit ECDSA signatures using about 70 samples, and 3 most significant bits using around 95 samples. For fewer bits known, either the Fourier analysis technique or a more powerful application of these lattice techniques is required, along with significantly more computational power.

Known nonzero most significant bits. If the most significant bits of the k i are nonzero and known, we can write k i = a i + b i , where the a i are known, and the b i are small, so satisfy some bound |b i | < K. Then substituting into Equation 6, we obtain

(a i + b i ) + t i (a m + b m ) + u i ≡ 0 mod n b i + t i b m + u i + a i + t i a m ≡ 0 mod n Thus we can let u i = u i + a i + t i b m ,
and use the same lattice construction as above, with u i substituted for u i .

Nonce rebalancing. The signature nonces k i take values in the range 0 < k i < n, but the lattice construction bounds the absolute value |k i |. Thus if we know that 0 < k i < K for some bound K, we can achieve a tighter bound by renormalizing the signatures. Let k i = k i -K/2, so that |k i | < K/2. Then we can write Equations 7 as

k i + t i k m + u i ≡ 0 mod n (k i + K/2 + t i (k m + K/2) + u i ≡ 0 mod n k i + t i k m + (t i + 1)K/2 + u i ≡ 0 mod n
Thus we have an equivalent problem with t i = t i , u i = (t i + 1)K/2 + u i , and K = K/2, and can solve as before. This optimization can make a significant difference in practice by reducing the number of required samples.

(EC)

DSA key recovery from least significant bits of the nonce k

The attack described in the previous section works just as well for known least significant bits of the (EC)DSA nonce. Problem setup. We input a collection (EC)DSA signatures (r i , s i ) on message hashes h i . For each signature, we know the least significant bits, so the signature nonces k i satisfy

k 1 k 2 2 b i a i . . .
k i = a i + 2 b i
for known a i , and b i unknown but satisfying |b i | < B. Substituting these into Equations 7, we get

a i + 2 b i + t i (a m + 2 b m ) + u i ≡ 0 mod n 2 b i + 2 t i b m + a i + t i a m + u i ≡ 0 mod n b i + t i b m + 2 -(a i + t i a m + u i ) ≡ 0 mod n
We have an equivalent instance of the problem with t i = t i , u i = 2 -(a i + t i a m + u i ), and B = B, and solve as above. Recovering an ECDSA key from middle bits of the nonce k is slightly more complex than the methods discussed above, because we have two unknown "chunks" of the nonce to recover per signature. Fortunately, we can deal with these by extending the methods to multiple variables per signature. The method we will use here is similar to the multivariate extension in Section 4.2.4, but this case is simpler.

(EC)DSA key recovery from middle bits of the nonce

k k 1 k 2 2 c i b i a i . . .
Problem setup. We will use the same elliptic curve group parameters as above. Let p = 0xffffffffffffd21f be a 64-bit prime, and let E : y 2 = x 3 + 3 be an elliptic curve over F p . Let g = (1, 2) be our generator point on E, which has order n = 0xfffffffefa23f437.

We have two ECDSA signatures (r 1 , s 1 ) =(1a4adeb76b4a90e0, eba129bb2f97f7cd)

on message hash h 1 = 608932fcfaa7785d and (r 2 , s 2 ) =(c4e5bec792193b51, 0202d6eecb712ae3)

on message hash h 2 = 4de972930ab4a534
We know some middle bits of the corresponding nonces. Let

a 1 = 0x50e2fd5d8000
be the middle 34 bits of the signature nonce k 1 used for the first signature above. The first and last 15 bits are unknown. Let

a 2 = 0x172930ab48000
be the middle 34 bits of the signature nonce k 2 used for the second signature above.

Cast the problem as a system of equations. As above, our two signature nonces k 1 and k 2 satisfy the

k 1 + tk 2 + u ≡ 0 mod n (8)
where t = -s -1 1 s 2 r 1 r -1 2 and u = s -1 1 r 1 h 2 r -1 2 -s -1 1 h 1 . Since we know the middle bits of k 1 and k 2 are a 1 and a 2 respectively, we can write Let u = a 1 + ta 2 + u. We wish to find the small solution

k 1 = a 1 + b 1 + 2 c 1 and k 2 = a 2 + b 2 + 2 c 2 where b 1 , c 1 , b 2 ,
x 1 = b 1 , y 1 = c 1 , x 2 = b 2 , y 2 = c 2 to the linear equation f (x 1 , y 2 , x 2 , y 2 ) = x 1 + 2 y 1 + tx 2 + 2 ty 2 + u ≡ 0 mod n (9)
Construct a lattice. We construct the following lattice basis:

B =       K K • 2 49 Kt Kt • 2 49 u Kn Kn Kn n      
If we call the BKZ algorithm on B, we obtain a basis that contains the vector v = (0x6589e5fb1823K, -0x42b0986d3e11K, 0x8d3b91566f89K, 0x41be198fb49eK, -0x1dd626d2645d8f7e)

This corresponds to the linear equation

0x6589e5fb1823x 1 -0x42b0986d3e11y 1 + 0x8d3b91566f89x 2 + 0x41be198fb49ey 2 -0x1dd626d2645d8f7e = 0
We can do the same for the next three short vectors in the basis, and obtain four linear polynomials in our four unknowns. Solving the system, we obtain the solutions

x 1 = 0x241c y 1 = 0x39a2 x 2 = 0x2534 y 2 = 0x26f4
More detailed explanation. The row vectors of the lattice correspond to the weighted coefficient vectors of the linear polynomial f in Equation 9, nx 1 , ny 1 , nx 2 , and ny 2 . Each of these linear polynomials vanishes by construction modulo n when evaluated at the desired solution x 1 = b 1 , y 1 = c 1 , x 2 = b 2 , y 2 = c 2 , and thus so does any linear polynomial corresponding to a vector in this lattice. If we can find a lattice vector whose 1 norm is less than n, then the corresponding linear equation vanishes over the integers when evaluated at the desired solution. Since we have four unknowns, if we can find four sufficiently short lattice vectors corresponding to four linearly independent equations, we can solve for our desired unknowns. The determinant of our example lattice is det B = K 4 n 4 , and the lattice has dimension 5. Thus, ignoring approximation factors and constants, we expect to find a vector of length det B 1/ dim B = (Kn) (4/5) . This is less than n when K 4 < n; in our example this is satisfied because we have chosen a 15-bit K and a 64-bit n.

The determinant bounds guarantee that we will find one short lattice vector, but do not guarantee that we will find four short lattice vectors. For that, we rely on the heuristic that the reduced vectors of a random lattice are close to the same length.

(EC)DSA key recovery from many chunks of nonce bits

The above technique can be extended to an arbitrary number of variables. The extension is called the Extended Hidden Number problem [START_REF] Hlavác | Extended hidden number problem and its cryptanalytic applications[END_REF] and can be used to solve for ECDSA keys when many chunks of signature nonces are known. Each unknown "chunk" of nonce in each signature introduces a new variable, so the resulting lattice will have dimension one larger than the total number of unknowns; if there are m signatures and h unknown chunks of nonce per signature, the lattice will have dimension mh + 1. We expect this technique to find the solution when the parameters are such that the system of equations has a unique solution. If the size of each chunk is K, heuristically this will happen when K mh < n m-1 . This technique has been used in practice in [START_REF] Fan | Attacking OpenSSL implementation of ECDSA with a few signatures[END_REF] and further explored in [START_REF] De Micheli | A tale of three signatures: Practical attack of ECDSA with wNAF[END_REF].

6 Key recovery method for the Diffie-Hellman Key Exchange 6.1 Finite field and elliptic curve Diffie-Hellman preliminaries

The Diffie-Hellman (DH) key exchange protocol [START_REF] Diffie | New directions in cryptography[END_REF] allows two parties to create a common secret in a secure manner. We summarize the protocol in the context of finite fields and elliptic curves.

Finite field Diffie-Hellman. Finite-field Diffie-Hellman parameters are specified by a prime p and a group generator g. Common implementation choices are p a safe prime, i.e., q = (p -1)/2 is prime, in which case g is often equal to 2, 3 or 4, or p is chosen such that p -1 has a 160, 224, or 256-bit prime factor q and g generates a subgroup of F * p of order q. Key exchange is performed as follows:

1. Alice chooses a random private key a, where 1 ≤ a < q and computes a public key A = g a mod p.

2. Bob chooses a random private key b, where 1 ≤ b < q and computes a public key B = g b mod p.

3. Alice and Bob exchange the public keys.

4. Alice computes s A = B a mod p.

Bob computes s

B = A b mod p.
Because B a mod p = (g b ) a mod p = (g a ) b mod p = A b mod p, we have s A = s B . The latter is the secret that now Alice and Bob share.

Elliptic Curve Diffie-Hellman The Elliptic Curve Diffie-Hellman (ECDH) protocol is the elliptic curve counterpart of the Diffie-Hellman key exchange protocol. In ECDH, Alice and Bob agree on an elliptic curve E over a finite field and a generator G of order q. The protocol proceeds as follows:

1. Alice chooses a random private integer a, where 1 ≤ a < q and computes a public key A = aG.

2. Bob chooses a random private integer b, where 1 ≤ b < q and computes a public key B = bG.

3. Alice and Bob exchange the public keys.

4. Alice computes s A = aB.

Bob computes s

B = bA.

The shared secret is s

A = aB = a(bG) = b(aG) = bA = s B .

Most significant bits of finite field Diffie-Hellman shared secret

The Hidden Number Problem approach we used in the previous section to recover ECDSA or DSA keys from information about the nonces can also be used to recover a Diffie-Hellman shared secret from most significant bits.

B c r i k i s sB c
Recovering Diffie-Hellman shared secret from most significant bits of s.

Problem setup. Let p = 0xffffffffffffffffffffffffffffc3a7 be a 128bit prime used for finite field Diffie-Hellman, and let g = 2 be a generator of the multiplicative group modulo p.

Let s the Diffie-Hellman shared secret s between public keys A = g a mod p = 0x3526bb85185259cd42b61e5532fe60e0 and B = g b mod p = 0x564df0b92ea00ea314eb5a246b01ac9c.

We have learned the value of the first 65 bits of s: let r 1 = 0x3330422f6047011b8000000000000000, so we know that s = r 1 + k 1 where k 1 < K = 2 63 . Let c = 0x56e112dac14f4a4cc02951414aa43a38. We have also learned the most significant 65 bits of the Diffie-Hellman shared secret between AC = g a+c = g a g c mod p and B. Let

r 2 = 0x80097373878e37d20000000000000000. We know that g (a+c)b = g ab g bc = sB c mod p. Let t = B c so st = r 2 + k 2 mod p where k 2 < K = 2 63 .
Cast the problem as a system of equations. We have two relations

s = r 1 + k 1 mod p st = r 2 + k 2 mod p
where s, k 1 , and k 2 are small and unknown, and r 1 , r 2 , and t are known. We can eliminate the variable s to obtain the linear equation

k 1 -t -1 k 2 + r 1 -t -1 r 2 ≡ 0 mod p
We now have a linear equation in the same form as the Hidden Number Problem we solved in the previous section. Construct a lattice. We construct the lattice basis

M =   p t -1 1 a 1 -t -1 a 2 K  
If we call the LLL algorithm on M , we obtain a basis that contains the vector (-0x2ddb23aa673107bd, -0x216afa75f66a39d5, 0x10000000000000000)

This corresponds to our desired solution (k 1 , k 2 , K), although if the Diffie-Hellman assumption is true we cannot verify its correctness. More detailed explanation. This method is due to Boneh and Venkatesan [START_REF] Boneh | Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes[END_REF], and was the original motivation for their formulation of the Hidden Number Problem. The Raccoon attack recently demonstrated an attack scenario using this technique in the context of TLS [MBA + 20].

This method can be adapted to multiple samples with the same number of bits required as the attacks on ECDSA. Knowing the most significant bits of s is not necessary either; we only need the most significant bits of known multiples t i of s.

Discrete log from contiguous bits of Diffie-Hellman secret exponents

This section addresses the problem of Diffie-Hellman key recovery when the known partial information is part of one or the other of the secret exponents.

The technique we apply in this section is Pollard's kangaroo (also known as lambda) algorithm [START_REF] Pollard | Monte Carlo methods for index computation mod p[END_REF]. Unlike the techniques of the previous sections, which are generally efficient when the attacker's knowledge of the key is above a certain threshold, and either inefficient or infeasible when the attacker's knowledge of the key is below this threshold, this algorithm runs in exponential time: square root of the size of the interval. Thus it provides a significant benefit over brute force, but in practice is likely limited to 80 bits or fewer of key recovery unless you have access to an unusually large amount of computational resources. The Pollard kangaroo algorithm is a generic discrete logarithm algorithm that is designed to compute discrete logarithms when the discrete logarithm lies in a small known interval. It applies to both elliptic curve and finite field discrete logarithms. We will use finite field discrete logarithms for our examples, but the algorithm is the same in the elliptic curve context. 6.3.1 Known most significant bits of the Diffie-Hellman secret exponent.

Problem Setup. Using the same notation for finite fields as in Section 6.1, let A be a a Diffie-Hellman public key, p be a prime modulus, and g a generator of a multiplicative group of order q modulo p. These values are all public, and thus we assume that they are known. Imagine that we have obtained a consecutive fraction of the most significant bits of the secret exponent a, and we wish to recover the unknown bits of a to reconstruct the secret. In other words, let a = m + r, where m = 2 m for some known integers m and , and 0 ≤ r < 2 is unknown. Let w be the width of the interval that r is contained in: here we have w = 2 .

For our concrete example, let p = 0xfef3 be a 16-bit prime, and let g = 3 be a multiplicative generator of the group of order q = (p -1)/2 = 0x7f79 modulo p. We know a Diffie-Hellman public key A = 0xa163 and we are given the most significant bits of the secret exponent a but the 8 least significant bits of a are unknown, corresponding to m = 0x1400, = 8, and r < 2 8 . Take some pseudorandom walks. We define a deterministic pseudorandom walk along values s 0 , s 1 , . . . , s i , . . . in our multiplicative group modulo p (and the corresponding exponents s 0 = g xo mod p, . . . , when known) by choosing a set of random step lengths for the exponents in [0, √ w]. For our example, we pseudorandomy generated the lengths (1, 3, 7, 10).

s i+1 →          s i g mod p
if s i ≡ 0 mod 4 s i g 3 mod p if s i ≡ 1 mod 4 s i g 7 mod p if s i ≡ 2 mod 4 s i g 10 mod p if s i ≡ 3 mod 4 This is a small sample pseudorandom walk generated to run our small example computation. Each step in the pseudorandom walk is determined by the representation of the previous value as an integer 0 ≤ s i < p.

We run two random walks. The first random walk, which is called "the tame kangaroo", starts in the middle of the interval of exponents to be searched, at s 0 = g m+ w 2 mod p. In our example, we have m = 0x1400 and w = 2 8 = 256, so the tame kangaroo begins at s 0 = g 0x1480 mod p = 0x9581. We take √ w steps along this deterministic pseudorandom path, and store the values s i together with the exponent x i that is computed at each step so that g xi ≡ s i mod p.

The second random walk is called the "wild kangaroo". It begins at the target s 0 = A = 0xa163 and follows the same rules as above. We do not know the secret exponent a, but at every step of the walk, we know that s i = Ag x i mod p = g a+x i mod p. We take at most √ w steps along this deterministic pseudorandom path.

If at some point the wild kangaroo's path intersects the tame kangaroo's path, then we are done and can compute the result. Compute the discrete log. We know that s i = s j for s i on the tame kangaroo's path and s j on the wild kangaroo's path. Thus we have s i = s j mod p g xi = g a+x j mod p

x i = a + x j mod q

x i -x j = a mod q

In our example, the kangaroos' paths intersected at g 0x1497 and g a+0x36 ; we can thus compute a = 0x1461 and verify that g 0x1461 ≡ 0xa163 mod p. More detailed explanation. Pollard gave the original version of this algorithm in [START_REF] Pollard | Monte Carlo methods for index computation mod p[END_REF]. Teske gives an alternative random walk in [START_REF] Teske | On random walks for pollard's rho method[END_REF] that should provide an advantage in theory, but in practice, it seems that no noticeable advantage is gained from it.

We expect this algorithm to reach a collision in O( √ w) steps; this algorithm thus takes O( √ w) time to compute a discrete log in an interval of width w. Thus in principle, the armchair cryptanalyst should be able to compute discrete logarithms within intervals of 64 to 80 bits, and those with more resources should be able to go slightly higher than this.

In order to scale to these larger bit sizes, several changes are necessary. First, one typically uses a random walk with many more subdivisions: 32 might be a typical value. Second, van Oorschot and Wiener [START_REF] Oorschot | Parallel collision search with cryptanalytic applications[END_REF] show how to parallelize the kangaroo algorithm using the method of distinguished points. The idea behind this method is that storing the entire tame kangaroo walk will require too much memory. Instead, one stores a subset of values that satisfy some distinguishing property, such as starting with a certain number of zeros. Then the algorithm launches many wild and tame kangaroo walks, storing distinguished points in a central database. The algorithm is finished when a wild and a tame kangaroo land on the same distinguished point.

Elliptic curves. This algorithm applies equally well to elliptic curve discrete logarithm. One can gain a √ 2 improvement in the complexity of the algorithm as a by-product of the efficiency of inversion on elliptic curves. Since the points P and -P share the same x-coordinate, one can then do a pseudorandom walk on equivalence classes for the relation P ∼ ±P . It is straightforward to extend the kangaroo method to solve for unknown most significant bits of the exponent. As before, we have a known A = g a mod p for unknown a that we wish to solve for. In the case of unknown most significant bits, we know an m such that a = m + 2 r for some unknown r satisfying 0 ≤ r < w. The offset is known. Then we can reduce to the previous problem by running the kangaroo algorithm on the value A = g 2 -A = g 2 -+m+2 r mod p. The case of recovering a Diffie-Hellman secret key in practice with multiple chunks of unknown bits is still an open problem. In theory, finding the secret key in this particular case can be done using a multi-dimensional variant of the discrete log problem. The latter generalizes the discrete logarithm problem in an interval to the case of multiple intervals, see [Rup10, Chapter 6] for further details. In [START_REF] Singh | Improvements to the Gaudry-Schost Algorithm for Multidimensional discrete logarithm problems and Applications[END_REF], Ruprai analyzes the multi-dimensional discrete log problem for small dimensions. This approach appears to run into boundary issues for multi-dimensional pseudorandom walks when the dimension is greater than five, suggesting that this approach may not extend to the case of recovering many unknown chunks of a Diffie-Hellman exponent.

Conclusion

This work surveyed key recovery methods with partial information for popular public key cryptographic algorithms. We focused in particular on the most widely-deployed asymmetric primitives: RSA, (EC)DSA and Diffie-Hellman. The motivation for these algorithms arises from a variety of side-channel attacks.

While the existence of key recovery algorithms for certain cases may determine whether a particular vulnerability is exploitable or not, we emphasize that these thresholds for an efficiently exploitable key recovery attack should not be used to guide countermeasures. Instead, implementations should strive to have fully constant-time operations for all cryptographic operations to protect against side-channel attacks.

Figure 1 :

 1 Figure 1: Illustration of low-exponent RSA message recovery attack setup. The attacker knows the public modulus N , a ciphertext c, and the padding a prepended to the unknown message m before encryption. The attacker wishes to recover m.

Figure 2 :

 2 Figure 2: Factorization of N = pq given contiguous known most significant bits of p.

Figure 3 :

 3 Figure 3: Factorization of N = pq given contiguous known least significant bits of p.

Figure 4 :

 4 Figure 4: Factorization of N = pq given contiguous known bits of p in the middle.

Figure 5 :

 5 Figure 5: Factorization of N = pq given multiple chunks of p.

Figure 6 :

 6 Figure 6: Efficient factorization of N = pq given many chunks of p and no information about p is an open problem.

dNFigure 7 :

 7 Figure 7: For small exponent e, the most significant bits of d do not allow full key recovery.

d d 0 NFigure 8 :

 08 Figure 8: Recovering RSA p given contiguous least significant bits of d.

Figure 9 :

 9 Figure 9: Factorization of N = pq given non-consecutive bits of both p and q.

Figure 12 :

 12 Figure 12: (EC)DSA key recovery from signatures where most significant bits of the nonces are known.

Figure 13 :

 13 Figure 13: (EC)DSA key recovery from signatures where least significant bits of the nonces are known.

Figure 14 :

 14 Figure 14: (EC)DSA key recovery from signatures where middle bits of the nonces are known.

  DSA key recovery from signatures where multiple chunks of the nonces are known.

Figure 15 :

 15 Figure 15: Recovering Diffie-Hellman shared secret with most significant bits of secret exponent.

6. 3 . 2 Figure 16 :

 3216 Figure 16: Recovering Diffie-Hellman shared secret with least significant bits

Figure 17 :

 17 Figure 17: Recovering Diffie-Hellman shared secret with multiple chunks of unknown bits.

Table 1 :

 1 Visual table of contents for key recovery methods for public-key cryptosystems.Cold boot and memory attacks. An entirely different class of side-channel attacks that can reveal partial information against keys include attacks that may leak the contents of memory. These include cold boot attacks [HSH + 08], DMA (Direct Memory Access), Heartbleed, and Spectre/Meltdown [LSG + 18, KHF + 19]

	Scheme	Secret information	Bits known	Technique	Section
	RSA	p ≥ 50% most significant		Coppersmith's method	§4.2.2
		bits
	RSA	p ≥ 50% least significant		Coppersmith's method	§4.2.3
		bits
	RSA	p middle bits		Multivariate Coppersmith	§4.2.4
	RSA	p multiple chunks of bits		Multivariate Coppersmith	§4.2.4
	RSA	> log log N chunks of p		Open problem
	RSA	d mod (p -1) MSBs		Coppersmith's method	§4.2.7
	RSA	d mod (p -1) LSBs		Coppersmith's method §4.2.7 and §4.2.3
	RSA	d mod (p -1) middle bits		Multivariate Coppersmith §4.2.7 and §4.2.4
	RSA	d mod (p -1) chunks of bits		Multivariate Coppersmith §4.2.7 and §4.2.4
	RSA	d most significant bits		Not possible	§4.2.8
	RSA	d ≥ 25% least significant		Coppersmith's method	§4.2.9
		bits
	RSA	≥ 50% random bits of p and		Branch and prune	§4.3.1
		q
				Branch and prune	§4.3.2
	(EC)DSA	MSBs of signature nonces		Hidden Number Problem	§5.2
	(EC)DSA	LSBs of signature nonces		Hidden Number Problem	§5.2
	(EC)DSA	Middle bits of signature		Hidden Number Problem	§5.2
		nonces
	(EC)DSA	Chunks of bits of signature		Extended HNP	§5.2.4
		nonces
	EC(DSA)	Many bits of nonce		Scales poorly
	Diffie-Hellman Most significant bits of		Hidden Number Problem	§6.2
		shared secret g ab
	Diffie-Hellman Secret exponent a		Pollard kangaroo method	§6.3
	Diffie-Hellman Chunks of bits of secret ex-		Open problem
		ponent

RSA

≥ 50% of bits of d mod (p -1) and d mod (q -1)

  and c 2 are unknown but small, less than some bound K. In our example, we have|b 1 |, |b 2 |, |c 1 |, |c 2 | ≤ 2 15 and = 64 -15 = 49.Substituting and rearranging into Equation 8, we haveb 1 + 2 c 1 + tb 2 + 2 tc 2 + a 1 + ta 2 + u ≡ 0 mod n

Acknowledgements

Pierrick Gaudry, Daniel Genkin, and Yuval Yarom made significant contributions to early versions of this work. We thank Akira Takahashi for helpful clarifications. This work was funded by the US National Science Foundation under grants no. 1513671 and 1651344.

Iteratively solve for each bit. The main idea of the algorithm is to iteratively solve for the bits of the unknowns p and q, starting at the least significant bits. These can then be checked against the known public value of N .

At the least significant bit, the value is known for p and is unknown for q. There are two options for the value of q, but only the bit value 1 satisfies the constraint that pq = N mod 2. The algorithm then proceeds to the next step, where the value of the second bit is known for q but not for p. Only the bit value 1 satisfies the constraint pq = N mod 2 2 , so the algorithm continues down this branch. Since this generates a tree, the tree can be traversed in depth-first or breadth-first order; depth-first will be more memory efficient. This is illustrated in Figure 10.

Figure 10: The branch and prune tree for our numeric example. The algorithm begins at the right-hand node representing the least significant bits, and iteratively branches and prunes guesses for successive bits moving towards the most significant bits.

The algorithm works because N = pq mod 2 i for all values of i. Additionally, we want some assurance that an incorrect guess for a value at a particular bit location should eventually lead to that branch being pruned. Heuristically, when the ith bits of both p and q are unknown, the tree will branch; when bit i is known for one but not the other, there will be a unique solution; and when the ith bits of both p and q are known, an incorrect solution has around a 50% probability of being pruned. Thus the algorithm is expected to be efficient as long as there are not long runs of simultaneous unknown bits. We assume the length of p and q is known. Once the algorithm has traversed this many bits, the final solution pq = N can be checked without modular constraints.

When random bits are known from p and q, the analysis of [START_REF] Heninger | Reconstructing RSA private keys from random key bits[END_REF] shows that the tree of generated solutions is expected to have polynomial size when 57% of the bits of p and q are revealed at random. This algorithm can still be efficient if the distribution of bits known is not random, as long as it allows efficient pruning of the tree. An example would be learning 3 out of every 5 bits of p and q, as in [START_REF] Yarom | CacheBleed: A timing attack on OpenSSL constant time RSA[END_REF].

Paterson, Polychroniadou, and Sibborn [START_REF] Kenneth | A coding-theoretic approach to recovering noisy RSA keys[END_REF] give an analysis of the required information for different scenarios, and observe that doing a depth-first search is more efficient memory-wise than a breadth-first search.

We give a sample branch and prune tree for recovering d p and d q from known bits, starting from the least significant bits on the right side of the tree. At each bit location, the value of p up to bit i is uniquely determined by the guess for d p up to bit i, and the value of q up to bit i is uniquely determined by the buess for d q up to bit i. The red X marks the branches that are pruned by verifying the relation pq = N mod 2 i .


Kuruva Balanna

Krishnaprasad Madica

Subrata Mukherjee

Arghya Ghosh

Thomas Poisson

Tatiana Besset

Garima Jindal
email: gjindal@iisc.ac.in

Akkattu T Biju
email: atbiju@iisc.ac.in

N-Heterocyclic Carbene-Catalyzed Formal [6+2] Annulation Reaction via Cross-Conjugated Aza-Trienolate Intermediates

Keywords: [6+2] annulations, conjugated aza-trienolates, heterocycles, N-heterocyclic carbenes, organocatalysis

come   L'archive ouverte pluridisciplinaire

Over the past three decades, catalysis using N-heterocyclic carbenes (NHCs) has emerged as a flexible synthetic tool for the unconventional access to target molecules. [1] This catalytically active species is responsible for the umpolung of aldehydes, thus leading to the generation of nucleophilic Breslow intermediates. [2] The two fundamental reactions proceeding via NHC-generated acyl anions are the benzoin condensation [START_REF] Menon | For selected reviews on benzoin reaction[END_REF] and Stetter reaction. [START_REF] Yetra | For selected reviews on Stetter reaction[END_REF] Moreover, addition of NHCs to -unsaturated aldehydes could result in the generation of homoenolate equivalents, [5] and -unsaturated acylazoliums under oxidative conditions.[6] A variety of carbocycles and heterocycles can easily be accessed by intercepting the homoenolates/a,bunsaturated acylazoliums. In 2004, the Bode [7] and Rovis[8] groups independently uncovered the generation of azolium enolates from NHCs by the addition to -epoxyaldehydes and -chloroaldehydes, respectively. The reaction afforded -hydroxyesters or saturated esters upon quenching the NHC-enolates with alcohols (Scheme 1, eq. 1, 2). Moreover, the azolium enolates can also be generated by the treatment of NHCs with ketenes,[9] enals,[10] carboxylic acids, [11] and aliphatic aldehydes [12] or esters [13] bearing a C-H protons. In 2011, Ye and co-workers extended the NHC-enolate concept to the generation of NHC bound dienolates. [14] The in situ formed dienolates were intercepted with activated ketones in a [4+2] fashion to form unsaturated d-lactones (Scheme 1, eq. 3). Subsequently, Chi and coworkers reported an elegant generation of azolium dienolates from enals under oxidative conditions employing NHC/Lewis acid cooperative catalysis (Scheme 1, eq. 4). [15] Interestingly, however, the application of this concept for the generation of NHCbound cross-conjugated aza-trienolates followed by their trapping with electrophiles, to the best of our knowledge is unknown. This will be interesting given that the related cross conjugated enamines and their aza version are known in secondary amine catalysis.[16] Herein, we demonstrate the NHCcatalyzed generation of cross-conjugated aza-trienolates from nitrogen-containing heterocyclic aldehydes followed by their interception with -trifluoroacetophenones in a [6+2] fashion resulting in the synthesis of pyrrolooxazolones derivatives (eq. 5). The present studies commenced with the treatment of pyrrole carboxaldehyde 1a with -trifluoroacetophenone 2a in the presence of the NHC catalyst generated from the triazolium salt 4 using Cs2CO3 base under oxidative conditions using the bisquinone 5 in CHCl3. Interestingly, under these conditions, the [6+2] annulation product formed by the trapping of the aza-fulvene type trienolate generated from 1a and 4 (under oxidative conditions) with the electron-poor carbonyl of 2a, the pyrrolooxazolone 3a, was formed in 83% yield (Table 1, entry 1). Impressed by this reactivity, various parameters such as NHC source, base, solvent have been examined. Compared with the carbene generated from 4, reaction performed using other carbene precursors 6-9 resulted in the reduced yield of 3a (entries 2-5). Moreover, Cs2CO3 was found to be the best base for this transformation, as the reactions carried out using other inorganic (K2CO3 and KOtBu) and organic (DBU and DABCO) bases returned inferior yields of 3a (entries 6-9). The reactions carried out in solvents such as THF, 1,2dichloroethane and toluene did not improve the yield of 3a indicating that CHCl3 is the optimal solvent for this [6+2] annulation (entries 10-12). Notably, reducing the loading of 4 to 10 mol% resulted in the formation of 3a in 55% yield with 12% recovery of 1a (entry 13). Control experiments performed without NHC precursor 4 or the oxidant 5 did not afford 3a indicating the role of carbene as well as the oxidant in this reaction (entries 14,15). [17] Having the optimized reaction conditions in hand, the scope and limitations of this [6+2] annulation have been examined (Scheme 2). A series of -trifluoroacetophenone derivatives bearing electrondonating,-neutral and -withdrawing groups at the 4-position of the aromatic ring are well tolerated under the present NHC-catalyzed conditions and the desired pyrrolooxazolones are formed in moderate to good yields (3a-3j). Notably, substrates having electron-withdrawing groups required 36 h for completion of the reaction. This sheds light on a stepwise pathway in which the initially generated crossconjugated aza-trienolates adds to the electrophilic carbonyl group of 1 forming an alkoxide, which undergoes an intramolecular acylation to afford the product. Moreover, -trifluoroacetophenones having substituent at the 3-position of the ring worked well under the present conditions furnishing the desired products in moderate to good yields (3k-3o). Disappointingly, reactions performed using 2-aryl substituted -trifluoroacetophenones provided only traces of the product. Interestingly, the disubstituted -trifluoroacetophenones afforded the desired products under the optimized conditions. In the case of the dichloro derivative 3q, the structure was confirmed using single-crystal Xray analysis.

[18] The reaction using pyrenyl trifluoromethyl ketone afforded the product 3s in 27% yield. In addition, a series of heteroaryl trifluoromethyl ketones readily underwent smooth [6+2] annulation affording the target products in good yields (3t-3x) thus demonstrating the versatility of the present reaction. The introduction of substituent on pyrrole carboxaldehyde 1a affected the outcome of the reaction. For instance, the aldehyde having bromine at the 4-position returned only 39% yield of the product 3y, and iodine at the 4-position afforded 3z in 18% yield.

Table 1. Optimization of the reaction conditions. [a] Entry Variation of the standard conditions Yield [%] [b] of 2a This is an indication of the role p-electron cloud of aldehyde on this [6+2] annulation. Furthermore, unsubstituted indole 2-carboxaldehyde afforded the desired product 3aa in 72% yield. Finally, substitution at the 3-position of indole 2-carboxaldehyde did not affect the outcome of the reaction and the target products are formed in moderate to good yields (3ab-3ac). To gain insight into the mechanism of the reaction, we performed a few experiments. When the reaction of 1a and 2a was performed in the absence of NHC pre-catalyst 4, the desired product 3a was not formed indicating the role of NHC in this [6+2] annulation (Scheme 3, eq 6). Moreover, the acetal 10a (likely formed by the N-H addition of 1a to 2a followed by intramolecular cyclization) was not observed under these conditions showing that the direct N-H addition of initially formed acylazolium and cyclization in a [3+2] pathway is not operating in this case. [19] In addition, when the reaction was performed using N-Boc protected aldehyde 11 a, the product 3a was not formed signifying the role of N-H moiety in forming the NHCbound cross-conjugated aza-trienolates (eq 7).

Scheme 3. Control experiment and reaction using N-Boc aldehyde. that the keto form C is _19 kcalmol_1 lower in energy than the enol form. Further, intermediate E which arises as a result of deprotonation with the Cs2CO3 base, was found to be _47 kcalmol_1 lower in energy than C. We have also performed the preliminary studies on the enantioselective version of this [6+2] annulation. Thus, treatment of the indole aldehyde 1d with 2a using the carbene generated from the chiral triazolium salt 12 using Cs2CO3 as the base resulted in the formation of the desired product chiral-3 aa in 72% yield and 89:11 er (Scheme 5).

Scheme 5. Preliminary study on the enantioselective version.

In conclusion, we have demonstrated the NHC-catalyzed formal [6+2] annulation of nitrogen-containing heterocyclic aldehydes with -trifluoroacetophenones allowing the synthesis of pyrrolooxazolones in moderate to good yields. [START_REF] Liu | While this manuscript was under review, Jin and co-workers demonstrated a closely related NHCcatalyzed reaction of nitrogen-containing heterocyclic aldehydes and activated ketones for the enantioselective synthesis of multi-functionalized cyclic N,O-acetals. For details[END_REF] The key to the success of the present reaction is the generation of crossconjugated aza-trienolates (aza-fulvene type) from NHC and heteroaldehydes (supported by DFT studies). Mild reaction conditions, broad scope, new mode of carbene reactivity are the notable features of the present annulation. Further studies on NHC-bound cross-conjugated aza-trienolates are ongoing in our laboratory.

Scheme 1 .

 1 Scheme 1. Generation and reaction of various NHC-enolates.

  Scheme 2. Scope of the NHC-catalyzed formal [6+2] annulation reaction. General conditions: 1 (0.5 mmol), 3 (0.75 mmol), 4 (20 mol%), Cs2CO3 (50 mol%), 5 (1.0 equiv), CHCl3 (4.0 mL), 30°C, and 12 h. Yields of the isolated products are given. [a] Reaction run for 36 h.[b] Structure confirmed by X-ray analysis.[c] Run for24 h. [d] The product contained _3% of oxidant 5.

Scheme 4 .Figure 1 .

 41 Scheme 4. Tentative mechanism of the reaction. Mechanistically, the free carbene generated from 4 adds to the aldehyde 1a forming the Breslow intermediate B (via the tetrahedral intermediate A),[2a, 20] which is subsequently oxidized by the bisquinone 5 to the NHC-acylazolium intermediate C (Scheme 4). The intermediate C could tautomerize to the cross-conjugated aza-trienol D. The intermediate C or its tautomer D was detected in high resolution mass spectrum (ESI) of a stoichiometric reaction carried out using 1a, 4, Cs2CO3 under oxidative conditions.[17, 21] Under basic conditions, deprotonation of intermediate C/D could generate the key cross-conjugated aza-trienolates (aza-fulvene type) E. Efforts to isolate the intermediate C, D, or E failed in our hands. The nucleophilic aza-trienolate E could add to the carbonyl group of 2a resulting in the generation of the acyl azolium F, which could undergo an intramolecular acylation to form the desired product 3a with the regeneration of the NHC catalyst. To get further insight into the proposed mechanism, we have carried out a preliminary DFT study with the B3LYP functional.[22] Given that the formation of a Breslow intermediate and its subsequent oxidation is well documented,[1c, d] we focused on the newly proposed intermediate E and its reaction with the ketone 2a. Two different configurations, i.e., E and Z, were optimized for intermediate E. Further calculations were performed with the E isomer as it was about 5 kcalmol _1 lower in energy than the Z isomer. The conversion of E to F proceeds via transition state TS(E-F) and the activation free-energy was found to be about 15 kcalmol _1 making this a facile step. The optimized geometries of transition state and the intermediates E-2a (pre-reacting complex between E and 2a), and F are shown in Figure 1. It should be noted that intermediate F is preorganized for the final C-O bond formation, where the C-O distance is 2.17 Å. The final step leading to the product 3a and generation of the free carbene takes place via a concerted late transition state TS(F-3a) where the C-O bond distance is 1.50 Å, and the activation barrier is 8.6 kcalmol _1 . We also looked at the thermodynamic stability of the intermediate C, Scheme 3. Control experiment and reaction using N-Boc aldehyde. its enol form D and the deprotonated form E.[23] It was found

Acknowledgements

Generous financial support by IFCPAR-CEFIPRA (no. 5505-1) is gratefully acknowledged. G. J. thanks Supercomputer Education and Research Centre (SERC), IISc Bangalore for computing time. K. B. and K. M. thank UGC for the PhD scholarship and DS Kothari post-doctoral fellowship, respectively, and A.G. thanks CSIR for the research fellowship. We thank Dr. M. Venkateswarulu and Mr Ravi Teja for collecting the X-ray data of 3qand Mr. Arun Patel from the help with 1 H NMR experiments.