網頁設計社 課前預習 Crypto

• 網頁設計社 課前預習 Crypto
  • ROT-3
  • ROT-13
  • ROT-47
  • Substitution Cipher (替換式密碼)
  • RSA
    • EZ
    • Medium
  • HomeWork

ROT-3

ROT-X 通常指的是明文(Plain Text) 經過 Caesar 加密位移 X 的這個過程

所以 ROT-3 就是明文往後移 3 位 ABC -> DEF
所以題目給的是往後移 3 位的結果
那就往後移 23 位 (等於往前移 3 位) 的方式還原明文

可以使用線上工具 Online Caesar Solver

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

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

RSA

RSA 通常會產一個質數 p 跟質數 q
並且

$p\ast q$ 產生 N
生成一個公鑰 e
明文為 M

$C=M^{e}modN$

這樣就生成了密文 C

如果要解密

則需要先將 N 分解 為 p q
並且產生 N 的 phi

$\varphi (N)=(p-1)\ast (q-1)$

這時候要生成私鑰 d

$ed\equiv 1mod\varphi (N)$

$\to (e\ast d)mod(p-1)\ast (q-1)=1$

$\to d\equiv e^{\varphi (N{)}^{-1}}$

所以 d 為 e 在 mod

$\varphi (N)$ 下的模反元素

反解密文就是

$M=C^{d}modN$

EZ

題目生成腳本

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
所以照著最上面的做法做就好

Solve

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

題目生成腳本

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 去計算

$\varphi (N)$ 接著算 d

我們可以透過 factorDB 去尋找已知的分解結果

把 n 丟上去就會看到這個 n 剛好有結果

Solve

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

完整題目生成腳本

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

p = gcd(n1 , n2)

這樣我們就能夠直接求出 q1 跟 q2

q1 = n1 // p
q2 = n2 // p

然後選擇其中一項解即可

Solve

#!/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"))