 Int. J. Communications, Network and System Sciences, 2011, 4, 197-204 doi:10.4236/ijcns.2011.44024 Published Online April 2011 (http://www.SciRP.org/journal/ijcns) Copyright © 2011 SciRes. IJCNS Cubic Root Extractors of Gaussian Integers and Their Application in Fast Encryption for Time-Constrained Secure Communication Boris Verkhovsky Computer Science Department, New Jersey Institute of Technology, Newark, USA E-mail: verb73@gmail.com Received March 2, 2011; revised April 12, 2011; accepted April 15, 2011 Abstract There are settings where encryption must be performed by a sender under a time constraint. This paper de-scribes an encryption/decryption algorithm based on modular arithmetic of complex integers called Gaus-sians. It is shown how cubic extractors operate and how to find all cubic roots of the Gaussian. All valida-tions (proofs) are provided in the Appendix. Detailed numeric illustrations explain how to use the method of digital isotopes to avoid ambiguity in recovery of the original plaintext by the receiver. Keywords: Cryptographic Protocol, Secure Communication, Time-Constrained Encryption, Cubic Root Extractor, Gaussian Integers, Modular Arithmetic, Prefix/Suffix Positioning, Digital Isotope, Quadratic Residue, Jacoby Symbol 1. Introduction This paper describes a cryptographic algorithm based on the extraction of cubic roots from complex numbers a + bi with integer components a and b. Such complex integers are called Gaussian integers (Gaussians, for short) . Let’s denote and , where N is called a norm of (a, b). In modular arithmetic based on Gaussians, if p is a prime and , then for every integer a and b holds an equivalent of the Fermat identity : , :aba bi 2:Nabmod 0Np21 21,mod1,0pab p. (1) This means that the cycles in Gaussian modular arith-metic have order , while the cycles in modular arithmetic based on real integers have order 2pp. Ap-plication of Gaussians for ElGamal cryptosystem is con-sidered in ; and the RSA digital signature is described in . Public key cryptography based on cubic roots of real integers is provided in  and in . Definition1: A Gaussian integer (x, y) is called the cu-bic root of (a, b) modulo integer n, and defined as 3,modab n, if 3,,modxyabn. (2) Proposition1: If p is a prime, and mod12 1p13:,mod 1,0pVab p1, (3) then there exists a cubic root of (a, b) modulo p. Proposition2: If , then for every integer a and b there exists an unique cubic root of (a, b) modulo p. mod12 5pProposition3: If and 2mod 91p1:mod1,0pWV p1, (4) then there exists a cubic root of (a, b) modulo prime p. Remark1: Here are examples, where 2mod 91p: p = 17, 19, 53, 71, 89, 107, 109, 179, 197, 199, 269, 271. The following two algorithms are constructive proofs of these propositions. 2. Algorithm-1 Step 1.1: Compute 213:, modpWab p; (5) Step 2.1: if 1,0W, then cubic root of (a, b) mod-ulo p does not exist; Step 3.1: Compute :mod9sp ; (6) {there are six possibilities}; = 1;2;4s 198 B. VERKHOVSKY Step 4.1: if , then 1s:4ms, (7) otherwise apply Algorithm-2; Step 5.1: Compute 2:13pEmp9, (8) {where m = 1 or 2, see Table 1}; Step 6.1: Compute ,: ,modpExyabp4. (9) Example 1: Let p = 23; ; ,19,ab 1762(23 1)/3:(19, 4)(19, 4)mod 23(1,0);W :59pE hence (19,4) is a cubic residue. ;   593,:19,419,4mod 2316,16.xy  Indeed,  316,16mod 2319, 4. It is easy to verify that (5, 2) and (2, 5) are also cubic roots of (19, 4). Hence, algo-rithm (5)-(9) computes only one of three cubic roots of (a, b). How to compute the two other cubic roots is dis-cussed in sections 5 and A3. 3. Algorithm-2 If q mod 12 = 5, then a cubic root exists for every (a, b); and each Gaussian has a unique cubic root. The follow-ing algorithm computes such a cubic root (1). Step 1.2: Compute cubic extractor :2 13qEq ; Step 2.2: Compute (10) :, modqERab qStep 3.2: Output (x, y):=R. Three examples are provided in Table 2. 4. Multiplicity of Cubic Roots Proposition 4: Suppose are three cubic 12, and CC C3 Table 1.Cubic extractors pE and m. p 7 11 13 23 pE; m 5; 2 27; 2 19; 1 59; 1 p 29 31 41 43 pE; m 187; 2 107; 1 187; 1 411; 2 Table 2. Illustrations of cubic root extraction; q mod 12 = 5. q; (a, b) 53; (19, 13) 89; (17, 77) 269; (19, 73) qE 35 59 179 (x, y) (45, 28) (6, 85) (112, 124) roots of L:= (a, b) modulo p, each satisfying the equation 3mod 0CL p; (11) then for every i = 1, 2, 3 the following identities hold: 3modiCL p. (12) 123123mod0; mod ;CCC pCC CpL  12 1323mod 0.CCCC CCp (13) 2mod 0ij kCC Cp, (14) where {i, j, k} is every permutation of {1, 2, 3}. 2mod 0.ij ijCC CCp (15) 5. Cubic Roots of (1, 0) and Gaussians In order to find two other roots of (a, b), consider cubic roots of unity: 3,: 1,0moduw n. (16) If (x, y) is a cubic root of (a, b), then ,,uwxy and 2,,moduw xyp are also its cubic roots modulo n. Proposition 5: If p is a Blum prime, then either 3or3 modulo p exists, but not both; if 3 mod p exists, then 12mod;and 132mod.up pwpp (17) If 3modp exists, then 13modu p. (18) Proof is provided in the Appendix. 6. Existence of 3 modor3modpp Jacoby symbols [8,9] analyze whether a specified integer is quadratic residue (QR). If p is a Blum prime, then 231/83mod311 332or 11.3pp      (19) Therefore, if p mod 12 = 11, then 3 is QR. Seven ex-amples are listed in Table 3. Table 3. 3modp if p mod 12 = 11. p 11 23 47 59 71 83 107 3 5 16 12 48 43 70 89 Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY 199,;mod;pYet, if p mod 12 = 7, then –3 is QR. (20) 7. Properties of Gaussian Cubes Consider  322 22,:,3, 3modtvuwu uwwuwp (21) Property 1: 322 22,3,3uwuuwwu wtv (22) Property 2: 322 22,3,3(,)wuw wuuwuvtp (23) Property 3: If u + w = p, then  333,, mo1d1,uuwwu . (24) 8. Cryptographic Protocol System design (each user’s actions): Step 1.3: Selects two large distinct primes p and q, where p mod 12 = 11; ; and q mod 12 = 5; 2mod 91pStep 2.3: Computes n = pq; {n is user’s public key; p and q are his private keys}; Step 3.3: Finds cubic root (u, w) of (1, 0) modulo p: 12mod;3mod.uppwu p Step 4.3: Pre-computes 11:mod; :modmod;PqqpQ ppqn Protocol implementation: Suppose a sender (Sam) wants to securely transmit a plaintext G to receiver (Re-gina); Sam divides G into an array of blocks  112 2,; ,;; , ;kkghghgh and kk in such a way that every gnhn; Encryption {Sam’s actions}: Step 5.3: He gets Regina’s public key n; computes ciphertext 3,:, modab ghn; and sends (a, b) to her; Decryption {Regina’s actions}: Step 6.3: She, using her private keys p and q, extracts cubic roots  331:,mod; and :,mod;MabpR abq Step 7.3: She computes  21 32:,mod ; and :,mod ;MMuw pMMuw p Step 8.3: {Using Chinese Remainder Theorem , Re- gina computes all 3 roots of (a, b) 3:,modDabn}: for k = 1,2,3 :mkkDMPRQodn; Step 9.3: {The original plaintext is recovered via dig-ital isotopes-see sections 10 and 11}: D = G. 9. Efficient Encryption of Gaussians Squaring of a Gaussian requires two multiplications of real integers (MoRI); and multiplication of two Gaus-sians requires three MoRI . Therefore, the cubic power of Gaussian requires five MoRI. Yet, encryption 33223,:,3 ,3modabghgghgh hp in Step 5.3 requires only four MoRI: 221212 32 4133 44:mod;:mod;:;:2;:2:mod;:mod;PgpPh pSPP AS P A S PPgA pPhAp ; {there are no 1A and 2A}; where the doublings are achieved by binary shifting; then 12 and P22P34,P P,:ab. 10. Asymmetric Tagging of Digital Isotopes In cryptographic algorithms based on extraction of square roots of real integers  or Gaussians  there are four pairs of solutions, and only one of them is the original plaintext. To distinguish the original solution from the other three, the authors use methods of tails, which is an analogue of using isotopes to tag various chemical com-ponents. If the digital isotopes repeat r rightmost digits in each component of plaintext (g, h), then the probability of erroneous recovery of the “plaintext” is of order 2110r. For instance, if the length of isotope r = 3, then the probability of error is one in one million. As shown below, a more elaborate strategy must be used to avoid ambiguity in the recovery of the original plaintext. Definition 2: If there exist Gaussians with distinct components x and y such that 33,,modxyyx p, (25) then such cubic roots are called Gaussian twins (or CT, for short). Proposition 6: If the square root of 3 modulo prime p exists, then there exists the CT; {see Table4 for examples}. Table 4. Examples of cubic roots twins (CT) for p = 83. (a, b) (27, 56) (31, 52)(26, 57) (2, 81) (78, 5)(53, 30)3,ab (22, 76);(76, 22)(15, 24);(24, 15)(46, 8); (8, 46) (77, 7); (7, 77) (8, 5);(5, 8) (1, 11);(11, 1) Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY 200 0Proof: since , then (25) implies the following relationships: mod 0xy p  222222 22221, 1,,,,0;,2 0,,20, 2mod0;.., 2mod0.x yxyxy yxyxxy xyxyy x xyxyxypiex yxyp    (26) Let y := Txmod p, then i.e., which implies that 2212modxTTp , 0;241modTT p23modTp . For instance, if p = 83, then 370, i.e., . 270mod8311 or 68TIf x = 1, then y = {11 or 68}; hence ; and .  331,6868,1 mod8373,10331,1111,1mod 8353,30It means that 353,30mod83 equals either 1,11 or . Yet, if in both components the rightmost digit is “1”, it is not clear whether the original plaintext is (0, 1) or (1, 0). For every p mod 12 = 11 there exist CTs that satisfy (25) {examples are provided in Table 4). 11,141p11. Numeric Illustration Algorithm in a nutshell System design: Let Regina’s p = 227 and q = 1109, where , p mod 12 = 11; and q mod 12 = 5; she computes n = pq = 251,743; P and Q: 2mod 941p1111:mod=11091109mod 2271109 96106464;:=mod227227mod1109227 640145280;Pqq pQpp q and a cubic root (u w) of (1,0) modulo p: 22712 mod113up ; 5731133mod 22725;wu  Remark 2: ; 2,,moduwup wp 3, 25mod 2271, 0{indeed, ; 113 2and 113,25mod 227113,202};:227 mod 9 2s; :42 2m; and Gaussian cubic extractor {Step 5. 1} 2: 2 2271 3911451pE; finally, Regina pre-computes another cubic extractor :2 13739qEq . Encryption: Suppose the sender (Sam) wants to se-curely transmit message G = (1941, 2487) to Regina with two-digit isotopes: Z := 100G + Gmod100 = (194141, 248787). In this case the probability of erroneous recovery of the original message will not exceed 1/10,000, i.e., it equals 0.01%. Sam computes ciphertext 3,:mod 251743227258,195067ab Z Decryption: Regina computes  11451111451:227258,195067mod 227 31,74mod22774,78M and two other cubic roots:  21:,74,78113,2556, 222;MMuw 32:,56,222113,2597,154;MMuw and then unique cubic root R modulo q   739: ,mod227258,195067 66,371mod1109.qERab q Using the Chinese Remainder Theorem , Regina computes (28): System design: Select p, q; Compute n, P, Q, u, w, s, m, , pqEncryption: Create plaintext Z with isotopes; com-pute ciphertext (a, b); EE; Decryption: R; RQ; 12;;11,11091109mod 227 227227mod1109mod251743 106464145280mod251743;kkkxy MRMR  3MMM. until she detects isotopes  11,106464145280 66,37110646474,7822246, 25878mod96549,274294;where251743xy Mnn  22,10646422246,25878mod10646456,22222246, 25878mod1941, 2487.xy Mnn 41 87 Therefore, Regina recovers the original Gaussian block of information; and it is not necessary to compute 3,xy. 12. Optimized Recovery of Information Let 12 12, ; , kkkMMM RRR; Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY 201then 112 2;kk kkxMP RQyMP RQ . 11112, MMM is computed by cubic root extraction; if the isotopes in Z are detected, then the original infor-mation is recovered; otherwise Regina needs to compute four components of two other cubic roots of (a, b): 211121112 1112, (,) ,MMMuwMuMwMwMu ; (27) 3111211 121112, ,,MMMuwMuMwMwMu. (28) Yet, to minimize computational burden, instead of computing 2 and 3MM, she finds 112:NMwP; (29) and then computes 211111xMuP RQN. (30) If the isotopes are detected, then she computes , otherwise Regina computes 2y32 111 111232 and .xx NMuPRQMwPy (31) 13. Elimination of Ambiguity in Recovery of Original Information The probability of erroneous recovery can be decreased if, instead of repeating r rightmost digits of g and h, the following procedure is applied: 1) Consider r leftmost digits (prefix rP) of the first component g in plaintext (g, h) and repeat it as its digital isotope; 2) Consider r rightmost digits (suffix rS) of the sec-ond component h of plaintext (g, h) and repeat it as its digital isotope. Example 2: if (g, h) = (31415926, 27182845) and r = 2, then (3131415926, 2718284545). NB: if n is t-digits long and the number of digits in g is smaller than t, then the prefix . To avoid ambiguity, the sender must attach both digital isotopes r and r as suffixes. Below is a simple mne-monic/schematic rule for constructing the digital isotopes: 00 0rPP Spriority, cocktailrity, cock.prio tailprio tail Remark 3: Therefore, there can be two types of cubic roots with isotopes: (PUP, VSS) and (USS, PVP). Only the former one is authentic. Hence, a receiver (Regina) searches for the cubic root with isotopes in format (PUP, VSS), where P and S are prefix and suffix respectively. In this case (PU, VS) is acceptable as the genuine plaintext. Example 3: if t = 8; r = 2; and (g, h) = (00415926, 07182845), then 6822 2(mod10 )10,:(mod10 )10mod10 ) 00415926,07182845gg gZhh h00 45 14. Second Numeric Illustration System design: Let p = 227; q = 1109, n = pq = 251,743; P = 106464; Q = 145280; (u, w) = (113,25); 2s; 2m; 11451;pE 739qE. Encryption: Plaintext G = (1756, 2011); plaintext with isotopes Z := (175617, 201111); and ciphertext (a,b) = (57971, 209989); Decryption: R = (395, 382); M := (202, 137); 1mod239939;QRn  112: 115336NMwP196xMuPQRN; 21111688 ; since there is no isotope in 2x, then 33,xy is the original Gaussian. Indeed, 32121756xx N17 . 15. Algorithm Analysis The cryptographic algorithm described above is neither a generalization nor a special case of the RSA protocol . First of all, the following identity holds: 211,mod1,0pqab n 1. (32) In the RSA algorithm, if z is the length of group cycle , then each user selects a public key e that is co-prime with z. In the proposed algorithm the length of cycle c is equal 2:1cp q1. (33) Therefore in the RSA extension it would have been necessary to compute a multiplicative inverse d of e modulo c. Yet, in the algorithm described above the en-cryption key e = 3. Hence, the decryption key d cannot be computed as a modular multiplicative inverse, since gcd 3,3z, which implies that such an inverse does not exist . 16. Communication Speed-Up Suppose it is necessary to transmit an H digit-long plain-Copyright © 2011 SciRes. IJCNS B. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 202 text, where the size of each block must not exceed six-teen digits; in addition, suppose that we want to ensure that the probability of erroneous recovery does not ex-ceed one in one million. There are two options: Option 1 is to select the size of each block equal to ten digits and the size of each tail equal to six digits; Option 2 is to select the size of each block equal to thirteen dig-its and the size of each tail equal to three digits. In the 1st option we will treat each block individually as a real integer; which implies that we need to transmit H/10 real integers. In the 2nd option we will treat a pair of blocks as a Gaussian; which implies that we need to transmit H/26 Gaussians, i.e., H/13 real integers. There-fore, the first option requires 13/10 = 1.3 times more bandwidth, than the second option. In other words, the bandwidth can be reduced by 30% if Gaussian integers are considered. 17. Possible Applications and Conclusions The proposed cryptosystem has significant specifics: the encryption is substantially faster than the decryption. There are certain settings where the sender has limited time to transmit the message: visual images or video, and receiver does not have such restriction. For instance, the sender is a system that urgently needs to transmit infor-mation prior to either collision with a target or before it is destroyed by a hostile action . Another example is if the sender (say, an interplanetary or interstellar space station) detects an impending collision with an asteroid and is programmed to report about such collision and transmit visual and other details about the asteroid. In this case it is paramount to ensure the reliability of message delivery [15,16]. Yet another example is of a security camera that has detected an imminent explosion and is pre-designed to report the situation (audio, pic-tures and/or video)  prior to its own destruction from the explosion. 18. Acknowledgements I express my appreciation to J. Jones, and R. Rubino for corrections, and to E. A. Verkhovsky as well as anony-mous reviewers for several suggestions that improved this paper. 19. References  C. F. Gauss, “Disquisitiones Arithmeticae,” English translation, Yale University Press, New Haven, 1986.  J. T. Cross, “The Euler’s φ-Function in the Gaussian In-tegers,” American Mathematics, Vol. 55, 1983, pp. 518-528. doi:10.2307/2322785  A. N. El-Kassar, M. Rizk, N. Mirza and Y. Wada, “El-Gamal Public Key Cryptosystem in the Domain of Gaus-sian Integers,” International Journal of Applied Mathe-matics, Vol. 7, No. 4, 2001, pp. 405-412.  H. Elkamchouchi, K. Elshenawy and H. Shaban, “Ex-tended RSA Cryptosystem and Digital Signature Schemes in the Domain of Gaussian Integers,” The 8th Interna-tional Conference on Communication Systems, Washing-ton, 25-28 November 2002, pp. 91-95.  S. Kak, “The Cubic Public-Key Transformation,” Cir-cuits Systems Signal Processing, Vol. 26, No. 3, 2007, pp. 353-359. doi:10.1007/s00034-006-0309-x  B. Verkhovsky, “Accelerated Cybersecure Communica-tion Based on Reduced Encryption/Decryption and In-formation Assurance Protocols,” Journal of Telecommu-nication Managements, Vol. 2, No. 3, 2009, pp. 284-293.  R. W. Hadden, “On the Shoulders of Merchants: Exchange and the Mathematical Conception of Nature in Early Modern Europe,” State University of New York Press, New York, 1994.  R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, New York, 2001.  A. Menezes, P. van Oorschot and S. Vanstone, “Hand-book of Applied Cryptography,” CRC Press, Boca Raton, 1997.  D. Knuth, “The Art of Computer Programming, Vol. 1: Fundamental Algorithms,” 3rd Edition, Addison-Wesley, Upper Saddle River, 1998.  A. Karatsuba and Y. Ofman, “Multiplication of Many- Digital Numbers by Automatic Computers,” Doklady Ak- ademii Nauk SSSR, Vol. 14, No. 145, 1962, pp. 293-294.  M. Rabin, “Digitized Signatures and Public-Key Func-tions as Intractable as Factorization,” Technical Report, MIT/LCS/TR-212, January 1979.  R. Rivest, A. Shamir and L. Adleman, “A Method of Ob- taining Digital Signature and Public-Key Cryptosys-tems,” Communication of ACM, Vol. 21, No. 2, 1978, pp. 120-126. doi:10.1145/359340.359342  B. Verkhovsky, “Enhanced Euclid Algorithm for Modu-lar Multiplicative Inverse and Its Complexity,” Advances in Computer Cybernetics, Vol. 6, 1999, pp. 51-57.  B. Verkhovsky, “Selection of Entanglements in Informa-tion Assurance Protocols and Optimal Retrieval of Original Blocks,” Journal of Telecommunications Man-agement, Vol. 2, No. 2, 2009, pp. 186-194.  B. Verkhovsky, “Information Assurance Protocols: Effi-ciency Analysis and Implementation for Secure Commu-nication,” Journal of Information Assurance and Security, Vol. 5, No. 3, 2008, pp. 263-269.  Z. Xu and J. Sun, “Video Encryption Technology and Application,” English translation, Nova Science Publishers Inc., New York, 2010, pp. 1-99. B. VERKHOVSKY Copyright © 2011 SciRes. IJCNS 203 Appendix A1. Validation of Algorithm-1 If condition (5) holds; then  221311333,,m,,od,pmpmpExy abpabab ab (A1) If 213,mod1pab p,0, then by Definition (2) (x, y) is a cubic root of (a, b) modulo prime p. Hence, if 219p is not an integer, then there exists an integer m such that pE is an integer, i.e., there exists an integer solution of equation 213mod90mp . (A2) Indeed, observe that 1) Every integer greater than 3 can be expressed ei-ther as p=6k+1 or as p = 6k–1; 2) 213p is an integer for every prime greater than 3; 3) If 219p is not an integer, then k mod 3 = 0; and 213p is not co-prime with 3. Therefore, (A2) can be rewritten as 213mod3 2mp. (A3) If there is no integer solution of Equation (A3); then Algorithm-1 is not applicable for these cases. In other terms, if either 19p or 19p is an integer, then pE is not an integer. A2. Validation of Algorithm-2 Let 213,,mqRabab odq. (A4) Since q mod 12 = 5, then 12q is even, hence by Euler criterion of quadratic residuosity , i.e., 1/21modqq1:1modip q (A5) is a real integer; and hence (a, b)mod q is also a real in-teger. Therefore, by the Fermat identity . Q. E. D. 3mod ,RqabA3. More on Identities for Cubic Roots By the Vieta theorem , equation 3mod 0CL p; (A6) implies that 123mod 0CC CCCCp . (A7) Hence, (A6) and (A7) imply 123 123mod0; mod;CCCpCCCpL  (A8) and for every permutation {i, j, k} of 1, 2, 3 2mod 0ij kCC Cp. (A9) On the other hand, (A9) implies 2mod 0.ij ijCC CCp (A10) Yet, neither (A9) nor (A10) are instrumental in recov-ery of all cubic roots. A4. Proof of Proposition 5 Algebraic approach: 33223,3,3moduwuuwuw wp1,0 (A11) Therefore from (A6) we deduce two equations with unknown u and w: 223moduuwp1; (A12) and 223modwu wp0. (A13) Since in (A13) mod 0wp, then 223moduw p. (A14) Hence, (A12) and (A14) imply that 32810mod; or214 21mod 0upuuu p.  (A15) Equation (A15) holds if either  12modup p ; (A16) or 2421moduu p0. (A17) Thus in (A16) case, if there exists square root of 3 modulo p, then from (A14) 31wu p 32. (A18) Otherwise, Equation (A17) implies that 13modu p; (A19) and finally from (A12) we deduce w. Trigonometric approach: Consider 33,1,0cosπisinπ(cos π3isinπ3)1,32 moduwp   (A20) B. VERKHOVSKY 204 .Proposition7: If (x, y) is a cubic root of (a, b) modulo p, then and ,,moduwxyp2,,moduw xyp are also cubic roots of (a, b). Proof: From Definition1 (2) for k = 1, 2 3,, ,modkuw xyabp Q.E.D. Copyright © 2011 SciRes. IJCNS