RSA基础笔记

文章发布时间:

2023-09-08

最后更新时间:

2023-09-11

文章总字数:

1.5k

学crypto不长时间内遇到的题大多都是rsa相关的题目，打算直接来整理一下rsa的内容。

RSA介绍

RSA 加密算法是一种非对称加密算法。在公开密钥加密和电子商业中 RSA 被广泛使用。RSA 是 1977 年由罗纳德 · 李维斯特（Ron Rivest）、阿迪 · 萨莫尔（Adi Shamir）和伦纳德 · 阿德曼（Leonard Adleman）一起提出的。RSA 就是他们三人姓氏开头字母拼在一起组成的。

RSA 算法的可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。如今，只有短的 RSA 密钥才可能被强力方式解破。到 2017 年为止，还没有任何可靠的攻击 RSA 算法的方式。

基本原理

公钥与私钥的产生

1.随机选取两个不同大质数和，计算

2.根据欧拉函数，求得

3.选择一个小于的整数，使和互素。并求得模的逆元，命名为，有

4.将和的记录销毁

此时，是公钥，是私钥。

消息加密

首先需要将消息以一个双方约定好的格式转化为一个小于，且与互质的整数。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：

$m^e\equiv c\mod{N}$

消息解密

利用密钥进行解密。

$c^d\equiv m\mod{N}$

~~上述内容均来自CTFWiki~~

-example

from Crypto.Util.number import *

c = 30691232452128669052305371115180097177294479938026014749161868515829428425138132603996202260560122315012913870349336288842909273354993573489869530575104380833275595193605165300908452032408792329246901352615423312079849067596198536334364108820925409520915833013632159139929170333544966895214174663797058473253
p = 10271280551288472856987510413460997884890943068375125000031548270778287320402104925104706174892136963176424819840044521307032212563934575625497632478103881
q = 12360589907705437261666506204292999164487703125392652130810029273222342650377968792952840678684622841895717217508994994151976676085089006546199016112674981
e = 65537

N = p * q
phi = (p - 1) * (q - 1)
d = inverse(e, phi)
m = pow(c, d, N)

print(long_to_bytes(m))

常见题型

暴力分解N

-factor_signin(MoeCTF2023)

这题需要将两个N暴力分解，可以使用网站factordb、sagemath中输入ecm.factor(N)、yafu在命令行中输入.\yafu-x64.exe "factor(N)"

N分解后就可以计算phi(N)从而计算出flag

小公钥指数攻击

在特别小，比如时，可以使用小公钥指数攻击：

$c\equiv m^3\mod{N}$

则：

$m^3=c+k\times N\\ m=\sqrt[3]{c+k\times N}\\$

可以从小到大枚举，依次开三次根，直到开出整数为止。

-baby_e(MoeCTF2023)

本题很小，而且很大，在就能得出结果，即直接开的7次方根。

用sagemath计算：

1
2
3

x = var('x')
root = x^(1/7)
root(x = c)

e与phi不互素

在选取时要求其与互素，如果不互素就可以直接计算，如下例

-bad_E(MoeCTF2023)

虽然p,q,n,e都给出来了，但是直接尝试的时候会发现报错，这就是是计算d的时候e与phi不互素导致的出错。

计算p-1,q-1与e的公因数发现e是p-1的因数。

$m^e\equiv c\mod{n}\\ m^e\equiv c\mod{q}\\ m\equiv c^d\mod{q}\\ ed\equiv1\mod{q-1}$

所以

from Crypto.Util.number import *

q = ...
e = 65537
c = ...

d = inverse(e,q-1)

m = pow(c,d,q)

print(long_to_bytes(m))

模不互素

简单说就是存在两个公钥的N不互素，既然不互素，那就可以直接求最大公因数来分解N。

-rsa_signin(MoeCTF2023)

题目中一共有11组n，遍历能找到两组不互素。

共模攻击

