论文
Boneh Publications: Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes (stanford.edu)

隐藏数问题（HNP / Hidden Number Problem）

HNP定义

MSB（most significant bits）

多大的k可以来解决HNP问题

定理1

定理2

LLL算法

“Unofficial” - 35C3 CTF | Holocircuit’s blog

LLL格约减算法的定义

LLL格约减之后得到优质基，优质基其中一条性质是基尽可能小

LLL的应用

可规约到格的另一个基本问题：最近向量问题（CVP)。

E.G

?A,X*?B应该多大呢

保证vk中的每一项的长度都差不多，这样有利于找到vk

Lattice 之 HNP

有这样的一些等式，然后A,B已知,k的bit位数要小于p的bit位数，等式数量足够的情况下，少6bit位数可以求解k

具体构造如下矩阵

其中K为ki同bit位数的数（bit_length(ki)=250 K=2^250)

Z为需要自己构造的数

要尽可能的满足Z*x的bit位数与K一致

一般Z取K/q, K的构造也是为了让vk中的每一项的长度都差不多，这样有利于找到vk

例题

HGAME2024 WEEK3 HNP

题目

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

def encrypt(m,p,t):
    return [(ti*m)%p for ti in t]

m=bytes_to_long(flag[:63])
length=m.bit_length()+8
p=getStrongPrime(length)
n=32
t=[getRandomRange(0,p) for _ in range(n)]
enc=encrypt(m,p,t)
res=[i%(2**n+1) for i in enc]

print(f'p={p}')
print(f't={t}')
print(f'res={res}')

"""
p=11306299241774950053269547103284637414407835125777245204069367567691021928864773207548731051592853515206232365901169778048084146520829032339328263913558053
t=[3322008555255129336821309701482996933045379792432532251579564581211072677403244970423357912298444457457306659801200188166569132560659008356952740599371688, 8276764260264858811845211578415023343942634613522088631021199433066924291049858607045960690574035761370394263154981351728494309737901121703288822616367266, 9872291736922974456420418463601129094227231979218385985149661132792467621940722580745327835405374826293791332815176458750548942757024017382881517284991646, 4021521745142535813153669961146457406640791935844796005344073886289668464885011415887755787903927824762833158130615018326666118383128627535623639046817799, 24569151076141700493541155834378165089870615699969211988778938492838766214386066952596557490584021813819164202001474086538804476667616708172536787956586, 3218501156520848572861458831123822689702035242514803505049101779996231750875036344564322600086861361414609201214822262908428091097382781770850929067404210, 3563405987398375076327633444036492163004958714828685846202818610320439306396912425420391070117069875583786819323173342951172594046652017297552813501557159, 4914709045693863038598225124534515048993310770286105070725513667435983789847547225180024824321458761262390817487861675595466513538901373422149236133926354, 10800566112999947911006702454427389510409658644419749067440812458744391509925306994806187389406032718319773665587324010542068486131582672363925769248595266, 623364920052209790798128731089194813138909691039137935275037339503622126325928773037501254722851684318024014108149525215083265733712809162344553998427324, 4918421097628430613801265525870561041230011029818851291086862970508621529074497601678774921285912745589840510459677522074887576152015356984592589649844431, 7445733357215847370070696136653689748718028080364812263947785747353258936968978183471549706166364243148972154215055224857918834937707555053246184822095602, 9333534755049225627530284249388438694002602645047933865453159836796667198966058177988500184073454386184080934727537200575457598976121667373801441395932440, 5010854803179970445838791575321127911278311635230076639023411571148488903400610121248617307773872612743228998892986200202713496570375447255258630932158822, 6000645068462569819648461070140557521144801013490106632356836325002546400871463957228581143954591005398533252218429970486115490535584071786260818773166324, 8007260909124669381862034901556111245780505987082990804380814797200322228942432673939944693062470178256867366602331612363176408356304641672459456517978560, 10179739175373883376929532026389135792129233730601278687507041429438945598523995700184622359660605910932803141785598758326254886448481046307666042835829725, 8390072767717395701926289779433055672863880336031837009119103448675232362942223633129328309118158273835961567436591234922783953373319767835877266849545292, 7875011911562967874676113680693929230283866841475641162854665293111344467709424408623198370942797099964625447512797138192853009126888853283526034411007513, 5293772811020012501020124775214770193234655210319343058648675411115210453680753070042821835082619634341500680892323002118953557746116918093661769464642068, 2613797279426774540306461931319193657999892129844832159658771717387120246795689678231275371499556522396061591882431426310841974713419974045883021613987705, 9658126012133217804126630005236073513485215390812977974660029053522665282550965040288256074945246850744694519543358777252929661561636241161575937061521711, 2982535220844977621775139406357528876019349385634811795480230677982345697183586203669094998039995683973939721644887543907494963824968042199353945120367505, 107289984878191849357180490850397539311037762262082755398160292401340078782643246498566039415279868796667596686125847400130898160017838981308638814854641, 120993130590874228473811314869823704699012435303134640953201808807618070048912918046616664677916248813062043597607873728870402493717351447905456920806865, 2253040652771796284266254261719805768102740653097446325869783812201171144150768875885963729324915714812719138247784194752636928267712344736198611708630089, 8650007272154283057350664311505887535841268767424545016901418989555620869091145651216448723200240914143882774616678968725523914310965356875681207295242434, 9628747829107584650014156079928108801687158029086221730883999749044532846489666115473993005442192859171931882795973774131309900021287319059216105939670757, 10846936951522093706092027908131679912432689712451920718439096706435533926996215766191967052667966065917006691565771695772798711202812180782901250249613072, 1606865651227988736664127021678689299989045439998336603562232908863405778474520915170766771811336319655792746590981740617823564813573118410064976081989237, 6239063657591721097735049409610872941214078699330136826592958549212481802973973104374548555184907929255031570525343007518434357690480429981016781110249612, 1855365916387114620581029939707053701062476745235578683558063796604744448050278138954359506922875967537567359575662394297579958372107484276360920567730458]
res=[2150646508, 1512876052, 2420557546, 2504482055, 892924885, 213721693, 2708081441, 1242578136, 717552493, 3210536920, 2868728798, 1873446451, 645647556, 2863150833, 2481560171, 2518043272, 3183116112, 3032464437, 934713925, 470165267, 1104983992, 194502564, 1621769687, 3844589346, 21450588, 2520267465, 2516176644, 3290591307, 3605562914, 140915309, 3690380156, 3646976628]
"""

