[XCTF] Normal_RSA

RSA

某著名非对称加密算法

计算过程

首先随机取两个非常大的质数, $p$ 和 $q$ , 并且 $p$ 和 $q$ 不能相等, 计算 $N= p \times q$
根据欧拉函数, 求得 $r = \phi(N) = \phi(p) \times \phi(q) = (p - 1)(q - 1)$
选择一个小于 $\phi(N)$ 的整数 $e$ , 使 $e$ 与 $e$ 互质. 并求得 $e$ 关于 $r$ 的模逆元, 取名为 $d$ ( $ed \equiv 1 (\mod r)$ )
销毁 $p$ 和 $q$

其中得到的 $(N, e)$ 是公钥, $(N, d)$ 是私钥

攻击弱 RSA 公钥

XCTF: NO.GFSJ0528 Normal_RSA(在adworld.xctf.org.cn/challenges/list, 需要自己搜索)

题目给出一个公钥和一个加密后的文件, 需要根据公钥获得私钥.
瞅眼公钥文件的信息

openssl rsa -pubin -text -in public.pem

输出

Public-Key: (256 bit)
Modulus:
    00:c2:63:6a:e5:c3:d8:e4:3f:fb:97:ab:09:02:8f:
    1a:ac:6c:0b:f6:cd:3d:70:eb:ca:28:1b:ff:e9:7f:
    be:30:dd
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMJjauXD2OQ/+5erCQKPGqxsC/bNPXDr
yigb/+l/vjDdAgMBAAE=
-----END PUBLIC KEY-----

只有 256 位, 可以直接暴力(目前公认比较安全的 rsa 至少需要 2048 位)

首先根据 rsa 公钥计算出 $N$ :

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa


with open("public.pem", "rb") as f:
    public_key = serialization.load_pem_public_key(f.read())

    n = public_key.public_numbers().n
    e = public_key.public_numbers().e
    print(f"n: {n}, e: {e}")

有了 $N$ 之后还需要把他分解为两个质数, 使用factordb.com快速分解, 得到两个整数275127860351348928173285174381581152299 和 319576316814478949870590164193048041239

有了这两个质数之后, 就可以计算私钥指数 $\phi(N)$ 了.

p = 275127860351348928173285174381581152299
q = 319576316814478949870590164193048041239

phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
print(f"d: {d}")

在 python 中可以直接使用pow(N, -1, MOD)的方式来求逆元, 写起来很简单(不然还要写快速幂, 用费马小定理求值), 第三个参数则是取模.

最后使用上面得到的所有参数生成私钥即可

private_numbers = rsa.RSAPrivateNumbers(
    p=p,
    q=q,
    d=d,
    dmp1=d % (p - 1),
    dmq1=d % (q - 1),
    iqmp=pow(q, -1, p),
    public_numbers=rsa.RSAPublicNumbers(
        e=e,
        n=n,
    ),
)
private_key = private_numbers.private_key()

# write private key to a file
key = private_key.private_bytes(
    encoding=serialization.Encoding.PEM,
    format=serialization.PrivateFormat.PKCS8,
    encryption_algorithm=serialization.NoEncryption(),
)
with open("private.key", "wb") as f:
    f.write(key)
    print(f"Private key written to private.key")

最后, 先来检查一下生成的公钥是否与私钥匹配
先使用openssl从私钥生成一个新的公钥:

openssl rsa -in private.key -pubout > new_public.pem

然后看看有什么不同:

diff public.pem new_public.pem

输出为空, 两个文件的内容完全一致, 也就是说我们的私钥是匹配的
接下来就可以直接解密文件的内容了

openssl pkeyutl -decrypt -inkey private.key -in flag.enc

输出

PCTF{256b_i5_m3dium}

成功拿到 flag

附上完整代码:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives.asymmetric import rsa


with open("public.pem", "rb") as f:
    public_key = serialization.load_pem_public_key(f.read())

    n = public_key.public_numbers().n
    e = public_key.public_numbers().e
    print(f"n: {n}, e: {e}")

    p = 275127860351348928173285174381581152299
    q = 319576316814478949870590164193048041239

    phi = (p - 1) * (q - 1)
    d = pow(e, -1, phi)
    print(f"d: {d}")

    private_numbers = rsa.RSAPrivateNumbers(
        p=p,
        q=q,
        d=d,
        dmp1=d % (p - 1),
        dmq1=d % (q - 1),
        iqmp=pow(q, -1, p),
        public_numbers=rsa.RSAPublicNumbers(
            e=e,
            n=n,
        ),
    )
    private_key = private_numbers.private_key()

    # write private key to a file
    key = private_key.private_bytes(
        encoding=serialization.Encoding.PEM,
        format=serialization.PrivateFormat.PKCS8,
        encryption_algorithm=serialization.NoEncryption(),
    )
    with open("private.key", "wb") as f:
        f.write(key)
        print(f"Private key written to private.key")

很简单吧, ~~现在试试自己设计一个属于自己的加密算法吧~~

另, 《关于我不会 Reverse, 所以把游戏玩通关了这件事》(GFSJ0487 game)

游戏通关