加解密学习笔记

Posted by fsoooo Blog on April 10, 2018

加密技术包括两个元素:算法密钥

算法是将普通的信息或者可以理解的信息与一串数字(密钥)结合,产生不可理解的密文的步骤。

密钥是用来对数据进行编码和解密的一种算法。

在安全保密中,可通过适当的钥加密技术和管理机制来保证网络的信息通信安全。

大纲介绍

常用的加密解密方法主要有以下加大类:

  • 基本加密方法
  • 对称加密方法
  • 非对称加密方法

下面我们简单介绍一下这几种加密码方法

加密解密技术

我们先来了解一下加密解密的技术。

数据加密和数据解密是一对逆过程。

先来看加密解密的公式:

加密:

img

数据加密是用加密算法E和加密密钥K1将明文P转换成密文C 用上面公式表示。

解密:

img

数据解密是数据加密的逆过程, 解密算法D和解密密钥K2奖密文C转换成明文P。

通过下图我们可以清晰的看到,数据加密及解密的整修过程:

img

发送端将明文P 通过加密算法E与加密密钥Ke,生成密文C,然后传输到接收端,接收端收到密文后通过解密算法D与解密密钥Kd对密文C进行解密,最终还原明文P。

知道了加密的整个过程,我们来看看上面所说的三种加密解密方式。

基本加密方法

基本加密方法只要分为:

  1. 位移法

    • 按照一定的规则,重新安排明文中的比特或字符的顺序来形成密文,而字符本身保持不变。

    例如: hello world! 我们可以变为: lord l!oleh, 只需要按照一定的规则解开就可以了。

  2. 置换法

    • 按照一定的规则,用一个字符去置换(替代)另一个字符来形成密文。

    我们还是以 hello world! 为例,约定一个简单的算法把h变成9r>c, l>#,那么得到的结果就是: 9e##o woc##d! 解密把它逆过来就好了,非常简单。

对称加密技术

  • 对称密钥加密 又称为对称加密私钥加密共享密钥加密,是密码学中的一类加密算法。
  • 这类算法在加密和解密时使用相同的密钥,或是使用两个可以简单地相互推算的密钥。
  • 实际上,这组密钥成为在两个或多个成员间的共同秘密,以便维持专属的通信联系。

上面说得可能有点饶,举个简单的例子: 假设小明与小红在考试,他们相互约定了一个算法: 当小明连续咳嗽三声的时候小红看着小明,如果小明摸了下左耳朵,那就说明小红可以给小明传答案了。如果没有,那可能是小明感冒了… 然后怎么传答案呢? 小红摸左耳朵代表A, 摸右耳朵代表B,左手抠鼻子代表C,右手抠鼻子代表D

怎么样,通过上面的个简单的例子是不是比较好理解呢,对称加密码就是双方约定好一个算法,通过这个算法进行加密解密。

对称加密类型

常用的对称加密码主要分为以下几类:

  1. DES
  2. 三重DES(TDEA)或3DES
  3. RC-5
  4. IDEA
  5. AES

DES 主要采用替换和移位的方法加密,它用56位密钥对64位二进制数据进行加密,每次加密可对64位输入数据进行16轮编码,经一系列替换和移位后输入的64位原始数据转换成了不同的64位输出数据。DES算法运算速度快,密钥产生容易。

三重DES 在DES的基础上采用了三重DES,用两个56位的密钥k1和k2. 发送方k1加密,k2解密,再使用k1加密。接收方则使用k1解密,k2加密,再使用k1解密

RC-5 引入了一种新的密码基本变换数据相依旋转方法,即一个中间的字是另一个中间的低位所决定的循环移位结果,以提高密码强度

IDEA 是国际数据加密算法 是在DES算法的基础上发展而来,类似于三重DES。密钥长度为128位。

AES 基于排列和置换运算。提成列是对数据重新进行安排,置换是将一个数据单元替换成另一个。可以使用128,192,256们的密钥,并且用128位(16字节)分组加密和解密数据。

DES(数据加密标准)

