Modular binomial

A modular binomial problem is a mathematical problem in which a binomial expression of the form :

$$x = (a + b)^e \bmod N$$

where :

• a and b are integers,

• e is a positive integer (the exponent),

• and N is a positive integer (the modulus).

In cryptography, the modular binomial problem is used in RSA encryption, where the integers a, b, and N are related to the encryption and decryption keys, and the exponent e is used to encrypt a message. Solving the modular binomial problem for a given c, e, and N is considered to be a hard problem and is the basis of RSA encryption's security.

Searching p and q

The modular binomial problem can have the following form :

$$c_1 = (a_1 \cdot p + b_1 \cdot q)^{e_1} \bmod N\\ c_2 = (a_2 \cdot p + b_2 \cdot q)^{e_2} \bmod N\\$$

Given the value of c1, c2 a1, a2, e1, e2 and N and where N = p*q it's possible to retrieve p and q as follow :

The main idea is to :

• upper c1 using the exponent used in the c2 equation : e2

• upper c2 using the exponent used in the c1 equation : e1

Doing that, c1 and c2 are on the same exponent : e1.e2

In order to retrieve q it's needed to isolate it, so it's needed to make the two equation to had the same p value

• Multiply by a1**(-e1*e2) in the c1 equation reduce P factor to 1

• Multiply by `a2**(-e1*e2) in the c2 equation reduce P factor to 1

Then, by substrat c1 to c2 there is a p**(e1*e2) - p**(e1*e2) which is 0 so they can be remove of the equation

$$c_1^{e_2} = (a_1 \cdot p + b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\ c_1^{e_2} = (a_1 \cdot p)^{e_1 \cdot e_2} + (b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\ a_1^{-e_1 \cdot e_2} \cdot c_1^{e_2} = a_1^{-e_1 \cdot e_2} \cdot (a_1 \cdot p)^{e_1 \cdot e_2} + a_1^{-e_1 \cdot e_2} \cdot (b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\ a_1^{-e_1 \cdot e_2} \cdot c_1^{e_2} = p^{e_1 \cdot e_2} + a_1^{-e_1 \cdot e_2} \cdot(b_1 \cdot q)^{e_1 \cdot e_2} \bmod N\\$$

Make the same with c2

$$c_2^{e_1} = (a_2 \cdot p + b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\ c_2^{e_1} = (a_2 \cdot p)^{e_2 \cdot e_1} + (b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\ a_2^{-e_2 \cdot e_1} \cdot c_2^{e_1} = a_2^{-e_2 \cdot e_1} \cdot (a_2 \cdot p)^{e_2 \cdot e_1} + a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\ a_2^{-e_2 \cdot e_1} \cdot c_2^{e_1} = p^{e_2 \cdot e_1} + a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} \bmod N\\$$

Then

$$a_2^{-e_2 \cdot e_1} \cdot c_2^{e_1} - a_1^{-e_1 \cdot e_2} \cdot c_1^{e_2} = p^{e_2 \cdot e_1} + a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} - p^{e_1 \cdot e_2} - a_1^{-e_1 \cdot e_2} \cdot(b_1 \cdot q)^{e_1 \cdot e_2} \bmod N \\= a_2^{-e_2 \cdot e_1} \cdot (b_2 \cdot q)^{e_2 \cdot e_1} - a_1^{-e_1 \cdot e_2} \cdot(b_1 \cdot q)^{e_1 \cdot e_2} \bmod N$$

So, q = gcd(pow(a2,(-e2 * e1),N) * pow(c2, e1, N) - pow(a1, (-e1 * e2), N) * pow(c1, e2, N), N)

Do the same to get p