RSA 介紹¶

RSA 加密算法是一種非對稱加密算法。在公開密鑰加密和電子商業中 RSA 被廣泛使用。RSA 是 1977 年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

RSA 算法的可靠性由極大整數因數分解的難度決定。換言之，對一極大整數做因數分解愈困難，RSA 算法愈可靠。假如有人找到一種快速因數分解的算法的話，那麼用 RSA 加密的信息的可靠性就肯定會極度下降。但找到這樣的算法的可能性是非常小的。如今，只有短的 RSA 密鑰纔可能被強力方式解破。到 2017 年爲止，還沒有任何可靠的攻擊 RSA 算法的方式。

基本原理¶

公鑰與私鑰的產生¶

隨機選擇兩個不同大質數 $p$ 和 $q$ ，計算 $N = p \times q$
根據歐拉函數，求得 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$
選擇一個小於 $\varphi (N)$ 的整數 $e$ ，使 $e$ 和 $\varphi (N)$ 互質。並求得 $e$ 關於 $\varphi (N)$ 的模反元素，命名爲 $d$ ，有 $ed\equiv 1 \pmod {\varphi (N)}$
將 $p$ 和 $q$ 的記錄銷燬

此時， $(N,e)$ 是公鑰， $(N,d)$ 是私鑰。

消息加密¶

首先需要將消息以一個雙方約定好的格式轉化爲一個小於 $N$ ，且與 $N$ 互質的整數 $m$ 。如果消息太長，可以將消息分爲幾段，這也就是我們所說的塊加密，後對於每一部分利用如下公式加密：

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

消息解密¶

利用密鑰 $d$ 進行解密。

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

正確性證明¶

即我們要證 $m^{ed} \equiv m \bmod N$ ，已知 $ed \equiv 1 \bmod \phi(N)$ ，那麼 $ed=k\phi(N)+1$ ，即需要證明

$m^{k\phi(N)+1} \equiv m \bmod N$

這裏我們分兩種情況證明

第一種情況 $gcd(m,N)=1$ ，那麼 $m^{\phi(N)} \equiv 1 \bmod N$ ，因此原式成立。

第二種情況 $gcd(m,N)\neq 1$ ，那麼 $m$ 必然是 $p$ 或者 $q$ 的倍數，並且 $n=m$ 小於 $N$ 。我們假設

$m=xp$

那麼 $x$ 必然小於 $q$ ，又由於 $q$ 是素數。那麼

$m^{\phi(q)} \equiv 1 \bmod q$

進而

$m^{k\phi(N)}=m^{k(p-1)(q-1)}=(m^{\phi(q)})^{k(p-1)} \equiv 1 \bmod q$

那麼

$m^{k\phi(N)+1}=m+uqm$

進而

$m^{k\phi(N)+1}=m+uqxp=m+uxN$

所以原式成立。

基本工具¶

RSAtool¶

安裝

git clone https://github.com/ius/rsatool.git
cd rsatool
python rsatool.py -h

生成私鑰

python rsatool.py -f PEM -o private.pem -p 1234567 -q 7654321

RSA Converter¶

根據給定密鑰對，生成 pem 文件
根據 $n$ ， $e$ ， $d$ 得出 $p$ ， $q$

openssl¶

查看公鑰文件

openssl rsa -pubin -in pubkey.pem -text -modulus

解密

rsautl -decrypt -inkey private.pem -in flag.enc -out flag

更加具體的細節請參考 openssl --help。

分解整數工具¶

網站分解，factor.db
命令行分解，factordb-pycli，借用 factordb 數據庫。
yafu

python 庫¶

primefac¶

整數分解庫，包含了很多整數分解的算法。

gmpy¶

gmpy.root(a, b)，返回一個元組 (x, y)，其中 x 爲 a 開 b 次方的值，y 是判斷 x 是否爲整數的布爾型變量

gmpy2¶

安裝時，可能會需要自己另行安裝 mpfr 與 mpc 庫。

gmpy2.iroot(a, b)，類似於 gmpy.root(a,b)

pycrypto¶

安裝
```
sudo pip install pycrypto
```

使用

import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5

msg = 'crypto here'
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
privatekey = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
key = PKCS1_v1_5.new(pubkey)
enc = key.encrypt(msg).encode('base64')
key = PKCS1_v1_5.new(privatekey)
msg = key.decrypt(enc.decode('base64'), e)

Jarvis OJ - Basic - veryeasyRSA¶

p = 3487583947589437589237958723892346254777 q = 8767867843568934765983476584376578389

e = 65537

求 d =

請提交 PCTF{d}

直接根據 $ed\equiv 1 \pmod{\varphi (N)}$ ，其中 $\varphi (N)=\varphi (p)\varphi (q)=(p-1)(q-1)$ ，可得 $d$ 。

import gmpy2
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
phin = (p - 1) * (q - 1)
print gmpy2.invert(e, phin)

➜  Jarvis OJ-Basic-veryeasyRSA git:(master) ✗ python exp.py       
19178568796155560423675975774142829153827883709027717723363077606260717434369

2018 CodeGate CTF Rsababy¶

程序就是一個簡單的 RSA，不過程序還生成了兩個奇怪的數

e = 65537
n = p * q
pi_n = (p-1)*(q-1)
d = mulinv(e, pi_n)
h = (d+p)^(d-p)
g = d*(p-0xdeadbeef)

所以，問題應該出自這裏，所以我們就從此下手，不放這裏先假設 const = 0xdeadbeef。那麼

$eg = ed * (p-const)$

進而，根據 RSA 可知

$2^{eg}=2^{ed * (p-const)}=2^{p-const} \pmod n$

$2^{p-const} * 2^{const-1} = 2^{p-1} \pmod n$

所以

$2^{p-1} = 2^{eg} * 2^{const-1}+kn$

而與此同時根據費馬小定理，我們知道

$2^{p-1} \equiv 1 \pmod p$

所以

$p|2^{p-1}-1 | 2^{eg+const-1}-1+kn$

進而

$p|2^{eg+const-1}-1$

所以

$p|gcd(2^{eg+const-1}-1,n)$

因此，代碼如下

tmp = gmpy2.powmod(2,e*g+const-1,n)-1
p = gmpy2.gcd(tmp,n)
q = n/p
phin = (p-1)*(q-1)
d =gmpy2.invert(e,phin)
plain = gmpy2.powmod(data,d,n)
print hex(plain)[2:].decode('hex')

2018 國家安全周 pure math¶

題目的基本描述是這個樣子的

1) p ** p % q = 1137973316343089029387365135250835133803975869258714714790597743585251681751361684698632609164883988455302237641489036138661596754239799122081528662395492
2) q ** q % p = 6901383184477756324584651464895743132603115552606852729050186289748558760692261058141015199261946483809004373728135568483701274908717004197776113227815323
3) (p ** q + q ** p) % (p*q) = 16791287391494893024031688699360885996180880807427715700800644759680986120242383930558410147341340225420991368114858791447699399702390358184412301644459406
4) (p+q) ** (p+q) % (p*q) = 63112211860889153729003401381621068190906433969243079543438386686621389392583849748240273643614258173423474299387234175508649197780206757067354426424570586101908571600743792328163163458500138799976944702155779196849585083397395750018148652864158388247163109077215394538930498877175474225571393901460434679279
5) FLAG ** 31337 % (p*q) = 6931243291746179589612148118911670244427928875888377273917973305632621316868302667641610838193899081089153471883271406133321321416064760200919958612671379845738048938060512995550639898688604592620908415248701721672948126507753670027043162669545932921683579001870526727737212722417683610956855529996310258030
Now, what’s the FLAG???

我們的目的基本上就是求得 FLAG，那麼怎麼做呢?這個題目需要我們具有較好的數論功底。

根據題目中這樣的內容，我們可以假設 $p$ ， $q$ 都是大素數，那麼

$p^{q-1} \equiv 1\bmod q$

那麼

$p^{q} \equiv p \bmod pq$

那麼我們可以根據 3）知道

$p^q+q^p \equiv p+q \bmod pq$

而 $p+q$ 又顯然小於 $pq$ ，所以我們就知道 $p+q$ 的數值。

進一步，我們假設1），2），3），4），5）對應的值分別爲 $x_1$ , $x_2$ , $x_3$ , $x_4$ , $x_5$ 則

根據4），我們可以知道

$(p+q)^{p+q} \equiv p^{p+q}+q^{p+q} \bmod pq$

又因爲1）和 2），則

$p^pp \equiv px_1\bmod pq$

$q^qq \equiv qx_2 \bmod pq$

因此

$px_1+qx_2 \equiv x_4 \bmod pq$

根據 $x_1$ 和 $x_2$ 的求得方式，我們可以知道這裏也是等號，因此我們得到了一個二元一次方程組，直接求解即可。

import gmpy2
x1 = 1137973316343089029387365135250835133803975869258714714790597743585251681751361684698632609164883988455302237641489036138661596754239799122081528662395492
x2 = 6901383184477756324584651464895743132603115552606852729050186289748558760692261058141015199261946483809004373728135568483701274908717004197776113227815323
p_q = 16791287391494893024031688699360885996180880807427715700800644759680986120242383930558410147341340225420991368114858791447699399702390358184412301644459406
x4 = 63112211860889153729003401381621068190906433969243079543438386686621389392583849748240273643614258173423474299387234175508649197780206757067354426424570586101908571600743792328163163458500138799976944702155779196849585083397395750018148652864158388247163109077215394538930498877175474225571393901460434679279

if (x4 - x1 * p_q) % (x2 - x1) == 0:
    print 'True'
q = (x4 - x1 * p_q) / (x2 - x1)
print q
p = p_q - q

c = 6931243291746179589612148118911670244427928875888377273917973305632621316868302667641610838193899081089153471883271406133321321416064760200919958612671379845738048938060512995550639898688604592620908415248701721672948126507753670027043162669545932921683579001870526727737212722417683610956855529996310258030

phin = (p - 1) * (q - 1)
d = gmpy2.invert(31337, phin)
flag = gmpy2.powmod(c, d, p * q)
flag = hex(flag)[2:]
print flag.decode('hex')

flag 如下

➜  2018-國家安全周第一場-puremath git:(master) ✗ python exp.py
True
7635093784603905632817000902311635311970645531806863592697496927519352405158721310359124595712780726701027634372170535318453656286180828724079479352052417
flag{6a66b8d5-6047-4299-a48e-4c4d1f874d12}

2018 Pwnhub LHY¶

首先分析這段代碼

assert gmpy.is_prime(y)**2016 + gmpy.is_prime(x + 1)**2017 + (
    (x**2 - 1)**2 % (2 * x * y - 1) + 2
)**2018 == 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

由於 gmpy.is_prime 要麼返回1，要麼返回 0，所以我們可以很容易地試出來 y 是素數，x+1 也是素數，並且

$(x^2-1)^2\equiv 0 \bmod (2xy-1)$

爲了式子能夠整除，猜測 $x=2y$ 。

於是，對於下面的內容

p = gmpy.next_prime(x**3 + y**3)
q = gmpy.next_prime(x**2 * y + y**2 * x)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy.invert(0x10001, phi)
enc = pow(bytes_to_long(flag), 0x10001, n)
print 'n =', n
print 'enc =', enc

$p$ 和 $q$ 自然爲

$p=next\_prime(9y^3)$

$q=next\_prime(6y^3)$

根據素數的間隔，可以知道 $p$ 和 $q$ 最多比括號裏的數字大一點，這裏一般不會超過 $1000$ 。

那麼

$n \geq 54y^6$

所以我們知道了 $y$ 的上界，而對於 $y$ 的下界其實也不會離上界太遠，我們大概減個幾十萬。進而，我們利用二分查找的方式來尋找 $p$ 和 $q$ ，如下

import gmpy2
tmp = 30097557298197417800049182668952226601954645169633891463401117760245367082644152355564014438095421962150109895432272944128252155287648477680131934943095113263121691874508742328500559321036238322775864636883202538152031804102118831278605474474352011895348919417742923873371980983336517409056008233804190890418285814476821890492630167665485823056526646050928460488168341721716361299816947722947465808004305806687049198633489997459201469227952552870291934919760829984421958853221330987033580524592596407485826446284220272614663464267135596497185086055090126893989371261962903295313304735911034185619611156742146

print gmpy2.iroot(tmp, 2018)
print gmpy2.iroot(tmp - 1, 2018)

print gmpy2.iroot(tmp - 2, 2018)

n = 260272753019642842691231717156206014402348296256668058656902033827190888150939144319270903947159599144884859205368557385941127216969379550487700198771513118894125094678559478972591331182960004648132846372455712958337042783083099376871113795475285658106058675217077803768944674144803250791799957440111855021945690877200606577646234107957498370758707097662736662439460472126493593605957225541979181422479704018055731221681621886820626215670393536343427267329350730257979042198593215747542270975288047196483958369426727778580292311145109908665004662296440533724591193527886702374790526322791818523938910660223971454070731594803459613066617828657725704376475527288174777197739360634209448477565044519733575375490101670974499385760735451471034271880800081246883157088501597655371430353965493264345172541221268942926210055390568364981514774743693528424196241142665685211916330254113610598390909248626686397970038848966187547231199741

y = 191904757378974300059526915134037747982760255307942501070454569331878491189601823952845623286161325306079772871025816081849039036850918375408172174102720702781463514549851887084613000000L
y = gmpy2.next_prime(y)

enc = 73933313646416156737449236838459526871566017180178176765840447023088664788672323530940171469589918772272559607026808711216932468486201094786991159096267208480969757088208089800600731106685561375522764783335332964711981392251568543122418192877756299395774738176188452197889668610818741062203831272066261677731889616150485770623945568369493256759711422067551058418926344060504112146971937651406886327429318390247733970549845424064244469193626197360072341969574784310397213033860597822010667926563087858301337091484951760613299203587677078666096526093414014637559237148644939541419075479462431789925219269815364529507771308181435591670281081465439913711912925412078002618729159141400730636976744132429329651487292506365655834202469178066850282850374067239317928012461993443785247524500680257923687511378073703423047348824611101206633407452837948194591695712958510124436821151767823443033286425729473563002691262316964646014201612

end = gmpy2.iroot(n / 54, 6)[0]
beg = end - 2000000

mid = 1
while beg < end:
    mid = (beg + end) / 2
    if gmpy2.is_prime(mid) != 1:
        mid = gmpy2.next_prime(mid)
    p = gmpy2.next_prime(9 * mid**3)
    q = gmpy2.next_prime(6 * mid**3)
    n1 = p * q
    if n1 == n:
        print p, q
        phin = (p - 1) * (q - 1)
        d = gmpy2.invert(0x10001, phin)
        m = gmpy2.powmod(enc, d, n)
        print hex(m)[2:].strip('L').decode('hex')
        print 'ok'
        exit(0)
    elif n1 < n:
        beg = mid
    else:
        end = mid
    print beg, end