科学网 › 标签 › RSA

标签: RSA

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

没有相关内容

相关日志

RSA流密码互补加密: sjdkx 2019-9-17 15:21; 　　RSA加密具有非对称性可以完成诸如数字签名及验签之类的事情，这是对称密码所不能完成的，但是能加密的内容很少速度较慢，且密钥冗长不便于使用。而流密码加密是一种对称加密简单并且安全性很高，且速度很快能加密的信息量很大。如果将两者结合起来就能做出一种能完成数字认证又能快速加密大量信息的软件。　　实际上只要简单的让两者都参与加密即可，RSA的参与使加密具有了不对称性，流密码的参与形成了坚实的加密，这就像保险箱加了两把锁。RSA的参与的意义就是使加密具有了不对称性，并不需要其对加密的安全性做出贡献，所以可以尽可能的简单，用小质数算出的公钥私钥完成加密即可，程序使用固定的公钥私钥和模数，并且不怕这些数据被窃密者利用，原因是毫无用处，保险箱内是秘密，RSA这把锁打开了，流密码那道锁打不开信息仍然是安全的。　　这里公钥私钥是完全对称的称为 A钥和 B钥，对本地文件你可以用 A钥加密 B钥解密，也可以用 B钥加密 A钥解密。由于这种多选择性，想要实施穷举攻击就困难了。　　程序能加密很大的文件大约 1M/s。; 个人分类: 密码学相关|2316 次阅读|0 个评论

RSA高速加密: sjdkx 2019-8-24 09:39; 　　RSA用于信息加密其性能不敢恭维，可取之处也就是用两个密钥完成加密解密而已，据说这样可以相互印证。这里的加密程序即利用了RSA也利用对称密码的序列密码进行双重的加密，这相当于加了两把锁，从安全的角度看，你只有将锁全部打开才可能解密成功，尽管其中一只锁质量是很差的，这和木桶效应正好相反，RSA如果用小质数计算公钥私钥速度也是很快的，我们利用它们来加密让程序具有公钥加密私钥解密或私钥加密公钥解密的性质，而加密的安全性由序列密码去负责，这样我们就具有了高速和安全的RSA加密程序。　　这里的RSA不是利用两个大质数计算公钥私钥，而是利用大量的小质数计算出的大量的公钥和私钥，所以密钥文件中充斥着大量的公钥和私钥信息，并且公钥或私钥文件都不是一次性使用的你可以使用多次，每次的计算位置（起点）都是不一样的，这些位置是由用户密码根据不同情况计算出来的，破解难度可想而知。　　以往的RSA加密的信息少的可怜，只能处理百多个字节，而这里的例子就可以处理十几M字节的数据，想要处理大文件只要将密钥文件做大即可，而且速度是很快的，在我这主频1.06G的老机子上，处理10M的文件也只需七八秒。　　本加密程序是试验性质的一切从简，采用的是原地加密的方式，明文加密后并不改变其名或扩展名所以使用者必须自己心中有数。　　密钥全部是二进制文件形式，不像现在流行的公钥私钥文件都是base64编码，这和文件的体量有关，那些以base64编码存在的密钥文件不知这样做目的何在? 为了让用户看得见？让用户欣赏还是检查？莫名其妙。　　这里的公钥文件和私钥文件地位是同等的，叫做 A钥和 B钥文件更为贴切，暂且以扩展名 .A钥和扩展名 .B钥区分之。　　压缩包里有三个文件一个是加密文件，另两个是密钥文件。加密文件界面有使用说明。　　欢迎多提意见。破解就别想了，单纯的序列密码加密程序都破解不了，双重加密就别做梦了。附件：加密软件。在这里也可下载： RSA高速加密-『密码算法』-看雪安全论坛 https://bbs.pediy.com/thread-254110.htm; 个人分类: 密码学相关|2768 次阅读|0 个评论

RSA小质数加密: sjdkx 2019-7-30 14:39; 　　根据RSA的特点尝试利用小质数算出的公钥私钥及模数来快速的加密文件，首先建立资源库里面装载着众多的适用于两个字节范围内的数据，资源库的三项内容公钥数据私钥数据公共模数数据，每组占6个的字节，根据这些数据和用户密码和密钥长度要求建立公钥文件和私钥文件，密钥文件没项数据占四个字节，公钥或私钥占两个，公共模数占两个字节。设置用户密码是将来有必要时能复现出公钥和私钥文件，然后是加密程序，完全是利用RSA的公式运作。安全性问题：　　这不同于大质数加密只用一对密钥，这里利用成千上万的密钥对，破解起来也并非易事，欢迎大家来破解。　　编制的简陋小程序，一个加密程序，一个公钥文件一个私钥文件，可以处理50k一下的文件。为了方便分析都没有加密处理。加密速度是可以和AES媲美的，缺陷是拖累较多。如果真是容易破解那要考虑双加密的问题了，即加密软件不只是利用公钥私钥文件来加密，另外还有口令保护，实际一直都是如此吧。　　RSA小质数加密，具有一般非对称加密的特点，数表操作速度比对称加密还快。希望大家找出其致命缺陷攻击它，使其日臻完善。; 个人分类: 密码学相关|2257 次阅读|0 个评论

