这套题收获到的最大的是rsa攻击方式。

另外附文章一篇:http://blog.csdn.net/veritas501/article/details/55257957

爱吃培根的你

1
2
3
听说你也喜欢吃培根?那我们一起来欣赏一段培根的介绍吧:

bacoN is one of aMerICa'S sWEethEartS. it's A dARlinG, SuCCulEnt fOoD tHAt PaIRs FlawLE

小写对应A,大写对应B,然后培根解密。

熟悉的声音

1
XYYY YXXX XYXX XXY XYY X XYY YX YYXX

显然摩斯密码,拿到notepad里面替换,解密+凯撒。

Base64

1
GUYDIMZVGQ2DMN3CGRQTONJXGM3TINLGG42DGMZXGM3TINLGGY4DGNBXGYZTGNLGGY3DGNBWMU3WI===

显然base32,然后16进制转字符。

veryRSA

1
2
3
4
5
已知RSA公钥生成参数:

p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389

e = 65537
1
tool.py -p X -q x -e X

手贱的A君

1
2
3
4
5
某天A君的网站被日,管理员密码被改,死活登不上,去数据库一看,啥,这密码md5不是和原来一样吗?为啥登不上咧?

d78b6f302l25cdc811adfe8d4e7c9fd34

请提交PCTF{原来的管理员密码}

长度为33,md5显然不可能为33,去除一位,爆破。

veryeasy

直接搜flag。

easy RSA

1
2
3
4
5
已知一段加密的信息为:0xdc2eeeb2782c,且已知加密所用的公钥:(N=322831561921859 e = 23)

请解密出明文,提交时请将数字转化成ascii码提交,比如你解出的明文是0x6162,请提交字符串ab

提交格式:PCTF{明文字符串}

用yafu分解N,得到p、q,rsatool.py脚本得到d,cdn求明文。

取证

Volatility

medium RSA

1
2
3
4
5
6
7
8
from Crypto.PublicKey import RSA
pub = RSA.importKey(open('pub.key').read())
n = long(pub.n)
e = long(pub.e)
print 'n:',n
print 'e:',e
print 'n(hex):',hex(n)
print 'e(hex):',hex(e)

脚本分解公钥:

1
2
n: 87924348264132406875276140514499937145050893665602592992418171647042491658461
e: 65537

yafu分解N

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import math
import sys
from Crypto.PublicKey import RSA

keypair = RSA.generate(1024)

keypair.p = 275127860351348928173285174381581152299
keypair.q = 319576316814478949870590164193048041239
keypair.e = 65537

keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))

i = 1
while (True):
x = (Qn * i ) + 1
if (x % keypair.e == 0):
keypair.d = x / keypair.e
break
i += 1

private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()

p、q、e生成私钥

1
2
3
4
5
6
7
8
私钥解密脚本
import rsa
prifile = open('private.pem')
p = prifile.read()
privkey = rsa.PrivateKey.load_pkcs1(p)
crypto = open('flag.enc').read()
message = rsa.decrypt(crypto, privkey)
print message

hard RSA

涉及到rabin的,还没了解到,先丢两个脚本吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2

def n2s(num):
t = hex(num)[2:]
if len(t) % 2 == 1:
return ('0'+t).decode('hex')
return t.decode('hex')

c = int(open('flag.enc','rb').read().encode('hex'),16)
p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239
n = p*q
r = pow(c,(p+1)/4,p)
s = pow(c,(q+1)/4,q)
a = gmpy2.invert(p,q)
b = gmpy2.invert(q,p)
x =(a*p*s+b*q*r)%n
y =(a*p*s-b*q*r)%n

