---
tags: 網頁設計社 109
---
# 網頁設計社 課前預習 Crypto
[TOC]
## ROT-3
`ROT-X` 通常指的是明文(Plain Text) 經過 `Caesar` 加密位移 X 的這個過程
所以 `ROT-3` 就是明文往後移 3 位 `ABC` -> `DEF`
所以題目給的是往後移 3 位的結果
那就往後移 23 位 (等於往前移 3 位) 的方式還原明文
可以使用線上工具 [Online Caesar Solver](https://www.dcode.fr/caesar-cipher)
Cipher Text : `IODJ{i1U57_7Ub_0i_fUbs70}`
Plain Text : `FLAG{f1R57_7Ry_0f_cRyp70}`
## ROT-13
原理等同上面 只是 `ROT-13` 常會被獨立拉出來講
一個明文經過兩次 `ROT-13` 一樣等於明文
因為 `13 + 13 == 26`
所以用同樣的工具解即可
Cipher Text : `SYNT{13_1f_3dh4Y_70_3_1a_E07!?!?}`
Plain Text : `FLAG{13_1s_3qu4L_70_3_1n_R07!?!?}`
## ROT-47
普通的 `ROT-1` ~ `ROT-26` 基本上都是將單位限制在字母
```
ABCDEFGHIJKLMNOPQRSTUVWXYZ
abcdefghijklmnopqrstuvwxyz
```
`ROT-47` 則是增加了其他的單位
```
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNO
PQRSTUVWXYZ[\]^_\`abcdefghijklmnopqrstuvwxyz{|}~
```
但是 ROT-47 已經不再是位移的加密法了 而是有自己固定的表
所以不會存在 Key 的問題
`ABC` 經過 ROT-47 必定是 `pqr`
`pqr` 經過 ROT-47 必定是 `ABC`
[Online ROT-47 Solver](https://www.dcode.fr/rot-47-cipher)
Cipher Text : ```u{pvL~z04cb$cC0$bC:tD0xd0f@_0bcdJN```
Plain Text : `FLAG{OK_c43S4r_S3riEs_I5_7o0_345y}`
## Substitution Cipher (替換式密碼)
Substitution 就跟他名字一樣
會將某個字全部改成另外一個字
可是通常我們不會拿到所謂的 AlphaBet
這時候就要透過 `詞頻分析(Frequency Analysis)` 去猜測哪個字轉換成哪個字
不過詞頻分析必須在足夠多文字的狀況下準確率才會高
[Online Substition Solver](https://www.guballa.de/substitution-solver)
## RSA
RSA 通常會產一個質數 p 跟質數 q
並且 $p * q$ 產生 N
生成一個公鑰 e
明文為 M
$C = M ^{e}\ mod\ N$
這樣就生成了密文 C
如果要解密
則需要先將 N 分解 為 p q
並且產生 N 的 phi
$\phi(N) = (p - 1) * (q - 1)$
這時候要生成私鑰 d
$e d \equiv 1\ mod\ \phi(N)$
$\rightarrow (e * d)\ mod\ (p - 1) * (q - 1) = 1$
$\rightarrow d \equiv e ^ {\phi(N)^ {-1}}$
所以 d 為 e 在 mod $\phi(N)$ 下的模反元素
反解密文就是 $M = C^{d}\ mod\ N$
### EZ
:::spoiler 題目生成腳本
```python=
from Crypto.Util.number import getPrime , bytes_to_long
from gmpy2 import invert
p = getPrime(300)
q = getPrime(300)
n = p * q
e = 65537
d = invert(e , phi)
flag = "<CENSORED>"
m = bytes_to_long(flag)
c = pow(m , e , n)
print("d = {}\nn = {}\nc = {}".format(d , n , c))
```
:::
這題已經給了 c d n
所以照著最上面的做法做就好
:::spoiler Solve
```python=
from Crypto.Util.number import long_to_bytes
d = 1344939239776366990935622463961489359140452856321101516248708348578875896102438797450331586598999829539928031430749836055341616561771081285548126081116282354929872955174989209125377
n = 2471907649257495189997977716659490945369562478117562119871882860530982937990507921602512235774768141756158636840136723491042834034904344968108565557024434327520349498588752709967189
c = 819215704696949569378048307065024357817709672340647740001167828559855162549632702602380242339988471062471053844009762193707843808932617292741534009610491063461280050418643276060343
print(long_to_bytes(pow(c , d , n)))
```
:::
Plain Text : `FLAG{RSA_15_tO()_EZZZZZZZZZZZZZZZZZZZZZ}`
### Medium
:::spoiler 題目生成腳本
```python=
from Crypto.Util.number import getPrime , bytes_to_long
p = getPrime(200)
q = getPrime(200)
n = p * q
e = 65537
flag = "<CENSORED>"
m = bytes_to_long(flag)
c = pow(m , e , n)
print("c = {}\ne = {}\nn = {}".format(c , e , n))
```
:::
這次只有給 c e n 了
所以需要自行分解 n 去計算 $\phi(N)$ 接著算 d
我們可以透過 factorDB 去尋找已知的分解結果
把 n 丟上去就會看到這個 n 剛好有結果
:::spoiler Solve
```python=
from gmpy2 import invert
from Crypto.Util.number import long_to_bytes
c = 1746556679338870404898027611524787577185747794969695663566697818653136706087741777676885930621912564690645654197639142252
e = 65537
n = 1891069273714264626402743793841358723166679597286337462645411575494175032702564905530101985949449542560475109474409423001
p = 1312638725457843296441325087628683365692505445859637479943363
q = n // p
phi = (p - 1) * (q - 1)
d = invert(e , phi) # e 在模 phi(n) 下的模反
m = pow(c , d , n)
flag = long_to_bytes(m)
print(flag)
```
:::
Plain Text : `FLAG{A_L1tTl3_H4rD_w1th_0n1y_c_e_n}`
RSA 還有很多可以玩的 像是 `Padding Oracle` , `Known High Bit` ...
不過這些都要有很好的數學基礎
如果想要了解上面的計算過程
可以去看
> 費馬小定理
> 擴展歐幾里得
> 其他現代數論
因為我不知道你們課程中間上了啥 所以我就隨便寫
然後你們社長說想要有 HomeWork
所以那題我會在一個禮拜後寫解答
請先不要互相討論
## HomeWork
:::spoiler 完整題目生成腳本
```python=
from Crypto.Util.number import getPrime , bytes_to_long
flag = "<CENSORED>"
m = bytes_to_long(flag)
p = getPrime(500)
q1 = getPrime(500)
q2 = getPrime(500)
e = 0x10001
n1 = p * q1
n2 = p * q2
c1 = pow(m , e , n1)
c2 = pow(m , e , n2)
print("e = {}".format(e))
print("n1 = {}\nc1 = {}".format(n1 , c1))
print("n2 = {}\nc2 = {}".format(n2 , c2))
```
:::
我們先觀察一下內容
先把 `flag` 轉成數值的型態
接著 `getPrime` 生成 3 個 500 bit 的質數
`n1 = p * q1`
`n2 = p * q2`
這題攻擊點還滿明顯的
因為這次數值沒有辦法在 `factorDB` 上找到分解結果 (因為我沒上傳
所以直接像 `Medium` 硬解是不行的
不果可以觀察到 `n1` 跟 `n2` 共用了 p 這個質數
這就導致可以用輾轉相除法 直接得出 p
```python
p = gcd(n1 , n2)
```
這樣我們就能夠直接求出 `q1` 跟 `q2`
```python
q1 = n1 // p
q2 = n2 // p
```
然後選擇其中一項解即可
:::spoiler Solve
```python=
#!/usr/bin/python3
#!/usr/bin/python3
from Crypto.Util.number import long_to_bytes , GCD as gcd , inverse
e = 65537
n1 = 6068861093630746873768044688355298853083933009151961959188398961991863662151040864023339960011762462716389408933643989595286625007357793284214976356220021947194167010841038712605936232976686304351806381912214526638889234734932206094279579468712928780599596867762144892875118061985287887022646785837931
c1 = 3037342385739340367945904507379234973270735346973053423827283532096686615043623553094270264773951241329919873680487591181900409596948892088978158885683349009824512337304501764385989949839227854473143867071614764567958934212454211569051348678228551927885263001839701881982410839250993400652882230084374
n2 = 5342614899878968582043167026416417823904513647814239187008523122799106581332751539182555882626616040374365092831435269204997935976083420121296343605521759051815011705404929317993638111725882462301884186561624155889947445993847694026184453321304168163893381032745245492630042587897319519455229019629677
c2 = 4892329037617392667911100636460358752067797545427681944944031663995636089331976974525766744337299190728976024830034200179220287873870550272911108078586491953686309057949022354733449281629082848435441476115806898250285872623607409488277068004805238437982434359757500505773657567770686411309217984543755
p = gcd(n1 , n2)
q1 = n1 // p
q2 = n2 // p
d1 = inverse(e , (p - 1) * (q1 - 1))
d2 = inverse(e , (p - 1) * (q2 - 1))
m1 = pow(c1 , d1 , n1)
m2 = pow(c2 , d2 , n2)
print(long_to_bytes(m1).decode("utf-8"))
print(long_to_bytes(m2).decode("utf-8"))
```
:::
Sign in with Wallet
Connect another wallet