Modular Inverse Algorithms without Multiplications for Cryptographic Applications
Appendix: function prototypes in MATLAB
Download 288.56 Kb.
|
7.Appendix: function prototypes in MATLABThese serve only as vehicles of verification of the correctness of the algorithms, and test beds for experimenting. In a loop millions of function calls can be performed with random parameters, and compared to the result of the built-in extended GCD function, taking only a few minutes time. for i = 1:1e6 x = floor(2^51*rand(1,2)); % 2^9 to see problems at small numbers x(2) = max(bitor(x(2),1),3); % m = odd b = XXXinv(x(1),x(2)); if modinv(x(1),x(2)) ~= b || b > x(2) || b < 0 disp([x,b]) end end Note that the parameters are at most 51-bit random integers. Intermediate results of the algorithms can get one bit longer than the parameters, and MATLAB stores integers in double precision floating point registers, having 52-bit precision. Modular inverse based on the built in extended GCD algorithm: function C = modinv(a,m) %modinv(a,m) -> inverse of a mod m, based on Euclidean extended GCD alg [G,C,D] = gcd(a,m); if G~= 1, C = 0; return, end if C < 0, C = C + m; end Binary Right-shift algorithm, with signed arithmetic: function R = RSSinv(a,m) %RSSinv(a,m) -> inverse of a mod m, Right-Shift binary alg % m = odd, Signed arithmetic if ~mod(m,2) || a==0, R = 0; return, end U = m; V = a; R = 0; S = 1; while V > 0 if ~mod(U,2), U = U/2; % U is even if ~mod(R,2), R = R/2; else R = (R+m)/2; end % R = full length elseif ~mod(V,2), V = V/2; % V is even if ~mod(S,2), S = S/2; else S = (S+m)/2; end % S = full length else % U, V odd if U > V, U = U - V; R = R - S; else V = V - U; S = S - R; end end end if U > 1, R = 0; return,end while R < 0, R = R + m; end % loops at most twice (-2m < R < 3m) while R > m, R = R - m; end % R can grow longer than m Binary Right-shift algorithm, with unsigned arithmetic: function R = RSUinv(a,m) %RSUinv(a,m) -> inverse of a mod m, Right-Shift binary alg, using Unsigned % m = odd if ~mod(m,2), R = 0; return, end U = m; V = a; R = 0; S = 1; while V > 0 if ~mod(U,2) % U is even U = U/2; if ~mod(R,2), R = R/2; else R = (R+m)/2; end % R = full length elseif ~mod(V,2) % V is even V = V/2; if ~mod(S,2), S = S/2; else S = (S+m)/2; end % S = full length else % U, V odd if U > V, U = U - V; if R < S, R = R - S + m; else R = R - S; end else, V = V - U; if S < R, S = S - R + m; else S = S - R; end end end end if U > 1, R = 0; return, end Shifting Euclidean algorithm with unsigned arithmetic: function S = SEUinv(a,m) %SEUinv(a,m) -> inverse of a mod m, Shifting Euclidean alg, using Unsigned if a < m U = m; V = a; R = 0; S = 1; else V = m; U = a; S = 0; R = 1; end while V > 1 f = bits(U) - bits(V); % U >= V, f >= 0 if U < bitshift(V,f), f = f - 1; end U = U - bitshift(V,f); % always U >= 0 t = S; for i = 1:f t = t+t; % #adds <= bits(U)+bits(V) if t > m, t = t - m; end end R = R - t; % check R < t beforhand if R < 0, R = R + m; end % one of R,S gets large soon if U < V t = U; U = V; V = t; % swap(U,V) t = R; R = S; S = t; % swap(R,S) end end if V == 0, S = 0; end It uses the simple function bits(n), telling the number of bits n is represented with: function b = bits(n) [x,b] = log2(n); Shifting Euclidean algorithm with signed arithmetic: function S = SESinv(a,m) %SESinv(a,m) -> inverse of a mod m, Shifting Euclidean alg, using Signed if a < m, U = m; V = a; R = 0; S = 1; else V = m; U = a; S = 0; R = 1; end while abs(V) > 1 f = bits(U) - bits(V); if sign(U) == sign(V) U = U - shift(V,f); R = R - shift(S,f); else U = U + shift(V,f); R = R + shift(S,f); end if abs(U) < abs(V) t = U; U = V; V = t; % swap(U,V) t = R; R = S; S = t; % swap(R,S) end end if V== 0, S = 0; elseif V < 0, S = -S; end if S > m, S = S - m; elseif S < 0, S = S + m; end It uses also the simple function shift(n,i), shifting the signed integer n by i bits to the left: function s = shift(n,i) s = sign(n)*bitshift(abs(n),i); Double Plus-minus Right-shift algorithm (RS2+−) using signed arithmetic: function R = R2Sinv(a,m) %R2Sinv(a,m) -> inverse of a mod m, Right-shift 2-fold +/- binary alg % m = odd, using Signed arithmetic if ~mod(m,2) || a==0, R = 0; return, end U = m; V = a; R = 0; S = 1; Q = mod(m,4); m2 = 2*m; while ~mod(V,2) % for each trailing 0 bit V = V/2; if ~mod(S,2), S = S/2; elseif S > m, S = (S-m)/2; else S = (S+m)/2; end end while 1 % U,V = odd if U > V if mod(U,4) == mod(V,4) U = U - V; R = R - S; else U = U + V; R = R + S; end U = U/4; T = mod(R,4); if T == 0, R = R/4; elseif T == 2, R = (R+m2)/4; elseif T == Q, R = (R-m)/4; else R = (R+m)/4; end while ~mod(U,2),U = U/2; if ~mod(R,2),R = R/2; elseif R > m,R = (R-m)/2; else R = (R+m)/2; end end % |R| < m else if mod(U,4) == mod(V,4) V = V - U; S = S - R; else V = V + U; S = S + R; end if V == 0, break; end V = V/4; T = mod(S,4); if T == 0, S = S/4; elseif T == 2, S = (S+m2)/4; elseif T == Q, S = (S-m)/4; else S = (S+m)/4; end while ~mod(V,2),V = V/2; if ~mod(S,2),S = S/2; elseif S > m,S = (S-m)/2; else S = (S+m)/2; end end end end if U > 1, R = 0; return, end if R < 0, R = R + m; end
- /- Directory: Papers Papers -> From Warfighters to Crimefighters: The Origins of Domestic Police Militarization Papers -> The Tragedy of Overfishing and Possible Solutions Stephanie Bellotti Papers -> Prospects for Basic Income in Developing Countries: a comparative Analysis of Welfare Regimes in the South Papers -> Weather regime transitions and the interannual variability of the North Atlantic Oscillation. Part I: a likely connection Papers -> Fast Truncated Multiplication for Cryptographic Applications Papers -> Reflections on the Industrial Revolution in Britain: William Blake and J. M. W. Turner Papers -> This is the first tpb on this product Papers -> Basic aspects of hurricanes for technology faculty in the United States Papers -> Title Software based Remote Attestation: measuring integrity of user applications and kernels Authors Download 288.56 Kb. Share with your friends:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||