标签: 加密

细分加密方法

sjdkx 2020-8-27 18:23

　　加密破解中穷举攻击是比较常用的有效方法，这是由于用户密码的长度是有限的，当穷举了这些可能的密码输入后，正确的密码一定包含在输入之中，相应的正解也包含在破解过的密文之中，这时你只要找到明文破解也就成功了，前提是你必须认识明文你才有可能找到它，明文也许是文本文件，或exe文件或媒体文件等等，文本可以直接看懂，其它的都有各自的特征需要识别确认，这些都需要观察文件的上下文联系来判断到底是什么。 　　细分加密顾名思义，它不是通篇加密，而是一小段一小段的加密就是将文件分成若干小段分段进行加密，当然解密时也是分段处理的，这样的好处是当段落小到一定程度时，你无法对这些小段做上下文联系的判断，也就是你不清楚它们的含义，这样也就无法完成穷举攻击了，尤其是细分到字节时，但是分的越细计算量越大耗时越多，所以需要权衡最佳配置。 　　细分加密的作用主要是抵御穷举攻击，对分析法攻击的作用是显而易见的就不多说了。

个人分类: 密码学相关|1546 次阅读|0 个评论

北斗短报文求助最有效的压缩方式，以便应用在油田，矿山，海洋探测管理通讯等领域

yangxintie1 2020-8-26 09:33

北斗短报文可以传送1000字节，实际传送5次完成 有什么办法加大压缩力度，那个朋友做这个，那位朋友在 加密，压缩及码表您是否也有兴趣，请和我联系（1185824765@qq.com） 北斗终端急迫需要，以便把此技术用在油田，矿山，海洋探测管理通讯 西北工业大学，航空学院，杨新铁

个人分类: 胆剑篇|2200 次阅读|0 个评论

区块链加密数字货币可能没有防御战

热度 1 outcrop 2019-6-24 11:17

最近随着Facebook计划推出Libra区块链加密货币的消息，区块链加密数字货币再一次走进大众的视野；相关的解读文章比较多，我就尝试用大白话稍微做一个介绍。 区块链加密数字货币有三个核心的概念：区块链、加密、数字货币。区块链指的是不可篡改（篡改代价极大）分布式账本，全世界每一个全节点，都（尽量）实时同步着同样的账目，比如全球比特币节点的账目，一定是一致的。加密指的是非对称加密算法，公钥可以用来作为钱包地址，私钥可以用来签名交易，加密消息等；比如Aeternity项目采用了ED25519椭圆曲线算法来实现公钥私钥。数字货币则比较好理解，就是字面意思。 作为数字资产，区块链加密数字货币首先要安全，需要有共识算法来作保障。所谓共识算法，就是在数学算法上来解决一个问题：人们凭什么相信你这个数字货币是可靠的？目前流行的共识算法有POW（工作量证明）、POS（股权证明）、DPOS（授权股权证明）、BFT（拜占庭算法）等。比如比特币采用的共识算法是POW（工作量证明）。 根据价格的稳定性，目前市面上流通的数字货币可以分为两种：稳定币和非稳定币。稳定币如TUSD、USDT等通过公司铆定的法币美元代币。非稳定币如比特币，随着供需的变化，价格变化极大。 前面是关于区块链数字货币的基础知识，回到最近的主角Libra。技术实现上，Libra采用BFT共识算法。从发布的测试网络来看，功能还很简单，支持命令行工具，还没有api、sdk等外围支持，应该是以技术展示为目的。 上周（6月18号）Facebook发布的这款区块链加密数字货币的白皮书，目标宏大，尝试锚定一篮子货币。这个起步，很容易让人联想到美元锚定黄金，然后抛弃黄金单飞的往事。由于互联网的无地域限制，Libra一旦在部分经济强势地区（如美国）流行，积累到一定的社会能量后，只要不断网，Libra可能率先直接取代部分小国家的法币，接管其铸币权。成长后的Libra对其他国家法币的冲击力，可以远甚于美元。 相对于微信、支付宝等中国强势的互联网支付产品，Libra借助区块链技术的一个明显优势在于账目的透明性：账目在每一个节点都有；这一点对很多用户来说，意味着透明、安全、可靠。 Libra的最初阻力，可能源于欧美等国家自身；不过从预留71个席位来看，这是对传统金融行业的示好，虚位以待他们的加入。一旦稳定的联盟形成，那么在下一代互联网下，区块链+5G，可能爆发出极大的金融能量。只要不断网，很难拒绝。 中国目前的移动支付站在世界前沿，但对周边以及全世界的渗透力，仍然有限；区块链加密数字货币技术上目前已经比较成熟，阿里腾讯等公司有天然的技术和应用优势。但如何走出去，可能还需要加紧出台相关策略。 区块链加密数字货币如互联网一样，没有地域限制；对中国来说，短期的防守可能没问题，但CNY想要想走向全世界，区块链加密数字货币还需要积极努力进取。

个人分类: 计算机应用技术|4335 次阅读|2 个评论

未知数加密理论

sjdkx 2019-4-28 15:53

　　信息加密技术说白了就是信息隐藏技术，原文件如果是可以看懂的东西，加密后就看不懂了，也就实现了保密，经过加密的信息在存储、和传输中就安全了，他人得到了也看不懂。 　　用什么来隐藏信息，没别的东西也是数据了俗称密钥、或密匙，如果你手头有个加密软件，你想看看这款软件密钥做的怎么样，你可以这样让它加密一个空文件，也就是内容全部是零的文件，这时密文全部为密钥数组所占据，你可以检验密钥数组的优劣。如果密钥数组是乱码数组，并能通过NIST检测就认为密钥数组是好的，否则就是差的。 　　其实密钥数组的关键不是其随机性，而是其未知性，这要你用尽所有办法也不能得到任何密钥数组的信息，那这个数组就是好的，而不管随机性好不好都能起到严格的加密作用。 　　　　　　　　　　明文 算符 密钥 = 密文 　　从这个式子可见，如果明文未知、密钥未知、密文已知的情况下是二元一次方程是不可解的，即使知道算法的细节也是如此。 　　尽管如此，为什么穷举攻击能够得手呢？这是软件自身缺陷造成的，本来软件对所有真假用户密码都是对等的，但某些软件却让其不对等，你的用户密码是真的软件一种反应，是假的软件另一种反应，造成了软件成为密码的筛选器，这样穷举攻击就得手了，winrar的加密就是这种例子，所以加密软件不要自取灭亡出卖自己。 　　即使没有上述缺陷，加密仍不能保障信息绝对安全，这是由于明文本身的特征造成的，因为正解存在于众多的解之中，尽管很困难只要功夫到了仍可以辨识出来。这个问题的解决，笔者认为需要多次加密，至少二次加密才能确保信息安全。道理很简单，第一遍加密就破坏的被加密文件的特征而形成乱码文件，第二次加密是对无特征的乱码加密，只要你不记录任何数据，破解时将没有方向所以不能进行，这样数据就安全了。

个人分类: 密码学相关|1898 次阅读|0 个评论

随机函数加密信息

sjdkx 2019-3-5 13:30

　　随机函数所生成的数据的随机性并不太好，这是由于其生成机制所造成的，例如数据生成于同样的公式或条件，被称为伪随机数，要想将数据当成密钥，人们觉得那是不可靠的，就是因为其不够随机，前面的帖子也说过如何将不够随机的数组通过随机排序改造成随机数组的方法，但是实际上并无必要，因为具体应用时，这些数据并不是单独出现的，而且还通过了数据加工最后的结果体现在密文了，所以你从伪随机数组的随机性不好这些缺陷得不到被加密信息的任何东西，所以加密是相对安全的，想通过分析法破解密文也是做梦，因为其中未知的东西太多了。 　　为什么说是相对安全呢？这是因为如果你掌握了一些明文的特征可以通过穷举法来攻击密文，注意必须是掌握一些特征否则穷举攻击就没有了方向，也就不能成功。如此是不是加密就没有安全的方法了？非也，只要破坏了那些穷举攻击的依据，穷举攻击就无的放矢了，多次加密就能实现这些，如果使用不同性质的加密软件效果会更好。 　　分析法和穷举都不能得逞你的数据就安全了。

个人分类: 密码学相关|1756 次阅读|0 个评论

混沌保密通信方向如何选择NSFC申报代码？

lcqq 2019-1-27 09:48

http://npd.nsfc.gov.cn

3931 次阅读|0 个评论

加密算法和加密方法

sjdkx 2018-11-16 00:01

　　好的算法可以对抗分析法攻击，但仍然是不安全的，因为攻击者可以用穷举法，因为用户密码是有限的，所以只要有足够的时间都是可以攻破的。这是明文有特征的情况，但是如果明文无特征你就无法攻击了，因为你连目标是什么东西都不知道就没有办法进行判断和攻击。所以说光有好的算法是不够的，还要有好的方法。 　　好的方法也就是对抗攻击的策略，利用现有条件使安全性最大化，多次加密就是实现安全加密的好方法，最简单的就是二次加密了，它的作用是第一次加密就将明文的信息打乱了，成为没有特征的乱码，而对乱码加密是不可破解的，故第二次加密完成后信息就安全了。

个人分类: 密码学相关|1509 次阅读|0 个评论

安全加密

sjdkx 2018-10-30 19:37

　　机密的东西为了安全起见，对其进行加密，所谓安全加密是指不能被破解的加密。 　　有人认为凡是加密都能被破解，那是愚见。能被破解都是自己不严谨造成的。 　　加密实际就是一种数值变换，一般都是制作一些随机数组作为密钥进行加密的，密钥数组的质量很重要，如果密钥数组能通过NIST检测就算是比较好的。 　　先看下面的例子：有一个乱码组成的文件，我们对这个文件进行加密，结果依然是乱码。这样的文件就是不可破解的。因为你无法判断解密是否成功 。除非你事先对乱码文件进行了保存，或测量其CRC值，通过比对得到解密是否成功的结论。其实只要密码正确，密文完好无损解密必然会成功的。密文也是一种很娇气的东西，任何损坏都可能造成不能解密的结果。由此得到结论：乱码文件不可破解。因为你没有衡量标准。 　　有了上面的基础，安全加密就非常容易了，最简单的方式就是对明文进行二次加密。第一次加密就使明文变为乱码文件了，再次加密就完成了安全加密。只要密文完好、软件完好、密码正确，就可以保证解密成功。即使量子计算机来了也不怕，它不是不好解密的问题，而是不能解密对什么攻击都不怕，因为没有前进方向，再强的运算能力也无用武之地。 　　如果明文本身就是乱码那么一次加密就是安全的。 　　传统加密软件的致命缺陷：传统加密软件能够将本来不可破解的乱码文件（无任何特征）变为能够破解的东西。它是如何做到的呢？原来它是将明文特征保存在密文中，当你解密时一旦发生错误，它将报告你错误。这样做的结果是对于任何文件使用穷举攻击都能被破解，因为密码长度是有限的，当你穷举了所有情况必定将正解囊括其中。为了一点微不足道的用户体验，出卖加密软件的本分——数据安全，实在是很可悲的事情。

个人分类: 密码学相关|1687 次阅读|0 个评论

微分加密方法

sjdkx 2018-4-1 07:31

　　微分加密方法是一种提高加密强度的方法，没有什么高深的理论，但是非常有效。流密码和分组密码加密方式都是可以应用此法的。 　　方法很简单，就是将被加密文件分成许多小段分别对这些小段加密即可。每一小段只有几个字节甚至是一个字节。这样将大大提高加密性能，假如破解者侥幸攻破了一小段，对其来说也没有用处，除非同时攻破许多段。穷举攻击同样遇到极大的困难，因为此时使用的用户密码实在是太长了，甚至和明文一样长，你穷举将是毫无意义的无用功。 　　方法需要很长的加密密码，我们从哪里获得这些呢？可以从随机函数那里得到，只要从用户输入密码中计算出随机函数的种子，并得到需要的密码长度，和一些参数信息，你使用的密码是取之不尽的。 　　参见笔者帖子【少量输入密码而使用大量密码的方法】等。

个人分类: 密码学相关|2476 次阅读|0 个评论

量子芯片7——抗量子破译加密的原理

jiazhang55 2017-3-20 13:02

对于多进制而言，破译基于量子态的随机密码的精确值，是非常难的。我们都知道标准量子时间 ，是一个无限不循环小数，我们设计一个200个量子哈密顿函数的x为一组密码（如123(相当于c光速)），使其解为标准量子时间的某几十位（严格保密），然后以一个200个量子的哈密顿算法作为密码载体，进行传输。如果我们用一个100量子位多进制量子计算机破解，以G赫兹频率计算，需要的时间为 *标准量子时间位数s，这是一个天文数字。 而这是考虑量子计算机硬水平非常完美的情况下，当然经典计算机更是望尘莫及。而现实生活中，几万个量子系统的哈密顿函数非常容易得到（拓扑相变的波函数 就是中之一）。 到这里， 基本就将抗量子破译的加密方式，介绍完了

个人分类: 交流感受|260 次阅读|0 个评论

关于量子加密，与解密

jiazhang55 2017-2-11 18:01

量子加密，是一种全新加密方式，但其秘密保护原理，与经典计算机一样。虽然，我并不是密码学方面的。 但我可以给予一个引导。 其实密码机制，就是量子计算机强大的并行处理能力。 我们举一个例子，一个250比特的量子计算机，处理一个问题需要1s，但一个50量子位的量子计算机，处理同样的问题则需要用2 200 秒。 而量子计算机，的可实现量子比特数，是由上一代最高量子位的量子计算机决定的。其实这个原理和经典计算机相同。 如果我们制作一个，当时最快的量子计算机需要用10年才能解密的密码，这个密码就是不会被破解的。 但，量子加密方式 只能在量子芯片上运转，所以将经典 芯片换为量子芯片，是势在必行的办法。

个人分类: 交流感受|305 次阅读|0 个评论

大众密码学

sjdkx 2015-4-1 12:59

序论 　　通过多年研究总结出一套适用于计算机的文件加密方法，它属于流密码加密但不需要线性反馈位移寄存器，那东西限制了普通计算机用户的应用，因为分组密码方式不但是自找麻烦而且限制了自己所以不被采用，又因为非对称密码的加密方式技术还不成熟速度太慢也不采用。本方法用户密码长度不受限制，但是用户密码不能过短，这是因为用户密码是完成加密的重要参数，如果信息量太少则不能形成千变万化的状态，那样就不能很好地隐藏秘密了。 第一节 加密原理 　　信息加密技术实际是信息隐藏技术，好的加密能保护信息不被没有授权的人读懂。任何信息都可以用数字表示，所以信息加密一般落实到文件加密。所有各类文件都可以是加密对象。 加密原理很简单： 　　就是用未知数来隐藏被加密对象数字而已，设A是被加密对象一般称为明文，一个明文没什么用处，而明文数组则可能是文章或可执行程序或是媒体文件等等，一般文件都可以用字节作为元素。明文是有可能被看懂或识别的，例如字符文章等，也可能是乱码。B表示未知数，一般它和明文有相同的数字单位也就是字节，C表示加密结果的数字，这里用加法加密，当然也可以用别的运算符但必须有相应的逆运算存在。 　　　　　　　　　　A + B = C 　　这是一个数字的加密，可见只知道C不知道B是无法知道A的，两个未知数一个方程无法求解。对于一组数字则有： 　　　　　　　　　　A1 + B1 = C1，A2 + B2 = C2，...An + Bn = Cn 　　这样明文数组A1，A2，...An被未知数组B1，B2，...Bn加密成了密文数组C1，C2，...Cn。一般未知数组被称为密钥数组，解密是加密的逆运算。如果密钥数组只是用一次，并且密钥数组元素之间没有任何关系这样的加密是不可破解的。那为什么有的加密可以破解呢？ 　　从上面可见密钥数组和明文数组是一样长的，如果文件长了就很不方便管理密钥数组。现在的常规方式是用户提供“用户密码”，加密程序根据这些数据用一些算法拓展这些数据制作一个密钥数组，密钥数组长度是密码数组的几千倍几十万倍或更多倍都是有可能的。由少量数据生成大量数据总是有漏洞的，根据这些漏洞理论上是能破解密钥数组的，破解者除了得到密文还可能得到加密软件甚至加密程序的源码。 　　所以加密者努力寻找好的算法避免缺陷被利用，解密者则努力寻找漏洞突破封锁。 第二节 密钥数组的建立 　　鉴于文件是以字节为单位，密钥数组也是以字节为单位，我们知道字节是八位二进制数，数值从0 到 255，共计256个元素。我们要建造的密钥数组是：分布均匀的，数据之间毫无关联的。这样才能确保被加密数据的安全。 　　下面讨论几种建造密钥数组的方法，它们的加密强度和易用性都是不同的： 　　ａ）用一个随机函数；随机函数要求能通过各项测试，周期很大，这样由用户密码计算出一个种子，就可以由此点向后取值，做模256后就形成了字节数组，这样的数组数据之间是有关联的，因为它们来自同一随机函数，在保密性要求不高的情况下可以用它，并且使用时每项再乘一个系数加上一个系数，这两个系数也是由用户密码计算出来。 　　b）用多个随机函数；和a）类似这里用多个随机函数的值的运算结果做密钥，这样的密钥之间的关系就不好被利用破解了，所以这个加密强度比a）高些。 　　c）构造密钥数组;字节数组的基本元素就是256个，要建造 N个数据的密钥数组，为了分布均匀，设k为一个整数，让256×k大于等于N并且256×（k-1）小于N，这样每种元素取 k个，做成一个长度为256×k的数组，我们要将这些数据搅拌均匀，最后取N个即可。数组最初的状态是什么样都没关系，顺序排列的比较好形成，这样我们就有了原始数组。 　　上面建立了元素绝对均匀的原始数组，现在我们设法将其变为乱码数组，并且数组成员之间是没有关系的，我们采用随机排序的方法，来打乱数组的秩序，随机排序就是让数组内的元素位置随机的交换，一般可以用循环来完成，例如256×k的长度的数组，用一个循环变量i，从头到尾的循环，另外随机的在256×k中选择一个位置，用这个位置的元素和第i个元素进行交换，这样循环一次每个元素都被交换了，交换完成后新的顺序建立了，生成了新的数组。从256×k中随机的选择位置的操作可以用随机函数来完成，也可以拼凑一些随机性较强的变数来完成，让随机函数值和一些变量经代数运算生成一个大数据，用此数据模256×k，就可以得到随机位置了。一遍随机排序不理想可以进行多遍，一般借助于优秀的随机函数一遍就足够了。我们这样控制随机排序，由用户密码的计算值做成随机函数的种子，这里只做最简单的叙述，实际应用时，你可以搞得很复杂，例如将数组分成若干段分别处理，也可以使用多个随机函数参与运算...,这些完成后你将得到一个长度为256×k的乱码数组，从中取 N个就达到目的了。 第三节 文件的加密和解密 　　有了密钥数组应用加密原理中的方法就可以加密或解密了，这里是流密码加密方式，被加密文件是以字节为单位的信息流一般称为明文流，在得到用户密码后用第二节中的方法生成以字节为单位的密钥数组这是密钥流，用它们依次做加密操作则得到密文流可以保存于文件中这就是密文。密文可以保存或公开传播。密文可以在加密软件的帮助下，应用你掌握的用户密码，让软件将密文还原为明文这就是解密。 第四节 安全性问题 　　加密算法是公开的、加密软件也是公开的安全性取决于你的密钥数组的质量，如果你的密钥数组各项是完全独立的（第二节方法c）则解密是做不到的。有人可能想若用穷举法长时间计算理论上就能破解，穷举法不是万能的，本方法用户密码不受限制如果密码长一些穷举攻击是徒劳的，你可以这样组织用户密码，它有固定不变的较长的前缀或后缀这样便于记忆和变化的部分，这样就又长又好记了。并且加密软件不检测用户密码的正误，因为任何检测都能帮助破解者，这样穷举攻击必须自己判定结果，这既费时又容易出错。另外还有专门对付穷举攻击的方法就不多说了。

