SUSCTF-Writeup(Crypto)

large case

这题没有提供e，给了p、q、r，并且条件里说了e由三个素因子组成，所以不难想到分解p-1，q-1，r-1，从而对e的可能值进行组合。不过就算组合过了，也不能用常规方法解题，因为本题e phi不互素，所以考虑对其开根，又考虑到这题的e会相对较大，所以用AMM算法对其开根。AMM算法详见 Intended Solution to Crypto Problems in NCTF 2019 | Soreat_u's Blog (soreatu.com)

在这之前可以对e的因子进行猜测，由于需要使用到CRT组合，所以因子不会太大，并且因子不会是共有的因数，于是可以猜测e使用p-1中的757，q-1中的66553，r-1中的5156273（如果不对，再进行调整，可供调整的选择不多，一些小的因数比如3、7，可以直接跑，很快就可以知道不满足）。

这里e值的选择，在看了NepNep师傅的wp之后学到了一手k次剩余的判断方法（这波是信安数基学的不扎实） 。由RSA加密，c是模p的e次剩余，那么c必然也是模p的ep次剩余（因为ep是e的因⼦）。同理c是模q 的eq次剩余，c是模r的er次剩余。⽤这个条件筛⼀下$ep,eq,er$，得到 $ep = 757, eq = 2$或 $66553$， $er = 2$ 或 $5156273$。然后我们知道因子不能是公有的因数，所以e的值只有一种可能。

def is_kth_residue(a, k, p):
	k = k % (p-1)
	a = a % p
	return True if pow(a, (p-1)//k, p) == 1 else False

for i in range(len(p_minus_1_factor)):
	if is_kth_residue(c, p_minus_1_factor[i], p):
		print(f"e_p: {p_minus_1_factor[i]}")
for i in range(len(q_minus_1_factor)):
	if is_kth_residue(c, q_minus_1_factor[i], q):
		print(f"e_q: {q_minus_1_factor[i]}")
for i in range(len(r_minus_1_factor)):
	if is_kth_residue(c, r_minus_1_factor[i], r):
		print(f"e_q: {r_minus_1_factor[i]}")

可以注意到flag的长度在1025-2048比特之间，所以我们不需要考虑r的部分，只考虑p、q。有了猜测的e，我们就可以把多于2048的pad去掉，留下一部分\x00

之后分别计算模p和模q的情况

对上面的式子使用AMM算法，就可以得到mp、mq的列表，然后使用CRT对其组合，用SUSCTF校验即可，整个过程大约十几分钟。

from Crypto.Util.number import *
import time
import random
c = 2832775557487418816663494645849097066925967799754895979829784499040437385450603537732862576495758207240632734290947928291961063611897822688909447511260639429367768479378599532712621774918733304857247099714044615691877995534173849302353620399896455615474093581673774297730056975663792651743809514320379189748228186812362112753688073161375690508818356712739795492736743994105438575736577194329751372142329306630950863097761601196849158280502041616545429586870751042908365507050717385205371671658706357669408813112610215766159761927196639404951251535622349916877296956767883165696947955379829079278948514755758174884809479690995427980775293393456403529481055942899970158049070109142310832516606657100119207595631431023336544432679282722485978175459551109374822024850128128796213791820270973849303929674648894135672365776376696816104314090776423931007123128977218361110636927878232444348690591774581974226318856099862175526133892
p = 127846753573603084140032502367311687577517286192893830888210505400863747960458410091624928485398237221748639465569360357083610343901195273740653100259873512668015324620239720302434418836556626441491996755736644886234427063508445212117628827393696641594389475794455769831224080974098671804484986257952189021223
q = 145855456487495382044171198958191111759614682359121667762539436558951453420409098978730659224765186993202647878416602503196995715156477020462357271957894750950465766809623184979464111968346235929375202282811814079958258215558862385475337911665725569669510022344713444067774094112542265293776098223712339100693
r = 165967627827619421909025667485886197280531070386062799707570138462960892786375448755168117226002965841166040777799690060003514218907279202146293715568618421507166624010447447835500614000601643150187327886055136468260391127675012777934049855029499330117864969171026445847229725440665179150874362143944727374907
# fp = [2, 7, 757, 1709, 85015583 , 339028665499, 149105250954771885483776047]
# fq = [2, 3, 66553,81768440203, 84405986771, 38037107558208320033, 16137718604846030589135490851713]
# fr = [2, 5156273, 10012111, 11607389, 68872137169799749, 9691125310820433463]
# e_list = []
# for i in fp:
#     for j in fq:
#         for k in fr:
#             e_list.append(i*j*k)
# print(e)
e = 757 * 66553 *5156273
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            j = - discrete_log(d, a)
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return result

def findAllPRoot(p, e):
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    return proot
def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp
n=p*q*r
# tmp = pow(int(1<<1024),int(e),n)
tmp = 2794203162952680694875426764547234241112236710433123774476303768639242351566319207612773628883250609134659396011750795113351981408956541443986997306105869563120160376511155383832592237253107342927670770094240045412123787825031261131955433947396826167219004667304636335427373984885928591487526163086731412269053200262557436796244981351739716063496342017497841802350338687039580076905949641402173299773716271511639533823663740291331408514189072329517625171120136705677613965360814741037067953490597466636290290725085921897578223035738383932219334876192857916281288629471625406358741715112812225419217748429901501082216480552255233899368763011103720695984389763743356559299690991047172680728215625377751497287365075742929734077041112027582350488222091280835389084342367259161290929159777553525296385682720359499417021854388648183468514374707670903349123145819166174953312125050648613697527164777642887701658900202492759171557250
realc=inverse_mod(tmp,n)*c%n
er=5156273
der = inverse_mod(er,(p-1)*(q-1))
c = pow(int(realc), der,p*q)
dp = inverse_mod(66553, p-1)
dq = inverse_mod(757, q-1)
cp = pow(int(c),int(dp),int(p))
cq = pow(int(c),int(dq),int(q))
mp = AMM(cp, 757, p)
mq = AMM(cq, 66553, q)
p_proot = findAllPRoot(p, 757)
q_proot = findAllPRoot(q, 66553)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)

