PlaidCTF 2019 CRYPTO Writeup

2019-04-22 约 2738 字 预计阅读 6 分钟

声明:本文 【PlaidCTF 2019 CRYPTO Writeup】 由作者 aliyuuu 于 2019-04-22 09:50:00 首发 先知社区 曾经 浏览数 3 次

感谢 aliyuuu 的辛苦付出!

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运算,然后推算出三轮加密的实际含义,最后是通过找不动点得到第一组数据,由一组数据推所有数据。

关键词:[‘安全技术’, ‘CTF’]


author

旭达网络

旭达网络技术博客,曾记录各种技术问题,一贴搞定.
本文采用知识共享署名 4.0 国际许可协议进行许可。

We notice you're using an adblocker. If you like our webite please keep us running by whitelisting this site in your ad blocker. We’re serving quality, related ads only. Thank you!

I've whitelisted your website.

Not now