my crypto-1

1. Many Time Pad

Coursera Dan Boneh Week 1 Program Assignment（link）

题目分析

题目中11个密文均应用了相同的密钥我们知道：

$c_{1}=k \oplus m_{1},c_{2}=k \oplus m_{2},c_{1}\oplus c_{2}=m_{1}\oplus m_{2}$

根据提示中的考虑空格与 [a-zA-Z] 字符进行亦或运算会改变大小写（a变成A，B变成b）我们可以设置一个判断函数magic()：如果运算结果是0则是相同字符亦或运算，若是合法字符则是一个合法字符和空格运算，其余结果用输出’_'来标记。

def magic(c):
    if c == 0:  # same ('A' xor 'A' = '\x00')
        return '*'
    if chr(c) in string.ascii_letters:  # space xor letter
        return chr(c)
    return '_'

然后我们来运行以上步骤，通过把11个密文分别两两亦或得到带有提示符的明文亦或结果，然后通过提示字段猜测最长的那个明文具体值（也就是第7个明文（编号为6））

for c1, c2 in combinations(MSGS, 2):
   xm = strxor(bytes.fromhex(c1), bytes.fromhex(c2))
   print('{:2} {:2}'.format(MSGS.index(c1), MSGS.index(c2)), ''.join(magic(i) for i in xm))

然后就是繁琐的猜测明文过程

# KEY = strxor(bytes.fromhex(MSGS[10]), b'The ')
# KEY = strxor(bytes.fromhex(MSGS[5]), b'There are ')
# KEY = strxor(bytes.fromhex(MSGS[3]), b'The ciphertext ')
# KEY = strxor(bytes.fromhex(MSGS[10]), b'The secret message is ')  # The end is not correct
# KEY = strxor(bytes.fromhex(MSGS[5]), b'There are two types of ')
# KEY = strxor(bytes.fromhex(MSGS[7]), b'We can see the point where ')
# KEY = strxor(bytes.fromhex(MSGS[7]), b' The Concise OxfordDictionaries ')  # Interesting; Step back
# KEY = strxor(bytes.fromhex(MSGS[5]), b'There are two types of crypto')
# KEY = strxor(bytes.fromhex(MSGS[6]), b'There are two types of cyptography')
# KEY = strxor(bytes.fromhex(MSGS[0]), b'We can factor the number 15 with quantum')
# KEY = strxor(bytes.fromhex(MSGS[3]), b'The ciphertext produced by a weak encryption ')
# KEY = strxor(bytes.fromhex(MSGS[10]), b'The secret message is: When using a stream cipher')
# KEY = strxor(bytes.fromhex(MSGS[3]), b'The ciphertext produced by a weak encryption algorithm ')
# KEY = strxor(bytes.fromhex(MSGS[10]), b'The secret message is: When using a stream cipher, never use ')
# KEY = strxor(bytes.fromhex(MSGS[6]), b'There are two types of cyptography: one that allows the Government ')
# KEY = strxor(bytes.fromhex(MSGS[0]), b'We can factor the number 15 with quantum computers. We can also factor ')
# KEY = strxor(bytes.fromhex(MSGS[10]), b'The secret message is: When using a stream cipher, never use the key more than ')
# KEY = strxor(bytes.fromhex(MSGS[3]), b'The ciphertext produced by a weak encryption algorithm looks as good as ciphertext ')

最后得到最长的明文是There are two types of cyptography: one that allows the Government to use brute force to break the code, and one that requires the Government to use brute force to break you通过亦或得到密钥最后解出最终答案。

The secret message is: When using a stream cipher, never use the key more than once

完整代码

import sys
import random
from itertools import combinations
import string

