Ask Your Question
0

Bivariate Coppersmith method

asked 2021-04-30 19:21:39 +0200

P_1_6 gravatar image

updated 2021-05-04 11:38:20 +0200

Given the bivariate polynomial

p(m,n) = 675 * m * n + 297 * m + 25 * n + 11

The bivariate Coppersmith method can be used to find m0 and n0 such that

(675 * m0 * n0 + 297 * m0 + 25 * n0 + 11) mod (1763) = 0

where is it

m0 = 3 ; n0 = 3

Unfortunately I cannot understand the hypotheses

Kindly someone could only explain the hypotheses to me

EDIT1:

OTHER INFORMATION

You can choose some coefficients and their size order of this type of polynomial in O (16).

(N-3)/8-q*(p-A)/8-[4-(A-7)*(A-5)/8]=A*(q+A-4-8)/8

->

N=p*q

if we choose A such that p-A mod 8 = 0 



we can write it this way


(N-3)/8-Q-[4-(A-7)*(A-5)/8]=A*X

so there are 4 chances to find A and they are

8*h+1 ; 8*h+3 ; 8*h+5 ; 8*h+7



(N-3)/8-p*(q-B)/8-[4-(B-7)*(A-5)/8]=B*(p+B-4-8)/8

->

N=p*q

if we choose B such that q-B mod 8 = 0



we can write it this way


(N-3)/8-P-[4-(B-7)*(B-5)/8]=B*Y

so there are 4 chances to find B and they are

8*k+1 ; 8*k+3 ; 8*k+5 ; 8*k+7


f(N,A,B) is  O(16)





Example

1763=41*43


220-q*(p-25)/8-[4-(25-7)*(25-5)/8]=25*(q+25-4-8)/8

220-p*(q-27)/8-[4-(27-7)*(27-5)/8]=27*(p+B-4-8)/8


220-Q-[4-(25-7)*(25-5)/8]=25*X

220-P-[4-(27-7)*(27-5)/8]=27*X


Q=25*a+11   X=10-a  

P=27*b+1    X=10-b 


220-Q-[4-(17-7)*(17-5)/8]=17*X

Q=17*c+10   X=13-c      9-a=13-c -> c=a+4

220-P-[4-(19-7)*(19-5)/8]=19*X

P=19*d+9    X=12-d      9-b=12-d  ->d=b+3



p=(19*(b+3)+9)-(27*b+1)=65-8*b      

q=(17*(a+4)+10)-(25*a+11)=67-8*a    



(65-8*b)*(67-8*a)=1763
,
(10-a)-(10-b)=((67-8*a)-(65-8*b)-2)/8


(65-8*b)*(27*1763)/(-8*(27*b+1)+1763)=1763 TRUE




So I thought about using the bivariate Coppersmith method

Q=25*a+11 

P=27*b+1


p(m,n)=p(b,a)=P*Q=(27*b+1)*(25*a+11)=Z*1763

EDIT2:

At least see if I understand:

in my case given two polynomials

for example

(25*a+11)*(27*b+1) mod 1763 ==0

and

(17*(a+4)+10)*(19*(b+3)+9) mod 1763 == 0

the first question is can they be both modulo 1763?

|a|<IntegerPart[sqrt(1763/2)]

|b|<2*IntegerPart[sqrt(1763/2)]

if this method can be applied, it can be solved in polynomial time

Did I get it right ?

edit retag flag offensive close merge delete

Comments

Your question would be better addressed to https://math.stackexchange.com/ : this forum is oriented towards the use of Sagemath to execute mathematical computations ; mathematical foundations are discussed only when this is relevant to computation.

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2021-05-01 07:14:30 +0200 )edit

@Emmanuel Charpentier is there any method to use bivariate coppersmith method in sagemath?

P_1_6 gravatar imageP_1_6 ( 2021-05-01 10:06:06 +0200 )edit

Some implementation is available at https://github.com/ubuntor/coppersmit...

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-02 04:33:11 +0200 )edit

@Max Alekseyev thank you

P_1_6 gravatar imageP_1_6 ( 2021-05-02 10:17:33 +0200 )edit

