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$
3
  • $\begingroup$ You may be interested in the modular inversion hidden number problem $\endgroup$
    – Ella Rose
    Commented Feb 8, 2018 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
    Commented Feb 8, 2018 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$ Commented Feb 8, 2018 at 13:24

2 Answers 2

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$
5
  • 3
    $\begingroup$ How do you compute that if $p$ does not have an inverse? $\endgroup$
    – Conrado
    Commented Feb 8, 2018 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
    Commented Feb 8, 2018 at 12:48
  • $\begingroup$ One reference for those wondering $\endgroup$
    – Conrado
    Commented Feb 8, 2018 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$ Commented Feb 8, 2018 at 20:04
  • $\begingroup$ Nevermind, stupid question $\endgroup$ Commented Feb 8, 2018 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 and acknowledge you have read our privacy policy.

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