如何反转异或移位操作

Question

我有以下异或移位编码器

char a[] = "text";
int b = strlen(a);
for (int c = 0; c < b; c++) {
    if (c > 0) a[c] ^= a[c-1];
    a[c] ^= a[c] >> 3;
    a[c] ^= a[c] >> 2;
    a[c] ^= a[c] >> 1;
    printf("%02x", (unsigned int)(a[c]));
}

我想将十六进制输出恢复为原始字符串。

考虑到移位在某些情况下会消除右侧无法再检索的位，这甚至有可能吗？如果可能的话，如何恢复这些操作？

Answer 1

是的，没那么难。只需将 xor-shit 结果映射回其原始值即可。考虑这个函数：

char f(char c) {
    c ^= c >> 3;
    c ^= c >> 2;
    c ^= c >> 1;
    return c;
}

您应该能够让自己满意，对于每个可能的输入值（从 0 到 127），都有一个对应的唯一输出。（当然，如果将 char 更改为 unsigned char，则该函数将适用于任何 8 位输入。）

使用这个函数，你可以很容易地创建一个数组来执行这个函数的逆运算：

char g(char c) {
    static char *map = NULL;
    if (!map) {
        map = malloc(128);
        for (int i=0; i<128; i++) map[f(i)] = i;
    }
    return map[c];
}

然后就写一个函数依次读取字符串的每个字符，应用这个反向函数，然后将结果与前一个值异或：

char *decode(char *s, int len) {
    char *start = s, last = 0;
    while (len--) {
        char tmp = *s;
        *s = last ^ g(*s);
        last = tmp;
        s++;
    }
    return start;
}

Answer 2

considering that the shift would in some cases eliminate bits on the right side

其实这是微不足道的，特别是因为比特被消除了！

让我们反转您示例中的最后一步，您应该能够从那里向后工作。让我们将 8 位数字的数字视为名为 a 到 h 的布尔变量以及生成的布尔变量 i 到 p:

abcdefgh ^
0abcdefg =
ijklmnop

我们只看到i到p，但我们想找到a到h。请注意 a^0=i，但是任何与 0 异或的东西都只是它本身，所以我们知道 a。我们还知道：b^a=j，如果我们用“a”对两边进行异或，我们得到 b^a^a=j^a。 Xor 的特殊之处在于对具有相同值的东西进行两次异或将其抵消，因此等式简化为 b=j^a。现在我们有 b。我相信你知道如何继续这个并获得其余的数字并最终获得种子。

Answer 3

查找 table 在这种情况下仅使用 8 位值就可以工作，但也可以在没有 8 位值的情况下进行这种反转。

要反转 x ^= x >> a 做：

x ^= x >> a;
x ^= x >> (2*a);
x ^= x >> (4*a);
x ^= x >> (8*a);
// ...

直到移位量a超过类型的位宽。考虑到这一点，您可以拥有像这样的编码和解码功能：

void encode(unsigned char* str, size_t len) {
    for (int c = 0; c < len; c++) {
        if (c > 0) str[c] ^= str[c-1];
        str[c] ^= str[c] >> 3;
        str[c] ^= str[c] >> 2;
        str[c] ^= str[c] >> 1;
    }
}

void decode(unsigned char* str, size_t len) {
    for (int c = len - 1; c >= 0; c--) {
        str[c] ^= str[c] >> 1;
        str[c] ^= str[c] >> 2;
        str[c] ^= str[c] >> 4;
        
        str[c] ^= str[c] >> 2;
        str[c] ^= str[c] >> 4;
        
        str[c] ^= str[c] >> 3;
        str[c] ^= str[c] >> 6;
        if (c > 0) str[c] ^= str[c-1];
    }
}

如何反转异或移位操作

How to reverse XOR-shift operations

c

xor

shift