4
$\begingroup$

Assume we have a somehow unorthodox implementation of RSA whereby:

$p$ and $q$ are chosen primes of length $n/2$ where $n$ is the number of bits desired in $N=p\,q$ and $$\begin{align} \phi &= (p-1)(q-1)\\ d &= p\\ e &= d^{-1}\bmod \phi \end{align}$$

I can see that there is a weakness here but I'm unsure of how it translates. Playing around a bit I see that I end up with:

$$e = \frac{\phi j + 1}p $$

Further assuming that $\frac{1}p$ can be considered infinitesimal: $$e ≈ j\left(q\left(1+\frac{1}p\right) -1\right)$$

So basically: $$e ≈ j(q-1)$$

Is that right? Am I missing something?

|improve this question
$\endgroup$
  • 1
    $\begingroup$ Do you mean $e = \mathrm{modinv}(d,\phi)?$ Otherwise explain how to get $e.$ $\endgroup$ – gammatester Sep 3 '18 at 15:28
8
$\begingroup$

Yes, it's broken. Here is the approach I see:

$$p = \text{gcd}( n, r^e - r \bmod n)$$

with quite high probability, for random $r$.

This happens because $e \equiv 1 \bmod p-1$, and hence $r^e \equiv r \pmod p$ (for any $r$). It is unlikely that $r^e \equiv r \pmod q$, and hence $r^e - r$ has $p$ as a factor, but (probably) doesn't have $q$.

|improve this answer
$\endgroup$
  • $\begingroup$ I'm trying to derive the equation myself (the implementation works like a charm, just trying to understand it better). Would you mind expanding? Do you use Fermat's little theorem? $\endgroup$ – S. L. Sep 4 '18 at 15:59
  • 1
    $\begingroup$ @S.L. Two things: $d = p$ implies $d \equiv 1 \pmod{p-1}$, which imples that $d^{-1} = e \equiv 1 \pmod{p-1}$, that is, $e = k(p-1) + 1$ for some integer $k$. Second thing: Fermat's little theorem (as he originally stated it) says that $a^p \equiv a \pmod p$ for all $a, p$ (with $p$ prime). A simple extension gives $a^{k(p-1) + 1} \equiv a \pmod p$ for all $a, k, p$ (with $p$ prime). Combining these two ideas immediately gives the result. $\endgroup$ – poncho Sep 4 '18 at 16:12
  • $\begingroup$ OK I follow up to Fermat's theorem. in this case, $e$ i.e. $k(p-1)+1$ isn't prime. Moreover, wouldn't that be $$a^{k(p-1)+1} = a (mod (k(p-1)+1)$$ ? Thanks! $\endgroup$ – S. L. Sep 4 '18 at 16:37
  • 1
    $\begingroup$ @S.L.: it doesn't matter whether $k(p-1) + 1$ is prime or not; it only matters that $p$ is prime. As for the extension to FLT, it really is $a^{k(p-1)+1} \equiv a \pmod p$; showable by simple induction (it's true for $k=0, 1$, and if it's true for $k=1, x$, it's easy to show it's true for $k = x+1$) $\endgroup$ – poncho Sep 4 '18 at 16:47

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.