共享多个RSA密钥对的模数是否安全？

#1 楼

我遇到了类似的问题，花了很长时间弄清楚所有的数学运算，因为有些证明可能很简洁。因此，我自己写了一个关于如何分解N的完整解释，而无需使用所有符号，并且不需要太多的先验知识。

这是共享模数攻击的一种应用，由Boneh在分析RSA攻击时。

无论如何，这样的系统并不安全。如果您知道有效的$ e $和$ d $，则可以考虑$ N $。
给定$（e，d，N）$，可以更正式地表示，其中$ N = pq $对于一些素数$ p $和$ q $，
和$ ed \ equiv 1 \ bmod {\ lambda（N）} $，可以很容易地找到$ p $和$ q $。

注意：$ \ lambda（N）$是Carmichael函数。如果您习惯于用$ \ phi（N）$来描述RSA，那么这非常相似。卡迈克尔定理是欧拉定理的一个概括，指出：
$$ \ forall a \，| \，\ gcd（a，N）= 1，\; a ^ {\ lambda（N）} \ equiv 1 \ pmod {N} $$
其中$ \ lambda（N）$是使该语句成立的最小整数。对于$ N = pq $，此数字仅为$ \ DeclareMathOperator {\ lcm} {lcm} \ lcm（p-1，q-1）$。 $ \ lambda（N）\，| \，\ phi（N）$也是正确的，因此在描述RSA时使用$ \ lambda（N）$代替$ \ phi（N）$只是一个概括。 。


首先，一些事实。考虑求解以下等式：

$$ \ begin {aligned}
y ^ 2＆\ equiv 1 \ bmod {N} \\
（y + 1）（y-1）和\ equiv 0 \ bmod {N} \\
\ end {aligned} $$

即计算一个的平方根。现在，请注意$ p \，| \，N $和
$ q \，| \，N $。由于零积属性
在模数为质数时在模算术中成立，因此确实是：

$$ y \ equiv \ pm 1 \ bmod {p} \; \，\文本{and} \; \，y \ equiv \ pm 1 \ bmod {q} $$

因此，我们知道：

$$ \ begin {aligned}
y \ equiv 1 \ bmod {p}＆\，\ text {or} \; \，y \ equiv -1 \ bmod {p} \\
y \ equiv 1 \ bmod {q}＆ \，\ text {or} \; \，y \ equiv -1 \ bmod {q} \ end {aligned} $$

这样就为N的每个因子提供了两种余数选择。由此，您可以从每个因子中选取一个值来构建四个方程组。每个方程组都有一个唯一的模N $（根据中国剩余定理）。
但是，并非所有解决方案都是一样的。考虑：

$$ \开始{aligned}
y＆\ equiv 1 \ bmod {p} \\
y＆\ equiv 1 \ bmod {q} \ end { aligned} $$

这有一个解决方案$ y = 1 $，这是微不足道的。两个都剩下$ -1 $的解决方案也很简单（$ y = N-1 $），也没有用。但是，现在考虑以下情况：

$$ \ begin {aligned}
y＆\ equiv -1 \ bmod {q} \ end {aligned} $$

这有一个简单的解决方案。此外，如果您知道此解决方案，则可以通过注意$ y-1 \ equiv 0 \ bmod {p} $，来分解$ N $，因此
$ p \，| \，y-1 $。由于$ p \，| \，N $也很容易通过计算
$ \ gcd（y-1，N）$来找到$ p $。交换$ p $和$ q $的对称方程对称系统也可以这样说。由于$ p $和$ q $是可互换的，因此
具有相同的结果。

我们还知道任何非平凡的根（即非1或-1）都必须
来自我们所研究的两个非平凡案例之一，因为我们知道这些方程的解是唯一的。这意味着上述逻辑
适用于我们可能发现的任何非平凡根。

因此，我们有事实1：如果$ y $是一个模的非平凡平方根
$ N $，其中$ N $是两个素数的乘积，$ N $的因子之一是$ \ gcd（y-1，N）$。

第二个要简单得多：

$$ \ begin {aligned}
a ^ b＆= c \\
a ^ {{\ frac b 2} + { \ frac b 2}}＆= c \\
a ^ {\ frac b 2} a ^ {\ frac b 2}＆= c \\
（a ^ {\ frac b 2}） ^ 2＆= c \ end {aligned} $$

这是事实2：给定$ a $，$ b $和$ c $使得$ a ^ b = c $，则平方$ c $
的根是$ a ^ {\ frac b 2} $。只要b是偶数（即
$ 2 \，| \，b $），这很容易计算。


现在可以进行实际攻击了。首先，请注意
$ ed-1 \ equiv 0 \ bmod {\ lambda（N）} $。此值很重要，因此让
$ k = ed-1 $。因为它等于零，所以$ \ lambda（N）\，| \，k $。
此外，$ 2 \，| \，\ lambda（N）$也就是$ 2 \，| \，k $。然后$ k $可以用
形式写成$ k = 2 ^ tr $，表示某个奇数$ r $且$ t> 0 $。

