RSA加解密实战（CTF）

这个实战题目来源于我参加的某海外CTF比赛原题，由于这个题目相较于一般的 RSA 加密方式有些许差别，个人感觉比较有趣且不难懂，于是拿来分享。

对于 RSA 加密的基本认识

一、什么是 RSA 加密算法

        RSA 加密是一种非对称加密方式，使用2种密钥分别对数据进行加解密：

                a、公钥：用于数据的加密，可以公开共享

                b、私钥：用于数据的解密，需要妥善保管，不能泄露

        公钥只能用于加密数据，私钥只能用于解密数据，二者不可更换使用，即用公钥加密的数据只能使用对应的私钥进行解密，反之亦然。

二、RSA 加密的数学基础

        RSA算法的核心是大数运算和模运算，基于数论中的一些性质：

                a、大素数的生成：选择两个大素数 p 和 q

                b、模数 n 的计算： n=p×q

                c、欧拉函数 φ(n)： φ(n)=(p−1)×(q−1)

                d、选择加密指数 e： e 与 φ(n) 互质，通常选择 e=65537，可以带来较好的计算效率

                e、计算解密指数 d：d 是 e 关于 φ(n) 的模逆元素，即满足 e⋅d≡1 mod  φ(n)

三、密钥生成步骤

        1、选择两个大素数 p 和 q，计算 n=p×q

        2、计算 φ(n)=(p−1)×(q−1) 

        3、选择一个整数 e，满足 1<e<φ(n)且 gcd(e,φ(n))=1

        4、计算 e 的模逆 d，即 e⋅d≡1mod  φ(n)

        5、公钥为 (n,e)，私钥为 (n,d)

四、加密过程

要加密的明文消息 m 转换为整数 m 且 0≤m<n，加密得到的密文 c 计算如下：

五、解密过程

接收到密文 ccc 后，解密计算如下：

题目分享与解析

首先题目的线索是直接给了一个关于 RSA 密钥生成和加解密的 python 源码，需要对这串代码进行简要分析：

# getPrime用于生成指定位数的质数
# bytes_to_long 用于将字节序列转化为长整型数字
# long_to_bytes 用于将长整型数字转化为字节序列
# FLAG_GAMGAM 定义在 flag 模块中的常量，通常时需要加密的字符串
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from flags import FLAG_GAMGAM

#生成密钥
def gen_key():
    p = getPrime(4096)   #生成一个4096位的大素数
    n = 2*p         #公钥的模数n
    e = 65537       #常用公钥指数e=65535
    #一般来说RSA的模数是两个大素数的乘积 n = p * q , 根据欧拉函数可得 φ(n) = φ(p) * φ(q) = (p-1)*(q-1)，又因为n=2p，所以 φ(n) = p-1
    phi_n = (p - 1)  
    #计算私钥指数d
    d = pow(e, -1, phi_n)

	#返回公钥和私钥
    return (n, e), (n, d)

#定义加密函数，接收整型明文 pt 和公钥，并返回一个加密后的整型密文
def encrypt(pt: int, pub_key: (int, int)) -> int:
    n, e = pub_key
    return pow(pt, e, n)


#定义解密函数，接收整型密文 ct 和私钥，并返回一个解密后的整型明文
def decrypt(ct: int, priv_key: (int, int)) -> int:
    n, d = priv_key
    return pow(ct, d, n)


#转化明文，方便后续的 RSA 加密
pt = bytes_to_long(FLAG_GAMGAM)
#生成公钥和私钥
pub, priv = gen_key()

#加密得到密文
ct = encrypt(pt, pub)

print(pub)  #输出公钥（n，e）
print(ct)   #输出密文 ct

""" output : 
pub = (1187036881143255678002463758823328059054967286304079946698830107983054756455116137560640360907617090768892222200232769013898086641365526920365941657223719909608623612364565491394396836689005779953582737606769612044152900984410189797945160970640233269434857215156707188226644140186233117418578999649675501923158500973527860820476774162258056088176836933971626651722297419469001832141393303687831763041541298637984981484605886538085054999743028130034186150375954369138007688335922353720290223733062752735362640330007395278113210621407774253326748367183647916542260385241849328645829055161868897760626313462053770486741600871918596910274170809764858924373557759944088849747488101309508664734646761762412297919300985341470183672896494363089287897564003884864937477882116184866139314943820121458541671053111784924614354354051278861337795171453392846554516472806170955424094756390970572454084554064299959563385403753982420758416150497980281277588694172034437436874006653172021381177623273333042379989422646166480734410913148567193586525237775287519085811109666011917375279015787726665088346364963313941503929463975682736763812440239892582271133388552728034109040233071519106207594592661468817905961569517921007110971395505830618097714478302, 65537)
ct = 795807804195143453698199351714341881491007858193124317249991960343873442402330541927355975462857321435938754440321580174443331666641181625664069405050964566344381744709294110771870536802353007022271867378658681771017152652337537847752445300535171488167996282441962543976576696465573991060306807268553659109840313328518099780850408480656440234846473549017585724141302898515099966486748289860601838615696366759534875502563433987281076478746704673766615604679732113066945172837918782569635525478298453073137252252807049842035005266808708242245205256476149494296039430508531375107451338401537609064664390446408507706477965483671800993119312002909135270398571898844908643483215653937390863031730605961379386046951618745731912613235578147115643378764728145934422515365821994913473759604466504627671738552946527189180057717976411101700962342930065732023681381389942592202841123754672836935980227561011259880242223658584675417448037977336301973044247690228389495603711704632306639520856078639797104835378636642939190389932673963835980987694812947833691746134338765367684261289851826492260573430796933048931658801423183863572727478714738535956082504958502080116828296338104460121704114347331800007862970894127699814246457589160922514051314061
"""

