基于“正常”离散对数的密码系统（DSA，Diffie-Hellman，ElGamal）在整数有限域中以大素数$ p $取模。但是，那里还有其他有限域，特别是二进制域$ GF（2 ^ n）$。铜匠描述了一种针对二进制场中离散对数的特殊攻击，后来由Adleman和Huang提炼为更通用的功能场筛。 Joux和Lercier使用FFS来获得$ GF（2 ^ n）$离散对数的当前记录，其中$ n = 613 $。

我想知道的是：


$ GF（2 ^ n）$中的离散对数与以$ n $位的质数$ p $为模的离散对数相比如何？在Coppersmith发布他的算法时，它使二进制字段中的离散对数看起来比其主要的$ p $对应项容易，但后者后来也得到了改进。
对于$ GF（ 2 ^ n）$，$ n $本身是否是素数？当前记录是$ GF（2 ^ {613}）$的记录，超过了先前的$ GF（2 ^ {607}）$记录，并且607和613都是素数。 $ GF（2 ^ {1024}）$中的离散对数会比$ GF（2 ^ {1021}）$中的离散对数更容易吗？


#1 楼

$ \ mathbb {F} _ {p} $中的离散对数与一般整数的整数分解具有相同的渐进复杂度：一般整数$ L_p [1 / 3,1.923] $，$ L_p [1 / 3,1.587] $用于特殊整数。 $ \ mathbb {F} _ {p ^ n} $中的离散对数具有与分解特殊整数相同的渐进复杂度，即通过函数字段筛分分解特殊整数，即$ L_ {p ^ n} [1/3，1.587] $。

因此，从分解记录中推论，我们可以得出结论：$ \ mathbb {F} _ {2 ^ {1021}} $中的离散对数比离散对数模容易一个768位的通用质数，大约与伪梅森素数$ 2 ^ {1021}-c $的模数相同。也许复合度扩展字段是否更容易求解。可能以多种方式表示同一复合字段（通常称为字段塔），并且某些表示可能比其他表示更快的中断。以下是安德鲁·奥德兹科（Andrew Odlyzko）于1985年发表的论文《离散对数及其密码学意义》的引文：


实际上，由于在字段及其子字段之间移动的可能性，这些字段可能非常弱。 br />

但是，没有关于复合度相对于素度的显着渐近优势的数据（如果存在的话，基于配对的方案将是敬酒的，因为嵌入度很大程度上取决于复合度）。

也不应忘记检查$ p ^ n-1 $的平滑度，以避免尴尬的Pohlig-Hellman中断。
似乎综合学位的确比初等学位弱。对于复合$ n $，Göloğlu等人和Joux攻击字段$ \ mathbb {F} _ {2 ^ n} $的最新结果比上面提到的函数字段筛快得多。有关更多信息，请参见此问题。

评论

$ \ begingroup $
欢迎使用Crypto Stack Exchange！遗憾的是，我们尚未在此处启用MatJax公式支持，因此您的公式看起来有些生。另外，您的链接也丢失了。
$ \ endgroup $
–PaŭloEbermann
2011年8月19日，0：54


$ \ begingroup $
好吧，删除了LaTeX语法，并进行了一些常规修复（包括链接）。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
11年8月19日在11:59
$ \ begingroup $
由于我们现在可以使用LaTeX语法，因此我在您的帖子中再次添加了公式。请检查我没有改变任何错误。
$ \ endgroup $
–PaŭloEbermann
2011-09-30 18:02
$ \ begingroup $
最近有一些与该问题相关的结果，包括Göloğlu，Granger，McGuire和Zumbrägel在桌面计算机上解决$ 6120 $位DLP
$ \ endgroup $
–fgrieu♦
13年5月29日在5:07


$ \ begingroup $
高度复合扩展度意味着乘法组的顺序将自动具有某些因素。反过来，这允许基于中文余数定理的DLP攻击。但是，单个大素数仍会给攻击者带来麻烦。例如2 ^ 1024-1 =（2 ^ 512-1）（2 ^ 512 + 1）。后一个因子是具有已知因子分解的费马数F_9，其最大因子约为7 * 10 ^ 92。仍然很大，但是当您拥有自动因素时，某些大小会被浪费掉。梅森素数在这方面是好的。
$ \ endgroup $
–吉尔基·拉托宁（Jyrki Lahtonen）
2014年7月3日在21:45

#2 楼

Antoine Joux非常高兴地向我发送了以下有关该主题的内容：


人们担心[具有复合指数的字段的对数]可能会更容易，这就是为什么他们使用质数指数的原因。对于指数的某些分解，将有限域视为扩展塔$（p ^ {n_1}）^ {n_2} $确实使事情变得容易。

请参阅“函数R. Lercier和我本人在“中度原始案例”中使用了“现场筛”。我尚未删除它，因为那样会使评论变得悬而未决。]
超过$ GF（2 ^ m）$的椭圆形提示，其中$ m $是复合的，可能很容易受到基于Weil下降的攻击。希望在离散对数计算中显示最新技术的人们选择ma素数的问题，因此不可能有这样的捷径。 Markus Maurer，Alfred Menezes和Edlyn Teske的综合学位领域（2001）是我可以方便地找到的有关该主题的最新著作。

评论

$ \ begingroup $
请注意，对复合度椭圆曲线的Weil下降方法将离散对数从$ E（\ mathbb {F} _ {2 ^ n}）$转移到$ J（\ mathbb {F} _ {2 ^ {（（n / p）}}）$，其中$ p $是$ n $的约数，而$ J $是高次椭圆曲线的雅可比行列式，其中离散对数可能更快。但是，最初的问题是关于基本字段$ \ mathbb {F} _ {2 ^ n} $中的离散对数。 Weil / Tate配对可用于将$ E（\ mathbb {F} _ {2 ^ n}）$转移到$ \ mathbb {F} _ {2 ^ n} $（MOV和FR攻击）。
$ \ endgroup $
–塞缪尔·内维斯（Samuel Neves）
2011-09-30 21:19


#3 楼

为了完成@Samuel的答案，当$ n $是复合的时，可以使用一些快捷方式；但是，它们仅贡献较小的常数因子，因此它们不会改变渐近行为：


如果将$ n $除以$ r $，则可以首先求解离散对数在子字段$ GF（2 ^ r）$中。在基于筛子的算法中，这可以提供最终线性代数步骤所需的关系的一半。如果$ n $不是素数，那么$ 2 ^ n-1 $也不是素数，可以通过使用中国余数定理更有效地实现这种操作。

如果在一个子组，可以削弱子组的选择。如果对于非平凡因子$ r $和$ s $，$ n = rs $，则$ GF（2 ^ n）^ {*} $的大小为$ 2 ^ n-1 $，是$ 2 ^ r-的倍数。 1 $。如果我们选择一个由订单$ q $的值$ g $生成的子组，其中$ q $除以$ 2 ^ r-1 $，那么我们实际上是在$ GF（2 ^ r）$中计算事物，并且可以求解离散通过在该子字段中进行日志记录，因为$ r $不超过$ n / 2 $，因此攻击效率更高。换句话说，在选择子组订单$ q $（质数）时，我们必须确保$ q $不会将任何$ r $除以$ n $来除以$ 2 ^ r-1 $。质数$ n $是确保这一点的简单方法。