"Pseudo-Random" Number Generation Within Cryptographic Algorithms: The DDS Case Mihir Bellare 1, Shaft Goldwasser 2 and Daniele Micciancio 2 1 Dept. of Computer Science & Engineering, University of California at San Diego, 9500 Gilman Drive, La Jolla, California 92093, USA. E-Mail: mihir(cid:14)9 .ucsd. edu. URL: http://~-cse, ucsd. edu/users/mihir. 2 MtT Laboratory for Computer Science, 545 Technology Square, Cambridge, MA 02139, USA. E-Marl: {shafi,micr162 lcs.mit, edu. Abstract. The DSS signature algorithm requires the signer to generate a new random number with every signature. We show that if random numbers for DSS are generated using a linear congruential pseudorandom number generator (LCG) then the secret key can be quickly recovered after seeing a few signatures. This illustrates the high vulnerability of the DSS to weaknesses in the underlying random number generation process. It also confirms, that a sequence produced by LCG is not only predictable as has been known before, but should be used with extreme caution even within cryptographic applications that would appear to protect this sequence. The attack we present applies to truncated linear congruential generators as well, and can be extended to any pseudo random generator that can be described via modular linear equations. 1 Introduction Randomness is a key ingredient for cryptography. Random bits are necessary not only for generating cryptographic keys, but are also often an integral part of steps of cryptographic algorithms. Examples are the DSS signature algorithm [16] which requires the choice of a new random number every time a new signa- ture is generated, and CBC encryption, which requires the generation of a new random IV each time a new message is encrypted. (In fact, any secure, stateless encryption scheme must be probabilistic, requiring new randomness for each en- cryption [8].) In some cases, the random numbers chosen may have to be kept secret (as for DSS, where the leakage of one such random number compromises the secret key), whereas for other cases they can be made public (as in CBC encryption, where the IV may be sent in the clear). In practice, the random bits will be generated by a pseudo random number generation process. For example, the DSS description [16] explicitly allows either using random or pseudo-random numbers. When this is done, the security of the scheme of course depends in a crucial way on the quality of the random bits produced by the generator. Thus, an evaluation of the overall security of a cryptographic algorithm should consider and take into account the choice of the pseudorandom generator.
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 001
`
`

`

`278 It has been well accepted that a good notion of pseudorandomness for cryp- tographic purposes is unpredictability [18,20,3,7]: given an initial sequence pro- duced by a pseudo-random number generator on an unknown seed, it is hard to predict with better probability than guessing at random, the next bit in the sequence output by the generator. Such generators can be constructed based on number-theoretic assumptions, but are computationally costly. Alternatively, one could build a generator out of DES which would be unpredictable assuming DES behaves like a pseudorandom function, but in some contexts this may be deemed costly too, or we might not want to make such a strong assumption. Since using a weaker generator does not necessarily mean the resulting crypto- graphic algorithm is insecure, in practice one usually uses some weak but fast generator. The intent of our paper is to illustrate the extreme care with which one should choose a pseudo random number generator to use within a particular cryptographic algorithm. Specifically, we consider a concrete algorithm, the Dig- ital Signature Standard [16], and a concrete pseudo random number generator, the linear congruential generator (LCG) or truncated linear congruential pseudo random generator. We then show that if a LCG or truncated LCG is used to pro- duce the pseudo random choices called for in DSS, then DSS becomes completely breakable. We remark that the Standard [16] recommends the use of a pseudo-random generator based on SHA-1 or DES. The attack we describe does not say anything about the use of DSS with such generators, but it does illustrates the high vulnerability of the DSS to the underlying random number generation process. We remark that LCGs are known to be predictable if part of the pseudo- random sequence is made public (see section 1.2 for details). However in DSS none of the pseudo-random numbers used is ever revealed, and thus predictability does not imply insecurity here. Let us now look at all this more closely. 1.1 Pseudorandom numbers in DSS Recall that the DSS has public parameters p, q, g where p, q are primes, of 512 bits and 160 bits respectively, and g is a generator of an order q subgroup of Z~. The signer has a public key y -- gX where x E Zq. To sign a message m E Zq, the signer picks at random a number k E {1,..., q - 1} and computes a signature (r, s), where r = (gk mod p) mod q and s -- (xr + m)k -1 mod q. Here the "nonce" k is chosen at random, anew for each message. In practice, a sequence of nonces will be produced by a generator G which, given some initial seed k0, produces a sequence of values kl, k2,...; ki will be the nonce for the i-th signature. The adversary (cryptanalyst) sees the public key y, and triples (mi,ri,si) where (ri, si) is a signature of mi. Notice that the secrecy of the nonces is crucial. If ever a single nonce ki is revealed to the adversary, then the latter can recover the secret key x, because x = (siki -mi)r~ 1 mod q. However, the nonces appear to be very well protected, making it hard to exploit any such weakness. The
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 002
`
`

