2
$\begingroup$

I am trying to crack an unpadded RSA set up for a homework.

I have public key (R,e) and encrypted message E.

R:=1189873858375600120035497781492406260116261348762168101523668479976252918878873543993974091515716923413521166189;
e:=7;
E:=935688997292570230577548538417371291686892187342525833188430568797480485753147343888751799688783739259397891334;

Obviously, the attack that I'm supposed to use has something to do with the size of the public encryption exponent but I'm struggling to see exactly how to use it.

I understand the relationship between e, d and φ(n) and understand that there is an integer k < min{e, d} such that φ(n) = (e ∗ d − 1)/k but I don't understand how I can use that fact to brute force discover φ(n).

It appears that the solution comes from doing some kind of search from 1..k but since d is still unknown, I don't really see how to take advantage of that.

Can someone enlighten me, please?

$\endgroup$
7
  • 4
    $\begingroup$ I suspect that the smallness of the encryption exponent has nothing to do with it; instead, consider the modulus, which is approximately circa 372 bits long; how can you take advantage of that? $\endgroup$
    – poncho
    Oct 1, 2014 at 3:31
  • 2
    $\begingroup$ To elaborate a bit on poncho's comment, most real world RSA encryption schemes use small encryption exponents for performance, usually 3, 17 or 65537 - so $e = 7$ may not be of any help! $\endgroup$
    – Thomas
    Oct 1, 2014 at 6:43
  • $\begingroup$ If the message is shorter than the length of the modulus divided by the public exponent, you can simply compute the $e$ root, for example via binary search. For real RSA the padding ensures that the message has similar length as the modulus, but for unpadded RSA short messages can happen. $\endgroup$ Oct 1, 2014 at 8:10
  • 2
    $\begingroup$ The actual statement (see Problem 2) does not hint that padding or small exponent are relevant, so I guess Poncho hinted to the expected resolution path. $\;$ Notice that this homework is not quite past its due date + allowance; please do not post a solution before that. $\endgroup$
    – fgrieu
    Oct 1, 2014 at 8:26
  • 1
    $\begingroup$ 1) Simply running a factoring software sounds a little dull for a homework question. It's also weird that the moduli for Problem 1 are smaller. If you bothered to setup factoring software for Problem 2 you use it to solve problem 1 as well, without exploiting the same message encryption weakness. 2) the short message and small exponent approach doesn't seem to work. $\endgroup$ Oct 1, 2014 at 9:54

1 Answer 1

2
$\begingroup$

The question is from Problem 2 in Assignment 6 given here. It looks much like a straight instance of the RSA problem: we want to find $x\in\mathbb N$ such that $x^e=E\bmod R$ and $x<R$, given $R$, $E$, $e=7$, with $E$ expected to be the product of two unknown primes $p,q$ such that $e$ is coprime with $(p-1)\cdot(q-1)$.

It is correct that knowing none of $d$, $\varphi(R)$ or $\lambda(R)$, nor the factorization of $R$, we can't solve the problem by massaging $e\cdot d\equiv1\pmod{\varphi(R)}$ or $e\cdot d\equiv1\pmod{\lambda(R)}$ with $e$ small.

The fact that $e$ is small would help if it turned out that $E$ (or $i\cdot R+E$ for some small $i$) was an exact power of $e$; for this would allow to find $x$ by extracting an $e$-th root. For random parameters, this happens with odds about ${R^{1/e-1}}$, thus decreasing with $e$. But $R$ is so big that theses odds are vanishingly low for $e\ge2$. In fact, any small odd $e>2$ is believed a safe choice in RSA when $x$ is random or properly padded.

The most classic avenue to solve an RSA problem is to factor the public modulus $R$. This is how Part 1 of Assignment 2 was done, for $R$ of 276 bits. In the present problem, $R$ is 367-bit, therefore brute force factorization is feasible (it was feasible in 1995 by means available to academics; see this answer). However it would require a significant effort, and I do not know that Maple's built-in factorization primitive would factor a properly chosen 367-bit RSA modulus in reasonable time.

We should not rule out factorization though: in this course, Alice (which, we are told, has $R,e$ as public key) has in Assignment 4 made unconventional and rather poor choice of key; so there is a chance that $R$ was not properly chosen and can be factored with little effort, using some of the factorization methods likely alluded to in the course.

Hint 1: The problem can be solved with practically any big-number calculator offering modular exponentiation, without even writing an iterative program.

Hint 2: (Hover mouse to see it)

Alice may have put too much emphasis on being ultra-resistant to trial division for a given magnitude of $R$.

$\endgroup$
4
  • $\begingroup$ Hey Fgrieu, I got a similar assignment problem and I can't run the factorization software on a 309 digit long so roughly almost 1000 bits long n along with e being 5, Although I will try this trial division method but would hope if something better way using lattice theory? $\endgroup$ Nov 25, 2014 at 6:45
  • $\begingroup$ @codeomnitrix: the assignment in this question was intended to be solvable in one iteration of the Fermat factoring method; that is, the simple 4 steps in this answer. That may be worth trying in your case (especially if there is any hint that the factors are very close, or mention of the method); and perhaps the full Fermat factoring. $\endgroup$
    – fgrieu
    Nov 25, 2014 at 12:31
  • $\begingroup$ No fgrieu, neither factors are too close nor the (p-1) or (q-1) is smooth i.e. easily factorized. So that option is wiped out. Can you please help me with Coppersmith's method? Thanks in advance.. Please see the question - crypto.stackexchange.com/questions/20450/… $\endgroup$ Nov 27, 2014 at 12:44
  • $\begingroup$ @codeomnitrix: I scratched my head and failed to see how Coppersmith's method (also here) could help in your other question as it originally stood; but the modified one is very different! $\endgroup$
    – fgrieu
    Nov 27, 2014 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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