Yui's Blog

sign the ca7s 这题跟sign in the ca7s是一模一样的，但是多一个level3，所以只贴这一道题。 题目 1234567891011121314151617181920212223242526272829303132333435363738394041424344from Crypto.Util.number import bytes_to_longfrom hashlib import md5import osFLAG = os.environ.get("FLAG", "flag{**redacted**}")E = EllipticCurve(GF(0x1337_ca7_eae368ff5d702e6067aaaa77ca_ca7_1337), [0, 3])G, n = E(1, 2), E.order()def sign(priv, ctx, msg): k = bytes_to_long(ctx + md5(str(priv).encode() + msg).digest()) ...

原理 总结一下RSA问题中gcd(e,φ(n))≠1gcd(e,\varphi(n)) \neq 1gcd(e,φ(n))​=1的情况。 令gcd(e,φ(n))=bgcd(e,\varphi(n)) = bgcd(e,φ(n))=b，e=a⋅be=a \cdot be=a⋅b，那么aaa与φ(n)互素\varphi(n)互素φ(n)互素，可以求得aaa的逆元ddd。 mab≡c(modn)cd=mabd≡ma(modn)m^{ab} \equiv c \pmod{n} \\ c^{d} = m^{abd} \equiv m^a \pmod{n} mab≡c(modn)cd=mabd≡ma(modn) 这个时候对mam^ama的结果在模nnn意义下开aaa次根号即可。这里通常aaa比较小，否则需要考虑+k⋅n+ k \cdot n+k⋅n然后再开aaa次根号。 还有一种特殊情况就是gcd(e,φ(n))=egcd(e,\varphi(n)) =...

一元Coppersmith 1f.small_roots(x=x0,beta=beta0,epsilon=epsilon0) 这个函数是处理整数环/模数环上首一多项式的f(x)=0f(x)=0f(x)=0的问题，能返回满足条件的小根。 m泄露 123456R.<x> = PolynomialRing(Zmod(n))f = (m_high + x)^e - cm_low = f.small_roots(X=2^mbits,beta=1)[0]#mbits就是m泄露的位数m = int(m_high + m_low)print("m =",m)print(long_to_bytes(m)) 参考的方程就是me−c≡0(modn)m^e-c \equiv 0 \pmod{n}me−c≡0(modn)。如果是mmm低位泄露等情况构造核心就是mhigh+x⋅2k+mlowm_{high}+x \cdot 2^{k}+m_{low}mhigh​+x⋅2k+mlow​。 p泄露 1234567P.<x> =...

根 nth_root() 求解xm=kx^m=kxm=k 123#x=k.nth_root(m)x=27.nth_root(3)x = mod(27, 2^120).nth_root(3) 这里也可以构造多项式求解,处理模下的问题时就把ZZ换成Zmod(n)而且要multiplicities=False，就是不需要计算重数。 123P.<x>=PolynomialRing(ZZ)f=x^m-kx=f.roots(multiplicities=False) 线性代数 charpoly() 可以返回矩阵MMM的特征多项式。 1x=M.charpoly().roots(multiplicities=False) 和roots()函数结合就可以直接求得特征值。 eigenvectors 可以返回矩阵MMM的特征值，特征向量，几何重数，分为eigenvectors_right()和eigenvectors_left() 1x=M.eigenvectors_right() 返回MMM的右特征向量也就是Mv=λvM v =\lambda...

Smart Attack 适用于p=E.order()p = \text{E.order()}p=E.order() 脚本 123456789101112131415161718192021222324def SmartAttack(P,Q,p):#Q==k*P E = P.curve() Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ]) P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True) for P_Qp in P_Qps: if GF(p)(P_Qp.xy()[1]) == P.xy()[1]: break Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True) for Q_Qp in Q_Qps: if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]: break ...

