数字密码锁的快速破解

     姜咏江

1          数字密码锁

表1黄色底纹部分是一个10位的二进制密码锁。表头X0至X9标明数码的位置。每一行数据叫子句。当设定一组变量值时，子句中至少有一个数码与对应设定的变量值相同，那么这个子句不阻止开锁，否则阻止开锁。显然，当所有的子句都不阻止开锁，那么密码锁就被打开了。表1密钥行给出的一组变量值就是这个密码锁的一个密钥。

表 1  一个十位数字密码锁

由于子句复杂，数量众多，当变量数N很大时（例如N=256），用目前最快的计算机要找到密钥，耗费的时间都将无法忍受。除非能够设计出一次能够并行计算2^N个数据的处理器。

研究过P/NP问题的读者，容易看出，所谓密码锁就是SAT问题的二进制表示，密钥就是SAT的一个满足解。目前的计算机求出SAT的满足解，完备算法有DPLL方法和暴力破解法。它们都是指数时间复杂度的算法，一般性求出密钥很慢，满足不了实际需要。据说量子计算机可以一次并行计算2^N个数据，因而可以快速求出SAT的满足解。

现实中，如果有一次对比，就能够找出2^N个N位数中那些包含一个子句的计算机，那么密码锁也可以象量子计算机一样快得到破解。

2          二进制限位数及性质

限位数是用数码表示位数确定的数。例如二进制数码的位数就固定为3。数码0不能省略，那么就是3位的限位数有8个。写出来为：000、001、010、011、100、101、110、111。0和1叫互为反码。将对应位置数码相反的限位数叫反码数。显然（000、111），（001、110），…，（011、100）。

子句的反码数叫其反子句。容易证明，一个子句的反子句唯一，非反子句至少有一位数码相同。

表1中具有相同变量的子句叫子句块。子句块对应变量一组值，使其没有子句阻止开锁，这组值叫子句块的解。由表1可见，若子句块无解，该密码锁没有密钥。

用下面的子句块性质，容易找到子句块的解。

性质：子句块中子句的反子句不在，则这个子句是子句块的解。

证明：一个子句的反子句是唯一的。若一个子句的反子句不在这个子句块中，其余子句必然与这个子句，至少有一个对应位置数码与该子句数码相同，故这个子句就是该子句块的解。

推论：属于一个子句块的一对互反子句，都不在所属子句块中，它们都是这个子句块的解。

这个性质可由性质1直接推出。

3          求解定理

数字密码锁求出密钥，可以用重要的求解定理。在N位二进制数中，一个子句必然包含在一些数中。在2^N个N位数中，找到包含一个子句的那些数，并消去的方法叫子句包含消去法。全部N位数集叫解空间。每个N位数叫可能解。

定理：将子句包含在其中的那些可能解消去，解空间中剩余可能解的反码数都是密码锁的密钥。

证明：因为不在密码锁中的子句，一定都在剩余可能解中，因而剩余的可能解一定包含不在任何子句块中的那些子句。依据性质和推论，剩余可能解的反码数一定包含每个子句块的解，因而剩余可能解的反码数是密钥。定理成立。

4          数据纠缠态

现在的计算机只是用0和1表示数据。并行计算需要表示0、1和空格。因而需要引入00表示0，11表示1，而用01或10表示空格（纠缠态）。那么表1就可以用两个N=10位的二进制数表示一个子句。例如，第一个子句用0100000000和0111111111来表示。前面两个对应位置是00和11，后面对应位置只要是01表示即可。

用0和1的纠缠态表示能够表达任何离散数据，从而将离散数据包含问题，转化成了连续二进制数的运算问题，进而可以用逻辑电路设计出并行运算处理器。

5          并行处理器SPU

设定离散数据纠缠态表示，依据求解定理，可以实现对SAT问题求满足解。SAT问题并行处理器SAT Process Unit(SPU)的逻辑结构如图1所示。如果N给变量的子句有m个，可将子句被当成纠缠态，那逐一送到子句寄存器，通过一次能够确定2^N个N位数中是否包含这个子句的SAT运算器SPU，消去包含子句的可能解，再通过取反就能够得到全部密钥。

图 1  处理器SPU

6          仿量子计算机

据说N位的量子计算机一次能够处理2^N个数据。用逻辑电路也能设计一次处理2^N个数据的计算机，因而把它叫做仿量子计算机。量子计算机现在并不成熟，何时能够引入应用，恐怕还不好说。仿量子计算机也一次能够处理2^N个数据，速度之快当然可以与量子计算机媲美。

仿量子计算机（逻辑结构见图2）是在目前的计算机上加增SPU处理器，并且依据需要增加了相应的指令系统。该机优点不需要重新建立一套编程应用方式。仿量子计算机有快速和易用的优点。

图 2  仿量子计算机结构

图2是以存储设备为中心的计算机设计逻辑，PU是普通处理器，SPU是并行处理器，MU是存储设备。

2019/11/20