CRYPTOHACK学习

Introduction to CryptoHack

Finding Flags

crypto{y0ur_f1rst_fl4g}

Great Snakes

crypto{z3n_0f_pyth0n}

ASCII

python
Python 3.10.7 (tags/v3.10.7:6cc6b13, Sep  5 2022, 14:08:36) [MSC v.1933 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> xl=[99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]
>>> print("".join([chr(i) for i in xl]))
crypto{ASCII_pr1nt4bl3}
>>> print("".join(map(chr,xl)))
crypto{ASCII_pr1nt4bl3}

Hex

>>> print(bytes.fromhex("63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d"))
b'crypto{You_will_be_working_with_hex_strings_a_lot}'

Base64

Python 3.10.7 (tags/v3.10.7:6cc6b13, Sep  5 2022, 14:08:36) [MSC v.1933 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> import base64
>>> bt=bytes.fromhex("72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf")
>>> print(bt)
b'r\xbc\xa9\xb6\x8f\xc1j\xc7\xbe\xeb\x8f\x84\x9d\xca\x1d\x8ax>\x8a\xcf\x96y\xbf\x92i\xf7\xbf'
>>> print(base64.b64encode(bt))
b'crypto/Base+64+Encoding+is+Web+Safe/'

Bytes and Big Integers

>>> from Crypto.Util.number import *
>>> print(long_to_bytes(11515195063862318899931685488813747395775516287289682636499965282714637259206269))
b'crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}'

XOR Starter

python
Python 3.10.7 (tags/v3.10.7:6cc6b13, Sep  5 2022, 14:08:36) [MSC v.1933 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license" for more information.
>>> st = "label"
>>> print("".join(chr(ord(i)^13) for i in st))
aloha
>>> def xor(a,b):
...     return a^b
...
>>> print("".join(chr(xor(ord(i),13)) for i in st))
aloha

XOR Properties

k1_ord = [o for o in bytes.fromhex("a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313")]
k23_ord = [o for o in bytes.fromhex("c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1")]
flag_123_ord = [o for o in bytes.fromhex("04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf")]

k123_ord=[a^b for a,b in zip(k1_ord,k23_ord)]
flag_ord=[a^b for a,b in zip(flag_123_ord,k123_ord)]

print(bytes(flag_ord))

Favourite byte

st=bytes.fromhex('73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d')
for num in range(256):
    string="".join((chr(num ^ i) for i in st))
    if string.startswith("crypto"):
        print(string)

You either know, XOR you don’t

flag格式形如crypto{FLAG}

与密钥异或后得到0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104

那么这个字符串的前七位字节和最后一个字节与crypto{、}异或就能得到密钥的前七位。最后一位可能不准，因为密钥短的话就循环异或，不一定最后一位就和最后一个字节异或

先计算出来：

enc_flag = '0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104'
partial_flag = 'crypto{'

encflag_ord=[o for o in bytes.fromhex(enc_flag)]
par_ord=[o for o in partial_flag.encode()]
key_start="".join([chr(a^b) for (a,b) in zip(encflag_ord,par_ord)])
key_end=chr(encflag_ord[-1] ^ ord('}'))
print(key_start)
print(key_end)

输出myXORke和y，拼在一起有意义：myXORkey

所以认为它是密钥

下面就计算他和异或后的字符串就行

长度不一致，一般是循环使用短序列

这里默认使用pwn库的xor函数

import pwn
key="myXORkey"
enc="0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104"
flag=pwn.xor(key.encode(),bytes.fromhex(enc)).decode()
print(flag)

crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}

Modular Arithmetic

Greatest Common Divisor

我自己写的gcd脚本：

def gcd(a,b):
    x=max(a,b)
    y=min(a,b)
    while x%y!=0:
        a=y
        y=(x%y)
        x=a
    print(y)

gcd(52920,66528)

DeepSeek优化的：

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

print(gcd(52920, 66528))  # 输出结果：1512

它好聪明

Extended GCD

原理知道，但是写不出来脚本

GingerCarrot的脚本，不是很好理解这个脚本，可能我不明白递归，代码能力退化了

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = egcd(b % a, a)
        return gcd, y - (b // a) * x, x


print(egcd(26513, 32321))

Modular Square Root

a = 8479994658316772151941616510097127087554541274812435112009425778595495359700244470400642403747058566807127814165396640215844192327900454116257979487432016769329970767046735091249898678088061634796559556704959846424131820416048436501387617211770124292793308079214153179977624440438616958575058361193975686620046439877308339989295604537867493683872778843921771307305602776398786978353866231661453376056771972069776398999013769588936194859344941268223184197231368887060609212875507518936172060702209557124430477137421847130682601666968691651447236917018634902407704797328509461854842432015009878011354022108661461024768
p = 30531851861994333252675935111487950694414332763909083514133769861350960895076504687261369815735742549428789138300843082086550059082835141454526618160634109969195486322015775943030060449557090064811940139431735209185996454739163555910726493597222646855506445602953689527405362207926990442391705014604777038685880527537489845359101552442292804398472642356609304810680731556542002301547846635101455995732584071355903010856718680732337369128498655255277003643669031694516851390505923416710601212618443109844041514942401969629158975457079026906304328749039997262960301209158175920051890620947063936347307238412281568760161
Mod(a,p).sqrt()

Chinese Remainder Theorem

我是手算的

算出了6482，但解是 \(kM + \sum_{i=1}^{n}a_{i}t_{i}M_{i}\ ;\ k\in \mathbb{Z}\) 一般都是要求最小的解，所以我这边模M即可，得到872

wp有代码版本，推荐几个：

from Crypto.Util.number import *
"""
x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17
"""
print((2*11*17*inverse(11*17,5) + 3*5*17*inverse(5*17,11) + 5*5*11*inverse(5*11,17)) % 935)

这个不好理解的话，看下面这个

from Crypto.Util.number import inverse

M = 5 * 11 * 17
M1 = M // 5
M2 = M // 11
M3 = M // 17

N1 = inverse(M1, 5)
N2 = inverse(M2, 11)
N3 = inverse(M3, 17)

ans = pow(2 * M1 * N1 + 3 * M2 * N2 + 5 * M3 * N3, 1, M)
print(ans)

from sympy.ntheory.modular import crt
 
r = [2, 3, 5]
m = [5, 11, 17]
 
print(crt(m, r)[0])

Adrien’s Signs

正经CTF题目了

代码注释如下：

from random import randint

a = 288260533169915
p = 1007621497415251

FLAG = b'crypto{????????????????????}'


def encrypt_flag(flag):
    ciphertext = []
    plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) # flag里面每个字节都转换成二进制字符串，去除前面的0b前缀，补齐8位，连接起来
    for b in plaintext:
        e = randint(1, p) # 在1和p之间生成随机数
        n = pow(a, e, p) # 模幂运算，就是a^e mod p
        if b == '1': 
            ciphertext.append(n) # 若b为字节1，则将n加入密文
        else:
            n = -n % p # 相当于p-n
            ciphertext.append(n) # 若b为字节0，则将p-n加入密文
    return ciphertext # 输出的密文就是附件里的，要求求出FLAG


print(encrypt_flag(FLAG))