Int. J. Communications, Network and System Sciences, 2011, 4, 475-481
doi:10.4236/ijcns.2011.47058 Published Online July 2011 (http://www.SciRP.org/journal/ijcns)
Double-Moduli Gaussian Encryption/Decryption with
Primary Residues and Secret Controls
Boris S. Verkhovsky
Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA
Received June 22, 2011; revised July 5, 2011; accepted July 19, 2011
Abstract
In this paper an encryption-decryption algorithm based on two moduli is described: one in the real field of
integers and another in the field of complex integers. Also the proper selection of cryptographic system pa-
rameters is described. Several numeric illustrations explain step-by-step how to pre-condition a plaintext,
how to select secret control parameters, how to ensure feasibility of all private keys and how to avoid ambi-
guity in the process of information recovery. The proposed public key cryptographic system is faster than
most of known public key cryptosystems, since it requires a small number of multiplications and additions,
and does not require exponentiations for its implementation.
Keywords: Ambiguity-Free Information Recovery, Complex Modulus, Cryptosystem Design, Cycling
Identity, Information Hiding, Plaintext Preconditioning, Primary Residue, Public-Key
Cryptography, Secret Controls, Threshold Parameters
1. Introduction and Primary Residues
This paper describes and briefly analyzes a public key
cryptographic (PKC) based on primary residues and
Gaussian modulus. The framework of the proposed PKC
partially resembles NTRU PKC [1,2] {more details are
provided in www.ntru.com} that was introduced in 1996
and later patented by three mathematicians from Brown
University. Their PKC was analyzed in several papers
[3-5]: in [3] it was pointed out that the decryption did not
always recover the initial plaintext. Nevertheless, the
NTRU had such a computational appeal that its authors
were granted a USA patent even before the flaws in the
algorithm were eliminated. Papers [4,5] provided several
scenarios of cryptanalysis of the NTRU.
In this paper we consider a public key cryptographic
system with two modulo reductions:
● Real integer modulus n and
● Complex (Gaussian) modulus R [6].
As a result, all public and private keys of each user
and secret controls S are also Gaussians. Since plaintext
blocks are also Gaussian, to avoid ambiguity in informa-
tion recovery a concept of primary residues is introduced.
It is demonstrated how to ensure that all keys of the pro-
posed cryptosystem provide unambiguous recovery of
initially pre-conditioned and subsequently-encrypted in-
formation.
In the proposed cryptosystem there is no necessity to
consider polynomials with binary coefficients as it is
done in papers [1] and [2].
1.1. Complex Modulo Reduction
Real modulus: In a group based on real modulo reduction
n there are two results, whether n is either prime or
composite: if mod 0anb

, then mod 0anbn


is also correct.
In order to avoid ambiguity, we can stipulate that only
non-negative results are feasible.
Complex modulus: Consider Gaussian integers


12
:,
B
bb, and


12
:,Rrr. In an arithmetic based on
modulo reduction with complex integer R there are four
possible results: if mod
A
RB, where both A and B
are complex integers, then





  
121 122
1221 112212
mod, ;,;
,; ,
ARbbbrbr
brbr brrbrr

 
are also correct. In order to avoid ambiguity in this case,
it is stipulated in this paper that only primary residues
are feasible {a definition and details are provided below}.
Let’s define the norm N of R as

B. VERKHOVSKY 476
22
12
::NRrr (1.1)
Then



 
12
12 12
,: ,mod,
,,, ,
xy abrr
ababrrNr r

 

(1.2)
1.2. Primary Residues
Let’s define two functions of integer variables x1 and x2
with integer parameters r1 and r2:

121221
,: ;
H
xxrxrx (1.3)
and

1211 22
,:Vxxrx rx. (1.4)
Definition 1.1 {primary residue}: A Gaussian integer

12
,
A
aa is called a primary residue modulo R if it
satisfies four inequalities:

12
0, 1Haa N; (1.5)
and

12
0, 1Vaa N. (1.6)
Property 1.1: If a Gaussian integer G is a primary
residue modulo Gaussian R, then
mod .GRG (1.7)
In the cryptographic scheme described below a plain-
text M is divided onto pairs of blocks


12
,
M
mm,
where each pair is treated as a Gaussian integer. In the
cryptographic algorithm below, it is important to assure
that the numeric representation

12
,
M
mm is a pri-
mary residue modulo R.
1.3. Plaintext as Primary Residue
In general,

12
,
M
mm is the primary residue modulo
R, if m1 and m2 satisfy the following inequalities:

12
0, 1HmmN; (1.8)

12
0, 1VmmN. (1.9)
Remark 1.1: If both components in R are positive, then

12
,1,0aa  is not a primary residue modulo R since
(1.5) does not hold. Indeed,






21 12
1, 01,mod,rr rr .
And, as a result, property (1.7) does not always hold.
However, if 21
0rr, then (1,0) is the primary resi-
due.
If 20r, then (1.8) implies
22
122 112
0rmr mrr ; (1.10)
and (1.9) implies that
22
112 212
0.rmrmrr  (1.11)
Therefore, the right inequalities in (1.10) and (1.11)
are respectively equivalent to

1122 21
0( )rr mr rm
and

111222
0( )rr mr rm ,
which hold if
211 211
;; and mrmr mr

. (1.12)
In addition, the left inequality in (1.11) holds if

 
21 12
mm rr. (1.13)
1.4. Geometric Interpretation
All primary residues are located inside a tilted square
(rhomb) with vertices


0, 0;;;1RiR iR and with
sides equal
22
12
rr (1.1).
If


12
gcd ,1rr

, then there are exactly 1N

pri-
mary residues inside this rhomb.
2. Cryptographic System Based on Primary
Residues
1) All users (i = 1, 2, ···) agree to select a large real inte-
ger n {the same for all of them};
2) The i-th user has private and public keys, and secret
controls ,,,,
iiiii
PRU QS with index i; {in the forthcom-
ing discussion index i is omitted for the sake of simplic-
ity of notations};
3) Vari ables : P, R, U, Q, S, F, W, where each of them
is a complex (Gaussian) integer;
4) User’s private keys:

