2
$\begingroup$

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) enter image description here

here is the link where I find it: https://www.cs.purdue.edu/homes/ninghui/courses/Fall04/lectures/lect14-c.pdf

thanks in advance¡ :)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks¡ your answer is very helpful, I will work on it, if I have some doubt on this, hope you can help me a little more (I hope that won´t be necessary, I´ll try to get it by my self), but anyway, thanks so much. $\endgroup$ – JuanMan394 Oct 22 '14 at 23:15

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.