科学网 › 标签 › 加密

标签: 加密

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

没有相关内容

相关日志

[转载]你的数据库安全吗？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。是函数加密的一个最大进展。; 个人分类: 信息安全|19591 次阅读|4 个评论

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

可实践的同态加密：IBM发布了开源软件库: chzg99 2013-6-2 15:22; IBM在密码学上迈出了新的一步：发布了一个实现同态加密的开源软件库：HELib。 HE是英文Homomorphic Encryption(HE)的缩写。HElib也许会成为密码学上的一个里程碑。遥想2009年Gentry突破性的实现全同态加密方案时，该方案还是理论上的，并不能实现，而且理论上的效率也非常差。短短4年过去，软件库都开发出来了，而且还产生了一大堆优化技术，可圈可点呀！ Helib提供的是BGV方案的实现，以及提供了一些使得全同态加密更快的优化方法，例如：密文打包技术等。 HElib目前可能更多的是对同态加密研究人员使用，目前该库所提供的是都是一些简单的例程调用，例如：加法，乘法，移位等运算，可以把它看成是一个面向同态加密的“汇编语言”。今后还会及时的推出更多更丰富的例程调用。另外该库没有实现 bootstrapping ，提供的是层次同态加密方案，所以参数必须设置的充分大才能完成所需的计算。该库用C++和NTL数学库来实现的。; 个人分类: 信息安全|7913 次阅读|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 。可以互相交流。; 个人分类: 信息安全|10649 次阅读|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 可以运行任意功能函数，而不是某一类功能函数（这叫同态方案）。估计多少英雄好汉到了这里就觉得没戏了，于是另寻他路，于是一个突破就擦肩而过。那么下面让我们分析一下症结所在。; 个人分类: 信息安全|22985 次阅读|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交流。; 个人分类: 计算机应用技术|4639 次阅读|10 个评论

私秘染房真好: maxuejia 2010-10-30 21:39; 用过秘私染房吗？那是一款很棒的隐私文件保持工具。使用方便，安全性好。在那里，文件加密被称为涂染，解密被称为恢复。你家里有没有隐私文件？千万要保护好啊。; 个人分类: 未分类|2681 次阅读|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文档|8601 次阅读|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 个评论

更多...

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

关闭 安全验证

标签: 加密

相关帖子

相关日志

关闭安全验证