如何从列表中找到正确的公钥并解密它？

Question

您将获得一个唯一的 RSA 公钥，但密钥中使用的 RNG（随机数生成器） 一代人都遭受着脆弱性的困扰。此外，您还会获得由同一系统上的同一 RNG 生成的公钥列表。你的目标是获得 仅使用所提供的信息（即公钥列表）从给定的公钥中获取唯一的私钥。

公钥列表：4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35、36、38、39、40、42、44、45、46、48、49、50、51、52、54、55、56、57、58、60、62、63、64、65、66、 68、69、70、72、74、75、76、77、78、80、81、82、84、85、86、87、88、90、91、92、93、94、95、96、98、 99, 100, 102, 104, 105, 106, 108.

密钥对通过以下步骤生成：

1. 选择两个具有相同位大小的不同大素数，例如 p 和 q 。 5 和 2
2. 设 N = p ∗ q ，且 φ(N) = (p − 1) ∗ (q − 1) 。 10=5 乘以 2。&(5-1)*(2-1)=4
3. 选取一个整数 e ，使得 1 < e < φ(N) and gcd(e, φ(N)) = 1 . e=3.& 1<3<4 & gcd(3, 4=1)
4. 获取 e 的模逆： d ≡ e mod φ(N) （即 d ∗ e ≡ 1 mod φ(N)）。 d= 3 mod 4。d=3
5. 返回(N, e)作为公钥，d作为私钥。

我尝试使用扩展欧几里得算法代码。没用。

   def task_6(self, given_public_key_n: int, given_public_key_e: 
    int, public_key_list: list) -> int:
    # TODO: Implement this method for Task 6
    d=0

    def egcd(a: int, b: int):
        """return (g, x, y) such that a*x + b*y = g = gcd(a, b)"""
        if a == 0:
            return (b, 0, 1)
        else:
            b_div_a, b_mod_a = divmod(b, a)
            g, x, y = egcd(b_mod_a, a)
            return (g, y - b_div_a * x, x)

    def modinv(a: int, b: int) -> int:
        """return x such that (x * a) % b == 1"""
        g, x, _ = egcd(a, b)
        return x % b

    # initialize variables to be used
    n = given_public_key_n
    e = given_public_key_e

    # loop through each public key from public key list
    for public_key in public_key_list:
            # compute the common factor q, from the given public key n and current public key
            q = math.gcd(given_public_key_n, public_key)

            # if common factor is not equal to 1, stop processing further, as candidate factor is found
            if q != 1:
                break

    # public key n, is obtained by multiplying two prime factors p x q, since we have n and q, we can solve for the other factor p
    p = n // q

    # compute for the indicator of Euler (phi) using p and q
    phi = (p - 1) * (q - 1)

    # compute for d (private key) using the equation
        # d * e = 1 % phi
        # we use the pow operator to compute for the modular inverse d = e^-1 mod phi
    d = modinv(e, phi)

    # return found private key
    return d

所以 D = 3。我对吗？