# Modular Inverse as a Problem

Given a modulus $N$ and a number $a$, a multiplicative inverse exists for $a$ if $a$ and $N$ are coprime. Why isn’t there a cryptosystem that uses this as a computational problem?

Example

Alice and Bob agree on a public modulus $N$ and a public number $p$ such that $p$ and $N$ are not coprime. Then Alice sends Bob $a \cdot p \bmod N$ and Bob sends Alice $b \cdot p \bmod N$. Where $a$ and $b$ can be any number. Then they compute the shared secret: $a (b \cdot p) \bmod N \equiv b (a\cdot p) \bmod N$.

• You may be interested in the modular inversion hidden number problem – Ella Rose Feb 8 '18 at 12:39
• Potentially helpful fact: If $A=ap\bmod N$ has a solution (as is the case here by construction), then there are precisely $\gcd(p,N)$ solutions. – SEJPM Feb 8 '18 at 13:06
• Not having an inverse doesn't mean that the problem becomes difficult to solve, only that it becomes lossy/ambiguous. – CodesInChaos Feb 8 '18 at 13:24

This doesn't work, because it is easy to compute $a$ from $ap \bmod N$ given $p$ and $N$. More precisely, it is easy to compute some $a'$ such that $a'p \equiv ap \pmod N$; $a'$ will not necessarily equal $a$, but that doesn't matter since $a'(bp) \equiv b(a'p) \equiv b(ap) \pmod N$, so the secret is correctly recovered.

In other words, this is Diffie-Hellman in the additive group mod $N$, and it doesn't work because discrete logs are easy to compute in such groups.

• How do you compute that if $p$ does not have an inverse? – Conrado Feb 8 '18 at 12:30
• @Conrado Solving congruences of the form $ax \equiv b \pmod n$ is a staple of elementary number theory courses; Google has more references on it than I can count. – fkraiem Feb 8 '18 at 12:48
• One reference for those wondering – Conrado Feb 8 '18 at 15:33
• Can this be done for three variables? Such as if you know x and y can you find w * v given: xwv = y mod N. – MarquisDeSitruce Feb 8 '18 at 20:04
• Nevermind, stupid question – MarquisDeSitruce Feb 8 '18 at 20:12

The question's secret exchange protocol is insecure, because it is easy to compute the shared secret $S=(a\cdot b\cdot p\bmod N)$ from $A=(a\cdot p\bmod N)$ and $B=(b\cdot p\bmod N)$, by computing the constants of 1 below (once), then using a formula of 4 (for each protocol run).

1. Compute $g=\gcd(N,p)\$, $\ M=\displaystyle{N\over g}\$, $\ q=\displaystyle{p\over g}\$, and $r=(q^{-1}\bmod M)$ which is well-defined (because any common factor of $N$ and $p$ has been eliminated from $M$ and $q$).
2. $g$ divides $A$, $B$, and $S$; and it holds that $\displaystyle{A\over g}=(a\cdot q\bmod M)\$, $\ \displaystyle{B\over g}=(b\cdot q\bmod M)\$, and $\ \displaystyle{S\over g}=(a\cdot b\cdot q\bmod M)$
3. Therefore, $(a\bmod M)\,=\,\left(\displaystyle{A\over g}\cdot r\bmod M\right)\$, $\ (b\bmod M)\,=\,\left(\displaystyle{B\over g}\cdot r\bmod M\right)\$, and $\ \displaystyle{S\over g}\,=\,\left(\displaystyle{A\over g}\cdot r\cdot\displaystyle{B\over g}\cdot r\cdot q\bmod M\right)\,=\,\left(\displaystyle{A\over g}\cdot\displaystyle{B\over g}\cdot r\bmod M\right)$
4. From which it comes $S\ =\ \left(\displaystyle{A\over g}\cdot\displaystyle{B\over g}\cdot r\bmod M\right)\cdot g$
or equivalently $S\ =\ \left(\displaystyle{A\over g}\cdot B\cdot r\bmod N\right)$

Numerical illustration: $N=1095339$; $p=527541$; $a=979429$; $b=867172$;
$A=22365$; $B=450702$; $S=(a\cdot B\bmod N)=(b\cdot A\bmod N)=229446$
Step 1: $g=\gcd(N,p)=21\$; $\ M=\displaystyle{N\over g}=52159\$; $\ q=\displaystyle{p\over g}=25121\$; and $\ r=(q^{-1}\bmod M)=38337$
Step 4: $S\ =\ \left(\displaystyle{A\over g}\cdot\displaystyle{B\over g}\cdot r\bmod M\right)\cdot g\ =\ \left(\displaystyle{A\over g}\cdot B\cdot r\bmod N\right)=229446$