Redpwn CTF

I really enjoyed this CTF, only focused on the crypto, but had a good time and learnt a lot. Enough to bother doing this writeup at least.

This is my first write-up I’ve done after becoming part of cr0wn. The challenges written up below are the ones I focused on, but they were solved as a team. Thanks especially to Holocircuit, Hrpr, Hyperreality, V01d who helped me understand how to actually do any of this.

Challenge	Points
Seekrypt	495
Speedy Signatures	496
Jeopardy	499

Seekrypt

Secrets encrypted.

Challenge

#!/usr/bin/env python3

from Crypto.Util.number import *
import random

flag = open('flag.txt','rb').read()
assert len(flag) < 100

def gen(bits):
	while True:
		alpha = getPrime(bits)
		beta = getPrime(bits)
		mod = alpha*beta
		x = random.randint(1, mod)
		y = alpha^(bytes_to_long(flag[len(flag)//2:])<<0x1f0)

		if pow(beta**2*x,(alpha-1)//2,alpha) + pow(alpha**2*x,(beta-1)//2,beta) == alpha+beta-2:
		    break
	return (x,y), mod

def encrypt(m,p,k):
	m = bin(bytes_to_long(m))[2:]
	x,a = p
	c = []

	for b in m:
		while True:
			y = random.randint(1,k)
			if GCD(y,k) == 1:
				c.append((x**int(b)*y**2)%k)
				break
	return c

a,b = gen(1024)
encrypted = encrypt(flag[:len(flag)//2],a,b)
print(encrypted, a[1], b)

TL;DR

We are given an integer y which shares it MSB and LSB with an unknown prime
Using a Coppersmith attack, we can recover the prime alpha from the known bits
One half of the flag from y^alpha
The second half of the flag is recovered bit by bit from encrypted knowing that when e is a QR for alpha, the flag bit is 0, and 1 otherwise.

Solution

This challenge has the flag cut in half and hidden with two different puzzles. We see that the second half of the flag is used to create the integer y which is given as output. Although there’s a lot more going on in the challenge, we can immediately find the second half of the flag from the following data:

flag = open('flag.txt','rb').read()
assert len(flag) < 100
alpha = getPrime(bits)
beta = getPrime(bits)
mod = alpha*beta
y = alpha^(bytes_to_long(flag[len(flag)//2:])<<0x1f0)

We understand mod = alpha * beta = N as a composite of two large primes and so we should be thinking about this as an RSA-like challenge. The first thing we notice is that flag has at most 100 bytes, and so has a maximum bit length of 800. Cutting that in half, we have the maximum of 400 bits for bytes_to_long(flag[len(flag)//2:]). This quantity is then bit-shifted by 0x1f0 = 496, such that the integer bytes_to_long(flag[len(flag)//2:])<<0x1f0 will have 0 as the bottom most 496 bits, and will have a maximum bit-length of 400 + 496 = 896

We now know that a 1024 bit prime is XORd with a (at most) 896 bit flag-fragment with 496 trailing zeros. This means from the given y = alpha^flag_half we know that the bottom 496 bits and the top 1024 - 896 will be the same as the bits of alpha.

From this, we can apply a Coppersmith attack on alpha to recover it from the known bits. To use small_roots() we need to write alpha as a polynomial, we can do this with

alpha = MSB + x*(1 << 498) + LSB 

For some unknown x, and known bits MSB, LSB, which we can calculate

max_flag = 400
lower_mask = 496
known_upper = (1024 - max_flag - lower_mask)
upper_mask = (1024 - known_upper)
known_bits = lower_mask+known_upper

MSB = y & (((1 << upper_mask) - 1) << upper_mask)
LSB = y & ((1 << lower_mask) - 1)

Finally, to use small_roots, we want to rewrite this function such that x has no multiplicative factor, which we do by finding the inverse of (1 << 496) mod N.

PR.<x> = PolynomialRing(Zmod(N))

r = 1 << (lower_mask)
ir = inverse_mod(r, N)

f = x + (MSB + LSB) * ir
roots = f.small_roots(X=2^(1024 - known_bits), beta=0.45, epsilon=1/64)
if roots:
    root = int(roots[0])
    kalpha = root + (msb_part + lsb_part) * ir
    alpha = gcd(N, kalpha)
    assert alpha != 1, "Fail"
    assert alpha != N, "Fail"
    print(alpha)

The output of small_roots gives us the value for x, which we can then use to reconstruct alpha by simply performing alpha^y.

The second half of the flag is much much easier. We see that in the generation, a random integer x is found such that

pow(beta**2*x,(alpha-1)//2,alpha) + pow(alpha**2*x,(beta-1)//2,beta) == alpha+beta-2

This looks long and complicated, but it’s actually pretty simple. The terms on the left hand side are in the form: pow(p, q-1, q) * pow(x,(q-1)//2,q) for primes {p,q}. From Fermat’s little theorem, we know that pow(q, p-1, p) = 1, and pow(x,(p-1)//2,p) calculates the Legendre symbol for x. The values for pow(x,(p-1)//2,p) take values in {0,1,-1} mod p and so we see the equation simplifies to

pow(x,(alpha-1)//2,alpha) + pow(x,(beta-1)//2,beta) == alpha+beta-2

Which is only satisfied when x is a non quadratic residue (NQR) for both alpha and beta, i.e., pow(x,(p-1)//2,p) = -1 = p - 1 mod p for both primes alpha, beta.

So why is it important that x is a non quadratic residue? We see that the list encrypted is populated by looking at each bit of the flag fragment

def encrypt(m,p,N):
	m = bin(bytes_to_long(m))[2:]
	x,y = p
	c = []

	for b in m:
		while True:
			y = random.randint(1,N)
			if GCD(y,k) == 1:
				c.append((x**int(b)*y**2)%N)
				break
	return c

When the bit of the flag is 0, we see we append y**2 mod N, otherwise we append x*y**2 mod N. As a NQR*QR is always a NQR, we see that when e is a QR of alpha or beta, the flag bit is 0, else it is 1. Hence, given the list encrypted and the prime alpha from above, we calculate it’s Legendre symbol, and build the binary of the message element by element in the list.

Note: We could not have used N to solve this with the Jacobi symbold (e/N). The reason being that as x is a NQR for both {alpha,beta} the Jacobi symbol of (e / N) = (e/alpha)*(e/beta) will always be 1. (The two options being 1*1 mod N or -1*-1 mod N).

The solution is quick to write up using the inbuilt kroneckerfunction from sage, and looks like:

bin_flag = ''
for e in encrypted:
	if kronecker(e,alpha) == 1:
		bin_flag += '0'
	else:
		bin_flag += '1'

flag_first = long_to_bytes(int(bin_flag,2)).decode()

Implementation

Putting this all into one script, we grab the flag. I really enjoyed this puzzle and liked how each side of the challenge was realated to each other. Thanks Tux!

from Crypto.Util.number import *

# =============================================
# Challenge Data
# =============================================

encrypted = [8275388885893443678512608174583957947590309348942674029219139766033877421235161075918724281644541406737426325546718855424922421027456863273458919998545467221054722513118900731853582010191616529523149239211823326097059481394982405216805736026843496287510870984960606881599659029681463533442028850871083557245708431081611576195650081295754646614223075146244172640035745595201096575799953106958958823961745347809868725990094382564782459573369267084258180629996951381010335197918437224707631804268793231007408577148700601701733125925778103081617704618150464316944867015215136115148852858427081632945440226864874485969036, 15024296399248205807122283689218566390496831326714396409792698800299803699301917950571943978689203513033584150094505457016262896601569472975694249735868927545747376155035355172679069869391576487683339945053025561973538233598962491053616062448590875865853120541090533979077586759609748116789893243566792470265647394997623728211496444114524716174538826025238226744167882966331979570971147974439013520123807853304141074922819254390573278963951028965333115123709521490574568657424853506100358492167003754085320874172675844872523407009636278408648249022482033283263545795955048395340172016592888042786341560412169364360001, 8306804146139841703662296481670028512569861001982166156300978867964732343666844421908720481508208344128833750429002100096384052015432491831892049736734497300228735845740855915814234072220578188540365762661298990446887696869442265423101051767761814869830227497381321288755842752400643084896381346770315602771712252950207458333740221122576793634691535640996291946630387371059710336481841029337199092184199195481031420940512259368428183199169604313686269963008566029405931099768575763578093273177788903942347613920927708476120538300169317081584387486689950862668362006780346364210752321874739147678128956856905307430939, 9090926834832880131039466112389521759835027092102666051830975522775416131941390663603517122663639030241606461726928803519872080716380468494566458111754697844347834330110848437904571565293442668818757561252515736911844854788968098131116050728406756552916538064387685819180609776930078066840543172090378828357305032923534421583824825498146736224877546038077507027963258714149451501988469802610847930077560203513625718011204415608918856306514943906502065352408657406521500840695610237528570390850631051297301958628398021610281666561743392425150858199215990245235295138526825586977098559233597568287319243164987238349396, 10526789517277012439437477478714936461723275233079469631554614785653564207198044048929502315168773360705453770844386240881946111126846839174151177062492583563520701673511065729492968109502375092733986202426882625918910004477282670061892964406000653395900311729160009502037803343946006228979422398747388473288813597837921732768366801583756444889333300852297214868082499035054987339851967907090518876310425359250852198141165625500908066587940559435100607106532015981542704619533823939076229330235810171674557802079539863155524561515389817189885635848380361783695990224919666705106139855484254131956974093838150059627236, 9003753733613904486287458171339728086811199429996510961739387618312464105866856434273809012724471190111990704832234029121866642971810167675626855816956117520083517665771956881566340780821231541293176778611919702977766091857788798237265822668841618777558403360079306181115507146118237268401892952346082420409549162066462494546747598186867064502018101728457590400800594297072899646568026777506515853955050270441919182744002186040048976480858578894267458182096893848190609301499454615236154959261033187197098254571487727266947262729259719995265793914875270755301423038377698368020094207076171948172861958762760313218882, 10068658465473196270532475081894763591388192479211118027075487006954776823815932905382212629741136410019740441174914532976962441769960639588585947341379281525535404431111630135876546483887325907794071134248951814972629532764951869976271149237195543275466887093329843083399333768459948777790197819519649472898923114672624544076972927816523704276700807722016766315255036268147235529713638221779340326869921517142718033469669512937584217738178557790175375234407553853715689690070913626886156078712548648762981345905651060689958956808012506429003000317965674253524689184998783775751070497391445507519385786969701312249770, 8214810102194933594308069870478868225120076730504905518089087491973828409772738094104948640593886231020082757238243088298703760897031833051384729979196236196281037948707784493651795698484761341791837718155899264459216789782672100087596860897016195663248920660881014928850728908469518483938282453644668029685293765059050840727012393781023421906701085610700861703691833116468441036373319294213842117029540254803688164909913909868344334009471581518128153693297667410025638408608151514105372254633557289818450411361991475433531918919481137733164420298475716965179160550406340764267103292868867371591070606766226368312384, 10563384197118850441900193742522804083811132573837116217421570161888194408556070812875963319385759644134349695164901373327564658061652956314523574524858331080588808598125699052287605106201714043807817428043840087002938353845272396786298464072596481608009560488803633732261103163680918048927214992238818695123297980261564892408997021970610477765905671859944084662751303295438306158980334425975416649676628397645032798025850867299637062506376544547273701019783357763493914629835912448221445020936247842452706097884936538343691715463345421246864867121307125256476296245978184944842618441074671950346363986928642867431529, 3713782353555722602362010136405655520634663369580450853233803101083194227028982815581979442401966342688910148940472608845574797906630957771315963051052224920239010840042783700038909407468294955189724340424070183668085470878889818401857555483532483861001531382206901756791757661119914172473009261351815830944550751476990919930639905217202021106029596949501526991563758005356530120805564122955887170644001082992726258118351274254891995600317931435092579918036765780973708229340569281331041507397034175054167104124384944567981951563808716346233032325527604868569039009789632404139834354000494960494166920340102966477652, 12040023514607804225177335042780297822193547746732553466519151038912881078719897874792464408208347411501836057564926672269108734506545012430732069572960021261596112708026997683925081006646145366329389463991922779921675241812950844045889879479488609091969504070048031810239386688020394190896052330570608055098639243235625010235286185137892703432034792607936780969312252579917965350047449736938149753284853170574599762416700505075564239889486104402932263705341756606353866498729802615481414418542642085785813871503187709201327033479742930293511274076842779764083521469523134380202417566360604214150314597538775733094449, 4182704370322682566151967954208044093122433899611179433372773109642053644911092443070790653127271118424079480842674550632253217724454658947151418225883350873513860635680863150321440789480536414299571955505917769386201884467374326169106654392650118369610231355474229397414600973327860604128674774689646879819297819873514098852460160506512637179400640473917613979187172950733644503446613824474695557201475542639258478377647353778368527904475448263999287059425823002967619091654007184437307506239911395390724423421418929014688134975910290525054222919349601960265551396389808438794942485179059420646373328592562110875935, 4508157810377775057054934788581176681995962182195041651328738999986592464287575600715684275536558106039740714013972015497525136854128359016735231728104700742126995515000462057819202258786397098323015304576420290548560985846247230914302207611237825230281512357301333861456434604002941370568431718438304397993106014901561660714217778995969676367227729922234937595718008538102109056077307406903861612355089521471710135108714155082046775442728609020663950462867181860090595860127540827167103662236832592398100364230583869427792285490949436524598831956240220240907443660968456011020043632159227448218779862179238966321095, 11833836686794762493389692187087510136787100711221775614702238798372740339365015352106794720795072164791096760868835081265903098750755678972870578961427917570042854775096463138203780630379944995116852385085676807336079105458262604724150544983983680327979969572509186605523570417314442028748997757117402496428024597221123274971781806538907058582799105877279753527712077067817158080698721705008083382019042167248303815089366448983787084961368664566971502245945613482720039366747490938213784461659886532030988465916568032678500580388199557355827198904887485892236318494737576705141932803203753013278803086355315612551183, 9390095431026387834907673966762863332167841318149807124747496464189586038816758837037255434612736962103622044518634284148626919043575987992536043474495998254021043120187146765915745813716554874074483388444121676892472209976591010742020191195424033231885804546149263187827427242295079134513915454452479621230233448045464822891387804481796809579986819236273615909669010488048353973130154601370106243945659106657093087292318425982282198150305988679273988227357180313181953499890685971493534150284110802400195255863139638968663821481370007171302051388006212073511310495825495704602374984642735302764219143673669730559603, 7728868260097165258325512162962631682123733861487313442607852797918905627048797803508624254041009454363876137239781888812824636850880843157737058756183279779491022770077253568903973764963779014960229687098468556201912722007789009072431170773705177867920619390026701419087738421459966376817190718658917479912717869359536509675804300435230181896693936625733588808268139275251298351830392077411953476646681813541761652875492379859976230746747161296547953368828928660878504881275200549777863318450589479881637575104571789854005973284291393590410698338671978623530380813871981902958922137381094638485707719414917357009187, 10189927468040444993092586238703188214739132641516794090800041086364416360111257273753798484510942035289590486455984400350174593296678264236395189494858329795895824316008784030499984626523776787057050159081960248647967212717459484544082171685517415308767238574997212899452419105756096094543327981607204104137165771088778934801800642833430734491860524967876506229910351582714530753726270826171331426795703936458982046007145496201419210940368101786905862729003582892547000086022063991084745656657098091868557059922873137544400480190674901990237743439890808644083437587231116109855979440652220445592237956414058775070151, 8236255615288216737233342137062975563981512400448231144119013745026457396491150203671046550780723594554772587640757706132817343585912947669427757618987404207970871563791693921376286756061916676013021114894910850869347773818111958270870400028553657835178730330677854701702485060066578016912933205664230906064207875063139449929940796392586248219708958813075524811726954594642540262483443852595011554617713244371526401374774976888324294565456082067042857554516785188551315632003184886037774810362890645748324339409532729015116181993006076770619610663295692762727233056760800856291905688633850601016380834674290593033814, 3473198504170475545876730971456469563763342907454567276943754514011700006770395061621347422934046856292986491200899333031919410153559760169281801096803341507210554097181790112581399892174192565302155827890588668181693598484813112002176762588839108274393949813482983180263169611985281056897218601236733471927817801394248631621953026748465468104208319575191434559851824560567244766740867270643643080329496143421079763142847120271215457358260755841821297601612337573428415203026913617528529859990276538451041158949438356428116331450305732069080800157660087548860430662038190305327250449208144766777008500039860721229660, 5610735858540692651784723977717771076003573144440467912274200237699776316290955512277741145007783383494320363708439910220931439860424060681363730189347716172850312120665137811299217485507087730501693529595570764350491687116062496296792844505055171586439254883975162728236113520266068839032253295422517685040097229274479342431866261785603890137662762163978517720761085891749977330710053394647570278885227415573067135591893761353822036939946408487025978400577747834622220826463045374395813113748982087467257142559238532190393437414671349064393074880119291229404056767579678618604180524565209174089839044434714561944694, 11176076667488645406745652327171917716446417194575716127411164810986517749107802972937418295978040643389940316752610061136434837719599771298836271964842150829484308426927316298802698366195957896538751503612661852457519898398952483047063352436661213676754892680526775857714084006780297348656740092391036307237929318149318396079558263637905063980697091331180315812288287348814120865679219865801004920067264189322794849766132529995025233093768306677382369405826446770553217688021378597625391658554538197947552266599558574554006769124515615515197000639178644721144171154739336697234085766408323442588032184354448644204848, 11416572686491513123379507005215658875765086145522702191611409740738413742316073504544727674717006103070319445753081372530122925855788428643277346531956690560245411373184657786474084602065926793508020749128633339606862438661806372871784157187026048159182536921893628653939071350500128621520235865165493259329408598230549646504962479678459688109815966407672512249987851235673900480550554799532225350775159747820557497354188169949945626518394659729549200931136321198050224268435015499665343593919375884905049126924847184250423358509353981718421897251262850628542683327743883697937074219890770588170420880115512101564762, 10523724910208933464812991923568395076722472984209303629018412833194777915564863483835100760190427427880962824670722932391550801913321021076390293876616331818239012427337893327439918055828366974539921915593945621219565330404767858923408274666737270126919511526454745606640025298644609038052604294878709487534865955253633918333223333879424428507727130681734250516878112781986828292113888597325509521170781274478155608012102842983046339140288035115708874931661099364731034962030829368594443884281533786936798829872741389822449571270648093413601061283260904786333494218494975171314738484383857691899631799919938420856957, 14365902777854250531983507602664309923015005167645884278945840924939071223466766967290376724494723411730147618483955478391331518620286819246924772511743257805492912979619809893863280730458829905856759708728919947859746821166234955628968376481717289750410591787552618458209263578716314885073581177800453091495975924544696126055703989942738779484826213131418402443604738334502050551683568609423702169701996015388756179309333183442799476303038318215377678152397894782352599973842375297786468311754538017544187662407854492419166728270199868303381649771437224708694091369087106035183433646991290508264802262323861332550116, 6022669031166747253466015339055995683996490219779227431073941591159625450759399668388588623195297259370236391379380267063536076324830294921760848919711263267559176171057494193211176749372936677787531543149399435366664972464676023486069288457518007573954621546444552795842447567137705816940873155883227545339121574570360466854571283856608218146257177217725295873816126341807496786042068185326681194799568209330390811050131901061216855784474299081502457680617712775607031235616229511646164034787969210556330585465636862540037347534311336801156030134644802987586688204047991611117427367968627869201711276601205371093919, 14178143334702995711224677704872466715091490617379439831733487637228083284188901311983616663695808397085734913719344600405251686150831528656302047072340539968230723433301788529616623237924387814101388716293541588988502784101449665214818532912349932404266795674124745685709793582162386817707620066554580142149212645098447752026009855192781623817367254806186284664625011321638610247932199543750217700448124190971521157103000045031556572047178912636656890071698776287326125888236908608221740969951155885228272148079963328348040529492808084359765572305545064388149774570742147783615145500116629655283436336222366327543406, 2680694524573180510619388201364051956601371678626391643107074412361381069403125947698678225063626428698917021785592445711838163172162359861736932747529950301873046271424574982870967985158058371593102557602636589570170621892557141141890971308668815321321503846592691104760153182493173228131111669725218287430013076199633505869722650653471230844973353770543433580350352997695912141095717556776042423299523637339514996694804061478395355232111329297566967096869832367088294558338779659711819074452339499289329236095862199932247595807459057788640451741247616687346483386335709540893162289374277509809033849394952307960585, 7478797866767288177842590557744979347761318151001769080926453642372665971078854559404929429533831964726956415195994378611670569410451711422282005274821931987455210091843102814304596405241825589335607034784044881971150238738517391880937791655999639819771979955821435731333716281513883730007806365757816468753070749747852937599167905365829150573933335225537271763569203939077628984917567871123995663164333544291462730081421781584369739712819645132052534587203082434052907909075469922372615750377044879450432513785661204414594312043845016705644213917758530136038213977501633500345728565735490454571637088698053351282058, 11886840181470037072367499175055683225679270502498128458158694920914785565436864610112181200403310783097482126193153589047228843841978210695871814286817260095579253909639108860259637041828373762432612146251368747039379561840706451564261266647291032218038177218174963531324061931656772043667740581858687265351593183131721230440968373818535928436349273532930515825453633730706324750578097156542138694133418009576599035850809366587674284577915488229845838784023971322777768625816793683732261992862646935210677172812974476972934895449820728110690039646399600054233305704650273134378459145317845299276434637028635767223462, 2216960839748624388459153780170456316924086708811353035411015501288750028345315185724068026696346669655596020325162845908385816646003589421068916971172024307172818766796568807210583154992886441265716347716750577942103145646553615969178321374665546934473173285085041862023716353943428707418260824848718424309202872827500090021593693764154373923221927770193447154567668601160122224299767143871729287729336361625573566427425777162068174110188807322711625673306228759377160291466390815205580451777519597083906158744026660417700384870973545360482494491372172626175686993967315252516591053138185989262143895170934789837982, 8463755598473187211768479408502123448267857511527855998115925756697591210942507697141702867920476710609211442389921498556023471904376450380494335821890581522634876033738104980219758056801907451098156537824790701711317640988631514715071699331492106328103419122762416582995708093656829153328248772635394504968903357670121616456999817631902269048198599931847533625808729547462810703241231963410572023573441547403697642531584083965112168970492938486392199982540151512486445159210453122187155349626706949647814851489127140982364673732166930109951403346543701510594655823570077993298130847377564591662211212809798554006313, 11669029083164068827959305898870952163583409531894609836904587375987997016043922234590812448667953841336809832498377507968271207191887227096827158403842387580518522018119481580097590560765854651886856641375402643671911943942882941602771593524173196112352900870797272850926855475038472585864420721323469436582488256898242102198409339224792476853240372018721632079359601189385546918676811939444789798793252387321857199284972000847774042545236354893193567850652496133506686538610102264639466688067586885159990470325240532456931519979934443896574738255893331623848084516167731047977483052727795746031271729817639984706102, 7034591715586025670257400075150516708591163727130659288048895054931819771811408355732593769192148247715670310607367519300097082489935735167637024998529268936933945915618402676499468241051409227947394390861342738650867959430488928982695340486311994486151751605199891653343017626233945357380082727663135590875697586197058573555738489424694507764434341179890603171843509014876489820165022112170755148787041666307962104172311332366563054319249032363402167058599286377479607916057924347311910939053730031083618215189816988494907507543337649200172136826603966403082813112203821328587592168859202563557990701452188983077100, 2780908644277163156594934974067263877876352882525071854429514335638556765964233337918318546035803945521387422955398713321590020812695765487129768975055915263827753925026442274260317839160965674232285173318706423561470374130438804820483313473713303297973880689191166955062446627562279431851341431336371401588284505479465814444525773971892706977738596810189463641565306780755328057441692550104630288541554441782967574599396685201947336267791497144470269703474943409052519917031731113108494531412015574642110425099379094103092917223351307712292115474725049201111055438011639765944389552069634593117734425429987141240261, 10404513245276011341483479942739715224797010232802912687290865978208016528869669478119476869491971128071835088449597367454256088939889422708834976172487513080083443668285738241594863633871425978572680681776475953491893382826702367953395087449714577435707739417979162809997442780837328448083724182904991786384992232048285420209103312128501678197403108992511039199404598436244078174784966088849256295508766701171439989894308724609097757626248115475096887464919247957938896202712857176647085322080028586904704785513641861853598916621432191397458633912437128897702822612007877981950799633656963155514290763129663906274293, 348543172566425094267390019248254585843854038342942924698403095997551582634381613617057341711648617230193268606615528780048410943905269530808251238466258631838901987761955753848467526648584038249883600186046302077226422425981226208896846897766398750507395712564730011207725768780681073163348889651288372741196594043635156219216495862353232751600736243053824875057253386163990392302384455350591348919057205487763820268423171825380637011680660174869825118565915576609531001219841843425877889383347643934625732646311981691236936219614701861819483650539628291914744450424368276463407550933725783124804902417682926475643, 1862565071922487005086663051339057570593283826223227951030703733195337228156589818511419160496708387398431991616394703161049908289762833143693409180258557791440793006351157989862872462220238262161065914478288822467630347482923416613879230004853565574246549359456399823325227711410594047215142697373259250406926546753989593068176194347220446107529012764007148093717637384709823548379525463354373665488480355525834886462242089645285285249808505141692348453012480064035596741061739908582360334795011215987801998735877574864574207800331408089616207833602489817768744283098154895425356155561899103510344776580917514005999, 7791316716322855278497706884529042143282484239200017242538597106715404982368789818452435382237615495565127581707946123304955590430004621759354710819303625563207189921457901345457117694897840559645433585598140264675462377131310190054108518789256262872027562200433265093561868047839654850504509573900671408967204863041658680399004434677068216787576540232169302936462226884932793715950017402982945890864923566619561418294496820125983043990560866905439408720768051846228172327949684111225157456882994829527348579778152150931182116605081768444459716244226147342128825313465790575765812259597204965579364124277814540219766, 10911832963184217835532697581521167925334771539453317373311120843526463226266540240507961249871684972579593048012425564890483226594507101738145781968227773461699739460502688594113771757732004978258153686172814145067600010256987625470463432011925483723302348030331326339597983922765660107778917227640786682845155273428964648054689720988283106815377155716401054114968530271480955095080567937536715468218186833238272168555604885314613062998547454114911556456349426534084662186342131757605897563841613677106844892347086419471883283673140288230654622437038343205957056758415952085034684419006717730488952304523759073096909, 8805661576559823179168203130601768598992677210327865485308059735123403938745783870876580316736911840453558014732300234338477920142095160130643896013618515035270196229124782849216027958215525984193111812653527340495085371787196831505561539004481525429835570012691574546585686475226086768496241941291460175300643292326119595869720403766473861574458267142911056445306234232811597059008576858074218956825146013761034158794163618282523237907558497170989782219974596330256647101843879180996894925790446284520148008000460495881565442102220619914305464461756780391385872379310110325568134624005137129425003270608198685719855, 14039452113852900517934673829590693310305496339920559529942737533390764212574529637449012692384524696970969028053055154844295250283381816438259225112527265802156316500264008415557282357800945399230008272548150067835848238930576851814431739623840578739622609543235082477302534137352094899279225763851615377107058785398170778534220683470873515524482680439100969053275630766491667512816141982033638561924183396717269008744422741525143942610271829699215464945287281292942037229717356779421070398321329552029495108267364761013945538926625328401517176256932355308976341282931691870829621882734265030549150559397998071309367, 13186735669883811488444711221565076301786614468300919648383539567647716162597728794295331115962129863438148566109139888403691860045240775335568142657907134868089850280543415014151895787269676222086052449860266389569707664767338195752602843714561807424779397520082989238421798991949101093180483309917886247951815228077723352992457183543627141060883234700744890364455521423343959940973569181763779231696662314503390737946554621996497479279688283452957732781215536870142849264317847565523943592743211573460743410285553149358390891410245923189183511030339897172188542591228500082858661374191273333942300144555948256855319, 13199327855270764544525026558150115881192201465814851248503345382344697512404378154954105407236878264597397059680257805544550324230845548111911679518083356918070289189665278600968557293048298134435810743016366064559165440517221655462536573687493841312612070653768856647458406334991607474290969928240889082210493843013133167680556924962263717538057465883853017988043861317095507117972541820056607582691597492942481969173321103341435909448150967179826878617543815000082244921718700205864383856766050676285880221950158851533491847851771364705315303856372287397919979557251156127886884015623195126516870008651066910188793, 4454453488522425497430544571845732424572325073674451923313049338711562747358134363701610574752487716604138206684879968953162383009440101995844888488057187463123693776244658218403197677060122728972945658406112389886411608724508017432736511238674377043913889010500811525212291593985887095036218076264885402056403639389750598013495109077659221465125413306921482067078932552979552004063582949397080549825572832118346807523825939796908848853746692668853536137285414687641800203943386402884762589734026393001935667332653904213504113465757908637134479690555787519830780334820960373370311930276412368107975457894817968766313, 13344222374099615818796933720823540138227340064950390502126060414449574677165638209566178926377513365686061573432848574666794056784991165026855266006298073567634154732279787404054935073932254379754264312880390465486248694983081814113865151845482502278155757502733881982509297384739400677580991718054358755390327792121638673111932765766571228727568357983312239817790508307160171196235525275470164269779590268439875952024271592872393494659826169320744515891424492596940694466281960842867208935718694388051216929151283299161956973640159401046726410218224701722953236879512262435885095373920531937528035782075878686797793, 4549509528550102624007494101936308700006279417735836715411385802267554534014307483652229835093437957310922897449047559680642403359098552147563253520655539648325769409454930198229693333020071297407975575614014074223393137105123150721188243522138714832026294121315979816031927332597721915790597553638935547058268631060208658119743893022527672399387655104917532508245171452933998217814622107893834380479527023628204126612619403915525477946910399451175266921987244925461252546067922057868536614186988096034352636262226079868953643748241719660154663638810648004441467967931857402831046520418208115024127015811994547174437, 13669523792877420589383070144175360617439958319788222744638553991419667933200090690336114826937249084743715699659308574007244907830790951237114622130097462389102238337046607317486429327144205153943848084848839555725641469800873358505670905574929891568811357070868543245876488522249639656106496711161270713575619864729864986375546149351535679581517218296438525286548520817216590529043601616093165300928266260630645657433469332034492299772440995655775906538796441775109034453535581603747102102600938203696679569126789580219481971225045471692262019450742650946099619483074748707801615868626253472132366860668565806280152, 9810717995095057081681377169450969332126097662755664018993262167262015535143745461153569766121744153780103601863360742041288870965619732805892782566917196669385737593275663023745239730529655016737413526335593877974947060565336973407626793145535478019504037739370451850767086861113660828811456364458987663413449674889436698494766276856559756804401465798753915953848251237194546087958548267967378986385609076281539615278965291927952881733589808565376541084747600263267136259754773034546953489599411577713585750617139868972189700556992777231463905987248419980459295991430280287076517078865196020289782892011983557636723, 9389387710780309443091636019586422287143969636090102291378709201482074280456424347296341727105807830809947225528055325455100500820455679311534147538591293932737703994131101944117285125569102219878108174232259330656454757648944064111462544897650468829821835884750247255412852676560102138448249968723223765938401245604999872265507210907770923036639750311359327270767788825921786988029709543782110713592139551857176149961337879830947639119648833033471278283907139968319935753491458133378536728660305431979060276749927151696434834197830279932801445629135926813848276350946301251490164017195884321122789987495368888351322, 11302899383728944385854014866272828482276354248127517359680401891430560937057117297895951367057961647217385878001023004859153281633920258643469415310436503926251358479056466606322164478329332928532286281092212587861021543290024628427879736320812222067436295280326244938447659984749626126599113583322356455968417014672841390914488709205382999413512726209316416861865176477130564744666068364444352859312186555857804849370427183347317258395817671571362665055769759797611847583497072327476771618373735198123087262730267141005712221340892145688688879093072821246614421261054275525827959298857720758646652015848892301866325, 6009289352739863752658149671220717389207045166140845566674798339888331510717872847483983045605357759739827019600017903011626644049973226686249930276607390799260647969624198239661239266469378736546794809010536131379688822164365429709657839177790288435865140713527618299744638001391790357332702940491091324674870794434218611611113629638625565170861833815340217235188650054537405389349493728991507278846862083559316519276133969192337916458452628161148388644500551254704303992041919796186101669688202647314105272192922363925894763337564531845654721977625530947574273582553252571205044476936554386075352306802996916784736, 14700756711328681587104866293230523952825682058737823078277750591869753805504314398804774655701269673343291035346232705282336747061416310098445604442804237437105393076641175874208134045442267022680692066727963936023028600360673560355375814870709473306497583346993207780126697312783208535836149739190495283778134346528412095437566245226912790636156665432072779949155150315480110351445839102449687608087231406077890815195246148827457693476325233660994988893621900064962814258985086137517289983468004485957737322136319328347037876883271619927722386035097453664035985453065621029014416189468907092984431012397469475380822, 11617128762841905021290302101253512479251857297608607329472672629986379335422655846205036076502495515090793997724646701838097337205422423755367987412143338245744155977995853733003555520961448331776446748829755327693308991793029744436468011137157800971594447292257890472114356986875232596056561022278533349960034984495932365675062345035118784756871504854193280271365081645691337391380439145646070909110472695434964400571474217270325364523502885609211377132232532272450098093577989124900618749053290940812363450692061745025089069542484959309622314434797444405132948562219806380564653394520159657750227552533423193493969, 3841289139146089120342802569317450686435657828323876034319303961969867828040265078048840717217927575629144020301298454007157826779780100154211289985160199870187008181832956828489507525087082103219742383589440636819987820446791555533817028270539105643415623908821595552672923953044343121967487953269977241516286648329088476925046729918957104259591109842510092655337063553551172719944659659486232816495195590689055386035520513265297368033005806977946980751089421772669684205232360939763916245626713717579608435433837480206353104614655623968511847193908650883334304291142499324442927941997421156823714434031322899453428, 8719270433680245055264488365708898136467883129294384215502475925339992342826841155806139978976363680892591607565311956152627912143438044010468431239781279261770924887019708034255811534346491427645458875705022403881892378300857917988409604589156513054898362078407114284525447906040175290101864977588796355024120578638259959850833353119202176924691103989534288246672469016391884724051698831666033143284808314170296929255073391401744385745598528126483258033788294457242774281141956395447924747104424991599316569059159679631242535815027735862781657296987464439834923394146345403031876567550987634270136733232850527891543, 13102471757891171127862583467011117747136836313983687954777904235144186097499065194808162189555605075094539937535953029174900647835748933254049193264324966299240964085955612095143740732404233592680191496235343593880784892574536506463898539033104627511473907853123870655444750040958254994584213929441174194345648369597441512794890170676507520213193396894397537884286190418624573027767752992570246445298655011256138393286797248655555400634908606393947945125852864301851348371662116562684101327690733695188644513352081828440640344387730757687560739561067399510266386649232937420767485702877651350294648368163169965479713, 3310469721304491815766024511467222819648863019554376281061443198292371640031325800492210945125911510066983414717431087663200651561421090676846921305005409794081090875568665745454659233659290640617188085778377840269405142850784142549834307441172170897766863307738994523034219290754754993446434922316370131706116988817102378262212737267700998473861886007785367248682999080353516440029669223641879496346272490953904350293219003522110173296900150254627084099773765725193718645267768760710397290508305618088049918967363987779441994298639242649498198186429385324882102479495876112858273991428370408016418864488913358548399, 11393456360673115764250043378056740348721211239339063627043189413655819754653336883938551509989912293157496455630201707160181246892449377915844004340717859199785229778452350402743439383431752455846471498004684005667065764053728126662177447524756753197390508152676409864899150031189466370669588318515995230355747613013738765974423008915984325133040473813623185155237276500752489844955758716210024786581672859411752832191487684259828878050766506366368504329301614616638918141303006150128028073160171875237955677637602114271624387004215938601338485567035328319314314087326781498307130533905963593941303286195335680901180, 9838545785778026660527422489864857962654548073005602706161989792384835352084523628950498047170293195501947820374961490211237017579914207790017979143692562243785984040944086316442695150827854353642984941625528424214578080483540345816065942739787871633316246689533388158886732801430127682490593157816615923917658568829496994256361564018507047253991212518358888686146041991722293447731984650260678751590945978619515649110787802746043629346726589178409763006374274992204255855603441940579133777625134827272139909181894358205154453246052353522956366169248775067031318743419613141801378014663704258110570094280519730656882, 7190976065444706497618673039286644485190289593559052391239566849673546236109942550101501983627389019504478093692496145710661286873077115749602041416663279855816035202459884703957549506067196365012922763389174900109464306793540173810089180382030673728967126247708145198748331512340107359781700094743409678339832087407847040360838646761567037007003383571670675054572059119582882517296496279485019696785768081071561600956747889550638502940170782016847242121516666212226434110832302779378310669151246041338191081127301676225522885246840671726864237449781582406491950870039593748519023727437097913286441850537524798654353, 14996387091285881176266085956190520322780888380878072203302682078454051017314261078640824111737314993643478477781717274854189273713216586600845876082137064817948701236962498513410575052609852080003887916891332218721420738629805956515728867132640513602799121521855543621327661321625274019152835418696826395435503037673139570497158999097364740540086306853353470804425366689702276999611343203854614644158175927217990092790029677363119281756755904215372459376686847026568164818793242722757937655592546631510676997297276554354144395399567443303598805627825745409269728554232398813695840007155719008058532355516316318852956, 9583766538725180653577867746749041606972211826658998223983068169143226677052158702272583830834011693091209230976042257452717312129310956025349862617445486787409532567355901298747030542904721858800988522083520981549225556419520181667130161539225745674332173438354227810723686774492484092072767201061220163998280065110929774502670757916177810232762027673119964667030167539494529856470501814748588923929352012821765873499000015220820135618195178197053453726466898187950804201394075602145047162488514948376740380902041397307725916691647934635560394924011723753499548516966632766947613240088713911111183319975472192142102, 4772209830120888393586405787596409759116654382266072017946572365486922021418002232350140181024268244152880218843705854476176734362065951763619656615936112681037192127377374780733014904800078394487764295445371962377503673286238428762966041690917315940141514638685221287037032967368241317966509710051918202351264357665310530003926116162906292615336540243423721868696654202742720843925197143589706371346696026173693904264926231157616644874759600438300441233233298200896236146305278842241519288175589106989636179989041320631399888907081620371455951020892653879577611542189682359940020787360721634316904657875376289731994, 2947386937165173315184449667017793586788330772065645697188384559233596380183052593342088316778059613879762246120633746251592444387606122020157507616557284697507162914517064991413410439158551360151976097015017938810946172670228590438636630117544351558401604567753404619095958071635133277381060456444162299582952080779585773103403253404608745466319984291206451067872757807704676282062783747371603808117128885563788647934718612542131168277291936850360686929371568685673079360546883462051923988148208127175851486558346520299888177105285095462077120425620929113334739857582740781080665913903381891310589819105860413117619, 7863582313481285616923035849141551131897735337717653547843549670781961501147205005198086323014527965830786670103537136711238530566436225497230882502978936105710558368924795308012673772319147689399499424834667810218823704512152258126151588660682783208400463201955419694843240604908851457544687487084255551221922469410091963410315578139439519248044930910393164535386225527626266206743754101760574672882513654964556809316951207156222524919301574360335991486592433831651816217857690037283123582103150098648635912242677295826867229638193782734722101218392869803229091640500818984931779705040754258189256812568662454579632, 5264608052971023165774531703284376640943168953906399293608382696507920845545946974482141870583715889093558209933450553661701857353238232695862587394786807528771901552306598897136027481691828006260306932102713334732340921579340626090856585117109796783771701408319264034538002100333639987286979058184756112221021800182517815552765515488513264776238629626255427536513537761187973412234119794942677291444325900038961086944319613723241910634483279205014601946925267792853400760402573286668914615850172831599703618871665890208206506085706876885981979949559997142739044999306967291652527389135321031976464682673543468365560, 13846064466826463338830283194450290509099385429575498349083486428473127444247884974261410982409482629439892822274983453472074961497551841988290939636624536949264486740344599218119242939239003234229676926556513745539556846830536258156332258727144422472307509952942510519777935930079728451779906614393973555659883642442725984900054975287700275859664926595547880641820624068794951953342089879005717163181667792141696233522582050993293649514026347624765617035935559698420240628433019238460038054610700759297639508768510654984638539720119697312147102932449617068315042410313016579439218502505382246991071696348217195959246, 7453370682471740583181823505330629472799150120602186677178397978597262609924829512070203648538270601259448855781081729900048158927398248979383629065976348059129287365380754431116231667887507469925211038645268220382864084573106259118175243190437478516508912117025608140109887099976327071700559349261846849503067474233895679261342932175722417701276115618256774900582203593578885892281770713974411151637969703839939961613645724276353848273999136675595122874288466800995563811212939757933090563229110821724628967648944592623616661206202616410249373527860607709420650308392004754576364755732066893388454618601830589606693, 4317625227263533220904110400715789569869826367270947079962678689618303216432581071155136352680944411239146155962090597651286086104054924309245212733927313291497234228947504283684975384941252680330752242633822264241560013950309778017805895616065648480933032106204420655353789967638711081614116516938337443302076736832052545620809862083951492355670724315882252239716318446367578633257119219431192227715048262033428251860529445348036495575657711144834833417870023193636859211542817711300290205574241652765097721373970940812268885422218219735778766598770128151256064450595651688665809421872114044500999262438775316188357, 6009268210358665637068774288951622076773718680860036103887054718251611419268016844883085337174804354375826912102242950458059564227689876187285432560376555146437528325222293208852083855083230661399432566948274745427873585856548819818976369442522868627468540827377942538475211960454553095135257234200623459914804302570971821787071181640609193675183969351796696990261362529099392626214658829409066648642037121011366154508810870358481108521297843651904721613474413850824647575510852978393492288778976147297646162841248558934072019701399708387652673659289337463836086368161805253199849976551830711038337385120196148551097, 13536490421378380473804870021443019114072527439052132296774457896100885721255031392142638378741479597128417545054123676275647576713525450766402484527234394324052701100661770006578854155075921429381001877892971007806810454014951959552903892101510606890910381874597514507572889806501620210798981309965107919153208614620621618082598632030492185022549763233367164309728328583248114412129863480186195458648051380358413435912996702433769415325417569989830419922740885127453644788852914683736230200891433085336771773905393097463313218842185463406306807023929234492855566486921528735906031449023852161062499877703496340252301, 8441314907248187736374297029514958470569340253084036635151743806870111400548894977226940010903512977525188613276825119401187760361964701381356489022729960499750547853886646345145770328465377810159219394125017259461655984606085503910803178032020285778122538524611322503597455433511996067093318277500582847855490885712033124941093277924689768866910476843829527807091144442643107789532894148973268390216828993381877405772760804516071629109208331582828242345126847432013824787668017735393629986616077608501051918926810940248530522432991032297098693401211913738055287204527521763465779963109533834646372060856926253972131, 889379590594645939349612545372016712841005657261424943298191730124050437579030011916714303377281336753333261395215504804356694877258924720291947913277606869868604770841932878964543520538666232708315316563591758570930877852295614451758236080543553636160348518081854980633472649335981078842582741277912656024662315173239314261403084913581943620662631362687050756096257077860334750257684290444259675749868282832165378410838801669077267657328327220349099465500158494421270341281256918086643128846536050912734215360769390868313610255120839587401750859787467151379239418250493656144589320817110428374715541396771091349417, 513960913671954031639059447811665309014208604279725783623071049485467390076978927808940480426147383827417926327904764729956529028230129350950373554522583147673964911829835588454934507582644962521373055125073909648725277327778200497633983008561423158705931058201088852858495190084041131854716107500649486307877153084644145683755586325560901195638945035797270306765975243234530295540565642744492640390163352044952251789436983751074000359499780677370952140117540083241421706483548079029265031611432761411698293723006224832625670277394443303879430862406415222301286074978003096825539989658028484600565554077965163871075, 12784133621494786317206223502271650853557670299595382872838369412075420688824547188321385891026781105979520575690639149528411997058677263291454440551270094791701862802222067778300050961718119204734314033514413939863247765836379892565236617032841508670572744815843021392529577970303323931853472572533602085596203083247772716315599160128185395536006538637313397916527812773307150582188979812393327884183276895537830685957917763966959605814477150058333238398182752713113177540574589901113741662620431882349102082017531495479247090554300863256697917225034407596926780077069618334660971158267542563975482297152090672612542, 7946858568456275901353634795296449406207104010944282742550939518582039545180673182830999490481074160761552090458825583418491578733831333099000143398315025904922452929559236356692923505343709601352469065167497117411308572404001642182737523396330418015945514220920888259525578277603740594822862749014467288501573118700522532283379408856268078887566148137662235818843322254663478431852397795168643768676684838622562933676074433889438196076839463472625739166494273215019449005102876746446370633298170401862655149134054367406414018358417110654594360526155017664888275993629567368296213931757172095619843734838440847617346, 2175304100027010394765705893856450743510008174694321093330107522328789723938431112945437167082492503187928250015961816804557726018090345287666437208228760175837171705672474586043943235487138613777327062678518026813695034084346029193578873498451221247618059531690690343131091953433840018420264879384642811087248340844826617758755337651257675354653419610323598106865101289464779492771350437446675907542536464769122204493668040687254615483331338032165192224353004888172648547383850371423112882838441237165556385633123021902569144045897305613765810680100536135594511086887054346712169530301057660431139923385592854213613, 9115094823316681198123128999721751896418899466971022514436230540668968676985805982744325122282058769394363274855196012132626434220516804346615521276492853800970988917339787962562901680116963157877044518455130918445306280418781016136272648854716464244914398154297943577281442452833554819454969116322702533232164376705324798712067074532827543372625847145873578566088719660121617651744890925666798348264040060683787640616817056004029900901000582159679619898108581615876977926906895428593568821434297775504165523008042373836343264742084016342061321967294865148170293185425870262690503782785370023923094940429605629429763, 203287614655859984522450549431105006564070082490521737033581954425354279354236849478782458683143559002757390685992245999465879537464095975373985688536438329750472563274552149355767985257028400257758534513308415139433050467042311746934511834544440606716906319718859024514957221832451629225677360558118945851493225855158743977517448626221055623073419143595084230708279570245259971608417826711601796148003974135256176194351719846883361179502463020206709741519945216395865473706385930225721664690933698998664926934329196769173394250663418376928061872165256387167225954862272588659760135346564018756974592700544124145436, 9883107688216660053637433463771504552194450749677280642271783194846720115722699248763436537385082343267738838952775948530735856112893883748572505385425701499031043174181904911929131461485971225852709000773838947525419646020975418761381967623427493902148278779555242758944344783281168461405622553410377268517796108584521708038550435008981297207373724024699292241716586109516683295836952713733269427699780155988216939709095644601082012807550786501665071260290540182284370749131727920826736343476078102229415877671523432741036966276654062929599914472036053714620414012487290367264190112392025088865139525221354227713330, 5440207855055275466762348444906955742829015966843652742470170680815435563901288121961767237101399366567164805678891107666491148955914683316072739241197643442365232078620181278849280624379020138930546354791571843214552821142571953586149565766031162827694678104049473377751701524286007898882379837885777928353020770020801796835801738819779496911726153647891894001199100119295806691177466453444400404666710871725430984427445844051544100473368773100178377498934671254826512818149213881540330976826238090303368956041386815448005495476802458756219983890377087416670286965550095035797168916110165889335258143948804040549938, 8655819144220064247148599853028878795108210544521306508164966295815789006966766382751596729430321026492805544827599270064266835350665555898037643359115235549381636992655537757096589003565425469446901536326908137404916761916241091956829074197000402890922554975053670405533137627647032005103027360722035424166100765999324479514952439205906489561221983409633219231149322454662957347736311176702706180673534715956916758947535802243191985142581654852579066227825267540413174703994745139807164587713935223132249237670633264857262959185581256544460761434340246997809995215193108353890048976387601435637124444377815765054512, 2549828590736741620819270939954841824530003386890690798385047804121983717625257509332569248217109261907025032405654066905335721222708625902496512004053071698200153410648990348263614647494508411497299198749983814262139600459932892601117080831019616851677972726709239745473327003035712153321945676828244050889401417205802573291814220918367269623457878721579150106523514677533490208033553525965302626101958207906012695336450305889957479707412673069907097456944191972509338899045083809325982306691197318116088199453968748519246525587845771266969331986984885832436078708901339379155445782206172762281647967404787994903875, 13480255023421504030102744183638325967561401878406689357710142569357577646797435343864946215370603411980735938174702112727893710844456090111046674139272366093169918767584756196317005731428295886138636759215837636045695054948899816694383041007002307308870473301195816143843598814226408760750108939891079948650822979056416551888488589754585714832319035108779634269421782009331665635259507999230480022590050014935328308044638149325917197906205450093766482796570945972776055339214403579785927059751223476591696688360164638512279748022417029034626737298731586561553143168555996917987927256741538091293252996184749356542376, 10331069871306131580332051297906247897700538986341424956200077698833277001312631014597315201938782850596643291624489873087435835668158947055072435632524774723565268628099714819146753035651904172372959548440892514335761382632122749519251297851153422590501288857107524265130437650954235881208062204284107935962222897345575642182139522114313368041123493165904247859889513166424348321188758826964247416383490198739053575381208465121331449195784565739918106711049773977844356778334720135837602902764510667590686679199621370056710546469087024472998808616832387798016830118196528680004913653816072625013197307070576948211523, 12602890320015622303841526584089523995205379039152756630075613132458586272905429613993507082379221995062491523328369650737517871596436679097850503319962251745583194747271887970359039916760615968687205570686231128269455028590306034678264956174441345568404258182225728979257019385756813319267286424565678403325600063994823911110797136680649090069332376507660397511783307891707442307899444432996513798926990157486412506913090295545636080124153598190920281419067713853632583259279233637008483954734334337749339322664414435736507629082352291102793445092958704909994717570581347177300287846314463713792006783412965919190130, 11218364421055374046418008576701584653788374145397854887145800658658058696403862716885588703700585194634841684740489931325208955102749532329161886550198003661580633485676063328036789761413865999029576416878556976901431633961860029554286390293125810829938455906669545779449712248682674284187985869944920857560925414594476953903350415542311752435640429333494626242236851665280697401738290144680991245878537666127700398931069829602779932203463059351131234830257013763158098631150444713822842510949782751317096240807139506934897574353606568100668806891195657603877972279848147125239232994147832930998824186161686196965200, 12547000120709181187992416128929665727063806532371909855329736958793771410530805098446393012211346894305628029724243448974220276051391277115741195121539546786654223930016061373637721130617749420215448436319069267233078312128904914352492700110796144537150380720898010544721131482695381424827286940720749193938002739807302480331729158991407573785205215280722396068279043137290368885597946701535087824142792207031198690469208907620724305220548104234414518525578198006670598006331479559791619635671775698549772543328090563562859156340885167998420008920993173367822680038456280705489473697753152722854316159001812907760049, 1553552582069851866855499245390441122339447160680054294186866192261448984003003284171754154944701263851864342998371094675798493905999118554032626467197844320093059856399093686243682746053539557975186554960300009587908436518082810884609668917453158840057593161358233463652096896138098906049077184471879464884353404248216377946185892779417266833333426552355676586990427824745129050712089842887832008168769475048609616477512026897692700605821718416069345860053191404256745189194842985272453925208267786233022966597723331110224689423306424588565556985268577001833967320151436347398436703593741855114486824162057429056193, 1798670904280035194148247319250952946286854382407426762269754784998239779334736742900987739354298564249119992888185249567272619380103553151038112770137750506530929636706797401880376819354138340025409311137334666860508919379083329929191159026501070249035189734455174436828802541647353903886261890035897506128717581253109538419254939297246762804148702889467961335433584599042734907455423552857440313785236466836652976199672280251984938229683378957444118184963712477264562437232015356145770623271836297648218438126567466684063353493332216148884425276336427424136171797944275707939913882732089292901681069383954714370845, 13780762260894603579147347784171823112483632545021487482290137190284814136751912139703641193391470429449336964416944755725537929054894675997409533920587403747032998472646431246022086574209199949354501722991305831801652603198030922490261962100148358651740307416969907251661147263760400127616977177699600196645870894111658201912352231617135570147381170422851698972380024621660529110104640542642563848438598150018957583175110116957584911445720960509183301017427967253433136357365781212664726815564664160075125210883964258162230393393544892847591394240164059602253933037604898057935533661826669244150474781860043331231257, 9223392802836033158256889991749304834600172644382789822344177650654387656729394427470159084537256080861772219847893581973772890408362223403889369084120205685433230942133658883658234401061417801928825967964726138616687001021602273961627914377762124927752166289513535215349758619555858223943918159620754827163987231323830457281382633284807330369288316455219127696272584968044546233942171303847739819514567024362196114319475143430672820706513267956697324067735798389054925103899794946871575765637763144095273580871435277164100952200212982192161895398347229602149104987867479507441564605708424484792597661578456916954853, 1090863455756964360182427467342779585934581198994457125481584771069360691858519821297957653324050115418341113156488057494955526602250792052918732211166420100344869503163876059129397037201198694569059501195490165680971497602336259402027807865442242375585930560731684773677874104284047294898854430738279767404176151579607624423224261919344761637478549425740860516339382390777740904805500729551997933167330645492073867959144545207143485427833157265159591394575851681681080776614293856728076379096992267521498499030131771928423608321013706467101937829949777472662498993099005158298906843841854238067755955025254889676936, 10628624949793377180789669615963941853666672034090779688727811752914134046322431427784900342174276662629424828403465963458266310989547025336844064510225618136209408802111491984070441378988463008625278265264704490271140074100145994103955873425605906264279406085154403888265018292833420701444892206147146956813970257512688490374689363868528294466123929549565843136228473192658830507867457097875135399453598458493189232366666506876506352144898566936492604486451533215802508426862050617154549975965191841490273055288668285238504270662541962753860624386355569087073451273388202766654633925794997259512515200709781804681557, 5491460316141659382572371573618935138728959060032314654080033113339761974127308895474814330509707487974279174582781302555058355325464021246655616432291228466456692370970362778351626310145587150794910585269451030485654382153129953130886011576453911321603269378489083746893112254596762675698226686879135775026942158262363604218777107142861587217713582574114112523559282762541999722436689505829404129309534695089317324943440186788339026244556287828452218945970306373425715985340408912958668643945714398485201372669754250394485919923098793548882804150620263551112255149377944704293467019599084315645276466100539350798898, 260530033338771951684245545204745158824102147274534727502944137986261018085317242204900541609697372053642589087924169384237595598657260572836217473431533241852748000284926949988713364543959838246011166212185000074763133335275564638316684983264885075532186975109443737928719253221275036479933268120187011681115085125560106743825078469942562916521657973956698233732861423623511602823422123844252388665830249091880362357400332080879382288773654452002643217285867857849427626266228664237445040781898900347391651475101584359947907092853212097267988408007984431464791162832551001828763648415325561374407195339902861221690, 2948131840427186027835742978561324495505481406702585768668352240183277630737669415196341082117417046723368257860915876463630074606015887458974159922336653659557647760166541152143164802023331458313299235841791209120846348280925647031301270365360815018871507131955828412541933207047208770129681355265173046890822762573166564089613109048060392947535622867224619799466091035237993420153755155397493587226378958391874762467470122405430260496401050632440941748282020302510440830317995492050789776356317102241729475812285186359679200523658726262247786886280754975376543017416030129707101443101288757386491132315946825672334, 858612668184334550705080103888683962271126145615307700124438459189850654023076378478247859997577730588195102395876049513095005255958043445001518303458607347285157646570274072796338542025222927760121087768453734003772337029807086975788597836741307846075878374134924463234563469204025874735007824045230601920043092368446449239104454631923463784228354246932386072528570387723074777284844124263792623956556667994861598960005620833244681777802558482167306379426215460787882587649298888652577534323677604239732737395770242579535065853674192195293096910062302121961262664886516725006974924589281930861005566623633436521161, 12390905527641208205484887193041905291353154962763774562659251433960224210512694972257787528324902383672862495229767278974432368672550501215650229355499891900206977201166073047117703149633254042222113353336826457596595886262541689378779674347236930349487403583695555798683646665470242259429388364592574848407960095057714084594694071344242721629044675951139626922618529292104496811345776087015022978061717787411651107100785603074079244531447626311517998040631964122035703207115098296659200798145162264227564876245986002518314753521859201141686667285701298929813525646683012288252277291564915240956720513143807187745503, 2921603479091378050986201588160719307224719615647168872730247005239371150834765330544273068041259403540507837732016833730869367348928254672154322207666773202096692260092081146696908883890878480169120837382216315960275292795096395209666883182962120708156104941064935088814989549868365512481645050022483338138179393967951816266171392303632442843725325540187833746777999765029075480014721739055398002524382018856520165672822093466274704322192558458434053538650192151890601661521453770426389539726602961933981996012755945779767263819556817748286978986383907117728696315171384569471498500842481669397142603415835127974160, 11650167350441317668928716653943615150685627037537500446571783633463603119417451006417914667164706509118951375309897914467292876802306258391739957237039397365710888631925991301309927391453349258336102981835957525193174145319455480103780553088806989266124548271153814649978628933697498219773057876232986065291667016972261127205402559661016303763154657212052549819563940237587630835464934587032769892249538366505631415917841125652382631397168856692110213076419134754071843420832194013244726825196043194791014217387818334516187527302901214585246367314658073367456095277794209459224031127107895730137300571239695569079724, 8021039383604751844614216724436477247011217170367153569208025319515730230482856729914258082822824006452846685450723959850903196066919228156189795637102149958079662336538064235529240538358806017335662105472683860395160991521693115465883192286215395768099339338323949299299362829155984673025881767344120132600914572039560619376388801668440500876487281979889281363017997726548832397284458801669644514491877362352503242766061458648031139390982154513682140742833230599629458385718639115273802389305395519673841871289974081595201525288567319853715914828443124342251255175765884989735605726927412713009724340335449974633514, 4477416761384710794203596978575324653274590383796301254792410928289990401145534168971258007875843044339403745866881434566382629367310734356480893035286174425028510657382391378617193120964905656491279602315047794760731960205688200074728582077318876161713320092968715915094114238083273556118669320657012258036843280272164178280988756447428345753513498417597011257223342645265699727006343852950461893480338004676626644264558178354478847975115795471179578161929247580986857150123507112409001580100455212502752531485108233879248197247713348415965267531952063070148676356144156803685917894597971846841383828089709876286736, 7206708692979071065159904400616961722593507836537900372654226352786504402579734053203163760146383313528238170682451024185263551885577415755261496324119785572821146117304473078761870643239961781272908632631503074383879197347740304186320165324722094288765539109961122480671343685061749545752322281338528592810716584360488106710590057545348501326778207966008134102248610103452517387810006626168888860750330198019524961559754939236547102704688402400242837790161275345368089788151080067008343475522115042327684176044321207351612203517077779280310473916393719841290997846034314283393278990299747253287259707744910932539408, 1406540507967677161705225090169976104564245394108254054047004709970985103394199356556066906255223915874645192382694814704234006839795363931808611097384205472752739243764787203529988381617177266142286640765922381790105277376972801136385414770701862620322481959783032276172764707810736247064053214250445093834894366232148406317565498718853251497270312872587973274234590601200663519261638482166732911407189692160419566967502286408406238651690052532002491976533144388490818988098941324131755913010369204114872713267589773463760505155143113122292080203877817019049020008019773876253366843203793909507017947491102137648355, 9310494543900908934600341922423248773201063423074782237830898147106348926911457148898171190393007887588715888441423801549265412246994926111286542091708764738087508665649450752933313796099761307430733808467540019269564146362619045166278876623913620546176757207752172943861126598087495010429482084621931439220849311205935192277310344710148352165706240820459291138527191754885925681629533544841071589388954231634029726216273034042710159614377879982956995774771363211361653171538699046016034068461455865227330410742724695416996120081822493726324193962366069372767629773959700090420726280903503347144785621449091199698439, 3278034746557838216148747361042690395117260457269069556753145494940212901279971015035154048826617048262529572095211723156244488635699113995343804470719660062087464587837821630583394921657080163595714738198537602950769897574500246587126718759426989839149792776412454182790795492085113933269863756059391958041684740383423512851571530521985584220450404275092477363347693232003361647047832912928215039755287765113900329017753913735640486787943783964003020901478925734835150061178093485582634318220462290024209425636521816124223744595646264346602512925710205678505440600208465870720766418740440896422083697081371390248497, 12343407036688480280091218619067409894190981300330095107619100682949004592277107937537193254319723934236408889442364246283274047590311505318394324640161478379310376117149562575637502832027780837360944321024400116681774315002957716153817688130719630886849540762315007802379001702799763232907348958986642453586397484393948391508691046783295420662839546289420811837979589835832956187124903239003068054551028608163386560964012838447407073187474484065777852863494475161232356165559505758099191831208136183748229302420542137334902581376649229824753064404813730109022286273413798853804057665795615638020687765019828392669145, 2770526812086431176255398098812350744464057417754123359108018739501487160362189919596881058466335189473785889222561332269204184057852254786419031075297597983604530053404269795796457838765616558266062808100370260455413783925258231424400074854336431994120509026158266095716672776977005562906822863950350093963316794376721496650128399100394397980271380510072076218781803383368016528947558420852494540768520826184359179891262513149961198753342327936351166038330735336139828995305915420784050489338274910121835129488810376396482946557121482073812055426957717839033826299446591097908277527069429166847715663726357676492531, 14096458189230156146953952978136043503853280271435268994283727135983678047935107246890306753759146439086190386633111394139095834469712447441048327783351784744492349935263720959908244629152166482290667858029725195300767779990104422338047845925477749836618692401667545047365806196919368247379562850020982757025275434324592417874377031621859643583990859162143552160167215722558277429880478756113404598754410422477564111129393544275934121777254350558711389339620976023409735766816417156275024773371310575878324513901593157558740255989145673835460872668639352397020155834611075162316200135765077506836204168024352287364576, 1712168203779135470528292044598749024173719112506966121687728620984155833591542091657084914450190304558486865496250661115279844013609437992998517958065323911479174242740826960690060104760309359869598616987730346809031987907057172572960711921650986763178297831593646131532131746687744549504535815736026309126945970092215244986266544450052200795631905135037517754659369104751620977227121355542911094937006914253255763879957664807808697004846250370529098646161792003731117948757759955921977489091964365286181308761748158210065032229768929689726319038565734332532736464578706513765956223590981266026725197495819426924436, 13761215552618140671364805581836948225801377829856577875070754262879412740034419843388550644836563653516020903385906556450907236512748136254619139719652108885336290476336092613429462507858326792278511505682598394770456591767240779910672538967685132613789322873368190515749360502080080499151240194281717629749208348220125364257946870010951180551485096533635462089623961965498224867142801485141982776389959167062851782725559338064109311131278642644378215729238671475496730774767408362531202046690113774189795124255068261067832220459970996239888011310834244444517690929409664950278257262819542417404446258127903564569341, 7558582488229051837332539188307360097069978956965416411219466524276052075963179996252345334428822579389833494260759145282050293117022833592761075541351765760549276653843815168813624345025270238336582927104290310667218597120735925130162277466237347421661235744334399122756068577962631966896455856876969562329358779339102658138990043079795171548841787227537473092656005967563639809780407309095757745232189047442467319145873548222606282427687900518518236257301628782375814253559759745769120836525998229890747817352593684237101392183605411867137208545064100070473089291402656194713695553527188242266586667835779086805228, 3547542725376026370540033325405696146406260099661226360537994064117264097529655106479687164505614087152750518121277951399014623077218293339712685778188559735769183114619734263341361416486872015229411809501106708425276235036824108508130213267140971251811791338799212021427235457014273240598763135577405433694550632481622969175291100195876646029196538843785795093499967503420706118502260864250434057818567638274215885381602359693514928190693738940666795849370355337751512738079529664638048902704043049895015267808094731366946760063082188400639247322478886706877934127852839875206066586573676506821832679141210202116892, 12448734425402865799777453080811659487659130140747975798410709255238174664908611202987859655966575890660026426892433861410944676586449405759738406142058310998580490765822963735559634207628454671630012230105807922839072494114738735192835644139388341017326101415479294840801789875091881349889038586462813779139348948106520671808237635738739461093846445886998707663774493738052985241253195505492072771098920478708784457870301225296505109455105367642800772644108916282562310064666267909920175215179308834918136129037848058653609298873202689149912593922900339745161971758665131073942948844190162813386640670031422346314079, 9707049501926945847610789143910211076942624758568289322848500798374357995476947455605337845818284328249035847091294671461588897143865663373155229888712120410830596196613866361780874130530121709852769174236709362861349895084652924902991625028620868721547096779011757197752751149459717557248067408358895814928382664811294836351085935948642814572062995471295573677688713111211265995185252681778675606720482436519317448736207906260048359594586019752731985207260644020524474411859294588135467481504395226342385583873471815672758457248568104671300533597696799416164932852740011702561723040351673569819080182626620027799160, 5997859100053191858873883284317503344885216952219401290137414511728329792348861664001620421765351349016842096297007973732845665422397761548060845150070294143140932182813956161264094176662853120684982897596484556374634501659247106618452641826922410727951217809059801035349500151467949757089730110615275631842430146411395636854048524885953926565552566518033112023547181353098155683441799730243495565973777085736996523744800755366069898336644236835546478758561899183904313036410975326408627437687950466379233450415679754644631286437654373601245025504773302265999255130982876751709032824525058322476614743456789952670691, 2594426081824688468483901666578948937662785307268869330950954684436104993117692626026513919210329353605100113866759879767626329862322968875706939522926813344391055102238112923196013678792518571326815112240470396151182915819662977623574546490770710004517673439082147261429032455723695799337662683147884731475368544788679337235050217465938680540334323077978645691329931035903717407975179749469634088584355333889022629767729256232841328112726313556893164081782859928316146653709160272346236468091744182130203655050557041532515717562615804964277798294595214811259219416076397660094310332940986805005667856868508012775091, 4915469893210558064866173577613646679891389969808644368885794019869280383707910359216156542107417769524946049192646138656280969878706156935331827750782984796852694052607436430581378526906211397201323186249213711241449576880830200306070092389866829163755644003286087277586617346692674065426872717596445988381683588161070796139646988133571419426331585258833416159573181210963742577641584288413086859407058725133419670445998711061356863954173753302224553276783471558981627052053865201689833338063386690171988150624256619081193017898866171556299107233088680633955182396746097356800139979084696251220378697777099774917488, 14019248849969844673941349783442299840228647687821448313671465086544037575808658490029768180390178463142724041516997749176256777989941632119364874668639357503474436472795201415535514400893482656763358072760437698477657963949086036785056280976621499672712933098359184213868076262615871441965671453464763907573363115315321771997192473130527693328806235949548431653138742658566846271462205851184472134531116356592425014108965715127148069024950395272635702893943679829910425651237359721766862189661298853136243177699567812561868209056917377089724878550762924443102419280127210202148001068825994194775989262340286542954512, 8810315116357539992065165677008632947747872570193457415050316861430891332873367324397762386412692872839544009647875893208764137704827800757807415324764289920057914996826371541801013355130986469478668367708547355203504704148024187922274556009386676137468678532210803282601372423982788052194071701817915979042097974119422502771529653117376188233254683421970582959327168390618575806565657146580253796149321742774627227960987049552667360847536890622191017309639644429891572522588290194168395801531082133941276986015650075188255994723360386747869495454536281108494899019039395029504943467012968504321625648985749636242606, 13566232565927369447482829466066912458193479299374735715590529671276916916738152188498001451642299741339644716756693193929842191348686266382787878874261180150395198290545471198652247285121673427736379543398656936272726596584780905519069993171798960576210882146406380783070515574688327023597874327541558849184967902697304064979664395105113968967073808480395086944136441146369272907407412592249594750136817042836274017828652943851999975369742438496733183322513416947890518669387256048133435564552896602866928059916948793089480529304261673054147665320883540379423277038662253497561792706676031694875606069965313871021416, 8590921492906678896378420445351560926713957227235538265053303414637623106519316654858858680388567830357664016415076257134804156130563429717920101507029698114059204165065273707432915635246065210277830039845269775627979911051125405744916197098223489496209021770075494541663478261542816375437774633343494450499133211459407722180761806842476265953434065668224752490629180106246485805540777333260100385531830644539401536908161979087070185905273659584851355449083167196113725470070737894996856362343071759001984592265624880693320408861793780641188239219274092706122785333051271329826143776161781288436631722888934524712143, 8845252466616023879448678251562690798307329340790009403446289300428734948299486367974550804903303672803167315323793175517758107699690177542501460405470047925123289284821805548152764327132162938391297601486280124848829871635835226472850797258248484073614030862908180838665316447181775740068860205152303550776258476314449140396099917434488427784579685227672506088074676008008967426444977276431590245995757215902606273799733785103437128677746687835350950515120114439340578176985677978256130436741773449219681045728728955574588702125891036121586626887082920925427369782497578178536890902267158850606592265390865506669673, 1137291165032930263575543027422156939837541641547601760507322210788099249341393114804540475367565126297874372891394011262926032276507568362116041682906791123145963860747782780434853842463936395157517070582970141279851534734962006939017072929363013631599269342506763623208732096416259297718731400694820391635210104908594712802565934881456579895732802599800540636985415210241460189685085603437447571954509193317692485780785798564345530792768813986636809515572987678982486439698066166831441999557091648731249772813511700207392362426456879951072103800762849947930632836160871543681598410709922765452424345873142672266761, 13513807767221454962774765606799569477565617628797563912809798593793473406135664131936547232620224430610282821344483248505605078512656744567449743723678273285531981075631642729094345810811866090141147792047218571849337364726734729429055247719307380263753026740376842451566543861673563644948160144096970352503896388126112320971757785001231461505909797512610045271976200884424014399960505295234790475748395461970766584652942853007498227903733002061388463784848395026828319663949794486867351390469923713806579693493206285468341592628076399551484413083768779249301842099707969260635312935994500672232026066629544842561615, 1948173350373496741215028660780290545121514771666541429917214725389316516099704744675632030441982822048851471807242405077599493350468418243427175247112653693915364808986778291656831984952566832325369705328032701504808067748311315064576551844868622482806366199957953171785405751200403310222590133437462295047893406190658477172918489972788121602667475649200076472546741904907484381891362823762384549097066508901259699930842316143643920135338765011124427125035747121883045917528485256451642127282286432893144575196768052567166517051717119451092655584293158442695122635656563251551369324183388470755160900676889480516123, 3694379847580160611039484203604963835660815577208780146903607949016820301620455307554832098942049250220635827911567826077693631718369015931725158112022767639502401874238604575031054177437045164765611903236258004417594153719365770710448571596542798606004024686475997196663532850471968909521236218907049458255602816549703537446544375095785792848265474730141466688398831809233902146574662791809469706632432806574148439574004693509302717992998560834518126233290875236632494106268258222013605982691185318113673694528293186309488161106261037163626234874478104369474484793646963142312815857167880583154486897160702881783846, 13100710038542426656805076583687419632164662210545055587586737592310789510706302980620569264405360783248277996436146249115702798167955338955333171955392531672001238189514159298774905523553466342463867238918665852032567282134445151077686285421387791100175828117648344224276797822761123590891367579977648505787925172188700165152181711978479188803372382907124058265977868889302166458741425948623658657877794190304076049155895831078270339873829950967766017593828839707912214416972988262048443603583138939265185229104590333938863002633838898868175987402605265883284902740138017202465186038130073550038246010089896603725663, 3852652095822933778046931362644792467475824249936194071992637202696953764275937441277762654667214777690762208114969306581617521800729551998278398574402176003791391499256914310115672760000843705383731986117277642758850882810355767623252637387731481560395505912441813322993671475388814217476674556743472358938701965064413072884659051875760208196906937165575704341807700014804803838470804048651835572006887453120194602339851305565842770834144518789626855360453559616773550460338935135006398722235997124414678750736476504222316254087925756976395641535485434842907110189421731153061525831032708635644300664148210177301899, 12218212292555031547835220140121412464480708257422782553925231134369891943675767028453349535235845504946120458046949499186630221360908373098157344794716844167834796809242968300259859127326203629455442283192213729287881944801076151024158388298356736282178151885464382237605861076067430175912978814749738700955268171220745971180552595649565151466791025887069684021909595988591402706034234661782128769661377483754300601254937194594498452147898805698824765175568533810260146861201279508280547884607541280927691487674487066527311084845790997627666917393787232292294853237534105142562523090298337925617953336382244853752156, 2896785408539675548762728186954553064625555260594597496483215013779182425141679539276525994546526733026872776352493630290006129976480646399840212533092124655542014559467083615157785322073224886356616160266940654491266148507179710840379332033941096884956113201045305429741797926747173407243011050376917364885268193132382549375521197573595599907206875566368916510104820300985545364809233900524588350980968931452949729987917173828548392848659623205552703380962067591196034366037954964360630556952338386795758504508551601840861307828529037576771028918637862900826733051998148235254057176472218330330542051600289559575897, 4495214777104206154002530437474094268471277925222137381371536617146457310482279765513980173550446360598876649316227696557406548143603913421374364361063610474715008961404594966508667237635129178131351833481485010497018867746599052317793997473234460587534251190348065986081141459492732515137295209456934190611757636902123709461016061714356412413273948964326490306870133671246364317671243109642500307879843011279543764710847996925583379703383959543938208333235542236273305015713908444768889942221054292710264184043776812173569578002813602054202917870703910841410711507103553724047925021917002039921756046159888890242343, 5529844141894489844254713132328534957893455394146870381956030559690949307210022357762297743046411917454423382726841931258021598036218413956087240641403304784892150704501610653950162200496671190581234617520418780867840187257266376752917058798716388117989018362837863463646549984829858277851522339991753548773077412825204870946064236649347063984059459248604144327987059120732967246970879466050849997423221488498958998022596146739964376649533271893578633685987893363626780911970270796449409294393117570269554002816733489864019268355073109153801825119316622844904957496279684265904320613407282563631194950599321678554061, 7657120011593963475946234623666818180150961650519952898501728691120557955892745752375264929128113959868100946943714011955565958282126911025102655379200591993662103348293440973715073161628485200332761042547041328733567593604673037669433440663463341579391246652347207071124906384532734024570225933751304023025185754759520213532405042166476618173109991699562490019902979197149651867592793719646127934032256819020659021546070547620991514823448630448275672919447588368582427780359911165401715420526099720759990169336527218825816427599139815418919246745162492106819492298023950847447819932572883260255007894466674329361344, 7835961057263767274626348904955520141645979185947389774269597306809207190775736505642348312684394821344823461140830983808500621643342216042457275017803283991450679342713116864299640611452068690928845633025856512926165365432838156477435563612081555322873080944079915413399911270733026092278436238086963557109392673786993705368957556239605612735538671271826473004961692976438291167300367566932341740612645899969043640819289099089397355843884111614614215048650990844491199723349579805965527705442331349306541289746502898037431655892065491880713269018903996580510701591196253261102716942871446508193647037933334732964997, 11353314051483515551936821503808408238917055051903545023385176875084703551185642277274491393259077228767015423411422895545612938760410140931726216437555341695608783339442760329444053899335372103209133599680877521674602945910141554992545106225892908856917778992959308472715114250833961304535595573009941072248124379685113266284993666385963999176103504284892574508213956742303409090941635268668421005285679798220364234297855905686714654509693459202560872442211131177119111435437721347500959086853032250422784767654803369781417169390270151379541441103777007520967443810986726820653961823695262854029921638404102255837164, 11300348163305588274160436547736333822436038866940587285270441275614883284754283320370750755709719245887699367454997730295274109011039215723919851775724441780200988412837161079112304869844550997305826213526953804022989207469182380814744988487884010567692234634922061173308127004484122429884803927323682178308751205177734801549961508262272107340988822886855775589298642332495534703816669972689483902294731218076230271070352864707092010569575760655120073022420539618287925845479797673381713679165744928107426516279668714852362467481388011002164751932727927919142608616718594258408124871026789188723747022229157766627443, 5317190057185651676864655116193900175661763244958534732953359731572079314524983049850401656789617187417787771870221219056088862989571373026556313098099819298777822609414381859307262738166982542667808093700955630804174749255834411470144685601052874799546197267678142560679394576126742611410003931380249016492977821065715811530654813580269646139782731134295477672629745945991295821444488040223233184958860664786682821891554183706111918817287636264013525344373939534799865409160747080395802331258059560623539475444446225576048693022987972518801389657445288699430859371358934782526846715229174686326090248641441165875234, 1351569408956943907077681510659154696810675040858254191737287684344586639808748013554976975315699678508039390004710684970126992915073819300605817348337891646968976472751425631550615903539712595666404511832012777418584776759248226672826196055836363873821886408897037359543975538767623182623977172237539183729287404239021668169131175456354147253682981126254083212560811557636523384973513712006207797352328894847773433068606087660515915702028369887878622559276250117597373477548645223727125970141178069279030801782167387483388010418464128784411222628352130698190127998209646586643490939906954959363611428483829556433028, 10921155881652869609665933205671338224356780472897304063083088889395938285473820135966825870739261787168715605583849488620086560521961625404698735302670052577374871946299656040125481805780330940049722259711244723584068771100116710170731990243981993378859663422180581706072432914386888707243294246638229194615133543656672796733259502081107035172937898893369702232471711720189378730075176225250768457999947917575898270643612924009871627593078484876879812770142959826121397131788658652681736663772835841868529004318753648242818500239546459789717929162306194223109470499921811566277847442692055143552423960982671888751379, 13502945544330121506245173092042602719766206930773452523150924564875332958597945215168133510321391092767356545971586755777243297952469106049447764137047728608506233546106677064440830448398774366226182093845650781903349402158336953063244875660026259278665460828212275544396722181934080603274687359335988287104668239561438071241811193042264856959037549464090624061616317805072700627614621547894381935040497487576398167244146890516899127945701243310632155239187420953687229548788471547600759423390594893411750051114456891765383337505833298108837399234279913223551265194595125141315662675975358154242531260810721091168130, 14231650934919609121953109270370708872555201995443515127998942284850419568858465731536071394998977616471427697545958117273946536860632592760071037733341384321908948852879109346827396361633907260415165475853757137767266547391778389552184779811336915969108013908616580478836785403185633675530106122097763124256213583685689491805064349288059916736673212167503613852350404518261269779138480954340609063427290939762568933735620800882480424824832949022528597626971347503462509338793239732692453078099553812041792853850650141998738223246428431372094314584688540719081949201342911364450505320979057654482934300452734551599338, 13837418302454084892522797335103882033427895032680730811213223862487574120639067406241863974270233990519761211692078291210782441478777105356669102380326379603233539331122513856676968070547716034121504737702105976261900851239795172134868824500380419500319519941262076160352363616137856110414836765515890435816622916246814377743475863404845936430220297072299322330323625455428505061897461790631930565298547689424901493108544592089288871735792929202103888379697690511946647925404395932180911628150445627209175764441185475737967001489490786039614683936324389623415872291668667341635078533245875450271469849901629204612704, 4826606825742745183613669724307005114089938063034771868288853536223347861442719319224101398198873985321317884008393305616897848682687125840863827531269029496553663250412034525235773350647383821293995868411863930150465605483040282959445663334461574122725051490758020523941723739367003223720386011777882377375593170199823885699392875000437591841495139451356083342813957838532671891265715389443814035896328280156649153637111376957900077511951721068701851956389385809790287728109415651819920032339081196549030990744868444508030312005305322277216079326253284788009856168829965267354792549688471625749195952767851237888322, 14577251763730872959322025543586865626024589400647174959053809475344583855789168067375055135137378725494678299944918789660016165154800312109195052355388621693789524470456596034747697643944759529342335502182492484834506613840472404959962975311042052061666534519259264699145847155034791815840344028433462094795962999513019646479230743789951043280178270194109274382138393863442700458004815721185699070772279337797880053457400118793144040808280622982958659775285783233740387583635993137157139209929188410216207595048167634117973473902740296576844540305991658168281822663668641165492783220189994969123953846621227660070012, 7927656852448914019029988246629498679715834491056307307191234184794128103888816458196244326858496301629158932084428740110413350512112605067846727547727816234775333495220525913438818963301152668799257762039399506422391741752900919697727557914953602299946994881871869901590151374381698988415122380710230574780363435968271944980739001099085126644303864974242000106365746821670856713633261355487025271652221280881321577804639587244700806182770134811608816852744072804911532871960961250872581559875369556450249509627662381155468434999727348506035646982224697868190104727881259222186245308925675604700795863253835392083091, 620267600204153619789913807069167972459624845017553194754290581805039245569964870154616681838572640748903084224563886870256005657735878377138304137414743654138255294249907263090403392260981339752190194701898198761549769667021159967332693229580963785394015818663518471703792050149942287773314998975243045503064784286825990459893539709579960716309697354806647785917842237864578653598802120539014404019516063097343545542456756805063374142033550173121659779905417114395576371650563849639028946798975830840532889487882495816135233756810107804205685897554912972877620416717655595471019604445655214282074628749889791010212, 1876943923808353166443581356525290571102727135983759794091988352777520439430021288068363525771487664630679210158670943127184093293933666992201491936752376767318101818596057505575574647863942012923102457834542708922712464619871850746398126866884197445501403695717432968230536523409125842896173805647175173867517793507330840615918464318859952675563299324852165192048093834793508355204862219252055844472606290065921721101751322565362790378071976944390410775454096478071519378386836689902627147870474322694362268190070933716754662263569229449636358587181594918792321240332665421132131015390358202920354015102863093042570, 7816938508321678362339733437997629634768395580897485874009796669382990813724915718170590762406061730871423236515614597910082661744284433537071540306936411790345785031504146659345977150049441384547974766738958003383784327854196431639822426431790929672920085485598626222154773024153105510307906924683427152750009013785096270540026251477494199927808222541688107954382428764977629578868478745910807865295699852333143727702904721880943045067549338706358419092691746715008435496375260291090039835422606736364900019708671387881059506090796280008249598328994431901241994966560976472709885106949228840289620238728498820701028, 9381419320085926353657420008698841512971503473905218866008775187092477854627867083679092112014289346743550661714177825411964449494668006051549025749305394008472976634548150288097034642196974071195674514354193546807323212690152582815305876911239511783147739711708374644188548751287759010557736296423900710102781444844323066741911134324379267727902289373434450988412065822142731230646521039587645079083070916426619802881027580448274917113850218645247464301506815941111911350708523543353162473303473480679409582131072197914795747691772717732609521478154429335418745111075347509187950511780656649168304663582914227601858, 14589425329804367196377949705629747274814891050597512278986570239696565260482695052935875286037575810067731845542890411179041784202125002477821774025633172972643176721169592746506762705944229980948496815539746464657961229153842759614544401114447581468006411006507546408865865467186141008775030864379746995594162447611881229292827542625600330698570038047643095497036228556426981614464675853644275271372370022698317935486251627081669433742324307720383052436597336108548757455392736660860945566189395073611140650791219088600140743378366775098197925483635128815883227449110735609844753017306712918725490620586658156506920, 7638932262546943160382012150762474443490330224797410115006526616212732560776674766863188274450789399781159095928933339188053911917648370210631373888475375730791521566505692721183697918167224130890467697198572392238845867732367628119931765311341466807633986197845789521585443263148374109945159143958649586824908495581718696702860899364712475019905503426351159637646588179244245544925797163424300190536765884938448388240874977348719016431562431287284892218473247913920489687260575076841033925380875545540753217443659287176653308753081302902543624834743144754553614564742479100096602045980008761218548693887208850847358, 5573162790461938911256326571551089048835924784711152773479398060043252770534616955072221062550672045640366084539155835577120551419676941501624144036547986404818061247612944468577034879556759542670111087395289539456578207374797247228875141617254675730245913746525829584752492129184940835767437520993868125711052439604778800481870710546124783589359069908767219090037274040882233588866061138879189978383426720524326969044031180365386323600338273861296373430538486341285778907150765038834490958789670503907777871427990359414353773311334096739477799191052557491730927704843822028940227271978585948884055361256508978404658, 6316989328179454287926947791936442104657384107224109801362070607417193232159011157938475782206392290081128330998210277107800922524078921251053626340119190603997513636971902641271057303272594828645241990147902212213085402268790475875361301153951109462664705891022098824861141729771714967279129245896495677639642395437380836585586506963423508262822246581947484224202697871588143693747345262640022096022735797052817071349963152291390760527780424713128850429740414120686131735874605803334505474698683080782887991502550241423809893608712391603846386528486255923824737060449813927199792098970478971281199454801298311723346, 15169537484966814509575612733481798158754527049470245280839385822863057232298800961021105733875949545327020153892790791962669727562787724265909068925074610112044015107429166921510816972263389761468600154954950586673418065736367480879751590513123780805028665758058723184815380213822174995737365818448337846889751344762144354146055097839319587140978363242598404389657459367707428645594337217906655774220870147286105403244794531630632730204528597527209561073227068752015840085463798179002702124719392591205376718565003771669481600980492503383677029953821606261000556817344592572070467939385222906571989628102977041849993, 5947593166577364067359008003762446409468299168106893257045139526125692496633332614149966463386254771703902406475943285117899074740237093496861166392407741426698478874705803152064094973847007740596658716313720991658881452573261540267297932676920999050387180386660288547498933954229699792634750080810467597647931613586692444314446628718513435688160430846129138818679239139046523291289820137665093990570323449045644385574598452088838555446847085627765507404261594462513019538754477136919625761915714830185126275060015513857182897659979081896524524048163573916254048216075706792821675071885843851946803121640673632324959, 11377205506539563915983491650452022972872521196892589677191194260942374676469409473620646648018418341118355187991400998528615474082650284069025006559284422003291425760985298287978678092753754556207801186968445777658396711299465345658445050414993138336124035663319130102368938598222399419847969615678113890875023809014542844328689758553531859366329506023439385670738698110934976148421488833153972680280833027746973987933676057416015100520640122270004871449535176192678030314724463276458632330960583518025079732002231708356515969697094896221608046151798342472231592689213650455163045489302277352664936603799473037171028, 3067977817696661677415228507782430971721019126520663151902677657453674389847032503292137480212135798109203592140880362423499673414069537987516086542526022276824959493053960717106599496331820903492710360730873460305342950427378740560338687428924344388534591105670803945873128815263573345158205061131667140576353687264989736125614597240700365344847086802098423652159952879298066091846053275694416001758877210174119916495877835528060119258365983302675668351877364801590528417114159152650516002776508163150956125637238621843517207119296182658085857168384288561101637190751291008584303890685546113436333215955640252227265, 5744067068969497658843411627844598730440164945514574976220753524342999318226678139958499226226139889955728181400303932559928894797395772522655622280554922836832123047145860879608009762356295099371646596444623528540713796692598948149849613099140301866262343669578444096542870678391789363745552874250971282391308514597390785723706393998021553235965540364470176056135884330700114907337197140871073039697807291758898583928990394134368952431643318117512213097357124651810145781072260340011499623163023369647891390437826039023659642692307074831676787248948927172585803689800692799330692890530479934480800096292571821266038, 3728013926543126688351786139913117272019172100201251541493625902467267361319322392246476112481477712239677919152589385973277868390170656320700777782394012255082253352988640934461620526573375158851950428085182023803190799750686288302229863419494406196009088644723761771104502008482808054128084963090020910939807751362720378743438771185755244414851340614475705766206978173067044066824960602032609609605865884927087523450593790603174231475805204574876728307375579867618029736136424028138242771922953386426893273035376267399736944742518495516758531464958711014928753257047050886099338585048756267128856163378312055863300, 6386543051846906069316411939619818474700112510026718846210736801894291572975950393443398430550327450073831373592910851141819281890553083067488544518976119219798965474991444478395257462203479880306667656501512596509833246546654134192958717882506145623138540040810173742865255127744893123164118959892588978356837745843349796686892563879662884844737740307817160214750706073095364614877227522228152233208047373175993555969640771669189465212220970037725171499193598860631796397544923428490353241486544527338245796316802854155142040107026911480593831160061645752260923098178483757305941231517659873049596645667851210560663, 12810054833044488599994030592725767479471644635209917557294327535820424039565282830818401148163021009453145281382263269016465472076077570794405119395660978616327120612304144149062733931579517936699819521488270828771083039188018567432770854279053126941694719685509557356153320872633156168917804779870820806255075217895948655028342272243709463256186480784902573012267098198781616279706411836413710518707032425703222517382232793049148183910088016981397827583087625659284764260751772939842006336991839053437836279248649756882525183715232259815591179259046327395571253782033183525635405420333996279872236030648379476766652, 9790861894178265138649329957975634097004074085609830164719287008550575324660355068828859842461927950485013538348281063808609091900888650504159020131299724939490680445278083990146020460986668072743823037787979054203545372281478036875112066978495243276276848502702351824832483267450587584148314219936466464595820889646540790610171404552612649566885011482824160582569956437449968554437751076495940547429716550219674616042803918176460107673822704177600034220927583982607928434690394336185271285066667863383571505565319676047286936690527488055878794043818821491720029450560136183322496274566147648326263098740876535276226, 14941928582815067425974841172190574444378239822879338173338529260995627110434568877639861590590054943779607255385077210838082025087159368814341551968261996455810115010305194881702969563856839888616117528076294208230476328244525725711451130713475807878941722207580830194267012587346846221365590101243826576266414119248754405195132400233696710187319451958829752315275085866563135642628406846838588411688752577422480982252484661298424116136737484631241981602956131376781197322193303158443968527005443683561826196117528135260067611984882324014003917219138211001641448927103817684481070094094312702971771963261417991597129, 8933941832943017774683760646724508907623488386232262221607013288054572556813776780153217640078669875258137020067228202217056367975764654249354514924648225836561085285058301123641841401430543499351852636063650545231333543938933601359921971539861391300480017844386840212860750146278957403029099461377549646187649849626604094799234287495908914067451661116637174857305934937242289725790521548213794680997519700870878304639389736411222025671455280701740545209723805600882955359665255810420494789178019840670932016226648021594077995146011383621442225715071796671077500864299691672137015425758710688263148976286208742262026, 7189531691622164883663509960181025858001028375280861439878680235525305787870080796042295254315145269383918327594206202552179996171515179605428484916075922713182971786851277134555861370984545083669895591514463050399485841684193344210697147684738962974497987841410850183336125554346866419938469564581022460590835273087019913861526168692366943084274915423319915776882689704745380953526045417912822776241201905331045806468125000892722875855774206528891957680476619452424783749131897935438670356985924178757994905405043577777127814373285763420993526142269793013694362731021567336384732544481565852640390672715358542809537, 6064552638802125806427451167589199521889900865354204125678997956711139492800749589314218614351469251844919098563755809578414211752138055138605265545669041699917824030021079067848795894867547448915492546654151699179563869074024043484553677101518155583619787991865231413975929960385270642023230607248186500606941332522981406294848203752212684946308815631554104600364896252127457478614107222383719185125162890368509317752263574066985639169451449376089169187856689369444588091946263358180271376940612902211771059112415603631270736667411360365153432511846498195215815173264347324606427284468915133236650362977545442455852, 3757672169445264107971423071814182131286130661397989225341545237995405450632725345668027136571542345590762577806221650654440813495584710638745014412429710851373424305084991948468850468108434785766418588531770782872101548942403538716532574928038534558321701788527663676502191260908172493136215409032761553895601511343263713635309830572671984903006985325600402720527475932658255467488213990237822064945848005468719912465872148999423080152087011892439228331043780727161279337197729038247510658738147934424545004369009303555100707166604122283802538534419252949325022633255873513181883152614985949590898984093998647145101, 7932455482274849843856157373454039138379926112646091062461473879083725905937313647324600380583326087481913244603563704633383358340388710872803906662240438983902137177138130072365465362910571561699547260362911924118694970696694270013978038868433262235687643165491418213006433193198931513526352665462217397612407014196565462082268595520498079619361864807339282832715085812975782031986461499566087134476693937597656767303493461606062836333466963564390635712516027271045400640760434116765833634778851636669957160030537847948784324897314979961601315370212303077453007997291016299947132405718353297358905824255008681861155, 9643055526998971723550136917345820148408543416998860032745612724628548867044560219596393254094190952074352612222895431521931683954942378758887921276127363349921967622249056182308898597826254757140529220611698885141373840347934664114563429746094308393425380970188775152045908627628205872142493047220330353863435462580164896929029103159191720337770427661149456927984023689170926019260487654653486169259046619471976701651137658851891431670548992838484919486390630400394688398919941591580218963552241515606018292491179497674927125233215719232894406668298041893377130568935915747724926618867327795385631024828666992247290, 11991291936384249369299698960518452849197236702705046670797230536490646232574266823011882047771871263563958928292883359281150433470733364761531682307281015423233797307425849390952418769772954627375847688808019097402958253279005305321654839119431551961191267150730556191454563985326459151647722217475140922045123105154751577287911472133757954746059443387035699642090684900338481407677643564521515154732780059546256650900748321637805701916685766926209830275004462112351935656979999855501616137571087167047200300961123034119495151020236218531255368763429034677260560791839745496161699745648261310859430418928259838821877, 535432114057863526721782434773060476314783390601088957460181851546342640883254127412123051617696298084533237135258831964495787908557481727452476303462875525899468898542147490380334856449499058330928205011270209234685730723864472225095065307769448521963694951880858407717685485624188152301124295278231651350481300454923440559384718572957516483393533015119553955205313334306421947123551979954996730191124604715274005878039845010985536421909520112125609958397202341572239768413481386022216928426614920006657747275803129737848798924377678218828129407956211537817653888774942399161098139151280345135324439924390647578447, 3220011893134401371685402508709570472954321680147572400748655907736116236949239232471865184735935060986427421735874400382323708661778420607205643397120625212149915957123206704115218408307357635163567836539740291889649945922083575544531026407704564852193567430337899525651882563251489935659434862239585931445386182900475111383035782777110957999260469336596351264088257604776954552644350647123373029487309225329173370793391298008274549644140586551594364452972663976771502258875569895740603464426584624196673298237363374673926922455688177544649002555892994236167532271023243983655761171318293792377113542858566178496099, 600122127467611861535587750203240963722874764507701038574617649105517093473305023944722040981050907794894905212292005560707125161493982695124762995975561806023413711807655068751569919597884466936104514030246037470131236752735283648245689269062142040919305342933627639120706635587037744802907827081604673022771273538534733872678332193744014523171816720033663200154852989866810664528898786921579631462648683949136354120240536506040625155114361126304505311924724932810624031883431945425014700535632983003379206542396676369759375253708692839310942501083016757146084672651607696245154073463556817920222804497847164148919, 50339512756553218623275380521558565448522193507925069318597771693335727558645505269279849795689316025903371638062876838537481809174578837000746975150264636295515544549565932864086631224480476618397606098787650961842917904322124283224278003752654627557489493925252640851312485394751458689570792104787835243865990881912516716525586110492203669174057562631787289272078652486184361913997429327414173045545135047551050613272877244505569286519089174641129008448747456868547415740807138821776024579954821689809965762676749324884212104363300094487322179875649780580332349914589317935624904109987599308152755760109143998751, 2224052005319063310384833424571934114400672558432404242381905814511179810742030560350177349071409363750758241338680395569734118269781584440271895990245604848943806635157416514113258827374454952809970271386110087207508607390430297238397541176592036684563957770694483227502809589049390218716580287319602904576531353794449649752291506567150970839094403827770723675015315212078408652075616795416368705882795103845032693417192286782410109366855505313733288028208468270805685771032485770634904973630137084989377953129799398695697242170165528481764660518305154014425898879629342906389549414591962229397062951169181957613772, 14275670029178714903570161767731192958220334072487644021135501546154111018394507711784102560675898728703551625745188968783353245055200924545127266579966009234810166523868529387643082883396920063132158864801583422164786381216921410297796749913731310404282342028039015946530818270526086443576375122234693984977205437699084929093584215611860806604287366917946728372311689443012961954819905719979378291190426781986119706110863100933299963179506166416418054362453691479338228849129764521228492880521802440955679378275011329235311197539812660608180724223253704604510134527835590821059331109458744742818858846356253593919531, 15185267432573639872076451132381569108753197506130696653478204442671128758434601622689459772629495431846087048936093224045313962183756777493423781016880600479033189411448283857759357851994434290310594725722879282332643289647226135888077467069738865968248849760032499611636818992667031741275200673818274894399046858443812683901145769338502611405193937143715627051494420688437190439484530572665252784950524954193813471431595615326555357362633515516288947994386712464157832892920276023462983548902705721189213696133154874467828534425941602843750295170291794415853195885281848637800437396343242095744915839066120343669835, 4879612428754295937996584844091512342716460204385686317553157289975002514620577593461029415861271197762441172875278234911205482000756498339763036950624564472636257514773519763666991573860894276474054415661963387082148717148767197550421064139240397093639320406464471250749794667740342232727466890999631793412317216638922742472659285972540106866101582942494555088578850040519435163083990211708703743270478476125112243254909428357352375797466497456095306901543973138659960199424970345513286107351069292703979769192976611096956001669308704595069094064027759052255441962743707680906571973207705878800116890860845938365313, 13435769058792763769626800085331577749241311952820804865145669377919625981581930666008825328077571148346388301555592609695394682396961076513311737816689884586045473971108663893952535731310042327943385167931931292074040099579338736066141894121948781791059561614055815752555628118995199961572248091297363156939872455241328696005013936781034371134327057601448521193269957794508387807195379773273424271775456314422342642329396116104834938471386558748037037194676893299569297051408737690766559250385415762912771492157370721855236609757206633273674544752588311049273127701476107995180392366776959962073751358804453934264822, 5542391033984572544309028531389422971749386287310398650064759146056388139061239743350966248739512828662896288019520288789169620634070690325846524902738247390553179708695348999655663004248286927459903589852764109482892918049412370269451893429328376067510710716929724521128037362408634829718638989649378574944664300430926714090821349770630009233952908142218164609020667984529215493287562346124317275409239431987965976823163648426455033785427976663404454759315964366873174968697119869398126678051558414223741447774769077630031896415254462323850019653881007037612035431997632863402935959031120710934676652292745987552564, 7803771781604746567978670142366176211984105434265577521767049566379964787078616070698680678168611174665429405417360935498034238714028357563441325981892258003864290346670241911746376332239643594850716369803549246294442214035293785034621922255220635836077225479352277029220291866614319421647173230321410480286886004486084632842728845734298495565712055426737629190015118447709093852567572090746746050779709718275402339813672109898743347121206272493894060986200601346893915910976840657529593720977557535780309071909928945656096643035960534235851024503316616061477903387540114187195071552617153258585962762789075414254915, 14550724562704244944703001094464708866118583220140784805885627719365556627988376278754707689093972969349178721660857614321368932723144628948795449510718735413720101787664412941833526358101398817245437043857540957492731059840934120463645319480246514699946076556700094958280111962658342779338550641756163208113946017431633955439422681536586526992494477394950159923043083987374929069647572056298076586571294730893656686542747475962224078283620769820190726515470370511343368135142558003358091412606728280151913025167789010638083795849306759853030145372320263447336943700553613116285561830879718369554705010982278703015146, 905755239615698046917022704401444719058830696106792105613543070490366423294837441201806258289017784280371737165348249248540854504265831516849018277416932866299336239106708674975914941807666993305750374858829476210791273122096544472833319114105444370634112455342146414479012688814172547960236061374911624282061363046783557923827320816913212999080823079317544299850365273998799406681848162954685240532278613419809460514237902043544840643860358949307003764990315636348667272914654500775652364776790508549048920659618418289189390271348289806007639874838125860129786731187213522265469446766099215974758176006605295618767, 7915090956224022374584153035329677930760602324913366274914099616372530014821669872922029199280579673718360049211187283454036357627703010146787272540387836186310970471921562263287618743609546828045818758877660800866975304702304781145943396854041288746412787575424739458089628221000536116492000890424249362235871273868021938168254811377658319199786374987384702895144976889493294593285522270424742879586162359966454589990688111496105717457074774054811268352170360883117172702503937008625176386334487901762750645956269186658184576645311174520095229077940637672105837937568215335574573338945448208463183181650200574319521, 14763393385290026733197984451938251764500304950949477862517410602831207505119757773656807829542172390446444010290762471320179908128187311008089883939249276413552270059861673891348215695607497457666677564123060846133272837927596708127198103339476850512330365278945869327209254061050089506436848446321763438343975374446912256970106369447492988471712481144621850019093302619134925684479372890232199060516056309301691572273855120229597177989013483276068808539109370117444484829090496984477819390567872497246027312176918926335452602762312180977819584817205669476385354295783330428298399415009867697107464325775483795517013, 2150968155803335913363944655799048711177756024031497208561219369184651823411896398206103053008309258010856227320307405212398634256897082660711172072445776859641396686863798236121046149607393813988895924478736961764232731564685259899357186507477452666842292679644633002246889962808183301328196650745647952049360117868327788634205413595767393904381245184639956811757179108236180682995963146514385252570925670308261918433799298249053395672766651837667338857997840793025021032238040620474800360217807228451120850980707687140925278309225341530944521350999129746122709712685871266335998732036361963871209292594802524064101, 1621247785994414577096336196647521349817049804990384617464952973203230306307857922207468761232737599901164753791285580679538889344111919552515408202260470616459201407453582942612182465243477573071487434446380140259238805756369920645142256679935674418413360056180189060733418103577103670612138756542234369027316020275787436503010486414069881051181338543909351746458728413404815831543169362161966148295895116811244087835995649375765604294021158802779625502233442241495631937176464502661240716265459140132115036716519930252160167771008304418744537536306813506291748023693113555720799359629144460150230687796932042872788, 12653661263933313158010445295827911078052091969010093241210145578155754878979217485399410281534812100929813010419860352532224967167431622421039500495670810206747776677024105707782070259562367678861613287932741930632463012385574522104482010838696309575292850982449178115041161849285350620692016969038794022625011172869473379878596332964200046446381652122309043885596860473594957796503920623875922190031007438114222058453968936876256694011647084188329681792420409742872685859056145064002905732635272179892966593625002291375760264116889957423750594473358096935392700461707675903098779964480706150298843472016713620048481, 14868722585432620007939501680935571162388681421829578513050545259008979163047733359580356950992297756162145479919874655543450474972783321515837325514292960384800177141171434665364085523932526547918297799064135332986896875066234825475731881219999577248008180494593013499536466162681794510605863748906242245161867234483003972786162175485163654352303622782325270691241062282845984054224234236940136336914114004334651661957510036702642949240274854106258897602782749325959157882539520944440616382180589134596567236254739911284646573457452256101251961529913173624227884785142791559516096027018563613676698997529068628822733, 2904894244506373336700029430295136170411787536172583592934412543067342684987464336340696718350799815451180187771580284274606287155951795828004750429529935433611907342655713466726831094359657043862784742242155071480001583543128061449385899856663521440050916449392455867135588784009666418641011960669211873711582367082203767946431279485891981969382775078654508040570714070407148618123618606714381513626301740190610436677744321114469663101719306727782964486133073639902742507110277175711469720548065188912746589626340332959672786629839002745179577537221513924970149632442104756092464692305083515620327704751641094385712, 2311496682794141631393420771709374663788213994503027855766651012581376335568105719704931207071834360591533363344618424911627157460583965571525701960142929716584817402580657054549277944994182188715943759153621765610865466204024604777534919347801110823949525986038782321751457918114396449189991652197873390916863434743323122586527929217668867770082227439982318755730818586524576788420303869223274094565266573748173259299969551921482979793337870335831853130918886855205947289802728270019087116034410999353521654557806069182995651685981262466235295952900547714612846442390404213099933951734500758673006253643940947086008, 10117897844328142554868011629224408328585879959397771398504408610738842585832539484663480981437647194604214719909992685051999939838608686081084682835419220976398827848486553357549292079257306403769048998196611196561240954606770601361727287883238401093766508916929317946918613324823317362092034591318445144066546042427273019549300258380921594913902001986306589011965666788178679331145858966700881551785133817763571902505550341846611179695195498270739226440723926356944662002221523572560249339565306465693000039318230644995458965366961356285492950000214489533646952111481794205036614639206002533823601587340295828370994, 4587235939987152175190427622584103868490891054186671469570586151463960185396121234316968296966658157649490438346603705741652328121958970674137717691454750135392903767115604161170135271543963021530930855146085192790012307386121668276002640011779029154138658580327036934616621082855150383642924499744251880745845698583828788678539041126320664372702103274435926243115370424243252889712645839115101399022698426928357971647869985872493436862410636864183762039651239072627781733745709849370970612899905680068907832445824298091930170205048445061695862130970435293211407006758107672795911793737491509504926456944309881982063, 9734243771507223400094729866441249064234301630037137864752355688924381135451313546830773230943980367164348995891412212472580314086822048980792893434887515259768178572523325855034106928532755025161856955313795107129638991679291563737375919707924222328928077876871539786925901609947248420009157216012585857479775638683738435966114050922884170065985793065933136009517888090205235993284455287104589783414595864852228393012276776801125825410251453177409914255568146312776814719830324106891608165166295787305704926397123654471021855824974937129922447149099718848275610677870680266085883741199452851548669728989224343773899, 9524751900640364479498012309668638994370791138615820974704530977866085132715519345925617494448306574688110083533886745499679597773380168634659545344892684471115029107448937323479819452236047288512404519536913021005805700886162005889705833019328032574096034116927149229382109650209107438127718273416332819082241516461246218171832411347554172464171271404922397966941970036412217244448896270633582359944514721065762586825788974097178203233796669379273528649226152448864312976163859241159421272655047597802459138931863223442413969604232069832565562247016042938436024799287903457545760076019985848859749690917845223646772, 6536915891592978945445369842251656498817857264239331442302402420830049783465718638399738625250702336033555266286659420999658949721040058295705470936793472139728282523463093820651530965374114159399673584545608457695240826571324097122201509456482155547042374032378324715223783186052973928587715806499358745492990058522318345804530601506883208009167959005089483148880434858261422179323896484164697984638156491187655636416396929931051337507799269484921436422842504413949274990535494507570031977133420340615831153297111063761288062839360540272292814673668750360915516864560166129454693186822091335182502264904371159907778, 8763858311153858089091251038913957850703267839149826476795030913273996626470115696111847365469625965769187125066842162573743556870147225348750632232589385832850469901157234182162636472802018846126743882969651303207454919676503869442938104055296302254346374346068521381054011081656169104186107189142968206691320767308294152956198039626042980846365912306582669367631060557963086678191807496485935313252293213351419798785368621926603678401877114710179488096702539792495997898049561883173993589662730552278310429749628719178776133541261696625011729689561072557382224732997323017903939823849599038253861922570822322820276, 10304055861959903628564746443884079658351658243993068573334889760638463424891184889804452600302018788263977157330137399626142471493238810579422444893878535949408833748921231931032995043898521179338062501479622906064161406382177363491168948613310101548224936388979895595210747899639710435519855324578874416098445986110190998007657658033137332895083663322339462689653087716220505926783192851034210001478545953953772290490457886936536262123353395710736192964692912144297136701462808928618872742872081662561345888211317808837383489883198622178140403249909951015310658469409501964637033684844744097419380495978652378530590, 14726340382389201981076355990454933749444735863353274018300226923350606166798930510338215744409551071236213258959785941777543461416888515060553450080546945226599930884021760578146826190380243514334898926029752256996514817331888223212619376148871600388912836046683943461422881130821982347868218020075045505488203309838213572747025496047530186362804836482205802581206392014251998733184109739252212944535175617536446089111640943152520037225509511544609062905792894323389603110920435919909102123651652804588698116132704777230659415759240970896638436469245429551782628368860017693353785302248876758620465407470376132883291, 5599860591487561964716668210709891276819258051334913329818114435055876802859146828098080759330153387653100119476058042742333340356224138052040431412674919105182622428202100791247156749801060922968286951288889779970763601729018054408835615249352231256072020958589483732431247365364610622216980952118970314513316676713926958581047757755493384012279702207656487266731989010905367063579901512845112407021906532052363064361920080023604157294412015045566167604691002342575520496164358789503582587448492627476170094790170749377500688934897762307400705306084636357255443809776613633544032895760971886930192529742051400685987, 7284681863487265391975348919356990710834427830336211658438794920413778371087625936301280861476846527447690148243948914904749064651294882224202880958189781601006957746218002224828496942001862919753723795185985913946073098029587410312298432251663639205394865772717411252791851102137070740003594281594955971942314927045536689407992538538908768583435958187052292896998345905135095318114341622140226234431469947234761309607949627578172259127738392293739648665322872160581489980676455114901454740866994466438467703214080056327294705089107758941278308992503990002210564727054321740584996808616669732313919614946481462835844, 4218644104851503674908335618324190458918353640979450709174985494086644772693888285345167522531276904407777923519727833040474760645218964665353871865271436639445357690968793378067696265886339698761047867574581351892753525140266203868699974425144098602963165461350432213438525620306578396107551746424702245896304916951306022323518517263675997918680052333918993848772489417782953820606330445707231081343337061105927736500164328434626392964708808370826632373594538269317810596383026952685342820735431957139112915830275509992720289836507740847425382215602427538451767264337906889870491464577704813919216902353508958675657, 3672490596511566765203546014934906368981891296242298837341664823952197542718959857623660644000502506879446337926287940783604560248421940124883120304322804336373919042114401423441194422550605353143138286904783074470904252416656295042859735444846506089150768814937568090874160884780625373473660653610401924120876477675798543697640619115545437655461201340595931043277002471886509228395808759370374265056026024599676247165157846709075227706409801838730206264031201772589426254176886587455834782467084855973474182708429093173554162692807917064547205153992896789225045606490073915230867234814142192039039186977582623541991, 1280207537632386354095168594645745139800033256199572667391263331571431259341050067911945186686482088984279507592101929090568530563742757379154439484391303366642876649942104475779358854097707219003659617824423032733996209532412339358588307580458613840803495726952195629346638462860734997635900255432451049953558399424955070784426905987448831573109818364575601864657778702125662281705821672639181050096970500037835145175609289872368106026963689041126796876022753001062422368000963690325758995290294034719103020941655230530849890614499072659200706945379797175180592819900448774517610011420350291882830962683544583361379, 1712852887288208728850263360102828405532867981117990676104988275083835100154395762305155676788845488123596618035049120063817401470764810516234363195711980024295294614580706542069215574499299259546748778488278187721616589927510040339680492857783746131516806864166248748174814753552178483515357540746014581911497410907664268197848854948390102048396788624390841066138941548581656449991597764113606784331561791669241168463770037794548948337528295591533262303994768702090891638163379564489208107657803500264384269033874779467352375563064216555703447802999052946344733781030854695768291023706244504481654025894705160680367, 4431355620488982649161592962565317592196074246840668689829552685975571072898550308441496420304760549363267267015708985131070769668873215698645508024032418557499365274661957102501603200191497007292017973265519129480232872076410729880412556049422997162707500159504193181621350637358277536523148862096467158234995065716025432547078048958330780122712083214706241445610546030345699525776977421932192560015568960275308076897252086297013105798511322845558782544907676153848356707540415892940997174646395180426720560282342215294174764345782226301366466949655945763440960802301845483963562699501549284665051559641116730271064, 151880862766790267548931295384178655780310339535162671301084454000351564148877387201522010524511060176936135824065717736524998485756807491787511598453859426876046152155609330734232088716456827747028098827416498908259339363197706889262333376164123757801863624888709948235034878100934110696685851061820438712409402136344081182176180861748936207257413301575039067291144999442588261090044098295904832386037051479211241831251993693133979390359677388164592536832362964085108253933527515566044108717185372569625990349924960150872967742369156278005696911801367754186267082039740015781598286019935335260230154588146194474570, 9484034931276031132531963944651896350789895896461790715546579215176264719586629759948604137860443744326010201227145091634385183753289444978389776884964629188781090430214095938329292803406669876372175186495894744319714804810337368997181185087019639005033503349417399678480994901307634080924618023009074231824044105422013232607329336801445993122319744348742586696709304431718981737020319710085023839524741523002295255110491665519227510455524421206461155186367979774733323367247057775210143794465781289220390567563119466936158692159460076442310614834206342665950603105627872425864298849858951309156808082002452439252375, 7571925654760390482758163502785570636415340074376395512511566382090898408093888172845542299305123480557092551728329622043703281862222797484472838001769316090333655971518390269044280128908985547295175688556076050994514503756419730377240772442932139894970565925755864398733207809526221895028302743654815358965700847416420156786060644227496789803454837651514842218394209521547888532830641764547720707062808483281932421750470631335122609774959367466533836079919921467710939774592164364039670117932503074903125902581093889602927004143379512533035382317879349531360523514706795998894620784432184964950988980909595752363891, 6407242458564458605989587511182718985516094933911484897577359717780776739986097352338695025318316928131020600227581257631946183306976157385836796808768757437700457318945886155356522094058824299350704019049355567347950163298841776910197772237827631473999655276984027656436342326224553937882149508139691242015084311118170763529246433945081402134207122136801590156411201768445377350965027810905600921023414736267008464560948603367869469615355754125562183214690346459023615799680037125096284762140484819908754476021025094042209800734064256465008427694884056306700228286842316616273574024985156127411412421276908819046325, 1582973058630839374201016845587895187514184456338711562603058389464647564354857518185777707067534352738422221243872621546790913024035141210308751808035033403508675800690418168791480677811439800763140381805978683017343728549585793044134326450180108362717333856096542671222448578734360169509953605279750835886609990527940475390984025731644580342531087058939615733750763498609323959035000197342557541691877906461534234845751849332481544519994911904816124667302855836989182149196400290405533457661829694605590638144618216311896644287846360917369054788425992163463639937794227562814960298002860709306544428349686311404972, 8388015083753817396404634498682833124836683671660485453889705362279160874113976096738153723449169481885447222156217427509343858332778149307460784057788816852773238473735797196152562925262109386268377005832211979197341745235152950815021307336600058594016692701569536560183900809315167001507909905778241359207806264218465274232258300488042841612249765945741085272980647205313951530101418826813096576267892094467521521388407855400694081878769903840814458560849614556706982030343107427070128171143229655593040437235274621132018338475980754222081676543951773645671723305719447701663871222424115036651254625522300007239701, 10360941377589999022884694845551237952313651488092752234649767575644201444852340084975112554641538017252967970972957403469841755927828786235277889366377352903779354009188274474957839495808036815048488352099199171067353370582233123062854270327278611899110567041211285835664193384275654396217606545976221188607145656891324513369162209324704100876407219674076329493105327684033551137582360182876805940184081838609222513710457511996697851978083979112522791428711457760414078438660045777781768019100868178746924945090206469745588225371455309918653370882043866832570514299530747286071108672487459805604889856610219366804014, 8161901277931264917118321806438891982202459388170964941292783162817780535249918112011362767977501016796186950982925784123055737546728140139002974376577736078814455520715324277366410323589568459000202785717062704689299805792262230045704532890430228890170828537204236829122606564459083180369744253692448209028566213795360522127608792223090436338427386950676480928525972254897349872989084292693044025672191209560017949683042024981585613220102151330914603710629813105622440218241644321683880490890195924490483901102869498497598949099879463304286519916279176791887333598605029626783283403707240923608501706742364927375755, 3782934195580492970180553866690449168010554186676222377418642624082619622859185723632805913731884871238511062871897434982104311875969090082587357096919684332126026810464696214804435658699124624221912695831411261021231266007249592961038454862818925502558482993002316735563151406299564849453648995738323003174425196603882980739318361661030203486760444364981054604720894314579655693051996596948056646567854867442593477678298818302489675363637454575898939148670286200131667117694840159071023352805842073218091565232974675345213769255012314089478053043859999354934245816908321254655470259685403484121721732410179071909610, 4114288597820022391125749188593027331026351039891222488536665213535380955042348711292928818299649797254047980414924488507472673794895383345342755166338719529629024257899708879765175623019868958302420946489389732849538793053839443691183813115596740255056419155265900578687105616665757027809606575582356555742146088792494391267341885803290264524421594020107904982737546075821190809550246387205502119648498927900788485223892423569470562773532097508386244730162864877944588432760249428477514334185668405238153761731850875748256603557178354672438459988042032562814329971608812515437635295411468449565452675942774316206013, 2468727754756925819726861736190593621570046070871578606388696474245120115522326636693130800754080546162785192842832459057836867341368082934906260069239112961361692674650208597082199887350150839030058646994785607426625727970227499607119891164624551142853858271042540511609618146084904175770636709162032909941429219734872961413193822705315842015365285572086085647286208340120868212089861253380516987189869290785143340973734685089531458054028129325141655075320282438433328071745815943438030050163239166494145939144788889434940446857879823966791075081816156226809238767119154957534729526282707918484809620959504025510233, 5041583120384178574754510543688981082040786059980378870869528517432482880646412362035353568647325910788836773038302206401235636240338444958835100646705735328715604610231176333303643765405591811730634011257239004081881887737235628184117405520828122129872518662873327501243198817273583721212234131948724805119027093899639285588119846447228534563699931022861687089824617389295935458023549482716471562995496035039971509002778768230183266163952750352979536005821487905338801933287628096411437854970267226157338195424655395101974161257085648280057846927918950024081038726269481291665731476455018934720255596968609432126352, 3629978873963365713741293889261126305566884657878540878807380681141546011975570214362542948053419920414211144704219306412388357870720062302195338375316408028635651420973098109381976668448344851960334653995430945714115093796939197394543028081942953296541913643405709442447842078969949410043830044362615696580259777410007066198762944292291103029467510065924722224906549577127621285748840752548745135992723308600452185065036513480583509838475010347800214539512382370509794246452027711110224397889694036954365109376074293882446509512060824628361627195391124064476003663926265210359146847719930722568319452002284036846095, 7465884946864808816280400983921745652219229053919294972054563236224428084190170532445027972732697684793483179410804714564309726525353029932194842972851055112308571160969547308519376170012231811908010956339028345397423670664169287743638878450295116145909956614915931329721502899329483097078852781221245827712109449889486791334663673535144850500434760842655687896533350254346795876458494274878983729112135056763392168367015761802196298757300377011202516526172245534298113864704724948443444040718818888904140779015377662182720446432451484939660097067723388289241439328930611237639471279028828354169293414805986615310310, 1896910503688876953851471739495515353616939763519846984235526999312399689704270907725479920101085014190640303842672895668870303047421243574875601258804726531297952143528558019763378508736919158794601838339326290559343520786726493370550654638242868555375944685955808937052985027827276567300966879391153835453735899337934408695318353937022427261586766741412834930980512461948246300668891525818750373781239103216659049912060640276786074091742421383051496962688122891703418558216856523195689253840489810912141843001096981004337323881864785544633182926762250336752052350749110334631434144787663360833417650963944585434582] 
y = 136437248584749771882310599149278388531535057166399265926387706469408766646754256272579824944594286947565201090386154252642859489386692473805411897253949013507330688499956189228793511815053892879974238599863038816313198964134947169977378713887483007849103288310288698573564963610808423262228756458677190730145
N = 15208002172852064705513549049156125156229213752159018163825621612365155017442357321243997240694068589814280403280924059115680689958405528673283969584726875025903837971544565855345730100919461985993701827484692130096087415066915297046298354141978649627535608324891962634115164448150854962245168416609362554295547467846154568712738134639516660184864893586000423886731114509172379025554849606702807764604046562890333894888196970691461892191718079065215120535321387122435702257687877333759869565354852332910433540118176537491958544695956496612702255403127864825597702515541366203734967406176296928067151309367243599261047

# =============================================
# Solution
# =============================================

max_flag = 400
lower_mask = 496
known_upper = (1024 - max_flag - lower_mask)
upper_mask = (1024 - known_upper)
known_bits = lower_mask+known_upper

MSB = y & (((1 << upper_mask) - 1) << upper_mask)
LSB = y & ((1 << lower_mask) - 1)

print(f'known number of bits = {known_bits}')
print('Finding roots..')

PR.<x> = PolynomialRing(Zmod(N))

r = 1 << (lower_mask)
ir = inverse_mod(r, N)

f = x + (MSB + LSB) * ir
roots = f.small_roots(X=2^(1024 - known_bits), beta=0.45, epsilon=1/64)
if roots:
    root = int(roots[0])
    kalpha = root + (msb_part + lsb_part) * ir
    alpha = gcd(N, kalpha)
    assert alpha != 1, "Fail"
    assert alpha != N, "Fail"
    print(alpha)

# alpha = 136437248584749771882310599149278388531535057166399265926387706469408766646754256272579824337507311270141846388413460068357591608585943215991636909883491826121544218636098300792976192313647146944748229438407801334865956608317244973051161890353895660399085055691697783021603089766899505767068206163163800347041

flag_second = long_to_bytes(alpha ^^ y).decode()

bin_flag = ''
for e in encrypted:
	if kronecker(e,alpha) == 1:
		bin_flag += '0'
	else:
		bin_flag += '1'

flag_first = long_to_bytes(int(bin_flag,2)).decode()
print(flag_first + flag_second)

# flag{y0u_f0und_m0re_th4n_s3cr3ts.....th3_fl4g_1ts3lf!!!!}

Speedy Signatures

Guess my number!

nc 2020.redpwnc.tf 31452

Challenge

#!/usr/bin/env python3

from Crypto.Util.number import inverse
import ecdsa
import random
import hashlib

flag = open('flag.txt','rb').read()

C = ecdsa.NIST256p
G = C.generator
n = C.order
k = random.randint(1,n-1)

for i in range(100):
	print("> ROUND ",i+1)

	ans = random.randint(1,n-1)
	Q = G*ans
	print(Q.x(),Q.y())

	m1 = input("Enter first message: ").encode()
	h1 = int(hashlib.sha256(m1).hexdigest(),16)
	done = False
	while not done:
		k1 = k+random.randint(1,4096)
		P = k1*G
		r1 = P.x()%n
		if r1 == 0:
			continue
		s1 = inverse(k1,n)*(h1+r1*ans)%n
		if s1 == 0:
			continue
		done = True

	m2 = input("Enter second message: ").encode()
	h2 = int(hashlib.sha256(m2).hexdigest(),16)
	done = False
	while not done:
		k2 = k+random.randint(1,4096)
		if k1 == k2:
			continue
		P2 = k2*G
		r2 = P2.x()%n
		if r2 == 0:
			continue
		s2 = inverse(k2,n)*(h2+r2*ans)%n
		if s2 == 0:
			continue
		done = True

	sigs = [str(r1),str(s1),str(r2),str(s2)]
	random.shuffle(sigs)
	sigs.pop(random.randint(0,3))
	print(' '.join(sigs))

	user_ans = int(input("What's my number?\n").strip())
	if user_ans == ans:
		print("Correct!")
		if i == 99:
			print("Here's your flag: {}".format(flag))
	else:
		print("Wrong! Better luck next time...")
		break
	print()

TL;DR

Stage 1

Connect to the server until we recieve a data package with (s1,s2,r1).
Guess all permutations of the data and use the guessed r1 to calculate 2*4096 possible r2.
From guessing all r1, r2 we also obtain the differences in the nonces dk.
Use dk to find secret from the given data together with the guessed r2.
Use secret to calculate k1_first.
Send secret to the server.

Other stages

From k1_first guess the nonce k1_round for the pair (s1,r1) from 2*4096 possible k1_round
Find secret from f(s1,r1,k1).
Use k1 to lower the bounds on the brute for additional nonces.
Send secret to the server.

Solution

Note: My main motivation for writing this up is so I can ask the challenge author Tux if it is the intended solution. This script is pretty slow and requires a lot of guessing. I would love to know if given s1,s2,r1 or s1,r1,r2 is suffient to find secret knowing that |k1 - k2| < 4096.

This challenge, like most CTF challenges associated to ECDSA, is about the closeness of nonce values. The canoncial challenge is the famous playstation three attack where the nonces are reused. For ECDSA there is the message m we want to sign. To sign m the server creates a private key d, and a public key Q. The public key is produced from the private key via the a scalar multiplication of a generator: Q = d*G. It is vital for the generator G to be of prime order, we will denote the order of G as n. We ensure the order of G is prime by working on an elliptic curve E of prime order.

To sign the message m, the server calculates the hash: h = Hash(m). A cryptographically secure integer k is picked. This value is known as the nonce (aside: the name nonce is used because it denotes n_once, or a number to be used only once!). A random point on the curve is produced from R = k*G and an integer r = R.x mod n is caluclated. If r is zero, a new k is generated and a new r is calculated. Finally the server signs h by calculating s = k^-1(h + r*d) mod n. The signed message S(m) is the tuple (r,s).

For the remaining dicussion, all arithmetic is mod n.

The hardness of the ECDLP means it is infeasible to calculate d from Q given a curve of a suffiently large order. However if the nonce k is innapropriately picked, d can be recovered from h,r,s through signing multiple messages. When k is fixed, the secret d can be recovered from only two signings, using that the nonce can be recovered from

k = s1^-1*(h1 + r1*d) = s2^-1*(h2 + r2*d)  --> k =  (h1 - h2) / (s1 - s2)

and that the secret is d = r^-1*(sk - h). This is the famous PS3 attack.

We can do better than this though, we don’t need k1 = k2, but only that k1 and k2 differ by a known number of bits. If an attacker can calculate the difference k1 - k2, the secret d can be recovered in the following way.

k1 = s1^-1*(h1 + r1*d), k2 = s2^-1*(h2 + r2*d)
k1 - k2 = s1^-1*(h1 + r1*d) - s2^-1*(h2 + r2*d)
s1*s2*(k1 - k2) = s2*(h1 + r1*d) - s1*(h2 + r2*d)
d*(s1*r2 - s2*r1) = (s2*h1 - s1*h2) - s1*s2*(k1 - k2)
d = (s2*h1 - s1*h2) - s1*s2*(k1 - k2)*(s1*r2 - s2*r1)^-1

An implmentation of the lattice attack to recover k1 - k2 from a set of signed messages is wonderfully described here: Trail of Bits: ECDSA - Handle With Care. I originally thought we’d need to use this to solve this challenge but it turns out knowing the difference of k1,k2 is given for free while trying to recover other data.

Onto the challenge. We connect to a server, and are able to sign two messages. The server replies with the public key and generates the tuples (r1,s1) and (r2,s2). We control the signed message m1, m2. The nonces used for the challenge are generated insecurely and we see that their difference is only at most 4096. This challenge would be easy if not for the next step:

sigs = [str(r1),str(s1),str(r2),str(s2)]
random.shuffle(sigs)
sigs.pop(random.randint(0,3))
print(' '.join(sigs))

We are only given 3 of the four pieces (r1,s1,r2,s2) AND we don’t know which of these integers is which. We can break down our problem in two questions:

Case 1: given (r1,s1,r2), can we calculate d?
Case 2: given (r1,s1,s2), can we calculate d?

For the first case, I have no idea how to solve this. Maybe there’s a way, but I can’t see it. It might then seems like it’s impossible to pass all 100 rounds of teh challenge, but we find that if we can solve one round, the remaining 99 are easier.

For the second case, we know that r1 = k1*G and the missing data is r2 = k2*G. As |k1 - k2| < 4096, we can take r1, lift it to find R1. We can then generate 2*4096 points such that one of them is R2 = k2*G. Once we have R1 and R2, we know k1 - k2 and we can solve the above equation for d. Note the contrast to case 1, where knowing (r1,s1,r2) doesn’t help you find s2 (as far as i know).

So if we solve case 2, how can we solve all other rounds? Well, we can use our secret d to find k1 from our data. It is this additional information that allows us to guess every other nonce for the rest of the challenge. As the difference is small, given k_found every other k will be one of 2*4096 nonces either side of it.

Our first question is given some data (?,?,?) how do we know if we are in case 1 or case 2? By taking the data given, we know that one of them is r1. By lifting this onto the curve we can look at the 2*4096 possible r2 values, if any of these points are in our array, we know we have r1, r2 and thus it is s2 which is missing.

# Returns r1, r2, k1 - k2 if both r1,r2 in the data,
# otherwise None.
def find_r_value(data_array):
    for r_guess in data_array[1:]:
        try:
            R1 = E.lift_x(r_guess)
        except:
            continue
        for i in range(-4096, 4096):
            R2 = R1 + i * G
            r2_guess = Integer(R2.xy()[0])
            if r2_guess in data_array and r2_guess != r_guess:
                return r_guess, r2_guess, i
    return None

Note, this also gives k1 - k2, but this is not enough to solve, as we do not know what s2 is.

So we can analyse the data packet on the first connection using this function. If we find both r1,r2 we quit and try again. When only one r1 value is in the set, we continue and calculate all possible r2 values. One of these r2 will produce a secret d such that d*G == Q. We implement this like so

def big_brute(guesses, Qx, Qy):
    # O(6 * 8192 * 2)
    # permutation * k_gap values * pos or neg k_gap
    for guess in guesses:
        ra, sa, sb = guess
        try:
            R1 = E.lift_x(ra)
        except:
            continue
        for i in range(-4096, 4096):
            print("i = ", i)
            R2 = R1 + i * G
            rb = int(R2.xy()[0])
            k_gap = i

            for kd in [k_gap, -k_gap]:
            	# guess the k_gap, use to derive a potential secret
                potential_priv_key = (sb * h1) - (sa * h1) - (sa * sb * kd)
                potential_priv_key *= inverse_mod((rb * sa) - (ra * sb), n)
                potential_priv_key %= n
                pG = potential_priv_key * ecG
                if pG.x() == Qx and pG.y() == Qy:
                    print("found private key!")
                    r1_found = ra
                    s1_found = sa
                    secret = potential_priv_key
                    return r1_found, s1_found, secret
    exit("Something went wrong, exiting")

Note that we’re now using python rather than sage to do the scalar multiplication on our curve. V01d noticed it was MUCH faster, and the switch to the ecdsa package made our script take ~ 30 mins rather than several hours.

Now we have the secret, we can also calculate the nonce k1 and send the secret to the server, progressing to round 2.

We can reduce our search space of the permutations of the data by again checking if r1,r2 are in given_data:

if check_data is None:
    print("One r value found, full search space")
    guesses = list(itertools.permutations(given_data))
else:
    print("Both r values found, reduced search space")
    ra,rb,_ = check_data
    for x in given_data:
        if x != ra and x != rb:
            sa = x
            break
    guesses = [[sa, ra, rb], [sa, rb, ra]]

We see that when both ri values appear, we can identify s1 and reduce our guesses from the 6 permutations to just 2. Given these permutations we guess 2*4096 possible nonces and calculate the secret from them. If the secret produces the public key, we are successful and we move to the next round

def brute_from_nonce(guesses, Qx, Qy):
    for guess in guesses:
        sa, ra, _ = guess
        for i in range(-k_lower, k_upper):
            k_guess = k1_found + i
            potential_priv_key = inverse(ra, n) * (k_guess * sa - h1) % n
            pG = potential_priv_key * ecG
            if pG.x() == Qx and pG.y() == Qy:
                print("found private key!")
                secret = potential_priv_key
                print(secret)
                return secret, k_guess

All we have to do is do this 99 times. We can speed it up a bit by using each recovered nonce from the above check to reduce the bound we guess over by recalculating the bounds each round

if k_guess > k1_found:
    k_diff = 4096 - (k_guess - k1_found)
    if k_diff < k_lower:
        k_lower = k_diff
elif k_guess < k1_found:
    k_diff = 4096 - (k1_found - k_guess)
    if k_diff < k_upper:
        k_upper = k_diff

After about 20 rounds the search space halves, which is pretty nice.

Thanks to v01d, who was able to change up my slow script and produce something fairly reasonable. Thanks to hyperreality who ran my slow script and was gonna leave it on overnight until v01d saved us!

Implementation

import os
os.environ["PWNLIB_NOTERM"] = "True"

from pwn import *
import hashlib
import itertools
from Crypto.Util.number import inverse
import gmpy2
import ecdsa

ecC = ecdsa.NIST256p
ecG = ecC.generator
ecn = ecC.order

a = -3
b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
E = EllipticCurve(GF(p), [a, b])
n = 115792089210356248762697446949407573529996955224135760342422259061068512044369
G = E(
    48439561293906451759052585252797914202762949526041747995844080717082404635286,
    36134250956749795798585127919587881956611106672985015071877198253568414405109,
)

# We'll always send the same message, so let's grab it now.
h1 = int(hashlib.sha256(b"password").hexdigest(), 16)


"""
For stage one, we have a 50% chance of being able to continue
using the method described above. If we find both r1 and r2
in the given data we exit and run the script again
"""

# --- REMOTE ---
IP = "2020.redpwnc.tf"
PORT = 31452
r = remote(IP, PORT, level="debug")

r.recvuntil("> ROUND")
r.recvline()
response = r.recvuntil("Enter", drop=True)

Qs = response.split(b" ")
Q = E(Integer(Qs[0]), Integer(Qs[1]))
print("Q = ", Q)

r.sendlineafter("message: ", b"password")
r.sendlineafter("message: ", b"password")

data = r.recvline().decode().split(" ")
r.recvuntil("number?")

given_data = list(map(Integer, data))
print("*" * 80)
print("Available Data")
print("*" * 80)
for d in given_data:
    print(f"?? = {d}")

# Returns r1, r2, k1 - k2 if both r1,r2 in the data,
# otherwise None.
def find_r_value(data_array):
    for r_guess in data_array[1:]:
        try:
            R1 = E.lift_x(r_guess)
        except:
            continue
        for i in range(-4096, 4096):
            R2 = R1 + i * G
            r2_guess = Integer(R2.xy()[0])
            if r2_guess in data_array and r2_guess != r_guess:
                return r_guess, r2_guess, i
    return None


check_data = find_r_value(given_data)

if check_data is not None:
    print("Need both s1, s2")
    print("Exiting")
    exit()

else:
    print("r1 or r2 is missing, we can proceed")
    guesses = list(itertools.permutations(given_data))


def big_brute(guesses, Qx, Qy):
    # O(6 * 8192 * 2)
    # permutation * k_gap values * pos or neg k_gap
    for guess in guesses:
        ra, sa, sb = guess
        try:
            R1 = E.lift_x(ra)
        except:
            continue
        for i in range(-4096, 4096):
            print("i = ", i)
            R2 = R1 + i * G
            rb = int(R2.xy()[0])
            k_gap = i

            for kd in [k_gap, -k_gap]:
            	# guess the k_gap, use to derive a potential secret
                potential_priv_key = (sb * h1) - (sa * h1) - (sa * sb * kd)
                potential_priv_key *= inverse_mod((rb * sa) - (ra * sb), n)
                potential_priv_key %= n
                pG = potential_priv_key * ecG
                if pG.x() == Qx and pG.y() == Qy:
                    print("found private key!")
                    r1_found = ra
                    s1_found = sa
                    secret = potential_priv_key
                    return r1_found, s1_found, secret
    exit("Something went wrong, exiting")

Qx, Qy = map(int, Q.xy())
r1_found, s1_found, secret = big_brute(guesses, Qx, Qy)

print("Recovered secret from brute force, found:")
print(f"r1_found = {r1_found}")
print(f"s1_found = {s1_found}")
print(f"secret = {secret}")
print("We can now calculate the nonce")
k1_found = inverse_mod(s1_found, n) * (h1 + r1_found * secret) % n

# Set generic bounds, which we will lower over each round
k_upper = 4096
k_lower = 4096

print(f"Nonce found: {k1_found}")
print("Subsequent rounds we can go faster (but still pretty slowly)")
r.sendline(str(secret))


"""
For every other round, we have the nonce within 
8192 guess, so we take the data, permute through
the guesses to find the pair (r1,r2) and then try 
all 8000 nonces until the secret works.
"""

def brute_from_nonce(guesses, Qx, Qy):
    for guess in guesses:
        sa, ra, _ = guess
        for i in range(-k_lower, k_upper):
            k_guess = k1_found + i
            potential_priv_key = inverse(ra, n) * (k_guess * sa - h1) % n
            pG = potential_priv_key * ecG
            if pG.x() == Qx and pG.y() == Qy:
                print("found private key!")
                secret = potential_priv_key
                print(secret)
                return secret, k_guess

iRnd = 0
while True:
    print("Round ", iRnd)
    print(f"Brute search for nonce between {-k_lower}, {k_upper}")
    response = r.recvuntil("message: ")
    cut = response.decode().split("\n")
    Qx, Qy = map(int, cut[-2].split(" "))
    print(Qx, Qy)

    r.sendline("password")
    r.recvuntil("message: ")
    r.sendline("password")

    data = r.recvline().decode().split(" ")
    r.recvuntil("number?")

    given_data = list(map(Integer, data))
    print("*" * 80)
    print("Available Data")
    print("*" * 80)
    for d in given_data:
        print(f"?? = {d}")

    check_data = find_r_value(given_data)
    if check_data is None:
        print("One r value found, full search space")
        guesses = list(itertools.permutations(given_data))
    else:
        print("Both r values found, reduced search space")
        ra,rb,_ = check_data
        for x in given_data:
            if x != ra and x != rb:
                sa = x
                break
        guesses = [[sa, ra, rb], [sa, rb, ra]]

    secret, k_guess = brute_from_nonce(guesses, Qx, Qy)
    if k_guess > k1_found:
        k_diff = 4096 - (k_guess - k1_found)
        if k_diff < k_lower:
            k_lower = k_diff
    elif k_guess < k1_found:
        k_diff = 4096 - (k1_found - k_guess)
        if k_diff < k_upper:
            k_upper = k_diff

    r.sendline(str(secret))
    iRnd += 1

#flag{s0m3t1m3s_crypt0gr4ph1c_1mpl3m3nt4t10ns_f41l}

Jeopardy

The choice is yours…choose your curve!

nc 2020.redpwnc.tf 31542

Challenge

#!/usr/bin/env sage
import random
import time
import asyncio
import traceback

flag = open('flag.txt','r').read()

def isPrime(n):
    if n == 2: return True
    if n%2 == 0: return False
    r,d = 0,n-1
    while d%2 == 0: r += 1; d //= 2
    for k in range(1):
        a = random.randint(2,n-2)
        x = pow(a,d,n)
        if x == 1 or x == n-1: continue
        for i in range(r-1):
            x = pow(x,2,n)
            if x == n-1: continue
        else: return False
    return True


async def handle_conn(reader, writer):
    async def prompt(ptext):
        writer.write(ptext.encode())
        await writer.drain()
        return (await reader.readline()).decode()

    try:
        BITS = 200

        a = Integer(await prompt('a: '))
        b = Integer(await prompt('b: '))
        p = Integer(await prompt('p: '))

        E = EllipticCurve(GF(p), [a,b])
        assert E.order().nbits() >= BITS
        assert E.order() != p
        assert isPrime(E.order())

        G = E.gens()[0]
        writer.write(f'{G}\n'.encode())
        secret = random.randint(1,E.order()-1)
        pub = G * secret
        writer.write(f'{pub}\n'.encode())

        user = int(await prompt('secret?'))
        if user == secret:
            writer.write(f'{flag}\n'.encode())
            await writer.drain()
    except Exception:
        writer.write(traceback.format_exc(2).encode())
    finally:
        await writer.drain()
        writer.close()
        await writer.wait_closed()


async def main():
    server = await asyncio.start_server(handle_conn, '0.0.0.0', 9999)

    addr = server.sockets[0].getsockname()
    print(f'Listening on {addr}')

    async with server:
        await server.serve_forever()

asyncio.run(main())

TL;DR

Server needs a curve which has a prime order which is different from the characteristic of the finite field
When a curve is accepted, the server builds the ECDLP and asks us to solve it.
Order of the curve must be at least 200 bits, if the order of the curve is prime, we cannot solve dlog
However, the order is checked with a broken isPrime function, vulnreable to composite strong pseudoprimes
We solve the challenge by first calculating a strong pseudoprime passing isPrime which is smooth enough that we can reasonibly solve dlog
We then must construct an elliptic curve of this order and pass it to the server. If the curve is accepted we are given G, Q=dG which we must derive d from

Solution

This challenge was a golf challenge, where the number of bits the prime needed to satisfy decreased over time. When the challenge is solved, the number is fixed. The challenge was solved fairly quickly and the order of the curve was fixed at 200 bits.

I did not solve this challenge during the competition. The algorithm for finding an elliptic curve of prescribed order was duanting and I was unable to make it work. Holocircuit did amazing work and got very close, but we couldnt squash all the bugs before the end of the competition. Since the CTF ended, I learnt many people solved this challenge by using ecgen, an unmaintained and notorious tool which will generate a curve. I have also since found a wonderful paper Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation which has an almost complete solution to this challenge.

I will split this write-up into three stages, calculating a strong pseudoprime, constructing a curve of prime order and solving dlog for the curve. For the last step, I have emulated the server and I use a dummy flag… I don’t know what the real one is.

Step One: Strong Pseudoprimes

Miller-Rabin

I already had some experience fooling the Miller-Rabin test from a paper by Arnault: Constructing Carmichael numbers which are strong primes to several bases and even had some code lying around. However it was hard to generalise to many many factors and the best integer I found was 238 bits with 5 factors. This passed isPrime with about 6% success (this isPrime function is so whack).

C = 340649031679478708871356501710247209854526956821188127472136012686397651
bit length: 238
factors: [10360877555851, 134691408226051, 424795979789851, 549126510460051, 1046448633140851]
bit lengths: [44, 47, 49, 49, 50]

I decided the bit length of the factors was too large to reasonibly solve dlog, so I started looking for other methods.

Universal forms

The second method I used was constructing Carmichael numbers from universal forms, based off the paper On Fermat’s Simple Theorem which shows how we have a one parameter condition to construct Carmichael numbers with n factors. These Carmichael numbers passed the test less often, but often enough with ~1% success.

For an integer M, we can find Carmichael numbers C from universal forms, which can be written as

U_n+1 = (6M + 1)(12M + 1)(18M + 1)(2^2 M + 1)...(2^n-1 M +1)

where each factor of U_n+1 must be prime. Using the following snippet of code

def universal_forms(SEED, l):
	coeffs = [6,12,18,36,72,144,288,576,1152,1728]
	coeffs = coeffs[:l]
	while True:
		ps = [c*SEED + 1 for c in coeffs]
		if all(isPrime(p) for p in ps):
			return ps, SEED + 1
		SEED += 1

I was able to calculate several composite numbers which passed the isPrime test with at least 1% success with 5 factors. I could not find composite integers of more factors which passed the test with this bound of success. A subset of the integers I found was

C = 1300166808692042795962532177088827946815806931819239012667149
bit length: 200
factors: [313114417687, 626228835373, 939343253059, 1878686506117, 3757373012233]
bit lengths: [39, 40, 40, 41, 42]
...
C = 2880633345009518112283310208636540975082090682427396690125869
bit length: 201
factors: [367113915967, 734227831933, 1101341747899, 2202683495797, 4405366991593]
bit lengths: [39, 40, 41, 42, 43]

This was progress, and during the CTF I felt like this was good enough. 42 bits as a highest factor seemed reasonable. I was surprised by how easy this was to implement and how quick it was. For larger C, I can see this getting very slow, especially when you require k > 3 factors.

Erdos Method + Granville and Pomerance

This section is a bonus, and based off two algorithms in Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation. We can use the Erdos method to find Carmichael numbers of many many small factors. These numbers however never pass the isPrime test (or close to never) so what we can do is then use the algoritm of Granville and Pomerance which generates Carmichael numbers from Carmichael numbers. The implementation I used was

"""
Majority of code from https://eprint.iacr.org/2019/032.pdf
Safety in Numbers: On the Need for Robust Diffie-Hellman Parameter Validation
"""

import itertools
from operator import mul

def all_combinations(any_list): 
	"""
	Wrapper for itertools to generate all possible combinations of all (non trivial) sizes.
	"""
	return itertools.chain.from_iterable(itertools.combinations(any_list , i + 1) for i in range(len(any_list)))

def LCMpim1(n):
	"""
	Takes as input n: a list of integers p_i and returns the lcm(p_i-1) for all i 
	"""
	pim1list = []
	for pi in n:
		pim1 = pi - 1
		pim1list.append(pim1) 
	return lcm(pim1list)

def listbuild(L):
	"""
	Takes as input a (highly composite) number L and returns a list of all primes p such 
	that p-1 | L where p does not divide L. We include the additional requirement that p = 3 mod 4.
	"""
	a = list(factor(L))
	p = []
	for y in a:
		for i in range(0, y[1]): 
			p.append(y[0])
	
	pvals = all_combinations(p) 
	ps = []
	for pp in pvals:
		t = reduce(mul, pp, 1)
		tt = t + 1
		if tt.is_prime(proof=False) and L % tt != 0:
			if tt not in ps: 
				ps.append(tt)
	pps = []
	ps.sort()
	# we now filter results to only inlude p with p = 3 mod 4 
	for p in ps:
		if p % 4 == 3: 
			pps.append(p)
	return pps

def erdos_build(factors , L, k):
	"""
	This function takes a list of possible factors, a (highly composite) integer L and k,
	and produces a Carmichael number with k factors sampled from "factors" such that the 
	LCM of each factor p_i - 1 is equal to L. Output is parsed as n,[p_1,p_2,...,p_k] 
	where n = p_1 * p_2 * ... * p_k.
	"""
	if k <=2:
		print("Choice of factors must be >=3")
		return 0
	for i in itertools.combinations(factors , k):
		v = reduce(mul, i, 1) 
		if v % L == 1:
			fin = list(i) 
			fin.sort()
			if LCMpim1(fin) == L:
				return [v,fin]
	print("None found, try increasing size of factor list")


def granville_and_pomerance(factors):
	k = 1
	L = LCMpim1(factors)
	while True:
		M = 1 + k*L
		qs = [1 + M*(p-1) for p in factors]
		if all(q.is_prime(proof=False) for q in qs):
			N = prod(qs)
			return N, qs
		k += 1


Ls = [810810, 2088450, 4054050, 7657650, 13783770, 22972950, 53603550]

# Small L picked to keep N.nbits() small
L = 2*3^4*5*7*11
factors = listbuild(L)
print(factors, L, len(factors))

char, car_factors = erdos_build(factors , L, 6)
print(char, car_factors)

N, qs = granville_and_pomerance(car_factors)

print(N)
print(qs)
print(N.nbits())
print([q.nbits() for q in qs])

Using this produced a Carmichael number passing 3% of tests of the form:

C = 17226095350814884309562782709503476832333815043778073233750461
bit length: 204
factors: [2118459439, 7767684607, 19066134943, 31776891571, 38838423031, 44487648199]
bit lengths [31, 33, 35, 35, 36, 36]

Having this sixth factor is great and greatly simplifies the upcomming dlog problem.

Step Two: Generating a curve of prescribed order

Hindsight Checklist

Solve using ecgen (Boo!!)
Solve using algorithm given by Galbraith, Massimo, and Paterson
Solve using algorithm by ChiCubed written to solve this challenge!
Write your own algoritm

Of these four lists, only the last was avaliable to me during the competition. I tried to implement something, but it was far too slow as my method of finding a discriment with a small square-free part was terrible. Approximately, it was of the same form as the naive solution in Bröker’s thesis. Holocircuit attempted (and got insanely close) to implementing the algorithm in section 4.1 of Reinier Bröker’s Thesis. After the compeition we realised it was about 1 or two lines keeping us from the solve! I haven’t managed to fix my own implementation of it. It feels dishonest to display any fixed code here after seeing the work by ChiCubed, which would simply be a refactoring of their work.

The paper by Galbraith, Massimo, and Paterson produces an algorithm in appendix C (Algorithm of Bröker and Stevenhagen), however this is limited to an order N which is squarefree and has only 3 factors. The implmentation by ChiCubed is a much more general realisation of Bröker’s algorithm.

Running ChiCubed’s implementation of Bröker’s alorithm with a prescribed order 17226095350814884309562782709503476832333815043778073233750461 produced a curve within 10 minutes:

Jack: ~ % sage redpwn/generate_order.sage
trying 171259 16555727575344674102260187525/2*a + 4686538145203615415053289961063/2
success! Elliptic Curve defined by y^2 = x^3 + 16100304990402797113692811685429247648780477314497521961846040*x + 16470469406676450872902150339598545251380983030417104004004538 over Finite Field of size 17226095350814884309562782709498790294188611428363019943789399

Step Three: Grabbing the flag

I don’t have access to the server anymore and didn’t have it in me to bother doing all the boring side of socket stuff so I just made a dummy script to solve with my fresh curve.

#!/usr/bin/env sage
import random

flag = 'flag{I_dont_know_what_this_is}'
BITS = 200

def isPrime(n):
    if n == 2: return True
    if n%2 == 0: return False
    r,d = 0,n-1
    while d%2 == 0: r += 1; d //= 2
    for k in range(1):
        a = random.randint(2,n-2)
        x = pow(a,d,n)
        if x == 1 or x == n-1: continue
        for i in range(r-1):
            x = pow(x,2,n)
            if x == n-1: continue
        else: return False
    return True

def solve_challenge(G,Q):
    return G.discrete_log(Q)

"""
To solve this challenge, all we are allowed to send to the server
is the curve parameters [p,a,b]. Sending these, the server checks
three conditions, then sets up the ECDLP

We will send the params params from curve generator function which found the curve

Elliptic Curve defined by y^2 = x^3 + 16100304990402797113692811685429247648780477314497521961846040*x + 16470469406676450872902150339598545251380983030417104004004538 over Finite Field of size 17226095350814884309562782709498790294188611428363019943789399
E.order() 
17226095350814884309562782709503476832333815043778073233750461
"""

# What we would send to the server
a = 16100304990402797113692811685429247648780477314497521961846040
b = 16470469406676450872902150339598545251380983030417104004004538
p = 17226095350814884309562782709498790294188611428363019943789399

# We know it only passes 3% of the time, so we would have to connect many times to the server
connections = 0
while True:
    connections += 1
    E = EllipticCurve(GF(p), [a,b])
    if E.order().nbits() >= BITS and E.order() != p and isPrime(E.order()):
        break

print(f'Curve accepted after {connections} connections, max connection number estimated as ~33')

"""
Passing the checks, the server asks us to solve the ECDLP
"""

G = E.gens()[0]
print(G)
secret = random.randint(1,E.order()-1)
Q = G * secret
print(Q)

"""
As the order of E is smooth, we can do this easily!
"""
print('Calculating discrete logarithm of Q')
user = solve_challenge(G,Q)
print(user)

if user == secret:
    print(flag)
# flag{I_dont_know_what_this_is}

Redpwn CTF

Contents

Seekrypt

Challenge

TL;DR

Solution

Implementation

Speedy Signatures

Challenge

TL;DR

Stage 1

Other stages

Solution

Implementation

Jeopardy

Challenge

TL;DR

Solution

Step One: Strong Pseudoprimes

Miller-Rabin

Universal forms

Erdos Method + Granville and Pomerance

Step Two: Generating a curve of prescribed order

Step Three: Grabbing the flag