Paper Menu >>
Journal Menu >>
![]() 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) Copyright © 2011 SciRes. 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 E-mail: verb73@gmail.com 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 Copyright © 2011 SciRes. IJCNS 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 Copyright © 2011 SciRes. IJCNS 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 Copyright © 2011 SciRes. IJCNS 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 Copyright © 2011 SciRes. IJCNS 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 Copyright © 2011 SciRes. IJCNS 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 Copyright © 2011 SciRes. IJCNS 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. |