题解

wp

from Crypto.Util.number import *
import gmpy2

p = 
B = []
R = []
n = 32
kbits = 512-n
M = Matrix(QQ,n+2,n+2)
for i in range(n):
    M[i,i] = p
    M[-2,i] = B[i]*inverse(2^(32)+1,p)
    M[-1,i] = -R[i]*inverse(2^(32)+1,p)

t = QQ(2^kbits /p)
K = 2^kbits

M[-2,-2] = t
M[-1,-1] = K

for _ in M.LLL():
    if abs(_[-1]) == K:
        flag = abs(_[-2]) // t
        print( long_to_bytes(int(flag)))
        break

MTCTF strange_rsa3

题目

from Crypto.Util.number import *
from secret import flag3

qBits = 2048
pBits = 512
num = 2
q = getPrime(qBits)
p = [getPrime(pBits) for _ in range(num)]
r = [getRandomRange(1, 2 ** (pBits * 2))]

a = getRandomRange(1, 2 ** pBits)
b = getRandomRange(1, 2 ** pBits)
gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1] ** 2) % (p[0] * p[1] ** 2)
r.append(a * r[0] % p[1] ** 2)

n = [p[i] * q + r[i] for i in range(num)]
e = 0x10001
c = pow(bytes_to_long(flag3), e, q)

output = open('output.txt', 'w')
output.write('n = ' + str(n) + '\n')
output.write('c = ' + str(c) + '\n')
output.write('gift = ' + str(gift) + '\n')

'''

n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
p = [10946837640113493291358837873345799060524211396318128031616119937230375611461398026242887066008841733944238658233988256373284494642790134423412452126096931,8870637512403646759604184989075036324872077413980854140857074514347730644595095752344958376649371893483720976713973475270507678333288479309954238685161531]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999

'''

题解

连分数求解出p0,p1

求b

第一种解法 HNP问题构造格

第二种解法模上P

gift = (p[0] a - p[1]) inverse(b, p[0] p[1] ** 2)
同时模上p[0]
gift%p[0]=-p[1]ib

求出r0

wp

第一种

