CTFshow-月饼杯

crypto1_中秋月

​ 题目以及hint：

密文：

hint：某古典密码；经此古典密码加密后，密文还是大写；keyword+plaintext (+plaintext…+plaintext)；自动钥匙⊕；明文全大写，得到后转小写，并以_连接单词

​ ⊕符号通常就是异或的表示，根据题意应该是明文经过加密以后（大写字母）还经过了异或才得到当前的密文，所以可以先尝试还原异或之前的大写字母：

1
2
3
4
5
6
7
8
9
s='fsskryenvkm~jl{ejs}jwflzsnpgmifq{{j{|suhzrjppnx|qvixt~whu'
for i in range(255):
	res=''
	for j in range(0,len(s)):
		temp = ord(s[j])^i
		if 65<=temp<=90 :	#由大小写字母构成
			res += (chr(temp))
	if len(res)==len(s):
		print(res)

​ 得到：YLLTMFZQITRAUSDZULBUHYSELQOXRVYNDDUDCLJWEMUOOQGCNIVGKAHWJ

​ 根据keyword+plaintext (+plaintext…+plaintext)可知该加密算法为autokey密码，是一种多表替换密码，与维吉尼亚密码密码类似。对于替换类密码的破解github上有一个项目：python_cryptanalysis

​ 由于该项目仅支持python2，于是适当修改源码运行得到flag

​ 解密完整代码：

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
107
108
#main.py
from ngram_score import ngram_score
from pycipher import Autokey
import re
from itertools import permutations

s='fsskryenvkm~jl{ejs}jwflzsnpgmifq{{j{|suhzrjppnx|qvixt~whu'
for i in range(255):
   res=''
   for j in range(0,len(s)):
      temp = ord(s[j])^i
      if 65<=temp<=90 :  #由大小写字母构成
         res += (chr(temp))
   if len(res)==len(s):
      print(res)


qgram = ngram_score('quadgrams.txt')
trigram = ngram_score('trigrams.txt')
ctext = 'YLLTMFZQITRAUSDZULBUHYSELQOXRVYNDDUDCLJWEMUOOQGCNIVGKAHWJ'
ctext = re.sub(r'[^A-Z]', '', ctext.upper())



class nbest(object):
   def __init__(self, N=1000):
      self.store = []
      self.N = N


   def add(self, item):
      self.store.append(item)
      self.store.sort(reverse=True)
      self.store = self.store[:self.N]


   def __getitem__(self, k):
      return self.store[k]


   def __len__(self):
      return len(self.store)


# init
N=100
for KLEN in range(3,20):
    rec = nbest(N)

    for i in permutations('ABCDEFGHIJKLMNOPQRSTUVWXYZ',3):
        key = ''.join(i) + 'A'*(KLEN-len(i))
        pt = Autokey(key).decipher(ctext)
        score = 0
        for j in range(0,len(ctext),KLEN):
            score += trigram.score(pt[j:j+3])
        rec.add((score,''.join(i),pt[:30]))

    next_rec = nbest(N)
    for i in range(0,KLEN-3):
        for k in range(N):
            for c in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
                key = rec[k][1] + c
                fullkey = key + 'A'*(KLEN-len(key))
                pt = Autokey(fullkey).decipher(ctext)
                score = 0
                for j in range(0,len(ctext),KLEN):
                    score += qgram.score(pt[j:j+len(key)])
                next_rec.add((score,key,pt[:30]))
        rec = next_rec
        next_rec = nbest(N)
    bestkey = rec[0][1]
    pt = Autokey(bestkey).decipher(ctext)
    bestscore = qgram.score(pt)
    for i in range(N):
        pt = Autokey(rec[i][1]).decipher(ctext)
        score = qgram.score(pt)
        if score > bestscore:
            bestkey = rec[i][1]
            bestscore = score
    print (bestscore,'autokey, klen',KLEN,':"'+bestkey+'",',Autokey(bestkey).decipher(ctext).lower())
 

#ngram_score.py
from math import log10

class ngram_score(object):
    def __init__(self,ngramfile,sep=' '):
        ''' load a file containing ngrams and counts, calculate log probabilities '''
        self.ngrams = {}
        for line in open(ngramfile):
            key,count = line.split(sep)
            self.ngrams[key] = int(count)
        self.L = len(key)
        #print(self.ngrams.items())
        self.N = sum(self.ngrams.values())
        #calculate log probabilities
        for key in self.ngrams.keys():
            self.ngrams[key] = log10(float(self.ngrams[key])/self.N)
        self.floor = log10(0.01/self.N)

    def score(self,text):
        ''' compute the score of text '''
        score = 0
        ngrams = self.ngrams.__getitem__
        for i in range(len(text)-self.L+1):
            if text[i:i+self.L] in self.ngrams: score += ngrams(text[i:i+self.L])
            else: score += self.floor
        return score

crypto2_月自圆

​ 题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- coding:utf-8 -*-
#Author: Lazzaro

from itertools import *
from random import *
from string import *