`

`279 cryptanalyst only sees ri = (gk, mod p) mod q from which he cannot recover ki short of computing discrete logarithms, and in fact not even then, due to the second mod operation. So even if G is a predictable generator, meaning, say, that given kl, k2 we can find k3, there is no a priori reason to think DSS is vulnerable with this generator, because how can the cryptanalyst ever get to know kl, k2 anyway? This might encourage a user to think that even a weak (predictable) gener- ator is OK for DSS. This view would be wrong. We indicate that in fact DSS is vulnerable, because without a sufficiently good pseudorandom number gen- eration process, the "masking" of the nonces provided by the algorithm is not sufficient to protect the nonces, even though recovering them seems a priori to require solving the discrete logarithm problem. In fact we prove a quite general lemma showing why this masking is essentially ineffective for pretty much any pseudorandom generator, and show specifically how to recover the keys when the generator is an LCG or truncated LCG. Thus one should not succumb to the temptation of using a weak generator for DSS. 1.2 Linear congruential generators Recall that linear congruential generators are pseudo-random number genera- tors based on a linear recurrence Xn+l = aXn + b mod M where a, b and M are parameters initially chosen at random and then fixed, and the seed is the initial value X0. The advantage of linear congruential generators is that they are fast, and it has been shown [11] that they have good statistical properties for appropriate choices of the parameters a, b, M. On the other hand, their unpredictability properties are known to be quite weak. Clearly they are predictable in their simplest form: if the parameters a, b and M are known, given X0 all the other Xn can be easily computed. Plumstead (Boyar) [17] shows that even if the parameters a, b, M are unknown the sequence of numbers produced by a linear congruential generator is still predictable given some of the Xi. Truncated LCG were suggested by Knuth [12] as a possible way to make a linear congruential generator secure. However these generators have also been shown to be predictable [5,9,19] as have more general congruential generators [4,13]. However, as indicated above, this predictability does not directly mean a cryptographic algorithm using the generator is breakable, since it is possible none of the bits of the random numbers used by the algorithm are ever made public. DSS is (was) a case in point. 1.3 Cryptanalysis of DSS with LCG DSS WITH LCG. We consider what happens when the nonces in DSS are gen- erated using an LCG with known parameters a, b, M and hidden seed k0. The predictability of the generator does not a priori appear to be a problem, due to the masking provided by the algorithm as indicated above. However, given just three valid signatures, we show how to recover the secret key. UNIQUENESS LEMMA. We begin with a general lemma which indicates why the above intuition that the DSS protects the nonces may be false. The lemma (called
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 003
`
`

`

`280 the Uniqueness Lemma) says that as long as the nonces are pseudorandomly generated then, even if we ignore the relations ri = (g~' mod p) mod q, the DSS signature equations siki - fix = mi uniquely determine the secret key with high probability. This means the cryptanalyst can effectively ignore the masking that is supposed to protect the nonces. This is true for any pseudorandom generation process, even a cryptographically strong one, using an unpredictable generator. This lemma tells us we can concentrate on the signature equations. SOLVING THE EQUATIONS. We begin the cryptanalysis of DSS with LCG by combining the DSS "signature equations" with the LCG generation equations to get a system of equations. (In the process we ignore the ri = (gk~ mod p) mod q relations, invoking the Uniqueness Lemma to say that solving the signature equations suffices to find the secret key.) However, this system is not trivial to solve because it is a system of simultaneous modular equations in different moduli. Techniques like Gaussian elimination fail. Instead we turn to lattice reduction. We show how to use Babai's closest vector approximation algorithm to solve such a system. The main difficulty here is dealing with the fact that this algorithm only returns (not very good) approximations to the closest vector. We then extend this to the case of the truncated LCG. 1.4 Other results, discussion, and implications We extend our techniques to provide a general algorithm for solving a system of simultaneous linear modular equations in different moduli. (Another way of doing this, when the number of equations is constant, is to reduce the problem to integer programming in constant dimension and apply the algorithms of [14,10]. Our alternative solution seems simpler and more direct.) In many cryptographic algorithms, the random numbers used are processed in a way that the public information gives little information about the original numbers. This is the case for the nonces in DSS. In such a setting, it may be reasonable to think that weak random number generators can suffice: even predictable generators could be fine because not enough information about the random numbers is revealed to make predictability even come into play. We are indicating this may not always be true: the quality of random bits matters even when the only thing an adversary sees is the result of a one-way functions on these bits. A common pseudo-random number generator that comes standard with var- ious operating systems is a linear congruential generator with modulus 232. It is plausible that there are DSA implementations available where the k values are formed by concatenating 5 consecutive outputs from such a generator. Our attack easily extends to this case. 2 Preliminaries 2.1 The Digital Signature Standard The Digital Signature Standard (DSS, see [16]) is an E1Gamal-like [6] digital signature algorithm based on the hardness of computing the discrete logarithm in some finite fields.
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 004
`
`

`

`281 THE SCHEME. The scheme uses the following parameters: a prime number p, a prime number q which divides p - 1 and an element g E Z~ of order q. (Chosen as g = h (p-1)/q where h is a generator of the cyclic group Z;). These parameters may be common to all users of the signature scheme and we will consider them as fixed in the rest of the paper. The standard asks that 2159 < q < 216~ and p > 2511. We let G -- { gO : a E Zq } denote the subgroup generated by g. Note it has prime order, and that the exponents are from a field, namely Zq. The secret key of a user is a random integer x in the range {0,..., q - 1}, and the corresponding public key is y = gX mod p. DSA (the Digital Signature Algorithm that underlies the standard) can be used to sign any message m E Zq, as follows. The signer generates a random number k E {1,..., q - 1}, which we call the nonce. It then computes the values A -- gk mod p and r = A mod q. It sets s = (xr + m) (cid:12)9 k -1 mod q, where k -1 is the multiplicative inverse of k in the group Z$. The signature of message m is the pair (r, s) and will be denoted by DSA(x, k, m). Note that a new, random nonce is chosen for each signature. A purported signature (r, s) of message m can be verified, given the user's public key y, by computing the values Ul = m.s -1 mod q, u2 = r.s -1 mod q and checking that (gUl y~2 mod p) mod q = r. Notice that the values (r, s) output by DSA(x, k, m) satisfy the relation sk - rx = m (mod q). We will make use of this relation in our attack on the DSS. HASHING. The 160-bit "message" m above is not the actual text one wants to sign, but rather the hash of it, under a strong, collision resistant cryptographic hash function H. Specifically, if m is the actual text to be signed, the standard sets H = SHA-1, the Secure Hash Algorithm of [15]. The hashing serves two purposes. The first is to enable one to sign messages of length longer than 160 bits. Second, it "randomizes" the message to prevent any possible attacks based on the algebraic structure of the scheme. Accordingly, following [2], we treat the hash function as a random oracle. We stress that we are considering attacks. In this context, treating H as a random oracle only strengthens our results. If the scheme is breakable when H is a random oracle, we should definitely consider it insecure, because a random oracle is the "best" possible hash function! Our attack on the DSS algorithm does not involve the hash function H other than to assume it random. Therefore we will assume that the messages are already integers in the range {0,..., q - 1} and that they are randomly distributed. SECRECY OF THE NONCE. Recall that for every signature, the signer generates a new, random nonce k. An important feature (drawback!) of the DSS is that the security relies on the secrecy of the nonces. If any nonce k ever becomes revealed, at any time, even long after the signature (r, s) was generated, then given the nonce and the signature one can immediately recover the secret key x, via x = (sk - m)r -1 rood q. This is a key point in our attack.
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 005
`
`

`

`282 2.2 Pseudo-Random Number Generators Each time DSA is used to digitally sign a message m, a nonce k is needed. Ideally k should be a truly random number. In practice the nonces k are pseudo-random numbers produced by a pseudo-random number generator. A pseudo-random number generator is a program G that on input a seed a, generates a seemingly random sequence of numbers G(a) = kl, ks,.... The DSS algorithm can be used in conjunction with a pseudo-random number generator as follows. On input a secret key x, a seed a to the generator, and a sequence of messages ml,..., ran, run G(a) to generate a sequence of pseudo- random numbers kl,..., kn and run DSA on input x, mi, ki for all i = 1,..., n. The pseudo-random number generators we consider in this paper are all variants of the linear congruential generator. LINEAR CONGRUENTIAL GENERATORS. A linear congruential generator (LCG) is parameterized by a modulus M and two numbers a, b E ZM. The seed to G is just a number a -- ko E ZM. On input k0, the generator produces a sequence of numbers, G(ko) = kt,k2,.., defined by the linear recurrence ki+t = aki + b mod M. The values ki can be directly used by DSA as random nonces to sign the messages. (In which case they are treated modulo q. We assume that with high probability a ki value will not be 0.) TRUNCATED LINEAR CONGRUENTIAL GENERATORS. For security reasons it has been suggested that only some of the bits of the number produced by a linear congruential generator be used by applications, in our case the DSA algorithm. A truncated linear congruential generator does exactly this. Let's look at this more closely. A truncated linear congruential generator is parameterized by a modulus M, two numbers a,b E ZM and two indices l,h such that 0 < l < h < lgM. The seed is a number ao E ZM and the generator produces numbers in the range {0, .... 2 h-l - 1}. The generator computes a sequence ai according to the linear recurrence ai+l = aai + b mod M. Then, each number ai is truncated by taking only bits l,..., h - 1 of the number, to get the number ki = ((ai - (ai rood 2t)) mod 2h)/2 z which is output by the generator. 3 The attack We look at the security of the DSS when the nonces are generated using a LCG with parameters a, b, M. Later we will extend this to truncated LCGs. 3.1 Overview Our attack on DSS exploits the relationship sk - rx -- m mod q holding for any digital signature (r, s) = DSA(x, k, m) produced by the DSA algorithm. The idea is this. Assume that we receive two messages mt and m2 together with their digital signatures (rl, st) = DSA(x, kl, ml) and (r2, s2) -- DSA(x, k2, m2). We know that stkl -rlx =mx mod q and s2k2 -r2x = m2 mod q. The cryptanalyst knows mz, rl, sl, m2, r2, s2. He also knows the public parameters p, q, g of the DSS and the public key y = g= of the signer. What is hidden from him is the
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 006
`
`

`

`283 secret key x of the signer, and also the nonces kl, k2 which the signer used to produce the signatures. At this point, the cryptanalyst is not expected to have any way of determin- ing any of the unknowns short of computing discrete logarithms. However, now suppose we know that a linear congruential generator with parameters a, b, M has been used to produce the nonces. We assume the cryptanalyst knows the parameters a, b, M defining the LCG. (They were chosen at random, but then made public.) What is unknown to the cryptanalyst is the seed ko used by the signer to start the LCG. Now, we can combine the two signature equations above with the linear congruential equation k2 -- akl + b mod M. These three equations together yield a system of three modular equations in three unknowns: Slkl - fix -- ml (mod q) s2k2 - r2x : m2 (mod q) -akl + k2 = b (mod M) (1) Our approach is to try to solve these equations. Note it is a system of simulta- neous modular linear equations in different moduli. This approach at once raises two questions. One, of course, is how to solve such a system. But the other question may need to be addressed first. Namely, even if we solve it, how do we know the solutions we get are the desired ones? That is, there may be many different solutions, and finding a solution to the system (1) does not necessarily imply that we found the right one. (Meaning the one corresponding to the secret key x.) This worry arises from a feature of this approach that we should highlight. We are not using all available information. We propose to ignore the fact that ri = (gki mod p) mod q. We will simply try to solve the equations, and see what we get. When we are ignoring what may seem a fundamental relation of the DSS signatures, it is not clear why solving the equations will bring us the right solutions: our system of equations might be under-determined. We will answer this question in Section 3.2, showing that even disregarding the non-linear relationships rl = (gkl mod p) mod q and r2 = (gk2 mod p) mod q, the solution to our equations is uniquely determined in most of the cases. Then we can turn to the problem of solving a system of modular linear equations. If the moduli are the same, M -- q, the equations can be easily solved by linear algebra. So, it is insecure to use q as the modulus in the LCG. However, if the modulus M is chosen (randomly and) independently from q, as we assume, one might still imagine that the equation k2 = akl + b mod M does not help in finding the secret key because it is in a different modulus and cannot be easily combined with the other equations. In other words, we are faced with solving a system of simultaneous modular linear equations in different moduli. We address this via lattice reduction techniques in Section 3.3. In later sections we extend the attack to truncated LCGs and also present a general method for solving systems of simultaneous linear modular equations in different modulii.
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 007
`
`

`

`284 3.2 The Uniqueness Lemma In this section we prove that when DSS is used with a pseudo-random number generator, a few signatures are usually enough for the linear equations siki - rix = rnl to uniquely determine the secret key x, disregarding that it must be also that ri -- gk~ mod p mod q. This answers the first question that we posed in section 3.1 and opens up the possibility of breaking DSS by solving a system of linear equations. We stress this is true for any generator, not just LCG. The generator might be very strong (eg. cryptographically strong) or very weak, it does not matter. The number of signatures needed depends only on the length of the seed of the generator, growing linearly with this. The statement we make is a probabilistic one: with high probability the system of equations obtained by using DSS with a linear congruential generator has a unique solution. The probability is taken over the choices of the messages to be signed only. (As discussed in Section 2, these are hashes of the real messages under some "strong" one-way hash function, and so considering them random is natural, especially from an attack point of view.) In other words, no matter how we had chosen x and a, once they are fixed, if the messages mi are randomly chosen the secret key x is uniquely determined with high probability. Before stating the lemma we need some definitions. Fix a secret key x E Zq of the DSS. Let G be some generator (not necessarily LCG) and let M be the total number of seeds that G can take. So we will think of a seed of G as being in ZM. Now fix a seed a E ZM of the generator ~. Let G(a) = kt,k2,... ,kn. Fix a message sequence ml,..., mn E Zq and let (ri, si) = DSA(x, ki, mi) be the signature of mi using nonce ki, for i -- 1,..., n. Let x' E Zq and a ~ E ZM, and let ~(a') = kl,..., k~. We say (x', a') is a false solution with respect to x,a, ml,...,mn ifx ~ x' but sik~ -fix ~ = mi modq for all i = 1,...,n. That is, the secret key is not the right one, but the equations work out anyway. Lemma 1. Fix a secret key x E Z a of the DSS, and a seed a E ZM of the generator ~. Now, choose n messages ml,...,mn uniformly at random from Z a. The probability, over the choices of the messages only, that there exists some (x',a ~) which is a false solution with respect to x,a, mt,...,mn is less than Mq t-n. Moreover, the expected number of such false solutions is also less than Mq 1-n. Proof. Let kl,..., kn = ~(a) be the output of the generator on seed a. Since a is fixed, so are kl,..., kn. We will assume these are all in Z~. Fix x' E Zq and a' E ZM such that x r x', and let k~,..., kin = 6(a'). For this fixed x ~, a', and for a fixed i, we claim that the probability, over the choice of mi, that sik~ - rix' = mi, is at most 1/q. (Here (ri, si) = DSA(x, ki, mi), so that ri = gk~ is a fixed quantity, while si = (mi + xri)k~ 1 is a random variable depending on the choice of mi.) The reason this claim is not entirely obvious is that indeed si depends on mi. We first note that sik~ - fix ~ = mi implies ki ~ k~. To see this, note mi = siki - rix = mik~ - rlx ~. If ki = k~ we would get siki - rix = siki - rix' which yields x = x' because ri ~ 0. But we assumed x ~ x ~.
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 008
`
`