from Crypto.Util.number import isPrime, long_to_bytes
from Crypto.Util.number import inverse

n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999
print(gift.bit_length())
#求p0,p1

'''
def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    #辗转相除法
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf

def gradualFra(cf):
    numerator = 0#分子
    denominator = 1#分母
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return (numerator, denominator)
def getGradualFra(cf):
    gf = []
    for i in range(1, len(cf)):
        gf.append(gradualFra(cf[:i]))
    return gf
cf=continuedFra(n[0],n[1])
p=[]
for (pp1, pp0) in getGradualFra(cf):#所有渐进分数
    if int(pp1).bit_length()==512 and int(pp0).bit_length()==512:
        if isPrime(pp1) and isPrime(pp0):
            p.append(pp0)
            p.append(pp1)
            #print("p0",pp0)
            #print("p1",pp1)
            break
print(p)
'''
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999

p=[10946837640113493291358837873345799060524211396318128031616119937230375611461398026242887066008841733944238658233988256373284494642790134423412452126096931, 8870637512403646759604184989075036324872077413980854140857074514347730644595095752344958376649371893483720976713973475270507678333288479309954238685161531]
mod=p[0]*p[1]*p[1]
igift=inverse(gift,mod)

#构造格子
'''b1=vector(ZZ,[1,0,p[0]*igift])
b2=vector(ZZ,[0,2**512,p[1]*igift])
b3=vector(ZZ,[0,0,mod])
m = matrix(ZZ,[b1,b2,b3])#
re=m.LLL()
#[11022212982424652632647405376934304592755205611710996956605750639057526541029596360155260174701488414125581957719469209021506720182948113423105539872264354                                                                             -13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096                                                                               9864245136392130046455737513510508070496025625897918994462477425135301427183420481191209852444833597428299605829396903107753368813219485870517193682708546]
a=abs(re[0][0])
b=abs(re[0][-1])
#a=11022212982424652632647405376934304592755205611710996956605750639057526541029596360155260174701488414125581957719469209021506720182948113423105539872264354
#b=9864245136392130046455737513510508070496025625897918994462477425135301427183420481191209852444833597428299605829396903107753368813219485870517193682708546
'''
'''n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999

p=[10946837640113493291358837873345799060524211396318128031616119937230375611461398026242887066008841733944238658233988256373284494642790134423412452126096931, 8870637512403646759604184989075036324872077413980854140857074514347730644595095752344958376649371893483720976713973475270507678333288479309954238685161531]
mod=p[0]*p[1]*p[1]

#构造格子
b1=vector(ZZ,[1,0,p[0]])
b2=vector(ZZ,[0,1,gift])
b3=vector(ZZ,[0,0,mod])
m = matrix(ZZ,[b1,b2,b3])
re=m.LLL()
print(int(re[0][0]).bit_length())

b1=vector(ZZ,[5,-4,2])
b2=vector(ZZ,[-9,-19,3])
b3=vector(ZZ,[14,15,9])
m = matrix(ZZ,[b1,b2,b3])
re=m.LLL()
print(int(re[0][0]).bit_length())
b=re[0][-1]
'''
#解求r
r=igift*inverse(b, p[0] * p[1] ** 2) *(p[0]*n[1]-p[1]*n[0])%mod
print(r)
q=(n[0]-r)//p[0]
assert q*p[0]+r==n[0]
phi=q-1
e=65537
d=inverse(e,phi)
m=pow(c,d,q)
print(m)
print(long_to_bytes(m))
#flag{bbfd3b8cc77896de867998bab7659e2fbce6378f}

第二种

