This is the problem, I have to explain how works the algorithm on the image with modular arithmetic for a discrete math class., I tried to explain it, but I couldn´t. In the class, I have seen this topics: Euclidean Algoritm, RSA, Bézout's identity, The Chinese remainder theorem, Euler's theorem, Euler φ function, Fermat's little theorem and other primality filters like Miller_Rabin. This problem is extra at the class, but I need to explain it, I´m the only one on the class who has to explain it. So please, I would be so, so, so grateful with the one who can explain me how the algorithm works (mathematically) , for example: why ed is congruent with? 1 mod phi?(N) (the first fact in the image)
here is the link where I find it: https://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect14-c.pdf
thanks in advance¡ 🙂
Best Answer
Recall how RSA works: we have a modulus $n = pq$, and an exponentiation exponent $e$ and a decryption exponent $d$. And $d$ is chosen such that it is the inverse of $e$ modulo $\phi(n) = (p-1)(q-1)$.
( This means that $ed \equiv 1 \mod \phi(n)$, or equivalently $ed = 1 + k\phi(n)$ for some $k \in \mathbb{Z}$. And then Fermat says that $x^{\phi(n)} \equiv 1 \mod n$ and so $(x^e)^d = x^{ed} = x^{1+ k\phi(n)} = x^1 (x^{\phi(n)})^k \equiv x 1^k = x \mod n$, so that exponentiation with $e$ and $d$, modulo $n$, are each other's inverse. )
So you know that $ed - 1$, which you can compute when $e$ and $d$ are known, is a multiple of $\phi(n)$, which is a multiple of 4 (as $p-1$ and $q-1$ are both even). So we can write $ed -1$ as $2^s r$, where $r$ is odd (just divide out factors of 2, $s$ many times, till we are left with an odd number).
You also know that $x^{ed-1} = 1 \mod n$, when $(x,n) = 1$. (If $(x,n) \neq 1$, $(x,n) = p$ or $(x,n) = q$ and we factored $n$; the probability that this happens is of course very small for large enough $p,q$). So picking random such $x$ (or $w$, as in your link) and then computing $x^r \mod n$, $x^{2r} \mod n$, etc., we are sure to get to $1$ eventually (when we have done it $s$ times, we are at $2^s r = ed -1$ and this power gives 1).
Now look at the number $m$ in the sequence of powers starting from $x^r$ and then squaring till we get $1$. We could start with $x^r \equiv 1$ (so no previous) or the power before we get $1$ is equal to $-1$ modulo $n$: we then have found a trivial square root of $1$ (the next squaring gives $1$, and we try another $x$. But if this is not the case (and the probability of this is more than half, as the slide says) we have found a non trivial square root $m$ of $1$, and that number $m$ is $+1$ modulo one prime and $-1$ modulo the other prime (see slide 6 of the linked presentation), so $m+1$ has a non-trivial factor with $n$ and gives us one (and thus both) of the primes.
You might have to try a few different $x$, but in a few tries you'll factor $n$ this way.