`

`285 Now, note that if sik~-rix' = mi then it must be that (mi+xri)k:~ x k~-rix' = mi, or mi(1-k~lk~) = rixk~-lk~-rix'. But ki ~ k~ implies 1-k~-lk~ # 0 whence ri(xk~-l k~ - x') ri(xk~ - x'ki) -1 , ki - k~ mi 1 - k i k~ But the right hand side does not depend on the choice of mi, because all the quantities there are fixed. (We use here that ri does not depend on mi, a property of DSS.) This means there is only one value mi for which the above equation can be true. So if we pick m~ at random from Zq, there is only a 1/q chance that the above equation can be true. Now since the messages are chosen independently at random, the probability that sik~ - fix ~ = mi for all i = 1,... ,n, is q-n. Recall this is for fixed x ~ E Zq (x' r x) and a ~ E ZM. The probability that there exists x~,a ~ which is a false solution is thus, by the union bound, at most (q - 1)M. q-" < Mq 1-n. For the claim about the expected number of false solutions, use linearity of expectation instead of the union bound. | Recall these results are true for any pseudo-random number generator G. That is even if G is cryptographically strong, with high probability there will be only one secret key x and seed a such that the equations rix ~ + sik~ = mi are si- multaneously satisfied. Clearly if G is cryptographically strong it will be hard to recover these x and a from the signatures (ri, si) and messages mi only. But for the LCG it can be done. 3.3 Solving the equations Lemma 1 shows that even if M ~ q, if M and q have the same size (i.e., 1/2 < M/q < 2), the system of equations 1 will usually have only a few solutions. Therefore, if we can solve the system of equations we can also retrieve the secret key. SOLVING VIA INTEGER PROGRAMMING. We remark that systems of linear equa- tions in different moduli can be rewritten as integer programming problems by introducing a new variable for each equation. Since we have a constant num- ber of equations, they can thus be solved using polynomial time algorithms for integer programming in constant dimensions as given in [14,10]. However these algorithms are relatively complex and slow. Instead, we we want to solve more directly and simply. We now present a simple lattice based algorithm that solves our system using a nearest lattice vector approximation algorithm as a subrou- tine. THE NEAREST LATTICE VECTOR PROBLEM. Let B = {bx,..., b,} be a finite set of vectors in R n. The lattice generated by B is the set of all integer combinations of the vectors in B and is denoted by L(B). Given B and a vector x E R n not in L(B), the nearest lattice vector problem asks for a lattice vectors w E L(B) such that liT - xll = minveL(B) IIv -- xll. In [1], Babai gave a simple polynomial time algorithm to find an approximate solution to the nearest lattice vector problem: given the basis B and the target vector x, Babai's algorithm returns a
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 009
`
`

