Int. J. Communications, Network and System Sciences, 2012, 5, 834-838
http://dx.doi.org/10.4236/ijcns.2012.512088 Published Online December 2012 (http://www.SciRP.org/journal/ijcns)
Cryptanalysis of the Double-Moduli Cryptosystem
Sonia Mihaela Bogos, Serge Vaudenay
École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland
Received October 2, 2012; revised November 2, 2012; accepted November 13, 2012
ABSTRACT
In this article we present a lattice attack done on a NTRU-like 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 Pre-conditioning; Plaintext Attack; Public-Key Scheme;
Lattices; LLL Algorithm; Orthogonal Lattices
1. Introduction
Lattice-based cryptography has become a research topic
more and more studied nowadays. It may offer a good
alternative to cryptographic schemes based on classical
number-theory 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
NTRU-like 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 full-rank 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.
L
aabb
 L
It makes sense to speak about orthogonal lattice only
for non full-rank lattices, where . The lattice
nmL

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 [7-9] 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 non-zero vector of ,
L
L


1
L

. It is possible to apply the LLL algorithm for the
orthogonal lattice L

(See Algorithm 2.1).
The notation


m
p
bm
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
L

.
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
B
 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
A
aai and , we say that
12
Rrri
A
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

,1R iR
and

.NR
This definition allows us to have the following theo-
rem:
Theorem 1. For any two Gaussian integers


,
A
Ri,
with 0R

, there exists unique


,BCi such that
A
RCB
and is a primary residue modulo. B R
We denote . Note that modBA R
A
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


ican 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
A
has a unique prime representative (i.e., R1
A
R


is
an unit).
Two Gaussian integers,


,
A
Ri, 0A

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
M
mm
R
i
R
with
the public key , one has to pre-condition 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 pre-conditioned plaintext
must be selected such that the upper bound of the
real and imaginary parts is
U
R
W6n. The algorithms of
pre-conditioning and recovery of a plaintext are de-
scribed afterwards.
Algorithm 3.2 shows how to encrypt a pre-condi-
tioned plaintext W. Besides the public key U, the
sender chooses periodically a new value


12
Sssii
.
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 pre-conditioned plaintext is
QPRP
R

S. M. BOGOS, S. VAUDENAY 836
Algorithm 3.1. Key generation.
Input: Large integer . n
Output: Public key ; Private key: Ui



,.
P
Ri





Constraints: 21 12 :0, 6,||23;
P
ippn ppn 


212112
:0, ,6,||23.
R
irrrr nrrn 


1. Choose uniformly ,
P
Ri



such that the constraints are
respected and


12
,gcdpr r
12
,1,pgcd1,
P
and
R
are relatively prime,
P
and are relatively prime. n
2. Compute 1mod .
F
Pn


3. mod.UFR n
Algorithm 3.2. Encryption.
Input: Pre-conditioned 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:

,.
P
Ri


Output: Pre-conditioned plaintext .Wi


1. mod .
D
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 Pre-Conditioning
As aforementioned, the plaintext is pre-conditioned 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
M
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 non-negligible probability.
Algorithm 3.4. Plaintext pre-conditioning.
Input: Message .
M
i





Output: Pre-conditioned 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: Pre-conditioned plaintext Wi


Output: Message .
M
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
,
L
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

S. M. BOGOS, S. VAUDENAY 837
Algorithm 2.1 to obtain a reduced basis of BL

.
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


,
P
R

, pre-conditioned plain-
text .W
1. Set the basis of lattice
L
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 .
L

3. With
 121212
, ,,,,,
j
jjjjj
j
v pprrkk
construct
12
jj
j
P
ppi and 12
jj
j
R
rri, with 14j.

4. If

,
j
j
PR such that
j
P and
j
R
are relatively prime,
14,j 
then
j
PP
 and
j
R
R

Run Algorithm 4.2 with input C and private key


','.
P
R
else Fail.
Algorithm 4.2. New decryption procedure.
Input: Encryption , large integer. .Ci

n
Private key:

,.
P
Ri




Output: Pre-conditioned plaintext .Wi


1. mod .
D
PC n


2. Compute
1mod .QPR 


3. For all 13 possible values for
x
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
x
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
x
.
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
x
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 one-way encryption
secure).
4.2. Experimental Results
The experiments were done on an INTEL Q9550
GHz processor, running a 32-bit version of Windows 7.
2.83
The implementation of the scheme and of the attack
was done in the PARI-GP environment. The structure of
the scheme was respected as it is described in Algo-

S. M. BOGOS, S. VAUDENAY 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, “Double-Moduli Gaussian Encryption/
Decryption with Primary Residues and Secret Controls,”
IJCNS, Vol. 4, No. 7, 2011, pp. 475-481.
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, 11-15 May 1997, pp.
52-61.
[3] A. May, “Cryptanalysis of NTRU,” 1999.
http://www-stud.rbi.informatik.uni-frankfurt.de/~alex/ntru.ps
rithms 3.1-3.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
Ring-Based Public Key Cryptosystem,” Algorithmic Num-
ber Theory, Third International Symposium, ANTS-III,
Portland, 21-25 June 1998, pp. 267-288.
[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. 515-534.
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
Worst-Case 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, 15-19 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, 18-22 August 1985, pp. 403-408.
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 Low-Density
Subset Sum Problems,” Journal of the ACM, Vol. 32, No.
1, 1985, pp. 229-246. 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, 9-13
December 2001, pp. 1-20.
RPR
[10] P. Q. Nguyen and D. Stehlé, “An LLL Algorithm with
Quadratic Complexity,” SIAM Journal on Computing,
Vol. 39, No. 3, 2009, pp. 874-903.
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. 201-224.
doi:10.1016/0304-3975(87)90064-8
5. Conclusion
In this article we have presented a lattice attack done on a
NTRU-like 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, “Merkle-Hellman Revisited: A
Cryptanalysis of the Qu-Vanstone Cryptosystem Based
on Group Factorizations,” Advances in Cryptology—
CRYPTO’97, 17th Annual International Cryptology Con-
ference, Santa Barbara, 17-21 August 1997, pp. 198-212.