个人分类: 密码学相关|2350 次阅读|0 个评论

利用encfs和百度云盘组建加密的git仓库

liujs 2014-5-25 08:54

关于encfs，参见: http://www.arg0.net/encfsintro 关于百度云盘linux下的客户端bypy, 参见： https://github.com/houtianze/bypy 操作步骤： 一.有关encfs的操作： 1.mkdir -p /home2/repo 2.mkdir /home2/repo.enc !这是加密的目录 3.encfs /home2/repo.enc /home2/repo !提示输入密码，这是加密文件系统密码，必须牢记 执行完上述操作，repo.enc挂到repo下，写进repo的文件/目录将被加密后出现在repo.enc里，内容和文件名都将被加密。执行fusermount -u /home2/repo, 卸载加密文件系统，/home2/repo变空。 二.git的有关操作： 4. mkdir /home2/repo/srcg; cd /home2/repo/srcg; git init --bare 5. cd ~/srcg; git remote add enc file:///home2/repo/srcg !~/srcg是本地工作目录 git push enc master ! 三.与百度云盘的同步 将加密后的repo.enc同步到百度云盘的/gitrepo目录下： 首次操作，上传整个目录： bypy.py upload /home2/repo.enc /gitrepo 以后本地更新后，push之后执行： bypy.py syncup /home2/repo.enc /gitrepo True pull之前执行： bypy.py syncdown /gitrepo /home2/repo.enc True

8280 次阅读|3 个评论

谷歌地球的经纬度准确吗

热度 2 smalljasmine 2014-3-8 22:00

下了个landsat8 oli 影像，本来想用google earth来精校正的，但结果发现同样一个点，影像与谷歌地球差10'的纬度，整整差了6540米啊，又听说google earth是经过加密的，真不知道如何是好

4785 次阅读|2 个评论

常用的时间计算复杂度

热度 1 chzg99 2014-1-13 03:28

全同态加密中经常用到准多项式时间、对数多项式时间、亚指数时间等等。下面这张表详细列出了这些概念的意义及范例。表中 poly( x ) = x O (1) ,表示关于x的一个多项式。 Name Complexity class Running time ( T ( n )) Examples of running times Example algorithms constant time O (1) 10 Determining if an integer (represented in binary) is even or odd inverse Ackermann time O (α(n)) Amortized time per operation using a disjoint set iterated logarithmic time O ( log * n ) Distributed coloring of cycles log-logarithmic O (log log n ) Amortized time per operation using a bounded priority queue logarithmic time DLOGTIME O (log n ) log n , log( n 2 ) Binary search polylogarithmic time poly(log n ) (log n ) 2 fractional power O ( n c ) where 0 c 1 n 1/2 , n 2/3 Searching in a kd-tree linear time O ( n ) n Finding the smallest item in an unsorted array n log star n time O ( n log * n ) Seidel 's polygon triangulation algorithm. linearithmic time O ( n log n ) n log n , log n ! Fastest possible comparison sort quadratic time O ( n 2 ) n 2 Bubble sort ; Insertion sort ; Direct convolution cubic time O ( n 3 ) n 3 Naive multiplication of two n × n matrices. Calculating partial correlation . polynomial time P 2 O (log n ) = poly( n ) n , n log n , n 10 Karmarkar's algorithm for linear programming ; AKS primality test quasi-polynomial time QP 2 poly(log n ) n log log n , n log n Best-known O(log 2 n )- approximation algorithm for the directed Steiner tree problem . sub-exponential time (first definition) SUBEXP O (2 n ε ) for all ε 0 O (2 log n log log n ) Assuming complexity theoretic conjectures, BPP is contained in SUBEXP. sub-exponential time (second definition) 2 o ( n ) 2 n 1/3 Best-known algorithm for integer factorization and graph isomorphism exponential time E 2 O ( n ) 1.1 n , 10 n Solving the traveling salesman problem using dynamic programming factorial time O ( n !) n ! Solving the traveling salesman problem via brute-force search exponential time EXPTIME 2 poly( n ) 2 n , 2 n 2 double exponential time 2-EXPTIME 2 2 poly( n ) 2 2 n Deciding the truth of a given statement in Presburger arithmetic

个人分类: 全同态|8650 次阅读|1 个评论

全同态加密释疑（五）：为什么是电路观点

热度 4 chzg99 2013-12-8 21:38

全同态加密释疑（五）：为什么是电路观点 陈智罡 这个问题是许多刚接触全同态加密研究者困惑的一个问题。 也许初学者以为密码学都是基于数论观点的，其实真正的密码学的灵魂落脚点是计算复杂度。密码学中的所有方案必须要依赖于一个数学难题，这是其安全性所在的根本。问题有多难？拿什么来衡量？答曰：计算复杂度。所以有一本很有名但是很枯涩难懂的一本著名密码学理论书：《 Foundations of Cryptography 》（ Oded Goldreich 著），里面深刻阐述了这一观点。 但是电路观点在密码学中的方案由来已久。例如，姚期智的论文“ How to generate and exchange secrets” 就是通过布尔电路观点构造安全函数计算，产生了著名的概念“ garbled circuit” 。 强调一下，电路观点是一种计算复杂度的计算模型，用途是衡量解决问题所需要的资源，例如时间、存储量等。在电路计算模型下，有使用的 gate 的数量，电路的深度等。 为什么要使用电路观点来构造密码学中的方案？ 采用电路计算模型的原因是电路模型需要“接触“到所有的输入数据，因而不会泄露任何信息，所以传统的安全计算都是采用电路模型的。尽管电路模型非常强大（等价于图灵机），但在某些方面图灵机计算模型要比电路模型的计算效率要高（例如折半查找）。例如在存储有 n 个数据项的数据库中，若使用标准的安全计算协议，首先把函数表示成电路进行计算，该协议的复杂度是Ω ( n ) 。但是若使用图灵机计算模型下的二分查找，时间复杂度为 О ( log n ) 。 电路模型下，算法的性能是用最坏情况下的性能来衡量的。其原因是图灵机算法转换成电路模型下的算法后，该算法工作在无循环的算法结构下，这使得电路模型要考虑所有出现的情况，也就是最坏情况下的运行时间。简单的说，如果一个算法在实践中绝大多数的实例都是运行在多项式时间下，但是对于极少数实例时运行在指数时间下，那么电路模型的计算时间就是指数时间。 所以任何东西，此消彼长，都要付出代价的。 对于所有的全同态加密、基于属性加密、通用函数的两方及多方安全计算协议、对于通用函数的函数加密，都是采用的电路观点。 能否对于电路模型下的密码学方案，让其享受图灵机模型下的时间而不是最坏情况下的时间呢？ 好消息： Shafi Goldwasser 等人在今年的美密会上“ Howto Run Turing Machines on Encrypted Data “论文中，提出了将一个图灵机算法编译成一个工作在电路上的算法（该算法可以看成被加密了），该算法运行在密文下，该电路上的算法的计算时间是图灵机模型下的算法计算时间。针对全同态加密方案、基于属性的加密方案、函数加密方案都进行了这种形式的尝试。 坏消息：这个被加密的运行在电路上的算法，泄露了图灵机模型下的算法计算时间。而且这些方案都是概念上的证明，并不是真正的一个实在的方案。所以意义并不大。

个人分类: 全同态|11667 次阅读|9 个评论

全同态加密释疑（三）：为什么不能运行自己的解密电路

热度 5 chzg99 2013-11-17 20:46

全同态加密释疑（三）：为什么不能运行自己的解密电路 陈智罡 前面说过，要想降低密文计算带来的噪音，可以通过同态解密的方式得到一个新的密文，这个新密文的噪音是恒定的，所以使得我们可以进行下一次计算，每次计算后都通过同态解密约减噪音，就能够获得全同态加密了。然而同态解密是需要 Evaluate 算法能够运行自己的解密函数的，在早期的全同态加密方案中（ Gentry09 ， DGHV ），包括 BV11 方案如果最后一步不使用模维数约减的话， Evaluate 都不能够运行自己的解密函数。 很多同学学到这里的时候，都很纳闷，解密函数不就是一些加法乘法模运算么，为什么计算不了，难道还有计算不了的函数？这个问题是问我的人最多的，今天给大家好好解释一下。 所谓的运行不了自己的解密函数，是有语境的，准确的说是“ Evaluate 算法不能够运行自己的解密函数”，而 Evaluate 算法的输入是什么？同态解密时， Evaluate 算法输入的是解密电路，还有往解密电路里输入的一些密文，这些密文是由密钥和密文的每一位加密而成的，上次博文详细说过这事。那么 Evaluate 算法做的工作是什么呢？ Evaluate 算法做的工作就是让这些密文在解密电路里计算，是密文的计算，记住了！由于密文计算过程会产生噪音，所以密文只能够进行有限次的计算，超过这个界就会产生解密的错误。所以如果 解密电路的深度小于方案所允许计算的深度 （这里方案所允许计算的深度指的是 Somewhat 同态方案的计算能力），那么就可以完成同态解密的工作。但是如果解密电路的深度大于方案所允许计算的深度，那么就悲催了，我们就不能够使用同态解密这个方法去降低密文的噪音。怎么办？ Gentry 在他的论文里发明了一种方法叫“压缩解密电路”，就是把解密电路的深度降低，从而满足“解密电路的深度小于方案所允许计算的深度”，这样就可以使用同态解密技术了，方案就可以启动了！压缩解密电路是要付出代价的，同时需要一个假设“稀疏子集和问题”，该问题没有被很好的研究过，所以是假设。不过目前的方案已经不需要压缩解密电路了，例如 BGV 方案， Bra12 方案，这些方案都能够运行自己的解密电路，所以不需要压缩的方法了。 同态解密的技术成就了全同态加密的诞生，然而其效率却非常低，所以后面诞生了模交换技术。至于什么是模交换技术，下回分解。

个人分类: 全同态|7456 次阅读|10 个评论

[转载]wikii - RSA加密演算法

chnfirst 2013-11-12 22:30