start = time.time()
print('Start CRT...')
for mpp in mps:
    print(mpp)
    for mqq in mqs:
        solution = crt([int(mpp), int(mqq)], [p, q])
        if b'SUSCTF' in long_to_bytes(solution):
            print(long_to_bytes(solution))
            end = time.time()
            print("Finished in {} seconds.".format(end - start))
#For RSA, the wrong key generation method can also reveal information. You recover my secret message, and here is the flag:
#SUSCTF{N0n_c0prime_RSA_c1pher_cAn_a1s0_recover_me33age!!!}

InverseProblem

题目名字是反问题，一开始被名字带偏了，还去找了矩阵反问题，找到了病态矩阵求解的一些知识，用一些相关正规化方法也调不出结果。后来想了想，这题就因为python浮点数的精度是52位，所以方程组很敏感，给它每个数都扩大的话，敏感的那部分误差就相当于error，那就直接用LWE或者CVP去解就行了。
这里就通过Embedded Technique的构造，把CVP转化成SVP

然后规约之后的第一行就是近似解，所以只要解近似解的方程就可以了。

exp如下

import numpy as np
f=open('b.txt','r')
b=[]
for line in f:
    tmp = line[:-5].replace('.','')
    b.append(int(tmp))

def gravity(n,d=0.25):
    A=np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            A[i,j]=d/n*(d**2+((i-j)/n)**2)**(-1.5)
    return A

A = gravity(85)
A = [[int(j*10^18) for j in i] for i in A]

M = []
for i in range(85):
    M.append(A[i] + [0])

M.append(b + [1])
M = Matrix(ZZ, M)
ans = M.LLL()[0]
flag=M.solve_left(ans)
print(bytes(flag[:-1]))

Ez_Pager_Tiper

这道题是一个lfsr的题目，当时比赛的时候没注意到给了data这个文件夹，当时想了好久怎么通过最后的结果逆回去，然后就做不出来了。赛后看师傅们的wp才发现有这么个文件夹，里面的文件名base64过了，而且每个文件开头都是类似的格式。因此我们只需要通过解加密文件名，获得文件开头的明文，格式为 Date: yyyy-mm-dd。

再对magic_box里的函数进行审计，其中第一部分是常见的LFSR，第二部分中confusion 经过测试可以知道，当mask中有奇数个1，输出LFSR2；当mask中有偶数个1，输出LFSR1^LFSR2 。

>>> def malicious_magic(magic):
    now = (-magic & magic)
    magic ^= now
    return int(now), int(magic)

