[Crypto学习笔记] AES对称加密类题目
发布时间：
目录
前置概念
aes原理
一个字节包含8bit位, 故可以将bit位转化为系数多项式进行运算1, 以下是一个简单例子:
from sage.all import *
a = b'a'
bin_a = bin(a[0])[2:]
R = PolynomialRing(GF(2), 'x')
x = R.gen()
f = 0*x
for i in range(8):
try:
f += int(bin_a[::-1][i]) * x**i
except:
pass
print(bin_a)
print(f)
# 1100001
# x^6 + x^5 + 1
有一说一, 我总感觉这个概念好像在学习p-adic概念的时候看过(这一部分概念将放在ECC的部分进行介绍),
加法运算
对多项式进行加法运算等效于对各项常数进行模2加法.
\[\begin{matrix} a = 0b01100001 \\ e = 0b01100101 \\ a \oplus e = 0b00000100 \end{matrix}\]可以用代码表示:
>>> bin(b'a'[0])
'0b1100001'
>>> bin(b'e'[0])
'0b1100101'
>>> b'a'[0]^b'e'[0]
4
>>> bin(b'a'[0]^b'e'[0])
'0b100'
乘法运算
本质上先将多项式进行乘法, 对获取的
glacierctf2024
aes_overdrive
题目
本次为远程题目, 主要有两个附件, 其中challenge.py文件如下:
#!/usr/bin/env python3
import os
from typing import List
from Crypto.Util.Padding import pad, unpad
import aes
NORMAL_ROUNDS = 22
PREMIUM_ROUNDS = 24
PREMIUM_USER = b"premium"
def expand_key(key: bytes, rounds: int) -> List[List[int]]:
round_keys = [[key[i:i + 4] for i in range(0, len(key), 4)]]
while len(round_keys) < rounds + 1:
base_key = b"".join(round_keys[-1])
round_keys += aes.expand_key(base_key, 10)[1:]
round_keys = [b"".join(k) for k in round_keys]
round_keys = [aes.bytes2matrix(k) for k in round_keys]
return round_keys[:rounds + 1]
def encrypt_block(pt: bytes, key: bytes, rounds: int) -> bytes:
if len(pt) != 16 or len(key) != 16:
raise ValueError("Invalid input length")
subkeys = expand_key(key, rounds)
assert len(subkeys) == rounds + 1
block = aes.bytes2matrix(pt)
aes.add_round_key(block, subkeys[0])
for i in range(1, rounds+1):
aes.sub_bytes(block)
aes.shift_rows(block)
aes.mix_columns(block)
aes.add_round_key(block, subkeys[i])
return aes.matrix2bytes(block)
def decrypt_block(ct: bytes, key: bytes, rounds: int) -> bytes:
if len(ct) != 16 or len(key) != 16:
raise ValueError("Invalid input length")
subkeys = expand_key(key, rounds)[::-1]
assert len(subkeys) == rounds + 1
block = aes.bytes2matrix(ct)
for i in range(rounds):
aes.add_round_key(block, subkeys[i])
aes.inv_mix_columns(block)
aes.inv_shift_rows(block)
aes.inv_sub_bytes(block)
aes.add_round_key(block, subkeys[-1])
return aes.matrix2bytes(block)
def encrypt_msg(pt: str, key: bytes, premium: bool) -> str:
pt_bytes = pad(pt.encode(), 16)
pt_blocks = [pt_bytes[i:i + 16] for i in range(0, len(pt_bytes), 16)]
for block in pt_blocks[1:]:
if block.startswith(PREMIUM_USER):
raise ValueError("Invalid plaintext")
if len(pt_blocks) > 3:
raise ValueError("Message too long")
rounds = PREMIUM_ROUNDS if premium else NORMAL_ROUNDS
ct = b"".join([encrypt_block(block, key, rounds) for block in pt_blocks])
return ct.hex()
def decrypt_msg(ct: str, key: bytes, premium: bool) -> str:
ct_bytes = bytes.fromhex(ct)
ct_blocks = [ct_bytes[i:i + 16] for i in range(0, len(ct_bytes), 16)]
if len(ct_blocks) > 3:
raise ValueError("Ciphertext too long")
rounds = PREMIUM_ROUNDS if premium else NORMAL_ROUNDS
pt = b"".join([decrypt_block(block, key, rounds) for block in ct_blocks])
return unpad(pt, 16).decode()
def main():
key = os.urandom(16)
attempts = 0
max_attempts = 3
while attempts <= max_attempts:
option = input(
"Enter option (1: Encrypt, 2: Premium Encrypt, 3: Guess Key): ")
if option == "1":
pt = input("Enter plaintext: ")
if pt == PREMIUM_USER.decode():
print("Not so fast my friend.")
return
ct = encrypt_msg(pt, key, False)
print(f"Ciphertext: {ct}")
elif option == "2":
ct = input("Enter ciphertext: ")
try:
if decrypt_msg(ct, key, False) != PREMIUM_USER.decode():
print("Sorry, you are not a premium user.")
return
except Exception:
print("Error")
return
pt = input("Enter plaintext: ")
ct = encrypt_msg(pt, key, True)
print(f"Ciphertext: {ct}")
elif option == "3":
key_guess = input("Enter key (hex): ")
try:
key_guess = bytes.fromhex(key_guess)
if key_guess == key:
print("Correct key!")
with open('/app/flag.txt', 'r') as flag:
print(f"Flag: {flag.read().strip()}")
return
else:
print("Incorrect key.")
except ValueError:
print("Invalid key format. Please enter a valid hex string.")
else:
print("Invalid option. Please choose 1, 2, or 3.")
attempts += 1
print("Maximum attempts reached. See you later!")
if __name__ == "__main__":
main()
aes.py文件如下:
#!/usr/bin/env python3
"""
This is an exercise in secure symmetric-key encryption, implemented in pure
Python (no external libraries needed).
Original AES-128 implementation by Bo Zhu (http://about.bozhu.me) at
https://github.com/bozhu/AES-Python . PKCS#7 padding, CBC mode, PKBDF2, HMAC,
byte array and string support added by me at https://github.com/boppreh/aes.
Other block modes contributed by @righthandabacus.
Although this is an exercise, the `encrypt` and `decrypt` functions should
provide reasonable security to encrypted messages.
"""
# Taken from: https://github.com/boppreh/aes
s_box = (
0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)
inv_s_box = (
0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)
def sub_bytes(s):
for i in range(4):
for j in range(4):
s[i][j] = s_box[s[i][j]]
def inv_sub_bytes(s):
for i in range(4):
for j in range(4):
s[i][j] = inv_s_box[s[i][j]]
def shift_rows(s):
s[0][1], s[1][1], s[2][1], s[3][1] = s[1][1], s[2][1], s[3][1], s[0][1]
s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
s[0][3], s[1][3], s[2][3], s[3][3] = s[3][3], s[0][3], s[1][3], s[2][3]
def inv_shift_rows(s):
s[0][1], s[1][1], s[2][1], s[3][1] = s[3][1], s[0][1], s[1][1], s[2][1]
s[0][2], s[1][2], s[2][2], s[3][2] = s[2][2], s[3][2], s[0][2], s[1][2]
s[0][3], s[1][3], s[2][3], s[3][3] = s[1][3], s[2][3], s[3][3], s[0][3]
def add_round_key(s, k):
for i in range(4):
for j in range(4):
s[i][j] ^= k[i][j]
# learned from https://web.archive.org/web/20100626212235/http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)
def mix_single_column(a):
# see Sec 4.1.2 in The Design of Rijndael
t = a[0] ^ a[1] ^ a[2] ^ a[3]
u = a[0]
a[0] ^= t ^ xtime(a[0] ^ a[1])
a[1] ^= t ^ xtime(a[1] ^ a[2])
a[2] ^= t ^ xtime(a[2] ^ a[3])
a[3] ^= t ^ xtime(a[3] ^ u)
def mix_columns(s):
for i in range(4):
mix_single_column(s[i])
def inv_mix_columns(s):
# see Sec 4.1.3 in The Design of Rijndael
for i in range(4):
u = xtime(xtime(s[i][0] ^ s[i][2]))
v = xtime(xtime(s[i][1] ^ s[i][3]))
s[i][0] ^= u
s[i][1] ^= v
s[i][2] ^= u
s[i][3] ^= v
mix_columns(s)
r_con = (
0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)
def bytes2matrix(text):
""" Converts a 16-byte array into a 4x4 matrix. """
return [list(text[i:i+4]) for i in range(0, len(text), 4)]
def matrix2bytes(matrix):
""" Converts a 4x4 matrix into a 16-byte array. """
return bytes(sum(matrix, []))
def xor_bytes(a, b):
""" Returns a new byte array with the elements xor'ed. """
return bytes(i^j for i, j in zip(a, b))
def pad(plaintext):
"""
Pads the given plaintext with PKCS#7 padding to a multiple of 16 bytes.
Note that if the plaintext size is a multiple of 16,
a whole block will be added.
"""
padding_len = 16 - (len(plaintext) % 16)
padding = bytes([padding_len] * padding_len)
return plaintext + padding
def unpad(plaintext):
"""
Removes a PKCS#7 padding, returning the unpadded text and ensuring the
padding was correct.
"""
padding_len = plaintext[-1]
assert padding_len > 0
message, padding = plaintext[:-padding_len], plaintext[-padding_len:]
assert all(p == padding_len for p in padding)
return message
def expand_key(master_key, rounds):
"""
Expands and returns a list of key matrices for the given master_key.
"""
# Initialize round keys with raw key material.
key_columns = bytes2matrix(master_key)
iteration_size = len(master_key) // 4
i = 1
while len(key_columns) < (rounds + 1) * 4:
# Copy previous word.
word = list(key_columns[-1])
# Perform schedule_core once every "row".
if len(key_columns) % iteration_size == 0:
# Circular shift.
word.append(word.pop(0))
# Map to S-BOX.
word = [s_box[b] for b in word]
# XOR with first byte of R-CON, since the others bytes of R-CON are 0.
word[0] ^= r_con[i]
i += 1
elif len(master_key) == 32 and len(key_columns) % iteration_size == 4:
# Run word through S-box in the fourth iteration when using a
# 256-bit key.
word = [s_box[b] for b in word]
# XOR with equivalent word from previous iteration.
word = xor_bytes(word, key_columns[-iteration_size])
key_columns.append(word)
# Group key words in 4x4 byte matrices.
return [key_columns[4*i : 4*(i+1)] for i in range(len(key_columns) // 4)]
题目分析
这是我第一次做AES, 所以会过得详细一些. challenge.py部分主要为一套加密解密和获取flag功能的前端模块, 在main()函数中我们可以获取4次机会加密, 高级加密, 猜测key:
key = os.urandom(16)
attempts = 0
max_attempts = 3
while attempts <= max_attempts:
option = input(
"Enter option (1: Encrypt, 2: Premium Encrypt, 3: Guess Key): ")
实际上最后需要留一次用于猜key, 故总共只有3次机会去加密以破解key, 最简单的方法便是使用相关的明文分别进行加密和高级加密, 可以得到两轮加密的差值, 接下来就是尝试凑出两个相关加密:
def encrypt_msg(pt: str, key: bytes, premium: bool) -> str:
pt_bytes = pad(pt.encode(), 16)
pt_blocks = [pt_bytes[i:i + 16] for i in range(0, len(pt_bytes), 16)]
for block in pt_blocks[1:]:
if block.startswith(PREMIUM_USER):
raise ValueError("Invalid plaintext")
if len(pt_blocks) > 3:
raise ValueError("Message too long")
rounds = PREMIUM_ROUNDS if premium else NORMAL_ROUNDS
ct = b"".join([encrypt_block(block, key, rounds) for block in pt_blocks])
return ct.hex()
定位到这个函数可以找到关联性, 传入参数premium会影响轮次, 其中有两个限制(这里本来应该是找到函数场景后返回来看的, 但是考虑到编写方式, 现在一起分析一下):
每个块以
PREMIUM_USER开始块小于等于3
EXP
参考文献
- https://mcsch.dev/posts/glacierctf-2024/
李子臣.密码学——基础理论与应用[M].北京.电子工业出版社.2019.09. ↩