week4
哎呀数据丢失了
具体分析我就不说了，最简单的证书分析，base64解码后前三个数据分别就是n,e,d。
我当时看得是公主的博客，可以参考:RSA进阶（一） - Kicky_Mu - 博客园 (cnblogs.com)
from Crypto.Util.number import *
from gmpy2 import *
n=0x00bd278484122aef9a69ec647290219ded06edd2b7611721b326850b2f5060daeed7694356667c479ca9ccb6969f4fbe6dc7fa6759aca21d8a96a881a8e4a0217732757e649d503191511fa96da42ed1da2fa3bc8c9c65fbd9c0dd6f430359ac45e455d32c5b0ea29d21e647ff80e50abcbb80f76adb67007a04e85dbaeb4c8f1d
e=0x010001
d=0x2265e355593071ae3501062b4746b5bf7af918cebc5b46879bc3aa0b0aa4f26b68c4fdb7e29f4b2e943a6421f40abe689c6b4f0c21b6c184886d5056f46ca26908540ec07b82ad47e667971a01fac6162e93a7fc61aed5660f826aeba34d78accd18fc59e7921701f10ff51d52883706b864287cfdb34e309c93829d29d867c9
with open("out",'rb') as f:
c=f.read()
m=bytes_to_long(c)
print(long_to_bytes(pow(m,d,n)))
"""30
82 025c
0201 00
02 81 81 00bd278484122aef9a69ec647290219ded06edd2b7611721b326850b2f5060daeed7694356667c479ca9ccb6969f4fbe6dc7fa6759aca21d8a96a881a8e4a0217732757e649d503191511fa96da42ed1da2fa3bc8c9c65fbd9c0dd6f430359ac45e455d32c5b0ea29d21e647ff80e50abcbb80f76adb67007a04e85dbaeb4c8f1d
02 03 010001
02 81 80 2265e355593071ae3501062b4746b5bf7af918cebc5b46879bc3aa0b0aa4f26b68c4fdb7e29f4b2e943a6421f40abe689c6b4f0c21b6c184886d5056f46ca26908540ec07b82ad47e667971a01fac6162e93a7fc61aed5660f826aeba34d78accd18fc59e7921701f10ff51d52883706b864287cfdb34e309c93829d29d867c9
02 41 00c6e091a25cd8e75937af8370674f71ff000ce87a49a8374e654fe3b1877c63813c895c3cb83da4c3bc457aeedef78574bba69b1ac3a21d3fcd0b3a1ffa05aa93
02 41 00f37c0714f1d2e836e73a806ddb3509245539ceb363623d3e4f7887456580519cb513f6564508c8d5ea6b9ccb0b67b58168243bb96d61e8db6377413bbb95fd8f
02404e066d1cb630a3136db57e6beb1c5
02d2b67e50d953859fa77e50fffe697f6b20d7e16a1fbe6b36dd7bfaaab6ceecf7d2ce200984f889ad11d30fa6cf13aa7e1
024100a3c4583f0e27fd68703e3903aadd11390ed9c2dd858b1e063b0da66e56c6e81daeedae52783c60590143404291793febba5
0249ba3a6a72868ce5d61ffd9f2a1
0240369cfe9a217
02c39b0d07fdf8a4d82fe362177dd92fc82
02d699914b9a634016f6e30e270bde8c2d0068743a77d2fa8831cba75536e0f2f1578ddd4e4b5e7685"""
rabin
from Crypto.Util.number import *
flag=b"BaseCTF{}"
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
assert p%4==3 and q%4==3
n = p*q
e = 4
c = pow(m,e,n)
print("p=",p)
print("q=",q)
print("n=",n)
print("c=",c)
print("e=",e)
"""
p= 8531212975719216550108614256955774722172741885676113601617182716356239301381951899737237219659253655889636684200345109462928796329670321336864298557778843
q= 7443256287912111739335729314443559886458007838130371799255078565502662459436043455787869631999073617967343884377537828940738213460508765519478956421282871
n= 63500004625039456439237191267891267558404574431112995926594213383621331385226487443753506088788203040258384788149958095020759745138424276657604371402824844725005596890673468964961037168078105356669148960568974603581485045691990626520286184874115519591663033533771400334558853058140717812903874350138362098253
c= 51452608438757130697131508192775727191605112918772187364577097224326062184288501602000700342623122861398852536963355962672293705131887315354242193416090384360837672258861475017098419459125395949090523474744886423754439919504732741712693909507972791203801494594878447921609420574365853676576693694677914169353
e= 4
"""
高次rabin攻击
\[c\equiv m^4\equiv x^2\mod n\\ c\equiv m^4\equiv x^2\mod p\quad说明c是模p下的二次剩余\\ 可得这条结论c^{\frac{p-1}{2}}\equiv 1\mod p\\ （详细证明看上面NSSCTF中xenny师傅的文章）\\ x^2\equiv c\equiv c^{\frac{p-1}{2}}*c\equiv c^{\frac{p+1}{2}}\mod p\\ 由条件p\equiv3\mod4，可知c^{\frac{p+1}{2}}可以进行开方\\ 得：x_1\equiv c^{\frac{p+1}{4}}\mod p和x_2\equiv(p-c^{\frac{p+1}{4}})\mod p\\ 同理得：x_3\equiv c^{\frac{q+1}{4}}\mod q和x_4\equiv(q-c^{\frac{q+1}{4}})\mod q\\ 之后对x_1,x_2,x_3,x_4都再进行一次rabin就可以得到16个m_i\\ 进行筛选可得最终flag \]
from Crypto.Util.number import *
import math
p= 7069399887135404147313451925856463790122288322955120353958439275669624760478622857767374372872346990136954266792268812402268519788981659317134531701377703
q= 7140401794925570651681210965995716787861669619864423417950517149172165700476247742598189428763096590450485848849559705021102255619953633260576326755189491
n= 50478355643148266354923007679620780526141911052216183219350733856301203909504117920782157926474133059342037694939720794471142298089233400685616528009799838411628460021560455031638939642439782783664643276781622313533393143794433785002028042268329216889290321025657400866309989050114906562764560145969527319173
c= 4087656016708624348430154736700209864616058176527780296412388210036556189223356217878476122554309456912053098904757651242467846016533157893713565869179648449607552843430116377433424175512165110689917185788645907642250661954679293286430479127383793220643392349769864898681882146542120386576626400193522553192
e= 16
def rabin(c):
m1 = pow(c, (p + 1) // 4, p)
m2 = p-pow(c, (p + 1) // 4, p)
m3 = pow(c, (q + 1) // 4, q)
m4 = q-pow(c, (q + 1) // 4, q)
return m1,m2,m3,m4
cs = [c]
lge=math.log(e,2)
for i in range(int(lge)): #range里放log2e
t = set()
for c2 in cs:
x = rabin(c2)
for j in x:
t.add(j)
cs = list(t)
for i in cs:
flag=long_to_bytes(i)
if b'BaseCTF' in flag:
print(flag)
#BaseCTF{01c28b9c-7924-4c04-b71d-1cca15342618}
extendmd5
from Crypto.Util.number import *
import hashlib
import socketserver
import signal
import os
import random
flag = os.getenv('GZCTF_FLAG')
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):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass
def recv(self):
return self._recvall()
def my_md5(self,text):
mymd5=hashlib.md5()
mymd5.update(text)
return mymd5.hexdigest()
def handle(self):
signal.alarm(30)
c=random.randint(1,64)
want=random.randbytes(c)
want_md5=self.my_md5(want)
self.send(want_md5.encode())
while True:
self.send(b"\nPlease input the secret:")
secret = self.recv()
final=want+secret
final_md5=self.my_md5(final)
self.send(b"\nPlease input your md5:")
your_md5=self.recv().decode()
if final_md5 == your_md5:
self.send(flag.encode())
break
self.send(b"\nConnection has been closed =.= ")
self.request.close()
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 9999
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
（前言：循环100次单纯想检验一下写代码解决，而不是直接用别人的脚本生成一个结果就好了，所以可能会有点恶心，请见谅）
就是放在密码里得md5扩展攻击
原始内容长度是随机，爆破一下就可以了。
（以下原理讲的可能不是很清楚，可以看结合第二周web中的视频讲解观看）
原理：
首先需要从md5加密过程开始说起，md5加密是分组进行加密的，每组512bits。在一开始，需要对明文进行填充，如果最后分组不满512bits的需要填充到512bits；如果原始内容刚刚好可以分组，那也需要填充一个512bits的分组。md5扩展攻击最重要的就是理解填充规则。
填充规则：
首先添加一个固定字节b'\x80'，之后需要填充由原始明文长度计算得来的8个字节，这8个字节是一定需要填充的，所以如果这个时候明文已经到达了57bytes，再填充8字节就会不再是刚好的64bytes(512bits)，所以这时候我们要新添一个分组。最后八字节为原始明文长度，填充方式为小端序。
比如len=10，先填上个b'\x80'，这时候长度为11，可以填充8字节，那么再填充b'\x00'*(64-8-1-10)，64为一个分组的字节数，8为最后需要填充的数据，1是最开始填充的b'\x80'，最后填充八个字节为b'\x50\x00\x00\x00\x00\x00\x00\x00'。
比如len=33，先填上个b'\x80'，那么再填充b'\x00'*(64-8-1-33)，最后填充八个字节为b'\x08\x01\x00\x00\x00\x00\x00\x00'。原始数据为264bits，验证：0x108=264
比如len=56，先填上个b'\x80'，这时候有57字节，再填充8字节的话为65字节，那么不满足分组条件，所以这时候我们需要再填充b'\x00'*(64*2-8-1-56)，也就是63个0字节，最后填充八个字节为b'\xc0\x01\x00\x00\x00\x00\x00\x00。原始数据为448bits，验证：0x01c0=448
当我们填充完数据后，从第一个分组开始进行md5加密，加密过程可以不用在意，只需知道每次加密后得到32个16六进制，加密后的结果分成四组，当成下一个分组加密的IV，这是攻击的关键。
一开始，我们知道原始内容的md5值，并且原始内容长度小于64字节。这时候，服务器我们可以在原始内容后面添加自定义数据，那么最重要的就是，根据填充规则，我们只要知道原始内容长度，我们就可以自己进行填充，只要我们自己填充的数据与md5加密时一样，最后计算出的md5值也会一样，那么这个结果是作为下一组内容加密时的IV。
所以我们像服务器发送数据为：填充内容+任意内容
最后发送 任意内容的md5结果，当然这里需要根据服务器一开始传来的md5值作为IV来进行加密
这里我用GPT生成了一份md5加密代码，在加密时传送进去IV值，最重要的是，我这份源码是原始的md5加密代码，我们需要在”任意内容“前填上64bytes*分组数，而且在加密函数(my_md5)中，我们只要最后一个分组的结果，所以我们需要跳过前面几个分组（在代码中skip变量处体现）
from pwn import *
import struct
import math
# 定义MD5所需的常量
T = [int(4294967296 * abs(math.sin(i + 1))) & 0xFFFFFFFF for i in range(64)]
# 定义左旋转函数
def left_rotate(x, c):
return (x << c) | (x >> (32 - c))
# 定义MD5主循环所需的四个基本函数
def F(x, y, z):
return (x & y) | (~x & z)
def G(x, y, z):
return (x & z) | (y & ~z)
def H(x, y, z):
return x ^ y ^ z
def I(x, y, z):
return y ^ (x | ~z)
# 定义MD5算法
def my_md5(message, A, B, C, D, skip):
# 初始化变量
a, b, c, d = A, B, C, D
# 填充消息
original_length = len(message) * 8
message += b'\x80'
while (len(message) * 8) % 512 != 448:
message += b'\x00'
message += struct.pack('<Q', original_length)
# 处理每个512位（64字节）块
# 跳过前几个分组
for i in range(64 * skip, len(message), 64):
block = message[i:i + 64]
X = struct.unpack('<16I', block)
# 备份当前的a, b, c, d值
AA, BB, CC, DD = a, b, c, d
# 进行四轮操作，每轮16步
for i in range(64):
if 0 <= i <= 15:
k, s, func = i, [7, 12, 17, 22][i % 4], F(b, c, d)
elif 16 <= i <= 31:
k, s, func = (5 * i + 1) % 16, [5, 9, 14, 20][i % 4], G(b, c, d)
elif 32 <= i <= 47:
k, s, func = (3 * i + 5) % 16, [4, 11, 16, 23][i % 4], H(b, c, d)
elif 48 <= i <= 63:
k, s, func = (7 * i) % 16, [6, 10, 15, 21][i % 4], I(b, c, d)
temp = b + left_rotate((a + func + X[k] + T[i]) & 0xFFFFFFFF, s)
a, b, c, d = d, temp & 0xFFFFFFFF, b, c
# 将结果加到当前的a, b, c, d
a = (a + AA) & 0xFFFFFFFF
b = (b + BB) & 0xFFFFFFFF
c = (c + CC) & 0xFFFFFFFF
d = (d + DD) & 0xFFFFFFFF
# 返回哈希结果
return struct.pack('<4I', a, b, c, d).hex()
rem = remote("challenge.basectf.fun", 33573)
for _ in range(100):
want_md5 = rem.recv(32).decode() # 接收原始数据的md5
# 计算成iv
iv = []
for i in range(4):
tmp = ""
for j in range(4):
tmp += want_md5[(i + 1) * 8 - (j + 1) * 2:(i + 1) * 8 - j * 2]
iv.append(int(tmp, 16))
# 爆破长度
for i in range(32, 64):
rem.recvuntil(b"Please input the secret:")
# 填充消息
payload = b''
payload_length = i * 8
payload += b'\x80'
while ((i + len(payload)) * 8) % 512 != 448:
payload += b'\x00'
payload += struct.pack('<Q', payload_length)
payload += b'naby'
rem.sendline(payload)
# 计算填充数据后的有几个分组，需要跳过计算
skip = (i + len(payload) - 4) // 64
A, B, C, D = iv
message = b'a' * (64 * skip) + b'naby'
res = my_md5(message, A, B, C, D, skip)
rem.recvuntil(b"Please input your md5:")
rem.sendline(res.encode())
rem.recvline()
m = rem.recvline()
if b'correct' in m:
print(_, want_md5, i, m)
break
rem.interactive()
Fin
猜猜看
from Crypto.Util.number import *
import socketserver
import numpy as np
import random
import ast
import os
flag = os.getenv('GZCTF_FLAG').encode()
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):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass
def recv(self):
return self._recvall()
def handle(self):
assert len(flag)==45
self.send(b"hello.")
m=bytes_to_long(flag)
m=bin(m)[2:]
length=len(m)
x=np.array([int(i) for i in m])
T=np.array([[random.getrandbits(1) for _ in range(length)] for __ in range(length)])
y=np.dot(x,T)
self.send(str(list(y)).encode())
while True:
user_input=ast.literal_eval(self.recv().strip().decode('utf-8'))
if isinstance(user_input,list):
try:
mat=np.array(user_input)
res=list(np.dot(mat,T))
self.send(str(res).encode())
except:
self.send(b'wrong!!')
else:
self.send(b'wrong!')
break
self.send(b"\nConnection has been closed =.= ")
self.request.close()
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 9999
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
灵感来自借nss3rd研究MT19937题目时想出来的点子。
参考：浅析MT19937伪随机数生成算法-安全客 - 安全资讯平台 (anquanke.com)
有提到一个黑盒测试，通过矩阵乘法的性质，利用左乘一个只有一个1，其他都位0的矩阵，可以得到右矩阵的某一行。
import numpy as np
from Crypto.Util.number import *
from pwn import *
p=remote()
p.recvline()
flag=eval(p.recvline())
length=45*8-1
T=[]
for i in range(length):
x=[0]*i+[1]+[0]*(length-1-i)
p.sendline(str(x).encode())
T.append(eval(p.recvline()))
T=np.array(T)
t_ni=np.linalg.inv(T)
m=np.dot(flag,t_ni)
m=np.round(m)
flag=""
for i in m:
if i==1:
flag+='1'
else:
flag+='0'
print(long_to_bytes(int(flag,2)))
p.interactive()
ECB是不安全的
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
import socketserver
import os
import base64
flag = os.getenv('GZCTF_FLAG').encode()
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):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass
def recv(self):
return self._recvall()
def handle(self):
self.send(b"the server will connect you entered to the front of flag.")
self.send(b"then you will receive ciphertext(b64encode) encrypted by AES-ECB.")
key=os.urandom(16)
my_aes=AES.new(key=key,mode=AES.MODE_ECB)
self.send(base64.b64encode(my_aes.encrypt(pad(flag,AES.block_size))))
while True:
self.send(b':')
cin=self.recv()
final=cin+flag
self.send(base64.b64encode(my_aes.encrypt(pad(final,AES.block_size))))
self.send(b"\nConnection has been closed =.= ")
self.request.close()
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 9999
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
灵感来源之前国外的一场，也没有给源码，甚至没有提示。
后面在cryptohack上也遇到了，就拿来出了一题。
这题我们可以在原始内容前面加上 任意内容。
通过测试AES加密的密文，我们可以知道flag的长度。
之后有两种方法，exp里都有写，但是从后往前爆破flag的也个点我没搞懂就先不讲了，只讲从前往后的。
先讲利用原理：ECB模式中，算法对每一个分组进行加密，与前后分组无关，当密钥固定之后，只要这一个分组的明文相同，那么加密之后的密文也相同。
这里直接举个例子。
比如flag是BaseCTF{0123456789}，长度为19.一开始服务器给我们发送密文（base64解密之后）为32字节，为两个AES-ECB分组。我们给服务器依次发送1-16字节的数据，发送一个1字节时，服务器加密20字节，最后密文还是32字节；当发送14字节时，服务器加密33字节，最后密文为48字节，发生了变化，在这时，我们就可以计算出flag长度为32-(14-1)=19。
之后利用刚刚讲的原理，我们发送flag长度填充到一个AES-ECB分组长度减一的内容，比如这里我们发送31字节的a，这时候服务器加密：
\(aaaaaaaaaaaaaaaa|aaaaaaaaaaaaaaB|aseCTF\{0123456789\}\)
之后我们爆破flag的第一个字节，少发送一个字节，这时候服务器加密：
\(aaaaaaaaaaaaaaaa|aaaaaaaaaaaaaaa?|BaseCTF\{0123456789\}\)
当我们爆破到这个字节为B时，服务器加密的第二个分组跟我们第一次发送的第二个分组相同，产生的密文也就相同，那么就可以推断出爆破成功，之后发送数据就要连带上爆破出来的flag。
这里在举爆破一个分组长度后的例子：
此时我们需要爆破flag的第17字节，我们已知flag的前16字节，我们发送(31-16)=15字节的a，得到：
\(aaaaaaaaaaaaaaaB|aseCTF\{012345678|9\}\)
之后爆破第17位，此时发送数据需要带上flag，这是我们发送的数据aaaaaaaaaaaaaaaB|aseCTF{01234567?，最后得到：
\(aaaaaaaaaaaaaaaaB|aseCTF\{01234567?|BaseCTF\{0123456789\}\)
from pwn import *
from Crypto.Util.number import *
import base64
p=remote()
print(p.recvline())
print(p.recvline())
c=p.recvline()[:-1]
c=base64.b64decode(c)
length1=0
for i in range(16):
p.recvline() # b":\n"
payload=b'a'*i
p.sendline(payload)
d=p.recvline()[:-1]
d=base64.b64decode(d)
if len(d)!=len(c):
length1=i
break
length_flag=len(c)-length1
print(length_flag)
# 从前往后爆破flag
payload_length=len(c)+16 # 多一个分组保容错
flag=b''
for i in range(payload_length-1,payload_length-1-length_flag,-1):
p.recvline() # b":\n"
payload=b'a'*i
p.sendline(payload)
d=p.recvline()[:-1]
d=base64.b64decode(d)
for j in range(33,128):
p.recvline() # b":\n"
payload1=b'a'*i+flag+chr(j).encode()
p.sendline(payload1)
e=p.recvline()[:-1]
e=base64.b64decode(e)
e=e[payload_length-16:payload_length]
if e in d:
flag+=chr(j).encode()
break
print(flag)
"""# 从后往前爆破flag(此方法需要知道填充模式)
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
# 在前面填充到满足AES加密的分组长度
dic='{}-BCTF0123456789abcdef'
flag=b''
for i in range(length_flag):
p.recvline() # b":\n"
server_payload=b'a'*(length1+i+1)
p.sendline(server_payload)
server_flag=p.recvline()[:-1]
server_flag=base64.b64decode(server_flag)
for j in dic:
p.recvline() # b":\n"
my_payload=j.encode()+flag
my_payload=pad(my_payload,AES.block_size)
my_payload=my_payload+b'a' # 我也不知道这里为什么要多加一个字节,当i=2时不加这个字节就会出错
p.sendline(my_payload)
my_flag=p.recvline()[:-1]
my_flag=base64.b64decode(my_flag)
my_flag=my_flag[:16]
if my_flag in server_flag:
flag=j.encode()+flag
break
print(flag)"""
p.interactive()
の歪来
from Crypto.Util.number import *
from gmpy2 import *
flag=b''
assert len(flag)==28
m=bytes_to_long(flag)
n=getPrime(2048)
e=32
c=pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)
AMM开根
论文在这里：1111.4877 (arxiv.org)
我还没搞懂，所以直接套用了板子。
我出这题只是想着AMM的常规板子是两个素数求解然后求CRT，我就改成了一个素数，然后小m可以直接得到。
from Crypto.Util.number import *
from gmpy2 import *
import random
import math
p = 17363249226879909675667629533972233798566313669420563155296918020175446973456428454735263489044575257132690882883587342817653451483222705760704890265900885255972067349104579938808591608382992680533327518070878297438339884996059309549300942570104747348751766711833983705979880714174709047335147739991850385244159235504375559144283494800573079055547597410783559965162216203307100248001158445665271438067670522510991047688414176659907164436539491205637933681658814267567385232097679554282863595183422504494357205180093828786415060565003183966959273253039416986816444073158723191290806413175478175738266995214965220231649
e = 32
c = 6840453756562205147103219479843999687625029691496635689045074720240615321966887831642035124198445485320265097191334720798522097422084141332044111764558336174743819347952914775206809737198058220362381349481027893609144697054465070779290329222696236671374412706789862193871687821041053566873553189148668599841084370137084893575567622972476409755187388121177923217208552049876944055745912987536390075417261016809335539362984984190264791744790640858201038207982043569204062714722892105134794280417020318408200038144689432974312283915592134911446185412636709207566063730723406969727969141426530341540330398465744403597273
def onemod(e, q):
p = random.randint(1, q-1)
while(powmod(p, (q-1)//e, q) == 1): # (r,s)=1
p = random.randint(1, q)
return p
def AMM_rth(o, r, q): # r|(q-1
assert((q-1) % r == 0)
p = onemod(r, q)
t = 0
s = q-1
while(s % r == 0):
s = s//r
t += 1
k = 1
while((s*k+1) % r != 0):
k += 1
alp = (s*k+1)//r
a = powmod(p, r**(t-1)*s, q)
b = powmod(o, r*a-1, q)
c = powmod(p, s, q)
h = 1
for i in range(1, t-1):
d = powmod(int(b), r**(t-1-i), q)
if d == 1:
j = 0
else:
j = (-math.log(d, a)) % r
b = (b*(c**(r*j))) % q
h = (h*c**j) % q
c = (c*r) % q
result = (powmod(o, alp, q)*h)
return result
def ALL_Solution(m, q, rt, cq, e):
mp = []
for pr in rt:
r = (pr*m) % q
# assert(pow(r, e, q) == cq)
mp.append(r)
return mp
def calc(mp, mq, e, p, q):
i = 1
j = 1
t1 = invert(q, p)
t2 = invert(p, q)
for mp1 in mp:
for mq1 in mq:
j += 1
if j % 100000 == 0:
print(j)
ans = (mp1*t1*q+mq1*t2*p) % (p*q)
if check(ans):
return
return
def check(m):
try:
a = long_to_bytes(m)
if b'NSSCTF' in a:
print(a)
return True
else:
return False
except:
return False
def ALL_ROOT2(r, q): # use function set() and .add() ensure that the generated elements are not repeated
li = set()
while(len(li) < r):
p = powmod(random.randint(1, q-1), (q-1)//r, q)
li.add(p)
return li
cp = c % p
mp = AMM_rth(cp, e, p)
rt1 = ALL_ROOT2(e, p)
amp = ALL_Solution(mp, p, rt1, cp, e)
for i in amp:
m=long_to_bytes(i)
if b'BaseCTF' in m:
print(m)
break
老涩批了
from Crypto.Util.number import *
import socketserver
import os
import uuid
flag = os.getenv('GZCTF_FLAG').encode()
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):
try:
if newline:
msg += b'\n'
self.request.sendall(msg)
except:
pass
def recv(self):
return self._recvall()
def handle(self):
p=getPrime(256)
q=getPrime(256)
n=p*q
e=65537
d=inverse(e,(p-1)*(q-1))
text=b'BaseCTF{'+str(uuid.uuid4()).encode()+b'}'
m1=bytes_to_long(text[:len(text)//2])
c1=pow(m1,e,n)
m2=bytes_to_long(text[len(text)//2:])
c2=pow(m2,e,n)
self.send(b'n = '+str(n).encode())
self.send(b'e = '+str(e).encode())
self.send(b'c1 = '+str(c1).encode())
self.send(b'c2 = '+str(c2).encode())
while True:
select=self.recv().strip()
if select==b'1':
c=int(self.recv().decode().strip())
m=pow(c,d,n)
res=m&1
elif select==b'2':
c=int(self.recv().decode().strip())
m=pow(c,d,n)
res=long_to_bytes(m,64)[0]
elif select==b'3':
user_text=self.recv().strip()
if user_text==text:
self.send(flag)
break
else:
self.send(b'try again')
break
else :
self.send(b'wrong')
break
self.send(str(res).encode())
self.send(b"\nConnection has been closed =.= ")
self.request.close()
class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
class ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):
pass
if __name__ == "__main__":
HOST, PORT = '0.0.0.0', 9999
server = ForkedServer((HOST, PORT), Task)
server.allow_reuse_address = True
server.serve_forever()
参考了La佬的博客：RSA | Lazzaro (lazzzaro.github.io)
说明一下出题：没点子了，就逛ctfwiki上看到了这个，然后搜了一圈只找到了LSB的代码，MSB没有，我就顺便结合起来了，然后由于GZ这里每个队伍开不同容器flag还是一样的，为了防止多次加密不安全，所以套了一下，先道个歉。
原理我就不献丑了，可以去看看佬们的博客。
from Crypto.Util.number import *
import decimal
from pwn import *
from time import *
rem=remote()
rem.recvuntil(b'n = ')
n=int(rem.recvline().decode().strip())
rem.recvuntil(b'e = ')
e=int(rem.recvline().decode().strip())
rem.recvuntil(b'c1 = ')
c1=int(rem.recvline().decode().strip())
rem.recvuntil(b'c2 = ')
c2=int(rem.recvline().decode().strip())
def server_decode1(c):
rem.sendline(b'1')
sleep(0.01)
rem.sendline(str(c).encode())
rec=rem.recvline().strip()
return rec
kbits = n.bit_length()
decimal.getcontext().prec = kbits
L = decimal.Decimal(0)
R = decimal.Decimal(int(n))
for i in range(kbits):
c1 = (c1 * pow(2, e, n)) % n
recv = server_decode1(c1)
if recv == b'1':
L = (L + R) // 2
else:
R = (L + R) // 2
flag1=long_to_bytes(int((R)))
print(flag1)
sleep(0.01)
def server_decode2(c):
rem.sendline(b'2')
sleep(0.01)
rem.sendline(str(c).encode())
rec=rem.recvline().strip()
return rec
k=1
while True:
c22 = (c2 * pow(2, e*k, n)) % n
res=server_decode2(c22)
res=int(res)
if res&1:
break
k=k+1
L=2**(k-1)
R=2**k
while True:
if R-L==1:
break
x=(L+R)//2
c22 = (c2 * pow(x, e, n)) % n
res=server_decode2(c22)
res=int(res)
if res:
R=x
else :
L=x
flag2=(2**(kbits-8)//L)
print(long_to_bytes(flag2))
user_text=flag1[:-1]+b'-'+long_to_bytes(flag2)
print(user_text)
rem.sendline(b'3')
sleep(0.01)
rem.sendline(user_text)
rem.interactive()
PDP
from Crypto.Util.number import *
from gmpy2 import *
import hashlib
import hmac
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import *
def KeyGen():
while True:
pp=getPrime(512)
p=2*pp+1
while not isPrime(p):
pp=getPrime(512)
p=2*pp+1
qq=getPrime(512)
q=2*qq+1
while not isPrime(q):
qq=getPrime(512)
q=2*qq+1
if pp!=qq:
break
n=p*q
phi=(p-1)*(q-1)
e=getPrime(1024)
d=invert(e,phi)
v=getRandomNBitInteger(128)
g=e**2%n
return (n,g,e,d,v)
def TagBlock(n,g,d,v):
f=open("ABigFile",'rb')
F=f.read()
f.close()
b_size=64 # 64B
block_count=len(F)//b_size + (0 if len(F)%b_size==0 else 1)
W=[]
tags=[]
for i in range(block_count):
Wi=str(v)+str(i)
W.append(Wi)
block=bytes_to_long(F[i*b_size:(i+1)*b_size])
my_md5=hashlib.md5()
my_md5.update(Wi.encode())
tags.append(pow((int(my_md5.hexdigest(),16)*pow(g,block,n))%n,d,n))
return (W,tags)
def GenProof(n,g):
c=randint(400,500)
k1=getRandomNBitInteger(256)
k2=getRandomNBitInteger(160)
s=getRandomNBitInteger(16)
return (c,k1,k2,s,pow(g,s,n))
def gen_proof(n,tags,c,k1,k2,gs,judge=0):
f=open("ABigFile",'rb')
F=f.read()
f.close()
b_size=64 # 64B
if judge:
listF=list(F)
X=[]
for i in range(len(F)//100):
x=randint(0,len(F)-1)
while listF[x]==0:
x=randint(0,len(F)-1)
X.append(x)
listF[x]=0
F=b''
for i in listF:
F+=long_to_bytes(i)
block_count=len(F)//b_size + (0 if len(F)%b_size==0 else 1)
T=1
temp=0
for j in range(c):
my_aes=AES.new(long_to_bytes(k1),mode=AES.MODE_ECB)
i=my_aes.encrypt(pad(long_to_bytes(j),AES.block_size))
i=bytes_to_long(i)%block_count
my_sha256=hashlib.sha256
my_hmac=hmac.new(long_to_bytes(k2),digestmod=my_sha256)
my_hmac.update(long_to_bytes(j))
a=int(my_hmac.hexdigest(),16)%n
T=(T*(pow(tags[i],a,n)))%n
block=bytes_to_long(F[i*b_size:(i+1)*b_size])%n
temp=temp+block*a
temp=pow(gs,temp,n)
my_sha1=hashlib.sha1()
my_sha1.update(str(temp).encode())
rho=int(my_sha1.hexdigest(),16)
return (T,rho)
n,g,e,d,v=KeyGen()
with open("./output/key.txt",'w') as file:
file.write(str(n)+'\n')
file.write(str(e)+'\n')
W,tags=TagBlock(n,g,d,v)
with open("./output/W.txt","w") as file:
for i in W:
file.write(str(i))
file.write('\n')
c,k1,k2,s,gs=GenProof(n,g)
with open("./output/chal.txt",'w') as file:
file.write(str(c)+'\n')
file.write(str(k1)+'\n')
file.write(str(k2)+'\n')
file.write(str(s)+'\n')
T,rho=gen_proof(n,tags,c,k1,k2,gs)
with open("./output/result.txt",'w') as file:
file.write(str(T)+'\n')
flag_md5=hashlib.md5()
flag_md5.update(str(rho).encode())
print(b'BaseCTF{'+flag_md5.hexdigest().encode()+b'}')
我的毕设课题，正好感觉能出成一题就出了，具体不多说，详了解的可以看：naby1/S-PDP (github.com)
from Crypto.Util.number import *
from gmpy2 import *
import hashlib
import hmac
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import *
def CheckProff(n,e,W,c,k1,k2,s,T):
tau=pow(T,e,n)
block_count=len(W)
for j in range(c):
my_aes=AES.new(long_to_bytes(k1),mode=AES.MODE_ECB)
i=my_aes.encrypt(pad(long_to_bytes(j),AES.block_size))
i=bytes_to_long(i)%block_count
my_sha256=hashlib.sha256
my_hmac=hmac.new(long_to_bytes(k2),digestmod=my_sha256)
my_hmac.update(long_to_bytes(j))
a=int(my_hmac.hexdigest(),16)%n
Wi=str(W[i])
my_md5=hashlib.md5()
my_md5.update(Wi.encode())
hw=pow(int(my_md5.hexdigest(),16),a,n)
tau=(tau*invert(hw,n))%n
tau=pow(tau,s,n)
my_sha1=hashlib.sha1()
my_sha1.update(str(tau).encode())
tau=int(my_sha1.hexdigest(),16)
flag_md5=hashlib.md5()
flag_md5.update(str(tau).encode())
print(b'BaseCTF{'+flag_md5.hexdigest().encode()+b'}')
with open("./output/key.txt",'r') as file:
n=int(file.readline())
e=int(file.readline())
W=[]
with open("./output/W.txt","r") as file:
fl=file.readline()
while fl:
W.append(int(fl))
fl=file.readline()
with open("./output/chal.txt",'r') as file:
c=int(file.readline())
k1=int(file.readline())
k2=int(file.readline())
s=int(file.readline())
T=234286400251524464112670458144913694525518333434039777508421611102466502545441606446799021254782625175811569624228349681696143431027926557585053651139957429856785510525021542033961575674601192776283321921860155347475439442726331189839563865687519551977156169783131926796425661730777079164446161030078497564104
CheckProff(n,e,W,c,k1,k2,s,T)
#BaseCTF{d198bce7a2f06ed24d3b043bddbd7512}