信息安全数学拓展-单素数RSA

数论基础在密码学的应用举例

拿2024BaseCTF 的babyrsa举例：

题目

python
from Crypto.Util.number import *

flag=b'BaseCTF{}'
m=bytes_to_long(flag)

n=getPrime(1024)
e=65537
c=pow(m,e,n)

print("n =",n)
print("e =",e)
print("c =",c)
"""
n = 104183228088542215832586853960545770129432455017084922666863784677429101830081296092160577385504119992684465370064078111180392569428724567004127219404823572026223436862745730173139986492602477713885542326870467400963852118869315846751389455454901156056052615838896369328997848311481063843872424140860836988323
e = 65537
c = 82196463059676486575535008370915456813185183463924294571176174789532397479953946434034716719910791511862636560490018194366403813871056990901867869218620209108897605739690399997114809024111921392073218916312505618204406951839504667533298180440796183056408632017397568390899568498216649685642586091862054119832
"""

单素数RSA是基于RSA算法的一个简化版本，其中使用的密钥只涉及一个素数。
单素数RSA的一个主要特点是它简化了密钥的生成过程，因为只需要找到一个大素数，而不是两个。然而，这也意味着它可能比双素数RSA（传统的RSA算法）更不安全，因为攻击者只需要找到一个素数就可以破解密钥。因此，单素数RSA在实际应用中并不常见，它更多的是作为一个理论概念或者在某些特定的、对安全性要求不高的场景中使用。

在这题中，被加密的信息是字节数据m，为了对其进行加密，将m转换为大整数。
随机生成1024位大质数n作为密钥，选择与n互质的素数e作为公钥进行加密。
题目给出了大质数n，公钥，被加密数据。要求计算出私钥并对其进行解密。

题解：

python
from Crypto.Util.number import *
import gmpy2
n = 104183228088542215832586853960545770129432455017084922666863784677429101830081296092160577385504119992684465370064078111180392569428724567004127219404823572026223436862745730173139986492602477713885542326870467400963852118869315846751389455454901156056052615838896369328997848311481063843872424140860836988323
e = 65537
c = 82196463059676486575535008370915456813185183463924294571176174789532397479953946434034716719910791511862636560490018194366403813871056990901867869218620209108897605739690399997114809024111921392073218916312505618204406951839504667533298180440796183056408632017397568390899568498216649685642586091862054119832

phin = n-1
d = gmpy2.invert(e, phin)
m = pow(c, d, n)
print(long_to_bytes(m))
#b'BaseCTF{7d7c90ae-1127-4170-9e0d-d796efcd305b}'

理解这个题解有两个个关键点：

$\mathbf{欧拉函数的性质：若p为素数，则\phi(p)=p-1}\newline \mathbf{e\times d=1\space mod(\space \phi(n))}\newline$ $\mathbf{已知c=m^e\space(mod\space n)如何反解m？}\newline \mathbf{已知：a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \mathbf{\implies c\equiv m^{e\space (mod \space \phi(n))}\space (mod \space n)} \mathbf{设整数d，m\equiv c^x\space (mod \space n)}\newline \mathbf{\implies m^{e\space (mod \space \phi(n))} \equiv c^{x\times e \space (mod\space \phi(m))} \equiv c}\newline \mathbf{要使上式成立，d必须满足是e在模\phi(n)意义下的逆元，即e\times d=1\space mod(\space \phi(n))}$ $\mathbf{证明：a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \mathbf{若b<\phi(m)：显然成立}\newline \mathbf{若b>=\phi(m)：}\newline \mathbf{b=n\phi(m)+k}\newline \mathbf{k=b(mod(\phi(m)))}\newline \mathbf{a^b\equiv a^{n\phi(m)+k}\equiv a^{n\phi(m)}\times a^{k}\space (mod\space m)}\newline \mathbf{a^{\phi(m)}\equiv1 \space (mod\space m) \space\space[欧拉定理]}\newline \mathbf{a^{n\phi(m)}\equiv1 \space (mod\space m)}\newline \mathbf{\implies a^{b}\equiv a^k\space (mod\space m)}\newline \mathbf{\implies a^b\equiv a^{b(mod\space\phi(m))} \space(mod \space m)}\newline \space \newline$