12
,;
P
pp

12
,
R
rr; where
R is also a Gaussian prime
and


12 12
gcd,1; gcd,1;pp rr

 (2.1)
{the second condition in (2.1) holds if R is a Gaussian
prime};
Remark 2.1: The stipulation that R is a Gaussian prime
is sufficient to assure that certain conditions hold, but not
necessary. Hence, it can be omitted under other consid-
erations.
5) Every user pre-computes inverse
 
1
121 2
:,:, mod
F
ff ppn

 [7]; (2.2)
Remark 2.2: a Gaussian multiplicative inverse F of P
modulo real integer n exists
if

 
22
12
gcd ,1;:
P
nPpp
; (2.3)
6) Every user pre-computes her/his public key



 
1212 12
:,:, ,mod;Uuu ffrrn (2.4)
7) Every user pre-computes a multiplicative inverse Q
of P modulo Gaussian prime R:

B. VERKHOVSKY 477
 
1
121 212
:,: ,mod,;Qqqpprr

 (2.5)
Multiplicative inverse Q of P modulo R exists if

gcd,1,0.PR  (2.6)
Remark 2.3: As demonstrated in [7], P has multiplica-
tive inverse modulo R even if

gcd ,1PR. For
instance, although



12 21
,,rr rr,
yet

12 21
gcd,,,1, 0.rrrr 


(2.7)
Therefore, if R is a Gaussian prime, then every Gaus-
sian is co-prime with R, i.e., it has a multiplicative in-
verse modulo R. Primality of R is sufficient, but not nec-
essary condition. The algorithm for computation of Q in
(2.5) is provided below in Section 9.
Remark 2.4: Condition (1.13) is not directly verifiable
by a sender since R is the private key of the receiver. Yet,
the sender has an option to indirectly satisfy (1.13). In-
deed, if 21 rr and 21
1mm

, then (1.13) holds; oth-
erwise switch m1 and m2 in M:
2112
:;:wmwm (2.8)
Then, as a result,
 
21 12
1.ww rr (2.9)
Remark 2.5: Since r1 and r2 are design parameters of
the cryptographic algorithm, they can be properly se-
lected. On the other hand, m1 and m2 are inputs of the
algorithm. As a result, a designer of this algorithm must
ensure that both inequalities (1.11) hold for every pair

