查看“︁伽罗瓦/计数器模式”︁的源代码

在[[密码学]]中，'''伽罗瓦/计数器模式（GCM）'''<ref><nowiki>RFC 5288</nowiki> ''AES Galois Counter Mode (GCM) Cipher Suites for TLS''</ref>是一种[[对称加密|对称]][[分组密码|分组加密算法]]的[[分组密码工作模式|工作模式]]，因其良好的性能而被广泛采用。最快速的GCM通信信道可以用便宜的硬件来实现<ref>{{cite book|last1=Lemsitzer|first1=S.|last2=Wolkerstorfer|first2=J.|last3=Felber|first3=N.|last4=Braendli|first4=M.|title=Cryptographic Hardware and Embedded Systems - CHES 2007|chapter=Multi-gigabit GCM-AES Architecture Optimized for FPGAs|editor-last=Paillier|editor-first=P.|editor2-last=Verbauwhede|editor2-first=I.|publisher=Springer|year=2007|isbn=978-3-540-74734-5|pages=227–238|doi=10.1007/978-3-540-74735-2_16|series=Lecture Notes in Computer Science|volume=4727}}</ref>。

GCM算法提供数据真实性（与完整性）和机密性的验证，基于关联数据[[认证加密|认证加密（AEAD）]]方法。这表示它需要密钥K、明文P和一些附加数据（associated data，以下简称AD）作为输入；然后使用密钥对明文 P 加密得到密文 C，并根据密文和AD（未加密）的计算来得到认证标签 T。知道K（密钥）的接收者在收到AD、C（密文）和T（认证标签）后可以解密密文以得到P（明文），并且可以检查T（认证标签）以确保密文和AD都没有被篡改。

