最近在研究加密算法,发现异或操作在加密算法中用途特别广,也特别好用。下面以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(异或)运算。
- 将明文编码,即转换为二进制。
- 随机生成和明文二进制位数相同的密钥。
- 将明文和密钥的二进制进行XOR操作,生成密文。
解密过程:
依靠的是XOR(异或)操作的自反性,通过明文和密钥异或得到的密文,再通过将密文和密钥再次异或操作得到明文。
虽然一次性密码本非常简单,但是一次性密码本是绝对无法破解的,这个破解并不是指现有的计算能力不够,而是指即使拥有无穷大的计算能力也无法破解。
如果我们拿到了密文并进行暴力破解,也就是将所有顺序的密钥尝试一遍,假设密文长度是32bit,那么我们将得到2的32次方数量的明文。显然我们无法判断哪一个是正确的明文,因为在所有的组合排列中可能生成多个有意义的文字。所以这种解密是无意义的,就像是我知道了原文的长度,然后自己构造这个长度的原文。因此一次性密码本是无法破译的。
当然OTP密码也有缺点,比如密钥太长,无法重复使用等问题。文章来源:https://www.toymoban.com/news/detail-684240.html
码字不易,记得点赞关注哟!文章来源地址https://www.toymoban.com/news/detail-684240.html
到了这里,关于Java中异或操作和OTP算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!