Int. J. Communications, Network and System Sciences, 2011, 4, 133-138
doi:10.4236/ijcns.2011.43016 Published Online March 2011 (http://www.SciRP.org/journal/ijcns)
Information Protection Based on Extraction of Square
Roots of Gaussian Integers
Boris S. Verkhovsky
Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA
Received February 13, 201 1; revised February 20, 2011; accepted Februa ry 22, 2011
Abstract
A cryptosystem, based on computation of square roots of complex integers modulo composite n, is described
in this paper. This paper provides an algorithm extracting a square root of Gaussian integer. Various proper-
ties of square roots and a method for finding Gaussian generators are demonstrated. The generators can be
instrumental in constructing other cryptosystems. It is shown how to significantly reduce average complexity
of decryption per each block of ciphertext.
Keywords: Public Key Cryptosystems, Square-Root Extraction, Gaussian Integers, Gaussian Generator,
Multiplicative Inverse, Square Root Algorithm, Information Hiding, Ambiguity of Recovery
1. Introduction
In recent publications public-key cryptography (PKC)
algorithms are generalized in the field of complex inte-
gers that were introdu ced and analyzed by Carl F. Gauss
[1]. In this paper complex numbers are denoted as

, :.aba bi
Definition 1: If all components in

, are integers,
then such complex number is called a Gaussian integer
[1].
b a

Applications of Gaussian integers {Gaussians, for
short} in PKC were extended to the RSA scheme [2],
and to ElGamal cryptosystems [3]. While groups based
on real integers have cycles of order , groups
based on Gaussians modulo prime p have cycles of order
. In this paper is described a cryptosystem based
on extractors of square roots of complex integers modulo
composite n. The kernel of the proposed application is a
method for extracting square roots of a Gaussian modulo
k, where , and are distinct and large
primes.

Op

2
Op
nkk npqkk pk q
2. Gaussian Integers
2.1. Arithmetic of Gaussian Integers
Modulo reduction:
 
, modmod,modabn anbn;
Multiplication: Let






; , :,,mod:; :;
g
habcd nAacBbd 
C := a + c; D := b + d; then

: mod
g
AB n ;
and


: modhCDAB n [4].
Modular multiplicative inverse:
If


22
gcd, 1abn

, then there exists (r, s) such that






1,0ab,, mod rs n.
Gaussian (r, s) is called a modular multiplicative in-
verse of (a, b) [5]; and
 


1
22
, :, mod .rsap b abn

 

.
(2.1)
2.2. Square Root of Gaussians
(x, y) is called a square root of (c, d) modulo p if
 
2
, mod ,
x
ypcd (2.2)
Let in (2.2) Gaussian (c, d) be an input and Gaussian
(x, y) be an unknown output. From multiplication of two
complex numbers follows that



222
, , 2 mod.
x
yxyxy p (2.3)
Hence (2.2) and (2.3) imply that x and y satisfy


22
mod ;
x
ypc

 (2.4)
and 2 mod .
x
ypd (2.5)

134 B. S. VERKHOVSKY
As in the case of real integers, not every Gaussian
modulo p has a square root.
Definition 2: If a square root of (c, d) exists, then (c, d)
is called a Gaussian quadratic residue (GQR); otherwise
(c, d) is called a Gaussian quadratic non-residue
(GQNR).
2.3. Gaussian Integers Modulo Non-Blum
Prime p
If a prime p satisfies pmod4 = 3, then it is called a Blum
prime. Using Euler criterion, it is easy to verify that, if
pmod4 = 1, then is a QR modulo p [6]. Theref ore
1p

mod

11 pp  is a real integer.
Corollary 1: All Gaussians modulo a non-Blum prime
are real integers.
In this paper, only Blum prime moduli are considered.
Example 1: If p = {41, 53, 61}, then the correspond-
ing

1 mod ip


(2.2





c

are equal {9, 23, 11}. Cor-
ollary1 implies that for every c and d
i.e., (c, d) is a real integer.


mod6111 ,cidc d
2.4. Properties of Square Roots
Proposition 1: Let

, ab ). Then
the following properties hold:
 
2 mod , p cd
1) ; and
 
2
,mod ,pabpcpd
 
2
, mod , ap bpcp d; (2.6)
2) If , then
 
