Xor异或解密

发表于 | 分类于 |
字数统计: 1.4k 字 | 阅读时长 ≈ 6 分钟

Xorzz

De1ctf密码学一道题，当时不会做，orz….,题目

from itertools import *
from data import flag,plain

key=flag.strip("de1ctf{").strip("}")
assert(len(key)<38)
salt="WeAreDe1taTeam"
ki=cycle(key)
si=cycle(salt)
cipher = ''.join([hex(ord(p) ^ ord(next(ki)) ^ ord(next(si)))[2:].zfill(2) for p in plain])
print cipher
output:

49380d773440222d1b421b3060380c3f403c3844791b202651306721135b6229294a3c3222357e766b2f15561b35305e3c3b670e49382c295c6c170553577d3a2b791470406318315d753f03637f2b614a4f2e1c4f21027e227a4122757b446037786a7b0e37635024246d60136f7802543e4d36265c3e035a725c6322700d626b345d1d6464283a016f35714d434124281b607d315f66212d671428026a4f4f79657e34153f3467097e4e135f187a21767f02125b375563517a3742597b6c394e78742c4a725069606576777c314429264f6e330d7530453f22537f5e3034560d22146831456b1b72725f30676d0d5c71617d48753e26667e2f7a334c731c22630a242c7140457a42324629064441036c7e646208630e745531436b7c51743a36674c4f352a5575407b767a5c747176016c0676386e403a2b42356a727a04662b4446375f36265f3f124b724c6e346544706277641025063420016629225b43432428036f29341a2338627c47650b264c477c653a67043e6766152a485c7f33617264780656537e5468143f305f4537722352303c3d4379043d69797e6f3922527b24536e310d653d4c33696c635474637d0326516f745e610d773340306621105a7361654e3e392970687c2e335f3015677d4b3a724a4659767c2f5b7c16055a126820306c14315d6b59224a27311f747f336f4d5974321a22507b22705a226c6d446a37375761423a2b5c29247163046d7e47032244377508300751727126326f117f7a38670c2b23203d4f27046a5c5e1532601126292f577776606f0c6d0126474b2a73737a41316362146e581d7c1228717664091c

题目中

ord(p) ^ ord(next(ki)) ^ ord(next(si))

三个异或之后再转换为16进制，[2:].zfill(2)去掉了头两位0x，并在少于两位时左补0，输出有1200位，也就是一次异或得到两位数字
由此可以得出ord(p) ^ ord(next(ki))的一串值，然后plain是个600位的字符串，key循环和plain中的每一位字符异或，然后就不会了orz….

先是python2按位异或，python中字符串*一个数字n相当于将字符串重复了n遍，(密文的长度/salt长度)+1是salt字符串重复的次数，再 [:len(h)]取与密文相同的位数，然后strxor按位异或，结果base64加密后输出

# coding=<encoding name>
# vim: set fileencoding=utf-8 :
import itertools
import base64
from Crypto.Util.strxor import strxor

a='WeAreDe1taTeam'
h='49380d773440222d1b421b3060.....'
h=h.decode('hex')
m=(a*(len(h)/len(a)+1))[:len(h)]
o=strxor(h,m).encode('base64')
print(o)

一次流密码的解密

汉明距离猜解密钥长度

汉明距离其实是在二进制层面观测两个等长字符串的比特位差异，也就是1111和1000的汉名距离为3，两个二进制字符串按位异或有多少个1，汉明距离就为多少

那么汉明距离和密文长度又有什么关系呢？
两个以ascii编码的英文字符的汉明距离是2-3之间，也就是说正常英文字母的平均汉明距离为2-3（每比特），任意字符（非纯字母）的两两汉明距离平均为4。当我们使用了正确的密钥长度后，对密文中两两字母进行计算汉明距离，汉明距离的值应该是趋于最小

根据猜解的密钥长度解得密钥

利用明文中空格

在使用异或加密的形式下，使用相同密钥加密的明文和密文间存在这两个规律：
1.密文和密文异或等于明文和明文异或。 也就是说将明文和密文按照密钥长度分组后，相对应得两个密文字符和两个明文字符异或是相等的
2.空格和所有小写字母异或结果是相应的大写字母，空格和所有大写字母异或是相应的小写字母。