一、对于“phi_n = (p - 1)”的补充说明

        1、欧拉函数φ(n)的定义
                欧拉函数 φ(n) 是指在小于 n 的正整数中，与 n 互质的数的个数

        2、欧拉函数性质
                a、若 n 为质数，那么φ(n)=n-1
                b、乘法性质：
                        若两个数 a、b 互质，则φ(a * b)=φ(a) * φ(b)

        根据上述定义和性质，可得：
        因为两个质数 p、q 一定互质，且 n=p*q
        所以 φ(n)=φ(p * q)=φ(p) * φ(q) = (p-1) * (q-1)

        因为n=2p 且2与p互质，所以 φ(n) = φ(2 * p) = φ(2) * φ(p)
        根据：
                a、φ(2)=1，因为小于 2 且与 2 互质的数只有 1
                b、φ(p)=p−1，因为 p 是素数，所有小于 p 的数都与 p 互质

        得出结论：
                φ(n) = φ(2) * φ(p) = 1*(p-1) = p-1

二、具体解析

        这个RSA加密的实现并没有使用传统的 n=p*q，而是利用 ”根据n=2p，使得 φ(n)=p-1” 这一公钥生成方式，这就是我开头说的 “与一般的 RSA 加密方式的些许差别 ”，即公钥的生成。

        根据以上的分析，整理解题思路:
                1、求解p：由于`n=2p`，因此`p=n/2`
                2、求解d：因为`p=n/2`，可以得到`φ(n)=p−1`，根据代码`d = pow(e, -1, phi_n)`，可以得到私钥指数d
                3、解密：得到 d 后，使用 RSA 解密公式 `pt=ct^d  mod  n`还原明文。
                4、回转字符串：最后，使用 `long_to_bytes(pt)` 将整数明文转换回原始 FLAG 的字符串形式

用于解密的python代码：

from Crypto.Util.number import long_to_bytes

# 已知的公钥 n 和密文 ct
n = 1187036881143255678002463758823328059054967286304079946698830107983054756455116137560640360907617090768892222200232769013898086641365526920365941657223719909608623612364565491394396836689005779953582737606769612044152900984410189797945160970640233269434857215156707188226644140186233117418578999649675501923158500973527860820476774162258056088176836933971626651722297419469001832141393303687831763041541298637984981484605886538085054999743028130034186150375954369138007688335922353720290223733062752735362640330007395278113210621407774253326748367183647916542260385241849328645829055161868897760626313462053770486741600871918596910274170809764858924373557759944088849747488101309508664734646761762412297919300985341470183672896494363089287897564003884864937477882116184866139314943820121458541671053111784924614354354051278861337795171453392846554516472806170955424094756390970572454084554064299959563385403753982420758416150497980281277588694172034437436874006653172021381177623273333042379989422646166480734410913148567193586525237775287519085811109666011917375279015787726665088346364963313941503929463975682736763812440239892582271133388552728034109040233071519106207594592661468817905961569517921007110971395505830618097714478302
e = 65537
ct = 795807804195143453698199351714341881491007858193124317249991960343873442402330541927355975462857321435938754440321580174443331666641181625664069405050964566344381744709294110771870536802353007022271867378658681771017152652337537847752445300535171488167996282441962543976576696465573991060306807268553659109840313328518099780850408480656440234846473549017585724141302898515099966486748289860601838615696366759534875502563433987281076478746704673766615604679732113066945172837918782569635525478298453073137252252807049842035005266808708242245205256476149494296039430508531375107451338401537609064664390446408507706477965483671800993119312002909135270398571898844908643483215653937390863031730605961379386046951618745731912613235578147115643378764728145934422515365821994913473759604466504627671738552946527189180057717976411101700962342930065732023681381389942592202841123754672836935980227561011259880242223658584675417448037977336301973044247690228389495603711704632306639520856078639797104835378636642939190389932673963835980987694812947833691746134338765367684261289851826492260573430796933048931658801423183863572727478714738535956082504958502080116828296338104460121704114347331800007862970894127699814246457589160922514051314061

# Step 1: 计算 p 和 phi_n
p = n // 2
phi_n = p - 1

# Step 2: 计算 d
d = pow(e, -1, phi_n)

# Step 3: 解密密文
pt = pow(ct, d, n)

# Step 4: 转换为字符串
flag = long_to_bytes(pt)
#根据要求的 flag 形式输出完整的flag
print(f"4T{{{flag.decode()}}}")

三、结果

        最后成功拿到 flag：