线性同余生成器 / 线性同余方法（LCG）

概念

线性同余方法（LCG）是个产生伪随机数的方法
LCG的性能和随机性取决于选取的参数。如果选择恰当的参数，LCG可以生成长周期和均匀分布的伪随机数序列。然而，不恰当的参数选择可能导致序列的周期较短或者存在可预测的模式，从而影响其随机性和安全性

LCG的周期最大为 M，但大部分情况都会少于 M。要令LCG达到最大周期，应符合以下条件：
1.B,M 互质；
2.M 的所有质因数都能整除 A-1
3.若 M 是4的倍数，A-1 也是
4.A,B,N0 都比 M 小
5.A,B 是正整数

from functools import reduce
from math import gcd
from Crypto.Util.number import *

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0]*multiplier) % modulus
    return modulus, multiplier, increment

def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)

def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)

# N[i+1] = (A*N[i]+B) % M
# A,B,N均未知
sequence = []
modulus, multiplier, increment = crack_unknown_modulus(sequence)
print('A = '+str(multiplier))
print('B = '+str(increment))
print('N = '+str(modulus))

公式及推论

公式

推论

经典题目分析

lcg_1

题目

from Crypto.Util.number import *
flag = b'Spirit{***********************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = 33477128523140105764301644224721378964069
print("seed = ",seed)
for i in range(10):
    seed = (a*seed+b)%n
ciphertext = seed^plaintext
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("c = ",ciphertext)
# seed =  33477128523140105764301644224721378964069
# a =  216636540518719887613942270143367229109002078444183475587474655399326769391
# b =  186914533399403414430047931765983818420963789311681346652500920904075344361
# n =  155908129777160236018105193822448288416284495517789603884888599242193844951
# c =  209481865531297761516458182436122824479565806914713408748457524641378381493

题解

seed,a,b,n，lcg所有参数都已知，ciphertext = seed^plaintext—→plaintext = seed^ciphertext

wp

from Crypto.Util.number import *
seed =  33477128523140105764301644224721378964069
a =  216636540518719887613942270143367229109002078444183475587474655399326769391
b =  186914533399403414430047931765983818420963789311681346652500920904075344361
n =  155908129777160236018105193822448288416284495517789603884888599242193844951
c =  209481865531297761516458182436122824479565806914713408748457524641378381493

print("seed = ",seed)
for i in range(10):
    seed = (a*seed+b)%n
flag = seed^c
print(long_to_bytes(flag))
#b'Spirit{0ops!___you_know__LCG!!}'

lcg_2

题目

from Crypto.Util.number import *
flag = b'Spirit{*****************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext

for i in range(10):
    seed = (a*seed+b)%n
ciphertext = seed

print("a = ",a)
print("b = ",b)
print("n = ",n)
print("c = ",ciphertext)

# a =  59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969
# b =  32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137
# n =  43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467
# c =  8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276

题解

flag就是seed,已知a,b,n,c求seed，即推论1

wp

from Crypto.Util.number import *
a =  59398519837969938359106832224056187683937568250770488082448642852427682484407513407602969
b =  32787000674666987602016858366912565306237308217749461581158833948068732710645816477126137
n =  43520375935212094874930431059580037292338304730539718469760580887565958566208139467751467
c =  8594514452808046357337682911504074858048299513743867887936794439125949418153561841842276
seed=c
for i in range(10):
    seed=(inverse(a,n)*(seed-b))%n
flag=seed
print(long_to_bytes(flag))
#b'Spirit{Orzzz__number_the0ry_master!!}'

lcg_3

题目

from Crypto.Util.number import *
flag = b'Spirit{*********************}'
plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
seed = getPrime(length)
n = getPrime(length)

b = plaintext

output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)
ciphertext = seed

print("a = ",a)
print("n = ",n)
print("output1 = ",output[6])
print("output2 = ",output[7])

# a =  3227817955364471534349157142678648291258297398767210469734127072571531
# n =  2731559135349690299261470294200742325021575620377673492747570362484359
# output1 =  56589787378668192618096432693925935599152815634076528548991768641673
# output2 =  2551791066380515596393984193995180671839531603273409907026871637002460

题解

知道两个连续的随机数，已知a,n，推论3

b→flag

wp

