Soreat_u's Blog

Intended Solution to Crypto Problems in VN Open Competition

 Writeup

File

题目文件可以在BuuCTF上找到： https://buuoj.cn/challenges

CRT

考点主要是在中国剩余定理(CRT)这边。

平时遇到的要用CRT基本上都是只有一个解的，但是广义上的CRT是可能不止一解的。

所以就随便敲了几行代码出了这一题。

Intended Solution 1

在《信息安全数学基础》这本书上，CRT那边是给了两种证明方法的。

  • 构造证明
  • 递归证明

构造证明就是直接把解法构造出来。

递归证明挺有意思的，因为它联系到了前面学到的求解一次同余式的内容。 $$ \begin{aligned} \begin{cases} x &\equiv c_1 \pmod{n_1}\newline x &\equiv c_2 \pmod{n_2}\newline &\vdots \newline x &\equiv c_i \pmod{n_i} \end{cases} \end{aligned} $$ 怎么解这个玩意呢？

我们可以先把下标为1的同余式转化成等式： $$ x \equiv c_1 \pmod{n_1} \Leftrightarrow x = c_1 + k_1 n_1 $$ 然后我们把这个$x$的等式代入下标为2的同余式中， $$ c_1 + k_1n_1 \equiv c_2 \pmod{n_2} $$ 化简下， $$ n_1k_1 \equiv c_2 - c_1 \pmod{n_2} $$ 这就是一个求解一次同余式的问题，未知量是这个$k_1$。

求出$k_1$后，代入回$x = c_1 + k_1 n_1$，我们就可以得到$x \pmod{n_1 n_2}$的结果，然后一直这样操作下去，直到获得$x \pmod{n_1 n_2 \cdots n_i}$的结果。

直接引用我之前某个Notes 中的内容：

Screen Shot 2020-03-03 at 1.07.50 AM

由于我们这边的模数$n$是这样取的：ms = [getRandomNBitInteger(128) for i in range(8)]

所以，很大概率上$\gcd(n_1, n_2)$会不等于1，导致多解（由于$x$是确实有的，所以不存在无解的情况）。

多解怎么办呢？

一个办法就是，我们在递归求解的时候，一定要求出这个一次同余式的所有解，再代入下一组。

一个草草的实现：

 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

import hashlib

def egcd(a, b):
    '''
    Extended Euclidean Algorithm.
    returns x, y, gcd(a,b) such that ax + by = gcd(a,b).
    '''
    u, u1 = 1, 0
    v, v1 = 0, 1
    while b:
        q, r = divmod(a, b)
        u, u1 = u1, u - q * u1
        v, v1 = v1, v - q * v1
        a, b = b, r
    return u, v, a

def gcd(a,b):
    '''
    Calculate the Greatest Common Divisor of a, b.
    '''
    # a, b = (b, a) if a < b else (a, b)
    while b:
        a, b = b, a % b
    return a

