CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

数字密码锁的快速破解

已有 6243 次阅读 2019-11-21 17:45 |个人分类:数字密码锁|系统分类:科研笔记| SAT, 并行计算, 求解密钥

数字密码锁的快速破解

     姜咏江

1          数字密码锁

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

一个十位数字密码锁

密钥:

1

1

0

0

1

0

0

0

0

1

码位置:

X9

X8

X7

X6

X5

X4

X3

X2

X1

X0

 

 

 

0

1









1

0









1

0

1








1

1

1









0


0

0








0

0

0








0

0

1








0

1

0










1



1


1





0



0


0






0

1


1







1

0


0











1

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

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

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

2          二进制限位数及性质

限位数是用数码表示位数确定的数。例如二进制数码的位数就固定为3。数码0不能省略,那么就是3位的限位数有8个。写出来为:00000101001110010111011101叫互为反码。将对应位置数码相反的限位数叫反码数。显然(000111),(001110),,(011100)。

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

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

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

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

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

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

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

3          求解定理

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

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

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

4          数据纠缠态

现在的计算机只是用01表示数据。并行计算需要表示01空格。因而需要引入00表示011表示1,而用0110表示空格(纠缠态)。那么表1就可以用两个N=10位的二进制数表示一个子句。例如,第一个子句用01000000000111111111来表示。前面两个对应位置是0011,后面对应位置只要是01表示即可。

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

5          并行处理器SPU

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

处理器SPU

6          仿量子计算机

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

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

仿量子计算机结构

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

2019/11/20




https://wap.sciencenet.cn/blog-340399-1207039.html

上一篇:量子纠缠超光速运动存在!
下一篇:子句包含消去法多项式时间证明
收藏 IP: 116.243.238.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 02:14

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部