2024-DASCTF-暑期挑战赛-wp-crypto

其实根本没打，rec一个人早杀完了，我在ImaginaryCTF坐牢XD，实在卡住的时候来看了下题玩。

complex_enc

题目描述：

1
2
3

宁静祥和的一天里，半空中突然出现一道光门，我们怎么进去呢？

On a peaceful and serene day, a portal of light suddenly appeared in mid-air. How do we get inside?

题目：

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


def GET_KEY(n):
    sum=2
    key=[1]
    for i in range(n):
        r=random.randint(0,1)
        x=sum+random.randint(0,n)*r
        key.append(x)
        sum+=x
    return key

def enc(m,k):
    cipher_list = []
    for i in range(len(m)):
        if m[i] == 1:
            cipher_list.append(m[i] * k[i])
    cipher = sum(cipher_list)
    return cipher

m=bytes_to_long(flag)
m = [int(bit) for byte in flag for bit in format(byte, '08b')]
key=GET_KEY(len(m))
c=enc(m,key)

with open('output.txt', 'w') as f:
    f.write(str(c))
    f.write(str(key))

output.txt：

1
2

287687761937146187597379915545639385740275457170939564210821293233370716878150576
[1, 2, 87, 99, 190, 380, 760, 1702, 3350, 6712, 13302, 26669, 53257, 106512, 213212, 426262, 852583, 1705083, 3410164, 6820581, 13640909, 27281818, 54563749, 109127508, 218254958, 436509851, 873019897, 1746039768, 3492079367, 6984158992, 13968317822, 27936635563, 55873271257, 111746542368, 223493084736, 446986169472, 893972338944, 1787944677888, 3575889355776, 7151778711750, 14303557423366, 28607114846668, 57214229693336, 114428459386792, 228856918773559, 457713837547023, 915427675094046, 1830855350188252, 3661710700376344, 7323421400752912, 14646842801505675, 29293685603011275, 58587371206022773, 117174742412045483, 234349484824090806, 468698969648181659, 937397939296363271, 1874795878592726601, 3749591757185453143, 7499183514370906547, 14998367028741812852, 29996734057483625898, 59993468114967251756, 119986936229934503501, 239973872459869007099, 479947744919738013939, 959895489839476027878, 1919790979678952055983, 3839581959357904111739, 7679163918715808223719, 15358327837431616447319, 30716655674863232894717, 61433311349726465789458, 122866622699452931578804, 245733245398905863157495, 491466490797811726314990, 982932981595623452629980, 1965865963191246905260222, 3931731926382493810520182, 7863463852764987621040623, 15726927705529975242080987, 31453855411059950484161974, 62907710822119900968323970, 125815421644239801936647918, 251630843288479603873295836, 503261686576959207746591710, 1006523373153918415493183613, 2013046746307836830986367190, 4026093492615673661972734253, 8052186985231347323945468456, 16104373970462694647890936894, 32208747940925389295781874025, 64417495881850778591563748059, 128834991763701557183127495888, 257669983527403114366254991760, 515339967054806228732509983520, 1030679934109612457465019967093, 2061359868219224914930039934133, 4122719736438449829860079868450, 8245439472876899659720159736935, 16490878945753799319440319473651, 32981757891507598638880638947330, 65963515783015197277761277894728, 131927031566030394555522555789579, 263854063132060789111045111579109, 527708126264121578222090223158048, 1055416252528243156444180446316096, 2110832505056486312888360892632193, 4221665010112972625776721785264450, 8443330020225945251553443570528835, 16886660040451890503106887141057670, 33773320080903781006213774282115477, 67546640161807562012427548564230882, 135093280323615124024855097128461699, 270186560647230248049710194256923398, 540373121294460496099420388513846796, 1080746242588920992198840777027693592, 2161492485177841984397681554055387246, 4322984970355683968795363108110774528, 8645969940711367937590726216221549105, 17291939881422735875181452432443098117, 34583879762845471750362904864886196180, 69167759525690943500725809729772392360, 138335519051381887001451619459544784838, 276671038102763774002903238919089569616, 553342076205527548005806477838179139174, 1106684152411055096011612955676358278348, 2213368304822110192023225911352716556750, 4426736609644220384046451822705433113446, 8853473219288440768092903645410866226907, 17706946438576881536185807290821732453830, 35413892877153763072371614581643464907890, 70827785754307526144743229163286929815519, 141655571508615052289486458326573859631099, 283311143017230104578972916653147719262229, 566622286034460209157945833306295438524626, 1133244572068920418315891666612590877049074, 2266489144137840836631783333225181754098066, 4532978288275681673263566666450363508196132, 9065956576551363346527133332900727016392264, 18131913153102726693054266665801454032784553, 36263826306205453386108533331602908065569081, 72527652612410906772217066663205816131138180, 145055305224821813544434133326411632262276342, 290110610449643627088868266652823264524552684, 580221220899287254177736533305646529049105368, 1160442441798574508355473066611293058098210736, 2320884883597149016710946133222586116196421472, 4641769767194298033421892266445172232392842944, 9283539534388596066843784532890344464785686063, 18567079068777192133687569065780688929571371951, 37134158137554384267375138131561377859142743902, 74268316275108768534750276263122755718285487804, 148536632550217537069500552526245511436570975608, 297073265100435074139001105052491022873141951360, 594146530200870148278002210104982045746283902576, 1188293060401740296556004420209964091492567805360, 2376586120803480593112008840419928182985135610512, 4753172241606961186224017680839856365970271221024, 9506344483213922372448035361679712731940542442048, 19012688966427844744896070723359425463881084884096, 38025377932855689489792141446718850927762169768220, 76050755865711378979584282893437701855524339536412, 152101511731422757959168565786875403711048679072824, 304203023462845515918337131573750807422097358145648, 608406046925691031836674263147501614844194716291296, 1216812093851382063673348526295003229688389432582797, 2433624187702764127346697052590006459376778865165617, 4867248375405528254693394105180012918753557730331006, 9734496750811056509386788210360025837507115460662129, 19468993501622113018773576420720051675014230921324265, 38937987003244226037547152841440103350028461842648406, 77875974006488452075094305682880206700056923685296910, 155751948012976904150188611365760413400113847370593722, 311503896025953808300377222731520826800227694741187444, 623007792051907616600754445463041653600455389482374933, 1246015584103815233201508890926083307200910778964749821, 2492031168207630466403017781852166614401821557929499642, 4984062336415260932806035563704333228803643115858999284, 9968124672830521865612071127408666457607286231717998666, 19936249345661043731224142254817332915214572463435997301, 39872498691322087462448284509634665830429144926871994535, 79744997382644174924896569019269331660858289853743989190, 159489994765288349849793138038538663321716579707487978260, 318979989530576699699586276077077326643433159414975956596, 637959979061153399399172552154154653286866318829951913129, 1275919958122306798798345104308309306573732637659903826311, 2551839916244613597596690208616618613147465275319807652591, 5103679832489227195193380417233237226294930550639615305147, 10207359664978454390386760834466474452589861101279230610294, 20414719329956908780773521668932948905179722202558461220588, 40829438659913817561547043337865897810359444405116922441176, 81658877319827635123094086675731795620718888810233844882508, 163317754639655270246188173351463591241437777620467689764860, 326635509279310540492376346702927182482875555240935379529854, 653271018558621080984752693405854364965751110481870759059704, 1306542037117242161969505386811708729931502220963741518119363, 2613084074234484323939010773623417459863004441927483036238705, 5226168148468968647878021547246834919726008883854966072477346, 10452336296937937295756043094493669839452017767709932144954692, 20904672593875874591512086188987339678904035535419864289909384, 41809345187751749183024172377974679357808071070839728579818768, 83618690375503498366048344755949358715616142141679457159637536, 167237380751006996732096689511898717431232284283358914319275072, 334474761502013993464193379023797434862464568566717828638550144, 668949523004027986928386758047594869724929137133435657277100288, 1337899046008055973856773516095189739449858274266871314554200576, 2675798092016111947713547032190379478899716548533742629108401375, 5351596184032223895427094064380758957799433097067485258216802527, 10703192368064447790854188128761517915598866194134970516433605054, 21406384736128895581708376257523035831197732388269941032867210108, 42812769472257791163416752515046071662395464776539882065734420216, 85625538944515582326833505030092143324790929553079764131468840607, 171251077889031164653667010060184286649581859106159528262937681073, 342502155778062329307334020120368573299163718212319056525875362112, 685004311556124658614668040240737146598327436424638113051750724224, 1370008623112249317229336080481474293196654872849276226103501448448, 2740017246224498634458672160962948586393309745698552452207002896896, 5480034492448997268917344321925897172786619491397104904414005793914, 10960068984897994537834688643851794345573238982794209808828011587706, 21920137969795989075669377287703588691146477965588419617656023175412, 43840275939591978151338754575407177382292955931176839235312046350824, 87680551879183956302677509150814354764585911862353678470624092701691, 175361103758367912605355018301628709529171823724707356941248185403485, 350722207516735825210710036603257419058343647449414713882496370806824, 701444415033471650421420073206514838116687294898829427764992741613648, 1402888830066943300842840146413029676233374589797658855529985483227499, 2805777660133886601685680292826059352466749179595317711059970966454839, 5611555320267773203371360585652118704933498359190635422119941932909634, 11223110640535546406742721171304237409866996718381270844239883865819325, 22446221281071092813485442342608474819733993436762541688479767731638735, 44892442562142185626970884685216949639467986873525083376959535463277328, 89784885124284371253941769370433899278935973747050166753919070926554729, 179569770248568742507883538740867798557871947494100333507838141853109648, 359139540497137485015767077481735597115743894988200667015676283706219166, 718279080994274970031534154963471194231487789976401334031352567412438331, 1436558161988549940063068309926942388462975579952802668062705134824876530, 2873116323977099880126136619853884776925951159905605336125410269649753060, 5746232647954199760252273239707769553851902319811210672250820539299506381, 11492465295908399520504546479415539107703804639622421344501641078599012695, 22984930591816799041009092958831078215407609279244842689003282157198025444, 45969861183633598082018185917662156430815218558489685378006564314396050678, 91939722367267196164036371835324312861630437116979370756013128628792101318, 183879444734534392328072743670648625723260874233958741512026257257584202636, 367758889469068784656145487341297251446521748467917483024052514515168405272, 735517778938137569312290974682594502893043496935834966048105029030336810544, 1471035557876275138624581949365189005786086993871669932096210058060673621088, 2942071115752550277249163898730378011572173987743339864192420116121347242216, 5884142231505100554498327797460756023144347975486679728384840232242694484649, 11768284463010201108996655594921512046288695950973359456769680464485388969041, 23536568926020402217993311189843024092577391901946718913539360928970777938082, 47073137852040804435986622379686048185154783803893437827078721857941555876305, 94146275704081608871973244759372096370309567607786875654157443715883111752579, 188292551408163217743946489518744192740619135215573751308314887431766223505070, 376585102816326435487892979037488385481238270431147502616629774863532447010118, 753170205632652870975785958074976770962476540862295005233259549727064894020344, 1506340411265305741951571916149953541924953081724590010466519099454129788040580, 3012680822530611483903143832299907083849906163449180020933038198908259576081160, 6025361645061222967806287664599814167699812326898360041866076397816519152162452, 12050723290122445935612575329199628335399624653796720083732152795633038304324883, 24101446580244891871225150658399256670799249307593440167464305591266076608649853, 48202893160489783742450301316798513341598498615186880334928611182532153217299508, 96405786320979567484900602633597026683196997230373760669857222365064306434599262, 192811572641959134969801205267194053366393994460747521339714444730128612869198530, 385623145283918269939602410534388106732787988921495042679428889460257225738396863]

