2023 第六届安洵杯Crypto WP
一、010101
# -*- coding:utf-8 -*-
import os
import random
import string
import hashlib
import socketserver
from Crypto.Util.number import isPrime, long_to_bytes, getStrongPrime, bytes_to_long
flag = b"D0g3{}"
class MyServer(socketserver.BaseRequestHandler):
def proof(self):
random.seed(os.urandom(8))
random_str = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
str_sha256 = hashlib.sha256(random_str.encode()).hexdigest()
self.request.sendall(('SHA256(XXXX + %s):%s\n' % (random_str[4:], str_sha256)).encode())
self.request.sendall('Give Me XXXX:\n'.encode())
XXXX = self.request.recv(2048).strip()
if hashlib.sha256((XXXX + random_str[4:].encode())).hexdigest() != str_sha256:
return False
return True
def getPQN(self):
while True:
p = getStrongPrime(2048)
q = getStrongPrime(2048)
n = p * q
if p.bit_length() 2048 and q.bit_length() 2048 and n.bit_length() == 4096:
return p, q, n
def encrypt(self):
p, q, n = self.getPQN()
m = bytes_to_long(flag)
e = 0x10001
c = pow(m, e, n)
p = bin(p)[2:]
p1 = list(p[:1024])
p2 = list(p[1024:])
p1[random.choice([i for i, c in enumerate(p1) if c == '1'])] = '0'
p2[random.choice([i for i, c in enumerate(p1) if c == '0'])] = '1'
return n, ''.join(p1) + ''.join(p2), c
def handle(self):
if not self.proof():
self.request.sendall(b'Error Hash!')
return
n, p, c = self.encrypt()
self.request.sendall('Press 1 to get ciphertext\n'.encode())
number = self.request.recv(512).strip().decode()
if number == '1':
self.request.sendall((str(n) + '\n').encode())
self.request.sendall((str(p) + '\n').encode())
self.request.sendall((str(c) + '\n').encode())
else:
self.request.sendall('Incorrect input!\n'.encode())
return
class ThreadedTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
if name == '__main__':
sever = socketserver.ThreadingTCPServer(('0.0.0.0', 10001), MyServer)
ThreadedTCPServer.allow_reuse_address = True
ThreadedTCPServer.allow_reuse_port = True
sever.serve_forever()
使用
getStrongPrime生成两个 2048 位的强质数p和q，并计算它们的乘积n作为 RSA 模数。将预设的 flag（密钥信息）转换为长整数
m，然后使用固定的公钥指数e（典型的65537）来计算密文c。代码故意修改了
p的二进制表示，随机选择一个 "1" 改成 "0"，再选择一个 "0" 改成 "1"。
EXP：
既然不知道程序翻转了哪一个“1”，哪一个“0”，那么就通过尝试翻转每一对位，检测修正后的 p 是否为素数且能整除 n ，通过 n 除以修正后的 p，得到另一个质数 q
p q已知，可求出私钥d
from Crypto.Util.number import inverse, long_to_bytes, isPrime
n = 806901386280970687425283178205645199915879018887961438451755440487469539053664984582240245997564028310572787027025270484467759686881741271301026187786083265349128089479689697254391561604562915784917149129389003473816512691697200989449917982980964466770314061138460682064667581021167583944497633063417646205883685631136220667658006115697993547061546056378894644571208332256285300929978924040152075210980284481510427681808374912408867812211468418833758665130104276122779424787620793102517970974196602162311121330978308969159608984641671727042497865724969272277451359292917367965743910956295072929960716017910964650137375477956329487530303617215413164646951414417276666117136992029471642719992696464513353022479243193416840782299236171164287322632583572133887454951892125335338000867652943472810390765040297814895655435003941079105043989591800552505805195397288585256387145460181623844001073901908941941854251966197702804292913614637127351936403804037825353469061801239024788403567545695381846365050182338534902305055093400912351248391340305830423177535113505237261746488738976244664600184915587742673802967577103339980940066214838220720029898921804328913087985698840899487092290478150950452911251270037829431947435653912842611658158143 # 从服务器接收到的n
e = 0x10001
c = 321704276426296568819600015439653283275331254092127249785798006980725603812052605185018165531368234127063970086435935864294765205412921408836856632652357058897614538994307989479240527698688631638484633156391864661336561788068754558765431280172366347927314556437695672750962512483246416354596600622636228920655084584873031808605242425685282021464949029663507158979891698253501413470383195223828257998549703800245571884269261690621397347963560104917225204856547852731584158929272776280675834580105051660928979366144244461206440086721564825718159486486903636744540051720368873320933283000010322896987622736596208585179371287531953415057273578119233977759810650276016764035140677791469907330749487620383826096715871331997482841323266172597454716254350010044172824143827793803412440802167997539580850035937011741544698511182251616337421487089479574787283604850518288256236816238385859945866829652096044959646762121510276349146010839147415735108857493852315811212606304296732199024078373407886645164470075910110056919022448266791841806364852271911906063605870396054880847104762217516989135599069639221993227733845719503693742685753438175234764120193088420538963119443032987510990610764109283542087868753153695322603128367434938970172200612 # 从服务器接收到的密文c
p_bits = "11111110100011001011100101001101100011010010000101010100111000010111001000111101000001010000001000100001111001010100010011011001001011110011010011101111101110001110110000000111111001100100100001110010101011001000101111111110000010010110011000101010001011010111011101111001110100101100001000100011011001000011010111000000100100110011111010001101101011111100101001011111101000011110100110010010100000110001011001011000101100101011111111110110100011100011000110010000000001101110100010111011110001001001011011011100111101110000101000001111111111011000010101111110001001100111110110111101001101010100100111010011101101010111110110111000010110001110101000010111000100011010000010001100100110001101101011010100011110011111100010000110010110111000101100100101011010101101100001100101011000011000011110000101110100111111111100100110010010001101100001011001011010101110010111111010111100111110100100000010000001001111101101001111100110011100101110111001000010110010010111100010110100001101101111111011011010101011010001011111101110001000110101001011111100001111001001101010011110000000010101110010110011011011100101111010111001101110101010110111100000010110000101011000001100101011001011110001101010010010100111100100100101101101010101111000011110010010000010011111011001111001111100110000101111110010110000011000000101111011001010110100010111110111110001000100010011000001100000101111100001011111111011101101101001100101111011111110100011101010100011010100010101011011100110000111000111101101100100000100001101110101000101010111000001101100111111010110111011110011010110111101010101110011001000111111011100111011010100011011001011111110110001010001111001110100011010110110110001000101110110111010000011101010101011101100010001100011010100010111101100000011011000110011111011111001001111101110101010011000110001111001010001101010111001001110101110110000000100001100111111101110011011011000011011010000000011001111010100101010011101000110101111110011111011100101101100010100000110010000111010101011110000110010100000110011101010001010110100011000000011001101" # 从服务器接收到的错误的p的二进制字符串
# 尝试修正p的函数
def correct_p(p_bits):
# 遍历所有位的组合，尝试翻转两位
for i in range(len(p_bits)):
for j in range(i + 1, len(p_bits)):
# 翻转第i位和第j位
corrected_p_bits = list(p_bits)
corrected_p_bits[i] = "1" if corrected_p_bits[i] == "0" else "0"
corrected_p_bits[j] = "1" if corrected_p_bits[j] == "0" else "0"
corrected_p_bits = "".join(corrected_p_bits)
# 将二进制字符串转换为整数
corrected_p = int(corrected_p_bits, 2)
# 检查是否是素数且是n的因子
if isPrime(corrected_p) and n % corrected_p == 0:
return corrected_p
return None
# 尝试修正p
corrected_p = correct_p(p_bits)
if corrected_p is None:
print("Failed to correct p")
else:
# 计算q
q = n // corrected_p
# 确保q也是素数
if not isPrime(q):
print("Failed to correct p: q is not prime")
else:
# 计算私钥d
phi_n = (corrected_p - 1) * (q - 1)
d = inverse(e, phi_n)
# 解密c得到明文m
m = pow(c, d, n)
# 将明文m转换为字节串得到flag
flag = long_to_bytes(m)
print(f"Flag: {flag}")
D0g3{sYuWzkFk12A1gcWxG9pymFcjJL7CqN4Cq8PAIACObJ}
二、POA
# -*- coding:utf-8 -*-
from Crypto.Util.number import isPrime, long_to_bytes, getStrongPrime, bytes_to_long
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
import os
import binascii
import random
import string
import hashlib
import socketserver
FLAG = "{0P@d4Ttk}"
KEY = b'your_key_key_key'
# IV = b'key_key_key_your'
IV = b'D0g3{U_Get_Fl4g}'
def cbc_decrypt(c, iv):
aes = AES.new(KEY, AES.MODE_CBC, iv=iv)
return aes.decrypt(c)
def encrypt():
plain_text = ''.join([random.choice(string.ascii_letters) for _ in range(2)]) + FLAG
aes = AES.new(KEY, AES.MODE_CBC, iv=IV)
plain_text = pad(plain_text.encode(), AES.block_size)
# print(plain_text)
cipher = aes.encrypt(plain_text)
# print(cipher)
# print(cipher.hex())
# print(IV.hex() + cipher.hex())
# print(len(cipher))
return IV.hex() + cipher.hex()
def asserts(pt: bytes):
num = pt[-1]
if len(pt) == 16:
result = pt[::-1]
count = 0
for i in result:
if i == num:
count += 1
else:
break
if count == num:
return True
else:
return False
else:
return False
def decrypt(c):
iv = c[:32]
cipher = c[32:]
plain_text = cbc_decrypt(binascii.unhexlify(cipher), binascii.unhexlify(iv))
if asserts(plain_text):
return True
else:
return False
class MyServer(socketserver.BaseRequestHandler):
def proof(self):
random.seed(os.urandom(8))
random_str = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
str_sha256 = hashlib.sha256(random_str.encode()).hexdigest()
self.request.sendall(('SHA256(XXXX + %s):%s\n' % (random_str[4:], str_sha256)).encode())
self.request.sendall('Give Me XXXX:\n'.encode())
XXXX = self.request.recv(2048).strip()
if hashlib.sha256((XXXX + random_str[4:].encode())).hexdigest() != str_sha256:
return False
return True
def handle(self):
if not self.proof():
self.request.sendall(b'Error Hash!')
return
cipher = encrypt()
self.request.sendall('Welcome to AES System, please choose the following options:\n1. encrypt the flag\n2. decrypt the flag\n'.encode())
# self.request.sendall(''.encode())
# self.request.sendall(''.encode())
n = 0
while n < 65536:
options = self.request.recv(512).strip().decode()
if options == '1':
self.request.sendall(('This is your flag: %s\n' % cipher).encode())
elif options == '2':
self.request.sendall('Please enter ciphertext:\n'.encode())
recv_cipher = self.request.recv(512).strip().decode()
if decrypt(recv_cipher):
self.request.sendall('True\n'.encode())
else:
self.request.sendall('False\n'.encode())
else:
self.request.sendall('Input wrong! Please re-enter\n'.encode())
n += 1
return
class ThreadedTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
if name == '__main__':
sever = socketserver.ThreadingTCPServer(('0.0.0.0', 10010), MyServer)
ThreadedTCPServer.allow_reuse_address = True
ThreadedTCPServer.allow_reuse_port = True
sever.serve_forever()
程序主要实现以下操作（问了gpt才知道的）
加密功能：
使用
encrypt()函数，随机生成一个包含固定 FLAG 的明文，然后用 AES-CBC 模式对其进行加密。加密使用预设的密钥
KEY和初始向量IV。生成的密文与 IV 一起转换为十六进制字符串并返回。
解密验证功能：
decrypt(c)函数接受一个十六进制的密文字符串，从中提取 IV 和密文。使用提取的 IV 和
KEY对密文进行 AES-CBC 解密。使用
asserts()函数检查解密后的明文是否符合 PKCS#7 填充格式，即明文的最后一个字节值指示的数量与尾部重复的字节数量匹配。
EXP:
这题由于采用了AES-CBC方式加密，那么就存在POA攻击（详情可见博客文章AES-CBC算法中Padding Oracle Attack的实现）的可能性。不断构造IV并发送，接收解密结果，恢复AES CBC解密的中间值，最后与IV进⾏异或得到结果
from hashlib import sha256
import itertools
import socket
import string
from Crypto.Util.number import long_to_bytes, bytes_to_long
def proof(broke, Hash):
assert len(broke) == 16 and len(Hash) == 64
shaTable = string.ascii_letters + string.digits
for ii in itertools.permutations(shaTable, 4):
x = "".join(ii)
s = x + broke
if sha256(s.encode()).hexdigest() == Hash:
print(x)
return x
def con():
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("124.71.177.14", 10010))
proof_data = sock.recv(2048)
send_proof = (
proof(proof_data[14:30].decode(), proof_data[32:96].decode())
).encode()
sock.recv(2048)
sock.send(send_proof)
data1 = sock.recv(2048)
print(data1.decode())
sock.send("1\n".encode())
cipher = sock.recv(4096).decode().split(" ")[-1]
print(cipher)
guess_iv = [0 for _ in range(16)]
restore_midd = [0 for _ in range(16)]
index = 1
for i in range(15, -1, -1):
for j in range(0, 256):
sock.send("2".encode())
txt = sock.recv(4096).decode()
guess_iv[i] = j
mess = bytes(guess_iv).hex() + cipher[32:]
sock.send(("%s\n" % mess).encode())
result = sock.recv(4096).strip().decode()
if result == "True":
print("find")
restore_midd[i] = index ^ j
for k in range(15, i - 1, -1):
guess_iv[k] = restore_midd[k] ^ (index + 1)
break
index += 1
m = bytes_to_long(bytes(restore_midd)) ^ int(cipher[:32], 16)
print(long_to_bytes(m))
if __name__ == "__main__":
con()
三、RABIN
# -*- coding:utf-8 -*-
import os
import random
import string
import hashlib
import socketserver
from secret import *
import uuid
import gmpy2
from Crypto.Util.number import isPrime, long_to_bytes, getStrongPrime, bytes_to_long
def get_flag(head):
table = string.printable
name = ''.join([random.choice(table) for i in range(10)])
return head + '{' + str(uuid.uuid5(uuid.NAMESPACE_OID, name)) + '}'
def relation():
a, b = 0, 0
for i in range(x - (2**2 - 1)):
a += pow(e1, i)
for j in range(3):
b += pow(e2, j)
if a == b:
return True
return False
def get_pqr():
while True:
p = getStrongPrime(1024)
q = getStrongPrime(1024)
if p % 4 3 and q % 4 3:
break
r = 2
while True:
r = r * x
if r.bit_length() > 1024 and isPrime(r - 1):
r = r - 1
break
return p, q, r
def encrypt():
# if relation():
# print('success')
# else:
# print('false')
flag = 'D0g3{82309bce-9db6-5340-a9e4-a67a9ba15345}' # get_flag('D0g3')
m1 = ''.join([random.choice(string.ascii_letters) for _ in range(234)]) + ' ' + flag[:21]
m2 = flag[21:] + ' ' + ''.join([random.choice(string.ascii_letters) for _ in range(234)])
p, q, r = get_pqr()
phi = (p - 1) (q - 1) (q - 1)
while True:
try:
d = gmpy2.invert(e2, phi)
break
except Exception as e:
p, q, r = get_pqr()
n = p q r
inv_p = gmpy2.invert(p, q)
inv_q = gmpy2.invert(q, p)
# print(e1, e2)
c1 = pow(bytes_to_long(m1.encode()), e1, n)
c2 = pow(bytes_to_long(m2.encode()), e2, n)
return n, inv_p, inv_q, c1, c2
# print("n = %d" % n)
# print("ip = %d" % inv_p)
# print("iq = %d" % inv_q)
# print("c1 = %d" % c1)
# print("c2 = %d" % c2)
class MyServer(socketserver.BaseRequestHandler):
def proof(self):
random.seed(os.urandom(8))
random_str = ''.join([random.choice(string.ascii_letters + string.digits) for _ in range(20)])
str_sha256 = hashlib.sha256(random_str.encode()).hexdigest()
self.request.sendall(('SHA256(XXXX + %s):%s\n' % (random_str[4:], str_sha256)).encode())
self.request.sendall('Give Me XXXX:\n'.encode())
XXXX = self.request.recv(2048).strip()
if hashlib.sha256((XXXX + random_str[4:].encode())).hexdigest() != str_sha256:
return False
return True
def handle(self):
if not self.proof():
self.request.sendall(b'Error Hash!')
return
n, inv_p, inv_q, c1, c2 = encrypt()
self.request.sendall('Press 1 to get ciphertext\n'.encode())
number = self.request.recv(512).strip().decode()
if number == '1':
self.request.sendall(("n = %d\n" % n).encode())
self.request.sendall(("inv_p = %d\n" % inv_p).encode())
self.request.sendall(("inv_q = %d\n" % inv_q).encode())
self.request.sendall(("c1 = %d\n" % c1).encode())
self.request.sendall(("c2 = %d\n" % c2).encode())
else:
self.request.sendall('Incorrect input!\n'.encode())
return
class ThreadedTCPServer(socketserver.ThreadingMixIn, socketserver.TCPServer):
pass
if name == '__main__':
sever = socketserver.ThreadingTCPServer(('0.0.0.0', 10100), MyServer)
ThreadedTCPServer.allow_reuse_address = True
ThreadedTCPServer.allow_reuse_port = True
sever.serve_forever()
这道题不同寻常的考察了特殊的RSA算法的特殊算法——Rabin加密，是本次难度最高的密码学题
Rabin算法是一种公钥加密算法，由迈克尔·拉宾（Michael Rabin）在1979年发明。它是基于大数因数分解问题的困难性，类似于RSA算法，但在一些方面提供了更强的安全保证。Rabin算法的核心思想和RSA算法类似，都利用了大质数的乘积作为密钥的一部分。使用私钥 p 和 q，密文 c 可以通过求解模 p 和 q 下的平方根，再应用中国剩余定理（CRT）来恢复明文 m。由于每个模方程可能有两个解，解密过程通常会得到四个潜在的明文候选，需要额外信息来确定正确的明文。
EXP:
解⽅程恢复e1， e2 解RSA+RSA Rabin
from Crypto.Util.number import isPrime, long_to_bytes
from decimal import Decimal, getcontext
from sympy import *
import itertools
import gmpy2
getcontext().prec = 4096 # To get all digits
def quadratic(b, c):
b, c = Decimal(b), Decimal(c)
disc = b**2 - 4 * c
return (-b + disc.sqrt()) / 2, (-b - disc.sqrt()) / 2
n = 250814637051807819966792611245960610922650272171774421100096725362876110354331644672361070288421932814011240278013930236506935606208856158245203226575206173399353228955646434946185162337249508916173886601690750176079643923598040239558820163968619858461299932945052867416892052800080380065469520552769729908237916948231811852512702334673059498173828710097943836553665421008502790227505238045663138503444330272778394062239358945912631242535901236920740968520395320695821881700272436374765803456467229511027996411612705127440152548517761802229692762942039810655711762857733655968843311390554894490989464889063115195307376546315206091850157113517967028388112696773322299195386885674487736953704278131208605733928620385647653506188387270203806469091593555942596009391614056683438954798377100513743826890914546813802825956772601161008749865452605755445313141047898707485333785540081269386385654187051443297745903924802393853636159179216465330611652590550085005018159338383332480775331023418636856327968211907
inv_p = 18572680482956333849695203716461713104773047923602099298094682396862191850514405358287530759577107822437397076448196882484810348534389142512538132336772660002619635584317411507556898261467535786390472312057865009529503815275471152631242674775023579999529144217652870406017527500924054906365970316171601724395
inv_q = 136535048380593205200147274200607623672178047616047871024461976135751463050074132537068629202262492753981526789311501011207084603084500046237452580036584406621193450044354252290673799669278685039786072212806149907642025392079172459205884032545048534994511661271942133535933734878627347694553081776269463131011
c1 = 24438369699277358577099809092522666507794264940897211362396512304628436041222873422281052071040304574363510205249804316939250072085516605409716236630122437693098107965690357983662511641360852519159201210407149426013456665654927559031576450707769140579811457087575821158806216834589419118616293649134570029348864168061503995325421166403367212784956918879123538609647020213238539717446246806658900303124564032457968947891973269315221759825010175759282900948586059414233078011374547085622341941301930819816001572766834718060688545069956096308661744521329011217013954462888420216389590625029416601914841651975749769319907679957725817987535287875463052512829357180018005408137318173906769605861407680810593420749995979362702366940275048900413734250464314983304164277188084351968745605375769912296693849464371792448471466297537539956183639108372537896814803224393949374263943947266927232857089835606620154448584587895531774998281005520646293399213187296591877953310626414259916310440526985379452834140797344
c2 = 223295770243896926174824405932791118562132019446137106707499244470470652130983482933886296317979962549790414754161520435096091469226090668617978924038597496895109870016050016361204593776094886916554978524328312654899592058243030170843460725094455369392386666825873918339575610780772636586002747595613558066320125773587684070090772498121214867506696972158540355910065773892648404521506595636503850295827650330993678348250267770526157595871258640949265795928803796357149879172931040916773382169296914793584970211453674931039251561404963603173087988508276297347805041885971003956420812510128302146772371481501739596756529250961807845809297176387467035756066576014695851369095199182667219429449627072080517064563211041402250659878953388165820020061897516163246110562240123389210713625152448308461232879889286613844389367421303837747532095262647017908028398324773681913209915202010758289748837739798240683937739276900417861582443180262419471329076908687714213527415105489215148326758425520069134366726191206
r = 2
while True:
r = r * 8
if r.bit_length() > 1024 and isPrime(r - 1):
r = r - 1
break
print(int(r))
pq = n // r
k1k2 = inv_p * inv_q - 1
alpha_times_beta = k1k2 * pq
alpha_plus_beta = pq * inv_p * inv_q - 1 - k1k2 * pq
e1 = 2
e2 = 5
alpha, beta = quadratic(-alpha_plus_beta, alpha_times_beta)
p = gcd(pq, int(alpha))
q = gcd(pq, int(beta))
assert p * q == pq
p, q = symbols("p q")
eq1 = Eq(inv_p * p + inv_q * q - pq - 1, 0)
eq2 = Eq(p * q, pq)
sol = solve((eq1, eq2), (p, q))
print(sol)
p = int(
155067211748080035817706240824444294173177315452053655302198450440797223063993902553854738130782449160496432645166392115875035577949847055717925643946457912682751338169862368227051614666060761234405201526539028698479896781769397552330889288635473271948706547821980919655770653459515096024615873307927376930323
)
q = int(
155406237257371285686734630614272846342794427544939674750800108880031404165544180838277971813657235395399719426255865993550582439955633684106295486647395174391393520922781711164275517262754514023537536287360365851886349215688978809822032291068515106418115813510512126616124030805066436158518403149436994756207
)
print(isPrime(p), p)
print(isPrime(q), q)
print(isPrime(r))
phi = (p - 1) * (q - 1) * (r - 1)
print(phi)
d2 = gmpy2.invert(e2, phi)
m2 = pow(c2, d2, n)
print(long_to_bytes(m2))
mp = pow(c1, (p + 1) // 4, p)
mq = pow(c1, (q + 1) // 4, q)
mr = pow(c1, (r + 1) // 4, r)
bp = n // p
bq = n // q
br = n // r
ap = pow(bp, -1, p)
aq = pow(bq, -1, q)
ar = pow(br, -1, r)
for sp, sq, sr in itertools.product((-1, 1), repeat=3):
m = (sp * ap * bp * mp + sq * aq * bq * mq + sr * ar * br * mr) % n
m = long_to_bytes(m)
if b"D0g3" in m:
print(m)
评论