上周打的 ImaginaryCTF,比赛期间只做出了几道相对简单的密码学赛题,菜菜。复现的时候更是被狠狠的打击了。
rsa
题目给了三个文件,分别是 flag.enc;private.pem;public.pem;所以我们直接从 private.pem 里面导出私钥然后解密就可以了,基础操作题。
1234567 |
from Crypto.PublicKey import RSAfrom Crypto.Util.number import bytes_to_long, long_to_byteskey = 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
1234567891011 |
import randomemojis = [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个字符相同的子串,会发现刚好只有一个,于是我们就能确定下来一些字符。然后根据已知的碎片信息一点点分析,在解题代码的注释中我列出了字符替换的逻辑。
1234567891011121314151617181920212223242526272829303132333435 |
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 \mdata = data.replace("🎁","2").replace("🐶","0")# 20 " "data = data.replace("🦋","1").replace("🚀","c")# 74797069636🦋6🚀6🚀79 typicallydata = data.replace("🌼","5").replace("⚡","e")# 77726974746🌼6⚡ writtendata = data.replace("🌺","f")# 6🌺6e6c696e65 onlinedata = data.replace("🍔","d")# 656e7669726f6e6🍔656e742e environment.data = data.replace("🌞","8") |
PS:赛后看了官方解,只需要随便找一篇英文文章样例,十六进制编码后统计里面出现字符的频率,然后将这一题密文中各个emoji根据出现的频率排列,然后一一替换即可。
signer
12345678910111213141516171819202122232425262728293031323334353637383940414243 |
import textwrapfrom binascii import crc32from Crypto.Util.number import getPrimep, q = getPrime(1024), getPrime(1024)n = p*qe = 65537d = 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
,不过由于限制
123 |
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 破解的一个考点)然后让服务器给这两条消息签名得到 $sig_1,sig_2$,然后计算 $sig_1\cdot sig_2 \pmod n$ 就是 PASSWORD 的签名了。发送给服务器就可以获得 flag 了。
tan
12 |
print(tan(int.from_bytes(open("flag.txt", "rb").read().strip(), "big")).n(1024))# -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714 |
来自maple的 oneline crypto, $tan(flag) = c$,原本是 $tan$ 是可以由 $arctan$ 逆回去的,不过因为 $tan$ 函数的周期是 $2\pi$,所以 $arctan(c) \equiv flag \pmod{2\pi}$,写成等式有 $arctan(c) = flag + 2k \pi,k \in \mathbb{Z}$,
考虑构造格 $M =\begin{bmatrix} arctan(c)& 1 & 0 & 0\newline\pi&0&1 & 0\newline 1&0&0 & 1 \newline\end{bmatrix}$,会存在向量 $l = [-1 \ 2k \ flag]$ 使得 $l \times M = [0 \ -1 \ 2k \ flag]$,其实跟背包问题格子差不多。为了保证得到目标向量,我们也考虑给格子的第一列都乘上一个比较大的数,比如 $10^{307}$ 这样(刚好 $c$ 的小数点后面有307位)
1234567891011121314 |
c = -0.7578486465144361653056740883647981074157721568235263947812770328593706155446273431983003083023944193451634501133844062222318380912228469321984711771640337084400211818130699382144693337133198331117688092846455855532799303682791981067718891947573941091671581719597626862194794682042719495503282817868258547714ac = 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
123456789101112131415161718192021222324252627282930313233 |
from Crypto.Util.number import *from math import gcddef 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) == mprint(f"{pub = }")print(f"{c = }") |
题目基于 RSA 公钥加密系统,$c \equiv m^e \pmod n$,给出了公钥对和密文 $c$。区别于正常的 RSA,这里给出的公钥指数是 $e’ = e + prime \cdot phi$,$prime$ 是一个 682 比特的素数。而 $e$ 本身也是一个 1024 比特的素数。
考虑组成 $e’$ 两项的大小关系,计算 $\frac{e’}{n}$,由于 $\varphi(n) \approx n$,所以 $\frac{e’}{n} \approx prime$,我们只需要在附近 $\pm10$ 的地方找一下就能找到 $prime$ 了。
随后我们计算 $e’//prime$ ( // 表示整除 ),由于 $phi$ 是2048 比特 $e$ 是 1024 比特,所以 $phi = e’//prime + \epsilon $ 其中 $\epsilon$ 可以看作一个 342比特的噪声。也就意味着我们能够知道 $phi$ 的高 1706 比特。根据 $phi = n + 1 - (p+q)$ 我们即可获取 $p+q$ 的高位,在使用一下平方差公式 $(p+q)^2 - 4n = (p-q)^2$,就能得到 $p-q$ 的高位,从而 $p = ((p+q)+(p-q))/2$ 得到 $p$ 的高位,然后利用 coppersmith 就能得到完整的 $p$,从而分解 $n$,解密得到 flag
123456789101112131415161718192021222324 |
from Crypto.Util.number import *from gmpy2 import irootn,e = (, )c = pr = e // n + 1print(pr)print(isPrime(pr))phibar = e // prp_a_qbar = n+1-phibarp_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 + xp0 = 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
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 |
#!/usr/bin/env python3from random import getrandbitsfrom galois import GFimport numpy as npDECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"F = GF(13) # lucky numbern = 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 = 15000cards = 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。
注意到每一次使用 $M^{random} \cdot cards$ 来“洗牌”,$cards$ 是上一轮的手牌,并且会在猜完后展示出来;$M$ 是一个行列式不为 0 的随机矩阵。$random$ 是由 getrandbits(32)
生成而来。那么思路就比较清晰了。
刚开始我们设 $bet=1$,然后就乱猜,主要目的就是看他的手牌,然后根据前后手牌的变化来 “想办法” 搞到这个 $random$,搞到 624 个之后我们就能够预测后续的 $random$,那个时候我们就一直 all in 就行了。
那么这个 “想办法” 该想什么样的办法呢,这是解题的关键,也是比赛的时候没想通的2333。如果我们能够知道 $M$ 和 $M^{random}$,那么我们就需要解一个矩阵的离散对数问题;这个好像可以取行列式来做,这样就转化为有限域下的离散对数问题了。那怎么搞到 $M$ 或者 $M$ 的行列式呢?
哎?注意到这个guess不是说你输入啥猜的就是啥,他会有一步处理,$guess = M \times input$,所以要满足的是 $M \times input = M ^{random} \times cards$。
那么,如果我们在输入的时候,构造的特殊一点,比如 input = [1 0 0 0 ...]
,那么在经过 $M \times input$ 后,guess 的值就是 $M$ 第一列。不过我们不能直接获取到自己的 guess,只能根据最后展示的手牌和猜对的牌数来判断 guess 的值。那么怎么搞呢?撞!
guess 每个位置的牌都有 13 种可能,当前仅当猜对的总数为 0 的时候,我们就能够进行一次否定,可以保证每一个位置都不是所展示手牌的对应位置的牌。
当每个位置的可能都只剩 1 的时候,我们就获取了 $M$ 的一列值,然后进行下一列的撞。
(由于远程环境挂了,本地起 process 遇到点问题,就稍微改了改源代码在本地验证了)
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283 |
from operator import lshift, rshiftfrom tqdm import trangefrom random import getrandbitsfrom galois import GFimport numpy as npDECK = "🂡🂢🂣🂤🂥🂦🂧🂨🂩🂪🂫🂭🂮"F = GF(13) # lucky numbern = 10# Let's not use a singular matrix, please.# We do quality random over here.global MM = [[0]]while np.linalg.det(M) == 0: M = F.Random((n, n))global moneymoney = 15000global cardscards = 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 = 10hands = []col = [set(range(13)) for _ in range(n)]MM = []i = 0while 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 次暴力后我们能够拿到 $M$ ,不过想通过解离散对数获取 $random$ 的话,也还得获取到 $M^{random}$。根据题目我们有式子 $card_2 = M^{random} \cdot card_1$,由于线性代数学的一团糟,并不太知道接下来怎么搞,于是选择先“逃课”。根据 github 里巨人提供的板子
12345678910111213141516171819202122232425262728293031 |
# https://github.com/jvdsn/crypto-attacks/blob/master/shared/matrices.pydef 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 |
利用我们前面一千四百多次的手牌和撞出来的 $M$ 直接调 dlog_equation
就能获取所有 $random$ 了,然后就是一个基础的 MT19937 状态恢复然后预测,这里就不过多赘述了。
不好意思,就到底为止了,后面的题目连题面都看不懂了,elf 文件,so 文件,factor 文件,wtf??????也许以后能看懂呢?也许叭…
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081,也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
- 右白虎
- 微信扫一扫
评论