defexgcd(m, n, x=0, y=0): if n == 0: x = 1 y = 0 return (m, x, y) a1 = b = 1 a = b1 = 0 c = m d = n q = int(c / d) r = c % d while r: c = d d = r t = a1 a1 = a a = t - q * a t = b1 b1 = b b = t - q * b q = int(c / d) r = c % d x = a y = b return x
defquick_algorithm(a, b, c): a = a % c ans = 1 while b != 0: if b & 1: ans = (ans * a) % c b >>= 1 a = (a * a) % c return ans
# 假设p,q是下面的数字 p = 2147483647 q = 524287
n = p * q
phi_n = (p - 1) * (q - 1) # 因为e一般是65537,但是也可以指定符合要求的e值 e = 17 d = 0 d = exgcd(e, phi_n) print(d)
运行代码,输出:132458307156089
XAYUTCTF{132458307156089}
Do you know rsa’s key?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
import base64 from Crypto.PublicKey import RSA from Crypto.Cipher import PKCS1_v1_5
data = "kZXHviP8yVEdvuZG7nDfEKXfKMW2E0h0f0oSTyEwNX5Ju67ETr+zKqP9w2swTlF17qi2zP14hJY3/jOBNmBCt64LR6N8OPLHV1DqIVlnbub9danFLaupNNvVofZRTIeGMnI+RJ9BdvEfHjimSsZMm0nRPeQ3I2IA/tMxA/EakMvh7pGPcN+fnbITBWWI9ukWqqxofsaOlfECU8QkG+P1svVz8pi8xpIaN+3Dn0Y7khG1ybPckavnSmY1UO9rIbS98Y3ujQfQnkvCCbKJ06L7eWxX8mhBXFd2169e1BnQKLHres5MqWg1LHMlDIRFy+23RWU13PW8tfGaVe1NwftGoA==" withopen("rsa_private_key.pem", 'r') as fp: # 读取私钥 pri_key = fp.read() # 加载私钥对象 rsa_key = RSA.importKey(pri_key) # 构建解密器 rsa = PKCS1_v1_5.new(rsa_key) # 进行数据解密,解密前需要现将base64进行解码; result = rsa.decrypt(base64.b64decode(data), None) print(result.decode("utf-8"))