看这个output形状就知道是个经典的超递增背包，所以用最终sum倒着逐个减回来就行。

exp：

flag = ""
for i in range(len(c)):
    if(sum >= c[len(c)-i-1]):
        flag += "1"
        sum -= c[len(c)-i-1]
    else:
        flag += "0"
assert sum == 0

print(long_to_bytes(int(flag[1:][::-1],2)))


#DASCTF{you_kn0w_b@ckpack_Crypt0?}

1z_RSA

题目描述：

1
2
3

我们来到了提瓦特与现实世界的边界，我们怎么卡进去呢？

We've arrived at the boundary between Teyvat and the real world. How do we glitch inside?

题目：

from Crypto.Util.number import *
from sympy import *
import os
from secrets import flag

nbit =130
e = 3
l = getPrime(505)
m = bytes_to_long(flag + os.urandom(64))

assert len(flag) == 29

while True:
    p, q = getPrime(nbit), getPrime(nbit)
    PQ = int(str(p<<120)+str(q))
    QP = int(str(q<<120)+str(p))
    if isPrime(PQ) and isPrime(QP):
        break

n = PQ * QP
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))
N = PP * QQ
M = pow(m,1,l)
c = pow(m,e,N)

print('n =', n)
print('M =', M)
print('l =', l)
print('c =', c)

'''
n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923
'''

要解决题目就要获得N的分解，而N的因子PP、QQ其实是由PQ、QP唯一决定的，所以其实就是要获得n=PQ*QP的分解。

而PQ、QP这两个素数又是由两个素数p、q按如下方式生成的：

1 2	PQ = int(str(p<<120)+str(q)) QP = int(str(q<<120)+str(p))

自己测试一下，可以发现130bit的素数按十进制大概有39或40位数字，也就是说PQ和QP可以写成：

$PQ = 2^{120}10^{a}p+q \quad a\in\{39,40\}$ $QP = 2^{120}10^{b}q+p \quad b\in\{39,40\}$

所以乘起来就有：

$n = (2^{120}10^{a}p+q)(2^{120}10^{b}q+p)$

可以发现p、q完全算小量，所以乘起来二元copper就可以获得分解，之后常规解密就行了，由于不互素所以还要AMM或者有限域开根，最后crt一下。

exp：

from Crypto.Util.number import *
from sympy import nextprime
import itertools

def small_roots(f, bounds, m=1, d=None):
	if not d:
		d = f.degree()

	R = f.base_ring()
	N = R.cardinality()
	
	f /= f.coefficients().pop(0)
	f = f.change_ring(ZZ)

	G = Sequence([], f.parent())
	for i in range(m+1):
		base = N^(m-i) * f^i
		for shifts in itertools.product(range(d), repeat=f.nvariables()):
			g = base * prod(map(power, f.variables(), shifts))
			G.append(g)

	B, monomials = G.coefficients_monomials()
	monomials = vector(monomials)

	factors = [monomial(*bounds) for monomial in monomials]
	for i, factor in enumerate(factors):
		B.rescale_col(i, factor)

	B = B.dense_matrix().LLL()

	B = B.change_ring(QQ)
	for i, factor in enumerate(factors):
		B.rescale_col(i, 1/factor)

	H = Sequence([], f.parent().change_ring(QQ))
	for h in filter(None, B*monomials):
		H.append(h)
		I = H.ideal()
		if I.dimension() == -1:
			H.pop()
		elif I.dimension() == 0:
			roots = []
			for root in I.variety(ring=ZZ):
				root = tuple(R(root[var]) for var in f.variables())
				roots.append(root)
			return roots

	return []