#gift = (p[0] * a - p[1]) * inverse(b, p[0] * p[1] ** 2)
#同时模上p[0]
#gift%p[0]=-p[1]*ib
n = [334024028297795358428409534536782438908850190596668304865805437854374647984162763213581202801755428896203566172506219587266859416880045688129543855047675462354257676254231028533265496444966553195988075269677126779791155950793986187076641998741755872346979307739639779735262978907659727511419480461209503641512912873117056664008629779726881137366723127568036608925132936367006658464077463797854166622020483102972486974655232026096153672010479488999300909745157075526157596970246521452157940857495163175605553461432715056788388724755538433445976849818771932805940067427962262593386608298455471107791678224956504101174392785507134071131842103995133811964997751791768061100121699973057595724142612170517768245173187399850847945628945800042668385798893530527806229363060713249, 270672332309468804376393577492871858269490099887383011988714622534037610808764741901954257217313289938393835900354736668003700671505047142365053976908516056996483106174902631762442253779775073373220342445779447626486345253598470015470094856727845150372622299396840670432953284676150980428391739322739397783248924710490946083987879121564403742528241040454099534823772379455574658130173290640751198753015984316400694738114541263533626932367096040344071742474883684682734122111076840572805111010694147825191233741720325878397443178835435703420465683485344417909319591496135706730327376897531024858122747777315158814568580929655522627811650949169204543250919027738723235091257934106114809110289433115714333069841583284243937630033653684708127947780848521445941847102881070046]
c = 24426016715355498456650532748209528249200902516644306644652290745346403378221744208791754411669322694597831272399935610924080672864361088045894354412944203199767471898920740773322967470374385635042086816010876203117884874681450622109443867183037282062248951073356702181165103759051513426785435705002047708435055880616309144483691648077981524802908185706596363674820857151388761087408514551645305031742705266691826719380663571699663832536944531865183586885154128228789310222929701360939023228059118720311899056620389378996862413971733056546988166759451010742768802840638380019172710929867945108511664271273569394689619
gift = 173299379625576798749821685155193435290573235640007530711924098468561852299646118206367598564087551037396665586630782838190274697684611102346492601699992667822233634078800006099513099432664305226448819277556828816420517850404262393535832488384876680039695417291460237594174659357055221582914415278609167623124281569332881993050546046852564902573985929794261636296569394448935231131668411811662581097119330330246497311885207256858435515769776396794250803110128999
p=[10946837640113493291358837873345799060524211396318128031616119937230375611461398026242887066008841733944238658233988256373284494642790134423412452126096931, 8870637512403646759604184989075036324872077413980854140857074514347730644595095752344958376649371893483720976713973475270507678333288479309954238685161531]

mod=p[0]*p[1]*p[1]
t=gift%p[0]
ip1=inverse(p[1],p[0])
tt=p[0]-t
#print(t)
#print(p[0]-t)
ib=tt*ip1
b=inverse(ib,mod)%p[0]
print(b)
print(b.bit_length())
#9864245136392130046455737513510508070496025625897918994462477425135301427183420481191209852444833597428299605829396903107753368813219485870517193682708546
#512
#

小研究

逆元的比特值靠近模数的比特

