How to write matlab code for modular multiplicative inverse in cryptography
57 次查看(过去 30 天)
显示 更早的评论
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 ...
0 个评论
回答(3 个)
John D'Errico
2020-1-8
编辑:John D'Errico
2020-1-8
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?
The trick is to use the Extended Euclidean algorithm. It is reasonably fast and efficient. But again, just use GCD.
0 个评论
Jan
2013-7-12
编辑:Jan
2013-7-12
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.
1 个评论
Cedric Martens
2021-12-19
编辑:Cedric Martens
2021-12-19
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
Stefano Roddaro
2020-1-8
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
1 个评论
John D'Errico
2020-1-8
编辑:John D'Errico
2020-1-8
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
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Encryption / Cryptography 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!