然后，选择任意$ x $（即$ \ forall x \，| \，2 \ leq x $$ x ^ k \ equiv x ^ {k \，\ bmod {\ lambda（N）}} \ equiv x ^ 0 \ equiv 1 \ pmod {N} $$
应用事实2，我们可以通过
计算$ x ^ {\ frac k 2}来找到一个模$ N $的平方根{N} $。现在有几种可能性：


结果为$ 1 $。这是一个简单的解决方案。但是，如果
指数为偶数，则可以再次尝试，将
指数再除以2。如果指数是奇数，则选择一个新的$ x $，
然后再次尝试攻击。
结果为$ N-1 $，即$ -1 $。这是一个简单的解决方案。与前面的情况不同，将指数再次除以2不会得到1的平方根，而是产生负1的平方根。
因此，选择一个新的$ x $然后重试。
结果与以上均不相同。这是一个不平凡的解决方案。
剩下的就是通过应用事实1来分解$ N $。换句话说，该算法可以表示为：


计算$ k = ed-1 $
在$ k $，因式分解中确定$ 2 $，$ t $的指数将$ k $分解为$ k = 2 ^ tr $的形式，其中$ t> 0 $并且$ r $为奇数。
随机选择$ x \，| \，2 \ leq x 计算序列
$ s = x ^ {\ frac k 2}，x ^ {\ frac k 4}，\ dots，x ^ {\ frac k {2 ^ t}} \ pmod {N} $

确定第一个索引$ i $，使$ s_i \ neq \ pm 1 $和
$ s_ {i-1} = 1 $


如果没有这样的索引，请选择一个新的$ x $，然后重试。
否则，让$ p = \ gcd（s_i-1，N）$和$ q = \ frac N p $。


完成。

攻击依赖于您可以轻松生成与一个模$ N $一致的数字的事实。此外，将指数除以2可以很容易地求出这些数字的平方根。有一个
机会，取这个平方根会产生
模N $的非平凡平方根，这使您可以通过
使用欧几里得算法。这是一种概率算法，
在于它依赖于非平凡的解决方案。如果没有找到非平凡的解决方案，则该算法需要从新的$ x $开始。


获得非平凡的解决方案的机会很重要
使用此算法时的考虑。因此，要确定此概率，请考虑一种选择随机$ x $取模$ N $的方法。对于某些指数$ e $，则也是随机的。还应注意
，对于任何给定的模数$ m $，整数集均以模数$ m $均匀地分布在小于$ m $的正整数集中； $ P（x ^ e \ equiv 1 \ bmod {m}）= P（x ^ e \ equiv m-1 \ equiv -1 \ bmod {m}）$$
事实1的证明需要解决方案由两个等式组成的系统的方程组，每个都是从两个可能的方程式中“挑选”出来的。
有四个可能的方程组，每个都有相同的可能性，因为
数的均等分布mod $ m $。因此， $ x $满足上述任何一个系统的概率为
$ \ frac 1 4 = 25 \％$。由于这些系统中的两个产生非平凡的
解，因此，给定随机$ x $
，非平凡的解的概率为$ 50 \％$。通过在$ \ sqrt {x ^ e} \ equiv 1 \ bmod {m} $的情况下继续计算平方根，可以提高这种可能性。但是，
因为该数字与序列中的前一个数字相关，所以一个
不能再提出严格的随机性论证，即序列中的下一项也有$ 50 \％$的机会是不平凡的。您可以说
，但是：
$$ P（\ exists \，\ text {$ s $中的非平凡解}）\ geq 50 \％$$
上面算法描述中给出的$ s $的定义。因此，
从$ x $的随机
值生成恒定的有限数量的序列可以提供产生非平凡解的任意高概率。 br /> />由于计算整个序列$ s $不能保证更高的找到非平凡解的可能性，因此合理地思考为什么要打扰计算整个序列。但是，在计算
$ x ^ {\ frac k 2} $时，很容易“免费”获得整个序列。通过将$ k $部分分解为$ 2 ^ tr $，可以将$ s $递归定义为：

$$ \ begin {aligned}
s_t＆= x ^ r \\
s_i＆= s_ {i + 1} ^ 2 \ end {aligned} $$

请注意，此递归定义从后到前定义了序列，
因此在计算$ s_1 $的过程中，还会计算该序列的所有其他项
。平方是与
pow-mod操作
将进行的相同计算，因此在计算序列的附加项时不会增加复杂性。

然后，下面是执行上述部分分解的代码（在python中）：

# Returns a tuple (r, t) | n = r*2^t
# Complexity O(lg n)*
def remove_even(n):
    if n == 0:
        return (0, 0)
    r = n
    t = 0
    while (r & 1) == 0:
        t = t + 1
        r = r >> 1
    return (r, t)

这可以在$ \ Theta中实现（\ lg n）$时间。此实现
进行重复的移位，因此在最坏的情况下，运行时间是\\ Theta（（\ lg n）^ 2）$。一个实现可以通过遍历$ n $的位而不执行重复的移位来实现最佳时间；
但是，对于python longs来说这更困难，因此为了清楚起见使用了这种方法。

