上周打的 ImaginaryCTF,比赛期间只做出了几道相对简单的密码学赛题,菜菜。复现的时候更是被狠狠地打击了。
rsa
题目给了三个文件,分别是 flag.enc;private.pem;public.pem;所以我们直接从 private.pem 里面导出私钥然后解密就可以了,基础操作题。
from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long, long_to_bytes
key = RSA.importKey(open('private.pem', "rb").read())
flag = bytes_to_long(open("flag.enc", "rb").read())
print(long_to_bytes(pow(flag, key.d, key.n)))
emoticons
import random
emojis = [n for n in "🌸🍔🐳🚀🌞🎉🍦🎈🐶🍕🌺🎸⚡️🦋🌼🎁"]
m = open("text.txt", "rb").read().hex()
random.shuffle(emojis)
for e, c in zip(emojis, "0123456789abcdef"):
m = m.replace(c, e)
open("out.txt", "w").write(m)
题目逻辑很简单,就是将明文编码成十六进制,然后使用类似于简单替换密码,将十六个字符随机映射到十六个emoji图案上。可以看到题目给的输出密文的数据量还是比较大的,所以其实考点应该就是简单的词频分析。
在比赛的时候有点猪脑过载,我就是一点点人工分析过来的,首先考虑 flag 的格式,"ictf{".hex() == '696374667b',然后我们在密文中找第0,2,6,7个字符相同,第4,8个字符相同的子串,会发现刚好只有一个,于是我们就能确定下来一些字符。然后根据已知的碎片信息一点点分析,在解题代码的注释中我列出了字符替换的逻辑。
with open("outs.txt","r",encoding = "utf-8") as f:
data = f.read()
#print(len(data))
emojis = [n for n in "🌸🍔🐳🚀🌞🎉🍦🎈🐶🍕🌺🎸⚡🦋🌼🎁"]
# "ictf{".hex() == '696374667b'
for i in range(len(data)):
sli = data[i:i+10]
if sli[0] == sli[2] == sli[6] == sli[7] and sli[4] == sli[8]:
print(i,sli)
🎈🐳🎈🌸🍕🎉🎈🎈🍕🎸
with open("outs.txt","r") as f:
data = f.read()
data = data.replace("🎈","6").replace("🍕","7").replace("🐳","9").replace("🌸","3").replace("🎉","4").replace("🎸","b")
data = data.replace("🍦","a") # 0a m
data = data.replace("🎁","2").replace("🐶","0") # 20 " "
data = data.replace("🦋","1").replace("🚀","c") # 74797069636🦋6🚀6🚀79 typically
data = data.replace("🌼","5").replace("⚡","e") # 77726974746🌼6⚡ written
data = data.replace("🌺","f") # 6🌺6e6c696e65 online
data = data.replace("🍔","d") # 656e7669726f6e6🍔656e742e environment.
data = data.replace("🌞","8")
PS:赛后看了官方解,只需要随便找一篇英文文章样例,十六进制编码后统计里面出现字符的频率,然后将这一题密文中各个emoji根据出现的频率排列,然后一一替换即可。
signer
import textwrap
from binascii import crc32
from Crypto.Util.number import getPrime
p, q = getPrime(1024), getPrime(1024)
n = p*q
e = 65537
d = pow(e, -1, (p-1)*(q-1))
PASSWORD = b"give me the flag!!!"
print("--------------------------------------------------------------")
print(" Welcome to the secure signing app! ")
print(" I will sign whatever you want, except the secret password. ")
print("--------------------------------------------------------------")
print()
print("--------------------------------------------------------------")
print("n".join(textwrap.wrap(f"{n = }", len("-------------------------------------------------------------"))))
print("--------------------------------------------------------------")
print()
while True:
print("1. Sign")
print("2. Get flag")
choice = int(input())
if choice == 1:
print("Enter message:")
message = input().encode()
# crc32 is secure and has no collisions, but just in case
if message == PASSWORD or crc32(message) == crc32(PASSWORD):
print("Stop this trickery!")
exit()
print("Signature:", pow(crc32(message), d, n))
elif choice == 2:
print("Enter the signature for the password:")
s = int(input())
if pow(s, e, n) == crc32(PASSWORD):
print("You win! The flag is", open("flag.txt").read())
exit()
else:
print("Wrong.")
exit()
题目基于 RSA 签名系统,需要我们给出 PASSWORD = b"give me the flag!!!"
的签名,另外这里的签名不是对消息进行哈希,而是使用 crc32 来表示。我们知道 crc32 只有 4 个字节,因此这样一个多对一的映射在明文输入大于4个字节的时候是非常好碰撞的。所以这里首先计算 crc32(PASSWORD)
得到值 3542523789
,不过由于限制
if message == PASSWORD or crc32(message) == crc32(PASSWORD):
print("Stop this trickery!")
exit()
我们不能直接输入PASSWORD,也不能输入和 PASSWORD 的 crc32 相等的消息。但是由于 RSA 具有乘法同态,所以我们可以先将 3542523789
分解为 13477 * 262857
,然后分别碰撞出 crc32 等于 13477 和 262857 的两个消息,例如 2i_pQM
和 22p6NE
。(crc32 碰撞的脚本还是比较好找的,毕竟是 MISC 中 zip 破解的一个考点)然后让服务器给这两条消息签名得到 ,然后计算 就是 PASSWORD 的签名了。发送给服务器就可以获得 flag 了。
tan
print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024))
# -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714
来自maple的 oneline crypto, ,原本是 是可以由 逆回去的,不过因为 函数的周期是 ,所以 ,写成等式有 ,
考虑构造格
,会存在向量 使得 ,其实跟背包问题格子差不多。为了保证得到目标向量,我们考虑给格子的第一列都乘上一个比较大的数,比如 这样(刚好 的小数点后面有307位)
c = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714
ac = atan(c)
shift = 10^307
m=[[ac * shift, 1,0,0],
[(pi.n(1024)) * shift, 0,1,0],
[1 * shift, 0,0,1]]
M = matrix(QQ,m)
L = M.LLL()
long_to_bytes(abs(L[0][-1]))
# b'ictf{can_you_break_sin_or_cos_too?}'
PS:由于取整会导致误差,所以格基规约后矩阵的第一行向量的第一个元素并不是 0 。
wasteful
from Crypto.Util.number import *
from math import gcd
def keygen(sz):
p = getPrime(sz // 2)
q = getPrime(sz // 2)
n = p * q
phi = (p - 1) * (q - 1)
e_fast = getPrime(sz // 2)
# to make encryption more time consuming :P
e_slow = e_fast + getPrime(sz // 3) * phi
d = pow(e_fast, -1, phi)
return (n, e_slow), (n, e_fast), (n, d)
def encrypt(pub, m):
n, e = pub
return pow(m, e, n)
def decrypt(priv, c):
n, d = priv
return pow(c, d, n)
pub, pub_fast, priv = keygen(2048)
m = bytes_to_long(open("flag.txt", "rb").read().strip())
c = encrypt(pub, m)
assert c == encrypt(pub_fast, m)
assert decrypt(priv, c) == m
print(f"{pub = }")
print(f"{c = }")
题目基于 RSA 公钥加密系统,,给出了公钥对和密文 。区别于正常的 RSA,这里给出的公钥指数是 , 是一个 682 比特的素数。而 本身也是一个 1024 比特的素数。
考虑组成 两项的大小关系,计算 ,由于 ,所以 ,我们只需要在附近 的地方找一下就能找到 了。
随后我们计算 ( // 表示整除 ),由于 是2048 比特 是 1024 比特,所以 其中 可以看作一个 342比特的噪声。也就意味着我们能够知道 的高 1706 比特。根据 我们即可获取 的高位,在使用一下平方差公式 ,就能得到 的高位,从而 得到 的高位,然后利用 coppersmith 就能得到完整的 ,从而分解 ,解密得到 flag
from Crypto.Util.number import *
from gmpy2 import iroot
n,e = (, )
c =
pr = e // n + 1
print(pr)
print(isPrime(pr))
phibar = e // pr
p_a_qbar = n+1-phibar
p_s_qbar = iroot((p_a_qbar**2-4*n),2)[0]
pbar = int((p_a_qbar+p_s_qbar)//2)
R.<x> = Zmod(n)[]
f = pbar + x
p0 = f.small_roots(X=2^400,beta=0.4)[0]
p = int(pbar+p0)
q = int(n//p)
d = inverse(e,(p-1)*(q-1))
m = pow(c,d,n)
print(long_to_bytes(int(m)))
# b'ictf{just_an_obligatory_coppersmith_challenge}'
以上就是比赛期间搞出来的五道题目了,猜牌游戏比赛的时候看了一半不太会,赛后对着官方 exp 尝试复现了下。
blind_guess
#!/usr/bin/env python3
from random import getrandbits
from galois import GF
import numpy as np
DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
F = GF(13) # lucky number
n = 10
# Let's not use a singular matrix, please.
# We do quality random over here.
M = [[0]]
while np.linalg.det(M) == 0:
M = F.Random((n, n))
money = 15000
cards = F.Random(n)
while all(int(c) == 0 for c in cards):
cards = F.Random(n)
while money > 0:
print('balance:', money)
choice = input('> ')
if choice == 'buy flag':
if money < 1_000_000_000:
print("You're too poor!")
continue
from redacted import FLAG
money -= 1_000_000_000
print("What a guess god! Here's your flag:", FLAG)
elif choice == 'play':
bet = int(input('bet: '))
assert money >= bet > 0
print("Can you blindly guess my cards?")
cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards # shuffle cards
guess = M @ F([*map(DECK.index, input('guess: ').split())]) # blind guess
total = sum(cards == guess)
print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])
money += 2*(total - 5)*bet
elif choice == 'exit':
print("Chickened out, huh? No flag for you.")
exit()
print("Woops... Looks like you guessed your way out of money :>")
题目是一个猜牌游戏,初始的拥有 15000 的 money,每一次猜牌可以自定义下注 bet,随后根据猜对的数量进行获利,获利规则为 2*(total - 5)*bet
,即猜对六张及以上才可以获利。到 money 大于 1_000_000_000 后就可以获取 flag。
注意到每一次使用 来“洗牌”, 是上一轮的手牌,并且会在猜完后展示出来; 是一个行列式不为 0 的随机矩阵。 是由 getrandbits(32)
生成而来。那么思路就比较清晰了。
刚开始我们设 ,然后就乱猜,主要目的就是看他的手牌,然后根据前后手牌的变化来 “想办法” 搞到这个 ,搞到 624 个之后我们就能够预测后续的 ,那个时候我们就一直 all in 就行了。
那么这个 “想办法” 该想什么样的办法呢,这是解题的关键,也是比赛的时候没想通的2333。如果我们能够知道 和 ,那么我们就需要解一个矩阵的离散对数问题;这个好像可以取行列式来做,这样就转化为有限域下的离散对数问题了。那怎么搞到 或者 的行列式呢?
哎?注意到这个guess不是说你输入啥就表示猜的就是啥,他会有一步处理,,所以要满足的是 。
那么,如果我们在输入的时候,构造的特殊一点,比如 input = [1 0 0 0 ...]
,那么在经过 后,guess 的值就是 第一列。不过我们不能直接获取到自己的 guess,只能根据最后展示的手牌和猜对的牌数来判断 guess 的值。那么怎么搞呢?撞!
guess 每个位置的牌都有 13 种可能,当前仅当猜对的总数为 0 的时候,我们就能够进行一次否定,可以保证每一个位置都不是所展示手牌的对应位置的牌。
当每个位置的可能都只剩 1 的时候,我们就获取了 的一列值,然后进行下一列的撞。
(由于远程环境挂了,本地起 process 遇到点问题,就稍微改了改源代码在本地验证了)
from operator import lshift, rshift
from tqdm import trange
from random import getrandbits
from galois import GF
import numpy as np
DECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"
F = GF(13) # lucky number
n = 10
# Let's not use a singular matrix, please.
# We do quality random over here.
global M
M = [[0]]
while np.linalg.det(M) == 0:
M = F.Random((n, n))
global money
money = 15000
global cards
cards = F.Random(n)
while all(int(c) == 0 for c in cards):
cards = F.Random(n)
def local_game(choice,bet,inputs):
global money
global cards
while money > 0:
#print('balance:', money)
if choice == 'buy flag':
if money < 1_000_000_000:
print("You're too poor!")
continue
from redacted import FLAG
money -= 1_000_000_000
print("What a guess god! Here's your flag:", FLAG)
elif choice == 'play':
assert money >= bet > 0
#print("Can you blindly guess my cards?")
cards = np.linalg.matrix_power(M, getrandbits(32)) @ cards # shuffle cards
guess = M @ F([*map(DECK.index, inputs.split())]) # blind guess
total = sum(cards == guess)
#print(f'You guessed {total} cards! My hand was:', *[DECK[c] for c in cards])
money += 2*(total - 5)*bet
return [int(c) for c in cards],total
elif choice == 'exit':
print("Chickened out, huh? No flag for you.")
exit()
#print("Woops... Looks like you guessed your way out of money :>")
n = 10
hands = []
col = [set(range(13)) for _ in range(n)]
MM = []
i = 0
while i < n:
guesscard = i*[0] + [1] + (n-i-1)*[0]
hand, total = local_game('play',1, ' '.join(DECK[int(c)] for c in guesscard))
hands.append(hand)
if total == 0:
for r, c in zip(col, hand):
r.discard(c)
if all(len(r) == 1 for r in col):
MM.append([c for r in col for c in r])
col = [set(range(13)) for _ in range(n)]
i += 1
print('i =', i)
print('M =', MM)
print(f"Collected {len(hands)} hands")
# M = [[2, 4, 3, 2, 5, 7, 9, 11, 7, 10], [12, 0, 7, 9, 1, 3, 0, 5, 5, 10], [0, 4, 1, 5, 10, 10, 5, 11, 2, 3], [4, 6, 5, 4, 2, 8, 0, 11, 0, 0], [12, 10, 8, 7, 12, 4, 10, 12, 3, 1], [6, 11, 2, 11, 7, 11, 10, 7, 12, 12], [2, 10, 1, 7, 2, 7, 0, 8, 1, 10], [10, 0, 8, 10, 12, 5, 4, 10, 5, 12], [10, 11, 8, 9, 11, 1, 9, 7, 5, 3], [11, 1, 8, 4, 3, 8, 6, 2, 11, 9]]
# Collected 1403 hands
在大约经过1400 次暴力后我们能够拿到 ,不过想通过解离散对数获取 的话,也还需要获取到 。根据题目我们有式子 ,由于线性代数学的一团糟,并不太知道接下来怎么搞,于是选择先“逃课”。根据 github 里巨人提供的板子
# https://github.com/jvdsn/crypto-attacks/blob/master/shared/matrices.py
def dlog_equation(A, x, y):
"""
Computes l such that A^l * x = y, in GF(p).
:param A: the matrix A
:param x: the vector x
:param y: the vector y
:return: l, or None if l could not be found
"""
assert A.is_square()
# TODO: extend to GF(p^k) if necessary?
J, P = A.jordan_form(transformation=True)
x = P ** -1 * x
y = P ** -1 * y
r = 0
for s1, s2 in zip(*J.subdivisions()):
S = J.subdivision(s1, s2)
assert S.is_square()
n = S.nrows()
r += n
if n >= 2:
x1 = x[r - 1]
x2 = x[r]
y1 = y[r - 1]
y2 = y[r]
l = S[n - 1, n - 1] * (y1 - x1 * y2 / x2) / y2
return int(l)
return None
利用我们前面一千四百多次的手牌和撞出来的 直接调 dlog_equation
就能获取所有 了,然后就是一个基础的 MT19937 状态恢复然后预测,这里就不过多赘述了。
不好意思,就到底为止了,后面的题目连题面都看不懂了,elf 文件,so 文件,factor 文件,wtf??????也许以后能看懂呢?也许叭...
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论