这个必须mark呀，楼主辛苦。最近在学pc端加密算法

Mark下，……

上一篇：从Android中RSA算法到密码学非对称性加密算法到大数因子多项式分解（一）

抱歉这周比较忙，更新慢了，书接上回。上回说到Android的签名体系中的非对称性加密算法，进而提出了公钥、私钥概念和RSA数字证书。今天就来说说这些概念和举例。

1.私钥公钥是什么？
一言蔽之：
私有密钥加密法=对称性密钥加密算法=加密解密都用一把私钥对应一套数学算法
公开密钥加密法=非对称性密钥加密算法=加密阶段产生两把数学性相关的、且能互解的、且算法不同的钥匙，一把由创造者保存为私钥，另一把分发给需要的用户为公钥。

以下是入门，高手略过直接看下面举例即可。对于新手虽然字多，看完后相当于你读了几十页的书

2.对称密钥加密法是什么？
私有密钥加密法<也叫对称性密钥加密算法>
指在计算机网络上甲、乙两用户之间进行通信时,发送方甲为了保护要传输的明文信息不被第三方窃取,采用密钥A对信息进行加密而形成密文M并发送给接收方乙,接收方乙用同样的一把密钥A对收到的密文M进行解密,得到明文信息,从而完成密文通信目的的方法。这种信息加密传输方式,就称为私有密钥加密法。上述加密法的一个最大特点是,信息发送方与信息接收方均需采用同样的密钥,具有对称性,所以私有密钥加密又称为对称密钥加密。

具体到电子商务,很多环节要用到私有密钥加密法。例如,在两个商务实体或两个银行之间进行资金的支付结算时,涉及大量的资金流信息的传输与交换。这里以发送方甲银行与接收方乙银行的一次资金信息传输为例,来描述应用私有密钥加密法的过程:银行甲借助专业私有密钥加密算法生成私有密钥A,并且复制一份密钥A借助一个安全可靠通道(如采用数字信封)秘密传递给银行乙;银行甲在本地利用密钥A把信息明文加密成信息密文;银行甲把信息密文借助网络通道传输给银行乙;银行乙接受信息密文;银行乙在本地利用一样的密钥A把信息密文解密成信息明文。这样银行乙就知道银行甲的资金转账通知单的内容,结束通信。

世界上一些专业组织机构研发了许多种私有密钥加密算法,比较著名的有DES算法及其各种变形、国际数据加密算法IDEA等。DES算法由美国国家标准局提出,1977年公布实施,是目前广泛采用的私有密钥加密算法之一,主要应用于银行业中的电子资金转账、军事定点通信等领域,比如电子支票的加密传送。经过20多年的使用,已经发现DES很多不足之处,随着计算机技术进步,对DES的破解方法也日趋有效,所以更安全的高级加密标准AES将会替代DES成为新一代加密标准。

私有密钥加密法的主要优点是运算量小,加解密速度快,由于加解密应用同一把密钥而应用简单。在专用网络中由于通信各方相对固定、所以应用效果较好。但是,私有密钥加密技术也存在着以下一些问题:一是分发不易。由于算法公开,其安全性完全依赖于对私有密钥的保护。因此,密钥使用一段时间后就要更换,而且必须使用与传递加密文件不同的途径来传递密钥,即需要一个传递私有密钥的安全秘密渠道,这样秘密渠道的安全性是相对的,通过电话通知、邮寄软盘、专门派人传送等方式均存在一些问题。二是管理复杂,代价高昂。私有密钥密码体制用于公众通信网时,每对通信对象的密钥不同,必须由不被第三者知道的方式,事先通知对方。随着通信对象的增加,公众通信网上的密码使用者必须保存所有通信对象的大量的密钥。这种大量密钥的分配和保存,是私有密钥密码体制存在的最大问题。三是难以进行用户身份的认定。采用私有密钥加密法实现信息传输,只是解决了数据的机密性问题,并不能认证信息发送者的身份。若密钥被泄露,如被非法获取者猜出,则加密信息就可能被破译,攻击者还可用非法截取到的密钥,以合法身份发送伪造信息。在电子商务中,有可能存在欺骗,别有用心者可能冒用别人的名义发送资金转账指令。因此,必须经常更换密钥,以确保系统安全。四是采用私有密钥加密法的系统比较脆弱,较易遭到不同密码分析的攻击。五是它仅能用于对数据进行加解密处理,提供数据的机密性,不能用于数字签名。

