RSA加密算法实现以及C#与java互通加解密

 

一.RSA算法简介

关于RSA加密算法可以参考：http://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

大体是先生成两个大素数p和q，再生成e，e和（p-1）*（q-1）互素。

取p和q的乘积：n=p*q 为公共模数。

再生成正整数d，满足d*e-1可以被（p-1）*（q-1）整除。

这样d就为私钥，(e,n)为公钥，形成rsa的公私钥对。

其中n的二进制位称为该密钥长度，密钥越长越难破解，也就越安全。

二.填充算法

由于密钥长度有限，一次性加密的数据长度也有限，因此必须对明文进行分块加密，再合并加密结果。

以1024位密钥为例，n为1024位，即128个字节，则明文需要分块成每块长128个字节，不足128位的使用特定格式的数据填充。

所以分块的算法称为填充算法，有不同的标准，如NoPPadding、OAEPPadding、PKCS1Padding等。

本文实现的是PKCS1Padding填充算法，规范文档是这个：http://man.chinaunix.net/develop/rfc/RFC2313.txt

该算法规定的格式如下：

00 || BT || PS || 00 || D

其中BT可选择01和02，01表示私钥加密，02表示公钥加密。如果BT是01则PS需要使用oxFF填充，为02的话则需要使用随机非0填充。D表示分割的明文块。

PS的长度至少为8个字节，因此D至多只能为128-8-2=117个字节长。

三.C#实现

之所以要使用C#实现是因为官方版本只实现了公钥加密且在明文中间增加了一些数字再进行的加密，使用私钥解密出来后需要去除增加的数字。

而要实现私钥加密则只能自己实现了，这里使用到了一个大整数类:BigInteger。我是从这里下载的:http://www.codeproject.com/Articles/2728/C-BigInteger-Class

C#里生成公私钥对可以使用如下代码：

RSACryptoServiceProvider key = new RSACryptoServiceProvider();
RSAParameters param = key.ExportParameters(true);
Console.WriteLine(Convert.ToBase64String(param.Modulus));
Console.WriteLine(Convert.ToBase64String(param.Exponent));
Console.WriteLine(Convert.ToBase64String(param.D));

其中Modulus+Exponent为公钥，D为私钥，C#里是以base64格式保存的。

填充算法实现如下（blockLen为模的字节数，这里为128）：

//填充
        private byte[] add_PKCS1_padding(byte[] oText, int blockLen)
        {      
            byte[] result = new byte[blockLen];
            result[0] = 0x00;
            result[1] = 0x01;  
            
            int padLen = blockLen - 3 - oText.Length;                       
            for (int i = 0; i < padLen; i++)
            {
                result[i + 2] = 0xff;
            }

            result[padLen + 2] = 0x00;

            int j = 0;
            for (int i = padLen + 3; i < blockLen; i++)
            {
                result[i] = oText[j++];                
            }
            
            return result;
        }

私钥加密方法如下：

//私钥加密
        private byte[] priEncrypt(byte[] block, RSACryptoServiceProvider key)
        {
            RSAParameters param = key.ExportParameters(true);
            BigInteger d = new BigInteger(param.D);
            BigInteger n = new BigInteger(param.Modulus);
            BigInteger biText = new BigInteger(block);
            BigInteger biEnText = biText.modPow(d, n);
            return biEnText.getBytes();
        }

则整个私钥加密方法可以如下进行：

//私钥加密
        public byte[] encryptByPriKey(String src, RSACryptoServiceProvider key){
            //获得明文字节数组
            byte[] oText = System.Text.Encoding.Default.GetBytes(src);
            //填充
            oText = add_PKCS1_padding(oText, 128);            
            //加密
            byte[] result = priEncrypt(oText, key);            
            return result;
        }  

加密结果为字节数组，可以转化为base64编码的字符串，但是建议转化为十六进制字符串，便于用于web传递。

对于大于128字节的明文，需要分成多段进行加密，使用本文的填充算法实现是大于117字节的明文就需要分段。

