西电网安实验班 现代密码学 实验四
西电网安实验班 现代密码学 实验三
题目一Project Euler RSA Encryption Problem 182链接：https://projecteuler.net/problem=182RSA 有可能存在加密但没有加密的情况。起初遍历所有可能的消息并逐个加密来计算 unconsealed messages count。后来发现有以下公式：$$ N = (1 + \gcd(e-1, p-1)) \times (1 + \gcd(e-1, q-1)) $$from gmpy2 import gcd p = 1009 q = 3643 phi = (p - 1) * (q - 1) min_unconcealed = p * q candidates = [] for e in range(3, phi, 2): if gcd(e, phi) != 1: continue count = (1 + gcd(e - 1, p - 1)) * (1 + gcd(e - 1, q - 1)) if count < min_unconcealed: min_unconcealed = count candidates = [e] elif count == min_unconcealed: candidates.append(e) print(f"min_unconcealed: {min_unconcealed}") print("e:", end=" ") for e in candidates[:50]: print(f'{e} ', end='') print()题目二Implement RSA链接：https://www.cryptopals.com/sets/5/challenges/39只是实现一个简单的 RSA，要求手写 exgcd 和 modinv，那就手写吧。from gmpy2 import next_prime, powmod from secrets import randbits from Crypto.Util.number import bytes_to_long def gcd(a, b): while b != 0: a, b = b, a % b return a def ex_gcd(a, b): if b == 0: return 1, 0 else: x1, y1 = ex_gcd(b, a % b) x = y1 y = x1 - (a // b) * y1 return x, y def inverse(a, m): x, _ = ex_gcd(a, m) return (x % m + m) % m e = 3 while True: p = next_prime(randbits(64)) q = next_prime(randbits(64)) n = p * q phi = (p - 1) * (q - 1) if gcd(e, phi) == 1: break m = bytes_to_long(b'pwnerik.cn') assert 0 <= m < n c = powmod(m, e, n) d = inverse(e, phi) msg = powmod(c, d, n) assert m == msg这个实现有很多问题，例如 e、p、q 太小。