---
# System prepended metadata

title: Cryptography
tags: [pwn.college]

---

# Cryptography

### XOR
就是xor
![image](https://hackmd.io/_uploads/BkRwau4kee.png)

### XORing ASCII Strings
可以使用`strxor`來對字串進行xor運算
```python=
from Crypto.Util.strxor import strxor

key = b"(%#!##)$%&"
enc_secret = b"OosKlSNinm"
print(strxor(enc_secret, key))
```

### One-time Pad
一次性密碼本，運作方式就是`密文 = 明文 XOR 金鑰`
```python=
from Crypto.Util.strxor import strxor

key = "4cb3e7bda6064fd4850c4d65d49ada337f5e98eb8263501a72589f5b40ab7329b1503f97cb05547561ddb440eedfbc1e236d5b84711ea619d7257df1"
flag_str = "3cc48993c56923b8e06b281e95dc945a0d17c8a4c953266e3f60d96a139f226cf93a0de4af33625b308584239492c66970236be32551d15cad7200fb"

# 將 hex 字串轉成 bytes
byte_key = bytes.fromhex(key)
byte_flag = bytes.fromhex(flag_str)

print(strxor(byte_flag, byte_key).decode('utf-8'))
```

先用`fromhex`把這個字串先轉成byte的hex形式，接著就可以使用`strxor`來做解密

### Many-time Pad
xor兩次相同的key就會回到原來的密文

### AES
對稱式加密演算法，加密和解密都是使用同一個金鑰
AES是「區塊加密」，一次加密一個「固定大小的資料區塊」，每個區塊是：
1. 16 bytes（128 位元）
2. 如果訊息不足 16 bytes，就會「填充（padding）」
3. 如果訊息超過 16 bytes，就要拆成多個區塊處理

AES 本身只能處理一個區塊，但我們通常需要加密更長的訊息，所以要用「加密模式」來定義多區塊如何處理
#### ECB模式
1. 把訊息切為16bytes的獨立區塊
2. 不參考前後區塊
3. 把加密後的區塊串接在一起
4. 如果有重複的內容，它們的加密結果會一模一樣，這會導致加密後的密文暴露出模式（pattern）

```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

key = "07d87dd91e666d21859d4fa5968b4856"
enc_flag = "256f2a7cfa820f05bededa0a3a40a50dae9fea00e194750332d2d1bfebd7aac203ffde32195b15aa06aee87db08cd8f6ee4a78d6419b678153ef751536b22ff1"

key = bytes.fromhex(key)
enc_flag = bytes.fromhex(enc_flag)

cipher = AES.new(key=key, mode=AES.MODE_ECB)

plaintext_padded = cipher.decrypt(enc_flag)
plaintext = unpad(plaintext_padded, AES.block_size)

print(plaintext.decode("utf-8"))
```

使用`AES.new`設定AES模塊，mode使用與加密時相同的模式(ECB)
因為加密時必須是16byte的倍數，所以她有先進行pad，因此解密後要unpad，才是真實內容

### AES-ECB-CPA
使用ECB可能會發生藉由相同密文得到的相同內容來猜測原始資料
**CPA**攻擊手法就是「相同的明文 → 會產生相同的密文」，這讓攻擊者能建立明文到密文的對照表（codebook）

```python=
from pwn import *

flag = b"pwn.college{"
printable_chars = ''.join([chr(i) for i in range(32, 127)])

def enc_flag(c):
    p.sendline(b"1")
    p.recvuntil("Data? ")
    p.sendline(flag + c.encode())
    p.recvuntil("Result: ")
    return p.recvuntil("\n")[:-1]

def get_flag():
    p.sendline(b"2")
    p.recvuntil("Index? ")
    p.sendline(b"0")
    p.recvuntil("Length? ")
    p.sendline(str(len(flag)+1).encode())
    p.recvuntil("Result: ")
    return p.recvuntil("\n")[:-1]


if __name__ == "__main__":
    p = process("/challenge/run")
    while True:
        c = ''
        for c in printable_chars:
            p.recvuntil("Choice? ")
            if(enc_flag(c) == get_flag()) :
                flag += c.encode()
                print(flag.decode('utf-8'))
                break
        if c == '}':
            break

    p.interactive()
```
驗證多加的字元是否與真實的flag的某區段加密的結果是否相同
可以藉此暴力破解密文

### AES_ECB_CPA_HTTP
```python=
import requests
import string
from bs4 import BeautifulSoup

printable_chars = ''.join([chr(i) for i in range(32, 127)])
url = 'http://challenge.localhost:80'

flag = "pwn.college{"

while True:
    payload = f"substr(flag, 1, {len(flag)+1})"
    data = {"query": payload}
    response = requests.get(url, params=data)
    soup = BeautifulSoup(response.text, 'html.parser')
    encrypted_flag = soup.find_all("pre")[1].text.strip()
    for c in printable_chars:
        payload = f"'{flag + c}'"
        data = {"query": payload}
        response = requests.get(url, params=data)
        soup = BeautifulSoup(response.text, 'html.parser')
        pre_tags = soup.find_all("pre")
        if len(pre_tags) >= 2:
            encrypted_result = pre_tags[1].text.strip()
        if encrypted_result == encrypted_flag:
            flag += c
            print(flag)
            break
    if c == '}':
        break
```

可用構建`SELECT 'pwn.college{' FROM secrets`來看特定字串AES加密後的結果
構建`SELECT substr(flag, 1, 3) FROM secrets`來看部分flag加密後的結果
因此一樣可以暴力破解

### AES_ECB_CPA_HTTP(base64)
返回的result會再經過base64加密`b64encode(ct).decode()`
但因為我們只是比對是否相等，所以沒有影響，跟上一題使用的腳本相同


### AES_ECB_CPA_Suffix
由後往前爆破
```python=
from pwn import *

flag = b"}"
printable_chars = ''.join([chr(i) for i in range(32, 127)])

def enc_flag(c):
    p.sendline(b"1")
    p.recvuntil("Data? ")
    p.sendline(c.encode() + flag)
    p.recvuntil("Result: ")
    return p.recvuntil("\n")[:-1]

def get_flag():
    p.sendline(b"2")
    p.recvuntil("Length? ")
    p.sendline(str(len(flag)+1).encode())
    p.recvuntil("Result: ")
    return p.recvuntil("\n")[:-1]


if __name__ == "__main__":
    p = process("/challenge/run")
    while True:
        c = ''
        for c in printable_chars:
            p.recvuntil("Choice? ")
            if(enc_flag(c) == get_flag()) :
                flag = c.encode() + flag
                print(flag.decode('utf-8'))
                break
        if flag.decode('utf-8').startswith("pwn.college{"):
            break

    p.interactive()
```

### AES-ECB-CPA-Prefix
利用 `'a' * 15 + c` 比對 `'a' * 15 + flag`的第一個block可以用來洩漏flag的第一個字元
並依此類推，不斷減少'a'的數量可以推出更多flag的字元
當'a'的數量小於0時表示第一個block已經不夠用了，要跳向下一個block
```python=
from pwn import *

flag = b"pwn.college{"
prefixlen = 3
blocks = 1
printable_chars = ''.join([chr(i) for i in range(32, 127)])

def enc_flag(c):
    p.sendline(b"1")
    p.recvuntil("Data? ")
    p.sendline(b'a' * prefixlen + flag + c.encode())
    p.recvuntil("Result: ")
    return p.recvuntil("\n")[:-1]

def get_flag():
    p.sendline(b"2")
    p.recvuntil("Data? ")
    p.sendline(b'a' * prefixlen)
    p.recvuntil("Result: ")
    return p.recvuntil("\n")[:-1]


if __name__ == "__main__":
    p = process("/challenge/run")
    while True:
        gg_flag = get_flag()[(blocks-1)*32: blocks*32]
        for c in printable_chars:
            p.recvuntil("Choice? ")
            if(enc_flag(c)[(blocks-1)*32: blocks*32] == gg_flag) :
                flag = flag + c.encode()
                print(flag.decode('utf-8'))
                prefixlen -= 1
                if prefixlen < 0 :
                    prefixlen = 15
                    blocks += 1
                break
        if c == '}':
            break

    p.interactive()
```

### AES-ECB-CPA-Prefix-Miniboss
跟前面一樣是用prefix慢慢leak，只是這次就沒有分兩個功能了，都是同一個輸入源
```python=
from pwn import *

flag = b"pwn.college{"
prefixlen = 3
blocks = 1
printable_chars = ''.join([chr(i) for i in range(32, 127)])

if __name__ == "__main__":
    p = process("/challenge/run")
    while True:
        p.recvuntil("Data? ")
        p.sendline((b'a'*prefixlen).hex())
        p.recvuntil("Ciphertext: ")
        real_flag = p.recvuntil("\n")[:-1][(blocks-1)*32: blocks*32]
        for c in printable_chars:
            p.recvuntil("Data? ")
            p.sendline((b'a'*prefixlen).hex() + flag.hex() + c.encode().hex())
            p.recvuntil("Ciphertext: ")
            gg_flag = p.recvuntil("\n")[:-1][(blocks-1)*32: blocks*32]
            if(gg_flag == real_flag):
                flag = flag + c.encode()
                print(flag.decode('utf-8'))
                prefixlen -= 1
                if prefixlen < 0 :
                    prefixlen = 15
                    blocks += 1
                break
        if c == '}':
            break

    p.interactive()
```

### AES-ECB-CPA-Prefix-Boss
這題是前面的題目的SQL版本
關鍵是下面這句，他會從數據庫將資料取出，將資料從新到舊以`"|"`為分隔做拼接
`pt = b"|".join(post["content"] for post in db.execute("SELECT content FROM posts ORDER BY ROWID DESC").fetchall())`

```python=
import requests
import string
from bs4 import BeautifulSoup
import base64

printable_chars = ''.join([chr(i) for i in range(32, 127)])
url = 'http://challenge.localhost:80'
reset = 'http://challenge.localhost:80/reset'
flag = "pwn.college{"
prefixlen = 2
blocks = 1

while True:
    rreset = requests.post(reset)
    payload = "a" * prefixlen
    data = {"content": payload}
    response = requests.post(url, data=data)
    soup = BeautifulSoup(response.text, 'html.parser')
    pre_tags = soup.find_all("pre")
    if len(pre_tags) >= 1:
        encrypted_result = pre_tags[0].text.strip()
    real_flag = base64.b64decode(encrypted_result)[(blocks-1)*16: blocks*16]
    for c in printable_chars:
        payload = "a" * prefixlen + "|" + flag + c
        data = {"content": payload}
        response = requests.post(url, data=data)
        soup = BeautifulSoup(response.text, 'html.parser')
        pre_tags = soup.find_all("pre")
        if len(pre_tags) >= 1:
            encrypted_result = pre_tags[0].text.strip()
        encrypted_result = base64.b64decode(encrypted_result)[(blocks-1)*16: blocks*16]
        if encrypted_result == real_flag:
            flag = flag + c
            print(flag)
            prefixlen -= 1
            if prefixlen < 0:
                prefixlen = 15
                blocks += 1
            break
    if c == '}':
        break
```

### AES-CBC
1. CBC（密文鏈接模式）比 ECB 更安全，因為它通過將每個明文區塊與上一個密文區塊進行 XOR 操作來實現加密
2. CBC的區塊在加密之前會先跟上一塊進行XOR
3. 但如果是第一塊，就會跟一個隨機向量 IV 進行XOR再加密

```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from Crypto.Random import get_random_bytes

flag = open("/flag", "rb").read()

key = get_random_bytes(16)
cipher = AES.new(key=key, mode=AES.MODE_CBC)
ciphertext = cipher.iv + cipher.encrypt(pad(flag, cipher.block_size))
```
> AES-CBC的加密方法


ciphertext的前16個bytes是vi，可以先取出來，接著就能結合key來做解密
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

key = bytes.fromhex('ee7f38b64c8f3c2ea4d9cfde7738220a')
ciphertext = bytes.fromhex('60a5111b40a0f3e907f4c6902a59e0ea2dc2089e7bd41025f247e76cc5208b4295cf81fa8689d30e3215456371d1e6d91666f38f370934b726d757176e9d30e430c9025cbc523cbaa213f281f09cf216')

iv = ciphertext[:16]
actual_ciphertext = ciphertext[16:]

cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
decrypted_text = unpad(cipher.decrypt(actual_ciphertext), AES.block_size)

print(decrypted_text)
```

### AES-CBC Tampering
1. 在 CBC 模式下，如果一個攻擊者能夠攔截並篡改傳輸過程中的密文，那麼他可以對 後續區塊的解密結果進行干預
2. 這是一種**選擇密文攻擊**（Chosen-Ciphertext Attack）。例如，攻擊者可以改動第 N-1 區塊的密文，使得解密後的第 N 區塊變成他想要的結果

這題會給我們一個 iv+AES_CBC加密的`"sleep"`
```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from Crypto.Random import get_random_bytes

import time
import sys

key = open("/challenge/.key", "rb").read()

while line := sys.stdin.readline():
    if not line.startswith("TASK: "):
        continue
    data = bytes.fromhex(line.split()[1])
    iv, ciphertext = data[:16], data[16:]

    cipher = AES.new(key=key, mode=AES.MODE_CBC, iv=iv)
    try:
        plaintext = unpad(cipher.decrypt(ciphertext), cipher.block_size).decode('latin1')
    except ValueError as e:
        print("Error:", e)
        continue

    print(f"Hex of plaintext: {plaintext.encode('latin1').hex()}")
    print(f"Received command: {plaintext}")
    if plaintext == "sleep":
        print("Sleeping!")
        time.sleep(1)
    elif plaintext == "flag!":
        print("Victory! Your flag:")
        print(open("/flag").read())
    else:
        print("Unknown command!")
```

可以傳入一段iv加上密文，經過解密後可以執行其命令
我們可以修改的部分為iv，如果iv都是0的話，這樣就可以得到sleep跟iv進行XOR了但還沒加密的結果
接著藉由修改iv來讓解密出來的結果進行XOR為`flag!`
要注意的是`unpad(cipher.decrypt(ciphertext), cipher.block_size).decode('latin1')`這邊是解密後與iv進行XOR要進行unpad，所以後面的幾個bytes原先是空的，我們解密回去那邊仍要保留是pad填充的結果
所以我們的iv只能修改前五個bytes，後面要維持原樣，這樣才能讓unpad知道後面幾個bytes是空的


### AES-CBC Resizing
unpad原理：假設你的區塊大小是16字節，而明文長度是13字節，則填充會加上3個字節，每個字節的值都是 `\x03`，使得總長度達到16字節
這題`sleep`和`flag`字串長度不同，所以在處理unpad時要特別注意
原先填充11個bytes，所以應該是`\x0a` XOR iv = 加密前的值

```python=
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad, pad
from Crypto.Util.strxor import strxor

ciphertext = bytes.fromhex('410ae6bfeb65c09e6b0d8af933377d03dc3f503a2323024afc5b4b8a2384ee18')

iv = ciphertext[:16]
actual_ciphertext = ciphertext[16:]
plain = strxor(pad(b"sleep", AES.block_size), iv) # 加密前的字串
print(strxor(b'flag', plain[:4]).hex(),end='')    # 把前4個byte修改為flag的iv
print(strxor(b'\x0c'*12, plain[4:] ).hex(),end='')    # 把後面12個byte都修改為\x0c的iv
print(ciphertext[16:].hex())
```


### AES-CBC-POA-Partial-Block
參考這篇的POA手法：
https://dylanpindur.com/blog/padding-oracles-an-animated-primer/

```python=
from pwn import *
from Crypto.Util.strxor import strxor
from Crypto.Util.Padding import unpad

raw_str = 'TASK: be845017c766af291c419be77319a2a78e80ff7e5ab78bb6244dfdaa722825a0'
data = bytes.fromhex(raw_str.split()[1])
iv, ciphertext = data[:16], data[16:]
print(iv.hex())
print(ciphertext)
p = process('/challenge/worker')
p.recvuntil('long!')

flag = b''

for j in range (15, -1, -1):
    temp_iv = strxor(flag, bytes([16 - j])*len(flag))
    for i in range(256):
        suffix = bytes([i])
        # print('TASK: ' + iv[:j].hex() + suffix.hex() + temp_iv[::-1].hex() + ciphertext.hex())
        p.sendline('TASK: ' + iv[:j].hex() + suffix.hex() + temp_iv[::-1].hex() + ciphertext.hex())
        re = p.recv()
        if re == b'\n':
            re = p.recv()
        print(re)
        if re == b'Unknown command!\n' or re == b'Correct! Use /challenge/redeem to redeem the password for the flag!\n':
            flag += bytes([i ^ (16-j)])
            print(flag[::-1])
            break
print(unpad(strxor(iv, flag[::-1]), 16).decode('latin1'))
# print(strxor(iv, flag[::-1]))

p.interactive()
```

### AES-CBC-POA-Full-Block
PKCS7的pad如果剛好是full block，像是要pad到16 bytes，如果剛好已經是16 bytes的倍數，則會在最後面加一個新的block表示pad，因此如果知道剛好是16的倍數，則可以直接跳過最後一個block不看，因此直接用上一題的腳本即可


### AES-CBC-POA-Multi-Block
處理多個block，但要逆向推回去原本的block只需前後兩塊做POA就可以慢慢把block都leak出來
利用POA可以回推XOR後的plaintext，接著再跟前面加密後的block做XOR就能得到原始密文
```python=
from pwn import *
from Crypto.Util.strxor import strxor
from Crypto.Util.Padding import unpad

raw_str = 'TASK: 9c73dec3e7547e20a16ec219e99c15ee902822fb9620777623a183626fc7a3ba47566a72157e4367092fe4ae50c323219de9af60aec064046db9185d7307584cf2ff37710707a1933e1a56eb47c826cc'
data = bytes.fromhex(raw_str.split()[1])
ciphertext_list = []
i = 0
while i < len(data):
    ciphertext_list.append(data[i : i+16])
    i+=16
p = process('/challenge/worker')
print(ciphertext_list)

flag = b''

for k in range(len(ciphertext_list)-1, 0, -1):
    ciphertext = ciphertext_list[k]
    iv = ciphertext_list[k-1]
    print(iv)
    temp_flag = b''
    for j in range (15, -1, -1):
        temp_iv = strxor(temp_flag, bytes([16 - j])*len(temp_flag))
        for i in range(256):
            suffix = bytes([i])
            payload = 'TASK: ' + iv[:j].hex() + suffix.hex() + temp_iv[::-1].hex() + ciphertext.hex()
            # print(payload)
            p.sendline(payload)
            re = p.recv()
            if re == b'\n':
                re = p.recv()
            # print(re)
            if re == b'Unknown command!\n' or re == b'Correct! Use /challenge/redeem to redeem the password for the flag!\n':
                temp_flag += bytes([i ^ (16-j)])
                print(temp_flag[::-1])
                break
    flag += strxor(iv, temp_flag[::-1])[::-1]
print(flag[::-1])


p.interactive()

```

### AES-CBC-POA-Encrpyt
能夠利用POA改變加密前的明文
假設明文有2個block，我們能利用POA獲得兩塊block的intermedia_value
`明文 XOR 前一block的加密結果 = 當前block的intermedia_value`
利用這個方法我們可以修改前一block的加密結果來讓當前block還原回去的明文變成我們自訂的
但這樣會修改前一個block，所以需要重新獲得前一塊block的intermedia_value
這樣才能繼續構建出超過原本長度的假的加密結果，來改變明文

```python=
from pwn import *
from Crypto.Util.strxor import strxor
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad, pad

p = process('/challenge/worker')

commend = 'please give me the flag, kind worker process!'
commend = pad(commend.encode(), AES.block_size)
print(commend)

def get_intermedia(raw_str):
    data = bytes.fromhex(raw_str.split()[1])
    ciphertext_list = []
    i = 0
    while i < len(data):
        ciphertext_list.append(data[i : i+16])
        i+=16
    flag = b''
    intermedia = b''
    for k in range(len(ciphertext_list)-1, 0, -1):
        ciphertext = ciphertext_list[k]
        iv = ciphertext_list[k-1]
        temp_flag = b''
        for j in range (15, -1, -1):
            temp_iv = strxor(temp_flag, bytes([16 - j])*len(temp_flag))
            for i in range(256):
                suffix = bytes([i])
                payload = 'TASK: ' + '00'*j + suffix.hex() + temp_iv[::-1].hex() + ciphertext.hex()
                p.sendline(payload)
                re = p.recv()
                if re == b'\n':
                    re = p.recv()
                # print(re)
                if re == b'Unknown command!\n' or re == b'Sleeping!\n':
                    temp_flag += bytes([i ^ (16-j)])
                    break
        intermedia += temp_flag
        flag += strxor(iv, temp_flag[::-1])[::-1]
    # print('intermedia: ' + str(intermedia[::-1]))
    # print('decrypt_str: ' + str(flag[::-1]))
    return intermedia[::-1]

fake_enc = b''
task = 'TASK: 2ad203761e9c4d24d205399358e793e84f5b727be99310ee14d334287707be52'
enc = '4f5b727be99310ee14d334287707be52'
fake_enc += bytes.fromhex(enc)[::-1]
for i in range(len(commend)//16 - 1, -1, -1):
    intermedia_value = get_intermedia(task)
    print('intermedia_value: ' + str(intermedia_value))
    print(commend[i*16: i*16+16])
    enc = strxor(commend[i*16: i*16+16], intermedia_value)
    fake_enc += enc[::-1]
    task = 'TASK: ' + '00'*16 + enc.hex()
print(fake_enc[::-1].hex())

p.interactive()

```

### DHKE
Diffie-Hellman 金鑰交換協定（DHKE）
一個質數`p`和一個稱為「生成元」的數字`g`
甲先挑一個數字`a`，乙也挑一個數字`b`
計算 `A = g^a mod p`, `B = g^b mod p`，接著再傳給對方，這是公開的被知道也沒差
接著計算共享金鑰`s = A^b mod p`和`s = B^a mod p`，這兩個會是相同的



```python=
p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff
g = 0x2
A = 0x2db439abf8cd018ffdd81406829a82e37c0bb587d1788d404533ae535af3d308eaa136ce79e90e355c292fe6075f7f077a159a0754bf7fee932f93f1410d514ab09ee1907c7ce480c5e6333c2157353daa3ea1985c7a22c6b4579ed712c3df93890ff409dcff01a31297d665f83b8c62f07817ed1e15f4054822182592c98784bdbe6d6cf7e7b591a2d3fb017164484e406703396e43c00df9ca5b485e644b976a011352ac0ff19042c41b7d0a9a5439df9a68f62da913290b24ea76000a90aeb790f015e6848fc4616ad978ed9fdedaa87c01e51e34be272f0f0db4ad6f5f07166c1f6c445c73479996e7070e8919bb0810a2e978f35d0b90b2bbe4f5617251

b = 1026
print(hex((g ** b) % p)) 
print(hex((A ** b) % p))
```
> 可以藉由輸入`B`來決定`b`，這樣就能計算出共享金鑰s

### DHKE-to-AES
DHKE通常是用來建立一個隱密的通道，而不是直接加密資料
若要加密則可以使用部分的`s`作為AES密鑰來進行加密

### RSA 1
[RSA介紹](https://ithelp.ithome.com.tw/articles/10250721)
[RSA證明](https://silverwind1982.pixnet.net/blog/post/360901318)

RSA為非對稱加密
公鑰 `{e, n}`和私鑰 `{d, n}`
加密明文m => `c = m^e mod n`
解密密文c => `m = c^d mod n`

```python=
n = 0xbd97fcc69f4c02ca60518c52d43e2cbda2f12516fb4dfbab97ce67cf04304f75ee31a712310b937befb866aef89eb52c3775fdbc1c7bfdfe8056905ad25131b9dbdaee66f96e70d5a450063f8c72ef155b4c6d577affddd5cc7ead6180dfec50504862bd0a583fe2702f1058f8a094440b3fbad319954e2ae17d1609ef1bbe71b46ec285190f7dd2c7e56405ee1f390a986db3237299b3b36df3bf8d81ee18a4d3de534936a9b13403ab66eb26fac969d6848c448657a3472c3cd632957c94d0e7a9f0c41e8597bac3bfed5b8eea6269904feb124d51b89808fff5bc5de8abe7a3716fe11a926e1a7e1753dcc182c6f10d52c6a89764ca5a5314aea7b55fbdfd
e = 0x10001
d = 0x4d1383e4ef8fc436a7ef9f1f713f918acaba443cd28f8277e0f03d8d90835f5a6f2a6a645fe1f7e453b160b553479a19ceb63e20026879fac40bed05af28e911490af90e8dead31e577d5cfceac932df38cd9a4a0d2c05f04c0157d522c265dcc4b698c58776170aa456cdcb8dd022568348365869b7241f14aa7892334dd11ecf5de96c3642449db6cf609c6abe4bcc811036101a7653efaa6018adba41fd420708e4540c45d5166c6c54a6c5a9edc6d9f8ea0d94a023804c2ce6e904508d2916666cf0a0e996fffd842f72f7cdc7807e3d751c550d55d729d68d29f01d8803528fa87990e2fd9b659f87d86923cffcea0b127a86293418d8a1b1a9c4e62dd5
cipher = 'db246ab603860be4e66a890a00086cad2f155261438e128a094d4853d436782f4e64bb29ae3d37fd25d0b3ccd543b41059d60a494c6f65caddd6a4e39bf7eac5896be3e1dd742bdcc4f75047bb892bba938229f1db0f66e80f855f18c6c1d76b0a47e32be484a20066acfac5d07d51aae75dcbc80e3fef02363b322ac4f86b0efab38d927604e3faf4f6ad7929ab030a08c72e285e1a096da834ccb3e515051dc6e422de1d9791767bb3186752c2511f22d94d77da73e130e88e0ee57896943179078587412b9c70d8da916f1894cc92c55b65edd4560ad13beeeceb39613900b6a942d49cd6596dc181222f4a3eab5b914989d9ca236e2a6d4970a0aed9647f'
cipher_int = bytes.fromhex(cipher)
cipher_int = int.from_bytes(cipher_int, "little")

m = pow(cipher_int, d, n)
print(m.to_bytes(256, 'little').strip(b"\0").decode('latin-1'))
```

### RSA 2
給e, p, q反推d出來解密
```python=
from Crypto.Util.number import inverse, long_to_bytes

e = 0x10001
p = 0xd52f3ba9336c03b7fbd941586920bd404bb48b5b0001c0ba4822de6a2ead65afd18971c07ea560ead402055c95b34fe5f65e469a9490b4d811c3a6b1ffa141ad1c07d0808c729b1a1aa70157d604ecd76eb339c0a1ec23b0e7efa3d37d6feec0ef20c041f9c83cb77c8b013dfdaba49aadd93f97fa2a02743d589b8d9ee724d3
q = 0xf8aa53029129db56e91d79130186a0acaa40bcb94cd19cf1bf4909fd2113847c8b728db16aa1ae0ab5a9eaec91aa0fda3d6d3576c6756ed69981683701ec31a8dd55237339cf2cae2ab05b2917b618d041051bc7fc067b90aea2863e5f5c082b7a651388dfc3c25a091b1e4513f50e58e101489d083362b083f39aab0a4a97a7
n = p*q
phi = (p - 1) * (q - 1)

# d = e^(-1) mod φ(n)
d = inverse(e, phi)

cipher = 'a5c0c66797d01f5d57344e69ae346ab5a6de3d44c39aaf5525c9cfdcf06fb299ced9fbe446abb0e2fe0497e9bf2792844d4c1ac1f84dbdba333fea7ddd3eb725c52f5fd05d23adc2be43d26f905aa631c1912941ab566f2c2ed61d6d8caeea6b40038dc5b4a817a6609be667922276da99316720efc1587670a480f43cac7e9dc32ad7b033f600a23fc1e84a6be86876edbd1e8dc730a92955d5c84a4051f62ab025e76cae1e49b506677c6aa42396ea24a4a47738ed333a430ce0df08ef194f4681e42fadfc1254b7bc328154a298f38eeaaf2828b819dc693a1e39566922a33dbf617877ba4e324b1f27191f16363e25d88b88a1a88f581c9a583e9ea18876'
cipher_int = bytes.fromhex(cipher)
cipher_int = int.from_bytes(cipher_int, "little")

m = pow(cipher_int, d, n)
print(m.to_bytes(256, 'little').strip(b"\0").decode('latin-1'))
```

### RSA Signature
數位簽章是用私鑰加密，接著用公鑰解密
能利用 `x^a * x^b = x^(ab)`
`new_s = (s1 * s2) mod n = (x^d mod n * y^d mod n) mod n = ((x*y)^d) mod n`
因此能利用`x`和`y`組成另一個數位簽章

解法：
利用`int.from_bytes(b"flag", "little")`來計算`b"flag"`的值(1734437990)
接著可以拆分成target = m1 * m2 => `10 * 173443799`
利用`base64.b64encode(m1.to_bytes((m1.bit_length() + 7) // 8, "little"))`來對其做base64加密，接著能獲得數位簽章s1和s2
利用`new_s = (s1 * s2) mod n`可得到新的簽章來偽造成flag
```python=
s1 = '7wLIS5OKIbz4d98hrwjUOZLdIQmh8tz5yLaZl0fxObQFQmgNweuQdBNlJWoxxqJU1VnweeW9D37MI2uNwd+40BMQRu3FEJgLbRSF+rZqrTRUhU5571/mKRNjUHZdmcGp9CLoZI2DasyPkK9u8/+nUggVSzLKPYIurbijeUKr4uDi5BAZgQ4/q0I6TjBMN/nQrrnDv/jMZ1rgUybjUZsNGWKCEfH/ZgKoAJTg6rLSO5CP3HDycR6REAq56gN8jEUIqdslZ0mqq04gOgP1IWPfJ0yB2bvGOTEn1UzcgXyvxCVAf0rew5vhxGy+kaIPPwka7cBM0ZBd3hPW2HG0LixyKg=='
s2 = 'nXQbtGt/+euIpsCcPfbjmuRtKdNpf1BfxYDF5kPtq97qLQLlFuSDKK0QILQ9dUXOU2iErmyK+5I7pkwzxgIcU/aFkWOMtYUZrbDTRIz2n7dVDvsl5LYPVjPlS3LJf5f6N0oC2AWSBvdnUYZPGtWseUx+Kb9g808/C1pdtuau346FHUzxEdYXmGcuZogwpvpGWc/f/1eufLBLH6H/FhW4wobpMKqaFzZU25vCy5nF928ypFKMasc2QX4ByODqzALSdMo2cmotqGTe88Jg2Y4fP2OqGDaihT76w6vyk4xtagp6v8P4xHcL/v2ALzJ+RQld/MG9wLyFbfwUBkd9cES/Lw=='

s1_int = int.from_bytes(base64.b64decode(s1), "little")
s2_int = int.from_bytes(base64.b64decode(s2), "little")

n = 0xb64a8bfaf9afb74b6da04535ca29d030c761e51e9d1936932b2963cf4aa6c0576e7d70f7902e52485c23476a51a3287f3b8b1157b0af0c45e5c532919b1e93eb702cbfe94f2a7c877f45c2676ba0bfd79b276734144dd9caa8c755452f4871318eb8999e764841c86e4e0543d5b3c45575a4ad5c9bdc152ad21e06356a395168c8c1bbfd00aa466a5283998fd4b06c22cfbffd54a6a9c987268e70c2ad4dbd1dfa7b9d7cf5f9c64a8452e12f68e9fc3dc4b498f5e35c927abb518e2f1a99318c0b9255d6acb21716260cd1b8bc9bcd22b13eaf0be58c7482b7c56a7f009de228d703fdd3700f18d48369158202731626972f02bedd4cd70397b84af23d1f689f

new_s = (s1_int * s2_int % n)
print(base64.b64encode(new_s.to_bytes(256, "little")).decode())
```

### SHA 1
利用暴力破解來碰撞前3bytes
```python=
from hashlib import sha256
import os

target_prefix = "4d7483"  # 範例：目標雜湊的前 3 bytes

i = 0
while True:
    # 將int轉成8bytes的 hex形式的bytes ex: 1 => \x00\x00\x00\x00\x00\x00\x00\x01
    candidate = i.to_bytes(8, 'big')
    h = sha256(candidate).hexdigest()
    if h.startswith(target_prefix):
        print(f"[+] Found! input: {candidate.hex()}, hash: {h}")
        break
    if i % 100000 == 0:
        print(f"[*] Tried {i} inputs...")
    i += 1
```

### SHA 2
```python=
import hashlib
import base64

challenge_b64 = "qgBoriRep3T/IbLmCyRI7ygorOeHJPRmGdOWE9GOe2Q="
challenge = base64.b64decode(challenge_b64)
print(challenge)

i = 0
while True:
    response = i.to_bytes(4, "big")  # 試試 4 bytes
    attempt = challenge + response
    digest = hashlib.sha256(attempt).digest()
    if digest.startswith(b"\x00\x00"):
        print(digest)
        print(f"[+] Found response: {base64.b64encode(response).decode()}")
        break
    i += 1
```

### RSA 3
```python=
import hashlib

e= 0x10001
d= 0x58480e026c0b091890da64ffa89401d98d7ff2a080e66e5605e131f82983be627577491ac80aa715c04cfe5cd44f6beeb4d5a18a33744ba5d9d4365039194eef746036ca87d2d149d9b9007094b1f093e1f3a1b5eb2af9cce6bbf498ad4b3c597b1c0396bb153773287436c36f77c98ef72227362aec970b047bb1fdc62a3f764411f9607f2aa286c1480f6ad4d49b6efaa50e9dd8156bae39da92af9a4df940d0c7843c0e6545188a62aaf709a539cef0bb75f053830ef34d9c306381f4a27e3b33dad92a9715b25387cfde1c4505436d622f914727b0a142f74a8549ae54ea180fec491dcb28c712492751ce344f3d8a5571a9159a3d775f48bef0c47d51fd
n= 0xce28468d7d49c3db25b46c96404bfd266478f99d4070cfdf6b32851bf5539af7e27f644a6d2c97e1e46e740e3c789322f2be960b2eee8e2efb5a5de9d1c67cb185e6ade581b3be0e1ee7492d1aac266212e30c7aa90b88c6c06a356a06d9867e9432aff542b64e0f1d3050da5307706929b5f1616fac062500c4a72e299adcdc55ce0d846f0e729ff2f509dd13aa67cb9a8ff8635466f5194efe2bfb9ef90459845b6ff84ce2d10f15977a7322f9f437d40f88a8e6e2e881d9235c167c17f5eb5bd90d73452e0c57efd347abc8f93af64655a5dfd6e879523a470759496f1959f16d7461c1b39f0abe528c72c61f164b394922f74688deceb0bed0c0cf6a955b
challenge= 0x18de996e62bac4e7e33fcb65bd693f7b4ea265ae524866cb1784444da44a9fb16068d145a90cda97ddcc92a99da75777dfb1223f1d16257797b77c296131b6a4dda905124fc4d04c6eccab16fa2c7c13f5e147edea3fdc562932d680efdfca6e501ad1c8d4cfb7048b3d3c87bcfcf1a3362da5764832e2678739abb8af4b8eafabde72184dba92be9b3dae6194c16bd6e7c87953362457a2d149c00015d9df7dba196a8e102cb9d247f45883a63f3b12f10fec8b074084448dee687412161de1e2b695a68eb5957828e3c92345bbf706cde384d115650e2e013ef1838e9a6ec7884415b3a176394194311a82d27db515e77926eb24b071b1231e1fe4565640

print(hex(pow(challenge, d, n)))
```

### RSA 4
自行選定p, q之後就能進行解密

### TLS 1



```python=
from Crypto.Util.number import inverse, long_to_bytes
from Crypto.PublicKey import RSA
from hashlib import sha256
import base64
import json

root_d = 0x1b217764903cc366cb741da1434984374eb660e7ebe80e8ce9989fe5df1d8fe26808f27a07a19fa6c3d5576f600aed9b7febffb024b32155cc65825d1f32fc8bf5fa042485f5d3bb1567c842250c9cfae7c45b4ceae67c687e24a018ddb0d683775bd96a924544404ffb89f9abdde305ba1e669c1fa02f00cbe9ac1a9ce5c031c7c3362c70737645ffdb28ab33d602c6dcefdd5b736dcd5bfdadfa4d21793280b290bfef7bcf6fc34b8b21775289811b3131411311f9528b33c4568825ecb0ce9d05f76555856364f01d7d809e67eaf4ef53271ac0db0df9ded56f6ef67654ba6a7b974bb4cd730a9bf4909a4d57ff9599299b07140dda049dd94a6df30b9fc9
root_n = 23652276506885177725097105136627198136549831414338888859189741707898380698160442441397161685052417196221803609894303200764522137314516773064544752650436122783432660067297364928831986392934876616564620490870811883592728491032916887096268686455128913865196668912748330165770608812882195128366444828583677529998916593563244628990799771471259380251670338339190455184521328301332443262975499272656471296298699218436423655808832787100749808427720558231665382831967437840559515970629569364964573380205886463845383592141936262608423603217109196831497581258629560557273102590782618168311811924582587995724670730754550845135817


user_key = RSA.generate(1024)  # 為了符合 n 的大小限制

user_certificate = {
    "name": "user",
    "key": {
        "e": user_key.e,
        "n": user_key.n,
    },
    "signer": "root",
}
print(user_certificate)

user_cert_data = json.dumps(user_certificate).encode()
user_cert_hash = sha256(user_cert_data).digest()

user_signature = pow(
    int.from_bytes(user_cert_hash, "little"),
    root_d,
    root_n
).to_bytes(256, "little")

print("User certificate:")
print(base64.b64encode(user_cert_data).decode())

print("\nUser certificate signature:")
print(base64.b64encode(user_signature).decode())

print("key_d: " + str(user_key.d))
print("key_e: " + str(user_key.e))
print("key_n: " + str(user_key.n))
```


### TLS 2
先用DHKE來作加密通道，獲得共享金鑰作為AES.CBC的加密key
資料發送的加密過程為先經過AES.CBC加密後再base64
數位簽證則是使用RSA來驗證

```python=
import sys
import string
import random
import pathlib
import base64
import json
import textwrap

from Crypto.Cipher import AES
from Crypto.Hash.SHA256 import SHA256Hash
from Crypto.PublicKey import RSA
from Crypto.Random import get_random_bytes
from Crypto.Random.random import getrandbits, randrange
from Crypto.Util.strxor import strxor
from Crypto.Util.Padding import pad, unpad

p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff
g = 0x2
A = 0x97302d410df96bdabd5c3f0a16ce6a4202985ab06fe1bdc82bfde72d8708e80edaf0848fc03acaffebe575a3a9cb27b5c8fe0cd80a35111734870e871cebdf22d9c49548580a425a88c7c26b9171e58c2521c8f2852ece7c2f7b9d48ad570c4dcc7d564b399f05eb8d2b2146b8374760beadc17fcb18b1e1a8fdc533c0ee3e7620c4b0f9a8466f3c048342fa3d44e6ab5fc24f68124026fde7c4dbec677514138f5e07f91dd780be58a39aaf2ff5505e57a783eadcc45f060c757bda6dbe2f36f9cc727b6f05c7855288d95c9c84830a2ee702bd84e10b29ad0f3748437077fe32e4e1bad0b568e08059ef6e93121c3d654af1bb6eefef159c79fb5b2a960c61
name = 'qjrkhlcsfxkuszqd'
b = 0x123456789

B = pow(g, b, p)
print("B: " + str(hex(B)))
if not (B > 2**1024):
    print("B too small")

s = pow(A, b, p)
print("s: " + str(hex(s)))

key = SHA256Hash(s.to_bytes(256, "little")).digest()[:16]
cipher_encrypt = AES.new(key=key, mode=AES.MODE_CBC, iv=b"\0"*16)
cipher_decrypt = AES.new(key=key, mode=AES.MODE_CBC, iv=b"\0"*16)

root_d = 0x1141a1cb530b5eaaef9ebfbc085d58a9fae7aa9bbe195020c344e1c96e9d95ca38743bcf585f08da66c8382bdec2150255a9f5c5a25635a9498594daa6f509ba00ac79b586bf1389e264d658eb8c58c21ef541826817451e567d991ec8600c777f042de4deb2e4ecfe6a70677f76a34de8d7c8e6e51bfb14d174f80c5791e75b1cff8d8e580538a90a425da833ee4efc4968373ea02434571b5202cc15a3cda80d3eed3e1735d2a23718981d44c60ceb5225cca9e25a3b199949c5e946c6fdea92a825fd7da8ef46863cc8212cd243ec6834b63fa5b21fa80dd9b389e03edfa0da02e163ada33aeebaa032179ddff4f42df02861bf626d17f4abb5d7fc3e2713
root_n = 23200159068951864154840549793369931021003345851595233662255815517619965193187353268488926973584919748963854823308874323688727034770105398061228988161906745702470467092289863471723770671951388892871631218232042864559109381887196644128117186587116842889574179383234399711865874039505580523484108718552141343634923199521435846132885049076835976555278778665509220381582864067428893588519223517219724871745391730452165550764261260508249098705023986134285252441333753408348351637052887954373391197775368730075323204578247276650802898396827296730233547145839491347027512399244678450919157374407473131797753351933151379792281

user_key = RSA.generate(1024)  # 為了符合 n 的大小限制

user_certificate = {
    "name": name,
    "key": {
        "e": user_key.e,
        "n": user_key.n,
    },
    "signer": "root",
}
print(user_certificate)

user_cert_data = json.dumps(user_certificate).encode()
user_cert_hash = SHA256Hash(user_cert_data).digest()

user_signature = pow(
    int.from_bytes(user_cert_hash, "little"),
    root_d,
    root_n
).to_bytes(256, "little")

print("User certificate:")
print(base64.b64encode(cipher_encrypt.encrypt(pad(user_cert_data, cipher_encrypt.block_size))).decode())

print("\nUser certificate signature:")
print(base64.b64encode(cipher_encrypt.encrypt(pad(user_signature, cipher_encrypt.block_size))).decode())

print()

user_signature_data = (
    name.encode().ljust(256, b"\0") +
    A.to_bytes(256, "little") +
    B.to_bytes(256, "little")
)
user_signature_hash = SHA256Hash(user_signature_data).digest()
user_signature_check = pow(
    int.from_bytes(user_signature_hash, "little"),
    user_key.d,
    user_key.n
).to_bytes(256, "little")
print("\nUser signature:")
print(base64.b64encode(cipher_encrypt.encrypt(pad(user_signature_check, cipher_encrypt.block_size))).decode())
print()

print("key_d: " + str(user_key.d))
print("key_e: " + str(user_key.e))
print("key_n: " + str(user_key.n))
```