2
,0 mod,0wp
2
 
0, mod , 0wppc ; (2.7)
3) If pmod4 = 3, then an integer c is either a quadratic
residue (QR) with two real roots or a quadratic non-
residue (QNR). In the latter case (c, 0) is a GQR with two
imaginary roots. In other words, if c is a QR, then p-c is
a GQR and vice verse: if modcpa, then

mod 0, pc ppa

; (2.8)
4) For every Blum prime p there exist exactly

212p GQRs and

212p GQNRs;
5) If
 
,mod ,cdp ab

, then
 
, mod , pcdp ba

(2.9)
and
 
, mod , cp dpp ab


; (2.10)
6) A GQR (0, d) has two roots

,
x
y such that

22
mod

x
yp. (2.11)
These properties yield from the identity




222
, , 2modaba babp

(2.12)
and from Euler criterion of quadratic residu osity [6].
Remark 1: As it is demonstrated in Section 5, the 6th
property can be applied in search for a Gaussian genera-
tor.
2.5. Symbolic Rules
Many properties including (2.6)-(2.11) are easier to ver-
ify if we define a generalization of Legendre symbol [7]
for Gaussian integers.
Definition 3:




1, if (, ) is GQR mod
,
1, if (, ) is GQ N R mod.
cd n
cd
cd n n (2.13)
Proposition 2: If pmod4 = 3, and qmod4 = 3, then the
following properties hold:
1)






,,, ,cde fcde f
pp




p



; (2.14)
2)




,00, 1 cd
pp
 


 
 
[8]; (2.15)
3)




,,,cdcd cd
pqp q







. (2.16)
3. Extraction of Square Roots
3.1. Algorithm
The following algorithm describes how to extract Gaus-
sian square roots of (c, d) if it is a GQR modulo Blum
prime p.
1) Compute


:1Lp4;
c
(3.1)
if c > 0 and d = 0, then assign
:mod
L
Ec p; (3.2)
2) if 2mod Ep

, then else
 
,:, 0xy E
L


 

, :0, 1;
x
yE (3.3)
3) if c = 0, d > 0, then assign

1
:12 mo
L
Edp p




d;
(3.4)
4) if




2112mod Edp p 
 , then


, :,

x
yEE (3.5)
else

 
, :, ;
x
ypEE  (3.6)

B. S. VERKHOVSKY
135
d;
5) if c > 0 and d > 0, then

22
: mo Ncd p (3.7)


is a norm of , ;, Ncdcd

N
;
6) assign
: mod
L
A
Np (3.8)
if
2 mod ,
A
pN (3.9)
then (c, d) does not have a square root; {end of algo-
rithm}; else

:12 mod
g
Ac pp 

;
:mod
L
Eg p;
g
(3.10)
7) if , then
2mod Ep: mod
x
Ep;

1
: m yEdAcp

od;
g
(3.11)
8) if , then
2 mod Epp

1
: mod ; : mod ;
x
EdcAp yEp
 (3.12)
Output two solutions

,

x
y; {end of algorithm}.
Remark 2: System of Equations (2.4)-(2.5) has a
closed-form solution: if A is pre-computed in (3.8), then

12 mod ;

x
cAp p  (3.13)

12 mod ,

y
cApp  (3.14)
where computation of x and y in (3.13)-(3.14) requires
three exponentiations (3.20). In addition, these square
roots in (3.8), (3.13) and (3.14) have four (

) signs.
Hence, there are sixteen combinations of these signs.
However, not all combinations of these signs are feasible.
Feasibility of these combinations is analyzed in Subsec-
tion 3.3.
3.2. Algorithm Validation
In the following discussion it is assumed that both com-
ponents in (c, d) are strictly positive integers. Since the
left sides of both Equations (2.4) and (2.5) are homoge-
neous, consider :yxu;
;
(3.15)
where a positive integer u is unknown.
Then Equations (2.4) and (2.5) imply that

22
1 mod
x
upc
.
(3.16)
and
2
2 mod
x
upd
.
Hence, od, (3.19)
w
(3.17)
Then (3.16) and (3.17) imply that

2
1 mod 2du pcu (3.18)

1
: m udAcp


here


14
22 22
:.
p
Acdcd

 (3.20)
Therefore, (3.18)-(3.19) imply that


