NSSCTF Crypto系列--LCG

Crypto系列--LCG

Crypto系列--LCG(一)

[LCG]P1

from gmpy2 import *
from Crypto.Util.number import *

a = 113439939100914101419354202285461590291215238896870692949311811932229780896397
b = 72690056717043801599061138120661051737492950240498432137862769084012701248181
m = 72097313349570386649549374079845053721904511050364850556329251464748004927777
c = 9772191239287471628073298955242262680551177666345371468122081567252276480156
# c2 = ( a * c1 + b )  % m
a_1 = invert(a,m)
for i in range(1000000):
    c = (c - b) * a_1 % m
    flag = long_to_bytes(c)
    if b'NSSCTF{' in flag :
        print(i)
        print(flag)
        break

[LCG]P2

from gmpy2 import *
from Crypto.Util.number import *

a = 83968440254358975953360088805517488739689448515913931281582194839594954862517
m = 77161425490597512806099499399561161959645895427463118872087051902811605680317
c1 = 43959768681328408257423567932475057408934775157371406900460140947365416240650
c2 = 8052043336238864355872102889254781281466728072798160448260752595038552944808
# c2 = ( a * c1 + b )  % m
a_1 = invert(a,m)
b = (c2 - c1 * a ) % m
print(b.bit_length())
print(isPrime(b))
c = c1
for i in range(2**16):
    c = (c - b) * a_1 % m
    flag = long_to_bytes(c)
    if b'NSSCTF{' in flag :
        print(i)
        print(flag)
        break

[LCG]P3

from gmpy2 import *
from Crypto.Util.number import *

m = 96343920769213509183566159649645883498232615147408833719260458991750774595569
c1 = 10252710164251491500439276567353270040858009893278574805365710282130751735178
c2 = 45921408119394697679791444870712342819994277665465694974769614615154688489325
c3 = 27580830484789044454303424960338587428190874764114011948712258959481449527087

a = (c3 - c2) * invert(c2 - c1 , m) % m
b = (c3 - c2 * a) % m
a_1 = invert(a,m)
c = c1
for i in range(2**16):
    c = (c - b) * a_1 % m
    flag = long_to_bytes(c)
    if b'NSSCTF{' in flag :
        print(i)
        print(flag)
        break

[LCG]P4

from gmpy2 import *
from Crypto.Util.number import *

c = [47513456973995038401745402734715062697203139056061145149400619356555247755807,57250853157569177664354712595458385047274531304709190064872568447414717938749,30083421760501477670128918578491346192479634327952674530130693136467154794135,38739029019071698539301566649413274114468266283936163804522278316663267625091,42506270962409723585330663340839465445484970240895653869393419413017237427900]

t = []
for i in range(1,len(c)):
    t.append(c[i] - c[i - 1])

m = 0
for i in range(1,len(t) - 1):
    m = GCD(t[i-1]*t[i+1] - t[i]**2,m)
m = m//2

print(isPrime(m))

a = (c[2] - c[1]) * invert(c[1] - c[0],m)
b = (c[1] - c[0]*a)%m

a_1 = invert(a,m)
c = c[0]
for i in range(2**16):
    c = (c - b) * a_1 % m
    flag = long_to_bytes(c)
    if b'NSSCTF{' in flag :
        print(i)
        print(flag)
        break

[LCG]P5

from gmpy2 import *
from Crypto.Util.number import *
from functools import *

c1 = [
57648351648792284446777383544515312078150027665462203747924668509833442797796,
90378879763416486117626477831653213918315023665514305359005153448529276829825,
21826576702665114807208181233864324586557058567478767825970403161758214940301,
47594460970742467761038407996122637655856234121180714918606854365482948918701,
11871076497267630136796123094001159466754095580273018347962555675375123133730
]

t = []
for i in range(1,len(c1)):
    t.append(c1[i] - c1[i-1])

m = 0
for i in range(1,len(t)-1):
    m = gcd(t[i-1]*t[i+1] - t[i]**2,m)
# 分解一下
m = m//4

a = (c1[2] - c1[1])*invert(c1[1]-c1[0],m)
b = (c1[2] - c1[1]*a)%m
c = c1[0]
a_1 = invert(a,m)
for i in range(2**16):
    c = (c - b) * a_1 % m
    m1 = long_to_bytes(c)
    if b'NSSCTF' in m1:
        print(i)
        print(m1)
        break

[LCG]P6

from Crypto.Util.number import *
from gmpy2 import *

c = [
25445927935559969212648839062255651208014967526951331344342413906051118248013,
81572970970116732975667604095930675262596098540738447440566868976253289440293,
6956793925625110803779114150160476498676179542815207353218944386232051429289,
88042506866508011592456777776490262927213783361334741921985316105965255450508,
5652832125321707726481846809536180176877263519327268361130605456255558285092,
]
# 每次加密两次

t = []
m = 0
for i in range(1,len(c)):
    t.append(c[i] - c[i - 1 ] )

for i in range(1,len(t) - 1):
    m = gcd(t[i-1]*t[i+1] - t[i]**2,m)

a_2 = (c[3] - c[2])*invert(c[2] - c[1],m)
# a = iroot(a_2,2)[0]                  # 开方是true

# c[1] = (a * (c[0] * a + b) + b)%m
# c[1] = (a**2 *c[0] + (a+1)b)%m

a = a_2                                # 两次就是两次不需要开方
a_1 = invert(a,m)                      # 逆元
b = ( c[1] - c[0] * a_2 ) % m          # 把a*b 当成b就行啦
c = c[0]
for i in range(2**16):
    c = (c - b) * a_1 % m
    m1 = long_to_bytes(c)
    if b'NSSCTF' in m1:
        print(i)
        print(m1)
        break