深入理解对称加密和非对称加密

关于对称加密和非对称加密

我们都知道,密码体制有两种: 对称密码体制( 又称为单钥密码体制) 和非对称密码体制( 又称为双钥密码体制或公钥密码体制) 。对称密码体制使用相同的密钥( 秘密密钥) 对消息进行加密/解密,系统的保密性主要由密钥的安全性决定,而与算法是否保密无关。

对称密码体制设计和实现的中心是: 用何种方法产生满足保密要求的密钥以及用何种方法将密钥安全又可靠地分配给通信双方。对称密码体制可以通过分组密码或流密码来实现,它既可以用于数据加密,又可以用于消息认证。非对称密码体制使用公钥加密消息,使用私钥来解密。使用非对称密码体制可增强通信的安全性。

在密码学体系中,对称加密、非对称加密、单向散列函数、消息认证码、数字签名和伪随机数生成器被统称为密码学家的工具箱。其中,对称加密和非对称加密主要是用来保证机密性;单向散列函数用来保证消息的完整性;消息认证码的功能主要是认证;数字签名保证消息的不可抵赖性。这篇文章所要讲诉的就是保证消息的机密性的对称密码和非对称密码。

密码学的发展简史

密码学的发展大致可以分为 3 个阶段: 1949 年之前的古典密码学阶段; 1949 年至 1975 年密码学成为科学的分支; 1976 年以后对称密钥密码算法得到进一步发展,产生了密码学的新方向—公钥密码学。1976 年,W.Diffie 和 M.Hellman 在发表的文章“密码学的新方向”中首次公开提出了公钥密码( Public-key Cryptography) 的概念。公钥密码的提出实现了加密密钥和解密密钥之间的独立,解决了对称密码体制中通信双方必须共享密钥的问题,在密码学界具有划时代的意义。

本文的结构

文章会对称加密和非对称加密的加密的特点进行介绍,比较对称加密和非对称加密的优缺点,介绍几种比较经典的对称加密算法和非对称加密算法,例如:DES、 AES、RSA 和 ECC 等。

本文的混合加密所指的内容是取对称加密和非对称加密的优点,摒弃他们的缺点而形式的高效的混合加密方案,这种方式在目前的加密系统中的应用也很广泛。

对称加密

对称加密又称但密钥加密,整个加密过程中只使用一个密钥。所谓对称其实就是使用一把密钥加密,使用同一把密钥解密。对称加密由于加解和解密使用的是同一个密钥算法,故而在加解密的过程中速度比较快,适合于数据量比较大的加解密。

对称加密的主要有优点就是算法公开、计算量小、加密速度快、加密效率高;但是它也存在强大的缺点,缺点就是密钥协商过程中,一旦密钥泄露,别人可以获取到密钥,这样也能对密文进行解密。另外,每对用户每次使用对称加密算法时,都需要使用其他人不知道的独一密钥,这会使得收、发双方所拥有的钥匙数量巨大,密钥管理成为双方的负担。

常用的对称加密算法有 DES、3DES、AES、TDEA、Blowfish、RC2、RC4 和 RC5 等。

两种经典的对称加密算法

DES

DES 加密解密算法最初由美国 IBM 公司研究人员所设计发明,且为第一个公开的商用密码算法标准,自诞生以来便得到了 ISO 的一致认可。DES 是分组密码算法的典型代表,它的明文分组长度为 64bits,密钥长度为 64bits,其中包括有 8bits 的奇偶校验,因此有效密钥长度为 56bits。DES 加密解密算法使用的过程相同,且可以随时均都可以进行变动。它们其中有极少数被认为是易破解的弱密钥,但是很容易抛开它们不使用,因此其自身安全性主要依赖于有效密钥。

DES 算法加密过程首先先对明文分组进行操作,需要加密的明文分为每块 64bits 的固定大小。下图所示左右两部分分别为64bits 的明文分组加密过程和其 16 个子密钥生成的过程。

enter image description here