from Crypto.Util.number import *
a =  3227817955364471534349157142678648291258297398767210469734127072571531
n =  2731559135349690299261470294200742325021575620377673492747570362484359
output1 =  56589787378668192618096432693925935599152815634076528548991768641673
output2 =  2551791066380515596393984193995180671839531603273409907026871637002460

b=(output2-a*output1)%n
print(long_to_bytes(b))
#b'Spirit{Y0u_@r3_g00d_at__math}'

lcg_4

题目

from Crypto.Util.number import *
flag = b'Spirit{********************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)

print("n = ",n)
print("output = ",output)
# n =  714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819
# output =  [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]

题解

flag→seed

wp

from Crypto.Util.number import *
n =  714326667532888136341930300469812503108568533171958701229258381897431946521867367344505142446819
output =  [683884150135567569054700309393082274015273418755015984639210872641629102776137288905334345358223, 285126221039239401347664578761309935673889193236512702131697050766454881029340147180552409870425, 276893085775448203669487661735680485319995668779836512706851431217470824660349740546793492847822, 670041467944152108349892479463033808393249475608933110640580388877206700116661070302382578388629, 122640993538161410588195475312610802051543155060328971488277224112081166784263153107636108815824, 695403107966797625391061914491496301998976621394944936827202540832952594905520247784142392337171, 108297989103402878258100342544600235524390749601427490182149765480916965811652000881230504838949, 3348901603647903020607356217291999644800579775392251732059562193080862524671584235203807354488, 632094372828241320671255647451901056399237760301503199444470380543753167478243100611604222284853, 54758061879225024125896909645034267106973514243188358677311238070832154883782028437203621709276]
#求a
x0=output[0]
x1=output[1]
x2=output[2]
a=((x2-x1)*inverse((x1-x0),n))%n
print("a=",a)
#求b
b=(x1-a*x0)%n
print("b=",b)

seed=output[-1]
for i in range(10):
    seed = (inverse(a,n)*(seed-b))%n
print(long_to_bytes(seed))
# a= 65863586327872307178215811859890622391386702699190067821678721759311822315235571722857932007760
# b= 580530341837176922585879619790971707330065277035664726870365931385222825590112557483074386629351
# b'Spirit{Gr3at__J0b!_You_can_be___better!}'

lcg_5

题目

from Crypto.Util.number import *
flag = b'Spirit{****************************************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext
output = []
for i in range(10):
    seed = (a*seed+b)%n
    output.append(seed)

print("output = ",output)
# output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]

题解

和上一题一样，但是n不知道，多了一步求n (推论4求m (已知多组x))

wp

from Crypto.Util.number import *
import gmpy2
output =  [9997297986272510947766344959498975323136012075787120721424325775003840341552673589487134830298427997676238039214108, 4943092972488023184271739094993470430272327679424224016751930100362045115374960494124801675393555642497051610643836, 6774612894247319645272578624765063875876643849415903973872536662648051668240882405640569448229188596797636795502471, 9334780454901460926052785252362305555845335155501888087843525321238695716687151256717815518958670595053951084051571, 2615136943375677027346821049033296095071476608523371102901038444464314877549948107134114941301290458464611872942706, 11755491858586722647182265446253701221615594136571038555321378377363341368427070357031882725576677912630050307145062, 7752070270905673490804344757589080653234375679657568428025599872155387643476306575613147681330227562712490805492345, 8402957532602451691327737154745340793606649602871190615837661809359377788072256203797817090151599031273142680590748, 2802440081918604590502596146113670094262600952020687184659605307695151120589816943051322503094363578916773414004662, 5627226318035765837286789021891141596394835871645925685252241680021740265826179768429792645576780380635014113687982]
def find_gcd(numbers):   #求c中各元素的最大公约数
    result = numbers[0]
    for num in numbers[1:]:
        result = gcd(result, num)
    return result

#求n
t = []
for i in range(9):
    t.append(output[i]-output[i-1])
all_n = []
for i in range(7):
    tt=gcd((t[i+1]*t[i-1]-t[i]*t[i]), (t[i+2]*t[i]-t[i+1]*t[i+1]))
    if tt>2**5:
        all_n.append(tt)
n=find_gcd(all_n)
#求a
x0=output[0]
x1=output[1]
x2=output[2]
a=((x2-x1)*inverse((x1-x0),n))%n

#求b
b=(x1-a*x0)%n
seed = (inverse(a,n) * (x0 - b)) % n
print(long_to_bytes(seed))
#b'Spirit{final__lcg__is__co0m1ing__are_you_ready?}'