3.非对称密钥加密法是什么？
公开密钥加密法<也叫非对称性密钥加密算法>
公开密钥加密法是针对私有密钥加密法的缺陷而提出来的。是电子商务应用的核心密码技术。所谓公开密钥加密,就是指在计算机网络上甲、乙两用户之间进 行通信时,发送方甲为了保护要传输的明文信息不被第三方窃取,采用密钥A对信息进行加密而形成密文M并发送给接收方乙,接收方乙用另一把密钥B对收到的密 文M进行解密,得到明文信息完密文通信目的的方法。由于密钥A、密钥B这两把密钥中其中一把为用户私有,另一把对网络上的大众用户是公开的,所以这种信息 加密传输方式,就称为公开密钥加密法。与私有(对称)密钥加密法的加密和解密用同一把密钥的原理不同,公开密钥加密法的加密与解密所用密钥是不同的,不对 称,所以公开私有密钥加密法又称为非对称密钥加密法。

公开密钥加密法的应用原理是:借助密钥生成程序生产密钥A与密钥B,这两把密钥在数学上相关,对称作密钥对。用密钥对其中任何一个密钥加密时,可以用 另一个密钥解密,而且只能用此密钥对其中的另一个密钥解密。在实际应用中,某商家可以把生成的密钥A与密钥B做一个约定,将其中一把密钥如密钥A保存好, 只有商家自己知道并使用,不与别人共享,叫作私人密钥;将另一把密钥即密钥B则通过网络公开散发出去,谁都可以获取一把并能应用,属于公开的共享密钥,叫 做公开密钥。如果一个人选择并公布了他的公钥,其他任何人都可以用这一公钥来加密传送给那个人的消息。私钥是秘密保存的,只有私钥的所有者才能利用私钥对 密文进行解密,而且非法用户几乎不可能从公钥推导出私钥。存在下面两种应用情况:一是任何一个收到商家密钥B 的客户,都可以用此密钥B 加密信息,发送给这个商家,那么这些加密信息就只能被这个商家的私人密钥A解密。实现保密性。二是商家利用自己的私人密钥A对要发送的信息进行加密进成密 文信息,发送给商业合作伙伴,那么这个加密信息就只能被公开密钥B解密。这样,由于只能应用公开密钥B解密,根据数学相关关系可以断定密文的形成一定是运 用了私人密钥A进行加密的结果,而私人密钥A只有商家拥有,由此可以断定网上收到的密文一定是拥有私人密钥A的商家发送的。

具体到电子商务,很多环节要用到公开密钥加密法,例如在网络银行客户与银行进行资金的支付结算操作时,就涉及大量的资金流信息的安全传输与交换。以 客户甲与乙网络银行的资金信息传输为例,来描述应用公开密钥加密法在两种情况下的使用过程。首先,网络银行乙通过公开密钥加密法的密钥生成程序,生成自己 的私人密钥A与公开密钥B并数学相关,私人密钥A由网络银行乙自己独自保存,而公开密钥B 已经通过网络某种应用形式(如数字证书)分发给网络银行的众多客户,当然客户甲也拥有一把网络银行乙的公开密钥B。
　　1、客户甲传送一“支付通知”给网络银行乙,要求“支付通知”在传送中是密文,并且只能由网络银行乙解密知晓,从而实现了定点保密通信。客户甲利用获得的公开密钥B 在本地对“支付通知”明文进行加密,形成“支付通知”密文,通过网络将密文传输给网络银行乙。网络银行乙收到“支付通知”密文后,发现只能用自己的私人密钥A进行解密形成“支付通知”明文,断定只有自己知晓“支付通知”的内容,的确是发给自己的。
　　2、网络银行乙在按照收到的“支付通知”指令完成支付转账服务后, 必须回送客户甲“支付确认”,客户甲在收到“支付确认”后,断定只能是网络银行乙发来的,而不是别人假冒的,将来可作支付凭证,从而实现对网络银行业务行 为的认证,网络银行不能随意否认或抵赖。网络用户乙在按照客户甲的要求完成相关资金转账后,准备一个“支付确认”明文,在本地利用自己的私人密钥A对“支 付确认”明文进行加密,形成“支付确认”密文,通过网络将密文传输给客户甲。客户甲收到“支付确认”密文后,虽然自己有许多密钥,有自己的,也有别人的, 却发现只能用获得的网络银行乙的公开密钥B 进行解密,形成“支付确认”明文,由于公开密钥B 只能解密由私人密钥A加密的密文,而私人密钥A只有网络银行乙所有,因此客户甲断定这个“支付确认”只能是网络银行乙发来的,不是别人假冒的,可作支付完 成的凭证。

