文章 - PlaidCTF 2019 CRYPTO Writeup

PlaidCTF 2019 CRYPTO Writeup

上周末参加了一下PlaidCTF 2019国际比赛，详情可见CTF TIME，下面主要总结分享一下两道密码题的解题思路。

1.R u SAd?

1.1 分析

首先查看题目文件，共有三个文件rusad(python加密程序)、flag.enc(加密后的数据)、key.sad.pub(提供的公钥信息)。主要分析rusad加密代码，这是一个RSA加解密程序，首先定义了一个Key类，私钥参数为P、Q、D、DmP1、Dmq1，genkey函数生成RSA参数。main函数的功能是生成一个4096位的key，将key中的公钥信息输出到文件即key.sad.pub，其中包含N、E、iQmP、iPmQ，然后就是读入flag调用encrypt函数加密输出到文件flag.enc。

class Key:
    PRIVATE_INFO = ['P', 'Q', 'D', 'DmP1', 'DmQ1']
    def __init__(self, **kwargs):
        for k, v in kwargs.items():
            setattr(self, k, v)
        assert self.bits % 8 == 0

    def ispub(self):
        return all(not hasattr(self, key) for key in self.PRIVATE_INFO)

    def ispriv(self):
        return all(hasattr(self, key) for key in self.PRIVATE_INFO)

    def pub(self):
        p = deepcopy(self)
        for key in self.PRIVATE_INFO:
            if hasattr(p, key):
                delattr(p, key)
        return p

    def priv(self):
        raise NotImplementedError()