墨子沙龙有关量子通信话题的问与答（二）: 热度 4 lhy8848 2018-12-29 12:03; 本期问题速览 5. 量子通信与量子密钥分发是什么关系？ 6. 怎样理解量子密钥分发的“无条件安全性”？ 7. 量通宣传公钥加密方式 RSA 在量子计算机时代将能够被轻易破解，所以量子密钥是一个需要迫切发展的技术以防患于未然，如何看待这样的观点？ 8. 虽然面对很多批评，但是量通认为只要在密钥分发环节上，量子手段优于传统密钥分发手段，就值得发展这个技术方向，如何看待这个观点？第二期 5. 问：量子通信与量子密钥分发是什么关系？答：按照一般人理解的通信，如果仅仅从量子通信这个字面上进行联想，量子通信究竟做了什么似乎呼之欲出。但非常可惜，那是错得离谱的错觉。相当长一段时间，量通的宣传特意将量子通信（ QC ）与量子密钥分发（ QKD ）的界限模糊化，让几乎所有人甚至包括信息安全领域的专家也产生错觉，直到科学界反对的声音出现。现在越来越多的人开始认识到 , 曾经发生误解的量子通信其实只是量子密钥分发，只是广义的量子通信下面的一个分支而已，量通其实并不能采用量子的方式对信息进行加密，真正的加密算法仍然是传统的密钥加密，所不同的不过是采用了量子方式传送过来的量子密钥（ QK ）而已。讲真的话，量通如果单纯采用量子的方式，连一个 bit 的有用信息都发送不出去。只看格林兰岛的名字就误以为遍地鸟语花香，只看冰岛的名字就以为四处冰天雪地，这种望文生义的错觉，有时候就会被有心人充分利用起来。当人们错把 QKD 当做 QC 的时候，也就误把冯京当马凉，以为量通干的活是采用特殊的量子加密的方式，将信息以最高安全等级发送出去，利用人们对于量子的一知半解，对量通的安全承诺产生无条件的信任感，甚至觉得这个东西用在国防上都是镇国之宝。但凡多花点时间看看普通人对于量通文宣的高调点赞，就知道他们所臆想的量通与实际的量通相差有多遥远。笔者请教过一些知名的量子专家，即使他们知道量通其实就是 QKD ，但是也一直误以为国内量通实现的 QKD 采用的是量子纠缠模式（实际采用的是偏振模式），误解如此之深，连专家也难免入道，更不用提毫无分辨能力的普通人了，这就是量通要达到的目标，也确实达到了这个目标。按照墨子文对量子通信的定义，其中包括量子密钥分发和量子隐性传态两个领域。这个定义是否权威，恐怕还有很多争议，通常比较有把握的看法是量子通信涵盖的范围包含不仅限于上面两个分支，还在不断扩展中。 6. 问：怎样理解量子密钥分发的“无条件安全性”？答：现代密码学里面，信息安全采用的加密的技术手段通常是密钥的方式，当然除此之外还有其它形式，比如我们网络安全经常采用的物理隔离，也是信息安全常用的方式。对于密钥形式的加密解密手段，很早就由香农证明了异或加密体制下，当满足一次一密、明文密钥等长、密钥充分随机三个充要条件时，密文是不可破解的，因为破解的结果是非确定的、发散的。从这个意义上来说，人类已经证明了一个“完美”的加密机制。但是密码学里面不存在“无条件安全性”的概念，那只是一个情怀，根本不可能是一个严谨的科学定义，也更谈不上有什么证明，香农的算法也需要至少满足三个充要条件，缺一不可。量通的“无条件安全性”是以算力为基本思想，是与密钥加密的密文需要强力破解相比较而言的，他们认为只要保证最强大的算力也无法破解密文就是无条件安全。在参考中，潘院士对这种“无条件安全”做了解读，他认为以复杂性算法为基础的经典密码，都是理论上可以被破解的。遗憾的是，这种说法是完全错误的，香农的证明已经很好地反驳了这个理念。令人不解的是，同样是量通，也往往举出香农的证明来宣传量通的无条件安全性是得到了证明的。一方面贬低传统加密算法都是可破解的，一方面又说存在不可破解的加密体制，我无法调和量通这两种截然相反说法之间的矛盾。另外 2012 年图灵奖获得者莎菲 . 戈德瓦瑟也在视频中提出来一些算力不可破解的加密例子。我希望量通专家虚心听取一下这方面专家的不同意见，在这个领域里面，量通专家一点也不专业，不要提出一些自己都不知所云的新概念，那些东西禁不起任何专业知识的审视，只是凸显自己专业知识的贫乏。将信息安全仅仅局限在算力破解的范畴内是非常狭隘的，依照这样的思想，只要提供足够的算力，比如量子计算机，通过遍历密钥空间就能够破解所有密文，传统密码体系就会崩溃，这是对密码学的严重误解，不具有科学的严谨性，不可能获得任何信息安全领域专家的认同。很简单，如果明文就是一串无语义关系的数字或者字符串，或者破解结果出现发散的情况，强力破解根本不可能奏效。令人感到讽刺的是，量通采用的 BB84 协议属于物理操作序列，发送的只是密钥，真正进行加密解密操作的仍然是传统的加密算法，密钥分发过程只是物理操作，根本不存在密码学意义的算法，破解量通的方法也与算力无关。所以完全不能理解量通强调算力，究竟跟它有什么实质关系？要说有关系，也是算力与传统加密算法的关系。事实上，破解量通的方法根本不是从破解普通光纤上的密文着手，而是直接面对量子通道里面发送的密码明文，这完全不需要基于算力，而是基于物理过程序列。量通的“无条件安全”根本就是个噱头，将这个看起来美妙无比的光环套在自己的头上，却从来没有给出任何一个有效的证明。有时为了强调这个主张的权威性，明明干的是量子的活，却拿出传统密钥的香农定理为自己的结论背书，将两件风马牛不相及的事情硬捏合在一起，要多拧巴就有多拧巴，需要多强大的内心才能不被这种显然的错位所扭曲，严谨的信息安全专家是完全无法理解这些的。其实可以这样反过来想，对于普通人来说，算力跟信息安全程度直觉上的相关性还是很强的，如果量通不断强调算力，就会让人联想到量通可能是做加密解密的工作，只有发生这样的误解，各种文宣的操作才变得更有成效。可以看出来，量通把文宣也当作一个系统工程来做了，可惜能够清醒识别到这些的人真的太少了。 7. 问：量通宣传公钥加密方式 RSA 在量子计算机时代将能够被轻易破解，所以量子密钥是一个需要迫切发展的技术以防患于未然，如何看待这样的观点？答：量通 QKD 协议的局限性限定了密钥分发只能在已知的用户之间进行操作，要求发送和接收两端同时拥有专用的量子通道和发送接收设备， QKD 是纯粹点到点之间的协议，并且还不允许中间有任何中继器、交换机、路由器，现实中并不可能具有这样条件的用户。如果放宽尺度，就算允许量通在信道内接入所谓可信中继器（其中引入的巨大安全风险这里不展开谈），那么也仍然是属于确定用户之间的密钥分发。暂且不谈 RSA 安全性的真实性，退一步讲，假如 RSA 面临安全性风险，需要其它技术手段来替代，那么既然量通渲染他们是拯救这个密码危机的救世主，一定能够挺身而出，承担 RSA 原来所起的作用，可惜这种幻想是错误的。用户之间的密钥分发工作究竟采用何种加密体制取决于用户的类型。对于确定性的用户之间，他们之间会定期发送密钥，典型的就是一般金融机构的 KDC 之间密钥分发。这种确定性用户之间的密钥分发工作既可以采用非对称加密方式，也可以采用对称加密方式，没有什么特别的限制，当然如果量通一定要说 RSA 可能存在不安全的因素，那么 KDC 之间采用对称加密方式就是了，量通再怎么烘托密码危机的氛围，也不敢说对称加密也存在危机，因为第一，香农定理已经证明对称加密是可以做到绝对不可破解的；第二，量通的普通信道上就是采用对称加密方式来加密信息的，自己的刀绝对不能削了自己的把。 RSA 主要用于非确定性用户之间密钥分发工作。当两个陌生人之间需要进行保密通讯的时候，首先在一个用户端生成对称密钥，并通过公钥系统加密后，发送给通信的对方，此后，两用户之间就可以通过对称密钥进行保密通讯。这种应用情景最典型的就是我们日常的互联网和移动应用。非确定性用户之间只能采用公钥体制进行密钥分发，你不可能期待任意两个陌生人之间都能通过量子通信线缆直连，中间还不能有路由器和分组交换机，这样的组网方式连一点存在的可能都没有。这类用户之间的保密通讯，量通这盘大菜根本端不上桌，所以让人感到他们如此大声宣讲 RSA 不安全，岂不是显得太滑稽了， You can you up 啊 ! 况且，公钥体制又不是 RSA 唱独角戏，候选的角色太多了，今天 RSA 不好用，明天全世界就能重新下载个插件换个新方法，你让量通试试能不能一夜之间换个玩法？用硬件的方法来解决软件能够轻易解决的问题，这在 IT 界、在密码学领域都是愚不可及的想法，违背最基本的科学技术发展的方向。二十几年前计算机里面还有硬件加密卡和汉卡来支持信息加密和汉字输入输出，现在还有谁的机器里面有这些古董？ RSA 的加密原理很简单，就像哥德巴赫猜想一样貌似谁都能解决这个问题。量通显然轻看了解决这个问题的困难程度，他们寄希望于量子计算机的突破。但是他们其实内心里比谁都知道，迄今为止，虽然量子学界闹哄哄今天说做出来几十个量子比特，明天说马上就要实现量子霸权，可是他们从来没有主动说出来，他们说的那些个量子比特根本就不是量子计算理论里面的量子比特，量子计算机的量子比特现在都称之为逻辑量子比特，而所有量子计算机的理论包括量子霸权所指出的 50 个量子比特都是这个逻辑意义上的量子比特。现在世界上最先进的实验室里，连一个逻辑量子比特都没有做出来，更不要谈十几年后就会做出来什么量子计算机了，那个目标现在离我们远得连影子都看不到，搞不清楚量通专家为什么对量子计算机的问世这么自信，是不是唯有此才能制造出来黑云压顶的危机感？量通未雨绸缪的提前量打得未免太多了，不知道等到量子计算机问世的时候，那些量通设备是否已经锈成了渣，成为博物馆的出土文物？量通渲染 RSA 危机，在早期是因为他们对密码学知识的理解实在太皮毛，所以没有意识到， RSA 的角色量通根本无法扮演，等到开始做工程实施的时候，才发现面向用户的最后一公里组网，他们完全无法完成。于是他们想出来的着法就是通过量子手段，从远程到本地之间协商出来大量密钥并囤积起来，美其名曰量子密钥 QK （有关囤积 QK 的问题后面还会讨论），似乎这些自带仙气的 QK 具有某种魔法，能比本地生成的密钥加密出来的密文安全度更高。我承认我有点幸灾乐祸地冷眼观看量通如何将他们囤积的 QK 分发给两个陌生的用户，毕竟他们承诺几年内将量通普及到千家万户。如果不用明文发送这些囤积的 QK ，他们就得发明一种非公钥的新加密体制用来分发密钥，这种新体制还只能利用现成的网络系统。如果量通确实做到了这些，那倒还真的是密码学界的一大突破，获得个图灵奖肯定没有问题。令我感到好奇的是，尽管量通宣称已经有了那么广泛的商业应用，但他们从来不愿意告诉大家这最后一公里的密钥是怎么发送出去的？这些过程目前可都是谜团，量通专家不妨给大家普及一下这方面信息安全的知识，我可以保证能够听懂这方面知识的听众足够多，想要在这个环节一直保持模糊状态除非什么都不做。 8. 问：虽然面对很多批评，但是量通认为只要在密钥分发环节上，量子手段优于传统密钥分发手段，就值得发展这个技术方向，如何看待这个观点？答：这样的观点恰恰将量通专家对于信息安全理解的片面性暴露得清清楚楚。信息安全从来都是需要从全局的角度来衡量，需要遵循木桶原理。城池都是从最薄弱处被攻破的，这个道理连普通人都懂。在之前，量通通过各种文宣渲染危机，模糊化他们实际所做的工作，所以一般人甚至包括专业人士都以为量通真的是对通信系统采用量子的方式进行加密，但是在反对者不断纠正的声音中，量通不得不承认他们只是做了密钥分发的工作。那么传统密钥分发是否存在这个薄弱环节？密钥分发其实有两种类型，第一种是确定性用户间分发密钥，也就是 Alice 和 Bob 都是固定的通讯伙伴，比较典型的就是银行 KDC 之间；第二种是不确定性伙伴之间分发密钥，典型的就是互联网和移动用户之间。对于第一种类型，可以事先预置对称密钥，通过对称加密的方式进行密钥分发，甚至都不直接分发密钥，而只是发送无意义的随机数，由 Alice 和 Bob 根据随机数各自算出密钥。无论采用哪种方式，密钥分发的安全性都不低于量通的密钥分发手段，因为很简单的道理，只要采用了所谓的可信中继，量通的密钥也是采用经典的对称加密算法发送的。虽然量通的量子通道能够协商出来密钥，姑且不谈这个量子通道的安全性（这个通道恰恰是更不安全的），要想分发这个密钥，仍然需要采用传统的对称加密的方式进行加密传输，这就跟传统的加密方法没有什么不同，又何谈量通密钥分发安全性更高？这么简单的道理理解起来很难吗？对于第二种方式，属于临时通讯加密，只能采用非对称加密方式分发密钥，这种情况下量通的机制在理论上就已经根本不可能提供任何支持。在 IT 行业里，网络协议设计是最复杂的设计工作之一，需要全面考虑各种复杂的情况，覆盖所有可能的应用情景，只要想想 5G 标准制定引起这个世界多大的风波，就知道这里面从来就没有简单的工作。 BB84 协议是也只能是一个点对点网络协议，它的设计并非出自网络专家之手（当然也不是出自信息安全专家之手），完全没有能够理解网络协议设计需要关注的诸多内容，因此是非常粗糙简陋的设计，如果评分的话，开根号乘 10 也达不到 IT 行业网络协议设计的及格水平。这样一个协议从来就不是一个“完成”状态的协议，从根子上根本不具备任何组网的发展前景，任何组网的企图也都将破坏基本的安全前提，所以只能算是实验室里面拍脑袋捣鼓出来的东西。只要稍微思考一下就能够知道，类似 BB84 这样双通道模式设计出来的密钥分发协议，实际隐含一个应用原则：“ 谁分发密钥，谁消费密钥 ”，这个原则在实验室点对点密钥分发环境下倒不是什么致命的问题，可惜量通专家从来没有意识到，也没有能力总结出这样一个技术限制。他们的潜意识里面想当然认为点对点环境下的密钥分发协议，可以推而广之地应用在普通网络环境下，跟普通情况下的密钥分发没有什么不同，密钥的分发与使用是可以分割开来的。就是因为这个错误的认识，使得量通专家认为只要保证密钥分发环节是安全的，量通存在的理由就具有说服力，至于这些密钥究竟由谁来使用是与安全性无关的。所以他们认为采用囤积 QK 的方式，通过给各种用户提供安全度更高的密钥，就能获得更高的信息安全水平。这种想法愚不可及，可以用一个简单的例子来说明。比如上海本地一些用户想要使用一些密钥来加密信息，那么通过量通手段在北京和上海之间一站一站协商传送过来密钥，或者直接就在上海本地生成这些密钥，哪一种更安全一些？不言而喻，后者连密钥协商传输过程都不存在，当然不可能存在涉及到协商与传输过程的安全问题，相比较量通来说反而是无限安全的。 BB84 的点对点协议与可组网协议不是处于一个技术进化层次，量通的密钥分发不存在有价值的应用场景，囤积 QK 也将造成新的安全问题，后续的问答环节将进一步讨论这方面的问题。那么有什么理由花着工程建设成本，带着安全风险将密钥从北京分发到上海？那种认为量子手段优于传统密钥分发手段的观点应该休矣。墨子沙龙有关量子通信话题的问与答（一）墨子沙龙有关量子通信话题的问与答（三）墨子沙龙有关量子通信话题的问与答（四）墨子沙龙有关量子通信话题的问与答（五）参考资料： . 墨子沙龙 . 量子通信的问与答（上）什么是量子通信 . 2018-11-02. https://mp.weixin.qq.com/s/dWn-g098ZZ6KeUeQx1mc7g . 墨子沙龙 . 量子通信的问与答（中）什么是量子通信 . 2018-11-03. https://mp.weixin.qq.com/s/GT9hmW1qooG7f35VSi5fGA . . 墨子沙龙 . 量子通信的问与答（下）什么是量子通信 . 2018-11-04. https://mp.weixin.qq.com/s/_J34VZIltGnSxca8zI6u0A . . 徐令予 . 英美等国家如何评估“量子通信”工程化 . 观察者网 . 2018-10-31. https://www.guancha.cn/XuLingyu/2018_10_31_477593.shtml . 量子大观 . 定位广泛商用全长 609 公里“武合干线”贯通量子国家骨干网 . 2018-11-13. https://mp.weixin.qq.com/s/UdUrQ6m7kSEOHLgdV88Dng . 国务院 . 关于加强地方政府性债务管理的意见 . 2014-09-21 http://www.screnhe.gov.cn/InfoSend/Detail.aspx?id=20180126182643-873980-00-000 . 莎菲 . 戈德瓦瑟 (2012 年图灵奖获得者 ) ，潘建伟 . 看顶尖科学家激辩：量子计算与密码学 . 2018-10-31. https://m.thepaper.cn/newsDetail_forward_2582333 . 李红雨 . 沃尔夫奖的迷失 . 科学网. 2018-10-08 http://blog.sciencenet.cn/home.php?mod=spaceuid=46717do=blogid=1139647 . @ 九维空间 Sturman . 解读 2012 年诺贝尔物理学奖 . 2012-10-09 https://www.guokr.com/blog/356396/ http://blog.sciencenet.cn/home.php?mod=spaceuid=46717do=blogid=1139647 . Prof. Peter Zoller winner of Wolf Prize in Physics-2013 http://www.wolffund.org.il/index.php?dir=sitepage=winnerscs=737 . John F. Clauser Winner of Wolf Prize in Physics - 2010 http://www.wolffund.org.il/index.php?dir=sitepage=winnerscs=283 . 2005 年诺贝尔物理学奖解读 . 2005-12-03 http://blog.sina.com.cn/s/blog_4440e332010000ov.html . Juan Yin,……. S atellite-Based Entanglement Distribution Over 1200 kilometers. Science 2017-06-16 http://www.docin.com/p-1951266714.html . 徐令予 . “熔断和幽灵”有可能威胁量子通信干线的安全 . 观察者网 . 2018-01-31 https://www.guancha.cn/XuLingyu/2018_01_31_445230.shtml . 李红雨 . 量子通信是安全的吗？（下）科学网 . 2016-3-23 http://blog.sciencenet.cn/blog-46717-964437.html . 周炳琨等 . 激光原理（第六版） . 国防工业出版社 . 2009.1 . 用噪声保密我研究成果可使光通信“抗劫持” . 中国科技网 . 2018-05-21 http://www.stdaily.com/index/kejixinwen/2018-05/21/content_672370.shtml . 程小康 . 美媒惊叹中国量子加密技术领先：专家警告美国若再等 5 年才投入，就晚了 . 观察者网 . 2018-12-05 https://www.guancha.cn/industry-science/2018_12_05_482211.shtml; 4060 次阅读|13 个评论

