HZNUCTF2024
HZNUCTF2024
ez_encode
cyberchef 一把嗦了
sign-up
1 | from gmpy2 import * |
其中q=next_prime(p+(p>>500))
指的是:$ q= [p+\frac{1}{2^{500}}p] +r $
即 $ q = [(1+\frac{1}{2^{500}}p] +r $, r是为了将q凑为质数的整数。
$ \therefore n = p\ast q = [(1+ \frac{1}{2^{500}})p^2]+rp$
$ \therefore (1+\frac{1}{2^{500}})n = ((1+ \frac{1}{2^{500}})p)^2 + (1+\frac{1}{2^{500}})rp > ((1+\frac{1}{2^{500}})p)^2 ——①$
$\because q^2 = [(1+\frac{1}{2^{500}})p + r]^2 = ((1+\frac{1}{2^{500}})p)^2 + 2[(1+\frac{1}{2^{500}})rp] + r^2 ——②$
易知,②式大于①式
$\therefore 经过比较得 [(1+\frac{1}{2^{500}})p]^2 < [(1+\frac{1}{2^{500}})n]< [(1+\frac{1}{2^{500}})p + r]^2$
通过开方缩小范围得
$(1+\frac{1}{2^{500}})p < \sqrt{(1 + \frac{1}{2^{500}})n} < (1+\frac{1}{2^{500}})p +r = q $
所以,$\sqrt{(1+\frac{1}{2^{500}})n}$的下一个素数即为q
q = next_prime(iroot((n + (n >> 500)), 2)[0])
ez_rsa
1 | from Crypto.Util.number import * |
根据题目得到一个关于k的多项式方程组
用sage求解多项式
1 | var('k') |
即可求得k,再求得p,q解一般rsa即可
你知道什么叫第二重要极限吗?
你知道什么叫做第二重要极限吗?
其中
1 | a_i = [1,9,9,8,4,6,1,9,9,4,8,1,4] |
使用在线工具求得极限后md5加密即可