12
,mm by partitioning the plaintext onto blocks of
appropriate sizes.
Remark 2.6: In the forthcoming discussion it is as-
sumed that

12
:,Www is already pre-conditioned
plaintext; i.e., in every Gaussian block 12
ww.
3. Hiding Information and Its Recovery
3.1. Threshold Parameter
Suppose that a sender (Sam) transmits a plaintext mes-
sage

12
,
M
mm to a receiver (Rene). The size of
plaintext blocks m1 and m2 must be selected in such a
way that
12 1
0, ;mm ur (3.1)
and plaintext M must be a primary residue modulo R
{see (1.8-1.13)}. Here variable u (threshold) is the same
for all users; its value is established below.
3.2. Sender’s Secret Key
For security reason, the sender periodically selects a
randomized secret key

12
:,Sss. S plays two roles: it
is a screen/veil that hides information; and at the same
time it is a control that enables the system user to satisfy
certain constraints. Proper selection of S is discussed
below.
Encryption: Using Rene’s public key U, Sam selects
secret control S and computes ciphertext:


:mod.CMSU n (3.2)
Decryption: {requires real and Gaussian modulo re-
ductions}:
Stage 1 {Real modulo n reduction}:
:modDPC n

; (3.3)
Stage 2 {Gaussian modulo R reduction}:
:mod.
Z
QD R

(3.4)
3.3. Algorithm for Multiplicative Inverse of P
Modulo Complex R
The algorithm computes the user’s private key


1mod ,QP R 
 where

,.Rpq (3.5)
If R is a Gaussian prime, then


2mod N
QP R

 , where 22 .Npq (3.6)
Computation (3.6) of multiplicative inverse (3.5) is
based on the following identity.
Propositi on 3.1 {cyclic identity}: If






gcd,,,1, 0abpq 

and

,pq is a prime, then the
following identity holds:
 
1
,mod,1,0
N
ab pq
 [6]. (3.7)
4. Validation of Encryption-Decryption
Algorithm
Proposition 4.1: If W is a primary residue and private
keys P, R and secret control S are selected in such a way
that holds


mod ,PW RSnPW RS (4.1)
then in (3.4)
.
Z
W

(4.2)
Proof: (2.2, 2.4, 2.5, 3.3 and 4.1) imply that


 





 
4.1
2.2
2.4
3.2 3.3
1, 0mod
mod mod
mod mod
modmod .
PW RSPWRSn
PWPFn RSn
PWFRn Sn
PW USnPCnD


 


 

  
 


 
(4.3)

B. VERKHOVSKY 478
Equation (4.3) holds since W, P, R, S are properly se-
lected to ensure Equation (4.1).
Then





 
4.3
2.5 ;1.7
mod mod
mod mod
modmod
1,0mod0
.
Z
QDRQPWRSR
QPRWR
QSR RR
WQS R
W

 



 
 

(4.4)
Finally, the latter equality in (4.4) holds since W is a
primary residue modulo R (1.5)-(1.7), i.e., because
modWRW. Q. E. D.
Propositi on 4 .2: if
● Absolute value of every component of private keys
P and R is larger than threshold parameter 6un
and does not exceed 2u;
● Each component of plaintext W is positive and does
not exceed u; and
● Absolute value of each component in secret control
S does not exceed u,
then the encryption/decryption cryptosystem (3.2)-(3.4)
provides unambiguous results.
5. Cryptosystem Design
Inputs m1 and m2 are independent variables known only
to the sender (Sam). There are two types of variables:
long-term static system parameters (strategic variables)
and short-term dynamic controls (tactical variables):
System parameter n; Strategic variables P and R; Dy-
namic controls S; and Observable inputs: W

12
ww.
Here it is assumed that plaintext

