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中的一个随机元素相同的概率，记为$MI_C(x,y)$，假设英文字母在x，y中出现次数分别为$f_i f'_i$，那么交互重合指数就是：

  交互重合指数的性质等同于重合指数的性质。

有了上面的知识，我们就可以开始写脚本了。

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)