Document for 西湖论🗡🔪⚔🖋✂

Table of Contents

依旧是神仙打架的PY大赛

题的质量也一般，是为了拖时间拉长战线出的题，嘛，大伙有钱赚就行，

这点预算还想要原创？

笑喜了

西湖论剑2021Crypto #

密码人集合 #

数独题,属实绷不住了,记一下已经有人出国这种题了以后不能出了🎄🎄🎄

hardrsa #

src

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

p = getPrime(512)
q = getPrime(512)
n = p**4*q

e = 65537
phi = gmpy2.lcm(p - 1, q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print ("dp = " + str(dp))
print ("c = " + str(c))

y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839

g = 2
x = 2019*p**2 + 2020*p**3 + 2021*p**4
c1 = pow(g, x, y)
print( "c1 = " + str(c1))


# dp = 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473

# c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425

# c1 = 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059

喜闻乐见的数学题+离散对数形式

推下公式用sage一把梭哈

from Crypto.Util.number import *
import sympy

dp= 379476973158146550831004952747643994439940435656483772269013081580532539640189020020958796514224150837680366977747272291881285391919167077726836326564473
c = 57248258945927387673579467348106118747034381190703777861409527336272914559699490353325906672956273559867941402281438670652710909532261303394045079629146156340801932254839021574139943933451924062888426726353230757284582863993227592703323133265180414382062132580526658205716218046366247653881764658891315592607194355733209493239611216193118424602510964102026998674323685134796018596817393268106583737153516632969041693280725297929277751136040546830230533898514659714717213371619853137272515967067008805521051613107141555788516894223654851277785393355178114230929014037436770678131148140398384394716456450269539065009396311996040422853740049508500540281488171285233445744799680022307180452210793913614131646875949698079917313572873073033804639877699884489290120302696697425
c1= 78100131461872285613426244322737502147219485108799130975202429638042859488136933783498210914335741940761656137516033926418975363734194661031678516857040723532055448695928820624094400481464950181126638456234669814982411270985650209245687765595483738876975572521276963149542659187680075917322308512163904423297381635532771690434016589132876171283596320435623376283425228536157726781524870348614983116408815088257609788517986810622505961538812889953185684256469540369809863103948326444090715161351198229163190130903661874631020304481842715086104243998808382859633753938512915886223513449238733721777977175430329717970940440862059204518224126792822912141479260791232312544748301412636222498841676742208390622353022668320809201312724936862167350709823581870722831329406359010293121019764160016316259432749291142448874259446854582307626758650151607770478334719317941727680935243820313144829826081955539778570565232935463201135110049861204432285060029237229518297291679114165265808862862827211193711159152992427133176177796045981572758903474465179346029811563765283254777813433339892058322013228964103304946743888213068397672540863260883314665492088793554775674610994639537263588276076992907735153702002001005383321442974097626786699895993544581572457476437853778794888945238622869401634353220344790419326516836146140706852577748364903349138246106379954647002557091131475669295997196484548199507335421499556985949139162639560622973283109342746186994609598854386966520638338999059
y = 449703347709287328982446812318870158230369688625894307953604074502413258045265502496365998383562119915565080518077360839705004058211784369656486678307007348691991136610142919372779782779111507129101110674559235388392082113417306002050124215904803026894400155194275424834577942500150410440057660679460918645357376095613079720172148302097893734034788458122333816759162605888879531594217661921547293164281934920669935417080156833072528358511807757748554348615957977663784762124746554638152693469580761002437793837094101338408017407251986116589240523625340964025531357446706263871843489143068620501020284421781243879675292060268876353250854369189182926055204229002568224846436918153245720514450234433170717311083868591477186061896282790880850797471658321324127334704438430354844770131980049668516350774939625369909869906362174015628078258039638111064842324979997867746404806457329528690722757322373158670827203350590809390932986616805533168714686834174965211242863201076482127152571774960580915318022303418111346406295217571564155573765371519749325922145875128395909112254242027512400564855444101325427710643212690768272048881411988830011985059218048684311349415764441760364762942692722834850287985399559042457470942580456516395188637916303814055777357738894264037988945951468416861647204658893837753361851667573185920779272635885127149348845064478121843462789367112698673780005436144393573832498203659056909233757206537514290993810628872250841862059672570704733990716282248839
g = 2
x = sympy.discrete_log(y, c1, g)
p = sympy.symbols("p")
a = sympy.solve([2019*p**2 + 2020*p**3 + 2021*p**4-x], [p])
#print(a)
p = 12131601165788024635030034921084070470053842112984866821070395281728468805072716002494427632757418621194662541766157553264889658892783635499016425528807741
m = pow(c, dp, p)
print(long_to_bytes(m))

unknown_dsa #

听说要用什么勾八佩尔方程做

咱们大专人下人也不懂那些

直接连分数一把梭哈👨‍🎓👨‍🎓👨‍🎓

连分数打重要参数

#! /usr/bin/sage
from gmpy2 import iroot
from icecream import *
from sage.all import *
from sage.groups.generic import bsgs
from Crypto.Util.number import *

w = [3912956711, 4013184893, 3260747771]
c1 = [2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704, 21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961, 301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424]
c2 = [148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144, 1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256, 10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]

def finduv(w):
    # w = 3912956711
    sqrt_w = sqrt(w).n(2000)
    print(sqrt_w)
    for uv in continued_fraction(sqrt_w).convergents():
        u = uv.numerator()
        v = uv.denominator()
        # input()
        # ic(u,v)
        if(u**2 - w*v**2<20 and u**2 - w*v**2>0):
            ic(u,v)
            ic(u**2 - w*v**2)
            return u,v
uu=[]
vv =[]

for wi in w:
    u,v = finduv(wi)
    uu.append(u)
    vv.append(v)
print(len(uu),len(vv))
print(uu)
print(vv)

'''
uu = [3246103877570376338979874480058302388590234989573846048429589091918737949572620392050082083210013471538484670450175602957972442230909, 121723653124334943327337351369224143389428692536182586690052931548156177466437320964701609590004825981378294358781446032392886186351422728173975231719924841105480990927174913175897972732532233, 1440176324831562539183617425199117363244429114385437232965257039323873256269894716229817484088631407074328498896710966713912857642565350306252498754145253802734893404773499918668829576304890397994277568525506501428687843547083479356423917301477033624346211335450]
vv = [51893133018606205089677829160555654307824024355546397002081760065608182810917693193575928567213487534685441075575788061525676783, 1921455776649552079281304558665818887261070948261008212148121820969448652705855804423423681848341600084863078530401518931263150887409200101780191600802601105030806253998955929263882382004, 25220695816897075916217095856631009012504127590059436393692101250418226097323331193222730091563032067314889286051745468263446649323295355350101318199942950223572194027189199046045156046295274639977052585768365501640340023356756783359924935106074017605019787]
w = [3912956711, 4013184893, 3260747771]
cu = [2852589223779928796266540600421678790889067284911682578924216186052590393595645322161563386615512475256726384365091711034449682791268994623758937752874750918200961888997082477100811025721898720783666868623498246219677221106227660895519058631965055790709130207760704, 21115849906180139656310664607458425637670520081983248258984166026222898753505008904136688820075720411004158264138659762101873588583686473388951744733936769732617279649797085152057880233721961, 301899179092185964785847705166950181255677272294377823045011205035318463496682788289651177635341894308537787449148199583490117059526971759804426977947952721266880757177055335088777693134693713345640206540670123872210178680306100865355059146219281124303460105424]
cv = [148052450029409767056623510365366602228778431569288407577131980435074529632715014971133452626021226944632282479312378667353792117133452069972334169386837227285924011187035671874758901028719505163887789382835770664218045743465222788859258272826217869877607314144, 1643631850318055151946938381389671039738824953272816402371095118047179758846703070931850238668262625444826564833452294807110544441537830199752050040697440948146092723713661125309994275256, 10949587016016795940445976198460149258144635366996455598605244743540728764635947061037779912661207322820180541114179612916018317600403816027703391110922112311910900034442340387304006761589708943814396303183085858356961537279163175384848010568152485779372842]

ans1 = int(crt(cv,vv))
print(iroot(ans1,int(7)))
m2 = 10336852405630488944198347577475266693234960398137850045398990629116544863921454
uu2 = [iroot(int(1+w[i]*vv[i]**2),int(2)) for i in range(3)]
print(uu2)
print(uu)


'''

喜闻乐见打DSA


# from sage.all import *
# from sage.groups.generic import bsgs
from Crypto.Util.number import *
from Crypto.PublicKey import DSA
from Crypto.Hash import SHA
from gmpy2 import invert,powmod,iroot
import random
from Crypto.Util.number import *

m1=b'Hello, this is the first message.'

m2=b'YES!! that is the second message.'
n, t, invg, = 85198615386075607567070020969981777827671873654631200472078241980737834438897900146248840279191139156416537108399682874370629888207334506237040017838313558911275073904148451540255705818477581182866269413018263079858680221647341680762989080418039972704759003343616652475438155806858735982352930771244880990190318526933267455248913782297991685041187565140859, 106239950213206316301683907545763916336055243955706210944736472425965200103461421781804731678430116333702099777855279469137219165293725500887590280355973107580745212368937514070059991848948031718253804694621821734957604838125210951711527151265000736896607029198, 60132176395922896902518845244051065417143507550519860211077965501783315971109433544482411208238485135554065241864956361676878220342500208011089383751225437417049893725546176799417188875972677293680033005399883113531193705353404892141811493415079755456185858889801456386910892239869732805273879281094613329645326287205736614546311143635580051444446576104548
r1, s1, s2 = 498841194617327650445431051685964174399227739376, 376599166921876118994132185660203151983500670896, 187705159843973102963593151204361139335048329243
r2, s3  = 620827881415493136309071302986914844220776856282, 674735360250004315267988424435741132047607535029
h1 = bytes_to_long(SHA.new(m1).digest())
h2 = bytes_to_long(SHA.new(m2).digest())

# 解方程
'''
a=1
b=-1
c=-n*t
delta = b**2-4*a*c
print(delta)
print(iroot(delta,2))
p = (-b+iroot(delta,2)[0])//(2*a)

'''


q = 895513916279543445314258868563331268261201605181
p = 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839

k = (h1-h2)*inverse(s1-s2,q)
x1 = ((s1*k-h1)*inverse(r1,q))%q
print(x1)
flag=b''
flag+=long_to_bytes(x1)
# b'DASCTF{f11bad18f5297'
x1 = 389668174084597613214310991510959871854822701367
g = inverse(invg,n)
r2 = powmod(g, x1, p) % q
x2 = ((s3*k-h1)*inverse(r2,q))%q
print(x2)
flag+=long_to_bytes(x2)
print(flag)

q = 895513916279543445314258868563331268261201605181
p = 95139353880772104939870618145448234251031105153406565833029787299040378395002190438381537974853777890692924407167823818980082672873538133127131356810153012924025270883966172420658777903337576027105954119811495411149092960422055445121097259802686960288258399754185484307350305454788837702363971523085335074839
# DASCTF{f11bad18f529750fe52c56eed85d001b}

SpecialCurve2 #

这个还有点意思，感觉是某研究生👴拿来搞心态的

好难好难好难

把底层大专鼠鼠难住了捏

src

from Crypto.Util.number import *
# from flag import flag
import random

def add(P1,P2):
    x1,y1=P1
    x2,y2=P2
    x3=(x1*x2-y1*y2)%n
    y3=(x1*y2+x2*y1)%n
    return (x3,y3)

def mul(P,k):
    assert k>=0
    Q=(1,0)
    while k>0:
        if k%2:
            k-=1
            Q=add(P,Q)
        else:
            k//=2
            P=add(P,P)
    return Q

def getMyPrime():
    while True:
        q=getPrime(88)
        p=2*q+1
        if isPrime(p):
            return p

e=getPrime(256)
n=getMyPrime()*getMyPrime()*getMyPrime()
print('n=%d'%n)

G=(1,1)
# HINT=mul(G,e)
g=G
Q=(1,0)
for i in range(10):
   g=add(g,Q) 
   print(i,g)
print(add(G,G))
print(mul(G,3))
print(mul(G,8))


# print('HINT=%s'%str(HINT))

# x=bytes_to_long(flag[7:39])
# y=bytes_to_long(flag[39:-1])
# M=(x,y)
# C=mul(M,e)
# print('C=%s'%str(C))
'''
n=92916331959725072239888159454032910975918656644816711315436128106147081837990823
HINT=(1225348982571480649501200428324593233958863708041772597837722864848672736148168, 1225348982571480649501200428324593233958863708041772597837722864848672736148168)
C=(44449540438169324776115009805536158060439126505148790545560105884100348391877176, 73284708680726118305136396988078557189299357177640330968917927635171441710392723)
'''

学习复旦大哥博客得知这玩意是

复数域上的离散对数问题+复数RSA：

$(X_1+iY_1)(X_2+iY_2)=X_1X_2 + i^2(Y_1Y_2) + i(X_1Y_2+X_2Y_1)$

$=X_1X_2 -(Y_1Y_2) + i(X_1Y_2+X_2Y_1)$

所以，X存放的是实部，Y存放虚部。。。

简写下来就是这样

$Z^e=(X+iY)^e\pmod{n}$

这里e没给，想要先求离散对数拿e

这里的算法是将实数和复数提出来构建到坐标轴上计算

这样一来所有计算就都在实数上了

$cip=\sqrt{x^2+y^2}$

$cip^2=x^2+y^2$

$G=(1,1),OG=1+1=2$

$x^2+y^2=(1+1)^e=OC = OG^e\pmod{N}$

# SageMath script
mod = 92916331959725072239888159454032910975918656644816711315436128106147081837990823
cipher = 1225348982571480649501200428324593233958863708041772597837722864848672736148168^2*2%mod
base = 2
e = pari(f"znlog({cipher},Mod({base},{mod}))")
print(e)

exp

from Crypto.Util.number import long_to_bytes
import gmpy2


def add(P1,P2):
    x1,y1=P1
    x2,y2=P2
    x3=(x1*x2-y1*y2)%n
    y3=(x1*y2+x2*y1)%n
    return (x3,y3)

def mul(P,k):
    assert k>=0
    Q=(1,0)
    while k>0:
        if k%2:
            k-=1
            Q=add(P,Q)
        else:
            k//=2
            P=add(P,P)
    return Q
n=92916331959725072239888159454032910975918656644816711315436128106147081837990823
HINT=(1225348982571480649501200428324593233958863708041772597837722864848672736148168, 1225348982571480649501200428324593233958863708041772597837722864848672736148168)
C=(44449540438169324776115009805536158060439126505148790545560105884100348391877176, 73284708680726118305136396988078557189299357177640330968917927635171441710392723)


from Crypto.Util.number import long_to_bytes
import gmpy2

e = 96564183954285580248216944343172776827819893296479821021220123492652817873253
# sage: factor(92916331959725072239888159454032910975918656644816
# ....: 711315436128106147081837990823)
# 425886199617876462796191899 * 434321947632744071481092243 * 502327221194518528553936039

p = [425886199617876462796191899, 434321947632744071481092243, 502327221194518528553936039] 

phi = (p[0]**2-1)*(p[1]**2-1)*(p[2]**2-1) 
d = gmpy2.invert(e, phi) 

M = mul(C,d) 
print(mul(M,e)==C)
# assert mul(G,e)==HINT

print(long_to_bytes(M[0])+long_to_bytes(M[1]))
# True
# b'47f4f203afe894ddbb1bcf6368d901cf93990354dadbc5b7794e199d4f0b59cb'

FilterRandom #

加了层的套娃lfsr

src

import random
from secret import init1,init2,flag


class lfsr():
    def __init__(self, state, mask, length):
        self.state = state
        self.mask = mask
        self.lengthmask = 2**length-1

    def next(self):
        nextdata = (self.state << 1) & self.lengthmask 
        tmp = self.state & self.mask & self.lengthmask 
        output = 0
        while tmp != 0:
            output ^= (tmp & 1)
            tmp = tmp >> 1
        nextdata ^= output
        self.state = nextdata
        return output

def my_filter(c1,c2):
    if random.random()>0.1:
        return str(c1)
    else:
        return str(c2)

N=64
mask1=random.getrandbits(N)
mask2=random.getrandbits(N)
print(mask1)
print(mask2)
l1=lfsr(init1,mask1,N)
l2=lfsr(init2,mask2,N)
output=''
for i in range(2048):
    output+=my_filter(l1.next(),l2.next())
print(output)
'''
17638491756192425134
14623996511862197922
10001011010100011000100101001011100010110111001100001110000111011011100101101101000111101100010111100011000011111111010101111100101010101100010100000111011010011110111000100000101100101010110100111100011000101010101011011111011011000001101001011000010000011110001111001111011100110011111111101000111101001010000110001110111101001001101011101101001010001101010010110000000000001001101100101011110011010110011010110110011001001111001010100011110111100100010110111100110010000000010010011110001100000011000001110001000000010000100100101100000011100000011110101001011010011010100001101000010100100000011001011001000110000000000111011101000110010110111110010101110010001010001111111000011010000011001110111001000010011000000111010111100000100010011001111101110110100100011111000111000011111101010010110011111100010000100101011000001010101111101111001000011101111000111000101011010111100110001011011100101001010110110110110011100100111100110001101110010100010111100000110000010110100010001100011011001100100110101110010100011101110110010000010011100000011100000101010011011111110000100000010001010111011011111110100111100011100011110110010001011101111001011101010110111001001000111001001111001111110111111100001111100100110011111110110101000011010111110010001100000111100010011100011010000101010111010101101000011001110011000000110110110001101100110101110010010111011100110101000110000011001010100000110000000001110010001010001001101111100001111111011010010011100110010000111010001001111111110000010101110011010100100101101100111000010110100110010001010110111110011000111011101110100010000110110110011001011111011111000000000000001110000001000011000110111000000110100110110001111011111100010010011100101010000111000011111010000001010010011101010010110011000000001111110000000010111011000010001111000100110101110001000011111001101111111100011111011001001110000101001101110100111010011011101000110010000001001000001100110001110101100001000110100100010111101100010100110011111010011100100001101111010000110110101111111001111011100001101100000001101111100100
'''

两个64位的lfsr，设为s1,s2,加了个滤波，也就是random()>0.1时，输出s1,否则输出s2。认为random很随机，那么所有输出的很大一部分都是来自于s1,那么应该有连续64个输出同时来自于s1。也就是知道lfsr的一个现态，可以逆lfsr回溯到初态，再利用次初态生成输出流，若与题目中输出流相符程度很大，则可认为此时的初态是正确的。

对于逆lfsr，异或矩阵直接梭哈

嫖代码

class lfsr():
    def __init__(self, init, mask, length):
        self.init = init
        self.mask = mask
        self.lengthmask = 2**length-1
 
    def next(self):
        nextdata = (self.init << 1) & self.lengthmask 
        i = self.init & self.mask & self.lengthmask 
        output = 0
        while i != 0:
            output ^= (i & 1)
            i = i >> 1
        nextdata ^= output
        self.init = nextdata
        return output
    
output='10001011010100011000100101001011100010110111001100001110000111011011100101101101000111101100010111100011000011111111010101111100101010101100010100000111011010011110111000100000101100101010110100111100011000101010101011011111011011000001101001011000010000011110001111001111011100110011111111101000111101001010000110001110111101001001101011101101001010001101010010110000000000001001101100101011110011010110011010110110011001001111001010100011110111100100010110111100110010000000010010011110001100000011000001110001000000010000100100101100000011100000011110101001011010011010100001101000010100100000011001011001000110000000000111011101000110010110111110010101110010001010001111111000011010000011001110111001000010011000000111010111100000100010011001111101110110100100011111000111000011111101010010110011111100010000100101011000001010101111101111001000011101111000111000101011010111100110001011011100101001010110110110110011100100111100110001101110010100010111100000110000010110100010001100011011001100100110101110010100011101110110010000010011100000011100000101010011011111110000100000010001010111011011111110100111100011100011110110010001011101111001011101010110111001001000111001001111001111110111111100001111100100110011111110110101000011010111110010001100000111100010011100011010000101010111010101101000011001110011000000110110110001101100110101110010010111011100110101000110000011001010100000110000000001110010001010001001101111100001111111011010010011100110010000111010001001111111110000010101110011010100100101101100111000010110100110010001010110111110011000111011101110100010000110110110011001011111011111000000000000001110000001000011000110111000000110100110110001111011111100010010011100101010000111000011111010000001010010011101010010110011000000001111110000000010111011000010001111000100110101110001000011111001101111111100011111011001001110000101001101110100111010011011101000110010000001001000001100110001110101100001000110100100010111101100010100110011111010011100100001101111010000110110101111111001111011100001101100000001101111100100'
mask1=17638491756192425134
mask2=14623996511862197922
N=64
 
def delfsr(rounds,init,mask):
    for j in range(rounds+N):
        t=init%2
        init=init>>1
        t^=bin(init&mask)[2:].count('1')%2
        init=(t<<(N-1))+init
    return init
 
def correlation(A,B):
    assert len(A)==len(B)
    N=2048
    d=0
    for i in range(len(A)):
        if A[i]==B[i]:
            d+=1
    return d/N
       
def guess_init1(output,mask):
    possible,max_p=0,0.0
    for i in range(0,len(output)-N):
        init=int(output[i:i+N],2)
        init=delfsr(i,init,mask)
        LFSR=lfsr(init,mask,N)
        out=''
        for i in range(2048):
            out+=str(LFSR.next())
        p=correlation(out,output)
        if p>max_p:
            possible,max_p=init,p
    print('possible: ',possible)
    print('max_p: ',max_p)
    return possible
 
init1=guess_init1(output,mask1)
#15401137114601469828
'''
possible:  15401137114601469828
max_p:  0.9453125
'''
init1=15401137114601469828
LFSR=lfsr(init1,mask1,N)
'''
known=[]
for i in range(2048):
    o=LFSR.next()
    if o !=int(output[i]):
        known.append((i,int(output[i])))
#print(known)
'''
known=[(4, 1), (12, 0), (30, 1), (37, 0), (41, 1), (53, 1), (69, 0), (85, 1), (97, 1), (101, 0), (146, 0), (148, 0), (193, 0), (196, 1), (260, 0), (281, 0), (341, 1), (357, 1), (390, 1), (407, 0), (428, 0), (431, 0), (438, 1), (477, 1), (520, 0), (523, 0), (529, 0), (539, 0), (541, 1), (566, 0), (607, 1), (613, 0), (619, 0), (623, 1), (640, 0), (660, 1), (733, 0), (750, 0), (811, 0), (816, 0), (824, 0), (873, 1), (887, 0), (906, 1), (910, 0), (939, 0), (948, 0), (959, 0), (971, 1), (977, 0), (1001, 1), (1026, 1), (1030, 0), (1046, 0), (1052, 0), (1078, 0), (1082, 0), (1109, 1), (1120, 0), (1126, 0), (1137, 1), (1158, 1), (1163, 0), (1194, 1), (1195, 1), (1222, 1), (1237, 1), (1244, 1), (1280, 0), (1286, 0), (1311, 1), (1345, 1), (1391, 0), (1401, 0), (1415, 0), (1440, 1), (1456, 0), (1495, 1), (1506, 0), (1518, 0), (1532, 1), (1535, 1), (1571, 1), (1612, 0), (1619, 0), (1624, 1), (1642, 0), (1646, 1), (1654, 0), (1709, 0), (1718, 0), (1745, 0), (1764, 0), (1792, 0), (1797, 1), (1834, 1), (1848, 1), (1855, 1), (1861, 1), (1871, 0), (1894, 0), (1901, 0), (1906, 1), (1925, 0), (1950, 0), (1967, 0), (1970, 0), (1979, 0), (2026, 1), (2027, 1), (2036, 1), (2046, 0)]
M = block_matrix(Zmod(2), [Matrix([0] * 63), identity_matrix(63)], nrows = 2, subdivide = False)
 
mask = mask2.digits(2)[::-1]
mask = Matrix(Zmod(2), mask).T
 
M = block_matrix(Zmod(2), [M, mask], ncols = 2, subdivide = False)
A = []
for index, out in known:
    A.append((M^index*mask).list())
 
A = Matrix(Zmod(2), A).T
y = vector(Zmod(2), [x[1] for x in known])
init=A.solve_left(y).list()
print(int(''.join([str(i) for i in init]),2))
#11256716742701089092

还有个啥题叫啥wiener #

记得到时候去嫖脚本👨‍🦳