#逆元的比特值估算

  from Crypto.Util.number import*

  qBits = 2048
  pBits = 512
  num = 2
  for i in range(10):
      q = getPrime(qBits)
      p = getPrime(pBits)
      r = getRandomRange(1, 2 ** (pBits * 2))
      #1024
      x=inverse(q,r)
      print(x.bit_length())
      '''

  qBits = 2048
  pBits = 512
  #q,在p下的逆元
  511
  511
  512
  510
  511
  511
  509
  511
  512
  510

  #q 2048,r 1024
  # x=inverse(q,r)
  1023
  1023
  1021
  1023
  1016
  1024
  1022
  1022
  1015
  1020

XCTF2020-高校战役

题目

#!/usr/bin/env python3
import os
from random import SystemRandom
from string import ascii_letters, digits
from hashlib import sha256

from Crypto.Util import number

from flag import FLAG

random = SystemRandom()

def proof_of_work():
    s = os.urandom(10)
    digest = sha256(s).hexdigest()
    print(f"sha256(XXX + {s[3:].hex()}) == {digest}")
    try:
        x = input("Give me XXX in hex: ")
    except:
        print("Invalid input!")
        return False

    if len(x) != 6 or x != s[:3].hex():
        print("Wrong XXX!")
        return False
    return True

def genkey():
    '''
    q:  128 bit
    p:  1024 bit
    h:  2
    x:  [1, q-1]
    :return:
    '''
    # DSA
    q = number.getPrime(128)

    while True:
        t = random.getrandbits(1024-128-1)
        p = (t * 2*q + 1)
        if number.isPrime(p):
            break

    e = (p-1) // q
    g = pow(2, e, p)

    x = random.randint(1, q-1)
    y = pow(g, x, p)

    return {'y':y, 'g':g, 'p':p, 'q':q, 'x':x}

def sign(m, key):
    '''

    :param m: 待签名的消息
    :param key: 密钥
    :return: (r,s)
    '''
    g, p, q, x = key['g'], key['p'], key['q'], key['x']

    k = random.randint(1, q-1)
    print(f"k.bit_length() == {k.bit_length()}")

    Hm = int.from_bytes(sha256(m.encode()).digest(), 'big')

    r = pow(g, k, p) % q
    s = (number.inverse(k, q) * (Hm + x*r)) % q
    return (r, s)

#验签
def verify(m, sig, key):
    '''

    :param m: 待验签的消息
    :param sig: 签名
    :param key:  密钥
    :return:  true or false
    '''
    r, s = sig
    y, g, p, q = key['y'], key['g'], key['p'], key['q']
    if not (0 < r < q) or not (0 < s < q):
        return False

    Hm = int.from_bytes(sha256(m.encode()).digest(), 'big')
    w = number.inverse(s, q)
    u1 = (w * Hm) % q
    u2 = (w * r) % q
    v = ( (pow(g, u1, p) * pow(y, u2, p)) % p ) % q

    return v == r

#对输出的name做出限制
#长度0 < len(name) <= 20
#是字母和数字的组合
#不能包含admin
def _is_valid_name(name):
    if not (0 < len(name) <= 20):
        print("Invalid username length!")
        return False

    for c in name:
        if c not in ascii_letters + digits:
            print("Invalid character in username!")
            return False

    if name == "admin":
        print("Username can't be 'admin'")
        return False

    return True

#产生签名
def sign_up(key):
    name = input("Please input your username: ")
    if not _is_valid_name(name):
        return

    (r, s) = sign(name, key)
    sig = name.encode() + r.to_bytes(20, 'big') + s.to_bytes(20, 'big')
    print(f"Here is your signature in hex: {sig.hex().upper()}")

#验证签名
def sign_in(key):
    data = input("Please send me your signature: ")
    try:
        data = bytes.fromhex(data)
    except ValueError:
        print("Invalid signature format!")
        return
    if not (40 < len(data) <= 60):
        print("Invalid signature length!")
        return

    (name, r, s) = (data[:-40].decode(), data[-40:-20], data[-20:])
    sig = map(lambda x: int.from_bytes(x, 'big'), (r, s))

    if not verify(name, sig, key):
        print("Wrong signature!")
        return

    print(f"Welcome, {name}")
    if name == "admin":
        print(f"The flag is {FLAG}")

menu = '''
1. sign up
2. sign in
3. exit
'''

def main():
    try:
        if not proof_of_work():
            return

        print("Generating DSA parameters...")
        key = genkey()
        print(f"p = {key['p']}")
        print(f"q = {key['q']}")
        print(f"g = {key['g']}")
        print(f"y = {key['y']}")

        while True:
            print(menu)
            choice = input("$ ")

            if choice == "1":
                sign_up(key)

            elif choice == "2":
                sign_in(key)

            elif choice == "3":
                print("Bye!")
                return

            else:
                print("Invalid choice!")
                continue
    except:
        pass

main()

##

题解

多了一步筛选，if k_bits < 122:

构造格求出私钥x（128bit),筛选k的比特与X相差较小的

wp

import re
import json
import string
import subprocess
from random import sample
from hashlib import sha256

from Crypto.Util.number import inverse
from pwn import *

host, port = ('127.0.0.1', 10000)
r = remote(host, port)
# context.log_level = 'debug'

# Proof of Work
rec = r.recvline().decode()

suffix = re.findall(r'\+ ([0-9a-f]*?)\)', rec)[0]
digest = re.findall(r'== ([0-9a-f]*?)\n', rec)[0]
print(f"suffix: {suffix} \ndigest: {digest}")

for i in range(256**3):
    guess = i.to_bytes(3, 'big') + bytes.fromhex(suffix)
    if sha256(guess).hexdigest() == digest:
        print('[!] Find: ' + guess.hex())
        break
else:
    print('Not found...')

r.sendlineafter(b'Give me XXX in hex: ', guess[:3].hex().encode())

# DSA params
params = r.recvuntil(b'3. exit\n').decode()
p = int(re.findall(r'p = ([0-9]*?)\n', params)[0])
q = int(re.findall(r'q = ([0-9]*?)\n', params)[0])
g = int(re.findall(r'g = ([0-9]*?)\n', params)[0])
y = int(re.findall(r'y = ([0-9]*?)\n', params)[0])
print(f"p: {p}\nq: {q}\ng: {g}\ny: {y}")

# Interactive
Hm_s = []
r_s = []
s_s = []

s = string.ascii_letters + string.digits
cnt = 0
total = 0
while cnt < 40:
    total += 1
    name = ''.join(random.sample(s, 10)).encode()
    r.sendlineafter(b"$ ", b"1")
    r.sendlineafter(b"Please input your username: ", name)

    rec = r.recvuntil(b"3. exit\n").decode()
    k_bits = int(re.findall(r"== ([0-9]*?)\n", rec)[0])
    if k_bits < 122:
        cnt += 1

        data = re.findall(r"in hex: ([0-9A-Z]*?)\n", rec)[0]
        sig = bytes.fromhex(data)
        (name, sig_r, sig_s) = (sig[:-40], sig[-40:-20], sig[-20:])
        (sig_r, sig_s) = map(lambda x: int.from_bytes(x, 'big'), (sig_r, sig_s))

        print(f"\ncount: {cnt}\nk_bits: {k_bits}")
        print(f"sig_r: {sig_r}\nsig_s: {sig_s}")

        Hm = int.from_bytes(sha256(name).digest(), 'big')
        Hm_s.append(Hm)
        r_s.append(sig_r)
        s_s.append(sig_s)

print(f"\nTotal times: {total}")

# save data
f = open('data', 'w')
json.dump([q, Hm_s, r_s, s_s], f)
f.close()

# solve HNP
print("\nSolving HNP...")
cmd = "sage solver.sage"
try:
    res = subprocess.check_output(cmd.split(' '))
except:
    print("Can't find x...")
    exit(1)
x = int(res)

# check
assert(y == pow(g, x, p))
print(f"find x: {x}")

#找到私钥x
# forge signature
admin = b"admin"
Hm = int.from_bytes(sha256(admin).digest(), 'big')
k = 0xdeadbeef
k_inv = inverse(k, q)
sig_r = pow(g, k, p) % q
sig_s = (k_inv * (Hm + x*sig_r)) % q

# sign in
#sig = name.encode() + r.to_bytes(20, 'big') + s.to_bytes(20, 'big')
sig = admin + sig_r.to_bytes(20, 'big') + sig_s.to_bytes(20, 'big')
print(f"Sending signature: {sig.hex().upper()}")
r.sendlineafter(b'$ ', b"2")
r.sendlineafter(b'Please send me your signature: ', sig.hex().upper().encode())

r.interactive()

'''
# input: q, r_s, s_s, Hm_s
import json

