RSA中的lcm与phi

#1 楼

我将使用以下常见定义和符号：


$ a \ equiv b \ pmod c $表示$ c> 0 $和$ c $除以$ ba $
$ a \ equiv b ^ {-1} \ pmod {c} $表示$ a \ cdot b \ equiv 1 \ pmod {c} $
$ a = b \ bmod c $表示$ a \ equiv b \ pmod {c} $和$ 0 \ le a $ a = b ^ {-1} \ bmod c $表示$ a \ equiv b ^ {-1} \ pmod c $和$ 0 \ le a $ \ varphi $是欧拉totient函数（也称为$ \ phi $）
$ \ lambda $是Carmichael函数


我将$ N $的积限制为不同的素数；对于两个这样的素数，$ \ varphi（N）=（p-1）\ cdot（q-1）$，$ \ lambda（N）= \ operatorname {lcm}（p-1，q-1）$和$ \ varphi（N）= \ lambda（N）\ cdot \ gcd（p-1，q-1）$。


加密标准PKCS＃1要求私有指数$ d $是$ 0
注意$ e \ cdot d \ equiv1 \ pmod {\ lambda（N）} $，或等价的$ d \ equiv e ^ {-1} \ pmod {\ lambda（N）} $，并没有唯一地定义$ d $。如果$ d $是有效的私有指数，则从数学角度来看，$ k \ cdot \ lambda（N）+ d $也是有效的私有指数$ \ forall k \ in \ mathbb Z $，并且从PKCS有效$ 0
使用$ d = e ^ {-1} \ bmod \ lambda（N）$而不是$ d \ equiv e ^ {-1} \ pmod {\ varphi（N）} $并不是一个好的速度优化：如果一个是对速度感兴趣，根本不使用$ d $！而是使用中国剩余定理（CRT）来实现RSA，在该算法中，使用可以计算为$ d_p = e ^ {-1} \ bmod {（ p-1）} $，无论选择了哪个$ d $。

更新：如注释中所述，FIPS 186-4标准需要$ 2 ^ {\ lceil \ log_2（N）\ rceil / 2}

评论

---

$ \ begingroup $
Nist Fips 186-4明确要求$ 2 ^ {nlen / 2} $ \ endgroup $
–user27950
2015年10月4日17:58

---

#2 楼

$ \ varphi $和$ \ lambda $的安全性应该等效，因为它们在使用上下文中在数学上是等效的。 （也就是说：$（\ mathbb Z / pq \ mathbb Z）^ \ times $中的$ d´$ th次幂与$ d $ th次幂完全相同。）

但是，计算$ d $的数学上正确的模数是$ \ lambda（pq）$：它恰好是组$（\ mathbb Z / pq \ mathbb Z）^ \ times $的指数，即，负整数$ k $，使得所有$ x \ in（\ mathbb Z / pq \ mathbb Z）^ \ times $的$ x ^ k \ equiv1 \ pmod {pq} $。这两个选项都可以，但是从概念上讲，实际需要的是$ \ lambda $。加上实际的性能优势，这使其成为更好的选择。