这样当两个密文按照字节异或后的结果处于字母表的ascii值之间，我们就可以有很大的概率认为异或的明文字符之一是空格

也就是 密文第一位^密文第31位=字母表ascii=明文第1(31)位^空格

按密钥长度将密文进行分组，取其中一个分组，将里面的字符两两异或，如果某一密文字符和其他密文字符异或的结果都处于字母表区间，那么我们将推断其对应位置的明文为空格，密文字节与空格异或就得到了对应位置的密钥密钥

字频攻击

最后附上脚本，造轮子是不可能自己会造的(枯了
本文非原创，原文参考链接：https://www.anquanke.com/post/id/161171

没想明白为什么^无法进行str^str的异或，但是在脚本中就可以qaq

import base64
import string


def bxor(a, b):     # 计算汉明距离，两个二进制字符串按位异或有多少个1就有多少个不同的字符
    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 hamming_distance(b1, b2):#计算二进制字符按位异或后1的个数
    differing_bits = 0
    for byte in bxor(b1, b2):
        differing_bits += bin(byte).count("1")
    return differing_bits



def score(s):
    freq = {}
    freq[' '] = 700000000
    freq['e'] = 390395169
    freq['t'] = 282039486
    freq['a'] = 248362256
    freq['o'] = 235661502
    freq['i'] = 214822972
    freq['n'] = 214319386
    freq['s'] = 196844692
    freq['h'] = 193607737
    freq['r'] = 184990759
    freq['d'] = 134044565
    freq['l'] = 125951672
    freq['u'] = 88219598
    freq['c'] = 79962026
    freq['m'] = 79502870
    freq['f'] = 72967175
    freq['w'] = 69069021
    freq['g'] = 61549736
    freq['y'] = 59010696
    freq['p'] = 55746578
    freq['b'] = 47673928
    freq['v'] = 30476191
    freq['k'] = 22969448
    freq['x'] = 5574077
    freq['j'] = 4507165
    freq['q'] = 3649838
    freq['z'] = 2456495
    score = 0
    string=bytes.decode(s)
    for c in string.lower():
        if c in freq:
            score += freq[c]
    return score


def break_single_key_xor(b1):
    max_score = 0
    english_plaintext = 0
    key = 0

    for i in range(0,256):
        b2 = [i] * len(b1)
        try:
            plaintext = bxor(b1, b2)
            pscore = score(plaintext)
        except Exception:
            continue
        if pscore > max_score or not max_score:
            max_score = pscore
            english_plaintext = plaintext
            key = chr(i)
    return key



text = '上面脚本中输出的结果'
with open(r"c:/Users/lyy18291855970/Desktop/密码学/密码题/the cryptopals crypto challenges/6.txt", "r") as f:
    for line in f:
        text += line
b = base64.b64decode(text)


normalized_distances = []


for KEYSIZE in range(2, 40):
    #我们取其中前6段计算平局汉明距离
    b1 = b[: KEYSIZE]
    b2 = b[KEYSIZE: KEYSIZE * 2]
    b3 = b[KEYSIZE * 2: KEYSIZE * 3]
    b4 = b[KEYSIZE * 3: KEYSIZE * 4]
    b5 = b[KEYSIZE * 4: KEYSIZE * 5]
    b6 = b[KEYSIZE * 5: KEYSIZE * 6]
    b7 = b[KEYSIZE * 6: KEYSIZE * 7]

    normalized_distance = float(
        hamming_distance(b1, b2) +
        hamming_distance(b2, b3) +
        hamming_distance(b3, b4) +
        hamming_distance(b4, b5) +
        hamming_distance(b5, b6) 
    ) / (KEYSIZE * 5)
    normalized_distances.append(
        (KEYSIZE, normalized_distance)
    )
normalized_distances = sorted(normalized_distances, key=lambda x: x[1])


for KEYSIZE, _ in normalized_distances[:5]:
    block_bytes = [[] for _ in range(KEYSIZE)]
    for i, byte in enumerate(b):
        block_bytes[i % KEYSIZE].append(byte)
    keys = ''

    for bbytes in block_bytes:
        keys += break_single_key_xor(bbytes)
    key = bytearray(keys * len(b), "utf-8")
    plaintext = bxor(b, key)
    print("keysize:", KEYSIZE)
    print("key is:", keys, "n")
    s = bytes.decode(plaintext)
    print(s)
0%