0%

MRCTFwp(crypto)

MRCTFwp(crypto)

水题挺多,倒是最后一题还有点东西

古典密码知多少

猪圈+圣堂武士+mc附魔文字+栅栏密码

没有什么华丽胡哨的

MRCTF{CRYPTOFUN}

keyboard

手机九键

按几下就是第几个字母

MRCTF{mobilephone}

天干地支+甲子

(我记得buu有道差不多的,不然还真想不到

先对表,然后+60,转ascii,就可以了,~(甚至觉得手动操作比脚本快~

MRCTF{goodjob}

vigenere

不多说啥了,原理详见soreau师傅的博客orz

http://www.soreatu.com/essay/Cryptanalysis%20of%20Vigenere%20Cipher.html

exp:(由于我为了偷懒是跟xor的魔改版放在一起的脚本,因此也许有些乱,建议去sore师傅博客看)

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
table = [chr(x) for x in range(ord('a') , ord('z')+1)]
ROTL = lambda s1 , key : ''.join([table[(table.index(x) - key + len(table))%len(table)] for x in s1])
ROTR = lambda s1 , key : ''.join([table[(table.index(x) + key)%len(table)] for x in s1])
def IndCo(nlist):
'''judge the key size by Index of coincidence
nlist : the lower cipher list(bytes)
return the result(if the size is the true size , the result is round 0.06.Else , the result will be below 0.05)'''

resultlist = []
for j in nlist:
freq = {}
lenth = len(j)
for i in j:
if i in freq:
freq[i] += 1
else:
freq[i] = 1
result = 0
for i in freq:
result += freq[i]*(freq[i] - 1)
result /= lenth * (lenth-1)
resultlist.append(result)
if sum(resultlist) / len(resultlist) > 0.055:
return True
return False
def keysize(msg ,begin=4 , end = 40):
'''break the key size
msg: the cipher(lower)(bytes)
begin , end: the range of key size
return the most probable key size list'''
MsgLenth = len(msg)

keysize = []
group = min(begin , 4)
for size in range(begin , end + 1):
templist = [msg[i::size] for i in range(group)]
if IndCo(templist):
keysize.append(size)
return keysize
def ChiSquared(msg):
'''Chi-squared Statistic
msg: str'''
standard_letter_frequency = { # From https://en.wikipedia.org/wiki/Letter_frequency.
'e': 0.12702,'t': 0.09056,'a': 0.08167,'o': 0.07507,'i': 0.06966,'n': 0.06749,
's': 0.06327,'h': 0.06094,'r': 0.05987,'d': 0.04253,'l': 0.04025,'c': 0.02782,
'u': 0.02758,'m': 0.02406,'w': 0.02360,'f': 0.02228,'g': 0.02015,'y': 0.01974,
'p': 0.01929,'b': 0.01492,'v': 0.00978,'k': 0.00772,'j': 0.00153,'x': 0.00150,
'q': 0.00095,'z': 0.00074,' ': 0.25000}
result = 0
msg = msg.lower()
for i in msg:
if i in standard_letter_frequency:
result += standard_letter_frequency[i]
return result
def singlekey_rot(cipher):
'''get the most probable key byte
cipher: encrypted by the same byte of key.And must be letters(without blank)(string)(lower)
return: the byte of key(str)'''
result = -1
for i in range(26):
tempmsg = ROTL(cipher , i)
tempresult = ChiSquared(tempmsg , 0)
if tempresult < result or result == -1:
result = tempresult
key = chr(i + ord('a'))
return key
def break_key_reuse_rot(msg):
'''msg: str
return a dic {keysize : key}, keysize is int, key is bytes'''
key_size = keysize(msg , 1)
key = {}
for i in key_size:
temp = ''
for j in range(i):
temp += singlekey_rot(msg[j::i])
key[i] = temp
return key
f = open('./vigenere/cipher.txt' , 'r')
s = f.read()
c = ''
for i in s:
if ord('a') <= ord(i) <= ord('z'):
c += i
key = break_key_reuse_rot(c)[6]
getdiff = lambda char: ord(char)-ord('a')
getchar = lambda num: chr(ord('a')+num)
def vigenere(src, key):
assert(src.isalpha() and key.isalpha())
return(getchar((getdiff(src) - getdiff(key) + 26) % 26))
count = 0
for i in s:
if(i.isalpha()):
print(vigenere(i, key[count % len(key)]), end='')
count+=1
else:
print(i, end='')

(后面是抄出题脚本用爆破出的key解密得到flag)

easyrsa

先算p,给n与$\phi(n)$求p,q,由于n=pq,因此只需要求出p+q就可以用一元二次方程求出答案。

而$\phi(n) = (p-1)*(q-1) = pq-p-q+1 $

因此$p+q = n - \phi(n) + 1$

接下来一元二次方程就行

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
def Solve(a , b , c):
'''solve ax^2+bx+c=0 , return x1 , x2'''
delta = b**2 - 4 * a * c
if delta < 0:
return 0
if is_square(delta):
sqr_delta = isqrt(delta)
temp1 = -b + sqr_delta
temp2 = -b - sqr_delta
if temp1 % (2*a) != 0 or temp2 % (2*a) != 0:
return 0
else:
return [temp1//(2*a) , temp2//(2*a)]
else:
return 0
def get_next(x):
if x % 2 == 0:
x += 1
else:
x+=2
while not is_prime(x):
x += 2
return x
def gen_p():
n = mpz(14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024336556028267742021320891681762543660468484018686865891073110757394154024833552558863671537491089957038648328973790692356014778420333896705595252711514117478072828880198506187667924020260600124717243067420876363980538994101929437978668709128652587073901337310278665778299513763593234951137512120572797739181693)
phi = mpz(14057332139537395701238463644827948204030576528558543283405966933509944444681257521108769303999679955371474546213196051386802936343092965202519504111238572269823072199039812208100301939365080328518578704076769147484922508482686658959347725753762078590928561862163337382463252361958145933210306431342748775024099427363967321110127562039879018616082926935567951378185280882426903064598376668106616694623540074057210432790309571018778281723710994930151635857933293394780142192586806292968028305922173313521186946635709194350912242693822450297748434301924950358561859804256788098033426537956252964976682327991427626735740)
p_q = n - phi + 1
p , q = Solve(1 , -p_q , n)
if p > q :
p , q = q , p
factor2 = 2021 * p + 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return get_next(factor2)

q比p难求一点,已知e*d与n求p和q

而k2是可以通过e*d // n得到,k2也不会很大因此可以从$k_2$往上找,基本在1-3之间一定能出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def gen_q():
n = mpz(20714298338160449749545360743688018842877274054540852096459485283936802341271363766157976112525034004319938054034934880860956966585051684483662535780621673316774842614701726445870630109196016676725183412879870463432277629916669130494040403733295593655306104176367902352484367520262917943100467697540593925707162162616635533550262718808746254599456286578409187895171015796991910123804529825519519278388910483133813330902530160448972926096083990208243274548561238253002789474920730760001104048093295680593033327818821255300893423412192265814418546134015557579236219461780344469127987669565138930308525189944897421753947)
ed = mpz(100772079222298134586116156850742817855408127716962891929259868746672572602333918958075582671752493618259518286336122772703330183037221105058298653490794337885098499073583821832532798309513538383175233429533467348390389323225198805294950484802068148590902907221150968539067980432831310376368202773212266320112670699737501054831646286585142281419237572222713975646843555024731855688573834108711874406149540078253774349708158063055754932812675786123700768288048445326199880983717504538825498103789304873682191053050366806825802602658674268440844577955499368404019114913934477160428428662847012289516655310680119638600315228284298935201)
ed = ed -1
k = ed// n
for i in range(k , k + 2):
if ed % i == 0:
phi = ed // i
break
p_q = n - phi + 1
p , q = Solve(1 , -p_q , n)
if p > q :
p , q = q , p
factor2 = 2021 * p - 2020 * q
if factor2 < 0:
factor2 = (-1) * factor2
return get_next(factor2)

正常rsa

1
2
3
4
5
6
7
8
Ciphertext =  40855937355228438525361161524441274634175356845950884889338630813182607485910094677909779126550263304194796000904384775495000943424070396334435810126536165332565417336797036611773382728344687175253081047586602838685027428292621557914514629024324794275772522013126464926990620140406412999485728750385876868115091735425577555027394033416643032644774339644654011686716639760512353355719065795222201167219831780961308225780478482467294410828543488412258764446494815238766185728454416691898859462532083437213793104823759147317613637881419787581920745151430394526712790608442960106537539121880514269830696341737507717448946962021
p = gen_p()
q = gen_q()
n = p * q
phi = (p-1) * (q-1)
e = 65537
d = invert(e , phi)
print(bytes.fromhex(hex(powmod(Ciphertext , d , n))[2:]))

babyrsa

baby题居然比easy题简单!

题目中,gen_p是getPrime(128)后,在它后面找了连续的17个质数,并且告诉了我们第9个,显然这是很容易得到剩下16个,然后给了powmod(p , 65537,n),n是17个质数的乘积,而知道了17个质数,很容易求得$\phi(n) = \prod_{i=1}^{17} {(p_i-1)} $接下来就可以计算$d = invert(65537 , \phi(n)),p = powmod(factor, d , n)$

exp:

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
def get_next(x):
if x % 2 == 0:
x += 1
else:
x+=2
while not is_prime(x):
x += 2
return x
def get_pre(x):
if x % 2 == 0:
x -= 1
else:
x-=2
while not is_prime(x):
x -= 2
return x
def gen_p():
p0 = mpz(206027926847308612719677572554991143421)
plist = [p0]
for i in range(9):
plist.append(get_pre(plist[-1]))
plist.reverse()
for i in range(7):
plist.append(get_next(plist[-1]))
n = 1
for i in range(17):
n *= plist[i]
factor = mpz(213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839)
phi = 1
for i in range(17):
phi *= plist[i] - 1
d = invert(65537 , phi)
return get_next(powmod(factor , d , n))

q就是白给,直接求个逆就能算

1
2
3
4
5
6
def gen_q():
q1 = mpz(103766439849465588084625049495793857634556517064563488433148224524638105971161051763127718438062862548184814747601299494052813662851459740127499557785398714481909461631996020048315790167967699932967974484481209879664173009585231469785141628982021847883945871201430155071257803163523612863113967495969578605521)
q2 = mpz(151010734276916939790591461278981486442548035032350797306496105136358723586953123484087860176438629843688462671681777513652947555325607414858514566053513243083627810686084890261120641161987614435114887565491866120507844566210561620503961205851409386041194326728437073995372322433035153519757017396063066469743)
subq = mpz(168992529793593315757895995101430241994953638330919314800130536809801824971112039572562389449584350643924391984800978193707795909956472992631004290479273525116959461856227262232600089176950810729475058260332177626961286009876630340945093629959302803189668904123890991069113826241497783666995751391361028949651)
q = powmod(subq , q2 , q1)
return get_next(q)

接下来就是正常rsa解密

1
2
3
4
5
6
7
8
p = gen_p()
q = gen_q()
n = p * q
phi = (p-1)*(q-1)
e = 65537
c = mpz(1709187240516367141460862187749451047644094885791761673574674330840842792189795049968394122216854491757922647656430908587059997070488674220330847871811836724541907666983042376216411561826640060734307013458794925025684062804589439843027290282034999617915124231838524593607080377300985152179828199569474241678651559771763395596697140206072537688129790126472053987391538280007082203006348029125729650207661362371936196789562658458778312533505938858959644541233578654340925901963957980047639114170033936570060250438906130591377904182111622236567507022711176457301476543461600524993045300728432815672077399879668276471832)
d = invert(e , phi)
print(bytes.fromhex(hex(powmod(c , d, n))[2:]))

real random

题目告诉了M与D,猜对flag_part是哪一个就给flag的一字节。先分析random那个函数,将M分解,可以得到p,q(p与q是getPrime(6),总共只有8种可能,很容易分解),用p与q能够算出m和b

但是c不知道,因此推测对于不同的c,也许会有一个共同的周期,或是周期有一个固定的公倍数

因此每进行m次操作,就会回到初始值,random[0]是进行了2**d次操作的,因此只要发$m-(2^d mod m)$即可

exp:

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
from gmpy2 import mpz , is_prime , powmod , invert
from pwn import *
import sys
from Crypto.Util.number import getPrime
sys.path.append('/home/shallow/crypto/rsa')
from factor import Pollard_rho
context.log_level = 'debug'
prime = [47, 67, 59, 53, 37, 41, 61, 43]
def factor(n):
for i in prime:
if n %(i-1) == 0:
return [i , n// (i-1) + 1]
def generate_flag(pre):
return pre// (16**2+1)
def guess(n , d):
p , q = factor(n)
m = p * q * 2 ** 5
return m - (2 ** d % m)
p = remote('38.39.244.2', '28101')
p.recvuntil(b'GAME START : )')
def recv():
p.recvuntil('m: ')
m = int(p.recvuntil('\n'))
p.recvuntil('d: ')
d = int(p.recvuntil('\n'))
p.recvuntil('Now guess where the flag is ^_^ \n')
return m , d

def send(num):
p.sendline(str(num))
pre_flag = int(p.recvuntil('\n'))
print(pre_flag)
return chr(generate_flag(pre_flag))
flag = ''
while 1 :
m , d = recv()
num = guess(m , d)
flag += send(num)
print(flag)