t = 40

# Load data
f = open("data", "r")
(q, Hm_s, r_s, s_s) = json.load(f)

# Calculate A & B
A = []
B = []
for r, s, Hm in zip(r_s, s_s, Hm_s):
    A.append( ZZ( (inverse_mod(s, q)*r) % q ) )
    B.append( ZZ( (inverse_mod(s, q)*Hm) % q ) )

# Construct Lattice
K = 2^122   # k < 2^122
X = q * identity_matrix(QQ, t) # t * t
Z = matrix(QQ, [0] * t + [K/q] + [0]).transpose() # t+1 column
Z2 = matrix(QQ, [0] * (t+1) + [K]).transpose()    # t+2 column

Y = block_matrix([[X],[matrix(QQ, A)], [matrix(QQ, B)]]) # (t+2) * t
Y = block_matrix([[Y, Z, Z2]])

# Find short vector
Y = Y.LLL()

# check
k0 = ZZ(Y[1, 0] % q)
x = ZZ(Y[1, -2] / (K/q) % q)
assert(k0 == (A[0]*x + B[0]) % q)
print x'''

NPUCTF2020-babyLCG

题目

from Crypto.Util.number import *
from Crypto.Cipher import AES
from secret import flag

class LCG:
    def __init__(self, bit_length):
        m = getPrime(bit_length)
        a = getRandomRange(2, m)
        b = getRandomRange(2, m)
        seed = getRandomRange(2, m)
        self._key = {'a': a, 'b': b, 'm': m}
        self._state = seed

    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state

    def export_key(self):
        return self._key

def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()
    f = open("HNP/key", "w")
    f.write(str(key))
    return rand_iter

def leak_data(rand_iter):
    f = open("HNP/old", "w")
    for i in range(20):
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter

def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)

def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    encrypt(rand_iter)

if __name__ == "__main__":
    main()

#key={'b': 153582801876235638173762045261195852087, 'a': 107763262682494809191803026213015101802, 'm': 226649634126248141841388712969771891297}
#old=
#ct=

题解

恢复seed，接下来生生随机数，KEY，iv可知，decrypt

恢复seed(已知a,b,m和伪随机数的高位，恢复seed）

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

保证规约出来的$[l_1,l_2......l_i,l_0,?K]$bit差不多

算出seed之后脚本直接更改题目里这几个值就好啦

wp

'''
b=153582801876235638173762045261195852087
a=107763262682494809191803026213015101802
m=226649634126248141841388712969771891297
leak = [0]
# 读取文件内容并添加到列表中
with open('D:\\fj\\old', 'r') as file:
    for line in file:
        leak.append(int(line.strip()))
