Crypto - onetimepad2, understand the nature of the algorithm

Posted on Edited on In Word count in article: 3.1k Reading time ≈ 3 mins.

0ctf quals 2017的题, 是之前做过的onetimepad的升级版. 因为这道题涉及到了有限域下乘法, 矩阵乘法, 快速幂, 离散对数, 所以记录一下(学费了学费了…

题目源码

先上代码

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
#!/usr/bin/env python
# coding=utf-8

from os import urandom

def process1(m, k):
    res = 0
    for i in bin(k)[2:]:
        res = res << 1;
        if (int(i)):
            res = res ^ m
        if (res >> 128):
            res = res ^ P
    return res

def process2(a, b):
    res = []
    res.append(process1(a[0], b[0]) ^ process1(a[1], b[2]))
    res.append(process1(a[0], b[1]) ^ process1(a[1], b[3]))
    res.append(process1(a[2], b[0]) ^ process1(a[3], b[2]))
    res.append(process1(a[2], b[1]) ^ process1(a[3], b[3]))
    return res

def nextrand(rand):
    global N, A, B
    tmp1 = [1, 0, 0, 1]
    tmp2 = [A, B, 0, 1]
    s = N
    N = process1(N, N)
    while s:
        if s % 2:
            tmp1 = process2(tmp2, tmp1)
        tmp2 = process2(tmp2, tmp2)
        s = s / 2
    return process1(rand, tmp1[0]) ^ tmp1[1]


def keygen():
    key = str2num(urandom(16))
    while True:
        yield key
        key = nextrand(key)

def encrypt(message):
    length = len(message)
    pad = '\x00' + urandom(15 - (length % 16))
    to_encrypt = message + pad
    res = ''
    generator = keygen()
    f = open('key.txt', 'w') # This is used to decrypt and of course you won't get it.
    for i, key in zip(range(0, length, 16), generator):
        f.write(hex(key)+'\n')
        res += num2str(str2num(to_encrypt[i:i+16]) ^ key)
    f.close()
    return res

def decrypt(ciphertxt):
    # TODO
    pass

def str2num(s):
    return int(s.encode('hex'), 16)

def num2str(n, block=16):
    s = hex(n)[2:].strip('L')
    s = '0' * ((32-len(s)) % 32) + s
    return s.decode('hex')

P = 0x100000000000000000000000000000087
A = 0xc6a5777f4dc639d7d1a50d6521e79bfd
B = 0x2e18716441db24baf79ff92393735345
N = str2num(urandom(16))
assert N != 0

if __name__ == '__main__':
    with open('top_secret') as f:
        top_secret = f.read().strip()
    assert len(top_secret) == 16
    plain = "One-Time Pad is used here. You won't know that the flag is flag{%s}." % top_secret

    with open('ciphertxt', 'w') as f:
        f.write(encrypt(plain).encode('hex')+'\n')


整个流程挺简单的, 就是对palin加密. 但是里面的每个函数都挺有意思的. 下面一个一个来分析

process1(m,k)

先看process1(m,k)
很多时候这种看着就像在一个域里面做的计算, 可以随便几个小的数进去看看结果是什么. 如果是一些简单的操作比如加减乘除啥的一般很容易能看出来.
而这个process1(m,k)就是在GF(2^128)下做m*k. 可以理解为就是一个乘法吧.

为什么是个乘法呢?

平时纸上算乘法的时候都要用到竖式, 而这里的算法就是一个先计算高位的竖式.从最高位开始一位一位往下乘.(这个用纸上写出来会好理解吧, 这里就不写了

process2(a,b)

这个函数就是个矩阵的乘法, 输出的就是 矩阵a * 矩阵b.

怎么看出来?

经验? 一般遇到这种两个矩阵(数列)特定下标在进行加和乘计算的, 把每个式子写出来, 看能不能写成两个矩阵之间的操作, 而这里就是一个矩阵的乘法

nextrand(rand)

这个函数才是重点!!!

1
2
3
4
5
6
7
8
9
10
11
12
def nextrand(rand):
    global N, A, B
    tmp1 = [1, 0, 0, 1]
    tmp2 = [A, B, 0, 1]
    s = N
    N = process1(N, N)
    while s:
        if s % 2:
            tmp1 = process2(tmp2, tmp1)
        tmp2 = process2(tmp2, tmp2)
        s = s / 2
    return process1(rand, tmp1[0]) ^ tmp1[1]

看不懂的地方就是中间的循环结构, 不知道具体在干什么. 查了一下wp才知道, 这是个快速幂!!!没想到第一次接触快速幂是在密码的题目里…

快速幂

简单说一下快速幂吧, 计算机计算一个数的高次幂(例如3^60^)的时候, 如果直接计算60个3相乘就会特别慢, 但是可以把 3^60^ 化成 9^30^, 这样就只需要乘30次了.
继续算下去会发生一个问题 3^60^ = 9^30^ = 81^15^ 这里有个15次幂, 如果除以2就是7.5, 7.5次幂是没办法计算的. 所以这里有个操作, 就是81^15^ = 81^14^ 81^1^, 然后继续对81^14^进行化简.
所以最终的结果就是

1
2
3
3^60 = 9^30 = 81^15 = 81^14 * 81^1 = 6561^7 + 81^1 =....
= 43046721^3 * 43046721^1 * 6561^1 * 81^1
= 1853020188851841^1 * 43046721^1 * 6561^1 * 81^1

可以看到结果有个特点, 就是最后一定会化成多个数的一次幂的乘积.而什么时候能分出一次幂呢? *就是次幂为奇数的时候!!!

回到函数

回到函数里, 结合上面说的快速幂的算法, 可以看出这个循环就是计算
tmp1 = tmp2^s,

未完待续….