SHA

DeeLMind大约 8 分钟

SHA

SHA（Secure Hash Algorithm）是由美国国家安全局（NSA）设计的哈希函数族。SHA算法通过对输入数据进行哈希计算，生成固定长度的哈希值，广泛应用于数字签名、信息完整性验证等领域。SHA算法的安全性依赖于输入的长度和处理速度。

SHA家族的算法

SHA算法家族包含多个不同的版本，主要包括SHA-0、SHA-1、SHA-2和SHA-3系列。每种算法的特点和安全性各不相同。

SHA算法的应用

  • 数字签名：确保数据的完整性和身份验证。
  • 密码学协议：如SSL/TLS协议中的密钥交换和身份认证。
  • 区块链技术：例如比特币中使用SHA-256算法来确保交易的安全性。
  • 数据完整性验证：校验文件在传输过程中是否被篡改。

SHA256原理

  1. 数据填充

在消息末尾添加一个1位的比特。

然后添加若干个0位，直到消息的长度接近512的倍数。

最后，消息的长度（以比特为单位）以64位二进制形式追加到消息的末尾。

假设我们有一个消息"abc"，其长度为3字节（24比特）。我们来详细计算这个消息如何填充至512位。

"a" = 01100001  
"b" = 01100010  
"c" = 01100011

011000010110001001100011

0110000101100010011000111

0110000101100010011000111[0...0]  (487个零)

0110000101100010011000111[0...0](487个零)0000000000000000000000000000000000000000000000000000000000011000
  1. 初始化哈希值
H0 = 0x6a09e667
H1 = 0xbb67ae85
H2 = 0x3c6ef372
H3 = 0xa54ff53a
H4 = 0x510e527f
H5 = 0x9b05688c
H6 = 0x1f83d9ab
H7 = 0x5be0cd19

  1. 消息分块

  2. 消息扩展

  3. 迭代计算

什么是非线性关系？

在密码学中，非线性 指的是一个输入与输出之间没有简单、直接的比例或加法关系。非线性使得攻击者无法通过观察某些输入的变化来推测输出的变化或计算过程中的其他信息。简单地说，输入与输出之间的关系是复杂且难以预测的。

增加数据的 非线性关系 是现代加密算法中非常重要的设计原则，尤其是在设计哈希函数、对称加密算法（如 AES）以及公钥加密算法（如 RSA）时。非线性关系的引入能显著增强算法的 安全性 和 抗攻击性，尤其是针对 碰撞攻击、预映像攻击 和 字典攻击 等。

举例：

  • 线性关系：如果一个加密算法是线性的，那么加密结果可能只是输入的某种简单函数（例如，输入加上一个常量或通过线性变换）。这种关系容易被预测和攻击。

  • 非线性关系：非线性则意味着输入与输出之间存在复杂的数学关系，例如通过一些不可逆的位操作、非线性函数或多轮变换进行数据转换。这种关系使得即使输入发生微小变化，输出也会产生显著且不可预测的变化。

非线性关系在加密算法中的重要性

1) 增强复杂性和不可预测性

  • 非线性函数使得攻击者无法仅凭输入数据的部分信息推测输出。这是因为输入和输出之间没有简单的数学关系，而是通过复杂的操作生成结果。
  • 例如，AES 中的 S-Box（替换盒）通过非线性映射将输入数据的每一位与其他位进行复杂的交叉映射，导致输出数据对输入的每一位都有强烈的依赖。

2) 防止线性分析和差分分析攻击

  • 差分分析攻击（Differential Cryptanalysis） 和 线性分析攻击（Linear Cryptanalysis） 是针对加密算法的一种高级攻击方式。攻击者通过观察加密过程中的输入与输出之间的关系（差分或线性关系）来推测密钥或其它信息。
  • 引入非线性关系可以打破这些攻击的基础，使得攻击者无法通过寻找某种规律来破解算法。

3) 增强雪崩效应（Avalanche Effect）

  • 雪崩效应 是指加密算法的输出在输入发生微小变化时，应该发生显著变化。非线性操作增强了这种效应，即使输入数据的某个位发生微小变化，输出的结果也会发生巨大变化，从而提高加密算法的安全性。
  • 例如，在 SHA-256 中，sigma0(x) 操作通过多个轮次的位移、异或等操作确保了雪崩效应，使得输入的任何微小变化都会导致输出哈希值的巨大变化。

4) 避免早期的密码学攻击

  • 早期的加密算法大多数使用线性或简单的数学变换，这导致它们易受 频率分析、代数攻击 和 碰撞攻击 等传统密码学攻击的影响。非线性关系是现代加密算法防止这些攻击的有效手段。

如何通过位操作增强非线性关系？

在哈希算法（如 SHA-256）和对称加密算法（如 AES）中，非线性关系通常是通过 位操作 和 数学变换 来实现的。以下是一些常见的方法：

1) 循环右移（Rotate Right）

  • 通过循环右移，输入数据的位会被重新排列。每一轮的位移操作使得原始数据的位之间没有直接的线性关系，从而增强了数据的非线性。
  • 在 SHA-256 中，rotr(x, n)（循环右移操作）将数据的不同部分以不同的方式重新排列，使得每一轮运算后的输出结果都依赖于之前的所有操作。

