【凝聚交流会】Gröbner Basis 及其在 Related Message Attack 中的应用

4 minute read

Published:

本文主要介绍 Gröbner 基基本概念及其在 Related Message Attack 中的应用。

1. Gröbner Basis 相关概念

1. 背景

代数攻击是现代密码学中的一种攻击方法,其主要方法就是利用代数系统的良好性质及求解方法来攻击现存的密码学系统。 而求解有限域上的多变元二次方程是代数攻击的热点之一,因为该类方程在密码学中有着众多应用,比如 AES 可以用稀疏的超定的多变元二次方程来描述。 在国内外求解该类方程一般有两种方法,一种就是 Gröbner 基方法及其变种,但它有明显的缺点。 首先是效率差,用它求解多变元二次方程问题时,Gröbner 基方法的时间复杂度理论上为双指数,实际运行时间为单指数。 其次是时间复杂度难以度量,由于上诉两种方法都要达到一定条件才能终止算法,但是何时能达到条件不能预先判断,造成时间复杂度难以度量。对于稀疏的系统,Gröbner 基方法能够受益于系统的稀疏性,但是复杂度依然难以度量。

2. 定义

多项式组 ${\Bbb{G}} \subset {\cal{K}}[x]$ 称为给定项序 $<$ 下的 Gröbner 基,如果范式 $nform(G,{\Bbb{G}})$ 对所有 $G \in {\cal{K}}[x]$ 都是唯一的。 称 ${\Bbb{G}}$为多项式组${\Bbb{P}} \subset {\cal{K}}[x]$ 或理想 $<{\Bbb{P}}>$ 的 Gröbner 基,如果 ${\Bbb{G}}$ 是 Gröbner 基,且 $<{\Bbb{P}}> = <{\Bbb{G}}>$。 注:每个理想都有一个由有限多个多项式构成的Gröbner基,这由Hilbert基定理保证。

3. 性质

给定项序,下列条件是等价的:

(注:从 hexo 换成 academicpages 之后公式显示有点问题,所以直接放截图)

4. 生成

此处列出的是由 Buchberger 提出的第一个生成 Gröbner 基的算法。 截至目前,已有多种优化的算法,感兴趣可以自行 Google 相关资料。 相关引理详见《计算机代数》,此处未免篇幅累赘,省略。

2. 我对于Gröbner Basis的理解

我觉得 Gröbner Basis 本质上就是 gcd。只不过最简单的 gcd 是两个整数求公因数,或者是两个多项式求公因式,而现在是对于一个理想求其一组 Gröbner Basis。 多项式约化就是一种多元多项式的除法,是域上一元多项式欧几里德除法在多元多项式的推广。范式则类似余数。n 个数,随便哪一个模其最大公因数都为 0;而对理想上的每一组生成元,一般而言约化得到的范式可以多种多样,但它对 Gröbner Basis 的范式都是唯一的。

参考文献:Low-Exponent RSA with Related Messages. 这是Coppersmith等四人几十年前发表在欧密上的论文。

论文大致意思总结如下:

3.1 Abstract

攻击条件:

多组 RSA 加密的明密文 明文存在已知的多项式关系 不变的、已知的小公钥指数

3.2 文献主体

1. Introduction:

作者表示自己提出的这种方法与 Hastad广播攻击Simmons共模攻击 不一样,而是受到 Franklin 一种 e=3 下明文有线性关系的攻击的影响。

2. Generalizing the exponet e:

作者讨论了一元多项式的情况,并指出无论 e 为何值,用 多项式的gcd 总能求解,复杂度主要来源于 gcd。本文在4.2部分开头介绍了这种方法。

3. Generalizing the degree $\delta$ of the polynomial:

作者讨论了更进一步的情况,如果两个明文关系不是显函数,而是隐函数,那怎么办?作者提出了用 Resultant(结式)。这种解法的复杂度主要来源于结式的计算。在第三部分末尾,作者进行了总结,gcd 与结式本质上都可以归于 Gröbner Basis 的一种形式。

4. Generalizing the number of messages k:

作者讨论了最一般的情况,给出一个表明所有明文之间关系的多项式,以及每对明密文间关系的多项式 ${x_i^e}-{c_i} = 0 \mod N$,就可以使用 Gröbner Basis 方法解出所有明文。作者并对齐次、非齐次两种情况进行了讨论。

5. Implications:

作者讨论了两种应用,针对 The TMN protocolVerifiable signature sharing 的攻击。还是挺好理解的。

3.3 Conclusions:

