【解码异或排列】一个简单有趣的异或逆运算密码题1.题目概述2.题目分析3.密码逆运算

72 阅读 0 评论 48 点赞

我是靠谱客的博主无情小懒虫，最近开发中收集的这篇文章主要介绍【解码异或排列】一个简单有趣的异或逆运算密码题1.题目概述2.题目分析3.密码逆运算，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

此题源于一个简单算法题的改编，在做这个算法题的时候，突然发现可以拿来做一个简单的密码题，在此分享一下分析思路。

1.题目概述

一个简单的Python加密，需要分析代码逆运算得出flag。

from flag import flag
import base64

print(len(flag))
table=sorted(flag)
for i in table:
    print(ord(i),end="")
print()
passwd=[]
for i in range(len(flag)-1):
    passwd.append((ord(flag[i])-64)^(ord(flag[i+1])-64))
print(base64.b64encode(bytes(passwd)))
'''
控制台输出如下:
27
656667686970717273747576777879808182838485868788899091
b'BhIXBg0MHAYfERIXAgEPAgEHFgIbFRQMAxY='
'''

2.题目分析

分析python代码，发现主要的步骤如下：
- 输出flag的长度为27。
- 对flag进行排序，输出flag每一位的ASCII码，得到656667686970717273747576777879808182838485868788899091。
- 定义列表passwd，其中
  passwd[i] = (ord(flag[i])-64)^(ord(flag[i+1])-64)。
分析其具体的步骤，可以发现如下特点：
- 1.flag长度27。
- 2.flag的ASCII范围是65-91。
- 3.flag的所有位不重复。
- 4.ord(flag[i] -64)的范围为1-27。
基于以上分析，可以将问题抽象为：
- 一个整数数组a，由前27个正整数组成，经过加密后得到长度为26的数组b，且加密的算法为：b[i] = a[i] ^ a[i+1]。
- 现在我们得到了base64编码后的b数组，需要求得a数组，进而可以求出flag。
公式推导思路：
- 如果我们不考虑任何边界情况，单独从b[i] = a[i] ^ a[i+1]这个加密算法来看，可以得出b[i-1] = a[i-1] ^ a[i]，接下来需要推导出a[i]的公式。
- 原式两边同时对a[i-1]异或，得到b[i-1] ^ a[i-1] = a[i-1] ^ a[i] ^ a[i-1]。
- a[i-1] ^ b[i-1] = a[i-1] ^ a[i-1] ^ a[i]。
- a[i-1] ^ b[i-1] = 0 ^ a[i]。
- a[i] = a[i-1] ^ b[i-1]。
- 从上面的推导，我们已经可以得到a[i]的具体公式，但是上面这个公式其实只对i >= 1的情况适用，当i==0时，这个公式就不再适用，所以我们得先求出a[0]的值。
求a[0]的思路：
- 对a[0]，如果我们知道整个a数组的异或结果，并且知道除了a[0]整个数组的异或结果，就可以得出a[0]的值，设a数组的异或结果为all，设除了a[0]外的所有异或结果为not0，那么a[0] = all ^ not0。
- 对于all，由于a数组由1-27的不同数字组成，所以可以很容易的得到。
- 对于not0，由于b数组是26位，且有b[1] = a[1] ^ a[2]，b[3] = a[3] ^ a[4]，b[5] = a[5] ^ a[6]，依次类推，可以得到not0 = b[1] ^ b[3] ^ b[5] ... ^ b[25]。b数组已知，not0就可以很容易的得到。
- 综合上面三个步骤，我们就可以得出a[0]的值。
综合上述所有的思路，我们得到最终的求解思路：
- 对输出结果进行base64解码，得到encode数组。
- 求出1-27的异或结果，求出encode[1] ^ encode[3] ^ encode[5] ... ^ encode[25]的结果，从而得到flag[0]的值。
- 利用公式flag[i] = flag[i-1] ^ encode[i-1]得到flag数组其它元素。
- 对flag数组每位加上64，得到最终的代码。

3.密码逆运算

解密Python脚本如下：

import base64

# 异或逆运算解密
def decode(b):
    a=[]
    all = 1
    # 求a中所有异或值
    for i in range(2,28):
        all ^= i
    not0=b[1]
    # 求a中除了第一个元素的所有异或值
    for i in range(3,len(b),2):
        not0 ^= b[i]
    # a[0]
    a0 = all ^ not0
    a.append(a0)
    # a剩余元素的值
    for i in range(1,27):
        a.append(a[i-1] ^ b[i-1])
    return a


passwd = 'BhIXBg0MHAYfERIXAgEPAgEHFgIbFRQMAxY='
passwd = base64.b64decode(passwd)
encode = []
for i in passwd:
    encode.append(i)
flag = decode(encode)
for i in flag:
    print(chr(i+64),end="")