DES 核心算法模块
  • IP 初始置换

    IP 初始置换,在第一轮运算之前执行,对输入的分组采用下面的数字进行 IP 初始变换,按照从左向右、从上向下进行置换。

    58 50 42 34 26 18 10 2 
    60 52 44 36 28 20 12 4 
    62 54 46 38 30 22 14 6 
    64 56 48 40 32 24 16 8 
    57 49 41 33 25 17  9 1 
    59 51 43 35 27 19 11 3 
    61 53 45 37 29 21 13 5 
    63 55 47 39 31 23 15 7
  • 子密钥获取流程

    子密钥的获取流程如下图enter image description here

    此处,用户输入 64 位的密钥。根据密钥置换表 PC-1,将 64 位变成 56 位密钥(此处去掉了奇偶校验位)。

    PC-1 置换得到的 56 位密钥。此处密钥被分为前 28位 C0 和后 28 位 D0。分别对它们进行循环左移,C0 左移得到 C1,D0 左移得到 D1。

    将 C1 和 D1 合并变成 56 位。然后通过 PC-2 表进行压缩置换,得到此轮的 48 位子密钥 K1。

    再对 C1 和 D1 进行相同的左移和压缩置换,获取下一轮的子密钥……一共进行 16 轮,于是可以得到 16 个 48 bits 的子密钥。

  • E和扩展

    E 盒扩展置换,则是将右半部分 32bits 按照 8 行 4 列方式依次排列,得到一个 8*4的二维矩阵,然后根据如表 2 所示的 E 盒扩展置换表扩展为 8*6的二维矩阵。

    32  1  2  3  4  5 
    4   5  6  7  8  9 
    8   9 10 11 12 13 
    12 13 14 15 16 17 
    16 17 18 19 20 21 
    20 21 22 23 24 25 
    24 25 26 27 28 29 
    28 29 30 31 32  1
  • 异或运算

    将 P 盒置换的结果与最初的 64bits 分组的左半部分异或,然后左、右半部分交换,接着开始另一轮。

  • S 盒扩展

    当产生了 48bits 密钥后就可以和明文进行异或运算,便可得到 48bits 的密文。再开始下轮的 S 盒迭代运算,其功能是把 6bit数据变为 4bits 数据,每个 S 盒是一个 4 行、16 列的表。每个 S盒的使用方法为:S 盒收到 6bits 的输入,6bits 的第 1 个 bit 和最后 1 个 bits 构成的 2 位二进制为该 S 盒行号,中间的 4bits 二进制为该 S 盒的列号,然后根据行号和列号查 S 盒定义表得到对应的值(通常为十进制),该值就是 S 盒变换的输出,并转化为二进制。

  • P 盒置换

    S 盒代替运算之后,输出 32bits,作为 F 函数最后一个变换 P 盒置换的输入。将该 32bits 位数据进行 P 盒置换,置换后得到一个仍然是 32 bits 的结果,此处可得 F 函数的输出值。

  • 逆初始置换

    DES 完成 16 轮变换后,得到 64bits 数据作为 IP-1 逆初始置换的输入,经过 IP-1 逆初始置换表(如表 3 所示),64bits 输入数据位置重新编排,就得到 64bits 的密文。

    40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
    38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
    36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
    34 2 42 10 50 18 58 26 33 1 41  9 49 17 57 25
AES

AES 加密算法为分组密码,分组长度为 128 位即 16 个字节,密匙长度有128、192 或 256 位,根据密匙 长 度的不同,加密的轮数也不同,本文采用长度为 128 位的密匙,加密轮数为 10 轮。AES 加密算法不仅编码紧凑、设计简单而且可抵抗多种类型的攻击,其基本结构包括 4个部分。这四个部分分别为字节替换、行位移、列混合和轮密匙加。

字节替换(SubBytes)

字节替换也就是通 过 S-BOX 对字节元素进行非线性的变换,S-BOX 由有限域 GF(2 的 8 次方) 上的乘法求逆运算和仿射变换运算而来,通过查表的方式即可直接得到变换前后的字节元素,替换后字节元素至少有两位发生变换,能 充分打乱原来的字节元素,本文所介绍的 AES 加 密 算 法 就是对 S-BOX 进行改 进 而 来。具体替换规则为假设一字 节为 xy,则 S-BOX 中第x行第y列所对应的元素就是替换后的元素。

行位移(ShiftRows)

行位移是 AES 加密算法中的一个简单线性运算,即在 4 x 4 的状态矩阵中,把第i行循环左移i个字节(i=0, 1, 2, 3)。

列混合(MixColumns)

列混合是将状态矩阵中的每一列看成一个多项式,让其与一个固定的多项式 a(x) 相乘,再做模多项式 m(x) = x4(x的四次方) + 1 的运算,其中 a(x)=’03‘x3(x的3次方)+ ’01‘x2(x的平方)+ '01'x + ‘02’。

