go - rand.Prime(rand.Reader, 3072) 执行时间长

Question

我以实现 RSA 为例。几周前，它似乎工作正常。

然而，现在 key 的生成需要很长时间(>10 秒)。我已将范围缩小到以下行:

import "crypto/rand"

p, _ := rand.Prime(rand.Reader, 3072)

为什么这会花费大量时间？

Answer 1

除了进行素性测试的计算成本外，根据 crypto/rand文档中，这些数字来自“加密安全伪随机数生成器”。这种随机性来源might be slow ，具体取决于您的环境。

这可能就是为什么 crypto/prime 使用 io.Reader 的原因，这样我们就可以为它提供另一个随机源。 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)
}

即便如此，正如 James K Polk 所建议的那样，由于素数测试的成本，尝试生成 3000 位素数似乎本身就很慢(在我的机器上也需要几秒钟)。