中域数字签名算法(DSA)

Question

当我们必须解离散对数问题a^x\equiv b\pmod p时，我理解它，其中a和b是给定的整数，我们必须找到秘密整数x，使这个方程对于给定的模p成立。

当a和b是多项式时，我不明白，我们不仅要处理模整数，而且还要处理另一个多项式。

1. 你能给我一个适用于这种情况的DSA的明确的工作示例吗？
2. 我们知道针对它的攻击是什么？

编辑:在原标准中，有限域具有特征2。所谓“中”域，是指素数p较大的域GF(p^n)。而不是p=2，而是10^{10}和n=17左右。

编辑2:我自己的例子：a=4 x^6+10 x^5+11 x^4+3 x^3+x^2+15 x+7 b=12 x^6+4 x^5+8 x^4+4 x^3+9 x^2+6 x+7 m_1=x^7-2 m_2=17

找到e那个a^e\equiv b\pmod{m_1}\pmod{m_2}

我不确定我的例子是否相关，关于多项式m_1和素数m_2的选择有一些准则。我选择了他们任意的。但我可以说，e=103是一个解决方案，因为我用暴力强迫它。

Answer 1

这个问题涉及到有限域 \mathrm{GF}(p^n)。它希望研究/攻击DSA的一个变体(该领域的乘法子群)，而不是\mathrm{GF}(p)。无论该变体是什么，都可以通过在离散对数问题中求解\mathrm{GF}(p^n)来攻击它。

\mathrm{GF}(p^n)的乘法子群有订单p^n-1，任意元素的顺序除以它。如果a的阶数没有大的素数因子，那么波利格-赫尔曼方法允许简化为更容易的子问题，这是像一步一步或波拉德氏肌这样的一般DLP算法所能解决的。DSA通过在大素数阶q的乘法子群(例如，至少256位)中工作来阻止这种攻击。这也使签名大小保持在最小(是q的两倍)。

所设想的参数是p\approx10^{10}和n=17，因此p^n约为565位，这使得这样的子群似乎是可行的.如果我们希望p略低于2^{32}和x^{17}-2 不可约模p (简化计算)，我们可以使用32位p=\mathtt{ffe083f1}_\text{h}，p^{17}-1具有最高的素数因子262位q=\mathtt{2a92bc16243adf3264304adf2adc292c32e64b569a5abfbd7be71d7a1816e3d8c1}_\text{h}。为了得到一个阶q的元素，我们可以选择几乎任意的多项式u，找出u的阶r (我们用p^{17}-1分解的素数除以D30的素数，而把u提高到1)，并使用g=u^{r/q}作为阶q子群的生成元。

从这和SHA-512建立一个DSA模拟是很容易的.唯一的困难是，当原始的p成指数模q，然后是约简模D36时。其中一个并行的选择是使指数模x^{17}-2\pmod p，然后在\Bbb Z中在x=2^{32}点(即将表示为32位整数的系数连在一起)计算该多项式，然后减少模q。

这将使一个有效的数字减影服务，对所有上述算法的安全，多亏了大型q。但这是不安全的，因为其他DLP方法适用于当前的情况。拉兹万·巴布列斯库和塞西尔·皮埃洛的“适用于中、高特性有限域的多数场筛”最近的研究结果摘要载于LMS计算与数学杂志，2014年。

试探性:选择攻击的算法可以是密码2006议事程序中的Antoine、Reynald、Nigel P. Smart和Frederik‘s 中质数情况下的数域筛。

在问题结尾的一个小例子中的沉思尝试在\mathrm{GF}(17^7)中工作，但是使用了一个多项式m_1=x^7-2，它不是不可约模p=17=m_2，因为(x+8)(x^6+9x^5+13x^4+15x^3+16x^2+8x+4)\\\quad\equiv x^7-2\pmod{17}

因此，(x+8)不是可逆的，我们得到了一个环

如果我们改变为p=29，这使得x^7-2不可约。我假设如下所示。

\mathrm{GF}(p^n)的乘法子群有序p^n-1，这里是29^7-1。这一因素如2^2\cdot7^2\cdot88009573。a的顺序必然是它的除数。通过计算a^{(29^7-1)/2}=-1\ne1、a^{(29^7-1)/7}=-5\ne1和a^{(29^7-1)/88009573}\ne1，我们得到a是全乘群的生成元。b\ne0，因此a^e=b有一个解决方案。