前言
网络空间的竞争归根结底是人才的竞争。网络安全说千遍不如打一遍。为提升学生网络安全实战技能水平，为选拔、培养、推荐优秀网络安全专业人才创造条件，我校首届“鲲鹏杯”网络空间安全竞赛，我收获到了不少。
斐波那契数列
题目
encryption:
1,1346269,2,5,8,13,3,21,34,55,89,144,233,377,610,987,2584,4181,6765,1597,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,2178309,1
cipher:flag{0efa24ed49aa78d97bc2657c4aeaf4da}
解题
拿到这题，给的提示是“斐波那契”，第一反应想到的是buu上的“达芬奇密码”。
将给的这一串数进行升序排序
1
2
3
| li1=[1,1346269,2,5,8,13,3,21,34,55,89,144,233,377,610,987,2584,4181,6765,1597,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,2178309,1]
li1.sort( );
print("list=",li1)
|
输出：
1
| list= [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309]
|
给了一串flag，看看能不能找到联系
1
2
3
| b='0efa24ed49aa78d97bc2657c4aeaf4ad'
print(len(b))
print(len(li1))
|
发现它们的长度都是32，于是确定这是和达芬奇密码一样一一对应的关系。排序前后的数据没有相差很多，手动位移即可。其中两个1，第一第二位顺序上不确定。
结果
1
| flag{0dfea24d49aa78d927bc657c4aeaf4ae}
|
凯撒？替换？呵呵！
题目
1
| MTHJ{CUBCGXGUGXWREXIPOYAOEYFIGXWRXCHTKHFCOHCFDUCGTXZOHIXOEOWMEHZO}
|
解题
看到MTHJ{xxx}，想到FLAG{XXX}，对应两个字母的差值不一样，因此不可能是单纯的按照字母顺序的位移凯撒密码。所以，进行爆破。
quipqiup - cryptoquip and cryptogram solver
结果显而易见
结果
输入的结果太坑了，带着花括号试了好几次，未果
最后是没外壳也没空格
1
| substitutioncipherdecryptionisalwayseasyjustlikeapieceofcake
|
crypto-ComplexEncode
题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| from Crypto.Util.number import *
from flag import FLAG,false_flag
import gmpy2
import random
import hashlib
import base64
def rsaEncode(msg):
f=open("out","a")
while True:
ran=random.randint(3, 12)
if isPrime(ran):
break
e=ran*getPrime(30)
p = getPrime(1024)
q = getPrime(1024)
while (not gmpy2.gcd((p-1)*(q-1),e)==ran or p*q<pow(msg,ran)):
p = getPrime(1024)
q = getPrime(1024)
n=p*q
assert(pow(msg,ran)<n)
print("rsaEncode_init_finish!")
dsaEncode(p)
f.write("rsaEncode n:"+hex(n)+"\n")
f.write("rsaEncode e:"+hex(e)+"\n")
c=pow(msg,e,n)
f.write("rsaEncode flag is:"+hex(c)+"\n")
f.close()
def rsaEncode2(m):
m=int.from_bytes(m.encode(),'big')
f=open("out","w")
while True:
ran=random.randint(20, 50)
if isPrime(ran):
break
e=ran*getPrime(30)
p = getPrime(1024)
q = gmpy2.next_prime(p)
while (not gmpy2.gcd((p-1)*(q-1),e)==ran or p*q>pow(m,ran)):
p = getPrime(1024)
q = gmpy2.next_prime(p)
n=p*q
assert(pow(m,ran)>n)
c=pow(m,e,n)
f.write("n2:"+hex(n)+"\n")
f.write("e2:"+hex(e)+"\n")
f.write("rsaEncode2 re is:"+hex(c)+"\n")
f.close()
print("rsaEncode2_finish!")
return pow(m,ran,n)
def dsaEncode(p):
key=genkey(p)
(r,s,k,q)=sign(rsaEncode2(false_flag),key)
sig= r.to_bytes(205, 'big') + s.to_bytes(205, 'big') + k.to_bytes(205, 'big')+ q.to_bytes(205, 'big')
f=open("out","a")
f.write("dsaEncode :"+base64.b64encode(sig).decode()+"\n")
f.close()
def genkey(x):
N=1024
L=2048-N-1
while True:
q = getPrime(N)
if q-1>x:
break
assert(q-1>x)
while True:
t = random.getrandbits(L)
p = (t * 2*q + 1)
if isPrime(p):
break
e = (p-1) // q
g = pow(2, e, p)
y = pow(g, x, p)
print("genkey_finish!")
return {'y':y, 'g':g, 'p':p, 'q':q, 'x':x}
def sign(m, key):
g, p, q, x = key['g'], key['p'], key['q'], key['x']
k = random.randint(1, q-1)
Hm = int.from_bytes(hashlib.md5(str(m).encode('utf-8')).hexdigest().encode(), 'big')
r = pow(g, k, p) % q
s = (inverse(k, q) * (Hm + x*r)) % q
return (r, s, k, q)
if __name__ == "__main__":
msg=int.from_bytes(FLAG.encode(),'big')
rsaEncode(msg)
|
解题
1、先把dsaEncode进行base64编码，
1
2
3
4
5
6
| import base64
dsaEncode="AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACR4uuC531illQ9yIEW1Ki22kYtZNrX77elRFDZr8EKcnrkZC+yyMxlxFNsCrFqEPhGzAPXS++Aa248WMv1uZDNIzi84jiMw7ZWS82OKEwzy0ozV7lEa7deI+QoVdl49kXx3ZVaR2/TrXrfr3dkiBQyORp/DPsSQdkdLoCmtgNycQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAmkIjVBdkWLaqnSz0OdPi69RsjMwT1wVxq81vfDFnOO+JYKfG0OiAZEeJoSeParez6jBH0+RLVc4f6xOFgZcDYopkzR8ZNYlJR78oWmi/0cuxt4nYTTVirtUux3JrT75YQ/+bWmhswBMHQeIAttvqoZp/YZPOmHZdDkl7arrdZ5UAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEt+f1ID5QKI6NEqnVMMputnxfuIs4hCKZbPCEeV6uGoLJSbKaxBlzaO37bTzINBAxCcKQfCsV4ZwZFpTmozZ/dSdoKnIq/tcPh++80pUAjSjVI/rVInJi4CKgaeaf/8MX8ajCImkLJt6N4pA109eZ6TVJDFnbSRRY9P5i5iF2XwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACh5RoGbxvmvqT2pj93NhFj5UruyVjoxCkyw5kD2qEVCfKXZT1ysK9F5A2MJuU1qLKiJ76ATUVid1dtanCzd8XzkzfdY3nEtxqJ4CEJTSnIuthBz4ETBd8+v2+Oc4nTaimIdhQrEtI5M2z9+tq+uQ/qaXbg735CQiU7jjyALgOCoQ=="
print(len(dsaEncode))
key=base64.b64decode(dsaEncode)
print(key)
print(len(key))
|
根据这段代码
1
2
3
4
5
| r=int(key[:205].encode("hex"),16)
s=int(key[205:410].encode("hex"),16)
k=int(key[410:615].encode("hex"),16)
q=int(key[615:820].encode("hex"),16)
x=(gmpy2.invert(r,q)*(k*s-Hm))%q
|
阅读代码后，我们发现rsa1中的p就是dsa的x，x≡（Hm+xr）k^-1^mod q,从上文第一段代码base64后我们可以得到r，s，k，q。
通过RSA2解出m,这里的e和phi不互质，所以要先求解m^gcd(e,phi)^,再解m
分解n2得到p2和q2
1
2
3
4
5
6
7
8
9
10
| n2=0x431a834246a5969d460cee6b7db01ec4e05daffd60d6674fd1cf3ab96544ad788df5ef729eba08fce3d6c237b47b7cbda093fb414672eea6a58bd902c7e73844a85b2626e3f17a2c2b6c6521288925792bfa2a338cf1d2128d771b55bac2a2cc85f95dd68b4463661813c7ed268c1ca203c74b513edf749799acbfd70b656976f81d124c0385f4dfe549185a4853ace927db615c1ce95b8230a504dbdc6db1ff639e9700e6f074432493b6bf1aa349a9cf66a7116a6095803718a5b78d541b7fbf643bed0bbde5a9370f54a457feef2fde1db15012c337385d011c4a601fe092a0b0a503b65efb1d2c70de6883a504d04292e4216e5c586e0df85b00732460f5
e2=0x57e6b0c63
rsaEncode2=0x174e74a04d09ee859030c9fa292c266f9de06bf833dcffc5d24a4382251620cac743cf2d500428d5784fc271e610965547675db2716a9ab277395fc565a2d8520b21d4384a525beda292c276b4477852255c910b0dd08374e68e421b137d90c6c8ca98e219a73231eb285707fff221e57a005113ec16ef61bde87bebd69da1d09cccda411242ba7607a470b31e54e79603eb2c568825a7534df24d0e411fa60d96925f3f2cc63e3ab60f1fe51be80009aba3fdfe947365e578f04fd04a1f9e4afb5fc7ccc1ee831622917386c0d7ae00e6f3f4abd818f6e76d9d173a2e53357496441ae140284c8a6cc3aa22232f1a58fc101427236f2c2afc2277470eb83116
p2 = 92038254802992589334836021211021722416892343074988502820738425960842862985591620926198422759102071572852989309010179392091711882907907766877651639325642946829388178711105989373057972159393372729050507806434617955128196692311614810456775707826817847326317108693718175021812398842350298774399748620926186724103
q2 = 92038254802992589334836021211021722416892343074988502820738425960842862985591620926198422759102071572852989309010179392091711882907907766877651639325642946829388178711105989373057972159393372729050507806434617955128196692311614810456775707826817847326317108693718175021812398842350298774399748620926186723619
assert p2*q2==n2
phi=(p2-1)*(q2-1)
g2=gmpy2.gcd(e2,phi)
d2=gmpy2.invert(e2/g2,phi)
m2=pow(rsaEncode2,d2,n2)
|
在dsa中直接是对rsa2中的m^gcd(e,phi)^做MD5
1
2
3
4
5
6
| x=(gmpy2.invert(r,q)*(k*s-Hm))%q
p=n/x
phi=(p-1)*(x-1)
g=gmpy2.gcd(e,phi)
d=gmpy2.invert(e/g,phi)
m=pow(flag,d,n)
|
因为gcd（e，phi）较小，可以通过爆破求解m
1
2
3
4
5
6
| for i in xrange(1000000):
ss=gmpy2.iroot(i*n+m,g)
if ss[1]:
print ss[0]
print hex(ss[0])[2:].decode("hex")
break
|
总的代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| import gmpy2
import base64
import hashlib
n2=0x431a834246a5969d460cee6b7db01ec4e05daffd60d6674fd1cf3ab96544ad788df5ef729eba08fce3d6c237b47b7cbda093fb414672eea6a58bd902c7e73844a85b2626e3f17a2c2b6c6521288925792bfa2a338cf1d2128d771b55bac2a2cc85f95dd68b4463661813c7ed268c1ca203c74b513edf749799acbfd70b656976f81d124c0385f4dfe549185a4853ace927db615c1ce95b8230a504dbdc6db1ff639e9700e6f074432493b6bf1aa349a9cf66a7116a6095803718a5b78d541b7fbf643bed0bbde5a9370f54a457feef2fde1db15012c337385d011c4a601fe092a0b0a503b65efb1d2c70de6883a504d04292e4216e5c586e0df85b00732460f5
e2=0x57e6b0c63
rsaEncode2=0x174e74a04d09ee859030c9fa292c266f9de06bf833dcffc5d24a4382251620cac743cf2d500428d5784fc271e610965547675db2716a9ab277395fc565a2d8520b21d4384a525beda292c276b4477852255c910b0dd08374e68e421b137d90c6c8ca98e219a73231eb285707fff221e57a005113ec16ef61bde87bebd69da1d09cccda411242ba7607a470b31e54e79603eb2c568825a7534df24d0e411fa60d96925f3f2cc63e3ab60f1fe51be80009aba3fdfe947365e578f04fd04a1f9e4afb5fc7ccc1ee831622917386c0d7ae00e6f3f4abd818f6e76d9d173a2e53357496441ae140284c8a6cc3aa22232f1a58fc101427236f2c2afc2277470eb83116
dsaEncode="AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACR4uuC531illQ9yIEW1Ki22kYtZNrX77elRFDZr8EKcnrkZC+yyMxlxFNsCrFqEPhGzAPXS++Aa248WMv1uZDNIzi84jiMw7ZWS82OKEwzy0ozV7lEa7deI+QoVdl49kXx3ZVaR2/TrXrfr3dkiBQyORp/DPsSQdkdLoCmtgNycQAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAmkIjVBdkWLaqnSz0OdPi69RsjMwT1wVxq81vfDFnOO+JYKfG0OiAZEeJoSeParez6jBH0+RLVc4f6xOFgZcDYopkzR8ZNYlJR78oWmi/0cuxt4nYTTVirtUux3JrT75YQ/+bWmhswBMHQeIAttvqoZp/YZPOmHZdDkl7arrdZ5UAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEt+f1ID5QKI6NEqnVMMputnxfuIs4hCKZbPCEeV6uGoLJSbKaxBlzaO37bTzINBAxCcKQfCsV4ZwZFpTmozZ/dSdoKnIq/tcPh++80pUAjSjVI/rVInJi4CKgaeaf/8MX8ajCImkLJt6N4pA109eZ6TVJDFnbSRRY9P5i5iF2XwAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAACh5RoGbxvmvqT2pj93NhFj5UruyVjoxCkyw5kD2qEVCfKXZT1ysK9F5A2MJuU1qLKiJ76ATUVid1dtanCzd8XzkzfdY3nEtxqJ4CEJTSnIuthBz4ETBd8+v2+Oc4nTaimIdhQrEtI5M2z9+tq+uQ/qaXbg735CQiU7jjyALgOCoQ=="
n=0x769bf99a95e9f446788300bfc679b04f26498d26ce1f1384ef22a4bc0606d2fdcf4af86b8e9b26003f561532613a8b7bcb09c0009aefc09c5297f53342b9fe111562c0789dfa91ff4def12c7cb551828079418e1244387f392d6f420c04eb8b99278f5dacb6042828dae19c1f6638d46f9601aceee1511bf600ef548db15ea6ce1ae975cd08236fdac7d457ac9fa203c8f7914702c78dc3ef24fa50c32208225096f5af761f9e4c581dfca7dbc2a4062d59196578e0213a8d1d8a05bfe398a3c8c195b3997fb01b930e2c925732ef78fdd39b4e4681ab3fea4d2c4f1a3b935df5d494817e2c8eef72e3f22f1ef80c3455add7206baf92495ae59adaa7f1bfd25
e=0x12a316381
flag=0xa97f8fd2cbf4aa1cae331dc5261c93a8da3c0a4aadd33cf204cdb2e38e3afdd16aed1a23cd911f96ddc7152b14120949235c0f1849999c5eae06932900f0ccb7c19fb3854623dc0bbc9b9b1fe640075d1db0be91f0e45776b959d008edd17cf41c24d711a5c767d10a630eec8d96baf2668a358c3cbe4533e410667748d73725c04113e9c7d4f19d520aab6b3241a96feb54632a6f816efdc3a2d7c28604a25ce9fd3dc1d0210e0c70132618125bf8eae1f73fa48699fb7cffe5721b5b7fc8511d6cec4ecef1a8bca0d8fe29b0856b3648feac3f1020650063c40be606d9faf0004517dfb202dfb9c664a887f366119ef2efcbf84813f9a4ad54e9ad05e20f0
p2 = 92038254802992589334836021211021722416892343074988502820738425960842862985591620926198422759102071572852989309010179392091711882907907766877651639325642946829388178711105989373057972159393372729050507806434617955128196692311614810456775707826817847326317108693718175021812398842350298774399748620926186724103
q2 = 92038254802992589334836021211021722416892343074988502820738425960842862985591620926198422759102071572852989309010179392091711882907907766877651639325642946829388178711105989373057972159393372729050507806434617955128196692311614810456775707826817847326317108693718175021812398842350298774399748620926186723619
assert p2*q2==n2
phi=(p2-1)*(q2-1)
g2=gmpy2.gcd(e2,phi)
d2=gmpy2.invert(e2/g2,phi)
m2=pow(rsaEncode2,d2,n2)
Hm=int(hashlib.md5(str(m2).encode()).hexdigest().encode("hex"),16)
key=base64.b64decode(dsaEncode)
r=int(key[:205].encode("hex"),16)
s=int(key[205:410].encode("hex"),16)
k=int(key[410:615].encode("hex"),16)
q=int(key[615:820].encode("hex"),16)
x=(gmpy2.invert(r,q)*(k*s-Hm))%q
p=n/x
phi=(p-1)*(x-1)
g=gmpy2.gcd(e,phi)
d=gmpy2.invert(e/g,phi)
m=pow(flag,d,n)
for i in xrange(1000000):
ss=gmpy2.iroot(i*n+m,g)
if ss[1]:
print ss[0]
print hex(ss[0])[2:].decode("hex")
break
|
结果
1
| flag{2a4d55342b46289d1f624d3083c5e2de}
|
wechat
alipay