CryptoHack "INTRODUCTION TO CRYPTOHACK"

# はじめに
CTFのCryptoにとてもとても興味があるので，有名な常設CTFである[CryptoHack](https://cryptohack.org/)を始めました．

なお，以下のような人間が書いています．

* Pythonの教養があまりない
* ガチガチのCTF初心者

質のいい解説ではなく，半分くらい備忘録で書いているのでご了承ください．
間違っている箇所があれば，指摘していただけると嬉しいです．

あと，後々の問題で"byte"と書いているもの，これ多分ASCIIコードのことです．

# ASCII
ASCIIは，7桁の2進数（0000000~1111111）で表すことのできる整数値（0~127）に対して，大小のラテン文字や数字，英文でよく使われる約物などを割り当てた文字コードです．
![ASCII.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/e4b3c274-0db8-9bc5-b2aa-f6cfa9e67fce.png)
この問題では，
`[99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]`
が与えられるので，それぞれの整数値を対応する文字に変換します．

人力でやってもいいのですが，いかんせんめんどくさいのでコードを書いてプログラムにやらせます．
組み込み関数 `chr()` を使用することで，ASCIIコードを文字に変換することが可能です．
ただし，**一文字ずつしか変換できない**ので，for文をうまく使って出力してあげましょう．
```python
flag = [99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]

for i in flag:
    print(chr(i), end = '')
```
上記のコードを実行すると，flagとして `crypto{ASCII_pr1nt4bl3}` が得られます．


余談として，ASCIIに関する他の簡単な解説等には「1byteで英数字・記号を表現する」と書いてあります．
この場合，「1byte = 8bit」であるので，8桁の2進数を利用して表現していることになります．

> ASCIIは，7桁の2進数（0000000~1111111）で表すことのできる整数値（0~127）に対して，大小のラテン文字や数字，英文でよく使われる約物などを割り当てた文字コードです．

さっきの説明と矛盾しますね．これは，ASCIIコードが**7桁で英数字・記号を表現しており，最後の1桁を「パリティビット(parity bit)」に割り当てているため**です．

パリティビットについての説明は，省略します．以下のサイト等を参考にするといいかもです．
[パリティビットとは - 「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典](https://wa3.i-3-i.info/word16601.html)

# Hex
![Hex.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/a71db30c-159b-c3af-7e6a-f2ce803f4b95.png)
何かしら暗号化を行うとき，暗号文は普通はASCIIコードではないbyteを持つそうです．（なるほど？）

暗号化されたデータを共有したい場合は，異なるシステム間で移植可能なものにエンコード（変換）するのが一般的だそうです．（なるほど）

文章より，今回は16進数でflagがエンコードされているようです．
なので，byteにデコード（逆変換）してあげましょう．組み込み関数の`bytes.fromhex()`を使用します．
```python
flag = '63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d'

print(bytes.fromhex(flag))
```
上記のコードを実行すると，flagとして `crypto{You_will_be_working_with_hex_strings_a_lot}` が得られます．

# Base64
base64は，全てのデータをアルファベット(a~z, A~z)と数字(0~9)，一部の記号(+,/)の**64文字**で表すエンコード方式のことです．（64進数っていうのかな？）
base64については，以下の記事がわかりやすかったです．
[base64ってなんぞ？？理解のために実装してみた - Qiita](https://qiita.com/PlanetMeron/items/2905e2d0aa7fe46a36d4)

![Base64.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/1e2ff7fd-4e39-d4a5-eda1-e6fc9b1c95a1.png)
文章より，16進数をbyteにデコードし，base64にエンコードするとflagを入手できるようです．
今回は`base64`ライブラリ内にある，`base64.b64encode()`を使用します．
```python
import base64

flag = '72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf'
print(base64.b64encode(bytes.fromhex(flag)))
```
上記のコードを実行すると，flagとして `crypto/Base+64+Encoding+is+Web+Safe/` が得られます．

# Bytes and Big Integers
文字の数値変換のお話の様です．
![Bytes_and_Big_Intengers.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/fd447eb1-8908-d4a1-3e2a-bbf71a883825.png)
RSA等の暗号は数字で表現されていますが，文章等は文字で表現されています．
そのため，文章等を暗号化し、数学的演算処理を行うにはどうしたらいいかの説明ですね．

一般的には，文章のbyteを16進数に変換し，連結する手法がとられるそうです．10進数でも表現可能とかなんとか．

与えられた文字列は，どこからどう見ても（多分）10進数ですかね...
なので，byteに変換してあげましょう．`PyCryptodome`ライブラリ内の関数`long_to_bytes()`を使います．
```python
from Crypto.Util.number import *

flag = 11515195063862318899931685488813747395775516287289682636499965282714637259206269
print(long_to_bytes(flag))
```
上記のコードを実行すると，flagとして `crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}` が得られます．

# XOR Starter
この問題から，XOR（排他的論理和）を扱っていきます．
XORは，**2つの入力の片方が真でもう片方が偽の時に真となり，両方とも真あるいは偽の時は偽となる**論理演算のことを指します．論理演算のORの真偽が入れ替わったものですね．

もっとわかりやすく言うと，「**2つのうち1つだけ正しければOK，両方とも正しいか両方とも間違っていたらダメ**」みたいな感じですかね．
以下のサイトがオススメです．同じようなたとえ書いてました．
[排他的論理和（XOR）- 「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典](https://wa3.i-3-i.info/word11664.html)
![XOR_Starter.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/c8e2b5a7-2806-44da-f506-701ab908cd2a.png)
文章では，"label"を13でXORするように言われているので，言われたとおりにします．

XORするときは，`pwntools`ライブラリ内の関数`xor()`がとても便利です．推しです．
だって，データ形式が違っても文字列の長さが違っても，演算してくれるもん．
```python
from pwn import xor

key1 = 'label'
key2 = 13
flag = xor(key1, key2)

print('crypto{{{}}}'.format(flag.decode()))
```
上記のコードを実行すると，flagとして `crypto{aloha}` が得られます．

# XOR Properties
XORの演算の性質についての問題ですね．代数的性質がﾁﾗﾁﾗっとうかがえます．
![XOR_Properties.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/33de553a-897d-0a4b-f651-eae09ac809b2.png)
1\. 可換である．
```math
A \oplus B = B \oplus A
```
2\. 結合的である．
```math
A \oplus \left(B \oplus C \right) = \left(A \oplus B\right) \oplus C
```
3\. 中立元を持つ．
```math
A \oplus 0 = A
```
4\. 自己逆元を持つ．
```math
A \oplus A = 0
```
こう，なんというか，加算や乗算と似たような性質を感じますね．
というわけで，上記の性質を使ってflagを求めます．流れとしては
```math
(KEY2 \oplus KEY1) \oplus KEY1 = KEY2\\
(KEY3 \oplus KEY2) \oplus KEY2 = KEY3\\
(FLAG \oplus KEY1 \oplus KEY2 \oplus KEY3) \oplus KEY1 \oplus KEY2 \oplus KEY3 = FLAG
```
といった感じです．（長い）

実装すると，以下のようになります．
```python
from pwn import xor

key1 = 'a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313'
KEY1 = bytes.fromhex(key1)
key12 = '37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e'
KEY12 = bytes.fromhex(key12)
key23 = 'c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1'
KEY23 = bytes.fromhex(key23)
flag123= '04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf'
FLAG123 = bytes.fromhex(flag123)

KEY2 = xor(KEY1, KEY12)
KEY3 = xor(KEY2, KEY23)
FLAG = xor(FLAG123, KEY1, KEY2, KEY3)

flag = FLAG.decode()
print(flag)
```
上記のコードを実行すると，flagとして `crypto{x0r_i5_ass0c1at1v3}` が得られます．

# Favourite byte
![Favorite_byte.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/3308d957-e781-82fc-8ec1-d3ae942f2522.png)
問題文を読んでみると，

>I've hidden some data using XOR with a single byte, but that byte is a secret.
（1byteとXORしてデータを隠したけど，どのbyteを使ったかは秘密☆）

らしいので，8桁の2進数のどれかが正解のkeyです．
でも，0~255のどれかを一発で当てるのは困難というか，もはやエスパー．
そこで，for文を使って愚直に全探索します．

なお，0~255の間で全探索するため，大量の文字列・記号が出力されます．
そのため．if文を使って形式に当てはまる文字列だけを表示するようにしています．
```python
from pwn import xor

key = '73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d'
KEY = bytes.fromhex(key)

for i in range(256):
    flag = (xor(KEY, i)).decode()
    if flag[:7] == 'crypto{': #大量に文字が出るため，形式を満たしたflagのみ抽出
        print(flag)
```
上記のコードを実行すると，flagとして `crypto{0x10_15_my_f4v0ur173_by7e}` が得られます．

# You either know, XOR you don't
INSTRODUCTION TO CRYPTOHACKの中で，一番難しいというか**厄介**な問題です．
![you_know_either.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/688041/bd5817e8-e023-0810-47b1-c2e2a1aa3b5f.png)
今までは，XORする際に使用した秘密鍵が与えられていましたが，この問題では

> "I've encrypted the flag with my secret key, you'll never be able to guess it."
（私の秘密鍵でflagを暗号化したから，絶対推測できないぜﾊｯﾊｰ．）

と書いてあるため，**秘密鍵が明示的に与えられていません**．ここで結構頭を抱えました，ハゲそう．

ただし，下のヒントを見てみると

> Remember the flag format and how it might help you in this challenge
（flagの形式を覚えておくと，この問題で何か役立つかもね！！）

と言っているので，flagのテンプレ（？）である `crypto{}` が，何か使えそうです．

手が止まっていては何もできません，物は試しです．与えられた文字列 `0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104` と `crypto{}` でXORしてみます．
```python
from pwn import xor

data = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104')
part_key = xor(data, 'crypto{}'.encode())
print(part_key)
```
上記のコードを実行すると，結果として
`b'myXORke5hTX\x0fS[Uj>|~zH4kCFTX\x0fS[Uj>|~\x0eR[*hbv'`
が出力されます．

出力結果の冒頭7文字に注目すると `myXORke` となっており，これから秘密鍵が `myXORkey` であることが推測されます．何か使えそう，嬉しみですね．

得られた秘密鍵と与えられた文字列をXORすることで，flagを入手することができます．
```python
from pwn import xor

data = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104')
#part_key = xor(data, 'crypto{}'.encode())
#print(part_key)
flag = xor(data, 'myXORkey'.encode())
print(flag)
```
上記のコードを実行すると，結果として `b'crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}'` が出力され，
flagが `crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}` であることがわかります．

# おわりに
やってみた感じだと，どうもPythonが基礎教養として必要なようですね．
PyCrryptodomeとpwntoolsは，pythonにプリインストールされていないので，入れる必要アリです．
いや，最後にそれを書くなや．

"You either know, XOR you don't" が，個人的に一番厄介でした．いや，flagの形式がkeyの一部とか．わからんて．

次は，めちゃくちゃ数学な問題が出されるらしいです．（問題をﾁﾗｯと見た）
私、数学苦手なんだよなぁ...でも，暗号技術系を学ぶのに必要と思えば，仲良く...仲良く...なれそうにないです...