如何进行广播RSA攻击？ [已关闭]

Question

使用三个不同的 1,024 位 RSA 公钥对消息进行加密，从而产生三个不同的加密消息。它们都有公共指数 e = 3 .

您将获得三对公钥和关联的加密消息。你的工作是 恢复原始消息。

def​ ​task_7​(self,
n_1_str: str, c_1_str: str,
       n_2_str: str, c_2_str: str,
       n_3_str: str, c_3_str: str) -> str:
n_1 = int(n_1_str, 16)
c_1 = int(c_1_str, 16)
n_2 = int(n_2_str, 16)
c_2 = int(c_2_str, 16)
n_3 = int(n_3_str, 16)
c_3 = int(c_3_str, 16)
msg = ​'' m = ​0
 # Solve for m, which is an integer value,
# the line below will convert it to a string
msg = bytes.fromhex(hex(m).rstrip(​'​L​'​)[2:]).decode(​'​UTF-8​')​
return​ msg


def test_task_7(self):
    msg = self.project_3.task_7('0xd8a7bcd5864fbf881a5e4e8b53ab86f248ef3b03e65f2b2b264c8c43d14594351e1a66eeedfb43eafcb669a178f39d75ccde67a6c26b73a9cc9e44971a540dae5af6b7d65583199680822a62385705956fcaf85d8cc3cd7e95071662a2af1aaf6962b3219e8ec0c83ce1a783493b2d31e14d0ffbeef03d71f0806419b5af4745',
                                '0x373ad5c2602a01b004a58104691d55c64b413a0199458f74e02fd83a44f45fb5267f7513f2eb14aa2badf6c0eb108264da8a93e5bb74cef850626ac921d513aad73782c1ce306940709c40a42696acb61c02d47fdc597c8745faa7d398e04441da658afe12c8be9ddd7979a0780071dc7bd8f5f6d44d49baa14a0a8a47cbed0e',
                                '0xaaf7fc5bb222d376ecb6e30018de69e92ab3dbf69bc6353bebf4e9644a3df559a0b4d1218147f7c8d0c8f8b4988c2b53d2a46d23aa92d866d6b7e3fbdcd5ea0741a17ccbd0cd377201c4bac3570060d986c1e8b49e2b72d61236db6baeb89057e7f3df6cb048db9589816f86a657584c58f2c33792c23b91e4e6addf355da46b',
                                '0x9ca691c4c48c72058854d4ea7ea9a9c4f4bb16bb26d4595ed1b196a9547c153395d74a21595420408f694c2eae250fd52af72e3b5f09302d8c20cc2df69c3faa4569ab4ba363478a012292f596fd38b93fd71fb8893355087d9f8a27ad79eb310fb6a5a9610fffba36790995300ab451c96a724a31da0266b7bfd32a16e288d8',
                                '0x82879f425e2cf26d35f11e8e72c7e805a25ae7ea80373a5e40aaad8fd81358f84cbd7c05faab4a6a30082c581113c7c00f8f4e773ab56366a22358d486f5cd295bfb6dc12830b39f81d1b485f162f20fff3649bb6d42c270485810c9fa7429a7fe1c835e11699c01d126d7498ba1e9ff1e53788f3112219732a68cd86d87124b',
                                '0x2d7529415c865a466401434461d661e9cf54741705c73ac71a541d16ddba7a7a23f5a8df87aef4a669216588ca3f5a25a133855c91b438fb9f2aac276f86480aad2d074de3d69168d33b3d385abe15f34252ef3af8fbd49444bb3658a578ed20d84637b8a2572ba3e17ba65bbba39c6c0a458c6b9f75f126ea3e8f412f75bc54')
    self.assertEqual(msg, 'You keep using that word. I do not think it means what you think it means.')

我尝试过中国剩余定理。没用。

def chinese_remainder_theorem(items):
        # Determine N, the product of all n_i
        N = 1
        for a, n in items:
            N *= n

        # Find the solution (mod N)
        result = 0
        for a, n in items:
            m = N // n
            r, s, d = extended_gcd(n, m)
            if d != 1:
                raise ("Input not pairwise co-prime")
            result += a * s * m

        # Make sure we return the canonical solution.
        return result % N

    def extended_gcd(a, b):
        x, y = 0, 1
        lastx, lasty = 1, 0

        while b:
            a, (q, b) = b, divmod(a, b)
            x, lastx = lastx - q * x, x
            y, lasty = lasty - q * y, y

        return (lastx, lasty, a)

    def mul_inv(a, b):
        b0 = b
        x0, x1 = 0, 1
        if b == 1:
            return 1
        while a > 1:
            q = a // b
            a, b = b, a % b
            x0, x1 = x1 - q * x0, x0
        if x1 < 0:
            x1 += b0
        return x1

    # Solve for m, which is an integer value, the line below will convert it to a string:

    C = int(chinese_remainder_theorem([(c_1, n_1), (c_2, n_2), (c_3, n_3)]))

    def nth_root(x, n):
        # Start with some reasonable bounds around the nth root.
        upper_bound = 1
        while upper_bound ** n <= x:
            upper_bound *= 2
        lower_bound = upper_bound // 2
        # Keep searching for a better result as long as the bounds make sense.
        while lower_bound < upper_bound:
            mid = (lower_bound + upper_bound) // 2
            mid_nth = mid ** n
            if lower_bound < mid and mid_nth < x:
                lower_bound = mid
            elif upper_bound > mid and mid_nth > x:
                upper_bound = mid
            else:
                # Found perfect nth root.
                return mid
        return mid + 1

    m = nth_root(C, 3)


    # Solve for m, which is an integer value, the line below will convert it to a string:
    msg = bytes.fromhex(hex(m).rstrip('L')[2:]).decode('UTF-8')
   
    return msg