轮密匙加(AddRoundKey)

轮密匙加变换就是让状态矩阵与经过密匙扩展得到的子密匙做异或运算,因此轮密匙加变换的逆变换就是其本身,其中子密匙是原始密匙通过密匙扩展算法得到的。

AES 算法流程

下图是整个算法的流程图

enter image description here

AES 加密算法先将 128 位的明文进行分组,得到一个 4x4 的明文状态矩阵作为算法的输入,然后选取密匙矩阵先对明文状态矩阵做一次轮密匙加变换,再经过 10 轮的轮函数加密,轮函数操作依次为字节替换、行位移、列混合和轮密匙加,其中由于最后一轮的列混合不仅不会提高安全性,反而会拉低 算 法 运 算 速 度,故该轮丢弃列混合变换。解密算法仍为 10 轮,由于算法的4个轮操作均为可逆变换,因此解密过程就是用与加密过程同样的密匙对每一轮的加密操作进行逆运算。

非对称加密

非对称加密又称为公钥密码,该技术是针对私钥密码体制(对称加密算法)的缺陷被提出来的,非对称加密会产生两把密钥,分别为公钥(Public Key)和私钥(Private Key),其中一把密钥用于加密,另一把密钥用于解密。非对称加密的特征是算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂,而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥,并且是非公开的,如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全,而非对称密钥体制有两种密钥,其中一个是公开的,这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就高了很多。

常用的非对称加密算发有 RSA、Elgamal、背包算法、Rabin、D-H、ECC(椭圆曲线加密算法)等。

两种经典的非对称加密算法

RSA

RSA 算法是一种迄今为止理论上比较成熟和完善的公钥密码体制,是非对称密码体制的典型代表。在网络、信息安全等许多方面都使用 RSA 算法,特别是 RSA 算法典型应用在通信中的数字签名,可实现对手的身份、不可抵赖性验证。在身份认证、信息安全、电子商务中有着广泛的应用前景。

RSA 的算法流程

RSA 算法由密钥的产生、加密算法和解密算法 3 个部分组成。

密钥的产生过程如下:

  1. 产生两个大素数 p 和 q ;

  2. 计算 n = p × q ,欧拉函数 φ(n) =(p - 1)(q - 1)

  3. 选择整数 e ,使其满足条件:1 < e < φ(n) ,且gcd(e,φ(n)) = 1(注:gcd () 函数计算两个数的最大公约数);

  4. 计算 e 的逆元 d :d∙e ≡ 1 mod φ(n)(注:由于gcd(e,φ(n)) = 1,则 d 一定存在);

  5. 取序对 (e,n) 为公钥,可公开;(d,n) 为私钥,对外保密。

加密算法过程如下

将要发送的字符串分割为长度为 m < n 的分组,然后对分组 mi 执行加密运算,得到密文 ci :ci ≡(mi)e mod n

解密算法过程如下

收到密文 ci 后,接收者使用自己的私钥执行解密运算,得到明文 mi :mi ≡(ci)d mod n

RSA 详细的算法设计流程

大素数的产生和测试

Miller-Rabin 算法是一种基于概率的素数测试方法,在密码学的素数产生中,由于该算法的速度快、原理简单、易于实现,成为进行素数检测的最佳选择。

Miller-Rabin 算法是对费马算法改进,它的操作步骤如下:

  1. 计算 m ,满足 n = (2r 2的r次方 ) m + 1;

  2. 选择随机数 a ∈[1,n] ;

  3. 若 am mod n = 1 ,或满足 aim mod n = n - 1 ,则 n 通过随机数 a 的测试;

  4. 再取不同 a 要的值对 n 进行 t = 5 次测试,如果每次测试结果为 n 是素数,则以高概率判定 n 是素数。假设 n 通过 t 次测试,则判定结果错误的概率是1/4t;若只通过一次测试,素数判定的错误概率是 25%。

流程图如下:

enter image description here

密钥 e 生成模块

通过上面的的大素数生成模块,可以得到大素数 p和大素数 q ,根据欧拉函数 φ(n) =(p - 1)(q - 1) ,同时密钥 e 与 φ(n) 互质,根据中国剩余定理可以计算密钥e 。

过程如下:

enter image description here

密钥 d 生成模块

通过大素数生成模块得到大素数 p 和 q ,密钥 e 生成模块,根据 1 = ed mod ( p - 1) (q - 1) 。利用中国剩余定理计算 e 的乘法逆元 d 。

