🔑

CTF Crypto まとめ

2024/07/01に公開

cryptography

CTF

tech

asusnがこれまで解いてきたCTFのCrypto問題をジャンルごとに分類してまとめていくページです

よく使うツール・テクニック

やること

GPTにコードを投げて以下のことを聞く
- 何の暗号に基づいているか or オリジナルの暗号かを聞く
- それぞれの関数が何をやっているか詳しく聞く
- 既存の暗号と違ってどこが違うかを聞く
それぞれの変数の値をprintして紐解いていく
部分的にわかっている暗号と復号文があれば、キーを推測できると考える
シード固定されている？毎回同じ結果にできる？
英語版のWikipediaを読む

テクニック

全ての文字

全ての文字で結果を試したいときはstring.printableを使う
string --- 一般的な文字列操作 — Python 3.12.4 ドキュメント

import string
strings = string.printable

0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ!"#%&\'()*+,-./:;<=>?@[\\]^_{|}~ \t\n\r\x0b\x0c

ファイルのロード

output.txtにある変数をpythonとして読みたい場合

with open('output.txt') as f:
    exec(f.read())

バイナリを読みたい場合

with open('secret.enc', 'rb') as f:
    secret = f.read()

bytes ⇔ int

int.from_bytes(b'i') # 105
int.from_bytes(b'\x00i', 'big') # 105
i.to_bytes() # b'i'
i.to_bytes(2, 'big') # b'\x00i'

hex ⇔ int

int('ff', 16) # 255
'{:02x}'.format(255) # 'ff'

bytes ⇔ long

from Crypto.Util.number import *
bytes_to_long(b)
long_to_bytes(l)

bytes ⇔ str

'str'.encode()
b'bytes'.decode()

bytes ⇔ hex

bytes.fromhex('deadbeef')
b'\xde\xad\xbe\xef'.hex()

素数(Crypto.Util)

from Crypto.Util.number import *
getPrime(512) # 512bitのランダムな素数を取得
isPrime(n) # 素数かどうか

素数(sympy)

from sympy import *
factorint(n) # 素因数分解
nextprime(n) # 次の素数

n乗根

import math
math.isqrt(k) # 2048くらいの大きい数の2乗根(整数値・切り捨て)

import gmpy2
root, exact = gmpy2.iroot(gmpy2.mpz(k), 3) # 大きい数の3乗根

計算

s = A / (1 + A) (mod p) の計算

s = A * pow(1 + A, -1 , p) % p

汎用ツール

何の暗号かを調べる

https://www.dcode.fr/cipher-identifier

素因数分解サイト

定理

中国の剰余定理

与えられた二つの整数 m1, m2 が互いに素ならば、任意に与えられる整数 a1, a2 に対し、連立合同式
x ≡ a1 (mod m1),
x ≡ a2 (mod m2)
を満たす整数 x が m1 m2 を法として一意的に存在する。

from sympy.ntheory.modular import solve_congruence
solve_congruence((a1, m1), (a2, m2), (a3, m3))

https://ja.wikipedia.org/wiki/中国の剰余定理

RSA

暗号化

from Crypto.Util.number import *

flag = b'asusn'
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * q
e = 65537
c = pow(m, e, n)

print(f"{m = }")
print(f"{p = }")
print(f"{q = }")
print(f"{n = }")
print(f"{e = }")
print(f"{c = }")

復号

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
flag = long_to_bytes(m).decode()

print(f"{phi = }")
print(f"{d = }")
print(f"{flag = }")

eが小さい(Low Public-Exponent Attack)

i = 0
while True:
    m, ok = gmpy2.iroot(c + i * n, e)
    if ok:
        break
    i += 1
print(long_to_bytes(m))

eが大きい(Wiener's Attack)

すなわちdが小さいとき。picoCTF2021の「Dachshund Attacks」など。

https://github.com/pablocelayes/rsa-wiener-attack/tree/master にあるコードをcloneして以下を実行

from RSAwienerHacker import *
d = hack_RSA(e, n)

異なるe1, e2で暗号化(Common Modulus Attack)

from sympy import gcdex

x, y, _ = gcdex(e1, e2)
m = (pow(c1, int(x), n) * pow(c2, int(y), n)) % n
print(long_to_bytes(m))

ツール

使ったことないけど試しておきたい

これも(from tchen)
https://github.com/jvdsn/crypto-attacks

RSA参考

どんな脆弱さがあるかは以下を確認するとよい

AES

AESについて

ECBがブロックごとに独立して暗号化するやつで、
CBCがIVを使って前のブロックの暗号をXORするやつ。

CyberChefにAESがあり、雑に試すことができる