MSGS = (
    '315c4eeaa8b5f8aaf9174145bf43e1784b8fa00dc71d885a804e5ee9fa40b16349c146fb778cdf2d3aff021dfff5b403b510d0d0455468aeb98622b137dae857553ccd8883a7bc37520e06e515d22c954eba5025b8cc57ee59418ce7dc6bc41556bdb36bbca3e8774301fbcaa3b83b220809560987815f65286764703de0f3d524400a19b159610b11ef3e',
    '234c02ecbbfbafa3ed18510abd11fa724fcda2018a1a8342cf064bbde548b12b07df44ba7191d9606ef4081ffde5ad46a5069d9f7f543bedb9c861bf29c7e205132eda9382b0bc2c5c4b45f919cf3a9f1cb74151f6d551f4480c82b2cb24cc5b028aa76eb7b4ab24171ab3cdadb8356f',
    '32510ba9a7b2bba9b8005d43a304b5714cc0bb0c8a34884dd91304b8ad40b62b07df44ba6e9d8a2368e51d04e0e7b207b70b9b8261112bacb6c866a232dfe257527dc29398f5f3251a0d47e503c66e935de81230b59b7afb5f41afa8d661cb',
    '32510ba9aab2a8a4fd06414fb517b5605cc0aa0dc91a8908c2064ba8ad5ea06a029056f47a8ad3306ef5021eafe1ac01a81197847a5c68a1b78769a37bc8f4575432c198ccb4ef63590256e305cd3a9544ee4160ead45aef520489e7da7d835402bca670bda8eb775200b8dabbba246b130f040d8ec6447e2c767f3d30ed81ea2e4c1404e1315a1010e7229be6636aaa',
    '3f561ba9adb4b6ebec54424ba317b564418fac0dd35f8c08d31a1fe9e24fe56808c213f17c81d9607cee021dafe1e001b21ade877a5e68bea88d61b93ac5ee0d562e8e9582f5ef375f0a4ae20ed86e935de81230b59b73fb4302cd95d770c65b40aaa065f2a5e33a5a0bb5dcaba43722130f042f8ec85b7c2070',
    '32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd2061bbde24eb76a19d84aba34d8de287be84d07e7e9a30ee714979c7e1123a8bd9822a33ecaf512472e8e8f8db3f9635c1949e640c621854eba0d79eccf52ff111284b4cc61d11902aebc66f2b2e436434eacc0aba938220b084800c2ca4e693522643573b2c4ce35050b0cf774201f0fe52ac9f26d71b6cf61a711cc229f77ace7aa88a2f19983122b11be87a59c355d25f8e4',
    '32510bfbacfbb9befd54415da243e1695ecabd58c519cd4bd90f1fa6ea5ba47b01c909ba7696cf606ef40c04afe1ac0aa8148dd066592ded9f8774b529c7ea125d298e8883f5e9305f4b44f915cb2bd05af51373fd9b4af511039fa2d96f83414aaaf261bda2e97b170fb5cce2a53e675c154c0d9681596934777e2275b381ce2e40582afe67650b13e72287ff2270abcf73bb028932836fbdecfecee0a3b894473c1bbeb6b4913a536ce4f9b13f1efff71ea313c8661dd9a4ce',
    '315c4eeaa8b5f8bffd11155ea506b56041c6a00c8a08854dd21a4bbde54ce56801d943ba708b8a3574f40c00fff9e00fa1439fd0654327a3bfc860b92f89ee04132ecb9298f5fd2d5e4b45e40ecc3b9d59e9417df7c95bba410e9aa2ca24c5474da2f276baa3ac325918b2daada43d6712150441c2e04f6565517f317da9d3',
    '271946f9bbb2aeadec111841a81abc300ecaa01bd8069d5cc91005e9fe4aad6e04d513e96d99de2569bc5e50eeeca709b50a8a987f4264edb6896fb537d0a716132ddc938fb0f836480e06ed0fcd6e9759f40462f9cf57f4564186a2c1778f1543efa270bda5e933421cbe88a4a52222190f471e9bd15f652b653b7071aec59a2705081ffe72651d08f822c9ed6d76e48b63ab15d0208573a7eef027',
    '466d06ece998b7a2fb1d464fed2ced7641ddaa3cc31c9941cf110abbf409ed39598005b3399ccfafb61d0315fca0a314be138a9f32503bedac8067f03adbf3575c3b8edc9ba7f537530541ab0f9f3cd04ff50d66f1d559ba520e89a2cb2a83',
    '32510ba9babebbbefd001547a810e67149caee11d945cd7fc81a05e9f85aac650e9052ba6a8cd8257bf14d13e6f0a803b54fde9e77472dbff89d71b57bddef121336cb85ccb8f3315f4b52e301d16e9f52f904',
)

