# Một số khái niệm cơ bản trong Cryptography
- **Cryptography**: là một thuật ngữ tiếng anh dịch ra là **mật mã học**. Đây là lĩnh vực khoa học nghiên cứu về mã hóa và giải mã thông tin với mục đích nghiên cứu các phương pháp, cách thức để chuyển đổi một thông tin từ dạng “**đọc hiểu**” sang dạng “**đọc nhưng không hiểu**” và ngược lại.
- **Ví dụ:** Bạn muốn gửi một tin nhắn `"HELLO"` cho người bạn của mình. Bạn có thể sử dụng một thuật toán mã hóa như **Caesar Cipher** và một khóa bí mật là $3$ để mã hóa tin nhắn của mình. Khi đó, tin nhắn sẽ trở thành `"KHOOR"`. Người bạn của bạn nhận được tin nhắn và biết rằng khóa bí mật là $3$, họ sẽ lùi lại $3$ ký tự trong bảng chữ cái để có được văn bản gốc là `"HELLO"`.
- **Cryptanalysis**: hay còn gọi là **thám mã**, là lĩnh vực liên quan đến việc phân tích và giải mật mã. Nói cách khác thì nó là phương pháp để tiếp cận văn bản gốc khi ta không có **key** gốc. Đây là một lĩnh vực quan trọng trong mật mã học, nơi mà các nhà nghiên cứu cố gắng tìm ra cách để phá vỡ các hệ thống mật mã.
- **Ví dụ:** Nếu một tin nhắn đã được mã hóa bằng **Caesar Cipher** với "**key**" là $3$ trở thành `"KHOOR"`, một cryptanalyst có thể sử dụng phương pháp **Brute-force** để thử lùi ngược tất cả các khả năng **(từ 1 đến 26)** và xem xét kết quả. Trong trường hợp này, họ sẽ nhận ra rằng `"KHOOR"` được giải mã ngược lại thành `"HELLO"` khi sử dụng key là $3$.
- **Encode/ Decode**:
- ***Encode***: là quá trình chuyển đổi thông tin từ một định dạng sang một định dạng khác, thường là để biến đổi dữ liệu sang một dạng mà dễ dàng xử lý hơn hoặc phù hợp hơn với mục đích sử dụng. Việc mã hóa không nhất thiết phải bảo mật.
- **Ví dụ:** Ta có đoạn văn bản gốc là `AT20N0118` sau khi encode (sử dụng mã **Hex**) thì ta được văn bản như sau: `415432304e30313138`, nó không còn dễ đọc như văn bản gốc nhưng nó sẽ giúp chúng ta dễ tính toán hơn.
- ***Decode***: là quá trình ngược lại với encode. Nó là quá trình chuyển đổi dữ liệu từ một định dạng mã hóa sang định dạng chuẩn hoặc dễ đọc hơn.
- **Ví dụ:** Bạn nhận được một dãy nhị phân `01001000 01100101 01101100 01101100 01101111 00101100 00100000 01110111 01101111 01110010 01101100 01100100 00100001`. Quá trình chuyển dãy nhị phân trên thành văn bản đọc được gọi là **decode**. Văn bản trên sau khi decode sẽ là: `Hello, world!`
- **Encrypt/Decrypt**:
- ***Encrypt:*** là quá trình biến đổi dữ liệu ban đầu thành dạng không đọc được hoặc khó đọc được, gọi là mã hóa. Bằng cách sử dụng một **thuật toán mã hóa** và một khóa. Mục đích chính của việc mã hóa là bảo vệ dữ liệu khỏi việc truy cập trái phép bằng cách biến dữ liệu trở nên không thể đọc được cho những người không có quyền truy cập. Để đọc được dữ liệu, người đó cần phải có chính xác khóa đã được dùng.
- Ví dụ bạn muốn gửi thông điệp `"crypto__is__math"` một cách an toàn. Bạn có thể sử dụng một thuật toán mã hóa như **AES** (Advanced Encryption Standard) và một **key** bí mật, ví dụ `1629051fd058eff82f2f46715084fead`. Thông điệp của bạn sẽ được mã hóa thành: `d4179437378d241e605c7897cb8ddb4e`. Nếu không có **key** thì không có cách nào để có được văn bản gốc.
- ***Decrypt:*** là quá trình ngược lại với encrypt. Nó giải mã dữ liệu đã được mã hóa bằng một thuật toán mã hóa với một **khóa** tương ứng. Mục đích của việc giải mã là khôi phục dữ liệu gốc từ dạng mã hóa và làm cho nó trở lại dạng có thể đọc được hoặc xử lý được.
```python!
from Crypto.Cipher import AES
key = bytes.fromhex("1629051fd058eff82f2f46715084fead")
enc = bytes.fromhex("d4179437378d241e605c7897cb8ddb4e")
cipher = AES.new(key, AES.MODE_ECB)
print(cipher.decrypt(enc).decode())
#crypto__is__math
```
- **Symmetric/ Asymmetric Cryptography**:
- ***Symmetric Cryptography***: là mã hóa đối xứng, tức là quá trình mã hóa và giải mã sẽ dùng chung một **khóa**.
- **Ví dụ:** AES là một trong những thuật toán symmetric cipher phổ biến nhất được sử dụng hiện nay. Nó là **Block Cipher**, có nghĩa là nó mã hóa và giải mã dữ liệu theo từng khối cố định.
- ***Asymmetric Cryptography***: là mã hóa bất đối xứng, việc mã hóa và giải mã sẽ cần nhiều hơn một khóa.
- **Ví dụ:** RSA là một trong những thuật toán mã hóa bất đổi xứng an toàn nhất hiện nay. Nó dựa trên độ khó của bài toán phân tích thừa số nguyên tố để giữ an toàn cho dữ liệu.
- **Block Cipher/Stream Cipher**:
- ***Block Cipher*** (mã hóa khối): là những thuật toán mã hóa đối xứng hoạt động trên những khối dữ liệu có độ dài xác định. Một khối plaintext sẽ được chuyển đổi thành một khối ciphertext tương ứng bằng cách áp dụng các phép biến đổi phức tạp như phép hoán vị, thay thế, XOR và ánh xạ...
- **Ví dụ:** Advanced Encryption Standard (**AES**) sử dụng các khối dữ liệu có kích thước **128 bit** và dùng các phép toán phức tạp để thực hiện các phép biến đổi trên mỗi khối. Block cipher thường được sử dụng trong các chế độ hoạt động như ECB (Electronic Codebook), CBC (Cipher Block Chaining)...
- ***Stream Cipher*** (mã hóa dòng): khác với mã hóa khối là chia plaintext thành một khối có kích thước cố định rồi mã hóa thì mã hóa dòng sẽ mã hóa plaintext theo từng bit hoặc từng bytes. Stream cipher dùng bộ khóa bí mật của nó tạo ra keystream là một dãy số ngẫu nhiên, dùng để mã hóa plaintext.
- **Ví dụ:** RC4 (Rivest Cipher 4), Salsa20, ChaCha20, A5/1, A5/2, Grain, Rabbit...
- **Hash Function** (hàm băm): có tác dụng biến đổi một giá trị đầu vào thành một giá trị băm nhất định mà không thể truy ngược lại giá trị ban đầu. Đặc biệt khi có một thay đổi nhỏ ở văn bản gốc thì cũng dẫn đến thay đổi lớn ở giá trị băm.
- **Ví dụ:** Hàm băm `SHA-256` sẽ băm chuỗi `"KCSC"` thành `"f60e9120d0a179b32a338b7eb6b5f966dd17150600e1376a48d1e1a39605559c"`. Ta không thể từ giá trị băm mà phục hồi văn bản gốc được.
# Challenge CryptoHack
## Introduction
### Finding Flags
- Ở challenge này, ta sẽ tập cách **submit flag**.
- Flag của CryptoHack sẽ có **format** `crypto{...}`.
- Nếu giải challenge ra flag có format như vậy thì có thể bạn đã giải challenge đúng.
- **Flag** đã cho sẵn là `crypto{y0ur_f1rst_fl4g}`.
- Ta chỉ cần copy rồi paste flag vào ô submit và nhấn nút submit là được điểm.
### Great Snakes
- Challenge này yêu cầu ta chạy file python `great_snakes.py` để có được **Flag**.
- Tải về rồi mở ra thì ta được đoạn code như sau:
- Chạy đoạn code và được kết quả như sau:
- ***Vậy flag của challenge này là crypto{z3n_0f_pyth0n}***
### Network Attacks
- Một vài challenge sẽ yêu cầu ta kết nối với server để giải được challenge.
- Những cách thức kết nối này có thể được thực hiện bằng cách chạy trên terminal của Linux (nếu như bạn có dùng Linux), còn không ta có thể cài **[wsl](https://youtu.be/wjbbl0TTMeo)** để có thể chạy hầu hết các lệnh của Linux trên Window:
- **Hướng dẫn:**
- Challenge yêu cầu ta kết nối đến sever `socket.cryptohack.org` với port là `11112`, ta sẽ sử dụng lệnh netcat (**nc**) để kết nối tới địa chỉ trên: `nc socket.cryptohack.org 11112`.
- Kết quả như sau:
- Đề yêu cầu hãy gửi một chuỗi `JSON` cho nó với key là `buy` và giá trị là `flag`, mình sẽ trả lời nó như sau:
- Khi mình yêu cầu server như thế thì server sẽ trả lại cho mình flag:
- Ở trên là cách làm thủ công, vì đề đã cho ta `Source Code` nên ta sẽ dùng nó để tương tác với server luôn:
- Tải file mà đề đã cho là:
- Ta sẽ được đoạn code sau:
```python
#!/usr/bin/env python3
from pwn import * # pip install pwntools
import json
HOST = "socket.cryptohack.org"
PORT = 11112
r = remote(HOST, PORT)
def json_recv():
line = r.readline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
print(r.readline())
print(r.readline())
print(r.readline())
print(r.readline())
request = {
"buy": "clothes"
}
json_send(request)
response = json_recv()
print(response)
```
- Ta sẽ chú ý ở phần *request*:
- **request** là một json dạng `{"buy" : "clothes"}`, request này sẽ được gửi đi cho server thông qua đoạn `json_send(request)`, nên ta sẽ chỉnh sửa nó cho phù hợp với yêu cầu.
- Vì đề đã nói là `Send a JSON object with the key buy and value flag` nên ta sẽ sửa value từ `clothes` thành `flag`:
- Ta chạy code để gửi request tới server, kết quả như sau:
- ***Vậy flag của challenge này là crypto{sh0pp1ng_f0r_fl4g5}***.
## ENCODING
### ASCII
- **Mô tả:** Challenge này giúp ta hiểu thêm về một mã là mã **ASCII** và cách chuyển đổi từ kiểu **số nguyên** sang kiểu **ASCII**.
- **Hướng dẫn:** chúng ta có thể sử dụng hàm **chr()** để chuyển đổi từ kiểu số nguyên sang kiểu ASCII/UNICODE tương ứng và sử dụng hàm **ord()** để làm ngược lại.
- **Lưu ý:** Hàm `chr()` và hàm `ord()` chỉ có thể mã hóa duy nhất **một** ký tự, nên ta không thể truyền toàn bộ list vào hàm mà phải dùng vòng lặp **for** để truyền từng phần tử trong list vào.
- Thực hiện như sau:
```python
integer_array = [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 integer_array:
print(chr(i), end='')
#chạy code sẽ được ouput là: crypto{ASCII_pr1nt4bl3}
```
- Hoặc có thể làm như thế này:
```python
integer_array = [99, 114, 121, 112, 116, 111, 123, 65, 83, 67, 73, 73, 95, 112, 114, 49, 110, 116, 52, 98, 108, 51, 125]
print("".join(chr(i) for i in integer_array))
```
- ***Vậy Flag của challenge này là: crypto{ASCII_pr1nt4bl3}***
### Hex
- **Mô tả:** Challenge này sẽ giúp ta hiểu thêm về mã **Hex**, một mã mà chúng ta sẽ thường xuyên gặp phải trong Cryptohacking và cách chuyển đổi từ mã Hex sang **Bytes**.
- Một byte hex được tạo nên từ **hai** giá trị thuộc tập
giá trị **[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F]** với giá trị của `A,B,C,D,E,F` là **[10, 11, 12, 13, 14, 15]**, ví dụ: `61`, `FF`, `E1`, `00`... Ta có thể chuyển hex sang số nguyên, ví dụ: `61` sẽ có giá trị nguyên là `int("61", 16) = 97`, và ta có thể chuyển số nguyên này sang **ascii** được, bằng cách sử dụng `chr(97) = a`, vậy từ giá trị hex `61` ta có thể chuyển thành chữ `a` rồi.
- Mã **bytes** là gì? nghe hơi lạ nhưng thực ra nó rất dễ hiểu, bạn tưởng tượng một chuỗi string mà thêm chữ **b** phía trước thì sẽ thành mã bytes, ví dụ: `"hello"` là string nhưng `b"hello` sẽ là mã bytes, mã bytes giúp ta biểu diễn dữ liệu dưới dạng chuỗi các byte với mỗi byte có giá trị từ **0** đến **255**, vì có đến **256** giá trị nên một byte có thể biểu diễn các ký tự ngoài bảng **ascii** được. Hầu hết các tool mà ta sử dụng sẽ hoạt động trên mã bytes rất nhiều.
- Ngoài biểu diễn các ký tự có thể in được thì mã byte còn được biểu diễn dưới dạng giống mã hex nhưng thêm **"\x"** phía trước, ví dụ: `b"\x00"`, `b"\x61"`, `b"\xfe"`, `b"\x6c\x6f"`. Khi ta thử **print** `b"\x61"`, nó sẽ in ra `b"a"` vì phần hex của `b"\x61"` là `61`, mà `61` là giá trị hex của chữ `a` nên `b"\x61"` sẽ in ra `b"a"` :smile:
- Vì vậy từ `hello` khi biểu diễn dưới mã bytes thì có thể để ở dạng `b"hello` và `b"\x68\x65\x6c\x6c\x6f"`, hai cách biểu diễn này là như nhau!
```python!
print(b"hello")
print(b"hello".hex())
print(b"\x68\x65\x6c\x6c\x6f")
print(b"\x68\x65\x6c\x6c\x6f".hex())
```
- Quay trở lại với Challenge thì đề yêu cầu ta chuyển chuỗi hex mà đề cho thành mã bytes để có được **Flag**, challenge có gợi ý cho ta dùng hàm **bytes.fromhex()** để chuyển từ hex sang bytes và dùng phương thức **.hex()** để chuyển từ bytes sang hex.
- Ta thực hiện như sau:
```python
hex_string = "63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d"
print(bytes.fromhex(hex_string))
```
- ***Vậy Flag của challenge này là: crypto{You_will_be_working_with_hex_strings_a_lot}**.*
### Base64
- **Mô tả:** Challenge này giới thiệu cho ta mã **Base64** và cách chuyển đổi từ mã **bytes** sang mã **Base64**.
- Mã **Base64** là một mã khá là phổ biến trong quá trình ta học Crypto, nó là một dạng mã hóa chuyển từ mã nhị phân sang string dựa vào một bảng gọi là bảng Base64:
- Cụ thể, nó sẽ chia văn bản dưới dạng nhị phân của ta thành các phần dài $6$ bit rồi ánh xạ $6$ bit đó vào bảng Base64 ở trên, ví dụ: từ `abc` khi viết dưới dạng nhị phân là: `011000010110001001100011`, ta chia nó thành $4$ phần dài $6$ bit: `011000 010110 001001 100011` rồi ánh xạ nó qua bảng Base64, `011000` sẽ là chữ `Y`, `010110` là chữ `W`, `001001` là chữ `J` và cuối cùng `100011` là `j`. Vậy từ `abc` khi chuyển sang mã Base64 sẽ là từ `YWJj`.
- Nhưng sẽ có trường hợp chiều dài nhị phân của chuỗi chúng ta nhập vào không chia hết cho $6$, khi một số là bội của $8$ chia cho $6$ thì số dư là $2$ hoặc $4$ nên ta tiến hành thêm các bit `0` vào để chiều dài của nó đủ $6$. Ta sẽ pad thêm vào chuỗi Base64 **một** dấu `=` nếu chuỗi nhị phân thiếu `00` và pad hai dấu `==` nếu chuỗi nhị phân thiếu `0000`.
- **Ví dụ:** từ `ab` có dạng nhị phân là `0110000101100010`, khi ta chia thành các đoạn $6$ bit thì ta thấy đoạn cuối chỉ dài $4$ bit mà thôi: `011000 010110 0010`, ta tiến hành thêm **hai** bit `0` ở cuối để nó dài đủ $6$ bit, vậy ta có chuỗi mới là: `011000 010110 001000`, khi ta ánh xạ qua bảng Base64 thì ta được kết quả: `YWI`, vì đã được thêm `00` ở cuối nên ta tiến hành pad thêm một dấu `=` ở kết quả Base64. Vậy từ `ab` khi chuyển qua Base64 sẽ là `YWI=`.
- Quay trở lại với Challenge thì đề yêu cầu ta chuyển chuỗi hex mà đề cho thành mã Base64 và submit như là **Flag**, challenge có gợi ý hãy sử dụng hàm `b64encode()` của thư viện **base64** để chuyển từ mã bytes sang mã Base64, ta thực hiện như sau:
```python
from base64 import b64encode
bytes_str = bytes.fromhex("72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf")
print(b64encode(bytes_str))
```
- ***Vậy Flag của challenge này là: crypto/Base+64+Encoding+is+Web+Safe/***.
### Bytes and Big Integers
- **Mô tả:** challenge này hướng dẫn ta cách chuyển các ký tự sang số nguyên để có thể sử dụng cho các thuật toán mã hóa vì khi tính toán phải làm việc trên số chứ không làm việc trên chữ được.
- Như đã học ở bài **ASCII** thì khi ta muốn chuyển một chữ cái sang số nguyên thì ta sử dụng hàm `ord()` đúng không? Vậy nếu ta muốn chuyển một đoạn dài hơn một ký tự thì sao? Không thể chuyển từng chữ sang số rồi cộng chúng lại được vì nó sẽ gây trùng lặp thông tin.
- Để chuyển một chuỗi ký tự sang số nguyên, ta thực hiện chuyển từng chữ sang mã hex rồi sau đó nối chuỗi các đoạn hex đó lại rồi chuyển qua số nguyên là hoàn thành, như ví dụ của đề, từ `HELLO` sẽ được chuyển thành các đoạn hex như thế này `[0x48, 0x45, 0x4c, 0x4c, 0x4f]`, sau đó ta nối chuỗi chúng lại thành `0x48454c4c4f` rồi chuyển sang số nguyên là thành công :thumbsup:
- Ta có thể thực hiện trong python như sau:
```python
text = "HELLO"
hex_text = text.encode().hex() #encode để chuyển từ kiểu string sang kiểu bytes
print(int(hex_text, 16)) #310400273487
```
- Quay trở lại với Challenge, đề yêu cầu ta chuyển dãy số nguyên khổng lồ mà đề cho thành **Flag** rồi submit, challenge cũng giới thiệu cho ta hai hàm của thư viện **PyCryptodome** có khả năng thực hiện điều trên là `long_to_bytes()` để chuyển từ số nguyên sang mã bytes và `bytes_to_long()` thực hiện ngược lại, bạn có thể dùng chúng để giải challenge này hoặc thực hiện chuyển sang hex rồi chuyển qua bytes cũng được, đều như nhau. Ta thực hiện như sau:
```python
from Crypto.Util.number import long_to_bytes
number = 11515195063862318899931685488813747395775516287289682636499965282714637259206269
print(long_to_bytes(number))
print(bytes.fromhex(hex(number)[2:])) #[2:] để bỏ đi ký tự 0x vì nếu để sẽ gây lỗi
```
- ***Vậy Flag của challenge này là: crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}***.
### Encoding Challenge
- **Mô tả:** challenge yêu cầu bạn kết nối tới sever `socket.cryptohack.org` với port là `13377` và giải mã **100** đoạn mã hóa để có **Flag**.
- Mình nghĩ challenge này không khó, chỉ là chúng ta chưa quen với cách tương tác với server thôi.
- Khi kết nối tới server, server sẽ trả lời như sau:
- Ta sẽ trả lời lại nó bằng JSON như sau:
- Nếu trả lời đúng thì nó sẽ đưa ra bài toán tiếp theo, khi ta làm được 100 bài thì challenge sẽ đưa ta flag.
- Ta không thể giải tay **100** bài được nên ta sẽ phải code.
- Đề cho ta 2 file là `13377.py` và `pwntools_example.py` với file `13377.py` là `source code` và `pwntools_example.py` là file hướng dẫn cách tương tác với server thông qua thư viện **pwntools**. Ta sẽ dựa theo file `pwntools_example.py` để giải.
- File `pwntools_example.py` như sau:
```python
from pwn import * # pip install pwntools
import json
r = remote('socket.cryptohack.org', 13377, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
received = json_recv()
print("Received type: ")
print(received["type"])
print("Received encoded value: ")
print(received["encoded"])
to_send = {
"decoded": "changeme"
}
json_send(to_send)
json_recv()
```
- Ta sẽ chú ý tới hai hàm là hàm `json_recv()` và hàm `json_send()`.
- Ta sử dụng hàm `json_recv()` để nhận chuỗi **JSON** từ server, chuỗi JSON đó sẽ trông như thế này: **{"type": encoding, "encoded": encoded}** với encoding là các kiểu mã hóa mà challenge random ra, bao gồm **["base64", "hex", "rot13", "bigint", "utf-8"]**.
- Còn hàm `json_send()` ta sẽ dùng nó để gửi chuỗi JSON chứa **decoded** tới server.
- Hướng dẫn:
- Ta gọi hàm `json_recv()` để nhận file JSON từ server.
- Sau đó ta chia file JSON đó ra làm hai là phần `encoding` và `encoded` như sau:
```python
received = json_recv()
encoding = received['type']
encoded = received['encoded']
```
- Ta biết rằng `encoding` là kiểu mã hóa nên ta sẽ dùng điều kiện để xét từng kiểu mã hóa của `encoding` rồi giải mã `encoded`:
```python
if encoding == "base64":
decoded = base64.b64decode(encoded).decode()
elif encoding == "hex":
decoded = bytes.fromhex(encoded).decode()
elif encoding == "rot13":
decoded = codecs.decode(encoded, "rot13")
elif encoding == "bigint":
decoded = Crypto.Util.number.long_to_bytes(int(encoded, 16)).decode()
elif encoding == "utf-8":
decoded = "".join(chr(o) for o in encoded)
```
- Các bước trên là các bước để giải mã `encoded`, bây giờ ta sẽ dùng hàm `json_send()` để gửi json chứa `decoded` tới server.
- Ta có hàm `to_send()` như sau:
```python
to_send = {
"decoded": "changeme"
}
json_send(to_send)
```
- Ta sẽ thay "**changeme**" thành decoded:
```python
to_send = {
"decoded": decoded
}
json_send(to_send)
```
- Vậy là ta đã hoàn thành phần code dùng để nhận file JSON và gửi lại file JSON cho server, Vì đề yêu cầu giải **100** bài nên ta sẽ đặt vào vòng lặp **100** lần.
- Cuối cùng ta sẽ sử dụng hàm `interactive()` để nhận flag khi đã lặp đủ **100** lần:
```python
r = remote('socket.cryptohack.org', 13377, level = 'debug')
r.interactive()
```
- Code giải: `a.py`
```python
from pwn import*
import json
import base64
import codecs
import Crypto.Util.number
r = remote('socket.cryptohack.org', 13377, level = 'debug')
def json_recv():
line = r.recvline()
return json.loads(line.decode())
def json_send(hsh):
request = json.dumps(hsh).encode()
r.sendline(request)
for i in range(100):
print(f"line {i+1}")
received = json_recv()
encoding = received['type']
encoded = received['encoded']
if encoding == "base64":
decoded = base64.b64decode(encoded).decode()
elif encoding == "hex":
decoded = bytes.fromhex(encoded).decode()
elif encoding == "rot13":
decoded = codecs.decode(encoded, "rot13")
elif encoding == "bigint":
decoded = Crypto.Util.number.long_to_bytes(int(encoded, 16)).decode()
elif encoding == "utf-8":
decoded = "".join(chr(o) for o in encoded)
to_send = {
"decoded": decoded
}
json_send(to_send)
r.interactive()
```
- **Lưu ý:** khi chạy code trên wsl thì nên chạy bằng *DEBUG*: `python3 a.py DEBUG`
- ***Vậy Flag của challenge này là: crypto{3nc0d3_d3c0d3_3nc0d3}***.
## XOR
### XOR Starter
- Mô tả: Challenge này sẽ giới thiệu cho chúng ta về **Xor**, rằng Xor là gì, và cách để Xor hai kiểu dữ liệu.
- Xor hay đầy đủ là **Exclusive Or**, tức là cách nó hoạt động ngược lại với hàm Or. Khi ta thực hiện phép Xor hai dãy bit **cùng độ dài**, nó sẽ trả về giá trị là $0$ (tức là sai) nếu hai bit đang xét giống nhau và sẽ trả về $1$ (đúng) nếu hai bit đang xét khác nhau.
- Người ta thường ký hiệu Xor bằng ký tự **⊕**, nhưng trong khi lập trình thì ta sẽ dùng ký tự này **"^"**.
- Ví dụ: hãy tính $1101 ⊕ 0100$. Đầu tiên phải kiểm tra chiều dài của hai dãy bit, nếu chúng bằng nhau thì ta sẽ bắt đầu xor, nếu không thì ta thêm các bit $0$ để chúng dài bằng nhau. Ta sẽ xor từng bit của 2 dãy bit trên, đầu tiên là xor $1$ và $0$ sẽ được $1$, xor $1$ và $1$ được $0$, xor $0$ và $0$ được $0$ và cuối cùng xor $1$ và $0$ sẽ được $1$. Vậy kết quả là: $1101 ⊕ 0100 = 1001$.
$$\begin{matrix}
1 & 1 & 0 & 1\\
\bigoplus & \bigoplus & \bigoplus & \bigoplus \\
0 & 1 & 0 & 0 \\
= & = & = & = \\
1 & 0 & 0 & 1
\end{matrix}$$
- Khi lập trình, ngoài xor hai dãy bit thì ta có thể xor hai kiểu dữ liệu Integer với nhau, Ví dụ:
```python
print(13^9)
#output sẽ là 4
```
- Hướng dẫn giải:
- Đề bài cho ta một chuỗi là **"label"** và số nguyên **13**, đề bài yêu cầu ta hãy xor **từng ký tự** của chuỗi **label** với số **13** và ta sẽ được chuỗi mới, gắn chuỗi đó vào **crypto{...}** và ta sẽ có được Flag.
- Vì đề bài yêu cầu phải Xor từng ký tự với số 13 nên ta phải biến đổi từng ký tự đó về kiểu dữ liệu Integer thì mới Xor được với số 13.
- Ta sẽ sử dụng hai hàm đó là hàm **chr()** và hàm **ord()**, hàm **chr()** sẽ có tác dụng biến một kiểu dữ liệu Integer sang kiểu dữ liệu ASCII tương ứng, còn hàm **ord()** sẽ thực hiện ngược lại.
- Ta sẽ dùng vòng lặp **For**, cho **i** chạy qua từng ký tự của **"label"**, rồi dùng hàm **ord()** để chuyển ký tự đó sang Integer, sau đó Xor số 13 với kiểu Integer ta vừa mới chuyển đổi, rồi ta dùng hàm chr() để đổi kiểu dữ liệu ta vừa mới Xor được sang lại ASCII.
- Vd: khi i = "l", hàm ord() sẽ chuyển chữ "l" thành số 118, sau đó xor số 108 với số 13 sẽ được số 97, cuối cùng ta dùng hàm chr() chuyển từ số 97 thành chữ "a"
- Đoạn Code sẽ như sau:
```python
string = "label"
for i in string:
int_value = ord(i)
new_int = int_value ^ 13
new_string = chr(new_int)
print(new_string, end="")
#output sẽ là aloha
```
- ***Vậy Flag của challenge này là: crypto{aloha}***.
### XOR Properties
- Mô tả: Challenge này sẽ giới thiệu chúng ta về các tính chất của Xor bao gồm **Commutative** (giao hoán), **Associative** (kết hợp), **Identity** (đồng nhất) và **Self-Inverse** (nghịch đảo).
- Xor có những tính chất sau:
- Commutative: $A ⊕ B = B ⊕ A$
- Associative: $A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C$
- Identity: $A ⊕ 0 = A$
- Self-Inverse: $A ⊕ A = 0$
- Hướng dẫn giải:
- Chú ý vào hàng cuối cùng vì nó có chứa $Flag$, như ta thấy thì hàng cuối là kết quả của: $$Flag ⊕ key_1 ⊕ key_3 ⊕ key_2$$
- Để giải ra được $Flag$ thì ta phải triệt tiêu đi $key_1 ⊕ key_3 ⊕ key_2$ bằng cách sử dụng hai tính chất là nghịch đảo và giao hoán. Ta sẽ xor $Flag ⊕ key_1 ⊕ key_3 ⊕ key_2$ với $key_1 ⊕ key_3 ⊕ key_2$ vì khi ta xor $key_1$, $key_2$, $key_3$ với chính nó thì chúng sẽ triệt tiêu và còn lại giá trị $0$, mà khi xor với $0$ thì không đổi nên ta sẽ còn lại $Flag$.
- Lưu ý: đoạn mã đề cho là mã hex nên ta phải chuyển thành kiểu số nguyên thì mới xor được với nhau.
- Đoạn code như sau:
```python
from Crypto.Util.number import*
def xor(a, b):
return a^b
k1=int('a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313',16)
k2k1=int('37dcb292030faa90d07eec17e3b1c6d8daf94c35d4c9191a5e1e',16)
k3k2=int('c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1',16)
fk1k3k2=int('04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf',16)
flag = xor(xor(fk1k3k2, k3k2), k1)
flag1 = long_to_bytes(flag).decode()
#ta dùng hàm long_to_bytes để chuyển kiểu số nguyên ở tên thành kiểu bytes rồi dùng hàm .decode() để chuyển thành kiểu ASCII.
print(flag1)
#ta sẽ được output là: crypto{x0r_i5_ass0c1at1v3}
```
- ***Vậy Flag của challenge này là: crypto{x0r_i5_ass0c1at1v3}***.
### Favourite byte
- Kể từ challenge này thì ta phải xor hai giá trị khác nhau về **chiều dài byte**, ta sẽ không dùng ký hiệu "**^**" để xor nữa mà sẽ dùng hàm **xor()** từ thư viện **pwn**.
- Khai báo hàm **xor()** như sau: `from pwn import*`.
- Sử dụng như sau:
```python
from pwn import*
data = b'label'
hint = 13
output = xor(data, hint)
print(output)
#output sẽ là b'aloha'
```
- Mô tả Challenge: đề cho ta output `73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d` là kết quả của **Flag ⊕ byte nào đó**. Việc ta cần làm là tìm ra byte bí mật đó và **xor ngược lại với output**. Ta sẽ có hai hướng giải challenge này.
- Hướng giải 1:
- Ta biết rằng một byte có đến **256 giá trị**, ta có thể lấy output xor lần lượt với 256 giá trị byte đó, khi nào xor với byte chính xác thì nó sẽ trả lại cho ta flag.
- Đoạn code như sau:
```python
from pwn import*
data = bytes.fromhex("73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d")
for i in range(256):
output = xor(i, data)
if b"crypto{" in output: #chỉ in ra output chứa format của flag
print(output)
#output sẽ là b'crypto{0x10_15_my_f4v0ur173_by7e}'
```
- Hướng giải 2:
- Ta biết format của flag là `crypto{...}` nên ta sẽ xor output với 7 bytes đầu của flag là `b'crypto{'` thì sẽ có được byte bí mật mà đề dùng để xor với flag:
```python
from pwn import*
data = bytes.fromhex("73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d")
form = b'crypto{'
print(xor(data, form))
#output sẽ là b'\x10\x10\x10\x10\x10\x10\x10C\x1aXP;N^,\x0f\x10?\x02K\x1dC\x17\x1bQSL4\x11\x1b^\x05\x19'
```
- Ta thấy 7 bytes đầu của output là `\x10`, tức `\x10` là bytes bí mật, bây giờ việc còn lại chỉ là xor byte bí mật đó với output.
```python
from pwn import*
data = bytes.fromhex("73626960647f6b206821204f21254f7d694f7624662065622127234f726927756d")
secret_byte = b'\x10'
print(xor(data, secret_byte))
#output sẽ là b'crypto{0x10_15_my_f4v0ur173_by7e}'
```
- ***Vậy Flag của challenge này là: crypto{0x10_15_my_f4v0ur173_by7e}***.
### You either know, XOR you don't
- **Mô tả**: Challenge này xor **flag** với **key nào đó** và yêu cầu ta đi tìm flag, nó gần gần giống với challenge trước.
- Challenge này với challenge trước có điểm chung là nó xor **flag** với một **key nào đó**, khác ở chỗ ở challenge trước thì key này là **1 byte bất kì**, còn ở challenge này **key** không còn là 1 byte nữa.
- Hướng dẫn:
- Vì đề gợi ý là hãy nhớ format của flag nên ta sẽ xor dữ kiện đề cho với **"crypto{"**.
```python
from pwn import xor
data = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104')
hint = b'crypto{'
output = xor(hint, data)
print(output)
#output là b'myXORke+y_Q\x0bHOMe$~seG8bGURN\x04DFWg)a|\x1dTM!an\x7f'
```
- Nhìn vào 7 bytes đầu của output ta đoán rằng **key** của challenge này sẽ là **b'myXORkey**.
- Để kết thúc challenge thì ta sẽ xor dữ kiện của đề với **key** mà ta vừa kiếm được, đoạn code sẽ như sau:
```python
from pwn import xor
data = bytes.fromhex('0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104')
key = b'myXORkey'
flag = xor(key, data)
print(flag)
#output sẽ là: b'crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}'
- ***Vậy flag của challenge này sẽ là: crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}***.
### Lemur XOR
- **Mô tả:** Challenge này cho ta hai file hình là `lemur.png`và `flag.png`. Đề yêu cầu ta XOR hai file hình đó lại, flag sẽ nằm trong output.
- Ta sẽ cài đặt thư viện `PIL` để dùng một số phương thức như `.open()`, `.new()`, `.getpixel()`, `.putpixel()`, `.save()` để xử lý hình ảnh. Dùng câu lệnh `pip install pillow` để cài `PIL`.
- Hướng giải như sau:
- Đầu tiên ta phải khai báo hai ảnh mà ta cần xor, ta sẽ dùng phương thức `.open()` để mở. Câu lệnh như sau:
```python
from PIL import Image
image1 = Image.open('lemur.png')
image2 = Image.open('flag.png')
```
- Ta sẽ kiểm tra kích thước của hai file ảnh bằng phương thức `.size` như sau:
```python
from PIL import Image
image1 = Image.open('lemur.png')
image2 = Image.open('flag.png')
print(image1.size, image2.size)
#output sẽ là (582, 327) (582, 327), chứng tỏ hai file có kích thước giống nhau
```
- Vì kích thước hai file ảnh là giống nhau nên ta có thể xor bình thường.
- Ý tưởng của ta là tạo ra một file ảnh rỗng, rồi sau khi xor từng pixel của hai tấm ảnh kia thì sẽ thêm pixel đó vào ảnh rỗng.
- Ta tạo ảnh rỗng có kích thước bẳng ảnh 1 và ảnh 2 bằng phương thức `.new()`, câu lệnh như sau:
```python
result_image = Image.new('RGB', (582, 327))
```
- Giờ ta sẽ tiến hành xor từng pixel của hai file ảnh kia
- Ta sẽ dùng hai vòng lặp và dùng phương thức `.getpixel()` để lấy từng pixel của ảnh:
```python
for x in range(582):
for y in range(327):
pixel1 = image1.getpixel((x, y)) #pixel1 sẽ là kiểu tuple lưu trữ 3 đối tượng là R, G, B
pixel2 = image2.getpixel((x, y))
```
- Sau khi có được giá trị pixel1 và pixel2 giờ ta sẽ $\oplus$ chúng.
- Vì một pixel là một tuple lưu trữ 3 giá trị $(R,G,B)$ nên ta sẽ thực hiện lấy từng màu trong pixel ra rồi xor:
```python
pixel1 = image_1.getpixel((x,y))
pixel2 = image_2.getpixel((x,y))
R = pixel1[0] ^ pixel2[0]
G = pixel1[1] ^ pixel2[1]
B = pixel1[2] ^ pixel2[2]
```
- Khi có được 3 giá trị **(R,G,B)**, ta sẽ đặt chúng vào một tuple:
```python
pixel3 = tuple((R,G,B))
```
- Sau khi có được pixel màu đã xor thì mình sẽ chuyển nó vào ảnh rỗng `result_image` đã tạo lúc trước. Đoạn code như sau:
```python
result_image.putpixel((x, y), pixel3)
```
- Xong xuôi các bước trên thì mình sẽ dùng phương thức `.save()` để lưu ảnh.
```python
result_image.save('output.png')
```
- Đoạn code hoàn chỉnh:
```python
from PIL import Image
image_1 = Image.open("flag.png")
image_2 = Image.open("lemur.png")
width, height = image_1.size
image_3 = Image.new("RGB", (width, height))
for x in range(width):
for y in range(height):
pixel_1 = image_1.getpixel((x,y))
pixel_2 = image_2.getpixel((x,y))
R = pixel_1[0] ^ pixel_2[0]
G = pixel_1[1] ^ pixel_2[1]
B = pixel_1[2] ^ pixel_2[2]
pixel_3 = tuple((R,G,B))
image_3.putpixel((x,y), pixel_3)
image_3.save("output.png")
```
- `image_3.png`
- ***Vậy cờ của challenge này là: crypto{X0Rly_n0t!}***.
## MATHEMATICS
### Greatest Common Divisor
- Mô tả: Challenge này sẽ giới thiệu cho chúng ta **The Greatest Common Divisor** (GCD) là gì và cách dùng **thuật toán Euclid** để tìm GCD.
- **The Greatest Common Divisor** (GCD) tiếng việt là **Ước chung lớn nhất**. Ước chung lớn nhất là số nguyên dương lớn nhất là ước số chung của các số đó. Ví dụ ước chung lớn nhất của $6$ và $15$ là $3$, kí hiệu $GCD(6, 15) = 3$.
- Hai số **a** và **b** được gọi là **số nguyên tố cùng nhau** nếu có $GCD(a, b) = 1$.
- Để tính GCD thì ta có nhiều cách nhưng bây giờ ta sẽ sử dụng **thuật toán Euclid** để tính GCD.
- Thuật toán Euclid để tìm GCD của $a$ và $b$ có thể viết thành một dãy các phương trình như sau như sau:
$$\begin{matrix}
a = q_0b+r_0 \\
b = q_1r_0+r_1 \\
r_0 = q_2r_1+r_2 \\
r_1 = q_3r_2+r_3 \\
\vdots \\
r_{N-2} = q_Nr_{N-1} + r_N\\
\end{matrix}$$
- Các số dư là $r$ luôn giảm dần theo từng bước nhưng không thể là số âm nên số dư sau cùng $r_N$ phải bằng $0$ và thuật toán dừng lại tại đó. Số dư khác không cuối cùng $r_{N−1}$ chính là ước chung lớn nhất của $a$ và $b$. Số $N$ không thể là vô hạn vì chỉ có một số lượng hữu hạn các số nguyên dương nằm giữa số dư ban đầu $r_0$ và số $0$.
- Có thể hiểu đơn giản như sau: cho hai số nguyên $a$ và $b$ với $a$ > $b$. Ta lấy $a$ % $b$ được $r$. Sau đó ta lấy $b$ % $r$ được $r_1$. Rồi lấy $r$ % $r_1$ được $r_2$. Vì các số dư luôn giảm dần nên đến một lúc nào đó $r_N$ phải bằng $0$. Số dư khác không cuối cùng $r_{N-1}$ sẽ là ước chung lớn nhất của $a$ và $b$.
- Ví dụ: tính $GCD(17, 11)$. Ta lấy $17$ % $11$ được $6$, tiếp tục lấy $11$ % $6$ được $5$, sau đó lấy $6$ % $5$ được $1$. Cuối cùng lấy $5$ % $1$ được $0$. Vì phần dư cuối cùng là $0$ nên ta sẽ lấy $1$ làm ước chung lớn nhất.
- Thuật toán tìm GCD trong python:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
```
- Hướng dẫn giải:
- Sử dụng đoạn code ở trên để tính:
```python
a = 66528
b = 52920
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
print(gcd(a, b))
#kết quả sẽ là 1512
```
- ***Vậy Flag của challenge này là 1512***
### Extended GCD
- Challenge nãy sẽ giới thiệu chúng ta về **Extended GCD** và cách để tính **EGCD**.
- **Extended GCD** hay còn gọi là **thuật toán Euclid mở rộng** là cách tìm hai số nguyên **u** và **v** sao cho:
$$a \times u + b \times v = gcd(a,b)$$
- Ta có thể chưa cần dùng thuật toán EGCD mà có thể tìm cặp số $u$ và $v$ bằng cách sau:
- Ví dụ: tìm EGCD của $81$ và $57$.
- Ta viết các dãy phương trình tìm GCD như dưới:
```
81 = 1(57) + 24
57 = 2(24) + 9
24 = 2(9) + 6
9 = 1(6) + 3
6 = 2(3) + 0
```
- Có GCD của $81$ và $57$ là $3$. Bây giờ sẽ tìm hai số $u$ và $v$ sao cho $u \times 81 + v \times 57 = 3$.
- Ta làm như sau:
- Bắt đầu bằng dòng gần dòng cuối cùng nhất là dòng $9 = 1(6) + 3$ ta viết lại thành $3 = 9 - 1(6)$.
- Sử dụng dòng ở trên dòng vừa rồi là $24 = 2(9) + 6$, ta biến đổi thành $6 = 24 - 2(9)$.
- Sau đó ta thế dòng $6 = 24 - 2(9)$ vào dòng $3 = 9 - 1(6)$ sẽ được $3 = 9 - 1[24 - 2(9)]$ rút gọn được $3 = 3(9) - 1(24)$.
- Ta lại tiếp tục sử dụng dòng ở trên là $57 = 2(24) + 9$, viết lại thành $9 = 57 - 2(24)$.
- Sau đó thế $9 = 57 - 2(24)$ vào lại phương trình $3 = 3(9) - 1(24)$ sẽ được $3 = 3(57) - 7(24)$.
- Cuối cùng ta sử dụng dòng trên cùng là $81 = 1(57) + 24$ viết thành $24 = 81 - 1(57)$ rồi đem thế vào $3 = 3(57) - 7(24)$ ta được $3 = 10(57) -7(81)$.
- Vậy ta đã tìm được hai số $u$ và $v$ thỏa phương trình $u \times 81 + v \times 57 = 3$ là $u = -7$ và $v = 10$.
- Hai số $u$ và $v$ còn có thể giúp ta tìm nghịch đảo của $a$ trong modulo $N$, nếu $GCD(a, N) = 1$ thì tồn tại hai số $u$ và $v$ sao cho: $$u \times a + v \times N = 1$$ $$\Leftrightarrow u \times a = 1 + (-v) \times N$$ $$\Leftrightarrow u \times a \equiv 1 \hspace{1mm}(mod\hspace{1mm}N)$$
- $u$ chính là phần tử nghịch đảo của $a$ trong mod $N$. Có thể hiểu phần tử nghịch đảo $u$ là số $u$ nào đó khi nó nhân cho $a$ và đem đi % $N$ sẽ được $1$.
- Ví dụ: tìm $x$ sao cho $5 \times x ≡ 1\hspace{1mm}(mod \hspace{1mm}3)$, tức là tìm $x$ để khi $x$ nhân $5$ rồi % $3$ sẽ được $1$. Ta sẽ tìm được $x = 2$.
- **Thuật toán** Euclid mở rộng như sau:
```python
{Thuật toán Euclide: a, b không đồng thời bằng 0, trả về gcd(a, b)}
function gcd(a, b);
begin
while b ≠ 0 do
begin
r:= a mod b; a:= b; b:= r;
end;
Result:= a;
end;
{Thuật toán Euclide mở rộng: a, b không đồng thời bằng 0, trả về cặp (x, y) sao cho a * x + b * y = gcd(a, b)
Về tư tưởng là ghép quá trình tính cặp số (x, y) vào trong vòng lặp chính của thuật toán Euclide.}
function Extended_gcd(a, b);
begin
(xa, ya):= (1, 0);
(xb, yb):= (0, 1);
while b ≠ 0 do
begin
q:= a div b;
r:= a mod b; a:= b; b:= r; //Đoạn này giống thuật toán Euclide.
(xr, yr):= (xa, ya) - q * (xb, yb); //Hiểu là: (xr, yr):= (xa, ya) "mod" (xb, yb);
(xa, ya):= (xb, yb);
(xb, yb):= (xr, yr);
end;
Result:= (xa, ya);
end;
```
- Hướng dẫn giải challenge:
- Ta code thuật toán EGCD như sau:
```python
def extended_euclidean_algorithm(a, b):
if b == 0:
return a, 1, 0
else:
gcd, x, y = extended_euclidean_algorithm(b, a % b)
return gcd, y, x - (a // b) * y
# Thay đổi giá trị của a và b tại đây
a = 26513
b = 32321
gcd_result, x, y = extended_euclidean_algorithm(a, b)
print(f"Ước chung lớn nhất của {a} và {b} là {gcd_result}")
print(f"Các số u và v sao cho a*u + b*v = GCD(a, b) là ({x}, {y})")
#Ước chung lớn nhất của 26513 và 32321 là 1
#Các số x và y sao cho ax + by = GCD(a, b) là (10245, -8404)
```
- ***Vậy Flag của challenge này là -8404***
### Modular Arithmetic 1
- **Mô tả**: challenge này sẽ giới thiệu chúng ta khái niệm **congruent modulo**.
- **Congruent modulo** nghĩa là đồng dư modulo, hai số nguyên $a$ và $b$ được gọi là đồng dư trong modulo $m$ nếu $a ≡ b\hspace{1mm}(mod\hspace{1mm}m)$. Tức là $a$ và $b$ sẽ cùng một **số dư** khi chia cho $m$.
- Ví dụ: $9 ≡ 1\hspace{1mm}(mod\hspace{1mm}4)$ nghĩa là $9$ % $4$ và $1$ % $4$ đều có chung kết quả là $1$.
- Hoặc ta có thể hiểu $a ≡ b\hspace{1mm}(mod\hspace{1mm}m)$ nghĩa là $a$ % $m = b$.
- Nếu $a ≡ 0\hspace{1mm}(mod\hspace{1mm}m)$ thì có nghĩa $a$ chia hết cho $m$, kí hiệu là $m | a$.
- Hướng dẫn giải challenge:
- Challenge yêu cầu chúng ta tìm $x$ và $y$, $Flag$ sẽ là **số nhỏ hơn**.
- Sử dụng tính chất $a ≡ b\hspace{1mm}(mod\hspace{1mm}m)$ $\Leftrightarrow a$ % $m = b$
- Ta sẽ code như sau:
```python
print(8146798528947 % 17)
print(11 % 6)
#Chạy chương trình và thấy 4 < 5
```
- **_Vậy flag của challenge này là 4_**.
### Modular Arithmetic 2
- Mô tả: Challenge này giới thiệu cho chúng ta về **định lí Fermat nhỏ**.
- **Định lý nhỏ Fermat nhỏ** khẳng định rằng nếu $p$ là một số nguyên tố, thì với mọi số nguyên $a$ bất kì, $a ^p - a$ sẽ **chia hết** cho $p$. $$a^{p}\equiv a\hspace{1mm}(mod\hspace{1mm}p)$$
- Ta có thể viết Định lý nhỏ Fermat nhỏ thành: $$a^{p-1}\equiv 1\hspace{1mm}(mod\hspace{1mm}p)$$
- Hướng dẫn giải challenge:
- Đề cho một số nguyên tố $p = 65537$ và một số vô cùng lớn là $273246787654^{65536}$. Bây giờ yêu cầu tính $273246787654 ^ {65536}\hspace{1mm}mod\hspace{1mm}p$.
- Ta sẽ sử dụng công thức vừa học ở trên: $a^{p-1}\equiv 1\hspace{1mm}(mod\hspace{1mm}p)$.
- Vì $p = 65537$ là số nguyên tố và số mũ là $p - 1$ thõa mãn công thức nên kết quả sẽ là $1$
- _**Vậy Flag của challenge này là 1**_.
### Modular Inverting
- **Mô tả**: challenge này sẽ đào sâu vào **phần tử nghịch đảo modulo**.
- Trong trường hữu hạn $Fp$ ($p$ là số nguyên tố), là tập hợp các số nguyên **{0,1,2,..p-1}**. Với mọi phần tử $g$ của miền $Fp$, tồn tại một số nguyên $d$ duy nhất nào đó sao cho: $$g \times d ≡ 1\hspace{1mm}(mod\hspace{1mm}p)$$
- **Chú ý**: chỉ khi $GCD(a, p) = 1$, tức $a$ và $p$ nguyên tố cùng nhau thì mới tồn tại phần tử nghịch đảo của $a$.
- Ví dụ: $x \times 6 ≡ 1\hspace{1mm}(mod\hspace{1mm}10)$, ở đây $p = 10$ và $a = 6$ không nguyên tố cùng nhau, sẽ không thể tìm được $x$ nào mà nhân với $6$ rồi đem chia cho $10$ mà ra $1$ cả.
- Nhưng nếu ta thay $p$ bằng $11$ thì kết quả sẽ khác: $x \times 6 ≡ 1\hspace{1mm}(mod\hspace{1mm}11)$, khi này $GCD(6, 11) = 1$ thì kết quả là $x = 2$. Vì $2 \times 6$ bằng $12$, và $12$ % $11 = 1$.
- Hướng dẫn giải challenge:
- Đề bài như sau: $3 * d ≡ 1\hspace{1mm}mod\hspace{1mm}1$, tìm $d$.
- Tức là đang kêu ta tìm phần tử nghịch đảo của $3$ trong modulo $13$.
- Có thể hiểu như này: tìm số nguyên $d$ nào đó nằm trong đoạn **[0,12]** sao cho nhân với $3$ rồi chia cho $13$ còn dư $1$.
```python
for i in range(13):
if (i*3) % 13 == 1: #Phần tử nào nhân 3 mà chia cho 13 còn dư 1
print(i)
```
- Hoặc bạn có thể sử dụng hàm `Pow()` trong python. $Pow(a, b, c)$ $=a^b\hspace{1mm}mod\hspace{1mm}c$.
```python
print(pow(3, -1, 13))
# Kết quả là 9
```
- **_Vậy Flag của challenge này là 9_**.
## DATA FORMATS
### Privacy-Enhanced Mail?
- **Mô tả:** Challenge này giới thiệu cho ta về **tệp PEM** và yêu cầu ta tìm **khóa d** của một file pem và submit nó như là $Flag$.
- Có thể hiểu file **pem** như là file để ta lưu các khóa của hệ mã **[RSA](https://hackmd.io/@at20n0118/S1SlizGXA)**, bao gồm cặp khóa công khai như $(e,n)$ và cặp khóa bí mật $(d,n)$. Chúng sẽ được mã hóa bằng mã **Base64**, file pem bên dưới là file pem lưu trữ cặp khóa công khai của RSA, nên nó sẽ bắt đầu bằng dòng chữ **-----BEGIN PUBLIC KEY-----** và kết thúc bằng dòng **-----END PUBLIC KEY-----**
```python
-----BEGIN PUBLIC KEY-----
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCcbCZK2epVo/MY2KFtU5PQADza
8qTM/ls0xX9LrZbvT9zj0ti1bcRiFmo9F+60U54d6xx3kuv8sBoqTZ5k5jKvlmjX
xKagmUUdzrIsLl1gO/9GxpEssaDkMQ0+cqVndmiQn9oJk7kNIw2svfYgzPJ2UFXd
Yj9N6hcZUfwp/9135wIDAQAB
-----END PUBLIC KEY-----
```
- Để chuyển một cặp khóa công khai hoặc một cặp khóa bí mật vào một file pem thì ta sử dụng phương thức `.export_key()` của thư viện **Crypto.PublicKey**, sử dụng như sau:
```python
from Crypto.PublicKey import RSA
key = RSA.generate(1024) # dùng để tạo các khóa e,d,n cho RSA
with open("public_key.pem", "wb") as f:
f.write(key.public_key().export_key())
```
- Khi ta có một file pem trong tay, ta sẽ sử dụng phương thức `.import_key()` để đọc khóa, thực hiện như sau:
```python
from Crypto.PublicKey import RSA
key = RSA.generate(1024)
with open("public_key.pem", "r") as f:
data = RSA.import_key(f.read())
# (e,n) là khóa công khai, còn d là khóa bí mật
print(data.e)
print(data.n)
```
- Lưu ý là ta không thể đọc được khóa $d$ trong file **PUBLIC KEY** nhé, vì file đó chỉ lưu $e$ và $n$, ta chỉ có thể đọc được khóa $d$ từ file **PRIVATE KEY** thôi :smile:
- Quay trở lại challenge thì đề cho ta một file pem **PRIVATE KEY** chứa khóa bí mật $d$ của RSA, nhiệm vụ của ta là đọc được khóa $d$ và submit nó.
```python
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAzvKDt+EO+A6oE1LItSunkWJ8vN6Tgcu8Ck077joGDfG2NtxD
4vyQxGTQngr6jEKJuVz2MIwDcdXtFLIF+ISX9HfALQ3yiedNS80n/TR1BNcJSlzI
uqLmFxddmjmfUvHFuFLvxgXRga3mg3r7olTW+1fxOS0ZVeDJqFCaORRvoAYOgLgu
d2/E0aaaJi9cN7CjmdJ7Q3m6ryGuCwqEvZ1KgVWWa7fKcFopnl/fcsSecwbDV5hW
fmvxiAUJy1mNSPwkf5YhGQ+83g9N588RpLLMXmgt6KimtiWnJsqtDPRlY4Bjxdpu
V3QyUdo2ymqnquZnE/vlU/hn6/s8+ctdTqfSCwIDAQABAoIBAHw7HVNPKZtDwSYI
djA8CpW+F7+Rpd8vHKzafHWgI25PgeEhDSfAEm+zTYDyekGk1+SMp8Ww54h4sZ/Q
1sC/aDD7ikQBsW2TitVMTQs1aGIFbLBVTrKrg5CtGCWzHa+/L8BdGU84wvIkINMh
CtoCMCQmQMrgBeuFy8jcyhgl6nSW2bFwxcv+NU/hmmMQK4LzjV18JRc1IIuDpUJA
kn+JmEjBal/nDOlQ2v97+fS3G1mBAaUgSM0wwWy5lDMLEFktLJXU0OV59Sh/90qI
Jo0DiWmMj3ua6BPzkkaJPQJmHPCNnLzsn3Is920OlvHhdzfins6GdnZ8tuHfDb0t
cx7YSLECgYEA7ftHFeupO8TCy+cSyAgQJ8yGqNKNLHjJcg5t5vaAMeDjT/pe7w/R
0IWuScCoADiL9+6YqUp34RgeYDkks7O7nc6XuABi8oMMjxGYPfrdVfH5zlNimS4U
wl93bvfazutxnhz58vYvS6bQA95NQn7rWk2YFWRPzhJVkxvfK6N/x6cCgYEA3p21
w10lYvHNNiI0KBjHvroDMyB+39vD8mSObRQQuJFJdKWuMq+o5OrkC0KtpYZ+Gw4z
L9DQosip3hrb7b2B+bq0yP7Izj5mAVXizQTGkluT/YivvgXcxVKoNuNTqTEgmyOh
Pn6w+PqRnESsSFzjfWrahTCrVomcZmnUTFh0rv0CgYBETN68+tKqNbFWhe4M/Mtu
MLPhFfSwc8YU9vEx3UMzjYCPvqKqZ9bmyscXobRVw+Tf9llYFOhM8Pge06el74qE
IvvGMk4zncrn8LvJ5grKFNWGEsZ0ghYxJucHMRlaU5ZbM6PEyEUQqEKBKbbww65W
T3i7gvuof/iRbOljA9yzdwKBgQDT9Pc+Fu7k4XNRCon8b3OnnjYztMn4XKeZn7KY
GtW81eBJpwJQEj5OD3OnYQoyovZozkFgUoKDq2lJJuul1ZzuaJ1/Dk+lR3YZ6Wtz
ZwumCHnEmSMzWyOT4Rp2gEWEv1jbPbZl6XyY4wJG9n/OulqDbHy4+dj5ITb/r93J
/yLCBQKBgHa8XYMLzH63Ieh69VZF/7jO3d3lZ4LlMEYT0BF7synfe9q6x7s0ia9b
f6/QCkmOxPC868qhOMgSS48L+TMKmQNQSm9b9oy2ILlLA0KDsX5O/Foyiz1scwr7
nh6tZ+tVQCRvFviIEGkaXdEiBN4eTbcjfc5md/u9eA5N21Pzgd/G
-----END RSA PRIVATE KEY-----
```
- Ta sẽ sử dụng phương thức `.import_key()` đã nhắc ở trên để đọc khóa $d$, thực hiện như sau:
```python
from Crypto.PublicKey import RSA
a = RSA.import_key(open("privacy_enhanced_mail.pem", "r").read())
print(a.d)
```
- ***Vậy Flag của challenge này là: 15682700288056331364787171045819973654991149949197959929860861228180021707316851924456205543665565810892674190059831330231436970914474774562714945620519144389785158908994181951348846017432506464163564960993784254153395406799101314760033445065193429592512349952020982932218524462341002102063435489318813316464511621736943938440710470694912336237680219746204595128959161800595216366237538296447335375818871952520026993102148328897083547184286493241191505953601668858941129790966909236941127851370202421135897091086763569884760099112291072056970636380417349019579768748054760104838790424708988260443926906673795975104689***.
### CERTainly not
- **Mô tả:** Challenge này giới thiệu về file **DER** và yêu cầu ta tìm khóa công khai $n$ của file này để submit.
- File Der cũng có phần tương tự file Pem, có một số cấu hình yêu cầu ta phải cung cấp file Der nhưng có cái chỉ cần file pem thôi, nên chúng ta cũng nên biết qua về file này. File Der cũng giúp ta mã hóa và lưu các chứng chỉ (certificate) và các cặp khóa của RSA như file Pem.
- Quay trở lại với Challenge thì đề yêu cầu ta đọc khóa công khai $n$ từ file và submit nó như $Flag$, ta cũng làm tương tự Challenge trước, lần này ta sẽ dùng **"rb"** để đọc file vì file Der lưu trữ dữ liệu dưới dạng nhị phân.
- Đoạn code như sau:
```python
from Crypto.PublicKey import RSA
with open("2048b-rsa-example-cert.der", "rb") as f:
data = RSA.import_key(f.read())
print(data.n)
```
- ***Vậy Flag của challenge này là: 22825373692019530804306212864609512775374171823993708516509897631547513634635856375624003737068034549047677999310941837454378829351398302382629658264078775456838626207507725494030600516872852306191255492926495965536379271875310457319107936020730050476235278671528265817571433919561175665096171189758406136453987966255236963782666066962654678464950075923060327358691356632908606498231755963567382339010985222623205586923466405809217426670333410014429905146941652293366212903733630083016398810887356019977409467374742266276267137547021576874204809506045914964491063393800499167416471949021995447722415959979785959569497***.
### SSH Keys
- **Mô tả:** challenge này giới thiệu về **Secure Shell Protocol** (SSH) và yêu cầu ta lấy được khóa $n$ từ file **pub** mà đề cho để submit như $Flag$.
- SSH là một chương trình tương tác giữa máy chủ và máy khách có sử dụng cơ chế mã hoá đủ mạnh nhằm ngăn chặn các hiện tượng nghe trộm, đánh cắp thông tin trên đường truyền.
- Quay trở lại với Challeng thì file pub cũng lưu trữ khóa RSA tương tự như file pem nên ta vẫn có thể làm như những bài trước để đọc được khóa RSA mã hóa trong file.
- Đoạn code như sau:
```python
from Crypto.PublicKey import RSA
f = open('bruce_rsa.pub','rb').read()
flag = RSA.importKey(f)
print(flag.n)
```
- ***Vậy Flag của challenge này là: 3931406272922523448436194599820093016241472658151801552845094518579507815990600459669259603645261532927611152984942840889898756532060894857045175300145765800633499005451738872081381267004069865557395638550041114206143085403607234109293286336393552756893984605214352988705258638979454736514997314223669075900783806715398880310695945945147755132919037973889075191785977797861557228678159538882153544717797100401096435062359474129755625453831882490603560134477043235433202708948615234536984715872113343812760102812323180391544496030163653046931414723851374554873036582282389904838597668286543337426581680817796038711228401443244655162199302352017964997866677317161014083116730535875521286631858102768961098851209400973899393964931605067856005410998631842673030901078008408649613538143799959803685041566964514489809211962984534322348394428010908984318940411698961150731204316670646676976361958828528229837610795843145048243492909***.
### Transparency
- Mô tả: Challenge này giới thiệu cho ta về giao thức Transport Layer Security (TSL) và này yêu cầu ta tìm tên miền phụ của cryptohack.org và truy cập vào để lấy flag.
- TLS trước đây là SSL là giao thức mật mã được thiết kế để cung cấp truyền thông an toàn qua một mạng máy tính.
- Hướng dẫn:
- Để giải challenge này có nhiều cách nhưng mình sẽ dùng cách dễ nhất để tìm tên miền phụ.
- Để tìm tên miền phụ của một Web nào đó thì ta có thể truy cập vào trang Web sau: https://crt.sh.
- Ta nhập địa chỉ cryptohack.org vào ô tìm kiếm để tìm tên miền phụ.
- Ta thấy tên miền này trùng với tên challenge nên ta sẽ truy cập vào.
- Đường dẫn này sẽ cho ta Flag của challenge.
- ***Vậy Flag của challenge này là: crypto{thx_redpwn_for_inspiration}***.
# END
Sign in with Wallet
Connect another wallet