题目
描述
1 | I love univariate polynomials... |
1 | from Crypto.Util.number import getPrime, bytes_to_long |
思路：
根据题目描述univariate polynomials（单变量多项式），题目中也是反复利用p，所以可以从p开始下手。 从 w = pow(2,f(p),n)开始，这里也是我学习中感觉非常巧妙的地方，先了解前提知识费马小定理gcd(a,p)=1,
所以w除以p的模数就为2^k, 那么
代码(错误的)
1 | from Crypto.Util.number import * |
代码报错了，检查大概知道了原因在于k的值最后是负数，所以直接2^k不行。
正确部分
1 | k = f % (x-1) |
解释：当k是负数时，
首先我们肯定都对RSA加密以及解密原理有了一定认识，比如加密的这句代码：$c=m^e\mod(n)$通过这种方式来得到我们的密文c，但是这个方法有个前提就是m必须小于于n，原因下面再提。然后再看解密，$m=c^d \mod(n)$可以通过欧拉定理来证明这个过程得到$c^d\mod(n)=m\mod(n)$,显然我们能发现如果m大于n会导致得到的密文$newm=m\mod(n)$，我们得到的是newm，而不是m，所以就不完整了，自然还原出来的明文多半就是乱码，那么如何处理这类m>n的问题就是要学习的构造格。学习参考：2024-NSSCTF-密码工坊非官方dlc-wp-crypto | 糖醋小鸡块的blog
1 | from Crypto.Util.number import * |
由题目可以知道进行了一个加密再解密的过程，最后解出来是乱码的原因也就是在于m大于n导致数据丢失了。
我们先猜测message范围是所有数字大小字母以及下划线，那么对应的ASCII码范围就在（48，128）之间，假设message长度为le，那么：
$$
m=256^{le-7}*pre+256m_0+suf
$$
(其中pre=b’DASCTF{‘,suf=b’}’,m_0为括号中间部分)。
那么就有：
$$
c=(256^{le-7}*pre+256m_0+suf)\mod(n)
$$
就能得到$m_0 \mod(n)$的值：
$$
m_0=256^{-1}(c-256^{le-7}pre-suf)\mod(n)
$$
然和记$m_0$每个字节为$s_i$从而用ascii的角度将其表示为：
$$
m_0=\sum_{i=0}^{le-9}256^{i}s_i=s_0+256s_1+256^{2}s_2+…+256^{le-9}s_{le-9}\mod(n)
$$
即可以写成：
$$
m_0=\sum_{i=0}^{le-9}256^is_i+kn
$$
就可以构造格来找目标向量:
$$
M = \left(
\begin{array}{*{7}{c}}
1 &0 &0 &0 & 0& 0& 1\\
0& 1 & 0& 0& 0& 0& 256\\
0& 0& \ddots & 0&0 &0 & \vdots\\
0& 0&0 & \ddots & 0&0 & \vdots\\
0& 0& 0& 0& 1 & 0& 256^{le-9}\\
0& 0& 0& 0&0 & 1 & -m_0\\
0&0 & 0&0 & 0&0 & n\\
\end{array}
\right)
$$
有:
$$
(s_0,s_1,…,s_{le-9},1,k)*M=(s_0,s_1,…,s_{le-9},1,0)
$$
这样解出来的向量预期就在48-128之间，范围太大了结果肯定不太行，优化方法就是令:
$$
t_i=s_i-88
$$
这样目标向量范围就为（-40，40）可以解了。
1 | from Crypto.Util.number import * |
由于此题不知道长度所以找了一个范围进行遍历求解，然后找出有意义的输出
好久好久没有更新博客了😭最近确实懈怠了一点，还有就是在了解一些web方向的内容所以密码看的比较少了。还是进入今天的正题吧，如标题所见是对coppersmith的一些学习记录。具体原理也不用深究做几道题熟悉一下脚本直接往上代数据就好了。以下是几个一元的脚本模板。
1 | # 已知 N 和 p 的高位 p_high，缺失 kbits 位 |
这里以2025-L3HCTF的math_problem为例
1 | import gmpy2 |
思路：首先由hint1和n取最大公因数可以解出r（虽然这个时候把r当成n来用，$\phi(n)=r-1$,用rsa就直接可以解出来了，算是非预期吧）预期做法就是对hint2转换可以得到p的低400位然后coppersmith解出p从而解题。
令$k=p \mod 2^{400}$,$hint2=(1+3n)^k \mod n^3$,由二项式展开再消去带有$n^3$的因子的项化解完就是这样
$hint2 \equiv 1 + 3kn + \frac{9}{2}k(k-1)n^2 \pmod{n^3}$，$(hint2-1)//n\equiv 3k+\frac{9}{2}k(k-1)n \pmod{n^2}$,让$(hint2-1)//n=h$,然后再模n，$h \equiv3k \mod n$左右乘3的逆元就可以得到k即p的低四百位。
exp:
1 | from math import gcd |
参考https://tangcuxiaojikuai.xyz/post/146254b2.html
其中Φ的构造是一模一样的，所以直接套用脚本就解出了，后来看好像还可以通过连分数的方式解题。
1 | from Crypto.Util.number import * |
往typora插入图片，图片文件夹一定要和创建的.md文件夹放在同一个文件夹下。不然文件移动位置后图片会因找不到地址而消失
1 | 格式！[提示文字](图片地址) 即先！然后快捷键ctrl+k |
相信很多人尝试上面图片的插入方法会遇到在typora能正常显示图片，但在网页上图片却无法加载。这是因为上述地址如D:\blog\source\images\Elaina.jpg为本地地址，而hexo+github搭建的博客并不能访问本地地址所以自然无法成功。
最简单粗暴的方法就是直接将图片拖到typora中，typora会直接创建博客文章同名的文件夹存放图片。但是就是感觉文章写多了有点乱乱的。
说来也巧本以为早就解决了图片的问题结果又出现了，这次经过更长时间捣鼓得出结论上面例子里的【提示文字】不能为纯数字不然部署到GitHub上就被认定为width而不是title导致图片无法加载。
前言：因为程序设计的作业要用到easyx图形库，又因为本人习惯用vscode,所以尝试在vscode中安装easyx但是路途确实有点艰辛，虽然最后回顾过程其实也很简单。
参考https://codebus.cn/bestans/easyx-for-mingw。
下载网址中的压缩包然后按照网址所说将压缩包中include的头文件和lib64的库文件拷贝到mingw的头文件和库文件中。
链接选项增加：-leasyx，这样可以在编译的时候链接 libeasyx.a 库文件。
在tasks.json中添加即可
这里以本人遇到一个问题为例子，本来按照教程将对应的文件复制到对应位置后就可以了但是却依然有问题如下图
现在我们尝试测试一个代码结果发现找不到这个文件。但是上图中可以看到iostream是可以被找到的，那么我们只要找到这个文件存放的位置再把easyx.h这个文件也放到相同文件夹即可。按住ctrl然后鼠标点击iostream就可以找到具体位置
如图所示我们找到该文件位置后再添加easyx.h就不报错了（话说这时候才发现自己的怎么是MSVC怪不得前面一开始不行😢，一直以为是mingw不过没什么关系。
最后也是成功运行，接下来就可以进行后续的一些工作了。
一开始也是照着博客以及ai一顿捣鼓，最后终于完成还是很开心的，通过这次也对这些头文件貌似有了更深入的一些了解，也有了更多相关经验，以后也会继续探索学习。
以ISCTF2024crypto蓝鲨的费马这道题为例子讲解自己学到的一个解决方法
1 | import libnum |
$1.\text{leak} = d + p + q$ 其中 leak 简写为 L
$2. m = \text{pow}(c, d, n)，即 m = c^d \mod n.$
$3.d = L - (p + q) .$
根据欧拉函数的定义：$\phi = (p - 1)(q - 1) = pq - p - q + 1$
由于 n = pq ，因此：$\phi = n + 1 - (p + q)$
根据欧拉定理:$c^\phi \equiv1 \mod n$
代入 $\phi$的表达式：$c^{n + 1 - (p + q)} \equiv 1 \mod n$
可以进一步推导：$c^{n + 1} \equiv c^{p + q} \mod n$
因此:$c^{n + 1} \equiv c^{p + q} \mod n$
已知 d = L - (p + q) ，代入 $c^d \mod n = m$ ：
$c^{L - (p + q)} \mod n = m$
根据前面的推导：$c^{n + 1} \equiv c^{p + q} \mod n$
因此：$c^{L - (n + 1)} \mod n = m$
$m = \text{pow}(c, L - n - 1, n)$
1 | c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997 |
dp=d mod (p-1)
dq=d mod (q-1)
因为$\phi(n)=(p-1)*(q-1)$,这里也出现了（p-1）所以这几个存在一定的联系，一旦泄露可能会造成安全隐患。
题目部分数据
1 | import gmpy2 as gp |
同样先进行推导，化简成为一个可以靠程序解决的式子。
1.dp=d mod(p-1)
2.两边同乘e,$dpe \equiv de \mod(p-1)$
3.$ed =k_1*(p-1)+dpe,而ed \equiv 1 \mod \phi(n),\phi(n)=(p-1)(q-1)$
4.$k_1*(p-1)+dpe = 1+k_2(p-1)*(q-1)$
5.接下来就合并同类项解方程
6.化简得$dp*e=(k_2(q-1)-k_1)(p-1)+1$,令$k_2(q-1)-k_1=X$
7.$dp*e=X(p-1)+1$,首先dp<(p-1),所以X<e.
8.$p-1=\frac{dp*e-1}{X}$,因为X的范围已知直接遍历爆破即可求出p-1的值从而后续就变为常规RSA问题了
exp:
1 | import gmpy2 as gp |
原谅我太懒了，懒得推导了直接脚本拿来用得了。
1 | from gmpy2 import * |
在做题时遇到离散对数问题中碰到很多CRT相关知识，但最初了解比较浅显，现在准备再稍微细致的回顾一下。
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中$n_1$ $n_2$ ······$n_k$ 两两互质)：
$$
\begin{cases} x\equiv a_1 \pmod{n_1}\\ x\equiv a_2 \pmod{n_2}\\ x\equiv a_3 \pmod{n_3}\\ ·····\\ ·····\\ ·····\\ x\equiv a_k \pmod{n_k} \end{cases}
$$
a.计算$m_i=n/n_i$;
b.计算$m_i在模n_i意义下的逆元m_i^{-1}$; 逆元$m_im_i^{-1}\equiv 1\pmod{n_i}$
c.计算$c_i=m_im_i^{-1}$
1 |
|
当然了上述代码可能更多用于算法题中，密码学里python有很多强大的库可以直接调用CRT
1 | from sympy.ntheory.modular import crt |
虽然说密码学里直接秒了，但我还是觉得搞清背后逻辑会更有理解。
$当i\neq j时，有m_j\equiv 0 \pmod{n_i}$
$这是因为m_j=n/n_j$
$所以c_j \equiv 0 \pmod{n_i},c_i\equiv 1 \pmod{n_i} $
$ x \equiv \sum_{j=1}^{k}{a_jc_j} \equiv a_ic_i\equiv a_i\pmod{n_i}$
$对于任意的i的取值均符合x\equiv a_i \pmod{n_i}$
所以上述方法可行
部分密码题目复现，后续应该会把没复现的几道题补上吧（或许吧
1 | c=670610235999012099846283721569059674725712804950807955010725968103642359765806 |
简单的RSA，借助yafu对n进行质因数分解得到多了质数p1,p2,p3等。那么phi=（p1-1)(p2-1)(p3-1)·····
后续就正常RSA那一套解就好了。flag:TGCTF{f4888_6abdc_9c2bd_9036bb}
1 | from math import gcd |
思路：flag拆成两部分，分别求出前后两部分然后合并即可。
前半部分知道p和q也知道e的大致范围（相对来说比较小）直接爆破即可，后半部分e很小可以进行爆破。
代码：
前半部分
1 | from sympy import primerange |
后半部分：
1 | from sympy import primerange |
1 | from flag import FLAG |
Franklin-Reiter 相关消息攻击 两个密文对应的消息存在线性关系.
1 | from Crypto.Util.number import long_to_bytes |
咕咕咕，后续这题应该不搞了，大概去看LCG相关的题学习一下就好了
咕咕咕，这题emmmm也不搞了吧，学习一下p的低位泄露然后就过。后续应该放在RSA中leak问题那篇文章中
这是我的第一个博客
懒惰的我终于开始初步学习密码学中格的相关内容了，虽然很早之前就看过了，但是由于东西实在是太多了根本看不下去，看了也不理解。现在再次开始密码学之路，这篇文章算是边学边理解的感悟吧。
经过学长的点明后，对于我目前学习最初步的格来说就把格理解为线性向量，把线性代数的知识运用上去，无非就是换了很多全新的名词，本质上按线性向量去理解会轻松很多。所以说还是要有一定线代基础不然还是很难接受（但线代本身也确实很抽象😢）
目前看过来分为svp（shortest vector problem）最短向量问题和cvp（closest vector problem)最近向量问题。两个名字看中文感觉就是一回事最短和最近，但事实上区别很大。
感觉正式讲法很难理解，我自己想法就是格中有一组基向量【b1，b2】以及很多点，要通过基向量找到一个点，使得这个点离原点最近，而λ1就是最短向量。有时候因为基的点分布并不理想，很多时候找出来的是最短向量λ1的倍数，这就是svp的宽松版本了。
在基中找一个点t，找到距离这个点最近的格点。换句话理解就是找到一个向量λ1使得t向量（蓝色线）与λ1相减后得到的向量μ最短。同样存在cvp的宽松版本，如图中2μ，只不过目前我对于宽松版本还未很好理解。
嗯感觉这个原理非常复杂，想理解目前水平做不到，差不多想就是LLL是一个格基约化算法，作用是将上面图片中格变得更加整齐（就是把图中倾斜绿色点变得和坐标轴一样整齐）。反正目前做一些初步题大概就是按题目意思构造一个合理的格然后对格直接用LLL.( )会得到一个短向量，然后从这些向量中可以找到我们需要的，然后差不多就可以解出题目。所以不需要理解直接用吧😢然后顺带提一下BKZ算法，也是理解为更高级的LLL，直接用别管原理什么的。