print n2s(x%n)
print n2s((-x)%n)
print n2s(y%n)
print n2s((-y)%n)
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#!/usr/bin/env python
'''
Rabin cryptosystem challenge:
N=0x6b612825bd7972986b4c0ccb8ccb2fbcd25fffbadd57350d713f73b1e51ba9fc4a6ae862475efa3c9fe7dfb4c89b4f92e925ce8e8eb8af1c40c15d2d99ca61fcb018ad92656a738c8ecf95413aa63d1262325ae70530b964437a9f9b03efd90fb1effc5bfd60153abc5c5852f437d748d91935d20626e18cbffa24459d786601
c=0xd9d6345f4f961790abb7830d367bede431f91112d11aabe1ed311c7710f43b9b0d5331f71a1fccbfca71f739ee5be42c16c6b4de2a9cbee1d827878083acc04247c6e678d075520ec727ef047ed55457ba794cf1d650cbed5b12508a65d36e6bf729b2b13feb5ce3409d6116a97abcd3c44f136a5befcb434e934da16808b0b
'''
# some functions from http://codereview.stackexchange.com/questions/43210/tonelli-shanks-algorithm-implementation-of-prime-modular-square-root/43267
def legendre_symbol(a, p):
"""
Legendre symbol
Define if a is a quadratic residue modulo odd prime
http://en.wikipedia.org/wiki/Legendre_symbol
"""
ls = pow(a, (p - 1)/2, p)
if ls == p - 1:
return -1
return ls
def prime_mod_sqrt(a, p):
"""
Square root modulo prime number
Solve the equation
x^2 = a mod p
and return list of x solution
http://en.wikipedia.org/wiki/Tonelli-Shanks_algorithm
"""
a %= p
# Simple case
if a == 0:
return [0]
if p == 2:
return [a]
# Check solution existence on odd prime
if legendre_symbol(a, p) != 1:
return []
# Simple case
if p % 4 == 3:
x = pow(a, (p + 1)/4, p)
return [x, p-x]
# Factor p-1 on the form q * 2^s (with Q odd)
q, s = p - 1, 0
while q % 2 == 0:
s += 1
q //= 2
# Select a z which is a quadratic non resudue modulo p
z = 1
while legendre_symbol(z, p) != -1:
z += 1
c = pow(z, q, p)
# Search for a solution
x = pow(a, (q + 1)/2, p)
t = pow(a, q, p)
m = s
while t != 1:
# Find the lowest i such that t^(2^i) = 1
i, e = 0, 2
for i in xrange(1, m):
if pow(t, e, p) == 1:
break
e *= 2
# Update next value to iterate
b = pow(c, 2**(m - i - 1), p)
x = (x * b) % p
t = (t * b * b) % p
c = (b * b) % p
m = i
return [x, p-x]
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
# This finds a solution for c = x^2 (mod p^2)
def find_solution(c, p):
'''
Hensel lifting is fairly simple. In one sense, the idea is to use
Newton's method to get a better result. That is, if p is an odd
prime, and
r^2 = n (mod p),
then you can find the root mod p^2 by changing your first
"approximation" r to
r - (r^2 - n)/(2r) (mod p^2).
http://mathforum.org/library/drmath/view/70474.html
'''
n = p ** 2
# Get square roots for x^2 (mod p)
r = prime_mod_sqrt(c,p)[0]
inverse_2_mod_n = modinv(2, n)
inverse_r_mod_n = modinv(r, n)
new_r = r - inverse_2_mod_n * (r - c * inverse_r_mod_n)
return new_r % n
if __name__ == "__main__":
# These are the given values
n = 0x6b612825bd7972986b4c0ccb8ccb2fbcd25fffbadd57350d713f73b1e51ba9fc4a6ae862475efa3c9fe7dfb4c89b4f92e925ce8e8eb8af1c40c15d2d99ca61fcb018ad92656a738c8ecf95413aa63d1262325ae70530b964437a9f9b03efd90fb1effc5bfd60153abc5c5852f437d748d91935d20626e18cbffa24459d786601L
# n is a perfect square: n = p * p
p = 0xa5cc6d4e9f6a893c148c6993e1956968c93d9609ed70d8366e3bdf300b78d712e79c5425ffd8d480afcefc71b50d85e0914609af240c981c438acd1dcb27b301L
# encrypted message
c = 0xd9d6345f4f961790abb7830d367bede431f91112d11aabe1ed311c7710f43b9b0d5331f71a1fccbfca71f739ee5be42c16c6b4de2a9cbee1d827878083acc04247c6e678d075520ec727ef047ed55457ba794cf1d650cbed5b12508a65d36e6bf729b2b13feb5ce3409d6116a97abcd3c44f136a5befcb434e934da16808b0bL
solution = find_solution(c, p)
print hex(solution)[2:-1].decode("hex")

very hard rsa

共模攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from gmpy2 import invert
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)

c1 = int(open('flag.enc1', 'rb').read().encode('hex'),16)
c2 = int(open('flag.enc2', 'rb').read().encode('hex'),16)
e1 = 17
e2 = 65537
s = egcd(e1,e2)
s1 = s[1]
s2 = s[2]
if s1<0:
s1 = - s1
c1 = invert(c1, n)
elif s2<0:
s2 = - s2
c2 = invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print hex(m)[2:].decode('hex')

extremelyhardRSA

e指数攻击

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/env python
# -*- coding: utf-8 -*-
__author__ = 'ByStudent'
from libnum import s2n,n2s
from gmpy2 import iroot
n = 0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e = 3
f = open('flag.enc','rb')
c= f.read()
c = s2n(c)
f.close()
i = 0
while 1:
res = iroot(c+i*n,3)
if(res[1] == True):
print res
break
print "i="+str(i)
i = i+1
#i=118719487
m = 440721643740967258786371951429849843897639673893942371730874939742481383302887786063966117819631425015196093856646526738786745933078032806737504580146717737115929461581126895844008044713461807791172016433647699394456368658396746134702627548155069403689581548233891848149612485605022294307233116137509171389596747894529765156771462793389236431942344003532140158865426896855377113878133478689191912682550117563858186
print n2s(m)
# 结果
# Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}