http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95 RSA加密演算法 ​ ​ RSA加密演算法 是一种 非对称加密演算法 。在 公开密钥加密 和 电子商业 中RSA被广泛使用。RSA是 1977年 由 罗纳德·李维斯特 （Ron Rivest）、 阿迪·萨莫尔 （Adi Shamir）和 伦纳德·阿德曼 （Leonard Adleman）一起提出的。当时他们三人都在 麻省理工学院 工作。RSA就是他们三人姓氏开头字母拼在一起组成的。 1973年 ，在 英国政府通讯总部 工作的数学家 克利福德·柯克斯 （Clifford Cocks）在一个内部文件中提出了一个相同的算法，但他的发现被列入机密，一直到1997年才被发表。 对极大整数做 因数分解 的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。尽管如此，只有一些RSA算法的变种 被证明为其安全性依赖于 因数分解 。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到2008年为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。但在 分布式计算 和 量子计算机 理论日趋成熟的今天，RSA加密安全性受到了挑战。 1983年 麻省理工学院在 美国 为RSA算法申请了 专利 。这个专利 2000年 9月21日 失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认。 目录 1 操作 1.1 公钥与私钥的产生 1.2 加密消息 1.3 解密消息 1.4 签名消息 2 安全 3 实现细节 3.1 密钥生成 3.2 速度 3.3 密钥分配 3.4 时间攻击 4 典型密钥长度 5 已公开的或已知的攻击方法 6 相关条目 7 外部链接 操作 公钥与私钥的产生 假设 Alice 想要通过一个不可靠的媒体接收 Bob 的一条私人讯息。她可以用以下的方式来产生一个 公钥 和一个 私钥 ： 随意选择两个大的 质数 p 和 q ， p 不等于 q ，计算 N = pq 。 根据 欧拉函数 ，求得r= φ(N) = φ(p)φ(q) = ( p -1)( q -1) 选择一个小于r的整数 e ，求得e关于模r的 模反元素 ，命名为d。（模反元素存在，当且仅当e与r互质） 将 p 和 q 的记录销毁。 (N,e) 是公钥， (N,d) 是私钥。Alice将她的公钥(N,e)传给Bob，而将她的私钥(N,d)藏起来。 加密消息 假设Bob想给Alice送一个消息 m ，他知道Alice产生的 N 和 e 。他使用起先与Alice约好的格式将 m 转换为一个小于 N 的整数 n ，比如他可以将每一个字转换为这个字的 Unicode 码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 n 。用下面这个公式他可以将 n 加密为 c ： 计算 c 并不复杂。Bob算出 c 后就可以将它传递给Alice。 解密消息 Alice得到Bob的消息 c 后就可以利用她的密钥 d 来解码。她可以用以下这个公式来将 c 转换为 n ： 得到 n 后，她可以将原来的信息 m 重新复原。 解码的原理是 以及 ed ≡ 1 (mod p -1)和 ed ≡ 1 (mod q -1)。由 费马小定理 可证明（因为 p 和 q 是质数） 和 这说明（因为 p 和 q 是 不同 的质数，所以 p 和 q 互质） 签名消息 RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话，那么她可以为她的消息计算一个 散列值 (Message digest)，然后用她的密钥(private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么他就可以知道发信人持有甲的密钥，以及这个消息在传播路径上没有被篡改过。 安全 假设偷听者乙获得了甲的公钥 N 和 e 以及丙的加密消息 c ，但她无法直接获得甲的密钥 d 。要获得 d ，最简单的方法是将 N 分解为 p 和 q ，这样她可以得到 同余方程 d× e ≡ 1 (mod ( p -1)( q -1))并解出 d ，然后代入解密公式 导出 n （破密）。但至今为止还没有人找到一个多项式时间的算法来分解一个大的整数的因子，同时也还没有人能够证明这种算法不存在（见 因数分解 ）。 至今为止也没有人能够证明对 N 进行因数分解是唯一的从 c 导出 n 的方法，但今天还没有找到比它更简单的方法。（至少没有公开的方法。） 因此今天一般认为只要 N 足够大，那么骇客就没有办法了。 假如 N 的长度小于或等于256 位 ，那么用一台 个人电脑 在几个小时内就可以分解它的因子了。 1999年 ，数百台电脑合作分解了一个512位长的 N 。今天对 N 的要求是它至少要1024位长。 1994年 彼得·秀尔 （Peter Shor）证明一台 量子计算机 可以在多项式时间内进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话，那么秀尔的算法可以淘汰RSA和相关的衍生算法。（即依赖于分解大整数困难性的加密算法） 假如有人能够找到一种有效的分解大整数的算法的话，或者假如量子计算机可行的话，那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来说RSA在这种情况下是不可靠的。 实现细节 密钥生成 首先要使用概率算法来验证随机产生的大的整数是否质数，这样的算法比较快而且可以消除掉大多数非质数。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。 除此之外这样找到的 p 和 q 还要满足一定的要求，首先它们不能太靠近，此外 p -1或 q -1的因子不能太小，否则的话 N 也可以被很快地分解。 此外寻找质数的算法不能给攻击者任何信息，这些质数是怎样找到的，尤其产生随机数的软件必须非常好。要求是随机 和 不可预测。这两个要求并不相同。一个随机过程可能可以产生一个不相关的数的系列，但假如有人能够预测出（或部分地预测出）这个系列的话，那么它就已经不可靠了。比如有一些非常好的随机数算法，但它们都已经被发表，因此它们不能被使用，因为假如一个攻击者可以猜出 p 和 q 一半的位的话，那么他们就已经可以轻而易举地推算出另一半。 此外密钥 d 必须足够大， 1990年 有人证明假如 p 大于 q 而小于2 q （这是一个很经常的情况）而 ，那么从 N 和 e 可以很有效地推算出 d 。此外 e = 2永远不应该被使用。 速度 比起 DES 和其它 对称算法 来说，RSA要慢得多。实际上Bob一般使用一种对称算法来加密他的信息，然后用RSA来加密他的比较短的对称密码，然后将用RSA加密的对称密码和用对称算法加密的消息送给Alice。 这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，因为否则的话可以越过RSA来直接攻击对称密码。 密钥分配 和其它加密过程一样，对RSA来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡一个从中取代的攻击。假设Eve交给Bob一个公钥，并使Bob相信这是Alice的公钥，并且她可以截下Alice和Bob之间的信息传递，那么她可以将她自己的公钥传给Bob，Bob以为这是Alice的公钥。Eve可以将所有Bob传递给Alice的消息截下来，将这个消息用她自己的密钥解密，读这个消息，然后将这个消息再用Alice的公钥加密后传给Alice。理论上Alice和Bob都不会发现Eve在偷听他们的消息。今天人们一般用 数字认证 来防止这样的攻击。 时间攻击 1995年 有人提出了一种非常意想不到的攻击方式：假如Eve对Alice的硬件有充分的了解，而且知道它对一些特定的消息加密时所需要的时间的话，那么她可以很快地推导出 d 。这种攻击方式之所以会成立，主要是因为在进行加密时所进行的模指数运算是一个位元一个位元进行的，而位元为1所花的运算比位元为0的运算要多很多，因此若能得到多组讯息与其加密时间，就会有机会可以反推出私钥的内容。 典型密钥长度 1997年后开发的系统，用户应使用1024位密钥， 证书认证机构 应用2048位或以上。 已公开的或已知的攻击方法 针对RSA最流行的攻击一般是基于大数因数分解。1999年，RSA-155（512 bits）被成功分解，花了五个月时间（约8000 MIPS 年）和224 CPU hours 在一台有3.2G中央内存的Cray C916计算机上完成 。 2002年，RSA-158也被成功因数分解。 RSA-158表示如下： 39505874583265144526419767800614481996020776460304936454139376051579355626529450683609 727842468219535093544305870490251995655335710209799226484977949442955603 = 3388495837466721394368393204672181522815830368604993048084925840555281177 × 11658823406671259903148376558383270818131012258146392600439520994131344334162924536139 2009年12月12日，编号为 RSA-768 （768 bits, 232 digits）数也被成功分解 。这一事件威胁了现通行的1024-bit密钥的安全性，普遍认为用户应尽快升级到2048-bit或以上。 RSA-768表示如下： 123018668453011775513049495838496272077285356959533479219732245215172640050726 365751874520219978646938995647494277406384592519255732630345373154826850791702 6122142913461670429214311602221240479274737794080665351419597459856902143413 = 3347807169895689878604416984821269081770479498371376856891 2431388982883793878002287614711652531743087737814467999489 × 3674604366679959042824463379962795263227915816434308764267 6032283815739666511279233373417143396810270092798736308917 相关条目 量子电脑 秀尔演算法 公开密钥加密 外部链接 Diffie-Hellman 另一种非对称式加密法 RSA, The Security Division of EMC

个人分类: Linux|2 次阅读|0 个评论

全同态加密释疑（二）：一个技术

热度 3 chzg99 2013-11-10 01:28

全同态加密释疑（二）：一个技术 陈智罡 在全同态加密（Fully Homomorphic Encryption）方案中，有一个非常重要技术：同态解密。 为什么要同态解密，前面说过噪音问题是实现全同态加密方案的最大障碍。 Gentry 在实现全同态加密方案时，注意到可以在 Evaluate 算法中执行自己的解密函数，那么输入的数据是什么呢？ 解密函数当然输入的是密钥 sk 和密文 c 。但是不要忘了 Evaluate 算法是如何定义的。 Evaluate 算法是对输入的密文 c 1 ,c 2 ,… 执行函数 f 的操作，也就是对密文进行计算， 其实隐含在其中的本质是对密文做同态计算 ，即计算后的密文解密后要等于对明文做同样的计算，如果这点做不到，那么 Evaluate 算法即使能对密文做很多次运算，也是没有意义的，这点一定要清楚。 这就是两种形态，明文态和密文态，两种形态对应的是同一个计算电路。在明文态，输入电路的是明文，而这些明文都是位（因为是布尔电路）。在密文态，输入电路的就是把每一个明文变成密文就可以了（算术电路）。这是我的独家比喻，版权所有。 而现在如果 f 是解密函数，那么输入的密文是什么呢？ 只要看看明文态的时候输入的什么就知道了。 在明文态，对于解密电路，输入的肯定是密钥 sk 的每一位二进制位，以及密文 c 的每一位二进制位，因为是布尔电路，所以输入的数据都要化成二进制位的形式。 好了，现在在密文态，相应的把明文位变成密文就可以了，原来是一个位的地方现在变成了一个密文，那么将这些密文输入到解密电路中，结果是什么呢？是一个密文，这个密文解密后等于在明文态对明文做同样计算的结果。 现在我们关心的是这个从解密电路里出来的新密文和原来的密文 c 之间有什么关系？ 这两个密文对应的是同样的明文。 而我们关心的是两个密文的噪音一样么？ 肯定是不一样的，因为密文计算的噪音会随着计算次数不断增长。而从解密电路里出来的密文的噪音是一个固定值，是保持不变的。惊讶吧？ 我们希望的是什么？是解密电路里出来的密文的噪音比原密文的噪音小么？ NO ！我们要求没有这么高。我们只要求解密电路里出来的密文的噪音，还允许再进行一次乘法计算就可以了。 为什么？因为如果上面的要求成立的话，那么每次密文计算前，只要通过同态解密，出来的密文就可以保证再进行一次计算，不断循环下去，就可以做无限次计算了。当然要想做无限次计算还需要一个假设条件就是：循环安全。如果不做这个假设，我们只能做深度为 L 的电路计算。总之能够保证对密文做我们想要的计算了。 所以同态解密这个技术，是实现全同态加密的一个关键技术， Gentry 就通过它实现了全同态加密。 要想使用同态解密，必须在 Evaluate 算法中能够执行自己的解密函数才可以。很多人都纳闷，解密函数不就是计算一下么，例如在整数方案里解密函数就是： (c mod p) mod2 ，在 LWE 或环 -LWE 上解密函数是： ( c , s mod q ) mod 2 ，难道不能够执行这些函数？ 事情往往没有想象的那么简单，且听下回分解。

个人分类: 全同态|8665 次阅读|11 个评论

全同态加密释疑（一）：四个算法（1）

热度 1 chzg99 2013-11-3 19:09

全同态加密释疑（一）：四个算法（ 1 ） 陈智罡 2009 年全同态加密（ Fully Homomorphic Encryption ）的诞生，不仅是密码学界的一个大的突破（ Breakthrough ） , 而且是计算机理论界的一个突破。自从 2011 年创建了全同态加密 QQ 群，从几十号人到现在的将近 200 人，来自各个大学，包括国外。可见人们对全同态加密研究的热情。 另外在网上有许多同学问我一些问题，有些问题很雷同，可能也是初学者必经之路。全同态加密的入门确实比较难。作为一个过来者，非常愿意分享我的一些心得，所以这里我会把一些共性的问题，用一种深入浅出的方法讲述，希望每个人都能看懂。 其实在全同态加密论文的背后，有许多可以说出来的秘密，只不过这个秘密在论文里没空间也不适合讲，那么这里就搞一个专题“全同态加密释疑”，细说从头每个让你困惑的秘密。如果有愿意加入的朋友，可以一起分享心得体会。 今天说说全同态加密的四个算法。可能有些人会说，这个谁不知道，但是知道并不意味着清楚，只有深刻理解了这四个算法的含义，尤其是第四个算法的含义，才能清楚什么是部分同态加密方案，什么是执行自己的解密电路等等概念。 通常一个公钥加密方案有三个算法： KeyGen 算法（密钥生成）， Enc 算法（加密）， Dec 算法（解密）。但是在全同态加密中，除了上述三个算法之外，还包含第四个算法： Evaluate 算法（密文计算），这个算法的功能是对输入的密文进行计算。 首先说说 KeyGen 算法（密钥生成）。该算法用于生成公钥和密钥，公钥用于加密，私钥用于解密，这个地球人都知道。但是还可能生成另外一种公钥，即密文计算公钥，我们把它称之为 Evk 。 密文计算公钥 Evk 的作用是在执行 Evaluate 算法时用到，而且 Evk 的形式与使用的全同态方案直接相关。例如，如果是通过启动技术（ Bootstrapple ）获得全同态加密，即每次密文计算前要用同态解密约减密文的噪音，这时 Evk 就是对密钥的每一位加密后生成的密文，即密钥有多少位， Evk 里包含的公钥就有多少个。 Evk 中每个公钥的大小就是使用 Enc 加密后产生密文的大小。典型的代表就是 Gentry 的理想格方案以及后续的整数上的方案。 当然还有其他情况，例如，如果使用密钥交换与模交换技术获得全同态加密，典型代表就是 BGV 方案。这时 Evk 中包含的就是 L – 1 个矩阵， L 是方案中电路的深度，该矩阵用于密钥转换。每次密文计算后，都需要使用 Evk 中的公钥将维数扩张的密文向量转换成正常维数的密文向量。 当然还有一种情况就是不需要 Evk ，例如在 Crypto13 会议的论文 GSW13 中， Gentry 使用的密文是矩阵（方阵），所以密文乘积或相加不会产生密文维数改变的事情，所以在密文计算时没有用到公钥，这也是该论文可以产生基于身份或基于属性全同态加密方案的根本原因。 关于 Evk 就说了这么多，你觉得简单么？一个成功男人的背后，有多少……，那么一个概念的背后就有多少个概念在支撑。千万别小看了概念，只有善于抓概念，才能体会方案的脉络。

个人分类: 信息安全|15393 次阅读|5 个评论

[转载]你的数据库安全吗？CryptDB数据库软件可查询加密的SQL数据库

mclown 2013-10-31 18:29

来源： GigaOM 作者： Barb Darrow 摘自：你的数据库安全吗？CryptDB数据库软件可查询加密的SQL数据库 http://www.china-cloud.com/yunjishu/yunanquan/yunanquan/20130408_18807.html CryptDB是麻省理工计算机科学和人工智能实验室（CSAIL）的一个研究项目，该数据库软件允许用户查询加密的SQL数据库，而且能在不解密储存信息的情况下返回结果。尤其是对于云存储来说，这点具有非常重要的意义。 目前，面对国防、医疗保健以及金融行业的数据安全问题，越来越多的应用程序开始应用于数据的处理。其实，任何一个组织都难以保证重要的数据不会被窥探；而对于公有云来说，这个问题更为严重。 CryptDB，这是麻省理工学院计算机科学和人工智能实验室（CSAIL）的一个项目，该数据库软件允许用户查询加密的SQL数据库，而且能在不解密储存信息的情况下返回结果。CSAIL的主任Sam Madden表示，从理论上讲，用户可以收集自己所需要的信息，但不需要让自己组织内的人员“看”到这些数据。 图：CSAIL实验室主任 Sam Madden “我们的目标是实现对加密的数据进行SQL查询，你甚至不需要管理员事先解密这些数据。尤其是在云存储领域，这点非常重要。” Madden在SAP主办的一场活动上说道。 这项研究曾经得到过Google和花旗的资助。加密专家长期以来一直在寻找实现全同态加密技术，也就是数据加密成难以破译的数字字符串，能对这些加密后的字符串进行数学处理，然后解密结果。不过目前的全同态加密方案在实用性上还存有问题，因为该方案耗费的计算时间太长。CryptDB首次解决了实用性的问题，它将数据嵌套进多个加密层，每个都使用不同的密钥，允许对加密数据进行简单操作。此前全同态加密方案加密的数据操作所增加的计算时间是数以万亿倍，而CryptDB只增加了15-26%左右（来源于Cnbeta）。 根据CryptDB的官方主页： “它的工作原理是：在对加密的数据执行SQL查询时，使用的是一个SQL能够‘理解’的加密方案来进行加密。CryptDB同样将加密密钥和用户的密码进行了捆绑，这样的话数据项只有使用相应的用户的密码登陆才可以进行解密。作为结果，就是数据库管理员也不能接触到加密的数据，即使服务器被攻破，攻击者也无法解密用户的数据，如果该用户没有登录的话。” 这个技术团队的成员包括：Raluca Ada Popa, Catherine Redfield, Nickolai Zeldovich以及Hari Balarkishan。 CryptDB也可以运行在私有云中，不过目前还有一些具体的实现问题并没有得到解决。当被问及CryptDB如何协商通过防火墙的数据传输，Madden表示：“这并不是我们重点关注的方向，学术伟大之处在于，我们可以忽略对一些问题的研究。”

个人分类: 科技|1955 次阅读|0 个评论

[转载]无线路由器中 WEP wpa wpa2 这三种加密方式

chnfirst 2013-9-21 23:46

http://zhidao.baidu.com/question/217891252.html 无线路由器中 WEP wpa wpa2 这三种加密方式有什么区别 应该选择哪一种 2011-01-20 22:55 qq371942504 | 分类： 电脑/网络 | 浏览21469次 不说这三种加密方式的安全 只说说 他们在使用过程中有什么区别 和使用过程中方法一样吗 密码长度什么的 目前无线路由器里带有的加密模式主要有：WEP，WPA-PSK（TKIP），WPA2-PSK（AES）和WPA-PSK（TKIP）+WPA2-PSK（AES）。 WEP（有线等效加密） WEP是WiredEquivalentPrivacy的简称， 802.11b 标准里定义的一个用于 无线局域网 (WLAN)的安全性协议。WEP 被用来提供和有线lan同级的安全性。LAN天生比WLAN安全，因为LAN的物理结构对其有所保护，部分或全部网络埋在建筑物里面也可以防止未授权的访问。 经由 无线电波 的WLAN没有同样的物理结构，因此容易受到攻击、干扰。WEP的目标就是通过对 无线电波 里的 数据加密 提供安全性，如同端-端发送一样。 WEP特性里使用了rsa 数据安全 性公司开发的rc4prng算法。如果你的无线 基站 支持MAC过滤，推荐你连同WEP一起使用这个特性(MAC过滤比加密安全得多)。 尽管从名字上看似乎是一个针对有线网络的安全选项，其实并不是这样。WEP标准在无线网络的早期已经创建，目标是成为 无线局域网 WLAN的必要的 安全防护 层，但是WEP的表现无疑令人非常失望。它的根源在于设计上存在缺陷。在使用WEP的系统中，在无线网络中传输的数据是使用一个随机产生的密钥来加密的。但是，WEP用来产生这些密钥的方法很快就被发现具有可预测性，这样对于潜在的 入侵者 来说，就可以很容易的截取和破解这些密钥。即使是一个中等技术水平的无线黑客也可以在两到三分钟内迅速的破解WEP加密。 IEEE802.11的动态有线等效保密(WEP)模式是二十世纪九十年代后期设计的，当时功能强大的 加密技术 作为有效的武器受到美国严格的出口限制。由于害怕强大的 加密算法 被破解，无线网络产品是被被禁止出口的。然而，仅仅两年以后，动态有线等效保密模式就被发现存在严重的缺点。但是二十世纪九十年代的错误不应该被当著无线 网络安全 或者IEEE802.11标准本身，无线网络产业不能等待电气 电子工程师 协会修订标准，因此他们推出了动态密钥完整性协议 TKIP(动态有线等效保密的补丁版本)。 尽管WEP已经被证明是过时且低效的，但是今天在许多现代的无线访问点和无线路由器中，它依然被支持的加密模式。不仅如此，它依然是被个人或公司所使用的最多的加密方法之一。如果你正在使用WEP加密，如果你对你的网络的安全性非常重视的话，那么以后尽可能的不要再使用WEP，因为那真的不是很安全。 WPA-PSK（TKIP） 无线网络最初采用的安全机制是WEP（有线等效加密），但是后来发现WEP是很不安全的，802.11组织开始著手制定新的安全标准，也就是后来的 802.11i协议。但是标准的制定到最后的发布需要较长的时间，而且考虑到消费者不会因为为了网络的安全性而放弃原来的无线设备，因此 Wi-Fi联盟 在标准推出之前，在802.11i 草案 的基础上，制定了一种称为WPA(Wi-FiProctedAccess)的安全机制，它使用TKIP(临时密钥完整性协议)，它使用的 加密算法 还是WEP中使用的 加密算法 RC4，所以不需要修改原来无线设备的硬件，WPA针对WEP中存在的问题：IV过短、 密钥管理 过于简单、对消息完整性没有有效的保护，通过 软件升级 的方法提高网络的安全性。 WPA的出现给用户提供了一个完整的认证机制，AP根据用户的认证结果决定是否允许其接入无线网络中；认证成功后可以根据多种方式（传输数据包的多少、用户 接入网 络的时间等）动态地改变每个接入用户的加密密钥。另外，对用户在无线中传输的数据包进行MIC编码，确保用户数据不会被其他用户更改。作为 802.11i标准的 子集 ，WPA的核心就是IEEE 802.1x 和TKIP（TemporalKeyIntegrity Protocol）。 WPA考虑到不同的用户和不同的应用安全需要，例如：企业用户需要很高的安全保护（企业级），否则可能会泄露非常重要的 商业机密 ；而家庭用户往往只是使用网络来浏览Internet、收发E-mail、打印和 共享文件 ，这些用户对安全的要求相对较低。为了满足不同安全要求用户的需要，WPA中规定了两种应用模式：企业模式，家庭模式（包括小型办公室）。根据这两种不同的应用模式，WPA的认证也分别有两种不同的方式。对于大型企业的应用，常采用“ 802.1x +EAP”的方式，用户提供认证所需的凭证。但对于一些中小型的 企业网 络或者家庭用户，WPA也提供一种简化的模式，它不需要专门的认证服务器。这种模式叫做“WPA预共享密钥(WPA- PSK)”，它仅要求在每个WLAN节点(AP、无线路由器、网卡等)预先输入一个密钥即可实现。 这个密钥仅仅用于认证过程，而不用于传输数据的加密。 数据加密 的密钥是在认证成功后动态生成，系统将保证“一户一密”，不存在像WEP那样全网共享一个加密密钥的情形，因此大大地提高了系统的安全性。 WPA2-PSK（AES） 在802.11i颁布之后， Wi-Fi联盟 推出了WPA2，它支持AES(高级加密算法)，因此它需要新的硬件支持，它使用CCMP( 计数器 模式密码块链消息完整码协议)。在WPA/WPA2中，PTK的生成依赖PMK，而PMK获的有两种方式，一个是PSK的形式就是预共享密钥，在这种方式中 PMK=PSK，而另一种方式中，需要认证服务器和站点进行协商来产生PMK。 IEEE802.11所制定的是技术性标准, Wi-Fi联盟 所制定的是 商业化 标准,而Wi-Fi所制定的 商业化 标准基本上也都符合IEEE所制定的技术性标准。WPA(Wi-FiProtectedAccess)事实上就是由Wi-Fi联盟所制定的安全性标准,这个 商业化 标准存在的目的就是为了要支持 IEEE802.11i这个以技术为导向的安全性标准。而WPA2其实就是WPA的第二个版本。WPA之所以会出现两个版本的原因就在于Wi-Fi联盟的商业化运作。 我们知道802.11i这个任务小组成立的目的就是为了打造一个更安全的 无线局域网 ,所以在加密项目里规范了两个新的安全加密协定–TKIP与 CCMP(有些无线网路设备中会以AES、AES-CCMP的字眼来取代CCMP)。其中TKIP虽然针对WEP的弱点作了重大的改良,但保留了RC4演算法和基本架构,言下之意,TKIP亦存在著RC4本身所隐含的弱点。因而802.11i再打造一个全新、安全性更强、更适合应用在无线局域网环境的加密协定-CCMP。所以在CCMP就绪之前,TKIP就已经完成了。 但是要等到CCMP完成,再发布完整的IEEE802.11i标准,可能尚需一段时日,而Wi-Fi联盟为了要使得新的安全性标准能够尽快被布署,以消弭使用者对无线局域网安全性的疑虑,进而让无线局域网的市场可以迅速扩展开来,因而使用已经完成TKIP的IEEE802.11i第三版 草案 (IEEE802.11i draft3)为基准,制定了WPA。而于IEEE完成并公布IEEE802.11i无线局域网安全标准后,Wi-Fi联盟也随即公布了WPA第2版 (WPA2)。 WPA = IEEE 802.11i draft 3 = IEEE 802.1X/EAP +WEP(选择性项目)/TKIP WPA2 = IEEE 802.11i = IEEE 802.1X/EAP + WEP(选择性项目)/TKIP/CCMP 还有最后一种加密模式就是WPA-PSK（TKIP）+WPA2-PSK（AES），这是目前无线路由里最高的加密模式，目前这种加密模式因为兼容性的问题，还没有被很多用户所使用。目前最广为使用的就是WPA-PSK（TKIP）和WPA2-PSK（AES）两种加密模式。相信在经过加密之后的无线网络，一定能够让我们的用户安心放心的上网冲浪。

个人分类: 电脑、办公|0 个评论

云安全：从全同态加密到函数加密

热度 3 chzg99 2013-7-12 18:57

小小一片云，搅动大世界。云计算已经成为产业界、学术界、政府等各界均十分关注的焦点。 云计算虽好，其安全性却令人担忧。 人们希望云平台能够保证用户数据的机密性与完整性。很自然的一个方法就是：用户对自己的数据加密，然后将加密的数据外包到云端，云端使用全同态加密技术，就可以对密文进行计算。上述方法只是保证了数据的机密性，因为云端看不到用户真实的数据，看到的只是密文。数据的完整性可以通过校验技术等来保证。这里我们只对数据的机密性来讨论。 全同态加密，这一不可思议的技术，无疑是现代密码学最重要的成果之一，当然也是计算机科学界一项重大的成果。 千万不要以为有了云计算才有了全同态加密，事实上全同态加密早在云计算前就有了，这可以追述到1978年， Rivest, Adleman 和 Dertouzos就 提出： 是否无需密钥就能够对密文做任意功能的计算呢？从代数角度看这就是同态性。当时称为隐私同态。 历史有时有惊人的巧合。2007年当人们大力追捧云计算时，云计算的安全也就显得尤为重要，全同态加密的实现更加显得迫切。尽管在这之前，人们已经有了一些同态加密方案， 这些方案要么是满足加法同态，要么是满足乘法同态的，还有一些能够同时满足有限次加法与乘法的同态方案 ，但是在这些方案中没有一个是全同态的。 2009年Gentry的全同态加密方案如一道惊雷，炸响了学术界与工业界。学术界忙着探讨与改造Gentry的方案，工业界争论着全同态是否可以实践。 我认为，Gentry实现全同态的理论框架，至今都没有被打破。可以说目前所有安全的全同态加密方案都是基于Gentry架构的。这种架构的出发点就是对密文计算中不断增长的噪音进行消减。消减的技术就是同态解密，即对一个密文同态解密后得到一个新的密文，新的密文与原密文对应的是同一个明文，只是这个新密文的噪音如果比原密文小的话，就达到消减密文噪音的目的了。由于同态解密开销非常大，所以后面的人们又发明了密钥交换技术、模交换技术等来消减密文噪音。可能有人会问：是否可以构造出密文计算过程中噪音不增加的方案？如果这样的方案有，那么将会是一个大的突破。然而没有，所以现在的全同态加密方案还是在Gentry的大框架下进行构造。 Gentry的构造方法是一种非自然的方法，得到的不是一个天然的方案，是一个经过了人为的、拼凑的、工程性质的构造方法。这样说不是贬义，而是给我们了一种启示，要想达到某种目的，就要使用各种手段。所以你看到的全同态加密方案不是普通上的一个加密方案，而是一个需要若干步才能得到，而且还有各种限制的一个方案。最近在EPRINT上有一篇论文：An efficient FHE based on the hardness of solving systems of non-linear multivariate equations。这篇论文是我目前看到得唯一一个非Gentry框架的全同态加密方案，但是这个方案的安全性有缺陷，所以还不成气候。但是有一点我可以肯定的，直觉告诉我：非Gentry的构造方法应该是存在的，使用的方法依然是拼凑法。 全同态加密用于解决云安全有个问题，就是密文及密文计算的结果对于云平台完全是“不懂的”，这种“不懂”看似是完全安全的，但是实际用起来却做不了很多事情。例如，邮件服务器的垃圾邮件过滤，按道理用户把邮件加密后发出去，邮件服务器收到加密的邮件，可以通过全同态技术，运行垃圾邮件检测算法对加密邮件进行垃圾邮件检测，然而得到的检测结果是密文，邮件服务器“读不懂”检测结果，所以无法判断是否为垃圾邮件。还有很多其他例子，例如数据库的检索，由于要对密文进行比较，而比较的结果是密文，服务器无法判断是否找到了匹配的记录。 那么有没有一种方法，例如能让服务器只知道检测结果是否为垃圾邮件，而不知道邮件的内容呢？包括数据库的检索也一样。 有的，这就是所谓的函数加密。例如，任何人可以使用公钥PK对明文m进行加密得到密文Enc(m)，密钥的持有者对某个函数 F 颁发一个KEY, 任何拥有KEY和密文Enc(m)的一方，都可以计算F(m), 但是除了F(m)外不能获得关于m的任何信息。 这样上述垃圾邮件检测的例子就可以通过函数加密来解决。例如，Alice公开自己的公钥以及给邮件服务器一个KEY，这个KEY用于邮件服务器的垃圾邮件检测函数。当有人要发邮件给Allice的时候，先用Alice的公钥加密邮件，然后发出。邮件服务器收到邮件后，就可以通过垃圾邮件检测算法判断出邮件是否为垃圾邮件，然后做出相应的操作。 所以，一个支持所有函数的函数加密方案是非常有用的。这样的函数加密方案存在么？ Agrawal, Gorbunov, Vaikuntanathan and Wee 的结果说明：对多个通用函数能够提供任意多数量KEY的函数加密方案是不可能的。目前最好的结果就是：对任意一个通用函数提供一个KEY的函数加密方案。这个方案来自于今年STOC会议的论文：Succinct Functional Encryption and Applications Reusable Garbled Circuits and Beyond。是函数加密的一个最大进展。

个人分类: 信息安全|19662 次阅读|4 个评论

超星的pdg.67格式很加密

pgg 2013-6-14 01:22

超星的pdg.67格式很加密 在网上下了一本超星电子书，其实猪头哥我一直比较怵超星的电子书——因为它转换为 pdf 格式不方便，今晚的情形也不能例外！ 按照网上的各种提示依次试了 ProCX_2.0 、 BooXViewerPDG 和 Pdg2Pic 等几个软件，可能它们对老版的 pdg 格式起作用，而 pdg.67 的加密格式基本上无效，甚至没法导出文件。 花了一个小时时间，猪头哥最终放弃！不由感叹一声：超星的 pdg.67 格式文件做得真好，加密很强大！ 看来独有的加密格式确实是版权保护的好办法！

个人分类: 科研叙事|5633 次阅读|0 个评论

可实践的同态加密：IBM发布了开源软件库

chzg99 2013-6-2 15:22

IBM在密码学上迈出了新的一步：发布了一个实现同态加密的开源软件库：HELib。 HE是英文Homomorphic Encryption(HE)的缩写。HElib也许会成为密码学上的一个里程碑。遥想2009年Gentry突破性的实现全同态加密方案时，该方案还是理论上的，并不能实现，而且理论上的效率也非常差。短短4年过去，软件库都开发出来了，而且还产生了一大堆优化技术，可圈可点呀！ Helib提供的是BGV方案的实现 ，以及提供了一些使得全同态加密更快的优化方法，例如：密文打包技术等。 HElib目前可能更多的是对同态加密研究人员使用，目前该库所提供的是都是一些简单的例程调用，例如：加法，乘法，移位等运算，可以把它看成是一个面向同态加密的“汇编语言”。今后还会及时的推出更多更丰富的例程调用。 另外该库没有实现 bootstrapping ，提供的是层次同态加密方案，所以参数必须设置的充分大才能完成所需的计算。 该库用C++和NTL数学库来实现的。

个人分类: 信息安全|7964 次阅读|0 个评论

建议所有的程序员在数据库中存密码时都用密文啊！

热度 2 qinchuanq 2012-9-28 03:54

今天听一个师弟说他负责维护的服务器被种了很多木马。伤不起！ 他那个只是个数据库查询机。不过记录有大量用户的信息。虽然，机器本身的数据看起来没有什么价值，而且好像只是个只读查询机。但是大量的用户信息尤其是帐号密码信息是有很大价值的。 做个简单的假设：假如数据库中的某个人他接触有涉密信息，然后他在这台服务器里的帐号和密码或者仅仅只是密码和他在涉密系统里的密码一样。那么…… 或者，他不接触涉密，但是他所有的个人帐号密码全都一样，比如网银啊，QQ啊，邮箱啊。那么密码泄密也是很严重的。 有很多小黑就喜欢搜集这些帐号密码信息，直接做成字典，或者更高级一些，挖掘一下，加工一下，再做成字典，那么针对特定人群做成的字典，来破解特定人群的账户密码，成功率应该会提高很多。 所以建议所有程序员：在往数据库中存放用户帐号密码时，不要用明文。MD5都不安全了，何况明文？就我所知，国内的某教务管理系统好像就是明文存储帐号密码的。 这不坑爹么？

个人分类: 网络安全|579 次阅读|2 个评论

整数上全同态加密方案分析（3）--献给全同态加密的初学者

热度 9 chzg99 2012-9-27 13:00

1、 解密电路的深度 上面有一个人说对了一半，其实我们可以把解密电路用 AND 电路和 XOR 电路表出，计算一下电路的深度（电路的深度代表着运算的次数），然后再和 permitted functions 中功能电路所允许的最大深度做个比较，就知道解密电路是否属于 permitted functions 集合了。 首先来分析 permitted functions 集合所允许的电路深度。由于 permitted functions 集合里的任一功能函数 f 都可以用 AND 电路和 XOR 电路表出，而 AND 电路和 XOR 电路可以看做对输入的二进制位做乘法和加法，所以 f 电路的深度可以用输入位的对称多项式来衡量（用多项式衡量是因为多项式里恰好是变元的乘法和加法），又由于乘法是噪音的主要来源，所以可以用多项式中乘法次数来做电路深度的主要衡量指标。有： c* = f ( c1, c2, …， cn ) = f ( m1+2r1+pq, m2+2r2+pq, …， mn+2rn+pq ) = f ( m1+2r1, m2+2r2, …， mn+2rn ) +p( …… ) 密文 c* 的噪音为： c* mod p = f ( m1+2r1, m2+2r2, …， mn+2rn ), 要想 c* 解密正确必须有： f ( m1+2r1, m2+2r2, …， mn+2rn ) p/2, 其中 mi+2ri 是密文 ci 的噪音。不妨令 mi+2ri = xi, 且 xi B, B 是密文 ci 噪音的上界，则有： f ( x1, x2, …， xn ) p/2 。 我们的目标是衡量 f 的运算次数 d ，所以可以用初等对称多项式来表达 f ，有： f ( x1, x2, …， xn ) = x1x2 … xd + x1x3 … xd + ……；其中 d=n f ( x1, x2, …， xn ) 的每一项就是从 n 个变元 ( x1, x2, …， xn ) 里选取 d 个变元，因此有 C （ n, d ）个项（ C 表示组合运算），由 C （ n, d ） n d 得： f ( x1, x2, …， xn ) B d n d p/2 = d log p / log Bn , 也就是说 f 最多运算次数为 log p / log Bn 。 下面再看看解密电路的运算次数： Dec(c): (c mod p) mod 2= （ c – p* 「 c/p 」） mod 2 = Lsb(c) XOR Lsb( 「 c/p 」 ) 仔细端详解密电路的公式，发觉其复杂性主要来源是 c/p ，所以我们主要看 c/p 所需的运算次数。 c/p=c* p -1 , p -1 是小数，为了保证 c* p -1 取整之后的的精确度， p -1 要取 log c 位的。例如 12345678 * 0.111111 和 12345678 * 0.11111111 的结果取整后是不一样的。那么两个数相乘的次数如何衡量呢？有如下结论 : 乘两个 t 位数相当于加 t 个数 : 输出位是关于输入位的一个 2 次多项式 a3 a2 a1 b3 b2 b1 a3b1 a2b1 a1b1 a3b2 a2b2 a1b2 a3b3 a2b3 a1b3 加 t 个数可以应用“ 3-for-2 trick” :3 个数相加得到两个数相加，输出位是关于输入位的一个次数最多为 2 次的多项式 a3 a2 a1 b3 b2 b1 c3 c2 c1 a3+b3+c3 a2+b2+c2 a1+b1+c1 a3b3+a3c3+b3c3 a2b2+a2c2+b2c2 a1b1+a1c1+b1c1 一次 二次 那么 t 个数应用这个技巧经过 log 3/2 t 次相加后得到两个数，输出位的次数为 2 log 3/2 t = t log 3/2 2 = t 1.71 。 再看两个 t 位数相加： 进位： a2b2+a2a1b1+b2a1b1 a1b1 a3 a2 a1 b3 b2 b1 a3+b3+a2b2+a2a1b1+b2a1b1 a2+b2+a1b1 a1+b1 三次 输出位的次数最多为 t 次，因为上面 3 位数相加次数最多为 3 次。 结合起来有：乘两个 t 位数的次数最多为 2t 1.71 t=2t 2.71 ，而 c* p -1 里 c 的位数为 log c ， p -1 要取 log c 位的，又因为 log c log p ( 因为 pc) ，所以 c* p -1 的次数至少是 2(log p) 2.71 , 而前面说过 f 最多运算次数为 log p / log Bn ，所以解密电路的深度要大于 Evaluate 所允许运行功能电路的深度，因此如果 Evaluate 运行解密电路的话，将会产生不正确的结果，我们就说 Evaluate 无法运行解密电路，换句话说解密电路不在 permitted functions 集合里。 结论应该知道了吧，是一个坏消息。解密电路不在 permitted functions 集合里，其后果就是：无法对密文进行任意功能的运算！与全同态失之交臂。 怎么办呢？古人云：兵来将挡，水来土掩。解密电路深了，把它变浅不就完了。说容易做起来有点难。我觉得有技巧的地方就在于压缩解密电路。 2、 压缩解密电路 如何把电路变浅呢？一个直观的方法就是替别人承担一些工作，这样原来的任务量就变小了。 还是先来仔细打量一下问题出在的地方： c* p -1 这是一个乘积，要想把它变成一个较浅的运算电路，应该如何做呢？最直观的方法就是：把乘积变成和，也就是说把 c* p -1 —》∑ zi 。 c* 是密文，我们不可能拿它开刀，唯一可以做处理的地方就是 p -1 ，也就是说应该把 p -1 转换成一个和的形式即： p -1 —》∑ yi ，要知道 p 是私钥是不能公开的，所以可以把 p 隐藏在∑ yi 中，同时这种隐藏要不会泄露 p 才可行，所以要有一个陷门才可以，这个陷门就是 Sparse Subset Sum Prob (SSSP) ，就是给一串整数 x1,x2, ……， xn ，存在一个 {1, ……， n} 的子集 S ，使得∑ si * xi=0 ( 其中 i ∈ S) ，让你求这个 S 是不可行的。这个问题据说是困难的，好像没有被 well studied 。有了这个陷门就可以构造出： 取 y1,y2, … ,y n ∈ [0, 2) ，存在一个稀疏子集 S ，使得∑ si * yi ≈ 1/p mod 2 ( i ∈ S) ( 因为是实数所以用近似等于 1/p 表示，是存在一个误差的，这个误差不影响取整后的结果 ) 。令 zi — c*yi mod 2 ， zi 保留一定的精确度，从而有：∑ si * zi ≈ c/p mod 2 。所以解密电路中的「 c/p 」可以替换成「∑ si * zi 」。解密电路变成： Lsb(c) XOR Lsb( 「∑ si * zi 」 ) 。 这个变换后的方案，公钥除了原来的公钥 pk 之外还多加了一个向量 {yi} 。密文除了原来的 c 之外多出了一个向量 {zi} 。这个多出来的 zi 可以看做是提前拿出来计算以减轻解密电路负担的，这个方法叫预处理（ post-process ）。私钥由原来的 sk 变成了 {si} 。可以看到公钥变大，密文也变大，这个代价就是为了换得更浅的电路。那么电路变浅了吗？下面来分析一下： 主要分析一下∑ si * zi 的多项式次数，然后和我们前面分析的 f 所能执行的最大次数比较就 OK 。 假设 zi 的精确度为 n 位（我们考虑的都是二进制表示），整数位只考虑最低位，因为 Lsb( 「∑ si * zi 」 ) 是对和先取整再取最低有效位。如下所示： a1,0 · a1,-1 …… a1,-(n-1) a1,-n ---------- s1*z1 a2,0 · a2,-1 …… a2,-(n-1) a2,-n -----------s2*z2 a3,0 · a3,-1 …… a3,-(n-1) a3,-n …… ………… at,0 · at,-1 …… at,-(n-1) at,-n -----------sn*zn 如果上述 t 个数应用“ 3-for-2 trick” 相加，电路深度也不会满足要求。所以得另寻它法。 有个概念说一下： HammingWeight ，海明重量通俗的说就是向量中“ 1 ”的个数，由于我们是二进制相加，所以上面每一列相加的结果可以看成是该列的海明重量。那么海明重量怎么求呢？有一个定理非常有用，就是： 对于任意一个二进制向量 a1,a2, ……， at ，其海明重量为 W ，并且其二进制表示为 ;wn, …… w1w0 的话，则 wi 可以表示为关于变元 a1,a2, ……， at 的一个次数是 2 i 多项式。这个多项式很好求，就是对称多项式 e 2 i （ a1,a2, ……， at ），有现成的算法。 好了我们可以对上面的那些列运用此定理。对最低列求海明重量，则海明重量的最低位是 e 2 0 （ a1,-n, a2,-n ……， at,-n ） mod 2 ，它就是该列的和，这个海明重量的倒数第二位是 e 2 1 （ a1,-n, a2,-n ……， at,-n ） mod 2 ，就进位到倒数第二列记为 Cn,-(n-1) ，如此下去 ; Cn,0 Cn,-1 Cn,-(n-1) -------- 进位 a1,0 · a1,-1 …… a1,-(n-1) a1,-n a2,0 · a2,-1 …… a2,-(n-1) a2,-n a3,0 · a3,-1 …… a3,-(n-1) a3,-n …… at,0 · at,-1 …… at,-(n-1) at,-n b-n 最后得到： C-1,0 ………… Cn-1,0 Cn-1,-1 …… Cn,0 Cn,-1 Cn,-(n-1) a1,0 · a1,-1 …… a1,-(n-1) a1,-n a2,0 · a2,-1 …… a2,-(n-1) a2,-n a3,0 · a3,-1 …… a3,-(n-1) a3,-n …… at,0 · at,-1 …… at,-(n-1) at,-n b0 b-1 …… b-(n-1) b-n 则有： b= 「∑ si * zi 」 = (b0 + b-1 ) mod 2 ( 因为是取整，所以只关心第 0 列，取整是要取最近的整数，所以和 b-1 有关，如果 b-1 是 1 则要进上去 ) 别忘了我们现在的任务是要计算「∑ si * zi 」的电路关于 ai,j 的多项式次数。开始时可以看成都是一次的： a1,0 · a1,-1 …… a1,-(n-1) a1,-n deg=1 · deg=1 …… deg=1 deg=1 a2,0 · a2,-1 …… a2,-(n-1) a2,-n deg=1 · deg=1 …… deg=1 deg=1 a3,0 · a3,-1 …… a3,-(n-1) a3,-n deg=1 · deg=1 …… deg=1 deg=1 …… ………… at,0 · at,-1 …… at,-(n-1) at,-n deg=1 · deg=1 …… deg=1 deg=1 然后计算完最后一列，有了向前面各列的进位后 , 如下： e 2 n ( ) e 2 n-1 ( ) e 2 2 ( ) deg=1 · deg=1 …… deg=1 deg=1 deg=1 · deg=1 …… deg=1 deg=1 deg=1 · deg=1 …… deg=1 deg=1 …… ……………… deg=1 · deg=1 …… deg=1 deg=1 每一列关于 ai,j 的次数都变了，例如倒数第二列次数为 4 了，依次下去： e 2 1 ( ) …… …… e 2 n-1 ( ) e 2 n-2 ( ) …… e 2 n ( ) e 2 n-1 ( ) e 2 1 ( ) deg=1 · deg=1 …… deg=1 deg=1 deg=1 · deg=1 …… deg=1 deg=1 deg=1 · deg=1 …… deg=1 deg=1 …… ……………… deg=1 · deg=1 …… deg=1 deg=1 因为最后的结果是 (b0 + b-1 ) mod 2 ，所以我们只关心前面两列的次数（即第 0 列和第一列），显然最高次数为 2 n ，所以计算「∑ si * zi 」的电路关于 ai,j 的多项式次数为 2 n （别忘了 n 是 zi 的精确度）。回忆一下我们原来说的 f 所能计算的最高多项式次数为： log p / log Bn （ 2 n 中的 n 和此式的 n 不是一个 n ）。如何比较呢，得把参数确定一下，按照 DGHV 方案中的参数， λ为安全参数，取 ||p|| ～λ 2 , ||r|| ～λ ，所以 p ～ 2 λ 2 ， B ～ 2 λ ，则 log p / log Bn ～λ。要想让 Evaluate 能够运行 「∑ si * zi 」电路， zi 的精确度要取 log λ才可以。现在你知道 DGHV 论文中 zi 精确度为什么要取那个数了吧。 到此为止我们知道了解密电路经过压缩，可以被 Evaluate 正确运算了，从而解密电路堂而皇之的进入 permitted functions 集合里了，所以该方案可以对密文做任意功能的运算了，知道这意味着什么吧，全同态实现了。七拐八歪的才修成正果，确实不容易。 接下来我们总结一下实现步骤，其实上面已经有了。 3、 实现步骤 功能函数 f 里其实有两样基本东西就够了： AND 增强型电路， XOR 增强型电路，经过集成电路化后如下现状： 任意功能函数例如 f1 ，都可以应用如上两个增强电路组合来表示，例如： 所以每次计算的基本步骤如下： 1) 对输入的明文 m 进行加密 Enc(m), 得到密文（ c,z ） ,c 是密文， z 是向量 z1,z2, …… 也称为扩展密文。 2) 对输入的密文进行重加密。输入的密文为（ c,z ）。在对密文运算之前每次都要对其重加密。因为明文空间是 {0,1} ，所以加密一定是对密文按位来加密。重加密的过程就是解密的过程，但是对象是对加密的密文以及加密的私钥进行。所以有： c’=Enc(Lsb(c)) ，得到的 c’ 是一个整数。原本对 z 的每一位也要进行加密的，但是有一个方法可以提高效率，就是对 z 不加密，认为 z 的每一位自己就是自己的加密。另外私钥是 s=s1,s2, …… 是 0 和 1 的向量，对私钥的每一位的加密记为 sk’=Enc(s1),Enc(s2), …… =s1’ ， s2’, …… ，得到的 si’ 也是整数。然后运行 ∑ si * zi ，运行它的算法如前面所说，把每一个 zi 的二进制表示写成矩阵的一行，这样就得到一个矩阵： a1,0 · a1,-1 …… a1,-(n-1) a1,-n a2,0 · a2,-1 …… a2,-(n-1) a2,-n a3,0 · a3,-1 …… a3,-(n-1) a3,-n …… ………… at,0 · at,-1 …… at,-(n-1) at,-n 然后用 si’ 乘以上面矩阵第 i 行的每一位，得到一个整数矩阵 ( 矩阵中每一个元素都是整数 ) ： …… …… e 2 1 (b1,-(n-1), b2,-(n-1) …， bt,-(n-1) ） b1,0 · b1,-1 …… b1,-(n-1) b1,-n b2,0 · b2,-1 …… b2,-(n-1) b2,-n b3,0 · b3,-1 …… b3,-(n-1) b3,-n …… ………… bt,0 · bt,-1 …… bt,-(n-1) bt,-n e 2 0 (b1,-n, b2,-n …， bt,-n ） 然后对最后一列（最低位）求海明码，根据前面所述定理，海明码的最低位是 e 2 0 （ b1,-n, b2,-n ……， bt,-n ），其余各位 e 2 1 （ b1,-(n-1), b2,-(n-1) ……， bt,-(n-1) ），……，都作为进位进到前面相应的位。依次计算下去，第 1 列的结果是 b-1 = e 2 0 （ b1,-1, b2,-1 ……， bt,-1 ，……），第 0 列的结果是 b0 = e 2 0 （ b1,0, b2,0 ……， bt,0 ，……） b1,0 · b1,-1 …… b1,-(n-1) b1,-n b2,0 · b2,-1 …… b2,-(n-1) b2,-n b3,0 · b3,-1 …… b3,-(n-1) b3,-n …… ………… bt,0 · bt,-1 …… bt,-(n-1) bt,-n b0 b-1 3) 计算 b= ( b0 + b-1 ) ， b 就是对应的 Lsb( 「∑ si* zi 」 ) 密文运算的结果。 4) 根据上面已经得到的 c’=Enc(Lsb(c)) ，最终对密文 c 的重加密结果为： c* = c’+ b 知道此 c* 和 c 有什么关系么？ c* 是 c 的“重生”，噪音比原来降低了。 5) 然后将 c* 输入门电路。门电路一般都是二元的，需要两个输入，另外一个输入也用同样的方法计算得到 6) 进行门电路运算，例如加或乘，输出得到的结果。接下来有两种情况：第一种：此结果为最终结果，那么再进行重加密一次后，将密文返还给用户，用户解密后得到正确的运算结果。第二种：此结果不是最终结果，那么继续输入到下一级电路，依然是要先进行重加密。 4、 后记 历时一周的时间写了这个总结，就想用通俗的话语呈现整数上全同态方案的过程。整数全同态方案中另外就是有关参数的设置，噪音大小的分析等内容了，这个可以通过看 DGHV 方案来消化理解。 全部文章到此结束。此时此刻我觉得脑海里一篇空虚，很累很累，就好像春蚕将丝吐尽后的感觉。我知道，我需要看新的文章，以使我重生。 有个全同态加密群： 187291158 。可以互相交流。

