【密码学】一文读懂SM3

2022-06-12 2982

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： SM3是中华人民共和国政府采用的一种密码散列函数标准，前身为SCH4杂凑算法，由国家密码管理局于2010年12月17日发布，相关标准为"GM/T 0004-2012 《SM3密码杂凑算法》"。

一文读懂SM3

({02X~QR~71OPWM76MZDSYX.jpg 一文读懂SM3

算法简介

❝
SM3是中华人民共和国政府采用的一种密码散列函数标准，前身为SCH4杂凑算法，由国家密码管理局于2010年12月17日发布，相关标准为"GM/T 0004-2012 《SM3密码杂凑算法》"。2016年，成为中国国家密码标准(GB/T 32905-2016)。【维基百科】
❞

这个算法是公开的算法，其他公开的算法还有SM2和SM4, 再给自己挖个坑吧，有空的时候顺道研究研究剩下的两个。

算法描述

这个算法的结构和MD系列以及SHA1/SHA2相似。

消息填充

这一步和SHA256的填充方案一致，规则如下:

步骤一: 数据填充(Append Padding Bits)

SM3是按照分块进行处理的，分块长度为512bit, 大多数情况下，数据的长度不会恰好满足是512的整数倍，因此需要进行「padding」到给定的长度。

「填充规则」: 原始明文消息的b位之后补100..., 直到满足b + paddingLength % 512 = 448, 那如果b % 512在[448, 512(0)]之间呢，则在增加一个分块，按照前面的规则填充即可。

步骤二: 长度填充

之前说了，需要满足b + paddingLength % 512 = 448，那么对于最后一个分块，就还剩512 - 448 = 64 bit 这剩下的64bit存放的是原始消息的长度，也就是b。「SM3」最多可以处理明文长度小于等于2^64 bit的数据。

经过上面两个步骤的处理，最终得到的处理后的数据如下图所示:

4PMZ`W$T1RN%@1KD~~{X)PB.png

SM3-Padding

消息扩展

这里对于消息的处理与SHA系列有一些差别，这里并没有对原始的消息分组直接参与运算，而是通过某种规则，将消息扩展成为以及, 规则如下:

对于~, 内容为原始的消息字
而对于~, 通过如下的公式进行计算

W_{j} = P_{1}(W_{j - 16} \oplus W_{j-9} \oplus (W_{j-3} <<< 15)) \oplus (W_{j-13} <<< 7) \oplus W_{j-6}

对于~, 按照如下方式进行处理

W_{j}^{'} = W_j \oplus W_{j+4}

BR33UVZ1~2BCG{4QOOB8~SN.png SM3消息扩展

上图简单描述了一下消息扩展的过程，有部分细节并没有完全体现在图中，注意一下(全画出来图有点乱，所以省略了一下部分细节)。

迭代压缩

这块结构和SHA系列算法也比较相似，由初始化向量然后对于每一个扩展后的消息进行处理，直到处理完最后一个分块。

){]OBSBZ@})[VC]GJR1M64S.png 压缩迭代过程

整个算法的核心，也就是压缩函数，具体流程如下图所示:

}Q0H0}TEG[X9WLEAKK%NACI.png

压缩函数

对于详细压缩函数的计算过程，这里我就不贴出来了，可以参考本文给出的代码，也可以参考文末的资料。

输出

到此，最终迭代完成的变量，按照大端输出即为最终的杂凑值。

代码实现

rust作为老演员了，依然用它写吧, 感觉这些代码实现起来大同小异，语言特性我也没用多少，哈哈哈。

pub struct SM3 {}
fn p_0(x: u32) -> u32 {
    x ^ x.rotate_left(9) ^ x.rotate_left(17)
}
fn p_1(x: u32) -> u32 {
    x ^ x.rotate_left(15) ^ x.rotate_left(23)
}
fn ff(j: u32, x: u32, y: u32, z: u32) -> u32 {
    match j {
        n if n < 16 => x ^ y ^ z,
        n if 16 <= n && n < 64 => (x & y) | (x & z) | (y & z),
        _ => 0,
    }
}
fn gg(j: u32, x: u32, y: u32, z: u32) -> u32 {
    match j {
        n if n < 16 => x ^ y ^ z,
        n if n >= 16 => (x & y) | ((!x) & z),
        _ => 0,
    }
}
fn t(j: u32) -> u32 {
    return if j < 16 {
        0x79cc4519
    } else {
        0x7a879d8a
    }
}
impl SM3 {
    fn padding(message: &[u8]) -> Vec<u8> {
        let message_length = message.len() as u64 * 8;
        let mut result = message.to_owned();
        // padding 1
        result.push(0x80);
        // padding 0
        while ((result.len() * 8) + 64) % 512 != 0 {
            result.push(0b00000000);
        }
        for b in 0..8 {
            result.push((message_length >> ((7 - b) * 8)) as u8);
        }
        return result;
    }
    pub fn hash(message: &[u8]) -> String {
        let padding_message = SM3::padding(message);
        let mut iv: [u32; 8] = [
            0x7380166f, 0x4914b2b9, 0x172442d7, 0xda8a0600,
            0xa96f30bc, 0x163138aa, 0xe38dee4d, 0xb0fb0e4e,
        ];
        let mut v: [u32; 8] = [0; 8];
        let mut w = [0u32; 68];
        let mut w_p = [0u32; 64];
        for chunk in padding_message.chunks(64) {
            let m: Vec<u32> = chunk.chunks(4).map(|i| {
                ((i[0] as u32) << 24) | ((i[1] as u32) << 16) | ((i[2] as u32) << 8) | ((i[3] as u32) << 0)
            }).collect();
            for j in 0..16 {
                w[j] = m[j];
            }
            for j in 16..68 {
                w[j] = p_1(w[j - 16] ^ w[j - 9] ^ w[j - 3].rotate_left(15))
                    ^ w[j - 13].rotate_left(7)
                    ^ w[j - 6];
            }
            for j in 0..64 {
                w_p[j] = w[j] ^ w[j + 4];
            }
            v = iv;
            // ABCDEFGH
            // 01234567
            for j in 0..64 {
                // SS1 ← ((A ≪ 12) + E + (Tj ≪ j)) ≪ 7
                let mut ss1 = v[0]
                    .rotate_left(12)
                    .wrapping_add(v[4])
                    .wrapping_add(t(j).rotate_left(j as u32))
                    .rotate_left(7);
                let mut ss2 = ss1 ^ v[0].rotate_left(12);
                let mut tt1 = ff(j, v[0], v[1], v[2]).
                    wrapping_add(v[3])
                    .wrapping_add(ss2)
                    .wrapping_add(w_p[j as usize]);
                let mut tt2 = gg(j, v[4], v[5], v[6]).
                    wrapping_add(v[7])
                    .wrapping_add(ss1)
                    .wrapping_add(w[j as usize]);
                v[3] = v[2];
                v[2] = v[1].rotate_left(9);
                v[1] = v[0];
                v[0] = tt1;
                v[7] = v[6];
                v[6] = v[5].rotate_left(19);
                v[5] = v[4];
                v[4] = p_0(tt2);
            }
            iv[0] ^= v[0];
            iv[1] ^= v[1];
            iv[2] ^= v[2];
            iv[3] ^= v[3];
            iv[4] ^= v[4];
            iv[5] ^= v[5];
            iv[6] ^= v[6];
            iv[7] ^= v[7];
        }
        return String::from(format!(
            "{:08x}{:08x}{:08x}{:08x}{:08x}{:08x}{:08x}{:08x}",
            iv[0], iv[1], iv[2], iv[3], iv[4], iv[5], iv[6], iv[7]
        ));
    }
}
#[cfg(test)]
mod test {
    use crate::sm3::SM3;
    #[test]
    fn test() {
        println!("SM3([empty string]) = {}", SM3::hash("".as_bytes()));
        println!("SM3([The quick brown fox jumps over the lazy dog]) = {}", SM3::hash("The quick brown fox jumps over the lazy dog".as_bytes()));
    }
}