乐趣区

关于密码学:异或的4种堪称神奇的运用场景

原创:扣钉日记(微信公众号 ID:codelogs),欢送分享,转载请保留出处。

简介

家喻户晓,编程语言个别都内置了 3 种位运算符&(AND)|(OR)~(NOT),用来实现位运算,但其实还有一种十分罕用的位运算,即异或^(XOR),数学中罕用⊕示意。

异或的运算逻辑如下:
1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

简略来说,异或的个性是,两个值雷同,后果为 0,不同则后果为 1,所以才叫 异或 嘛,两个值相异再或起来,不就是 1 嘛😂

因为异或非凡的运算个性,使其能够实现一些神奇的操作,如下:

  1. 实现加减法
  2. 加解密
  3. 密钥替换
  4. 数据备份

那就来一起看看吧!

运算定律

  1. 任何值与本身异或,后果为 0

    x ^ x = 0
  2. 任何值与 0 异或,后果为其本身

    x ^ 0 = x
  3. 交换律

    x ^ y ^ z = x ^ z ^ y
  4. 结合律

    x ^ y ^ z = x ^ (y ^ z)

    异或的运算定律比较简单,就不写数学证实了,感兴趣可到网上搜寻。

实现加减法

XOR 的第一种使用场景就是实现加减法,在咱们上小学时,应该都学过 进位加法 退位减法 来做加减运算,咱们来温习一下吧。

  • 进位加法:
    当某一位上两数之和大于 10 时,须要进位,即高位上要多加一个 1。
  • 退位减法:
    当某一位上两数相减不够时,须要退位,即从高位上借 (减) 一个 1,来当作 10 用。

异或其实与这个相似,不过它不会产生进位与退位,如下:

  1. 如二进制加法 01 + 01 = 10,而异或运算是01 ^ 01 = 00,它其实做了加法,但高位不进位,所以异或又称 不进位加法
  2. 如二进制减法 10 - 01 = 01,而异或运算是10 ^ 01 = 11,也能够看做个位 0 向高位借了一个 1 当 2 来用,但高位不减 1,所以异或也能够称为 不退位减法

利用异或的这个个性,只有再解决一下进位和退位问题,就能够实现加减法了,如下是 java 代码实现:

public static int intPlus(int a, int b){while (b != 0){// 加法(未思考进位)
        int sum = a ^ b;
        // 进位值,二进制中 1 + 1 的场景才会进位,a & b 只有两个都为 1,后果才是 1,左移一位,就是进位值了
        int addition = (a & b) << 1;

        // 赋值,下次循环将进位加到 a 外面来,直到进位等于 0
        a = sum;
        b = addition;
    }
    return a;
}
public static int intSubtract(int a, int b){while (b != 0){// 减法(未思考退位)
        int sum = a ^ b;
        // 退位值,二进制中 0 - 1 的场景才会退位,~a & b 只有 a =0,b=1,后果才是 1,左移一位,就是退位值了
        int abdication = (~a & b) << 1;

        // 赋值,下次循环将退位再从 a 中减掉,直到退位等于 0
        a = sum;
        b = abdication;
    }
    return a;
}

这也是为什么 CPU 外面都是做位运算的逻辑门电路,却能实现数值计算😱

加解密

应用 XOR 能够实现简略的加解密,如果明文为 plain,密钥为 key,密文为 secret,则:

// 加密
secret = plain ^ key
// 解密
plain = secret ^ key

为什么肯定能解密呢,如下:

secret ^ key 
    = (plain ^ key) ^ key     // 代入加密表达式
    = plain ^ (key ^ key)     // 代入结合律
    = plain ^ 0               // 任何值与本身异或等于 0
    = plain                   // 任何值与 0 异或等于本身

java 实现如下:

public static byte[] xorEncrypt(byte[] plain, byte[] key){byte[] secret = new byte[plain.length];
    for(int i = 0; i < plain.length; i++){secret[i] = (byte) (plain[i] ^ key[i % key.length]);
    }
    return secret;
}

