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

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

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

点击全文阅读


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和端口，与服务器进行交互。现在没有环境无法复现了。

大致的流程：

  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。

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))


点击全文阅读


本文链接：http://zhangshiyu.com/post/29973.html

我们可以  求出  分解  
<< 上一篇 下一篇 >>

  • 评论（0）
  • 赞助本站

◎欢迎参与讨论，请在这里发表您的看法、交流您的观点。

最新文章

  • 林柒薇宋延桉小说全文免费阅读穿到八零年代和司令丈夫离婚那天全文免费阅读
  • 好看的妻子嫁作他人妇，我和女儿不认小说-妻子嫁作他人妇，我和女儿不认最新章节阅读
  • 《七零：那两口子万人嫌，太发癫了》完整版-盛春香裴清远在线全文阅读
  • 最新小说被山里糙汉追着满地跑主角闵小小闵烨全文在线阅读
  • 李慕云陶金辉全文小说最新章节阅读李慕云陶金辉
  • 《看到三十年后的联姻生活，我决定离婚》颜雯程绛-小说txt全文阅读
  • 长公主她风华正茂无弹窗在线阅读
  • 你敢说话，我就敢质疑主角是李云初张景小说百度云全文完整版阅读
  • 娶资助的贫困生当晚，她和竹马一起入洞房小说(完结)-安枫符垚无删减阅读
  • 心机女插足后，她和相亲对象闪婚了（全本）姜初棠夏芝芝完整章节列表免费阅读
  • 被撞流产后，我选择离婚小说百度云完整章节列表免费阅读
  • 沈糯周钦然《老公白月光在我家别墅养胎》全章节免费阅读

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1