def genkey(bits):
    assert bits % 2 == 0
    while True:
        p = genprime(bits // 2)
        q = genprime(bits // 2)
        e = 65537
        d, _, g = egcd(e, (p-1) * (q-1))
        if g != 1: continue
        iQmP, iPmQ, _ = egcd(q, p)
        return Key(
            N=p*q, P=p, Q=q, E=e, D=d%((p-1)*(q-1)), DmP1=d%(p-1), DmQ1=d%(q-1),
            iQmP=iQmP%p, iPmQ=iPmQ%q, bits=bits,
        )
def encrypt(key, data):
    data = bytes2num(pad(data, key.bits))
    assert 0 <= data and data < key.N
    data = pow(data, key.E, key.N)
    return num2bytes(data, key.bits // 8)

def decrypt(key, data):
    assert key.ispriv() and len(data) * 8 == key.bits
    data = bytes2num(data)
    assert 0 <= data and data < key.N
    v1 = pow(data, key.DmP1, key.P)
    v2 = pow(data, key.DmQ1, key.Q)
    data = (v2 * key.P * key.iPmQ + v1 * key.Q * key.iQmP) % key.N
    return unpad(num2bytes(data, key.bits // 8))

1.2 思路

注意到公钥文件key.sad.pub中包含的参数有N，E,iQmP,iPmQ，其中iQmP, iPmQ, _ = egcd(q, p);iQmP=iQmP%p, iPmQ=iPmQ%q

iQmP, iPmQ, _ = egcd(q, p)#即iQmp*q+iPmQ*p=1,其中一个为负数，一个为正数；
iQmP = iQmP%p             #iQmP = iQmP + p * i(i=0或1)
iPmQ = iPmQ%q             #iPmQ = iPmQ + Q * i(i=0或1)

最终得到iQmp*q+iPmQ*p=p*q+1=N+1，结合p*q=N可以得到两个方程，p、q两个未知数两个方程，直接求解即可：

b = N+1
a = gmpy2.iroot(b*b-4*iQmP*iPmQ*N, 2)[0]
p1 = (b+a)/(2*iQmP)
# p2 = (b-a)/(2*iQmP)
# q1 = (b+a)/(2*iPmQ)
q2 = (b-a)/(2*iPmQ)
# if (p1*q2==N):
#   print("success")

1.3 EXP

求解得到P和Q之后，正常计算欧拉函数phi(N)，计算私钥D。由于加密进行了填充，直接用D解密存在问题，将参数代入到Key中，然后调用decrypt函数解密即可，将代码写在rusad后面。

f = argparse.FileType('rb')("key.sad.pub")
key = pickle.load(f)
key.Q = 25004672227855409995386175663336188685177638541286666056441830847618100808198668167307814236224429885295241140194633625051478252429462828073782848889819460674774292004752724556602147320684206242726073358822655212944688523823150236245522627662371134165404316388528738697090763677910441487876514668914442018764569771021916503649822836288868439220382922721194436569302106969570041514638164319835688101248578648742016186666021527781591528560611986692317045407081396778512783312692838307769559661780971287324753785154074832628454871505400166651610503632212720604214996108967812794633118832616768643612648168060802523582631
key.P = 31659077809885706699482361830477717572837081779677626435829903374921581240849180063108552019274021826092781287218568613206006085334956822705610578514426596962412655157776833178744403034727698399320215892200440936975683502329350531806920697009386909154114556681774784614085691096050135180228131842452179315216957730905902673882170120973148157907231188547167482558383495097819905373068326760590890291412820411304614611983343203819383860434964843931325658872603238498210722446318497674396725811567139923114789843056157733621133155720503541819498078610854651245426825738313809229403279974283490718799392611854934535622307
if(key.P*key.Q==key.N):
    print("success")
e = 65537
d, _, g = egcd(e, (key.P-1) * (key.Q-1))
key.DmP1=d%(key.P-1)
key.DmQ1=d%(key.Q-1)
key.bits=4096
with open('flag.enc', 'rb') as f:
    cipher = f.read()
# print(len(cipher)*8)
m = decrypt(key,cipher)
print(m)

2.Horst

2.1 分析

题目给了一个python加密程序和一段密文，同样首先分析加密程序。程序首先定义了一个Permutation类，数据类型是列表list，主要关注的函数为乘法运算mul和逆元运算inv，其中cycles函数为输出时的转换函数，加解密过程中不涉及cycles函数，因此不需要考虑。可以看到程序随机生成一个密钥K，也就是flag，然后随机生成一组数据pt，使用K对其加密得到加密数据ct。题目提供了两组pt和ct数据，需要从中恢复K。

import os
import random
from hashlib import sha1

M = 3
N = 64
n = 2

class Permutation:
    def __init__(self, L):
        self.n = len(L)
        self.L = L
        assert all(i in L for i in range(self.n))

    def __mul__(self, other):
        assert self.n == other.n
        return Permutation([other.L[self.L[i]] for i in range(self.n)])

    def __eq__(self, other):
        return self.L == other.L

    def inv(self):
        return Permutation([self.L.index(i) for i in range(self.n)])

    def cycles(self):
        elts = list(range(self.n))
        cycles = []
        while len(elts) > 0:
            cur = []
            i = elts[0]
            while i not in cur:
                cur.append(i)
                elts.remove(i)
                i = self.L[i]
            cycles.append(cur)
        return cycles

    def __getitem__(self, i):
        return self.L[i]

    def __str__(self):
        return "".join("({})".format(" ".join(str(e) for e in c)) for c in self.cycles())

    def __repr__(self):
        return "Permutation({})".format(self.L)


def random_permutation(n):
    random.seed(os.urandom(100))
    L = list(range(n))
    for i in range(n-1):
        j = random.randint(i, n-1)
        L[i], L[j] = L[j], L[i]
    return Permutation(L)

for i in range(100):
    x = random_permutation(N)
    assert x * x.inv() == Permutation(list(range(N)))

def encrypt(m, k):
    x, y = m
    for i in range(M):
        x, y = (y, x * k.inv() * y * k)
    return x, y

def decrypt(c, k):
    x, y = c
    for i in range(M):
        x, y = (y * k.inv() * x.inv() * k, x)
    return x, y

if __name__ == "__main__":
    k = random_permutation(N)
    print "The flag is: PCTF{%s}" % sha1(str(k)).hexdigest()
    pairs = []
    for i in range(n):
        pt = random_permutation(N), random_permutation(N)
        ct = encrypt(pt, k)
        assert pt == decrypt(ct, k)
        pairs.append((pt,ct))
    with open("data.txt", "w") as f:
        f.write(str(pairs))

2.2 思路

分析加密函数，得知加密过程是进行三轮运算x, y = (y, x * k.inv() * y * k)，对于这里定义的list操作，[0,1,2,3,4,...,63]为一个单位元，其中k.inv()*k =单位元可以将k.inv()理解为k^-1。经过测试这里的list操作满足乘法结合律(a*b)*c=a*(b*c)，不满足乘法交换律a*b!=b*a。

## 第一轮
x1 = y
y1 = x*k^-1*y*k
## 第二轮
x2 = y1 = x*k^-1*y*k
y2 = x1*k^-1*y1*k = y*k^-1*x*k^-1*y*k*k 
## 第三轮
x3 = y2 = y*k^-1*x*k^-1*y*k*k
y3 = x2*k^-1*y2*k = (x*k^-1*y*k)*k^-1*(y*k^-1*x*k^-1*y*k*k)*k 
##
#得到: y3 = x*k^-1*y*x3*k (x,y明文pt,x3,y3密文ct)
##  k*x^-1*y3 = y*x3*k

分析加密流程可以得到k*A=B*k;A=x^-1*y3;B=y*x3，题目提供两组明密文对，因此可以计算得到两组A、B数据

计算得到：

A1=[56, 31, 46, 28, 5, 52, 12, 14, 10, 34, 22, 47, 6, 0, 39, 17, 32, 38, 13, 40, 4, 18, 15, 55, 50, 24, 9, 45, 59, 41, 23, 43, 26, 35, 29, 62, 63, 44, 51, 37, 58, 61, 19, 1, 48, 36, 11, 21, 25, 27, 20, 57, 53, 7, 33, 49, 16, 2, 54, 8, 3, 60, 42, 30]
B1=[48, 19, 58, 24, 20, 47, 31, 53, 59, 23, 1, 5, 42, 37, 33, 55, 2, 29, 12, 27, 8, 11, 56, 9, 44, 63, 14, 25, 10, 49, 61, 60, 22, 0, 18, 17, 40, 51, 15, 41, 50, 7, 36, 32, 26, 43, 16, 62, 21, 38, 54, 3, 45, 4, 46, 57, 13, 35, 30, 39, 6, 34, 28, 52]
A2=[40, 16, 48, 27, 18, 7, 55, 10, 9, 13, 5, 31, 57, 14, 35, 45, 60, 23, 41, 15, 63, 30, 39, 8, 33, 43, 59, 44, 6, 50, 1, 25, 52, 26, 38, 46, 21, 2, 12, 20, 49, 42, 34, 11, 0, 37, 47, 36, 32, 24, 51, 28, 4, 3, 22, 61, 54, 19, 58, 29, 62, 56, 17, 53]
B2=[3, 54, 28, 2, 44, 59, 27, 31, 50, 4, 35, 36, 21, 0, 8, 19, 38, 20, 14, 25, 16, 61, 26, 10, 57, 39, 55, 60, 33, 29, 52, 22, 49, 9, 30, 5, 58, 45, 13, 63, 1, 18, 15, 17, 32, 42, 6, 53, 37, 11, 43, 62, 24, 48, 56, 47, 34, 51, 41, 40, 46, 12, 23, 7]

再次分析乘法操作：[other.L[self.L[i]] for i in range(self.n)]

假设k=[k0,k1,k2,k3,k4,...,k63],k*A=B*k等价于A[ki]=k[B[i]]; i=0,1,2,3,...,63。

现在考虑找到满足B[i]=i的数据，在B2中找到B2[29]=29因此i=29代入上诉式子得到：A2[k29]=k[29]，同样在A2中搜索A[i]=[i]的数据得到A2[58]=58，因此k29=58

for i in range(64):
    if(i==B2.index(i)):
        print i
    if(i==A2.index(i)):
        print i
#29
#58
#[Finished in 0.2s]

2.3 EXP

在得到一组数据k29=58，就能根据A[ki]=k[B[i]]; i=0,1,2,3,...,63式子将其余数据推算出来。

例如：在B1和A1中找到相关的i，j，使得B1[i]=29;A1[j]=58，则A1[ki]=k29=58，就有k[i]=j

K = dict.fromkeys(A1, -1)
k = []
i = 29
value = 58
while i not in k:
    k.append(i)
    K[i] = value
    value = A1.index(value)
    i = B1.index(i)
print len(k)
print k
print K

通过上诉代码可先得到8组数据，再代入A2、B2中搜索即可得到所有数据：

K = {0: 59, 1: 2, 2: 50, 3: 29, 4: 55, 5: 15, 6: 43, 7: 30, 8: 27, 9: 6, 10: 57, 11: 22, 12: 7, 13: 26, 14: 3, 15: 35, 16: 24, 17: 40, 18: 53, 19: 46, 20: 49, 21: 10, 22: 16, 23: 12, 24: 41, 25: 47, 26: 60, 27: 11, 28: 51, 29: 58, 30: 4, 31: 1, 32: 56, 33: 28, 34: 52, 35: 19, 36: 39, 37: 9, 38: 33, 39: 36, 40: 37, 41: 63, 42: 14, 43: 0, 44: 61, 45: 13, 46: 25, 47: 17, 48: 8, 49: 54, 50: 44, 51: 34, 52: 18, 53: 23, 54: 48, 55: 62, 56: 32, 57: 42, 58: 20, 59: 45, 60: 31, 61: 5, 62: 38, 63: 21}
# 将字典K转成列表k代入计算
k = Permutation([59, 2, 50, 29, 55, 15, 43, 30, 27, 6, 57, 22, 7, 26, 3, 35, 24, 40, 53, 46, 49, 10, 16, 12, 41, 47, 60, 11, 51, 58, 4, 1, 56, 28, 52, 19, 39, 9, 33, 36, 37, 63, 14, 0, 61, 13, 25, 17, 8, 54, 44, 34, 18, 23, 48, 62, 32, 42, 20, 45, 31, 5, 38, 21])
print "The flag is: PCTF{%s}" % sha1(str(k)).hexdigest()

3.总结

这次的两个python加解密题还是比较简单的，主要考察的基础数学运算。RuSAd只要理解了egcd函数的原理就能直接解题，Horst相对麻烦一下，首先需要理解题目定义的list运算，然后推算出三轮加密的实际含义，最后是通过找不动点得到第一组数据，由一组数据推所有数据。