Modular binomial

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

x=(a+b)e mod Nx = (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 :

c1=(a1⋅p+b1⋅q)e1 mod Nc2=(a2⋅p+b2⋅q)e2 mod Nc_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

c1e2=(a1⋅p+b1⋅q)e1⋅e2 mod Nc1e2=(a1⋅p)e1⋅e2+(b1⋅q)e1⋅e2 mod Na1−e1⋅e2⋅c1e2=a1−e1⋅e2⋅(a1⋅p)e1⋅e2+a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod Na1−e1⋅e2⋅c1e2=pe1⋅e2+a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod Nc_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

c2e1=(a2⋅p+b2⋅q)e2⋅e1 mod Nc2e1=(a2⋅p)e2⋅e1+(b2⋅q)e2⋅e1 mod Na2−e2⋅e1⋅c2e1=a2−e2⋅e1⋅(a2⋅p)e2⋅e1+a2−e2⋅e1⋅(b2⋅q)e2⋅e1 mod Na2−e2⋅e1⋅c2e1=pe2⋅e1+a2−e2⋅e1⋅(b2⋅q)e2⋅e1 mod Nc_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

a2−e2⋅e1⋅c2e1−a1−e1⋅e2⋅c1e2=pe2⋅e1+a2−e2⋅e1⋅(b2⋅q)e2⋅e1−pe1⋅e2−a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod N=a2−e2⋅e1⋅(b2⋅q)e2⋅e1−a1−e1⋅e2⋅(b1⋅q)e1⋅e2 mod Na_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

PreviousChinese Remainder TheoremNextPadding

Last updated