模数为质数的多元一次模方程，线性同余生成器（LCG）
\[有若干a*x_n+c=y_n\bmod b，已知x_n,y_n\\a*x_0+c=y_0\bmod b，a*x_0+c=k_0*b+y_0\\a*x_1+c=y_1\bmod b，a*x_1+c=k_1*b+y_1\\两式相减：a*(x_1-x_0)=(k_1-k_0)*b+(y_1-y_0)(1)\\同理，a*(x_2-x_1)=(k_2-k_1)*b+(y_2-y_1)\\乘系数相减消元得：(x_2-x_1)*(y_1-y_0)-(x_1-x_0)*(y_2-y_1)=z*b\\因此，最少只需要4组等式（数量越多越精确），即可以通过对等式左边求最大公约数，求得b\\依据是根据数论：如果几个随机数分别乘以n，则这几个结果的最大公约数很可能是n\\对上式(1)，a=(y_1-y_0)*invert(x_1-x_0,b)\\最后，(y_0-a*x_0)\bmod b求得c\]sample：guess_game，网鼎杯-2020朱雀组
已知步长为2的连续值：S1,S3,S5，可通过S5-S3 ≡ (S3-S1)*a^2 % m`，再通过Tonelli–Shanks算法求模平方根。
线性递归函数（linear recurrence function）
sample：sequences，picoctf-2022；easywork，wangdingcup-2022白虎 \(根据递归公式，构造矩阵乘法公式：\\ f_1=\left[ \begin{matrix} 0\\ 1\\ 0\\ \end{matrix} \right] \left[ \begin{matrix} c & 0 & 0\\ a & b & n\\ 0 & 0 & 1\\ \end{matrix} \right] \left[ \begin{matrix} c\\ 1\\ 1\\ \end{matrix} \right]，进而得到：\\ f_n=\left[ \begin{matrix} 0\\ 1\\ 0\\ \end{matrix} \right] \left[ \begin{matrix} c & 0 & 0\\ a & b & n\\ 0 & 0 & 1\\ \end{matrix} \right]^n \left[ \begin{matrix} c\\ 1\\ 1\\ \end{matrix} \right]\\\)
方法1：借助sage的矩阵模幂运算
1 | |
方法2： \(对于矩阵M，构造对角矩阵D及对应矩阵P，满足：M=PDP^{-1}，\\ M^2=MM=PDP^{-1} PDP^{-1} = PDIDP^{-1}=PD^2P^{-1}\\ M^n=...=PD^nP^{-1}\)
1 | |
注意：当i太大时，计算i次幂会耗费太多时间，需要借助gmpy2.mpz，且最后结果直接参与取模计算，不要直接打印出来，否则会由于调用str转换耗费太多内存而失败。
1 | |
求离散对数（求指数）
1 | |
多项式相关
（1）明文为x，不同系数的两多项式，通过gcd(f,g)，求公因式（x-m），即为明文。sample：rotoRSA，rarctf-2021（http://www.zbc53.top/archives/143/）。
def gcd(g1, g2):
if g2==0:
return g1.monic() #monic首项为1
else:
return gcd(g2,g1%g2)
（2）有限域开根（求底数）：
R.<x> = PolynomialRing(Zmod(p))
f = x ^ e - c
sol = f.monic().roots()
if (len(sol) != 0):
（3）同上，模N开e次方：m**e = c mod N
m = Zmod(N)(c).nth_root(e, all=True)
（4）解模方程：
R.<a>=Zmod(b)[]
f=2021*a**3 + 2023*a**4 - 2022
f.roots()
（5）解方程：
x, y = var('x, y')
solve([x+y==6, x-y==4], x, y, solution_dict=True)
solve_mod([e*d0*X - k*(n*X-n-X*X*X + X*X) == X], N)
（6）在[0, pi/2]之间寻找方程解：
phi = var('x')
find_root(cos(x)==sin(x),0,pi/2)
（7）多个未知数，通过coppersmith求最小根。sample：hamburgerRSA，meituan-2021；Hamul，cryptoctf-2021（https://blog.maple3142.net/2021/08/01/cryptoctf-2021-writeups/）
PZ = PolynomialRing(Zmod(100 * n + 1), "p,q")
small_roots(f, (2 ^ 65, 2 ^ 65), m=7, d=3)
（8）有理域解方程：
X = polygen(RealField(2048))
f =X*((gift<<400)-X) - N
P_high = int(f.roots()[0][0])
（9）取多项式系数列表：
pol.list()
多项式乘积分解
sample：MidCrypto，xiangshan-2021；RaRctf-2021
a=[]
s=0
for i in range(1,17):
x=(N%(M**i)-s)//(M**(i-1))
a.append(x)
s+=x*M**(i-1)
PR.<x> = PolynomialRing(ZZ)
f=0
for i in range(len(a)):
f+=a[i]*x^i
print(f.factor())
佩尔（Pell）方程
I型Pell方程
\(型如：x^2-dy^2=1的二元二次不定方程，当d为平方数：x^2-dy^2=(x+\sqrt d)(x-\sqrt d)=1\Rightarrow x=1,y=0\\ 当d不为平方数时：称(x_0,y_0)为基本解，是满足方程的所有正整数解中使得x+\sqrt d最小的一组解（通过连分数或暴力方式求得）\\ 所有正整数解满足：x+y\sqrt d=(x_0+y_0\sqrt d)^n\\ 用矩阵表示为：\left(\begin{matrix}x_n\\y_n\\\end{matrix}\right)=\left(\begin{matrix}x_0&dy_0\\y_0&x_0\\\end{matrix}\right)^n\left(\begin{matrix}x_0\\y_0\\\end{matrix}\right)\\ 证明：若(x_1,y_1)，(x_2,y_2)是一组解，则\\ x_1^2-dy_1^2=1,x_2^2-dy_2^2=1\\ 两式相乘得(x_1^2-dy_1^2)(x_2^2-dy_2^2)=1\\ 展开配方得：(x_1x_2+dy_1y_2)^2-d(x_1y_2+y_1x_2)^2=1\\ 说明(x_1x_2+dy_1y_2,x_1y_2+y_1x_2)也是一组解，用矩阵表示即为上式\) 基本解通过连分数求得 \(x^2-dy^2=s，若s<\sqrt d，则\frac{x}{y}是\sqrt d的渐进分数\\ 证明：对于s>0，x^2-dy^2>0，有x>y\sqrt d，由x^2-dy^2=s，有x-y\sqrt d=\frac{s}{x+y\sqrt d}\\ |\frac{x}{y}-\sqrt d|=\frac{x-y\sqrt d}{y}=\frac{s}{y(x+y\sqrt d)}<\frac{s}{2y^2\sqrt d}<\frac{1}{2y^2}，满足定理2（勒让德判别法）\\ 对于s<0，做变换：x'=y,y'=x,d'=1/d,s'=-s/d，则等价于上面s<0情况，同理。\)
II型Pell方程
\(型如：x^2-dy^2=-1的二元二次不定方程\\ 所有正整数解满足：x+y\sqrt d=(x_0+y_0\sqrt d)^{2n+1}\)
广义Pell方程
\[型如：x^2-dy^2=c，基本解不止一组\\ 取I型Pell方程的基本解为(x_0,y_0)，广义Pell方程的其中一组基本解为(x_1,y_1)\\ 这组基本解确定的解系为：\left(\begin{matrix}x_n\\y_n\\\end{matrix}\right)=\left(\begin{matrix}x_1&dy_1\\y_1&x_1\\\end{matrix}\right)^{n-1}\left(\begin{matrix}x_0\\y_0\\\end{matrix}\right)\]组合数C(m,n) % p，卢卡斯定理
\[\left(\begin{matrix}m\\n\\\end{matrix}\right)=\left(\begin{matrix}m/p\\n/p\\\end{matrix}\right)\left(\begin{matrix}m\mod p\\n\mod p\\\end{matrix}\right)\mod p=\prod_{i=0}^k\left(\begin{matrix}m_i\\n_i\\\end{matrix}\right)\mod p\\ 其中m_i,n_i是m，n的p进制展开：m=m_kp^k+m_{k-1}p^{k-1}+...+m_1p+m_0\]x^3 + y^3 + z^3 = k，立方和
\[(9t^4)^3+(3t-9t^4)^3+(1-9t^3)^3 = 1\\ (1 + 6t^3)^3 + (1 - 6t^3)^3 + (-6t^2)^3 = 2\]a^2 + b^2 = n
sample：Ferman，CryptoCTF-2021
\[1.得到n的因式分解\\ 2.得到对于素数p=4k+1的方程解：a^2+b^2=p\\ (1)挑一个模p的非二次剩余x，使得x^2=-1\mod p\\ (2)对p和x做辗转相除，求到第一次遇到结果小于\sqrt p,结果即为问题的解\\ 3.将步骤2的解用等式组合：\\ (a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2=(ac-bd)^2+(ad+bc)^2\]或者通过sage：a, b = two_squares(n)
Goldwasser-Micali (GM) 加密
安全性依赖于从合数模n=pq的二次非剩余中区分二次剩余困难性假设。加密： \(n=p*q，选取r，满足J\left(\frac{r}{p}\right)=J\left(\frac{r}{q}\right)=-1\\ 对于明文二进制流每一个m_i，选取一个x_i\in [1,n-1]，计算c_i=r^{m_i}*x_i^2\mod n\) 直接计算J(c/n)都是1，只有解密方知道n=pq方可解密。解密： \(求J\left(\frac{c_i}{p}\right)与J\left(\frac{c_i}{q}\right)，都为1（c_i是模n的二次剩余），m_i=0，都为-1，m_i=1\)
基于密钥的凯撒密码Keyed Caesar
利用一个密钥，将密钥的每一位转换为数字（一般转化为字母表对应顺序的数字），分别以这一数字为密钥加密明文的每一位字母。sample：XMan一期夏令营分享赛宫保鸡丁队Crypto-100
1 | |
解密工具：JPK，可解带密钥与不带密钥。
二分查找
sample：noise，D^3CTF-2019
访问一个黑盒函数不超过50次：给定一个非负整数x，返回f(x) = (x + r) mod n，r是一个每次都重新生成的随机数 (1000 bits)。求n(1024 bits)。 \(假设已有[L, R]满足n \in [L, R]。如果可以找到一对(I, t)对于所有可能的n和r都满足：\\ f(I) = (I + r) \bmod n = I + r - tn\\即tn = I - f(I) + r，那么显然I - f(I) + r是t的倍数，它的范围只和r有关。所以可得n的新区间：\\ n = \frac{I - f(I) + r}{t} \in \left [ \frac{I - f(I) + r_{\min}}{t} , \frac{I - f(I) + r_{\max}}{t} \right ]\\ r的范围是\left [0, 2^{1000} \right ]。令s = r_{\max} - r_{\min} = 2^{1000}，则上述区间长度大约是\frac{s}{t}。\\现在的问题就转化为如何选取一对合适的(I, t)并且t尽可能大，这样得到的新区间就尽可能小。回到一开始的假设上，\\\forall r \in [0, s], n \in [L, R], \quad tn \leq I + r < (t+1)n\\即(tn - r){\max} \leq I < ((t + 1)n - r){\min}\\ 则有(tn - r){\max} = tR \quad < \quad ((t + 1)n - r){\min} = (t + 1)L - s\\ \Leftrightarrow \quad tR \leq (t + 1)L - s - 1 \Leftrightarrow \quad t \leq \frac{L - s - 1}{R-L}\\只要t满足这个条件，我们就可以找到对应的I。除此之外，因为t参与除法，所以还有一个下界t\geq 1，\\由此我们可以得到对L, R的限制条件:1 \leq t \leq \frac{L - s - 1}{R-L} \quad \Rightarrow \quad 2L\geq R + s + 1\\有两种方法来设置合法的初始[L, R]：\\1.直接假设n落在\left [2^{1023}, 2^{1024} \right ]（这样的概率大约是 50\%，所以如果假设不成立就多试几次）\\2.二分查找（这是一种很显然的方法，详见 exp）\\综上所述，首先选取一对L, R作为n的初始范围。\\然后令t为最大值\frac{L - s - 1}{R-L}，并在区间[tR, (t + 1)L - s - 1]中选择一个I\\由此可得新区间n \in \left [ \left \lceil \frac{I - f(I)}{t}\right \rceil, \left \lfloor \frac{I - f(I) + s}{t}\right \rfloor \right ]\\更新 [L, R]的值重复上述过程。n的范围跨度从\Delta \sim R-L缩小到\Delta' \sim \frac{s}{t}\\有\Delta' \sim \frac{s}{t} \sim \frac{s(R-L)}{L-s-1} \sim \frac{s\Delta}{L-s} \sim \frac{s\Delta}{n}\\所以迭代次数大约是\log_s n，一般在 45 次左右（同样如果一次不行，就多试几次）\\FYI：如果直接做一些假设（譬如假设n落在某个范围，令I = tR等等），可以省略掉一些繁琐的步骤得到一些更简单但需要多试几次的做法。\)
Okamoto-Uchiyama密码系统
sample：dislogAgain，工业互联网-2020
加密：
1 | |
解密：
1 | |
Paillier Crypto加密算法
sample：CSTPC, yangcheng-2020
加密：
1 | |
解密：
1 | |
与模数不互质，无法直接求逆元
sample：Beginner’s crypto，TSGctf-2020。 \(f * 2^{10000}=r\bmod 10^{175}\\f*2^{10000}=2^{175}*(r/2^{175})\bmod 10^{175}\\f*2^{10000}=x*10^{175} + 2^{175}*(r/2^{175})\\f*2^{9825}=x*5^{175}+(r/2^{175})\\f*2^{9825}=(r/2^{175})\bmod5^{175}\\f=2^{-9825}*(r/2^{175})\bmod 5^{175}\)
pow(x, y ** e, N)，N可分解
sample：密码挑战-^o^，ctfshow-2021
1 | |
a^2-kab+b^2=1
sample：Different_RSA，gdqwb-2021
1 | |
将k=4时的数组，利用数组识别网站OEIS，识别得到数组通式： \(a_{k,0}=1\\ a_{k,1}=k\\ a_{k,i}=k*a_{k,i-1}-a_{k,i-2}\\ 通解为(a_{k,i},a_{k,i+1})\)
x^n-1
sample：RSA？，yangcheng-2021 \(x^n-1=(x-1)(x^{n-1}+x^{n-2}+...1)\\=x*(x^{n-1}+x^{n-2}+...1)-(x^{n-1}+x^{n-2}+...1)\\=(x^n+x^{n-1}+x^{n-2}+...x)-(x^{n-1}+x^{n-2}+...x+1)=x^n-1\)
在DES、AES等块加密算法轮次key中隐藏信息
sample：Spy_DES，230422nssctf。借助python-encrypt，在每轮次打log查看
1 | |