def encrypt(m, a, si):
	c=""
	for i in range(len(m)):
		c+=hex(((ord(m[i])) * a + ord(next(si))) % 128)[2:].zfill(2)
		#zfill函数是将字符串右对齐指定长度，用0填充左边
	return c
	
if __name__ == "__main__":
	m = '****************************************************flag{*************}'
	assert(len(m)==71)
	a = randint(50,100)
	salt = ''.join(sample(ascii_uppercase, 4))#随机抽4个大写字母
	si = cycle(salt.lower())
	c=encrypt(m, a, si)
	print(c)
	
#3472184e657e50561c481f5c1c4e1938163e154431015e13062c1b073d4e3a444f4a5c5c7a071919167b034e1c29566647600c4e1c2956661b6c1f50622f0016317e563546202a

​ 由题目得flag长度为71，密文为172，一位明文对应两位密文

​ 这里由于a不大，salt长度也不长，且明文m中存在flag，正好可以用这几位去爆破出a和salt；flag在明文m中的位置是53，对应密文c中的位置是105；因此可以遍历si（26位字母）和a（50~100）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from itertools import *

def decrypt(m, a, si):
	c=""
	for i in range(len(m)):
		c+=hex(((ord(m[i])) * a + ord(next(si))) % 128)[2:].zfill(2)
	return c

if __name__ == "__main__":
	for i in range(50,100):
		for j in ascii_uppercase:
			si = cycle(j.lower())
			# if encrypt('f', i, si)=='1c':
			# 	print('i =',i,'\tj =',j)

			if decrypt('l', i, si)=='29':
				print('i =',i,'\tj =',j)

​ 通过字母f爆破的结果：

i = 52 j = D
i = 57 j = F
i = 62 j = H
i = 67 j = J
i = 72 j = L
i = 77 j = N
i = 82 j = P
i = 87 j = R
i = 92 j = T
i = 97 j = V

​ 通过字母l爆破的结果：

i = 54 j = A
i = 55 j = U
i = 61 j = M
i = 67 j = E
i = 68 j = Y
i = 74 j = Q
i = 80 j = I
i = 86 j = A
i = 87 j = U
i = 93 j = M
i = 99 j = E

​ 取两者的交集：a = 67

​ 再利用a爆破salt的另外两位：

1
2
3
4
5
if decrypt('a', 67, si)=='56':
	print('j =',j)

if decrypt('g', 67, si)=='66':
	print('j =',j)

​ 得到构成salt的字符为“J、E、S、Q”，又f字母是第53个，前边共52个字母是4的倍数，于是可以确定salt就为“JESQ”

​ 解密exp：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from itertools import *

if __name__ == "__main__":
    a=67
    salt = 'JESQ'
    si = cycle(salt.lower())
    c = '3472184e657e50561c481f5c1c4e1938163e154431015e13062c1b073d4e3a444f4a5c5c7a071919167b034e1c29566647600c4e1c2956661b6c1f50622f0016317e563546202a'
    q=len(c)//2
    s=''
    for i in range(q):
        b=c[:2]
        c=c[2:]
        sm=next(si)
        for k in range(1,126):
            m=chr(k)
            c1=hex(((ord(m)) * a + ord(sm)) % 128)[2:].zfill(2)
            #print(m,c1,int(c1,base=16)==int(b,base=16))
            if(int(c1,base=16)==int(b,base=16)):
                s+=m
                break
    print(s)

now_is_7fad9fcb-d361-4964-821c-177c906b8d20_flag_is_flag{md5(now-salt)}

​ 最后把now（7fad9fcb-d361-4964-821c-177c906b8d20）和salt拼接起来进行md5加密就得到flag{}里面包裹的内容。

crypto3_多少离怀

​ 题目：

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
# -*- coding:utf-8 -*-
#Author: Lazzaro

from Crypto.Util.number import getPrime,isPrime
from math import gamma
import random

def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

def getNewPrime():
    A = getPrime(512)
    B = nextPrime(A - random.randint(1e4,1e5))
    return nextPrime(gamma(B+2)%A)
	
p = getNewPrime()
q = getNewPrime()
r = getNewPrime()
n = p * q ** 2 * r ** 3
e = 0x10001
c = pow(flag,e,n)