`

`286 lattice vector w such that ][w - x H < c. minveL(B) [Iv -- XH, where c = 2 n/2 is an approximation factor depending only on the dimension of the lattice. THE LATTICE(cid:12)9 In order to solve the system of equations 1, we set up the following lattice(cid:12)9 Let x' = q/2, k' I = k~ = M/2 and define also % = min{x',q- x'}, 74, = min{k~, M- k~}, 742 = min{k~, M - k~}. Consider the lattice L generated by the columns of the matrix B = "-rl Sl 0 q0 0 -r2 0 s2 0 q 0 0 -a 1 00M 7~ 1 0 0 000 0 7~-~ 0 000 0 0 "y/~ 0 0 0 Notice that multiplying the first three columns of the matrix by x, kl, k2 and subtracting the appropriate multiples of the remaining columns to perform modular reduction, we obtain the lattice vector X = (ml, m2, m3, x/'yz, kl/'Ykl, k2/")'k2)T from which we can easily recover the secret key x. Running Babai's nearest lattice vector algorithm on lattice L(B) and target m xt t t T vector Y = ( 1,m2,m3, /%,kl/~kl,k2/Tk2) we obtain a lattice vector W such that IIY - W H < 81[Y - Xll. Now, if Ix - x' I < %/14, Ikl - k~[ < 7ki/14 and [k2 - k~[ < 742/14, then I[Y - W][ < 1 and since the first three entries of W are integers they must coincide with the corresponding entries in Y and we m x"" , T X II, " " satisfying have W (ml,m2, 3, /7=,kll'/'Y41, for kl, k2 = k2/7k2) some the equations 1. Moreover the following two inequalities are satisfied z" = (x" - z') + z' >_ -7= + % = 0 x" = (x"-x') +x' < % + (q-'7=) = q. Inequalities 0 < k[', k~' < M can be proved analogously. If the vector W does not have the desired form, that means that our initial guess (x I, I I kl, k2) was not a good enough. If this is the case we simply repeat all the above steps with a different value for x', k~, k~. One can check that if we let x' range in the set {q/2+ (1 - (1 - 1]8)J)q/2 1J = 0,... ,8Igq/2}, and kl,k2 in the set {M/2 + (1 - (1 - 1/8)J)M/2 I J = 0,... ,81gM/2}, there will be some x',k~,k~ such that Ix - x'[ < 7x/14, [kl - kl[ < 741/14 and [k2 - k~l < 742/14. ! t The number of possible z', kl, k 2 to start with, to be sure of finding a solution to the system is polynomial in lgq and lg M, so we can try all of them in polynomial time. I I Once we have found a solution x', kl,k 2 to the equations 1, we can check (cid:12)9 t that we actually found the secret key x by computing gZ mod p and comparing it with the public key y. If g~' rood p # y, then x # x' and we did not found the solution that we wanted. In this case we can use the method just described to find a solution to the equations i in the range 0 < x < x' or z' < x < q. Since by Lemma I the total number of z such that system 1 has solution is less then
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 010
`
`

`

`287 2 on the average, with high probability we will find the right x after one or two steps. This completes the description of the attack to DSS when used with linear congruential generators. 4 Solving Simultaneous Modular Equations The technique described in section 3.3 can be generalized to work on arbitrary systems of linear equations in different moduli. These kind of systems arises in the cryptanalysis of DSS when used with more sophisticated pseudo-random number generators, such as truncated linear congruential generators. In this section we state the problem of solving a system of linear equations in different moduli in its full generality and give an algorithm to find a solution to such a systems. When the number of equations and variables is fixed, the running time of the algorithm is polynomial in the logarithms of all numbers involved in the description of the equations. We consider the problem of finding "small" solutions to a system of modular linear equations in different moduli. More precisely, let U1,..., Un be positive integers and let Vv be the set of vectors {x E Z n m vi.lxil < ui}. Let also A = {aij} be an m (cid:141) n integer matrix, and b and M be two vectors in Z m. We want to find an integer vector x E Vv such that A (cid:12)9 x = b (rood M), i.e., Ixi] < Ui for all i = 1,...,n and the following modular equations are simultaneously satisfied al,lXl -t- ... q- al,nXn : bl (mod M1) am,iX1 + ... + am,nXn =bm (mod Mm). We first assume that the above system has a solution x and that a good approximation to this solution is known and devise a method to find the exact solution. Definition 2. Let x and y be two vectors in Vv. We say that vector y c- approximates x iff for all i = 1,..., n we have Ixi -Yil < (Ui -lyil)/(cv~. Lemma 3. Let c be a constant greater than 2 (m+n)]2 . There exists a polynomial time algorithm that on input U1,..., Un, A, b, M as above and a c-approximation y to a solution x E Vv to A (cid:12)9 x = b (mod M), finds a (possibly different) solution w E Vv to A . x = b (modM). Proo]. Let F = {~/i,j} be the n (cid:141) n diagonal matrix defined by "Yi,i = 1/(Ui -ly~l) and let M be the m (cid:141) m diagonal matrix whose diagonal entries are M1, (cid:12)9 (cid:12)9 (cid:12)9 Mm. Consider the lattice generated by the columns of the matrix L = [A M] and define the vectors X= I'x Fy
`
`MOBILEIRON, INC. - EXHIBIT 1006
`Page 011
`
`

`

`288 Notice that X is a lattice vector and I fix YII ~--~'~(xi- 2 2 1 1 - = y~) 7~,~ < - (cid:12)9 i-----i i----1 c2n e Running Babai's nearest lattice vector algorithm [1] on lattice L and target vector Y we obtain a lattice vector W such that HW - Y[] < c[]X - Y]I <- 1. Since the first m elements of W and Y are integers, they must be the same. So, [ ? ]forsomeintegervectorwsatisfyingA.w=b the