快速指数算法

得到 e 后,就可以通过公钥 (e,n) 进行加密得到密文 C 。在 RSA 加密过程中,为了计算 ci ≡(mi)e mod n ,采用快速指数算法。将快速指数算法描述为三元组(M,E,Y) ,其初始值为 (M,E,Y ) =(mi,e,1) 。重复执行以下操作:

①若 E 是奇数,则 Y = MY mod n ,E = E - 1 ; ②若 E 是偶数,则 X = XX mod n ,E = E/2 。 最终,当 E = 0 时,则 Y = X^E mod n 。

RSA加密和解密算法设计

过程如下:

enter image description here

ECC

椭圆曲线加密算法(ECC)是基于椭圆曲线数学的一种非对称密码算法,是建立在基于椭圆曲线的离散对数问题上的密码体制。随着分解大整数方法的进步以及各方面的完善,RSA 算法渐渐不能满足现状,ECC 算法的需求性逐渐增大。ECC 以其明显的“短密钥”优势得到了广泛应用,并逐渐被确定为许多编码方式的数字签名标准。当然,ECC 还有许多未解决的问题,不过这种引用了丰富数学理论的算法,也印证了将更多数学有较大可行性理论应用到密码学这一领域中。

首先从数学角度阐释算法加密原理,ECC椭圆曲线加密算法数学基础是利用有限域上椭圆曲线离散对数问题(ECDLP)的计算困难性,所谓椭圆曲线是指由韦尔斯特拉方程。其椭圆曲线方程如下:

y2 + a1xy + a2 y = x3 + a3x2 + a4 x + a5

下面是椭圆曲线方式图示

enter image description here

其中,系数 ai 定义在某个域上(密码算法中需要把之前连续曲线变为有限域上的点,故 ai 也定义在有限域中)。曲线上所有点和一个无穷远点构成一个集合连同定义上的加法(eg:a+b≡c (mod p))构成阿贝尔群。由于曲线上每一点都是非奇异点,故可在椭圆曲线上找到两点 P、Q,且存在如下关系式:

enter image description here

由此可见,已知 m、P 求 Q 较为容易,反之由 Q 逆向求 m、P 难度却较大,椭圆曲线密码正是基于该机制来展开设计及应用。

混合加密-对称加密和非对称加密的实际应用场景

所谓混合加密就是使用在实际的应用中把对称加密和非对称加密结合起来使用。我们都知道非对称加密算法比对称加密算法慢数千倍,但在保护通信安全方面,非对称加密算法却具有对称密码难以企及的优势。所以在实际的应用中,都是对称加密与非对称加密混合使用。取其优势,去其糟粕,达到完美使用的一个目的。

对称加密技术,即专用密钥加密技术或单钥密码技术,加密密钥与解密密钥一致,发送方与接收方用同一组的公私密钥对加密或者解密信息。数据加密的一个关键要求是有相同的密钥才能解密。因为通信双方共享密钥,如果密钥丢失或泄露,那么获取密钥的人就可以加密或者解密数据,所以为保证消息的机密性必须保障密钥的安全。 这种算法比较简单且计算量比较小,对网络开放、从而能够效率高地加密。同时存在的缺点,一是通讯双方基于通过非面对面的方式协商一个共同的密钥,因此不能保证协商过程的安全性。二是通讯双方每次进行数据传输时都使用惟一密钥,这使得对称加密技术在开放型的网络中需要使用和生成大量的密钥,对于密钥的管理就成为用户的很大负担。三是对称加密算法只能对数据进行加解密,保证数据的机密性,但无法验证通讯双方的真实身份,不能确定数据的完整性。

非对称密钥加密技术,由公钥和私钥形成一个密钥对,其中公钥向公众公开,私钥归密钥持有人单独保管。通讯双方使用非对称密钥对数据进行加密和解密时,必须使用相互匹配的公钥和私钥。它有两种方式:一种是发送方用接收方的公钥来加密信息,接收方用其私钥解密信息,这样接收方可以收到多个发送方传来的加密数据,且此加密数据只有接收方一个用户可以解读;另一种即发送方利用自身的私钥加密信息,接收方用对方公钥解密信息,这样一个信息有可能被多个接收方解密。 非对称密钥加密技术的优点是简化了密钥的发放及管理的过程,支持数字签名等安全认证技术,缺点是加密和解密的计算过程特别复杂,运行数据加密和解密的速度比较慢。



0
1780