Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I got stuck on a homework question. If anyone could help me with this certain problem, I would be grateful. I'll state what the problem say and some relevant theorem (i believe) that I used to partly prove the problem.

Problem: A decryption exponent for an RSA public key $(N,e)$ is an integer $d$ with the property that $a^{de} \equiv a \mod N$ for all integers $a$ such that $\gcd(a,N) = 1$. Note that $N = pq$ but $p,q$ is unknown where $p,q$ are distinct primes and $e$ is the encryption exponent.

Suppose I can find a decryption exponent for a given $(N,e)$ where $N$ is a fixed modulus and for a large number $e$ that is not $N$. How can I factor $N$?

Attempt: According to the RSA public key cryptosystem, primes $p$, $q$ are picked such that they are distinct and an encryption exponent $e$ is chosen such that $\gcd(e, (p-1)(q-1)) = 1$.

So here's what I did: Suppose that I am given two public keys with both public keys having the same modulus, so I have $(N, e_1)$ and $(N,e_2)$. By hypothesis, I can find $d_1$ and $d_2$ such that $e_1d_1 \equiv 1 \mod (p-1)(q-1)$ and $e_2d_2 \equiv 1 \mod (p-1)(q-1)$. By definition of congruences, there exists $k_1, k_2 \in \mathbb{Z}$ such that $e_1d_1 - 1 = k_1[(p-1)(q-1)]$ and $e_2d_2 - 1 = k_2[(p-1)(q-1)]$. Then I took the $\gcd(e_1d_1-1,e_2d_2 -1) = \gcd(k_1,k_2)[(p-1)(q-1)]$.

Consider the case when $\gcd(k_1,k_2) = 1$. Then we found the value of $(p-1)(q-1)$, so $(p-1)(q-1) = pq - (p+q) + 1 = N - (p+q) + 1$. This implies that $(p+q) = N + 1 - (p-1)(q-1)$. So we use the quadratic formula to solve $X^2 - (p+q)X + N$ since this equation equals $(X-q)(X-p)$. Hence, I found the factors of $N$.

But if the case that $\gcd(k_1,k_2) > 1$ seems to got me stuck. If anyone can help me with this by providing a way to think about this problem, that'll be great.

share|improve this question

1 Answer 1

I would try finding non-trivial square roots of $1$ modulo $N$. This is a bit probabilistic, but works in practice reasonably quickly I think.

You know that $de-1=\ell\,\mathrm{lcm}\{(p-1),(q-1)\}$. Note that both $p-1$ and $q-1$ are even, so they are not coprime. Write $$ de-1=2^km, $$ with $m$ odd (this is easy as you can just keep dividing by two). Let $a$ be a random integer. Most likely it is coprime to $N$ (check with Euclid- if not , then you found a factor of $N$ and can quit). Compute the power $z=a^m$ modulo $N$. Keep squaring $z$ (modulo $N$). We know that $z^{2^k}\equiv 1\pmod N$, because $$ z^{2^k}\equiv a^{2^km}\equiv 1\pmod N, $$ as $2^km$ is divisible by both $p-1$ and $q-1$. Let $k_1$ be the smallest integer, $0\le k_1\le k$, such that $z^{2^{k_1}}\equiv 1\pmod N$. If $k_1=0$, then we are out of luck, and must try another $a$. Otherwise let us examine $$ x\equiv z^{2^{k_1-1}} \pmod N. $$ Then $x^2\equiv 1\pmod N$. If $x\equiv -1$, then, again we are out of luck, and should try another $a$. If not, then we are done, because $(x-1)$ (and $(x+1)$) will have a non-trivial common factor with $N$ that we can again find with Euclid's algorithm.

Can we be denied success by a string of bad luck? Not really! Let $U_{q,2}$ be the group of residue classes modulo $q$ of order that is a power of two (=2-Sylow subgroup of $\mathbb{Z}/q\mathbb{Z}^*$), and similarly $U_{p,2}$. Then $z$ is equally likely to land on any element of $U_{q,2}$ (resp. $U_{p,2}$), and by CRT these two choices are independent from one another. The process fails, if and only if $z$ has the same order $2^{k_1}$ in both groups, because that is when $z^{2^{k_1-1}}\equiv-1$ modulo both $p$ and $q$ resulting in $x\equiv -1\pmod{N}$. The chance of this happening is at most one half. If $|U_{q,2}|=|U_{p,2}|$, then we succeed at least when $a$ is a quadratic residue modulo exactly one of the factors $p$ and $q$, because $z$ is in the maximal proper subgroup of $U_{q,2}$ (resp. $U_{p,2}$), iff it is a quadratic residue modulo $q$ (resp. modulo $p$). If $|U_{q,2}|\neq|U_{p,2}|$, the situation is even better, because success is guaranteed, when $z$ is of maximal order in the bigger group.

So with at least an even money chance of success in each round, we will succeed sooner rather than later.

share|improve this answer
1  
So a bit similar to Rabin-Miller primality testing. I think that the penultimate paragraph can be simplified (the business with quadratic residue vs. non-residue), but can't wrap my head around it now. –  Jyrki Lahtonen Jul 9 '12 at 11:42
1  
@MathNewbie: In your other question square roots of integers modulo $pq$ were also studied. Here it is a special case of looking for square roots of one. Except this time we use the square roots to find factors, not the other way around as was the case there. –  Jyrki Lahtonen Jul 10 '12 at 6:09
1  
@MathNewbie: This question is an even better match! In fact, they could all come from the same chapter of a textbook - one exercise logically leading to the next. –  Jyrki Lahtonen Jul 10 '12 at 6:12
    
Ah I see how I can apply it. Thanks. ;) –  MathNewbie Jul 10 '12 at 9:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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