# picoCTF - Cryptography write-up
未寫：
* Medium
* Guess My Cheese (Part 1)
* Guess My Cheese (Part 2)
* Hard
* 幾乎全部._.
* miniRSA

# Easy
## hashcrack
> hash

:::spoiler 解法
這題顧名思義就是要爆破hash
會有三題，用 [crackstation.net](https://crackstation.net/) 就能爆破出每一個的原始密碼了

:::
## EVEN RSA CAN BE BROKEN???
> RSA

:::spoiler 解法
這題應該算蠻簡單的RSA題(?
用 https://factordb.com/ 把N拆成p跟q就可以計算出明文了

c = 19299563540855451833375009754826650975382561529126997079773420450916832233929657435014237118139938964518004372254135381599273364925167849041821593703164849
n = 23773590867200874106198285582257407523714159251112305729184555849807530218449302598642496077891109002150830742101075803806364925644119482175729605818717162
e= 65537


p = 2
q = n//2

phin = (p-1)*(q-1)

d = pow(e,-1,phin)
m = pow(c,d,n)
msg = hex(m)
msg = msg[2:]
msg = bytes.fromhex(msg)
print(msg)

:::
## interencdec
> base64、caesar

:::spoiler 解法
打開檔案之後會看到一串==結尾的字串 `YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclh6ZzJhMnd6TW1zeWZRPT0nCg==`
看到==猜是base64
解碼一次之後變成 `b'd3BqdkpBTXtqaGx6aHlfazNqeTl3YTNrXzg2a2wzMmsyfQ=='`
把b裡面的再解碼一次 `wpjvJAM{jhlzhy_k3jy9wa3k_86kl32k2}`
看到有大誇號而且字位數差不多，猜是凱薩
試各種位移量，找到開頭為picoCTF的就是答案
:::

## Mod 26
> ROT13

:::spoiler 解法
題目問說知道ROT13是什麼嗎
所以就把題目給的字串做位移，偏移量13，就是答案了:D
:::

## The Numbers
> ASCII、caesar

:::spoiler 解法
檔案打開是一張圖片，有一堆數字，用py把每個+65轉換成字符

s = [16,9,3,15,3,20,6]
x = [20,8,5,14,21,13,2,5,18,19,13,1,19,15,14]

for i in s:
        print(chr(65+i),end="")

print()
for i in x:
        print(chr(65+i),end="")

然後凱薩找到開頭為PICOCTF的就是答案!
:::

## 13
> ROT13

:::spoiler 解法
題目問ROT13
一樣偏移量13就是答案
:::

# Medium
## ReadMyCert
> CSR

:::spoiler 解法
這題給了CSR檔案
CSR是憑證簽署要求（Certificate Signing Request，CSR）
他是一個加密過的文字檔，其內容記載身份以及使用憑證的域名
我們可以用openssl來解碼這個CSR檔案
CN那欄就是這題的flag

:::
## Vigenere
> Vigenère Cipher

:::spoiler 解法
把message用key做Vigenère cipher解密就有flagㄌ

:::
## Easy1
> Vigenère Cipher

:::spoiler 解法
這題說給了the encrypted flag, key, and a table
打開table我思考了一下想說，這不是Vigenère cipher的表嗎
把UFJKXQZQUNB 用SOLVECRYPTO做解密就得到flag了 (記得加picoCTF)

:::
## HideToSee
> atbash cipher

:::spoiler 解法
這題給了一張圖片 上面寫了atbash cipher跟一個網址
對這張圖片進行各種分析，最後用steghide提取出了一個txt

打開是被加密過的flag
圖片上寫了是atbash cipher 做解密就好ㄌ

:::
## rotation
> caesar

:::spoiler 解法
找到picoCTF就是flag了

:::
## caesar
> caesar

:::spoiler 解法
用 https://theblob.org/rot.cgi 找到最不像亂碼那個

:::
## Crack the Power
> RSA

:::spoiler 解法
這題給了n、c、e的數值，可以發現他的e只有20，在RSA中太小的數值通常會是可以破解的點👀
上網找腳本就可以直接破解他了~
程式邏輯大概是因為e很小，如果m也沒有太大，m^e的數字就不會比n大太多，取模的次數不多
m^e=c+k * n 可以直接窮舉可能的k，得出來的e次方根是整數就是正確解

:::
## substitution0
> 字頻分析

:::spoiler 解法
丟https://quipqiup.com/ 就好ㄌ~

:::
## substitution1
> 字頻分析

:::spoiler 解法
丟https://quipqiup.com/ 就好ㄌ~

:::
## rsa_oracle
> RSA - Chosen plaintext attack

:::spoiler 解法
題目給了一個secret.enc跟password.enc還有一個能解密除了密碼以外的解密機器，提示說了可以用OpenSSL 來解密這個secret.enc，但是需要密碼
所以推測這題要用Chosen plaintext attack來破解出password
RSA的加密公式是 `c = m^e mod n` ，解密公式是` m = c^d mod n`
我現在要解的是` c (c = password^e)`，我們發送一個已知的明文( m=2 ) 獲得他加密後的c2 (c2=2^e)
然後將兩個相乘後拿去解密 ， 因為我們送入的 `c*c2 = (password*2)^e` ， 所以我們解密解出來的就是 password * 2
將他除2就是password了 ， 把他轉成ascii就是secret.enc的密碼了

:::

## Custom encryption
> xor

:::spoiler 解法
題目給了兩個檔案
一個裡面看起來是程式運行後的結果，有a、b、cipher
另一個是原py檔案
閱讀一下程式
理解出他是隨機a、b然後進行dynamic_xor_encrypt跟encrypt
現在我們有a、b就能算出key，做出解密程式就能得出原本的flag
先把key算出來:
然後先做encrypt的解密，把陣列全部除key*311

然後做dynamic_xor_encrypt的解碼，由xor的特性可知，我們只要將密文再做一次xor即可得到明文

組合成一個py檔執行後就能獲得flag!

:::
## C3

:::spoiler 解法
題目會給一個encoder程式跟一個密文，他的加密方法是每一個字元會根據他在lookup1中的位子與他上一個字元做差值，然後對應到lookup2的字元
寫個python來做解密，解出來會是一個python2的程式

這個程式會讀取input然後只有 i 等於 b³ 的時候會輸出
上面的# 有一個寫個selfinput，所以就把這個程式作為這個程式的輸入就是flag了

:::

## transposition-trial

:::spoiler 解法
依題意將字串分成三個一組，因為flag格式已知為picoCTF開頭
可判斷出順序為2 3 1

然後就寫一個python解決他

:::

## substitution2
> 字頻分析

:::spoiler 解法
這題一眼看去感覺很多重複的字母，而且拿去跑凱薩找不到正確flag
推測應該跟字頻分析有關，用解碼器來解!
我用的是[quipqiup.com](https://quipqiup.com/)
把密文跟已知(三個大寫字母是CTF)填進去然後讓他跑!就能解出正確的flag了

:::
## rail-fence
> Rail fence cipher

:::spoiler 解法
題目說了是Rail fence cipher而且rails是4
原本要自己寫程式但發現有點難就上網找了參考
大概就是按照⬊⬈先用`*`標記出在哪
然後再橫的填入文字
再依照⬊⬈去得出原文
:::
## morse-code
> morse code

:::spoiler 解法
題目給了一個音檔，標題說了是摩斯代碼
所以就上網找個解碼器就好了~我用的是這個[databorder.com](https://databorder.com/transfer/morse-sound-receiver/)
解好之後長這樣

記得加上picoCTF{}跟把空白換_還有大寫換成小寫就是flag了~
:::
## credstuff
> caesar

:::spoiler 解法
題目給了一個tar檔案
先進行解壓縮 tar xvf leak.tar
會獲得一個資料夾裡面有兩個檔案

我們要找到 cultiris 對照的密碼
因為太多了所以寫一個py腳本來進行搜尋

得到的結果是 cvpbPGS{P7e1S_54I35_71Z3} 看起來被進行過凱薩加密
進行解碼，偏移量為13
:::
## basic-mod1

:::spoiler 解法
題目給了一串數字，說了要怎麼解碼
按照他說的寫成py就好了

:::
## basic-mod2
:::spoiler 解法
這題要求的是跟41的模逆元
用py的pow可以求模逆元

:::
## spelling-quiz
> 字頻分析

:::spoiler 解法
這題給的py看起來就是在做單字母替換加密
所以我們可以用字頻分析暴力破解
但只有flag這個檔案的話不夠多分析不出來
所以我加上另一個檔案的前面幾行一起去做分析，成功解出正確的flag
加上picoCTF{}就是答案

:::

## Mini RSA
> RSA低指數攻擊

:::spoiler 解法
題目給了N、e、c
RSA的加密是`c = m^e mod n`，但現在e很小，所以我們可以找到一個最小的k使`c + n*k = m^e` ，然後對這個值取整數開 e 次方根，是整數的話就找到明文了
然後把m轉成hex再轉成bytes就有答案了
寫成py讓他跑就可以了

:::
## Mind your Ps and Qs
> RSA

:::spoiler 解法
題目給了c、n、e的值，因為n很小，所以可以直接用[factordb.com](https://factordb.com/) 分解他，就可以得到p跟q
然後就可以算出歐拉函數 `φ(n) = (p-1)(q-1)`
接下來就可以算出私鑰d，然後就可以解出明文了!

:::
## Dachshund Attacks
> RSA - Wiener’s attack

:::spoiler 解法
題目說了d很小，所以我上網查了RSA d極小 攻擊
找到一個叫Wiener’s attack
然後看到一大堆推論跟程式碼，將我們得到的n、e、c填入後運行python就能解出flag

:::

## New Caesar

:::spoiler 解法
這題給了加密的程式跟要解的密文
加密的邏輯是先做b16編碼，再把每位元依照key做位移，key的範圍是他有給的ALPHABET，而且key的長度都只有1，所以我們可以直接枚舉key來做解密
觀察每個結果，最不像亂碼的就是flag (記得加上picoCTF{})

:::
## No Padding, No Problem
:::spoiler 解法
這題題目跟你說他會幫你解出除了flag以外的密文
查了一下好像是某種常見題型
連線上之後他會給你n、e、c
這題的解題概念是運用乘法同態性 `( Enc(m1) * Enc(m2) ≡ Enc(m1 * m2) mod n )`
所以就是我們要創造一個`c' = (c * (r^e mod n)) mod n `，把這個 c' 丟給他解密，你就會拿到 m * r，然後你可以除以 r 得到原本的 m

:::
## Easy Peasy
> xor

:::spoiler 解法
這題nc連線後會給你一個加密過的flag還會讓你輸入字串，觀察一下加密程式，可以發現它會先用key與flag做xor。
然後它會從 key 的當前位置開始繼續做加密，如果長度超過 key 結尾，會從開頭補滿長度，已知key = cipher ^ plaintext。所以我們可以先輸入一個長度為50000-len(flag_enc)的字串再輸入一個長度為flag_enc的字串就能成功解出與flag做xor的key部份了
由於將近50000的長度有點難直接輸入進去，所以用python來解這題
解出來的結果直接加上picoCTF{}就是flag了

:::
## Pixelated
:::spoiler 解法
這題給了兩個圖片要進行疊合，寫一個python將兩個圖片疊成一個
會得到一個全灰的圖

用StegSolve就能找到flag

:::
## Mr-Worldwide
:::spoiler 解法
這題給了一堆一對一對的數字，結合標題是world，這些應該是經緯度
用google map查出每個的地點
再找英文的首字母就是flag了

:::

## waves over lambda
> 字頻分析

:::spoiler 解法
題目給了一段替換式加密過的密文，也沒說是用甚麼加密方法
直接丟字頻分析就找到flag了(這題flag沒有picoCTF的格式)

:::
## Flags
:::spoiler 解法
題目給了張圖，是一堆不同形狀跟顏色的正方形組成的
我原本還想說可能是國旗，結果找不到
最後直接以圖搜圖某一塊，搜出國際信號旗
有兩個對照不出來我直接分別再以圖搜圖一次發現兩個都是數字

:::

## Tapping
> morse code

:::spoiler 解法
這題會獲得一個看起來像摩斯電碼的東西
複製去 [morsecode.world](https://morsecode.world/international/translator.html) 做個解碼
得到的結果就是flag

:::
## john_pollard
> RSA

:::spoiler 解法
題述說有些RSA憑證可被破壞，提示1說flag格式是picoCTF{p,q}
檔案裡是一段X.509 憑證，裡面包含了RSA的公鑰，所以可以從中解出n跟e
寫個python就可以了，得到n之後去 [factordb.com](https://factordb.com/) 分解就能得到p和q了

:::
## la cifra de
> Vigenère Cipher

:::spoiler 解法
這題給了一串密文，但有點分辨不出他是甚麼加密方法
所以丟一小段到線上工具去識別看看，第一名是Vigenère Cipher，但他又沒有說他的key是甚麼
[guballa.de](https://www.guballa.de/vigenere-solver) 這個工具可以在沒有key的情況下破解Vigenère Cipher
得到的明文中就包含著flag

:::
# Hard
## Very Smooth
> RSA

:::spoiler 解法
這題是一題 RSA 密碼學題目，漏洞在於 p和 q都是smooth prime，也就是小質因數的乘積加一。
我們可以利用 p - 1與 q - 1的可分解性，使用 Python 的 pollard_pm1()函式來分解出 p跟 q。
求出 p和 q 之後，就能還原出 RSA 私鑰，再進一步解密出 flag。

:::
## triple-secure
> RSA

:::spoiler 解法
這題就是做了三次的RSA，因為他的模數共用質因數，所以可以透過gcd得到p、q、r
計算每層對應的 φ(n)，再算出每一次對應的d，從第三層開始往回推就能得到明文了

:::
## Play Nice
> Playfair Cipher

:::spoiler 解法
連線後會給一個alphabet跟加密過的文字，要解出明文
觀察一下題目給的py檔案
發現他的矩陣是6\*6，其他都跟Playfair Cipher的規則是一樣的
所以反著推回去就是答案了!
❗這題flag沒有picoCTF開頭，他給的直接就是flag了~

:::

## b00tl3gRSA2
> RSA

:::spoiler 解法
這題看標題就看的出來是一題RSA，先使用 nc 連線取得 n、e、c 三個參數
觀察後可以發現，這題的 e 不是常見的 65537，而是一個非常大的數字。根據 RSA 中 ed ≡ 1 mod φ(n) 的特性，當 e 很大時，d 就會相對很小。可以聯想到RSA常見的Wiener's Attack
Wiener's Attack 能在私鑰指數 d 很小的情況下，透過 continued fraction 解出 d，進而解密密文取得明文。
可以參考 CryptoHack 的說明與攻擊腳本：
🔗 [cryptohack.gitbook.io](https://cryptohack.gitbook.io/cryptobook/untitled/low-private-component-attacks/wieners-attack)
只需要將腳本中的 n、e、c 換成本題給的參數，並安裝套件 owiener（pip install owiener），就能成功跑出 d 並解出 flag。

:::