2021羊城杯 部分CRYPTO WP

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)

2021羊城杯 部分CRYPTO WP

Ring Ring Ring

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

大致的流程:

  1. 先hash验证
  2. 输入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。

2021羊城杯 部分CRYPTO WP

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的范围内,就可以使用数学公式来表达这些参数。

 2021羊城杯 部分CRYPTO WP

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

Y = My

inv_Y = inverse_mod(Y, n)

2021羊城杯 部分CRYPTO WP

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

D = (a*a)%n

2021羊城杯 部分CRYPTO WP

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次循环计算,最后抛出一个二元组。

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

2021羊城杯 部分CRYPTO WP

2021羊城杯 部分CRYPTO WP

2021羊城杯 部分CRYPTO WP

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

2021羊城杯 部分CRYPTO WP

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

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

2021羊城杯 部分CRYPTO WP

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

2021羊城杯 部分CRYPTO WP

然而Yn,Xn与a都已经告知给我们了,因此我们可以求出2021羊城杯 部分CRYPTO WP的结果。

但是到这一步其实可以发现我们求出的这个结果仅仅是2021羊城杯 部分CRYPTO WP这一结果。这不就是RSA里的m=pow(c,d,n)吗?

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

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

2021羊城杯 部分CRYPTO WP

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

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

再次回到a的那条公式。

2021羊城杯 部分CRYPTO WP

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

2021羊城杯 部分CRYPTO WP

最终可以得到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

上一篇:From Predictive to Prescriptive Analytics


下一篇:游戏开发之C++智能指针(C++)