Int. J. Communications, Network and System Sciences, 2011, 4, 133138 doi:10.4236/ijcns.2011.43016 Published Online March 2011 (http://www.SciRP.org/journal/ijcns) Copyright © 2011 SciRes. 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 Email: verb73@gmail.com 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, SquareRoot Extraction, Gaussian Integers, Gaussian Generator, Multiplicative Inverse, Square Root Algorithm, Information Hiding, Ambiguity of Recovery 1. Introduction In recent publications publickey 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 npqkk pk q 2. Gaussian Integers 2.1. Arithmetic of Gaussian Integers Modulo reduction: , modmod,modabn anbn; Multiplication: Let ; , :,,mod:; :; habcd nAacBbd C := a + c; D := b + d; then : mod 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 , ypcd (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. yxyxy p (2.3) Hence (2.2) and (2.3) imply that x and y satisfy 22 mod ; ypc (2.4) and 2 mod . ypd (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 nonresidue (GQNR). 2.3. Gaussian Integers Modulo NonBlum 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 nonBlum 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 pc is a GQR and vice verse: if modcpa, 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 , y such that 22 mod yp. (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 :1Lp4; 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; yE (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 , :, yEE (3.5) else , :, ; ypEE (3.6) Copyright © 2011 SciRes. IJCNS
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 Np (3.8) if 2 mod , pN (3.9) then (c, d) does not have a square root; {end of algo rithm}; else :12 mod Ac pp ; :mod L Eg p; g (3.10) 7) if , then 2mod Ep: mod Ep; 1 : m yEdAcp od; g (3.11) 8) if , then 2 mod Epp 1 : mod ; : mod ; EdcAp yEp (3.12) Output two solutions , y; {end of algorithm}. Remark 2: System of Equations (2.4)(2.5) has a closedform solution: if A is precomputed in (3.8), then 12 mod ; cAp p (3.13) 12 mod , 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 upc . (3.16) and 2 2 mod upd . 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 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 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 1 1,21,2 1,22 mod ;yxu Acp 3.27) or ( 1 3,4 2 mod 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 coprime with p. Then from Euler criterion Copyright © 2011 SciRes. IJCNS
136 B. S. VERKHOVSKY of quadratic residuosity [6] either h or ph, but not both, is a QR modulo p. Indeed, since 1p2 is an odd integer, then 12 12p h mod . p php (3.29) Proposition 4: Let 2 N, (3.8), and le z t z := c or := d; if z is a en QR, th z is also a QR; else if z is a QNR, then 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 zAz p (3.31) 2: If , (3.32) then Corollary Ac 1/2 1 2mod 1 pp 11 , y and 22 , y are square roots else 33 , y 44 , and 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 precomputes 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 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 abod ;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 precomputed 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 squareroots 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 rewrite , :AB10,,mod102755,3466 .abab The direct computation shows that Copyright © 2011 SciRes. IJCNS
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 threedigit components (uvw, xyz), where u, v, ···, z are their decimal digits; let uv + xy = 61 and 11.wz Then with onedigit 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, “ Copyright © 2011 SciRes. IJCNS
B. S. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 138 lation, SpringerVerlag, New York, 1985. s of Gau main of Gaussian In mputers,” Doklady Aka [2] A. N. ElKassar, 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, 911 November 2005, pp. 298303. [3] A. ElKassar, M. Rizk, N. Mirza and Y. Awad, “ElGamal PublicKey Cryptosystem in the Do tegers,” International Journal of Applied Mathematics, Vol. 7, No. 4, 2001, pp. 405412. [4] A. Karatsuba and Y. Ofman, “Multiplication of Many Digital Numbers by Automatic Co demii Nauk SSSR, Vol. 145, No. 2, 1962, pp. 293294. [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. 901906. doi:10.4236/ijcns.2010.312123 [6] L. Euler, “Vollstandige Anleitung zur Algebra,” Reclam Publishing House, Leipzig, 1941, pp. 1527. [7] F. Lemmermeyer, “Reciprocity Laws: From Euler to Ei Based on ystem,” IRE Transac senstein,” SpringerVerlag, 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, 79 April 2008, pp. 11901191. [9] H. Garner, “The Residue Number S tions on Electronic Computers, Vol. EC8, No. 2, 1959, pp. 140147. doi:10.1109/TEC.1959.5219515 [10] M. Rabin, “Digitized Signatures and PublicKey Func Root Extractors of Gaussian In arch 2011. tions as Intractable as Factorization,” MIT/LCS Technical Report, TR212, 1979. [11] B. Verkhovsky, “Cubic tegers and Their Application in Fast Encryption for TimeConstrained 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