作者表示对于这种攻击,假如这个多项式关系对于加密正确性非常重要不可改变,那唯一的弥补办法是增加 e 的大小。具体原因我在本文 4.1 中给出了说明。同时作者表示,如果这个关系不是那么不可改变,改用 DES 或者增加一个随机填充也是一种弥补的方法。

4. Challenge Example

说明:在 Sagemath 中有现成的 Gröbner Basis 方法可用。 相关文档:Ideals in multivariate polynomial rings.

4.1 最简单的形式:两组明文间有线性关系的RSA

相关题目:SCTF 2016 RSA Level3 我自己测试这种题目时, 用了 512 位的 RSA。 生成了三组数据,分别是 e = 65537e = 17e = 3 三种情况,来验证这种攻击。 以下是生成数据的代码:

g2-320@ubuntu:~$ python
Python 2.7.12 (default, Oct  8 2019, 14:14:10) 
[GCC 5.4.0 20160609] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import gmpy2
>>> import random
>>> p = gmpy2.next_prime(random.randint(2**256, 2**257))
>>> q = gmpy2.next_prime(random.randint(2**256, 2**257))
>>> p
mpz(199683252293673665551472691665551419793349650011340723524326275042790538215033L)
>>> q
mpz(177787798437200103573500618398920414052119870389396547167356558834406597501933L)
>>> n = p*q
>>> from Crypto.Util.number import *
>>> m = bytes_to_long('flag{this_is_test_msg}')
>>> m
38321129010652222587800757898922313003422320906430333L

>>> e = 65537
>>> cipher = pow(m, e, n)
>>> cipher
mpz(32079134133196243215946640500899486279552014031350695307199364738201089296625873378274649417451760116933169195441061908886130536255173413749002138536771414L)
>>> m_plus = 23*m + 99
>>> cipher_plus = pow(m_plus, e, n)
>>> cipher_plus
mpz(12276014662806790653865363052857705894559447871403126234418086174080893903357036260039102434339405707893500191948934858593508431650009522414372493497970463L)
>>> m_plus
881385967245001119519417431675213199078713380847897758L

>>> e = 17
>>> cipher = pow(m, e, n)
>>> cipher_plus = pow(m_plus, e, n)
>>> cipher_plus
mpz(28606082917189139264038832696412169527619679661680847395960919733793696794943782760670059800699481275786442771989512934053301194429960957953756677145745281L)
>>> cipher
mpz(24439546177551424527853938711374973812107749021181713346118770935722716219558572862044068097107232087522487638493345116319525081800114531644726940090023740L)

>>> e = 3
>>> cipher = pow(m, e, n)
>>> cipher_plus = pow(m_plus, e, n)
>>> cipher
mpz(5445499167137528964884070031340986488239663807827124682854459507601437631093965002189691164007449611668780985793883849606877839709355094799525453839055472L)
>>> cipher_plus
mpz(10063684967535762831843230344378382796752167590864022080926660432413272390928038844154453095352466577842506453140302433290958056222027517425161695776508883L)

攻击代码则是在SageMath 8.7中运行。