个人分类: 信息安全|10728 次阅读|17 个评论

整数上全同态加密方案分析（2）--献给全同态加密的初学者

chzg99 2012-9-27 12:56

1、 Bootstappable ：一个生硬的思路 噪音阻碍了我们的目标，那么如何消除噪音这个敌人呢？一个直观的方法就是对密文解密，密文解密后噪音就没有了，但是要解密必须要知道私钥，要想通过获得私钥来消除噪音是不现实的。那么如果对密钥加密来做可以么？ 让我们先看看 Evaluate 算法。在 Evaluate 算法中能够对密文执行函数功能 f 的运算，其中 f 是属于 permitted founctions 集合的任一 founction （这里稍微解释一下， permitted founctions 集合也称 permitted circuit ，例如有两个函数功能 f1 和 f2 ，运行 Evaluate(pk, f1, c1,c2, …， cn) 和 Evaluate(pk, f1, c1,c2, …， cn) ，就是分别对密文执行 f1 运算和 f2 运算，如果 f1 运算的结果解密后恰好是 f1 对相应明文运算的结果（同态成立），那么 f1 就属于 permitted founctions 。而 f2 运算的结果解密后如果不等于 f2 对相应明文运算的结果，那么 f2 就不属于 permitted founctions 。）。 试想如果 Dec 解密算法也在 permitted founctions 集合中，那么 Evaluate 算法就可以执行 Dec 解密功能了。如果我们输入的是 s* （是用 pk2 对私钥 s 加密得到的密文），以及对运算密文 c* （是用 pk2 对 c 再加密的密文，原密文 c 是用 pk1 进行加密的 ) ，那么执行 Evaluate(pk2, Dec, s*,c*) ； 所得结果为一个新的密文，该密文是明文在 pk2 下加密的密文，是不是有点像魔术，就像原来一个人穿的是西装，现在你没有看到这个人换衣服的情况下，魔术师只是施了一下魔法，这个人立刻就换了一身运动服，人还是原来那个人，只是包装变了。这也是 Gentry 思想中一个最重要的特性：同态解密。 那么同态解密对于降低噪音又有什么关系呢？ 当密文运算后，噪音会被迅速放大，如果我们对运算后的密文做一次同态解密，是不是相当于得到了一个新鲜密文呢，而新鲜密文的噪音是最小的，所以达到了降噪的目的。（事实上同态解密后得到的密文的噪音要比新鲜密文噪音稍微大一些。）这一手法称之为：重加密技术，它为我们提供了降低噪音的一个方法。 接下来你肯定会想到：每次密文运算前只要对密文进行重加密来降低噪音，然后再进行密文运算，那么噪音永远都在可控的范围内，运算结果的解密也就不会失败了。运算电路可以反复递归此过程，就可以达到无限次密文运算的目的了。然而降低噪音并不是最终目的，降低噪音是为了能够进行下一次运算，所以解密电路加上一个门电路（这个门电路可以是加法门电路或者乘法门电路等等基本电路）称之为“增强电路”。如图： 由于重加密在每次执行前都需要一个公钥来加密私钥和密文，要进行多次重加密就需要一个公钥序列 {pk1,pk2, … ,pki} ，对应于公钥序列也有一个加密私钥链 {sk1*,sk2*, … ,sk(i-1)*} （其中 ski* 是用 pk(i+1) 加密 ski 得到的密文）。这个过程是如何进行的呢？ 运算电路的每一层都对应一对公钥与私钥。第一层对应的是 pk1 和 sk1 ，第二层对应的是 pk2 和 sk2 ……。例如 : 初始公钥为 pk1 ，对应的私钥为 sk1 ，在电路第一层进行重加密时，将用第二层电路的公钥 pk2 对 sk1 进行加密得到 sk1* （公钥对于所有层都是公开的），以及用 pk2 对密文进行加密；然后输入解密电路，解密电路运行后将输出一个密文，该密文是用 pk2 对明文进行加密的结果。同理在电路第二层进行重加密时，将用 pk3 对该层密钥 sk2 加密得到 sk2* ， , 以及对来自第一层电路的输出密文进行加密；然后输入解密电路，解密电路将输出一个密文，该密文是对明文用 pk3 进行加密的结果。如此下去。 这种情况下公钥与私钥的数量与电路的深度成线性的依赖关系。如果将被加密的私钥信息泄露，不会影响密钥本身的安全的话，这称之为 circular security 。如果全同态的加密方案是 circular security 的话，就不需要这么多公钥与私钥，所有电路层都共用一个公钥与加密的私钥就可以了。好处在于我们不需要为了确定密钥的数量，而在运算前确定执行函数功能的电路深度，从而方便许多。要证明前面的方案是 circular security 的还很困难，但是目前可以认为不会带来攻击的。 如果解密电路是在 Evaluate 所执行的 permitted functions 的集合里，则称该加密方案是 Bootstrappable 。从上面的解决思路可以看到没有特别绕弯子的地方，就是碰到问题解决问题，解决不了的，创造条件也要解决。通过创造同态执行解密电路的条件，从而降低噪音以达到无限次对密文运算的目的。 好了，到这里似乎全同态实现了（有种共产主义立马实现的感觉）。然而还存在一个问题： Evaluate 电路能否能够运行解密电路呢？换句话说：解密电路是否在 Evaluate 所执行的 permitted functions 的集合里呢？ 可能有些人会说 : 一个算法调用另外一个算法，有什么执行不了的？这就要说说电路的复杂度。 2、 电路复杂度 前面的方案中大家看到了是按“位”来加密的（即 m ∈ {0,1} ），加密后得到的是一个整数，密文膨胀的很厉害，那么为什么明文不取整数来加密呢？例如取明文 m ∈ Z 。我想原因是这样的：每个研究全同态的人们都想过了，但是没有找到一个方案可以把明文按照整数来加密。并不是说没有这种方案，估计只是现在还没有找到。 又有人会问：为什么全同态方案要用电路来描述呢？ 首先我们来说说什么叫一个方案是全同态的？如果一个方案能够对密文做任意功能的运算，而且运算结果所得密文是紧凑的，同时 Evaluate 算法（即运算）是有效地，那么我们就称该方案是全同态的。可以用下式说明： 上式太重要了，我觉得只要把上面的式子牢记在心，那么全同态的概念就装在心里了。“紧凑的”在这里就不说了，论文里有解释，而且也很好理解。正确性当然是必须的。那么如何衡量 Evaluate 的有效性呢？最直观的方法可以通过复杂度来衡量。显然 Evaluate 的复杂度依赖于所运算的功能 f 。那么 f 的复杂度如何衡量呢？当然最直接的方法是通过在图灵机上运算 f 的时间来衡量。但是功能函数 f 又是什么呢？我想应该是五花八门的功能，如果想用功能去描述它恐怕是一言难尽，但是如果用布尔电路的大小（ the size of boolean circuit, 即门电路的数量）来衡量，那么 f 就能够被拆解成一些简单的布尔电路：例如“与”电路、“或”电路、“非”电路。而这些电路是可以组合成任意电路的，也就是说可以表示任意功能的电路。同样我们也可以选择用 AND 电路和 XOR 电路，因为这两个电路是具有完备性质的，也就是说这两个电路的组合也可以表出任意功能的电路（而且用这两个电路来描述更加直观，它们直接对应的算术运算就是乘法和加法）。显然 AND 电路和 XOR 电路是属于 permitted functions 集合里的（为什么？因为 AND 电路是对应的是两个二进制位相乘， XOR 对应的是两个二进制位相加，上述同态方案肯定能够正确执行这两个运算，因为就是一次乘法或者一次加法，既然能够正确执行，所以它们就属于 permitted functions 集合）。又由于 AND 电路和 XOR 电路是完备的，所以任意功能都可以用这两个电路组合表出，也就是说该同态方案可以对密文做任意功能的运算，这不就是传说中的全同态定义么！任意功能的问题解决了，但是还缺一点：必须是正确的才行。你一阵对密文蹂躏后，如果结果解密后不是同样对明文蹂躏的结果，你有什么感觉？ 那么上述同态方案能够保证计算的正确性么？上面我们已经看到由于噪音的存在，该方案只能做有限次的运算，也就是说只能够对 permitted functions 集合里的功能函数保证是正确的，在此之外保证不了，现在你知道 permitted functions 集合里有什么东西了吧。那如何能够保证对密文做任意功能的运算还是正确的呢？前面说过可以通过重加密技术降低噪音呀！具体如何做呢？很简单：给 AND 电路上接一个解密电路，给 XOR 电路上也接一个解密电路，任何密文在进入 AND 电路或 XOR 电路之前，先让它进入解密电路进行重加密，之后从解密电路里出来的密文就是一个类似于新鲜密文的密文，噪音比进来前降低了，然后再让这个新的密文进入 AND 电路或 XOR 电路，这样我们就可以对密文正确的做任意功能的计算了！而接了解密电路的 AND 电路或 XOR 电路就称为增强电路。 总结一下：任意函数功能拿来，先用增强型 AND 电路和增强型 XOR 电路表出，这样就可以对密文做任意功能的计算了，由于是增强型的，我们不再害怕噪音的阻碍，可以无限运算下去。 OK ，全同态的蓝图终于在纸上实现了。 但是还有一个问题（问题真多，难怪人说科学是由问题产生的，现在我才理解），解密电路是属于 permitted functions 集合里的么？可能有人会说，方案中不是有解密电路么， Evaluate 应该可以运行它吧。另外还有人说，按照上面方法把解密电路表示成增强电路不就行了。别忘了，增强型电路是含有解密电路的，所以这样说等于由果来推因了。 AND 电路、 XOR 电路、解密电路都可看成是“原电路”（这个名字是我自己取的），就是说它们是构成任意功能函数的基石， permitted functions 集合里含有它们就完全够了。 前面我们已经解释了 AND 电路和 XOR 电路属于 permitted functions 集合的原因。唯一缺的就是没有证实解密电路也在 permitted functions 集合里。下面就来分析分析。