“熔断和幽灵”有可能威胁量子通信干线的安全: 热度 18 lxu2800 2018-3-2 09:07; “熔断和幽灵”有可能威胁量子通信干线的安全二评京沪量子通信干线工程 2018年的新年刚过，北京时间1月4日凌晨4时左右，英特尔公司通过其官方推特发布了一份关于产品安全漏洞的声明，“渔阳鼙鼓动地来，惊破霓裳羽衣曲。”一夜醒来，人们方知自己桌上的电脑、手中的智能手机和常去的热门网站几乎都存在严重的安全隐患，数字世界中保护我们隐私的原来只有一层糊窗纸，一捅就破，互联网上几乎人人在裸奔。这次问题出在英特尔的微处理器（CPU），它们都存在“熔断和幽灵”这两种可怕的安全漏洞，这两个漏洞的名字听上去就吓死人。其它公司的微处理器也都存在这些漏洞，他们都是难兄难弟，五十步别笑一百步。最不可思议的是这些芯片底层的安全缺陷竟然存在了一二十年不为人知，长期以来我们引以为傲的数字化大厦原来是建在一片沙滩上，災难隨时都可能发生。这些带有严重安全漏洞的微处理器不仅用在各种消费电子产品中，也被使用在核电站、飞行器和国防工程中。不信？请看下面这张网上公开的图片。图片展示的是量子通信京沪干线合肥总控中心，这是监控量子通信干线各个枢纽机关（其中主要是可信任中继站）的中心，这是掌握所有机密的核心，这是保护量子通信干线安全的最后屏障。请看总控制台上的计算机（红色箭头所指），屏幕显示正在运行微软公司的视窗操作系统，十有八九该机使用的也是英特尔的微处理器。不知这台计算机是否已经打上了针对“熔断和幽灵”漏洞的修复补丁？在如此高大上的设备中打个补丁，听上去真有点别扭，但又有什么更好的办法呢？（友情提示，微软的补丁本身也有漏洞哦，更新修复须小心。）除了合肥总控中心控制台上的计算机用了英特尔的微处理器，估计还有成百上千的英特尔微处理器被用在京沪量子干线的各种设备中。量子密码通信能够做的只是密钥分发，它本身无法作加密解密等更为复杂的操作。无论量子密码通信这个过程有多高深多玄乎，无论你上天入地，最终你还得输出壹与零组成的经典电讯号，并把这些二进制的电讯号交给英特尔的微处理器去完成对数据的加密与解密。没有计算机，没有这些微处理器，用几百位长的密钥对数据作加密解密是不可想象的。京沪量子通信干线从总控制台到各处的可信任中继站使用成百上千的微处理器，这些微处理器，不管是英特尔还是AMD或者ARM全都是一个熊样，全部带着严重的“熔断和幽灵”安全隐患，它们为恶意攻击者在量子干线上窃取密钥提供了许多机会。存在于微处理器硬件中的安全缺陷对量子通信系统的破坏性远超传统密码系统，其原因主要是两条：1）京沪量子通信干线使用了许多“可信任中继站。在这些中继站里密钥与各类硬件（包括微处理器）有亲密接触，恶意攻击者很容易通过诸如“熔断和幽灵”漏洞直接获取密钥。只要密钥落人手，千里长堤毁一旦。2）量子通信干线的建设者深知这些中继站是命门软肋，必须作彻底的“物理隔离”，就加建了不少监视和遥控设施，因而才有了上面图片显示的总控中心。在这些设施中又用了许多英特尔的微处理器，这就引入了更多的安全隐患和两次性伤害。传统密码系统没有以上这些问题，因为传统密码严格保证所有通过传输线路上的信息是经过加密保护的，这其中包括数据也包括密钥本身。换言之，无论传输线路上用了多少不安全的设备和微处理器，恶意攻击者不管处在传输线路的什么地方、使用了什么方法，能够看到的都是密文乱码，无法窃取任何有意义的信息。传统密码系统对通信线路和设备从来是不设防的，在互联网时代也根本无法点点设防，传统密码从思维层次上就胜量子通信一筹。那么传统密码是否就能保证绝对安全，正确的答案是：传统密码能保证信息从A传输到B之间有充分的安全，但是整个信息系统的安全还涉及许多其它因素，例如解密后数据的保管和存放、密钥的更新和保护等等环节，密码本身是无法保证整个信息系统安全的。换言之，传统密码可以保证信道安全，但不能保护信源的安全。只要是使用桌上电脑和手机，黑客就可以利用它们里面微处理器中的“熔断和幽灵”漏洞窃取秘密，不管是传统密码还是量子通信，全都没有用。当然量子通信的问题要更多更严重一点，因为量子通信让裸露的密钥在传送中接触了更多的微处理器。 “我们中间有些人对微软视窗操作系统的许多安全隐患熟视无睹，却对远为成熟安全的公钥密码RSA横挑眉毛竖挑眼，他们天天心安理得地使用着漏洞百出的微软视窗，却把公钥密码RSA描绘成明天就会引爆的地雷。他们的这种思维方式总让人感觉有些滑稽，这有点像即将沉没的游轮上的旅客不赶紧寻找救生圈，却在抱怨船上提供的食品临近保质期。” 上述这段文字摘自我的“量子密码工程建设还有太多不确定因素”一文，该文发表在观察者网上，发表日期为2017年12月6日。差不多一个月后就爆出了英特尔的“熔断和幽灵”事件。这旣不是先见之明，也不是乌鸦嘴，仅是时间巧合而已，只是问题比我预想的还要严重百倍。推动量子通信的逻辑是公钥密码有安全隐患，对此没人有异议，把量子通信作为一种未来的选项而开展相应的科学研究应该支持，这一直是我的态度。但是必须明白量子通信相关技术远未成熟，而公钥密码的安全隐患还在遥远的未来，匆忙建设京沪量子通信干线既无必要也没条件。任何工程项目上马必须经得起可行性、必要性和成本收益的分析和评判。有关量子通信的可行性、必要性和成本收益的详细分析可参见我的两篇文章：“炒作量子通信工程，连潘建伟都担心”，“量子密码工程建设还有太多不确定因素”，这里就不再重复。本文有两个重要的新材料要补充。（1）目前量子通信干线使用的可信任中继站存在安全隐患，干线工程的负责人在公开讲话中不否认这一点。他们透露正在研制替代方案——量子中继，他们自己承认量子中继技术的成熟估计还要十年时间。即使量子中继里面的一系列技术问题（希望里面少用英特尔芯片）在十年中全部被解决，那么现在这十年中这条京沪干线该怎么办？十年后更换所有中继站的费用知多少？这十年中传统密码完全不会有问题也要安全得多，建设这条量子通信干线的收益究竟又在何处？（2）传统密码系统在今后相当长时期内是足够安全的，这不仅有学术论文为证，近期火热发展的区块链技术是最强有力的佐证。众所周知，公钥密码就是区块链技术的安全基石，可以毫不夸张地说，没有公钥密码的安全就没有区块链技术。如果公钥密码真像量子通信推动者说得那样的不堪一击，为什么IT学术界和企业家会对区块链的明天投入如此多的热情和资金？难道这些人都是傻瓜吗？事实上，公钥密码并没有紧迫的危机，急于想代替公钥密码才真正令人不可理喻。从更长远的角度来看，任何技术都需要更新和完善，公钥密码技术当然也不例外。但是更新后的系统必须与互联网的总体框架协调，升级换代的过程也要稳步有序地推进。密码系统牵动整个互联网的生态环境，对于这种牵一发而动全身的技术更新，我们千万不能异想天开、草率行事。必须再次强调，公钥问题仅是密码系统的一部分，而密码系统又只是整个信息系统安全的一部分而已。今日信息系统的安全确实面临一系列严峻的挑战，但如果把这些挑战按危急严重程度罗列出来的话，密码安全问题根本进不了前三甲。隨着信息的电子化和网络化，密钥的产生、管理、分发全部是由电子计算机完成的，相比计算机硬件和操作系统的安全问题，所谓的公钥密码问题真是小巫见大巫了。今天我们终于看到了微处理器“熔断和幽灵”这个大巫的丑陋可憎的面目了，不过我可以告诉大家，千万别信英特尔轻描淡写的声明，这个大巫掀起的腥风血雨还远未结束。集中精力、协调配合去认真面对当前的头号大巫——“熔断和幽灵”——这才是信息安全领域的头等大事。利用“熔断”漏洞，低权限的程序可以访问操作系统的内核空间，获取系统底层的核心机密；当用户通过浏览器访问存在“幽灵”恶意程序的网站时，用户的帐号、密码和其它隐私信息可能会被泄漏；在云服务环境中，攻击者可利用“幽灵”漏洞可以突破用户间的隔离，窃取其他人的信息。 “熔断”是最容易被利用的缺陷，Intel所有处理器存在“熔断”缺陷，AMD处理器不存在“熔断”缺陷，ARM只有A57存在“熔断”缺陷。幽灵缺陷也不完全相同，Intel的幽灵缺陷很容易被利用，AMD因为构架复杂，研究者并未能真正突破。（岳晓东博士的评论）; 个人分类: 科普集锦|7037 次阅读|44 个评论