DES算法为密码体制中的对称密码体制,又被称为美国数据加密标准,是1972年美国IBM公司研制的对称密码体制加密算法。 明文按64位进行分组,密钥长64位,密钥事实上是56位参与DES运算(第8、16、24、32、40、48、56、64位是校验位, 使得每个密钥都有奇数个1)分组后的明文组和56位的密钥按位替代或交换的方法形成密文组的加密方法。

下图是它的加密流程:

img

DES的密钥长度为56位,这意味着加密时存在256个密钥可供选择,即72,057,594,037,927,936种可能性。

DES现在已经不是一种安全的加密方法,主要因为它使用的56位密钥过短。DES破解机包括1,856个自定义的芯片,可以在数天内破解一个DES密钥—本图显示了使用数个Deep Crack芯片搭成的DES破解机

下图就是专门破解DES加密的芯片:

img

AES(高级加密码标准)

AES为分组密码,分组密码也就是把明文分成一组一组的,每组长度相等,每次加密一组数据,直到加密完整个明文。在AES标准规范中,分组长度只能是128位,也就是说,每个分组为16个字节(每个字节8位)。密钥的长度可以使用128位、192位或256位。密钥的长度不同,推荐加密轮数也不同。

[图片上传失败…(image-baf2d4-1551780610742)]

比如我们家里的无线路由器,一般使用的就是AES加密。

img

AES算法流程

AES加密算法涉及4种操作:

  • 字节替代
  • 行移位
  • 列混淆
  • 轮密钥加

字节替换,上面已经讲过。

我们可以把加密的数据分解成 4x4 大小的表格,然后对表格里的每个空位进行替换然后移位,再进行列混淆加上密钥,重复上面几个步骤。

下图是加密解密的流程图:

img

字节代替

字节代替的主要功能是通过S盒完成一个字节到另外一个字节的映射。S盒的详细构造方法可以直接给出构造好的结果,S盒用于提供密码算法的混淆性。

用两张替换表可以秀好的理解:

加密替换表:

img

解密替换表:

img

假设: 字节00000000B能过加密替换表x=0,y=0替换后的值为(S[0][0]=)63H,再通过解密替换表即可得到替换前的值x=6,y=3,(S-1 [6][3]=)00H。

行移位

行移位是一个4x4的矩阵内部字节之间的置换,用于提供算法的扩散性。

行移位分有:

  • 正向行移位

    假设矩阵的名字为state,用公式表示:state[i][j] = state[i][(j+i)%4];其中i、j属于[0,3]。

  • 逆向行移位

    用公式表示:state[i][j] = state[i][(4+j-i)%4];其中i、j属于[0,3]。

正向行移位: 正向行移位用于加密,其原理图如下。其中:第一行保持不变,第二行循环左移8比特,第三行循环左移16比特,第四行循环左移24比特。

img

逆向行移位: 逆向行移位即是相反的操作,即:第一行保持不变,第二行循环右移8比特,第三行循环右移16比特,第四行循环右移24比特。

列混淆

利用GF(28)域上算术特性的一个代替,同样用于提供算法的扩散性。

同样的也有:

  • 正向列混淆

img

  • 逆向列混淆

img

对称加密思考

对称加密速度快但是安全性相对于非对称加密来说低,为什么呢?

  1. 密钥的交换需要建立在安全的通信基础上,而通信本身是不可能绝对安全的
  2. 加密和解密使用相同的密钥,如果信息泄露,提取到了密钥,密文就会被轻易破解
  3. 无法验证发送者,可以用相同的加密方式伪造密文,这时信息的来源就变得不可靠
  4. 密钥每使用一次都被抛弃,需要重新生成密钥

要想使用对称加密,那么分享信息的各个个体之间都需要分享这个密钥,比如1000个人之间都使用同一个密钥进行密文传输,只要其中一个人密钥被盗窃了,那么整体加密的信息将都被破解了。

那有什么方法呢,这个时候就可以引入另一种加密算法 非对称加密

非对称加密

如何做到即使一个人的密钥被盗窃了,最起码保证你给其他人发送密文不被破解?