个人分类: 信息安全|8252 次阅读|0 个评论

整数上全同态加密方案分析（1）--献给全同态加密的初学者

热度 4 chzg99 2012-9-27 12:54

这篇文章是我当时给国外一个学者写的全同态加密的介绍。对方要求尽可能以简单的例子呈现，当时写着写着就成了一篇通俗的科普文章，我尽量用口语，假设对方没有密码学的深厚背景。由于简单的例子也需要大量的计算量，曾经为了一个小例子，我计算了好几天，还是没有出来，所以也就放弃了举例子的想法。愿此文能够领你进入全同态加密的门槛。国内好像没有这种科普学术的期刊。国外有个科学美国人就不错。好了，那就开始吧！ 一篇论文看完了，如果都看懂了的话，很多人觉得案例都是小菜一碟，但是在我写这个案例的时候我发觉论文看懂了，更需要案例或者说实现来进一步深入或者夯实，因为只有通过具体的实现步骤，才能发现有些在论文中的一些细节问题，反过来更可以促进对论文的理解。 整数上全同态加密方案有两篇非常经典的论文，一篇是《 Fully Homomorphic Encryption over the Integers 》以下简称 DGHV 方案，还有一篇是 Gentry 写的《 Computing Arbitrary Functions of Encrypted Data 》简称 CAFED 论文。入门者适合先阅读 CAFED 论文，这并不是说这篇论文简单，只是因为这篇文章的写法很通俗（严格意义上这篇文章并不是一篇真正的论文，是给杂志写的文章，有点科普性质），有一个很好的比喻的例子“ Glovebox ”贯穿于整个论文中， Gentry 的文笔很好写的也很生动，对有些地方进行了背景解释，而这些解释恰好是 DGHV 论文中没有说的，当然一开始要想把 CAFED 论文彻底读懂也不是那么容易的。这个时候可以开始阅读 DGHV 这篇论文。这篇论文对于我来说是百读不厌，因为有些地方就算读了一百篇也不见得可以理解，而且这篇文章很适合深挖，有些很有趣的地方，例如噪声参数的设置等等。还有一篇论文就是全同态的经典论文《 Fully homomorphic encryption using ideal lattices 》，如果对格不熟悉的话，可以读这篇文章的前面三分之一，因为有详细的全同态的定义、层级全同态、允许电路、增强解密电路、 bootstrable 、重加密原理，以及如何通过递归实现全同态的，尤其是递归实现全同态的过程，在论文中还是值得反复理解的。剩下的当然还有 Gentry 的博士论文，也可以分阶段阅读。 这篇文章就算是我的一个阅读笔记吧，我打算写两个部分，一个是实现过程，另一个是方案的参数分析。 一、 方案实现过程 1、 全同态加密方案 至于什么是全同态等等形式化定义我就不说了，请参阅论文。 全同态加密用一句话来说就是：可以对加密数据做任意功能的运算，运算的结果解密后是相应于对明文做同样运算的结果。有点穿越的意思，从密文空间穿越到明文空间，但是穿越的时候是要被蒙上眼睛的。另外上面的那句话是不能说反的，例如：运算的结果加密后是相应于对明文做同样运算结果的加密，这样说是不对的，因为加密不是确定性的，每次加密由于引入了随机数，每次加密的结果都是不一样的，同一条明文对应的是好几条密文。而解密是确定的。 全同态具有这么好的性质，什么样的加密方案可以符合要求呢？往下看： Enc(m): m+2r+pq Dec(c): (c mod p) mod 2= （ c – p* 「 c/p 」） mod 2 = Lsb(c) XOR Lsb( 「 c/p 」 ) 上面这个加密方案显然是正确的，模 p 运算把 pq 消去，模 2 运算把 2r 消去，最后剩下明文 m 。这个公式看上去很简单，但是却很耐看，需要多看看。 公式中的 p 是一个正的奇数， q 是一个大的正整数（没有要求是奇数，它比 p 要大的多）， p 和 q 在密钥生成阶段确定， p 看成是密钥。而 r 是加密时随机选择的一个小的整数（可以为负数）。明文 m ∈ {0,1} ，是对“位”进行加密的，所得密文是整数。 上面方案的明文空间是 {0,1} ，密文空间是整数集。 全同态加密方案中除了加密、解密还有一个非常重要的算法就是： Evaluate ，它的作用就是对于给定的功能函数 f 以及密文 c1,c2, … ,ct 等做运算 f (c1,c2, … ,ct) 。在这里就是对密文做相应的整数加、减、乘运算。 以上方案可以看成是对称加密方案。下面来考虑公钥加密方案。其实把 pq 看成公钥就 OK 。由于 q 是公开的，所以如果把 pq 看成公钥，私钥 p 立刻就被知道了（ p=pq/q ）。怎么办呢？看上面加密算法中，当对明文 0 进行加密时，密文为 2r+pq, 所以我们可以做一个集合 {xi ； xi=2ri+pqi} ，公钥 pk 就是这个集合 {xi} ，加密时随机的从 {xi} 中选取一个子集 S ，按如下公式进行加密： Enc(m): m+2r+sum(S); 其中 sum(S) 表示对 S 中的 xi 进行求和。 由于 sum(S) 是一些 0 的加密密文之和，所以对解密并不影响，整个解密过程不变。 这个方案是安全的，就是我们所说的 DGHV 方案。其安全性依赖于一个困难问题“近似 GCD 问题”。就是给你一些 xi ，你求不出 p 来（由于整数上全同态研究热了，近似 GCD 也成了研究的一个点）。 为了说明方便，我们还是采取 pq 为公钥的方案（尽管不安全，但是不影响说明过程）。所以加密和解密还是按照一开始的公式，现在 pq 为公钥， p 还是私钥， q 是公开参数。再重复一遍我们的加密解密算法： Enc(m): m+2r+pq Dec(c): (c mod p) mod 2= （ c – p* 「 c/p 」） mod 2 = Lsb(c) XOR Lsb( 「 c/p 」 ) 另外在这里约定：一个实数模 p 为： a mod p = a - 「 a/p 」 *p, 「 a 」表示最近整数 , 即有唯一整数在（ a-1/2, a+1/2] 中。所以 a mod p 的范围也就变成了（ -p/2 ， p/2 ] （这个牢记）。这个和我们平时说的模 p 范围是不一样的，平时模 p 范围是 ，那是因为模公式中取得是向下取整： a mod p = a –floor （ a/p ） *p 。 Lsb 是最低有效位，因为是模 2 运算，所以结果就是这个二进制数的最低位。 2、 可怕的噪音 由于公钥 pq 是公开的，所以知道密文 c 后可以减去公钥得到： c-pq= m+2r 由于存在 r 的干扰，所以无法识别明文 m 。我们就把 m+2r 称为噪音。另外在解密时只有当 c mod p=m+2r p/2 时 , 再对它进行模 2 运算才能正确解密： （ m+2r ） mod 2= m 。 如果噪音大于 p/2 时， c mod p 就不再等于 m+2r ，解密就可能无法正确恢复出明文。所以噪音是影响解密的关键。而噪音会在密文计算中增长，下面来看看增长的势头： 假设 c1= m1+2r1+pq1; c2= m2+2r2+pq2; 其中 c1 是对密文 m1 的加密， c2 是对密文 m2 的加密。 密文加和乘运算： c1+c2=(m1+m2)+2(r1+r2)+p(q1+q2) c1*c2=( m1+2r1)(m2+2r2)+p(pq1q2+m1q2+m2q1+2r1q2+2r2q1) (c1+c2) mod p= (m1+m2)+2(r1+r2) c1*c2 mod p=( m1+2r1)(m2+2r2) 由上可见：密文之和的噪音是各自密文的噪音之和；而密文乘积的噪音是噪音之积。因此噪音的主要来源还是乘法运算，在乘法运算中噪音被放大的很快。 例如：设 p=11, q=5, m1=0, m2=1 ，然后分别随机选取 r1=1 和 r2= - 4, 有： c1=Enc(m1)=m1+2r1+pq=0+2*(-1)+11*5=53; c1 mod p= -2, Dec(c1)=0. c2=Enc(m2)=m2+2r2+pq=1+2*1+11*5=58; c2 mod p= 3, Dec(1)=1. 因为 c1 mod p 和 c2 mod p 都是在（ -p/2 ， p/2 ）范围内，所以解密正确。 c1 和 c2 称之为新鲜密文 , 就是直接由明文生成的密文，在新鲜密文中噪音是在一定合理的范围内的。 我们再来看看 c1*c2: c*=c1*c2=53*58=3074; c* mod p=5, Dec(c*)= 1 ≠ m1*m2=0 , 解密错误，错误的原因是噪音 c* mod p= -6 不在（ -p/2 ， p/2 ）范围内。 看来对密文运算会造成噪音的增大，当噪音超出范围，解密就失败，这意味着对密文运算不可能是无限次的（也就是 Evaluate 运算功能函数的电路深度是有限的，这在后面我们说到电路时会看到）。到这里我们只得到了一个运算时噪音范围不能超过 p/2 的同态方案（ Somewhat 同态方案），看来似乎用这个方案实现全同态是行不通的。我们需要的是全同态方案即 Evaluate 可以运行任意功能函数，而不是某一类功能函数（这叫同态方案）。估计多少英雄好汉到了这里就觉得没戏了，于是另寻他路，于是一个突破就擦肩而过。那么下面让我们分析一下症结所在。