12
, ww is already
preconditioned; {more details are provided below}.
In addition, every W must be a primary residue for the
receiver, i.e., W and modulus R for every user must sat-
isfy the following system of inequalities with eight inte-
ger variables:
11 22
0; 0;wur wur (5.1)
22
122 1122 112
0; ;rwr wrwrwrr (5.2)
22
2 211 111222
;.rwrw rwrrrw (5.3)
(5.1)-(5.3) are conditions that ensure that W is a primary
residue modulo R.
If 10s and 20p, then controls S and private key
P must satisfy constraints:
11112222
0;pwr spwrs (5.4)
111 12222;pwr spwrsn  (5.5)
1221122 1
0;pwp wrsrs  (5.6)
1221122 1.pwp wrsrsn

  (5.7)
If (5.4)-(5.7) hold, then (4.1) also holds.
6. Equalizing the Feasibility Intervals
Notice that at most three terms in (5.5) and (5.7) are
positive. Hence, if every product does not exceed 3n,
then the sum of three terms does not exceed n.
Let
0;;; ,
kkkk
wus uup vurv

 (6.1)
where u and v are unknown real numbers.
Hence 3,PCuv n

 i.e., 3.uv n (6.2)
Select such u and v that the lengths of feasibility inter-
vals for private keys P and R, secret key S and plaintext
W are equal. Hence, uvu

, which implies 2u = v.
Thus,
2
23un (6.3)
which implies that
6un and 23.vn (6.4)
Therefore, the following inequalities must hold:
06;6;
623;623.
kk
kk
wns n
npnnrn

 (6.5)
Notice that Sam (the sender)
● Knows the input w1 and w2;
● Does not know P and R of Rene (the receiver);
● Dynamically selects controls s1 and s2.
Corollary 6.1: If 3 and 3
ij kl
pwnrsn, the
value of each component in W and S is smaller than
6,n 1,p 2,p 1 r and 2 r are on interval 6, 2 3nn


,
then it ensures that W is a primary residue and that


modPWRSnPWRS (4.1).
Remark 6.1: By analogy with (5.1-5.3, 4.1) means that
PW + RS is a “primary residue” modulo n.
7. Plaintext Preconditioning and Recovery
Plaintext preconditioning: Compute
112
:;wmm

 (7.1)
if
12
,mm then 212 :wmm

 else 221 :1.wmm (7.2)
Plaintext recovery: After decryption, the receiver com-
pares parities of w1 and w2:
if


12
mod 2,ww then


112
:= 2mww and 211 :;mwm (7.3)

B. VERKHOVSKY 479
Table 1. Public keys {n-real, U-Gaussian} and private keys {P, Q, R-all Gaussian}.
R Private key P Private key


1modQP R 
 Private keymodUFR n

Public key
R = (2270,−2203) P = (2291, −2180) Q = (2858, 421) U = (7624492, 258305)
Table 2. {Encryption/Decryption}: n = 10006001; 0 1291W

; 0 1291S .

12
,Www