def strxor(a, b):
    if len(a) > len(b):
        return bytes([x ^ y for (x, y) in zip(a[:len(b)], b)])
    else:
        return bytes([x ^ y for (x, y) in zip(a, b[:len(a)])])

def magic(c):
    if c == 0:  # same ('A' xor 'A' = '\x00')
        return '*'
    if chr(c) in string.ascii_letters:  # space xor letter
        return chr(c)
    return '_'

def main():

    for c1, c2 in combinations(MSGS, 2):
        xm = strxor(bytes.fromhex(c1), bytes.fromhex(c2))
        print('{:2} {:2}'.format(MSGS.index(c1), MSGS.index(c2)), ''.join(magic(i) for i in xm))

    print('\n开始猜明文～（很显然先猜大部分都是_的字母，然后疯狂填字）\n')
    KEY = strxor(bytes.fromhex(MSGS[6]), b'There are two types of cyptography: one that allows the Government to use brute force to break the code, and one that requires the Government to use brute force to break you')
    for x, m in enumerate(MSGS):
        print(x, strxor(bytes.fromhex(m), KEY).decode(encoding= 'utf-8',errors='ignore'))

    print(KEY.hex())
if __name__ == '__main__':
    main()

2. PA1 option

Write a program that allows you to “crack” ciphertexts generated using a Vigenere-like cipher, where byte-wise XOR is used instead of addition modulo 26.

题目分析

简单来说就是解密vigenere的密码，但是其中运算过程是使用逐字节异或而不是加法模26。
所以我们首先需要得到密钥key，所以我们要定义一个寻找可能密钥字符的函数find_index_key(sub_arr)。这里定义all_key为所有可能的字符，包括字母、数字、逗号、点和空格。初始化两个列表test_key和possible_key。遍历test_key中的每个值（ASCII字符），并对sub_arr中的每个字节进行亦或，如果结果不在all_key中，则将该ASCII值从possible_key中移除。最后返回possible_key。

def find_index_key(sub_arr): 
    all_key = ascii_letters + digits + ',' + '.' + ' '
    test_key = []
    possible_key = []
    # 遍历整个ascii码(0-127)
    for x in range(0x00, 0xFF):
        test_key.append(x)
        possible_key.append(x)
    for i in test_key:
        for j in sub_arr:
            if chr(i ^ j) not in all_key:
                possible_key.remove(i)
                break
    return possible_key

然后遍历key的长度，然后和密文进行亦或运算查看可能的密钥可能。

for key_len in range(1, 30):
    for index in range(key_len):
        sub_arr = ct[index::key_len]  
        possible_ch = find_index_key(sub_arr)
        print('key_len = ', key_len, 'index = ', index, 'possible_ch = ', possible_ch)
        if possible_ch:
            k = []
            for j in possible_ch:
                k.append(chr(j ^ sub_arr[0]))
            print(k)

输出的部分结果如下（这里的index便于定位密钥的位置）

key_len =  7 index =  0 possible_ch =  [186]
['C']
key_len =  7 index =  1 possible_ch =  [31]
['r']
key_len =  7 index =  2 possible_ch =  [145]
['y']
key_len =  7 index =  3 possible_ch =  [178]
['p']
key_len =  7 index =  4 possible_ch =  [83]
['t']
key_len =  7 index =  5 possible_ch =  [205]
['o']
key_len =  7 index =  6 possible_ch =  [62]
['g']

得到关键的密钥key = [186, 31, 145, 178, 83, 205, 62]
最后带入就能解出明文，最终答案

