Java中异或操作和OTP算法

最近在研究加密算法，发现异或操作在加密算法中用途特别广，也特别好用。下面以Java语言为例，简单记录一下异或操作，以及在算法中的使用，包括常用的OTP算法。

一，异或操作特征

1， 相同出0，不同出1

换种说法是：无进位进行相加

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

比如
   101011
^ 110101
= 011110
即直接相加不需要关心进位

2， N ^ 0 = N (任何数异或上0都是自己)

可以用无进位相加来进行理解

3，N ^ N = 0 (因为二进制是一样的，相同出0)

4，异或符合 交换律 和 结合律

​ a ^ b = b ^ a 
(a ^ b) ^ c = a ^ (b ^ c)

5，自反性

a ^ b = c，c ^ b = a，即对同一个数字进行两次异或结果将回到最初的状态。

由此，通过明文和密钥异或得到的密文，再通过将密文和相同密钥再次异或操作得到明文。

二，算法应用

1，冒泡算法

冒泡排序中使用异或的方式交换数据的方式

public static void swap(int[] arr, int i, int j) {
    // 使用异或的方式进行交换
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

解析：

arr[i] = "A";

arr[j] = "B";

(1)  arr[i] = arr[i] ^ arr[j];     arr[i] = "A" ^ "B";

(2)  arr[j] = arr[i] ^ arr[j];     arr[j] = "A" ^ "B" ^ "B" ==>  "A" ^ 0  ==> "A"

(3) arr[i] = arr[i] ^ arr[j];      arr[i] = "A" ^ "B" ^ "A"==> "A" ^ "A" ^ "B"  ==> "0" ^ "B" ==> "B"

最后结果  ：   arr[i] = "B";     arr[j] = "A";

2，力扣算法实例1

有一堆数字，里面有一个数字的个数是奇数，其他数字的个数都是偶数，打印出这个奇数

public static void printOddNum1(int[] arr) {
    // 让这个数和所有的数进行异或
    int eor = 0;
    for (int num : arr) {
        eor ^= num;
    }
    // 最后出来就是那个奇数个的数
    System.out.println(eor);
}

解析：

1、无论异或的顺序是什么样的，最后的结果都是一样的

2、当两个相同的数进行异或，结果就是0，当0和一个数进行异或，结果就是这个数

3、所以异或到最后得到的那个数就是那个奇数

3，力扣算法实例2

有一堆数字，里面有两个数字的个数是奇数，其他数字的个数都是偶数，打印出这两个奇数

public static void printOddNum2(int[] arr) {
    // 让这个数和所有的数进行异或
    // 假如 第一个奇数为 a 第二个奇数为 b
    int eor = 0;
    for (int num : arr) {
        eor ^= num;
    }
    // 找到最右边的1的位置 异或不同才出1
    int rightNum = eor & (~eor + 1);
    // 将这个位置为1的数进行异或
    int eorOpen = 0;
    for (int num : arr) {
        // == 0 说明了在rightNum这个位置为 0
        if ((num & rightNum) == 0) {
            eorOpen ^= num;
        }
    }
    // eorOpen 不是 a 就是 b
    // 所以另一个数就是   eorOpen ^ eor
    System.out.println(eorOpen + " " + (eorOpen ^ eor));
}

解析：

1，先进行异或处理，将所有的数进行异或，当两个相同的数进行异或，结果就是0

2，因为0和任何数异或，得到的还是那个数，所以所有数异或之后得到的值就是两个奇数进行异或的值eor

3，因为这两个数字是不相同的，所以得到的值里面有一个数字为1

4，找到这个1的位置，再将这个位置为1的值进行异或，得到的值就是其中的一个此位置为1的数字eorOpen（个数是奇数的数字）

5，再将这个eorOpen值和之前第2步得到值eor进行异或得到的就是另一个奇数个数的数字

三，OTP算法

如果要说古典密码中，哪个最安全，那么一次性密码本一定会有一席之地。从理论层面上来说，它是牢不可破的（无法暴力破解），但在实际操作中却存在一些问题。

一次性密码本英文名为One-time Pad或者OTP，是在1882年被弗兰克·米勒（Frank Miller）发现并沿用至今，它是以随机的密钥（key）组成明文，且只使用一次，需要通信双方事先去沟通一个一次性的，与被加密信息长度相等或者更长的密钥。

加密过程：

就是将明文(待传信息的编码)和一串随机生成的二进制码进行XOR(异或)运算。

1. 将明文编码，即转换为二进制。
2. 随机生成和明文二进制位数相同的密钥。
3. 将明文和密钥的二进制进行XOR操作，生成密文。

解密过程：

依靠的是XOR（异或）操作的自反性，通过明文和密钥异或得到的密文，再通过将密文和密钥再次异或操作得到明文。

虽然一次性密码本非常简单，但是一次性密码本是绝对无法破解的，这个破解并不是指现有的计算能力不够，而是指即使拥有无穷大的计算能力也无法破解。

如果我们拿到了密文并进行暴力破解，也就是将所有顺序的密钥尝试一遍，假设密文长度是32bit，那么我们将得到2的32次方数量的明文。显然我们无法判断哪一个是正确的明文，因为在所有的组合排列中可能生成多个有意义的文字。所以这种解密是无意义的，就像是我知道了原文的长度，然后自己构造这个长度的原文。因此一次性密码本是无法破译的。

当然OTP密码也有缺点，比如密钥太长，无法重复使用等问题。

码字不易，记得点赞关注哟！