10
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ You may be interested in the modular inversion hidden number problem $\endgroup$ – Ella Rose Feb 8 '18 at 12:39
  • $\begingroup$ 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. $\endgroup$ – SEJPM Feb 8 '18 at 13:06
  • 4
    $\begingroup$ Not having an inverse doesn't mean that the problem becomes difficult to solve, only that it becomes lossy/ambiguous. $\endgroup$ – CodesInChaos Feb 8 '18 at 13:24
11
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ How do you compute that if $p$ does not have an inverse? $\endgroup$ – Conrado Feb 8 '18 at 12:30
  • 2
    $\begingroup$ @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. $\endgroup$ – fkraiem Feb 8 '18 at 12:48
  • $\begingroup$ One reference for those wondering $\endgroup$ – Conrado Feb 8 '18 at 15:33
  • $\begingroup$ 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. $\endgroup$ – MarquisDeSitruce Feb 8 '18 at 20:04
  • $\begingroup$ Nevermind, stupid question $\endgroup$ – MarquisDeSitruce Feb 8 '18 at 20:12
7
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.