Bigrsa

from Crypto.Util.number import *

from flag import *



n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061

n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073

e = 65537

m = bytes_to_long(flag)

c = pow(m, e, n1)

c = pow(c, e, n2)



print("c = %d" % c)



# output

# c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

算是签到题，先将flag与公钥（e,n1）进行加密，再与公钥（e,n2）第二次加密。

因此我们只需要依次解密就可以了。

n1与n2存在公因数，计算一下就能够分解出pq。

Exp：

import libnum, gmpy2
n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264
p = gmpy2.gcd(n1,n2)
q1 = n1//p
q2 = n2//p
phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)
 
d1 = gmpy2.invert(e,phi1)
d2 = gmpy2.invert(e,phi2)
 
m = pow(pow(c,d2,n2),d1,n1)
flag = libnum.n2s(m)
print(flag)

Ring Ring Ring

这道题只给了IP和端口，与服务器进行交互。现在没有环境无法复现了。

大致的流程：

先hash验证
输入100组（a,b,c,d,e）使得a**4+b**4+c**4+d**4==e**2

他这里只有一条等式，没有约束abcde的其他条件，因此我们可以假设a==b==c==d

那么计算一下e=2*a**2。

但是由于需要用VPN连接服务器，所以无法使用阿里云，导致我需要在本地装python pwntools与服务器交互。但是虚拟机突然不工作了，索性直接手动。

从1开始到100。sbcd输入都相同，e取他们的平方的两倍。

100次以后得到了flag。

RSA?

这道题拿到就是一个sage文件，给了加密的逻辑，话不多说，直接分析。

import os

from Crypto.Util.number import *



flag = "GWHT{xxxxxxxxx}"

p = getPrime(256)

q = getPrime(256)

n = p*q

N = (p-1)*(q-1)

e = 65537

Mx = bytes_to_long(os.urandom(30))

My = bytes_to_long(flag)

Z1 = (Mx*My)%n

inv_Z1 = inverse_mod(Z1, n)

inv_2 = inverse_mod(2, n)

X = ((Z1+inv_Z1)*inv_2)%n

Y = My

inv_Y = inverse_mod(Y, n)

a = ((inv_Z1-X)*inv_Y)%n

D = (a*a)%n



xy = lambda (x1,y1),(x2,y2) : ((x1*x2+D*y1*y2)%n, (x1*y2+x2*y1)%n)

def getloop((x,y), e):

        ret = (x, y)

        for i in range(e-1):

               ret = xy(ret, (x,y))

        return ret



print n

print getloop((X, Y), e)

print a



# 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023

# (5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785)

# 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141

前面都是正常的RSA构造流程，从第10行开始，是需要关注的重点。

Mx = bytes_to_long(os.urandom(30))
My = bytes_to_long(flag)
Z1 = (Mx*My)%n
inv_Z1 = inverse_mod(Z1, n)
inv_2 = inverse_mod(2, n)

这里生成了一个随机数（Mx），以及flag（My）。

Z1是Mx与My相乘

我们可以发现所有的操作只要超过n的就会就会取n的模，因此我们只要设定在n的范围内，就可以使用数学公式来表达这些参数。

$inv\_Z1=\frac{1}{Z1},inv\_2=\frac{1}{2}$

X = ((Z1+inv_Z1)*inv_2)%n

Y = My

inv_Y = inverse_mod(Y, n)

$X=\frac{1+M_x^{2}M_y^{2}}{2M_xM_y},Y=M_y,inv\_Y=\frac{1}{M_y}$

a = ((inv_Z1-X)*inv_Y)%n

D = (a*a)%n

$a=\frac{1-M_x^{2}M_y^{2}}{2M_xM_y^{2}},D=\frac{(1-M_x^{2}M_y^{2})^{2}}{4M_x^{2}M_y^{4}}$

xy = lambda (x1,y1),(x2,y2) : ((x1*x2+D*y1*y2)%n, (x1*y2+x2*y1)%n)

def getloop((x,y), e):

        ret = (x, y)

        for i in range(e-1):

               ret = xy(ret, (x,y))

        return ret

这里是关键代码，定义了一个函数，并且经过65536次循环计算，最后抛出一个二元组。

一开始看到这么复杂的运算，确实会有点蒙，但是其实只要计算个两三次就会发现规律了。

$n=0,X_0=X=\frac{1+M_x^{2}M_y^{2}}{2M_xM_y},Y_0=M_y$

$n=1,X_1=\frac{1+M_x^{4}M_y^{4}}{2M_x^{2}M_y^{2}},Y_1=\frac{1+M_x^{2}M_y^{2}}{M_x}$