这段代码将生成序列$ s $的项，直到找到一个
一个模$ N $的非平凡平方根：
-and-multiply
方法，即$ O（（\ lg N）^ 3）$。如前所述，
函数返回值（概率为'None'）的概率至少为$ 50 \％$，而
随机$ x $。

最后，给定有效的
RSA密钥，以下是一些实际计算模数的代码：多项式时间（ZPP）。例如，
该算法在14次迭代或少于14次迭代后成功的可能性
大于$ 99.99 \％$。计算$ k $是$ O（（\ lg N）^ 2）$，概率部分是$ O（（\ lg N）^ 3）$，而欧几里得算法
计算最大公约数也是$ O（（\ lg N）^ 3）$。
因此，整个算法将在（概率）
$ O（（\ lg N）^ 3）$中运行时间。

最后，这是运行此算法以分解RSA模数的示例：

# Returns a non-trivial sqrt(1) mod N, or None
# Arguments:
#     x: random integer 2 <= x < N
#     k: multiple of lambda(N)
#     N: modulus
# Complexity O((lg n)^3)
def get_root_one(x, k, N):
    (r, t) = remove_even(k)
    oldi = None
    i = pow(x, r, N)
    while i != 1:
        oldi = i
        i = (i*i) % N
    if oldi == N-1:
        return None #trivial
    return oldi

运行速度非常快，并证明了算法正确运行。
因子N。请注意，因子的顺序因运行而异，
取决于首先找到的根。但是，这两个因素的顺序无关紧要，所以对于攻击共享模数密码系统的目的来说，这是足够的算法。

回到最初的问题，如果Bob共享他的第一个私钥，
，而他的所有密钥都共享一个模数，那么Mallory可以使用此算法分解模数。一旦模数被分解，她就可以计算$ \ phi（N）=（p-1）（q-1）$。利用$ \ phi（N）$的知识，计算其他公钥（即对应的私钥）的模乘逆是扩展欧几里德算法的简单应用。

评论

---

$ \ begingroup $
$ \ phi（N）$应该替换为$ \：\ operatorname {L} \ hspace {-0.02 in} \ operatorname {cm}（\ hspace {.04 in} p \ hspace {-0.04 in }-\ hspace {-0.05 in} 1，q \ hspace {-0.04 in}-\ hspace {-0.05 in} 1）\; $。 $ \; \; \; $
$ \ endgroup $
–user991
2014年2月26日在20:49

---

$ \ begingroup $
@RickyDemer：该过程的几个步骤依赖于欧拉定理，但我只知道$ \ phi {N} $的那个定额。它也适用于$ Lcm（p-1，q-1）$吗？这是RSA的一部分，我从没做过。
$ \ endgroup $
–罗伯特·梅森
2014-2-27在12:57

---

$ \ begingroup $
无论如何，不​​错的答案@RobertMason
$ \ endgroup $
– DrLecter
2014-2-28在17:54

---

$ \ begingroup $
我将其更新为使用$ \ lambda（N）$而不是$ \ phi（N）$-感谢您的注意。
$ \ endgroup $
–罗伯特·梅森
2014-2-28在17:54

---

$ \ begingroup $
在remove_even（）中，我知道t是2的指数，因此每次r右移时都会递增。但是，是否有必要计算并返回此变量？它仅返回给调用函数，而不能在remove_even（）或调用函数中使用。
$ \ endgroup $
–卡尔·诺克斯
17年1月27日在16:40

---

#2 楼

不，这不安全。知道私有指数$ d $（和相应的公钥）可以分解$ m $模数，这可以检索所有其他私有指数（给定公共指数）。

Bob应该生成一个新的模数，这不是那么昂贵。另外，如果Bob的旧公用密钥已在任何地方注册，则应撤销其旧公用密钥。

#3 楼

当您至少知道$ e $小时（例如通常为65537的情况），知道$ d $的方法是一种简单得多的方法。您知道$ ed = 1 \，（\ textrm {mod} \，\ phi）$。由于您知道$ e $和$ d $，因此可以计算$ S = ed-1 $，并且由于第一个等式，该数字必须可被$ \ phi $整除。请注意，该值的最大值约为模量的65537倍（因为$ d $与模量的大小相同）。还应注意$ \ phi $与模量的大小相同。因此，$ S $实际上必须是$ \ phi $的较小倍数。因此，您可以简单地尝试除数$ k = 1，\ ldots，$，直到找到除以$ S $的除数，然后尝试计算“候选” $ \ phi'= S / k $。现在，您可以使用自己的知识$ pq = n $和$（p-1）（q-1）= \ phi'$轻松地从$ \ phi'$求解$ p $和$ q $，只需使用替换二次方程式的常用公式。请注意，您可能必须经历一些“错误的” $ k $（和错误的$ \ phi'$ s），当您击中不是真正因素的$ k $时，就会发生这种情况，而恰好是真实因素或$ \ phi $本身-它会除以$ S $，但会导致错误的$ \ phi'$。在这种情况下，只需继续尝试$ k $，因为正确的$ k $必须小于$ \ approx 65537 $，因此没有太多尝试。

#4 楼

@ robert-mason的答案很好，但是相当大。
这里是算法和紧随其后的证明。

证明（在第1部分的末尾）。