【密码学】一文读懂GCM(Golais计数器模式)

2022-06-12 1726

版权

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

简介： GCM(Galois计数器模式)同样的也是NIST提出来的，这个模式基于并行化设计，下面来一起看一下这个模式具体是如何工作的吧。

一文读懂`GCM`(Galois/计数器模式)

3SU52(GL6E(`]Y_]4J)HMUM.jpg 一文读懂GCM $5CMR{%FXF_LM{14E`0STGMJ.png$ GCM模式

GCM(Galois计数器模式)同样的也是NIST提出来的，这个模式基于并行化设计，下面来一起看一下这个模式具体是如何工作的吧。

预备知识

不同于CCM模式，这个模式没有用到之前学过的CTR或者MAC, 而是采用了两个新的函数：

「GHASH」: 带密钥的哈希函数
「GCTR」: 这个实际上也是每次加一的一个计数器，不过这个计数器有一点点小特别，具体哪里特别将在后文进行介绍

GHASH

先来看一下GHASH函数，这个函数以密钥和消息X作为输入，输出是一个128位的MAC值。

NRZ166~ACML[IOLTP~$~}GS.png

GHASH

这里的乘法和加法是基于这一个有限域之下的, 有关有限域的具体知识, 同样的不在这里赘述了, 具体过程如下:

初始化
对于每一个分组, 都有, 其中H是密钥
最后一个分组, 即为最终的MAC值

对于上面的乘法运算，参考文献给出了具体的算法。

GCTR

接下来，来看一下GCTR的具体过程，对于GCTR来说，和普通的CTR有一点点小差别，主要差别在计数器上，这个是最后32位做mod 的加法运算，前面的不变。

PZ90H%F(S3GJD2ICHRVF9ED.png GCTR

具体规则如下：

如果X是空串，直接返回
对消息X进行分组，按照16个字节也就是128bit进行分组
初始化
对于i = 2 到 n, = , 这里的是最右侧的32位+1并且mod
如果消息长度恰好是分组的整数倍，则计算
否则将截取到最后剩余的消息长度
C = || ... ||

GCM过程

到这里，整个GCM的基本算法就介绍完了，下面来看一下整个GCM的过程吧。

SZ}%ON9XYUWIPL`S%X3{7`G.png 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);
    }
}

【密码学】一文读懂GCM(Golais计数器模式)

一文读懂`GCM`(Galois/计数器模式)

预备知识

GHASH

GCTR

GCM过程

代码实现

热门文章

最新文章

相关电子书

【密码学】一文读懂GCM(Golais计数器模式)

一文读懂GCM(Galois/计数器模式)

预备知识

GHASH

GCTR

GCM过程

代码实现

热门文章

最新文章

相关电子书

一文读懂`GCM`(Galois/计数器模式)