#print(leak)
#leak=[0,7800489346663478448, 11267068470666042741, 5820429484185778982, 6151953690371151688, 548598048162918265, 1586400863715808041, 7464677042285115264, 4702115170280353188, 5123967912274624410, 8517471683845309964, 2106353633794059980, 11042210261466318284, 4280340333946566776, 6859855443227901284, 3149000387344084971, 7055653494757088867, 5378774397517873605, 8265548624197463024, 2898083382910841577, 4927088585601943730]
h=[]
for i in range(len(leak)):
    h.append(leak[i] <<64)
mm=18446744073709551616
print(mm.bit_length())
#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] % m)
    B.append((a*B[i-1]+a*h[i]+b-h[i+1]) % m)
A = A[1:]
B = B[1:]

tt=20-1
K=2**64

M = list(matrix(ZZ,tt+2,tt+2))
for i in range(tt):
    M[i][i] = m
    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,m))%m
print(seed)
seed=73991202721494681711496408225724067994
'''

from Crypto.Util.number import *
from Crypto.Cipher import AES

class LCG:
    def __init__(self, bit_length):
        b = 153582801876235638173762045261195852087
        a = 107763262682494809191803026213015101802
        m = 226649634126248141841388712969771891297
        seed = 73991202721494681711496408225724067994
        self._key = {'a': a, 'b': b, 'm': m}
        self._state = seed

    def next(self):
        self._state = (self._key['a'] * self._state + self._key['b']) % self._key['m']
        return self._state

    def export_key(self):
        return self._key

def gen_lcg():
    rand_iter = LCG(128)
    key = rand_iter.export_key()

    return rand_iter

def leak_data(rand_iter):
    f = open("HNP/old", "w")
    for i in range(20):
        f.write(str(rand_iter.next() >> 64) + "\n")
    return rand_iter

'''
def encrypt(rand_iter):
    f = open("ct", "wb")
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    cipher = AES.new(key, AES.MODE_CBC, iv)
    pt = flag + (16 - len(flag) % 16) * chr(16 - len(flag) % 16)
    ct = cipher.encrypt(pt.encode())
    f.write(ct)
'''
def decrypt(rand_iter):
    with open("D:\\fj\\ct", "rb") as f:
        m = f.read()

    print(m)
    #b'\xe0\xe0p,\xb7\xd6\xfc\x19\xac\xe7)\xbe\xfc\xa4\n\xf5\x01#\xf7\xa6\xed\xe1\xf3\xaeK:*\xcd{\x1d\xd87\x14s\x10X\x86\xaf\xd1WsD\x1f\xa0lej\xd6'
    key = rand_iter.next() >> 64
    key = (key << 64) + (rand_iter.next() >> 64)
    key = long_to_bytes(key).ljust(16, b'\x00')
    iv = long_to_bytes(rand_iter.next()).ljust(16, b'\x00')
    aes = AES.new(key, AES.MODE_CBC, iv)
    flag = aes.decrypt(m)
    print(flag)

def main():
    rand_iter = gen_lcg()
    rand_iter = leak_data(rand_iter)
    decrypt(rand_iter)

if __name__ == "__main__":
    main()
#npuctf{7ruc4t3d-L(G-4nd-LLL-4r3-1nt3r3st1ng}

总结

解决HNP问题