密码编码学算术学习.zip

# MD2哈希算法实现(附源码) > 相关文章: > - [MD2中用于随机置换的S盒是如何生成的？](https://blog.csdn.net/guyongqiangx/article/details/117856118) 学习MD2哈希算法第一手的参考资料是rfc1319文档，不过这个文档中有一处错误(关于Checksum计算)，由于没留意勘误说明，这让我在当初趟了个大坑，按照文档描述计算得到的哈希怎么都不对。 如果您打算学习MD2算法，强烈建议直接参考RFC1319，链接如下： - RFC1319: The MD2 Message-Digest Algorithm - https://www.rfc-editor.org/rfc/rfc1319.html 虽然rfc1319一共有11页，但是除去第5页开始的参考代码，再除去前言，申明和各种说明，关于算法本身描述只有3页，所以整个MD2算法描述部分倒也简洁。 ## 1. MD2算法描述 整个MD2哈希算法细节参考官方文档，以下对消息处理进行分层次的描述。 ### 1.1 消息填充 - 填充长度 MD2处理消息时每个block大小为16个字节，通过填充，使其消息长度为16字节的整数倍。 如果原始消息的长度已经是16字节的整数倍了，则再额外填充一个16字节的数据块。 - 填充内容 那到底要填充什么内容呢？官方文档的原话是： > ``` > Padding is performed as follows: "i" bytes of value "i" are appended > to the message so that the length in bytes of the padded message > becomes congruent to 0, modulo 16. At least one byte and at most 16 > 16 bytes are appended > ``` 简单来说，缺几个字节，就填几个字节的数值几。 例如， - 缺1个字节，则填充1个字节的0x01； - 缺2个字节，则填充2个自己的0x012； - 缺16个字节，则填充16个字节的0x10； ### 1.2 追加校验和(Checksum) 对填充后的数据，逐块计算，最后得到16字节的校验和(刚好1个block)，然后将这个1 block大小的校验和追加到填充消息的后面。 校验和的具体算法，参考官方文档的3.2节(Append Checksum)。 在校验和计算的描述中，有一个错误: ``` /* Process each 16-word block. */ For i = 0 to N/16-1 do /* Checksum block i. */ For j = 0 to 15 do Set c to M[i*16+j]. Set C[j] to S[c xor L]. <-- 这里应该是 "Set C[j] to C[j] xor S[c xor L]."，即 C[j] = C[j] ^ S[c ^ L] Set L to C[j]. end /* of loop on j */ end /* of loop on i */ ``` 以下是勘误链接： - https://www.rfc-editor.org/errata/eid555 ### 1.3 数据分块处理 在整个消息层面对消息填充，并追加了校验和以后，将消息按照每个block 16字节进行分块处理。 对每一个块数据的处理又分为三步(实际上是两步)。 **第一步，数据预处理** 缓冲区的前16字节存放上一个block的哈希值。(第一个时为0) 将待处理的16字节数据扩展为32字节，并存放到48字节缓冲区的后32个字节中。 **第二步，处理缓冲区数据** 对48字节的缓冲区数据进行18轮替换处理 **第三步，保留缓冲区前16字节数据** 48字节缓冲区数据的前16字节实际上就是到当前block为止的哈希值，需要将这个哈希值作为下一个block的输入之一。 每一个block数据在处理时有两个输入数据： 1. 上一个block的哈希值(第一个block处理时，输入数据为0) 2. 当前block的数据 ### 1.4 输出哈希 逐块处理数据时，最后一块的数据是整个消息的校验和。 在处理完这一块数据以后，输出缓冲区的前16字节作为整个消息的MD2哈希值。 ## 2. C语言代码(附详细注释) 整个代码共5个文件: md2.h, md2.c, md2test.c, utils.h, utils.c, Makefile - md2.h, md2.c - MD2算法实现的核心文件 - md2test.c - 测试文件，可以直接编译为可执行文件md2，计算计算任何字符串或输入文件的哈希。 - utils.h, utils.c, Makefile - 辅助文件 ### 2.1 核心源码及注释 - md2.h ``` #ifndef __ROCKY_MD2__H #define __ROCKY_MD2__H #define ERR_OK 0 #define ERR_ERR -1 /* generic error */ #define ERR_INV_PARAM -2 /* invalid parameter */ #define ERR_TOO_LONG -3 /* too long */ #define ERR_STATE_ERR -4 /* state error */ typedef unsigned char uint8_t; typedef unsigned short uint16_t; typedef unsigned int uint32_t; typedef unsigned long long uint64_t; typedef struct md2_context { /* * 数据总长度 * MD2和SHA3一样，都没有使用长度填充 * 所以total没有什么用，这里保留total为了调试打印第几块数据而已 */ uint64_t total; /* * 48字节的buffer， * 前16字节用于处理时保存和传递每个block(16字节)数据的哈希值 * 后32字节在处理每个block作为临时变量 * 所以也可以只定义16字节用于存放哈希，然后在处理每一块时临时申请48字节的buffer */ uint8_t X[48]; /* * 一个block(16字节)大小的缓冲区， * 用于保存处理中不足一个block的数据， * 以及最后填充的数据块和附加的checksum用于压缩处理 */ /* last block */ struct { uint32_t used; /* used bytes */ uint8_t buf[16]; /* block data buffer */ }last; /* 校验和 */ uint8_t checksum[16]; /* checksum */ }MD2_CTX; /* https://www.openssl.org/docs/man1.1.0/man3/MD5_Init.html */ int MD2_Init(MD2_CTX *c); int MD2_Update(MD2_CTX *c, const void *data, unsigned long len); /* int MD2_Update(MD2_CTX *c, const unsigned char *data, unsigned long len); */ int MD2_Final(unsigned char *md, MD2_CTX *c); unsigned char *MD2(const unsigned char *d, unsigned long n, unsigned char *md); #endif ``` - md2.c ``` #include <stdio.h> #include <string.h> #include "utils.h" #include "md2.h" //#define DEBUG #ifdef DEBUG #define DBG(...) printf(__VA_ARGS__) #define DUMP_BLOCK_DATA 1 #define DUMP_BLOCK_CHECKSUM 1 #define DUMP_BLOCK_HASH 1 #define DUMP_ROUND_DATA 1 #else #define DBG(...) #define DUMP_BLOCK_DATA 0 #define DUMP_BLOCK_CHECKSUM 0 #define DUMP_BLOCK_HASH 0 #define DUMP_ROUND_DATA 0 #endif #define HASH_BLOCK_SIZE 16 #define HASH_DIGEST_SIZE 16 #define HASH_ROUND_NUM 18 /* 只有MD2才会计算一个block大小的CheckSum数据 */ #define MD2_CHECKSUM_SIZE HASH_BLOCK_SIZE /* * 参考: * md2中用于随机置换的S盒是如何生成的？ * https://blog.csdn.net/guyongqiangx/article/details/117856118 */ static const uint8_t S[256] = { 0x29, 0x2E, 0x43, 0xC9, 0xA2, 0xD8, 0x7C, 0x01, 0x3D, 0x36, 0x54, 0xA1, 0xEC, 0xF0, 0x06, 0x13, 0x62, 0xA7, 0x05, 0xF3, 0xC0, 0xC7, 0x73, 0x8C, 0x98, 0x93, 0x2B, 0xD9, 0xBC, 0x4C, 0x82, 0xCA, 0x1E, 0x9B, 0x57, 0x3C, 0xFD, 0xD4, 0xE0, 0x16, 0x67, 0x42, 0x6F, 0x18, 0x8A, 0x17, 0xE5, 0x12, 0xBE, 0x4E, 0xC4, 0xD6, 0xDA, 0x9E, 0xDE, 0x49, 0xA0, 0xFB, 0xF5, 0x8E, 0xBB, 0x2F, 0xEE, 0x7A, 0xA9, 0x68, 0x79, 0x91, 0x15, 0xB2, 0x07, 0x3F, 0x94, 0xC2, 0x10, 0x89, 0x0B, 0x22, 0x5F, 0x21, 0x80, 0x7F, 0x5D, 0x9A, 0x5A, 0x90, 0x32, 0x27, 0x35, 0x3E, 0xCC, 0xE7, 0xBF, 0xF7, 0x97, 0x03, 0xFF, 0x19, 0x30, 0xB3, 0x48, 0xA5, 0xB5, 0xD1, 0xD7, 0x5E, 0x92, 0x2A, 0xAC, 0x56, 0xAA, 0xC6, 0x4F, 0xB8, 0x38, 0xD2, 0x96, 0xA4, 0x7D, 0xB6, 0x76, 0xFC, 0x6B, 0xE2, 0x9C, 0x74, 0x04, 0xF1, 0x45, 0x9D, 0x70, 0x59, 0x64, 0x71, 0x87, 0x20, 0x86, 0x5B, 0xCF, 0x65, 0xE6, 0x2D, 0xA8, 0x02, 0x1B, 0x60, 0x25, 0xAD, 0xAE, 0xB0, 0xB9, 0xF6, 0x1C, 0x46, 0x61, 0x69, 0x34, 0x40, 0x7E, 0x0F, 0x55, 0x47, 0xA3, 0x23, 0xDD, 0x51, 0xAF, 0x3A, 0xC3, 0x5C, 0xF9, 0xCE, 0xBA, 0xC5, 0xEA, 0x26, 0x2C, 0x53, 0x0D, 0x6E, 0x85, 0x28, 0x84, 0x09, 0xD3, 0xDF, 0xCD, 0xF4, 0x41, 0x81, 0x4D, 0x52, 0x6A, 0xDC, 0x37, 0xC8, 0x6