How to write matlab code for modular multiplicative inverse in cryptography

Hello Professionals ... Can anyone help in how to write matlab code for following ... Compute the modular multiplicative inverse: a=1/b mod m. in cryptography . here b and m is known and a to be find ...

Answer 1

[John D'Errico]

A multiplicative inverse modulo some number p means that

mod(x*xinv,p) == 1

That is, x has a mutiplicative inverse modulo p, if that equality holds true. For example, we will find

mod(2 * 4,7) = = 1

Therefore, 4 is the mutiplicative inverse of 2, modulo 7.

When the modulus (7 in my example) is a prime, we will find that ALL integers except zero will have a multiplicative inverse. When the base is composite, then an inverse will exist only if x and p are co-prime (relatively prime). For example, there is no integer x such that

mod(3*x,12)

will yield 1. so 3 has no multiplicative inverse, modulo 12. The clue is that 3 and 12 are not relatively prime - they share an integer factor greater than 1.

Given all of that, how can we compute the modular multiplicative inverse in MATLAB? It is actually not that difficult. The trick is to find it in the arguments of the function gcd. For example, find the multiplicative inverse of 2, mod 7.

[G,D] = gcd(2,7)
G =
     1
D =
    -3

The second argument will be a multiplicative inverse of 2, as long as G is 1. G is the GCD of the two numbers, and if they are relatively prime, then G will be 1. If so, then D will be a multiplicative inverse. (It will not be unique.)

My modinv code below does the computation. It uses GCD as the engine.

function Xinv = modinv(X,p)
% % modinv: mutiplicative modular inverse of X, mod p
% usage: y = modinv(X,p)

%
% arguments: (input)
%  X - integer(s) to compute the modular inverse in the field of integers
%      for some modular base b.
%
%      x may be scalar, vector or array
%  
%  p - integer modulus. SCALAR only.
%      When p is not a prime number, then some numbers will not have a
%      multiplicative inverse.
%
% arguments: (output)
%  Xinv - an array of the same size and shape as X, such that 
%      mod(X.*Xinv,p) == 1
%      
%      In those cases where X does not have a multiplicative inverse in the
%      field of integers modulo p, then Xinv will be returned as a NaN.
%
% Examples:
% % In the field of integers modulo 12, only 1,5,7, and 11 have a
% % multiplicative inverse. As it turns out, they are all their own inverses.
%
%  Xinv = modinv(0:11,12)
%  Xinv =
%   NaN  1  NaN  NaN  NaN    5  NaN    7  NaN  NaN  NaN   11
%
% % In the field generated by modular base 7 (which is prime) only 0 will
% % lack a modular multiplicative inverse.
%
%  Xinv = modinv(0:6,7)
%  Xinv =
%   NaN     1     4     5     2     3     6
% 
% % Works for large (symbolic) integers.
%
%  p = sym('12434354343545235345253')
%  p =
%  12434354343545235345253
%
%  modinv(2,p)
%  ans =
%  6217177171772617672627
%
% See also: gcd, sqrtmodp
%
% Author: John D'Errico
% Creation date: 1/2/2020

if numel(p) ~= 1
  error('p must be a scalar')
end

% pre-allocate Xinv as NaN in case some elements of X have no inverse
Xinv = NaN(size(X));

% if p is symbolic, then Xinv should also be symbolic.
if isa(p,'sym')
  Xinv = sym(Xinv);
end

% all the hard work will be done by gcd.
[G,C] = gcd(X,p);

% if G is not equal to 1, then no solution exists.
k = G == 1;
Xinv(k) = mod(C(k),p);

Could I have written a solution that does not use MATLAB's built-in GCD? Of course. But why?

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

The trick is to use the Extended Euclidean algorithm. It is reasonably fast and efficient. But again, just use GCD.

Answer 2

[Jan]

a = mod(1/b, m)

Usually I tend not to post obvious solutions and suggest reading the Getting Started chapters of the documentation. I do not want to solve otherones homework also. But for this question I'm confused.

[Cedric Martens]

this is not the answer. What the person is asking is they want to find an integer b such that a*b mod m = 1. Your solution 1/b is not an integer.

for example the inverse of 3 (mod 5) is 2 (2*3) mod 5 = 1

This is a common topic in cryptography

Answer 3

[Stefano Roddaro]

Old question, but maybe someone (like me) has the same doubt. The question is stated in somewhat confusing terms, I guess here the idea is to find an integer "a" such that mod(a*b,m)=1. This should work:

[div,c1,c2] = gcd(b,m);
% returns the greatest common divisor "div" and the two integer constants that solve
%
% c1*b + c2*m = div
%
if div==1
    a = mod(c1,m);
else
    % the inverse does not exist if b and m are not coprime
end

[John D'Errico]

Posting an answer now to this question, but you are correct. gcd does the work, although it is not that difficult to compute.

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm