What is RSA？

RSA 是一種非對稱加密演算法，加密和解密使用的是不同的金鑰，其安全性基於大數分解的困難性，主要應用於數據加密、數字簽名與身份驗證等。

• 公鑰：用作加密，任何人都可以使用。
• 私鑰：用作解密，僅持有的人才能解密。

RSA 加密的基本原理

• 密鑰生成：
  1. 選擇兩個大質數 𝑝 和 𝑞，計算其乘積 𝑛 = 𝑝 × 𝑞，𝑛 被稱為公開模數。
  2. 計算 𝜙(𝑛)=(𝑝−1)×(𝑞−1)，這是 Euler 函數。
  3. 選擇一個與 𝜙(𝑛) 互質的數 𝑒 作為公鑰指數，常見的 𝑒 是 3、17 或 65537。
  4. 計算私鑰指數 𝑑，滿足 𝑑×𝑒 ≡ 1(mod𝜙(𝑛))。
• 加密：
  1. 將要加密的訊息轉換為一串數字 𝑚，滿足 0 ≤ 𝑚 < 𝑛。
  2. 使用公鑰（𝑛,𝑒）進行加密，計算密文 𝑐 = 𝑚^𝑒 mod 𝑛。
• 解密：
  1. 使用私鑰（𝑛,𝑑）來解密，計算原始消息 𝑚 = 𝑐^𝑑 mod 𝑛。

安全性

RSA 的安全性依賴於大數分解的困難性，即使知道公開的模數 𝑛 和指數 𝑒，在沒有私鑰 𝑑 的情況下，想要從 𝑛 推算出 𝑝 和 𝑞 是極其困難的。如果能夠高效地進行質因數分解，RSA 就會被破解。因此，質數 𝑝 和 𝑞 必須足夠大，通常至少是 2048 位以上的數字。

RSA 加密在實際應用中雖然安全，但相比對稱加密速度較慢，因此多數應用中會將其與對稱加密算法結合，以提高性能和效率。

那一樣開始進行我們今天的 Lab

Lab_1 - Mini RSA

題目已知 e, n 跟密文 c。
提示說告訴我們 (M ** e) is just barely larger than N，看來就是低加密指數攻擊了。當密文 𝑀^𝑒 只比 n 大一點時，嘗試加上多個 n 的倍數 𝑖∗n 來找到合適的 𝑀^𝑒。

加密時 c = m^e mod n，反推回去 i x n + c = m^e。編寫以下腳本，執行後即可成功取得 flag。以下是解題程式碼。

n = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3
c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146919581675891411119628108546342758721287307471723093546788074479139848242227243523617899178070097350912870635303707113283010669418774091018728233471491573736725568575532635111164176010070788796616348740261987121152288917179932230769893513971774137615028741237163693178359120276497700812698199245070488892892209716639870702721110338285426338729911942926177029934906215716407021792856449586278849142522957603215285531263079546937443583905937777298337318454706096366106704204777777913076793265584075700215822263709126228246232640662350759018119501368721990988895700497330256765579153834824063344973587990533626156498797388821484630786016515988383280196865544019939739447062641481267899176504155482

import gmpy2

for i in range(1, 100000):
    m, exact = gmpy2.iroot(c + i * n, e)
    if exact:
        # print(m)
        print(bytes.fromhex(hex(m)[2:]).decode())
        break

Lab_2 - Mind your Ps and Qs

一樣題目有給 c, n 跟 e，不一樣的是這次 e 變大了。先看看能不能拆出 n 的質因數，使用 FactorDB() 這個函數，找出 p 跟 q。我們就能夠算出明文 m，再將明文使用 long_to_bytes() 函數轉為字串後就是 flag 啦~

c = 964354128913912393938480857590969826308054462950561875638492039363373779803642185
n = 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e = 65537 

from Crypto.Util.number import long_to_bytes
from factordb.factordb import FactorDB

# 使用 FactorDB 找出 n 的因數 p, q
f = FactorDB(n)
f.connect()
factors = f.get_factor_list()
p = factors[0]
q = factors[1]
print(p, q)

# phi 是 n 的歐拉函數
phi = (p - 1) * (q - 1)
# d 為 e 在 mod phi 下的反元素
d = pow(e, -1, phi)
# m 為 c 的 d 次方在 mod n 下的結果
m = pow(c, d, n)
print(long_to_bytes(m))

今天的練習就到這邊，以下是參考資料，請搭配服用：

wiki RSA 加密演算法
RSA 演算法
RSA 加密與解密

內文如有錯誤，還請不吝指教~