Cryptography is the practice and study of techniques for, among other things, secure communication in the presence of attackers. Cryptography has been used for hundreds, if not thousands, of years, but traditional cryptosystems were designed and evaluated in a fairly ad hoc manner. For example, the Vigenere encryption scheme was thought to be secure for decades after it was invented, but we now know, and this exercise demonstrates, that it can be broken very easily.

完整代码

from string import ascii_letters, digits

def find_index_key(sub_arr): 
    all_key = ascii_letters + digits + ',' + '.' + ' '
    test_key = []
    possible_key = []
    # 遍历整个ascii码(0-127)
    for x in range(0x00, 0xFF):
        test_key.append(x)
        possible_key.append(x)
    for i in test_key:
        for j in sub_arr:
            if chr(i ^ j) not in all_key:
                possible_key.remove(i)
                break
    return possible_key

s = "F96DE8C227A259C87EE1DA2AED57C93FE5DA36ED4EC87EF2C63AAE5B9A7EFFD673BE4ACF7BE8923CAB1ECE7AF2DA3DA44FCF7AE29235A24C963FF0DF3CA3599A70E5DA36BF1ECE77F8DC34BE129A6CF4D126BF5B9A7CFEDF3EB850D37CF0C63AA2509A76FF9227A55B9A6FE3D720A850D97AB1DD35ED5FCE6BF0D138A84CC931B1F121B44ECE70F6C032BD56C33FF9D320ED5CDF7AFF9226BE5BDE3FF7DD21ED56CF71F5C036A94D963FF8D473A351CE3FE5DA3CB84DDB71F5C17FED51DC3FE8D732BF4D963FF3C727ED4AC87EF5DB27A451D47EFD9230BF47CA6BFEC12ABE4ADF72E29224A84CDF3FF5D720A459D47AF59232A35A9A7AE7D33FB85FCE7AF5923AA31EDB3FF7D33ABF52C33FF0D673A551D93FFCD33DA35BC831B1F43CBF1EDF67F0DF23A15B963FE5DA36ED68D378F4DC36BF5B9A7AFFD121B44ECE76FEDC73BE5DD27AFCD773BA5FC93FE5DA3CB859D26BB1C63CED5CDF3FE2D730B84CDF3FF7DD21ED5ADF7CF0D636BE1EDB79E5D721ED57CE3FE6D320ED57D469F4DC27A85A963FF3C727ED49DF3FFFDD24ED55D470E69E73AC50DE3FE5DA3ABE1EDF67F4C030A44DDF3FF5D73EA250C96BE3D327A84D963FE5DA32B91ED36BB1D132A31ED87AB1D021A255DF71B1C436BF479A7AF0C13AA14794"
ct = bytes.fromhex(s)

for key_len in range(1, 30):
    for index in range(key_len):
        sub_arr = ct[index::key_len]  
        possible_ch = find_index_key(sub_arr)
        print('key_len = ', key_len, 'index = ', index, 'possible_ch = ', possible_ch)
        if possible_ch:
            k = []
            for j in possible_ch:
                k.append(chr(j ^ sub_arr[0]))
            print(k)

key = [186, 31, 145, 178, 83, 205, 62]
pt = ""
for i in range(len(ct)):
    pt += chr(ct[i] ^ key[i % 7])
print(pt)

3.Crypto Challenge Set 1(link)

(1) Convert hex to base64

如题就是把十六进制转化为base64

1
2
3

def hex_to_base64(hex_data):
    base64_string = base64.b64encode(bytes.fromhex(hex_data)).decode('utf-8')
    return base64_string

(2) Fixed XOR

等长亦或运算

def fixed_xor(hex_str1, hex_str2):
    byte_str1 = bytes.fromhex(hex_str1)
    byte_str2 = bytes.fromhex(hex_str2)
    xor_result = bytes([b1 ^ b2 for b1, b2 in zip(byte_str1, byte_str2)])
    hex_result = xor_result.hex()
    return hex_result

(3) Single-byte XOR cipher