对于 e = 65537 的情况,报错 OverflowError: exponent overflow (65537)。警告信息为 verbose 0 (3497: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.。 警告的意思我大概理解是说,Sage 它可能对运行时间进行了估计,发现代码执行完成会非常缓慢、消耗大量时间,是一种“拙劣”的实现。而报错信息直接说明溢出了。 看来这和我们预想的一致,在解多元方程组时,Gröbner 基方法和吴方法时间复杂度都是双指数,在 e 特别大的时候在实际中是无法应用的。

对于 e = 3e = 17 这两种情况,Sage 均在 5s 以内给出了答案。下面的代码就是在 e = 3 情况时的代码。根据运行时间我觉得可能 100 以内,甚至更大的范围都可以使用这种方法。

# SageMath 8.7
import binascii

n = 35501245810072228913672367010172242347060684556523303235539354129635298141575478801031308635247761064541784618194533893631338138562929323271122990587158789
cipher = 5445499167137528964884070031340986488239663807827124682854459507601437631093965002189691164007449611668780985793883849606877839709355094799525453839055472
cipher_plus = 10063684967535762831843230344378382796752167590864022080926660432413272390928038844154453095352466577842506453140302433290958056222027517425161695776508883
# m_plus = 23*m + 99
# cipher = pow(m, e, n)
# cipher_plus = pow(m_plus, e, n)
# e = 3

R.<x, y> = Zmod(n)[]
I = ideal(x^3 - cipher, y^3 - cipher_plus, y-23*x-99)
res = I.groebner_basis()

m_solve = n - long(res[0] - x)
m_plus_solve = n - long(res[1] - y)

print (binascii.a2b_hex(hex(m_solve).strip('L')))

代码执行的结果如图:

4.2 一般应用的形式:求解多元但次数较低的多项式方程组

相关题目:红帽杯_2019_Crypto_Related 在 4.1 中讨论的情况,除了 Gröbner 基这种多项式方程组求解的通法,一般在公钥指数较小的情况下还可以手动推导求解,或者在一元多项式的情况下用 Sage 直接写一个简单的 gcd 函数,比如:

def poly_gcd(a, b): 
    return a.monic() if b == 0 else poly_gcd(b, a % b)

运行效果: (用上面注释掉部分的代码则生成的多项式会是有限域上的。在密码学中求解模某个数条件下的多项式方程组是很常见的。)

但在多元的稍微复杂的情况下,则只能使用一些特殊的方法,比如 Gröbner 基方法。(此外还有吴方法等,感兴趣可以了解,属于《计算机代数》《符号计算》领域) 此处就用红帽杯 2019 的 Related 为例。代码如下:

# Sage Math 8.7
import binascii

n = 16084923760264169099484353317952979348361855860935256157402027983349457021767614332173154044206967015252105109115289920685657394517879177103414348487477378025259589760996270909325371731433876289897874303733424115117776042592359041482059737708721396118254756778152435821692154824236881182156000806958403005506732891823555324800528934757672719379501318525189471726279397236710401497352477683714139039769105043411654493442696289499967521222951945823233371845110807469944602345293068346574630273539870116158817556523565199093874587097230314166365220290730937380983228599414137341498205967870181640370981402627360812251649
s = 280513550110197745829890567436265496990
c1 = 10607235400098586699994392584841806592000660816191315008947917773605476365884572056544621466807636237415893192966935651590312237598366247520986667580174438232591692369894702423377081613821241343307094343575042030793564118302488401888197517625333923710172738913771484628557310164974384462856047065486913046647133386246976457961265115349103039946802386897315176633274295410371986422039106745216230401123542863714301114753239888820442112538285194875243192862692290859625788686421276234445677411280606266052059579743874849594812733193363406594409214632722438592376518310171297234081555028727538951934761726878443311071990
c2 = 2665348075952836665455323350891842781938471372943896177948046901127648217780657532963063228780230203325378931053293617434754585479452556620021360669764370971665619743473463613391689402725053682169256850873752706252379747752552015341379702582040497607180172854652311649467878714425698676142212588380080361100526614423533767196749274741380258842904968147508033091819979042560336703564128279527380969385330845759998657540777339113519036552454829323666242269607225156846084705957131127720351868483375138773025602253783595007177712673092409157674720974653789039702431795168654387038080256838321255342848782705785524911705
c3 = 4881225713895414151830685259288740981424662400248897086365166643853409947818654509692299250960938511400178276416929668757746679501254041354795468626916196040017280791985239849062273782179873724736552198083211250561192059448730545500442981534768431023858984817288359193663144417753847196868565476919041282010484259630583394963580424358743754334956833598351424515229883148081492471874232555456362089023976929766530371320876651940855297249474438564801349160584279330339012464716197806221216765180154233949297999618011342678854874769762792918534509941727751433687189532019000334342211838299512315478903418642056097679717

R.<x, y, z> = Zmod(n)[]
I = ideal(x + y + z - s, x^17 - c1, y^17 - c2, z^17 - c3)
res = I.groebner_basis()

m1 = n - long(res[0] - x)
m2 = n - long(res[1] - y)
m3 = n - long(res[2] - z)
m = (long(m3<<256) + long(m2<<128) + long(m1))
print (binascii.a2b_hex(hex(m)[2:].strip('L')))

运行结果:

5. 其他应用

  1. 判定多项式理想之间的(从属和包含等)关系,进行理想间的运算、理想的准素分解
  2. 解代数方程组
  3. 几何定理的机器证明(如蝴蝶定理)、有理参数曲线与曲面的隐式化、代数曲面的拼接、等距线和等距面的计算等

6. 参考文献

  1. 王东明 等《计算机代数》(第二版)
  2. Don CoppersmithLow-Exponent RSA with Related Messages

声明:本文采用 CC BY-NC-SA 4.0 授权。

This work is licensed under a CC BY-NC-SA 4.0.