#pA=6814157460586876042804041951834304833424062437744287469257313954502540797027261340622077218188033865281590529907571701131297782609357118357982463723982789
#pB=6814157460586876042804041951834304833424062437744287469257313954502540797027261340622077218188033865281590529907571701131297782609357118357982463723922147
#qA=7145646366857234331692232566211321498245533826533958883943688415057871253511271731661019642050252046201115975396366275083424623329930477623781348477881291
#qB=7145646366857234331692232566211321498245533826533958883943688415057871253511271731661019642050252046201115975396366275083424623329930477623781348477807457
#n=4451906216583258787166698210560165433649728830889954633721198623488802305844782492171757604711145165920462286487680020347239300947225371917344589502941576734875830871998499135120227347066586066943289430156378296665669974728569678779668142712266780949126509440672273927433367293606776081254094682033167575930701870261219046464773708974194213798032346187463443317770758989273370488582862531630356263732232300508706676725203199729764016766683870925164232508407363688370458877688991733322055785233669885166225464068579486683574954699370175267031949720967812902215635630884502987094547523361027411501285252862476410213277925430392164226297316310465146003494714018456407793759170649913180823814850170639706664167149612984905056804131124522209409607977589884632999710708045656852149371030046919242039957767777840304466948549383597755811307383659188216421501912831203089570725388153416013596114462069777713822433178099904907224119
#c=1996198968748552041728429851810599627895157160099076033250854211280074825148767841655949210593646824507865483166496070951130337321360509148527292165245205219296211294789087358959553387392928560150390604911087085313000622842025416521494799132969818997182731021267942464323979261593380113740152841984062184326431879167516288834455296913822921806893572566867611541664848820247889274979245086440402996661226884320574824077910315143756471444347386795428338020162169391827182914043434253974549636668126789355991920452920806351939782281969098470635517019120996509180703896707990501216102290302162705699788457579330150149320348175742131887213742989509004374645723471497302400169849858253644606818874098604333865973357374444445825761600866472906771935670261641342221394488068630591190697667016958881530367047928341661857241378511420562236766886349565409774340321441504290366223243635878057759623855735794209219474650425139791831374

​ hint给了要用到威尔逊定理，于是复习了一下：

在初等数论中，威尔逊定理给出了判定一个自然数是否素数的充分必要条件。即：当且仅当p为素数时：( p -1 )! ≡ -1 ( mod p )

​ 推导过程：

​ 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
40
41
42
43
44
45
46
47
48
49
from math import gamma
import random
import gmpy2
import binascii
from Cryptodome.Util.number import *

def nextPrime(n):
    n += 2 if n & 1 else 1
    while not isPrime(n):
        n += 2
    return n

def getNewPrime():
    A = getPrime(512)
    B = nextPrime(A - random.randint(1e4,1e5))
    return nextPrime(gamma(B+2)%A)

pA=6814157460586876042804041951834304833424062437744287469257313954502540797027261340622077218188033865281590529907571701131297782609357118357982463723982789
pB=6814157460586876042804041951834304833424062437744287469257313954502540797027261340622077218188033865281590529907571701131297782609357118357982463723922147
qA=7145646366857234331692232566211321498245533826533958883943688415057871253511271731661019642050252046201115975396366275083424623329930477623781348477881291
qB=7145646366857234331692232566211321498245533826533958883943688415057871253511271731661019642050252046201115975396366275083424623329930477623781348477807457

e = 0x10001
n=4451906216583258787166698210560165433649728830889954633721198623488802305844782492171757604711145165920462286487680020347239300947225371917344589502941576734875830871998499135120227347066586066943289430156378296665669974728569678779668142712266780949126509440672273927433367293606776081254094682033167575930701870261219046464773708974194213798032346187463443317770758989273370488582862531630356263732232300508706676725203199729764016766683870925164232508407363688370458877688991733322055785233669885166225464068579486683574954699370175267031949720967812902215635630884502987094547523361027411501285252862476410213277925430392164226297316310465146003494714018456407793759170649913180823814850170639706664167149612984905056804131124522209409607977589884632999710708045656852149371030046919242039957767777840304466948549383597755811307383659188216421501912831203089570725388153416013596114462069777713822433178099904907224119
c=1996198968748552041728429851810599627895157160099076033250854211280074825148767841655949210593646824507865483166496070951130337321360509148527292165245205219296211294789087358959553387392928560150390604911087085313000622842025416521494799132969818997182731021267942464323979261593380113740152841984062184326431879167516288834455296913822921806893572566867611541664848820247889274979245086440402996661226884320574824077910315143756471444347386795428338020162169391827182914043434253974549636668126789355991920452920806351939782281969098470635517019120996509180703896707990501216102290302162705699788457579330150149320348175742131887213742989509004374645723471497302400169849858253644606818874098604333865973357374444445825761600866472906771935670261641342221394488068630591190697667016958881530367047928341661857241378511420562236766886349565409774340321441504290366223243635878057759623855735794209219474650425139791831374

#求 ((pA-2)!/(pB+1)!)%pA 的逆元，等于((pB+1)!)%pA ，等于gamma(pB+2)%pA
p = 1
max = (pA-2) - (pB+1)
for i in range(0,max):
    p = p * gmpy2.invert((pA-i-2),pA) % pA
p = nextPrime(p)
#求 ((qA-2)!/(qB+1)!)%qA 的逆元，等于((qB+1)!)%qA ，等于gamma(qB+2)%qA
q = 1
max = (qA-2) - (qB+1)
for i in range(0,max):
    q = q * gmpy2.invert((qA-i-2),qA) % qA
q = nextPrime(q)

r = gmpy2.iroot(gmpy2.mpz(n//(p*q**2)),3)
print(r)

print('p =',p)
print('q =',q)
print('r =',r[0])
phi = (p-1)*(q**2-q)*(r[0]**3-r[0]**2)
d = gmpy2.invert(e,phi)
m = pow(c, d, n)
print(long_to_bytes(m))

扫一扫，分享到微信

微信分享二维码
本站总访问量： 总访客次数：

tag:

梦想是成为全栈佬并养一只猫