GCM使用块大小为128位的块密码（通常为[[高级加密标准|AES-128]]）的[[分组密码工作模式#计数器模式（CTR）|计数器模式]]进行加密，并使用[[有限域|'''伽罗瓦'''域]]GF（<math>2^{128}</math>）中的算术来计算认证标签；因此得名。

'''伽罗瓦消息认证码（GMAC）'''是GCM的一种仅用于认证的变体，可以形成增量[[訊息鑑別碼|消息认证码]]。GCM和GMAC都可以接受任意长度的[[初始向量|初始化向量]]。

即使是与相同的分组密码一起使用，不同的分组密码的操作模式也可能具有显著的不同性能和效率特征。GCM可以充分利用[[并发计算|并行处理]]，实现GCM可以有效地利用[[指令管線化|指令流水线]]或硬件流水线。相比之下，[[分组密码工作模式#密码块链接（CBC）|密码块链接（CBC）]]模式会导致[[流水线停顿|流水线停滞]]，从而影响其效率和性能。

== 基本操作 ==
与一般[[分组密码工作模式|计数器模式]]一样，每个块按顺序编号，然后该块编号与[[初始向量|初始化向量]]（Initialization Vector，IV） 组合并使用块密码算法（{{Math|E}}）加密（通常是[[高级加密标准|AES]]）。然后将此加密的结果与[[明文]]进行[[位操作#按位异或（XOR）|异或]]以产生[[密文]]。与所有计数器模式一样它本质上是一个[[流密码]]，因此必须对于每个加密流使用不同的 IV。

密文块被认为是一个[[多項式]]的系数，然后在密钥相关点H处使用[[有限域算术]]求值。随后再对结果进行加密，生成可用于验证数据完整性的身份验证标签。加密后的内容包含 IV、密文和身份验证标签。

[[File:GCM-Galois_Counter_Mode_with_IV.svg|550x550像素|''GCM加密操作'']]

== 数学基础 ==
GCM 将众所周知的[[伽罗瓦/计数器模式#CTR mode|计数器模式]]与新的 Galois 身份验证模式相结合。关键特征是用于验证[[有限域|的伽罗瓦域乘法易于并行计算。]]此功能允许此模式使用比[[分组密码工作模式#密码块链接（CBC）|CBC模式]]更高的吞吐量，使用的 GF(2 <sup>128</sup> ) 字段由多项式定义

: <math>x^{128} + x^7 + x^2 + x + 1</math>

身份验证标签是通过将数据块输入 GHASH 函数并对结果进行加密来构建的。这个 GHASH 函数定义为

: <math>\text{GHASH}(H,A,C) = X_{m+n+1}</math>

其中''H'' = ''E <sub>k</sub>'' (0 <sup>128</sup> [[分组密码|) 是哈希密钥，使用分组密码]]加密的 128 个零位的字符串， ''A''是仅经过身份验证（未加密）的数据， ''C''是[[密文]]， ''m''是 128- ''A 中的''位块（向上取整）， ''n是 C''中 128 位块的数量（向上取整），对于{{Nowrap|1=''i'' = 0, ..., ''m'' + ''n'' + 1}}''的变量 X <sub>i</sub>''定义如下。 <ref>{{Cite web|title=The Galois/Counter Mode of Operation (GCM)|url=http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf|access-date=20 July 2013|author=McGrew|first=David A.|year=2005|archive-date=2016-03-03|archive-url=https://web.archive.org/web/20160303203916/http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-spec.pdf|dead-url=no}} ''Note that there is a typo in the formulas in the article.''</ref>

首先，经过验证的文本和密文分别用零填充到 128 位的倍数，并组合成单个消息''S <sub>i</sub>'' ：

: <math>S_i = \begin{cases}
 A_i & \text{for }i = 1, \ldots, m - 1 \\
 A^*_m \parallel 0^{128-v} & \text{for }i = m \\
 C_{i-m} & \text{for }i = m + 1, \ldots, m + n - 1 \\
 C^*_n \parallel 0^{128-u}& \text{for }i = m + n \\
 \operatorname{len}(A) \parallel \operatorname{len}(C) & \text{for }i = m + n + 1
\end{cases}</math>

其中 len( ''A'' ) 和 len( ''C'' '') 分别是 A''和''C''的位长的 64 位表示， ''v''&nbsp;=&nbsp;连（''一''）&nbsp;模组&nbsp;''128 是 A''的最后一个块的位长， ''u''&nbsp;=&nbsp;长度( ''C'' )&nbsp;模组&nbsp;''128 是 C''的最后一个块的位长，并且<math>\parallel</math>表示位串的串联。

: <math>
 X_i = \sum_{j=1}^i S_j \cdot H^{i-j+1} = \begin{cases}
 0 & \text{for }i=0 \\
 \left(X_{i-1} \oplus S_i\right) \cdot H & \text{for } i = 1, \ldots, m + n + 1
\end{cases}
</math>

第二种形式是一种有效的迭代算法（每个''X <sub>i</sub>''取决于''X'' <sub>''i'' -1</sub> ），它是通过将[[秦九韶算法|霍纳的方法]]应用于第一种而产生的。只有最后的''X'' <sub>''m'' + ''n'' +1</sub>仍然是输出。

如果需要并行化哈希计算，可以通过交错''k''次来完成：

: <math>\begin{align}
 X^'_i & = \begin{cases}
  0 & \text{for }i \leq 0 \\
  \left(X^'_{i-k} \oplus S_i \right) \cdot H^k & \text{for } i = 1, \ldots, m + n + 1 - k \\
 \end{cases} \\[6pt]
 X_i & = \sum_{j=1}^k \left( X^'_{i+j-2k} \oplus S_{i+j-k} \right) \cdot H^{k-j+1}
\end{align}</math>

如果 IV 的长度不是 96，则使用 GHASH 函数计算''Counter 0'' ：

: <math>\begin{align} Counter 0 = \begin{cases} IV \parallel 0^{31} \parallel 1 & \text{for } len(IV) = 96 \\
 \text{GHASH}( \ IV \parallel 0^{s} \ \parallel \ 0^{64} \parallel len_{64}(IV) \ ) \text{ with } s = ( 128 - ( len(IV) \mod 128 )) \mod 128 & \text{otherwise} \end{cases} \end{align} </math>

GCM 由John Viega和 David A. McGrew 设计，是对Carter-Wegman 计数器模式（CWC 模式）的改进。 

2007 年 11 月， [[國家標準技術研究所|NIST]]宣布发布 NIST 特别出版物 800-38D''对块密码操作模式的建议：伽罗瓦/计数器模式 (GCM) 和 伽罗瓦消息验证码（GMAC），''使 GCM 和 GMAC 成为官方标准。 

== 使用 ==
GCM 模式用于IEEE 802.1AE (MACsec) 以太网安全、 [[IEEE 802.11ad]] （也称为[[WiGig]] ）、ANSI ( INCITS )[[光纤通道]]安全协议 (FC-SP)、 [[IEEE 1619|IEEE P1619]] .1 磁带存储、 [[互联网工程任务组|IETF]] [[IPsec]]标准、 <ref>RFC 4106 The Use of Galois/Counter Mode (GCM) in IPsec Encapsulating Security Payload (ESP)</ref> <ref>RFC 4543 ''The Use of Galois Message Authentication Code (GMAC) in IPsec ESP and AH''</ref> [[Secure Shell|SSH]] ， <ref>RFC 5647 ''AES Galois Counter Mode for the Secure Shell Transport Layer Protocol''</ref> [[傳輸層安全性協定|TLS]] 1.2 <ref>RFC 5288 ''AES Galois Counter Mode (GCM) Cipher Suites for TLS''</ref> <ref>RFC 6367 ''Addition of the Camellia Cipher Suites to Transport Layer Security (TLS)''</ref>和 TLS 1.3。 <ref>RFC 8446 ''The Transport Layer Security protocol version 1.3''</ref> AES-GCM 包含在NSA Suite B 密码学及其 2018 年商业国家安全算法 (CNSA)套件中的最新替代品中。 <ref>{{Cite web|title=Algorithm Registration - Computer Security Objects Register &#124; CSRC &#124; CSRC|url=https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration#AES|date=24 May 2016|access-date=2022-01-03|archive-date=2020-04-16|archive-url=https://web.archive.org/web/20200416045823/https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration#AES|dead-url=no}}</ref> GCM 模式用于[[SoftEther VPN]]服务器和客户端， <ref>{{Cite web|title=Why SoftEther VPN – SoftEther VPN Project|url=https://www.softether.org/1-features|access-date=2022-01-03|archive-date=2013-03-11|archive-url=https://web.archive.org/web/20130311084717/https://www.softether.org/1-features|dead-url=no}}</ref>以及自 2.4 版以来的[[OpenVPN|OpenVPN。]]

== 性能 ==
GCM 要求对每个加密和验证数据块（128 位）[[有限域|在 Galois 字段中进行]]一次分组密码操作和一次 128 位乘法。分组密码操作很容易流水线化或并行化；乘法运算很容易流水线化，并且可以通过一些适度的努力进行并行化（通过并行化实际操作，通过[[秦九韶算法|根据原始 NIST 提交调整 Horner 的方法]]，或两者兼而有之）。

英特尔添加了PCLMULQDQ指令，突出了它对 GCM 的使用。 <ref>{{Cite web|title=Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode (Revision 2.02)|url=http://software.intel.com/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode|access-date=2018-04-29|author=Gueron|date=April 2014|first=Shay|archive-date=2010-02-18|archive-url=https://web.archive.org/web/20100218191127/http://software.intel.com/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode|dead-url=no}}</ref> 2011 年，SPARC 添加了 XMULX 和 XMULXHI 指令，它们也执行 64 × 64 位无进位乘法。 2015 年，SPARC 添加了 XMPMUL 指令，该指令对更大的值执行 XOR 乘法，高达 2048 × 2048 位的输入值产生 4096 位的结果。这些指令支持 GF(2 <sup>''n''</sup> ) 上的快速乘法，并且可以与任何字段表示一起使用。

GCM 在许多平台上发布了令人印象深刻的性能结果。 Käsper 和 Schwabe 描述了一种“更快且抗时间攻击的AES-GCM” <ref>{{Cite book|last=Käsper|first=E.|last2=Schwabe|first2=P.|title=Cryptographic Hardware and Embedded Systems – CHES 2009|editor-last=Clavier|editor-first=C.|editor2-last=Gaj|editor2-first=K.|publisher=Springer|year=2009|isbn=978-3-642-04138-9|pages=1–17|doi=10.1007/978-3-642-04138-9_1|series=Lecture Notes in Computer Science|volume=5747}}</ref> ，它在 64 位英特尔处理器上实现了每字节 10.68 个周期的 AES-GCM 认证加密。Dai等人。使用 Intel 的 AES-NI 和 PCLMULQDQ 指令时，对于相同的算法，每字节报告 3.5 个周期。 Shay Gueron 和 Vlad Krasnov 在第三代英特尔处理器上实现了每字节 2.47 个周期。[[OpenSSL|为 OpenSSL]]和[[网络安全服务|NSS]]库准备了适当的补丁。 <ref>{{Cite web|title=AES-GCM for Efficient Authenticated Encryption – Ending the Reign of HMAC-SHA-1?|url=https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf|access-date=8 February 2013|author=Gueron|first=Shay|work=Workshop on Real-World Cryptography|archive-date=2014-03-10|archive-url=https://web.archive.org/web/20140310183919/https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf|dead-url=no}}</ref>

当需要对消息执行身份验证和加密时，软件实现可以通过重叠这些操作的执行来实现速度提升。通过交错操作[[指令層級平行|利用指令级并行性]]来提高性能。这个过程称为函数拼接， <ref>Gopal, V., Feghali, W., Guilford, J., Ozturk, E., Wolrich, G., Dixon, M., Locktyukhin, M., Perminov, M. [http://download.intel.com/design/intarch/PAPERS/323686.pdf "Fast Cryptographic Computation on Intel Architecture via Function Stitching"] {{Wayback|url=http://download.intel.com/design/intarch/PAPERS/323686.pdf |date=20110917090603 }} Intel Corp. (2010)</ref> ，虽然原则上它可以应用于密码算法的任何组合，但 GCM 特别适合。 Manley 和 Gregg <ref>{{Cite book|first=Raymond|last=Manley|first2=David|last2=Gregg|title=Progress in Cryptology – INDOCRYPT 2010|doi=10.1007/978-3-642-17401-8_22|editor-last=Gong|editor-first=G.|editor2-last=Gupta|editor2-first=K.C.|series=Lecture Notes in Computer Science|volume=6498|pages=311–327|isbn=978-3-642-17400-1|publisher=Springer|year=2010}} </ref>展示了在 GCM 中使用函数拼接时优化的简易性。他们提出了一个程序生成器，它采用加密算法的带注释的 C 版本，并生成在目标处理器上运行良好的代码。

例如，GCM 在嵌入式领域受到 Silicon Labs 的批评，因为并行处理不适合加密硬件引擎的高性能使用，因此降低了一些对性能最敏感的设备的加密性能。 <ref>{{Cite web|title=IoT Security Part 6: Galois Counter Mode|url=http://community.silabs.com/t5/Official-Blog-of-Silicon-Labs/IoT-Security-Part-6-Galois-Counter-Mode/ba-p/169191|access-date=2018-04-29|date=2016-05-06|archive-date=2016-05-11|archive-url=https://web.archive.org/web/20160511111925/http://community.silabs.com/t5/Official-Blog-of-Silicon-Labs/IoT-Security-Part-6-Galois-Counter-Mode/ba-p/169191|dead-url=no}}</ref>

== 专利 ==
根据作者的声明，GCM 不受专利保护。 <ref>{{Cite web|title=The Galois/Counter Mode of Operation (GCM) Intellectual Property Statement|url=http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-nist-ipr.pdf|author=McGrew|first=David A.|publisher=Computer Security Resource Center, NIST|access-date=2022-01-03|archive-date=2008-08-29|archive-url=https://web.archive.org/web/20080829220057/http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-nist-ipr.pdf|dead-url=no}}</ref>

== 安全性 ==
GCM 在具体的安全模型中被证明是安全的。 <ref>{{Cite book|first=David A.|last=McGrew|first2=John|last2=Viega|title=Proceedings of INDOCRYPT 2004|series=Lecture Notes in Computer Science|volume=3348|year=2004|doi=10.1007/978-3-540-30556-9_27|isbn=978-3-540-30556-9|publisher=Springer|bibcode=10.1.1.1.4591}}</ref>当它与与随机排列无法区分的分组密码一起使用时，它是安全的；然而，安全性取决于为使用相同密钥执行的每个加密[[初始向量|选择唯一的初始化向量]]''（参见''流密码攻击）。对于任何给定的密钥和初始化向量组合，GCM 仅限于加密{{Nowrap|2<sup>39</sup>−256}}位纯文本 (64 GiB)。 NIST 特别出版物 800-38D 包括初始化向量选择指南。

身份验证强度取决于身份验证标签的长度，就像所有对称消息身份验证代码一样。不鼓励在 GCM 中使用较短的身份验证标签。标记的位长，用 t 表示，是一个安全参数。一般来说，t 可以是以下五个值中的任意一个：128、120、112、104 或 96。对于某些应用，t 可能是 64 或 32，但这两个标签长度的使用限制了输入的长度数据和密钥的生命周期。 NIST SP 800-38D 中的附录 C 为这些约束提供了指导（例如，如果 t = 32 且最大数据包大小为 210 字节，则应调用身份验证解密函数不超过 211 次；如果 t = 64 且最大数据包大小为数据包大小为 215 字节，认证解密函数调用不超过 232 次）。

与任何消息认证代码一样，如果对手''随机选择一个 t''位标签，则对于概率度量为 2 <sup>- ''t 的''</sup>给定数据，它预计是正确的。然而，使用 GCM，对手可以通过选择带有 n 个单词的标签——密文的总长度加上任何额外的认证数据 (AAD)——以概率度量 2 <sup>- ''t''</sup>乘以 n 来增加成功的可能性。尽管如此，必须记住，对于任意大的''t'' ，这些最佳标签仍然由算法的生存度量{{Nowrap|1 − ''n''⋅2<sup>−''t''</sup>}}主导。此外，GCM 既不适合用于非常短的标签长度，也不适合用于非常长的消息。

Ferguson 和 Saarinen 分别描述了攻击者如何针对 GCM 身份验证执行最优攻击，满足其安全性的下限。 Ferguson 表明，如果''n''表示编码中的块总数（GHASH 函数的输入），那么有一种方法可以构建目标密文伪造，预计成功的概率约为''n'' ⋅2 <sup>− ''t''</sup> .如果标签长度''t''小于 128，那么这次攻击中的每一次成功伪造都会增加后续有针对性的伪造成功的概率，并泄漏有关哈希子密钥的信息，&nbsp;''H'' .最终， ''H''可能会被完全破坏，并且完全失去认证保证。 <ref>Niels Ferguson, [http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf Authentication Weaknesses in GCM] {{Wayback|url=http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-GCM/Ferguson2.pdf |date=20080921194134 }}, 2005-05-20</ref>

除了这种攻击，攻击者可能会尝试系统地猜测给定输入的许多不同标签以进行身份验证解密，从而增加其中一个（或多个）最终被视为有效的可能性。因此，实现 GCM 的系统或协议应监控并在必要时限制每个密钥的不成功验证尝试次数。

Saarinen 描述了 GCM弱密钥。 <ref name="gcm-ghash-weak-keys">{{Cite journal|title=Cycling Attacks on GCM, GHASH and Other Polynomial MACs and Hashes|url=http://eprint.iacr.org/2011/202|last=Markku-Juhani O. Saarinen|date=2011-04-20|publisher=FSE 2012|journal=|access-date=2022-01-03|archive-date=2020-11-23|archive-url=https://web.archive.org/web/20201123223051/https://eprint.iacr.org/2011/202|dead-url=no}}</ref>这项工作为基于多项式哈希的身份验证的工作原理提供了一些有价值的见解。更准确地说，这项工作描述了一种在给定有效 GCM 消息的情况下伪造 GCM 消息的特定方法，对于{{Nowrap|''n'' × 128}}位长的{{Nowrap|''n''⋅2<sup>−128</sup>}}然而，这项工作并没有表现出比以前已知的更有效的攻击；本文观察 1 中的成功概率与 INDOCRYPT 2004 分析中引理 2 的成功概率相匹配（设置{{Nowrap|1=''w'' = 128}}和{{Nowrap|1=''l'' = ''n'' × 128}} ）。 Saarinen 还描述了基于 Sophie Germain primes的 GCM 变体 Sophie Germain Counter Mode (SGCM)。

== 参见 ==
* [[认证加密]]
* [[分组密码工作模式|分组密码操作模式]]
* AES-GCM-SIV

==参考文献==
{{reflist}}

{{分组密码}}
{{密碼學|hash}}

[[Category:訊息鑑別碼]]
[[Category:有限域]]
[[Category:分组密码工作模式]]