简单来说就是: 每个人生成一个“私钥-公钥”对,这个私钥需要每个人自行进行保护!公钥可以随便分享,同时,生成的这个“私钥-公钥”对还有个强大的功能就是,使用私钥加密的信息,只能由该私钥对应的公钥才能解密,使用公钥加密的信息,只能由该公钥对应的私钥才能解密!

还是拿上面小明、小红来举例:

小明生成了他自己的一个“私钥-公钥”对,叫做“小明私钥-小明公钥”,小红生成了他自己的一个“小红私钥-小明公钥”对,之前我们说过私钥要每个个体自己进行保存,公钥可以随便分享,目的是为什么呢?是为了加密信息!

有了公钥、私钥之后,小明在QQ群里与小红说:

img

非对称解密算法 即使别人截取了,也只是知道该公钥而已,但是要是想解密使用该公钥加密的密文!只有一个人可以办得到!就是小红! 为什么?

小明使用小红的公钥加密的信息,只有小红的公钥所对应的私钥,这里就是“小红私钥”,才能解密!所以,没有小红私钥的第三方即时截取了这些密文,也破解不了!或者更严格的说在有限时间内比如说几十上面年内很难进行暴力破解!

我们来看看官方对非对称加密的解释

公开密钥加密,也称为非对称加密,一种密码学算法类型,在这种密码学方法中,需要一对密钥(其实这里密钥说法不好,就是“钥”),一个是私人密钥,另一个则是公开密钥。这两个密钥是数学相关,用某用户密钥加密后所得的信息,只能用该用户的解密密钥才能解密。如果知道了其中一个,并不能计算出另外一个。因此如果公开了一对密钥中的一个,并不会危害到另外一个的秘密性质。称公开的密钥为公钥;不公开的密钥为私钥。

看明白了么?是不是有一种WFT的感受?

img

非对称加密需要包含:

  • Private Key 私钥
  • Public Key 公钥

下图是非对称加密解密的过程图:

img

大概意思就是,要想使用非对称加密算法,首先要有一对key,一个为private key私钥,一个为public key公钥,然后可以把你的public key分发给想给你传密文的用户,然后用户使用该public key加密过得密文,只有使用你的private key才能解密,也就是说,只要你自己保存好你的private key,就能确保,别人想给你发的密文不被破解,所以你不用担心别人的密钥被盗。

  1. 小明用小红给的公钥给明文进加密
  2. 小红用自己的私钥对密文进行解密

这种加密是单向的,所以被称为非对称加密算法

Ok 我们来总结一下 非对称加密码的特点

优缺点

  • 优点:
    1. 允许在不安全的媒体上交换信息
    2. 解密的私钥不发往任何用户,即使密文泄露也不用担心被破解,因为没有私钥
    3. 可以验证消息的发送者
  • 缺点:
    1. 加密速度较慢

这种加密算法应用非常广泛,SSH, HTTPS, TLS,电子证书,电子签名,电子身份证等等。

RSA 加密解密算法

我们来举一个比较常用的算法RSA加密解密算法

RSA加密算法是非对称加密算法的一种,是三个牛逼的人一起提出的。RSA就是下图他们三人姓氏开头字母拼在一起组成的。

img

我猜左边两个会比右边这个更聪明(看头发(ˉ︶ˉ))

公钥和私钥的产生

我们来看看公钥与私钥的产生一共有四个步骤:

  1. 选择两个大素数p和我(大于10100)
  2. 令n=pq和z=(p-1)(q-1)
  3. 选择d与z的互质
  4. 选择e,使e*d=1(mod z)

(n,e)是公钥,(n,d)是私钥

明文P被分成了k位的块,k是满足2k<n的最大整数,于是有了0<=P<n (n最好大于 1024)

互质关系
  • 什么是互质关系?

    如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

  • 任意两个质数构成互质关系,比如13和61。

  • 一个数是质数,另一个数只要不是前者的倍数,两者就构成互质关系,比如3和10。

  • 如果两个数之中,较大的那个数是质数,则两者构成互质关系,比如97和57。

  • 1和任意一个自然数是都是互质关系,比如1和99。

  • p是大于1的整数,则p和p-1构成互质关系,比如57和56。

  • p是大于1的奇数,则p和p-2构成互质关系,比如17和15。