public static byte[] xorDecrypt(byte[] secret, byte[] key){return xorEncrypt(secret, key);
}

public static void main(String[] args) {byte[] plain = "hello xor".getBytes(StandardCharsets.UTF_8);
    byte[] key = "1234".getBytes(StandardCharsets.UTF_8);
    byte[] secret = xorEncrypt(plain, key);
    byte[] plain2 = xorDecrypt(secret, key);
    // 输入 plain:aGVsbG8geG9y,secret:WVdfWF4SS1tD, plain2:aGVsbG8geG9y
    System.out.printf("plain:%s,secret:%s, plain2:%s", Base64.encode(plain), Base64.encode(secret),
            Base64.encode(plain2));
}

密钥替换

密钥替换就是通信单方须要将加密密钥发送给对方,但不让两头的信道监听者晓得密钥是什么,而利用 XOR 就能够实现一种最简略的密钥替换计划,如下:

  1. 客户端生成一个随机密钥 p,而后再应用本人的密钥 k1 对其 XOR 加密,将加密后的 s1 发送给服务端,即 s1 = p ^ k1。
  2. 服务端再应用本人的密钥 k2 对 s1 做 XOR 加密,将加密后的 s2 回复给客户端,即 s2 = s1 ^ k2。
  3. 客户端再应用本人的密钥 k1 对 s2 做 XOR 解密,将解密后的 s3 回复给服务端,即 s3 = s2 ^ k1。
  4. 服务端再应用本人的密钥 k2 对 s3 做 XOR 解密,即 s4 = s3 ^ k2,而按 XOR 的性质,s4 会等于 p,即客户端顺利将 p 发送给了服务端,且两头通信数据都是加密的。

    整个过程能够看做先是单方都在密文中做了一次加密,而后单方又逐渐解开。

证实其正确性也很简略,只须要将式子代入一下即可,如下:

s4 = s3 ^ k2
   = (s2 ^ k1) ^ k2
   = ((s1 ^ k2) ^ k1) ^ k2
   = (((p ^ k1) ^ k2) ^ k1) ^ k2
   = p ^ k1 ^ k2 ^ k1 ^ k2         // 利用结合律
   = p ^ (k1 ^ k2) ^ (k1 ^ k2)     // 再利用结合律,把 k1 ^ k2 看成整体,就是加密之后再解密了
   = p

   // 也能够这样证实
   = p ^ k1 ^ k2 ^ k1 ^ k2         
   = p ^ (k1 ^ k1) ^ (k2 ^ k2)     // 利用交换律
   = p ^ 0 ^ 0                     // 利用本身与本身异或为 0
   = p                             // 利用任何值与 0 异或为其本身

数据备份

应用 XOR 也能够很容易实现多个数据的互备,如下:
如果有数据 a、b、c,则z = a ^ b ^ c,而后把数据 z 备份下来。

  • 当 a 失落时,可应用 z ^ b ^ c 来复原。
  • 当 b 失落时,可应用 z ^ a ^ c 来复原。
  • 当 c 失落时,可应用 z ^ a ^ b 来复原。

这真是太神奇了,备份了一份数据 z 后,失落了任何一份数据,都能够通过数据 z 与其它数据一起复原回来😎,而磁盘阵列技术 raid5 的数据备份原理,就是用的这个个性。

实现异或

因为在布尔代数中,其实只须要与、或、非运算就能够实现所有其它运算,所以异或其实也是能够通过与、或、非实现的,最直观的实现形式如下:

a ^ b = (~a & b) | (a & ~b)  

ok,异或的应用场景就介绍到这了,还有没有其它神奇的使用场景呢?如果有,可留言告知下😀

往期内容

密码学入门
接口偶然超时,竟又是 JVM 进展的锅!
耗时几个月,终于找到了 JVM 进展十几秒的起因
mysql 的 timestamp 会存在时区问题?
真正了解可反复读事务隔离级别
字符编码解惑

退出移动版