11
: mod .udAc p

 (3.21)
Indeed,



1222
1 mod uu dAcp



.
Then




2
x
12 mod ,Ac pp 

(3.22)
whic yields (3.13), and (3.15) implies (3.h finally14). In
addition, algorithm (3.1)-(3.12) requires only two extrac-
tions of the square roots.
Example 2: Let
 
,xy:6,1 mod 11.
= 3 and A = 9 (3.8). Compute N = 4, L
Since 2mod 4
A
pN

, then (6,1) is GQR.
Compu 3
mod 28p
te g = 2,
:
L
Eg

.
Since 2modE 9ppg

, then y:8 and 


mod11 9.cA
1
:d

xE


Another solution is




od 11 2,3. 9,8 m
3.3. Feasibility Analysis
s noticed in Remark3, there are combinations A4 216
of signs (

) in (3.13)-(3.14). I to determine
which of these combinations are feasible, rewrite Equa-
tions (3.13)-(3. 14 ) in generic form:

n order
12 mod ;vqrAcp p (3.23)
and

12 mod .zstAcp p (3.24)
Then variables v and z satisfy (2.4)-(2.5) if a
va

(3.25)
As a result, there are only four pairs o
m
nd only if
riables q, r, s and t satisfy equations:

22
1 mod qs rtqsp.
f variables that
ay satisfy (2.4) and (2.5):


1
12 mod d p


and (3.26)
uu Ac
 
1
34 mod .uu pAcdp


Then either 

1,22 mod
1
Ac p and
x

1
1,21,2 1,22 mod ;yxu Acp


 3.27)
