2024极客大挑战-CRYPTO-部分WP
凯撒加密
YEI{CKRIUSK_ZU_2024_MKKQ_INGRRKTMK}简单的凯撒，不多说，位移6
flag：
SYC{WELCOME_TO_2024_GEEK_CHALLENGE}RSA
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 = 33108009203593648507706487693709965711774665216872550007309537128959455938833
p = 192173332221883349384646293941837353967
q = 172282016556631997385463935089230918399
c = 5366332878961364744687912786162467698377615956518615197391990327680664213847
'''
最简单的RSA，上板子就出来了，也没什么说的
exp:
import gmpy2
from Crypto.Util.number import *
n = 33108009203593648507706487693709965711774665216872550007309537128959455938833
p = 192173332221883349384646293941837353967
q = 172282016556631997385463935089230918399
c = 5366332878961364744687912786162467698377615956518615197391990327680664213847
e=65537
phi_n =(p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c, d, n)
flag = long_to_bytes(m)
print(flag)
#b'SYC{RSA_is_easy}'
XOR
from Crypto.Util.number import *
from pwn import xor
key = b'...'
flag = b'...'
assert len(key)==4
enc = bytes_to_long(xor(flag,key))
f1 = 4585958212176920650644941909171976689111990
f2 = 3062959364761961602614252587049328627114908
e1 = enc^f1
e2 = e1^f2
print(e2)
"""
10706859949950921239354880312196039515724907
"""
就是简单的异或运算，就是要注意flag1的位数不能被4整除。
from Crypto.Util.number import long_to_bytes
# 给定的数据
f1 = 4585958212176920650644941909171976689111990
f2 = 3062959364761961602614252587049328627114908
e2 = 10706859949950921239354880312196039515724907
# 计算 flag1，也就是enc
flag1 = long_to_bytes(e2 ^ f2 ^ f1)
# 计算 key
flag0 = b'SYC{'
key = bytes([flag1[i] ^ flag0[i] for i in range(4)])
# 辅助函数：将 key 与每四位进行异或操作
def xor(x, key):
return bytes([x[i] ^ key[i % len(key)] for i in range(len(x))])
# 计算最终的 flag
flag = xor(flag1, key)
print(flag) # 输出: b'SYC{a_part_0f_X0R}'
dp
from Crypto.Util.number import getPrime,bytes_to_long
p,q = getPrime(512),getPrime(512)
n = p * q
e = 65537
d = pow(e,-1,(p-1) * (q-1))
dp = d % (p-1)
m = bytes_to_long(flag)
c = pow(m, e, n)
print("c = ",c)
print("n = ",n)
print("e = ",e)
print("dp = ",dp)
'''
c = 127916287434936224964530288403657504450134210781148845328357237956681373722556447001247137686758965891751380034827824922625307521221598031789165449134994998397717982461775225812413476283147124013667777578827293691666320739053915493782515447112364470583788127477537555786778672970196314874316507098162498135060
n = 157667866005866043809675592336288962106125998780791920007920833145068421861029354497045918471672956655205541928071253023208751202980457919399456984628429198438149779785543371372206661553180051432786094530268099696823142821724314197245158942206348670703497441629288741715352106143317909146546420870645633338871
e = 65537
dp = 2509050304161548479367108202753097217949816106531036020623500808413533337006939302155166063392071003278307018323129989037561756887882853296553118973548769
'''简单的dp泄露，也是上板子，分析过程在代码里面
import gmpy2
from Crypto.Util.number import *
c = 127916287434936224964530288403657504450134210781148845328357237956681373722556447001247137686758965891751380034827824922625307521221598031789165449134994998397717982461775225812413476283147124013667777578827293691666320739053915493782515447112364470583788127477537555786778672970196314874316507098162498135060
n = 157667866005866043809675592336288962106125998780791920007920833145068421861029354497045918471672956655205541928071253023208751202980457919399456984628429198438149779785543371372206661553180051432786094530268099696823142821724314197245158942206348670703497441629288741715352106143317909146546420870645633338871
e = 65537
dp = 2509050304161548479367108202753097217949816106531036020623500808413533337006939302155166063392071003278307018323129989037561756887882853296553118973548769
tmp = e * dp - 1
# 根据联立条件有: e*dp = 1 + k(p-1)，故求解p的式子为：(p-1) = (e*dp-1) / k
for k in range(1, e): # 因为K上限只到e，故遍历求解
if tmp % k == 0: # 验证(p-1)是否为整除结果
p = (tmp // k) +1
if n % p == 0: # 验证p能否被n整除
q = n // p
if gmpy2.is_prime(p) and gmpy2.is_prime(q): # 验证求解的p, q是否为素数
break
d = gmpy2.invert(e, (p - 1) * (q - 1)) # 求逆元，de = 1 mod fai(n)
m = gmpy2.powmod(c, d, n) # 幂取模，求明文
flag = long_to_bytes(m)
print(flag)
#b'SYC{welcome_to_crypto}'
共模攻击
from Crypto.Util.number import *
from secret import flag
p,q = [getPrime(1024) for _ in range(2)]
n = p*q
e = [getPrime(10) for _ in range(2)]
m = bytes_to_long(flag)
c = [pow(m, e[i], n) for i in range(2)]
print(f'n = {n}')
print(f'e1 = {e[0]}')
print(f'e2 = {e[1]}')
print(f'c1 = {c[0]}')
print(f'c2 = {c[1]}')
'''
n = 19742875423645690846073637620470497648804310111201409901059297083827103813674034450200432098143959078292346910591785265323563248781526393718834491458926162514713269984791730816121181307827624489725923763353393879316510062227511469438742429290073999388690825732236465647396755899136346150862848924231619666069528077790933176798057396704758072769660663756346237040909579775389576227450505746914753205890194457812893098491264392293949768193694560954874603451253079446652049592976605414438411872223250039782381259212718733455588477129910357095186014496957765297934289263536712574572533650393220492870445376144568199077767
e1 = 911
e2 = 967
c1 = 18676091924461946809127036439355116782539894105245796626898495935702348484076501694838877829307466429933623102626122909782775514926293363853121828819237500456062111805212209491398720528499589486241208820804465599279152640624618194425740368495072591471531868392274503936869225072123214869399971636428177516761675388589238329574042518038702529606188240859751459632643230538522947412931990009143731829484941397093509641320264169403755707495153433568106934850283614529793695266717330769019091782929139589939928210818515744604847453929432990185347112319971445630830477574679898503825626294542336195240055995445217249602983
c2 = 4229417863231092939788858229435938841085459330992709019823280977891432565586698228613770964563920779991584732527715378842621171338649745186081520176123907689669636473919678398014317024138622949923292787095400632018991311254591786179660603414693984024161009444842277220189315861986306573182865656366278782315864366857374874763243428496061153290565891942968876789905670073321426112497113145141539289020571684634406829272902118484670099097148727072718299512735637087933649345419433312872607209633402427461708181971718804026293074540519907755129917132236240606834816534369171888633588190859475764799895410284484045429152
'''
一眼共模攻击，要用到扩展欧几里得算法
import gmpy2
from Crypto.Util.number import *
n = 19742875423645690846073637620470497648804310111201409901059297083827103813674034450200432098143959078292346910591785265323563248781526393718834491458926162514713269984791730816121181307827624489725923763353393879316510062227511469438742429290073999388690825732236465647396755899136346150862848924231619666069528077790933176798057396704758072769660663756346237040909579775389576227450505746914753205890194457812893098491264392293949768193694560954874603451253079446652049592976605414438411872223250039782381259212718733455588477129910357095186014496957765297934289263536712574572533650393220492870445376144568199077767
e1 = 911
e2 = 967
c1 = 18676091924461946809127036439355116782539894105245796626898495935702348484076501694838877829307466429933623102626122909782775514926293363853121828819237500456062111805212209491398720528499589486241208820804465599279152640624618194425740368495072591471531868392274503936869225072123214869399971636428177516761675388589238329574042518038702529606188240859751459632643230538522947412931990009143731829484941397093509641320264169403755707495153433568106934850283614529793695266717330769019091782929139589939928210818515744604847453929432990185347112319971445630830477574679898503825626294542336195240055995445217249602983
c2 = 4229417863231092939788858229435938841085459330992709019823280977891432565586698228613770964563920779991584732527715378842621171338649745186081520176123907689669636473919678398014317024138622949923292787095400632018991311254591786179660603414693984024161009444842277220189315861986306573182865656366278782315864366857374874763243428496061153290565891942968876789905670073321426112497113145141539289020571684634406829272902118484670099097148727072718299512735637087933649345419433312872607209633402427461708181971718804026293074540519907755129917132236240606834816534369171888633588190859475764799895410284484045429152
# 扩展欧几里得算法
# return (r,x,y) 其中，r为a和b的最大公约数，xy满足ax + by = 1
r, s1, s2 = gmpy2.gcdext(e1, e2) # 计算s1，s2
print(r, s1, s2)
m = (gmpy2.powmod(c1, s1, n) * gmpy2.powmod(c2, s2, n)) % n # 计算明文m
m=gmpy2.iroot(m,r)[0]
flag = long_to_bytes(m)
print(flag)
#b'SYC{U_can_really_attack}'
ncoCRT
from Crypto.Util.number import *
import random
flag = b'SYC{...}'
m = bytes_to_long(flag+b'\x01'*23)
p = [0]*5
c = [0]*5
for i in range(5):
p0 = random.randint(2**100,2**101)
p[i] = p0
c = [m%p[i] for i in range(5)]
print(f"p = {p}")
print(f"c = {c}")
"""
p = [1921232050179818686537976490035, 2050175089402111328155892746480, 1960810970476421389691930930824, 1797713136323968089432024221276, 2326915607951286191807212748022]
c = [1259284928311091851012441581576, 1501691203352712190922548476321, 1660842626322200346728249202857, 657314037433265072289232145909, 2056630082529583499248887436721]
"""
看完题就是简单的中国剩余定理也就是CRT，看懂原理写份脚本就是了，如果嫌麻烦给AI也可以。
exp：
from gmpy2 import *
from functools import *
from Crypto.Util.number import *
def uni(P, Q):
r1, m1 = P
r2, m2 = Q
d = gcd(m1, m2)
assert (r2 - r1) % d == 0
l = gcdext(m1 // d, m2 // d)
return (r1 + (r2 - r1) // d * l[1] * m1) % lcm(m1, m2), lcm(m1, m2)
def CRT(eq):
return reduce(uni, eq)
ms= [1921232050179818686537976490035, 2050175089402111328155892746480, 1960810970476421389691930930824, 1797713136323968089432024221276, 2326915607951286191807212748022]
cs = [1259284928311091851012441581576, 1501691203352712190922548476321, 1660842626322200346728249202857, 657314037433265072289232145909, 2056630082529583499248887436721]
x, Lcm = CRT(zip(cs, ms))
print(long_to_bytes(x))
#b'SYC{wha+s_wr0n9!_CRT_bu+_n0+_<0mpr1me!}\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01\x01'
RnoCRT
import hashlib
from Crypto.Util.number import *
from secret import x
m = [getRandomNBitInteger(256) for i in range(10)]
u = hashlib.sha256(x).hexdigest()
assert u[:5]==b'6a651'
flag = b'SYC{'+u+b'}'
c = [x % i for i in m]
print(m)
print(c)
#[207867980504656835313307696396607264603, 245036212212570610987366430554968489325, 270836744824069537438646110613439698666, 319275775495422875474878625752594133023, 254268823435329877199449670714528712873, 213093607196415232366564484229844568444, 246921085368773491003187313772615702950]
#[150031581047390726903711035932621949276, 21260202376534810598778595491323328519, 144049733622518360270048059408969512643, 236920143187836025924037873968303507493, 99781504248790469459151935530031893836, 69236016568483424294966410179787943383, 20613188366058016717435734248097940419]
和上面的nonCRT一样，就是家里一个验证hash值环节，就用最小公倍数进行爆破一下就能出来了
from gmpy2 import *
from functools import *
import hashlib
import itertools
def uni(P, Q):
r1, m1 = P
r2, m2 = Q
d = gcd(m1, m2)
assert (r2 - r1) % d == 0
l = gcdext(m1 // d, m2 // d)
return (r1 + (r2 - r1) // d * l[1] * m1) % lcm(m1, m2), lcm(m1, m2)
def CRT(eq):
return reduce(uni, eq)
m=[207867980504656835313307696396607264603, 245036212212570610987366430554968489325, 270836744824069537438646110613439698666, 319275775495422875474878625752594133023, 254268823435329877199449670714528712873, 213093607196415232366564484229844568444, 246921085368773491003187313772615702950]
c=[150031581047390726903711035932621949276, 21260202376534810598778595491323328519, 144049733622518360270048059408969512643, 236920143187836025924037873968303507493, 99781504248790469459151935530031893836, 69236016568483424294966410179787943383, 20613188366058016717435734248097940419]
x, Lcm = CRT(zip(c, m))
for i in itertools.count(0):
flag = "flag{" + hashlib.sha256(str(x + i * Lcm).encode()).hexdigest() + "}"
if "6a651" in flag:
print(flag)
break
nc
from hashlib import sha256
import socketserver
import os
import signal
import string
import random
flag = "SYC{...}"
class Task(socketserver.BaseRequestHandler):
ctry = 0
def _recvall(self):
BUFF_SIZE = 2048
data = b''
while True:
part = self.request.recv(BUFF_SIZE)
data += part
if len(part) < BUFF_SIZE:
break
return data.strip()
def send(self, msg, newline=True):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass
def recv(self, prompt=b'[-] '):
self.send(prompt, newline=False)
return self._recvall()
def proof_of_work(self):
random.seed(os.urandom(8))
proof = ''.join(
[random.choice(string.ascii_letters+string.digits) for _ in range(20)])
_hexdigest = sha256(proof.encode()).hexdigest()
self.send(f"[+] sha256(XXXX+{proof[4:]}) == {_hexdigest}".encode())
x = self.recv(prompt=b'[+] Plz tell me XXXX: ')
if len(x) != 4 or sha256(x+proof[4:].encode()).hexdigest() != _hexdigest:
return False
return True
def handle(self):
signal.alarm(60)
try:
if not self.proof_of_work():
self.send(b'[!] Wrong!')
self.send(b'[*] Maybe you need a little force, right?')
return
else:
self.send(b'[*] HEY, MY NEW FRIENDDD, YOUUUUUU FIND THE RIGHT WAAAAAAY!')
self.send(b'[*] Or even more complex?')
self.send(b'[*] Maybe these details are not important. See below :D')
signal.alarm(400)
self.send(b'[+] ')
while self.ctry < 35:
data = self.recv().decode()
f = self.oraicle(data)
self.send(f)
self.ctry += 1
except TimeoutError:
self.send(b'[!] Ohhehe, Timeout!')
def oraicle(self,a):
if a.isdigit() and int(a)<33 and int(a)>0:
a = int(a)-1
return b'[+] ' + flag[a].encode()
return b'[!] Invalid Member!'
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
if __name__ == "__main__":
HOST,PORT = '0.0.0.0',12321
server = ForkedServer((HOST,PORT),Task)
server.allow_reuse_address = True
print(HOST, PORT)
server.serve_forever()
这是nc的主机的源码，其实主要就两个部分，先用hash碰撞通过md5验证，再通过通过不断输入有效数字（1到32），从而逐个字符地收集 flag。在收集到所有字符之后，你就可以将它们拼接成完整的 flag。
hash碰撞
import hashlib
hash_value = "bcf23b1235a6118e96e57801fce252c096b618ef37ee698a0f7bce3dfe827d71"
known_String = "l3bskjKkladxrKbi"
chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
# 暴力破解 然后将每个字符串求解sha256与hash_value进行比较
# 注意在使用sha256加密的时候传进的字符串必须是进行编码后的字符串 而且根据题意要比较的hash值是16进制 所以还需要转换成为16进制
for c1 in chars:
for c2 in chars:
for c3 in chars:
for c4 in chars:
key = c1 + c2 + c3 + c4
hash_String = (key + known_String).encode('utf-8')
hash = hashlib.sha256(hash_String).hexdigest()
if hash == hash_value:
print("Foud key:", key)
然后就一个个输入1-32拿到flag(我太菜了，写不来脚本，只能用笨办法了(っ ̯ -｡))，这里给个处理脚本
m='''
1
[+] S
[-] 2
[+] Y
[-] 3
[+] C
[-] 4
[+] {
[-] 5
[+] M
[-] 6
[+] A
[-] 7
[+] Y
[-] 8
[+] B
[-] 9
[+] 3
[-] 10
[+] _
[-] 11
[+] Y
[-] 12
[+] 0
[-] 13
[+] U
[-] 14
[+] _
[-] 15
[+] K
[-] 16
[+] N
[-] 17
[+] 0
[-] 18
[+] W
[-] 19
[+] _
[-] 20
[+] A
[-] 21
[+] 1
[-] 22
[+] A
[-] 23
[+] N
[-] 24
[+] -
[-] 25
[+] B
[-] 26
[+] 3
[-] 27
[+] <
[-] 28
[+] K
[-] 29
[+] 3
[-] 30
[+] R
[-] 31
[+] ?
[-] 32
[+] }
'''
print(m.replace('\n[-] ',"',").replace('\n[+] ',":'"))
d={ 1:'S',2:'Y',3:'C',4:'{',5:'M',6:'A',7:'Y',8:'B',9:'3',10:'_',11:'Y',12:'0',13:'U',14:'_',15:'K',16:'N',17:'0',18:'W',19:'_',20:'A',21:'1',22:'A',23:'N',24:'-',25:'B',26:'3',27:'<',28:'K',29:'3',30:'R',31:'?',32:'}'}
flag=''
for i in range(1,33):
flag+=d[i]
print(flag)
ezRSA
from Crypto.Util.number import *
from secret import flag
m = bytes_to_long(flag)
assert m.bit_length()<500
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
c = pow(m, e, n)
bits = 150
m = (m >> bits) << bits
h = (2024*m-2023) % n
print('n =',n)
print('c =',c)
print('h =',h)
'''
n = 98776098002891477120992675696155328927086322526307976337988006606436135336004472363084175941067711391936982491358233723506086793155908108571814951698009309071244571404116817767749308434991695075517682979438837852005396491907180020541510210086588426719828012276157990720969176680296088209573781988504138607511
c = 9379399412697943604731810117788765980709097637865795846842608472521416662350816995261599566999896411508374352899659705171307916591351157861393506101348972544843696221631571188094524310759046142743046919075577350821523746192424192386688583922197969461446371843309934880019670502610876840610213491163201385965
h = 111518648179416351438603824560360041496706848494616308866057817087295675324528913254309319829895222661760009533326673551072163865
'''
看见m = (m >> bits) << bits，首先想到m的高位泄露，而且c=m^3 modn也给了，用copper就能解出来，现在就想办法解出m，这里应该是出题人数据特意选的，仔细看看就会发现h和n相差很大，应该是因为2024*m-2023小于n,试着这样算发现真的是
h = 111518648179416351438603824560360041496706848494616308866057817087295675324528913254309319829895222661760009533326673551072163865
print((h+2023)%2024)
#0
print((h+2023)//2024)
#55098146333703730947926790790691720107068601034889480665048328600442527334253415639480889244019378785454550164687091675430912
m就算出来了，接下来就是解copper了
exp:
#sage
from Crypto.Util.number import *
n = 98776098002891477120992675696155328927086322526307976337988006606436135336004472363084175941067711391936982491358233723506086793155908108571814951698009309071244571404116817767749308434991695075517682979438837852005396491907180020541510210086588426719828012276157990720969176680296088209573781988504138607511
c = 9379399412697943604731810117788765980709097637865795846842608472521416662350816995261599566999896411508374352899659705171307916591351157861393506101348972544843696221631571188094524310759046142743046919075577350821523746192424192386688583922197969461446371843309934880019670502610876840610213491163201385965
m0=55098146333703730947926790790691720107068601034889480665048328600442527334253415639480889244019378785454550164687091675430912
bits = 150
PR.<x> = PolynomialRing(Zmod(n))
f = (x + m0)^3-c
f=f.monic()
x0 = f.small_roots(X=2^bits, beta=0.2)[0] # find root < 2^kbits with factor >= n^0.3
p = x0 + m0
print(long_to_bytes(m))
#b'SYC{crypto_is_very_interesting_wh@\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00'
highlow
from Crypto.Util.number import *
e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q
pxor = p ^ (bytes_to_long(flag)<<400)
assert len(flag)== 44
m = bytes_to_long(flag)
c = pow(m, e, n)
print('c =',c)
print('n =',n)
print('pxor =',pxor)
'''
c = 11017336122691034053241992293963114590816319844384287448629663672049205892828600396465505710922907685545939978376321927394655458727494361852952898280905220963163625482295222856129164172619564344634365520328815972232825639292605311741655988427166811406091329613627961070231457035303298793651546412496975662225857123805867756651901374507447803198638466304862480202099076813471571495380132563252630789218173007275890600746758285415274434393381125742526014986039652677605642226576741424053749512280825231217420239089105794080707322357602941046822659335487420672699022969372037662958497832065752272061853723653365171768556
n = 14091206320622523674847720139761543154822190879035380245424481267482550932229611965964424965958386255076593911062804299275581742665134207390532802109700225140999812698020838683697375891035625255222001884477214361835101442288725383073334392995186053867261497679234362794914108033574681292656522807928680812726462195077833184018122369579002715900477290345396065912536529290811962117814900448319776590712946259540382461632468634827959957286905806432005632864663985014872365672653476822833921870071851313424903481282350342304819149894610089804321405589433980650340610521659031234826823369114800150883988613877877881069579
pxor = 124229245244085791439650934438639686782423445183921252684721764061493908790073948877623812930339081158169421854801552819088679937157357924845248082716160727839419054107753000815066526032809275137495740454967765165248115412626716101315676902716808647904092798908601183908297141420793614426863816161203796966951
'''
poxr是p的中间几位杯flag异或得到的，顺带一提flag大概351bits，也就是说pxor包含p1024-351=673位，然后就是很简单的用coppersmith解出p就解出来了
from Crypto.Util.number import *
import gmpy2
pxor = 124229245244085791439650934438639686782423445183921252684721764061493908790073948877623812930339081158169421854801552819088679937157357924845248082716160727839419054107753000815066526032809275137495740454967765165248115412626716101315676902716808647904092798908601183908297141420793614426863816161203796966951
c = 11017336122691034053241992293963114590816319844384287448629663672049205892828600396465505710922907685545939978376321927394655458727494361852952898280905220963163625482295222856129164172619564344634365520328815972232825639292605311741655988427166811406091329613627961070231457035303298793651546412496975662225857123805867756651901374507447803198638466304862480202099076813471571495380132563252630789218173007275890600746758285415274434393381125742526014986039652677605642226576741424053749512280825231217420239089105794080707322357602941046822659335487420672699022969372037662958497832065752272061853723653365171768556
n = 14091206320622523674847720139761543154822190879035380245424481267482550932229611965964424965958386255076593911062804299275581742665134207390532802109700225140999812698020838683697375891035625255222001884477214361835101442288725383073334392995186053867261497679234362794914108033574681292656522807928680812726462195077833184018122369579002715900477290345396065912536529290811962117814900448319776590712946259540382461632468634827959957286905806432005632864663985014872365672653476822833921870071851313424903481282350342304819149894610089804321405589433980650340610521659031234826823369114800150883988613877877881069579
e=65537
ph=pxor>>751<<751
pl=pxor-(pxor>>400<<400)
pbar=ph+pl
kbits= 400 #右移位数
PR.<x> = PolynomialRing(Zmod(n))
f = x*2**kbits + pbar
f=f.monic()
x0 = f.small_roots(X=2^351,beta = 0.3)[0] # find root < 2^kbits with factor >= n^0.3
p = int(x0*2**kbits + pbar)
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(long_to_bytes(int(pow(c,d,n))))
#b'SYC{2f521b13bc9d6e932e9f5cbe511112df9e3a9c6}'
Number theory
from Crypto.Util.number import *
m = bytes_to_long(flag)
q = getPrime(1024)
p = getPrime(1024)
q1 = getPrime(1024)
p1 = getPrime(1024)
n = p * q
n1 = p1 * q
h0 = pow(1012 * q + 2024, p1, n1)
print(f"h0 = {h0}")
print(f"n1 = {n1}")
n2 = p * q1
h1 = getPrime(128)*p+getPrime(13)*q1
h2 = getPrime(128)*p+getPrime(13)*q1
print(f"h1 = {h1}")
print(f"h2 = {h2}")
print(f'n2 = {n2}')
e = 65537
c = pow(m, e, n)
print(f'c = {c}')
'''
h0 = 3220497006402049508998763812708472832647814868290156746347730942871191356255789659370553564805270033069126673720344310199953651087754072020225702916105541813428786992668144172000495857408180695235017329451164552864440669887978780387408892281885728829108705426036377534262123812335152528611168777211280571694805002313718755871797426493929314877273385162106226582910473718696585558235361302211164190022765345477880209355073870857330694309139033191510002831755011163554405501084092882774630793037506647051531578470767441695642108269033577519614546722167605348209455599860877630930453549375215766657975702946679735793440
n1 = 20609629372145649869124883931477035418773265506807982287973634398860995335157854064383658546598627777214414513344620919765235474447787454254677033199140440513722365295528339478763686234572386246701669139829187532179573583918405628738545887852577214800663095592976049188005405242091639210252676232732956312108538849591909382864675439965387851084691144379692503823575367370407191667133473482821484955537306602611587604747693171586870973700406072872451067709522642066831289686968535823774273770385924779368338446367102184983154486987531633971065357864924738084803301054789863293592286600424063888458243900130876991944561
h1 = 49194502383195208917988199785355579000471120627698824524136563939112767971337049691779758664899497703009458337602635607307068610164325874221815125058246159504553260658300727486252329656228567456351563661171511248498573151135374757953887871426130912974127123668357951196795364055703535399924661649957282476915345782505912688106575686848420343362888
h2 = 56029812337811022982598747354987989915364610368395101948222609237230875599013444593473706280586983516630982411154519894488542135837471701015074142753084529513202513061481615522865380857058628008542724882609524855349464549317203533208567803034618377155637303135785566874122555481931560957334493233423618193735362609235034574175221191665401074291634
n2 = 21127172569887870569621986802814771398069606826661397979515556618791602174698226712111670185315617811180192688381471253591193212149192104216153890060029438171543010427356810059660168369171504065120474047401466632600230981702536898738744701541132759858595341068713321976579864810553447534204513491008705215041861247277449063318972113826820821732327255577559447446606667162763843696891825420560307688553022453470653875157114663943723258181186659915926780802902213978395961981750159147594076399769386787561910947372748908551775527715538708855235861297549189165238857651886658156332640360898769204102407630920314871304057
c = 5607552428806279725164332098717496105359323731793797865776852054987286366396268835656116948807084338497364746716217052175055013330847114498067023163878490040957130515880922531725226729467904687450269817551037876044274898360914422201634758724176912018795267171627398316542607462818553194467631468793807762529509728325759331142060865432879561622747895422022839077034959965640817419843376693946391886148327389538923557583964708218796910422008150480950732394548385083016293891237783400286493750498647816940000092965104858068292374074379723230507283787259827582725133425982004517180631242028412315096023451549819804660838
'''
两个加密，我们要分别从里面解出p和q，先看q怎么求
n1 = p1 * q
h0 = pow(1012 * q + 2024, p1, n1)
用费马变化一下，再用gcd求公因数，变化过程如下：
import gmpy2
h0 = 3220497006402049508998763812708472832647814868290156746347730942871191356255789659370553564805270033069126673720344310199953651087754072020225702916105541813428786992668144172000495857408180695235017329451164552864440669887978780387408892281885728829108705426036377534262123812335152528611168777211280571694805002313718755871797426493929314877273385162106226582910473718696585558235361302211164190022765345477880209355073870857330694309139033191510002831755011163554405501084092882774630793037506647051531578470767441695642108269033577519614546722167605348209455599860877630930453549375215766657975702946679735793440
n1 = 20609629372145649869124883931477035418773265506807982287973634398860995335157854064383658546598627777214414513344620919765235474447787454254677033199140440513722365295528339478763686234572386246701669139829187532179573583918405628738545887852577214800663095592976049188005405242091639210252676232732956312108538849591909382864675439965387851084691144379692503823575367370407191667133473482821484955537306602611587604747693171586870973700406072872451067709522642066831289686968535823774273770385924779368338446367102184983154486987531633971065357864924738084803301054789863293592286600424063888458243900130876991944561
c = 5607552428806279725164332098717496105359323731793797865776852054987286366396268835656116948807084338497364746716217052175055013330847114498067023163878490040957130515880922531725226729467904687450269817551037876044274898360914422201634758724176912018795267171627398316542607462818553194467631468793807762529509728325759331142060865432879561622747895422022839077034959965640817419843376693946391886148327389538923557583964708218796910422008150480950732394548385083016293891237783400286493750498647816940000092965104858068292374074379723230507283787259827582725133425982004517180631242028412315096023451549819804660838
q=gmpy2.gcd(h0-pow(2024,n1,n1),n1)
print('q=',q)
#q= 118874695786116734917065043442458952547874656505388902849583986739750433740760352688054822604427183355141871756128562592954061494068247418404217180198818025424511398092449124305805738302689459754842048957858402877387959339315483803736974651246922275580029822892751678239186974759117933061631242872453942209471
再来看p
n2 = p * q1
h1 = getPrime(128)*p+getPrime(13)*q1
h2 = getPrime(128)*p+getPrime(13)*q1
光看确实没有什么东西可以帮助我们，但我们发现getPrime(13)，只有13bits,这么小，可以爆破出来p
from Crypto.Util.number import *
import gmpy2
h1 = 49194502383195208917988199785355579000471120627698824524136563939112767971337049691779758664899497703009458337602635607307068610164325874221815125058246159504553260658300727486252329656228567456351563661171511248498573151135374757953887871426130912974127123668357951196795364055703535399924661649957282476915345782505912688106575686848420343362888
h2 = 56029812337811022982598747354987989915364610368395101948222609237230875599013444593473706280586983516630982411154519894488542135837471701015074142753084529513202513061481615522865380857058628008542724882609524855349464549317203533208567803034618377155637303135785566874122555481931560957334493233423618193735362609235034574175221191665401074291634
n2 = 21127172569887870569621986802814771398069606826661397979515556618791602174698226712111670185315617811180192688381471253591193212149192104216153890060029438171543010427356810059660168369171504065120474047401466632600230981702536898738744701541132759858595341068713321976579864810553447534204513491008705215041861247277449063318972113826820821732327255577559447446606667162763843696891825420560307688553022453470653875157114663943723258181186659915926780802902213978395961981750159147594076399769386787561910947372748908551775527715538708855235861297549189165238857651886658156332640360898769204102407630920314871304057
l=[]
for i in range(2**12,2**13):
if isPrime(i):
l.append(i)
for a in l:
for b in l:
x=abs(h1*a-h2*b)
p=gmpy2.gcd(x,n2)
if p!=1:
print('p=',p)
#p= 178557871889789476735392773689039729944728430625818764599203953284194468360955366524476361619864195810267037397001299832526726480560276846147351034417947012223276604383027178163281207815083989579760615671067777036793963045167137767877397560786425871554804100602428308050015870442290953340882348809647523234561
求出了pq就是简单的解RSA了。
from Crypto.Util.number import *
import gmpy2
h1 = 49194502383195208917988199785355579000471120627698824524136563939112767971337049691779758664899497703009458337602635607307068610164325874221815125058246159504553260658300727486252329656228567456351563661171511248498573151135374757953887871426130912974127123668357951196795364055703535399924661649957282476915345782505912688106575686848420343362888
h2 = 56029812337811022982598747354987989915364610368395101948222609237230875599013444593473706280586983516630982411154519894488542135837471701015074142753084529513202513061481615522865380857058628008542724882609524855349464549317203533208567803034618377155637303135785566874122555481931560957334493233423618193735362609235034574175221191665401074291634
n2 = 21127172569887870569621986802814771398069606826661397979515556618791602174698226712111670185315617811180192688381471253591193212149192104216153890060029438171543010427356810059660168369171504065120474047401466632600230981702536898738744701541132759858595341068713321976579864810553447534204513491008705215041861247277449063318972113826820821732327255577559447446606667162763843696891825420560307688553022453470653875157114663943723258181186659915926780802902213978395961981750159147594076399769386787561910947372748908551775527715538708855235861297549189165238857651886658156332640360898769204102407630920314871304057
h0 = 3220497006402049508998763812708472832647814868290156746347730942871191356255789659370553564805270033069126673720344310199953651087754072020225702916105541813428786992668144172000495857408180695235017329451164552864440669887978780387408892281885728829108705426036377534262123812335152528611168777211280571694805002313718755871797426493929314877273385162106226582910473718696585558235361302211164190022765345477880209355073870857330694309139033191510002831755011163554405501084092882774630793037506647051531578470767441695642108269033577519614546722167605348209455599860877630930453549375215766657975702946679735793440
n1 = 20609629372145649869124883931477035418773265506807982287973634398860995335157854064383658546598627777214414513344620919765235474447787454254677033199140440513722365295528339478763686234572386246701669139829187532179573583918405628738545887852577214800663095592976049188005405242091639210252676232732956312108538849591909382864675439965387851084691144379692503823575367370407191667133473482821484955537306602611587604747693171586870973700406072872451067709522642066831289686968535823774273770385924779368338446367102184983154486987531633971065357864924738084803301054789863293592286600424063888458243900130876991944561
c = 5607552428806279725164332098717496105359323731793797865776852054987286366396268835656116948807084338497364746716217052175055013330847114498067023163878490040957130515880922531725226729467904687450269817551037876044274898360914422201634758724176912018795267171627398316542607462818553194467631468793807762529509728325759331142060865432879561622747895422022839077034959965640817419843376693946391886148327389538923557583964708218796910422008150480950732394548385083016293891237783400286493750498647816940000092965104858068292374074379723230507283787259827582725133425982004517180631242028412315096023451549819804660838
e = 65537
q=gmpy2.gcd(h0-pow(2024,n1,n1),n1)
print('q=',q)
l=[]
for i in range(2**12,2**13):
if isPrime(i):
l.append(i)
p = None
for a in l:
for b in l:
x = abs(h1 * a - h2 * b)
p = gmpy2.gcd(x, n2)
if p != 1:
print('p=', p)
break
if p is not None and p != 1:
break
n=p*q
phi_n=(p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
m = gmpy2.powmod(c, d, n)
flag = long_to_bytes(m)
print(flag)
'''
q= 118874695786116734917065043442458952547874656505388902849583986739750433740760352688054822604427183355141871756128562592954061494068247418404217180198818025424511398092449124305805738302689459754842048957858402877387959339315483803736974651246922275580029822892751678239186974759117933061631242872453942209471
p= 178557871889789476735392773689039729944728430625818764599203953284194468360955366524476361619864195810267037397001299832526726480560276846147351034417947012223276604383027178163281207815083989579760615671067777036793963045167137767877397560786425871554804100602428308050015870442290953340882348809647523234561
b'SYC{492aebb6-9c16-4b1a-ac42-fc608bf6063f}'
'''
LLL
from Crypto.Util.number import *
flag = b'******'
m = bytes_to_long(flag)
assert m.bit_length() == 327
p = getPrime(1024)
a = getPrime(1024)
c = getPrime(400)
b = (a*m + c) % p
print(f'a = {a}')
print(f'b = {b}')
print(f'p = {p}')
'''
a = 169790849804323540946197204708402762862586197604183102589270741859708550301920348112941305999764092197996929298474590062625556806793613268527763774013772685954699561684244945434843656515307801882995934869499880288594142919381501796488815033294127591623260894764750214588993456840404443515671353802614450411717
b = 87985708831523238980948938165414984318379459926002798504435964538203443877988599888615810231215118828138306895572062833107988965151522391460216837691927960249874511818878134399363147008042562222910234739940697553852540265617603482995091203105040187460485673579382171260197291783748886765929376179151804062085
p = 131724494512065658801039766546788821718063963144467818735768040631367069153816254855229655449559099188694403260044990366292026916085340250077198735215774149087025577263769846650728593180101073940507285459917860726551385227481715873503612683249433020201729190862430476054822102865441136763977415824331858801617
'''
简单的格密码，需要我们构建格然后配平，然后用格基规约解：
这里我们就构建好了一个格，但显然直接LLL是肯定不行的，还需要对他进行配平，以符合Hermite定理，同时还要让结果位数相近，先算Hermite定理
我们可以知道c、p的bits位数，所以可以打该确定两个数据的大小，这里看了一下后发现是不符合的，于是我们现在要进行配平，这里m尽量不要动，于是我们配平的位置就为左上角的1，算完可以知道变为176bits就符合了，但显然没把位数变得相近，于是我们在327到400间试了一下，发现377bits左右差不多
from Crypto.Util.number import *
a = 169790849804323540946197204708402762862586197604183102589270741859708550301920348112941305999764092197996929298474590062625556806793613268527763774013772685954699561684244945434843656515307801882995934869499880288594142919381501796488815033294127591623260894764750214588993456840404443515671353802614450411717
b = 87985708831523238980948938165414984318379459926002798504435964538203443877988599888615810231215118828138306895572062833107988965151522391460216837691927960249874511818878134399363147008042562222910234739940697553852540265617603482995091203105040187460485673579382171260197291783748886765929376179151804062085
p = 131724494512065658801039766546788821718063963144467818735768040631367069153816254855229655449559099188694403260044990366292026916085340250077198735215774149087025577263769846650728593180101073940507285459917860726551385227481715873503612683249433020201729190862430476054822102865441136763977415824331858801617
M = matrix([[2^377,0, b], [0,1, -a],[0,0,p]])
L = M.LLL()[0]
print(long_to_bytes(L[1]))
#b'SYC{1e989433efffd767589e989ad0f091075c06}'easy_LLL
from Crypto.Util.number import *
m = bytes_to_long(flag)
p = getPrime(1024)
assert m.bit_length() == 255
def encrypt(m):
a = getPrime(1024)
b = getPrime(400)
c = (a * m + b) % p
return c, a
result = [encrypt(m) for i in range(5)]
c = [x[0] for x in result]
a = [x[1] for x in result]
print('p =', p)
print('c =', c)
print('a =', a)
'''
p = 114770017142688382362918268558878024848633097928402093647914503696492833723966801545716194546592346338592062332306371502256979159033965343002132956304625610134374822329402499359634555710129039614275145668904822690744696925414716152630310915301980153974374009140517084226870950134327432658087834138202887501571
c = [25269157674120082500323585451842928560404625967932662908517922704871828513397233858615005968124017428639853960550468542894270451871612496631645175015826203493265945456529848647562285359912541672751550625137876486033809099678631009005979648033707322772087110235116987698692692467320479776960630479772236446980, 75827517416784647262997004080634347924631190865715212882627791181841845414253117114184423517850773219376565782814219713490136873921446382123059696483594598328510450811390866671002685611755205236016843942407419858592870716928648777362367108239158432436307113173823883182666320180058177554647020175991566479974, 4000439731719746534404360339840675006453847582492745979982221624660296805996044239209286181541462187650487112017410839740281883027081539802479046385802021188067656190594734619927933032154534742175380783895559841318520045144113562164247717915766667365412215754183668349398802684299015216478025166881475794536, 16711257143606850336586355581909703391105580636095435863487225535083010317005439435375105800641024112138121810242207127443011036209544967633123983636015153089843815287370646565071784002098183021489882046492609441708361550786752857773565252821037805549119284258373739189052221307754872723967188683410620808193, 106512227999048988543537542345636528925594107128125030635002665980574709006558840446189017357623681828677935125012144689963798865971782914704616798239451971370511961281779438306334353650663495164449411037055054859128957955413918744183200858441122917851347996800797164614883188302584586112732819164555910532500]
a = [177876163920838720585474640511391249051418827853372387342635245341495792468826199544624082182728094652999191797576747605771062756630817438777653951772485569478516324903956113309190795622258346824643390004835397272889256696087356239515881459115499360779486974615331766141255410923960657795391638070660994726539, 154147211832384364492785997490497428696214843927503185938896425556028644075902949520267734189423717477702286854849502563505554965833703544305651488482204719931055591825164774932532116940955079750398001376723036214113076925445019856194390932639722726924707396244454184674407094860919513514591518499956074524561, 162236910312416448303316079284626131452444352290110477620135842885125003493068172330766174225997049094080836685617836911475638508283918576304502582848847097467251286819613975600023439985149604495163647781268904127545271241114039490048103188362740808427663167350820948490766499995036870926879430699822216419877, 156324330649465856865205652642919116551480610060830456323361514761783406613162826555066367215822747145109223530381689780625035795004458919262362420375225560790467893332585836287433463308447660726674632677063603419250881619682710122472587150879771212601074942044613408069114640355658551759306352327418458216623, 94727349364308455432706991721504607810501329870619614073375570944298709074650444442139356318854809081925625009516102978518170343525726627149123655332253529418292440747073463615106501530133930750010290051226765906194210372904323460884238665194406125116885468971886527174150462509520345910607640580833401931201]
'''
这道题和上面那道题一样，就是有5个数据，一样算
p = 114770017142688382362918268558878024848633097928402093647914503696492833723966801545716194546592346338592062332306371502256979159033965343002132956304625610134374822329402499359634555710129039614275145668904822690744696925414716152630310915301980153974374009140517084226870950134327432658087834138202887501571
c = [25269157674120082500323585451842928560404625967932662908517922704871828513397233858615005968124017428639853960550468542894270451871612496631645175015826203493265945456529848647562285359912541672751550625137876486033809099678631009005979648033707322772087110235116987698692692467320479776960630479772236446980, 75827517416784647262997004080634347924631190865715212882627791181841845414253117114184423517850773219376565782814219713490136873921446382123059696483594598328510450811390866671002685611755205236016843942407419858592870716928648777362367108239158432436307113173823883182666320180058177554647020175991566479974, 4000439731719746534404360339840675006453847582492745979982221624660296805996044239209286181541462187650487112017410839740281883027081539802479046385802021188067656190594734619927933032154534742175380783895559841318520045144113562164247717915766667365412215754183668349398802684299015216478025166881475794536, 16711257143606850336586355581909703391105580636095435863487225535083010317005439435375105800641024112138121810242207127443011036209544967633123983636015153089843815287370646565071784002098183021489882046492609441708361550786752857773565252821037805549119284258373739189052221307754872723967188683410620808193, 106512227999048988543537542345636528925594107128125030635002665980574709006558840446189017357623681828677935125012144689963798865971782914704616798239451971370511961281779438306334353650663495164449411037055054859128957955413918744183200858441122917851347996800797164614883188302584586112732819164555910532500]
a = [177876163920838720585474640511391249051418827853372387342635245341495792468826199544624082182728094652999191797576747605771062756630817438777653951772485569478516324903956113309190795622258346824643390004835397272889256696087356239515881459115499360779486974615331766141255410923960657795391638070660994726539, 154147211832384364492785997490497428696214843927503185938896425556028644075902949520267734189423717477702286854849502563505554965833703544305651488482204719931055591825164774932532116940955079750398001376723036214113076925445019856194390932639722726924707396244454184674407094860919513514591518499956074524561, 162236910312416448303316079284626131452444352290110477620135842885125003493068172330766174225997049094080836685617836911475638508283918576304502582848847097467251286819613975600023439985149604495163647781268904127545271241114039490048103188362740808427663167350820948490766499995036870926879430699822216419877, 156324330649465856865205652642919116551480610060830456323361514761783406613162826555066367215822747145109223530381689780625035795004458919262362420375225560790467893332585836287433463308447660726674632677063603419250881619682710122472587150879771212601074942044613408069114640355658551759306352327418458216623, 94727349364308455432706991721504607810501329870619614073375570944298709074650444442139356318854809081925625009516102978518170343525726627149123655332253529418292440747073463615106501530133930750010290051226765906194210372904323460884238665194406125116885468971886527174150462509520345910607640580833401931201]
for i in range(5):
b=c[i]
A=a[i]
M = matrix([[2^400,0, b], [0,1, -A],[0,0,p]])
L = M.LLL()[0]
print(long_to_bytes(abs(L[1])))
'''
b'SYC{125b-5c7b19c7-90e2-8d87c8a8}'
b'SYC{125b-5c7b19c7-90e2-8d87c8a8}'
b'SYC{125b-5c7b19c7-90e2-8d87c8a8}'
b'SYC{125b-5c7b19c7-90e2-8d87c8a8}'
b'SYC{125b-5c7b19c7-90e2-8d87c8a8}'
'''
-
转载
分享
0 条评论
可输入 255 字
发布投稿
热门文章
优秀作者
