首页 > 学习收获 > 科海拾贝 > RSA/3DES及加解密
2021
11-09

RSA/3DES及加解密

不重要的前言:这份工作真是神奇,什么都得研究。竟然还有我自己动手写RSA的一天……

近期工作需要,搞了一下3DE和RSA,在网上搜索时,觉得网上的文章实在是有点坑,所以在自己的一亩三分地记录一下自己的一些理解。

1. 加密、对称加密、3DES

加密的根本含义是将数据以某种方式进行计算,让人看不出原有的样子,以保护数据内容。一般说的加密都是可逆加密,也就是加密后的密文是可以还原成原文的。MD5之类的算法其实算不得加密,最多只能是“提取特征值”的一种运算。

对称加密比较好理解,就是传统意义上的加密。A和B约定一种计算方式和一个特定的算子,传输信息时,A用计算方式用算子把数据给处理一下。B拿到了密文再用同样的算子和计算方式把数据反处理一下。就是对称加密。比如A和B约定传数据时,每个字节都加8(溢出数据丢弃高位),那A想给B传输0x00时,就给B发0x08。B拿到0x08之后,就知道A的数据是0x00。

实际使用的时候会有很多复杂的算法,比如DES/3DES/AES之类。具体的实现逻辑其实可以不用太关心,各家编程语言都有现成的库来调用。比如C#做3DES解密,只需要指定密码以及计算方式:

byte[] keys = 3deskeys[24];
var des = new TripleDESCryptoServiceProvider
{
   Key = keys,
   Mode = CipherMode.ECB,
   Padding = PaddingMode.PKCS7,
};
var desDec = des.CreateDecryptor();
byte[] buffer = somedatatobedecrypt[100];
byte[] result = desDec.TransformFinalBlock(buffer, 0, buffer.Length);

计算方式一般是两部分:分块方式(Mode)和填充方式(Padding),一个是指定数据超过算法允许的长度时,需要如何分块。另一个是指定数据不足算法要求的长度时,需要如何填充。具体的含义需要查最基本的加密算法定义文档。是纯数学的一些内容。

这里需要注意的是,如果做跨平台加解密,比如我现在遇到的用C#去还原JAVA的解密算法,需要注意各个语言的默认参数。例如上述C#代码实际上对应的是如下的Java实现:

byte[] keybytes = 3deskeys[24];
byte[] encryptedbytes = somedatatobedecrypt[100];
Key key = new SecretKeySpec(keybytes, 0, keybytes.length, "DESede");
Cipher cipher = Cipher.getInstance("DESede");
cipher.init(2, key);
byte[] recoveredBytes = cipher.doFinal(encryptedbytes);

也就是说,在Java里,不做任何指定的3DES,实际上使用的是3DES/ECB/PKCS7模式。C#默认3DES是3DES/CBC/PKCS7,如果不指定参数,直接使用默认算法计算的话,将无法得到正确的结果。

2. 非对称加密与RSA

对称加密比较坑的地方就是加密方和解密方都得有原始的全部的计算元素。一旦加密方式被其中一方或者在商讨过程中泄露,就会全丢光。所以密码学家们设计了非对称加密。非对称加密是一个巧妙的数学算法,他通过两套算子来进行加解密,A手里有一套算子a,B手里有另一套算子b,A将数据用算子a加密后,B可以用自己手里的算子b来解密,同时加密后的数据不能用算子a来解密。这样可以有很多的A,手里都掌握着a,但是b只在B手里。A们相互之间都不能解密信息,a这个算子甚至可以直接明文写在网络里,大家都可以用,但是只有B才能用b来解密这些数据。

算法的原理就比较巧(难)妙(懂),我就不(看)研(不)究(懂)了。目前常见的算法就是RSA了。

先吐个槽:现在网上大部分对RSA的研究都是某某语言如何实现RSA,真是非常实用主义。其实稍微了解一下这个算法本身,对开发有挺大帮助,尤其是一些奇葩需求。

从根本上来说,RSA算法实现的核心是一个计算方式,和两套算子。公开的那个算子叫公钥,私下保留的算子叫私钥。算子的计算方式网上都能找到,比如知乎的这里这里这里,都是挺好的文章。简单来说,RSA需要两个质数p和q,选一个e,然后可以算出n和d。最后将p、q丢弃,保留e、n、d。公钥一般是e和n,私钥是d和n。公钥用e和n的缘故是e有建议,一般都是选3和65537。然后n是计算时必须要有的一个数字所以必须公开。所以如果是把d和n作为公钥的话,私钥很容易被人猜到。所以一般都是公开e和n。

