0
$\begingroup$

This question already has an answer here:

If we know n, p, q, and we have an encrypt oracle, which means we can input any plaintext and we'll get its ciphertext, and here p is smooth, which means the factors of p-1 are very small, is that enough to calculate e?

For example:

p = 2825358799356427706663024960708722136834286486305347798012688116053523677768086334617217613136124531692391647211744439952800403676645562774212886257998496983
q = 10337283954544263472170278791530601673760495286924662114752553349800339084620440642699623351318238668505676679342020084424432507313348331999122612813890619
n = 29206536182417645249113286202575933507961601192752943735537579881626707207199452403892662039844713074854197618645901039044094832010037552445992186931851958735631229599823239720545227003201588932156434083262685149366461250432279773927909333322029749301716265801654446100464605379768903189432805028070006563502477

Here p-1 have small factors:

p-1 = 2 * 17 * 29 * 31 * 31 * 41 * 53 * 53 * 103 * 107 * 193 * 463 * 683 * 929 * 1109 * 1409 * 1423 * 1459 * 1709 * 2053 * 2333 * 2437 * 2579 * 2963 * 3109 * 3637 * 4027 * 5923 * 7573 * 41801 * 34157 * 13523 * 17791 * 13217 * 14533 * 11149 * 37243 * 12347 * 17317 * 32869 * 45361 * 49391 * 56417 * 56951 * 43781 * 42923 * 15749

And we can input any m and get its c using our oracle, so we have:

m^e ≡ c (mod n)

Now it seems that we only need to solve this discrete log problem, but how can we solve this problem using the parameters above?


Thanks for your reminding, but actually i have read this link:

RSA find public exponent

and i still puzzled, i hope someone can show me some steps about how to implement this kind of attack, and i wonder how can we make use of p-1's small factors.


Thanks for poncho, but it seems there is something wrong with my code, i still can't get the correct value of e, i choose 123456 as a random number to encrypt and then encrypt enc(123456) and got:

c = enc(enc(123456)) = 17974577248777970429974193084697471181210277285580092392033195488767776200819236267705669052619985405260940318425980741869808301889634123608397453532136916612725135424925324872375421244924126046402740221813856723105776789830098584046922765416861558450087174562390063142833657987626131117178041141905463105382359

and then i use the following code in SageMath to calculate e:

p = 2825358799356427706663024960708722136834286486305347798012688116053523677768086334617217613136124531692391647211744439952800403676645562774212886257998496983
q = 10337283954544263472170278791530601673760495286924662114752553349800339084620440642699623351318238668505676679342020084424432507313348331999122612813890619
n = 29206536182417645249113286202575933507961601192752943735537579881626707207199452403892662039844713074854197618645901039044094832010037552445992186931851958735631229599823239720545227003201588932156434083262685149366461250432279773927909333322029749301716265801654446100464605379768903189432805028070006563502477

primes = [2,17,29,31,31,41,53,53,103,107,193,463,683,929,1109,1409,1423,1459,1709,2053,2333,2437,2579,2963,3109,3637,4027,5923,7573,41801,34157,13523,17791,13217,14533,11149,37243,12347,17317,32869,45361,49391,56417,56951,43781,42923,15749]

c = 17974577248777970429974193084697471181210277285580092392033195488767776200819236267705669052619985405260940318425980741869808301889634123608397453532136916612725135424925324872375421244924126046402740221813856723105776789830098584046922765416861558450087174562390063142833657987626131117178041141905463105382359

dlog = []
for i in primes:
    mp = pow(123456,((p-1)/i),p)
    cp = pow(c,((p-1)/i),p)
    x = discrete_log(mod(cp,p),mod(mp,p))
    dlog.append(x)

e = crt(dlog,primes)

and it told me that the value of e is:

e = 462130554767632886969034297367396246605209293273817664964730594630594433397969157217333099716605053039266871532432394972235790396076679127447171454900191

but that is a wrong answer, the correct value of e is:

e = 1445852576412043017081765538998723059835885914115077827632812328642985727978723573983751233000157196893265656063733564385321002296041452192501389769403032725

So i wonder why i got a wrong answer using this way and how can i fix it?

$\endgroup$

marked as duplicate by Ilmari Karonen, AleksanderRas, e-sushi, Squeamish Ossifrage, Maeher May 13 at 8:28

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ "here p is smooth, which means the factors of p-1 are very small"; terminology nit: actually, 'smooth' means 'all the factors are small, not several of them... $\endgroup$ – poncho May 10 at 11:40
  • $\begingroup$ Can you be more specific about how crypto.stackexchange.com/questions/68916/… does not answer your question? $\endgroup$ – Squeamish Ossifrage May 10 at 14:42
  • $\begingroup$ I changed my question a little to clarify my puzzle, many thanks. $\endgroup$ – Insecticide May 10 at 15:34
  • $\begingroup$ It's unclear whether you're trying to compute discrete logs modulo $p$ or $n$ here. Have you tried reducing the problem to a very small case, like $p = 59$? $\endgroup$ – Squeamish Ossifrage May 11 at 22:50
0
$\begingroup$

Here's how to recover $e \bmod 37^2$:

  • Pick a random plaintext $m$, and use the oracle to obtain $c = c^e \bmod n$

  • Compute $m_p = m^{(p-1)/(37^2)} \bmod p$ and $c_p = c^{(p-1)/(37^2)} \bmod p$

  • If $m_p^{37} = 1$, then try again with a different random plaintext; this is to eliminate plaintexts that don't give you as much information as they could; if you weren't testing against the square $37^2$, this would be a simple comparison against 1.

  • Solve the discrete log problem $m_p^x = c_p \pmod p$; there are $37^2$ possibilities for $x$, so simple brute force works (there are square root algorithms that can do it faster, but in this small case brute force is good enough).

  • Have has $x = e \bmod 37^2$

Repeating this will the other prime power factors of $p-1$, and combining them with CRT will give you $e \bmod 2 \cdot 37^2 \cdot 89^2 \cdot 127^2 \cdot 149^2$. If you have $e < 2 \cdot 37^2 \cdot 89^2 \cdot 127^2 \cdot 149^2$, then this gives you the value of $e$ directly.

You could combine this with small factors of $q-1$ (of course, you won't learn anything new with factors that $p-1$ and $q-1$ share); this would allow you to recover slightly larger $e$ values. However, that's a far as this approach will take you.

$\endgroup$
  • $\begingroup$ Thanks for your reply, but using this way i still can't calculate the correct answer, is there anything wrong with my understanding of your method? $\endgroup$ – Insecticide May 10 at 15:31
  • $\begingroup$ I changed my question a little to clarify my puzzle, many thanks. $\endgroup$ – Insecticide May 10 at 15:34

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