@Max Alekseyev I shared other information .[] @Emmanuel Charpentier if the bivariate Coppersmith method is applicable is relevant to computation of factorization

P_1_6 gravatar imageP_1_6 ( 2021-05-02 21:16:11 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted
0

answered 2021-05-04 16:41:47 +0200

Max Alekseyev gravatar image

I'm not sure what is exactly your concern about the bivariate Coppersmith method -- if it's about the theory, you'd better read the original paper.

As for your second question - the two polynomials modulo 1763 have the same set of zeroes, simply because one of them represents a multiple of the other. This can be seen from computing their resultant and observing that it's zero modulo 1763. Here is a code illustrating that

R.<a,b> = PolynomialRing(ZZ)
p = (25*a+11)*(27*b+1)
q = (17*(a+4)+10)*(19*(b+3)+9)
r = p.resultant(q)
print('resultant:',r)
t = r.polynomial(b).change_ring(Integers(1763))
print('resultant mod 1763:',t)
edit flag offensive delete link more

Comments

  • I understood the concept of the resultant [thank you]
  • (65-8 * b) * (67-8 * a) -1763 = 0 can the bivariable coppermith method be applied here?
P_1_6 gravatar imageP_1_6 ( 2021-05-04 19:00:27 +0200 )edit

Does the polynomial have to be in this form to use bivariate Coppersmith method?

64*a^2*b^2-840*a^2*b+2600*a^2-856*a*b^2+10560*a*b-34800*a+2680*b^2-35472*b+108864=0
P_1_6 gravatar imageP_1_6 ( 2021-05-04 22:50:59 +0200 )edit

@Max Alekseyev can we use the Coppersmith method multivariate in this case?

(8*a*b-65*a-67*b+5) mod 319 = 0 ;   (25*a+11)*(27*b+1) mod 1763 = 0
P_1_6 gravatar imageP_1_6 ( 2021-05-05 10:44:37 +0200 )edit

Yes, Coppersmith method is applicable to (65-8 * b) * (67-8 * a) -1763 = 0, but not to 64*a^2*b^2-840*a^2*b+2600*a^2-856*a*b^2+10560*a*b-34800*a+2680*b^2-35472*b+108864=0 since the latter polynomial is reducible.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-05 19:26:05 +0200 )edit

@Max Alekseyev thank you. Do you also know the answer to the third question of the comments? [multivariate]

P_1_6 gravatar imageP_1_6 ( 2021-05-05 19:51:17 +0200 )edit

I do not follow this question since it's about two polynomials, while Coppersmith method applies to a single polynomial.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-05 19:58:24 +0200 )edit

@Max Alekseyev Thanks for your patience. I ask you a question: how is it solved and what is the computation cost to solve this?

(25*a+11)*(27*b+1) mod 1763 = 0
P_1_6 gravatar imageP_1_6 ( 2021-05-05 21:44:10 +0200 )edit

No, as we see that (25*a+11)*(27*b+1) is reducible (product of 2 factors).

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-05 21:55:42 +0200 )edit

@Max Alekseyev Thanks for your patience.

(25*a+11)*(27*b+1)-(65-8 * b) * (67-8 * a) mod  1763 = 0
P_1_6 gravatar imageP_1_6 ( 2021-05-05 22:03:05 +0200 )edit

@Max Alekseyev how is it solved and what is the computation cost to solve this?

P_1_6 gravatar imageP_1_6 ( 2021-05-05 22:24:16 +0200 )edit

@Max Alekseyev the real question is this: "RSA-based Ramsonware" can they be defeated in your opinion with this technique?

P_1_6 gravatar imageP_1_6 ( 2021-05-06 10:45:39 +0200 )edit

Is depends on the size of RSA modulus. Say, there is negligible chance with a 2048-bit, let along 4096-bit, modulus.

Max Alekseyev gravatar imageMax Alekseyev ( 2021-05-06 16:14:10 +0200 )edit

@Max Alekseyev thank you

P_1_6 gravatar imageP_1_6 ( 2021-05-06 17:28:02 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2021-04-30 19:21:39 +0200

Seen: 329 times

Last updated: May 04