一、Hash概念和基本要求1、Hash函数的定义1Hash是一个将任意长的消息M映射为较短的、固定长度的值的函数表示为。2Hash函数也称为哈希函数、散列函数、压缩函数、杂凑函数、指纹函数等其函数值称为哈希值、散列值、杂凑码、指纹、消息摘要等。3Hash函数一般是公开的。2、Hash函数满足条件及安全性定义1Hash函数的目的是为需认证的数据产生一个“指纹”Hash函数应满足以下条件①Hash函数的输入可以是任意长数据。②Hash函数的输出是固定长数据。③易于在软件和硬件实现。2Hash函数为了实现安全认证需要满足如下安全条件3、Hash函数的基本用法1加密消息与摘要①流程②作用加密提供了保密性摘要对比提供了完整性认证防止消息被篡改接收方却不知道2仅加密摘要①流程②作用消息本身是明文不提供保密性只有加密的摘要提供完整性认证攻击者不知道密钥K无法伪造摘要3用私钥签名摘要①流程②作用消息本身是明文不提供保密性私钥签名的摘要可以提供不可否认性只有Bob能生成这个签名4用私钥签名消息与摘要①流程②作用加密提供了保密性私钥签名提供认证以及不可否认性5使用共享秘密S提供认证①流程②作用消息本身不加密不提供保密性共享秘密S只有双方知道攻击者无法伪造摘要提供了认证6使用共享秘密S提供认证传输内容加密①流程②作用加密提供了保密性共享秘密S只有双方知道攻击者无法伪造摘要提供了认证二、生日攻击1、两类生日攻击1第I类生日攻击2第II类生日攻击2、生日攻击下的安全应用三、SHA-1算法1、SHA-1算法概述1安全杂凑算法Secure Hash AlgorithmSHA由美国NIST设计于1993年作为联邦信息处理标准公布。2SHA是基于MD4的算法其结构与MD4非常类似。2、SHA-1算法处理步骤1算法描述①算法的输入小于bit长的任意消息分为512bit长的分组。②算法的输出160bit长的消息摘要。③算法的框图与MD5一样但杂凑值的长度和链接变量的长度为160bit。2具体步骤①消息填充[1]目标填充后的消息长度bit长在模512下为448留出64bit存原始长度。[2]填充方式先加一个bit1后面补bit0直到长度满足要求。即使消息长度已经是448 mod 512也必须填充比如448bit的消息要填充512bit变成960bit[3]作用把消息长度信息固定在最后64bit防止攻击者通过修改消息长度来伪造碰撞。②附加消息长度[1]把填充前的原始消息长度用64bit big-endian格式数据的高字节保存在内存的低地址中附加到消息末尾如果消息长度超过2^64就取模2^64。[2]作用即使攻击者修改了消息也很难同时伪造出匹配的长度字段大幅提升抗碰撞能力。③初始化缓冲区[1]使用160bit长的缓冲区存储中间结果和最终杂凑值。[2]缓冲区为5个32bit以big-endian格式存储数据的寄存器A、B、C、D、E初始值固定如下公式表示为IV为缓冲区5个寄存器的初始值A 0x67452301B 0xEFCDAB89C 0x98BADCFBD 0x10325476E 0xC3D2E1F0④分组迭代压缩⑤输出消息所有分组处理完后最后一个分组的输出即为160bit的消息摘要公式表示为其中MD是最终的摘要值L为消息包括填充位和长度字段的分组数3SHA的压缩函数SHA的压缩函数由4轮处理过程组成每轮处理过程20步迭代运算组成每一步迭代运算的形式为3、SHA-1算法的C语言实现#include stdio.h #include stdint.h #include string.h // 左循环移位 #define ROTL(x, n) (((x) (n)) | ((x) (32 - (n)))) // 消息块大小 512 比特 64 字节 #define BLOCK_SIZE 64 // 根据步骤选择逻辑函数 #define F0(t, b, c, d) (((b) (c)) | ((~b) (d))) // 0 t 19 #define F1(t, b, c, d) ((b) ^ (c) ^ (d)) // 20 t 39 #define F2(t, b, c, d) (((b) (c)) | ((b) (d)) | ((c) (d))) // 40 t 59 #define F3(t, b, c, d) ((b) ^ (c) ^ (d)) // 60 t 79 // 常量 Kt #define K0 0x5A827999 // 0 t 19 #define K1 0x6ED9EBA1 // 20 t 39 #define K2 0x8F1BBCDC // 40 t 59 #define K3 0xCA62C1D6 // 60 t 79 // SHA-1 上下文结构 typedef struct { uint32_t h[5]; // 当前哈希值 uint64_t count; // 已处理比特数 uint8_t buffer[BLOCK_SIZE]; // 未处理的数据块 } SHA1_CTX; // 初始化上下文 void sha1_init(SHA1_CTX *ctx) { ctx-h[0] 0x67452301; ctx-h[1] 0xEFCDAB89; ctx-h[2] 0x98BADCFE; ctx-h[3] 0x10325476; ctx-h[4] 0xC3D2E1F0; ctx-count 0; memset(ctx-buffer, 0, BLOCK_SIZE); } // 处理一个 512 位块 void sha1_process_block(SHA1_CTX *ctx) { uint32_t w[80]; uint32_t a, b, c, d, e, temp; int t; // 将块分解为 16 个大端字 for (t 0; t 16; t) { w[t] (ctx-buffer[t * 4] 24) | (ctx-buffer[t * 4 1] 16) | (ctx-buffer[t * 4 2] 8) | (ctx-buffer[t * 4 3]); } // 扩展生成 80 个字 for (t 16; t 80; t) { w[t] ROTL(w[t - 3] ^ w[t - 8] ^ w[t - 14] ^ w[t - 16], 1); } a ctx-h[0]; b ctx-h[1]; c ctx-h[2]; d ctx-h[3]; e ctx-h[4]; // 主循环 for (t 0; t 80; t) { uint32_t f, k; if (t 20) { f F0(t, b, c, d); k K0; } else if (t 40) { f F1(t, b, c, d); k K1; } else if (t 60) { f F2(t, b, c, d); k K2; } else { f F3(t, b, c, d); k K3; } temp ROTL(a, 5) f e k w[t]; e d; d c; c ROTL(b, 30); b a; a temp; } // 更新哈希值 ctx-h[0] a; ctx-h[1] b; ctx-h[2] c; ctx-h[3] d; ctx-h[4] e; } // 更新上下文处理输入数据 void sha1_update(SHA1_CTX *ctx, const void *data, size_t len) { const uint8_t *bytes (const uint8_t*)data; size_t i; for (i 0; i len; i) { ctx-buffer[ctx-count % BLOCK_SIZE] bytes[i]; ctx-count; if ((ctx-count % BLOCK_SIZE) 0) { sha1_process_block(ctx); } } } // 完成哈希计算输出 20 字节摘要 void sha1_final(SHA1_CTX *ctx, uint8_t digest[20]) { uint64_t bit_len ctx-count * 8; size_t pad_len; // 先追加 0x80 字节 uint8_t final_byte 0x80; sha1_update(ctx, final_byte, 1); // 剩余空间不足 8 字节时填充 0x00 至新块并处理 while ((ctx-count % BLOCK_SIZE) ! 56) { final_byte 0x00; sha1_update(ctx, final_byte, 1); } // 追加 64 位长度大端序 uint8_t len_bytes[8]; for (int i 0; i 8; i) { len_bytes[i] (bit_len (56 - 8 * i)) 0xFF; } sha1_update(ctx, len_bytes, 8); // 提取最终哈希值大端序 for (int i 0; i 5; i) { digest[i * 4] (ctx-h[i] 24) 0xFF; digest[i * 4 1] (ctx-h[i] 16) 0xFF; digest[i * 4 2] (ctx-h[i] 8) 0xFF; digest[i * 4 3] ctx-h[i] 0xFF; } } // 便捷函数直接计算 SHA-1 哈希 void sha1(const uint8_t *data, size_t len, uint8_t digest[20]) { SHA1_CTX ctx; sha1_init(ctx); sha1_update(ctx, data, len); sha1_final(ctx, digest); } // 打印摘要的十六进制形式 void print_digest(const uint8_t digest[20]) { for (int i 0; i 20; i) { printf(%02x, digest[i]); } printf(\n); } // 测试 int main() { // 测试向量1空字符串 uint8_t digest[20]; sha1((const uint8_t*), 0, digest); printf(SHA-1(\\) ); print_digest(digest); // 应为 da39a3ee5e6b4b0d3255bfef95601890afd80709 // 测试向量2abc sha1((const uint8_t*)abc, 3, digest); printf(SHA-1(\abc\) ); print_digest(digest); // 应为 a9993e364706816aba3e25717850c26c9cd0d89d // 测试向量3abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq const char *long_str abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq; sha1((const uint8_t*)long_str, strlen(long_str), digest); printf(SHA-1(long) ); print_digest(digest); // 应为 84983e441c3bd26ebaae4aa1f95129e5e54670f1 return 0; }