需求和成本是工程立项的基础: 热度 16 lxu2800 2017-12-29 09:34; 需求和成本是工程立项的基础一评京沪量子通信干线工程 9月29日，世界首条量子保密通信干线——“京沪干线”正式开通。中国科技人员在量子保密通信相关技术领域，诸如高速高效率单光子探测、可信任光子中继站和星地量子密钥协商等方面都取得了重大进展，可喜可贺！对此我们不需要更多的溢美之词，此时此刻，客观的介绍和有益的建议比什么都重要。为什么要开发量子保密通信技术？因为从理论上讲，如果未来量子计算机真的建成，再如果建成的量子计算机有足够的量子位（Qbit）和足够的稳定性，那么今天密码系统中的非对称性的公钥密码RSA有可能被想象中的量子计算机破解。研发量子密码通信技术就是为了寻找未来可以替代RSA的技术。必须指出，虽然今日的密码系统并非尽善尽美，但也没有迫在眉梢的危机。由此可知，量子保密技术只可能是前瞻性的科学研究，而现在却把它做成了工程项目，这就必然会带来一些问题和争议。这些问题不得到澄清和解决，《九州量子》和《量子小镇》这些事件就会层出不穷。 “京沪干线”工程项目首席科学家、中科院院士潘建伟最近的谈话中提到：“....，但是大家不能把它炒作得太热之后，一个东西反而味道就变掉了。要严谨地去做事情。”从字里行间不难看出，他也担心京沪量子保密通信干线如果在过度炒作的舆论环境下，可能不利于解决实际的科学问题。他又说：“量子通信广泛应用取决于成本和需求两大因素。 ”这句话说到点子上了，评论工程项目，需求和成本就是两个始终绕不开的坎。让我们先对量子通信工程的需求作些分析。2017年5月有一篇论文：“后量子时代的RSA” ，该文发表后被多家相关杂志转载和引用，几乎一致的结论是现今使用的非对称性密码RSA不会因为量子计算机的出现而消亡。该论文的核心观点是：假设量子计算机已经建成，再假设量子计算机的量子位（Qbit）可以无限扩展，进一步假设该量子计算机的运行成本与现在通用电子计算机的成本可以相比，用这样一台超级想象出来的量子计算机来破解长度为 Terabyte（太字节，等于1024GB）的RSA非对称密钥需要量子计算机进行2^100（2的100次方）的量子位操作。 2^100是一个什么概念？这个数大于我们星球上所有细胞的总数！当然一个Terabyte长度的RSA公钥也有点过份了，但即使在目前使用的电子计算机上运行，从密钥的产生到加密和解密一共化时五天。这样的方案虽然不太实用但至少还是可以实现的。这篇论文并不是要为对抗量子计算机提供确切的方案，而是用实验和大量数据分析指出：即使围绕量子计算机的技术难题和运营成本全都解决，只要现行的RSA公钥增加字长和改善算法，就能迫使量子计算机的恶意攻击付出难以承受的代价，在后量子时代作为经典密码系统重要基石的RSA具有足够长的生命力。急于丢弃RSA等公钥密码系统而另辟蹊径可能真的是杞人忧天。让我们进一步对量子通信工程作些初步的成本分析。经典保密技术与量子保密技术的主要区别是：经典保密系统中通信的内容与密码的配送使用的是同一个通信网络，而量子保密系统必需两个通信网络，一个传送通信内容，另一个配送量子密码。量子保密技术势必会大幅增加通信的成本。由电路交换和分组交换技术构建起的经典通信网络从本质上来说与量子保密通信网络是格格不入、难以融合的。很难设想在原有的通信网络线路上实现量子密钥分发。换言之，为了通信未来的安全，我们必须在原有的通信网络之外加建一套传递密钥的专用网络。而且这条网络要求所有通信双方端到端全程使用光纤联接，当通信双方超过上百公里，还必须使用可信任中继站或卫星中继。暂不考虑工程的难度，对于普通用户特别是手机用户而言，仅成本一项无疑也是难以承受之重。到目前为止，在所有的经典加密技术中，通信的内容与加密的信息都在同网络上传输，信息交换和保证信息交换的安全措施是一个统一完整的过程，密码系统在整个通信过程中所占的额外成本是十分有限的。因此从工程角度来看，改进和革新经典加密技术比发展量子密码技术的成本要低得多，也更为切实可行，这一点越来越成为业内人士的共识。再让我们看看密码学界最近的动态，请先看下图：密码学界已经明确把公钥密码系统分成两大类，左列中都是目前常用的公钥密码，它们是“量子可破”的，即理论上在量子计算机攻击下是不安全的（事实上也并非如此，见文章的上部分分析）。图中右列的几种公钥密码系统被列为“量子不可破”，它们从原理上被证明是很难被今日的巨型电子计算机和还在纸上的量子计算机破解的，因而它们又被称为后量子时代的密码系统。在“量子不可破”的公钥密码系统中最受关注的是“lattice-based crypto ”（基于阻格的加密法），密码学界对该方法的研究已经有二十多年了，但始终没有进入工程应用阶段。其问题的本质是：该算法太复杂，运行效率低得无法使用；算法加以简化后，效率大幅提升，几乎可以与RSA媲美，但是却出现安全隐患。但是近年来对于该密码系统的研究取得了实质性进展，它们很可能就是美国国家安全局不久将要推出的后量子时代的密码系统中的重要组成部分。对付量子计算机未来可能的攻击，采用改进的经典数学方法而不是全新的量子密码技术己成为欧美密码界近期的共识，2017年年中在迪拜召开的RSA国际学术会议充分展示了这一点。这些改进后的新的密码算法完全可以在目前所有的计算机和通信网络上运行，现行一切通信方式釆用这些新算法进行升级换代过程可以变得更平稳更经济。把高铁工程与量子保密通信联系在一起，可以印象化地说明这样一个事实：洋人做不来的事，中国人可以做而且可以做得很好。但是我们必须明白，量子保密通信不是高铁工程，它只是一个不完整的示范性工程，工程的必需性和可行性正面临严峻的考验。人们出行可以坐高铁也可以不坐高铁，也可以坐一段高铁再加一段普客。但是通信系统中经典密码系统很难与量子密码系统兼用，如果一定要联在一起用，就会有木桶短板效应产生，量子保密系统不能为用户带来丝毫益处，除非通信双方全程使用量子保密系统，而我们都知道这对大量的普通用户又是多么地不切实际。高铁一通，上面坐满了普通百姓，而京沪量子干线开通至今，请问又有几个吃瓜群众享受到了量子保密通信的好处？那么金融行业，特别是银行系统是否会享受到量子通信干线的优越性呢？很可惜答案是否定的。量子计算机有可能破解RSA这类非对称密钥，而对于基于复杂逻辑运算的对称密钥体制根本就没有威胁。现在所有金融行业（包括银行）采用的都是对称密钥体制，这个标准由中国人民银行颁布的PBOC里面有详细的描述，并且PBOC标准也是参考美国的国家标准制定的，其实全世界的金融行业标准几乎都是一个模子刻出来的。银行系统密钥分发要用到RSA这类非对称密钥只有初始化的第一次，之后采用的都是对称密钥加密。其实初始化都未必会用到RSA，任何能够安全地将初始化密钥分发到密钥分发管理中心的手段都可以采用，毕竟只需要做一次的事情，麻烦一些也无所谓。银行与其它金融系统对量子保密通信是不会有多少兴趣的，哪怕你明天就变出一台有几万量子位的量子计算机，他们仍旧会是“量子围困万千重，我自巍然不动。” 军队会使用量子通信吗？从目前的技术状态来看，这更不可能。军队通信对网络的移动性、可变性、和抗干涉性有更高的要求，量子保密通信从本质上很难适应这样的网络通信环境。那么究竟谁是京沪量子干线上的主要用户呢？有报道说某某市政务系统开始采用量子保密通信技术，做些什么呢？使用量子密钥对视频通话加密解密。其实只要是了解政务系统的人都知道，跑在政务系统上面的信息，其实从来就没有太多需要保密传送的内容，真正机密的信息连一个字都不会放在政务网上的。所谓政务网采用量子通信多少带有作秀的成分。对量子保密通信概念的误解导致了一系列问题的产生，媒体的过份渲染和资本市场的炒作把问题进一步复杂化。因此有必要再次强调： 1）量子通信根本不是一种新的通信技术，它不是用来传递信息的，它从来不是、也永不可能为大众带来更快、更方便、更廉价的通信服务； 2）量子通信干线工程甚至也不是一套完整的密码安全系统，到目前为止，它不能提供密钥的分级发送管理、身份认真和电子签名这样一套完整的严格切实可行的信息安全服务； 3）目前量子通信工程只是基于BB84协议的量子密钥协商技术，原本是用来对付将来有可能发生的量子计算机对非对称RSA密钥攻击的一种防卫手段。但事实上RSA在后量子时代有足够强的生命力，而且更重要的是在许多应用环境中，RSA公共密钥並不是非要不可的。而在一些离不开RSA的环境中，量子通信又根本无法投入使用。对量子密码技术作前瞻性的科学研究我们应该支持，毕竟在后量子时代如何确保信息安全谁也不敢打保票，量子密码技术有可能发展成为对抗量子计算机攻击的有效工具，多一种选择总是好的。虽然危机仍在未定之天，但未雨绸缪作超前的研究也是应该的，因为新技术从概念提出、实验证明、技术和标准的建立都需要时间，千万不能等危机出现后再临阵磨枪。而且科学研究的过程中会提升相关技术的水平，也很可能会收获意想不到的副产品。对量子保密通信技术作前瞻性科学研究应该大力支持，我的这个态度始终也不会改变。但是铺开建设量子保密通信干线的工程项目必须谨慎再谨慎。从近期看，经典密码系统是安全的，到目前为止，量子保密技术不仅成本昂贵，而且功能上也无法替代经典密码系统。开发量子保密技术为的是应对未来可能发生的危机，但这种危机离我们仍十分地遥远，即使危机真的降临，改进升级后的经典密码系统应该足以应付危局。在后量子时代，量子密码技术并非是对抗危机的唯一选择，它很有可能仅是一枚永远也使用不上的备胎。 http://www.guancha.cn/society/2017_09_29_429255.shtml http://www.guancha.cn/economy/2017_09_30_429382.shtml http://www.guancha.cn/society/2017_09_29_429359.shtml https://eprint.iacr.org/2017/351.pdf 有关中国人民银行使用的PBOC简介，可参阅科学网李红雨博客：http://blog.sciencenet.cn/blog-46717-1074225.html 量子保密通信至今不是一套完整的密码安全系统。到目前为止，它不能对通信安全提供诸如密钥的分级发送管理、身份认真和电子签名这样一整套严格完整的全方位的服务。本文首发于观察者网2017年10月31日 , 发表时曾有多处删节。; 个人分类: 科普集锦|11860 次阅读|49 个评论

拿什么拯救你-危机四伏中的密码系统: 热度 24 lxu2800 2016-3-8 10:04; 量子密钥分配技术（上）拿什么拯救你-危机四伏中的密码系统长久以来人们都把密码与军事、外交联系在一起，印象中使用密码的人物如果不是躲在阴暗角落的间谍特务就是捍卫国家安全的孤胆英雄。事实上，今天每个普通人都离不开密码，密码技术已经飞入平常百姓家。当你在网上购物，当你用手机通话或收发微信，所有信息都在开放共享的网络上传输，现代通讯技术使得信息的传输变得十分方便、迅速和高效，但同时它也使信息很容易被黑客截获，没有密码技术保护在网上使用信用卡，在无线网上通话将会是难以想象的。据估计，每天有全世界生产总值一半以上的金钱财产在国际银行金融电讯网络（SWIFT）上流动，这样大规模的金融活动如果失去可靠有效的密码技术保护必会引起世界级的灾难！当然现代化的军隊也比过去更依赖于密码技术，否则哪来远程打击？如果遥测遥控的信息被盗，敌方可以隐藏保护自己，或者可以改变导弹的轨迹，甚至操纵无人机据为已有。事实上对今日的攻击方而言，使用导弹和飞机已是多余，如果能破解对方的密码系统，发个命令就可以秒杀对方城市的供电、公交和电讯系统，真正达到“不战而屈人之兵”的最佳效果。可以毫不夸张地说，密码学是信息时代-后工业时代的基础，密码技术对于政府、军队和大众生活，已是不可须臾离者也，它像空气一样，人们一刻也少不了它，但却常常为人所忽视。今天的密码技术正面临着严峻的挑战，新技术的研发已经刻不容缓。本文上篇将通过对密码技术基本知识的介绍，把密码危机的由来解释清楚，从而明白为什么要引人量子密钥分配技术，下篇将着重介绍量子密钥分配的原理和该技术的现状和展望。简单地说，密码技术就是发送方通过双方认同的某种规律把明文加密后得到密文，然后通过不安全讯道送给接送方，接收方再按照该规律把密文解密后还原成明文。最古典的两种加密方法无非是字母的置换和替代。替代法是按规律地将一组字母换成其他字母或符号，例如明文‘fly at once’变成密文‘gmz bu podf’（每个字母用字母序列中下一个字母取代）。使用同样的方法只要改变一个参数（每个字母用下两个字母取代），密文就变成‘hha cv qpfg’。在密码学中把这种加密解密的方法称为密码算法，而把算法中的秘密参数称为密钥（Key），它只能为通讯双方共享。 P1)对称密码体制中用相同的密钥作为加密和解密算法中的秘密参数。自有密码技术诞生起，破密技术的发展就没有消停过，这对冤家兄弟从古至今爭斗得难分难离。例如上面提到的字母替代法早已停止使用，它太容易被敌方破译。因为每个英文字母在明文中出现的机率是不同的，只要把密文中的字母也作一次出现率统计，不难找出字母之间替代的规律，从而破解密文。道高一尺，魔高一丈，高级的加密算法使字母的替代不是固定一一对应关系，字母替代的次序与出现机率也不是固定的，有兴趣的可以看本文后面附件中的“维热纳尔方阵”算法，这种算法并不难理解，但如果没有密钥就很难破译。二战中徳国军队使用的恩尼格玛(Enigma)密码机把密码技术推到了当时的顶峰。恩尼格玛密码机在密码技术上有三个突破：1）密码机依靠机电设备自动完成加密和解密过程，因而可以高效正确地完成高度复杂的密码算法；2）密码机上的转轮的设置和面板对接孔联线方式决定了字母复杂多变的替代关系，它们就是系统的密钥，密钥可以轻松地每天一变，这使得对密文的破译变得更为困难；3）由于算法和密钥的彻底分离，使得敌方缴获密码机没有多大用处，通讯的安全是靠复杂多变的密钥得到保障。 P2)二战中德军使用的恩尼格玛密码机。（右边）密码机上的转轮的配置和起始点的变化再加上机子正下方的对接孔不同的联接方式共同构成了系统的密钥。战时的英国情报机关为了破译德国的恩尼格玛密码伤足了脑筯，回顾这段历史的“Imitation Game ”是部值得一看的好电影。但是该影片过份夸大了英国情报机关的功绩，事实上战前波兰破译小组对恩尼格玛密码机的深入研究和德国内部叛徒提供的有关资料都为英国的破译帮了大忙。当然天才数学家图灵为破译恩尼格玛作出了巨大的贡献，图灵首先意识到“解铃还须系铃人”，机器成生的密码只能依靠机器破译，为此他越级向英国首相丘吉尔直接打报告，申请十万英镑研制破译机器，这在当时是一笔巨款。令所有人意外的是，丘吉尔竟然批准了这个看似极不靠谱项目，而且在百忙之中，亲自探望了图灵为首的破译小组。什么是领袖气质？领袖一定要能做到：慧眼识才招揽天下英雄；高瞻远瞩把握长远趋势。丘吉尔真不愧是一位世界级的枭雄。英国情报部门对恩尼格玛密码机破译始终守口如瓶、滴水不漏，到战争结束，德军仍不知自己许多重要军事行动已被英国掌握。更绝的是，英国战后把缴获的成千上万台恩尼格玛密码机送给了原殖民地的英国盟国，这些国家长期使用它们直到七十年代初期，而有关破译恩尼格玛密码机的故事要到七十年代中期才被逐步透露出来。英国正应该称为“阴国”才名符其实，由此也可看到殖民地国家要摆脱宗主国的控制获得真正的独立有多么的不容易。有了电脑以后，现代密码技术的算法更为高度复杂化。现今普遍使用的DES算法具有极高安全性，到目前为止，除了用穷举搜索法对DES算法进行攻击外，还没有发现更有效的办法。而近年来提出了AES和三重DES的变形方式会使破译变得更加困难。由于密钥中每位的数值是完全隨机选取的，一个128位长的密钥有2的128次方的不同组合，在世界最快的计算机中国天河2号上用穷举搜索法攻击也至少要化一万亿年才能得手！有必要再次强调密码系统包括算法和密钥两部份。一个好的密码系统的算法可以是公开的，就像上面提到的DES算法，只要通讯双方保护好密钥，加密后的资料就是安全的。这个原则又被称为柯克霍夫原则（Kerckhoffs' principle）。认为所有加密法都可以被破解是大众的误解。理论上已经证明，只要密钥不再重新使用，信息被与其等长或更长的密钥加密后是不可能破密的。既然如此，那么信息安全危机究竟在哪里呢？到目前为止讨论的所有密码体制中通讯双方使用相同的密钥进行加密和解密，在这种对称密码体制中信息的安全靠密钥保证。需要改变密钥时，通讯双方必须直接碰头交换，或者由可信任的第三方配送。所有问题也就发生在密钥分配过程中。保护和窃取密钥一直是许多警谍影视剧的重头戏，情节常常是这样的：交通员单骑行千里，到了上海的茶馆店里把缝在裤子里密码交与地下工作者，一旦发生意外把密码吞进肚子。由此也不难理解京剧“红灯记”歌词：“铁梅我，有准备；不怕抓，不怕放，不怕皮鞭打，不怕监牢押！粉身碎骨不交密电码--”。美国政府的密钥是COMSEC（通讯安全局）掌管和分发的，七十年代时，它们每天分发的密钥数以吨计。当装载着COMSEC密钥的船靠港时，密码分发员会上船收集各种卡片、纸带以及其它一切贮存密钥的介质，然后把它们分送给各处的客户。依靠第三方配送密钥增加了通迅双方的开支，而且第三方配送者本身也构成了严重的安全隠患。为了确保信息的安全必须经常更换密钥，但今天的通讯者常常相隔千山万水，要让通讯双方碰头交换密钥非常不现实，依靠第三方配送密钥一般人根本负担不起，而且也不一定及时可靠。密钥的配送问题长期困扰着密码学的专家们。到了七十年代，一种称为非对称密码体制（又称为公钥密码体制）应运而生。在前面介绍的对称密码体制中通讯双方使用同一个密钥进行加密和解密，而非对称密码通讯时加密和解密使用一对公钥和私钥，用公钥加密后的文件只能被与其对应的私钥解密，反之也然。现在请对照下图来了解公钥密码体制的流程。右边接收方通过计算产生一对公钥和私钥（分别为绿色和红色），接收方把绿色的公钥通过公开信道大大方方地送给左边的发送方，发送方用接收方送来的公钥对文件加密后通过公开信道送给接收方，接收方用红色的私钥对文件解密，文件安全可靠地从发送方送到了接收方。 P3)非对称密码体制（即公钥密码体制）的原理示意图。公钥密码体制的关键是用了公钥和私钥，一个公开一个隠秘，第三者拿了公钥没有任何用处，公钥能用来加密但不能解密，也推算不出私钥。而通讯双方可以隨时产生新的密钥对，把公钥通过开放信道送给发送方，把私钥藏妥，通讯双方无需直接碰头。这里介绍的是公钥密码体制的基本原理，实际应用中略为复杂一点，但原理相差无几。为了更好地理解公钥密码体制，可以把公钥看成一把打开的锁，私钥就是开锁的钥。接收方B把打开的锁通过公共渠道传给发送方A，A把文件放于箱中并用B送来的锁把箱子锁上，加锁后的箱子再通过公共渠道返还B，B用私钥把锁打开取出箱中文件。在传送过程中截获打开的锁毫无意义，事实上B乐意把许多打开的锁送出去并为众人所有，这样大家可以加锁给他送密信，而这把锁一旦锁上任何人再也无法打开，除了握有私钥的接收方B。公钥密码体制中加密和解密的算法很复杂，计算量大，事实上很少直接用它来加密文件，它真正的用途是用来传送前面所介绍的对称密码体制中的那个通讯双方共用的密钥。所以实际上文件传送流程应该是这样：A方先决定一个密钥，然后用B送来的公钥加密后传给B，B用自己的私钥对其解密后获得真正的密钥，然后双方就用此密钥对文件加密后传送给对方，收到方用该密钥对文件解密。这样的系统很安全，因为密钥可以随时改变并被公钥密码体制保护后在公共讯道上传输不被截获，这才是通讯安全的根本保证。那么天下是否就此太平无事了呢？很遗憾，答案却是否定的。“天下有贼”，而且贼的本事贼大。黑客攻击的重点是公钥系统，RSA公钥的产生基于两个大质数的乘积，它不是一个完全的隨机数，这就是整个密码系统中的阿喀琉斯的脚后根，一旦公钥系统破解，密钥就可能被截获，“皮之不存，毛将焉附？”整个系统就会崩溃。近年来美国技术标准局已经强烈建议把RSA公钥从1024位提高到2048位。提高公钥密码位数极大地增加了加密和解密所化的时间，给日常的应用带来了诸多不便，却并没有从根本上阻止黑客攻击的热情和力度，提高位数给使用者増添的困难远超对黑客的阻力。而2014年的一条爆炸性新闻更是震惊了密码学界，从美国国家安全局（NSA）叛逃的斯诺顿（Edward Snowden）披露了NSA有一个绝密的项目 Penetrating Hard Targets，计划建造一台专用于破密的量子计算机。据传该局已经存放了大量外国政府的密电，一旦项目成功立刻对它们动手开刀。量子计算机虽然还在试制中，但贝尔实验室的一位数学家已经为此设计好了攻击RSA的算法，并声称已经写成可以在量子计算机运用的程序，它可以轻松地破解公钥密码体制。量子计算机的研发进展是各强国的最高机密，媒体上的报道真真假假千万信不得，很有可能用以破译的专用量子计算机已经接近完工，这决不是危人耸听，密码世界从来是波诡云谲莫测高深。即使按专家们保守的预测，量子计算机的实际应用也许还要等十到十五年，但寻找新的密码系统，特别是开发密钥分配的新技术已经刻不容缓，因为新技术从开发到系统的建立和实用也需要时日，所以我们已经到了最危险的时刻！ Vigenere 密码附件 Vigenere.pdf 该密码机像部电动打字机，机器有26个字母按键和26个字母显示灯和一些机电联部件组成，这是固定部份，它们决定了加密和解密的算法；另外有三个可以装卸的转动轮和两排字母对接孔，这些转动轮排列的次序和开始的位置和字母对接孔的连线每天按照约定设置，它们就是每天通讯的密钥。发送时把明文字母用按键一一输入，经过机器复杂的变换后点亮不同的字母显示灯，这些字母出现的序列就是密文，把它用电报发送出去，接收方用同样的机器，按同样的密钥设置，键入密文，从字母显示灯的序列中读出的就是明文。公共密钥附件 Public Key.pdf; 个人分类: 科普集锦|24651 次阅读|52 个评论

