2021 羊城杯 Crypto部分 Writeup

菜鸡Crypto手,就解出来了两道题,都是相对比较简单的密码学题目,供各位大佬参考

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

手速题目,可以通过n1和n2直接的关系。

n1和n2经过测试是存在有一个不等于1的最大公约数,这个最大公约数显然就是共同的p,可以根据这一线索进行。然后就是两层的加密数值,求出两个q,然后再求出两个phi和d,然后这道题目就像剥洋葱一样简单了

EXP:

import gmpy2
import libnum
from Crypto.Util.number import *

n1 = 103835296409081751860770535514746586815395898427260334325680313648369132661057840680823295512236948953370895568419721331170834557812541468309298819497267746892814583806423027167382825479157951365823085639078738847647634406841331307035593810712914545347201619004253602692127370265833092082543067153606828049061
n2 = 115383198584677147487556014336448310721853841168758012445634182814180314480501828927160071015197089456042472185850893847370481817325868824076245290735749717384769661698895000176441497242371873981353689607711146852891551491168528799814311992471449640014501858763495472267168224015665906627382490565507927272073
e = 65537
# m = bytes_to_long(flag)
# c = pow(m, e, n1)
# c = pow(c, e, n2)

c = 60406168302768860804211220055708551816238816061772464557956985699400782163597251861675967909246187833328847989530950308053492202064477410641014045601986036822451416365957817685047102703301347664879870026582087365822433436251615243854347490600004857861059245403674349457345319269266645006969222744554974358264

p =int(gmpy2.gcd(n1,n2))
q1 = n1//p
q2 = n2//p
assert p*q1 == n1
assert p*q2 == n2


phi1 = (p-1)*(q1-1)
phi2 = (p-1)*(q2-1)

d1 = libnum.invmod(e,phi1)
d2 = libnum.invmod(e,phi2)

c1 = pow(c,d2,n2)
m = pow(c1,d1,n1)
flag = long_to_bytes(m)
print(flag)

RingRingRing

这道题目需要使用羊城杯官方的VPN进行连接,是一个远程的动态靶机,其实也就是一个身份认证加一个简单是数学运算题目,我是采用从简单的形式入手,由简单推向复杂,找出规律就行遍历求解。

$$ a^4+b^4+c^4+d^4 = e^2 $$

题目关键点也就是这个公式,根据这个公式的特点:

$$ 1^4 + 1^4 +1^4 + 1^4 = 2^2 $$

$$ 2^4 + 2^4 + 2^4 + 2^4 = 8^2 $$

$$ 4^4 + 4^4 + 4^4 + 4^4 = 32^2 $$

根据简单的数据推测出规律性的公式

$$ (2^n)^4+(2^n)^4+(2^n)^4+(2^n)^4 = (2^{2n+1})^2 $$

根据公式进行代码编写即可求解

EXP:

from pwn import *
import string
import hashlib
import itertools
sh = remote("192.168.39.50",2378)
line = sh.recvline().decode().strip("\n")
ans = line[-5:]
s2 = line[line.find("+")+2:line.find(")")]
for i in itertools.product(string.ascii_letters + string.digits, repeat=4):
    s1 = ''.join(i)
    ss = s1 + s2
    if (hashlib.md5(ss.encode()).hexdigest()[0:5] == ans):
        sh.sendline(s1)
        break

context.log_level = 'debug'
sh.recvline()
sh.recvline()
for j in range(100):
    for i in range(4):
        sh.sendline(str(2**j))
        sleep(1)
    sh.sendline(str(2**(2*j+1)))
    sleep(1)
sh.interactive()

Q.E.D.