当前最著名、应用最广泛的公开密钥系统是RSA(取自三个创始人的名字的第一个字母)算法。目前电子商务中大多数使用公开密钥加密法进行加解密和数字签名的产品和标准使用的都是RSA算法。RSA算法是基于大数的因子分解,而大数的因子分解是数学上的一个难题,其难度随数的位数加多而提高。

优点是可以在不安全的媒体上通信双方交换信息,不需共享通用密钥,用于解密的私钥不需发往任何地方,公钥在传递与发布过程中即使被截获,由于没有与公钥相匹配的私钥,截获公钥也没有意义。能够解决信息的否认与抵赖问题,身份认证较为方便。密钥分配简单,公开密钥可以像电话号码一样,告诉每一个网络成员,商业伙伴需要好好保管的只是一个私人密钥。而且密钥的保存量比起私人密钥加密少得多,管理较为方便。最大的缺陷就在于它的加解密速度。

废话一堆，这下面才是真格的：

4.RSA算法浓缩
[1] 私钥
首先, 找出三个数, p, q, r,
其中 p, q 是两个相异的质数, r 是与 (p-1)(q-1) 互质的数
p, q, r 这三个数便是 private key

[2]公钥
接著, 找出 m, 使得 rm == 1 mod (p-1)(q-1)
这个 m 一定存在, 因为 r 与 (p-1)(q-1) 互质, 用辗转相除法就可以得到了
再来, 计算 n = pq
m, n 这两个数便是 public key

[3]加密
若资料为 a, 将其看成是一个大整数, 假设 a < n
如果 a >= n 的话, 就将 a 表成 s 进位 (s <= n, 通常取 s = 2^t),
则每一位数均小於 n, 然後分段编码
接下来, 计算 b == a^m mod n, (0 <= b < n)

[4]解密
解码的过程是, 计算 c == b^r mod pq (0 <= c < pq)

5.RSA算法用数字举例<再浓缩>
问：用RSA算法加密时,已知公钥是（e=7,n=20）,私钥是（d=3,n=20）用公钥对消息M=3加密,得到的密文是多少?
解：
<要加密或解密的数字做e次方或d次方,得到的数字再和n进行模运算,模运算就是求余数>

加密时用公钥d,解密时用私钥e

加密过程：3的7次方等于2187,2187除以20等于109,余数是7 所以得到的密文就是7

解密过程：7的3次方343,343除以20等于340余数3,于是我们又得回原来的明文3

6.RSA算法java实例<再再浓缩>

package com.rsa.test;  
import java.security.*;  
import java.security.spec.*;  
import java.security.interfaces.*;  
import javax.crypto.spec.*;  
import javax.crypto.interfaces.*;  
import java.io.*;  
import java.math.*;  
public class RSATest {  
    public RSATest() {  
    }  
    public static void generateKey() {  
        try {  
            KeyPairGenerator kpg = KeyPairGenerator.getInstance("RSA");  
            kpg.initialize(1024);  
            KeyPair kp = kpg.genKeyPair();  
            PublicKey pbkey = kp.getPublic();  
            PrivateKey prkey = kp.getPrivate();  
            // 保存公钥  
            FileOutputStream f1 = new FileOutputStream("pubkey.dat");  
            ObjectOutputStream b1 = new ObjectOutputStream(f1);  
            b1.writeObject(pbkey);  
            // 保存私钥  
            FileOutputStream f2 = new FileOutputStream("privatekey.dat");  
            ObjectOutputStream b2 = new ObjectOutputStream(f2);  
            b2.writeObject(prkey);  
        } catch (Exception e) {  
        }  
    }  
    public static void encrypt() throws Exception {  
        String s = "Hello World!";  
        // 获取公钥及参数e,n  
        FileInputStream f = new FileInputStream("pubkey.dat");  
        ObjectInputStream b = new ObjectInputStream(f);  
        RSAPublicKey pbk = (RSAPublicKey) b.readObject();  
        BigInteger e = pbk.getPublicExponent();  
        BigInteger n = pbk.getModulus();  
        System.out.println("e= " + e);  
        System.out.println("n= " + n);  
        // 获取明文m  
        byte ptext[] = s.getBytes("UTF-8");  
        BigInteger m = new BigInteger(ptext);  
        // 计算密文c  
        BigInteger c = m.modPow(e, n);  
        System.out.println("c= " + c);  
        // 保存密文  
        String cs = c.toString();  
        BufferedWriter out =  
            new BufferedWriter(  
                new OutputStreamWriter(new FileOutputStream("encrypt.dat")));  
        out.write(cs, 0, cs.length());  
        out.close();  
    }  
    public static void decrypt() throws Exception {  
        // 读取密文  
        BufferedReader in =  
            new BufferedReader(  
                new InputStreamReader(new FileInputStream("encrypt.dat")));  
        String ctext = in.readLine();  
        BigInteger c = new BigInteger(ctext);  
        // 读取私钥  
        FileInputStream f = new FileInputStream("privatekey.dat");  
        ObjectInputStream b = new ObjectInputStream(f);  
        RSAPrivateKey prk = (RSAPrivateKey) b.readObject();  
        BigInteger d = prk.getPrivateExponent();  
        // 获取私钥参数及解密  
        BigInteger n = prk.getModulus();  
        System.out.println("d= " + d);  
        System.out.println("n= " + n);  
        BigInteger m = c.modPow(d, n);  
        // 显示解密结果  
        System.out.println("m= " + m);  
        byte[] mt = m.toByteArray();  
        System.out.println("PlainText is ");  
        for (int i = 0; i < mt.length; i++) {  
            System.out.print((char) mt[i]);  
        }  
    }  
    public static void main(String args[]) {  
        try {  
            generateKey();  
            encrypt();  
            decrypt();  
        } catch (Exception e) {  
            System.out.println(e.toString());  
        }  
    }  
}

结果：


7.公开密钥加密法是怎么做到的私钥A与公钥B互解？
一言蔽之：来自于大数因子的多项式分解：就是若我们设计几个超大的素数(每个都有999位)将它们相乘得到一个合数，现在叫你逆向求该合数的是由那几个素数相乘得到的？这几乎是不可能的(更准确的说是现代的计算机需要几万年人算就别想了)

1977年，艾德利曼(Adleman)、希爱默(Shamir)和鲁梅利(Rumely)发明了一个公开密钥码体制。在这个密码体制中，对电文的加密过程是公开的，但是，你仅知道加密过程而未被告知解密过程则不可能对电文进行解密。他们的体制就是依靠这样一个事实：我们能够很容易地将两个大素数(譬如两个百位素数)乘起来；反过来，要分解一不大整数(譬如200位)则几乎不可能。因此RSA体制就与素数判别和大数分解有密切联系。首先，要具体建立一个RSA体制就需要两个大素数，因而就涉及到寻找大素数的问题；而RSA体制的破译之可能性就依赖于分解一个大数可能性。于是，RSA体制的建立与破译就等价于素数判别与大数分解问题。

这里我要指出一点：随着数学的发展，大数因子分解问题可能会在不久的将来得到解决，从而RSA体制将不复存在！
根据美国AT&T研究院Peter W.Shor近期发表的论文来看，他将通过引入量子力学的基本原理，完成一个n位大数的质因子分解，可以达到多项式的时间复杂度。因为，原则上可以在一年左右的时间内分解一个400位的大数。
参考文献：Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput. 26 (5): 1484 1509

这次主要是知识，所以图少了点，多包涵。下次我们说说RSA算法等非对称性加密算法的基础：大数因子的多项式分解是何方神圣，敬请关注！

帖子我从临时会员版移到Android版了，2帖合并一帖了。
感谢你的分享！

帖子我从临时会员版移到Android版了，2帖合并一帖了。
感谢你的分享！

感谢分享

不错，排版也很用心。期待下篇。

感谢分享

RSA算法原理，推荐看一下阮一峰的博客RSA算法原理（一）