英文:
rand.Prime(rand.Reader, 3072) takes a long time to execute
问题
我实现了一个RSA的例子。几周前，它似乎工作得很好。
然而，现在生成密钥需要很长时间（>10秒）。我已经缩小到了这一行代码：
import "crypto/rand"
p, _ := rand.Prime(rand.Reader, 3072)
为什么这会花费很长时间呢？
英文:
I implemented RSA as an example. Several weeks ago, it seemed to work fine.
Now, however, the generation of keys takes a long time (>10 seconds). I've narrowed it down to the line:
import "crypto/rand"
p, _ := rand.Prime(rand.Reader, 3072)
Why would this take a significant amount of time?
答案1
得分: 1
除了进行素性测试的计算成本之外，根据crypto/rand文档，这些数字是从一个“具有密码学安全性的伪随机数生成器”中获取的。这样的随机源可能会很慢，这取决于您的环境。
这可能是为什么crypto/prime使用io.Reader的原因，这样我们就可以提供另一个随机源。例如：
package main
import (
cRand "crypto/rand"
"fmt"
mRand "math/rand"
)
// 从http://stackoverflow.com/questions/12771930/改编而来
type randReader struct {
src mRand.Source
}
func newRandReader() *randReader {
// FIXME: 从crypto/rand获取种子。
return &randReader{mRand.NewSource(42)}
}
func (r *randReader) Read(p []byte) (n int, err error) {
for i := range p {
p[i] = byte(r.src.Int63() & 0xff)
}
return len(p), nil
}
func main() {
fmt.Println("Hello, playground")
r := newRandReader()
p, _ := cRand.Prime(r, 300)
fmt.Println(p)
}
即使这样，尝试生成3000位的素数似乎本质上是很慢的（在我的机器上也需要几秒钟），这是由于素性测试的成本，正如James K Polk所建议的。
英文:
Besides the computational cost of doing primality testing, according to the crypto/rand documentation, the numbers are sourced from a "cryptographically secure pseudorandom number generator". Such sources of randomness might be slow, depending on your environment.
That's probably why crypto/prime consumes an io.Reader, so that we can feed it another source of randomness. e.g.:
package main
import (
cRand "crypto/rand"
"fmt"
mRand "math/rand"
)
// Adapted from http://stackoverflow.com/questions/12771930/
type randReader struct {
src mRand.Source
}
func newRandReader() *randReader {
// FIXME: source the seed from crypto/rand instead.
return &randReader{mRand.NewSource(42)}
}
func (r *randReader) Read(p []byte) (n int, err error) {
for i := range p {
p[i] = byte(r.src.Int63() & 0xff)
}
return len(p), nil
}
func main() {
fmt.Println("Hello, playground")
r := newRandReader()
p, _ := cRand.Prime(r, 300)
fmt.Println(p)
}
Even with this, trying to generate 3000-bit primes does appear to be inherently slow (takes several seconds on my machine too) due to the cost of primality testing, as James K Polk suggests.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论