为了方便的web环境下的数据交换，可以对明文进行urlencode后再进行加密，这样解密后使用urldecode可以得到明文。

实现如下：

//url编码
            String urlEncode = System.Uri.EscapeDataString(src); 

            //以117个字符为长度分割字符串进行加密
            int index = 0;
            int len = urlEncode.Length;
            String toEncrypt = "";
            while (index < len)
            {
                String temp = "";
                if (index + 117 < len)
                {
                    temp = urlEncode.Substring(index, index + 117);
                }
                else
                {
                    temp = urlEncode.Substring(index);
                }

                //加密           
                byte[] encrypted = encryptByPriKey(temp, r);

                //转化为16进制字符串
                String enc = bytesToHexStr(encrypted);
                toEncrypt += enc;

                index += 117;
            }
            Console.WriteLine(toEncrypt);

对节字数组转化为十六进制字符串可以如下实现：

char[] bcdLookup = { '0', '1', '2', '3', '4', '5',
            '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

        //字节转化为十六进制字符串
        public String bytesToHexStr(byte[] bcd) {
            String s  ="";

            for (int i = 0; i < bcd.Length; i++) {
                s +=(bcdLookup[(((byte)bcd[i]) >> 4) & 0x0f]);
                s+=(bcdLookup[(byte)bcd[i] & 0x0f]);
            }

            return s;
        }

至此为止，我们便实现了C#的私钥加密算法实现。

C#的签名实现使用官方实现即可与java互通，应该是没有使用填充的原因。

C#签名和验证实现如下：

//明文转化为字节数组
            byte[] srcBytes = System.Text.Encoding.Default.GetBytes(src);

            //签名
            byte[] signed = key.SignData(srcBytes, "sha1");

            //转化为16进制字符串      
            String sign = nr.bytesToHexStr(signed);
            Console.WriteLine(sign);

            //验证
            bool verify = r.VerifyData(srcBytes, "sha1", signed);
            Console.WriteLine(verify);

使用此方法签名的数据可以使用java验证。由于是签名和验证，不需要还原数据，所以可以直接对明文加密，不需要使用urlencode。

 

四.结语

java所实现的算法有完整的一套框架，包括了各种填充算法，可以轻松实现公钥加密和解密，签名和验证等，本文就不再示例。

 

附：公钥解密实现

//公钥解密
        public String decryptByPubKey(String enc, RSACryptoServiceProvider key)
        {
            String result = "";
            int blockLen = 256;
            int i = 0;
            while (i < enc.Length)
            {
                String temp = enc.Substring(i, blockLen);

                byte[] oText = hexToBytes(temp);
                
                //解密
                byte[] dec = pubDecrypt(oText, key);

                //去除填充
                dec = remove_PKCS1_padding(dec);

                result += System.Text.Encoding.Default.GetString(dec);

                i += blockLen;
            }
            return result;
        }

        //公钥解密
        private byte[] pubDecrypt(byte[] block, RSACryptoServiceProvider key)
        {
            RSAParameters param = key.ExportParameters(true);            
            BigInteger e = new BigInteger(param.Exponent);
            BigInteger n = new BigInteger(param.Modulus);
            BigInteger biText = new BigInteger(block);
            BigInteger biEnText = biText.modPow(e, n);
            return biEnText.getBytes();
        }

        //去除填充
        private byte[] remove_PKCS1_padding(byte[] oText)
        {
            int i = 2;
            byte b = (byte)(oText[i] & 0xff);
            while (b != 0)
            {
                i++;
                b = (byte)(oText[i] & 0xff);
            }
            byte[] result = new byte[oText.Length - i];
            int j = 0;
            while (i < oText.Length)
            {
                result[j++] = oText[i++];
            }
            return result;
        }

        //十六进制字符串转化成字节数组
        public byte[] hexToBytes(String s)
        {
            byte[] bytes = new byte[s.Length / 2];

            for (int i = 0; i < bytes.Length; i++)
            {
                bytes[i] = (byte)Convert.ToInt32(s.Substring(2 * i, 2), 16);
            }

            return bytes;
        }