一文读懂GCM(Galois/计数器模式)
![3SU52(GL6E(`]Y_]4J)HMUM.jpg](https://ucc.alicdn.com/pic/developer-ecology/5e62d3647a164d3abf9bd3238b9bbd18.jpg?x-oss-process=image/resize,w_1400/format,webp "3SU52(GL6E(`]Y_]4J)HMUM.jpg")
一文读懂GCM
GCM模式
GCM(Galois计数器模式)同样的也是NIST提出来的，这个模式基于并行化设计，下面来一起看一下这个模式具体是如何工作的吧。
预备知识
不同于CCM模式，这个模式没有用到之前学过的CTR或者MAC, 而是采用了两个新的函数：
- 「GHASH」: 带密钥的哈希函数
- 「GCTR」: 这个实际上也是每次加一的一个计数器，不过这个计数器有一点点小特别，具体哪里特别将在后文进行介绍
GHASH
先来看一下GHASH函数，这个函数以密钥和消息X作为输入，输出是一个128位的MAC值。
GHASH
这里的乘法和加法是基于这一个有限域之下的, 有关有限域的具体知识, 同样的不在这里赘述了, 具体过程如下:
- 初始化
- 对于每一个分组, 都有, 其中H是密钥
- 最后一个分组, 即为最终的MAC值
对于上面的乘法运算，参考文献给出了具体的算法。
GCTR
接下来，来看一下GCTR的具体过程，对于GCTR来说，和普通的CTR有一点点小差别，主要差别在计数器上，这个是最后32位做mod 的加法运算，前面的不变。
GCTR
具体规则如下：
- 如果X是空串，直接返回
- 对消息X进行分组，按照16个字节也就是128bit进行分组
- 初始化
- 对于i = 2 到 n, = , 这里的是最右侧的32位+1并且mod
- 如果消息长度恰好是分组的整数倍，则计算
- 否则将截取到最后剩余的消息长度
- C = || ... ||
GCM过程
到这里，整个GCM的基本算法就介绍完了，下面来看一下整个GCM的过程吧。
GCM过程
- H = E(K, ), 这里的H也就是GHASH的密钥
- 对于有如下两种情况
- = 96, 注意这里是比特长度，如果是字节，那么这里是12， = IV || || 1
- , 令 s = , 并且
- 令C = GCTR(K, (), P)
- 令 , 并令
- 新增一个有关无需加密数据和其长度的分组S, 并计算GHASH
- 计算T = , 我代码实现这里同样偷懒了一下，长度我直接输出了整个分组，注意一下
代码实现
老规矩，接着用rust来写啦，嘻嘻
use aes::AES; pub struct GCM { aes: AES, } // R = 11100001 || 0(120) const R: u128 = 0b11100001 << 120; fn gmul_128(x: u128, y: u128) -> u128 { let mut z = 0u128; let mut v = y; for i in (0..128).rev() { let xi = (x >> i) & 1; if xi != 0 { z ^= v; } v = match v & 1 == 0 { true => { v >> 1 } false => { (v >> 1) ^ R } }; } z } fn u8to128(bytes: &[u8]) -> u128 { let result = bytes.iter().rev().enumerate().fold(0, |acc, (i, &byte)| { acc | (byte as u128) << (i * 8) }); result } fn msb_s(s: usize, bytes: [u8; 16]) -> Vec<u8> { let mut result = vec![]; let n = s / 8; let remain = s % 8; for i in 0..n { result.push(bytes[i]); } if remain > 0 { result.push(bytes[n] >> (8 - remain)); } result } // incs(X)=MSBlen(X)-s(X) || [int(LSBs(X))+1 mod 2^s]s fn inc_32(bits: u128) -> u128 { let msb = bits >> 32; let mut lsb = (bits & 0xffffffff) as u32; lsb = lsb.wrapping_add(1); msb << 32 | lsb as u128 } fn ghash(key: u128, messages: &[u128]) -> u128 { let mut y = 0u128; for i in 0..messages.len() { let yi = gmul_128(y ^ messages[i], key); y = yi; } y } impl GCM { pub fn new(key: [u8; 16]) -> Self { let aes = AES::new(&key); Self { aes, } } fn ghash_key(&mut self) -> u128 { u8to128(&self.aes.encrypt_block(&[0u8; 16])) } pub fn gctr(&mut self, iv: u128, message: &[u8]) -> Vec<u8> { // 如果X是空串, 则直接返回 if message.len() == 0 { return vec![]; } let mut output = vec![]; let mut cb = iv; for chunk in message.chunks(16) { if chunk.len() < 16 { let msb = msb_s(chunk.len() * 8, self.aes.encrypt_block(&cb.to_be_bytes().try_into().expect(""))); let y = u8to128(chunk) ^ u8to128(&msb); output.extend_from_slice(&y.to_be_bytes()[16 - chunk.len()..16]) } else { let y = u8to128(chunk) ^ u8to128(&self.aes.encrypt_block(&cb.to_be_bytes().try_into().expect(""))); output.extend_from_slice(&y.to_be_bytes()); } // counter + 1 cb = inc_32(cb); } output } pub fn ae(&mut self, iv_bytes: &[u8], adata: &[u8], message: &[u8]) -> (Vec<u8>, Vec<u8>) { let ghash_key = self.ghash_key(); let mut iv_padding = vec![]; let iv = u8to128(iv_bytes); let j0 = match iv_bytes.len() == 12 { true => { iv << 32 | 0x00000001 } false => { // s = 128[len(iv) / 128] - len(iv) let s = 128 * (((iv_bytes.len() * 8) + 128 - 1) / 128) - (iv_bytes.len() * 8); iv_padding.push(iv << s); iv_padding.push((iv_bytes.len() * 8) as u128); ghash(ghash_key, &iv_padding) } }; let message_len = message.len() * 8; let adata_len = adata.len() * 8; let u = 128 * ((message_len + 128 - 1) / 128) - message_len; let v = 128 * ((adata_len + 128 - 1) / 128) - adata_len; println!("u, v: {}, {}", u, v); println!("j0 = {:02x?}", j0); let enc = self.gctr(inc_32(j0), &message); let mut bit_string = Vec::<u8>::new(); bit_string.extend_from_slice(adata); bit_string.extend_from_slice(&vec![0x00; v / 8]); // 这里认证的是密文 bit_string.extend_from_slice(&enc); bit_string.extend_from_slice(&vec![0x00; u / 8]); bit_string.extend_from_slice(&(adata_len as u64).to_be_bytes()); bit_string.extend_from_slice(&(message_len as u64).to_be_bytes()); println!("len = {}, bit_string[u8] = {:02x?}", bit_string.len(), bit_string); let bit_string: Vec<u128> = bit_string.chunks(16).map(|it| u8to128(it)).collect(); println!("bit_string[u128] = {:02x?}", bit_string); let s = ghash(ghash_key, &bit_string).to_be_bytes(); println!("{:02x?}", s); let tag = self.gctr(j0, &s); // println!("tag = {:02x?}", tag); // println!("enc = {:02x?}", enc); (tag, enc) } } #[cfg(test)] mod tests { use crate::{GCM, u8to128}; use hex_literal::hex; // example from https://csrc.nist.rip/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf #[test] fn test_u8to128() { let bytes = [ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 ]; assert_eq!(u8to128(&bytes), 1); } #[test] fn test_gcm_ae() { let key: [u8; 16] = hex!("00000000000000000000000000000000"); let p: Vec<u8> = vec![]; let iv = hex!("000000000000000000000000"); let mut gcm = GCM::new(key); let h = gcm.ghash_key(); assert_eq!(h, u8to128(&hex!("66e94bd4ef8a2c3b884cfa59ca342b2e"))); gcm.ae(&iv, &[], &p); } #[test] fn test_gcm_ae_test_case_two() { let key: [u8; 16] = hex!("00000000000000000000000000000000"); let p = hex!("00000000000000000000000000000000"); let iv = hex!("000000000000000000000000"); let mut gcm = GCM::new(key); let h = gcm.ghash_key(); assert_eq!(h, u8to128(&hex!("66e94bd4ef8a2c3b884cfa59ca342b2e"))); let (tag, enc) = gcm.ae(&iv, &[], &p); println!("tag = {:02x?}", tag); println!("enc = {:02x?}", enc); } #[test] fn test_gcm_ae_test_case_three() { let key: [u8; 16] = hex!("feffe9928665731c6d6a8f9467308308"); let p = hex!("d9313225f88406e5a55909c5aff5269a 86a7a9531534f7da2e4c303d8a318a72 1c3c0c95956809532fcf0e2449a6b525 b16aedf5aa0de657ba637b391aafd255"); let iv = hex!("cafebabefacedbaddecaf888"); let mut gcm = GCM::new(key); let (tag, enc) = gcm.ae(&iv, &[], &p); println!("tag = {:02x?}", tag); println!("enc = {:02x?}", enc); } #[test] fn test_gcm_ae_test_case_four() { let key: [u8; 16] = hex!("feffe9928665731c6d6a8f9467308308"); let p = hex!("d9313225f88406e5a55909c5aff5269a 86a7a9531534f7da2e4c303d8a318a72 1c3c0c95956809532fcf0e2449a6b525 b16aedf5aa0de657ba637b39"); let iv = hex!("cafebabefacedbaddecaf888"); let adata = hex!("feedfacedeadbeeffeedfacedeadbeefabaddad2"); let mut gcm = GCM::new(key); let (tag, enc) = gcm.ae(&iv, &adata, &p); println!("tag = {:02x?}", tag); println!("enc = {:02x?}", enc); } }
