socat）中使用的Diffie-Hellman模数不是素数。这导致一些人大喊“后门”。我不明白的是，这怎么可能允许后门？
我想问题可能出在小小组攻击。但这可能与模数为质数时一样大。或更好：一个非主要群体可能有一个大的主要子群体，而一个主要群体可能有一个小的主要子群体。
思路？
似乎Pohlig–Hellman可能是一个答案：您可以计算平滑顺序组中的离散对数。有人开始测试非质数模数的小因素，发现3684787 = 271 x 13597是一个因素。似乎没有其他“容易”的因素可以找到，这是否意味着即使对手知道因式分解，Pohlig-Hellman也不起作用。 （他需要小的因素，不仅需要已知的因素。）
#1 楼
这怎么可能造成后门？
好吧，如果对组合进行DH模运算，则攻击者可以解决DH问题（或DLog问题）对构成组合的每个素数进行模运算。
知道因式分解的人可以使用几种方法来解决DLog问题，这比预期的容易。
/>
可以将每个素数设置为允许进行较小的子组攻击（即，每个素数$ p，q $具有$ p-1，q-1 $平滑；但是这也使它更容易另一方面，可能会有一个$ p $和$ q $“部分平滑”；也就是说，$ p-1 $和$ q-1 $都将包含一个约64位的因子这将使DLog花费$ O（2 ^ {32}）$时间（烦人，但非常可行）；而$ p-1 $分解因数可能会花费$ O（2 ^ {64}）$时间。 （很可能没人会去尝试）。
这种方法的一种变体（如果也可以选择$ g $）是选择$ p-1 = 2p_1p_2 $，其中$ p_1 $是（例如）32位素数，而$ p_2 $是479位素数，然后选择$ g $以便生成（mod $ p $）一个子组订单$ p_1 $。而且，当然，您为$ q $做同样的事情。您实际看到的DLog问题将花费$ O（2 ^ {16}）$的工作，而$ pq $将很难考虑（除非有人猜测$ p_1 $，然后计算$ gcm（pq，g ^ {p_1} -1）$；后门安装程序希望没有人考虑尝试）
另一种方法是使复合材料（例如）具有4 256位素数，不需要承认小的小组。在那种情况下，对于知道分解的人可以通过解决4个以256位素数为模的问题来解决DLog问题。比小组攻击可以做的更多的工作；但是它仍然很实用（并且复合材料仍然很难分解）。
第三种方法是选择素数$ p $和$ q $对SNFS友好；也就是$ r ^ e + s $的形式，对于$ r来说，s $小。如果$ p $和$ q $为$ r $使用不同的值，这将不会立即显现。
因此，是的，复合模量可能是后门。
评论
$ \ begingroup $
@David天宇Wong：我正在研究选择模数的人（“攻击者”）如何使用复合模数来隐藏一小群（或其他）攻击。是的，他还可以选择容易受到小组攻击的1024位素数，但是其他任何注意到$ p-1 $可以平滑的人也可以收听-我正在尝试我们可以做NOBUS的方法（“但我们”）-也就是说，安装程序可以监听，但是对于其他任何人来说都很难，即使他们猜测攻击者的所作所为也是如此。
$ \ endgroup $
–雨披
16-2-3在18:43
$ \ begingroup $
我删除了我的问题，因为我想出了答案（没有看到您有时间回答），但是我实际上并不认为用素数来取消NOBUS！ （这是因为，如果p是素数，则阶数很容易计算，但是如果我们不知道非素数p的因式分解，则阶数很难计算）
$ \ endgroup $
– David天宇黄
16-2-3在18:51
$ \ begingroup $
同样以$ 2p_1p_2 $的方式，您只能在订单$ p_1 $的子组上进行dlog，这足以猜测整个组的dlog吗？
$ \ endgroup $
– David天宇黄
16年3月3日在19:05
$ \ begingroup $
@David天宇Wong：不；但是，如果选择$ g $（用于DH操作的生成器），则不必这样做；只要您可以在$ g ^ a $上执行dlog操作，就足够了。
$ \ endgroup $
–雨披
16年3月3日在19:11
$ \ begingroup $
@David天宇Wong：当然可以；如果您有一个解决方案$ y = g ^ {a_p} \ pmod {p} $和一个解决方案$ y = g ^ {a_q} \ pmod {q} $，那么我们知道$ y = g ^ a的解决方案\ pmod {pq} $具有$ a \ equiv a_p \ pmod {p-1} $和$ a \ equiv a_q \ pmod {q-1} $
$ \ endgroup $
–雨披
16-2-29在16:16
#2 楼
从那以后，我写了一篇论文来回答这个问题（当然是在Poncho的巨大帮助下）。我发现了很多实现后门的方法，有些是Nobody-But-Us（NOBUS）后门，而有些则不是（我在本文中也为NOBUS提供了一些“安全性”）。
我们的想法是寻找一种自然的方式，用Pohlig-将后门注入DH Hellman：
模数$ p $是质数，因此我们可以自然地计算出组中的公钥（元素）数：$ p-1 $ 。通过将此数字分解，您还可以获得可能的子组。如果您有足够的小子组$ p_i $，则可以使用中国剩余定理将您发现的许多局部私钥拼接在一起，成为真正的私钥。
这里的问题是，如果可以做Pohlig-Hellman，这意味着$ p_i $子组足够小，任何人都可以通过分解$ p-1 $来找到它们。
下一个想法是隐藏这些小子组，以便只有我们可以使用这种Pohlig-Hellman攻击。
这里的质数$ n $不再是质数了。相反，我们使用RSA模数$ n = p \ times q $。
由于$ n $不再是质数，要计算新的DH组中可能的公钥数量，我们需要计算$（p-1）（q-1）$（元素co的数量-加至$ n $）。这有点棘手，只有知道$ p $和$ q $的我们才能计算出这一点。
这样，在RSA的假设下，我们知道没有人能够分解元素数量（$（p-1）（q-1）$）以找出存在的子组。现在我们只有一小部分人隐藏起来，只有我们才能表演Pohlig-Hellman。
当然还有很多。阅读论文:)
评论
该模数是否已公开考虑？有人发现3684787 = 271 x 13597是一个因素
只要每个因子$ p_i ^ {e_i} $的乘法组顺序是平滑的，即$ p_i ^ {e_i-1}（p_i-1）$是否平滑，Pohlig-Hellman就会迅速工作。这些因素本身可以任意大。但这不是事实，否则可以使用$ p-1 $方法轻松分解数字。
什么是$ p-1 $方法？
@David天宇Wong p-1 = zh.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm