RSA 原理

RSA PKCS#1 v1.5加密标准主要描述了如何使用RSA公钥密码体系加密、解密数据，以及数字签名的算法，在网上可以直接查找到RFC的定义标准文本：
[English]
http://www.faqs.org/rfcs/rfc2313.html
[中文版本]
http://man.chinaunix.net/develop/rfc/RFC2313.txt

根据标准的定义，我们可以了解几个方面的内容：RSA公钥与私钥的构成，计算方法；加密、解密过程、数字签名过程，下面分别予以阐述：
1、RSA公钥与私钥的构成，计算方法
RSA的核心是2个大素数，p,q,描述如下：选择两个不同的奇素数p和q，以便e和（p-1）*（q-1）互素。
公开模数n是私人的素数p，q的乘积：n=p*q 。私人指数是一个正整数d，以便d*e-1可
以被（p-1）*（q-1）整除。模数n的字节长为k，k满足2^(8(k-1)) <= n < 2^(8k)。模数长度
k必须是至少12个字节，使之适应此文档中的块格式。
RSAPublicKey ::= SEQUENCE {
modulus INTEGER, — n
publicExponent INTEGER — e }
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, — n
publicExponent INTEGER, — e
privateExponent INTEGER, — d
prime1 INTEGER, — p
prime2 INTEGER, — q
exponent1 INTEGER, — d mod (p-1)
exponent2 INTEGER, — d mod (q-1)
coefficient INTEGER — (inverse of q) mod p }

对于根据p,q计算密钥，下面给出一段JAVA程序来实现该过程。

 1import java.math.BigInteger;
2
3public class RSAParameter {
4    private BigInteger p, q, e, n, d, dp, dq, qinv;
5
6    RSAParameter() {
7        super();
8    }
9
10    RSAParameter(String ps, String qs, String exps) {
11        init(new BigInteger(ps), new BigInteger(qs), new BigInteger(exps));
12    }
13
14    public void init(BigInteger prime1, BigInteger prime2, BigInteger exp) {
15        this.p = prime1;
16        this.q = prime2;
17        this.e = exp;
18        //n=p*q
19        n = prime1.multiply(prime2);
20        //exp*d=1 mod (p-1)(q-1)
21        d = exp.modInverse(prime1.subtract(BigInteger.ONE).multiply(prime2.subtract(BigInteger.ONE)));
22        //dp*r=1 mod (p-1) or d mod (p-1)
23        dp = d.mod(p.subtract(BigInteger.ONE));
24        //dp=exp.modInverse(p.subtract(BigInteger.ONE));    也可以这样计算dp
25        //dq*r=1 mod (q-1) or d mod (q-1)
26        dq = d.mod(q.subtract(BigInteger.ONE));
27        //q*qinv=1 mod p
28        qinv = q.modInverse(p);
29    }
30
31
32    public String toString() {
33        StringBuffer sb = new StringBuffer();
34        sb.append(“RSA Keyinfo:\n”);
35        sb.append(“PrivateKey:\n”);
36        sb.append(“modulus:” + n.toString() + “\n”);
37        sb.append(“public exponent:” + e.toString() + “\n”);
38        sb.append(“private exponent:” + d.toString() + “\n”);
39        sb.append(“prime p:” + p.toString() + “\n”);
40        sb.append(“prime q:” + q.toString() + “\n”);
41        sb.append(“prime exponent p:” + dp.toString() + “\n”);
42        sb.append(“prime exponent q:” + dq.toString() + “\n”);
43        sb.append(“crt coefficient:” + qinv.toString() + “\n”);
44        sb.append(“PublicKey:\n”);
45        sb.append(“modulus:” + n.toString() + “\n”);
46        sb.append(“public exponent:” + e.toString() + “\n”);
47        return sb.toString();
48    }
49}

2、加密、解密过程
首先需要知道密钥的长度，这是根据n的bits位来标识的，通常在java中密钥的长度k必须1024以上，也就是n应该是128 bytes.
加密，需要先将消息D格式化成EB的加密块，使EB长度=128 bytes，
EB的表述是EB = 00 || BT || PS || 00 || D
对于D的长度，不应该长于k-11个8位字节，其必为正数，因为模数的长度k是至少12个8位字节。这种限制保证了填充串PS的长度至少为8个8位字节，这是一项安全措施。
其中BT、PS值含义如下：
00 ：一般不用，数据D必须以一个非0字节开始，或是必须知道长度，以便加密块能被清楚的解析。
01 ：私钥操作标志，PS必须填充0xFF,通常为数字签名时使用，可以保证每次的签名数据唯一性
02 ：公钥操作标志，PS必须填充随机非0数，保证每次加密的结果比一样，提高安全性

加密过程将EB转换成整数，利用公钥e,n进行加密，计算公式为
ED=EB modpow (e,n)
加密后输出的结果长度应该是固定的,长度为k/8个bytes

解密过程则刚好相反，利用私钥d,n进行解密，计算公式为
EB=ED modpow (d,n)
解密后的结果是EB，因此我们必须了解是否用公钥加密的数据，如果是，解密后数据应该是
00 01 XX … XX 00 D,其中XX是随机填充的，只要定位最后的00位置，将尾部的bytes分割下来就是明文了。
私钥加密的数据解密后数据应该是
00 02 FF …FF 00 D,原理就差不多类似了

3、数字签名
数字签名中采用如下步骤
1)计算明文hash值hashdata
2)根据ASN.1规则编码hash算法特征串+hashdata，得到签名明文数据C
3)采用RSA私钥加密C得到digest签名数据

验证过程如下
1)采用公钥解密digest,得到C
2)根据C，ASN.1解码得到hash算法特征串，获知采用什么hash算法，hashdata是什么
3)根据hash算法计算明文的hashdata1，与hashdata比较是否一致
4)根据比较结果验证签名的有效性

加解密的原理基本好理解，关键是digestAlgorithm 的特征串，根据文档定义
DigestInfo ::= SEQUENCE {
digestAlgorithm DigestAlgorithmIdentifier,
digest Digest }
MD5计算hash时，标识符就是1.2.840.113549.2.5,对于ASN.1编码，其实是一种设备独立的编码规则，在底层网络通讯中广泛被采用，一般我们可以使用
3方的包例如bouncycastle来解析或者编码
md5 OBJECT IDENTIFIER ::=
{ iso(1) member-body(2) US(840) rsadsi(113549)
digestAlgorithm(2) 5 }
下面是一段演示代码

 1import org.bouncycastle.asn1.ASN1InputStream;
2import org.bouncycastle.asn1.DERObject;
3public class  DecodeASN1
4{
5    public static void main(String[] args)
6    {
7        //这是一段RSA签名数据DigestInfo，来源参数为
8        /**//*
9        n =
10
11“11262884410355204430037697963227736559286052877012462506633640513069629804403399522764270242067801598971086784186759359440143415620433468158326754347674901462092249508308706200
12
138872607905765651105670638572435826363983713767368815675341307594277511890573814685529893908327924650039275886811260735916324764564853″;
14        d =
15
16“29921735884873348540730634487046724939153373917277871233501428959680077593491857895669424780603703806961806612978266812214830860333455470055789419709075434021826716139325709532
17
18742771186379941997345196185777640711503947179993281763887256221502624948138721356270847024512768717268039878195832083548155677542117″;
19        e = “65537”;
20        明文：s=”1234″
21        算法：MD5
22        */
23        byte[] data={48,32,48,12,6,8,42,-122,72,-122,-9,13,2,5,5,0,4,16,-127,-36,-101,-37,82,-48,77,-62,0,54,-37,-40,49,62,-48,85};
24        ASN1InputStream is=new ASN1InputStream(res);
25        DERObject obj=is.readObject();
26        System.out.println(“ASN1解码：”+obj.toString());
27        //运行结果：
28        //ASN1解码：[[1.2.840.113549.2.5, NULL], #81dc9bdb52d04dc20036dbd8313ed055]
29    }
30}

因此我们可以列出常用的hash算法标识数据备用，避免每次都要自行ASN.1编码、解码，下面列出了常见的hash标识数据
MD2:     (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10 || H
MD5:     (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H
SHA-1:   (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H
SHA-256: (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H
SHA-384: (0x)30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H
SHA-512: (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H
根据前面数据的就可以直接分析出hash算法是什么。