2) 算术右移（Arithmetic Right Shift）

  • 算术右移 x >> n 操作在移动时会保留符号位。这个操作也会引入 非线性，因为它改变了数据的高低位结构，并且对不同的输入位有不同的影响。
  • 在 SHA-256 中，x >> 3 是一个算术右移操作，确保输入的高位和低位之间有较强的依赖关系。

3) 异或操作（XOR）

  • 异或操作是加密中常用的 非线性 运算。两个相同的值异或为 0，不同的值异或为 1。异或的这些特性使得它成为强有力的非线性操作。
  • 在 SHA-256 和其他加密算法中，多个异或操作被用来将输入数据的不同部分进行混合，使得输入数据的位之间没有简单的线性关系，从而增加了输出的复杂性。

4) S-Box（替换盒）

  • 在对称加密算法中，常通过 S-Box 来实现非线性映射。S-Box 是一个查找表，它根据输入的每一位生成输出的不同位。由于 S-Box 的输出不是线性的，这使得每个输入位对最终结果的影响变得复杂。
  • 在 AES 中，S-Box 负责将输入字节映射到不同的输出字节，通过这种非线性映射增加了算法的安全性。

5) 非线性函数（如 σ₀(x) 和 σ₁(x)）

  • 在 SHA-256 中，σ₀(x) 和 σ₁(x) 是两种非线性函数，用于对消息进行扩展。它们结合了右移、异或等操作，确保输入字的每一位对最终哈希值产生影响，并增强数据的非线性。

4. 非线性关系在具体算法中的作用

SHA-256 中的非线性操作：

  • sigma0(x) 和 sigma1(x) 中的位操作，如右移和异或，增加了输入数据和输出哈希值之间的 非线性关系。这些操作确保了输入的每一位都会影响最终的哈希结果，即使输入发生微小变化，也会导致哈希值的显著不同。

AES 中的非线性操作：

  • 在 AES 算法中，S-Box 是通过非线性映射引入非线性关系的关键部分。S-Box 使得每一位输入都通过复杂的映射生成输出，这种非线性映射是抵抗线性和差分攻击的关键。

SHA256代码

class SHA256:
    def __init__(self):
        # 初始化哈希常量
        self.K = [
            0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
            0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
            0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
            0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
            0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
            0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
            0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
            0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
        ]
        
        # 初始化初始哈希值
        self.H = [
            0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19
        ]
    
    # 循环右移操作
    def rotr(self, x, n):
        return (x >> n) | (x << (32 - n)) & 0xffffffff
    
    # 小写字母和大写字母的合并计算
    def ch(self, x, y, z):
        return (x & y) ^ (~x & z)
    
    # 选择最大值计算
    def maj(self, x, y, z):
        return (x & y) ^ (x & z) ^ (y & z)
    
    # 带扩展的终端位运算
    def sigma0(self, x):
        return self.rotr(x, 7) ^ self.rotr(x, 18) ^ (x >> 3)
    
    # 带扩展的卷曲运算
    def sigma1(self, x):
        return self.rotr(x, 17) ^ self.rotr(x, 19) ^ (x >> 10)
    
    def big_sigma0(self, x):
        return self.rotr(x, 2) ^ self.rotr(x, 13) ^ self.rotr(x, 22)
    
    def big_sigma1(self, x):
        return self.rotr(x, 6) ^ self.rotr(x, 11) ^ self.rotr(x, 25)
    
    def pad_message(self, message):
        # 将消息长度扩展到 512 位倍数
        length = len(message) * 8  # 比特长度
        message += b'\x80'  # 添加 1 后跟随零填充
        while len(message) % 64 != 56:
            message += b'\x00'
        message += length.to_bytes(8, byteorder='big')  # 最后加上长度信息
        return message
    
    def process_block(self, block):
        # 处理每个消息块
        w = [0] * 64
        for i in range(16):
            w[i] = int.from_bytes(block[i * 4: (i + 1) * 4], byteorder='big')
        
        for i in range(16, 64):
            w[i] = (self.sigma1(w[i - 2]) + w[i - 7] + self.sigma0(w[i - 15]) + w[i - 16]) & 0xffffffff
        
        a, b, c, d, e, f, g, h = self.H
        
        for i in range(64):
            t1 = (h + self.big_sigma1(e) + self.ch(e, f, g) + self.K[i] + w[i]) & 0xffffffff
            t2 = (self.big_sigma0(a) + self.maj(a, b, c)) & 0xffffffff
            
            h = g
            g = f
            f = e
            e = (d + t1) & 0xffffffff
            d = c
            c = b
            b = a
            a = (t1 + t2) & 0xffffffff
        
        self.H = [(x + y) & 0xffffffff for x, y in zip(self.H, [a, b, c, d, e, f, g, h])]
    
    def digest(self, message):
        # 消息预处理
        message = self.pad_message(message)
        
        # 逐块处理消息
        for i in range(0, len(message), 64):
            self.process_block(message[i:i+64])
        
        # 返回哈希值
        return ''.join(f'{x:08x}' for x in self.H)

# 示例
sha256 = SHA256()
message = b"Hello, world!"
hash_result = sha256.digest(message)
print(f"SHA-256 Hash: {hash_result}")
上次编辑于:
贡献者: DeeLMind
Copyright © 2023 極客方舟