To1in 的BUU刷题记录——2
4.[XNUCA2018]baby_crypto
The 26 letters a, b, c, ..., y, z correspond to the integers 0, 1, 2, ..., 25 len(key_a) = m len(key_k) = n c[i] = (p[i] * key_a[i % m] + key_k[i % n]) % 26 p is plain text, only lowercase letters are refered to. c is encrypted text I have appended the flag at the end of plain text, the format of which is like 'flagis......' Now you have the encrypted text, Good luck!
这道题只有一个加密公式以及输出的cipher，分级加密公式发现，加密方式和维吉尼亚密码的加密方式很像，只是多了key_a作为一个系数相乘。所以我们可以参考维吉尼亚的破译方式，对这道题进行分析。
维吉尼亚的破译方式一般是，先通过重合指数分析获得key的长度，再通过枚举以及计算交互重合指数，确定最终的key，最后进行还原。
下面介绍重合指数（IC）以及交互重合指数(MIC)的概念
-
当计算某个密文的重合指数（又名：重合概率，Index of Coincidence）时，即相当于求在某个密文中随机无放回地抽取其中的两位，这两位的字母相同的概率。值得注意的是，在单表代换的情况下， 明文与密文的IC值是相同的。
我们已经知道，维吉尼亚密码可以被分解为若干组平移密码来破译，而一个明文足够长的平移密码的重合指数接近0.0687。换言之，如果我们选取某个t值，使得分组后的密文的重合指数接近0.065，则说明选取的t值与密钥的长度是一致的。
-
假设x和y是两个长度分别为n和n’的字符串，x和y的交互重合指数定义为x中的一个随机元素与y中的一个随机元素相同的概率，记为，假设英文字母在x，y中出现次数分别为，那么交互重合指数就是：
交互重合指数的性质等同于重合指数的性质。
有了上面的知识，我们就可以开始写脚本了。
import gmpy2 dic_index = {'a': 0.08167, 'b': 0.01492, 'c': 0.02782, 'd': 0.04253, 'e': 0.12702, 'f': 0.02228, 'g': 0.02015, 'h': 0.06094, 'i': 0.06966, 'j': 0.00153, 'k': 0.00772, 'l': 0.04025, 'm': 0.02406, 'n': 0.06749, 'o': 0.07507, 'p': 0.01929, 'q': 0.00095, 'r': 0.05987, 's': 0.06327, 't': 0.09056, 'u': 0.02758, 'v': 0.00978, 'w': 0.02360, 'x': 0.00150, 'y': 0.01974, 'z': 0.00074} c = open('encrypted_message.txt', 'r').read() best_index = 0.065 # 英文文本的重合指数 alpha = 'abcdefghijklmnopqrstuvwxyz' # 重合指数 def Coincidence_index(s): frequency = {} # 初始化 for i in alpha: frequency[i] = 0 # 统计字母出现次数 for i in s: frequency[i] += 1 # 计算重合指数 index = 0 for i in alpha: index += frequency[i] * (frequency[i] - 1) return index / (len(s) * (len(s) - 1)) # 计算key_a key_b的最小公倍数,即周期 def get_t(c): t = [] # 这里我们假设了周期不超过100 for i in range(2, 100): index = 0 for j in range(i): # s是从cipher中取出的长为n*t的子密文段 s = ''.join(c[j + i * x] for x in range(len(c) // i)) index += Coincidence_index(s) # 最后计算t=i时，平均的重合指数，并与标准的进行对比 if abs(index / i - best_index) < 0.01: t.append(i) return t print(get_t(c)) # [6, 12, 18, 24, 30, 36, 42, 48, 54, 60, 66, 72, 78, 84, 90, 96] t = 6 # 下面的部分是爆破key_a key_b # 计算交互重合指数 def mutual_index_of_coincidence(m): frequency = {} # 初始化 for i in alpha: frequency[i] = 0 # 统计字母出现次数 for i in m: frequency[i] += 1 index = 0 for i in alpha: index += frequency[i] / len(m) * dic_index[i] return index # 获得明文 def decrypt(c, a, b): m = '' for i in c: m += alpha[((alpha.index(i) - b) * gmpy2.invert(a, 26)) % 26] return m # 获得一组密钥 def getkey(c): for i in range(26): if gmpy2.gcd(i, 26) != 1: continue for j in range(26): m = decrypt(c, i, j) index = mutual_index_of_coincidence(m) if abs(index - best_index) < 0.01: return i, j # 获得t组密钥 def get_key_in_t(c, t): for i in range(t): cipher = ''.join(c[i + x * t] for x in range(len(c) // t)) print(getkey(cipher)) get_key_in_t(c, t) # (19, 10) # (7, 9) # (23, 3) # (19, 24) # (7, 14) # (23, 15) # 据此我们可以猜测key_a=[19,7,23],key_b=[10,9,3,24,14,15] key_a = [19, 7, 23] key_b = [10, 9, 3, 24, 14, 15] m = '' a = len(key_a) b = len(key_b) for i in c: m += alpha[((alpha.index(i) - key_b[c.index(i) % b]) * gmpy2.invert(key_a[c.index(i) % a], 26)) % 26] print(m) #reference https://blog.csdn.net/weixin_44110537/article/details/107947158
5.[CISCN2018]sm
from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long from Crypto.Cipher import AES import hashlib from random import randint def gen512num(): order=[] while len(order)!=512: tmp=randint(1,512) if tmp not in order: order.append(tmp) ps=[] for i in range(512): p=getPrime(512-order[i]+10) pre=bin(p)[2:][0:(512-order[i])]+"1" ps.append(int(pre+"0"*(512-len(pre)),2)) return ps def run(): choose=getPrime(512) ps=gen512num() print "gen over" bchoose=bin(choose)[2:] r=0 bchoose = "0"*(512-len(bchoose))+bchoose for i in range(512): if bchoose[i]=='1': r=r^ps[i] flag=open("flag","r").read() key=long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(),16)) aes_obj = AES.new(key, AES.MODE_ECB) ef=aes_obj.encrypt(flag).encode("base64") open("r", "w").write(str(r)) open("ef","w").write(ef) gg="" for p in ps: gg+=str(p)+"\n" open("ps","w").write(gg) run()
可以看到题目用choose和bchoose生成了给我们的文件，以及aes加密过后的flag，所以这道题需要求bchoose。与其求解有关的是r和ps两个文件，其中r是由ps中一部分数异或生成的，异或是二进制下的加法，所以第25-27行我们可以把他写成矩阵形式：
所以我们只需要两边同乘ps构成的矩阵的逆即可求出bchoose。
ps=open('ps','r').readlines() c=[] for i in ps: c.append(eval(i.strip())) A=[] for i in c: A.append([int(x) for x in bin(i)[2:].zfill(512)]) r=eval(open('r','r').readline()) B=[int(x) for x in bin(r)[2:].zfill(512)] A=matrix(GF(2),A) B=matrix(GF(2),B) key=B*A.inverse() List=[] for i in key: List.append(i) print('List=',List) print('key=',key) #以上在sage中运行 #reference https://blog.csdn.net/weixin_44110537/article/details/107941247 from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long from Crypto.Cipher import AES import hashlib import base64 key=(1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1) choose=0 for i in range(512): choose=choose<<1 choose+=key[i] key = long_to_bytes(int(hashlib.md5(long_to_bytes(choose)).hexdigest(), 16)) aes_obj = AES.new(key, AES.MODE_ECB) ef=base64.b64decode(open('ef','rb').read().strip()) flag = aes_obj.decrypt(ef) print(flag)
Comments NOTHING