RSA加密算法和Euler定理: murongxixi 2013-11-12 23:54; 以前看过一部精彩的电视剧《暗算》，讲的是破译密码的故事。其中第二个单元，陈数饰演的海归密码专家黄依依，力排众议，另辟蹊径，破译了国民党的王牌密码“光复一号”，那傲人的风采，着实让我迷恋了好久。电视里看来，密码是个不明觉厉的东西，后来学习了相关知识才发现，其实密码也并非高不可攀的玩意，至少了解它的原理并不难。密码的应用场景很简单，发送方要把原文传递给接收方，为了防止第三者也获得这个原文，发送方需要按某种方式对原文进行一些处理，处理的过程就是加密，之后将密文传递出去，接收方则按某种方式将接受到的密文进行相应处理，即解密。故解密其实是加密的逆过程，由发送方和接收方事先商定好。虽然第三者可以通过某些手段截获密文，但是由于不知解密方式，因此想还原出原文是不太容易的，在未知解密方式的情况下，仅根据密文去还原原文就是密码破译。密码专家研究的就是如何设计安全的密码和如何破译已有的密码。用数学一点的语言描述就是：设原文为$X$，发送方用映射$f$作用于$X$得到密文$f(X)$，接收方用映射$g$作用于密文得到原文，也即$g(f(X)) = X$。举个众所周知的例子，凯撒密码是通过将字母按字母表顺序后移$3$位进行加密的，也即将字母$A$换作字母$D$，将字母$B$换作字母$E$等等，接收方只要知道发送方用的是凯撒密码，就只需将密文中的字母按字母表顺序前移$3$位即可解密，这个$3$称为密钥，当然也可以使用其他的整数。如果我们用数字$1$到$26$对字母$a$到$z$进行编码的话，凯撒密码对应的加密函数就是$f(x) = (x+3) \ (\mathrm{mod} \ 26)$，解密函数是$g(x) = (x-3) \ (\mathrm{mod} \ 26)$。注意，这里加密和解密需要使用相同的密钥，这样的密码被称为“对称加密算法”。这种加密模式有一个最大弱点：发送方必须把加密规则告诉接收方，否则无法解密，如何安全地传递密钥，就成了最头疼的问题。鉴于对称加密算法的重大缺陷，“非对称加密算法”应运而生，它的基本想法是接收方生成两把密钥(公钥和私钥)。公钥是公开的，任何人都可以获得，私钥则是保密的。发送方获取接收方的公钥，然后用它对原文进行加密。接收方得到密文后，用私钥即可解密。这样就避免了传递私钥的问题了。1977年，三位MIT的数学家Ron Rivest、Adi Shamir和Leonard Adleman设计了一种非对称加密算法，这种算法用他们三个人的姓氏的首字母命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的非对称加密算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。蹩脚的故事讲完了，下面来看一下RSA的细节，首先接收方先做如下工作：选取两个足够大的质数$p$和$q(p \neq q)$，并计算$n = pq$和$r = (p-1)(q-1)$。选取任意一个比$r$小且与$r$互素的数$e$，求得$e$关于模$r$的模反元素$d$，即满足$ed \equiv 1 \ (\mathrm{mod} \ r)$的$d$。将$n$和$e$公布出去，保留$d$，销毁$p$和$q$。假设发送方要传递原文$x$，则只需根据接收方公布出的$n$和$e$计算$x^e \equiv c \ (\mathrm{mod} \ n)$，这里$c$就是密文。接收方得到$c$后，可以通过$c^d \equiv x \ (\mathrm{mod} \ n)$还原出$x$。假设第三者获得了接收方公布的$N$和$e$以及发送方的加密消息$c$，但他无法直接获得$d$。要获得$d$，最简单的方法是将$n$分解为$p$和$q$，这样他可以得到同余方程$ de \equiv 1 \ (\mathrm{mod} \ (p-1)(q-1))$并解出$d$，然后代入解密公式$c^d \equiv x \ (\mathrm{mod} \ n)$导出$x$。但对于质因数分解问题，至今为止还没有一个多项式复杂度的算法，因此只要$n$足够大，密码就很安全了。最后要说明的就是模反元素$d$的存在性和$c^d \equiv x \ (\mathrm{mod} \ n)$的正确性，这要先引入Euler函数和Euler定理。 Euler函数$\varphi(n)$是小于等于$n$的正整数中与$n$互素的数的数目，它的计算方法如下：若$n=1$，有$\varphi(n) = 1$。若$n$为素数，有$\varphi(n) = n - 1$。若$n = p^k$，其中$p$是素数，$k$是正整数。显然小于等于$p^k$且不与其互素的都是$p$的倍数，于是$\varphi(n) = p^k - p^{k-1} = p^k(1 - 1/p) = n(1 - \frac{1}{p})$。若$n = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_k^{\alpha_k}$为$n$的标准分解式。下面我们应该剔除所有$p_1,\dots,p_k$的倍数，显然小于等于$n$且与$p_1$互素的数的个数为$n(1 - \frac{1}{p_1})$。接着剔除$p_2$的所有倍数，一共有$\frac{n}{p_2}$个，但是这$\frac{n}{p_2}$个数中有些也是$p_1$的倍数，之前已经剔除了，因此只能剔除这$\frac{n}{p_2}$个数中与$p_1$互素的数，易知有$\frac{n}{p_2}(1 - \frac{1}{p_1})$个，于是还剩$n(1 - \frac{1}{p_1}) - \frac{n}{p_2}(1 - \frac{1}{p_1}) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})$个。同理可得小于等于$n$且与$p_1$，$p_2$，$p_3$都互素的数的个数为\begin{align}n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) - \frac{n}{p_3}(1 - \frac{1}{p_1})(1 - \frac{1}{p_2}) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})(1 - \frac{1}{p_3})\end{align}重复这样的过程可得小于等于$n$且与$p_1,\dots,p_k$都互素的数的个数为\begin{align}\varphi(n) = n(1 - \frac{1}{p_1})(1 - \frac{1}{p_2})\dots(1 - \frac{1}{p_k})\end{align} Euler定理是一个关于同余的性质：若$n$和$a$为互素的正整数，则$a^{\varphi(n)} \equiv 1 \ (\mathrm{mod} \ n)$。设小于等于$n$且与其互素的所有数构成的集合为$Z = \{ x_1,\dots, x_{\varphi(n)} \}$，即$n$的一个化简剩余系。考虑集合$S = \{ ax_1(\mathrm{mod} \ n),\dots, ax_{\varphi(n)}(\mathrm{mod} \ n) \}$，对于任意$x_i$，由于$a$与$n$互素，故$a x_i$也与$n$互素，由此可得$a x_i (\mathrm{mod} \ n) \in Z$，这说明$S \subseteq Z$；又对于任意$x_i \neq x_j$，易知有$ax_i(\mathrm{mod} \ n) \neq ax_j(\mathrm{mod} \ n)$，故$S = Z$。于是 \begin{align} (x_1 \dots x_{\varphi(n)}) (\mathrm{mod} \ n) = (ax_1(\mathrm{mod} \ n) \dots ax_{\varphi(n)}(\mathrm{mod} \ n)) (\mathrm{mod} \ n) \\ = (ax_1 \dots ax_{\varphi(n)}) (\mathrm{mod} \ n) \\ = (a^{\varphi(n)} x_1 \dots x_{\varphi(n)}) (\mathrm{mod} \ n) \end{align} 注意$x_i$与$n$互素，故$a^{\varphi(n)} \equiv 1 (\mathrm{mod} \ n)$。若$n$为素数，则$\varphi(n) = n - 1$，此时Euler定理退化为一个特例$a^{n-1} \equiv 1 \ (\mathrm{mod} \ n)$，这就是Fermat小定理。由Euler定理知若$e$与$r$互素，只需取$d = e^{\varphi(n) - 1}$即可有$ed \equiv 1 \ (\mathrm{mod} \ r)$，这就证明了模反元素的存在性。注意$r = (p-1)(q-1) = \varphi(n)$，于是$ed = k\varphi(n)+1$，其中$k$为某整数，于是 \begin{align} c^d (\mathrm{mod} \ n) = x^{ed} (\mathrm{mod} \ n) = x^{k\varphi(n)+1} (\mathrm{mod} \ n) \end{align} 考虑三种情况：若$x$与$n$互素，由Euler定理知$x^{\varphi(n)} \equiv 1(\mathrm{mod} \ n)$，于是$x^{k\varphi(n)+1} (\mathrm{mod} \ n) = x$，这就证明了$c^d \equiv x (\mathrm{mod} \ n)$。若$x$是$n$的倍数，显然有$x^{k\varphi(n)+1} \equiv x (\mathrm{mod} \ n)$，于是$c^d \equiv x (\mathrm{mod} \ n)$。 $x$为$p$或$q$的倍数但不是$n$的倍数，不妨设$x = mp$，则$m$必然与$q$互素，否则$x$将是$n$的倍数。由Euler定理知$(mp)^{q-1} \equiv 1(\mathrm{mod} \ q)$，进一步可得$((mp)^{q-1})^{k(p-1)} \times mp \equiv mp(\mathrm{mod} \ q)$，也即$mp^{ed} \equiv mp(\mathrm{mod} \ q)$，注意$mp$是$p$的倍数，于是$x^{ed} \equiv x (\mathrm{mod} \ pq)$，这就证明了$c^d \equiv x (\mathrm{mod} \ n)$。; 个人分类: 数学相关|164 次阅读|0 个评论

