Cryptopals

做题笔记

惊了我前几天面试 Bitgo 正好问到了第三题，虽然本来也很简单。。。

Set 1

想了一下我那些解法似乎太暴力了而且只能处理 ASCII 的情况，如果是 UTF 应该就失效了。

1

func c01(str string) string {
	data, err := hex.DecodeString(str)
	if err != nil {
		panic(err)
	}
	return base64.StdEncoding.EncodeToString(data)
}

2

func c02(s1, s2 string) string {
	b1, err := hex.DecodeString(s1)
	if err != nil {
		panic(err)
	}
	b2, err := hex.DecodeString(s2)
	if err != nil {
		panic(err)
	}

	length := len(b1)
	if len(b1) < len(b2) {
		length = len(b2)
	}

	out := make([]byte, length)
	for i := 0; i < length; i++ {
		out[i] = b1[i] ^ b2[i]
	}
	return hex.EncodeToString(out)
}

3

func notValid(b byte) bool {
	//return b > 126
	return (b < 32 || b > 126) && b != 0 && b != 10
}

func c03(prefix, str string) {
	data, err := hex.DecodeString(str)
	if err != nil {
		panic(err)
	}

	length := len(data)
	var c uint8
	for c = 0; c != 255; c++ {
		out := make([]byte, length)
		valid := true
		for i := 0; i < length; i++ {
			b := data[i] ^ c
			if notValid(b) {
				valid = false
				break
			}
			out[i] = b
		}
		if valid {
			fmt.Printf("%s: %d: %s\n", prefix, c, string(out))
		}
	}
}

答案是Cooking MC's like a pound of bacon，用来加密的字符是 ASCII 值为 88 的X。

4

func c04(path string) {
	file, err := os.Open(path)
	if err != nil {
		panic(err)
	}

	r := bufio.NewReader(file)
	n := 0
	for {
		n++
		line, _, err := r.ReadLine()
		if err == io.EOF {
			return
		} else if err != nil {
			panic(err)
		}

		c03(fmt.Sprintf("%d", n), string(line))
	}
}

直接用上一题即可，这里值得注意的是notValid这个判断，之前忘处理换行调试了一会。

答案是第 171 行的Now that the party is jumping\n，用来加密的字符是 ASCII 值为 53 的5。

5

func c05(raw, key string) string {
	rawBytes := []byte(raw)
	keyBytes := []byte(key)
	n := len(rawBytes)/len(keyBytes) + 1

	length := len(rawBytes)
	keyBytes = bytes.Repeat(keyBytes, n)

	out := make([]byte, length)
	for i := 0; i < length; i++ {
		out[i] = rawBytes[i] ^ keyBytes[i]
	}
	return hex.EncodeToString(out)
}

6

func hamming(b1, b2 []byte) int {
	h := 0
	length := len(b1)
	if len(b1) < len(b2) {
		length = len(b2)
	}

	for i := 0; i < length; i++ {
		b := b1[i] ^ b2[i]
		h += bits.OnesCount8(b)
	}

	return h
}

按照问题里面的思路走，首先我们需要一个计算 Hamming Distance 的函数。

func c06(path string) {
	file, err := os.Open(path)
	if err != nil {
		panic(err)
	}

	dec := base64.NewDecoder(base64.StdEncoding, file)
	data, err := io.ReadAll(dec)
	if err != nil {
		panic(err)
	}

    keySize := 2
	lowestNormalized := float64(123456789)
	for i := 2; i <= 40; i++ {
		normalized := float64(hamming(data[:i], data[i:2 * i])) / float64(i)
		fmt.Printf("%d: %f\n", i, normalized)
		if lowestNormalized > normalized {
			lowestNormalized = normalized
			keySize = i
		}
	}
	fmt.Printf("%d: %f\n", keySize, lowestNormalized)

    ss := make([][]byte, keySize)

	for i := 0; i < keySize; i++ {
		c := uint8(0)
		for {
			valid := true
			for j := 0; i+keySize*j < len(data); j++ {
				if notValid(data[i+keySize*j] ^ c) {
					valid = false
					break
				}
			}
			if valid {
				fmt.Printf("%d: %d\n", i, c)
				if ss[i] == nil {
					ss[i] = []byte{c}
				} else {
					ss[i] = append(ss[i], c)
				}
			}

			if c == 255 {
				break
			} else {
				c++
			}
		}
	}

代码并不难写，值最低的密钥长度是 5，然而运行后却发现没有任何位置的任何字符是有效的。之后又试了几个值比较低的密钥长度也都不行，一气之下直接遍历所有长度，惊人地发现 29 是对的。

	for i := 0; i < keySize; i++ {
		if len(ss[i]) == 1 {
			fmt.Printf("%c", ss[i][0])
		} else {
			fmt.Printf("(%s)", string(ss[i]))
		}
	}
	fmt.Printf("\n")

因为一个位置可能存在多个有效的字符，所以我们可以打印一下所有情况然后人工分析。

	// Termi(dn)ator( *)(RX): B(gmpqrsuvwz{|)( !"#%&'()*+,-./02345789;<=>?i)ng th(`abcdefgikmpz}~)( sy)noi(sy)e
	// Terminator X: Bring the noise

	key := "Terminator X: Bring the noise"
	rawBytes := data
	keyBytes := []byte(key)
	n := len(rawBytes)/len(keyBytes) + 1

	length := len(rawBytes)
	keyBytes = bytes.Repeat(keyBytes, n)

	out := make([]byte, length)
	for i := 0; i < length; i++ {
		out[i] = rawBytes[i] ^ keyBytes[i]
	}
	fmt.Println(string(out))
}

