加密算法.md

Posted by lizhao on 07-09,2019

加密算法

[toc]

分类

常见的加密算法可以分成三类,对称加密算法,非对称加密算法和Hash算法。

介绍

不可逆加密-hash算法

MD5

Hash算法特别的地方在于它是一种单向算法,用户可以通过Hash算法对目标信息生成一段特定长度的唯一的Hash值,却不能通过这个Hash值重新获得目标信息。因此Hash算法常用在不可还原的密码存储、信息完整性校验等。

破解难度
32^36 = 6.3×e^49 
我也时无聊透了,你说的我也算了算,集体算法是,全球60亿人每人一台超级计算机,每台计算机每秒生产1万亿个不同MD5的文件,那么要持续多久呢?
答案是:80的22次方年,对不去,我实在无法想想这是多少年……
虽然这个数值不是无限的,但是已经等于无法达到了,起码以目前人类的认知和技术,这是个无法实现的事情
算法原理


1、数据填充

对消息进行数据填充,使消息的长度对512取模得448,设消息长度为X,即满足X mod 512=448。根据此公式得出需要填充的数据长度。

填充方法:在消息后面进行填充,填充第一位为1,其余为0。

2、添加消息长度

在第一步结果之后再填充上原消息的长度,可用来进行的存储长度为64位。如果消息长度大于264,则只使用其低64位的值,即(消息长度 对 264取模)。

在此步骤进行完毕后,最终消息长度就是512的整数倍。

3、数据处理

准备需要用到的数据:

4个常数: A = 0x67452301, B = 0x0EFCDAB89, C = 0x98BADCFE, D = 0x10325476;
4个函数:F(X,Y,Z)=(X & Y) | ((~X) & Z); G(X,Y,Z)=(X & Z) | (Y & (~Z));  H(X,Y,Z)=X ^ Y ^ Z; I(X,Y,Z)=Y ^ (X | (~Z));
把消息分以512位为一分组进行处理,每一个分组进行4轮变换,以上面所说4个常数为起始变量进行计算,重新输出4个变量,以这4个变量再进行下一分组的运算,如果已经是最后一个分组,则这4个变量为最后的结果,即MD5值。

具体计算的实现较为复杂,建议查阅相关书籍,下面给出在C++上的实现代码。

彩虹表

一个用于加密散列函数逆运算的预先计算好的表, 为破解密码的散列值(或称哈希值、微缩图、摘要、指纹、哈希密文)而准备

可逆加密

对称加密

对称加密(也叫私钥加密)指加密和解密使用相同密钥的加密算法。有时又叫传统密码算法,就是加密密钥能够从解密密钥中推算出来,同时解密密钥也可以从加密密钥中推算出来。而在大多数的对称算法中,加密密钥和解密密钥是相同的,所以也称这种加密算法为秘密密钥算法或单密钥算法。它要求发送方和接收方在安全通信之前,商定一个密钥。对称算法的安全性依赖于密钥,泄漏密钥就意味着任何人都可以对他们发送或接收的消息解密,所以密钥的保密性对通信性至关重要。

例子
秘钥是5
3 * 5 = 15
15 / 5 = 3

非对称加密

非对称加密算法需要两个密钥:公开密钥(publickey)和私有密钥(privatekey)。公开密钥与私有密钥是一对,如果用公开密钥对数据进行加密,只有用对应的私有密钥才能解密;如果用私有密钥对数据进行加密,那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥,所以这种算法叫作非对称加密算法。
非对称加密算法实现机密信息交换的基本过程是:甲方生成一对密钥并将其中的一把作为公用密钥向其它方公开;得到该公用密钥的乙方使用该密钥对机密信息进行加密后再发送给甲方;甲方再用自己保存的另一把专用密钥对加密后的信息进行解密。

公钥和私钥的产生

假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥:

随意选择两个大的质数p和q,p不等于q,计算N=pq。

根据欧拉函数,不大于N且与N互质的整数个数为(p-1)(q-1)

选择一个整数e与(p-1)(q-1)互质,并且e小于(p-1)(q-1)

用以下这个公式计算d:d×e≡1(mod(p-1)(q-1))

将p和q的记录销毁。

(N,e)是公钥,(N,d)是私钥。(N,d)是秘密的。Alice将她的公钥(N,e)传给Bob,而将她的私钥(N,d)藏起来。

加密消息

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

加密公式加密公式 n^e = c(mod N) 计算c并不复杂。Bob算出c后就可以将它传递给Alice。

解密消息

Alice得到Bob的消息c后就可以利用她的密钥d来解码。她可以用以下这个公式来将c转换为n:

解密公式解密公式 c^d = n(mod N)

得到n后,她可以将原来的信息m重新复原。

解码的原理是

以及ed≡1(modp-1)和ed≡1(modq-1)。由费马小定理可证明(因为p和q是质数)

这说明(因为p和q是不同的质数,所以p和q互质)

安全性
例子
取p = 7,q = 11,
得出N = 77,
得出(p-1)(q-1) = 60。
取e = 7
由d×e≡1(mod(p-1)(q-1)),
化简 7d mod 60 = 1
得出d = 43

(N,e)是公钥(77,7)
(N,d)是公钥(77,43)  
要发送的内容m为3