在网上常见的RSA文章中,公私钥对的生成都包含在样例代码中,使用KeyPairGenerator之类的现成的库来生成密钥对。实际应用时,公私钥对已经是设定好的,事实上并不需要临时生成一对密钥,更重要的是如何从现有的信息中获取到公私钥对。密码学标准里面定义了很多种密钥存储的方式,比如pem、PKCS1、PKCS8之类,核心就是通过固定的格式定义,来定义如何将公私钥编码在文件内。而软件实现就是需要通过现有库或者自己实现代码,来从文件中获取这些密钥信息。自己实现代码的部分信息比较少,通过搜索我发现了一个大神Michel(JavaScience)实现的一个C#代码库RSA Public, Private, and PKCS #8 key parser。感谢大神。

一般来说,获取到的密钥信息里面只包含必要的e和n,或者d和n,但是也有些密钥会把全部信息包含在里面,比如我这边项目里遇到的,可以把全部信息都导出来:

RSACryptoServiceProvider rsapro = JavaSci.DecodePrivateKeyInfo(rsakeystring);
BigInteger m = PrepareBigInteger(rsaParams.Modulus);
BigInteger e = PrepareBigInteger(rsaParams.Exponent);
BigInteger d = PrepareBigInteger(rsaParams.D);

BigInteger dp = PrepareBigInteger(rsaParams.DP); //pe
BigInteger dq = PrepareBigInteger(rsaParams.DQ); //qe
BigInteger iq = PrepareBigInteger(rsaParams.InverseQ); //coeff
BigInteger p = PrepareBigInteger(rsaParams.P);
BigInteger q = PrepareBigInteger(rsaParams.Q);

可以看到密钥里面,甚至包含了原始的p和q。此外还有一些参数,包括DP、DQ、Inverse,根据网上的说法,是用来进行加速计算的一些辅助算子。这个算法称之为“中国余数定理”或者“孙子定理”。信息是非常全的。

RSA的计算方式其实比较简单,是一个次方后取模的计算。公式就是 密文 = 信息 ^ e % n,解密就是 信息 = 密文 ^ d % n。实际计算时,会根据密码子的长度,将数据拆分为特定长度,然后将这个数据作为一个大的整数来进行计算,获得最终的结果。比如,1024bit的密码子,可以加密128byte的信息,所有的信息就会被拆分为128byte,在转换为大的整数,然后进行计算。

但是为了安全考虑,实际上不允许将数据拆分为128byte,而是需要拆为117byte,留出11byte用于填充,经过一个复杂的算法,可以填充一个随机数在里面,还可以进行加解密操作。填充模式也有几种规定。这里就有个坑,Java1.8里面,允许将RSA的加密模式指定为RSA/ECB/NOPADDING。也就是不使用填充。这种模式下,数据可以被拆分为128byte一块进行加密。但是C#里面是不允许进行这样的设定的。所以如果Java的算法使用了RSA/ECB/NOPADDING模式,那么用C#的官方库是无法进行对应的加解密的。即使有密钥对也无法进行。

Cipher c = Cipher.getInstance("RSA/ECB/NOPADDING");
c.init(1, publicKey);
byte[] signedData = c.doFinal(tbsBuffer);

如果C#里面一定要实现这种模式要怎么办呢?如果原文不长的情况下,可以尝试手动计算。也就是使用RSA的计算公式,直接使用公式计算。C#里面,上述代码事实上等同于:

BigInteger m = PrepareBigInteger(rsaParams.Modulus);
BigInteger exp = PrepareBigInteger(rsaParams.Exponent);
BigInteger value = PrepareBigInteger(tbsBuffer.Reverse().ToArray());
BigInteger biEn3 = BigInteger.ModPow(value, exp, m);
byte[] b5 = biEn3.ToByteArray().Reverse().ToArray();

这里使用了BigInteger这个.net 4.0以后引入的struct,通过手动计算来实现相同的算法。由于.net里面BigInteger默认是带符号数,为了避免影响,从网上抄了一段PrepareBigInteger来将byte[]转换为大整数。

private static BigInteger PrepareBigInteger(byte[] unsignedBigEndian)
        {
            // Leave an extra 0x00 byte so that the sign bit is clear
            byte[] tmp = new byte[unsignedBigEndian.Length + 1];
            Buffer.BlockCopy(unsignedBigEndian, 0, tmp, 1, unsignedBigEndian.Length);
            Array.Reverse(tmp);
            return new BigInteger(tmp);
        }

通过这种计算可以实现在C#下复刻Java的代码,实现完全相同的计算结果。但是多吐槽一句:如果是全新设计的方案,请务必摒弃ECB/Nopadding模式!务必摒弃ECB/Nopadding模式!务必摒弃ECB/Nopadding模式!重要的事情说三遍。要不然其实加密了约等于没加密。网上有个非常好的文章就在说这个,用一张图片来加密处理的话,如果使用ECB/Nopadding模式,加密后的图片依然可以看出原始图片的样子。然而我一下子找不到了汗。

最后编辑:
作者:龙天
匿名
这个作者貌似有点懒,什么都没有留下。

留下一个回复

你的email不会被公开。