lcg_6

题目

from Crypto.Util.number import *
flag = b'Spirit{*****************}'

plaintext = bytes_to_long(flag)
length = plaintext.bit_length()

a = getPrime(length)
b = getPrime(length)
n = getPrime(length)

seed = plaintext

output = []
for i in range(10):
    seed = (seed*a+b)%n
    output.append(seed>>64)
print("a = ",a)
print("b = ",b)
print("n = ",n)
print("output = ",output)
# a =  731111971045863129770849213414583830513204814328949766909151
# b =  456671883153709362919394459405008275757410555181682705944711
# n =  666147691257100304060287710111266554526660232037647662561651
# output =  [16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]

题解

hnp问题，构造格，恢复低位，高位已知，即可求出所有随机数

wp

from Crypto.Util.number import long_to_bytes

a =  731111971045863129770849213414583830513204814328949766909151
b =  456671883153709362919394459405008275757410555181682705944711
n =  666147691257100304060287710111266554526660232037647662561651
output =  [16985619148410545083429542035273917746612, 32633736473029292963326093326932585135645, 20531875000321097472853248514822638673918, 37524613187648387324374487657224279011, 21531154020699900519763323600774720747179, 1785016578450326289280053428455439687732, 15859114177482712954359285501450873939895, 10077571899928395052806024133320973530689, 30199391683019296398254401666338410561714, 21303634014034358798100587236618579995634]
#print(int((output[0]<<64)+2**64).bit_length())
#198
#print(n.bit_length())
#199

h=[0]
for i in range(len(output)):
    h.append(output[i] <<64)

#A0=a*1
#B0=a*0+a*hi-h{i+1}
A = [1]
B = [0]
#i从1开始遍历，所以h要全部向后移一位
for i in range(1, len(h)-1):
    A.append(a*A[i-1] % n)
    B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % n)
A = A[1:]
B = B[1:]
tt=10-1
K=2**64

M = list(matrix(ZZ,tt+2,tt+2))
for i in range(tt):
    M[i][i] = n
    M[-2][i] = A[i]
    M[-1][i] = B[i]
M[-1][-1] = K
M[-2][-2] = 1

M = matrix(ZZ,M)
res = M.LLL()
l0=res[0][-2]
#l0=
s0=l0+h[1]
#s0 = a*seed+b %m
seed = ((s0 - b)*inverse_mod(a,n))%n
print(seed)
print(long_to_bytes(seed))

#523755775854899556903370057799657730884325522670594452582781
b'Spirit{King__of__LCG_qWq}'

二元LCG

题目

from secret import flag

assert flag[:5] == b'cazy{'
assert flag[-1:] == b'}'
flag = flag[5:-1]
assert (len(flag) == 24)

class my_LCG:
    def __init__(self, seed1, seed2):
        self.state = [seed1, seed2]
        self.n = getPrime(64)
        while 1:
            self.a = bytes_to_long(flag[:8])
            self.b = bytes_to_long(flag[8:16])
            self.c = bytes_to_long(flag[16:])
            if self.a < self.n and self.b < self.n and self.c < self.n:
                break

    def next(self):
        new = (self.a * self.state[-1] + self.b * self.state[-2] + self.c) % self.n
        self.state.append(new)
        return new

def main():
    lcg = my_LCG(getRandomInteger(64), getRandomInteger(64))
    print("data = " + str([lcg.next() for _ in range(5)]))
    print("n = " + str(lcg.n))

if __name__ == "__main__":
    main()

# data = [2626199569775466793, 8922951687182166500, 454458498974504742, 7289424376539417914, 8673638837300855396]
# n = 10104483468358610819

题解

wp

t=[0]
for i in range(1,5):
    t.append(data[i] - data[i-1])

a=((t[3]*t[2]-t[4]*t[1])*inverse((t[2]*t[2]-t[3]*t[1]),n))%n
print("a=",a)

b=((t[3]-a*t[2])*inverse(t[1],n))%n
print("b=",b)

c=(data[2]-data[1]*a-b*data[0])%n
print("c=",c)

print(b'cazy{' + long_to_bytes(a) + long_to_bytes(b) + long_to_bytes(c) + b'}')
# a= 5490290802446982981
# b= 8175498372211240502
# c= 6859390560180138873
# b'cazy{L1near_Equ4t1on6_1s_34sy}'

三元LCG

LCG Revenge

