Lattice Learning

这一节利用格的知识解决一下之前遗留的问题

1.coppersmith

我们知道的是coppersmith是通过将求x₀满足f(x₀)≡0转换为一个具有相同根的小系数多项式F，使得能够满足F(x₀)=0

考虑一个简单情况下的应用:
N=17×19=323 ，F(x)=x²+33x+215 ，找小根x₀满足F(x₀)≡0(mod N)

我们找到多项式G(x)=9F(x)-N(x+6)=9x²-26x-3=(9x+1)(x-3)

于是我们便找到了小根x₀=3

下面证明几个需要用到的引理

Theorem1(Howgrave-Graham)

利用 Howgrave-Graham提出的一个定理，可以完善Coppersmith寻找m模方程根的思想。

F(x)=[a₀,a₁,···,a_n]，有F(x₀)≡0(mod N)

记

\[\vec{a}=(a_0,a_1x_0,···，a_nx_0^n) \]

那么当\(||\vec{a}||<\frac{N}{\sqrt{n+1}}\)时有F(x₀)=0

proof:

由cauchy不等式

\(|F(x)|≤\sqrt{(n+1)}||\vec{a}||<N\)

=>-N<F(x₀)<N =>F(x₀)=0

于是有了这个引理我们在求解模N的多项式小根解时，只需找到一个同根的小系数多项式

下面介绍小系数多项式如何找

根据上面例子的想法我们需要消去一个NG(x)

构造矩阵

\[A=\left[ \begin{matrix} N&0&0&0&···&0&0\\ 0&Nx&0&0&···&0&0\\ 0&0&Nx^2&0&···&0&0\\ ···&···&···&···&···&···&···\\ 0&0&0&0&···&Nx^{n-1}&0\\ a_0&a_1x&a_2x^2&a_3x^3&···&a_{x-1}x^{n-1}&x^n\\ \end{matrix} \right] \]

|A|=Nⁿ\(x^\frac{n(n+1)}{2}\)

现在对A进行格基规约

记规约后的第一行向量为\(\vec{s}\)

由LLL的性质(了解不多,以后进行补充)

||\(\vec{s}\)||≤\(2^{\frac{n-1}{4}}det(L)^{\frac{1}{n}}\)

于是对A规约后我们有规约后的向量\(\vec{a}≤2^{\frac{n}{4}}N^{\frac{n}{n+1}}x^{\frac{n}{2}}\)

于是根据Theorem1，若\(2^{\frac{n}{4}}N^{\frac{n}{n+1}}x^{\frac{n}{2}}<\frac{N}{\sqrt{n+1}}\)则该向量满足我们的需求(但是这个范围相比图一所示的范围还是松了，以后再进一步分析)

下面举几个例子实验一下(虽然small_roots很好，但是我们还是需要知道原理的)

1.已知明文高位攻击

from Crypto.Util.number import *

m=bytes_to_long(b'happy_new_year!!!happy_new_year!!!happy_new_year!!!happy_new_year!!!')
e=3
p=getPrime(256)
q=getPrime(256)
n=p*q
c=pow(m,e,n)
print(n)
print(c)
print(m>>40)

#9677308850805072615245338772573038756194472761218833637549002026260651828849253582986766773068999761609142518697886921427163239409796891474031612292051243
#3619062459035100688199905801885001763102350553764315045632083081114951726640899393420854287661472297915641990877935483766234743101262919652708578368432163
#21354909218710478405558840015746007979798119883625401161254670224022140989734793925077991132006894434531534543193456590592582639039948875227320492718437

直接用small_roots()

n=9677308850805072615245338772573038756194472761218833637549002026260651828849253582986766773068999761609142518697886921427163239409796891474031612292051243
c=3619062459035100688199905801885001763102350553764315045632083081114951726640899393420854287661472297915641990877935483766234743101262919652708578368432163
m=21354909218710478405558840015746007979798119883625401161254670224022140989734793925077991132006894434531534543193456590592582639039948875227320492718437
m=m<<40
PR.<x>=PolynomialRing(Zmod(n))
f=(x+m)^3-c
print(f.small_roots(X=2^40,beta=0.4))

自己实现一下small_roots()

n=9677308850805072615245338772573038756194472761218833637549002026260651828849253582986766773068999761609142518697886921427163239409796891474031612292051243
c=3619062459035100688199905801885001763102350553764315045632083081114951726640899393420854287661472297915641990877935483766234743101262919652708578368432163
m=21354909218710478405558840015746007979798119883625401161254670224022140989734793925077991132006894434531534543193456590592582639039948875227320492718437
m=m<<40
A=Matrix(ZZ,[[n,0,0,0],[0,n,0,0],[0,0,n,0],[m^3-c,3*m^2,3*m,1]])
a0,a1,a2,a3=A.LLL()[0]
f=a3*x^3+a2*x^2+a1*x+a0
print(f.roots())
x0=418526601505
m=m+x0
print(m)

2.已知p高位攻击

from Crypto.Util.number import *

m=bytes_to_long(b'happy_new_year!!!happy_new_year!!!happy_new_year!!!happy_new_year!!!')
e=65537
p=getPrime(256)
q=getPrime(256)
n=p*q
c=pow(m,e,n)
print(n)
print(c)
print(p>>50)

#5448125722893334260562280747888654536139933739196079020142053414414807314549486336443238126829178727553182036872421054100807188285011477255964328343680981
#4769039646084942249141712296616892568306162649820158521697617722547813960950902829355291119614076397745773349215760626720442369568516613267600527649911543
#81154826622582571852729289025450452700658483313221098257214353

这个按照原来的格的构造方式无法得出(还是没弄懂small_roots()在此处的实现)，这个地方有点特殊，copper在这个点的解决方式之前也没太看明白，到时候问明白一下