AI 助理
备案控制台
开发者社区 安全 文章 正文

【密码学】一文读懂MD2

2022-06-12 1459
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： MD2是Ranald Rivest在1989年提出的哈希函数，本文主要介绍一下MD2算法的基本原理，尽管现在MD2已经并不安全，作为一个结构比较简单的哈希函数，学习一下还是十分有必要的。

一文读懂MD2

T9Q6`5W9D5[M3R](HEH9~T3.jpg

一文读懂MD2

❝

MD2是Ranald Rivest在1989年提出的哈希函数，本文主要介绍一下MD2算法的基本原理，尽管现在MD2已经并不安全，作为一个结构比较简单的哈希函数，学习一下还是十分有必要的。

❞

image.gif3W)}M%N@YW7F`(434ZD9(5X.png

MD2 计算整体流程


算法流程

下面本文将简单描述一下MD2算法的基本流程

字节填充(Append Padding Bytes)

这个字节填充的方案和之前写过的MD5, SHA1, 不太一样，有兴趣的可以参考一下我写过的有关MD5或者SHA1的相关介绍。

MD4按照如下的规则填充，假设数据长度为m, 则需要填充16 - (m mod 16)个字节的数据，填充内容为16 - (m mod 16), 下图是当填充一整个分组的时候的示意图:

1ZEWWD2Q]8N@`_2V_}DB%BU.png

image.gifMD2-Padding

添加校验和(Append Checksum)

校验和按照如下的方式进行计算:

For i = 0 to 15 do:
    Set C[i] to 0.
end /* of loop on i */
Set L to 0.
/* 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 L to C[j].
    end /* of loop on j */
end /* of loop on i */

(53B_NQRRKW]`_)SOR4(6E7.pngMD2校验和

初始化MD Buffer(Initialize MD Buffer)

这个初始化比较简单，直接初始化48字节的0数组即可。

处理消息块(Process Message in 16-Byte Blocks)

这同样是算法的核心过程，这里直接贴一下RFC当中的算法了:

For i = 0 to N'/16-1 do
    /* Copy block i into X. */
    For j = 0 to 15 do
        Set X[16+j] to M[i*16+j].
        Set X[32+j] to (X[16+j] xor X[j]).
    end /* of loop on j */
    Set t to 0.
    /* Do 18 rounds. */
    For j = 0 to 17 do
        /* Round j. */
        For k = 0 to 47 do
           Set t and X[k] to (X[k] xor S[t]).
        end /* of loop on k */
        Set t to (t+j) modulo 256.
    end /* of loop on j */
end /* of loop on i */

这个过程和计算校验和有点相似，如下图所示:

_11MN4TNTT8ILD7WO7TMUJL.png

image.gif处理过程

输出

这一步比较简单，直接输出缓冲区(MD Buffer)的内容即为最终的结果。


算法实现

use std::iter::repeat;
static S_BOX: [u8; 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, 0x6C, 0xC1, 0xAB, 0xFA, 0x24, 0xE1, 0x7B, 0x08, 0x0C, 0xBD, 0xB1, 0x4A,
    0x78, 0x88, 0x95, 0x8B, 0xE3, 0x63, 0xE8, 0x6D, 0xE9, 0xCB, 0xD5, 0xFE, 0x3B, 0x00, 0x1D, 0x39,
    0xF2, 0xEF, 0xB7, 0x0E, 0x66, 0x58, 0xD0, 0xE4, 0xA6, 0x77, 0x72, 0xF8, 0xEB, 0x75, 0x4B, 0x0A,
    0x31, 0x44, 0x50, 0xB4, 0x8F, 0xED, 0x1F, 0x1A, 0xDB, 0x99, 0x8D, 0x33, 0x9F, 0x11, 0x83, 0x14,
];
pub struct MD2 {}
impl MD2 {
    fn padding(message: &[u8]) -> Vec<u8> {
        let mut result = message.to_vec();
        let padding_length = 16 - message.len() % 16;
        result.extend(repeat(padding_length as u8).take(padding_length));
        return result;
    }
    fn checksum(message: &[u8]) -> [u8; 16] {
        let mut checksum = [0u8; 16];
        let mut last = 0u8;
        for chuck in message.chunks(16) {
            for (m, c) in chuck.iter().zip(checksum.iter_mut()) {
                *c ^= S_BOX[(*m ^ last) as usize];
                last = *c;
            }
        }
        return checksum;
    }
    fn compress(state: &[u8], message: &[u8]) -> [u8; 16] {
        let mut x = [0u8; 48];
        for i in 0..16 {
            x[i] = state[i];
            x[i + 16] = message[i]
        }
        for (i, byte) in message.iter().enumerate() {
            x[32 + i] = *byte ^ x[i];
        }
        let mut t = 0u8;
        for i in 0..18 {
            for j in 0..x.len() {
                x[j] ^= S_BOX[t as usize];
                t = x[j];
            }
            t = t.wrapping_add(i);
        }
        let mut result = [0u8; 16];
        for i in 0..16 {
            result[i] = x[i];
        }
        return result;
    }
    fn hash(message: &[u8]) -> String {
        let mut message = MD2::padding(message);
        let csum = MD2::checksum(&message);
        message.extend(csum.to_vec());
        let hash = message.chunks(16).fold([0u8; 16], |state, chunk| MD2::compress(&state, chunk));
        return hash.iter().fold(String::new(), |a, &b| format!("{}{:02x}", a, b));
    }
}
#[cfg(test)]
mod test {
    use crate::md2::MD2;
    #[test]
    fn test() {
        println!("md2([empty string]) = {}", MD2::hash("".as_bytes()));
        println!("md2([The quick brown fox jumps over the lazy dog]) = {}", MD2::hash("The quick brown fox jumps over the lazy dog".as_bytes()));
    }
}

文章标签：
安全
算法
1729692684231857
目录
相关文章
机器学习Zero
|
6月前
|
机器学习/深度学习 算法 安全
密码学系列之五：MD5、SHA1——一文搞懂哈希函数
密码学系列之五：MD5、SHA1——一文搞懂哈希函数
机器学习Zero
3648 0
1729692684231857
|
Rust 算法 安全
【密码学】一文读懂HMAC
本文将来聊一聊基于哈希函数的消息认证码，在此之前，先来科普一下什么是 「消息认证码」 (MAC), 先来看一个简单的栗子
1729692684231857
1688 0
【密码学】一文读懂HMAC
1729692684231857
|
Rust 算法 数据安全/隐私保护
【密码学】一文读懂XTEA加密
本篇文章，我们来看一下上一次讲过的TEA加密算法的一个升级版XTEA, 相比于TEA, XTEA的安全性显然是更高的，其中的过程要比TEA稍微复杂一点点。
1729692684231857
1274 0
【密码学】一文读懂XTEA加密
1729692684231857
|
Rust 算法 Go
【密码学】一文读懂FNV Hash
FNV哈希全名为Fowler-Noll-Vo算法，是以三位发明人Glenn Fowler，Landon Curt Noll，Phong Vo的名字来命名的，最早在1991年提出。它可以快速hash大量的数据并保持较小的冲突概率，适合hash一些相近的字符串比如IP地址、URL、文件名等等。目前FNV算法有三个版本，分别是: FNV-0(已废弃)、FNV-1以及FNV-1a。这三个算法的结构非常相似，因此呢，在这里就一块说了。
1729692684231857
2750 0
【密码学】一文读懂FNV Hash
1729692684231857
|
Web App开发 Rust 算法
【密码学】一文读懂ChaCha20
好久没写新的加密算法的原理了, 这次所选取的加密算法结构比较简单, 一起来看一下吧。
1729692684231857
7686 0
【密码学】一文读懂ChaCha20
1729692684231857
|
算法 安全 Go
【密码学】一文读懂HKDF
我这又来水一篇文章，来聊一下HKDF(基于HMAC的密钥导出函数)。密钥派生函数是密钥管理的组成部分，他的目标是通过一些初始的数据派生出来密码学安全的随机密钥。
1729692684231857
3082 1
【密码学】一文读懂HKDF
游客zn7mvnkypuy76
|
5月前
|
算法 安全 Java
技术笔记：MD5加密算法详解
技术笔记：MD5加密算法详解
游客zn7mvnkypuy76
94 0
1729692684231857
|
Rust 算法 数据安全/隐私保护
【密码学】一文读懂SM3
SM3是中华人民共和国政府采用的一种密码散列函数标准，前身为SCH4杂凑算法，由国家密码管理局于2010年12月17日发布，相关标准为&quot;GM/T 0004-2012 《SM3密码杂凑算法》&quot;。
1729692684231857
3417 0
【密码学】一文读懂SM3
1729692684231857
|
算法 数据安全/隐私保护
【密码学】一文读懂SHA-1
SHA-1（Secure Hash Algorithm 1）是一种密码散列函数，美国国家安全局设计，并由美国国家标准技术研究所（NIST）发布为联邦资料处理标准（FIPS）。SHA-1可以生成一个被称为消息摘要的160位（20字节）散列值，散列值通常的呈现形式为40个十六进制数。
1729692684231857
1212 1
【密码学】一文读懂SHA-1
1729692684231857
|
算法 搜索推荐 安全
【密码学】一文读懂CCM
本文简单介绍了CCM模式下的认证和加密机制，实际上这个是AES-CTR模式和CMAC的一个组合，如果理解了前面这两个，本文应该还是比较好理解的。
1729692684231857
3396 0
【密码学】一文读懂CCM