das-2020-8-math stream-solve.py

# author: badmonkey

from Crypto.Util.number import *


x1 = 123702839015756050884261730350882737708358949223717439499184803586403380580917033774031115610745320766887583414238651786366942713037837183155670218651008201659397071753885966029204756119524199815830117337679903000409946531282131341544499373725768763177481236458288527526859422459135345981831473247316555618560
x2 = 53924539754438007029501782029367518619266978487508630921932520518338714507664032847344261722536853774745396939590212348751300654791168048424611586167435934594214127893014772880318410947388412139484910911558913354881832668949036424760411326983813389804113790149675585445672972740198653398937213550096612898644
x3 = 63167700157587157707659591399396856546372104423703909698033441469110658576803656359757694321232303912965997844863919208184964899691086676221424510238937996039639020372184420079106454203010811220417415790732729673830907444478937628707872186593129029778616120328244635824580198884662150104071084993653737914022
x4 = 60900060027375388502954968533962551010895369320035053843073456747137873661715722305461794383581233299465108460448730880547665937249092184288347189085393775979063774890144837289588709330708116910722986763529852613180587935929862087569945164722421961012524239918061319269183814829620043095252880283996001514164
x5 = 67113877662673866233083488077860646719333535770452193680770137339822227232411855308016162556072517267428842392157280102333021460946927124183519015361915428846609475511896652480835848461061078559069446935766782858959584622772958271986367572980550469374057939856055426306880686615182779562168848708759248213327
x6 = 35321475740169398933875140842714262960904281331750205573172983410230385562745162356815900214941351338686778803036306575637404857858578337229023073873912358708980334069653782813016210177757649710822363593438233897497585809695658043901986740902609804765459645039370188002526182350951413827277418881541889614752
cipher = 6257754829567986763892047832635830335816090670173191750751645793632788077917375687942054101544041498378086719313412925093077211368386033569497742486801694329756989184534154729709541023134576678323307630303652989589994288555559228966732861033813909078153507299492167442982631897158564781706799632969673086582


from gmpy2 import *
y1 = x3-x2
y2 = x4-x3
y3 = x5-x4
y4 = x6-x5

z1 = y2 - y1
z2 = y3 - y2
z3 = y4 - y3

A = z1*(x2-x4)
B = z2*(x1-x3)
C = z2*(x3-x5)
D = z3*(x2-x4)

n = gcd(A-B,C-D)
assert is_prime(n)


a = (x4+x2-2*x3)*inverse(x3-x1,n)%n
b = a + 1

c = (x3-a*x1-b*x2)%n

assert x4 == (a*x2+b*x3+c)%n
assert x5 == (a*x3+b*x4+c)%n
assert x6 == (a*x4+b*x5+c)%n

target = 2**1024


def recover(a,c,n,now,pre,limit=301):
    b = a+1
    while limit:
        now,pre = pre,((now-c-b*pre)*inverse(a,n))%n
        limit -= 1
    return int(pre),int(now)
a0,a1 = recover(a,c,n,x2,x1)


# 矩阵乘法
def mul(A,B,n):
    C = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(3):
            for k in range(3):
                C[i][j] = (C[i][j]+A[i][k]*B[k][j])%n
    return C
# 矩阵快速幂
def matrix_pow(A,k):
    I = [
        [1,0,0],
        [0,1,0],
        [0,0,1]
    ]
    while k>0:
        if k&1:
            I = mul(I,A,n)
        A = mul(A,A,n)
        k //=2
    return I
# 原始矩阵，这里笔者将初始的s[0],s[1] 恢复了出来
origin = [
    [a1,a0,1],
    [0,0,0],
    [0,0,0]
]
# 系数矩阵
coff = [
    [b,1,0],
    [a,0,0],
    [c,0,1]
] 
# 目标的系数矩阵 可以通过矩阵快速求解
COFF = matrix_pow(coff,target-1)
# 最终的结果
RES = mul(origin,COFF,n)

stream = int(RES[0][0])%n
flag = cipher^stream
print(long_to_bytes(flag))

das-2020-8-math stream-task.py

from Crypto.Util.number import isPrime, getPrime, bytes_to_long
from random import randint

flag = b'DASCTF{********************************}'

def generate():
    n = getPrime(1024)

    a, c = randint(1, n), randint(1, n)
    b = a + 1
    
    return a, b, c, n

def get_stream(target):
    stream = []
    for i in range(target + 1):
        if i < 2:
            stream.append(randint(1, n))
        else:
            stream.append((a * stream[i - 2] + b * stream[i - 1] + c) % n)
        if i > 300 and i < 307:
            print(stream[i])
    return stream

target = 2 ** 1024
a, b, c, n = generate()
stream = get_stream(target)

plain = bytes_to_long(flag)
cipher = plain ^ stream[target]

print(cipher)