HWS
RSA
2022 D^3CTF 原题
from Crypto.Util.number import *
from gmpy2 import *
N=26989781630503676259502221325791347584607522857769579575297691973258919576768826427059198152035415835627885162613470528107575781277590981314410130242259476764500731263549070841939946410404214950861916808234008589966849302830389937977667872854316531408288338541977868568209278283760692866116947597445559763998608870359453835826711179703215320653445704522573070650642347871171425399227090705774976383452533375854187754721093890020986550939103071021619840797519979671188117673303672023522910200606134989916541289908538417562640981839074992935652363458747488201289997240226553340491203815779083605965873519144351105635977
c=15608493359172313429111250362547316415137342033261379619116685637094829328864086722267534755459655689598026363165606700718051739433022581810982230521098576597484850535770518552787220173105513426779515790426303985414120033452747683669501078476628404455341179818932159581239994489678323564587149645006231756392148052557984581049067156468083162932334692086321511063682574943502393749684556026493316348892705114791740287823927634401828970155725090197482067045119003108806888768161101755244340832271562849138340706213702438667804460812804485276133545408754720942940596865774516864097546006862891145251661268265204662316437
e=65537
e1=8334176273377687778925968652923982846998724107624538105654894737480608040787164942908664678429487595866375466955578536932646638608374859799560790357357355475153852315429988251406716837806949387421402107779526648346112857245251481791000156326311794515247012084479404963628187413781724893173183595037984078029706687141452980915897613598715166764006079337996939237831127877822777298891345240992224457502307777453813403723860370336259768714433691700008761598135158249554720239480856332237245140606893060889458298812027643186014638882487288529484407249417947342798261233371859439003556025622531286607093086262182961900221
e2=22291783101991466901669802811072286361463259096412523019927956845014956726984633944311563809077545336731345629003968417408385538540199052480763352937138063001691494078141034164060073208592072783644252721127901996835233091410441838546235477819239598146496144359952946239328842198897348830164467799618269341456666825968971193729838026760012332020223490546511437879465268118749332615890600046622926159177680882780495663448654527562370133394251859961739946007037825763819500955365636946510343942994301809125029616066868596044885547005547390446468651797783520279531291808102209463733268922901056842903640261702268483580079
PR.<x> = PolynomialRing(Zmod(N))
f=e1*e2*x-e2+e1
res=f.monic().small_roots(X=2^1000,beta=0.44)[0]
p=iroot(gcd(ZZ(f(res)),N),6)[0]
q=N//p^7
assert p^7*q==N
d=inverse(0x10001,(p-1)*(q-1))
long_to_bytes(ZZ(pow(c,d,p*q))) random
源博客fuxuqiannian
先开方
开到30次方很奇怪
for i in range(21,36):
a = iroot(n,i)[0]
b = bin(a)
print(a.bit_length())
print(b)成功分解
a = 0b10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000101010000000011110
b = a
p = []
for i in range(10000):
b = next_prime(b)
if(n%b == 0):
p.append(b)
print(p)取指数
num = [0 for i in range(1,10)]
for i in range(len(p)):
while n % p[i] == 0 :
num[i] += 1
n = n//p[i]
print(num)
# [5, 4, 3, 4, 3, 5, 1, 2, 3]有限域内开108次方
位数和n相似只比n小两位，爆破大概十分钟
\(n \ 5251bits\)
\(m \ 5247bits\)
# sage
from threading import Thread
from tqdm import *
from gmpy2 import *
from functools import reduce
from Crypto.Util.number import *
import itertools
from libnum import *
n = 255550794734774347335455038653204099810524562323968101081052744238324333979282590769066826059535810339765419405089707653972316828518446466787073982991340735273047955757161722774546888128720663627716647123110956021905275918358574092054477588935546729192812379266210918802470144452212508255209922150559524376661512464064852413804511191503030046546647554981646983220695416838829085308878177824361071544916728725428437436959573167863053126718594118224053088660739173865895266537548733106779437480905737491231720771570860988017959907437998012442781279100256862684919251885437194156545435396952798548033193683684362049646718627530076461463826459504520525895649547513376441325848313193080013281816762156916219271109726593135112626577858906494025788770088106285316571255392298608980679161123528759865796345121056864973189231253364595956642612401745212207858555858704724770456899071144650909246822311039572915447866615638976747716646382091135281119109866295649034560378368202797914202112090339159898226929176034503535419893300159083361891627300767030933209665917744361038219820997348160094737332979677839131999258559999565207302339242257832022939036526481610130970477187338439181123984340269665409009894192138483254592729253191096427332283419085864095600303323775372526431524911842065699875575955728772820558157791292247976982470646890930951250598649964200733076634093613078091713383782021194766013790646324780327618195433827227105459480409797466859653960886570869469172506894631937612508518886406112758352094014377947728184352908630672750330561369500089138179794848896959683336195170519521
N = n
c = 29259244746260903447574448389058952310000390135231599667104954615635954705912759181552349897154663199516384757779582324312559110410628822220097857204989378367616522573650610718867075518776621505865327181301059226036067398269476892575801933638458560523584293063843890012581096233699743704556897984235725492806550009731913445801481786988321848320254380607620726887530437151238556482879159888862341096974129499878601309077513908335631417136332585391767849651968095851808312565329858938394084369711172343300695636449663297542069122814607488273607842533010193498547579501368165500427762712900139188279259336486273788664239339542187191374015805659616093967428577968683677885747775540903578723024681500272919689849253480672194507905399890280339044782040395397922973935735424691828624724029439840506402735626398047317544972966643810550593849196291833043243448655939654884418027006572740130515844853007135331296523599052132266288322473865775521953742444721612389547052020839760259179074124960827686670217980159612966767064088131176654212504654177367329044762238432531402899949096987765334061101859346928585114984440559379578507872401025874782849854603895110182401204202962118890563473961321104811452539667609870771280348801335004559132482743318366689808669972965573335905879806817618597010442262336079838039317609336210571773187461470707420797827741277982208089496339300646565067740673242728353659143107970717482392927903021102141779217003523105389389513154792904745687959335115429159530013641777064904216646895961910784920181748841104318013067029395394948190384737300533803009402182800702
e = 57564
p_list = p = [mpz(47890485652059026823698344598447161988085597568251161), mpz(47890485652059026823698344598447161988085597568297951), mpz(47890485652059026823698344598447161988085597568338059), mpz(47890485652059026823698344598447161988085597568363667), mpz(47890485652059026823698344598447161988085597568398337), mpz(47890485652059026823698344598447161988085597568433917), mpz(47890485652059026823698344598447161988085597568484111), mpz(47890485652059026823698344598447161988085597568667099), mpz(47890485652059026823698344598447161988085597568729849)]
mi = [5, 4, 3, 4, 3, 5, 1, 2, 3]
# print(len(mi),len(p_list))
n_list = [ZZ(p_list[i]) ** mi[i] for i in range(len(mi))]
# print(n_list)
# print(reduce((lambda x, y: x * y), n_list) - n) # 0
# print(euler_phi(p_list[0])) # 直接求欧拉函数
res=[]
for pi in n_list:
d = inverse(int(e//108),euler_phi(pi)) # 对n_listt 每一个 pi 求欧拉函数
m = pow(c,d,pi) # m = mm^108
res.append(Zmod(pi)(m).nth_root(108, all=True)) # nth_root # 最后一部分把 e 的公因数 108 去除之后用 sage 的 nth_root 直接开根即可，爆破大概7分钟。
# 在每一个pi环里 找到可以开108次方的放进result里面
# 在环里开108次方
# 会出来 9 个 list表 对应每个 pi
for vc in itertools.product(*res):
_c = [int(x) for x in vc]
m = long_to_bytes(int(crt(_c, n_list)))
if b"flag" in m:
print(m)
# b'flag{U_ar3_The_K1ng_oF_rand0m_kin9Dom!}DTv\x8e\x1e\xbdwQ\xdb+ \x92\xc5\\\\\x11|\x81\xd2\xb5\x0b\xec\x98*\xa37\xda\xcaB#\xd5IQ\xe3\x07h4\x86\t\x00\xfe\xec-~+!\xb5H\x074p\xc1c\x9c\xa1\x96|\x8d&\xf9\xdf\x11\xb1%i\\\x86V:\x9dc9%\xaa\x94\x9f\x04\xed1\xa8=\x90L\xfbpr\x90\\(\x85Y\xef\x83\x875:\x12\xa3\x9f\xdc\x8b\xea:\x08T\x02\xc0\x17\xe0\xd9\xb2\x16\xe3\x1b\x11\x97>\xf9\x90h\xb2\x9d\x0c\x1a\xa5\xb8\x99aiv}\x1d\xb4\x8e\xa9\x9d\xce9\x10\x00\xc2||\xf8*\xb0\xeb\x9e\x90<I\xa7\xc3\xde\x90\x0c\xc2\xc2\x92\xd8rX\'\xb4\x17\xc4NE#:q\x83Z\x82\x15\xa74}\xb6\xae\xcd=\xef\xbb\xf8\xb1$d\xba\xef\xd2Z\xff\x00\xa0\xe4\x07\xff \xd4\x15\x15\xe4\x00@)\xfbKp/\xef\x19o:bj\xbb\xca\xa2l\x08\x19\xd9\xe3$;\x8d\x85\xec\x11O\x10\xff\xca\xb5\x07\xed\xb6Xw\xa7\xf4\x14A[t \xa5x\xf7E5\xd1~\xe7\n"\x9e\x12&\x00 \xb0\xc4\x07\xbc\xdc\xcc\x0blb\xa0\xb6\xc0D_\xc0\xaa&\x1d\x96h\xe1\x908c\xdd,d\x01{r\xdeG\xfd{\xfc)L\x92+\x7fa\x9e2\xc4\x84I\x85\xb0b\x9e\x0b<y\x03\xa1x/\x07\n\x08\xfbU\xad\xf5\x0e2\xb2\x10uN\xa83\xd3\x9f\x9a\xd0\xa5L\xda>;v\xd2\xfc\x86\xcb\xc4\x02\xdbo\\{\xf6M\xd4k-\x08\xcc\xd1B+.z\xa9\xfc\x1a\x9f\xd3\xb3\xc3\x95x\x87=I\xd2\x16\x05r\xe5\xdf\xb9e\xbb\x9d\xcc\xec\xcd\x9fyq\xd4v\xf5\xc6\xda\xba\xd3\t\x7fha\xd5 \xbf\xbe\x12D\x15"@\xa9\x80\xab\xd4\xa1\x1c9\x96|\xf6\x92i\x8f!\xa4\xc2y\xd9>>\xac\x13`\xca\xcab\x11}\x1a\xf3GS\x9e\x06\x95\xc4\xd6\xe77\xd8(\x87G*\xf1v\t\xcd\xf7kfg\xcb3\xee}\x8fy\t_<\xde\x0eb\x8c7\xc0\xdfM\xfe\xb8B0\xf6\xad{_\xfe pN\xddPR\xb0\xb7\xdf\xab$B\x1f\x99N\xccd\xe6\xf7\xbe\x02Z\x1c\x01D\xb1\xef#7\xcc\x9d\x19h&s\xc5Exz\xeb\x86\x90\xe2\xc6H\xd2\xc2G\xe1,\x1e\xd4\xd6I\xa8,\x1a\xf8\x00\xbb< \xd9\t\xdb>6\x96:\x9f[\xacF@B\x11\xae\xab\x17\x1f\xec^\xf9\xd69\x0e\r\x011\xce\xb6\x91QX\xbf^hR\xde\xb7&\x1a\x10\x93\xea\x84\x82\x86+\x9d\xc7\xc2T_r\x8eQ\xe3\xc2\x1d\xf3\xa8\x94\xa7\xea'[0ctf 2016]
rsa
贴一个这个题目
有相似
from Crypto.Util.number import *
e=3
n=23292710978670380403641273270002884747060006568046290011918413375473934024039715180540887338067
c=2485360255306619684345131431867350432205477625621366642887752720125176463993839766742234027524
p = 32581479300404876772405716877547
q = 26440615366395242196516853423447
r = 27038194053540661979045656526063
P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()
P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()
P.<a>=PolynomialRing(Zmod(r),implementation='NTL')
g=a^e-c
mrs=g.monic().roots()
flag=[]
for mpp in mps:
x=mpp[0]
for mqq in mqs:
y=mqq[0]
for mrr in mrs:
z=mrr[0]
solution = CRT_list([int(x), int(y),int(z)], [p, q,r])
flag.append(solution)
for i in flag:
m=long_to_bytes(i)
if b'flag' or b'ctf' in m:
print(m)
