题目一

Project Euler RSA Encryption Problem 182

链接：https://projecteuler.net/problem=182

RSA 有可能存在加密但没有加密的情况。

起初遍历所有可能的消息并逐个加密来计算 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 太小。