用python或perl语言简单验证RSA算法: 热度 1 cambaluc 2013-6-27 22:25; python或perl语言都提供了很方便的对大整数计算的功能,这在C或Fortran中不易实现,需调用相关的库或另编程序。多年前听公开课，一位老师给学生讲电子商务安全，涉及到公钥密码，讲得生动，但没公式没具体的例子，总觉不合适，后来想想，找几个数做例子因涉及到大整数运算，可能还真有点难度。有python或perl进行大数运算，就很容易了。 RSA加密算法是1977年Ron Rivest、Adi Shamir和Leonard Adleman一起提出的。所以别说数论或陈景润研究的没多大用，这就是最好的应用例证。找两个大质数p、q，设n=p*q ，r=(p-1)*(q-1)，找e与r互质,且er 找d满足(d*e) mod r =1,(mod为取余) (n,e) 就是公钥，(n,d)就是私钥，也可互换，设M为明文整数（把明文分解转换为小于n的数），C为密文则加密过程为 C=M^e mod n 解密过程为 M=C^d mod n (^表示乘方运算) 一、不编程用python验证设p=23,q=31,则n是23*31=713,r=(23-1)*(31-1)=660 设e=53,可找到一个d=137,(不想编程，用excel公式=MOD((A1*53),660))往下一拉就可找到(A列填自然数,B列写公式)。则有(713,53),(713,137)为公钥和私钥。如把公钥给对方，其对123加密：写123**53%713，加密结果为216。用私钥解密：216**137%713，解密结果为123。 123**53是582064223547422878717064247856117219999744776198031672118462507358927240593089706379581941870601919048920591883。216*137更是一个大数。二、用perl验证同上例选23,31,找数d perl -e foreach ＄d (1..1000){ print(＄d),last if 53*＄d%660==1 } 得出137。对456加密及解密 D:perl -Mbigint -e print 456**53%713 654 D:perl -Mbigint -e print 654**137%713 456 其实23,37都是很小的素数,数字游戏,也挺有意思; 个人分类: 算法|8033 次阅读|3 个评论

RSA算法的证明: maoxianmenlian 2012-11-26 14:48; $证明： ^{d}mod(p\times q)=M，其中M为明文，(e,n)为公钥，(d,n)为私钥$ $ ^{d}mod(p\times q)$ $=(M^{e})^{d}mod (p\times q) //模算术的性质$ $=M^{ed}mod(p\times q)$ $又\because (ed)mod(p-1)(q-1)=1，即存在整数k满足ed=k(p-1)(q-1)+1，因此，我们必须证明：$ $M^{k(p-1)(q-1)+1}mod(p\times q)=M$ $即 mod(p\times q)=0$ $即证： mod(p)=0和 mod(q)=0$ $先证： mod(p)=0，同理可得 mod(q)=0$ $ mod(p)= mod(p)-(M)mod(p) //模算术的性质$ $\because mod(p)$ $= mod(p)$ $= mod(p)$ $=((M)mod(p))\times ^{k(q-1)} //模算术的性质$ $=((M)mod(p))\times (1)^{k(q-1)} //费马定理+欧拉定理$ $=(M)mod(p)$ $\therefore mod(p)-(M)mod(p)=0$ $\therefore mod(p)=0，结果得证$ 参考文献： 1、《密码编码学与网络安全-原理与实践(第四版)》，William Stallings著，孟庆树、王丽娜、傅建明等译; 个人分类: 网络安全|3582 次阅读|0 个评论

