RSA 挑战 - 利用 GCD 寻找私钥

这道 RSA 挑战题给出了一个公钥和密文，但私钥被隐藏了。需要利用提供的提示（GCD）来恢复私钥并解密密文。

代码中包含以下几个关键部分：

1. gen() 函数: 生成 RSA 密钥对和一个提示。

2. pad() 函数: 对 flag 进行填充。

3. bytes_to_long() 函数: 将字节串转换为整数，需要你填写实现。

4. 生成密文: 使用公钥对 flag 进行加密。

5. 提示: hint = gmpy2.gcd(E, phi)，其中 E 是公钥的一部分，phi 是欧拉函数的值。

提示: 利用 GCD 的性质，可以找到 E 和 phi 的公因子，从而帮助你恢复私钥 d。

解决步骤:

1. 理解提示: GCD 指的是最大公约数。提示 hint = gmpy2.gcd(E, phi) 告诉我们 E 和 phi 有一个共同的因子。

2. 恢复私钥: 由于 phi 可以被 hint 整除，我们可以尝试用 phi 除以 hint，得到一个更小的数。然后，尝试使用欧拉定理的逆运算，根据 e 和这个更小的数来恢复 d。

3. 解密密文: 使用恢复的私钥 d 对密文进行解密，得到 flag。

代码示例:

import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag


def pad(s, l):
    return s + os.urandom(l - len(s))


def gen():
    g = getPrime(8)
    while True:
        p = g * random.getrandbits(138) + 1
        if isPrime(p):
            break
    while True:
        q = g * random.getrandbits(138) + 1
        if isPrime(q):
            break
    N = p ** 5 * q
    phi = p ** 4 * (p - 1) * (q - 1)
    d = random.getrandbits(256)
    e = inverse(d, phi)
    E = e * g
    hint = gmpy2.gcd(E, phi)
    return N, E, hint


flag = pad(flag, 64)


def bytes_to_long(flag):
    return int.from_bytes(flag, 'big')


m = bytes_to_long(flag)
n, e, hint = gen()
c = pow(m, e, n)
print(f'hint = {hint}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
hint = 251
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162

通过理解提示和代码，你应该能够成功解密密文并获得 flag。 祝你好运！