欧拉函数

任意给定正整数n,在小于等于n的正整数之中,有多少个与n构成互质关系?

计算这个值的方法就叫做欧拉函数,以φ(n)表示。在1到8之中,与8形成互质关系的是1、3、5、7,所以 φ(n) = 4。

如果n可以分解成两个互质的整数之积:

n = p1 × p2

则:

φ(n) = φ(p1p2) = φ(p1)φ(p2)

所以:

φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24

加密消息

小明想给小红发送一个消息M,他知道小红产生的公钥(n,e)他使用起先与小红约好的格式将M转换为一个小于n的整数m,比如他可以将每一个字转换为这个字的Unicode码,然后将这些数字连在一起组成一个新的数字。如果他的信息非常长的话,他可以将这个信息分为几段,然后将每一段转换为m。用下面这个公式他可以将m加密为c

加密公式:

img

解密消息

德龙得到海丰的消息c后就可以利用他的私钥d来解码。他可以用以下这个公式来将c转换为m

解密公式:

img

假设:

p = 3, q = 11, n = 33, z = 20, d = 7, e = 3
C = P3(mod 33)
P = C7(mod 33)

套用公式:

img

则:

C = 23(mod 33) = 8(mod 33) = 8
P = 87(mod 33) = 2097152(mod 33) = 2

z=(p-1)(q-1), n=pq, Mod 取余数, (n,e)是公钥, (n,d)是私钥 设明文大P 为2, 2是明文。8是密文

小DEMO

参照上面的公式,我们写一个非常非常非常非常简单的例子:

img

最终得出的结果如下:

img

最大值在 32, 最小值: 1,明文不得超过 p * q,所以p,q必须大。

数字签名

RSA 的另一个最大的优点是其在数字签名中的应用。数字签名的作用是确认消息来源的可靠性,保证信息的完整性和不可否认性。假如A要公开发布自己的文件,A先用HASH算法生成这个文件的消息摘要(或者叫信息指纹),再用 RSA 加密算法(A 的私钥)对摘要进行加密。用户想要下载 A 发布的文件,需要同时下载文件和摘要,下载完毕后,用户使用 A 的公钥对摘要进行解密得到 A 之前生成的摘要,并且用户用同样的 HASH 算法对下载到的文件生成一份摘要,比对这两份摘要是否相等,如果相等,那么可以确定两件事情:文件是完整的,文件是 A 发布的。

我们从很多下载文件的网站都会看到一些 SHA256, MD5 码,这就是对文件进行校验的,验证文件是不是官方发页的,有没有被窜改过。我们看golang.org官方源码包:

img

RSA的算法安全性是基于大素数分解的困难性,攻击者可以分解已知的n,得到p和q,然后可得到z,最后用Euclid算法由e和z得到d。

Openssl生成公私钥

我们可以在服务器上生成自己的公钥私钥,服务器需要安装OpenSSL:

私钥:

img

下面是所生成的公钥:

img

RSA的安全性

常见的 RSA 攻击方法有:

  • 直接分解模数n
  • 对 RSA 的选择密文攻击
  • 对 RSA 的同模攻击
  • 对 RSA 小指数的攻击
  • RSA 的比特性攻击

广泛的应用证明 RSA 体制的安全性是相当可靠的。RSA 密码体制的安全性取决于其加密函数求逆的困难性,即大数因子分解的困难性。虽然至今在理论和实践中还未能证明有分解大整数的有效方法,但大数因子分解未被证明为是 NP 问题,随着计算机计算能力的提高,原来被认为不可能分解的某些大整数可能会被成功分解,这对 RSA 密码体制的安全性构成潜在的威胁。

在未来比较长的时间范围内(在不动用国家级计算机的情况下),大约几百年上千年,在不考虑量子计算和对密码算法破解分析没有太大突破的前提下,不大可能通过计算能力提升而使得现有的密码算法得到轻易地破解。