因为是单个字节的亦或密码，并且选取字母分数最高的密钥，所以遍历所有的key。选取明文中英文字符占比分数最大的明文和密钥。

import codecs

def decrypt_single_byte_xor(cipher_hex):
    cipher_bytes = codecs.decode(cipher_hex, 'hex')
    def is_english(text):
        return text.isascii() and text.isprintable()
    def english_score(text):
        return sum(1 for char in text if char.isalpha())
    best_key = None
    best_score = -1
    best_plaintext = ""
    
    for key in range(256):
        decrypted = bytes([cipher_bytes[i] ^ key for i in range(len(cipher_bytes))])
        decrypted_text = decrypted.decode('utf-8', errors='ignore')
        if is_english(decrypted_text):
            score = english_score(decrypted_text)
            if score > best_score:
                best_score = score
                best_key = key
                best_plaintext = decrypted_text
    return best_plaintext, best_key

cipher_hex = "1b37373331363f78151b7f2b783431333d78397828372d363c78373e783a393b3736"
decrypted_text, key = decrypt_single_byte_xor(cipher_hex)
print("Decrypted Text:", decrypted_text)
print("Key:", hex(key))

运行代码解出答案

1 2	Decrypted Text: Cooking MC's like a pound of bacon Key: 0x58

(4) Detect single-character XOR

这个引入上一问的函数并且加入字符频次表。通过逐行读取密文并且应用单字符密钥得到每行最高分数的key。最后选取出最高分数的明文作为答案输出。

def get_english_score(input_bytes):
    character_frequencies = {
        'a': .08167, 'b': .01492, 'c': .02782, 'd': .04253,
        'e': .12702, 'f': .02228, 'g': .02015, 'h': .06094,
        'i': .06094, 'j': .00153, 'k': .00772, 'l': .04025,
        'm': .02406, 'n': .06749, 'o': .07507, 'p': .01929,
        'q': .00095, 'r': .05987, 's': .06327, 't': .09056,
        'u': .02758, 'v': .00978, 'w': .02360, 'x': .00150,
        'y': .01974, 'z': .00074, ' ': .13000
    }
    return sum([character_frequencies.get(chr(byte), 0) for byte in input_bytes.lower()])

def single_char_xor(input_bytes, char_value):
    output_bytes = b''
    for byte in input_bytes:
        output_bytes += bytes([byte ^ char_value])
    return output_bytes

def bruteforce_single_char_xor(ciphertext):
    potential_messages = []
    for key_value in range(256):
        message = single_char_xor(ciphertext, key_value)
        score = get_english_score(message)
        data = {
            'message': message,
            'score': score,
            'key': key_value
        }
        potential_messages.append(data)
    return sorted(potential_messages, key=lambda x: x['score'], reverse=True)[0]

def detect_xor_cipher(file_path):
    with open(file_path, "r") as file:
        lines = file.readlines()
        best_plaintext = ""
        best_key = None
        best_score = -1

        for line in lines:
            cipher_hex = line.strip()
            ciphertext = bytes.fromhex(cipher_hex)
            result = bruteforce_single_char_xor(ciphertext)
            if result['score'] > best_score:
                best_score = result['score']
                best_plaintext = result['message']
                best_key = result['key']

        return best_plaintext, hex(best_key)

def main():
    file_path = "plain.txt"
    detected_plaintext, key = detect_xor_cipher(file_path)
    print("plaintext: ",detected_plaintext.decode())
    print(f"Key: {key}")

if __name__ == '__main__':
    main()

最终答案

1
2
3

plaintext:  Now that the party is jumping

Key: 0x35

(5) Implement repeating-key XOR

这个就是重复密钥进行亦或操作，代码如下。