$n=2,X_2=\frac{1+M_x^{6}M_y^{6}}{2M_x^{3}M_y^{3}},Y_1=\frac{1+M_x^{2}M_y^{2}+M_x^{4}M_y^{4}}{M_x^{2}M_y}$

我计算到这里就看出一些规律了。

$X_n=\frac{1+M_x^{2n+2}M_y^{2n+2}}{2M_x^{n+1}M_y^{n+1}},Y_n=\frac{\sum_{i=0}^{n} M_x^{2n}M_y^{2n}}{M_x^{n}M_y^{n-1}}$

能推算到这里，答案已经很接近了。

因为代码里的条件基本都被我们推完了，接下来只需要把已知信息和我们推导出来的公式结合起来，这道题应该就结束了。

$Y_n*a=\frac{(1-M_x^{2}M_y^{2})*\sum_{i=0}^{n} M_x^{2n}M_y^{2n}}{2M_x^{n+1}M_y^{n+1}} =\frac{1-M_x^{2n+2}M_y^{2n+2}}{2M_x^{n+1}M_y^{n+1}}$

我们可以发现上面这条公式推到出来的结果和Xn很接近，因此我们可以把Xn代入得到：

$Y_n*a=\frac{1+M_x^{2n+2}M_y^{2n+2}}{2M_x^{n+1}M_y^{n+1}}-\frac{2M_x^{2n+2}M_y^{2n+2}}{2M_x^{n+1}M_y^{n+1}}=X_n-M_x^{n+1}M_y^{n+1}$

然而Yn，Xn与a都已经告知给我们了，因此我们可以求出 $M_x^{n+1}M_y^{n+1}$ 的结果。

但是到这一步其实可以发现我们求出的这个结果仅仅是 $(M_xM_y)^{65537}$ 这一结果。这不就是RSA里的m=pow(c,d,n)吗？

我预期里解到这步应该会有关于分解n的提示，或者直接得出答案，但是这步仅仅给了我们密文，因此我们需要另外找方法分解n。

然而代码中已经没有更多关于分解n的提示了，注意到生成的p和q是256位比较小，因此也许可以爆破出来。于是用yafu分解n，结果秒出。

分解得到了pq，求出Mx*My就轻而易举了。

但是flag其实就是My，我们还需要从Mx*My中提取出My。

再次回到a的那条公式。

$a=\frac{1-M_x^{2}M_y^{2}}{2M_xM_y^{2}}$

我们可以发现这条公式的Mx和My不是齐次的。因此通过移项可以将一个My提取出来。

$M_y=\frac{1-M_x^{2}M_y^{2}}{2M_xM_y*a}$

最终可以得到My的值，也就得到了flag。

Exp:

import libnum, gmpy2
n = 13390709926509813526471364597371124446888078365567927211781799241724742352679484983709219580483800891886832613684875066109177882219522305348565532970795023
p = 115718235064789220654263009993128325569382592506655305434488398268608329541037
q = n//p
e = 65537
Xn, Yn = 5404548088049249951619519701935576492239293254135836357417714329205323074367876875480850741613547220698045360461761929952847796420174204143917852624050110, 2110372753170830610718226848526649992911771424441223687775304654852191999130502986109306355582366065947895295520226816523397652918227241733632791793362785
a = 1762039418842677123086894939949574689744108610561557889235294034870342076452734215004689409493802437034960516295735815195656138656970901855976802991519141
 
c = (Xn - Yn * a)%n
d = gmpy2.invert(e,(p-1)*(q-1))
xy = pow(c,d,n)
 
flag = ((1-xy*xy)*gmpy2.invert(2,n)*gmpy2.invert(xy,n)*gmpy2.invert(a,n))%n
print(libnum.n2s(flag))

张士玉小黑屋

当前位置：首页 » 《资源分享》 » 正文

2021羊城杯部分CRYPTO WP_机智的钢板的博客

6 人参与 2021年10月17日 17:23 分类 : 《资源分享》评论

Bigrsa

Ring Ring Ring

RSA?

评论（0）

赞助本站

最新文章

张士玉小黑屋

当前位置：首页 » 《资源分享》 » 正文

2021羊城杯 部分CRYPTO WP_机智的钢板的博客

6 人参与 2021年10月17日 17:23 分类 : 《资源分享》 评论

Bigrsa

Ring Ring Ring

RSA?

评论（0） 赞助本站

最新文章

2021羊城杯部分CRYPTO WP_机智的钢板的博客

6 人参与 2021年10月17日 17:23 分类 : 《资源分享》评论

评论（0）

赞助本站