算法精粹:经典计算机科学问题的Java实现
上QQ阅读APP看书,第一时间看更新

1.3 牢不可破的加密方案

一次性密码本(one-time pad)是一种数据加密方式,它将无意义的随机假数据(random dummy data)混入原始数据中,如果无法同时拿到加密结果和假数据,就不能重建原始数据。这本质上是给加密程序配上了密钥对。其中一个密钥是加密结果,另一个密钥则是随机假数据。只有一个密钥是没有用的,必须同时拥有两个密钥才能解密出原始数据。只要运行无误,一次性密码本就是一种无法破解的加密形式。图1.6展示了这一过程。

图1.6 一次性密码本会产生两个可以分开存放的密钥,后续可重新组合以重建原始数据

1.3.1 按顺序获取数据

在此示例中,我们将使用一次性密码本来加密字符串。Java字符串可被视为UTF-16字符序列(UTF-16是一种Unicode字符编码)。每个UTF-16字符是16位的并且可以进一步细分为2个字节(每个字节8位)。可以通过getBytes()方法将String转换为字节数组,也就是字节类型的数组。同样,可以使用String类型自带的构造函数将字节数组转换回String。还需要一个中间形式来存储密钥对,它由两个字节数组组成。以上就是KeyPair类的职责。

代码清单1.14 KeyPair.java

一次性密码本的加密操作中使用的假数据必须符合三个标准,这样最终的结果才不会被破解。这三个标准是,假数据必须与原始数据长度相同、真正随机、完全保密。第一个和第三个标准是常识。如果假数据因为太短而重复,就有可能被看出规律。如果其中一个密钥不完全保密(可能在其他地方重复使用或部分泄露),那么攻击者就能获得一条线索。第二个标准本身就提出了一个问题:能产生真正随机的数据吗?大多数计算机的答案是否定的。

在本例中,我们将使用标准库里Random类中的伪随机数据生成函数nextBytes()。这里的数据不是真正随机的,因为Random类在幕后采用的仍然是伪随机数生成器,但它对我们来说已经足够了。下面就生成一个随机密钥作为假数据使用。

代码清单1.15 UnbreakableEncryption.java

该方法创建了一个给定长度(length)的随机字节数组。最终,这些字节将作为密钥对中的假数据。

1.3.2 加密和解密

如何将假数据与要加密的原始数据相结合?XOR运算可以满足该需求。XOR是一种逻辑位运算(二进制位级别的操作),当其中一个操作数为真时,返回true;当两者都为真或都不为真时,返回false。可能大家都已经猜到了,XOR就是异或(Exclusive OR)。

在Java中,XOR运算符是^。在二进制数位的上下文中,0^1和1^0返回1,而0^0和1^1则返回0。如果使用XOR合并两个数的二进制位,那么把结果数与其中某个操作数重新合并即可生成另一个操作数,这是一个很有用的特性:

上述重要发现构成了一次性密码本加密方案的基础。为了生成结果数据,只要简单地将原始字符串的字节与随机生成且长度相同的字节(由randomKey()生成)进行XOR运算即可。返回的密钥对就是假数据和加密结果,如图1.6所示。

代码清单1.16 UnbreakableEncryption.java续

解密过程只需将encrypt()生成的密钥对重新合并即可。只要在两个密钥的每个二进制位之间再执行一次XOR运算,就可以完成解密任务了。最终的输出结果必须转换回String类型。这可以使用String类的构造函数来实现,该构造函数将字节数组作为其唯一参数。

代码清单1.17 UnbreakableEncryption.java续

如果上述一次性密码本的加密过程真的有效,那么就能够正确地加密和解密Unicode字符串了。

代码清单1.18 UnbreakableEncryption.java续

如果控制台输出One Time Pad!,则证明程序正确。