def LinearCongruenceSolver(a, c, m):
    '''
    Solve x such that `a * x ≡ c (mod m)`,
    returns all the possible *x*s (mod m), None if no solution.
    '''
    g = gcd(a, m)
    if c % g:
        return None
    u0 = egcd(a, m)[0]
    return [(c * u0 + k * m) // g % m for k in range(g)]


def CRT(ai, mi):
    '''
    Chinese Remainder Theorem.
    solve x such that `x ≡ ai[0] (mod mi[0]) ...`.
    '''
    assert(isinstance(mi, list) and isinstance(ai, list))
    a_s, m = set([ai[0]]), mi[0]
    for a1, m1 in zip(ai[1:], mi[1:]):
        # print(f"m1: {m1}")
        new_as = set()
        for a in a_s:
            ks = LinearCongruenceSolver(m, a1 - a, m1)
            if not ks:
                continue
            for k in ks:
                new_as.add(a + k*m)
        a_s = new_as
        m = m * m1
    return a_s, m


ms = [284461942441737992421992210219060544764, 218436209063777179204189567410606431578, 288673438109933649911276214358963643204, 239232622368515797881077917549177081575, 206264514127207567149705234795160750411, 338915547568169045185589241329271490503, 246545359356590592172327146579550739141, 219686182542160835171493232381209438048]
cs = [273520784183505348818648859874365852523, 128223029008039086716133583343107528289, 5111091025406771271167772696866083419, 33462335595116820423587878784664448439, 145377705960376589843356778052388633917, 128158421725856807614557926615949143594, 230664008267846531848877293149791626711, 94549019966480959688919233343793910003]


sol = CRT(cs, ms)
for x in sol[0]:
    if "4b93deeb" in  hashlib.sha256(str(x).encode()).hexdigest():
        print(x)
        flag = "flag{" + hashlib.sha256(str(x).encode()).hexdigest() + "}"
        print(flag)
        break

得到flag：flag{fa71921acdc2a756897d6b0c7ee41a7397386de2e7cde5b6adb525414b93deeb}

Intended Solution 2

不过后来想了想，由于模数里面肯定存在不互素的，我们实际上可以把这些不互素的，除去他们的最大公约数，也就是相当于算他们的最小公倍数$n_{lcm}$。

$x \pmod{n_{lcm}}$肯定就只有1解，假如说是$x_{lcm}$。

那么，$x$在$\mathbb{Z}$里的解就都可以表示为 $$ x = x_{lcm} + k\cdot n_{lcm} $$ 只要我们不断地增加这个$k$，然后检验sha256，就能找到那个想要的$x$。

甚至。。。我怀疑大家应该都是这么做的。。

wtcl。

Fast

这题灵感来源于某本书（An Introduction to Mathematical Cryptography）上的一道课后习题。

Screen Shot 2020-03-03 at 1.24.44 AM

想法挺好的。

但是肯定有问题。

没问题的话，那我们现在用的RSA应该有大概率上就是这个版本的了。

其实仔细观察的话，一眼就能看出来问题所在：

$$ g^{p-1} \equiv 1 \pmod{p} $$ 那么， $$ g_1 = g^{r_1(p-1)} \equiv 1 \pmod{p} $$ 因此， $$ g^{r_1(p-1)} - 1 = k\cdot p $$ 只要 $$ \gcd(g_1 - 1, N) $$ 即可分解出$p$，再用$N$整除下$p$即可得到$q$。

然后直接调用decrypt就能拿到flag了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

from Crypto.Util.number import *


N = 18680643069610062851842282268594530254220611012409807422663284548187050713427682950720783343430650669361838067625768840896513125210105582070603021732086193955893838077699465426052925750736212977005683541174195320832791835197114668838654054444342903298662698415765898335350206380896849522280206304272801325820946987172164086644949521111058774180676742851681476123338557138770304164634321305204827406522957769478330124484710532963132900017800651579612646041955628867746525508376194147796920773364680264059390497210260540079810501777507814448518995581208169818764701641258963569599247156932381367802991222265241699715283
g1 = 9143176283300810019842153344177123108612540016879643936458724056602746667157014763960725115919119704406826965726023263657276550779443988565368344040505696950820899770544814163379169539926317676679421275092688200844094929042154854719312788471536324082041360841253720783220459009201882865091829118575721525038404689868986360373373122049951274015083845966946475469982961355934516388706446794517870569063777231434618411404965077775991870069073539415961610645268985004687402050059891500490949250730689691141954694508001895390336750734542724392709744200091587065816283592253967715080611459937165344139809223328071517060208
c1, c2 = (3976514029543484086411168675941075541422870678409709261442618832911574665848843566949154289825219682094719766762966082440586568781997199077781276145091509192208487682443007457513002005089654365915817414921574344557570444253187757317116858499013550050579856269915915792827620535138057468531410166908365364129001407147467636145589396570815405571923148902993581000542566387654639930651683044853608873583911638108204074537952317056718986683846742909366072461130053275195290631718363272923316002049685111871888148244026652658482359335651889139243735138819453744763293112267738369048641158946411500606588429007794613880534, 18524535479582837341745231233387403662294605513261199630593257391163433751052467785080620993007681605662927226603747560698627838567782891522546977611597418150309028806158429831471152782211111046118637630899456903846057977815397285171313888516791822545633820066408276065732715348834255021260666966934592884548856831383262013360819013814149529393178712576141627031723067564594282618223686778534522328204603249125537258294561872667849498796757523663858312311082034700705599706428944071848443463999351872482644584735305157234751806369172212650596041534643187402820399145288902719434158798638116870325144146218568810928344)

p = GCD(N, g1 - 1)
q = N // p

def decrypt(c1, c2):
    xp = c1 % p
    xq = c2 % q
    # Chinese Remainder Theorem
    m = (xp*inverse(q, p)*q + xq*inverse(p, q)*p) % N
    return m

m = decrypt(c1, c2)
print(long_to_bytes(m))
# flag{1CE9514E-12AF-49BE-B002-6A3D7E6078FA}

所以啊。。

有些题目，虽然看上去是挺复杂的：

Screen Shot 2020-03-03 at 1.31.56 AM

但是，实际上是很简单的。

Backtrace

这题出的最轻松了，就10行代码就完事了。

就是想考一下对MT19937的掌握程度。

因为之前遇到过好几个要逆一下MT19937的题目：

  • EIS 2019

  • Byte CTF 2019

  • GXYCTF 2019

所以，就想考下如何从MT19937的1000个输出反推出前4个输出。

我之前也写过一个PRNG study ，不过写的实在是tcl。

推荐阅读：

Cryptopals 上也有一个叫你去日MT19937种子的任务。

badmoney师傅也有一篇post写的很好：浅析MT19937伪随机数生成算法

说来惭愧，想着去搞一下Cryptopals的，一直没去搞。。

画了一张简单的图：

image-20200303013927730

希望有助于理解。

具体分析就不写了。

贴下exp：

 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

def unBitShiftRightXor(value, shift):
    i = 0
    while i * shift < 32:
        part_mask =  ((0xffffffff << (32 - shift)) & 0xffffffff) >> (i * shift)
        part = value & part_mask
        value ^= part >> shift
        i += 1
    return value

def unBitShiftLeftXor(value, shift, mask):
    i = 0
    while i * shift < 32:
        part_mask = ((0xffffffff >> (32 - shift)) & 0xffffffff) << (i * shift)
        part = value & part_mask
        value ^= (part << shift) & mask
        i += 1
    return value

def getState(number):
    number = unBitShiftRightXor(number, 18)
    number = unBitShiftLeftXor(number, 15, 0xefc60000)
    number = unBitShiftLeftXor(number, 7, 0x9d2c5680)
    number = unBitShiftRightXor(number, 11)
    return number

def backtrace(numbers):
    """
    Returns the initial state of the MT PRNG based on list of the output numbers
    """
    # assert(len(numbers) == 624)
    state = []
    for number in numbers:
        state.append(getState(number))
    return state

def getOldStates(states):
    for i in range(3, -1, -1):
        tmp = states[i + 624] ^ states[i + 397]
        if tmp & 0x80000000 == 0x80000000:
            tmp ^= 0x9908b0df
        res = (tmp & 0x40000000) << 1

        tmp = states[i - 1 + 624] ^ states[i + 396]
        if tmp & 0x80000000 == 0x80000000:
            tmp ^= 0x9908b0df
            res |= 1
        res |= (tmp & 0x3fffffff) << 1
        # assert(res == states[i])
        states[i] = res

def next(states, i):
    y = (states[i] & 0x80000000) + (states[(i+1) % 624] & 0x7FFFFFFF)
    n = 0x9908b0df if y & 1 else 0
    res = states[(i+397) % 624] ^ (y >> 1) ^ n
    return res



with open('output.txt', 'r') as f:
    data = f.read()

outputs = [int(output) for output in data.split('\n')[:-1]]
states = [0]*4 + backtrace(outputs)
getOldStates(states)

import random
random.setstate(tuple([3, tuple(states[:624] + [0]), None]))
flag = "flag{" + ''.join(str(random.getrandbits(32)) for _ in range(4)) + "}"
print(flag)
# flag{1886737465387686573924175753923879771350}