一文读懂SM3
一文读懂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的数据。
经过上面两个步骤的处理，最终得到的处理后的数据如下图所示:
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}
SM3消息扩展
上图简单描述了一下消息扩展的过程，有部分细节并没有完全体现在图中，注意一下(全画出来图有点乱，所以省略了一下部分细节)。
迭代压缩
这块结构和SHA系列算法也比较相似，由初始化向量然后对于每一个扩展后的消息进行处理，直到处理完最后一个分块。
![){]OBSBZ@})[VC]GJR1M64S.png](https://ucc.alicdn.com/pic/developer-ecology/1619826dddb742fcab09999ed571117b.png?x-oss-process=image/resize,w_1400/format,webp "){]OBSBZ@})[VC]GJR1M64S.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())); } }