xs = xs[1:] + [new_state]

这一步相当于一个队列，将flag的第一部分丢掉，在队尾插入新的new_state。

求seed需要在前面插入

xs = [xs0] + xs[:2]

wp

from Crypto.Util.number import *
a = 18038175596386287827
b = 15503291946093443851
c = 17270168560153510007
p = 307956849617421078439840909609638388517
xs=[255290883651191064919890629542861653873, 221128501895959214555166046983862519384, 108104020183858879999084358722168548984]
for _ in range(10):
    xs0 = (xs[2] - (b*xs[0]+c*xs[1])) * inverse(a, p) % p
    xs = [xs0] + xs[:2]

print(xs)
print(long_to_bytes(xs[0])+long_to_bytes(xs[1])+long_to_bytes(xs[2]))

记2024年lcg一些题目

Dragon Knight CTF2024 Crypto_签到

题目

from Crypto.Util.number import *

m = b'flag{********}'
a =  getPrime(247)
b =  getPrime(247)
n =  getPrime(247)

seed = bytes_to_long(m)

class LCG:
    def __init__(self, seed, a, b, m):
        self.seed = seed  
        self.a = a  
        self.b = b  
        self.m = m  

    def generate(self):
        self.seed = (self.a * self.seed + self.b) % self.m
        self.seed = (self.a * self.seed + self.b) % self.m
        return self.seed

seed = bytes_to_long(m)

output = LCG(seed,a,b,n)

for i in range(getPrime(16)):
    output.generate()

print(output.generate())
print(output.generate())
print(output.generate())
print(output.generate())
print(output.generate())

题解

连用了两次x2 = a*x1+b mod n

x2=a (ax1+b)+b mod n =a *2 x1+a *b +b mod n

=A*x1+B

Gröbner基解同余方程，方程越多，结果越正确

from Crypto.Util.number import inverse, long_to_bytes

output = [5944442525761903973219225838876172353829065175803203250803344015146870499,
141002272698398325287408425994092371191022957387708398440724215884974524650,
42216026849704835847606250691811468183437263898865832489347515649912153042,
67696624031762373831757634064133996220332196053248058707361437259689848885,
19724224939085795542564952999993739673429585489399516522926780014664745253]
R.<a,b> = PolynomialRing(ZZ)

f1 = output[0]*a + b - output[1]
f2 = output[1]*a + b - output[2]
f3 = output[2]*a + b - output[3]
f4 = output[3]*a + b - output[4]
F = [f1,f2,f3,f4]
# 使用F构建一个理想的Ideal。
ideal = Ideal(F)
# 计算Ideal的Gröbner基I
I = ideal.groebner_basis()
a = ZZ(-I[0].univariate_polynomial()(0))
b = ZZ(-I[1].univariate_polynomial()(0))
n = ZZ(I[2])

a=a%n
b=b%n
a_= inverse(a,n)
seed=output[0]
for _ in range(2 ** 16):
    seed = a_ * (seed - b) % n
    flag = long_to_bytes(int(seed))
    if b'flag' in flag:
        print(flag)

# b'flag{Hello_CTF}'

Moectf 2024 week4 easy_LCG

题目

from sage.all import *
from random import getrandbits, randint
from secrets import randbelow
from Crypto.Util.number import getPrime,isPrime,inverse
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
from secret import priKey, flag
from hashlib import sha1
import os


q = getPrime(160)
while True:
    t0 = q*getrandbits(864)
    if isPrime(t0+1):
        p = t0 + 1
        break