nbit = 130
e = 3

n = 18339446336492672809908730785358232636383625709800392830207979464962269419140428722248172110017576390002616004691759163126532392634394976712779777822451878822759056304050545622761060245812934467784888422790178920804822224673755691
M = 36208281423355218604990190624029584747447986456188203264389519699277658026754156377638444926063784368328407938562964768329134840563331354924365667733322
l = 56911058350450672322326236658556745353275014753768458552003425206272938093282425278193278997347671093622024933189270932102361261551908054703317369295189
c = 720286366572443009268610917990845759123049408295363966717060100862857351750759651979922104897091176824666482923148635058966589592286465060161271579501861264957611980854954664798904862706450723639237791023808177615189976108231923

PR.<p,q> = PolynomialRing(Zmod(n))
f = ((2*p+1)*2^120*10^39+(2*q+1))*((2*q+1)*2^120*10^40+(2*p+1))
bounds = (2^(nbit-1),2^(nbit-1))
res = small_roots(f,bounds,m=2,d=3)
p,q = 2*int(res[0][1])+1,2*int(res[0][0])+1
print(p*q)
print(n % 10^79)
PQ = int(str(p<<120)+str(q))
QP = int(str(q<<120)+str(p))
PP = nextprime((PQ >> 190) * (QP & (2 ** 190 - 1)))
QQQ = nextprime((QP >> 190) * (PQ & (2 ** 190 - 1)))

mp = pow(c,inverse(3,PP-1),PP)
PR.<mq> = PolynomialRing(Zmod(QQQ))
f = mq^3 - c
res = f.roots()

for i in res:
	m = crt([int(i[0]),mp],[QQQ,PP])
	flag = long_to_bytes(int(m))
	if(b"DASCTF{" in flag):
		print(flag)


#DASCTF{Ar3_Y0u_Su93_Abt139??}

但是这都做完了，发现有一个信息其实根本没用上，就是：

1	M = pow(m,1,l)

相当于多给了个m模l的值，而由于加密指数仅仅为3，所以类似于明文低位泄露，可以写出：

$c = (lm_h + m_l)^3 \quad (mod\;N)$

所以得到N之后，预期应该也可以不AMM，直接copper可能就行了，或者就是用可以直接求逆的PP去和l做crt也行。总之信息给的很多。

found

题目描述：

1
2
3

你现在来到了提瓦特大陆，能不能发现宝藏呢？

You have now arrived on the continent of Teyvat. Can you discover any treasures?

题目：

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

bits = 1024
l = 138833858362699289505402947409766595473722379891580589518174731439613184249727659678966809301611194545239974736175752769503863392697421092435438747741790652435801956708356186578269272819715592752821497122516109657809748674185639254430403157877064556216401002688452227124543508128414591884297632663910714681207

assert isPrime(l)

def generate_prime(bits):
    return randprime(2**(bits-1), 2**bits)

def fun(data,y,n):
    return sum([data[i] * pow(y,i,n) for i in range(len(data))]) % n