def xor(plaintext, key):
    repeated_key = (key * (len(plaintext) // len(key))) + key[:len(plaintext) % len(key)]
    encrypted_decrypted = bytes([p ^ k for p, k in zip(plaintext.encode(), repeated_key.encode())])
    return encrypted_decrypted.hex()

plaintext = '''Burning 'em, if you ain't quick and nimble I go crazy when I hear a cymbal'''
key = "ICE"
encrypted1 = xor(plaintext, key)
print("Encrypted:", encrypted1)

(6) Break repeating-key XOR

首先要猜测密钥的长度这里范围由题目所述（2到40），设置了计算汉明距离的函数hamming_distance(a, b)其后继承上述题目的代码得到最高字符频次分数的密码。

import base64

def English_Scoring(t):
    letter_frequency = {
        'a': .08167, 'b': .01492, 'c': .02782, 'd': .04253,
        'e': .12702, 'f': .02228, 'g': .02015, 'h': .06094,
        'i': .06094, 'j': .00153, 'k': .00772, 'l': .04025,
        'm': .02406, 'n': .06749, 'o': .07507, 'p': .01929,
        'q': .00095, 'r': .05987, 's': .06327, 't': .09056,
        'u': .02758, 'v': .00978, 'w': .02360, 'x': .00150,
        'y': .01974, 'z': .00074, ' ': .15000
    }
    return sum([letter_frequency.get(chr(i), 0) for i in t.lower()])  

def Single_XOR(s, single_character):
    t = b''
    for i in s:
        t += bytes([i ^ single_character])
    return t

def ciphertext_XOR(s):
    _data = []
    for single_character in range(256):
        ciphertext = Single_XOR(s, single_character)
        score = English_Scoring(ciphertext)
        data = {
            'Single character': single_character,
            'ciphertext': ciphertext,
            'score': score
        }
        _data.append(data)
    score = sorted(_data, key=lambda score: score['score'], reverse=True)[0]
    return score

def Repeating_key_XOR(_cipher, _key):
    message = b''
    length = len(_key)
    for i in range(len(_cipher)):
        message += bytes([_cipher[i] ^ _key[i % length]])
    return message

def hamming_distance(a, b):
    distance = 0
    for i, j in zip(a, b):
        byte = i ^ j
        distance += sum(k == '1' for k in bin(byte))
    return distance

def Get_the_keysize(ciphertext):
    data = []
    for keysize in range(2, 41):
        block = [ciphertext[i:i + keysize] for i in range(0, len(ciphertext), keysize)]
        distances = []
        for i in range(len(block) - 1):
            block1 = block[i]
            block2 = block[i + 1]
            distance = hamming_distance(block1, block2)
            distances.append(distance / keysize)
        _distance = sum(distances) / len(distances)
        _data = {
            'keysize': keysize,
            'distance': _distance
        }
        data.append(_data)
    _keysize = sorted(data, key=lambda distance: distance['distance'])[0]
    return _keysize

def Break_repeating_key_XOR(ciphertext):
    _keysize = Get_the_keysize(ciphertext)
    keysize = _keysize['keysize']
    print("keysize:", keysize)
    key = b''
    message = b''
    block = [ciphertext[i:i + keysize] for i in range(0, len(ciphertext), keysize)]
    for i in range(keysize):
        new_block = b''
        for j in range(len(block) - 1):
            s = block[j]
            new_block += bytes([s[i]])
        score = ciphertext_XOR(new_block)
        key += bytes([score['Single character']])
    for k in range(len(block)):
        message += Repeating_key_XOR(block[k], key)
    return message, key

if __name__ == '__main__':
    with open('decription.txt', 'r') as of:
        ciphertext = of.read()
        ciphertext = base64.b64decode(ciphertext)
    message, key = Break_repeating_key_XOR(ciphertext)
    print("message:", message.decode('utf-8'), "\nkey:", key.decode('utf-8'))

最后运算出密钥长度为29，key: Terminator X: Bring the noise解密后的明文为：

I'm back and I'm ringin' the bell 
A rockin' on the mike while the fly girls yell 
In ecstasy in the back of me 
Well that's my DJ Deshay cuttin' all them Z's 
Hittin' hard and the girlies goin' crazy 
Vanilla's on the mike, man I'm not lazy. 

I'm lettin' my drug kick in 
It controls my mouth and I begin 
To just let it flow, let my concepts go 
My posse's to the side yellin', Go Vanilla Go! 

Smooth 'cause that's the way I will be 
And if you don't give a damn, then 
Why you starin' at me 
So get off 'cause I control the stage 
There's no dissin' allowed 
I'm in my own phase 
The girlies sa y they love me and that is ok 
And I can dance better than any kid n' play 

Stage 2 -- Yea the one ya' wanna listen to 
It's off my head so let the beat play through 
So I can funk it up and make it sound good 
1-2-3 Yo -- Knock on some wood 
For good luck, I like my rhymes atrocious 
Supercalafragilisticexpialidocious 
I'm an effect and that you can bet 
I can take a fly girl and make her wet. 

I'm like Samson -- Samson to Delilah 
There's no denyin', You can try to hang 
But you'll keep tryin' to get my style 
Over and over, practice makes perfect 
But not if you're a loafer. 

You'll get nowhere, no place, no time, no girls 
Soon -- Oh my God, homebody, you probably eat 
Spaghetti with a spoon! Come on and say it! 

VIP. Vanilla Ice yep, yep, I'm comin' hard like a rhino 
Intoxicating so you stagger like a wino 
So punks stop trying and girl stop cryin' 
Vanilla Ice is sellin' and you people are buyin' 
'Cause why the freaks are jockin' like Crazy Glue 
Movin' and groovin' trying to sing along 
All through the ghetto groovin' this here song 
Now you're amazed by the VIP posse. 

Steppin' so hard like a German Nazi 
Startled by the bases hittin' ground 
There's no trippin' on mine, I'm just gettin' down 
Sparkamatic, I'm hangin' tight like a fanatic 
You trapped me once and I thought that 
You might have it 
So step down and lend me your ear 
'89 in my time! You, '90 is my year. 

You're weakenin' fast, YO! and I can tell it 
Your body's gettin' hot, so, so I can smell it 
So don't be mad and don't be sad 
'Cause the lyrics belong to ICE, You can call me Dad 
You're pitchin' a fit, so step back and endure 
Let the witch doctor, Ice, do the dance to cure 
So come up close and don't be square 
You wanna battle me -- Anytime, anywhere 

You thought that I was weak, Boy, you're dead wrong 
So come on, everybody and sing this song 

Say -- Play that funky music Say, go white boy, go white boy go 
play that funky music Go white boy, go white boy, go 
Lay down and boogie and play that funky music till you die. 

Play that funky music Come on, Come on, let me hear 
Play that funky music white boy you say it, say it 
Play that funky music A little louder now 
Play that funky music, white boy Come on, Come on, Come on 
Play that funky music

4.MTC3 Cracking SHA1-Hashed Passwords

题目链接(link)

根据图片中键盘上的指纹分布，可以看出右边的数字键只有2486，很有可能是当做上下左右的功能，（常识这个应该是没有在密钥里的）所以就可以将密钥空间缩小。然后逐一写出剩余的可能按键，最后写一个dfs算法遍历每一种情况再用SHA1加密最后和给定哈希值比对。这里设置时钟得到运行时间为1s。

import hashlib
import itertools
import datetime
import sys

hash1 = "67ae1a64661ac8b4494666f58c4822408dd0a3e4"
str2 = [['Q', 'q'], ['W', 'w'], ['%', '5'], ['8', '('], ['=', '0'], ['I', 'i'], ['*', '+'], ['n', 'N']]

def sha_encrypt(string):
    sha = hashlib.sha1(string.encode())
    return sha.hexdigest()

starttime = datetime.datetime.now()
for combination in itertools.product(*str2):
    for perm in itertools.permutations(combination):
        candidate = "".join(perm)
        if sha_encrypt(candidate) == hash1:
            print("ans:", candidate)
            endtime = datetime.datetime.now()
            print("t:", (endtime - starttime).seconds, "seconds")
            sys.exit(0)

print("Password not found.")