如何解密采用右移1位后异或原消息规则加密的密文？

解密原理 #

加密规则：c = m ^ (m >> 1)（>>为无符号右移，高位补0）

我们可以直接从比特位的运算特性推导解密逻辑：

• 32位无符号整数的最高位（第31位）：m[31] = c[31]，因为m>>1的最高位是0，异或后不会改变m最高位的原始值
• 第k位（k<31）：m[k] = c[k] ^ m[k+1]，直接从加密公式c[k] = m[k] ^ m[k+1]变形可得

解密代码实现 #

1. 直观逐位实现 #

#include <stdio.h>
#include <stdint.h>

uint32_t decrypt(uint32_t c) {
    uint32_t m = 0;
    // 先赋值最高位
    m |= c & (1U << 31);
    // 从次高位往低位逐位计算
    for (int i = 30; i >= 0; --i) {
        uint32_t c_bit = (c >> i) & 1U;
        uint32_t m_high_bit = (m >> (i + 1)) & 1U;
        m |= (c_bit ^ m_high_bit) ? (1U << i) : 0;
    }
    return m;
}

2. 优化位运算实现（无循环，效率更高） #

和你之前右移6位的解密思路一致，利用位运算的信息扩散特性，适配右移1位的场景调整移位步长即可：

uint32_t decrypt_fast(uint32_t c) {
    uint32_t x = c;
    x ^= x >> 1;
    x ^= x >> 2;
    x ^= x >> 4;
    x ^= x >> 8;
    x ^= x >> 16;
    return x;
}

完整测试代码 #

int main() {
    // 测试0~0xFFFF所有值验证解密正确性
    uint32_t test_max = 0xFFFF;
    for (uint32_t m = 0; m <= test_max; ++m) {
        uint32_t c = m ^ (m >> 1);
        uint32_t decrypted = decrypt_fast(c);
        if (m != decrypted) {
            printf("解密失败：原始值%X，密文%X，解密结果%X\n", m, c, decrypted);
            return 1;
        }
    }
    printf("0~0xFFFF所有值测试通过！\n");
    return 0;
}

补充说明：你之前的测试代码存在一处笔误，输出加密值时打印的是原始值m，正确应该打印计算得到的c。

内容的提问来源于stack exchange，提问作者ravi prakash Mishra