or
 (

1
3,4 2 mod
x
Ac p

  and

1
3,43,4 3,42 mod yxu Acp

 . (3.28)
Thus, if (c, d) is a GQR, only two of these four
m prime and h be a posi-
tiv
pairs are
solutions of (2.4) and (2.5). An alternative extractor of
square roots is provided in [8].
Proposition 3: Let p be a Blu
e integer co-prime with p. Then from Euler criterion

136 B. S. VERKHOVSKY
of quadratic residuosity [6] either h or ph, but not
both, is a QR modulo p. Indeed, since

1p2 is an
odd integer, then





12
12p
h
 mod .
p
php

  (3.29)
Proposition 4: Let 2
A
N, (3.8), and le
z t z := c or := d; if


A
z is a en

QR, th
A
z is also a QR;
else if

A
z is a QNR, then


A
z is also QNR.
Indeed, frler criterion [6] om Eu
 
 
 
1
11pp
22
2
22
1
21
2
1
21
2
1 mod if
1mod if
p
pp
pp
AzAzA z
dd pzc
cc pzd




 


 

(3.30)
Thus






12 12
mod
pp
A
zAz

 p (3.31)
2: If
, (3.32)
then
Corollary
 
Ac
 

1/2
1
2mod 1
pp 


11
,
x
y and

22
,
x
y are square roots else

33
,

x
y

44
, and
x
yare roots of (c, d).
osition uare root of (c, d) modulo p
are squ
qProp 5: A s exists
if
. PKC Based on Square Roots
.1. System Design
Step 1: A pair of large and distinct Blum primes p and
q q are private
ke 3: Every user pre-computes
and only if there exists a square root of norm N of (c, d)
[9] and algorithm (3.1)-(3.12) is a constructive procedure
for computing it.
4
4
are independently selected by each user.
Step 2: n: = pq; n is a public key; p and
ys;
Step 1 :mod
M
p

; q
an
.2. Encryption
Step 4: A sender (called Alice) divides plaintext into
bl
nd an arra a
receiver (called Bob): Alice compu
(4.1)
d 1 :mod Wqp

.
4
ocks and represents each block in numeric form as a
positive integer m < n; pairs of integers 12
, ; ;mm 
212
, ;
ii
mm
 are treated as Gaussians

212
, ; 1, 2,
ii
m i


, :
ii
ab 
Step 5:

m
Suppose Alice wants to sey


112 2
   ,; ,; ; ,
kk
ab abab of Gaussians to
tes ciphertexts

2
, :, mod ;cdabn
11 11
 


11
, :, , m
ii ii
cdab abod ;n (4.2)
and transmits and

11
,cd


22
,
ik ik
cd
 over open
channels to Bob
.
.3. Decryption
Step 6: Using the algorithm (3.1)-(3.12) Bob finds
sq
4
uare roots


11
,uw of


11
,cd modulo p and then
modulo q;
Step 7: Bob finds square root of

11
,uw


11
,cd
ainderm
mark 3: An efficient implementation of CRT is
pr computes a multiplicative inverse of
odulo composite n by using the Rem
Theorem (CRT) and pre-computed M and W in Step 3,
[1];
Re
Chinese
ovided in [9];
Step 8: Bob


11
,w [5]:
1
u
 


1
22
111111
,, mod uwun wuwn

; (4.3)
Step 9:

(4.4)
Step 10:
 
1
11
, , , mod .
ii ii
abcduwn






111 1
, , ;ab uw (4.5)
Remark 4: In (4.2)


11
,ab is used to hide the plain-
texts


22
,
ik ik
ab
 from intruder. Since the com-
putatiative inverse (4.3) is computation-
ally simpler than extraction of square root of
an
on of multiplic


,cd ,
therefore this way of information hiding signifi
reduces average complexity of decryption per block of
the ciphertext.
cantly
4.4. Advantages of PKC Based on Gaussian
urrently a “tail” of 64 bits is added to every block of a
Integers
C
plaintext P in order to resolve ambiguity of Rabin de-
cryption [10]. In the PKC based on square-roots of Gaus-
sian integers for the same level of assurance we need to
add totally 64 bits to every Gaussian integer (rather than
to every real integer as in [10]). The cryptosystem pro-
posed in this paper requires

32Pn plaintext blocks
while the PKC in [10] requires
 
64Pn blocks.
5. Ambiguity in Recovery of Original
method of “tails” introduced in [10] does not always
Information and Its Elimination
A
work. Consider a plaintext (a, b) = (275, 346) and p =
6221. Using tails by repeating the last rightmost digits,
we re-write








, :AB10,,mod102755,3466 .abab 
The direct computation shows that

B. S. VERKHOVSKY
137

Hence, on the decryption stage, if Bob gets (2755,
34
(uvw

22
2755,3466 3466,2755

mod6221
66) and (3466, 2755) , there is no way to decide which
of two Gaussians is authentic. In general, for p = 6221
there are several hundreds Gaussians that have this prop-
erty, which creates ambiguity. Indeed, consider a Gaus-
sian with three-digit components (uvw, xyz), where u,
v, ···, z are their decimal digits; let uv + xy = 61 and
11.wz Then with one-digit tails we have
w, xyzz). There are 480 Gaussians that h
property described above.
The way to resolve the a
ave the
mbiguity is to label the Gaus-
sians asymmetrically: we use prefix of the first compo-
nent to create a tail [11]. It seems that this approach does
not completely eliminate ambiguity. For instance, if
p = 6221 and (a,b) = (474,147), then
(A,B) = (4744, 1477). Yet, it is obvious
is not acceptable as genuine. More examples are pro-
vided in Table 1.
Although the am
that (1477, 4744)
biguity remains unresolved if
(5.1)
the probability of such occurrence
. Gaussian Generators
Definition 4: An integer G = (a, b) is a Gaussian gen-
er
 
,,,a buvuxyx
is extremely minute
for large p applied in public key cryptography.
6
ator modulo p if 21mp
is the smallest integer for
which holds that


1, 0Gp.
Definition 5: Amod
m
n integer (a, b) is called a Gaussian
generator if

2
, 1ordabp

 (6.1)
Proposition 6: If


  
d , 0or0, ,pef (6.2)
then (a, b) is not a generator [5]. om observations that
14
, mo
p
ab 
Indeed, Equation (6.2) follows fr
 

2
, 1414orda bordepp
(6.3)
and that
Table 1. Resolution of ambiguity.
p B, A) (a, b) (A, B) (
6221 (4) (474,147744,1477) rejected
6277 (373,254) (3733,2544) rejected
6277 (474,153) (4744,1533) rejected
7477 (232,515) (2322,5155)



 



2
2
, bord 0,4
22, 014
12
d a
ord pfp
p
1fpor



 


(6.4)
Proposition 7: Let k > 1 be the smallest integer, for
w
. (6.5)
If
hich holds

,
k
ab
 
mod , pff


14kp , then (a, b) is
wise, if not a generator other-


14 and kp


p
4
41ord pf,

 (6.6)
then (a, b) is a generator. Indeed, (6.6) follows from ob-
servation that






4
2
, 4414
111.
orda bordpfp
pp p

  (6.7)
Remark 5: If



12
,mod ,
p
abp f
0, then (a, b)
is 1) / 4 is a prime,
not a generator.
Corollary 3: If (p +



14
,mod ,
p
abp f


,f
and


4
41ord fp


lo prime p. , then (a, b) is a generator
sed on extraction of square roots
modu
. Conclusion 7
ryptosystem baC
modulo composite integer n = pq of complex numbers
with integer components {called Gaussian integers} is
introduced and its validity is demonstrated. Security of
such cryptosystem is based on complexity of root extrac-
tion if large integer factors p and q of n are not known to
an intruder. The algorithm provided in this paper requires


Ologp time complexity for decryption. It is also de-
w to use properties of Gaussians in order to
find generators that can become instrumental in the de-
sign of various cryptosystem. When this paper has been
in typesetting process, Alexey Koval has suggested a
constructive idea [12] that eliminates the ambiguity in
case (5.1).
. Acknow
scribed ho
8ledgements
R. Rubino, M. Linderman,
Disquisitiones Arithmeticae,” English Trans-
express my appreciation toI
E. A. Verkhovsky, M. Sikorski and anonymous referees
for suggestions that improved this paper.
. References
(5155,2322)
9743 (545,428) (5455,4288) rejected
9743 (727,246) (7277,2466) rejected
9
[1] C. F. Gauss, “

B. S. VERKHOVSKY
138
lation, Springer-Verlag, New York, 1985.
s of Gau
main of Gaussian In-
mputers,” Doklady Aka-
[2] A. N. El-Kassar, R. A. Haraty, Y. A. Awad and N. C.
Debnath, “Modified RSA in the Domainssian
Integers and Polynomials over Finite Fields,” Proceed-
ings of the ISCA 18th International Conference on Com-
puter Applications in Industry and Engineering, Honolulu,
9-11 November 2005, pp. 298-303.
[3] A. El-Kassar, M. Rizk, N. Mirza and Y. Awad, “ElGamal
Public-Key Cryptosystem in the Do
tegers,” International Journal of Applied Mathematics,
Vol. 7, No. 4, 2001, pp. 405-412.
[4] A. Karatsuba and Y. Ofman, “Multiplication of Many-
Digital Numbers by Automatic Co
demii Nauk SSSR, Vol. 145, No. 2, 1962, pp. 293-294.
[5] B. Verkhovsky, “Enhanced Euclid Algorithm for Modu-
lar Multiplicative Inverse and Its Cryptographic Applica-
tion,” International Journal of Communications, Network
and System Sciences, Vol. 3, No. 12, 2010, pp. 901-906.
doi:10.4236/ijcns.2010.312123
[6] L. Euler, “Vollstandige Anleitung zur Algebra,” Reclam
Publishing House, Leipzig, 1941, pp. 1-527.
[7] F. Lemmermeyer, “Reciprocity Laws: From Euler to Ei-
Based on
ystem,” IRE Transac-
senstein,” Springer-Verlag, New York, 2000.
[8] B. Verkhovsky and A. Koval, “Cryptosystem
Extraction of Square Roots of Complex Integers,” In: S.
Latifi, Ed., Proceedings of 5th International Conference
on Information Technology: New Generations, Las Vegas,
7-9 April 2008, pp. 1190-1191.
[9] H. Garner, “The Residue Number S
tions on Electronic Computers, Vol. EC-8, No. 2, 1959,
pp. 140-147. doi:10.1109/TEC.1959.5219515
[10] M. Rabin, “Digitized Signatures and Public-Key Func-
Root Extractors of Gaussian In-
arch 2011.
tions as Intractable as Factorization,” MIT/LCS Technical
Report, TR-212, 1979.
[11] B. Verkhovsky, “Cubic
tegers and Their Application in Fast Encryption for
Time-Constrained Secure Communication,” to appear in
International Journal of Communications, Network and
System Sciences, Vol. 4, No. 4, 2011.
[12] A. Koval, Private Communication, 9 M