def gen(x, y, z, w, n):
    data = [randint(n // 4, n) for _ in range(10)]
    leak1 = pow(x + pow(y, z, n), w, n)
    leak2 = fun(data, y, n)
    return data, leak1, leak2

def encrypt(l,m,n):
    mm = bin(m)[2:].zfill((m.bit_length() // 8 + 1) * 8)
    length = len(mm)
    c = []
    s = []
    for i in range(length):
        a = randint(1, n)
        s.append(pow(a, length, n))
    for j in range(length):
        c.append(pow(l,int(mm[j]),n) * s[j] % n)
    return c

p, q = [generate_prime(bits) for _ in range(2)]
r = generate_prime(bits // 4)
n = p ** 2 * q * r
e1 = generate_prime(128)
e2 = generate_prime(128)
phi1 = p * (p - 1) * (q - 1) * (r - 1)
phi2 = (p - 1) * (p - 2) * (q - 2) * (r - 2)
d1 = inverse(e1, phi1)
d2 = inverse(e2, phi2)

t = getRandomRange(n // 4, n)
data, leak1, leak2 = gen(r, t, e1, d1, n)
m = bytes_to_long(flag)
c = encrypt(l, m, n)

with open('output.txt','w') as f:
    f.write(f'n = {n}\n')
    f.write(f'e1 = {e1}\n')
    f.write(f'ed = {e2 * d2}\n')
    f.write(f'data = {data}\n')
    f.write(f'leak1 = {leak1}\n')
    f.write(f'leak2 = {leak2}\n')
    f.write(f'c = {c}')

输出太长了不放在这里。

这个题信息又多又杂，先直接上一个最简单的解密流程吧：

由于：
$e_2d_2 = 1+k\phi_2 = 1+k'(p-1)$
所以有：
$e_2d_2 - 1 = k'(p-1)$
所以就能利用费马小定理和gcd求出p。
求出p之后，直接看他最后的encrypt过程如下：
- 把m转化为二进制串，记长度为$t$
- 随机生成一个列表s，里面的元素均为$a^{t}$的形式
- 逐比特加密，若当前第i比特为0，则密文为$a_i^{t}$，否则为$la_i^t$，其中$l$是一个给定的数字
测一下可以发现$l$根本不是模p下的二次剩余，然而由于t是偶数，所以s中的元素都是二次剩余，所以逐比特判断一下是否为二次剩余就可以还原flag了。别的信息都用不到。

exp：

from Crypto.Util.number import *

'''
data
'''

####################################### part1 get p
p = GCD(pow(2,ed-1,n)-1,n)

####################################### part2 decrypt
flag = ""
for i in range(len(c)):
    if(pow(c[i],(p-1)//2,p) == 1):
        flag += "0"
    else:
        flag += "1"
print(long_to_bytes(int(flag,2)))


#DASCTF{c764ba09-b2aa-12ed-ab17-9408ad39ce84}

题目这样就解完了，接下来看看还能求解些什么东西。

对于gen函数，他给了以下信息：

$leak_1 = (r + t^{e_1})^{d_1} \quad(mod\; n)$ $leak_2 = \sum_{i=1}^{10}data_it^i \quad (mod\;n)$

其实这很像之前一道hardrsa：

Crypto趣题-RSA(一) | 糖醋小鸡块的blog (tangcuxiaojikuai.xyz)

思路也基本是相同的，对于第一个式子有：

$leak_1^{e_1} - r = t^{e_1} \quad(mod\;n)$

而对于第二个式子，可以看作是一个以t为根的多项式，求出他的伴随矩阵后乘e1次方，就得到以e1为根的多项式了。由于r较小，所以把上式代入就可以copper求出r，exp如下：

PR.<x> = PolynomialRing(Zmod(n))
f = -leak2
for i in range(len(data)):
    f += data[i]*x^i
f = f.monic()
H = companion_matrix(f.coefficients())
He = H^e1
fe = He.charpoly()
r = pow(leak1,e1,n) - x
ff = fe(r).monic()
res = ff.small_roots(X=2^256,beta=1,epsilon=0.03)
print(res)

然而，由于p是给定的，所以把上述两个式子直接放在模p下求根也可以直接得到r，就不需要copper了。所以说信息又给的很多。

EZshamir

题目：

import os
from random import getrandbits
from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag

class Shamir:
    def __init__(self, pbits, noise_bit, n, m):
        self.pbits = pbits
        self.noise_bit = noise_bit
        self.n = n
        self.m = m
        self.p = getPrime(pbits)
        P.<x> = PolynomialRing(Zmod(self.p))
        self.poly = P([bytes_to_long(sha256(os.urandom(32)).digest()) for i in range(self.n)])

    def sample(self):
        t = getrandbits(self.pbits)
        y = int(self.poly(t))
        noise = getrandbits(noise_bit)
        return (t, y | noise)

    def get_msg(self):
        res = []
        for i in range(self.m):
            res.append(self.sample())
        return res

pbits = 400
noise_bit = 32
n = 100
m = 75

shamir = Shamir(pbits, noise_bit, n, m)
coefficient = shamir.poly()
key = "".join([str(i) for i in list(coefficient)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
ct = aes.encrypt(pad(flag, 16))

with open("data.txt", "w") as f:
    f.write(str(shamir.p)+'\n')
    f.write(str(shamir.get_msg())+'\n')
    f.write(str(bytes_to_long(ct))+'\n')

输出依然很长，就不放在这里。

题目是一个带错误的shamir秘密分享，先生成一个长为100的多项式系数列表，然后给出75组点对，并且每个点对的函数值的低位会有32bit的error。

乍一看好像不太能做，因为本身要分享秘密需要100组点对才行，而这里只有75组，更不用说还有error。然而细看会发现他的多项式系数都是sha256生成的哈希值，而p是400bit，所以系数显得很小；而error又更小，只有32bit。记多项式系数为ai，每次输出点对为(xi,yi)，error为ei，可以抽象出如下的矩阵方程：

$\left(\begin{matrix} 1&x_1&x_1^2&\cdots&x_1^{99}\\ 1&x_2&x_2^2&\cdots&x_2^{99}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_{75}&x_{75}^2&...&x_{75}^{99} \end{matrix}\right) \left(\begin{matrix} a_1\\ a_2\\ \vdots\\ a_{100} \end{matrix}\right) + \left(\begin{matrix} e_1\\ e_2\\ \vdots\\ e_{75} \end{matrix}\right) = \left(\begin{matrix} y_1\\ y_2\\ \vdots\\ y_{75} \end{matrix}\right)$

也就是：

$x_{75\times100}A_{100\times1} + e_{75\times1} = y_{75\times1}$

所以其实也就是个LWE了，用我之前写过的primal attack1，并且稍微改一下对角矩阵的大小，就可以把系数规约出来了。格有接近两百维所以当然要flatter才行，大约需要30s。

exp：

from hashlib import sha256, md5
from Crypto.Util.number import *
from Crypto.Cipher import AES
from subprocess import check_output

def flatter(M):
    # compile https://github.com/keeganryan/flatter and put it in $PATH
    z = "[[" + "]\n[".join(" ".join(map(str, row)) for row in M) + "]]"
    ret = check_output(["flatter"], input=z.encode())
    from re import findall
    return matrix(M.nrows(), M.ncols(), map(int, findall(b"-?\\d+", ret)))

pbits = 400
noise_bit = 32
n = 100
m = 75
p = 1914861180127910915217161496032452354459288330404267938814385633318816795789745430689392291853522228462459760259540145551
msgs = [(871685718803663381427930478762339134295053004512609923589551466783266783810259304828550374243064535763376291757646963959, 202160546047966750331912360731430418240633973593625005229082586127891061162361922677243409978233971196981357156050665207), (880630661134451484589856936400581718913135314681369937077374828269467594291354487238721693384105758714624990294669591318, 1095968002726348118037606681187141462053336336722142181092378890939072246257043346524710197351420437134900753767241347071), (2201481802919131040050333908088433208558917203945919199978631826943299343536825970006258238556122903076523292840756434743, 692254736946777374134144410762495005358360246411034340533738679554417430991182506230475828234351704793913692448647675007), (1378304382181829689586748896745391077371970833336011385982116414924775680216930605930619270704824436444608781376558454118, 1349836972600983636760377380443471914884359770040030987799061599827409370783772298884084190105572886840534075250106753145), (1353153805805015283526548792279508930383121644895000056925297797888893262990508466655386951026647093911241738634749231794, 708640659789589986759360580045421230914410242138084549192350870784628479597574645622638880069506009868145944996982225278), (1060943952101159814075555130286870049673510249558382992676797709837360932812847335287824269141102612270742087176360534041, 1039246257482395034113137526078027968667726416005827851568387262127498749146041230779139405404483176650987996444622585854), (2424118466972165402210232064008571072995878364648534891594437945505312271409808703384482184386252162745547514610618028336, 635156696412302837761915637951567688860519995373738062624916498633145442364997312202584276482319362616731324143180341246), (1772241931859851196567261257895529032033057998867860001437142889635454121520207911859978309001300625929738493595845855555, 500604911497932506773931452024208499570885483407547558939058205116845746585850868300414311672651970998734159786902749117), (187044491746709666918227023301039735707457548611767420757592410489694090421689472337383722846260140189038198219461031942, 227360883946968296249705407270310276359769497016888615738491818601296225309783611129587894811655567646792586796017233916), (698522560244433302990615272949028179635002687309158390959480083880213377867539289895143372657572453749378003459093150970, 1438446488346299625609140434323525340139617346663444436909013102079035123226801253230191914228775608263694160574643826415), (1314293541818269470008262253418684239221368418527916534392752287558240541875482130114787897305513520252998018265836595136, 933106402921508526957532367623168847119197804766985507707958985877339350054085035066950570021869141193740290685053960123), (1501745172784237049923522578654390251325669575513607134910901665808936517556360097769749957840258117848678845196676974438, 1516777488301366348170721193695469080262430948767494893352311177358850775942249045078694319757619073073088994542922628861), (1718313250889012550002734353486104431289067168806022987862850465345813017177898627414672453244745977044381286178413506161, 506057417158279773145112367533063233326190899630436097648290976200406049591277922238049560242268646574334872382933403615), (2574114678492270903282456732270950593394194358462333441160509514501148947640703147403802718744307473847235179125898798831, 1503310774908591444184865449721473627976722270933784408676574059139777045024294387334806494605277115228299871854598791166), (1770243408559044970812149306040976785192946281881654467315187543403793080522851914844996680381886937167658398949087446193, 1099237075950355774454839935750271630613513947414691912497783029355832037700530351594087156234712938075324990262460261245), (2166086041023587382902739106621961372440200378327129977520031042444044378994128764308981213008281610274832831816068579582, 662709908868241192557028160616176772511764390044399310771390622778705044736473497185759270701465132475627229112002146287), (2170463762878343673691652149382892550249493539913487563393294153717628928418073705621516968910372026548584895576642432967, 1413676394542378061807394780263485269329077458637078447074464881203630348193024572124672013567573482444837133106653543455), (1129266289804637843248865446624604876222278055268049666382746600434990532837254822384883357227875808573227656504651891817, 1535832745242864345604750984721590856572422259228943440577864210008688452305222147646810543026576688303372824677842288383), (2306555154959167883502684934268021903550464872811594873384525370627065323932167910172723635326929186844444801386870524867, 574207014379682600904001842474004352741607105704886122985304177072984415266547565043126591318153332317051149516485422972), (1724617341290962542300349861015192124473593787607849187241871123866653776294891983393875816012660538610025134685453770248, 1037506311823536647118763707562050051146414393535410677631530307480219373475166677371198285257502421566885284344997084663), (202616766252415923229841624622749382197002736241072130496684863225861466295470440453433729087043063339640795866357221636, 1486069111757435527648291199412538135459418727823506381342991481853059317128849411787275828115963269643450637901851750359), (782072578333357184532047183424922628763983310554137973249125608272717772586145583974361061586170067251618252434433193104, 283757911494107775111019950316083145592345149507512192994272372101655062364071745340414019692327679359235776555825852415), (2197595167942118116042253773798345585826387963460510458606977372991191820486797272252095468231729659915814456157670560486, 955293934596965502510872570415413020132164928134045802395033751487848017887015144832326371969637236306696054523237785589), (1098157283702819563820742199423754909028104781243946454418867995181539307551856844793857199640783377355282394025101300655, 635111390180648841537968959615311456853925067622053148053038395898914597955860998732345527697104011201693008366561317143), (1539369283131984995745859995105101736066475537281347948822432206665809508754710210661232887491808392388057664234877214907, 1873336536033306125287332317304933459481487853852475402907316652085126765046749618993624553154025815108827029610442783458), (2105684701096534411811602939870350859970761398331640507345513836997797916059406457337165075287082983610738904681969289045, 1070056100602518593988818068846549889380286647944194826819905043161724050669042969316031968306712388470995120352413349630), (142489011778634823488933340993644406251365634143001554672065147110660487229716505211502368066478460823953952289740995290, 1600505031347134429197259601839106217157515935077383802359036680943190353630112460191899585397343290624969344500745894703), (554711031900068277207319195022074787064807351540056727585559478009641245829914129658355024028140622126230477378977389537, 65339521639683012798947456976243744037602872322070608133060186211835711806848370610017017866030009537787109068192454654), (532900849979395683891747931991929993723658239680866376615001124559008204600725833769158798743570050012188528983307982345, 334144016771241488303216672075523455061388505657739817526966708251875900758813513342313135616513439456734341083743369135), (869702918099306179247127839502723535611690279734139047798433105147760657329410795136726045654330604238870805984709621246, 1169351283105013313749641940783038490083938869389146122787264490618765187367135121126934960933658038044552677868393266925), (786239400981081690761967926939692614214352370457999126682279606306346828244856149092806342991454830115357428173569519111, 341229317116770102168944480795910149567176593419165900124153031167345358788428115442807890687039322892597408592425778007), (2064213065995911617919315029041029121543167107287437882288959061187785048503282055451690399898250479932109432366548223997, 865205430622864313641681018820800198136329954993789609121686669624009340125228193996720833574248608603224773986947432415), (1996571933560681341081972550429260163713030332385776633835663546385508374790580854691775408939051083454291050879529580125, 559622002964744852554436566542525646157533309978763685146044798881793139644019170010343656282702809565334484141114392471), (1665201866056279622733275067329071022333699015026928761307123522986743452132023670960400981020146860918570153444345681972, 1206659985279999461070238583934930315667638779868565409888110141662803190569415230894181412146290317311945493517622418483), (1515824630378748853880547205191400487565887686063520538971380532161078510669610334484477786016989319170924543667026641318, 154768510600010010017326698396207970330238438685198973674456030784650112353692986269413531937661879315225602124927708924), (2400640362993011976891348699605911902016988451462173893625476704482508356176787307014920885489349704332546642981698540069, 1121421906118323024216284095711804126345276955926784522370067713782427318851230923383318334457757167182928811853910539965), (914679394823164487648957492231711749917619119979512000391828434330805091270968219541264417579001916453063785209093025303, 374627069056072738750323688310128739794138886219071824099120374559973078400286337012659440934169856150484268780102828020), (1021972013999414078223981430633642397558044349935082594710388870307835007718638824792649139809042384573145837264785258692, 102093917357525962153933641992946656421204665316272197308632790969421027148825374536157392412871816080580115446708002591), (1090613002154339666672492884775405717313689831457406446112184992081112549743653583926163772335048052650217605191460964064, 1013686859153230698540678410867250429548404782986370285534810877495709441098450523218264937019132584108142305563714746606), (2161046501022327990933396497482765893753709560942237251106031463450880235879988355009303131242535391464106086265266338474, 1842825126623549349236000977359585068860414649531034170142594564984327572182360450517454690000097975914639809219290654045), (734600260267770729123110997283110745757092649194443870464263775523592639286156519663230810008655565992062564338915033184, 1439472390868656814802271856900227714476824912359664972147156053839098765837149646453806800388007932953080250670815772651), (881335900275714936417588963897633003585264162416587081468620588101288614371107988322661634495058217226298025521720126634, 1438060177355585280770231938473797663421441580729795412881287946986577092068342750409767988724102261013424113586148457982), (876173729780067336779925806297809473013555554668200124165269741312909223647316933287442159368855433236050789576297672813, 584722637090302053439384198012199760324880317678105782762720083676914628942486088928409942979389876557255132127516159991), (1733558429089397683359597663185076627234549140640918522337597781379981378009350733554208954192805660163725305958818509205, 1010477387678444338602582972843701290504497269295430761287923107029938822433731115008623372768060580369747062615441406973), (1758000758086776729345325124199287880198692107697670885448853730203070351345566212118269510767350031899984650531292511829, 1484408939224604508966101404659297622265311898991708197399154932571955375325130297122648740841893311564144118335134464767), (1804131890436486866363129670875272535127829613109307224638927349502815652920038318044827248066297349084047126682198723537, 205851561043462971495790984180238782403371191306463313748537952075031757233102533087892093246459879467418213080624418525), (115055233675952369353652759916228030654313474433562820828539341357745365094094469880187786426435712648771454584499932530, 1176080864489594177205517592453183512444290818765306305520846987245653463202230068116379056777589684194022156652500590286), (2328185963017050382404641363914321749130815400658884925780323745763587492366183441185791654864416499947607965414839983680, 1886972372164945427290729032551681924723044624295253696412030824048931146570915452349880650169939511030432165431905079162), (1187461847839408713851221476312312384869325749843380494840008651043567024911068726332857155522639869883501560564590472502, 14245981570273560431111454126826341091354415427387740559245555665941487543601004914128539171516718107049427670791071455), (1275402030469087379247637832029139314437943507754693234009807154397029994354617242802931983091961356790463942774885431413, 1244618585414033483912499539268357193993901084573974055024618656871349876744646123907837743332137138284077968028988239205), (434412507816189969843251866894800201497317336949194643079967243932448367734854234524383921690504689272627248814185361829, 1193224411748734492892063266412070819051994764468021617840046995194588804893634149301845035319723286201666783735434959871), (967206800413690215868425566102618623559678834432686964828977512828919721907280699739833113197470139412151190023683313494, 1808530961381834386234136376719035780314110457320233165055990056489953593025409242256807470925700807422319096558572795309), (313624779412398332754376720890766035026328871037358868168298423270666735999144035960122672900278781994670311217953770375, 1686899500506262775384473022726677756466624697749756704659992441285341042856582261569357914257097304916151170085370461887), (2503049409019801269651799221722260539204050296212337202096008034125758666888245353212657377647881087341258220743220151950, 1805670425703721038437117454438319230600703158318099419770216013430708468787297957979021344350598998116788430512286857710), (542793615526234040152647477936504636873290026979804505200706031754909176961382452267207291751054204331474258583862955704, 137413216840404664240606423528330611923289618863367088636432169005845572010429296034368451334357274658088690084213739519), (1278727765228747216000039330509641392475448645848420065175572576050796418025108532539983143839105111868933395201633094022, 23388499359309984016274969787898858204391606769507546898645785064534114465222342746534462082168690576567031618802237437), (1012848580192164395816758294581574397534987673377799482227399907475636722043236850766024023620412517564680586256857352143, 1905214326869438439368196073362306288481014496204443072620153943726399155969870686475260450389360494546627630953811148739), (14681804970662677021409260234892378252555735233958673970664432299644093318314837872915339633110893420712659256185701001, 1011761630527797621590321605066946971053085037922024159289431337005985850853467103097812975363878048453898707806902513147), (1285297724752785338545033366325253262303128927017049271006754406539647664563391436762226286574374768602309413720192759993, 1493631305230939817393915729396076315723258260416123252804505906893714637325280535095299471289740565654113670071232495263), (1936455326607738910358536004445045468685935298243245355139607465446389473389575731412354107347767379820812067955096505581, 17221509529814003689149745147239645298120184452011530064684368807629510922529681925724732647573630702864807669020485630), (1712173121206746224826777847167590088908487771935061508185448418705799456315866273530139739504675597716276421618856320329, 863258960233895711001625204805338525869459949675833484269384656157104193362371966225031203968537041681324265578127949567), (122947819386929089053369455928546401519366926955589935482151285368760894784571110782585692673158533373827447719944343791, 1029102739229804972707735760530574223266205866939373652705629746591419564062928935797957680207632040596245681227704817914), (2385767142510533504647214446664898369383090132453476416454822794037991187237960157132343084153289103535309857420295111775, 1761624877069474386824225334992881109136596455709107320013742630575693526591737171363464568721656277644139593399384668014), (812771942753829583712722765469520203663717266127958627830326203252222513862479475416772893289895236549766564327139922612, 1400551965978757484763340299740157171921224208542574495162921941233365483529203665206398541892811136907423472715818784767), (1730447421466464570286474725493766890793606044225883792125770759375672642470742177732074062181325776806752255986611978352, 1227172422842784980554449107675660327741994737748190415035709694965213848256121533465275911556767542681543052337917439991), (884876570094879628298320898305798783174822422253214800767481822053599408285668812621687108791956015225332329856833897849, 753204920370187659065626153785437381083012604855618525406022085513242388007754850086113679887120336586260993544726445815), (2423878693124084232298267862648738136330397292982760413012437397441533882471872339001090243864079240084356627531832647422, 77986001656302970387684242942282141405916785932070787943262406584312194694807333266164831908062494860407574874622803959), (1290185371498453630061135665764650237444736789468400436115999443209964260044045414036036267228562648112405016415084034369, 68976337771940690010768399948574523361633543589446521911372413501313976435844421496476544211566756895340409483041171429), (534185007935476498632058534030834014275044346188926848916387521022740118957225895686427252642167800163347935460364558055, 731879744398464762194277983635893240035937844142280555568092822946046633080006561051406094554262898470573348173297417945), (2009543648096147223331131572743756103868310430657031922289948135024763757031731292638042205835167380178315151642456024876, 864568612425196666545678285566636785636433247142630432401391420609479878443671268150141447157212173236963221732165810175), (1757088643325711453646774590651240485497713141719261877086100356614624931730830270746024611221269656481354818801893802862, 974732470392774737526017597270025996122553373618728789664042196211840392818797860303355085148223560919202565975591828989), (288236986926014229269042124754978817491981631142567735873084199780621570926784314358694003281689620128867232148908447783, 1677180488607905300411659606081989540342864981198203708964066014660249657102993313228752304204059137461689367948628457454), (2357100534536251965755486926312170142467175578829851375102247846264889085384519286073305902768874043332485938824401972401, 701015346799246873651989606339191939588270778423404768025441929439466616345395882534334734331126078737835606277756551038), (361601359553041584651624082197420503156194921051661310152767809536879950298413026398079782027847432778044471125267794148, 338870184820594722235914590766168929044789583242319904735556030852263040707796808350885054449714833051229949699390437343), (437493113470125074131702090577490292225129373521518638964839429915294209870286662477332241046314129156199317300178856910, 304951333972637627160342487320016313244618388459742922018615396895218523409067458512473044675590109759792913998170528746)]
ct = 14058554635665083618818231958810639805770645952778992611953881143316377164307777281092527452513347998950720853358361

########################################################### part1 construct
A= []
b = []
for i in range(m):
    temp = [msgs[i][0]^j % p for j in range(n)]
    A.append(temp)
    b.append(msgs[i][1])
A = Matrix(ZZ,A)
b = vector(ZZ,b)

########################################################### part2 LLL
#primal_attack1
def primal_attack1(A,b,m,n,p,esz):
    L = block_matrix(
        [
            [matrix.identity(m)*p,matrix.zero(m, n+1)],
            [(matrix(A).T).stack(-vector(b)).change_ring(ZZ),matrix.identity(n+1)],
        ]
    )
    print(L.dimensions())
    Q = diagonal_matrix([2^256//esz]*m + [1]*n + [2^256])
    L *= Q
    L = flatter(L)
    L /= Q
    for res in L:
        if(res[-1] == 1):
            s = vector(GF(p), res[-n-1:-1])
            return s
        elif(res[-1] == -1):
            s = -vector(GF(p), res[-n-1:-1])
            return s
        
res = primal_attack1(A,b,m,n,p,2^32)
print(res)

key = "".join([str(i) for i in list(res)[1:]])
key = md5(key.encode()).digest()
aes = AES.new(key = key, mode = AES.MODE_ECB)
flag = aes.decrypt(long_to_bytes(ct))
print(flag)


#DASCTF{3617af36-7869-6939-3a09-bb8038aea171}

DAS_DSA

题目描述：

1	Please input your key: 上上下下左右左右DDAAAADD YES!! Oh!!,This your DDSSAA of DDAASS

题目：

DDAASSSAA.py：


from Crypto.Util.number import *
import hashlib

b2l=lambda x:bytes_to_long(x)
l2b=lambda x:long_to_bytes(x)
def xor(A,B):
  return bytes([a ^ b for a, b in zip(A, B)])
class SimpleDSASigner:
    def __init__(self, p, q, g, x,KEY):
        self.p = p
        self.q = q
        self.g = g
        self.x = x
        self.y = pow(self.g, self.x, self.p)
        self.KEY=KEY
    def sign(self, message):
        h = int(hashlib.sha256(message).hexdigest(), 16)
        k = b2l(xor(message,self.KEY))
        r = pow(self.g, k, self.p) % self.q
        s = (inverse(k, self.q) * (h + self.x * r)) % self.q
        if r != 0 and s != 0:
            return (r, s)
    def verify(self, message, r, s):
        h = int(hashlib.sha256(message).hexdigest(), 16)
        w = inverse(s, self.q)
        u1 = (h * w) % self.q
        u2 = (r * w) % self.q
        v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
        return v == r
    def give_gift(self):
        return (self.p,self.q,self.g,self.y)

task.py：

import random
from DDAASSSAA import *
from Crypto.Util.Padding import pad
from flag import FLAG
ALPHABET = "DAS"
KEY_LENGTH = 32

def generate_random_string(length, chars):
    return ''.join(random.choice(chars) for _ in range(length))

def get_message(num_messages):
    return [generate_random_string(random.randint(20, 32), ALPHABET) for _ in range(num_messages)]

def get_key():
    return generate_random_string(KEY_LENGTH, ALPHABET).encode()

def get_strong_prime(kbits):
    while True:
        q = getPrime(kbits)
        p = q * 2 + 1
        if isPrime(p):
            return p, q

def write_to_file(filename, data, rwx="w"):
    with open(filename, rwx) as file:
        for item in data:
            file.write(f"{item}\n")

if __name__ == "__main__":
    num_messages = 2024 // 65
    messages = get_message(num_messages)
    p, q = get_strong_prime(256)
    x = random.randrange(q)
    key = get_key()

    signer = SimpleDSASigner(p, q, 2, x, key)
    write_to_file("GIFT.txt", messages)
    signatures = [signer.sign(pad(msg.encode(), 32)) for msg in messages]
    write_to_file("enc.txt", map(str, signatures))
    write_to_file("enc.txt", [str(signer.give_gift())],"a")

    assert FLAG==b"DASCTF{"+key+b"}"

GIFT.txt：

SDSSDASSAAASSDADSASADASSSSADDS
SADADDAASSAASDSAAAAADS
SSASDDDSSSSDDSDAAAAAASAASDSA
SASSDSDSSSDSSDSDASADDA
SDDAAASASADDAADDSSSSDASAASADSA
AASADASADDSDDASADSAS
DASDDDDAASADDASADAAAAAADS
DSAAAASASDDDDDDSSASDADSASDDA
ADSSSSAADDSDDDADAADD
ASDDSADAASSASSDSDDSSD
SASSDDAASDDSADSDSSDAASSAD
DADSDAASAADDAAASASSSA
DADDADSSDADAADSSADDADDDSSDAS
AAASDSSDSAASDADDSADSDA
ASDASSDSDDADADSDSDDDDADSSAADAS
SDSASDADDASDASSDSAAASSASSDADA
AADDSSDSDADSASDDSASSDDD
SAADASAADAASDDDSASSDAASAAAS
SSDDADSAADSDSSADSADSAASASDSAS
DSDDAAASDDDSAASSDDDAASADSS
SASSAAAAAAADSDASSDASSDAS
DDDASAASDAADSSSASAAAADSDD
SASADSSSAADDASADDDADD
ASDDDDSDDSSSAASASDSSDDASA
DSAASDSDAADAAAAASADSDDDDAAA
ADSDADDDASASDSDADSADADDSASSSD
ADADDASSDSDASADDSADSD
SASAASDSDDASADASSSDSAAA
SASDDADSSDASDDSSDSDA
ADAASDSSDSDASSASADDSDDASAS
AADADDSAADDDSASADASSDAADADAA

enc.txt：

(59254487398967388114905667045028363843329923626238494813205814542210325221866, 38134152657262330507433713437784426184950965354807113354631630191330303144120)
(7272091585909282735283006759301331954064261183899338079418296410637263888770, 25499964678151126566605578540840513489434638253159604087981425065951344757164)
(6899645492048427857621143178962093646174799398991863666101058693217698732368, 9791582686238213337967141368906212036310014918808878260483336268832064128819)
(25004120896291255053237639070744331951278481119827357255754648579794346195560, 141512006531073436448016797005260994098008785866923890662245540709534244927)
(2970680424634969125510981613739745658897845410407912521400879068659540408508, 21793011307831199247000930716490000926029175766326909085969585420590222327264)
(54566000630497640561512172245143554745650114820675965968691149808463168361994, 14349862994826483344159692458388566295460798903541941504424537018216650283613)
(75159685495692974866291952764676724718763580667689472941977359299782008334398, 70458140884809949567915541063312538538372757595177423386408938073672211639375)
(20041025052466338500977838626769109456575569706600589389016534358968746705758, 65530083011107720400920780939345704754954869671333734672594688826098321351660)
(70127192435034402135747706941502224672808592757766109942714487474501491910214, 57063474646503909216126596725677068514339517777473453937098665282959018241139)
(9691674719110233709152049443866537766465800386755314400120771762265195237696, 62093763551744197212031574855244002702924782008725363963219173846480120194830)
(71705536377844454384479609516094364197930343317149881589774662842233960882414, 77374603032347186343803094100249733360600621594214414598796066240713702791608)
(52879693221782582945807231749976747516107564896599455986464226581743117039645, 1344584960351311598238142429846629993914377848692708811135221930719773821079)
(77382790022991362370508965243223326049308313776687214599186184000848696471646, 43641233828500431963081402892838426285406919342406723474664571883294369141394)
(56346141869522955969887972614456267251604757060687228073793419107933969328162, 76285674574149814839616688665569434237657824816977670694242559140508233840268)
(13673786393914569132256858604647869957632869873889606981549833789272316263013, 55327829510120473782794486945583818434703312785066895788282945944551470490709)
(64767740468987944636292946852714160626094908713011502873333251460983428727987, 13259490361346409766866273875042192439139048727072955549892484859673179719539)
(3957421961183318932163297455146838208380750250268324980567615749312524020603, 26882140137481455957383933013829466811327529673163422516945649296787438630196)
(26427922029900012253901950242265848521558605010629901777129266992870754082725, 69951840114040217998552588969628162605092507207522992695398095063314527794456)
(41377529326816743042387061355650636824586430044255853849728865473372840135697, 11219359019456290145545276763003725218855047474525360923001515509608652449000)
(25716607607446503241765016815241812755718791371526314953930748513731536667770, 28453782213087434330094261632474010077787574243224303728751260500450723227337)
(19800391798756020076641438144957219387739406397111495660920822320302304854123, 45451686690348328576376896082606976500453603983712180502700202971927238065259)
(38726290839677684687529233274549282905118675478275260942535144771737271586397, 40829316203033016996956478373044348905634931325393076578307296318880401948880)
(39209612764454560795450300186392582769693156243512973558204034254768849812055, 1354495451811853700039180690705948597695565424847801455594169929311025313998)
(65513712517147774905818288938959930101260466094015953149923879872714745367445, 15372704507991354781967074099137226451034611060413049367266363154832614415805)
(15729001560566023616632342669016214191974988848807788455841465085832368458445, 16327134664007312833089147621817036851276111964898734022794700122827444854947)
(42181696175119369852613642818168055609726913997313538977450877772345284116500, 9844926061501886811803369928846120575402269452312877926396348651872911440254)
(66136301537002842836817588252827389434354772150463143258637074246966542574050, 40179237579762663098604891208246052072476264271372972425562554108399403298795)
(28759447425094984124057238672075080352158483766211322160596339820824930247130, 31809179023991813094371890170356817265600467849999331763205655801654108159032)
(46713611880672324334213026166944979498146683097425440783760089321619754080806, 23270114877894114090584274918755188867365261145736710892185678426446455871613)
(57079205189933243387798430767693634017842334556643904914267966016857671112460, 18247249527866143497935092319901700668290600772967638096649240924154901762810)
(10688647176294432598580110142909961685073598720504815121442568862023227643325, 54331697420125697460151875535555752680845260504979536685075170636565355173106)
(156169498993837300941969389078565637464689185713213578550979549862042014984607, 78084749496918650470984694539282818732344592856606789275489774931021007492303, 2, 59080272611010540206200716660225398487916425104605746321153704646003914371135)

题目给出了31条DSA签名，与一般的DSA相比，数据有以下特殊性：

每次的msg是长为20-32的由”DAS”三个字母组成的串，并且padding到长为32(pad方式是固定的，也就是所有padding均已知)
每次的k均是key与对应msg的异或
key也是”DAS”串，长为32

给了这么多组数据显然是要HNP的，关键就在于k并不小。然而由于对于每个k，msg已知，并且key取值集合很小，所以简单爆破下key的头几个字节，就可以看成已知高位的HNP做了。

exp：

from Crypto.Util.number import *
from Crypto.Util.Padding import pad
from itertools import product
import hashlib

sigs = [(59254487398967388114905667045028363843329923626238494813205814542210325221866, 38134152657262330507433713437784426184950965354807113354631630191330303144120),(7272091585909282735283006759301331954064261183899338079418296410637263888770, 25499964678151126566605578540840513489434638253159604087981425065951344757164),(6899645492048427857621143178962093646174799398991863666101058693217698732368, 9791582686238213337967141368906212036310014918808878260483336268832064128819),(25004120896291255053237639070744331951278481119827357255754648579794346195560, 141512006531073436448016797005260994098008785866923890662245540709534244927),(2970680424634969125510981613739745658897845410407912521400879068659540408508, 21793011307831199247000930716490000926029175766326909085969585420590222327264),(54566000630497640561512172245143554745650114820675965968691149808463168361994, 14349862994826483344159692458388566295460798903541941504424537018216650283613),(75159685495692974866291952764676724718763580667689472941977359299782008334398, 70458140884809949567915541063312538538372757595177423386408938073672211639375),(20041025052466338500977838626769109456575569706600589389016534358968746705758, 65530083011107720400920780939345704754954869671333734672594688826098321351660),(70127192435034402135747706941502224672808592757766109942714487474501491910214, 57063474646503909216126596725677068514339517777473453937098665282959018241139),(9691674719110233709152049443866537766465800386755314400120771762265195237696, 62093763551744197212031574855244002702924782008725363963219173846480120194830),(71705536377844454384479609516094364197930343317149881589774662842233960882414, 77374603032347186343803094100249733360600621594214414598796066240713702791608),(52879693221782582945807231749976747516107564896599455986464226581743117039645, 1344584960351311598238142429846629993914377848692708811135221930719773821079),(77382790022991362370508965243223326049308313776687214599186184000848696471646, 43641233828500431963081402892838426285406919342406723474664571883294369141394),(56346141869522955969887972614456267251604757060687228073793419107933969328162, 76285674574149814839616688665569434237657824816977670694242559140508233840268),(13673786393914569132256858604647869957632869873889606981549833789272316263013, 55327829510120473782794486945583818434703312785066895788282945944551470490709),(64767740468987944636292946852714160626094908713011502873333251460983428727987, 13259490361346409766866273875042192439139048727072955549892484859673179719539),(3957421961183318932163297455146838208380750250268324980567615749312524020603, 26882140137481455957383933013829466811327529673163422516945649296787438630196),(26427922029900012253901950242265848521558605010629901777129266992870754082725, 69951840114040217998552588969628162605092507207522992695398095063314527794456),(41377529326816743042387061355650636824586430044255853849728865473372840135697, 11219359019456290145545276763003725218855047474525360923001515509608652449000),(25716607607446503241765016815241812755718791371526314953930748513731536667770, 28453782213087434330094261632474010077787574243224303728751260500450723227337),(19800391798756020076641438144957219387739406397111495660920822320302304854123, 45451686690348328576376896082606976500453603983712180502700202971927238065259),(38726290839677684687529233274549282905118675478275260942535144771737271586397, 40829316203033016996956478373044348905634931325393076578307296318880401948880),(39209612764454560795450300186392582769693156243512973558204034254768849812055, 1354495451811853700039180690705948597695565424847801455594169929311025313998),(65513712517147774905818288938959930101260466094015953149923879872714745367445, 15372704507991354781967074099137226451034611060413049367266363154832614415805),(15729001560566023616632342669016214191974988848807788455841465085832368458445, 16327134664007312833089147621817036851276111964898734022794700122827444854947),(42181696175119369852613642818168055609726913997313538977450877772345284116500, 9844926061501886811803369928846120575402269452312877926396348651872911440254),(66136301537002842836817588252827389434354772150463143258637074246966542574050, 40179237579762663098604891208246052072476264271372972425562554108399403298795),(28759447425094984124057238672075080352158483766211322160596339820824930247130, 31809179023991813094371890170356817265600467849999331763205655801654108159032),(46713611880672324334213026166944979498146683097425440783760089321619754080806, 23270114877894114090584274918755188867365261145736710892185678426446455871613),(57079205189933243387798430767693634017842334556643904914267966016857671112460, 18247249527866143497935092319901700668290600772967638096649240924154901762810),(10688647176294432598580110142909961685073598720504815121442568862023227643325, 54331697420125697460151875535555752680845260504979536685075170636565355173106)]
p,q,g,y = (156169498993837300941969389078565637464689185713213578550979549862042014984607, 78084749496918650470984694539282818732344592856606789275489774931021007492303, 2, 59080272611010540206200716660225398487916425104605746321153704646003914371135)
msgs = ["SDSSDASSAAASSDADSASADASSSSADDS","SADADDAASSAASDSAAAAADS","SSASDDDSSSSDDSDAAAAAASAASDSA","SASSDSDSSSDSSDSDASADDA","SDDAAASASADDAADDSSSSDASAASADSA","AASADASADDSDDASADSAS","DASDDDDAASADDASADAAAAAADS","DSAAAASASDDDDDDSSASDADSASDDA","ADSSSSAADDSDDDADAADD","ASDDSADAASSASSDSDDSSD","SASSDDAASDDSADSDSSDAASSAD","DADSDAASAADDAAASASSSA","DADDADSSDADAADSSADDADDDSSDAS","AAASDSSDSAASDADDSADSDA","ASDASSDSDDADADSDSDDDDADSSAADAS","SDSASDADDASDASSDSAAASSASSDADA","AADDSSDSDADSASDDSASSDDD","SAADASAADAASDDDSASSDAASAAAS","SSDDADSAADSDSSADSADSAASASDSAS","DSDDAAASDDDSAASSDDDAASADSS","SASSAAAAAAADSDASSDASSDAS","DDDASAASDAADSSSASAAAADSDD","SASADSSSAADDASADDDADD","ASDDDDSDDSSSAASASDSSDDASA","DSAASDSDAADAAAAASADSDDDDAAA","ADSDADDDASASDSDADSADADDSASSSD","ADADDASSDSDASADDSADSD","SASAASDSDDASADASSSDSAAA","SASDDADSSDASDDSSDSDA","ADAASDSSDSDASSASADDSDDASAS","AADADDSAADDDSASADASSDAADADAA"]


for keybytes in product("DAS",repeat=3):
    keyh = "".join(keybytes).encode()
    nums = len(sigs)
    L = matrix(ZZ,nums+1+nums,nums+1+nums)
    r0,s0 = sigs[0]
    h0 = int(hashlib.sha256(pad(msgs[0].encode(),32)).hexdigest(), 16)
    k0h = (bytes_to_long(msgs[0][:3].encode()) ^^ bytes_to_long(keyh)) * 256^29
    for i in range(1,nums):
        ri,si = sigs[i]
        hi = int(hashlib.sha256(pad(msgs[i].encode(),32)).hexdigest(), 16)
        kih = (bytes_to_long(msgs[i][:3].encode()) ^^ bytes_to_long(keyh)) * 256^29

        ci = hi*r0 - h0*ri + s0*k0h*ri - si*kih*r0
        L[i,i] = 1
        L[i, nums+i] = r0*si % q
        L[0, nums+i] = ri*s0 % q
        L[nums,nums+i] = ci % q
    for i in range(1,nums+1):
        L[-i,-i] = q
    L[nums,nums] = 256^29
    L[:,-nums:] *= q
    L[0,0] = 1

    res = L.LLL()[0]
    
    k0l = abs(res[0])
    k0 = k0h + k0l
    key = long_to_bytes(k0 ^^ bytes_to_long(pad(msgs[0].encode(),32)))
    if(all(ii in b"DAS" for ii in key)):
        print(key)
        break


#DASCTF{AADDAASAAASSSASSDSSASSDDDSDAAASS}