N1j复现
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()) ...
e与phin互素
原理 总结一下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
一元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> =...
Sagemath
根 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...
ECC
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...
lilctf-2025-crypto
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∥≤ndet(L)n1 这个定理给出了nnn维格LLL下最短向量的长度上界。 主要用处就是决定LLL算法构造格的格大小,见下文NTRU。 还原最小多项式 原理 最小多项式的定义:设α∈F\alpha \in...
paillier cryptosystem
原理 第一种参数模式 随机选择两个大质数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(线性反馈移位寄存器)之前,我们先对它的归属有一个大致的了解,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∑ncjai+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,...