>>> def confusion(magicy,c1, c2):
    magic = magicy
    output, cnt = magic, 0
    output ^= c1 ^ c2
    while magic:
        now, magic = malicious_magic(magic)
        cnt ^= now >> (now.bit_length() - 1)
        output ^= now
    output ^= cnt * c1
    return int(output)

>>> print(confusion(0b1001,3,4))
7
>>> print(confusion(0b10001,3,4))
7
>>> print(confusion(0b1000,3,4))
4
>>> print(confusion(0b10000,3,4))
4
>>> print(confusion(0b100010,3,4))
7
>>> print(confusion(0b100000010,3,4))
7
>>> print(confusion(0b100000010,3,4))
7
>>> print(confusion(0b1000110,3,4))
4
>>> print(confusion(0b101110,3,4))
7

所以对于problem1，可以知道他只使用了lfsr2。我们就可以用已知的明密文对进行异或，得到输出。然后用矩阵求出对应mask。

from Crypto.Util.number import *
from Crypto.Util.strxor import *

n1, n2 = 64, 12
plain1 = b'Date: 1984-04-01'
ciper1 = open('MTk4NC0wNC0wMQ==_6d30.enc', 'rb').read()
output1 = strxor(plain1, ciper1[:len(plain1)])
output1 = bytes_to_long(output1)
s = [int(x) for x in bin(output1)[2:]]

M = matrix(GF(2), 12, 12)
T = vector(GF(2), 12)
for i in range(12):
        M[i] = s[i : i + 12]
        T[i] = s[i+12]
mask = M.inverse() * T
print(mask[::-1])
#(1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1)
#mask2 =0b101000000001

有了mask2，我们就可以对problem2进行求解。通过运算可以知道这里的magic有偶数个1，所以输出是LFSR1^LFSR2。考虑对LFSR2的12bit的seed3爆破，然后通过已知LFSR2的输出以及开头明文，得到LFSR1的输出，之后求出mask1和seed1，就可以顺利求解。

from Crypto.Util.number import *
from Crypto.Util.strxor import *
class lfsr():
    def __init__(self, seed, mask, length):
        self.length_mask = 2 ** length - 1
        self.mask = mask & self.length_mask
        self.state = seed & self.length_mask

    def next(self):
        next_state = (self.state << 1) & self.length_mask
        i = self.state & self.mask & self.length_mask
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        next_state ^= output
        self.state = next_state
        return output

    def getrandbit(self, nbit):
        output = 0
        for _ in range(nbit):
            output = (output << 1) ^ self.next()
        return output
    
    def recover(self, output):
        lastbit = output & 1
        output >>= 1
        i = (output & self.mask) & self.length_mask
        while i != 0:
            lastbit ^= (i & 1)
            i >>= 1
        seed = (lastbit << (self.length_mask.bit_length()-1)) | output
        return seed
mask2=0b101000000001
plain2 = b'Date: 1984-12-25'
n1, n2 = 64, 12
x = (1<<12)-1

cipher2 = open('MTk4NC0xMi0yNQ==_76ff.enc', 'rb').read()
unknown_c = cipher2[16:]
output2 = strxor(plain2, cipher2[:16])
for seed3 in range(x):
    lfsr2 = lfsr(seed3, mask2, n2)
    outlfsr2 = long_to_bytes(lfsr2.getrandbit(128)).rjust(16,b"\x00")
    outlfsr1 = strxor(output2,outlfsr2)
    m = bin(bytes_to_long(outlfsr1))[2:].zfill(128)
    A = matrix(GF(2),n1,n1)    
    B = vector(GF(2), 64)
    for i in range(n1):
        A[i]=m[i:i+n1]
        B[i]=m[i+n1]
        if det(A)!=0 and det(B)!=0:
            mask1=int("".join([str(int(o)) for o in (A.inverse()*B)][::-1]),2)
            lfsr1=lfsr(int(m,2),mask1,n1)
            l2=lfsr2.getrandbit(((len(cipher2)-16)*8)).rjust((len(cipher2)-16),b"\x00")
            l1=lfsr1.getrandbit(((len(cipher2)-16)*8)).rjust((len(cipher2)-16),b"\x00")
            message = strxor(unknown_c,strxor(l1,l2))
            if b'SUSCTF' in message:
                print(message)