# How to calculate e if we know n,p,q,m,c? [duplicate]

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?

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?

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

• "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... – poncho May 10 at 11:40
• Can you be more specific about how crypto.stackexchange.com/questions/68916/… does not answer your question? – Squeamish Ossifrage May 10 at 14:42
• I changed my question a little to clarify my puzzle, many thanks. – Insecticide May 10 at 15:34
• 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$? – Squeamish Ossifrage May 11 at 22:50

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.

• 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? – Insecticide May 10 at 15:31
• I changed my question a little to clarify my puzzle, many thanks. – Insecticide May 10 at 15:34