对RSA-Factoring with High Bits Kn
首先从WHCTF2017-Untitled中开始：
此题考点很多，相关资料在本人的github网站上：
图片如下（显示一部分）：
untitled
题目给出了提示：Lack of some bits and brute them
考点三：
Factoring with High Bits Known
这类问题，解决的办法还是要分解N。
攻击条件：
当我们知道一个公钥中模数N的一个因子的较高位时，我们就有一定几率来分解N。
解密的脚本在本人的github网站上
解密脚本如下(适用于p4达到576bit)：
from sage.all import *
import binascii
n = 0x.... # 此处为16进制数
p4 =0x.... #p的高位 16进制
cipher = 0x 密文
e2 = 0xf93b
pbits = 1024
kbits = pbits - p4.nbits()
print p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:
p = p4+int(roots[0])
print "p: ", hex(int(p))
assert n % p == 0
q = n/int(p)
print "q: ", hex(int(q))
print gcd(p,q)
phin = (p-1)*(q-1)
print gcd(e2,phin)
d = inverse_mod(e2,phin)
flag = pow(cipher,d,n)
flag = hex(int(flag))[2:-1]
print binascii.unhexlify(flag)
这里要注意一下：p4必需要达到576bit。
脚本是用sage编写的。
以下说一下我对解密过程的理解：
解密函数：
多项式模方程小根
PR.<x> = PolynomialRing(Zmod(n))
生成一个以x为符号的一元多项式环。
f = x + p4
定义求解的函数
roots = f.small_roots(X=2^kbits, beta=0.4)
多项式小值根求解及因子分解
X：表示求解根的上界
目前RSA解密最好的方法仍然分解N，通过构建一个多项式的时间算法来达到RSA分解因子的目的。
shor 在1944年提出一种算法可以在N长度的多项式时间和空间内解决因式分解的问题，提出用量子图灵机模型代替图灵机模型。但是这个种方法至今人仍不清楚拥有充分大寄存器的量子计算机可被构造。
最终出现了另一种研究方法，为了实现多项式时间的复杂度，不得放宽RSA和分解因子的问题的条件。通过限制例子的参数到一个比一般的情况下小的区间上。但指数的大小不变。把这种约束的例子，把他们模化成多项式等式，然后进行求解。
RSA分解问题是输入N找到p，q的问题。他可以用被以下多项式来模化：
1506392137(1).png
多项式的整数根是：
Paste_Image.png
假设 p,q是相同比特长度，找到绝对值小于
所有正数的解，就可以解决分解因子的问题。我们只需要找到小值根。这里的小值根指根的大小比多项式的系数小。自然的可以定义x，y各自的上界X，Y最终目标是找到只要
就符合多项式时间算法的条件。因为我们不知道如何达到这个界,所以将分解因子问题放宽。
打字太费劲
这里重点就放在了
以上如果成立，我们就可以在多项式时间内找到该问题的解
这里使用了Coppersmith算法：
他的用途主要是找到多项式方程小值根,该求根算法本质上基于Lenstra，lenstra和lovasz给出的著名的LLL约化基算法,
Coppersmith的工作掀起了密码学界研究格基约化的热潮，他提出了利用LLL 算法求解非线性低维度多项式方程小根的方法。
Coppersmith的结论不同于传统的格基约化在密码分析中的应用方法。第一，他的结论是在非线性的情况下考虑的，而传统的方法通常是线性的；第二，若将 Coppersmith 的攻击方法推广到多变元的情况，则该方法是启发式的。也就是说推广后的结论依赖于一个假设条件，但是该假设条件在实际应用中基本可以得到满足。
Coppersmith算法的意义
关键思想是将有小值解的多项式方程编码成有小范数的向量系数。那些向量系数可以使用LLL约化基算法的应用程序。找到格基约化算法的一个重要的应用是寻找低指数多项式方程的小值根,这包含单变量多项式方程、双变量多项式方程及多变量方程。
为了求解多项式效果创造了前提条件
把多变元模方程求解小跟的问题转化成了切结具有相同根的整系数多项式问题
求解多项式小根的值主要依据的定理如下：
定理1
定理2
定理3，4
因子分解:
我们可以应用上面的技术到因子分解问题,当我们已知其中一些因子的高位比特,就可以分解该整数.
多项式时间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
例如：时间复杂度为O(nlog(n))、O(n^3) 的算法都是多项式时间算法，时间复杂度为O(nlog(n))、O(n!)、O(2n)的算法是指时间算法。
个人理解：如果在多项式时间内能够解出问题，则这个算法是可以接受的，若不能在多项式时间内解出问题。是不可以接受的，多项式小根值的求解方法，利用构造限制和条件，让问题的求解方法能够达到多项式时间之内。如何构造这里就使用格基规约方法
本人没有找到两个因子分解的例子，先用三个因子分解例子来说明：
证假设我们知道N=PQR中P，Q的
比特，
,通过除法我们知道的R前的
比特。
定义多项式：
格：
格是n维空间中一系列离散的点集合。最早的数论和结晶学的研究中，格基约化的是找一些具有良好性质的格基。比如，相对较短基或者几乎正交的基。
LLL 算法的意义：
该算法可以在多项式时间内得到一个向量长度近似与最短向量的格基。
LLL 算法是第一个具有实用价值的求格中短向量的多项式时间算法。
LLL算法描述
通过LLL算法，放宽严格正交的条件。我们可以的到相同近似的正交基。
LLL 约化基
下面给出算法流程，该算法是多项式时间算法。实际运用的时间复杂度小于理论时间复杂度。
LLL算法流程
Coppersmith
Coppersmith的工作掀起了密码学界研究格基约化的热潮，他提出了利用
LLL 算法求解非线性低维度多项式方程小根的方法。
他将方程求解小根的问题转化成具有相同根整系数多项式的的问题。
Howgrave-Graham
利用 Howgrave-Graham提出的一个定理，可以完善Coppersmith寻找m模方程根的思想。
满足定理内的两个条件，我们就能找到h(x)=0方程的根。
下面我们解决的问题是如何寻找h
为了找到多项式 h(x) ，它的系数满足 Howgrave-Graham 的界，可以使用格和格基约化的方法。
上面使用格和格基约化和LLL约化的算法，使h(x)=r1(x)一定满足Howgrave-Graham 的界
变换多项式的目的：构建的格Ｌ满足一个好的界
这里如果要详细介绍 就去找LLL算法在RSa安全性与分析中的应用
2.4节。
LLL 算法求解非线性低维度多项式方程小根的方法。LLL 算法求解任意维数的格中近似最短的向量。
coppersmith.sage
coppersmith.sage代码实现，这个程序中存在以下代码，我们对他们的内容进行稍加说明和解释：
beta = 0.5
dd = f.degree()
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
这里说明下，参数的的大小选泽，比如beta=0.5，epsilon = beta / 7。是可以根据具体情况，可以进行调整的，这里为什么会选择这样的参数。这是因为Coppersmith’s method的定理所选出的，这里证明方法本人没有看。（有时间的话在进行补充）
beta =0.5 我猜测是因为因式分解的因子必须相等。固采用0.5
dd：表示多项式的最高次幂
espilon：这里是自己选取的，目的是选取一个很小的量
mm表示最小整数
t：个人理解表示找到方程所有根的多项式时间
xx：用于构造一个界为xx的基格B
方程小根求解算法
这个有点难度，本人确实理解起来有些费劲，若有什么问题，请大家给予一定的帮助，并进行指正。这样也帮助本人能够更好的理解学习。
参考文献：
1.求多项式方程的小值解及其应用
2.LLL算法在RSA安全性分析中的应用
3.格基约算法并行化及应用研究
4.格基规约理论及器在密码设计中的应用
5.模_q的RSA体制的密码分析--端时立
6.方程小根值求解公式
7.最小多项式
8.Factoring with High Bits Known (刘大佬)
9.sage环境运行网站1
10.sage环境运行网站2
11.【CTF 攻略】第十届全国大学生信息安全竞赛writeup
12.【CTF攻略】FlappyPig HCTF2016 Writeup
13.湖湘杯 writeup
14.md公式转化