答案太长了就不贴了。

7

func c07(path string, key []byte) {
	c, err := aes.NewCipher(key)
	if err != nil {
		panic(err)
	}

	rawData, err := ioutil.ReadFile(path)
	if err != nil {
		panic(err)
	}

	data, err := base64.StdEncoding.DecodeString(string(rawData))
	if err != nil {
		panic(err)
	}

	decoded := make([]byte, c.BlockSize())
	for len(data) > 0 {
		c.Decrypt(decoded, data)
		data = data[c.BlockSize():]
		fmt.Printf("%s", string(decoded))
	}
}

自己手动实现一下 ECB 就行。

8

func c08(path string) {
	data, err := ioutil.ReadFile(path)
	if err != nil {
		panic(err)
	}

	lines := strings.Split(string(data), "\n")
	for _, line := range lines {
		str := line
		for len(str) > 0 {
			if strings.Contains(str[32:], str[:32]) {
				fmt.Println(line)
				return
			} else {
				str = str[32:]
			}
		}
	}
}

检测有没有重复的块。

答案是

d880619740a8a19b7840a8a31c810a3d08649af70dc06f4fd5d2d69c744cd283e2dd052f6b641dbf9d11b0348542bb5708649af70dc06f4fd5d2d69c744cd2839475c9dfdbc1d46597949d9c7e82bf5a08649af70dc06f4fd5d2d69c744cd28397a93eab8d6aecd566489154789a6b0308649af70dc06f4fd5d2d69c744cd283d403180c98c8f6db1f2a3f9c4040deb0ab51b29933f2c123c58386b06fba186a

Set 2

刚从青海回家，继续做题。考虑到 Go 不太适合写题以及马上要开始的工作，试试用 Python 写。

def xor(a1, a2):
    return bytes(a ^ b for (a, b) in zip(a1, a2))

9

def pkcs7(bytes : bytearray, length : int):
    n = length - len(bytes)
    return bytes + bytearray((n,)) * n

print(pkcs7(b'YELLOW SUBMARINE', 20))

没啥可说的。。。

10

AES_BLOCK_SIZE = 16
IV_EMPTY = bytearray((0,)) * AES_BLOCK_SIZE
from Crypto.Cipher import AES
import base64

def aescbcEnc(data : bytearray, iv : bytearray, key : bytearray):
    out = bytearray()
    last = iv
    cipher = AES.new(key, AES.MODE_ECB)
    for i in range(0, len(data), AES_BLOCK_SIZE):
        block = data[i:i + AES_BLOCK_SIZE]
        if len(block) < AES_BLOCK_SIZE:
            block = pkcs7(block, AES_BLOCK_SIZE)
            block = xor(block, last)

        ct = cipher.encrypt(block)
        last = ct
        out += ct
    return out

def aescbcDec(data : bytearray, iv : bytearray, key : bytearray):
    out = bytearray()
    last = iv
    cipher = AES.new(key, AES.MODE_ECB)
    for i in range(0, len(data), AES_BLOCK_SIZE):
        block = data[i:i + AES_BLOCK_SIZE]
        pt = cipher.decrypt(block)
        pt = xor(pt, last)
        last = block
        out += pt
    return out

print(aescbcDec(aescbcEnc(b'0123456789012345', IV_EMPTY, b'YELLOW SUBMARINE'), IV_EMPTY, b'YELLOW SUBMARINE'))
f10 = open('10.txt', 'r').read()
d10 = base64.b64decode(f10)
print(aescbcDec(d10, IV_EMPTY, b'YELLOW SUBMARINE'))

也没啥可说的。。。

11

还没看懂题