个人分类: 信息安全|23079 次阅读|5 个评论

[转载]搞定PDF不能复制的问题

热度 1 Bearjazz 2012-5-8 14:54

搞定PDF 不能复制 的问题 原文地址 http://blog.chinaunix.net/space.php?uid=10449864do=blogid=2956861 今天要写份文档，有一个比较好的 pdf 文档，想复制里面的一些内容，试了好几次都没有成功，开始还以为是键盘的原因，放狗搜了一下，有几个方法可以解决，最后实践发现， “Adult PDF Password Recovery” 这个软件最好用，而且转换速度比较快。 下载地址： http://www.jz5u.com/soft/security/recove/1851.html 这个软件是绿色汉化破解版的，使用很简单，就不啰嗦了。 编者：如果您在源地址下载不到软件可以联系我，给你传哈，祝您科研愉快！

个人分类: 我的研究|4635 次阅读|1 个评论

[转载]电脑硬盘私密文件如何加密

chnfirst 2011-12-1 13:55

http://www.wenbanzhu.com/%E7%94%B5%E8%84%91%E7%A1%AC%E7%9B%98%E7%A7%81%E5%AF%86%E6%96%87%E4%BB%B6%E5%A6%82%E4%BD%95%E5%8A%A0%E5%AF%86%EF%BC%8C%E6%9C%89%E5%93%AA%E4%BA%9B%E9%9A%90%E8%97%8F%E6%8A%80%E5%B7%A7%EF%BC%9F 电脑硬盘私密文件如何加密，有哪些隐藏技巧？ http://insurance.hexun.com/2011-07-01/131057279.html 放哪最安全?给你的隐私文件找个保险箱

个人分类: 电脑、办公|0 个评论

[转载]怎样给office 2010文档加密

zhao1198 2011-11-21 12:17

我们都知道，办公软件是一种极其重要的软件，尤其是我们所熟知的Office软件。我们可以在它上面轻松的制作幻灯片、表格等。但是有些重要文件 是我们不想别人知道的，比如 ，一些机密文件，所以 ，我们就要给它们设定一些密码。我在网上看了一下 ，有许多Office文档的加密经验。所以 ， 我也想制作一个经验 ，望大家指教。 首先我想说一下，此经验只适合于Office2010软件， 望大家多多包涵！ 工具/原料 计算机 办公软件 文档加密 步骤/方法 单击“文件”选项，在弹出的页面中选择“信息”。 在弹出的页面中选择“保护文档”， 单击“保护文档”，在下拉菜单中选择“加密文档”。 在弹出的“加密文档”的窗口的“密码”栏输入密码。 单击“确认”后，用同样的方法再输一遍密码。 单击确认后，如果两次输入的密码都相同，则会看到以下内容： 大功告成，在确认文档编辑无误后，可保存。 如果我们想再打开此加密文档， 文档就会提醒我们输入密码。输入正确的密码之后，才可以打开此加密文档。 注意事项 密码绝对不允许忘记，否则，无法打开加密文档！！ 不要向外人泄露密码。 极其重要的资料，还应该对其所在文件夹及磁盘加密，以防被破解。 密码区分大小写。

个人分类: MS|1994 次阅读|0 个评论

追风：ISI的思考

flamety 2011-9-24 15:57

引子：黑莓手机，加密过度无法监听 神经元编码规则，加密以去除干扰，典型isi频段差别。 ISI是形态决定还是化学通道决定,SP快慢决定峰值位置,——位置信息 分布函数的劈峰： 气体chotic，液体phasic， 晶体 tonic的SP 稳态模型，律动的吸引子？多稳态，多吸引子？ brain like do LOG coding! “数字感”的收获 Dr. Eugene M. Izhikevich

1 次阅读|0 个评论

数据的备份、加密、恢复与删除

热度 4 outcrop 2011-8-4 17:19

1、引言 打算从这一篇开始，逐渐形成自己的写作风格：那就是假定我的读者们都是善于思考、自学能力较强的人；根据一个线索和提示，能展开学习。因此以后将只讲述一些提示性的东西，减少技术细节描述。 电脑中的文件数据，一般是智力劳动的成果，不同场合下，可能需要对文件进行加密、隐藏、恢复与彻底清除等操作。 这里不得不提到数据安全的一个重要的原则是： 备份、备份、再备份 。 2、文件的备份、加密与恢复请移步： http://blog.sciencenet.cn/home.php?mod=spaceuid=1750do=blogid=358773 3、文件的删除 文件的删除，容易被大部分用户所忽视。简单的说， 一般我们在文件管理器中删除文件，以及格式化硬盘，并没有真正的删除数据 。有兴趣的老师同学，可以去关注下文件删除原理。 删除数据的恢复方法，可以参见上面的文章。 彻底删除文件，不借助其他软件的话，一个简单的方法，就是用无关数据填充硬盘的空白区域；借助软件删除的话，可以尝试Eraser（下载地址： http://eraser.heidi.ie/download.php ）等工具。彻底删除后，恢复难度极大，反正是超越了我的知识范围 4、结论 数据的安全，是最后一道屏障。一般来说， 备份 是最重要的工作，因为硬件必然会坏。 下篇博文将整理下关于局域网安全相关的资料：内容可能包括局域网里的数据欺骗、嗅探、劫持等话题，欢迎有空关注我的博客（ http://blog.sciencenet.cn/u/outcrop ），或者加入知识管理与信息安全QQ群：72575661交流。

