《算法图解》11.7读书笔记
SHA是美国的 NIST 和 NSA 设计的一种标准的 Hash 算法，SHA 用于数字签名的标准算法的 DSS 中，也是安全性很高的一种 Hash 算法。
SHA-1 是第一代 SHA 算法标准，后来的 SHA-224、SHA-256、SHA-384 和 SHA-512 被统称为 SHA-2
一、SHA-1 算法
SHA-1 算法的输入消息长度小于 264bit，最终输出的结果值是 160 Bits，SHA-1 与 MD4 相比较而言，主要增加了扩展变换，将前一轮的输出也加到了下一轮，这样增加了雪崩效应，而且由于其 160 Bits 的输出，对穷举攻击更具有抵抗性。
1、将消息摘要转换成位字符串
因为在 SHA-1 算法中，它的输入必须为位，所以我们首先要将其转化为位字符串，我们以“abc”字符串来说明问题，因为 'a'=97, 'b'=98, 'c'=99，所以将其转换为位串后为：
01100001 01100010 01100011
2、对转换后的位字符串进行补位操作
SHA-1 算法标准规定，必须对消息摘要进行补位操作，即将输入的数据进行填充，使得数据长度对 512 求余的结果为 448，填充比特位的最高位补一个 1，其余的位补 0，如果在补位之前已经满足对 512 取模余数为 448，也要进行补位，在其后补一位 1 即可。总之，补位是至少补一位，最多补 512 位，
我们依然以“abc”为例，其补位过程如下：
初始的信息摘要：01100001 01100010 01100011
第一步补位操作：01100001 01100010 01100011 1
..... ......
最后的补位操作：01100001 01100010 01100011 10.......0 （后面补了 423 个 0）
而后我们将补位操作后的信息摘要转换为十六进制，如下所示：
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
3、附加长度值
在信息摘要后面附加 64 Bits 的信息，用来表示原始信息摘要的长度，在这步操作之后，信息报文便是 512 Bits 的倍数。通常来说用一个 64 位的数据表示原始消息的长度，如果消息长度不大于 264，那么前 32 位就为0，在进行附加长度值操作后，其“abc”数据报文即变成如下形式：
61626380 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000018
因为“abc”占 3 个字节，即 24 位 ，换算为十六进制即为 0x18。
4、初始化缓存
一个 160 位 MD 缓冲区用以保存中间和最终散列函数的结果。它可以表示为 5 个 32 位的寄存器（H0, H1, H2, H3, H4），初始化为：
H0 = 0x67452301
H1 = 0xEFCDAB89
H2 = 0x98BADCFE
H3 = 0x10325476
H4 = 0xC3D2E1F0
如果大家对 MD5 不陌生的话，会发现一个重要的现象，其前四个与 MD5 一样，但不同之处为存储为 big-endien format。
5、计算消息摘要
在计算报文之前我们还要做一些基本的工作，就是在我们计算过程中要用到的方法或定义。
1)、循环左移操作符 Sn(x)，x 是一个字，也就是 32 Bits 大小的变量，n 是一个整数且 0<=n<=32。
Sn(X) = (X<<n) OR (X>>32-n)
2)、在程序中所要用到的常量，这一系列常量字 k(0)、k(1)、...k(79)，将其以十六进制表示如下：
Kt = 0x5A827999 (0 <= t <= 19)
Kt = 0x6ED9EBA1 (20 <= t <= 39)
Kt = 0x8F1BBCDC (40 <= t <= 59)
Kt = 0xCA62C1D6 (60 <= t <= 79)
3)、所要用到的一系列函数
Ft(b,c,d) ((b&c)|((~b)&d)) (0 <= t <= 19)
Ft(b,c,d) (b^c^d) (20 <= t <= 39)
Ft(b,c,d) ((b&c)|(b&d)|(c&d)) (40 <= t <= 59)
Ft(b,c,d) (b^c^d) (60 <= t <= 79)
4)、计算需要一个缓冲区，由 5 个 32 位的字组成，还需要一个 80 个 32 位字的缓冲区。第一个 5 个字的缓冲区被标识为 A，B，C，D，E。80 个字的缓冲区被标识为 W0, W1,..., W79。另外还需要一个一个字的 TEMP 缓冲区。
为了产生消息摘要，在第 4 部分中定义的 16 个字的数据块 M1, M2,..., Mn 会依次进行处理，处理每个数据块 Mi 包含 80 个步骤。
现在开始处理 M1, M2, ... , Mn。为了处理 Mi，需要进行下面的步骤：
(1). 将 Mi 分成 16 个字 W0, W1, ... , W15, W0 是最左边的字
(2). 对于 t = 16 到 79，令 Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16)
(3). 令 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
(5). 进行累加赋值：
H0 = H0 + A
H1 = H1 + B
H2 = H2 + C
H3 = H3 + D
H4 = H4 + E
在处理完所有的 Mn 后，消息摘要是一个160 位的字符串，以下面的顺序标识：
H0 H1 H2 H3 H4
对于SHA-256、SHA-384、SHA-512，也可以用相似的办法来计算消息摘要。对消息进行补位的算法完全是一样的。
二、SHA-256 算法
SHA-256 算法输入报文的最大长度不超过 264 Bits，输入按 512 Bits 分组进行处理，产生的输出是一个 256 Bits 的报文摘要。该算法处理包括以下几步：
1. 附加填充位
对报文进行填充使报文长度与 448 模 512 同余（长度 = 448 mod 512）， 填充的比特数范围是 1 到 512，填充比特串的最高位为 1，其余位为 0。 就是先在报文后面加一个 1，再加很多个 0，直到长度满足 mod 512=448。为什么是 448？因为 448+64=512。第二步会加上一个 64 位的原始报文的长度信息。
2. 附加长度值
将用 64 位表示的初始报文（填充前）的位长度附加在步骤 1 的结果后（低位字节优先）。
3. 初始化缓存
使用一个 256 位的缓存来存放该散列函数的中间及最终结果。它可以表示为 8 个 32 位的寄存器（A, B, C, D, E, F, G, H），初始化为：
A=0x6A09E667
B=0xBB67AE85
C=0x3C6EF372
D=0xA54FF53A
E=0x510E527F
F=0x9B05688C
G=0x1F83D9AB
H=0x5BE0CD19
4. 处理 512 位报文分组序列
该算法使用了六种基本逻辑函数，由 64 步迭代运算组成。每步都以 256 位缓存值 ABCDEFGH 为输入，然后更新缓存内容。每步使用一个 32 位常数值 Kt 和一个 32 位 Wt。 其中相关常量如下：
一系列的常量字 K(0),K(1), ... , K(79)，如果以 16 进制给出，它们取值如下：
Kt = 0x5A827999 (0<= t <= 19)
Kt = 0x6ED9EBA1 (20<= t <= 39)
Kt = 0x8F1BBCDC (40<= t <= 59)
Kt = 0xCA62C1D6 (60<= t <= 79)
六种基本函数如下：
参与运算的都是 32 位的数，Wt 是分组之后的报文，512bit=32bit*16。也就是 Wt t=1,2..16 由该组报文产生。 Wt t=17,18,..,64 由前面的 Wt 按递推公式计算出来。
Wt递推公式为：
Kt t=1,2..64 是已知的常数。
上面的计算就是不断更新 a,b,c…h 这 32bit*8 。在每个 512 位的分组里面迭代计算 64 次。
5. 结果输出
所有的 512 位分组处理完毕后，对于 SHA-256 算法最后一个分组产生的输出便是 256 位的报文摘要。
sha0 sha1
# -*- coding: utf-8 -*-
# @Author : Codeooo
# @Time : 2022/9/27
import hashlib
data = "Codeooo" # 要进行加密的数据
data_sha = hashlib.sha1(data.encode('utf-8')).hexdigest()
print(data_sha)
# 0xffffffff is used to make sure numbers dont go over 32
def chunks(messageLength, chunkSize):
chunkValues = []
for i in range(0, len(messageLength), chunkSize):
chunkValues.append(messageLength[i:i + chunkSize])
return chunkValues
def leftRotate(chunk, rotateLength):
return ((chunk << rotateLength) | (chunk >> (32 - rotateLength))) & 0xffffffff
def sha1Function(message):
# initial hash values
h0 = 0x67452301
h1 = 0xEFCDAB89
h2 = 0x98BADCFE
h3 = 0x10325476
h4 = 0xC3D2E1F0
messageLength = ""
# preprocessing
for char in range(len(message)):
messageLength += '{0:08b}'.format(ord(message[char]))
temp = messageLength
messageLength += '1'
while (len(messageLength) % 512 != 448):
messageLength += '0'
messageLength += '{0:064b}'.format(len(temp))
chunk = chunks(messageLength, 512)
for eachChunk in chunk:
words = chunks(eachChunk, 32)
w = [0] * 80
for n in range(0, 16):
w[n] = int(words[n], 2)
for i in range(16, 80):
# sha1
w[i] = leftRotate((w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16]), 1)
# sha0
# w[i] = (w[i - 3] ^ w[i - 8] ^ w[i - 14] ^ w[i - 16])
# Initialize hash value for this chunk:
a = h0
b = h1
c = h2
d = h3
e = h4
# main loop:
for i in range(0, 80):
if 0 <= i <= 19:
f = (b & c) | ((~b) & d)
k = 0x5A827999
elif 20 <= i <= 39:
f = b ^ c ^ d
k = 0x6ED9EBA1
elif 40 <= i <= 59:
f = (b & c) | (b & d) | (c & d)
k = 0x8F1BBCDC
elif 60 <= i <= 79:
f = b ^ c ^ d
k = 0xCA62C1D6
a, b, c, d, e = ((leftRotate(a, 5) + f + e + k + w[i]) & 0xffffffff, a, leftRotate(b, 30), c, d)
h0 = h0 + a & 0xffffffff
h1 = h1 + b & 0xffffffff
h2 = h2 + c & 0xffffffff
h3 = h3 + d & 0xffffffff
h4 = h4 + e & 0xffffffff
return '%08x%08x%08x%08x%08x' % (h0, h1, h2, h3, h4)
sha1Hash = sha1Function(data)
print(sha1Hash)