加密过程
由加密公式:m^e = c(mod N),
代入 c = 3^7 mod 77 
得出  c = 31

解密过程
由解密公式:c^d = m(mod N)
代入数据 m = 31^43 mod 77
解得m = 3

SHA1

输入任意的一个字符串,将会获得一个160位的二进制信息摘要(我们看到的,一般是已经转换成十六进制消息,共40位) 这篇文章将会以 Zab 为消息,然后进行转换

处理的步骤

声明常量及运算符:

  1. 运算符和符号

    X^Y    = X, Y逻辑与
    
    X // Y   = X, Y逻辑或
    
    X XOR Y= X, Y逻辑异或
    
    ~X     =   X逻辑取反
    
    X+Y定义如下:
    
    字 X 和 Y 代表两个整数 x 和y, 其中 0 <= x < 2^32 且 0 <= y < 2^32. 令整数z = (x + y) mod 2^32. 这时候 0 <= z < 2^32. 将z转换成字Z, 那么就是 Z = X + Y.
    
    循环左移位操作符Sn(X)。X是一个字,n是一个整数,0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n)
    
    X<<n定义如下:抛弃最左边的n位数字,将各个位依次向左移动n位,然后用0填补右边的n位(最后结果还是32位)。X>>n是抛弃右边的n位,将各个位依次向右移动n位,然后在左边的n位填0。因此可以叫Sn(X)位循环移位运算
    
  2. 常量K

    这个东西下面运算的时候用到,t是循环变量,是传入的参数,类似于分段函数,用到再往这里翻

    Kt = 0x5A827999 (0 <= t <= 19)

    Kt = 0x6ED9EBA1 (20 <= t <= 39)

    Kt = 0x8F1BBCDC (40 <= t <= 59)

    Kt = 0xCA62C1D6 (60 <= t <= 79).

  3. 定义函数

在SHA1中我们需要一系列的函数。
每个函数ft (0 <= t <= 79)都操作32位字B,C,D并且产生32位字作为输出。
ft(B,C,D)可以如下定义

ft(B,C,D) = (B AND C) or ((NOT B) AND D) ( 0 <= t <= 19)

ft(B,C,D) = B XOR C XOR D             (20 <= t <= 39)

ft(B,C,D) = (B AND C) or (B AND D) or (C AND D) (40 <= t <= 59)

ft(B,C,D) = B XOR C XOR D                    (60 <= t <= 79).

预处理

转成位

具体过程:按照该字符的ASCII码进行转换

补位

可以这么推算,最后输出的是一个定长的数据,那么输入的内容应该也是要保证长度,所以和md5一样,都有一个补位的机制。 具体过程:先补一个1,然后再补0,直到长度满足对512取模后余数是448

填入原数据长度

具体过程:原来的数据的长度,放到补位完消息的末尾,前面补0,共计64位

示例

原数据是Zab

转成位 
    Zab = 0x5A6162 = 0101 1010 0110 0001 0110 0010
    'Z' = 0x5A = 0101 1010
    'a' = 0x61 = 0110 0001
    'b' = 0x62 = 0110 0010
补位      
    先补一个1--》0101 1010 0110 0001 0110 0010 1 
    再补n个0 --》0101 1010 0110 0001 0110 0010 10...0
    十六进制写法:
        61626380 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000
    现在,数据的长度是448,对512取膜余数就是448
填入原数据长度
    原消息(0101 1010 0110 0001 0110 0010)长度是24,
    二进制消息后面补上:
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00011000
    十六进制补上 00000000 00000018
    结果就是
        61626380 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00000000
        00000000 00000000 00000000 00000018
        
下面就是按照这个十六进制角度来运算,二进制的可以自行转换

运算

求Mn

n的取值范围是0~15,根据我们之前预处理之后的数据获取

求Wn

n的范围是0~79,根据0.2标签的常量,0.3的函数,Mn,H0 ~ H4进行计算
> W t = M t , 当0≤t≤15   
> Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16) ,当16≤t≤79,这里的t-3,t-8是下标

求H0~H4

声明变量TEMP 
H0~H4 初始值
> H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0. 

声明变量A = H0, B = H1, C = H2, D = H3, E = H4.(4) 对于 t = 0 到 79,执行下面的循环
TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;
E = D; D = C; C = S30(B); B = A; A = TEMP;

按顺序拼接H0 H1 H2 H3 H4,即可得到结果

示例

第一步结束之后的数据为

> 61626380 00000000 00000000 00000000
> 00000000 00000000 00000000 00000000
> 00000000 00000000 00000000 00000000
> 00000000 00000000 00000000 00000018
求Mn
       M0 = 0x61626380
       M1 = 0x00000000
       M2 = 0x00000000
       M3 = 0x00000000
       ...
       M15 = 0x00000018
求Wn
    Wt = Mt , 当0≤t≤15   
    Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).当16≤t≤79
    W0 = M0 = 0x61626380
    W15 = M15 = 0x00000018
    ...
    W79 = 
求H0~H4

令 A = H0, B = H1, C = H2, D = H3, E = H4.
对于 t = 0 到 79,执行下面的循环
    TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;
    E = D; D = C; C = S30(B); B = A; A = TEMP;

令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E. 

按顺序拼接H0 H1 H2 H3 H4,

参考链接:

SHA1算法实现及详解

SHA1算法原理