定义 对与ppp剩余系中的aaa,若存在xxx满足 x2≡a(modp)x^2 \equiv a \pmod{p} x2≡a(modp) 则称aaa是模ppp的二次剩余,否则就称aaa是模ppp的非二次剩余。 性质1 在模ppp的完系中，总共有p−12\frac{p-1}{2}2p−1​个二次剩余，p−12\frac{p-1}{2}2p−1​个非二次剩余，并且二次剩余对应的xxx有x∈{1,2,⋯ ,p−12}x \in \{1,2,\cdots,\frac{p-1}{2} \}x∈{1,2,⋯,2p−1​}。 证明如下 首先我们知道 (p−k)2≡(−k)2=k2(modp)(p-k)^2 \equiv (-k)^2 = k^2 \pmod{p} (p−k)2≡(−k)2=k2(modp) 所以我们只需要考虑模ppp完系中的前p−12\frac{p-1}{2}2p−1​个数即可。下面我们证明对于集合{1,2,⋯ ,p−12\{1,2,\cdots,\frac{p-1}{2}{1,2,⋯,2p−1​中的任意两两平方模ppp都不相等。 假设存在x,yx,yx,y且x≠yx \ne...

ez_math 题目 1234567891011121314151617from sage.all import *from Crypto.Util.number import *flag = b'LILCTF{test_flag}'[7:-1]lambda1 = bytes_to_long(flag[:len(flag)//2])lambda2 = bytes_to_long(flag[len(flag)//2:])p = getPrime(512)def mul(vector, c): return [vector[0]*c, vector[1]*c]v1 = [getPrime(128), getPrime(128)]v2 = [getPrime(128), getPrime(128)]A = matrix(GF(p), [v1, v2])B = matrix(GF(p), [mul(v1,lambda1), mul(v2,lambda2)])C = A.inverse() * Bprint(f'p =...

Hermite定理 对任意nnn维格LLL，都存在一个非零向量v∈Lv \in Lv∈L，满足 ∥v∥≤ndet(L)1n \| v \| \leq \sqrt{n}det(L)^{\frac{1}{n}} ∥v∥≤n​det(L)n1​ 这个定理给出了nnn维格LLL下最短向量的长度上界。 主要用处就是决定LLL算法构造格的格大小，见下文NTRU。 还原最小多项式 原理 最小多项式的定义：设α∈F\alpha \in...

原理 第一种参数模式 随机选择两个大质数p,qp, qp,q，满足gcd⁡(pq,(p−1)(q−1))=1\gcd(pq, (p-1)(q-1))=1gcd(pq,(p−1)(q−1))=1。 计算 n=p⋅qn = p \cdot q n=p⋅q λ=lcm(p−1,q−1)=(p−1)(q−1)gcd⁡(p−1,q−1)\lambda = \mathrm{lcm}(p-1, q-1) = \frac{(p-1)(q-1)}{\gcd(p-1, q-1)} λ=lcm(p−1,q−1)=gcd(p−1,q−1)(p−1)(q−1)​ 选择随机整数ggg， 满足0<g<n20 < g < n^20<g<n2。 定义函数 L(x)=x−1nL(x) = \frac{x - 1}{n} L(x)=nx−1​ 计算 μ=(L(gλ mod n2))−1 mod n\mu = \bigl(L(g^{\lambda} \bmod n^2)\bigr)^{-1} \bmod n μ=(L(gλmodn2))−1modn 则公钥为(n,g)(n,...

LFSR 在介绍LFSR（线性反馈移位寄存器）之前，我们先对它的归属有一个大致的了解，LFSR是属于FSR（反馈移位寄存器）的一种，除了LFSR之外，还包括NFSR（非线性反馈移位寄存器）。 基本介绍 下面在有限域FpF_{p}Fp​下讨论n级LFSR： 反馈函数 ai+n=∑j=1ncjai+n−ja_{i+n} = \sum_{j=1}^{n} c_j a_{i+n-j} ai+n​=j=1∑n​cj​ai+n−j​ 既然反馈函数是一个线性变换，我们可以得知这个线性变换为 [ai+1,ai+2,…,ai+n]=[ai,ai+1,…,ai+n−1][00⋯0cn10⋯0cn−101⋯0cn−2⋮⋮⋱⋮⋮00⋯1c1][ai+1,ai+2,…,ai+n]=[a0,a1,…,an−1][00⋯0cn10⋯0cn−101⋯0cn−2⋮⋮⋱⋮⋮00⋯1c1]i+1\begin{array}{rcl} [a_{i+1}, a_{i+2}, \ldots, a_{i+n}] & = & [a_i, a_{i+1}, \ldots,...