12
,Sss C = (W + SU) mod nD = PC mod n Z = QD mod RPlaintext M Recovered
(1223, 973) (−859, 949) (9511830, 9559186) (5063750, 3609610)(1223, 973) (1098, 125)
(959, 941) (−999, 1234) (9149875, 5092460) (4699221, 5067188)(959, 941) (950, 9)
(1234, 95) (−954, 1285) (8880702, 5324391) (3699469, 2546137)(1234, 95) (569, 665)
(1267, 1201) (−999, 1234) (9150183, 5092720) (5971649, 4991408)(1267, 1201) (1234, 33)
(18, 17) (−16, 1291) (4812437, 3187326) (2886051, 2965525 (18, 17) (0, 18)
else


112
211 12
:12 and
:12.
mww
mwm ww

   (7.4)
8. Numeric Illustrations
Let n = 10006001; the user’s private keys P, Q, R and
public key U are listed in Table 1. Here

2291, 218010001081;P
P is a primary residue modulo R; R = 10006109; and
feasibility threshold parameters are equal:
u = 6n = 1291; and 2u = 23n = 2582.
In Table 2 every block of plaintext W is primary resi-
due of R, and the following constraints are satisfied:
12 21
06;0 6
s
sn wwn .
Notice that for each of five blocks W we considered
different secret controls S.
9. Algorithm for Multiplicative Inverse of P
Modulo complex R
This algorithm computes

1modQP R 
,
where

,Rpq. (1.1) (9.1)
If R is a Gaussian prime, then


2mod N
QP R

,
where
|| ||NR (9.2)
If 12
RRR, where each factor in R is a Gaussian
prime, then

1mod N
QP R
 
, (9.3)
where


N  is Euler totient function and
12
|||| ||||||||RRNR



. (9.4)
Computation (9.2) and (9.3) of multiplicative inverse
(9.1) is based on the following identity.
Propositi on 9.1 {cyclic identity}: If 
gcd[(a, b), (p, q)]=(1,0),
then the following identity holds:



 
1 ||, || 1
(,),mod( , )
pq
abab pq
  . (9.5)
Proof follows from identity




||, ||
( ,)mod(,)1,0
pq
ab pq

 [6]. (9.6)
Example 9.1: Suppose R = (9,-2) and P = (3,2); then
N=||(9,-2)||=85 and


85 64 

.
Hence,

63
1mod3, 2mod9,2(5,2)QP R 

.
Indeed,



 
3, 25,21,0modR .
Remark 9.1: The inverse of P can be also computed
via solution of a Diophantine equation, but that is beyond
the scope of this paper.
10. Computational Complexity
Encryption of each W requires three multiplications and
five additions of real integers.
Decryption requires twice as many of these operations.
Since addition/subtractions are much faster than multi-

B. VERKHOVSKY 480
plications, they can be neglected [8]. Therefore, we need
nine multiplication of


log 2n-digit long integers,
which means that bit-wise complexity is of order

2
log n. This complexity can be reduced if we apply
more elaborate algorithms for multiplication of multi-
digit long real integers [9,10].
11. Conclusions
In this paper an encryption-decryption algorithm based
on real and complex modulo reductions is considered
and analyzed. A concept of primary residues is intro-
duced to avoid ambiguity in information recovery. Sev-
eral numeric illustrations explain step-by-step how to
pre-condition a plaintext, how to select public and pri-
vate keys for every user, and how to select secret con-
trols for every block of the plaintext in order to ensure
unambiguous recovery of the initial information. The
proposed cryptosystem requires a small number of mul-
tiplications and additions, and as a result, it is extremely
fast.
Although certain steps in the proposed cryptosystem re-
semble the NTRU cryptosystem, yet it differs from the
NTRU in many features. One of them is absence of
polynomials.
In paper [8] is provided a brief history on the NTRU,
which is reiterated below. The NTRU that was initially
presented at Crypto ’96 was cryptanalyzed and broken in
[11] by the method of lattice-basis reduction methods [12]
that determines short vectors in a lattice, which arise on
the decryption stage. Soon after that in papers [13] and
[14] were described two other successful attempts to
break the NTRU. An NTRU signature scheme was pro-
posed in [15], but that scheme and its revision were bro-
ken in [16] and [17].
12. Acknowledgements
I express my appreciations to P. Garrett and C. Pomer-
ance for suggestions on Gaussian modulus reduction, and
to R. Rubino for comments that improved this paper.
Numerical illustrations provided in this paper were fa-
cilitated thanks to programming support by S. Sadik and
B. Saraswat.
13. References
[1] J. Hoffstein, J. Pipher and J. Silverman, “NTRU: A Ring-
Based Public Key Cryptosystem,” Algorithmic Number
Theory: 3rd International Symposium (Lecture Notes in
Computer Science), Portland, Vol. 1423, 21-25 June 1998,
pp. 267-288.
[2] J. Hoffstein, J. Pipher and J. Silverman, “NSS: An NTRU
Lattice-Based Signature Scheme,” Advances in Cryptol-
ogy—EUROCRYPT 2001: International Conference on
the Theory and Application of Cryptographic Techniques
(Lecture Notes in Computer Science), Innsbruck, Vol.
2045, 6-10 May 2001, pp. 211-228.
[3] N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J.
Proos, J. Silverman, A. Singer and W. Whyte, “The Im-
pact of Decryption Failures on the Security of NTRU En-
cryption,” Advances in Cryptology—CRYPTO 2003: 23rd
Annual International Cryptology Conference (Lecture Notes
in Computer Science), Santa Barbara, Vol. 2729, 17-21
August 2003, pp. 226-246.
[4] D. Coppersmith and A. Shamir, “Lattice Attacks on NTRU,”
Advances in Cryptology—EUROCRY PT ’97: Internati onal
Conference on the Theory and Application of Crypto-
graphic Techniques (Lecture Notes in Computer Science),
Konstanz, Vol. 1233, 11-15 May 1997, pp. 52-61.
[5] E. Jaulmes and A. Joux, “A Chosen Ciphertext Attack
against NTRU,” Advances in Cryptology—CRYPTO 2000:
20th Annual International Cryptology Conference (Lec-
ture Notes in Computer Science), Santa Barbara, Vol.
1880, 20-24 August 2000, pp. 20-35.
[6] B. Verkhovsky, “Protection of Sensitive Messages Based
on Quadratic Roots of Gaussians: Groups with Complex
Modulus,” International Journal Communications, Net-
work and System Sciences, Vol. 4, No. 5, 2011, pp. 287-
296. doi:10.4236/ijcns.2011.45033
[7] B. Verkhovsky, “Cubic Root Extractors of Gaussian In-
tegers and Their Application in Fast Encryption for
Time-Constrained Secure Communication,” International
Journal Communications, Network and System Sciences,
Vol. 4, No. 4, 2011, pp. 197-204.
doi:10.4236/ijcns.2011.44024
[8] N. Koblitz and A. J. Menezes, “A Survey of Public-Key
Cryptosystems,” Research Report, Department of Com-
binatorics & Optimization, University of Waterloo, Wa-
terloo, August 2004, pp. 1-47.
[9] A. L. Toom, “The Complexity of a Scheme of Functional
Elements Realizing the Multiplication of Integers,” Soviet
Mathematics Doklady, No. 3, 1963, pp. 714-716.
[10] D. J. Bernstein, “Fast Multiplication and its Applica-
tions,” In: J. P. Buhler and P. Stevenhagen, Eds., Algo-
rithmic Number Theory: Lattices, Number Fields, Curves
and Cryptography, MSRI, Cambridge University Press,
New York, 2008, pp. 325-384.
[11] D. Coppersmith and A. Shamir, “Lattice Attacks on
NTRU,” Advances in Cryptology, EUROCRYPT 1997,
Lecture Notes in Computer Science, Vol. 1233, Springer-
Verlag, Berlin, 1997, pp. 52-61.
[12] A. K. Lenstra, H. W. Lenstra Jr. and L. Lovasz, “Factor-
ing Polynomials with Integer Coefficients,” Mathema-
tische Annalen, Vol. 261, 1982, pp. 513-534.
[13] E. Jaulmes and A. Joux, “A Chosen Ciphertext Attack
against NTRU,” Advances in Cryptology, CRYPTO 2000,
Lecture Notes in Computer Science, Vol. 1880, Springer-
Verlag, Berlin, 2000, pp. 20-35.
[14] N. Howgrave-Graham, P. Nguyen, D. Pointcheval, J.
Proos, J. Silverman, A. Singer and W. Whyte, “The Im-

B. VERKHOVSKY 481
pact of Decryption Failures On The Security of NTRU
Encryption,” Advances in Cryptology, CRYPTO 2003,
Lecture Notes in Computer Science, Vol. 2729, Springer-
Verlag, Berlin, 2003, pp. 226-246.
[15] J. Hoffstein, J. Pipher and J. Silverman, “NSS: An NTRU
Lattice-Based Signature Scheme,” Advances in Cryptol-
ogy, EUROCRYPT 2001, Lecture Notes in Computer
Science, Vol. 2045, Springer-Verlag, Berlin, 2001, pp.
211-228
[16] C. Gentry, J. Jonsson, M. Szydlo and J. Stern, “Crypt-
analysis of the NTRU Signature Scheme (NSS) from
Eurocrypt 2001,” Advances in Cryptology, ASIACRYPT
2001, Lecture Notes in Computer Science, Vol. 2248,
Springer-Verlag, Berlin, 2001, pp. 1-20.
[17] C. Gentry and M. Szydlo, “Analysis of the Revised
NTRU Signature Scheme R-NSS,” Advances in Cryptol-
ogy, EUROCRYPT 2002, Lecture Notes in Computer
Science, Vol. 2332, Springer-Verlag, Berlin, 2002, pp.
299-320.