# RSA given d and d = p

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?

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

$$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$.
• @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. – poncho Sep 4 '18 at 16:12
• 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! – S. L. Sep 4 '18 at 16:37
• @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$) – poncho Sep 4 '18 at 16:47