多项式环上求解问题：

引自 Lazzaro @ https://lazzzaro.github.io

1.对于一些模n运算的求解，我们可以将问题转化为模n多项式环上求解答问题

1
2
3
4
5
6
7
R.<X> = PolynomialRing(Zmod(n))
#Zmod(n):指定模，定义界限为n的环；Z表示整数；指定模是划定这个环的界限，就是有效的数字只有从0到n，其他的都通过与n取模来保证在0～n这个范围内；Zmod代表这是一个整数域中的n模环
#ZZ：整数环；QQ：有理数环；RR：实数环；CC：复数环
#R：只是一个指针，指向用polynomialring指定的那个环（可以使用任意字符）
#PolynomialRing：这个就是说建立多项式环
#.<X>：指定一个变量的意思（可以用任意字符）

现在，观察如下方程式，

1
2
n = p * q
y ** 2 = x ** 3 + a * x + b mod(n)

其中 y，a，b已知，根据常规方程我们是无法求出x的解的，因为对于第二个方程，我们未知的变量有x和n，单个方程无法解决二元变量求解问题，因此我们需要将改方程转换到模n多项式环上求解，在多项式环上寻找可行解。

具体方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
from sage.all_cmdline import *
from Crypto.Util.number import *
from gmpy2 import *

R.<X> = PolynomialRing(Zmod(n))
f = x ** 3 + a * x + b - y ** 2
f = f.monic()   //monic函数是判断方程必定有根
pp = f.small_roots(X=2^64, beta=0.4,epsilon = 0.01或5/32)[0]
		在f.small_roots中参数beta、epsilon参数的选取相对固定，上面的组合可以解决绝大多数的问题，x的选取主要看f中x的取值范			围，我们要求的是small_roots，最小根，就要封一个上限。
    
#9757458594430450711
x0 = mpz(pp)            //x0为求得的x解。

其中，R定义了一个整数多项式环，f定义为方程 模n等于0，f.monic表示首一多项式，X定义求求解x的最大范围，最后x0即为在多项式环上求得的可行解x。之后我们只需用

1
gcd（n,y**2 - x0 ** 3  - a * x0 - b)

即可求得p，之后分解得到q，就是常规rsa了。

2.同样，解释一下之前用到的扩充明文，同样是在多项式环n上求解原明文。

即：给出了p，或者q的部分高位，求完整p/q

1
2
3
4
('n=','0xb50193dc86a450971312d72cc8794a1d3f4977bcd1584a20c31350ac70365644074c0fb50b090f38d39beb366babd784d6555d6de3be54dad3e87a93a703abddL')
('p=','0xd7e990dec6585656512c841ac932edaf048184bac5ebf9967000000000000000L')
('e=', '0x3')
('c=','0x428a95e5712e8aa22f6d4c39ee5ec85f422608c2f141abf22799c1860a5e343068ab55dfb5c99a7085714f4ce8950e85d8ed0a11fce3516cf66a641dca8321eeL')

可以发现p的低位是未知的，我们同样可以在多项式环n上去搜寻完整的p，使其满足f = x + p % n == 0 

1
2
3
4
5
6
kbits = 60             
PR.<x> = PolynomialRing(Zmod(n))
f = x + p
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]          //2**60为搜寻的x的范围
print("x: %s" %hex(int(x0)))
p = p+x0                                            //x0为低位明文，p+x0为完整明文。