个人分类: 计算机应用技术|4672 次阅读|10 个评论

私秘染房真好

maxuejia 2010-10-30 21:39

用过秘私染房吗？那是一款很棒的隐私文件保持工具。使用方便，安全性好。在那里，文件加密被称为涂染，解密被称为恢复。你家里有没有隐私文件？千万要保护好啊。

个人分类: 未分类|2689 次阅读|0 个评论

[转载]win7下两种加密方式，EFS和Bitlocker，孰优孰劣？

zoujingzone 2010-6-1 09:49

转自 http://bbs.pcbeta.com/thread-686655-1-1.html EFS，即 Encrypting File System，加密文件系统。从windows2000开始提供 Bitlocker，从windows vista开始提供，windows 7扩展到bitlocker to go。 bitlocker 和bitlocker to go还是有区别的，bitlocker用于加密系统分区，使得攻击者无法使用脱机攻击修改 用户 登录 密码 或者直接盗取用户数据。bitlocker to go 主要是加密其他数据 磁盘 。要求不像bitlocker必须使用TPM或者钥匙 U盘 来解锁，而是可以通过密码来解锁。 加密算法方面，Bitlocker使用128位或者256位的AES加密。EFS可以使用DESX（windows2000以后）3DES（XP以后）AES-256（XP SP1以后）， win7 默认的是AES-256算法。可见两者的加密等级是差不多的，AES也是目前广泛应用的安全算法。 灵活性方面，EFS加密单个文件，Bitlocker只能加密整个分区。EFS要更灵活一些。 从泄密可能方面，EFS加密单个文件，但是页面文件和休眠文件无法加密。攻击者可能通过翻看你页面文件中的数据得知你的隐私。而bitlocker强调整个分区加密，数据如果不存在加密的磁盘上就会存在内存上。当内存掉电以后攻击者无法通过任何非法手段取得信息。但是另一方面，如果Bitlocker to Go的用户使用密码解密，而密码又过于简单的话，会留下漏洞。而EFS强制使用多位 证书 来保证安全，密码复杂度是能够保证的。 EFS的另一个问题在于，文件名是不会加密的，文件名同样涉及个人隐私，尤其是当你的照片命名为圣诞节在北京元旦在日本春节在海南的话，别人虽然看不到照片但知道你去了哪里。同样，文件名也可能泄露你的姓名年龄电话住址等各种信息。尤其对于一些AV收藏家来说，光看文件名就知道你收藏的是哪位女星的了。 Bitlocker无疑更安全，在没有解密的时候是根本无法访问分区的任何字节的，连有多少文件都看不出来。但是问题在于，Bitlocker过于强调全盘加密的特性，系统 性能 下降是肯定的。你想任何页面交换，临时文件的操作读取，都要涉及加密和解密，哪怕是AES算法再简单也终归会影响系统性能。Bitlocker to go加密移动磁盘等无疑是一个好主意，缺点是只有win7能够很好的使用Bitlocker to go的磁盘，限制了U盘的使用范围。EFS同样面临这个问题，想要别人能够访问我的文件还需要对应的证书，证书和密码不同，涉及比较专业的知识，操作上比较难以处理。 个人 感觉 ：EFS最大的缺点在于不能加密文件名，bitlocker最大的缺点在于必须加密整个分区。 bitlocker预防离线攻击用的。 EFS是加密文件用的 微软在最新的 Windows 7 操作系统的旗舰版中为用户提供了一个强悍的BitLocker加密功能，该技术其实最早是出现于 vista 系 统中，BitLocker加密技术能够同时支持FAT和NTFS两种格式，用来加密保护用户数据，可以加密电脑的整个系统分区，也可以加密可移动的便携存 储设备，如U盘和移动硬盘等。Windows 7旗舰版中的BitLocker加密功能在之前版本的基础上有了更多的改进，其中对U盘等移动存储设备进行加密的BitLocker To Go就是最新加入的一项功能 google_ad_client = "pub-1732206342303357"; google_ad_slot = "4389161096"; google_ad_width = 728; google_ad_height = 90; google_protectAndRun("render_ads.js::google_render_ad", google_handleError, google_render_ad); EFS Bitlocker Bitlocker to Go 算法强度 优秀 优秀 优秀 保护全面性 一般 优秀 优秀 选择 一部分加密 能 不能 不能 对系统性能影响 小 大 中 容易操作 复杂 简单 简单 疏忽导致数据不可恢复 容易 不容易 不容易 移动数据 复杂 - 容易 系统兼容性 XP SP1+ Vista+ Win7+ 由于人造成的漏洞 小 小 大

个人分类: 科普集锦|76 次阅读|0 个评论

验证与破解的博弈

creator 2010-5-11 22:39

现在很多软件或网站都有验证码及数字签名等验证方式，但是脱壳，图像识别破解也在大行其道。 验证码及一些验证技术主要是为了防止机器人，在博客及评论模式热起来以后，很多人利用这个平台来打广告，甚至破坏正常的留言，比如科学网的留言系统就有很大漏洞，首先匿名留言的验证码容易破解，其次可以注册用户机器留言，这是一个容易受攻击的模式。 先看下为了防止机器人破解，大家都相出了什么招式： 来源： http://cn.engadget.com/2008/09/02/15-bt-captcha/ 1， 数学类 简单的加减乘除就不列举出来。 这种验证码的好处是需要一定的数学水平，可以较为有效的防止未成年人的进入，一般而言，未成年人都不能解答出上述结果。但缺点是比较费时。 比较适合成人网站验证，但是对于不懂数学的色狼是个问题。 2，扭曲型 采用不同字体及变形模糊效果是比较常用的办法。有效度70%以上，一般的识别软件都只能准确识别30%左右，但有时人也会识别错误。 当然这其中也包含很难辨别的内容。 3，化学知识或其他知识 一般包含各专业知识，很多专业的论坛都会提一些专业的问题，以防止机器人侵扰。 4，背景影响类型，跟第三种有类似的地方，但是能引起误识别，而不是普通的干扰背景。包括GIF动画类。 5，图形二次替代 这种图形的识别可以做到很难，而且需要替换理解。破解较难。这种值得提倡，简单高效。 6，特殊知识类型 这个需要较强的空间想象力，而且有时间限制。当然这里也可以借助图论，拓扑学，智力测试题里的一些东西来验证。比较变态。适合高难度的论坛注册，考考你智商够不够，不够格就不能加入。 这种类型的可以扩展成很复杂的验证识别，比如验证识别是时间限制的智力题或者下棋，如果没有较强的专业知识，是不可能破解的。假设将这种识别方式放在保险柜的识别上，而用户是一个五子棋或象棋爱好者，那么设置定时棋局，那么没有水平是不能打开这个保险柜的。甚至将一盘围棋的棋谱作为验证方式。 7，图形或情感验证 这是一种情感认知的验证，除了采取统计破解方法有点希望外，很难破解。 这里可以拓展一种方式，即人像识别的方式。比如以爱因斯坦的头像为例： 假设爱因斯坦，特斯拉和爱迪生的图片代表不同的数字或字母，那么提问可以是先爱因斯坦后特斯拉这样排列的字母数字组合是什么？为了防止统计识别，可以如爱因斯坦的红蓝框所示，每次随机截取分块，或者在图上随机破坏一块信息，比如扭曲，替换等方式，这样不影响人的识别，但是会影响统计破解。剩下的唯一一条破解路是图像识别了。 如下验证码基本能被破解了，很多OCR软件相当的厉害了： （图片来自网络） 所以要采取更高级的验证码。 验证码与图像识别的博弈，胜的一方常常是验证码。 毕竟图像识别的准确率还不高，比如汽车牌照，人像识别都还有待提高。图像识别问题没有完全解决，那么验证码就可以大行其道，使得验证码始终占据博弈上风。 利用这种方式来加密： 在我以前的博文有提到过，因为现在的破解都是靠计算机的高速破解计算而获得，即Bruce暴力破解居多，这样越是先进的计算机就越占便宜。所以很多黑客及过滤设备就能解密过滤，以达到截获信息的目的。现在假设每次解密或破解都必须人工输入验证码会怎样呢？所有的破解装置会变成破铜烂铁。实现方式就是将密文转化为验证码并二次加密，比如先用AES加密，然后将密文的一段转化为验证码，然后将验证码的二进制码插入密文二进制码中，混合再用一种加密方式加密。这样即使先把后一种加密破解了，也面临人工识别验证码并输入信息的过程，这一过程计算机无法自动完成。所以整个解密过程必须人工干预，这样其将无法通过自动破解来获得信息内容。黑客及不法分子在实际的信息拦截过程中，面对是海量的信息，采取的是随机或指定抓包来提取，即便如此也是要处理很多信息，如果要人工干预，破解量将相当有限。但是这样也会给使用者带来麻烦，会增加操作复杂性及计算耗费。 但是能带来很大安全性，比如瑞星杀毒在卸载时会输入验证码，某些权限的实施需要有人工识别过程，以免机器人或病毒破坏。特别是一些高级权限为了防止截取或非法操作，使用这些验证过程可大大提高安全性。 除加密软件外，其他软件也可以采用这种方式来加密或注册验证，在脱壳的过程中需要考虑验证问题时就会增加难度，或者在线注册时就可以减少欺骗和机器人干预。 保险柜，门禁等就可以量身定做，根据客户的特点来定制加密模式，比如采取游戏胜负验证加普通密码验证，但是对设备要求会很高。 最大的用途还是在网络传输及远程权限设置等环节，这些领域有更好的安全性才行，加了更多高级的验证码验证机制比普通的VPN+ssl模式更安全。

个人分类: 科学|2202 次阅读|0 个评论

关于火车票实名制的一个新算法

billzhenxing 2010-2-23 23:05

过年,一张小小的火车票, 愁死这么多人. 作为一个搞计算机的人来说，我很惭愧, 对于火车票的购买就没有一个好的算法来解决吗? 完全可以让我们这个领域的牛人（不是我） 设计一个合理的算法. 命题的适用范围 （需要解决的问题）: 1. 我的算法可以有效解决一人购买多张票(即可防止黄牛倒票) 2. 可以杜绝假票.(假票估计现在的系统就可以杜绝大部分假票) 3. 现在的火车票上的个人信息太多，容易泄漏。 算法描述:(我有没想到地方大家给我补充,给我提出新的问题,我在完善我的算法) 1. 我们可以像公交车的交通卡一样, 给买火车票的人办一张这样的卡, 反正这些过年回家的农民工兄弟,学生....每年至少也要做2次火车(即返乡一次), 所以可以用几十年(甚至终生), 2, 这张卡里保存本人的身份证号,以及火车的目标站信息(比方说目标是B站)。这样一个人在一天（假设到达目标站需要1天）之内只能买一次。到达目标站之后，出站的时候交通卡消磁，然后才可以买返程的火车票。这样顺便也杜绝了逃票的现象。如果是往返，那么就在往返的期限内只能买一次这个区域的车票。如果还想去别的地方， 这样的交通卡如果制作，具体不知道多少钱，估计不会太贵。这个成本费我认为农民工也可以负担，因为这张卡受用终身，而且可以保证如果有座的情况下可以买到票。所以大部分人愿意办理。如果以后效果好，可以强制办理。 3，这个交通卡的办理可以到提前到车站派出所办理，或者其他的派出所办理，代售火车票的地方不可以代办。如果有黄牛办理这种假的交通卡，也可以杜绝。方法如下： a, 首先这张卡全国独一无二，如果别人用了你的卡买了火车票导致你买不到火车票，你马上可以到车站相关公安部门举报，只要你带着身份证，证明你de卡被别人盗用，那么这张卡的信息马上就可以在系统查到，持假卡的人在哪里下车，那么在系统上修改， 这个持假卡的人就出不了站，自然可以抓到他，问他从哪里买的假卡，从而可以抓到高科技的黄牛。这个黄牛跟盗取别人信用卡的罪名差不多（具体这里不讨论）， b, 举报以后，你的交通卡就又可以正常买票了。最起码你买上票以后。黄牛即使还拥有你身份证号的假交通卡，他们也定不上票了。除非他们认识公安里边的内鬼。 c, 如果没有抓到高科技黄牛，那么你的卡还可能被盗，你以后还是有可能被黄牛抢先一步买票。这个问题的解决就需要，订票的时候来解决。 3, 订票的时候预防靠科技黄牛抢先订票，这个牵扯到手机的实名制（或者网络实名制）。 a, 如果交通卡也是实名制，手机也是实名制，那么订票的时候，可以用手机收到的识别码来解决这个问题。这个识别码是即时任意产生的。不可能被盗用，而且它只能发给本人的手机，高科技黄牛也没有招。 b, 现在还没有实行手机实名制，被黄牛抢先订票，只能就是按照3a的办法作了。

个人分类: 科研相关|12 次阅读|0 个评论

简单的fortran加密解密程序

dabing 2009-11-23 16:45

加密 解密

个人分类: Fortran文档|8643 次阅读|0 个评论

［投稿］公钥安全机制与宫爆鸡丁的故事

eloa 2009-4-20 12:18

