### Paper Menu >>

### Journal Menu >>

Int. J. Communications, Network and System Sciences, 2010, 3, 901-906 doi:10.4236/ijcns.2010.312123 Published Online December 2010 (http://www.SciRP.org/journal/ijcns) Copyright © 2010 SciRes. IJCNS Enhanced Euclid Algorithm for Modular Multiplicative Inverse and Its Application in Cryptographic Protocols Boris S. Verkhovsky Computer Science Department, New Jersey Institute of Technology, University Heights, Newark, USA E-mail: verb@njit.edu Received August 21, 2010; revised October 4, 2010; accepted November 16, 2010 Abstract Numerous cryptographic algorithms (ElGamal, Rabin, RSA, NTRU etc) require multiple computations of modulo multiplicative inverses. This paper describes and validates a new algorithm, called the Enhanced Euclid Algorithm, for modular multiplicative inverse (MMI). Analysis of the proposed algorithm shows that it is more efficient than the Extended Euclid algorithm (XEA). In addition, if a MMI does not exist, then it is not necessary to use the Backtracking procedure in the proposed algorithm; this case requires fewer opera- tions on every step (divisions, multiplications, additions, assignments and push operations on stack), than the XEA. Overall, XEA uses more multiplications, additions, assignments and twice as many variables than the proposed algorithm. Keywords: Extended-Euclid Algorithm, Modular Multiplicative Inverse, Public-Key Cryptography, RSA Cryptocol, Rabin Information Hiding Algorithm, ElGamal Encryption/Decryption, NTRU Cryptosystem, Computer Simulation, Low Memory Devices 1. Introduction Elements of modular arithmetic are essential for pub- lic-key encryption algorithms such as the RSA crypto- graphic algorithm [1-3], and RSA with digital signature [4]; ElGamal cryptocol [5]; Rabin encryption/decryption scheme based on extraction of square roots [6]; NTRU cryptosystem [7]; and extensions of some of these algo- rithms in Gaussian arithmetic require computation of a modular multiplicative inverse (MMI) [8-10]. The MMI is also computed for cryptanalysis of public-key crypto- graphic protocols [11-13]. A new algorithm, called the Enhanced-Euclid Algo- rithm (NEA), for modular multiplicative inverse (MMI) is described and validated in this paper. Definition 1: Given relatively prime integers and , there exists an unique integer x such that 0 p 1 p 1 1modpx p 0 . (1) Then x is defined as the modular multiplicative inverse of 1 p modulo or, for short, MMI. 0 The NEA finds for two relatively prime integers 0 and 1 an integer number x that satisfies the Equation (1). And if and are not relatively prime, then NEA finds a gcd(0,1). The Extended-Euclid algo- rithm (XEA) also finds a MMI of modulo if and only if gcd(,) = 1 [1,2,7]. pp p 0 p1 p p p p 1 p0 p 0 1 This paper proves the validity o f NEA and provides its analysis. The analysis demonstrates that NEA is faster than the Extended Euclid algorithm. Preliminary results of this paper are published in [8]. p 2. Basic Arrays and Their Properties Let’s consider five finite integer arrays: ; ; k k t w k z;; ii pc (2) Definition 2: Let i p and i c be integer arrays defined according to the following generating rules: Given two relatively prime integers 0 p and 1 p su that 0 p1iwhile i p ch 1 , p, for do 2 11 :m ii 1 d;: iiii pcpp o. pp (3) Definition 3: Let k t be an arbitrary integer array for all ; let for initially specified 0 1 0 and 1 the following generating rules be defined for all : 1k,w,w z z 2k 902 B. S. VERKHOVSKY 11 2 : kkk k wwt w ; and 11 2 : kkk k zzt z . (4) Proposition 1: Let’s define for 1k 1 1 :kk kkk ww Dzz . (5) Then 1 1 1k k D D. (6) Proof: Consider k and substitute in the left column the values of k and defined in (4). After simpli- fications we derive that D wk z 1kk DD , which recursively implies (6). Proposition 2: Consider the integer arrays k t, , and (4) k w k z where 00 1 :1; :wz0; :1z . Then is a multiplicative inverse of 1 1 1k k zz 1k w modulo for every . k Proof: Indeed, since , then (5) implies that w1 w 1 D 1 z 1 1k z 11 1k kkk k wz zwz , (7) or that 11 2 1111 11 kk kkk wzzzwz Then from (7) it follows that 11 11 1 111 kk kkk wzzwz 1k z , i.e., 1 1 1k k x zz . Proposition 3: If for all 0kr : kr tc kk , and , (8) : kr wp then and are the initial values that generate the arrays 0 p1 p ,, ii c p :and: krkkr tc wp k . Remark 1: Notice that = k t R i c and R ki wp, where the superscript R means that the arrays i c 1kzz and are written in a reverse order. i p Theorem 1: For all k = 1,, r, is the inverse of modulo p. 1 1k 1rk Proof follows from Propositions 1-3. p Theorem 1 implies the following assertions: 1) if k is odd and , 11z then x:=> 0; k z 2) if k is even and , 11z then x:=< 0. k z In the latter case select 0 :k x pz. (9) 3. Enhanced Euclid Algorithm for MMI The proposed algorithm uses stack as a data structure, [2]. vars: r; L; M; S; t: all integer numbers; b: Boolean; procedure Forward: 0 :Lp ; 1 : M p ; b: = 0; {r: = 0}; repeat :tLM ; :SLMt ; :1; :1;bbrr (10) push t {onto the top of the stack}; L: = M; M: = S; (11) until S = 1; Remark 2: if S = 0, then ; therefore the MMI does not exist; 01 gcd ,pp t procedure Backtracking: S: = 0; :1 b M ; {by (9) in the Theorem 1}; repeat pop t {from the top of the stack}; L: = Mt + S; (12) :; :SMML; until the stack is empty; output x: = L; {if x < 0, then x: = x +}. 0 Remark 3: r is the height of the stack and is used be- low for analysis of the proposed algorithm. p 4. Two Illustrative Examples Let’s demonstrate how NEA finds a multiplicative in- verse x of 27,182,845 modulo 31,415,926. Table 1 be- low shows the computation of remainders in the upper row and stores the quotients in the middle row (the stack). Then the Backtracking procedure is used to com- pute from right to left until the stack is empty. The inputs and MMI are shown in bold, and the stack val- ues are in italics. Since the total number of steps (the height of the stack) is equal to fourteen (i.e., even), then x = 13,939,773. Direct verification confirms that indeed 27182845 * 13939773 mod 31415926 = 1. In the second numerical example we need to find the MMI z of 27,319,913 modulo 177,276,627 {see Table 2}. Since the height of the stack is odd, then z = 177276627-344 80855 = 14279577 2. Direct computation verifies that z is indeed the MMI of 27319913, since 27319913 * 142795772 mod 1772766 27 = 1. 5. Complexity Analysis of MMI Algorithm Consider four non-negative integer arrays , k q k d, Copyright © 2010 SciRes. IJCNS B. S. VERKHOVSKY Copyright © 2010 SciRes. IJCNS 903 Table 1. Modular multiplicative inverse algorithm in progress. 31415926 2718208730 2845 4233081 1784359 664363 455633 Stack 1 6 2 2 1 2 112084 18789 792920927 3939773 614821750 4789 2172 61 (continuation) 208730 38173 17865 2443151 9 7 2 1 764 2 5 2 7 3 5 16 1 3 *** 92 7 168 7927 1084 3 61933967 4 3 1 0 Table 2.nd numal illusion. 177276627 27319913 136 5 1 Secoerictrat 3357149 605615 33619 473 Stack 6 2 22 18 71 13 7 *** 353108 25907 114 6 4480855 388077953992 7 1 0 ed as fo and ii p c definllows: 11 1 : kkk dqq ; (13) satisfy (3) and a (14) Then (3) and (14) imply that mod i p Hence both arrays and ar - creasing, and all termcorresarrays and ii pc re defined as 11 11 :; : iiikkkk ppcqqqd i p 11 : iiii pppc 1i p i p s of the k q ponding e strictly de c i d k d are positive er num Definition 4: an integ bers. j s x is a (s + 1)-dimensional ve consisting of the first s + 1 terms of actor, n array 01 1 , ,...,,, j j x xxx i.e., 0 :,,...,, …, 1 1 j ss s x xxxx. Theorem 2: Consider and 1; ii r cp ; ;1 kk sss dq 1 ir p. Let pq 00 ; ik s s cd, j = l suc following in i.e., for all j = 1,, s eists at least one h that . Thor al the there xjs ll l 1equalities hold: if 11jl, then cden f j j pq otherwise j j pq. (15) Proof: Assuming that the stat , it can also be demonstrated by Consi ement (15) holds for all induction that 1ij (15) also holds for ij. der 11 . jjjjjj j j qqp p q pp jj p j tdc (16) If 1jl lows: if , then else. Hence from (16) it fol0 j t 1 0 j t jl , then j j pq otherwise j j pq. Since 00 pq , then (14) holds for all js. Q.E.D. nsider af relatively prime s an arr Co pair o seeds 01 and pp that generateay i cr 1 r ir of relatively prime seeds 01 and pq ge . Consider also a pa tha an array nothe t nerates 1 k d, 1 s ual to one. Let r and s be the number of steps respectively to find MMe first and the second pair using either XEA or NEA. Thismption implies that s q i.e l its eq . such that Is for th not al assu te required rms are . Then by Theorem 2 ik s s pq and 1 ss pq. Hence rs. Corollary: A pair of seeds, that for a given 0 p re- quires the maximal number of steps for computation of a MMIrates an unary array of ., all s in i.e, genequotients, component i c1 r . Thus, as it follows ) an from (3 lowd (14), this pair of seeds must generate the foling array of integer numbers: 201 :ppp;312 :ppp;; 21 :1 rr r pp p . It is easy to verify that this array is equivalent to the of Fibonacci numbers sequence 21 , rr 432 ,...,, , F F In other words, for every 0,...,ir 2 : ir pF FFF . i , [14]. Remark 4: The pair ;pF pF is 02r ) a unary a11r rrayf qnot the only one that generates auotients and b) a decreasing integer array where the rth remainder eq pairs of seeds hav o uals one. Indeed, the followinge the same B. S. VERKHOVSKY 904 of the Lucas 3) 1 zero and negative indices are computed in accdance with the formula: property for all non-negative integer numbers t and u: 1) 02rr pF tF ; 111rr pF tF ; for t = 1 1 ; ; R i pL is a sequence 2 1r mbers 1, 3, 4, 7, 11, 18,[15]; 2) 021 1; rr ptF tF 1t; ;L L nu 1ptFtF ; 11rr ;pFtF t2 01rr1; 11 ; rr pFtF 4) 02 1; rr r ptFtFuF 2 1ptFtFuF 113rr r Here the Fibonacci num. bers with or 1 1m mm F F . For all pairs, listed above, exactly r steps are required to find the MMI. However, all these pairs are special cases of a pair of seeds where b; and Consider 01rr pbFF and 112rr pbFF . Therefore for all 0ir 1iriri pbFF , r p 11 r p. 15v 2 and 152w . Using a z kr -transform approach, we deduce that for all 0 5 k ww k rk pbvbv . (17) Then for a large r 510 k k k rk pbvwwbv since 1v. (18) The relation (18) implies that for a large r 051 r pwbv w . (19) Let 00 2 :max ,,2 b zrpbrp . Therefore p (20) 000 log 52log1 ww zpvp implies that the height of a stack satisfies the following inequality: [8]. Example 3: In this example (see Table 3 illustrates the case where the height of the sta in the Inequality (2 Thus (20) 00 log 1 w rp p , (21) the table below) 1 1919 mod31051364 . Indeed, 1919 * 1364 mod3105 = 1. ck is approaching the upper bound 1). Remark 5: Although this upper bound is achievable if 01 pb rr FF and 112rr pbFF , for this pair of inp 1r uts the MMI can be computed explicitly: indeed, it equals 1r F . Remark If in RSA public-key encryption [3], pc 6: , thenc 100 010 100 / loglogrw 10 10 ; therefore 479 logcr . housandemonstrate ge Over one t computer simulations d that the averaheight of the stack is actually almost 40 A) modulo provided that gcd = 1, [2,7]. 3 = g{there is n- ve if = 1 return Y3 = gcd ); % smaller than the upper bound in (21). 6. Extended-Euclid Algorithm (XE XEA also finds a multiplicative inverse of 1 p 00 1 1) Assign (X1, X2,X3):= (1, 0,0 p); (Y1,Y2,Y3)(0,1, 1 p); 2) if Y3 = 0 return Xcd(p,1 p); p(p,p):= 0 rse}; 3) Y3 o in (0 p, nv 1 p rseelse Y2 is the multiplicative ie; 4) :3QXY3; (22) 5) 3 3QY1,2,3 :11,22,T TTXQYXQYX ;(23) 6) ,3 :1,2 1,2, 3 X X Y; (24) X YY 7 ) 1,2, 3:1, 2, 3YY YTTT; 7. Comparative analysis of NEA vs. XEA for ard rocedure in (10), and Q in (22), respectively. division, th Table 3. {Worst-case space co 3105 1919 1186 733 9 7 2 1 (25) 8) goto 2. Both algorithms require equal number of steps r computation of all quotients: values of t on the Forw pIn addition, NEA requires r more steps on the Back- tracking procedure to compute the values of L in (12). Therefore each step of XEA requires one ree multiplications, three long algebraic additions and ten assignments, see (22)-(25). mplexity}: Size of stack. 453 280 17310766 41 25 16 Stack 1 1 1 1 1 1 1 1 1 1 1 1 1 3 *** 1364 843 521 322 199 123 76 47 29 18 11 7 4 3 1 0 Copyright © 2010 SciRes. IJCNS B. S. VERKHOVSKY 905 XEA Yet in boproures NEA uses one division, two multiplications, two long additions, o stacra, ( andht assign- n NEA I han XEA: uses ten variables. th ced tw mk opetionspushnd pop), a eig ents, see (10)-(12). NEA uses four integer variables, one binary variable and, in addition, 0 logwp of memory to store the stack. Notice that if a MMI does not exist, then there is no need to use the Backtracking procedure i.nthis case NEA requires even fewer operations tone division, one multiplication, one addition, one push op- eration and five assignments per every step. Yet XEA still requires the same number of operations per step as in the case if a MMI does exist. Hence, overall XEA uses more multiplications, more additions, more assignments and twice as many variables than the proposed algorithm. 8. Average Complexity of XEA and NEA both inputs are chosen randomly, then the If 01 and pp probability that 01 gcd ,1pp equals 2 6 [2]. Let us consider the following notations: x ea w-worst-case specific complexity (per step) of XEA; ; nea w-worst-case specific complexity of NEA x ea a-average-case specific complexity of XEA; nea arage-case specific complexity of NEA; let ;-ave on, muations push a hen ; ; ; masst tttt be time complexities of divisi d ltipl t ication, addition, assignment and stack oper nd pop respectively. T 3 +3+10; x ea dmas wt ttt (26) 2 +wt t 2+8+2; nea dmasst ttt (27) 2 2 6 st t2 +2+8+2 ++5+16 neadm a s dma sst atttt ttt tt Notice that (28) x ea xea aw; and t 9) implies dm ass tt ttt (29) Then (27)-(2 that 22 :231.538 (30) xea nea Ra a 9. Conclusions nalysis of the proposed algorithm (NEA) for modular rse demonstrates that its execution 53.8% less time, than the execution eed K-bit level for ublron algo- rithm, where the inputs are integers on the interval A multiplicative inve quires on averagere of the Extended Euclid algorithm. Theoretical analysis of space complexity of the En- hanced-Euclid algorithm shows that it requires relatively small bit-storage for its execution. This storage does not xcea 2a pic-key encypti 01 and pp 100 400 10,10. ey mode -Euclid algorithm r implementation of encryption in low memory en of this aper; and to A. Koripella for her assistance in running . van Oorschot and S. A. Vanstone, “Handbook of Applied Cryptography,” CRC Press, Boca ] R. L. Rivest, A. Shamir and L. Adleman, “A Method for On the other hand, computer simulations demonstrate that the average bit-storage is actually 40% smaller than 2K. Hence NEA can be executed if necessary by a cus- tom-built chip with relativlst memory, [7]. This property of the Enhanced is especially useful fo vironments such as smart or PC cards, cell phones, wearable computers and other integrated devices. 10. Acknowledgements I express my appreciation to R. Rubino, J. Runnells, M. Sikorski, C. Washington and to anonymous reviewer for comments and suggestions that improved the style p computer experiments. 11. References [1] R. Crandall and C. Pomerance, “Prime Numbers: A Computational Perspective,” Springer, Berlin, 2001. [2] A. J. Menezes, P. C Raton, 1997. [3 Obtaining Digital Signature and Public-Key Cryptosys- tems,” Communications of the ACM, Vol. 21, No. 2, 1978, pp. 120-126. [4] B. Verkhovsky, “Overpass-Crossing Scheme for Digital Signature,” Keynote Address, Proceedings of Interna- tional Conference on System Research, Informatics and Cybernetics, Baden-Baden, 30 July-4 August 2001. [5] T. ElGamal, “A Public-Key Cryptosystem and a Signa- ture Scheme Based on Discrete Logarithms,” IEEE Trans- actions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472. [6] M. Rabin, “Digitized Signatures and Public Key Func- tions as Intractable as Factorization,” Technical Report: MIT/LCS/TR-212, MIT Laboratory for Computer Science, Cambridge, 1979. [7] J. Hoffstein, J. Pipher and J. H. Silverman, “An Introduc- tion to Mathematical Cryptography,” Springer, Berlin, 2008. [8] B. Verkhovsky, “Multiplicative Inverse Algorithm and Its Complexity,” Proceedings of International Conference- InterSYMP-99, Baden-Baden, July 1999, pp. 62-67. [9] B. Verkhovsky, “Accelerated Cyber-Secure Communica- tion Based on Reduced Encryption/Decryption and In- formation Assurance Protocols,” Journal of Telecommu- nications Management, Vol. 2, No. 3, 2009, pp. 284-293. Copyright © 2010 SciRes. IJCNS B. S. VERKHOVSKY 906 riza- International Journal of Communications, Net- p. 1-8. . 276-288. ppendix omputer experiments decimal-digit long integers A and B were B; dul o A was computed; in era Table A1. Results of computer experiments. Range of S [10] B. Verkhov sky, “Hybrid Aut hentication Cybersy stem Based on Discrete Logarithm, Entanglements and Facto tion,” International Journal of Communications, Network and System Sciences, Vol. 3, No. 7, 2010, 579-584. [11] B. Verkhovsky, “Generalized Baby-Step Giant-Step Al- gorithm for Discrete Logarithm Problem,” Advances in Decision Technology and Intelligent Information Systems, International Institute for Advanced Studies in Systems Research and Cybernetics, Baden-Baden, 2008, pp. 88- 89. [12] B. Verkhovsky, “Integer Factorization: Solution via Al- gorithm for Constrained Discrete Logarithm Problem,” Journal of Computer Science, 2009, Vol. 5, No. 9, 674- 679. [13] B. Verkhovsky, “Potential Vulnerability of Encrypted Messages: Decomposability of Discrete Logarithm Prob- lems,” work and System Sciences, Vol. 3, No. 8, 2010, pp. 639-644. [14] R. B. McClenon, “Leonardo of Pisa and His Liber Quad- ratorum,” American Mathematical Monthly, Vol. 26, No. 1, 1919, p [15] D. Harkin, “On the Mathematical Works of Francois- Edouard-Anatole Lucas,” Enseignement Mathematique, Vol. 3, No. 2, 1957, pp A CN Average S ) Pairs of N1 generated randomly, where A > 2) Then MMI C of B mo other words we found an integer C, for which holds BC mod A = 1; 3) 125 experiments have been carried out for each value of N = {6, 8, 10,,18, 20}; 4) The values of S (size of stack-storage) for each N were tabulated; (not shown in the Table A1). 5) The values of avge S for every N and the range of S for each N are presented in the Table A1. [min, max] 6 12.65 [7, 17] 8 16.20 [9, 21] 10 19.96 [14, 29] 12 24.91 [19, 33] 14 28.53 [18, 36] 16 32.30 [20, 41] 18 36.70 [23, 50] 20 40.29 [26, 54] Copyright © 2010 SciRes. IJCNS |