x = priKey
assert p % q == 1
h = randint(1,p-1)
g = pow(h,(p-1)//q,p)
y = pow(g,x,p)


def sign(z, k):
    r = pow(g,k,p) % q
    s = (inverse(k,q)*(z+r*priKey)) % q
    return (r,s)


def verify(m,s,r):
    z = int.from_bytes(sha1(m).digest(), 'big')
    u1 = (inverse(s,q)*z) % q
    u2 = (inverse(s,q)*r) % q
    r0 = ((pow(g,u1,p)*pow(y,u2,p)) % p) % q
    return r0 == r


def lcg(a, b, q, x):
    while True:
        x = (a * x + b) % q
        yield x


msg = [os.urandom(16) for i in range(5)]

a, b, x = [randbelow(q) for _ in range(3)]
prng = lcg(a, b, q, x)
sigs = []
for m, k in zip(msg,prng):
    z = int.from_bytes(sha1(m).digest(), "big") % q
    r, s = sign(z, k)
    assert verify(m, s, r)
    sigs.append((r,s))


print(f"{g = }")
print(f"{h = }")
print(f"{q = }")
print(f"{p = }")
print(f"{msg = }")
print(f"{sigs = }")
key = sha1(str(priKey).encode()).digest()[:16]
iv = os.urandom(16)
cipher = AES.new(key, AES.MODE_CBC,iv)
ct = cipher.encrypt(pad(flag,16))
print(f"{iv = }")
print(f"{ct = }")

题解

AES key= priKey =x

Gröbner基解同余方程,已知si,H(mi),ri,q ,不知道k,a,b,x

from hashlib import sha1
from Crypto.Util.number import *
from gmpy2 import *
from Crypto.Cipher import AES

g = 81569684196645348869992756399797937971436996812346070571468655785762437078898141875334855024163673443340626854915520114728947696423441493858938345078236621180324085934092037313264170158390556505922997447268262289413542862021771393535087410035145796654466502374252061871227164352744675750669230756678480403551
h = 13360659280755238232904342818943446234394025788199830559222919690197648501739683227053179022521444870802363019867146013415532648906174842607370958566866152133141600828695657346665923432059572078189013989803088047702130843109809724983853650634669946823993666248096402349533564966478014376877154404963309438891
q = 1303803697251710037027345981217373884089065173721
p = 135386571420682237420633670579115261427110680959831458510661651985522155814624783887385220768310381778722922186771694358185961218902544998325115481951071052630790578356532158887162956411742570802131927372034113509208643043526086803989709252621829703679985669846412125110620244866047891680775125948940542426381
msg = [b'I\xf0\xccy\xd5~\xed\xf8A\xe4\xdf\x91+\xd4_$', b'~\xa0\x9bCB\xef\xc3SY4W\xf9Aa\rO',
       b'\xe6\x96\xf4\xac\n9\xa7\xc4\xef\x82S\xe9 XpJ', b'3,\xbb\xe2-\xcc\xa1o\xe6\x93+\xe8\xea=\x17\xd1',
       b'\x8c\x19PHN\xa8\xbc\xfc\xa20r\xe5\x0bMwJ']
sigs = [(913082810060387697659458045074628688804323008021, 601727298768376770098471394299356176250915124698),
        (406607720394287512952923256499351875907319590223, 946312910102100744958283218486828279657252761118),
        (1053968308548067185640057861411672512429603583019, 1284314986796793233060997182105901455285337520635),
        (878633001726272206179866067197006713383715110096, 1117986485818472813081237963762660460310066865326),
        (144589405182012718667990046652227725217611617110, 1028458755419859011294952635587376476938670485840)]
iv = b'M\xdf\x0e\x7f\xeaj\x17PE\x97\x8e\xee\xaf:\xa0\xc7'
ct = b"\xa8a\xff\xf1[(\x7f\xf9\x93\xeb0J\xc43\x99\xb25:\xf5>\x1c?\xbd\x8a\xcd)i)\xdd\x87l1\xf5L\xc5\xc5'N\x18\x8d\xa5\x9e\x84\xfe\x80\x9dm\xcc"
m=[]
for _ in msg:
    m.append(bytes_to_long(sha1(_).digest()))
print(m)
r = []
s = []
for i in sigs:
    r.append(i[0])
    s.append(i[1])

PR.<k1, k2, k3, k4, k5, a, b, x >= PolynomialRing(Zmod(q))
f1 = a * k1 + b - k2
f2 = a * k2 + b - k3
f3 = a * k3 + b - k4
f4 = a * k4 + b - k5
f5 = m[0] + r[0] * x - s[0] * k1
f6 = m[1] + r[1] * x - s[1] * k2
f7 = m[2] + r[2] * x - s[2] * k3
f8 = m[3] + r[3] * x - s[3] * k4
f9 = m[4] + r[4] * x - s[4] * k5

F = [f1, f2, f3, f4, f5, f6, f7, f8, f9]
ideal= Ideal(F)
I = ideal.groebner_basis()
x = ZZ(-I[-1].univariate_polynomial()(0))
key = sha1(str(x).encode()).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC,iv)
flag = cipher.decrypt(ct)
print(flag)
# b'moectf{w3ak_n0nce_is_h4rmful_to_h3alth}\t\t\t\t\t\t\t\t\t'