# Cryptography

### XOR
就是xor

### XORing ASCII Strings
可以使用`strxor`來對字串進行xor運算

from Crypto.Util.strxor import strxor

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

### One-time Pad
一次性密碼本，運作方式就是`密文 = 明文 XOR 金鑰`

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）

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）

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

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
由後往前爆破

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

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，只是這次就沒有分兩個功能了，都是同一個輸入源

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())`

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再加密

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來做解密

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"`

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 = 加密前的值

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/

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就能得到原始密文

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
這樣才能繼續構建出超過原本長度的假的加密結果，來改變明文

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`，這兩個會是相同的

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`

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出來解密

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

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

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

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

import hashlib

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

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

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

### TLS 1

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來驗證

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))