Int. J. Communications, Network and System Sciences, 2012, 5, 834838 http://dx.doi.org/10.4236/ijcns.2012.512088 Published Online December 2012 (http://www.SciRP.org/journal/ijcns) Cryptanalysis of the DoubleModuli Cryptosystem Sonia Mihaela Bogos, Serge Vaudenay École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland Email: soniamihaela.bogos@epfl.ch, serge.vaudenay@epfl.ch Received October 2, 2012; revised November 2, 2012; accepted November 13, 2012 ABSTRACT In this article we present a lattice attack done on a NTRUlike scheme introduced by Verkhovsky in [1]. We show how, based on the relation between the public and pr ivate key, we can c onstruct an a ttack which allows any p assive adversar y to decryp t the encryp ted messages. W e explain, step b y step, how a n a ttac ker ca n con str uct an eq uiv ale nt private key and guess what the original plaintext was. Our attack is efficient and provides good experimental re sults. Keywords: Complex Modulus; Primary Residue; Plaintex t Preconditioning; Plaintext Attack; PublicKey Scheme; Lattices; LLL Algorithm; Orthogonal Lattices 1. Introduction Latticebased cryptography has become a research topic more and more studied nowadays. It may offer a good alternative to cryptographic schemes based on classical numbertheory problems (e.g. discrete logarithm, factori zation) that are easily solved on quantum computers. Lattices have proven to provide securely hard prob lems on which we can build cryptographic schemes but also good tools for cryptanalysis. There are several lattice attacks [2,3] done on NTRU [4]. The main tool of these attacks is the LLL algorithm [5]. In order to overcome this, there are variants of NTRU which base their secu rity on lattice hard problems [6]. In this article we present a lattice attack done on a NTRUlike scheme introduced by Verkhovsky in [1]. Based on the relation between the public and private key, we construct an attack which allows any passive adversary to decrypt the encrypted messages. Moreover, our attack is efficient and provides good experimental results. 2. Preliminaries We present in this section the essential background in lattices and Gaussian integers and the algorithms we use in our attack. Notation. We use small letters and capital letters, and , to denote vectors and matrices, respectively. Capital letters like are also used for Gaussian inte gers. In order to avoid confusion, we use the Gaussian integers in the following form 12 . We denote by b BR Rrri ,ab the inner product of two vectors and . ab 2.1. Background Givennlinearly independent vectors 12 , a lattice is the set of all linear combinations of bi’s with integral coefficients: ,,, m n bb b L 12 ,,, . nii Lbbb LBxbx i We say that 12 is the basis of the lattice , is the rank and is the dimension of the lattice . If ,,, n bb b mB L Lnnm , then the lattice is called a fullrank lattice. We define the no rm, a, of a vector 12 ,,, m m aaa a to be the Euclidean norm. The orthogonal la ttice L of is the set of vectors orthogonal with all the vectors from : LL ,0, m. aabb L It makes sense to speak about orthogonal lattice only for non fullrank lattices, where . The lattice nmL has dimension and rank m. mn One important tool in cryptanalysis, LLL algorithm [5] was published in 1982 and since then couple of schemes were broken [79] by using it. Several improvements that reduce its complexity appeared in [10,11]. Given a basis of a lattice, th e aim of the L LL algorithm is to provide a LLL reduced basis where the first vector gives an ap proximation of the shortest nonzero vector of , L L 1 . It is possible to apply the LLL algorithm for the orthogonal lattice L (See Algorithm 2.1). The notation m bm b denotes the last compo nents of , with m bn . Bywe denote the trans T B C opyright © 2012 SciRes. IJCNS
S. M. BOGOS, S. VAUDENAY 835 Algorithm 2.1. LLL algorithm for[12]. L Input: Lattice basis . 12 ,,, m n bb b Output: A LLL reduced basis for . 1. Select 12 14 1 2n mmnmn i i cb . 2. Construct matrix . , T mm cB BI 3. Run LLL algorithm on the lattice spanned by to obtain the LLL reduced basis 1,, . m aa 4.Output 1,, . mmm pa pa n pose of matrix .B 2.2. Gaussian Integers Gaussian integers are represented by the set 2 12 12 ,,irrirr i 1. The norm of a Gaussian integer , denoted by R NR, is defined as . The units of 2 12 NR r r 2 i are . 1, i For division in i with unique remainder we need the following definition: Definition 1([1]). Given two Gaussian integers, 12 aai and , we say that 12 Rrri is a primary residue moduloif the following 4 inequalities are satisfied: R 1221 0rara NR 1 112 2 0raraNR 1. a All primary residues modulo Rre located inside the square with vertices ,,ORi with sides equal to ,1R iR and .NR This definition allows us to have the following theo rem: Theorem 1. For any two Gaussian integers , Ri, with 0R , there exists unique ,BCi such that RCB and is a primary residue modulo. B R We denote . Note that modBA R RC B is not the Euclidean division. For completeness, we provide in this section all the definitions used in the formalization of the scheme for which we construct an attack. Definition 2. PrimesinR ican be expressed by one of the following forms: 12 0,0 and 2 r is a prime number of the form 43n with rr 0,nn. 12 0,0 and 1 r is a prime number of the form 43n with rr 0,nn. 0,0 and 12 rr NR is a prime number. Theorem 2. A prime number of 12 Rrri i is an irreducible element. Every irreducible element has a unique prime representative (i.e., R1 R is an unit). Two Gaussian integers, , Ri, 0A and 0R , are relatively prime if they have no prime factors in common. The greatest (in the sense of the norm) com mon divisor of any two elements of i is unique up to a unit factor. The Euclid algorithm (using Euclidean division) always r eturns a greatest (in the sense of norm) common divisor. A multiplicative inverse of modulo , with R nn , exists if and only if and n NR n R are relatively prime. 3. Double Moduli Cryptosystem The cryptosystem introduced by Verkhovsky in [1], for which we construct an attack, is described in this section. We assume an a priori agreed large integer . Apart from the value , which is an integer, all the other pa rameters and inputs are Gaussian integers. n 3.1. Encryption/Decryption Algorithms Algorithm 3.1 presents the steps followed by a partici pant with the aim of obtaining its public and private keys. The private key consists of two parts, P an , wh are relatively prime. Here, P is invertible modulo n. The public key, U, is obtaineby multiplying R with the inverse of P modulo n. d ich d Before encrypting a message 12 mm R i R with the public key , one has to precondition the plaintext so that it is a primary residue modulo , where is part of the private key. Since is not known to the sender, a threshold is imposed so that the inequalities from Definition 1 hold. The preconditioned plaintext must be selected such that the upper bound of the real and imaginary parts is U R W6n. The algorithms of preconditioning and recovery of a plaintext are de scribed afterwards. Algorithm 3.2 shows how to encrypt a precondi tioned plaintext W. Besides the public key U, the sender chooses periodically a new value 12 Sssii . After hiding the value of the public key, by multiply ing it with, the ciphertext is obtained by adding this new value to the plaintext. S After receiving the ciphertext and provided that it has the correct private keys, the receiver is able to decrypt the message by following the steps from Algorithm 3.3. After the first step of the algorithm the receiver will compute as DPW RS . In the second step, he is able to compute as the inverse of modulo , as and were chosen such that they are relatively prime. Finally, in the last step, the preconditioned plaintext is QPRP R Copyright © 2012 SciRes. IJCNS
S. M. BOGOS, S. VAUDENAY 836 Algorithm 3.1. Key generation. Input: Large integer . n Output: Public key ; Private key: Ui ,. Ri Constraints: 21 12 :0, 6,23; ippn ppn 212112 :0, ,6,23. irrrr nrrn 1. Choose uniformly , Ri such that the constraints are respected and 12 ,gcdpr r 12 ,1,pgcd1, and are relatively prime, and are relatively prime. n 2. Compute 1mod . Pn 3. mod.UFR n Algorithm 3.2. Encryption. Input: Preconditioned plaintext , integer . Wi n Public key: . Ui Output: Encryption . Ci Constraints: 1212 :0,0 ,6Siss ssn ; 21 12 :0,0 ,6.Wi wwwwn 1. Select uniformly such that the constraints are respected. 12 Ss si 2. mod .CWSU n Algorithm 3.3. Decryption. Input: Encryption , large integer. Ci n Private key: ,. Ri Output: Preconditioned plaintext .Wi 1. mod . PC n 2. Compute 1mod .QP R 3. mod .WQD R obtained. Afterwards, the receiver will run the algorithm of plaintext recovery, algorithm illustrated later. 3.2. Plaintext PreConditioning As aforementioned, the plaintext is preconditioned be fore being encrypted. Similarly, a plaintext recovery al gorithm is necessary in order to obtain the original mes sage after decryption. These two transformations are il lustrated in Algorithms 3.4 and 3.5. As must be a primary residue modulo the sender must ensure that the original plaintext W ,R is split into blocks of appro priate sizes. 4. Using LLL to Break the Scheme This section presents our lattice attack. We prove that the double moduli scheme is insecure as any passive adver sary that observes the encrypted messages can decrypt them with a nonnegligible probability. Algorithm 3.4. Plaintext preconditioning. Input: Message . i Output: Preconditioned plaintext . Wi 1. . 112 wmm 2. if 12 ,mm t hen 21 2 ;wmm e lse 221 1.wmm Algorithm 3.5. Plaintext recovery. Input: Preconditioned plaintext Wi Output: Message . i 1. if 12 mod2ww then 11 2211 2, ;mww mwm else 112 12mww 21112 12. mwm ww 4.1. Lattice Attack An attacker is a probabilistic algorithm which runs in polynomial time. From Algorithm 3.1 an attacker can observe the following relation between , and namely P RU modPURn . Using this relation he is able to obtain an equivalent private key. This equivalent key is not necessary the private key ,PR, but can be used to decrypt correctly the encrypted message. We write the aforementioned relation for the imaginary and real parts and separate the known parts from those un known. We obtain the following equation: 1 2 12 1 21 2 1 2 10 00 010 0 p p uun r uu nr k k With the design constraints of the scheme where both components of the private key are of size n and the public key is of size , both and should be of size n1 k2 k n. Vectors 112 ,,1,0,,0vuun and 221 ,,0,1,0,vuu n are linearly independent and are also orthogonal. They form the basis, , of a lattice B 12 , vv of dimen sion and rank . Vector 62 112 ,,opp L.L 1212 from the above relation is orthogonal to both vectors and belongs to the orthogonal lattice of We can run ,,,rrkk Copyright © 2012 SciRes. IJCNS
S. M. BOGOS, S. VAUDENAY 837 Algorithm 2.1 to obtain a reduced basis of BL . The four vectors from B should be small in the sense that their norm should be at most 1 4 det L [12]. As 1 and 2 v are orthogonal, the determinant of can be easily computed as vL 222 2 n2 2 12 2 det1 1 31 Lvv nnnnn n Thus, the vectors of the reduced basis of L should have norm at most 1 24 31n which is of order .n Comparing this value with the norm of the vector 1 which is also of order o n indicates that 1 o may not be the shortest vector from L Nevertheless, using the vectors from we can find an equivalent key B ,PR that decrypts correctly the ciphertext . C With the results we have so far, we can design a de cryption strategy for an attacker illustrated in Algorithm 4.1. Algorithm 4.2 follows. The following lemma proves that the experiment works correctly: given the ciphertext and the public key, the attacker is able to obtain an equivalent private C Algorithm 4.1. Decrypting C with an equivalent private key (P′, R′). Input: Encryption .Ci Public key: , . Ui n Output: Equivalent private key , R , preconditioned plain text .W 1. Set the basis of lattice to be 12 (, )Bvv where, 0 ., 1122 21 ,,1,0,, 0, ,, 0,1,vuun vuun 2. Run the LLL algorithm to obtain the reduced basis, 1234 ' ',',',',Bvvvv of the orthogonal lattice . 3. With 121212 , ,,,,, jjjjj j v pprrkk construct 12 jj j ppi and 12 jj j rri, with 14j. 4. If , j PR such that P and are relatively prime, 14,j then PP and R Run Algorithm 4.2 with input C and private key ','. R else Fail. Algorithm 4.2. New decryption procedure. Input: Encryption , large integer. .Ci n Private key: ,. Ri Output: Preconditioned plaintext .Wi 1. mod . PC n 2. Compute 1mod .QPR 3. For all 13 possible values for i such that 5Nx , compute modWQ Dxn .R key and to decrypt correctly . C Lemma 1. The new decryption algorithm works cor rectly for an equivalent key ,PR , given that P and R are relatively prime. Proof. Let modCWSU n be the encrypted message. Algorithm 4.1 constructs the private key ,PR . From the way we obtained , we have L mo dnPU R. Then, mod mod mod mod . DPC n PWSU n PW PSUn PW RSn PW RSxn We can bound the value of from equality DPWRSx n . 2 22 2 max , 4max , 413 231 . 33 N xnN DN PWRS NDNP NR NS NW n nn n So, 5Nx which gives us possibilities for 13 . Using the last equality and computing , we obtain that 1modQP R mod mod mod . QDxn R QPWRS R WR By knowing the values of , Q and , we can find the value of n modWR . Having, with high probability, NW NR , we can guess the original precondi tioned plaintext by trying all four values that are inside the circle ,CONR with origin and radius O NR . Given moWdR , one may obtain the other three values by adding to it or ,iRR, R iR . If we analyze the complexity of Algorithm 4.1, we easily see that each step is completed in polynomial time. By running Algorithm 4.1, an adversary is able to de crypt any message with a high probability. Thus, the scheme is not secure (i.e. not even oneway encryption secure). 4.2. Experimental Results The experiments were done on an INTEL Q9550 GHz processor, running a 32bit version of Windows 7. 2.83 The implementation of the scheme and of the attack was done in the PARIGP environment. The structure of the scheme was respected as it is described in Algo Copyright © 2012 SciRes. IJCNS
S. M. BOGOS, S. VAUDENAY Copyright © 2012 SciRes. IJCNS 838 REFERENCES Table 1. Experimental results of the lattice attack. 2 log n Prob. of success Running time 128 1 0.09 s 256 0.996 0.28 s 12 0.999 0.8 s 1024 0.996 1.19 s 2048 0.997 2.23 s [1] B. S. Verkhovsky, “DoubleModuli Gaussian Encryption/ Decryption with Primary Residues and Secret Controls,” IJCNS, Vol. 4, No. 7, 2011, pp. 475481. doi:10.4236/ijcns.2011.47058 [2] D. Coppersmith and A. Shamir, “Lattice Attacks on NTRU,” Advances in Cryptology—EUROCRYPT ’97, Interna tional Conference on the Theory and Application of Cryp tographic Techniques, Konstanz, 1115 May 1997, pp. 5261. [3] A. May, “Cryptanalysis of NTRU,” 1999. http://wwwstud.rbi.informatik.unifrankfurt.de/~alex/ntru.ps rithms 3.13.3. From the beginning we use precondi tioned messages. For the Gaussian integers the division operation was implemented making use of the notion of primary residue (see Theorem 1). We made use of the already implemented LLL algorithm, qflll, from the PARI GP library. [4] J. Hoffstein, J. Pipher and J. H. Silverman, “NTRU: A RingBased Public Key Cryptosystem,” Algorithmic Num ber Theory, Third International Symposium, ANTSIII, Portland, 2125 June 1998, pp. 267288. [5] A. K. Lenstra, H. W. Lenstra Jr. and L. Lovász, “Factor ing Polynomials with Rational Coefficients,” Mathema tische Annalen, Vol. 261, No. 4, 1982, pp. 515534. doi:10.1007/BF01457454 Regarding the attack, the implementation respects Al gorithms 4.1 and 4.2. We run the attack and output all values that satisfy the constraints from Algorithm 3.2. We consider having a success when one of the outputted values is equal to the original plaintext. If no such value is displayed, then the attack fails. W[6] D. Stehlé and R. Steinfeld, “Making NTRU as Secure as WorstCase Problems over Ideal Lattices,” Advances in Cryptology—EUROCRYPT 2011—30th Annual Interna tional Conference on the Theory and applic ations of Cryp tographic Techniques, Tallinn, 1519 May 2011, pp. 27 47. We tested the attack for different sizes of the value namely values varies between 128 to bits. A thousand experiments were done for each size of . The results that we obtained are displayed in Table 1. ,n 2048 n[7] J. Håstad, “On Using RSA with Low Exponent in a Public Key Network,” Advances in Cryptology—CRYPTO ’85, Santa Barbara, 1822 August 1985, pp. 403408. In almost all the cases one of the candidates messages was the original plaintext. The very few cases when the message is not recovered is due to possible two scenarios. It may happen that all four possible values of R are smaller than the message and an attacker loses the value of the message by performing the operation . The second scenario may be that none of the four possible values of and are relatively prime. This can be repaired by constructing a new private key as the linear combination of the four possible private keys, using small coefficients. W modW [8] J. C. Lagarias and A. M. Odlyzko, “Solving LowDensity Subset Sum Problems,” Journal of the ACM, Vol. 32, No. 1, 1985, pp. 229246. doi:10.1145/2455.2461 [9] C. Gentry, J. Jonsson, J. Stern and M. Szydlo, “Crypt ANALYSIS of the NTRU Signature Scheme (NSS) from Eurocry pt 2001,” Advances in Cryptology—ASIACRYPT’01, 7th Internation al Conference on the The ory and Applic at i on of Cryptology and Information Security, Gold Coast, 913 December 2001, pp. 120. RPR [10] P. Q. Nguyen and D. Stehlé, “An LLL Algorithm with Quadratic Complexity,” SIAM Journal on Computing, Vol. 39, No. 3, 2009, pp. 874903. doi:10.1137/070705702 This experimental result ascertains that the double moduli cryptosystem from [1] is insecure. [11] C.P. Schnorr, “A Hierarchy of Polynomial Time Lattice Basis Reduction Algorithms,” Theoretical Computer Sci ence Journal, Vol. 53, 1987, pp. 201224. doi:10.1016/03043975(87)900648 5. Conclusion In this article we have presented a lattice attack done on a NTRUlike scheme. The main tool is the LLL algorithm used on the orthogonal lattice. Our attack is efficient and gives good results as, in almost all the cases, we can guess correctly the value of the plaintext. Hence, we broke the scheme. [12] P. Q. Nguyen and J. Stern, “MerkleHellman Revisited: A Cryptanalysis of the QuVanstone Cryptosystem Based on Group Factorizations,” Advances in Cryptology— CRYPTO’97, 17th Annual International Cryptology Con ference, Santa Barbara, 1721 August 1997, pp. 198212.
