FIPS203 后量子安全ML-KEM(标准简读)

FIPS 203是美国国家标准与技术研究院（NIST）发布的关于模块格基密钥封装机制（ML-KEM）的标准，旨在提供一种能抵御量子计算机攻击的密钥建立方案。以下是对该文档的详细总结：

标准概述

• 目的与范围：规定ML-KEM算法及参数集，用于在公共信道上建立共享密钥，提供了不同安全强度与性能权衡的参数集，包括ML-KEM - 512、ML-KEM - 768和ML-KEM - 1024。
• 背景：因量子计算机发展对现有公钥密码系统构成威胁，NIST开展后量子密码学标准化工作，ML-KEM基于CRYSTALS - KYBER算法，是被选中的标准化算法之一。

术语、缩写与符号

• 术语定义：详细解释了如批准、（KEM）密文、密码模块、解封装、封装等相关术语。
• 缩写：列举了AES、CBD、FIPS、KEM、LWE、MLWE、NIST等缩写的含义。
• 数学符号：定义了如n、q、ζ、B、Q、Z、Zm、Zq^n、Rq、Tq等符号的意义。

ML - KEM方案概述

• 密钥封装机制（KEM）：由KeyGen、Encaps、Decaps三个算法和参数集组成，用于双方建立共享密钥，ML-KEM的安全性基于Module Learning with Errors (MLWE)问题。
• ML - KEM方案
  • 计算假设：安全性基于MLWE问题，是Learning With Errors (LWE)问题的推广，与模块格中的计算问题相关。
  • 方案构造：先从MLWE问题构建公钥加密（PKE）方案，再用Fujisaki - Okamoto (FO)变换转换为KEM，使用Number - Theoretic Transform (NTT)提高多项式乘法效率。
  • 参数集与算法：包括ML-KEMKeyGen、ML-KEMEncaps、ML-KEMDecaps三个算法，有ML-KEM - 512、ML-KEM - 768、ML-KEM - 1024三个参数集，不同参数集影响密钥和密文长度及安全性。
  • 解封装失败：在正常情况下，解封装失败概率极低，如ML-KEM - 512的失败率为2^-138.8等。

ML - KEM实现要求

• K - PKE仅为组件：K - PKE不能单独使用，只能作为ML - KEM算法的子例程。
• 内部函数访问控制：ML - KEM内部函数接口仅用于测试，密钥生成和封装所需随机值由密码模块生成。
• 等效实现：允许使用数学等效步骤替换标准算法。
• 共享密钥使用：成功生成的共享密钥为256位，可直接用于对称加密或按规定方式派生密钥。
• 随机数生成：ML - KEMKeyGen和ML - KEMEncaps需使用批准的随机位生成器（RBG）生成随机数，不同参数集对RBG安全强度有不同要求。
• 输入检查：ML - KEMEncaps和ML - KEMDecaps需进行输入检查，确保输入合法。
• 中间值销毁：计算过程中的中间数据应及时销毁，部分数据可按规定保留。
• 禁止浮点运算：实现中不能使用浮点运算，以避免舍入误差导致错误结果。

辅助算法

• 密码函数：使用SHA3 - 256、SHA3 - 512、SHAKE128、SHAKE256等哈希函数和可扩展输出函数（XOF），通过包装函数定义来实例化PRF、哈希函数和XOF等，避免字节数组与位长度混淆。
• 通用算法
  • 转换与压缩算法：包括BitsToBytes、BytesToBits用于位数组和字节数组转换，Compress和Decompress用于整数压缩和解压缩，ByteEncode和ByteDecode用于整数与字节转换。
  • 采样算法：SampleNTT用于从均匀随机字节流生成NTT表示的多项式样本，SamplePolyCBD用于从特定分布采样多项式系数。
• 数论变换（NTT）：NTT是ML - KEM提高环Rq上乘法效率的重要部分，将多项式在Rq和Tq环之间进行转换，Tq环上乘法效率更高，算法9和10分别用于计算NTT和逆NTT，算法11用于计算Tq环上的乘法。

K - PKE组件方案

• K - PKE概述：由K - PKEKeyGen（密钥生成）、K - PKEEncrypt（加密）、K - PKEDecrypt（解密）三个算法组成，不能单独使用，作为ML - KEM算法子例程，其参数集与ML - KEM相关联。
• K - PKE密钥生成（K - PKEKeyGen）：输入随机数，生成加密密钥（可公开）和解密密钥（需保密），涉及矩阵A、向量s和噪声e的生成与计算。
• K - PKE加密（K - PKEEncrypt）：使用加密密钥、明文和随机数生成密文，包括提取向量、重新生成矩阵、采样噪声、计算新的噪声方程、编码消息等步骤。
• K - PKE解密（K - PKEDecrypt）：使用解密密钥解密密文得到明文，通过恢复系数、计算真实常数项、解码消息等操作完成。

ML - KEM主算法

• 内部密钥生成（ML - KEMKeyGen_internal）：输入两个随机种子，生成封装密钥（与K - PKE加密密钥相同）和解封装密钥（包含K - PKE解密密钥、封装密钥哈希值和随机值）。
• 内部封装（ML - KEMEncaps_internal）：输入封装密钥和随机字节数组，输出密文和共享密钥，通过K - PKE加密随机值得到密文，并从随机值和封装密钥派生共享密钥。
• 内部解封装（ML - KEMDecaps_internal）：输入解封装密钥和密文，输出共享密钥，解析解封装密钥，解密密文得到明文，重新加密明文并计算候选共享密钥，根据密文匹配情况确定最终共享密钥。
• ML - KEM密钥生成（ML - KEMKeyGen）：生成封装密钥和解封装密钥，种子可存储用于重新生成密钥，密钥对可进行检查但不保证生成正确。
• ML - KEM封装（ML - KEMEncaps）：输入封装密钥，生成密文和共享密钥，需进行封装密钥检查，包括类型检查和模数检查。
• ML - KEM解封装（ML - KEMDecaps）：输入解封装密钥和密文，输出共享密钥，需进行输入检查，包括密文类型检查、解封装密钥类型检查和哈希检查。

参数集

• 参数集内容：ML - KEM有三个参数集，每个参数集包含k、η1、η2、du、dv五个参数及n = 256和q = 3329两个常数，不同参数影响算法中矩阵、向量维度和分布等，如k决定矩阵A维度。
• 安全强度与性能：不同参数集对应不同安全强度，如ML - KEM - 512安全类别为1，ML - KEM - 768为3，ML - KEM - 1024为5，安全强度通过与特定块密码或哈希函数比较衡量，选择参数集时需权衡安全与性能，NIST推荐默认使用ML - KEM - 768。

代码参考

ML-KEM: https://github.com/pq-crystals/kyber