CRYPTO
其他题用AI梭，这里就分享两
EZRSA
task.py
from Crypto.Util.number import *
def genarate_emojiiiiii_prime(nbits, base=0):
while True:
p = getPrime(base // 32 * 32) if base >= 3 else 0
for i in range(nbits // 8 // 4 - base // 32):
p = (p << 32) + get_random_emojiiiiii() # 猜一猜
if isPrime(p):
return p
m = bytes_to_long(flag.encode()+ "".join([long_to_bytes(get_random_emojiiiiii()).decode() for _ in range(5)]).encode())
p = genarate_emojiiiiii_prime(512, 224)
q = genarate_emojiiiiii_prime(512)
n = p * q
e = "💯"
c = pow(m, bytes_to_long(e.encode()), n)
print("p0 =", long_to_bytes(p % 2 ** 256).decode())
print("n =", n)
print("c =", c)
p0 = '😘😾😂😋😶😾😳😷'
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
注意到这个p，它是512位的，其中emoji有9位，而且都在低位，由于每个emoji是32位。所以p的高位是224位，题目给出了p的低256位，也就是8个emoji，所以，思路是爆破那个emoji，然后用cooper，
已知288位可copper得到p,(之前我在试能不能出个非预期，就是爆破8位和已知的256位看下copper能不能出，发现不行，可能这题低位泄露那样做不行)
由于emoji的十进制只有最后两位不一样于是只要爆破100位即可，打头是：4036991100
from Crypto.Util.number import *
from tqdm import tqdm
p0 = 108837065531980906150333850570890620719343963272506332719822248235755953428663
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
e = "💯"
init=4036991100
for i in tqdm(range(100)):
PR.<x> = PolynomialRing(Zmod(n))
f=x*2^288+(init+i)*2^256+p0
f=f.monic()
roots = f.small_roots(X=2^225, beta=0.4,epsilon=0.04)
if roots:
if n%p==0:
print(int(roots[0]*2**288+(init+i)*2**256+p0))
break
会发现e和phi不互素
from Crypto.Util.number import *
from gmpy2 import gcd
p=467451634968209241106415317231027845482508518719063451615026255829305974692566892177271
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
q=n//p
e=4036989615
phi=(p-1)*(q-1)
print(gcd(e,phi))
#15
于是有限域开根，利用中国剩余定理
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcd, invert # 'invert' is typically used for computing inverses in gmpy2
p =12424840247075830662687097292458444573014198016321428995092662043898159667123240573630892907827505266982898641483333170032514244713840745287869771915696311
n = 156583691355552921614631145152732482393176197132995684056861057354110068341462353935267384379058316405283253737394317838367413343764593681931500132616527754658531492837010737718142600521325345568856010357221012237243808583944390972551218281979735678709596942275013178851539514928075449007568871314257800372579
c = 47047259652272336203165844654641527951135794808396961300275905227499051240355966018762052339199047708940870407974724853429554168419302817757183570945811400049095628907115694231183403596602759249583523605700220530849961163557032168735648835975899744556626132330921576826526953069435718888223260480397802737401
q = n // p
print(q)
e = 4036989615
phi = (p - 1) * (q - 1)
sea = gcd(e, phi)
e0 = e // sea
d = invert(e0, phi) # Alternatively, you could use: d = inverse(e0, phi) if using Sage's inverse function
# Recover mx
mx = pow(c, d, n)
# For modulus p
R_p.<y> = Zmod(p)[]
mx_p = Zmod(p)(mx) # Explicitly cast mx to Zmod(p)
f_p = y**15 - mx_p
f_p = f_p.monic()
m1 = f_p.roots()
# For modulus q
R_q.<z> = Zmod(q)[]
mx_q = Zmod(q)(mx) # Explicitly cast mx to Zmod(q)
f_q = z**15 - mx_q
f_q = f_q.monic()
m2 = f_q.roots()
print(m2)
# Reconstruct the message via Chinese Remainder Theorem
for root_p, _ in m1:
for root_q, _ in m2:
m = solve_crt([int(root_p), int(root_q)], [int(p), int(q)])
message = long_to_bytes(int(m))
print(message)
if b'TGCTF' in message:
print(message.decode())
#TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢
LLLCG
task.py
from hashlib import sha256
from Crypto.Util.number import getPrime, inverse, bytes_to_long, isPrime
from random import randint
import socketserver
from secret import flag, dsa_p, dsa_q
class TripleLCG:
def __init__(self, seed1, seed2, seed3, a, b, c, d, n):
self.state = [seed1, seed2, seed3]
self.a = a
self.b = b
self.c = c
self.d = d
self.n = n
def next(self):
new = (self.a * self.state[-3] + self.b * self.state[-2] + self.c * self.state[-1] + self.d) % self.n
self.state.append(new)
return new
class DSA:
def __init__(self):
# while True:
# self.q = getPrime(160)
# t = 2 * getPrime(1024 - 160) * self.q
# if isPrime(t + 1):
# self.p = t + 1
# break
self.p = dsa_p
self.q = dsa_q
self.g = pow(2, (self.p - 1) // self.q, self.p)
self.x = randint(1, self.q - 1)
self.y = pow(self.g, self.x, self.p)
def sign(self, msg, k):
h = bytes_to_long(sha256(msg).digest())
r = pow(self.g, k, self.p) % self.q
s = (inverse(k, self.q) * (h + self.x * r)) % self.q
return (r, s)
def verify(self, msg, r, s):
if not (0 < r < self.q and 0 < s < self.q):
return False
h = bytes_to_long(sha256(msg).digest())
w = inverse(s, self.q)
u1 = (h * w) % self.q
u2 = (r * w) % self.q
v = ((pow(self.g, u1, self.p) * pow(self.y, u2, self.p)) % self.p) % self.q
return v == r
class Task(socketserver.BaseRequestHandler):
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):
if newline:
msg += b'\n'
self.request.sendall(msg)
def recv(self, prompt=b'[-] '):
self.send(prompt, newline=False)
return self._recvall()
def handle(self):
n = getPrime(128)
a, b, c, d = [randint(1, n - 1) for _ in range(4)]
seed1, seed2, seed3 = [randint(1, n - 1) for _ in range(3)]
lcg = TripleLCG(seed1, seed2, seed3, a, b, c, d, n)
dsa = DSA()
self.send(b"Welcome to TGCTF Challenge!\n")
self.send(f"p = {dsa.p}, q = {dsa.q}, g = {dsa.g}, y = {dsa.y}".encode())
small_primes = [59093, 65371, 37337, 43759, 52859, 39541, 60457, 61469, 43711]
used_messages = set()
for o_v in range(3):
self.send(b"Select challenge parts: 1, 2, 3\n")
parts = self.recv().decode().split()
if '1' in parts:
self.send(b"Part 1\n")
for i in range(12):
self.send(f"Message {i + 1}: ".encode())
msg = self.recv()
used_messages.add(msg)
k = lcg.next()
r, s = dsa.sign(msg, k)
self.send(f"r = {r}, ks = {[k % p for p in small_primes]}\n".encode())
if '2' in parts:
self.send(b"Part 2\n")
for _ in range(307):
k = lcg.next()
for i in range(10):
self.send(f"Message {i + 1}: ".encode())
msg = self.recv()
k = lcg.next() % dsa.q
r, s = dsa.sign(msg, k)
self.send(f"Signature: r = {r}, s = {s}\n".encode())
used_messages.add(msg)
if '3' in parts:
self.send(b"Part 3\n")
self.send(b"Forged message: ")
final_msg = self.recv()
self.send(b"Forged r: ")
r = int(self.recv())
self.send(b"Forged s: ")
s = int(self.recv())
if final_msg in used_messages:
self.send(b"Message already signed!\n")
elif dsa.verify(final_msg, r, s):
self.send(f"Good! Your flag: {flag}\n".encode())
else:
self.send(b"Invalid signature.\n")
在多组签名中，我们的私钥是一样的，所以我们可以利用多组r,s构造格，就是HNP问题，LCG部分可以不用，算是非预期吧
exp
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcd, invert # 'invert' is typically used for computing inverses in gmpy2
from pwn import*
sh=remote("127.0.0.1",59003)
sh.recvuntil(b'!\n')
sh.recvuntil(b'\n')
sh.recvuntil(b'p = ')
p=int(sh.recvuntil(b',').decode()[:-1])
print('p = ',p)
sh.recvuntil(b'q = ')
q=int(sh.recvuntil(b',').decode()[:-1])
print('q = ',q)
sh.recvuntil(b'g = ')
g=int(sh.recvuntil(b',').decode()[:-1])
print('g = ',g)
sh.recvuntil(b'y = ')
y=int(sh.recvuntil(b'\n').decode()[:-1])
print('y = ',y)
sh.recvuntil(b'] ')
sh.sendline(b'2')
R=[]
S=[]
for i in range(10):
sh.recvuntil(b'] ')
sh.sendline(b'a')
sh.recvuntil(b'r = ')
r=int(sh.recvuntil(b',').decode()[:-1])
sh.recvuntil(b's = ')
s=int(sh.recvuntil(b'\n').decode()[:-1])
R.append(r)
S.append(s)
print(R,S)
print(len(R),len(S))
然后进行HNP，可以参考DSA数字签名 | DexterJie’Blog
from Crypto.Util.number import long_to_bytes
from gmpy2 import gcd, invert # 'invert' is typically used for computing inverses in gmpy2
R=[1021770883701960511201640510248080619540924006035, 939980824533482680071891371385459446417446481575, 321734702046585082499549250057285024121364050648, 590137946580634585425699916726669391077275435190, 389010470607883185570459729637848331362368697588, 1267566333105232950079636588484087666832425168485, 661447467307577463017118086868012137924145398407, 529403064158334841058264011428420779654337823871, 1106580011000751081816782060668695678730882806284, 231243816276112071490230542024917875432952301703]
S=[976289560224399246814179592627217361363606715460, 564075443563819608133729682604966315181766060038, 176492046611389625475944186436593241474903505221, 418702694170005727492996057810310565725866192577, 939492702905681412613217422286443740989487169290, 572233333315427970630247607847915555163210662283, 114921765547548492840109993041777558505058882618, 1286663188240954069077017764113323165750281939960, 559181084332499718142035179645661096802685815385, 113637958382403127180167384659270018402064396431]
import hashlib
from Crypto.Util.number import *
p = 184352699172192576270535944394450689601424152593934253476634864667530549943623545663040121406222033469867822007490624607150449533351028007649079671823930639894259153639431593427418637301705583834256344087212849054820629604266938603002612952530534395948672534275310804229044744624757608906107492972246321630467
q = 1427475768627039429244287846531087092897981204933
g = 179483243075904419855912998377411172058265425529332248345132802466991524049692135618377118498301129461020930474539980424661227889497234584809425572665861532126589551010542468047939006056449514768312598585142121764108071687257917794156000007175743318015987068492602701013540262918705248846831651675444456948643
y = 21091748292290526471555817007802280265346796219876888467762454268134814091273317992821975006174684323984671010080915673195420537285518300367950163468121475755024858761243585366476146847633249721847637924491721703590108964391014720328881200066815781813425008805252191522393702003656562568284814395007242535164
H = [int(hashlib.sha256('a'.encode()).hexdigest(),16) for i in range(10)]
def get_k():
n = len(R)
r0 = R[0]
h0 = H[0]
s0 = S[0]
A = []
B = []
for i in range(n):
a = inverse((r0 * S[i]),q) * (R[i] * s0) % q
b = inverse((r0 * S[i]),q) * (H[i]*r0 - h0 * R[i])
A.append(a)
B.append(b)
Ge = Matrix(ZZ,n+2,n+2)
for i in range(n):
Ge[i,i] = q
Ge[-2,i] = A[i]
Ge[-1,i] = B[i]
K = 2**160
Ge[-2,-2] = 1
Ge[-1,-1] = K
for line in Ge.LLL():
if abs(line[-1]) == K:
return line[-2]
h=H[0]
k= get_k()
print(k)
inv_r=inverse(R[0],q)
x = ((S[0]*k%q-h)*inv_r) % q
print(x)
最后与提交签名
from Crypto.Util.number import *
from hashlib import sha256
from gmpy2 import gcd, invert # 'invert' is typically used for computing inverses in gmpy2
from pwn import*
sh=remote("127.0.0.1",59003)
p = 184352699172192576270535944394450689601424152593934253476634864667530549943623545663040121406222033469867822007490624607150449533351028007649079671823930639894259153639431593427418637301705583834256344087212849054820629604266938603002612952530534395948672534275310804229044744624757608906107492972246321630467
q = 1427475768627039429244287846531087092897981204933
g = 179483243075904419855912998377411172058265425529332248345132802466991524049692135618377118498301129461020930474539980424661227889497234584809425572665861532126589551010542468047939006056449514768312598585142121764108071687257917794156000007175743318015987068492602701013540262918705248846831651675444456948643
y = 21091748292290526471555817007802280265346796219876888467762454268134814091273317992821975006174684323984671010080915673195420537285518300367950163468121475755024858761243585366476146847633249721847637924491721703590108964391014720328881200066815781813425008805252191522393702003656562568284814395007242535164
sh.recvuntil(b'!\n')
sh.recvuntil(b'\n')
x = 1295746761900640917551304835351915400403590832043
sh.recvuntil(b'] ')
sh.sendline(b'3')
end_m=b'b'
sh.recvuntil(b']')
sh.sendline(end_m)
end_h = bytes_to_long(sha256(b'b').digest())
r_ = pow(g,1,p)%q
s_ = ((end_h+x*r_)*inverse(1,q))%q
print(r_,s_)
sh.recvuntil(b']')
sh.sendline(str(r_).encode())
sh.recvuntil(b']')
sh.sendline(str(s_).encode())
sh.recvlines()
sh.interactive()