同一个明文m，同一个模数n，使用两个不同的e分别加密得到两个密文，这就需要共模攻击。

$c_1\equiv m^{e_1}\mod{N}\\ c_2\equiv m^{e_2}\mod{N}\\$

利用扩展欧几里得算法算出的两个整数r和s

$\begin{align} c_1^r c_2^s &\equiv m^{re_1}m^{se_2}&\mod{N}\\ &\equiv m^{re_1+se_2}&\mod{N}\\ &\equiv m &\mod{N} \end{align}$

假如r是负数，就要计算，s同理。

-n&n(MoeCTF2023)

from Crypto.Util.number import *
from gmpy2 import gcdext

c1 = ...
c2 = ...
n = ...
e1 = 0x114514
e2 = 19198101

a, r, s = gcdext(e1, e2)

m = (pow(c1, r, n) * pow(inverse(c2, n), -s, n)) % n

print(long_to_bytes(m))

|p-q|较小

如果两个素数相差不大，那么就有方法可以分解。

$\frac{(p+q)^2}{4}-n=\frac{(p+q)^2}{4}-pq=\frac{(p-q)^2}{4}$

|p-q|较小，所以较小，进而只比N大一点，所以与接近。

顺序检查大于的每一个整数 x，直到找到一个 x 使得 x^2^ -n是平方数，记为 y^2^
那么 x^2^−n=y^2^，进而根据平方差公式即可分解 N

-|p-q|(MoeCTF2023)

from gmpy2 import isqrt,is_square

n = ...

sqrtn = isqrt(n)

tmp = sqrtn
while True:
    if is_square(pow(tmp,2)-n):
        x = tmp
        y = isqrt(pow(tmp,2)-n)
        break
    tmp += 1

print(f'p = {x-y}')
print(f'q = {x+y}')

p-1光滑/p+1光滑

p-1与p+1光滑分别使用Pollard’s p-1分解算法和William’s p+1分解算法。

Pollard’s p-1:

from gmpy2 import *

a = 2
k = 2
N = 
while True:
    a = powmod(a, k, N)
    res = gcd(a-1, N)
    if res != 1 and res != N:
        q = N // res
        print("p =",res)
        print("q =",q)
        break
    k += 1

William’s p+1:

直接使用primefac库中的williams_pp1

已知n与phi分解n

from Crypto.Util.number import isPrime
from gmpy2 import gcd
from random import randrange


def factorize_multi_prime(N, phi):
    """
    Recovers the prime factors from a modulus if Euler's totient is known.
    This method works for a modulus consisting of any number of primes, but is considerably be slower than factorize.
    More information: Hinek M. J., Low M. K., Teske E., "On Some Attacks on Multi-prime RSA" (Section 3)
    :param N: the modulus
    :param phi: Euler's totient, the order of the multiplicative group modulo N
    :return: a tuple containing the prime factors
    """
    prime_factors = set()
    factors = [N]
    while len(factors) > 0:
        # Element to factorize.
        N = factors[0]

        w = randrange(2, N - 1)
        i = 1
        while phi % (2 ** i) == 0:
            sqrt_1 = pow(w, phi // (2 ** i), N)
            if sqrt_1 > 1 and sqrt_1 != N - 1:
                # We can remove the element to factorize now, because we have a factorization.
                factors = factors[1:]

                p = gcd(N, sqrt_1 + 1)
                q = N // p

                if isPrime(p):
                    prime_factors.add(p)
                elif p > 1:
                    factors.append(p)

                if isPrime(q):
                    prime_factors.add(q)
                elif q > 1:
                    factors.append(q)

                # Continue in the outer loop
                break

            i += 1

    return tuple(prime_factors)

primes = []

N = ...
phiN = ...

for i in (factorize_multi_prime(N,phiN)):
    primes.append(int(i))

print(primes)

-factorize_me!(MoeCTF2023)

To be continued

≡