moectf2024 Crypto wp
现代密码学入门指北 :
from Crypto.Util.number import bytes_to_long,
getPrime from secret import flag
p = getPrime(128)
q = getPrime(128)
n = p*q e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
print(f"n = {n}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")
'''
n = 40600296529065757616876034307502386207424439675894291036278463517602256790833
p = 197380555956482914197022424175976066223
q = 205695522197318297682903544013139543071
c = 36450632910287169149899281952743051320560762944710752155402435752196566406306 题目分析 :
最基础的RSA
EXP :
from Crypto.Util.number import *
import gmpy2
e=65537
c=36450632910287169149899281952743051320560762944710752155402435752196566406306
q=205695522197318297682903544013139543071
p=197380555956482914197022424175976066223
n=40600296529065757616876034307502386207424439675894291036278463517602256790833
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(m)
print(long_to_bytes(m))Signin :
from Crypto.Util.number import*
from secret import flag
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
c = pow(m,e,n)
pq = (p-1)*(q-2)
qp = (q-1)*(p-2)
p_q = p + q
print(f"{c = }")
print(f"{pq = }")
print(f"{qp = }")
print(f"{n = }")
print(f"{p_q = }")
'''
c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
pq = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687154230787854196153067547938936776488741864214499155892870610823979739278296501074632962069426593691194105670021035337609896886690049677222778251559566664735419100459953672218523709852732976706321086266274840999100037702428847290063111455101343033924136386513077951516363739936487970952511422443500922412450462
qp = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687077087914198877794354459669808240133383828356379423767736753506794441545506312066344576298453957064590180141648690226266236642320508613544047037110363523129966437840660693885863331837516125853621802358973786440314619135781324447765480391038912783714312479080029167695447650048419230865326299964671353746764860
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
p_q = 279533706577501791569740668595544511920056954944184570513187478007551195831693428589898548339751066551225424790534556602157835468618845221423643972870671556362200734472399328046960316064864571163851111207448753697980178391430044714097464866523838747053135392202848167518870720149808055682621080992998747265496
'''题目分析 :
先根据pq,qp求出p和q,然后就是最基础的RSA
EXP :
import gmpy2
import sympy as sp
from Crypto.Util.number import long_to_bytes
# 定义符号变量p,q
p, q = sp.symbols('p q')
# 定义方程组
pq = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687154230787854196153067547938936776488741864214499155892870610823979739278296501074632962069426593691194105670021035337609896886690049677222778251559566664735419100459953672218523709852732976706321086266274840999100037702428847290063111455101343033924136386513077951516363739936487970952511422443500922412450462
qp = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687077087914198877794354459669808240133383828356379423767736753506794441545506312066344576298453957064590180141648690226266236642320508613544047037110363523129966437840660693885863331837516125853621802358973786440314619135781324447765480391038912783714312479080029167695447650048419230865326299964671353746764860
eq1 = (p-1)*(q-2) - pq
eq2 = (q-1)*(p-2) - qp
# 求解方程组
sol = sp.solve((eq1,eq2), (p, q))
print(sol)
# 解题
e = 65537
n = 18047017539289114275195019384090026530425758236625347121394903879980914618669633902668100353788910470141976640337675700570573127020693081175961988571621759711122062452192526924744760561788625702044632350319245961013430665853071569777307047934247268954386678746085438134169871118814865536503043639618655569687534959910892789661065614807265825078942931717855566686073463382398417205648946713373617006449901977718981043020664616841303517708207413215548110294271101267236070252015782044263961319221848136717220979435486850254298686692230935985442120369913666939804135884857831857184001072678312992442792825575636200505903
c = 5654386228732582062836480859915557858019553457231956237167652323191768422394980061906028416785155458721240012614551996577092521454960121688179565370052222983096211611352630963027300416387011219744891121506834201808533675072141450111382372702075488292867077512403293072053681315714857246273046785264966933854754543533442866929316042885151966997466549713023923528666038905359773392516627983694351534177829247262148749867874156066768643169675380054673701641774814655290118723774060082161615682005335103074445205806731112430609256580951996554318845128022415956933291151825345962528562570998777860222407032989708801549746
p = 101195416461091716428326199733504078281010548412226222689665080411126731520752210150756388683557219973649948209094722629248795549538890771346214761833764975454769057589710497693291150424006859232283601953197097456280805871953601208233200402046794268614613979577032173301390416040533984248749301081715040789947
q = 178338290116410075141414468862040433639046406531958347823522397596424464310941218439142159656193846577575476581439833972909039919079954450077429211036906580907431676882688830353669165640857711931567509254251656241699372519476443505864264464477044478438521412625815994217480304109274071433871779911283706475549
d = gmpy2.invert(e, (p - 1) * (q - 1))
m = pow(c, d, n)
print(long_to_bytes(m))ez_hash :
from hashlib import sha256
from secret import flag, secrets
assert flag == b'moectf{' + secrets + b'}'
assert secrets[:4] == b'2100' and len(secrets) == 10
hash_value = sha256(secrets).hexdigest()
print(f"{hash_value = }")
# hash_value = '3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a'题目分析 :
flag就是secrets,已知secrets的前四位是2100，一共10位，还知道hash加密后的值，那么暴力得到secrets就行了
EXP :
from hashlib import sha256
hash_value = '3a5137149f705e4da1bf6742e62c018e3f7a1784ceebcb0030656a2b42f50b6a'
n = 2100000000
for i in range(1000000):
s = n + i
if sha256(str(s).encode()).hexdigest() == hash_value:
print(s)
breaksmall_and_big :
from secret import flag
from Crypto.Util.number import*
m = long_to_bytes(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 3
c = pow(m,e,n)
'''
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
'''题目分析 :
e很小，n很大，低指数爆破
EXP :
import gmpy2
from Crypto.Util.number import *
n = 20279309983698966932589436610174513524888616098014944133902125993694471293062261713076591251054086174169670848598415548609375570643330808663804049384020949389856831520202461767497906977295453545771698220639545101966866003886108320987081153619862170206953817850993602202650467676163476075276351519648193219850062278314841385459627485588891326899019745457679891867632849975694274064320723175687748633644074614068978098629566677125696150343248924059801632081514235975357906763251498042129457546586971828204136347260818828746304688911632041538714834683709493303900837361850396599138626509382069186433843547745480160634787
c = 150409620528288093947185249913242033500530715593845912018225648212915478065982806112747164334970339684262757
e = 3
for i in range(200000000):
if gmpy2.iroot(c+n*i,3)[1] == 1:
flag = gmpy2.iroot(c+n*i,3)[0]
print(long_to_bytes(flag))baby_equation :
from Crypto.Util.number import *
from secret import flag
l = len(flag)
m1, m2 = flag[:l//2], flag[l//2:]
a = bytes_to_long(m1)
b = bytes_to_long(m2)
k = 0x2227e398fc6ffcf5159863a345df85ba50d6845f8c06747769fee78f598e7cb1bcf875fb9e5a69ddd39da950f21cb49581c3487c29b7c61da0f584c32ea21ce1edda7f09a6e4c3ae3b4c8c12002bb2dfd0951037d3773a216e209900e51c7d78a0066aa9a387b068acbd4fb3168e915f306ba40
assert ((a**2 + 1)*(b**2 + 1) - 2*(a - b)*(a*b - 1)) == 4*(k + a*b)题目分析 :
题目把flag拆成了两半，然后分别转成了长整型，最后告诉了我们一个关系式，那我们就要从关系式出发，简化a,b与k的关系，然后分解，最后遍历出合适的a,b，并得到flag
推导过程 :
import sympy as sp
# 定义符号变量p,q
a, b, k = sp.symbols('a b k')
# 定义方程组
eq = ((a**2 + 1)*(b**2 + 1) - 2*(a - b)*(a*b - 1)) - 4*(k + a*b)
# 求解方程组
sol = sp.solve((eq), (a, b))
print(sol)运行得到：$a=(-b + 2sqrt(k) + 1)/(b - 1)$ ,即 $(a+1)(b-1)=2sqrt(k)$ 然后去分解 $2sqrt(k)$ ,发现有很多个因数，那么我们就要去遍历，找到正确的两个因数，最后得到flag
EXP :
from gmpy2 import *
from Crypto.Util.number import *
k = 0x2227e398fc6ffcf5159863a345df85ba50d6845f8c06747769fee78f598e7cb1bcf875fb9e5a69ddd39da950f21cb49581c3487c29b7c61da0f584c32ea21ce1edda7f09a6e4c3ae3b4c8c12002bb2dfd0951037d3773a216e209900e51c7d78a0066aa9a387b068acbd4fb3168e915f306ba40
x = int(iroot(4 * k, 2)[0])
print(x)
# factor(x)
factors = [2, 2, 2, 2, 3, 3, 31, 61, 223, 4013, 281317, 4151351, 5404604441993,
26798471753993, 25866088332911027256931479223, 64889106213996537255229963986303510188999911, 370523737,
339386329]
dic = {1: []}
for factor in factors:
for f in list(dic.keys()):
ff = f * factor
if ff not in dic:
dic[ff] = dic[f] + [factor]
for m1 in list(dic.keys()):
if b'moectf' in long_to_bytes(m1):
m2 = x // m1
if b'}' in long_to_bytes(m2 + 1):
print(long_to_bytes(m1 - 1) + long_to_bytes(m2 + 1))
else:
print(long_to_bytes(m1 + 1) + long_to_bytes(m2 - 1))大白兔 :
from Crypto.Util.number import *
flag = b'moectf{xxxxxxxxxx}'
m = bytes_to_long(flag)
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
def encrypt(m , e1 , e2):
p = getPrime(512)
q = getPrime(512)
N = p*q
c1 = pow((3*p + 7*q),e1,N)
c2 = pow((2*p + 5*q),e2,N)
e = 65537
c = pow(m , e , N)
return c
print(encrypt(m ,e1 , e2))
'''
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
'''题目分析 :
EXP :
from Crypto.Util.number import *
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
n = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
h1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
h2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
e = 65537
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
k = e1 * e2
h5 = pow(h2,e1,n)*pow(3,k,n)-pow(h1,e2,n)*pow(2,k,n)
k1 = inverse(pow(15,k,n)-pow(14,k,n), n)
h3 = h5 * k1 % n
p = GCD(h3, n)
q= n // p
phi = (p-1) * (q-1)
d = inverse(e, phi)
m = pow(c,d,n)
print(bytes.fromhex(hex(m)[2:]))More_secure_RSA :
from Crypto.Util.number import *
flag = b'moectf{xxxxxxxxxxxxxxxxx}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f'c = {c}')
print(f'n = {n}')
'''
Oh,it isn't secure enough!
'''
r = getPrime(1024)
n = n * r
c = pow(m, e, n)
print(f'C = {c}')
print(f'N = {n}')
'''
c = 12992001402636687796268040906463852467529970619872166160007439409443075922491126428847990768804065656732371491774347799153093983118784555645908829567829548859716413703103209412482479508343241998746249393768508777622820076455330613128741381912099938105655018512573026861940845244466234378454245880629342180767100764598827416092526417994583641312226881576127632370028945947135323079587274787414572359073029332698851987672702157745794918609888672070493920551556186777642058518490585668611348975669471428437362746100320309846155934102756433753034162932191229328675448044938003423750406476228868496511462133634606503693079
n = 16760451201391024696418913179234861888113832949815649025201341186309388740780898642590379902259593220641452627925947802309781199156988046583854929589247527084026680464342103254634748964055033978328252761138909542146887482496813497896976832003216423447393810177016885992747522928136591835072195940398326424124029565251687167288485208146954678847038593953469848332815562187712001459140478020493313651426887636649268670397448218362549694265319848881027371779537447178555467759075683890711378208297971106626715743420508210599451447691532788685271412002723151323393995544873109062325826624960729007816102008198301645376867
C = 1227033973455439811038965425016278272592822512256148222404772464092642222302372689559402052996223110030680007093325025949747279355588869610656002059632685923872583886766517117583919384724629204452792737574445503481745695471566288752636639781636328540996436873887919128841538555313423836184797745537334236330889208413647074397092468650216303253820651869085588312638684722811238160039030594617522353067149762052873350299600889103069287265886917090425220904041840138118263873905802974197870859876987498993203027783705816687972808545961406313020500064095748870911561417904189058228917692021384088878397661756664374001122513267695267328164638124063984860445614300596622724681078873949436838102653185753255893379061574117715898417467680511056057317389854185497208849779847977169612242457941087161796645858881075586042016211743804958051233958262543770583176092221108309442538853893897999632683991081144231262128099816782478630830512
N = 1582486998399823540384313363363200260039711250093373548450892400684356890467422451159815746483347199068277830442685312502502514973605405506156013209395631708510855837597653498237290013890476973370263029834010665311042146273467094659451409034794827522542915103958741659248650774670557720668659089460310790788084368196624348469099001192897822358856214600885522908210687134137858300443670196386746010492684253036113022895437366747816728740885167967611021884779088402351311559013670949736441410139393856449468509407623330301946032314939458008738468741010360957434872591481558393042769373898724673597908686260890901656655294366875485821714239821243979564573095617073080807533166477233759321906588148907331569823186970816432053078415316559827307902239918504432915818595223579467402557885923581022810437311450172587275470923899187494633883841322542969792396699601487817033616266657366148353065324836976610554682254923012474470450197
'''题目分析 :
EXP :
from Crypto.Util.number import *
import gmpy2
e=0x10001
c=1227033973455439811038965425016278272592822512256148222404772464092642222302372689559402052996223110030680007093325025949747279355588869610656002059632685923872583886766517117583919384724629204452792737574445503481745695471566288752636639781636328540996436873887919128841538555313423836184797745537334236330889208413647074397092468650216303253820651869085588312638684722811238160039030594617522353067149762052873350299600889103069287265886917090425220904041840138118263873905802974197870859876987498993203027783705816687972808545961406313020500064095748870911561417904189058228917692021384088878397661756664374001122513267695267328164638124063984860445614300596622724681078873949436838102653185753255893379061574117715898417467680511056057317389854185497208849779847977169612242457941087161796645858881075586042016211743804958051233958262543770583176092221108309442538853893897999632683991081144231262128099816782478630830512
q=94417923442805995407258485244637177394185577546369524188869104079881935019411561089256688017656901819534175347366083570379458398014401170940638651162942055446365562448376059016295192284562716900272450942947365490116604993713523212301010519976320946995874594164811989942446499971709687808731533101170900925991
p=16760451201391024696418913179234861888113832949815649025201341186309388740780898642590379902259593220641452627925947802309781199156988046583854929589247527084026680464342103254634748964055033978328252761138909542146887482496813497896976832003216423447393810177016885992747522928136591835072195940398326424124029565251687167288485208146954678847038593953469848332815562187712001459140478020493313651426887636649268670397448218362549694265319848881027371779537447178555467759075683890711378208297971106626715743420508210599451447691532788685271412002723151323393995544873109062325826624960729007816102008198301645376867
n=94417923442805995407258485244637177394185577546369524188869104079881935019411561089256688017656901819534175347366083570379458398014401170940638651162942055446365562448376059016295192284562716900272450942947365490116604993713523212301010519976320946995874594164811989942446499971709687808731533101170900925991
phi=(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(m)
print(long_to_bytes(m))ezlegendre :
from sympy import *
from Crypto.Util.number import *
a = 288260533169915
p = 1007621497415251
FLAG = b'moectf{xxxxxxxxxxxxxxxxxxxxx}'
def encrypt_flag(flag):
ciphertext = []
plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
for b in plaintext:
e = randprime(2, p)
if b == '1':
n = pow(a, -e, p)
ciphertext.append(n)
else:
n = pow(-a, e ,p)
ciphertext.append(n)
return ciphertext
print(encrypt_flag(FLAG))
'''
[869209361008868, 469987155014055, 477607245771711, 956121763882082, 460028889963055, 533967339350806, 476643304115038, 398098864395899, 708866397520182, 894852371427053, 830040978017214, 982890039414452, 407281601145406, 984373673613758, 331248820899125, 413731871413066, 112233590512619, 844508013531773, 660541015358267, 203847276465014, 196764266760616, 724197319842530, 812956074918088, 543222621016303, 696010102017333, 981894930207802, 267226118917619, 790129874087132, 347190586174502, 558560481026105, 950966879997572, 194292449369649, 939650649212499, 849325569453260, 954903252340838, 666432519482028, 633589915590432, 674835636376805, 411981317282694, 255883519424948, 20332021415046, 41211809179475, 615228291023827, 3174369207878, 692370202966600, 171277599642048, 550867407707890, 928211081192953, 619531888759759, 941561507423215, 227188515309784, 44358479590760, 191301655212015, 872434831540071, 139926467694171, 257184569797282, 424025125913335, 604314815606040, 688629170195562, 934061980780966, 117123867152708, 118775453146424, 650238997700650, 464296860203680, 846900558108148, 136810490139411, 734401553273199, 1003815301659353, 177890098513981, 989132152091058, 925193504078956, 16120118469157, 417698353358040, 321572997822303, 490470448511519, 143301632751724, 201665758214964, 55674980300458, 672801140720347, 538389842964759, 688041819793393, 205641306968894, 85514071959036, 765861630472651, 1002881651048918, 468366360167056, 617444592689374, 489960009824958, 277775292746563, 839649570289759, 44545172581275, 688402966446644, 63769456068611, 213999882436593, 216065701874753, 550918086303447, 537406584676363, 360111428305020, 49045746183886, 406387916012829, 616035592607376, 910420067160309, 793994862952614, 559040919034722, 563431245991661, 540696592133, 692916878493026, 196862724250440, 915740996075121, 93262251719033, 138249806426133, 804205456884944, 980827994771964, 610265656156428, 675182808097113, 871977346966751, 432436067933537, 442408025475728, 68859983520112, 981142230621570, 44959838765869, 718285129646124, 479524397547695, 589544640946059, 723473211888089, 45649254718349, 809760578240640, 924079152216550, 819111458104359, 635798987884173, 493145154891103, 930007668559676, 951257062978841, 271213718852471, 322982213108644, 399650597731932, 599981686178645, 679031137073299, 871271038222937, 181211009276874, 492456903306033, 565461124642037, 368127868271848, 818142124952965, 531075679825305, 470971994131221, 266554775796898, 667178714173757, 601760855209461, 973801647168834, 932955611573179, 560279111769633, 517548136647154, 549911181170332, 60313689384526, 949491482563099, 452808097613187, 526891136085621, 274705731912851, 434344133676355, 115452488467955, 777777483737098, 814398658724455, 910884139326892, 721153094839833, 123149817617701, 733044865256370, 453868668750506, 66612079427577, 764872507837542, 782137313744881, 24535133913719, 360725525868320, 843972203447559, 891517126809644, 360885232459056, 368491982324658, 283707800915486, 326364439338006, 577378371719791, 722856146079435, 103533837658784, 254688935670505, 377583660405763, 437013223157800, 104708446011619, 988031331348961, 6886781492092, 31048660015037, 202508578415311, 819068100189702, 945419575503259, 73138283255017, 139586913643073, 579156429956448, 1003950470653630, 43710932909704, 922978652768702, 2942054726977, 343866518172971, 681650663259700, 614368933971283, 778713632307973, 398606253834970, 652338331771108, 641949670227333, 252161824790388, 598999939736302, 316749687994360, 952960614096341, 396671237810412, 805539289473096, 358920713125289, 935634624997029, 663385581032613, 35662861967181, 651607545611746, 758681810095871, 611397958560345, 196198933017746, 886932929348591, 660636395367246, 468455431788915, 924092573734008, 950690129324433, 999587127966195, 888011838963394, 602531651309337, 872691790865711, 968486908482852, 453553188990935, 695483211524155, 202869346556262, 970853032785416, 464221034091328, 500444626777630, 938300733064411, 739460171542679, 106243138680201, 220381406498074, 736061259497615, 287985336691769, 828566732433388, 25653881073282, 621320181554384, 978367718394475, 699801594755984, 69045944311920, 918153290921350, 742496154847514, 363237956586620, 855864928899402, 800408376661392, 591608071268736, 644600617307002, 400767167982482, 909728690834744, 619305066037810, 403154906624258, 61283916530956, 841154857119583, 271928739448620, 943602826453375, 181046110086998, 505489926854412, 265242434598252, 397601251563453, 582010431811786, 867744877195598, 157197910775288, 966686261925769, 18876998620377, 389690805402299, 537227398431908, 347700971404069, 441035382034345, 130724065565645, 436020443846434, 995901787186173, 218421083750934, 171270989504749, 837304614857272, 95058522671678, 684115651758448, 759170700243634, 963623830143399, 134020269447492, 810880730174490, 197514429664776, 933293941632760, 298355176150228, 291165975126682, 652837005225218, 594968433103211, 717988266663274, 681283193706870, 94720698554954, 534912230024800, 57002875791544, 466283757471303, 98170275960806, 39674133238710, 328905545254275, 600446924183400, 170250560797853, 96447538360913, 402756881318255, 653833791145054, 624186905259950, 381562263941849, 65202471674875, 813603811804515, 82412251682881, 430813934901833, 630104191517524, 564446338863457, 521850616317191, 301536973562373, 530267275218593, 998500657074054, 7212267782858, 259640351421902, 387324702112626, 888396292341115, 749024753723971, 85418162375112, 883404575520240, 728635284501806, 407998283472092, 917783827814342, 843382891125076, 933249524460091, 237368870850561, 461947500031560, 606265478139720, 762497205024250, 196108161980785, 464712920731734, 802735147473729, 663472255956649, 80955982171827, 891052715882349, 129688607671519, 903004933201140, 813929727900992, 100503758506631, 602082014286842, 437397404488802, 47519859806478, 395180151536529, 546373743492093, 647339114173723, 411317111927540, 101696276166348, 678151959559988, 51668751683754, 265849155643268, 868421028571661, 787999759724884, 95267994279095, 689256950522950, 550554665183774, 426522315621696, 139457110594782, 807574535966969, 181385017851905, 221826095950324, 222071619532288, 419028990094469, 976525300090124, 328201093236083, 286722736191619, 492796951075221, 651514298199139, 571796506342022, 206711677756906, 47331710606546, 702594972120132, 392046509167760, 478407918714814, 592730815648701, 138641638103370, 174303830676571, 529279947866956, 137415107280702, 216392715868670, 86947465794518, 818726716800394, 340254397869880, 371508780067424, 325307981047717, 567687140806415, 822565446854328, 660813456229288, 19186753583566, 644846006777331, 141327393629965, 235920480869413, 838745724950584, 276825516838237, 662761874040532, 418355702214096, 313711926685110, 88437689500328, 460176433574732, 2450228266396, 882266239157054, 673897905650082, 206208153755434, 548920099001980, 153266184111387, 13255788142270, 922484903048545, 440748803998307, 916906240947778, 400842493149205, 220485381482889, 487235065872011, 956191700672996, 995028709816052, 494918773812268, 786696522967722, 535635917789998, 659174735355314, 463254511578315, 933226451519003, 145072370503877, 625388715158253, 426295995778131, 115935587473835, 600764310873265, 1001986508035110, 209492238677627, 654076248845276, 255757144067046, 688372647240070, 337337203838464, 515859807535188, 875162734787756, 794777961098119, 609676420444937, 212529507506835, 795546633511290, 241207048060749, 776801875116315, 481556344267066, 816808129431759, 493895095538575, 51663065130083, 872561553334056, 142484860361584, 366178848478200, 582100262745320, 442278448664580, 658722265331043, 838584617412841, 618888833439999, 841459921663339, 442091548782434, 871146541604948, 361232391335863, 267110542973009, 98775266993905, 726739643823148, 208174460713647, 436363607002850, 109080678453891, 324963987304404, 747129957189381, 629090382627354, 326901225863526, 501411395019558, 605957277216355, 924462072245263, 681742264224629, 411620165150528, 978576627121525, 942031139574369, 93231172524187, 25708686373165, 706440278468996, 89296822699255, 609549323696105, 348801631103012, 301019857245003, 568429888021619, 696641838804966, 449524020606334, 717635512592258, 621428075417344, 165738165511311, 158410762741058, 161602488447872, 382183389407570, 328907274595208, 766746904253365, 107746916578801, 659628742394117, 39850489385122, 666051397127749, 474312422270748, 261139991035351, 482902564645709, 676254393545935, 110235980231748, 299458232064890, 656749827505033, 963908115927553, 722720798875107, 905063483734809, 990795739600264, 945238054995697, 176905467315680, 259111931319224, 422601938259904, 117159396440728, 409211931685475, 396232968955842, 114107681334804, 654283725172919, 351622702709255, 679987416555993, 641640026840576, 609806003053710, 482822259657548, 356518658585635, 61811805139089, 69776954369190, 207172995482414, 423131926063329, 943649643602454, 293676703457600, 563080562597489, 908147079943053, 310010658630352, 911778151386170, 817768239483378, 693612854841870, 214788531589375, 582512152031643, 757729953753937, 856571657360108, 680607952419663, 916077663157203, 731305462677020, 66803615445082, 419287139690140, 861593185826982, 616548630486552, 565256279891822, 282588409958136, 520541630210605, 767345971760815, 656739637241909, 379580509057753, 932925281918941, 251029261628871, 725236776074076, 670964848242950, 999244627445965, 916872955089430, 213213460785344, 211432261756385, 31972183664064, 951358022841870, 284145155237805, 785243558960859, 106902570235769, 766091290254305, 795338261445944, 309041437408721, 676408097676556, 502688492691042, 305931665252032, 139617780975991, 783387572420705, 318509103806236, 279274843786582, 960812728784, 765420810885287, 675301912122800, 220900827019425, 68258429521733, 500343726947640]
'''题目分析 :
EXP :
from Crypto.Util.number import *
from gmpy2 import *
p = 303597842163255391032954159827039706827
a = 34032839867482535877794289018590990371
cipher=[278121435714344315140568219459348432240, 122382422611852957172920716982592319058, 191849618185577692976529819600455462899, 94093446512724714011050732403953711672, 201558180013426239467911190374373975458, 68492033218601874497788216187574770779, 126947642955989000352009944664122898350, 219437945679126072290321638679586528971, 10408701004947909240690738287845627083, 219535988722666848383982192122753961, 173567637131203826362373646044183699942, 80338874032631996985988465309690317981, 61648326003245372053550369002454592176, 277054378705807456129952597025123788853, 17470857904503332214835106820566514388, 107319431827283329450772973114594535432, 238441423134995169136195506348909981918, 99883768658373018345315220015462465736, 188411315575174906660227928060309276647, 295943321241733900048293164549062087749, 262338278682686249081320491433984960912, 22801563060010960126532333242621361398, 36078000835066266368898887303720772866, 247425961449456125528957438120145449797, 843438089399946244829648514213686381, 134335534828960937622820717215822744145, 74167533116771086420478022805099354924, 249545124784428362766858349552876226287, 37282715721530125580150140869828301122, 196898478251078084893324399909636605522, 238696815190757698227115893728186526132, 299823696269712032566096751491934189084, 36767842703053676220422513310147909442, 281632109692842887259013724387076511623, 205224361514529735350420756653899454354, 129596988754151892987950536398173236050, 97446545236373291551224026108880226180, 14756086145599449889630210375543256004, 286168982698537894139229515711563677530, 100213185917356165383902831965625948491, 268158998117979449824644211372962370753, 264445941122079798432485452672458533870, 87798213581165493463875527911737074678, 131092115794704283915645135973964447801, 164706020771920540681638256590936188046, 178911145710348095185845690896985420147, 154776411353263771717768237918437437524, 260700611701259748940616668959555019434, 222035631087536380654643071679210307962, 281292430628313502184158157303993732703, 24585161817233257375093541076165757776, 269816384363209013058085915818661743171, 39975571110634682056180877801094873602, 125235869385356820424712474803526156473, 218090799597950517977618266111343968738, 144927096680470512196610409630841999788, 213811208492716237073777701143156745108, 64650890972496600196147221913475681291, 302694535366090904732833802133573214043, 214939649183312746702067838266793720455, 219122905927283854730628133811860801459, 224882607595640234803004206355378578645, 260797062521664439666117613111279885285, 279805661574982797810336125346375782066, 147173814739967617543091047462951522968, 23908277835281045050455945166237585493, 186338363482466926309454195056482648936, 295140548360506354817984847059061185817, 151948366859968493761034274719548683660, 96829048650546562162402357888582895187, 61129603762762161772506800496463804206, 83474322431616849774020088719454672415, 25094865151197136947956010155927090038, 86284568910378075382309315924388555908, 269311313874077441782483719283243368999, 293865655623484061732669067594899514872, 42618744258317592068586041005421369378, 54330626035773013687614797098120791595, 147903584483139198945881545544727290390, 290219451327796902155034830296135328101, 147951591390019765447087623264411247959, 176721307425594106045985172455880551666, 10617017342351249793850566048327751981, 166002147246002788729535202156354835048, 43653265786517886972591512103899543742, 191250321143079662898769478274249620839, 142288830015965036385306900781029447609, 231943053864301712428957240550789860578, 259705854206260213018172677443232515015, 42547692646223561211915772930251024103, 210863755365631055277867177762462471179, 140297326776889591830655052829600610449, 136970598261461830690726521708413303997, 93221970399798040564077738881047391445, 192314170920206027886439562261321846026, 95904582457122325051140875987053990027, 158334009503860664724416914265160737388, 134039922705083767606698907224295596883, 7789601161004867293103537392246577269, 261069289329878459425835380641261840913, 123743427894205417735664872035238090896, 20126583572929979071576315733108811761, 5317214299018099740195727361345674110, 68965882674411789667953455991785095270, 235934145208367401015357242228361016868, 250709310980093244562698210062174570956, 167048130489822745377277729681835553856, 122439593796334321806299678109589886368, 117953800124952553873241816859976377866, 226311466875372429157352019491582796620, 301401080214561977683439914412806833619, 255816105091394723475431389696875064495, 73243049441397892506665249226961409560, 226985189100195407227032930008331832009, 164462051705780513134747720427967016844, 97905180778488273557095248936896399883, 40737879120410802220891174679005117779, 180413920169781019749877067396006212488, 171309368917976988181007951396904157090, 215065878665354148046787050342635722874, 54225964222741166664978354789209176721, 179980445108969868669560591527220171967, 39118880593034932654127449293138635964, 170210538859699997092506207353260760212, 62152643864232748107111075535730424573, 28285579676042878568229909932560645217, 69823876778445954036922428013285910904, 170371231064701443428318684885998283021, 211884923965526285445904695039560930451, 2912793651373467597058997684762696593, 220544861190999177045275484705781090327, 142755270297166955179253470066788794096, 264271123927382232040584192781810655563, 214901195876112453126242978678182365781, 252916600207311996808457367909175218824, 176399700725319294248909617737135018444, 230677646264271256129104604724615560658, 1568101696521094800575010545520002520, 276644650735844694794889591823343917140, 185355461344975191330786362319126511681, 248497269558037476989199286642120676823, 27426372552503547932146407600438894266, 99885839446999373024614710052031031159, 238693364649026611386487480573211208980, 27047849084544903200283111147329657123, 261687609401872239323715016608713989139, 34926503987070847956303036393611830590, 252495954285655595492775877967398282722, 249358827602419141539353237669905281246, 42551212101869966935955269842854722856, 286527336123436427709115043975536071462, 158097411156207320921055042509886995091, 40982984899524424348979403377331335675, 87268254405858939730919659372073314983, 142920872841164853694746048293715385493, 280344634952903421792629929689092857993, 203584314487374069738101729666435007339, 76747904284507590577908045394001414841, 18608573158088521401404614102481693137, 104158289118605398449367221892619783009, 182616719368573751169836443225324741716, 272025723760783252166092979911587562064, 24194069309604403496494752448487752613, 71973842397785917741048132725314885345, 281558046604363121112749722271741416764, 66965324704079734796576428718112513855, 105222756356650324548621319241035836840, 331654051401420900830576011369146182, 131087815164777263900650262777429797113, 76104729920151139813274463849368737612, 163253554841934325278065946152769269296, 35973933431510942249046321254376084104, 223355354158871484030430212060934655984, 181704973473887713398031933516341967465, 131391458395622565487686089688656869743, 153029062510158353978320224242258979076, 75598349867958834632866616947240059419, 107656133091853571710502064573530657194, 261653899003034450454605322537555204702, 102387069931966536076616272953425585051, 174654548539988861301269811985320013260, 30731762585661721683653192240732246059, 265493340795853624586170054917042208660, 174818040730242275465453007894471517233, 99514915046145707535310601810631334278, 133978892607644700903700803642408771370, 216019770199630171637325931783378096100, 76687884966028369399497157007109898467, 262185741950606001987209986574269562289, 101935410844521914696784339882721918198, 85956270718878931834010975962772401589, 117578315837774870077915813512746446219, 209811226703488479967593762805568394383, 85782228978690599612110880989543246041, 234993402267259336147096170367513324439, 158487299348452041021565296682698871789, 159701431055714867184644360639841355076, 109022557288733938098734847159477770521, 20764822884655633017647117775843651332, 144987524936939260617020678038224835887, 214906746504968333094519539609226540495, 61852186870193663367998110214331582115, 90175894032076080713807606548780168998, 283504071501037047650569090140982777586, 267695305479884628857258564337611106120, 2466175482923380874813569827625743835, 62561740902965346823256447383892272796, 181458673990444296212252831090106274182, 151903421483215372136947284355251617709, 19545903652854510304023406921387221130, 219205004027218279279153442572018305650, 62495663621315535552427938857863551873, 12365469869484359722316573851483855865, 84444120685499458796249283893323932282, 240719245204462516267560756675192129462, 27868242791206675092288978266113368469, 231956104988320170956546781095814860314, 238410591787987745803829175586952288627, 290649141309468101840354611586699479851, 288298044918505512172272603794059992911, 43375655853069820305921366762777897508, 195308577786654489057887409352840304641, 184459971400898842809886506207633536394, 255884612697066296714973816950917234211, 8695922085804648269560669225439485137, 109407350389195091443836128149623969417, 40151058765649465408124869078260007620, 125484946058191366826510549493690011718, 71132588066103752922321942940739808864, 74434669478187680319595294456652807097, 187368213679294937718535073296853726111, 63461505676143678393259420949793811831, 131619805472714703711458729455838994067, 8579657158619864010437706463902003097, 60626278761876782233388469543817973673, 44776499706241603722632560896220653186, 257249861781237389988455384617803171877, 161899873165011719282095749671993720527, 73303482092538159761390536102771615311, 141674253732456103774983358188317473860, 112299149158347774069079224861237069975, 192409969047313867540459549167233638120, 52560717143548208264188844553309600513, 209294007943747095607573416682772182613, 65285862009539442533024037477398617382, 141465096635701758351979378177631042196, 282970656853503001128091562858564344839, 50475483578642585644452991078499278745, 162546597698227455939743094437394415689, 65258447920153625609456176138520078583, 25184730952052088803921023041299838584, 228883100940853988548836641050823478387, 234342509561041384559923481191578502671, 96929129863331626375704681481278825323, 288533470498072097357398960101692503873, 202238020435442160571930572760188491021, 179010548891454398845389500871076122861, 210509821764943794358893224681677583929, 301357944197101288505771002301759006254, 188933290023352627523422420332593360537, 207946655777875200521742190622482472884, 288626263488145443150622420747070805416, 75616301779108425588545170038742534166, 58163857263381687168244101022135667109, 297006021514663344215599115965804102114, 297690420826548736122127126645053452341, 88307045391242971429880119414942510712, 186427606153958359494215188169120285788, 135488686276533521058776859854524444361, 185380054960856211260651416683468161990, 175033658667416561573078028845860911744, 223026004671602541191897755812121342354, 34657268786986063209312902409995458857, 120560332690000675303295481174067849230, 55304621833927249516093996383526467671, 111480233798478730015825495041130765708, 188996716801525995463705449722399676888, 276300230605454487705048192796463035731, 195951365841304132244984630163178946841, 97383655947416522972353051984313703380, 94486945760999630041197414137963583839, 180706938513681126017333618518691884990, 291355503207799224380050183085704824037, 69034413486375685936282884707402207337, 147750870458026934714106830614187010708, 45030500748522416863096615057804736553, 242760053973560804002707125041520857401, 78549841097746795170488790352479728712, 2356186555504071026416878904180857750, 250486437623828232647064146324392061051, 23443836455198610186212360005846025976, 174557226633145985326629017377610499133, 105578481831185315088267357915446186040, 275620780071666328887795273613981325091, 23435505408737317601794562472269448966, 153209223406380813663608757935808571040, 298537417505667302508269715871007454162, 203833907122687718347615710181705388877, 41923370405573382737900061813058979798, 3762696947926387653032627637114050038, 201362054098012734707571348865729525585, 285561801443127226417656620776228615886, 111526376057659222252771678197929357387, 203857473647840873587593099562928738804, 44500972779851392967974092230683443589, 131565609415497588649207556985146740667, 118140388348838985266223643241117982200, 151449885527204880099343472664885565851, 296392921256617994387220911796693904909, 171323803851876663161606688343678019752, 77152982746512263077542395226111426871, 71648764903315646849225859605038798241, 204032734481806785543119754456569617316, 6308687907566364067313782129902290691, 16601010504475415688487155708691097587, 267844409827567109183739120606590016153, 8224746302136608660764206696943998066, 66759882079234093195284745682061177129, 246382951504754280882643835151081337286, 255668159720160142170457715248631352728, 198682585307670767869381177003851088434, 52435298055396076040371814840062860322, 71487031168170283085378067681578926209, 19270201008106231446848331516948751837, 259975200953378762173082382130139147342, 100957428421542421187997144087873975651, 208596806512779765020431672051552927799, 299145970783704112359526450087000033589, 150947534399996219237186223933189906692, 2048564430495506099844799218948689248, 18962488382754079143174369765373573160, 123031997265327646442638576943887737076, 244982544573374061178705105734141424990, 146410849043938910996544914770892579969, 223289253099676841267315311685506771609, 51374350072145272462874563304717832675, 11071799523780604861063183113721965515, 64879815349665030137608387728274669513, 80407660651138778640313857555610913997, 303240361297474032656368918727922343524, 103535171867293830164396688627880762056, 80560992291681297484967629700766125368, 143230791823232014720768325847406122476, 188716605362804777650654549500430035344, 232870220205325961834389425482865329315, 283584919111555062850512413920721407255, 206566027046056486360456937040463884619, 157265544558229360994066706355140059167, 234540100059557817987307855523008271441, 145080729935010940836509908225154438654, 87632901547252991486640361323948527297, 132851295075144433057295220850764336697, 119332580967710872282556206817561230364, 252662535367310697404410284791596079390, 116953597995893914045234747272641030589, 100249498080127826743176896590140549012, 136127222991007877469608037092253387587, 293872159333237281344632727438901916796, 188380258232793584033919525452891729603, 1610116068556601814921533488550773010, 227538093179017809788576278302184723209, 96083211912155805281570727244009758189, 177565192075026414675108774674272650977, 48610376097473152433617435307712235835, 247706157308906487216795222963091222950, 158089460554439410339817265377357657075, 242596743543458727108836420358578527964, 157838486547678450498998359338995593594, 154936428786673098370270244313756793764, 230069001282099253337070315838992422706, 302203905412042965194022309363722872023, 278925578180003228386990239779184911424, 2121847168422140085785053284950978779, 88186566913792352545205577594300112005, 127051055548524716972172930848069016819, 216775577660712694343189516378309335187, 44934779747684486400910901018161470888, 32429597712898788634301884219187226083, 219683174528279300995710495669083670544, 37001671152735870067433052249003677244, 40408367335919429215031155701333780256, 156957056705864208022145617831060134907, 180077610045061934161783737112285900966, 59357544819520045255625797086421901884, 77751400794807935281264495346525107329, 4517615764752715802675887411287287137, 76319782726782483955139757169428276003, 176009402215469456144386392247781430661, 283055695252017869386094188584670242363, 20001716567499724882317501875143788088, 125228382132280749989067609697418628387, 144053090751393640875176862167012247830, 15289106046221987660093620422889539867, 111243866573605033251079958638430165633, 169264885994758018612038619809803723688, 11895954311759483419234457833286931577, 273147053963507607445612310063799123998, 158981773284803069491507978382595811562, 41293513794446810141896116395025053234, 57441237860743029006005815967510568612, 109171476551418034153338841133917497633, 136539712287056106151501004438585146777, 278918550892367788720071091355436733468, 211360251223022250021398148918837686812, 254351242496347083009146404917085951637, 130260153203964833202474997491055897705, 221930288825889900517852991745469270910, 66354211799382156899053592476719001842, 127898620670768976254134750731374490934, 298131830425274848646460016809595859328, 132109510144911727511061804395381822418, 210917766469026421985352121201196497206, 5441137715689271309917542693016936841, 209516950406881264617228336887254107528, 92275151703152148383106907311559718841, 46255650973652148247469464088017660080, 182628529221607295465655096378164148336, 52574278547120304143820897608762444985, 63698472804719856407197390836793525437, 30457182690865024857724004613999433676, 212073418196280214618461610817423630022, 48875930775858981513092672396243080640, 113234797533868946026347891158142991388, 256534108458875318962058222544020064164, 22522715662428558833985333846937440705, 97553118958308509177643330175409499003, 197088081433425221073434635573357125592, 157303116668734020456228309942188293059, 110316346669278795114546305726864504681, 228887397917708007004920589862367347873, 112210930213921962308944716344585917343, 95017760786235266842788931502689331157, 303479014347753799316861720146531596843, 138677197920058856282155251074088437081, 285912176726299387362893467150449209426, 120309832759140713296686339140142433386, 279125897926861811239250830750932241600, 289502053647872994218190050825294169535, 262459212837236162171047720358005836712, 290390838897912466575239533978002826151, 292988850197951752250595007039860868400, 34796135808311610468205608686622819504, 25206338413385638687826160218013868658, 42180804482932648992176529097078580055, 195897225052351816559125785179252565465, 290060760535408066224831756224248708027, 34243626514368402883316460494646065629, 159497726968729366867935528734367549832, 267785772871046662107247674801793846921, 47342328853090920958565777290912999560, 194980176549393239742230551297786993434, 88020247887557921707284362381274951852, 255474100333005567974457204812640809071, 93324791124684170744053910877870176609, 69542826141091170218040988642070014011, 188678529221313094426441439309063681864, 56030802691247887446204447769438570825, 74312207153349149422500961216106557393, 153811406554673020809393530896156460494, 130232956128662318657579623819323546361, 241587755919930468705435097001858194189, 150548598672513907492388638742866339038, 38780469811591978249139697733603217652, 237554030153815380781978075720171312418, 96541634878634946114738393982914693394, 83284071476491638125716901346418260661, 277535192833115492238855935055373371297, 92291115416977028401374199691398676627, 105634075531674200869064066234662065605, 59669321288506854711632528171527160495, 24913178886798791108798737682436779604, 191902245938756063865405758957515936934, 200833770402179506644143905670947994664, 249327029439265065126080906281744759655, 2368715218056973901783211260781833927, 133209645820509536502329231321782644514, 170083361139958757944996287868734988169, 143242266754832252556264383809361085258, 198438133508477313319510861550461456953, 226416574016152349355240811564666677855, 131995850810926550122710727062184985075, 206211971624338783828953817981719254101, 95022339713176475801874420969255633409, 39239785273544046574575511790952158726, 6761950061835300419279903725369635970, 160849355761964483498641169767552240859, 44129081383649229398785011378026849128, 116611486899507912253396257166983831123, 102748760887182142877957834312659347601, 100973668783270797012352094429175531207, 110548564207426762905750742091610942634, 205424582078496700107783237952155124442, 210932790939110827079725957948996247757, 54413304958149902897514912130730392489, 181315803651356180100745517014898850424, 183346938138867395962624263310328788228, 133507835720650939452036529283981720094, 244220649646693249242542702657146329679, 111814540087048948955999016117121133729, 210757262617434713384638061648414714521, 31712005436857719771604404352654183712, 299210790483067037892753875410776716305, 34216439939230284515095120240039231491, 246820219620854547856488049434101568744, 298588211282375015522910461809769779222, 53320103067319149790078933423751044737, 164977173816081040725650999609390274279, 234782977255751828939911143180631329578, 61521250269407451751766565186333346163, 119529895182262920689181379893081203421, 154588465395872896210615516764102943961, 153034255402211966905777978896125271527, 65497510688725487475002809757533544579, 76824114145168270682129892469858568031, 218064880554787781811938382300930885801, 196850060586188141836799779247809406205, 176023892018381269394229104598502170110, 32491776807255207889633110137157036238, 41150198830446315717651890670848632754, 260753023840843193587871227195221789744, 48345408122882987831052823644867513356, 80045935233531979816083287928071697883, 131878104259519592871955471048058374000, 15534379538690707223440448056318568055, 131291412522855581131329717355299310716, 37018675243998552749630837151597269431, 144343493968520204610097930388908478903, 67236444178494959708570043908346657722, 102574100831305499879105427279131095784, 249069309513964056714882166119752611668, 210718130986716991560768592011623825976, 266242407402824082344585571101593909650, 205203132247422842477137158586071965100, 301157372202750742637385626243753030679, 40886620741595313792996852647181029560, 253361171396328884567373946949359324229, 50071128101197582041162516700015376269, 106002417001877546867386840932652850816, 224086864980106045542532841236299648038, 42103921294151508500634063253613482845, 49777138159264482913170680298952908154, 24324534484842395819609478778764950811, 204106593629836179932302789646808274058, 266707066043760482642609614924857456238, 18723835069315957900598472598907945204, 244338819469013923747256697307964210342, 36296287172854997655950896217230267111, 292888671179451539882069138267865661448, 287111415651274690627399445990831389362, 79940439572496625318602146625920961720, 288270505176661814341807462681727466925, 153921178962139214138689743179633342125, 263564317934507756965522450042219801757, 197993323684501153884855839599466707355, 72143993205715719344183507132882267579, 67511075584002491895239101559049103979, 231396344630318648781207380069016790960, 268490084177254392405211695854127631350, 45968181401712207064942095991325993181, 34472329776995578971329318400545600788, 112967316661320871429337739209994987784, 209508577387521479468956337084132598710, 194445696189141465862938111222574992064, 229942079198360020568341753187100646148, 47944382795398541172186729027517882654, 54806201653083974379270761512143387910, 93457347627015900562505045196097224001, 152033139738914238723733340538181549419, 123719026823969669345162603978875451754, 154704533151410142607151617227929824563, 32428281285686815618553795197210513625, 265229864831280807254743597731258298440, 14904705423314872103792141735779112532, 177442398230615511669857060547212895616, 144918716871520627851549439448066637518, 203019416536984157536348865479415073573, 288452420706913930307744155709559750006, 282516471994395201735206793889605510595, 150722332251745138694381051866105655391, 234504581837296595003379465512031425988, 44178766618576668748878202507789103195, 217129489675072754441642067295058817201, 245087939287551829934600756568137757979, 240954534396950014938672406581264782638]
flag=''
for c in cipher:
if jacobi(c,p)==-1:
flag+='0'
else:
flag+='1'
flag=int(flag,2)
print(long_to_bytes(flag))
# moectf{minus_one_1s_n0t_qu4dr4tic_r4sidu4_when_p_mod_f0ur_equ41_to_thr33}new_system :
from random import randint
from Crypto.Util.number import getPrime,bytes_to_long
flag = b'moectf{???????????????}'
gift = bytes_to_long(flag)
def parametergenerate():
q = getPrime(256)
gift1 = randint(1, q)
gift2 = (gift - gift1) % q
x = randint(1, q)
assert gift == (gift1 + gift2) % q
return q , x , gift1, gift2
def encrypt(m , q , x):
a = randint(1, q)
c = (a*x + m) % q
return [a , c]
q , x , gift1 , gift2 = parametergenerate()
print(encrypt(gift1 , q , x))
print(encrypt(gift2 , q , x))
print(encrypt(gift , q , x))
print(f'q = {q}')
'''
[48152794364522745851371693618734308982941622286593286738834529420565211572487, 21052760152946883017126800753094180159601684210961525956716021776156447417961]
[48649737427609115586886970515713274413023152700099032993736004585718157300141, 6060718815088072976566240336428486321776540407635735983986746493811330309844]
[30099883325957937700435284907440664781247503171217717818782838808179889651361, 85333708281128255260940125642017184300901184334842582132090488518099650581761]
q = 105482865285555225519947662900872028851795846950902311343782163147659668129411
'''题目分析 :
EXP :
from Crypto.Util.number import *
g1=[48152794364522745851371693618734308982941622286593286738834529420565211572487, 21052760152946883017126800753094180159601684210961525956716021776156447417961]
g2=[48649737427609115586886970515713274413023152700099032993736004585718157300141, 6060718815088072976566240336428486321776540407635735983986746493811330309844]
g3=[30099883325957937700435284907440664781247503171217717818782838808179889651361, 85333708281128255260940125642017184300901184334842582132090488518099650581761]
q = 105482865285555225519947662900872028851795846950902311343782163147659668129411
x=inverse(g1[0]+g2[0]-g3[0], q)*(g1[1]+g2[1]-g3[1])%q
gift=(g3[1]-g3[0]*x)%q
print(long_to_bytes(gift))
# moectf{gift_1s_present}RSA_revenge :
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import flag
def emirp(x):
y = 0
while x !=0:
y = y*2 + x%2
x = x//2
return y
while True:
p = getPrime(512)
q = emirp(p)
if isPrime(q):
break
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(f"{n = }")
print(f"{c = }")
"""
n = 141326884939079067429645084585831428717383389026212274986490638181168709713585245213459139281395768330637635670530286514361666351728405851224861268366256203851725349214834643460959210675733248662738509224865058748116797242931605149244469367508052164539306170883496415576116236739853057847265650027628600443901
c = 47886145637416465474967586561554275347396273686722042112754589742652411190694422563845157055397690806283389102421131949492150512820301748529122456307491407924640312270962219946993529007414812671985960186335307490596107298906467618684990500775058344576523751336171093010950665199612378376864378029545530793597
"""题目分析 :
EXP :
from Crypto.Util.number import *
n = 141326884939079067429645084585831428717383389026212274986490638181168709713585245213459139281395768330637635670530286514361666351728405851224861268366256203851725349214834643460959210675733248662738509224865058748116797242931605149244469367508052164539306170883496415576116236739853057847265650027628600443901
c = 47886145637416465474967586561554275347396273686722042112754589742652411190694422563845157055397690806283389102421131949492150512820301748529122456307491407924640312270962219946993529007414812671985960186335307490596107298906467618684990500775058344576523751336171093010950665199612378376864378029545530793597
def find(p,q,bits,c):
if bits==256:
if p*q==n:
print('Find!')
print(p)
q=n//p
print(long_to_bytes(pow(c, inverse(65537, (p-1)*(q-1)),n)))
for pp in range(2):
for qq in range(2):
tmp_p=p+pp*2**(511-bits)+qq*2**bits
tmp_q=q+qq*2**(511-bits)+pp*2**bits
if tmp_p*tmp_q<=n and (tmp_p+2**(511-bits))*(tmp_q+2**(511-bits))>=n and tmp_p*tmp_q%(2**(bits+1))==n%(2**(bits+1)):
find(tmp_p, tmp_q, bits+1, c)
find(0, 0, 0, c)