3SAT算法研究及全面破译RSA密码: 热度 4 dulizhi95 2011-7-21 16:44; 3SAT 算法研究及全面破译 RSA 密码一个老美（应该是一流权威）给我建议，既然我的算法能在 PC 机上轻松地算出任何几万个节点的 Hamilton 环，那么，因为存在 known efficient reductions from RSA to Hamilton 环，我用此 reductions 方法就能够全面破译 RSA 密码系统，若能做到这一点，那就容易令人信服了，他还告诉了我迄今无人能解的 RSA 大数分解的网址。我马上要他告诉我这个方法，他给我寄来的是 3SAT 到 Hamilton 环的转换方法。他的方法非常麻烦，我把它简化了一下，但对 3SAT 的每个变量加子式，我仍然要用十几个节点来模拟( 不知道有没有更高效的方法？），而他的要用二十多个。也就是说，现在，在个人计算机上，我的程序能轻松地算出所有变量和子式分别在 1000 左右的 3SAT 问题。我说过，在目前中国最大的天河计算机上，我的计算量可扩大 100 倍( 若是指数型算法，那超大计算机对PC机也扩大不了几倍），故在该机上，可算任意的 200 万个节点图形的 Hamilton 环，以及 10 万个变量和子式的 3SAT 问题。问题是，我现在依然不知道有效的将 RSA 转化为 3SAT 的方法，我当然自己可以去推这个方法，但这样做一是需要花很多时间，二是不敢保证转化是高效的。所以，鉴于这个方法是公开的，非技术机密，还想请知晓的同行高人提供帮助或合作。; 3572 次阅读|3 个评论

他凭什么得了图灵奖？: 热度 3 tangchangjie 2010-12-7 10:07; 他凭什么得了图灵奖---我所认识的L . Adleman （3）（唐常杰） 1 幸运之星照耀有准备的头脑　　1976年，MIT的Rivest and Shamir 正在研究基于数论计算复杂性的新型密码技术；他们缺少扮演蓝军的研究者，Leonard .Adleman下列条件使得其他竞争者败下阵去： (a) UC Berkely的 EECS博士学位（文化底蕴与资质）； (b) 1975 -1976的三篇关于数论计算复杂性的论文（课题组急需的内功）； (c) 做过银行程序员，而且是编程高手（针对性极强的硬功）。　　　　黑白照片时代的RSA三剑客彩色照片时代的RSA三剑客　　　　　隐隐透出工作的疲惫笑意写在脸上，洋溢着丰收的喜悦　　Adleman本人在多年后（1996年8月）对NetWorker记者说，“我是在正确的地方，正确的时间，碰巧有正确知识的人”（ I was in the right place at the right time and, accidentally, had the right knowledge.）　　阳光好、土地肥、种子壮；基础、机遇、勤奋和经验，构成一个难能可贵的组合。　　舍他其谁也？　　他顺利地以讲师职称进入了Rivest and Shamir的密码技术研究团队,扮演蓝军，负责攻击。 2 RSA研究中的蓝军　　他们的攻防演习做了43 次，前42次蓝军胜，Adleman说，有些方案几分钟就破解了，有的用了几天。第43次，Rivest and Shamir，利用素数与整除性，构造了世界上第一个陷门单向函数，这个陷门之盾（详见本文科普部分），终于挡住了Adleman的才华之矛；用当时的计算机,要 long long time,成千上万年,才能破解。　　“红”方终于胜利了，这是红蓝双方的成功。　　他们先申请了专利，命名为 RSA公钥密码技术，在加州成立了RSA 数据安全公司，后来这个专利转到了MIT （猜测：因为这是职务发明，专利权归属学MIT学校）；1978年在顶级杂志CACM上发表了开创性的论文，于2002年三人共获图灵奖。　　 RSA最奇妙之点在于，互不相识的双方在不安全信道上，也能进行安全通信.其思想启发了今天的CA认证服务。因科普内容放在后面，这里暂用淘宝购物来比喻（实际上内涵不同），在淘宝上用支付宝购物，互不相识的买卖双方，通过第三方支付宝实现安全交易。　　说到这里，笔者想再次推荐在“ 基础、机遇、勤奋和成功 ”中中的哪个的积分公式，Leonard . Adleman正是这样一位基础好、路线对，勤奋而又有机遇的人，他成功了。 3 RSA公钥密码的用户感受先从用户感受来看这一发明的轮廓，把更深的原理放在附录2中，供有兴趣的朋友参考（其实，静下心来，用中学数学知识也能了解附录2的大概思想）。 ( a) 铸剑秘籍和鸳鸯剑传说中的铸剑师，得到了传说中的铸剑秘籍，制作了一对鸳鸯剑，形如y=f(x)和 x=g(y)；这两把剑刚好互为逆函数，即 x=g(f(x)), y=f(g(y))，真个是珠联璧合，天衣无缝；有下列特点： * 如果用y=f(x)加密，则可以用 x=g(y)解密，反之亦然； * 最终用户不必知道铸剑秘籍，就可使用鸳鸯剑； * 如只得到其中的一个，要想造出另外一个，知秘籍者易，不知秘籍者难，需要计算N万年。　　天下有这样的铸剑师，有这样的铸剑秘籍吗？　　有，而且办了公司，RSA公司就是这样的鸳鸯剑函数公司，批量生产（其生产流程参见附录2），对社会销售。一般人只能买鸳鸯剑函数，而买不到秘籍(正规名称：陷门、可理解为造钥匙的窍门，即一对秘密的大素数，参见附录2)。下面假定我们已经买回三对鸳鸯剑函数。 (b)公钥体制的大致思路。　　设x是明文，y是密文,有a,b,c三个户，他们从鸳鸯剑公司那里买回了自己的鸳鸯剑函数，鸳剑作公钥函数(让地球人都知道），鸯剑作私钥函数（妥善保管），用大写字母表示如下　　　　　公钥函数私钥函数　　　　　y=A(x), x=A -1 (y) 　　　　　y=B(x) , x=B -1 (y) , 　　　　　 y=C(x), x=C -1 (y) (c ) 用途1：举报罪犯。 a通过网络发信息x 给b，举报罪犯c；a当然不希望c知道，操作如下：　　a 把密文y=B(x)送给 B，　　b 收到密文y后，用x= B -1 (y)解密，即接受者用自己的私钥解密,得到明文x。　　即使c截获了y=B(x),也无法理解，因为要构造出函数B -1 ，相当于做因子分解，需要若干年。好像两位客家人用家乡话聊天，旁边的东北人即便听见了，也懂不起。 (d) 问题：举报后怎样领奖？如果是有奖举报，a凭什么领奖呢？ b说，的确收到了举报信息y=B(x)，凭什么说是a举报的呢？ (e) 增加发信者指纹，要点如下： * 为留下领奖凭据，a做了改进，把举报信息用改成 y=A -1 (B(x))，这好像在信封外再加一层信封; * b收到后，先用a的公钥y=A(x)函数脱去A -1 这层信封；注意，只有A自己才知道私钥函数A -1 (.. )，具有A -1 (…)这层信封的信息只能是A送来的，因此公钥密码体制还有防诬告，防抵赖的作用。 * b然后用自己的私钥B -1 解密。　以上就是公钥密码机制的思想，不需要微积分，需要若干数论中的关于整除性的定理；高三学生静下心来，也能理解思路框架，更多的技术细节的通俗解释在附录中，为通俗，有不到位的地方，请专家指正。 4《红灯记》要与时俱进传统的密码电报的密钥是密码本，需要单独的安全通道传送。截获与保卫密码本的斗争演绎出了许多可歌可泣的故事。现代京剧《红灯记》描写了抗日战争中，李玉和一家三代为保护密码本的故事，他们不怕牺牲、前赴后继，激励了几代人的革命激情。　　在公钥密码体制中，通信双方干脆公开自己的公钥，不怕敌人听到，而私钥静放囊中，不存在长途运送；所以，用人来传送密码本的故事，在未来战争中可能不会有了。　　爱国主义的主题是永存的，它将以新的形式存在和表达。在此意义上，《红灯记》也将与时俱进。　　附录1 天河一号超级计算机（10 15 次/秒）用穷举法分解200位大素数估计时间。通常的算法是 n=m (1/2) For (q=2；qn; q++)， If (q能整除m) { p=m/q; printf(“m分解为%d 和%d)\r\n”,p,q) } If (q==n) printf(“m本身是素数,不能分解\r\n”) 当m是一个200位的10进制整数时，for循环次数的数量级是10 100 ，用天河一号，每秒千万亿（10 15 ）次，还需要10 85 秒，假定一个聪明人找到一个好算法，把速度再提高十亿亿亿倍（10 25 ），还需要10 60 秒，一年不到10 9 秒，至少要10 51 年。（一年365x24x60x60=31536000秒 10 9 秒）附录2 陷门单向函数（鸳鸯剑函数）的制作下面的科普牺牲了严格性，希能使中学数学兴趣小组的朋友也看懂思路。 (a)双向函数 two-way function 　　三角函数y=Sin(x)的反函数是x=ArcSin(y)，对于基本三角函数，给定原来的函数f(x),不难找到反函数 f -1 （y）, 因为正反都容易，映射来去自由，所以称为双向函数。 (b) 单向函数 one-way function 　　单向函数y=f(x)有下列性质,如果给定x 1 ,求y 1 =f(x 1 )容易；反过来给定y 2 , 解方程y 2 =f(x) 求x 2 很难。（作为科普，就不费力地描述这个“很难”到底有多难）。乘法X与逆向运算因子分解InvX就是一对这样的冤家。给定两个100位的大素数p,q ，做乘法容易，对200位的合数做因子分解是一件难事（若干年）。附录1给了一个粗略的估计，如果用笨笨的穷举法，用高级计算机分解200位的大数，需要10 u 年，如果某聪明人吧方法加快了十亿亿亿（10 25 ）倍，只不过用v=u -25 取代了u，还要10 v 年。不解决根本问题。 ( c) 铸剑秘籍和鸳鸯剑传说中的铸剑师，得到了传说中的铸剑秘籍，制作了一对鸳鸯剑，形如y=f(x)和 x=g(y)；这两把剑刚好互为逆函数，即 x=g(f(x)), y=f(g(y))，真个是珠联璧合，天衣无缝；有下列特点： * 如果用y=f(x)加密，则可以用 x=g(y)解密； * 最终用户不必知道铸剑秘籍，就可使用鸳鸯剑； * 如只得到其中的一个，要想造出另外一个，知秘籍者易，不知秘籍者难，需要计算N年。 (d) 陷门单向函数 one-way function 　　RSA三剑客就是那个铸剑师；而那个秘籍，又称为陷门（或窍门），是一对大素数。为了做一对鸳鸯剑，需秘密地选一对数量级为10 100 的大素数p,q ，做乘法 n=pq；　　利用的整除性技术构造两个依赖于p和q的整数e 和 d ，(技术细节,参见 )， e 和 d 所藏身区间的大小的数量级是10 100 （穷举法搜索就死心了吧）。　　有了n,e, d,造出这一对互逆的鸳鸯剑（函数），一个做私钥，一个作公钥，如下： y = x e mod n , （做私钥） x = y d mod n （作公钥）　　教科书上，利用e,d的具体细节，可验证：x=（ x e mod n）d mod n= x ，即明文x 用鸳剑函数加密，而用鸯剑函数脱密，最后还原为明文，不失真。　　构造不是很复杂，计算起来也不慢；　　如只得到了鸳鸯剑之一，想造出另外一个，很难。因为关键是在数量级为10 100 的区间中找出 d或e, 但这需要把n分解为素数p,q, 如附录1的估计，这是难计算问题，现在的技术，要若干年。利用RSA原理，可开展鸳鸯函数租售业务，一般人只买鸳鸯函数，而不买秘籍(或陷门、即那一对素数)，这样，自己都不知道破解法，破解法被窃取的隐患就少一个。买回的鸳鸯剑，一个做私钥，自己保管好；一个作公钥，让地球人都知道。参考文献　 Leonard M. Adleman, Kenneth L. Manders: Computational Complexity of Decision Procedures for Polynomials (Extended Abstract) FOCS 1975: 169-177 　 Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials STOC 1976: 23-29 　 Leonard M. Adleman, Kenneth L. Manders: Diophantine Complexity FOCS 1976: 81-88 　 . R. Rivest ， A. Shamir L.Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM, 21(2):120-126,(February) 1978. 　博友 dailiangren （评论4）推荐的参考资料 ttp://zh.wikipedia.org/zh/RSA 加密演算法关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照 2 图灵奖得主是怎样炼成的-----侧应钱学森之问 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它系列博文的入口唐常杰博客主页科学博客主页; 个人分类: 科普札记|21977 次阅读|20 个评论

图灵奖得主是怎样炼成的--侧应钱学森之问: 热度 1 tangchangjie 2010-12-6 10:13; 图灵奖得主是怎样炼成的--我所认识的L.Adleman (2) （唐常杰）　钱学森问：为什么我们的大学培养不出杰出人才？本文不说“为什么不能”，而说“怎样能”，从另一个侧面响应钱学森之问。将介绍广谱多产且高质的科学家L .Adleman；他幼时非神童，青年时见异思迁，如他自己所说，“非常幼稚和不成熟”，但最后，成长为图灵奖得主。　　看看他的成长环境，看看他的人生经历，看看杰出人才的钢铁是怎样炼成的。　赶上了美国的盛世享太平伦纳德·阿德曼（Leonard M. Adleman）于1945年12月31日出生在一个由电器推销员和银行出纳员组成的犹太家庭。当时二战已结束,美国的综合国力和国际地位都处于一个历史区间的峰值，二战中备受艰辛的犹太人扬眉吐气,憧憬着幸福和繁荣。他的童年是美国经济科技和教育的成长期。　　中国的同龄人可没有那么好的童年运气。65年前，就在阿德曼出生的那一天，五星上将马歇尔在中国过了他退休后的第一个生日，65岁生日，（65后又一个65,真是无巧不成文）。　　马歇尔来华目的不是享受退休生活，而是筹备国-共-美的三方会谈和军事协调。时值重庆谈判后两个多月，神州大地战雨欲来风满楼，那以后的三年中国故事，地球人都知道。（本文将借用电视剧中的双线索方法，做四次对比和感慨，希望不影响主线。）　　　　好变好奇一少年他的小学和中学时期的故事鲜见报道，我们只能猜测，这位聪明好奇、见异思迁的犹太少年的生活是怎么样呢？像马克吐温笔下汤姆，沙耶，还是像哈克，贝利芬？从已知的佚事，用上一点关于人生履历数据流的聚类方法，有理由猜测，那一定是充满了兴趣、好奇和探索。高中的英语老师辅导他读哈姆雷特，启迪了它，他的生活和理想仍然充满了青春的变数、不确定和见异思迁。在电视上看了Mr.Wizard，他就想当化学家，听了远房亲戚的鼓动，又想当医生，上大学时，游移踌躇中选定了数学，天生一副探索者的身子骨。　　 I was fun. 下面这段他的话也印证了上述猜测：“Things have never change from when I was little child --going out and doing chemistry…. It never changed. I was fun then, it was fun now （从小就没变，走出去。作化学家……,那时充满了兴趣和好玩，现在也充满了兴趣和好玩）。　　不知道他像不像罗大佑在《童年》中唱的，想着“为什么太阳总下到山的那一边”，思考着“山里面有没有住着神仙”，那就是个“这么好奇、这么幻想的童年”。　　　　　　见异思迁一青年。 1963年，他毫无悬念地进入了名校UC Berkeley，作为本科教育的第一站，在游移和思迁中，放弃了小时候憧憬的化学家和医生、阴差阳错,不，应是阴 “ 合” 阳 “对” 地、正确地选择了数学。　　在美国，职业和个人也是“你选择了我，我选择了你”，设若Adleman去当医生，可能世界上会多一个名医，RSA这项发明则可能被延迟，其第三个字母 “A”也可能改变了，而DNA计算要等另外一个聪明勤奋和运气的、难能可贵的基因组合了。　　大学读了5年，1968年获得了UC Berkeley数学学士学位，顺而且爽。　　　　在中国的同龄人就没这样顺爽了，那一年，是文化革命第三年，造反派开始退场、刘少奇被开除出党，工宣队、军宣队进校，中国的在校大学生开始到军垦农场，…… 　　　　此后，伦纳德·阿德曼，浅试了闯荡社会，做过银行程序员，练成了编程高手（这是他后来扮演RSA蓝军的硬功），一度想进旧金山州立学院攻读物理，刚录取，还没注册，就又改了主意。　　他说，那时“不喜欢做物理实验，喜欢思考理性的东西。“ 　　见异思迁和志存高远（或可用有点贬义的词汇好高骛远，较难界定）是读研前的小伙子们的特色状态，未来的图奖得主L.Adleman也莫能其外，如他自述，当时是“难以置信的幼稚和不成熟 ”。　　短时间的且有益的晃荡，练就了程序员高手水平之后，又回到了UC Bekerl攻读博士学位，夯实了坚实的数学内功， 1976 写出了一篇关于数论计算复杂度的论文，获得了电子电气和计算机科学（EECS）的博士学位。　　　　那一年的中国，发生了太多太多的事情：例如唐山地震，例如四人帮垮台，……, 痛苦和新生相继，像凤凰涅槃；艰难和希望交织，似登山观日。在美国的L.Adleman拿到了博士学位，而同龄的中国人求索和思考的主要是“中国向何处去”，还不是学术和技术。…… 　　　　人生的辉煌一般地，博士生在指导下做科研，获得了博士学位，才算是独立研究生涯的正式开始。　　1976年来到MIT数学系，开始了人生的辉煌，1977做讲师，他加入了RSA公钥密码研究团队，扮演蓝军，为这一图灵奖成果做出了卓越贡献（本系列博文之三详述）。　　1979晋升副教授，在美国，一般讲师需要5-6年才能晋升副教授，在顶级大学MIT，能两年做到副教授。殊为不易。　　1980年到南方加利福尼亚大学（USC），1981年发表从合数中鉴别素数的算法，Adman本人认为这项成果超过了他在图灵奖成果RSA中的贡献，是他一生的骄傲，他曾说过，此项成果或可刻在自己的墓志铭上。　　1983升教授，他的学生弗雷德.科恩（Fred Cohen）那年写出了能自我繁殖的计算机程序-计算机病毒，在讨论班上演示时， Adleman命名其为计算机病毒，一不小心，成了计算机病毒的教父；稍后，发表了深刻的论文。　　　　那一年，中国迈开了改革开放的步伐，一批利用联合国贷款的中国学者和学生到了USC，为弥补因那特殊年代造成的十年差距，我认识的一些中国学者和学生特别勤奋；为了晚上能半费或免费上机，时不时地在星期二四六只打个盹，星期一三五才睡个6小时的“好”觉；只因中国刚打开久闭的窗户，满眼新奇，令人亢奋。　　　　1985 年，他继Seymour.Ginsburg之后，成为Henry Salvatori讲座教授, (一种荣誉或位置，退休前恒有不须申请的大额科研基金）,笔者目睹了他们都每周70小时工作方式。　　1991年发表了关于艾滋病免疫机理的数学模型的两篇论文：建立了数学模型描述艾滋病病毒破坏免疫力的数学过程。　　1994年在Science上发表了开创DNA计算领域的论文（见本系列博文之四）　　2002年，他成为第三十七位图灵奖(2002年)获得者（R、S、A三人共享）；如今，接近65岁了，还孜孜不倦的思考，如他自己所说，有时一天工作16小时，连续几周甚至几个月。在著名的DBLP文献库上可以看到，从2002年到2009年他在判定性问题，Infinite Ribbon问题，组合优化方面还有署名第一的文章发表。　　 L. Adleman的典型语录　　我是理论计算机科学家，是一生都异想天开的人。　　把有限的智力资源花在正确的问题上.(right question to spend your valuable limited intellectual resources) 没有好问题时，我情愿读魔幻小说。不是忙碌于平凡的工作而错失重要问题的机会。　　感谢这个的国度给我的科研自由,允许我按照我认为的最好方式来工作，　　当我是小孩子时候，科学是有趣的，现在还是有趣的，我惊奇这个社会允许我这样继续工作一生且给了我好的生活条件养家活口。　　可以每天16小时，持续几个月或几年去攻克一个问题，有时是如此的专注，以至于有人进我的工作室时，会把我吓一跳。　　从另一个角度议论钱学森之问钱学森问，为什么我们的大学培养不出杰出人才，L. Adleman的例子,从一个侧面做了响应。在科学成就上，L .Adleman达到了钱学森所说的杰出人才标准，有过之而无不足。　　L .Adleman不是神童，不是金钱的富二代，也不是知识和教育的富二代；不是少年老成，也非从小立大志。如他自己所说，他曾经幼稚，曾经很不成熟，曾经见异思迁；但他最终成长为图灵奖得主。从他的成长过程中，似可悟出：　　 1 和平、稳定与经济发展的盛世是科学文化人才批量出现的最重要条件；上面用类似于视剧的双线索方式，对比了Adleman及中国同龄人的条件。类似于Adleman成长的条件，在中国晚到了30多年。想告慰钱老钱学森大师，我们再稳定地发展十年、二十年（也给我们大致相同的时间，这才公平）；先小康了，然后又受教育了的中国人，才有足够的时间去反思、检讨和改进教育体制，中国的杰出人才也会批量地出现。　　科学文化人才的零星出现，可以靠家庭环境、个人奋斗和奇遇（如武侠人物）实现，而批量出现一定要安定繁荣的社会大环境。培养人比发展企业更花时间，以中国体育为例，两代人吃饱了、吃好了，第三代人的身体素质上去了，金字塔的底层又广又实，再加上正确方略，奥运亚运冠军就批量出现了。　　2 对见异思迁的宽容、对研究兴趣的尊重，是对潜在人才的爱护；　　3 素质教育和通才教育出大师；　　4 前辈大师对年轻人的扶持，“名师+明师”出高徒，这里的“明”，是开明的明；　　5 很多科学家都曾为经费伤透了心，如果能不为科研经费发愁，不年年为申请花去 N％的精力，那真是愉快科研，那真是善莫大焉；　　6 神童和学前教育并非必要条件，知识的富二代也不是必要条件。　　　　还有更多的“悟”，请博友们补充。关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照 2 图灵奖得主是怎样炼成的-----侧应钱学森之问 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它系列博文的入口唐常杰博客主页科学博客主页参考文献　 .Leonard M. Adleman On Distinguishing Prime Numbers From Composite Numbers, Annals of Mathematics, 117, 173-206, 1983. (with R. S. Rumely and C. Pomerance). Leonard M. Adleman，An Abstract Theory of Computer Viruses ，Leonard M. Adleman，Lecture Notes in Computer Science, 1990, Volume 403/1990. 　 Leonard Adleman, David Wofsy: Selective Depletion Of CD4+ T-Cells Elicits The Production Of CD8+ T-cells In Mice. Abstract. VII International Conference on AIDS. Flourence, Italy, (June) 1991. 　 Leonard Adleman, David Wofsy: T-cell Reconstitution Following Selective Depletion Of CD4+ T-cells. Abstract. Clinical Research, 39:2, 1991 　 Leonard M. Adleman Molecular Computation of Solutions To Combinatorial Problem, （Science, 266: 1021-1024, (Nov. 11(Nov. 11) 1994.); 个人分类: 人物故事|17471 次阅读|16 个评论

一位狂热科学家的工作照: 热度 1 tangchangjie 2010-12-6 08:36; 一位狂热科学家的工作照 -- 我所认识的L .Adleman (1) （唐常杰）　　下面这张照片的英文标题是 “A picture of the mad scientist at work“（一位的狂热科学家的工作照，也有人曾把mad翻译为疯狂）。灯光下，图灵奖得主 Leonard Adman（伦纳德·阿德曼）正在南加利福尼亚亚大学的DNA计算实验室中充满激情地工作。他是一位广谱多产的科学家，在他的下列成果中，普通人若幸有其一，就足以成名： a) 第三十七位图灵奖获得者(2002年，RSA ）（详见本系列之三）； b) 计算机病毒的教父（1983），他的学生 Fred Cohen,于1983年展示了一个能自我复制且能传染的程序。Adleman在讨论班上，联想起科幻小说，灵感突发，给程序命名为计算机病毒。稍后他们发表了深刻的论文。（详见本系列之四）。 c) 客串艾滋病免疫数学建模，提出了一个反常规的方法（详见本系列之五）； d) DNA计算的发明人。1994年在Science 上发表了开辟这一领域的论文（详见本系列之六）。 e) 在数论方面，提出了判别部分素数的方法；他自认为这一工作胜过在RSA中的贡献，准备刻在墓志铭上。 f) 是电脑黑客的影片的科学顾问，如Sneakers（《大盗》或《通天大盗》）等。……. 　　人们曾经认为，产生像牛顿，罗蒙罗索夫那样的广谱多产高质的科学家的时代绝对地一去不复返了，读了这个系列博文，也许会考虑去掉“绝对”二字。　　他是一位不知疲倦的科学家，如今接近65岁，还孜孜不倦的思考，如他自己所说，多年来，坚持第一线科研，有时一天工作16小时，连续几周甚至几个月。在著名的DBLP文献库上可以看到，从2002年到2009年他在判定性问题，Infinite Ribbon问题，组合优化方面还有著名第一的文章发表。　他是我认识的科学家。（上世纪）八十年代初，笔者曾在美国洛杉矶的南加利福尼亚大学（USC）计算机系学习，那几年，该系在全美计算机专业的排名区间是，相当不错。该系奠基者是形式语言和数据库理论先驱Seymour Ginsburg，他的研究团队中有三位外来学者：田中克己（Katrumi Tanaka，现日本著名数据库专家之一），现在颇有名气的Rich Hull和笔者。　我与田中的工作室与L.Adleman的办公室相邻，用数据挖掘的行话，我们是Adleman的两个最近邻（2-NN）。在走廊上、在讨论班上，在Ginsburg的办公室里，与他时有交流。　　在那如歌如诗如赛场的岁月中，田中和Hull非常勤奋，笔者的上千个日日夜夜最后也凝聚成了在Theoretical Computer Science上的三篇论文。　　当时的L.Adleman已是RSA发明人之一，继Ginsburg之后，他也成为讲座教授。我们像仰参菩提树一样向他请教。他是高人，指点之后或许会淡忘，但受教者会铭记终生；也许，他还记得给我们论文支招，还能记得对我的论文思路的“Wild and beautiful”考语。忆海钩沉却为何？笔者把过去的几个PPT改写成此系列博文，虽然是改写，也忙了一个周末；有下列目的： a) 介绍一位多才多艺、广谱多产且高质的科学家； b) 从另一个侧面来响应钱学森之问。在培养杰出人才方面，且不说“为什么不能”，而说“怎样能”，看看杰出人才是怎样炼成的； c) 纪念Leonard Adleman的，在月末的65周岁生日（12月31日）； d) 也许是老之将至，最近常忆起S.Ginsburg，他给我们讲过一些Leonard Adleman的轶事，写出来，方不负师生一场的缘分； e) 回答在博文 “中美学生思维差异、RSA蓝军以及盗梦算法争议与实验 ” 中关于的RSA蓝军的一个问题。关于 Leonard . Adleman的系列博文　　 1 一位狂热科学家的工作照 2 图灵奖得主是怎样炼成的-----侧应钱学森之问 3 他凭什么得到图灵奖？（在RSA中的贡献，+RSA科普） 4 一不小心，成了计算机病毒的教父 (科普） 5 奇思妙想，客串艾滋病免疫研究 (科普） 6 沧海横流，谁开辟了DNA计算? （DNA计算简介，科普）其它科普博文六度分隔的扩展应用--穿越几次见欧拉（科普+科幻）大数据与马航MH370 其它系列博文的入口唐常杰博客主页科学博客主页; 个人分类: 人物故事|29183 次阅读|20 个评论

中美学生思维差异、RSA蓝军以及盗梦算法争议与实验: tangchangjie 2010-11-6 14:47; 中美学生思维差异、RSA蓝军以及盗梦算法争议与实验 ---- 盗梦空间科普札记之四 1中美学生思维方式差异曾见过一文，议论中美学生思维方式差异，说：在某国际学生夏令营，数学老师出一个题目：“一昼夜中时钟的上的分针和时针重合多少次？” 中国学生善逻辑思维，立即拿笔画图计算；美国学生善观察，取下手表拨针做实验；因为其中还有一点思维转弯,如果规定时间比较短，两种方法都可能出错，但从统计的角度看，美国学生的实验法出错率会少一些。我更喜欢两种方法的结合，先观察自然现象或实验结果，然后上升到理论解释。一般非纯理论的科学家做研究都不会拒绝这种方法，就是理论性很强的科学问题，例如相对论理论研究，也要做思想实验、也要用观察去验证理论。 2 深思者提出的问题言归正传，回到关于盗梦空间的科普话题。上篇博文递归梦的判定性与图灵停机问题--盗梦空间科普札记之三引起了讨论.上篇博文主要结论是：　　命题递归梦是不可判定的，即不可能设计这样一个通用程序P，它能检查一切的梦串对M,s对应的那个梦是否会醒过来。　　博友的讨论很深入、认真。一些深思者提出了比较深刻、比较难回答的问题。例如。上篇博文的第8条评论给出了质疑，大致要点包括：　　 (1) 证明感觉像是悖论 ; (2)是否具有实际意义？(3) 唐文的程序A1看起不像递归，评论者自己还给出了一段自称是“ 无聊”的程序A2（如下），说与A1等效: bool M ( s) { ...　　 bool OK = !(M(s); ....; return OK;} } 要求分析是否悖论或其意义，还单独发了博文，详请可点击这里。想不到几篇娱乐兼科普的博文引出了许多内行来讨论，分析这些问题出现的原因，大致有： (a)问题的确比较搅人； (b)笔者解释得还不够细致、不够通俗。虽在回复中做了一些简答，还不够满意；因为，每年这一堂课后，都有类似的问题；这些问题有一定深度和难度，非深思者提不出来，不深思也回答不了。怎样改进这一部分课程的教学呢？思考正纠结，这个问题被博友的实验解决了。 3 实践是检验科普博文的方法之一今天，博友liuhuimin 在上文的讨论区发了评论（第13条），给出了试验程序，这里稍改排版格式，括号中的注释是本博主加的。他们的实验一方面回答了第8条评论给出的质疑，说明可能有误解或理解偏差。重要的是，提供了一个好例子。以后讲课到这部分、出现类似问题时，就可用这个例子。liuhuimin 的评论（上篇博文第13条）如下：我们兴趣小组热烈讨论了8楼的问题，开始（表决）是3:3；后来做了实验，在VC 6中写了程序做实验验证，果然，如唐老师说的两种结果。两个程序和运行结果如下： (a)无递归深度控制时： bool test_dream( ) { printf("检查盗梦空间递归程序\r\n"); test_dream( ); return true; } 运行结果，用VC6中跟踪工具，可以看到出错消息： Unhandled exception in Test (MSVCRTD.DLL):OXC0000FD:scak Overflow 出现了栈溢出。博主注：博主重复了这个试验，在Win7上等比较稳定的系统，系统能处理exception，只死去程序本身（而不会死机）；程序是错的，不能正确运行；当然也就不会推出上文评论8所谓的悖论了。 (b) 有递归深度控制的如下： bool test_dream2(int N) //有递归（深度）控制 { bool results=true; if (N==0) return true; else N--; printf("检查盗梦空间递归程序\r\n"); results= !( test_dream2(N)); return results; } 运行结果： N=偶数结果为 True; N=奇数结果为 false. 不会推出矛盾，也不会推出悖论。博主注：笔者重复了这个试验，程序能正常，但是，会按递归的层次数量的奇偶性给出确定的结果，没有出现质疑者设想的悖论。两个程序合起来，说明那个自称“无聊”的算法A2，不等价于博主给出的算法A1。这些讨论回答了那一个关于“递归梦是不可判定的” 质疑。有兴趣的内行，如果想看细致的讨论，可参考上篇博文及其评论之8---11等条目，其中，凝聚着博友们的深思。这个兴趣小组先做实验、观察事实，再用理论用模型去解释事实的方法特别可嘉。说明他们的在研究方法上已经上路，而导师招生时，可能都会喜欢这样的学生。 4 RSA算法研究过程中的蓝军就像论证三峡工程一样，质疑者扮演蓝军，提出了可能的问题，把可能的问题都考虑了，工程就可靠了。在这一意义上，质疑者都是贡献者。在RSA公钥加密算法研制过程中，Ron Rivest、Adi Shamirh 扮演红军，负责防卫；Lenonad Adleman扮演蓝军，负责发攻击和破解；RSA目前仍然最有影响力的公钥加密算法，能够抵抗到目前为止已知的所有密码攻击，RSA取名来自开他们三位研究者的名字，而Adleman扮演蓝军之功不可没。其实，对上面博文讨论的问题，笔者以前的认识还不是很深刻，通过这次回答和程序实验，理解也加深、感谢质疑，欢迎继续质疑。在这个义上，实践是检验真理的标准，也是检验科普博文的标准。参考文献 Material: Sipser, Michael (@MIT), Introduction to the Theory of Computation. PWS Publishing Company, 1997 ,机械工业出版社出版，2002。 ) Michael Sipser (麻省理工学院)，计算理论导引(第二版), 中译本 ,唐常杰陈鹏向勇刘齐宏译，机械工业出版社出版，2006.7 相关博文：　　盗梦空间科普札记之一：梦里乾坤递归深，醒来可知在哪层 ? 盗梦空间科普札记之二：用科学家的目光看电影；盗梦空间科普札记之三：递归梦的判定性与图灵机停机问题；盗梦空间科普札记之四：中美学生思维差异、RSA蓝军以及盗梦算法争议与实验　可计算理论是门修养课-研教散记11 （去年的博文）；　知识的共创和共享-研教散记（4）可在出版社网址下载课程的PPT，1600页面）　; 个人分类: 科普札记|11383 次阅读|12 个评论

更多...

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

关闭 安全验证

标签: RSA

相关帖子

相关日志

关闭安全验证