主页 / 问题 / 919256
Accepted
J. Doe
Asked:2020-12-13 04:57:36 +0000 UTC2020-12-13 04:57:36 +0000 UTC

Schnorr方案中的快速密钥生成算法

  • 772

给定：素数测试，素数生成函数。

我们需要找到一种算法来生成公钥的质数部分，q这样：

(p - 1) % q = 0， 在哪里

p- 1024 位的质数以及密钥的生成部分，

q- 160 位。

米勒-拉宾测试：

def milrab(n, k):
    if n < 2 or n % 2 == 0:
        return 0
    d = n - 1
    r = 0
    while d % 2 == 0:
        d >>= 1
        r += 1
    for i in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for j in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                continue
        return False  # составное
    return True  # простое

生成具有bits位大小的素数：

def pgen(bits):
    prime = False
    a = 0
    while not prime:
        a = random.randint(2**(bits - 1), 2**bits - 1)
        prime = milrab(a, 7)
    return a

部分公钥p和q：

def gen_p():
    return pgen(1024)

def gen_q(p):
    q = pgen(160)
    while (p - 1) % q != 0:
        q = pgen(160)
    return q

问题是生成q速度非常慢。有没有一种快速计算q乘数的方法p - 1？

python-3.x

1 个回答

  1. Best Answer

    到目前为止，我得出的结论是，您可以生成一个素数q（160 位），然后生成另一个数，我们称之为q_p，偶数和长度为 1024-160=864 位，我们将其乘以q并加一（如果乘积的长度为1023位，则进行下一次迭代并重新生成q_p），从而得到p，其简单性经测试验证。

    此外，在测试中，当生成一个随机数（在我的例子中称为a）时，我将 n > 202 的范围设置为 2:200（而不是 2:n-2）。

    执行时间减少到 0-5 秒。

    • 0

相关问题