科学松鼠会 发表于 2009-04-19 2:21 by Fantix 你有没有在网上买过东西？没？什么？哦，怕不安全。 现在信息科技日新月异，貌似一转眼的功夫，交电话费、考试报名、逛图书馆、订购午饭都搬上了互联网。方不方便且不说，单说足不出户能叫到午饭，这要在以前那可都是科幻小说啊。只不过科幻小说里，主人公可能只须对机器人吩咐说，来份宫爆鸡丁盖饭，外加一碗紫菜鸡蛋汤，一切就搞定了哪像现在这样，装五花八门的杀毒软件，还得随时小心钓鱼网站的陷阱。那现在的互联网真的如此危险么？先看看大宝的这次订餐经历，您再下结论也不迟。 话说大宝一日宅在家中，百无聊赖地度过了阴雨连绵的上午，忽然感觉腹中空虚，四肢无力他明白了，原来自己是饿了。闲话少说，大宝奔到电脑前，准备给自己淘一顿午饭。 飘过了几家附近的餐馆之后，大宝决定在啃的鸡点一份宫爆鸡丁盖饭套餐。点完菜，服务员小姐礼貌地将大宝带到了收银台这啃的鸡是先付帐、再上菜的。 （传说中的宫爆鸡丁。来源： princeroy ， cc-by-2.0） 如果互联网上也可以用现金买单就好了，那么啃的鸡也不用再多花冤枉钱，聘用专业的银行交易专家来收银了。可惜现实往往跟理想相反，坐在收银台里的，正是传说中的银行交易专家：致富宝。致富宝作为专业的支付中介，能非常熟练地处理各种银行业务不管是招行信用卡，还是农行借记卡，他都能应对自如。 就在这个时候，大宝忽然发现，带他来的服务员小姐溜回啃的鸡铺子里忙其它事儿去了，这致富宝原来是街边的一个小摊。再看这位摊主，正拿着宫爆鸡丁的单子，对着大宝得意地笑。大宝顿时惊出一身冷汗。 糟糕！上当了！ 大哥，这宫爆鸡丁儿不是你点哩？摊主口音挺重。 是倒是你就是那个什么什么银行交易专家？大宝半信半疑。 那能假了啊！你看看，工行农行中行建行摊主不高兴了。 得得得，你要是个钓鱼的，也照样这么说。大宝摆事实、讲道理，营业执照给我看看，是真的就行。 钓鱼 是指一些小商小贩，冒充自己是某支付平台或银行，骗取大众钱财的手段。 俺哪敢掉你的鱼啊！摊主边说，边从口袋里掏出一份证书，你验验，这能假了不，这会儿打（假）的正严哩。 这份证书可不是一般的营业执照。在数字世界里，光一个红红的公章印，说明不了什么问题。互联网上的电子证书，不仅包含一些基本信息如摊主姓名、工作单位、邮政编码等，还包含一把很重要的钥匙，和一个很重要的签名。 先说这把钥匙吧。其实这种钥匙是成对儿的，证书里面嵌的这把，叫做公钥；另一把由摊主保管，叫做母钥？其实挺合理的，配对嘛正确的叫法是私钥。从名字也可以看得出来，公钥是公开的，大家都可以拿来用；而私钥是个人保管的，比如摊主的这把私钥就由他个人保密持有，别人谁也拿不着。 这里，配对的两把钥匙之间是有数学相关性的，那这是怎样一种相关性的？用传说中的 RSA 算法举个例子吧，两把钥匙看上去是三个非常大（至少应该是，大的难破解嘛）的数字私钥是 (7, 10)，公钥是 (3, 10)。 那这钥匙是怎么算出来的呢？ 先选种子，随机选两个非常大的 质数 。在这个例子中，我选的是 2 和 5，但实际应用中应该越大、越没有规律越安全。这个时候，钥匙对中的公共部分 10 就算出来了：2 x 5 嘛。接着，3 也不难找随便挑一个跟 (2 - 1) x (5 - 1) = 1 x 4 = 4 互质 的、且比 4 小的数就可以了 3 和 4 没法被同一个比 1 大的数除开，这样一来，我们的公钥 (3, 10) 就定下来了。接下来算私钥，这个稍微麻烦一点点，就是要找一个乘以 3 的积除以 4 的余数刚好等于 1 的数字我选了 7，因为：7 x 3 mod 4 = 21 mod 4 = 1（这里的 4 还是前面 (2 - 1) x (5 - 1) 算出来的那个 4）。用数学点儿的话写下来，就是： 随机地选择两个非常大的质数 p 和 q，比如 2 和 5； 密钥对的公共部分就是 N = pq，就是例子中 N = 2 x 5 = 10； 算出一个中间数 M = (p - 1)(q - 1)，比如 M = (2 - 1) x (5 - 1) = 1 x 4 = 4； 选择一个小于 M，且与 M 互质的数 e，比如 e = 3； 根据 d x e mod M = 1 算出 d，比如 d = 7 因为 7 x 3 mod 4 = 1； 烧掉所有写着 p 和 q 的打草纸因为 不烧不专业 嘛。 然后呢，公钥就是 (e, M)，或者简单说 3 也成，对应的私钥就是 7，而 10 是公共部分。 那这两把钥匙有什么用呢？我们还是先来做两道简单的数学题。 第一题，8 的 3 次方整除 10 的余数是多少？八八六十四，64 乘以 8，这个 64 乘以 8 不好算是吧，没事，这个例子可以偷点懒只算个位数，反正不是要整除 10 么。8 x 8 = 64，4 x 8 = 32，结果就是 2 呗。 第二题，（用第一题的结果）2 的 7 次方整除 10 的余数是多少？2 x 2 = 4，4 x 2 = 8，8 x 2 = 16，6 x 2 = 12，2 x 2 = 4，4 x 2 = 8 数清楚了没，是 7 个不？结果正是 8。 没错，第二题的结果刚好是第一题里面的 8。这是一个巧合，还是一个愚人节玩笑？都不是，这是用数学方法证明过的（请见下面的分割线中间的部分），如果算出来不是 8 才是开玩笑呢。第一题中，我们其实用公钥 (3, 10) 把 8（我的银行卡密码，请勿模仿）给加密了加密成了 2；第二题，我们又用私钥 (7, 10)，把加了密的密码给解出来了。 （二战德国所使用的的洛伦兹密码机。图片来源： wikimedia ） 有那么点意思了，是吧。这样一来，我就可以用密文的 2 来代替明文的 8，放心地将密码告诉拥有私钥的人。即使密码中途被别人截获了，没有私钥的 骇客 依然无法取得我的密码。 有兴趣的话，您可以把公私钥匙调个个儿，再用相同的办法算一遍也就是用 7 加密、用 3 解密，结果是一样可以还原的。但是反过来之后，如果我还是加密银行卡密码的话，我的智商就值得研究了作为公钥的 3 是所有人都知道的，也就是说所有人都能解密得到原文，我根本用不着费事算来算去，直接把密码告诉大家就得了呗。这么做真的没有意义么？非也，这其实正是签名和验证。比如说，用 (3, 10) 是无法正确解密（验证）一段用 (5, 17) 加密（签名）的数据的，也就是说，解铃仍须系铃人，要想验证一个签名，只能用跟签名用的私钥对应的那一把公钥。而从理论上来说，私钥是个人保密持有的，所以我们可以通过解密的测试，来验证一段信息确实是原原本本地来自拥有私钥的人，而这个人也无法抵赖说根本没这么回事儿。 除非他把私钥弄丢了，别人捡了去。这一般情况下是有补救措施的挂失嘛，钥匙丢了换锁呗。但是如果你根本不知道钥匙丢了，那就没辙儿了。比如说，既然 3 和 10 大家都知道了，如果什么人背地里偷偷算出了这个 7，那岂不是千里之堤，溃于蚁穴？ 不必担心。 问题就在于，这个梁上君子打算怎么把 7 算出来。最直接也是最容易想到的办法，就是先将 10 分解成两个质因数 2 和 5，然后照前面的算法来算 7。这是唯一的办法吗？很遗憾，目前还没有人从数学上证明这是唯一的办法。为什么有人会去试图证明，这是唯一的办法？因为，他们还没找到其它更好的办法。恰巧，这个分解质因数的办法非常难。 因为打草纸烧掉了，所以理论上说，暂时没有别人知道 10 是由哪两个质数相乘得到的，一般情况下，算这个题的人（或是机器）也会很快忘掉这两个质数。虽然要破解前面的例子简单了点，但是有种你口算个一百来位的试试，呵呵。这也被相信是 RSA 算法的安全保障对于非常大的数字，分解出两个质因数是非常困难的。这个结论目前还没有人证明，但也没有人证明它不困难。尽管大家说法不一，但是有一点是肯定的数字越大越难算。有多难呢？ 1999 年计算机花了五个月的时间 ，解出了一个并不算很大的（512 bit）N 的两个质因数；而当 N 成倍增长时，破解的时间能到成百上千年等到破解出来的时候，加密保护的信息可能早就不是秘密了。据说有人证明用量子计算机，可以在可观的时间里，破解更大的数字。看来一旦量子计算机成为现实，RSA 就要下课了可惜眼下量子计算机还行不通，再加上我们选用的数字非常大，所以想简单地把 10 分解成 2 x 5，那是不可能的。 于是，要根据公钥 3 算出私钥 7 来，就几乎是不可能的了。所以，摊主可以安心地将公钥嵌在证书里，公之于众。例子中的 RSA 看似牢不可破，但现实中还需要许多的辅助手段，来进一步保证它的安全性。况且世界上也不是就 RSA 一家呀，所以嘛，这种公钥加密算法还是挺让人放心的。 总结一下了：解铃仍须系铃人，系铃定是解铃人（下半句我瞎掰的）。公钥、私钥都是一对儿一对儿的；要解密由公钥加密的数据，仅可以用对应的私钥；要验证由私钥签名的数据，仅可以用对应的公钥。这种一个加密另一个解的算法，一般就被形象地叫做非对称加密算法，这俩把密钥也被叫做非对称密钥。 如果这还没有满足您浓厚的数学兴趣的话，您可以继续阅读下面这段。（摘自维基百科， RSA加密算法的操作 不过貌似英文版更详细一点点） ==========哦美丽的分割线========== 公钥和私钥的产生 假设 Alice 想要通过一个不可靠的媒体接收 Bob 的一条私人讯息。她可以用以下的方式来产生一个 公钥 和一个 密钥 ： 随意选择两个大的 质数 p 和 q ， p 不等于 q ，计算 N = pq 。 根据 欧拉函数 ，不大于 N 且与 N 互质的整数个数为（ p -1）( q -1) 选择一个整数 e 与（ p -1）（ q -1）互质，并且e小于（ p -1）( q -1) 用以下这个公式计算 d ： d e 1 (mod ( p -1)( q -1)) 将 p 和 q 的记录销毁。 e 是公钥， d 是私钥。 d 是秘密的，而 N 是公众都知道的。Alice将她的公钥传给Bob，而将她的私钥藏起来。 加密消息 假设Bob想给Alice送一个消息 m ，他知道Alice产生的 N 和 e 。他使用起先与Alice约好的格式将 m 转换为一个小于 N 的整数 n ，比如他可以将每一个字转换为这个字的 Unicode 码，然后将这些数字连在一起组成一个数字。假如他的信息非常长的话，他可以将这个信息分为几段，然后将每一段转换为 n 。用下面这个公式他可以将 n 加密为 c ： 计算 c 并不复杂。Bob算出 c 后就可以将它传递给Alice。 解密消息 Alice得到Bob的消息 c 后就可以利用她的密钥 d 来解码。她可以用以下这个公式来将 c 转换为 n ： 得到 n 后，她可以将原来的信息 m 重新复原。 解码的原理是 以及 ed 1 (mod p -1)和 ed 1 (mod q -1)。 费马小定理 证明 和 这说明（因为 p 和 q 是 不同 的质数） ==========哦快乐的分割线========== 好了，回到我们饥肠辘辘的大宝的故事来吧。 我现在验证一段话，如果你能解出来，就算这营业执照是你的吧。大宝说着掏出一张白纸，背着摊主在纸上胡乱写下几个字戈壁滩上打酱油。 大宝从证书中取出钥匙也就是公钥了，再在纸上这么一比划，戈壁滩上打酱油几个字儿顿时被加密成 0101110（篇幅所限，此处略去上千个 0、1）1010101。 给你，试试吧。 我说是我的就是我的，摊主从怀里摸出一把旧钥匙（私钥，当然要藏好了），又在纸上一比划，那还能错的了了！ 0 和 1 渐渐隐去，戈壁滩上打酱油几个字儿又冒了出来解密验证成功，大宝无言以对，只得承认证书里的公钥的确是摊主本人的，除非摊主从真所有者那里抢的私钥。 好吧，就算这证书是你的吧。那你凭什么说，你就是证书上写的，大宝撇了一眼营业执照，什么致富宝什么的？ 大宝说的没错，每个人都可以伪造证书，就算这公钥确实属于他又能何如。 这买卖真难做！我不干了！摊主这回真的急了。 你不干了，我还要吃饭呢！大宝也急了，二话不说把摊主拉到了工商局 颁发营业执照的公信机构 。（可见，吃饭对大宝来说是多么重要） 到了工商局，办事员业务非常熟悉。 证书真伪辨别是么，请出示证书。 办事员拿着手持式扫描仪一扫，证书复印件就叮叮当当地出现在一旁的打印机中。只见他操起一把大剪刀，对着复印件咔嚓就是一刀，将证书拷贝一份为二。要不说他业务熟悉么，这一刀不偏不倚，刚刚好把前面提到过的电子签名部分剪了下来。 要说这电子签名是啥，还得先说这证书是怎么签发的。 （证书是怎样炼成的最右边 OK 的那个。图片来源：OpenClipart.org，GFDL） 当初致富宝开道创业的时候，写过一份营业执照申请函，内容就是现在这剪下的两半中，比较大的那一半电子签名是小半。工商局在评审了申请函之后，准予营业，于是签署了这一份证书，而证书中的电子签名正是官方签署的证据。 这到底还是公钥和私钥的讨论。话说工商局自己也有一对儿密钥，专门用来签署营业执照。当申请函得到批准的时候，办事员用工商局专用私钥在申请函上一比划，这申请函就被加密成了一段电子签名，也可以说，工商局在申请函上签名批准了。请注意，这申请函里到底包含什么呢？正如前面提到过，基本信息是必须有的，另外一个很重要的部分就是申请者或者叫摊主的公钥。毕竟公钥也是一种数据嘛，当作申请函数据的一部分来加密了。别弄浑了哦，办事员用工商局的私钥，加密了包含有摊主公钥的申请函，制作成了摊主证书的电子签名部分。这工商局的私钥可是公信机构独有的，平常要锁在很大的保险柜里的，所以签署出来的证书才是真的。 那我们就看看下一步，办事员怎么来辨别真伪吧。 这是我们工商局的公钥，大家可以免费索取的。办事员从柜台里搬出一箱子钥匙，说。 那照这么说，有了这个，大宝捡起一枚钥匙说，我自己也能辨别真伪咯。 没错。办事员也拿起一枚钥匙，在电子签名那一半上一比划，龙飞凤舞的电子签名乎的一下，变成了一份申请函的模样。 哎哟，好像不对哦。办事员拿过剪下的大半，跟刚解密出来的申请函一比，这哪是致富宝啊，明明写的是致富堡嘛。 大宝四下一看，那山寨摊主早溜之大吉了。真是虚惊一场，好歹大宝没有把钱给了那钓鱼的山寨摊主。 理论上，假的电子签名是不可能解密成跟原文仅一字之差的实际上是什么都解不出来的，只有真的签名才能解出原文来。另外为了减小数据量和其它考虑，原文在签名之前，做过摘要处理。故事中做了一些简化，特此声明。另外，虽然说两种密钥都可以加解密，但专业地来说，公钥是用来做加密和验证的，私钥是用来做解密和签名的。 如果您拥有一份个人电子证书，那么您也可以用您的私钥签署数据比如发电子邮件，那么收到信的人都可以用您证书中的公钥进行验证，以确认信件肯定是您亲笔签署的；反之，如果您的朋友有一份电子证书，那么您就可以很放心地用公钥加密一些只有您朋友可以阅读的数据，然后安全地通过您不信任的传播媒体比如互联网传递到您朋友的手中。电子签名在一定程度上，还保证了数据的完整性和不可抵赖性。 （一封给大宝的签名信，计算机可以验证其中的 PGP 签名） 后面发生的事情，就是大宝跟他验过真身的致富宝隔着一条河交易的过程了。没错，我是说隔着一条河这个城市似乎忘记修桥了，大宝只能扯着嗓子喊，把他的银行卡密码告诉致富宝才行。现在互联网啊，真是危机四伏，你说那个路由节点上没趴着三五成群的嗅探器的（夸张手法，请保留意见）。要是大宝真个把密码喊出来，那没等他吃完饭，卡里的钱就全没了。所以咧，大宝就跟致富宝商量了一个办法。 这个办法当然就是加密咯。大宝想用对方的公钥加密自己的密码，然后喊过去，对方解密出来就搞定了。但问题是，大宝的数学实在是太差了，要算乘方的话，手指头根本不够他掰的。况且，要加密的也不仅仅只是 6 位密码，还有像中国农业银行青岛市分行麦岛支行这样的银行名，还有很长的银行卡号，更是还有大宝的大名大卫／阿基米德／宝兰德／罗纳尔迪尼柯夫斯基。要让他把这些都加密算出来，非把他饿死不可，非对称加密算法并不适合于大批量的数据加密。所以，大宝想出了另一个办法 对称加密算法 。 说白了，就是用同一个，也是唯一一个密钥做加密解密的算法。原因么，简单呗。比如说，银行卡密码还是 8，那么加密就是 8 x 9 = 72，解密就是 72 / 9 = 8，这里的 9 就是对称密钥。 这种办法的缺点很明显，在双方进行加密通信之前，必须得先商量好一个对称密钥。并且一旦这个对称密钥丢了，那么所有数据都不安全了。像大宝这样隔着一条河，大声地告诉对方喂～密钥是 9！你除以 9 就行了！，无异于直接把密码告诉守在一旁的骇客。 大宝也不笨。9 作为对称密钥，不也是串儿数据么，反正也不长，用刚才想用的非对称加密算法，加密了再喊过去就是了呗，问题解决。 但是，这单单一个 9 实在是太好猜了，骇客只须认得九九表，就能一个一个地试出来。相比于用成百上千年才能破解的非对称密钥，数到九九八十一简直就是一眨眼的功夫。 不过要么怎么说魔高一尺，道高一丈呢，大宝有的是锦囊妙计。他把密码、银行名、卡号、持卡人姓名拼在一起，再随机分成一小份儿一小份儿的，然后用不同的对称密钥，分别加密。这样就增加了破解的难度，即使骇客破解出其中的一部分，也无法得到足够的信息去盗取钱财。而实际中，还有更多的锦囊来保证信息的安全。 于是，我们就看到大宝为了买到他的宫爆鸡丁，开始了 0 和 1 的传输。他先随便定下了一个对称密钥，然后用致富宝证书的公钥对其加密并传给对方；等对方解密出同一个对称密钥之后，大宝开始用对称算法加密传输数据；过了 1 分钟，暂停传输，重新定一个新的对称密钥，重复上述过程，直至数据全部传输完成。顺便说一句，这种为了安全和效率的综合考虑，混合使用对称算法和非对称算法的方法，叫做数字信封机制，像 HTTPS 、 SSH /SFTP，以及选择使用 SSL/TLS 的 IRC 、 IMAP 等协议，都是采用类似的这种机制实现的。 密码正确，确认付款，大宝终于吃到了他的宫爆鸡丁，故事也到此告一段落了。但是现实生活中，如果您在网上交易的时候，应该怎么做，才能保证数据的安全呢？ 首先，您可以仔细观察浏览器的地址栏，如果是像https://fantix.org这样以 https 打头的地址，那么您可以相信，至少这个地址采用了上述公钥办法做验证，并且所有数据都是加密传输的；否则如果是像http://fantix.org这样的 http（没有 s）打头的，就完全没有公钥私钥这一说，更没有身份验证的机制（只是说传输协议上没有保证，不代表不通过其他方法进行加密或验证），并且，发送未加密的数据就如同在互联网上喊一样，相当危险。 （我的网站已经加密，但貌似我的证书不是那么可信） 其次，一般浏览器像 FireFox ，都会自动验证服务器证书的真伪，比如域名是否相符，是否在有效期内等。并且一般浏览器内嵌了很多公信机构 CA 的证书（公钥），您不需要自己跑到工商局去，浏览器会搞定的。一旦发现有冒名顶替者，必然会弹出大字儿，提醒您不要上了钓鱼网站的当。（广告！FireFox 还可以辨识钓鱼网站，如您不慎勿入其中，则 FireFox 将用醒目的红字儿来警示您。） 在 FireFox 3 中，如果您浏览的页面被公信机构验证是货真价实的，证书合法有效，那么地址栏中https前面应该是 绿色的 ，点击它可以看到经营者信息；如果数据仅仅是加密过，不会被第三方窃听到的话，https前面的图标背景是蓝色的（如上图）；而对于普通的http协议，背景是没有特殊警示颜色的，比如在我的 Ubuntu 中，它是灰扑扑的。 补充说明，我们只谈了公钥安全机制，但并不是说绿色的标志就一定安全比如说一些木马就是最大的威胁。所以，如果您使用木马和病毒比较多的操作系统比如说 Microsoft Windows 的话（尤其是怕 黑屏 ，没有及时更新的盗版系统），我还是建议您，不要因为 FireFox 3 的绿色标志，就把杀毒软件、杀木马软件卸载掉。 这就是公钥安全机制与宫爆鸡丁的故事了，更流行的叫法是 PKI （Public-key Infrastructure, 公钥基础设施），包括一沓子算法、协议，还有一整套公信机构 CA（Certificate Authority，身份认证机构）的官僚体系。没准过不了多久，我们就会人手一份个人电子证书，连身份证都免了。 版本历史： 2009.4.14 - 修改了靠后面，前后不一致的一点点。添加图片、链接。排版。 2009.4.13 - 整理细节。 2009.4.7 - 替换了说理的那段，整理了一下逻辑，完善了论据。 2009.4.3 - 用真正的例子，替换掉了原来一个很白痴的例子。其他有微小改动。 2009.4.2 - 初稿完成。

个人分类: 其他|2067 次阅读|0 个评论