科学网 › 标签 › 密钥分发

标签: 密钥分发

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

仿量子计算机设计: accsys 2020-1-13 06:08; 姜咏江邮箱：accsys@126.com 关键词：量子计算机并行计算器 SAT SPU 1 前言理论上量子计算机能够同时计算 2 n 个数据，但结果需要概率处理。实现量子计算机任重而道远。能不能在传统计算机的基础上，设计出可以同时计算同量子计算机一样多的数据？这是可以做到的。本文向读者介绍一个实用的带有并行运算器 SPU(SAT Process Unit) 的计算机。该机虽然结构基本，但完全可以实现传统计算机的各种计算，同时又能够实现并行计算，完成传统计算机不能完成的工作，达到了量子计算机所能达到目标。 2 仿量子计算机结构仿量子计算机的基本结构如图 1 所示。 MU 是存储单位，其包含以程序数据为中心的各种存储环境设备。 PU 是顺序运算器，负责处理传统程序顺序执行的运算。 SPU 是同时并行运算器，负责 2 n 个二进制数据的运算。图 1 仿量子计算机结构 3 指令系统这台仿量子计算机的指令系统如表 1 所示。其中 Da 是累加器， X 是通用寄存器， Dram 是数据存储器， Iram 是程序存储器， Ptr 是通用指针， ccq 是并行运算合成器。本机指令采用 16 位的精简指令系统编码，指令代码占据高 6 位。表 1 仿量子计算机指令系统序号指令编码功能 1 Add 000001 X+da-da 2 Sub 000010 Da-X-da 3 Addc 000011 Da+X+carry-da c-carry 4 Subc 000100 Da-X+carry-da c-carry 5 Out 000101 Da-O 6 Dal n 000110 数 -dal 低 8 位接收数据 7 Dah n 000111 数 -dah 高 8 位接收数据 8 Xda 001000 X-da 9 Dax 001001 Da-X 10 Lda r 001010 Dram-da 11 Str r 001011 Da-dram 12 Jmp r 001100 跳转 13 Jz r 001101 Da=0 跳转 14 Jn r 001110 Da0 跳转 15 Jo r 001111 溢出跳转 16 Call r 010000 调用子程序 17 Ret 010001 返回 18 Lyu r 010010 与 19 Lhuo r 010011 或 20 Lfei r 010100 非 21 Lyh r 010101 异或 22 Inl 010110 输入到 da 低 8 位 23 Inh 010111 输入到 da 高 8 位 24 Jk r 011000 缓冲区空跳转 25 Incp 011001 Ptr+1 26 Decp 011010 Ptr-1 27 Srei 011011 输入到 iram 28 Datp 011100 Da-ptr 29 Jend r 011101 程序输入结束 30 Inp 011110 da 输入到 ptr 指示 iram 33 daq 100001 Ptr-cmar,da-ccq 34 Sat 100010 Ptr-cmar ， ccq- 子句寄存器 clr0 35 Jzp r 100011 ptr 为 0 跳转 36 Xout 100100 X 寄存器内容输出 37 Mzj 100101 将满足解写入 X 寄存器 38 Clrr 100110 Sat 计算初始化 39 End 100000 结束程序输入伪指令 4 并行计算实例为了直观通俗一点说明仿量子计算机的特点，我们以数据密码锁和 SAT 问题来说明。 4.1 数据密码锁通信中直接传送密钥是一个很危险的事情。用下面的数据密码锁可以增强保密性。数据密码锁是将密码隐藏在一组看似杂乱无章的数据中，需要通过特殊的处理方法，才能够将密码找出来。当数据密码锁变量相当多时，短时间根本无法找出隐藏的密码。因此，数据密码锁既可以作为隐蔽的密码传送工具，又可以担当数据锁，确保重要数据的安全。数据密码锁的制作简单，可以根据需要来设置密码的长短。再者本身是一组数据，可以实现明码传输，可以利用现有的数据通信方式，传输适时变动密码，特别是加密数据的密钥传输极为方便。下面表 1 是一个数据密码锁，隐藏着 9 位的密码。用这个密码锁可以控制任何操作通路。数据密码锁工作原理非常简单：当数据密码锁中每行的数据，都至少有一个数码与输入变量的值的对应数码相同时，锁就打开；只要有一行不满足这个条件，锁就不开。此锁隐藏的密码是 101011011 。读者可以试试，输入这个 9 位二进制数给 x 8 ~x 0 ，寻找列变量值与表中数码相同的行，将其消去。如果全部行数据都消去了，那么输入的数就是密码，就可以开锁。表 1 中我们在输入密码行，输入 101011011 ，然后逐行检查那些满足消去条件的行。含有 x 8 =1 的行有 2 、 3 、 4 、 5 、 7 行，将这些行消去。满足第二个数码 0 的行，剩下的行只有 8 、 9 这两行。以此类推，最终可将所有的行数据消去，则表明输入的变量值是这个数据密码锁的密码。表 2 数据密码锁行号 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 1 0 1 1 2 1 0 1 3 1 1 0 4 1 0 1 5 1 1 1 6 0 1 1 7 1 1 0 8 1 0 0 9 0 1 0 10 0 0 0 11 1 1 1 12 0 1 1 13 1 1 1 1 0 0 1 15 1 1 1 16 0 0 1 17 0 1 0 18 0 1 0 19 1 0 0 20 0 1 1 21 1 0 1 22 0 0 0 23 0 0 1 24 0 0 如果输入不是该锁的打开密码，那么就会有的数据行无法消去。例如，令 x 3 =0 ，则如表 3 所示，通过消去的方法，会有剩余行数据不能被消去。这表明输入的变量值不是数据密码锁承载的密码。本例隐藏的密码是唯一的，故而除了 101011011 都不可能将锁打开。假设数据密码锁打开输出“高电位 1 ”，打不开输出“低电位 0 ”，那么就可以用其输出控制任何开关线路。如果传输密钥，则可以直接将数据密码锁送出。接收方可以使用仿量子计算机破解软件，短时间找到隐藏其中的密钥。表 3 输入其它变量值测试输入密码： 1 0 1 0 1 0 0 1 1 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 x 0 0 1 1 数 1 0 1 据 1 1 0 密 1 0 1 码 1 1 1 锁 0 1 1 1 1 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 0 1 0 0 1 0 1 0 0 0 1 1 1 0 1 0 0 0 0 0 1 0 0 破解数据密码锁中的密钥，一般化是一个指数时间复杂度的过程。需要用量子计算机或仿量子计算机，才能在短时间完成这项工作。目前，庞大而复杂的量子计算机距离应用尚远，而仿量子计算机业已成熟。破解数据密码锁中隐藏的密钥，不成问题。 4.2 逻辑电路可靠性问题并行计算比较典型的例子是逻辑电路可靠性检测问题（ SAT 问题）。由于数字电路检测点很多，需要通过 Tsyetin 变换转化成合取范式，然后求出合取范式的满足解。用传统计算机求满足解，当合取范式中的变量较多时，机器运行时间不可忍受。如果用同时可以计算 2 n 个数据的运算器 SPU ，才能在短时间内求出合取范式的满足解。 4.2.1 Tsyetin 变换下面给出 Tsyetin 变换公式及二进制限位数表示方法。逻辑门电路可以变换成合取范式，这些变换公式如表 4 所示。当这些合取范式值为 1 时，就说明对应的门电路可靠。表 4 Tsyetin 变换逻辑符号逻辑表达式合取范式 C=AB (A’+B’+C)(A+C’)(B+C’) C=(AB)’ (A’+B’+C’)(A+C)(B+C) C=A+B (A+B+C’)(A’+C)(B’+C) C=(A+B)’ (A+B+C)(A’+C’)(B’+C’) C=A’ (A’+C’)(A+C) C=A⊕B (A’+B’+C’)(A+B+C’)(A+B’+C)(A’+B+C) 图 2 是设置了检测点的逻辑电路，用 Tsyetin 变换可以转化成合取范式 CNF 。图 2 逻辑电路检测点以下规定 x ’ 是 x 的非，加号是逻辑或运算符，与运算符省略。图 1 中逻辑电路检测点经过 Tsyetin 变换得到的合取范式为： CNF=( x 1 + x 4 )( x 1 ’+ x 4 ’)( x 4 + x 5 ’)( x 2 + x 5 ’)( x 2 ’+ x 5 + x 4 ’)( x 2 + x 6 )( x 7 ’+ x 1 )( x 6 + x 7 ’)( x 1 ’+ x 6 ’+ x 7 )( x 2 + x 8 )( x 2 ’+ x 8 ’)( x 8 + x 9 ’)( x 3 + x 9 ’)( x 3 ’+ x 8 ’+ x 9 )( x 5 ’+ x 10 )( x 7 ’+ x 10 )( x 5 + x 7 + x 10 ’) ( x 9 ’+ x 11 )( x 10 ’+ x 11 )( x 9 + x 10 + x 11 ’) x 11 (1) 可以用 0 表示变量否定， 1 表示变量肯定。这个合取范式的表示如表 5 所示。其中每一行叫子句，变量相同的子句形成子句块。表 5 二进制表示的 CNF 0 1 1 1 1 0 0 0 0 1 1 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 0 1 4.2.2 子句消去法从公式（ 1 ）可以看出，只要子句有变量值能够和表 5 中对应数码相同，那么这个子句的逻辑值就是 1 ，这样就可以在求 CNF=1 的问题中，将这个子句消去。如果找到一组变量值，对每个子句都会至少有一个数码与它的变量值相同，那么这组值就是这个 CNF=1 的满足解。满足解的实际意义在于，当逻辑电路输入端输入那些已知值时，其余各检测节点的值刚好也是满足解的变量值，那么电路的逻辑结果是真，是可靠的，反之电路就不可靠。 5 并行计算理论基础利用子句消去法，如果子句的一个数码与其变量的取值相同，就可以将这个子句消去，再求剩余部分的满足解。如果有 n 元变量的 CNF 要消去全部子句，就要设定 n 个变量的值。因为逻辑变量有 2 个值，所以最坏要进行的是 2 n 次选择数。这 2 n 个 n 位二进制数叫可能解空间。本文介绍的是子句包含消去法。是利用可能解空间中的可能解，来求 CNF 全部满足解。这要利用子句块的性质。能够将子句块中所有子句消去的子句块变量值叫子句块的解。对应数码互反的两个子句叫互反子句。显然，合取范式的某个子句块无解，那么这个合取范式一定无满足解。子句块有一些特殊的性质是子句包含消去法的基石。性质 1. 子句块中不是互反子句，至少有一个对应位置的数码相同。性质 2. 反子句不在子句块中，那么这个子句是该子句块的解。性质 3. 互反子句都不在所属子句块，它们都是该子句块的解。性质 4. 互反子句都在子句块中，它们都不是子句块的解。定理：将子句和包含子句那些可能解都消去，剩余的可能解的反码是原合取范式的满足解。证明：因为剩余的可能解都由不在合取范式中的那些子句构成，其中或者是子句块中子句的反子句，或者都不在子句块中。根据性质 2 、 3 ，则取反之后的可能解，一定由在子句块的子句或都不在子句块中的子句构成，则取反之后的可能解一定能将全部子句消去。上面的定理就是子句包含消去法。 6 子句包含消去法实例在表 5 解空间中，将包含子句的那些可能解消去，剩余的那些可能解如表 6 所示。表 6 解空间剩余的可能解 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 X 9 x 10 x 11 0 1 0 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 对剩余的可能解取其反码数，就得到了此问题的全部满足解（见表 7 ）。表 7 全部满足解 x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 1 0 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 0 1 0 1 1 0 1 将表 7 得到的这 5 个满足解带到表 5 进行验证，都可以得到 CNF=1 。 7 并行计算程序仿量子计算机的并行计算程序如表 8 所示。表 8 并行计算 SAT 程序标号汇编指令解释 start Dah 0 Dal 0 从 0 起，子句数量减 1 Datp 0000-ptr Loop0 Jk Loop0 缓冲区空跳转 Inl 输入低 8 位 Loop1 Jk loop1 缓冲区空跳转 Inh 输入高 8 位 Jend exit0 结束输入跳转 daq 送入 cnf 存储器 Incp Ptr+1 Jmp Loop0 读下一个字 Exit0 Clrr 清理反满足解寄存器 Loop2 Sat 子句并行处理求解 Jzp exit1 子句结束跳转（放在 sat 后） decp Jmp loop2 Exit1 Mzj 保存第一个满足解 Xout 输出第一个满足解 Clrr 清理反满足解寄存器 Ret End 结束程序输入伪指令在设计的仿量子计算机上，这个程序常驻内存，使用时用 call 指令调用就可以计算。输入 4430 4400 8000 （先送低 8 位后送高 8 位），就可以调用这个并行计算 SAT 问题的程序，然后输入并行处理数据，就能够得到 CNF=1 的满足解。另外在 320 的位置，将上面例题数据放入内存了，可以输入 4420 4400 8000 ，直接得到结果。不过数据要转换成纠缠态表示。 8 纠缠态数据结构表 9 中有许多空位置，要将空位置表达出来，才可以进行并行计算。用 01 或 10 来表示空格，用 00 表示 0 ， 11 表示 1 。这样表 9 左面的 8 列，就可以写成右面一列的并行处理数据。方法是一行数据用两行表示，上下对位表示 0 、 1 和空格。并行处理器 SPU 处理的是并行数据。表 9 纠缠态数据表示 1 1 1 1 0 1 1 1 X 7 X 6 X 5 X 4 X 3 X 2 X 1 X 0 （并行数据） 1 0 0 80 9F 0 1 0 40 5F 1 0 1 A0 BF 1 1 0 C0 DF 0 1 0 20 6F 0 1 1 30 7F 0 0 1 04 CF 1 0 0 20 F3 0 0 1 04 D7 1 1 1 2C FF 1 1 0 06 FE 1 0 1 05 FD 0 1 0 02 FA 1 0 10 FE 1 01 FF 9 结束语量子计算机有诸多的问题尚未解决，因而成为实用的计算机还要假以时日。量子计算的要点是同时计算 2 n 个数据，这样就将指数时间复杂度的计算转变成了多项式时间复杂度计算。仿量子计算机的同时处理器 SPU ，也可以同时计算 2 n 个数据，并且添加到传统的计算机之后，能使传统计算机成为实用的，既可以执行顺序计算又可以进行并行计算的完备计算机。计算机科学界已经证，明诸多的计算机难题都可以在多项式时间转化为 SAT 问题求解。仿量子计算机解决了 SAT 问题的计算，其余那些难题都将会迎刃而解。 2019 年 12 月 22 日星期日; 个人分类: 仿量子计算机|3407 次阅读|0 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 密钥分发

相关帖子

相关日志

关闭安全验证