---
# System prepended metadata

title: 'TASK 1 - Encode,Xor,Math'

---


# MỘT SỐ KHÁI NIỆM CƠ BẢN TRONG CRYPTO
* **Cryptography(Mật mã học)**: là việc thực hành và nghiên cứu các giao thức trao đổi thông tin an toàn mà không bị bên thứ ba can thiệp và tổn hại.
* **Cryptanalysis**: là quá trình phân tích và giải mã các hệ thống mật mã nhằm khám phá các lỗ hổng và tìm ra cách phá vỡ mã hóa.
* **Encode(mã hoá):** là quá trình chuyển đổi dữ liệu từ một định dạng cụ thể sang một định dạng khác theo quy chuẩn nhất định. Quá trình này giúp giảm dung lượng lưu trữ, tăng tốc độ truyền tải dữ liệu. Encode cũng là thuật ngữ thường được áp dụng để mô tả việc mã hóa các loại dữ liệu như âm thanh, ký tự, hình ảnh hoặc video.
    * VD: chuỗi `'Hello'` sau khi được mã hoá sang base64 sẽ là: `b'SGVsbG8='`.
* **Decode(giải mã):** là quá trình chuyển đổi dữ liệu từ dạng đã mã hóa thành dạng gốc hoặc dạng có thể đọc được bởi con người và máy tính; được thực hiện bằng cách loại bỏ các thao tác mã hóa để chuyển đổi dữ liệu về dạng ban đầu.
    * VD: chuỗi nhị phân `00001010` sau khi decode sẽ là: `10`
* **Encrypt(Mã hoá):** Là hành động biến *plaintext* thành dạng *ciphertext*.
* **Decrypt(Giải mã):** Là hành động đưa *ciphertext* về *plaintext* sử dụng *cipher* và *key* phù hợp.
    * **Plaintext (Bản rõ):** là thông tin ban đầu chưa được che giấu. Nó có thể ở dạng văn bản, hình ảnh, video hoặc bất kỳ định dạng khác. Plaintext có thể dễ dàng đọc và hiểu bởi bất kỳ ai có quyền truy cập vào nó nên nó cần được che dấu và bảo vệ. 
    * **Ciphertext (Bản mã):** Là kết quả của quá trình mã hoá plaintext, là dạng dữ liệu đã được che giấu. Ciphertext là vô nghĩa với các bên khác, ngoại trừ các bên trao đổi thông tin với nhau.
    * **Key (Khoá):** Còn gọi là cryptographic key (khoá mật mã), là một mẩu thông tin dưới dạng chuỗi số hoặc chữ cái, được sử dụng trong quá trình mã hoá và giải mã. Key là thành phần tối quan trọng, cần được giữ kín. Nếu key bị lộ, bất kỳ ai có được key cũng có thể biết được nội dung của plaintext.
    * **Cipher:** Là thuật toán dùng để mã hoá và giải mã dữ liệu.
    * **Decipher (Phá mã):** Là thuật toán dùng để tấn công vào ciphertext với mục tiêu tiếp cận đến plaintext mà không cần tới key.
* **Symmetric cryptography(mã hoá đối xứng):** còn được gọi là *mật mã khóa bí mật*, là phương pháp mã hóa tin nhắn đơn giản nhất. Nó liên quan đến việc sử dụng một khóa duy nhất cho cả quy trình mã hóa và giải mã. Khóa này có thể là một chuỗi bit, một thuật toán toán học hoặc một tập hợp các từ ngẫu nhiên chỉ có người tạo và người nhận biết. Cả bên gửi và bên nhận đều sử dụng cùng một khóa, do đó có thuật ngữ “đối xứng”. Khóa được giữ bí mật và phải được trao đổi một cách an toàn.
* **Asymmetric cryptography(mã hoá bất đối xứng):** còn được gọi là *mã hóa khóa công khai*, là một kỹ thuật mã hóa hiện đại sử dụng một cặp khóa công khai và riêng tư. Khóa công khai có sẵn cho bất kỳ ai, trong khi khóa riêng vẫn được giữ bí mật.
* **Block Cipher**: là một phương pháp mã hóa trong đó dữ liệu được chia thành các khối có kích thước cố định (ví dụ: 64-bit hoặc 128-bit), và mỗi khối được mã hóa độc lập bằng một thuật toán và một khóa mã hóa.
    * VD: thuật toán AES(Advanced Encryption Standard)
- **Stream Cipher**: là một phương pháp mã hóa trong đó dữ liệu được xử lý từng bit hoặc từng byte tại một thời điểm. Nó sử dụng một keystream (luồng khóa) để mã hóa dữ liệu gốc.
    - VD: thuật toán RC4(Rivest Cipher 4)
- **Hash function(Hàm băm)**: là hàm nhận một input đầu vào, từ input đó tạo ra một giá trị output (hay còn gọi là “hash value” – “giá trị băm”) tương ứng. Giá trị đầu vào có thể có độ dài tuỳ ý nhưng giá trị băm thì luôn có độ dài cố định. Hash function là hàm mã hoá một chiều.
    - VD: chuỗi `'Hello'` sau khi dùng hàm băm MD5 sẽ là: `8b1a9953c4611296a827abf8c47804d7`
# CHALLENGES TRONG CRYPTOHACK
## INTRODUCTION
### Finding Flags:
![image](https://hackmd.io/_uploads/B11I_bmQ1e.png)
- Challenge này cho ta làm quen với cờ, có dạng `crypto{...}`.
- Copy cờ `crypto{y0ur_f1rst_fl4g}` vào khung bên dưới và nộp để hoàn thành.

### Great Snakes:
![image](https://hackmd.io/_uploads/H17GcZmQ1l.png)
- Tải tệp Python đính kèm và chạy code sẽ tìm được cờ.
- ![image](https://hackmd.io/_uploads/SJtKobm71l.png)

### Network Attacks:
![image](https://hackmd.io/_uploads/BJ3Bn5SQJe.png)
- Challenge này yêu cầu kết nối đến server và tương tác bằng `JSON`.
    - Cú pháp của JSON có 2 phần đó là `key` và `value`.
    - Chuỗi JSON được bao lại bởi dấu ngoặc nhọn {}.
    - Các *key, value* của JSON bắt buộc phải đặt trong dấu nháy kép.
    - Nếu có nhiều dữ liệu (nhiều cặp key => value) thì dùng dấu phẩy `,` để ngăn cách.
- Cách giải:
    - Kết nối tới `socket.cryptohack.org`trên cổng `11112` bằng lệnh ==nc socket.cryptohack.org 11112== trên wsl.
    ![image](https://hackmd.io/_uploads/ByTpHiHX1g.png)
    - Sau đó gửi một đối tượng JSON với khóa `buy` và giá trị `flag` ta sẽ được cờ.
    ![image](https://hackmd.io/_uploads/ByGIUiSXkg.png)

## ENCODING
### ASCII:
![image](https://hackmd.io/_uploads/Sy7Jcanxke.png)
* Mô tả: đổi các số nguyên trong mảng thành mã ascii tương ứng để tìm cờ.
* Hướng dẫn: dùng hàm *chr()* để chuyển số nguyên sang kí tự ASCII, ngược lại dùng hàm *ord()*.
* Code:
    ```python
    arr = [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 arr:
    print(chr(i), end = '')
    #KQ: crypto{ASCII_pr1nt4bl3}
    ```    
* Vậy cờ của challenge này: *crypto{ASCII_pr1nt4bl3}*
### Hex:
![image](https://hackmd.io/_uploads/BJSj0Thgkx.png)
* Mô tả: cờ được mã hoá thành chuỗi hex, giải mã thành byte để tìm cờ.
* Hướng dẫn: dùng hàm **bytes.fromhex()** để chuyển hex thành bytes và ngược lại dùng phương thức **.hex()**.
* Code:
```python
s = "63727970746f7b596f755f77696c6c5f62655f776f726b696e675f776974685f6865785f737472696e67735f615f6c6f747d"
s = bytes.fromhex(s)
print(s)
#KQ: b'crypto{You_will_be_working_with_hex_strings_a_lot}'

```
* Vậy cờ của challenge này: *crypto{You_will_be_working_with_hex_strings_a_lot}*

### Base64:
![image](https://hackmd.io/_uploads/SytTx1Txke.png)

* Mô tả: giải mã chuỗi hex đã cho thành byte rồi mã hoá sang base64 để tìm cờ.
* Hướng dẫn: để dùng module base64, thêm dòng *import base64*; sử dụng hàm **b64encode()** để mã hoá.
* Code:
```python
import base64
s = '72bca9b68fc16ac7beeb8f849dca1d8a783e8acf9679bf9269f7bf'
s = base64.b64encode(bytes.fromhex(s))
print(s)
#KQ: b'crypto/Base+64+Encoding+is+Web+Safe/'
```
* Vậy cờ cần tìm: *crypto/Base+64+Encoding+is+Web+Safe/*

### Bytes and Big integers:
![image](https://hackmd.io/_uploads/rkLem-Tgke.png)
* Mô tả: chuyển đổi số nguyên đã cho thành byte để tìm cờ
* Hướng dẫn: dùng hàm **bytes_to_long()** để chuyển chuỗi byte sang 1 số nguyên, ngược lại dùng hàm **long_to_bytes()**. Thêm dòng `from Crypto.Ulti.number import*`.
* Code:
```python
from Crypto.Util.number import *
n = 11515195063862318899931685488813747395775516287289682636499965282714637259206269
n = long_to_bytes(n)
print(n)
#KQ: b'crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}'
```
* Vậy cờ cần tìm: *crypto{3nc0d1n6_4ll_7h3_w4y_d0wn}*

### Encoding challenge:
![image](https://hackmd.io/_uploads/Hk1GpbUmkg.png)
- 13377_py:
    ```python
    #!/usr/bin/env python3

	from Crypto.Util.number import bytes_to_long, long_to_bytes
	from utils import listener # this is cryptohack's server-side module and not part of python
	import base64
	import codecs
	import random
	
	FLAG = "crypto{????????????????????}"
	ENCODINGS = [
	    "base64",
	    "hex",
	    "rot13",
	    "bigint",
	    "utf-8",
	]
	with open('/usr/share/dict/words') as f:
	    WORDS = [line.strip().replace("'", "") for line in f.readlines()]

    class Challenge():
        def __init__(self):
            self.no_prompt = True # Immediately send data from the server without waiting for user input
            self.challenge_words = ""
            self.stage = 0

        def create_level(self):
            self.stage += 1
            self.challenge_words = "_".join(random.choices(WORDS, k=3))
            encoding = random.choice(ENCODINGS)

            if encoding == "base64":
                encoded = base64.b64encode(self.challenge_words.encode()).decode() # wow so encode
            elif encoding == "hex":
                encoded = self.challenge_words.encode().hex()
            elif encoding == "rot13":
                encoded = codecs.encode(self.challenge_words, 'rot_13')
            elif encoding == "bigint":
                encoded = hex(bytes_to_long(self.challenge_words.encode()))
            elif encoding == "utf-8":
                encoded = [ord(b) for b in self.challenge_words]

            return {"type": encoding, "encoded": encoded}

    # This challenge function is called on your input, which must be JSON
    # encoded
    #
    def challenge(self, your_input):
        if self.stage == 0:
            return self.create_level()
        elif self.stage == 100:
            self.exit = True
            return {"flag": FLAG}

        if self.challenge_words == your_input["decoded"]:
            return self.create_level()

        return {"error": "Decoding fail"}

    import builtins; builtins.Challenge = Challenge # hack to enable challenge to be run locally, see https://cryptohack.org/faq/#listener
    listener.start_server(port=13377)
    ```
- Thư viện `codecs`: hỗ trợ xử lí các mã hoá của dữ liệu. Các hàm phổ biến trong thư viện codecs:
    - **codecs.encode()**: chuyển đổi chuỗi hoặc bytes sang một dạng mã hoá cụ thể.
    - **codecs.decode()**: giải mã 1 chuỗi đã được mã hoá.
- `rot_13`: là một thuật toán mã hoá thay thế mỗi kí tự bằng 1 kí tự cách nó 13 vị trí trong bảng chữ cái, chỉ áp dụng cho các kí tự a->z và A->Z, bỏ qua các kí tự khác. VD:
```python
    import codecs

    text = "Hello, world!"
    encoded_text = codecs.encode(text, 'rot_13')  
    decoded_text = codecs.decode(encoded_text, 'rot_13')
    print(encoded_text) 
    print(decoded_text)
    # "Uryyb, jbeyq!"
    # "Hello, world!"
```
- Hàm **interactive()**: (trong pwntools) được dùng để giao tiếp hoặc kết nối mạng từ xa.
    - Khi gọi hàm interactive(), chương trình sẽ chờ người dùng nhập dữ liệu và gửi đi, đồng thời hiển thị dữ liệu nhận được.
    ```python
    from pwn import *
    # Tạo kết nối từ xa đến máy chủ
    connection = remote("socket.cryptohack.org", 13377)
    connection.interactive()
    ```
- Code:
    ```python
    from Crypto.Util.number import*
	from pwn import*
	import json
	import codecs
	import base64
	
	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):
	    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, "rot_13")
	    elif encoding == "bigint":
	        decoded = long_to_bytes(int(encoded,16)).decode()
	    elif encoding == "utf-8":
	        decoded = "".join(chr(b) for b in encoded)
	        
	    to_send = {
	    "decoded": decoded
	    }
	    json_send(to_send)
	    
	r.interactive()
    ```
- Vậy flag cần tìm: *crypto{3nc0d3_d3c0d3_3nc0d3}*

## XOR

### XOR Starter:
![image](https://hackmd.io/_uploads/BJlXLD4Qkl.png)
- Challenge này cho ta làm quen với phép XOR (viết tắt của "Exclusive or"), thực hiện so sánh từng cặp bit trong 2 giá trị, trả về `1` khi 2 bit trong cặp bit khác nhau. Kí hiệu: `^`và **chỉ dùng cho số nguyên (int)**.
- Mô tả: cho chuỗi string `label`, thực hiện phép xor lần lượt các kí tự trong chuỗi với số nguyên `13`, sau đó chuyển kết quả sang chuỗi để tìm cờ.
- Cách làm: 
    - Dùng hàm **ord()** chuyển các kí tự sang số nguyên rồi XOR với 13.
    - Dùng hàm **chr()** chuyển kết quả các phép XOR sang kí tự.
    - Ghép lại ta được cờ.
- Code:
    ```pyhon=
    for i in "label":
        print(chr(ord(i)^13), end="")
    # aloha
    ```
- Hoặc có thể dùng hàm xor():
   ```pyhon=
    from pwn import xor
    print(xor("label".encode(),13))
    ```
>[!Note] Hàm xor()
>Nằm trong thư viện pwn, có thể xor các chuỗi bytes hoặc str với nhau.
>Trường hợp độ dài các chuỗi không bằng nhau, hàm xor() sẽ tự động lặp lại chuỗi ngắn bằng với độ dài của chuỗi dài nhất.
- Vậy flag cần tìm: *crypto{aloha}*.

### XOR properties:
![image](https://hackmd.io/_uploads/HJZ0-XUXke.png)

- Để giải quyết challenge ta sẽ vận dụng các tính chất sau của XOR:
![image](https://hackmd.io/_uploads/SyTZf7L7Jg.png)
- Do không thể XOR các chuỗi với nhau nên ta sẽ chuyển sang bytes hoặc số nguyên rồi tiến hành XOR.
    - Cách 1: chuyển sang số nguyên: đặt `0x` ở đầu mỗi chuỗi hoặc dùng `int(<chuỗi>,16)`.
    ```python=
    from Crypto.Util.number import*

    key1 = 0xa6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313
    key23 = 0xc1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1
    flagk123 = 0x04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf
    print(long_to_bytes(flagk123^key1^key23))
    ```
     ```python=
    from Crypto.Util.number import*
    
    key1 = int('a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313',16)
    key23 = int('c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1',16)
    flagk123 = int('04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf',16)
    print(long_to_bytes(flagk123^key1^key23))
    ```
    - Cách 2: chuyển chuỗi hex sang bytes: dùng hàm bytes.fromhex(), sau đó ta dùng hàm **xor()** trong thư viện `pwn` để XOR các chuỗi dạng bytes.
     ```python=
    from Crypto.Util.number import*
    from pwn import*
    
    k1=bytes.fromhex('a6c8b6733c9b22de7bc0253266a3867df55acde8635e19c73313')
    k2_3=bytes.fromhex('c1545756687e7573db23aa1c3452a098b71a7fbf0fddddde5fc1')
    flag=bytes.fromhex('04ee9855208a2cd59091d04767ae47963170d1660df7f56f5faf')
    print(xor(k1,k2_3,flag)) 
    ```
- Vậy flag là: *crypto{x0r_i5_ass0c1at1v3}*
### Favorite Byte:
 ![image](https://hackmd.io/_uploads/S1AFEzPmyg.png)
- Đề cho chuỗi hex là kết quả của phép XOR flag với 1 byte bị giấu, để tìm cờ ta cần XOR chuỗi hex với byte đó.
- 1 byte có giá trị từ 0-255, vậy nên ta sẽ dùng vòng lặp để xor từng giá trị một với chuỗi hex.
- Code:
    ```python=
    from pwn import xor

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

	for i in range(256):
	    if b"crypto" in xor(key,i):
	        print(xor(key,i))
	        break
    #b'crypto{0x10_15_my_f4v0ur173_by7e}'
    ```
- Vậy flag là: *crypto{0x10_15_my_f4v0ur173_by7e}*
### You either know, XOR you don't:
![image](https://hackmd.io/_uploads/SkRAk7vmyg.png)
- Đề cho 1 chuỗi hex là kết quả của phép xor với 1 secret key, ta không thể làm như bài trên.
- Đề gợi ý dùng format của flag là crypto{...} để tìm ra secret key đó.
- Đầu tiên, ta sẽ xor lần lượt phần đầu fomat flag với chuỗi hex:
    ```python
    from Crypto.Util.number import*
    from pwn import*

    re = '0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e263451150104'
    re = bytes.fromhex(re)
    head = b'crypto{'
    
    print(xor(head,re[:7]))
    ```
    - Kết quả: `b'myXORke'`
    - Vậy nên dự đoán `key = b'myXORkey'`
- Code:
    ```python
	from Crypto.Util.number import*
	from pwn import*
	
	re = '0e0b213f26041e480b26217f27342e175d0e070a3c5b103e2526217f27342e175d0e077e2634511501	04'
	re = bytes.fromhex(re)
	
	print(xor(b'myXORkey',re))
    #KQ: b'crypto{1f_y0u_Kn0w_En0uGH_y0u_Kn0w_1t_4ll}'
    ```

### Lemur XOR:
![image](https://hackmd.io/_uploads/SkTDtFd7Jl.png)
- Ở thử thách này ta không XOR các số hay chữ mà là XOR các byte **RGB** của 2 ảnh mà đề cho.
    - **RGB** là một hệ màu dựa trên sự kết hợp của ba màu cơ bản: đỏ (Red), xanh lá(Green) và xanh dương(Blue).
    - Hình ảnh gồm nhiều điểm ảnh(pixel), mỗi pixel sẽ chứa bộ 3 giá trị dạng `tuple(R,G,B)`.
- Ta có thể truy xuất byte RGB của từng pixel trong 1 ảnh bằng thư viện `PIL(pillow)`. Một số phương thức trong thư viện:
    - **.open()**: mở hình ảnh
    - **.size**: lấy kích thước hình ảnh.
    - **.save(file, format=None, params)**: lưu ảnh vào 1 tệp.
        - `file`: đường dẫn hoặc tên tệp muốn lưu. VD: `"image.png"` hoặc `"D:/Documents/image.png"`.
        - `format`: định dạng tệp. VD: `"PNG"`, `"JPEG"`,...
        - `params`: các tham số tuỳ chọn (có thể bỏ qua).
    - **.getpixel((x,y))**: lấy pixel tại vị trí (x,y).
    - **.putpixel()**: thay đổi pixel
    - **.new(mode,size, color)**: tạo một hình ảnh mới.
        - `mode`: chế độ màu của ảnh (trong bài này là "RGB").
        - `size`: 1 tuple chứa chiều rộng và chiều cao của ảnh, dạng (width, height).
        - `color`: nếu bỏ qua tham số này thì màu mặc định là đen (`None` hoặc `(0,0,0)`); có thể là `tuple(R,G,B)`.
- Đầu tiên tạo 1 ảnh mới có kích thước bằng với kích thước 2 ảnh đã cho: `image = Image.new('RGB', image1.size)`. 
- Tiếp theo dùng vòng lặp lồng nhau để lấy vị trí pixel của từng ảnh:
   ```python
    for x in range(width):
        for y in range(height):
            pixel_1 = image_1.getpixel((x,y))
            pixel_2 = image_2.getpixel((x,y))
    ```
- Lấy từng giá trị trong 3 giá trị của mỗi pixel rồi XOR với nhau:
    ```python
    R = pixel1[0] ^ pixel2[0]
    G = pixel1[1] ^ pixel2[1]
    B = pixel1[2] ^ pixel2[2]
    ```
- Cuối cùng dùng phương thức **.save()** để lưu ảnh.
- Code:
```python
from PIL import Image

image1 = Image.open("flag.png")
image2 = Image.open("lemur.png")

image = Image.new("RGB", image1.size)

for x in range(image1.size[0]):
    for y in range(image.size[1]):
        pixel1 = image1.getpixel((x,y))
        pixel2 = image2.getpixel((x,y))

        R = pixel1[0] ^ pixel2[0]
        G = pixel1[1] ^ pixel2[1]
        B = pixel1[2] ^ pixel2[2]

        pixel3 = tuple((R,G,B))
        image.putpixel((x,y), pixel3)

image.save("result.png")
image.show()      
```
- Kết quả:
    ![image](https://hackmd.io/_uploads/B17SDq_7ke.png)


## MATHEMATICS
### Greatest Common Divisor:
![image](https://hackmd.io/_uploads/B10KJLvXye.png)
 - Ở challenge này ta chỉ cần tìm ra ước chung lớn nhất của 2 số nguyên cho trước là a và b.
 - Ta dùng thuật toán Euclide như sau:
   ```python
     def gcd(a,b):
         if b==0:
            return a
          else:
            return gcd(b,a%b)
    print(gcd(66528,52920))
    #KQ: 1512
    ```
    - Dùng tính chất: `gcd(a,b) = gcd(b,r)` với `r = a%b`
- Hoặc có thể dùng hàm **gcd()** trong thư viện math:
    ```python
    import math
        
    print(math.gcd(66528,52920))
    ```
### Extended GCD:
![image](https://hackmd.io/_uploads/B1RHULP7Jg.png)

- Ở challenge này, ta sẽ tìm cặp số $(u,v)$ ứng với 2 số nguyên cho trước là $p$ và $q$ thông qua **thuật toán Euclide mở rộng** sao cho thoả pt: 
        ![image](https://hackmd.io/_uploads/Sk2CULwXke.png)
    - Thuật toán Euclide mở rộng được dùng để tìm cặp số nguyên $(x,y)$ thoả pt: 
$ax+by = d$ với $d = gcd(a,b)$.
    - Trường hợp $d = 1$, $x$ và $y$ lần lượt là nghịch đảo modulo của *a mode b* và *b mode a*.
- Code:
   ```python
    def extended_euclide(a,b):
        x2 = 1; x1 = 0
        y2 = 0; y1 = 1
        while (b>0):
            q = a//b
            r = a - q*b
            x = x2 - q*x1
            y = y2 - q*y1 
            a = b; b = r
            x2 = x1; x1 = x
            y2 = y1; y1 = y
        d = a; x = x2; y = y2
        return (d,x,y)

    q=32321
    p=26513
    print(extended_euclide(q,p))
    #KQ: (1, 10245, -8404)
    ```
- Số cần tìm nhỏ hơn $\Rightarrow$ -8404.

### Modular Arithmetic 1:
![image](https://hackmd.io/_uploads/SynF7wwmyg.png)
- Challenge này ta cần tìm $x$ và $y$ là **đồng dư** của $11 \bmod 6$ và $8146798528947 \bmod 17$; số nhỏ hơn sẽ là số cần tìm.
    - 2 số nguyên là đồng dư khi có cùng số dư khi chia cho cùng một số nguyên.
- Code:
   ```python
    print(11 % 6)
    print(8146798528947 % 17)
    #5
    #4
    ```

### Modular Arithmetic 2:
![image](https://hackmd.io/_uploads/SkfBIwPXyg.png)

- Challenge này giới thiệu về **định lí Fermet nhỏ** như sau:
    $$a^{p-1} \equiv 1 \pmod p$$
    - Trong đó: $p$ là số nguyên tố, $a$ là số nguyên khác bội của $p$ hay $gcd(a,p) = 1$.
- Đề cho `p=65537` là một số nguyên tố, ta dùng hàm **gcd()** kiểm tra thì được: `gcd(27324678754,p) = 1` $\Rightarrow$ áp dụng định lí Fermat nhỏ được kết quả bằng `1`.

### Modular Inverting:
![image](https://hackmd.io/_uploads/rJKojwPQ1l.png)

- Challenge này giới thiệu về **nghịch đảo modulo** của một số nguyên.
    - Định nghĩa: nghịch đảo modulo của a là một số nguyên không âm $a^{-1}$ sao cho: $a*a^{-1} \equiv 1 \pmod M$
    - Điều kiện để tồn tại nghịch đảo modulo M của a: `gcd(a,M) = 1`.
- Đề yêu cầu ta tìm nghịch đảo modulo 13 của 3 $\Rightarrow$ ta dùng thuật toán Euclide mở rộng để giải quyết.
- Code:
    ```python
    def extended_euclide(a,b):
        x2 = 1; x1 = 0
        y2 = 0; y1 = 1
        while (b>0):
            q = a//b
            r = a - q*b
            x = x2 - q*x1
            y = y2 - q*y1 
            a = b; b = r
            x2 = x1; x1 = x
            y2 = y1; y1 = y
        d = a; x = x2; y = y2
        return (d,x,y)
        print(extended_euclide(3,13))
    ```
- Sau khi chạy code, kết quả là: `(1, -4, 1)`, do nghịch đảo modulo là một số nguyên không âm nên ta sẽ lấy đồng dư của `-4` là `9` cũng là đáp án cần tìm.

## DATA FORMATS
### Privacy-Enhanced Mail?
![image](https://hackmd.io/_uploads/SkxtA5OQ1x.png)
- Mô tả: Challenge này yêu cầu tìm khoá d của file **PEM**.
- **PEM** là dạng file để lưu trữ và truyền tải khoá mật mã, chứng chỉ số... trong nhiều hệ mã (ở challenge này là hệ RSA) và được mã hoá bằng **base64**. 
- **RSA** là một hệ mã bất đối xứng, sử dụng cặp khoá công khai **(n,e)** được chia sẻ với bất cứ ai để mã hoá thông tin và cặp khoá bí mật **(n,d)** chỉ có người sở hữu mới có để giải mã thông tin.
- Tệp PEM có RSA bắt đầu bằng: `-----BEGIN RSA PRIVATE KEY-----` (hoặc `-----BEGIN RSA PUBLIC KEY-----`) và kết thúc dạng `-----END RSA PRIVATE KEY-----` (hoặc `-----END RSA PUBLIC KEY-----`).
- Một số phương thức:
    - Tạo khóa: 
    ```python
    from Crypto.PublicKey import RSA
    key = RSA.generate(2048)
    ```
    > Trong key sẽ chứa đầy đủ các thành phần của RSA: $n,e,d,p,q,u$. 
    - Xuất khóa:
    ```python
    from Crypto.PublicKey import RSA
    key = RSA.generate(2048)

	# Xuất khóa riêng (private key)
	private_pem = key.export_key()
	print(private_pem.decode())
    ```
    - Ghi khóa ra file:
    ```python
    with open("private.pem", "wb") as f:
        f.write(private_pem)
    ```
    - Đọc khóa từ file pem:
    ```python
    from Crypto.PublicKey import RSA

    with open("private.pem", "r") as f:
        pem_data = RSA.import_key(f.read())

    print(data.d)
    ```
- Code:
```python
from Crypto.PublicKey import RSA

with open ("privacy_enhanced_mail.pem","r") as f:
    key = RSA.import_key(f.read())
    
print(key.d)
```
:::spoiler Kết quả
15682700288056331364787171045819973654991149949197959929860861228180021707316851924456205543665565810892674190059831330231436970914474774562714945620519144389785158908994181951348846017432506464163564960993784254153395406799101314760033445065193429592512349952020982932218524462341002102063435489318813316464511621736943938440710470694912336237680219746204595128959161800595216366237538296447335375818871952520026993102148328897083547184286493241191505953601668858941129790966909236941127851370202421135897091086763569884760099112291072056970636380417349019579768748054760104838790424708988260443926906673795975104689
:::
### CERTainly not:
![image](https://hackmd.io/_uploads/BycwHoOXJx.png)
- Thử thách này giới thiệu về file DER.
    - Là một loại file chứa chứng chỉ hoặc khóa mã hóa được mã hóa theo định dạng DER (Distinguished Encoding Rules). Đây là một dạng nhị phân của chuẩn X.509 được sử dụng phổ biến trong RSA, TLS/SSL, và chứng chỉ số.
    - Có điểm khác với PEM: DER ở dạng nhị phân nên không thể đọc được, ngược lại PEM ở dạng văn bản (base64) nên có thể xem và chỉnh sửa.
- Thử thách này yêu cầu ta tìm modulo $n$ trong file đề cho.
- Code:
```python
from Crypto.PublicKey import RSA

with open('2048b-rsa-example-cert.der','rb') as f:
    key = RSA.import_key(f.read())
print(key.n)
```
:::spoiler Kết quả
22825373692019530804306212864609512775374171823993708516509897631547513634635856375624003737068034549047677999310941837454378829351398302382629658264078775456838626207507725494030600516872852306191255492926495965536379271875310457319107936020730050476235278671528265817571433919561175665096171189758406136453987966255236963782666066962654678464950075923060327358691356632908606498231755963567382339010985222623205586923466405809217426670333410014429905146941652293366212903733630083016398810887356019977409467374742266276267137547021576874204809506045914964491063393800499167416471949021995447722415959979785959569497
:::


### SSH Keys:
![image](https://hackmd.io/_uploads/SJ0Qhjdm1x.png)
- Khóa SSH là một cặp khóa bất đối xứng được sử dụng để xác thực và kết nối an toàn đến các hệ thống từ xa qua giao thức SSH.
- Đề yêu cầu lấy modulo $n$ từ file pub đã cho, cách truy xuất tương tự như file pem.
    > `.pub` chứa khóa công khai nên không thể lấy d.
- Code:
    ```python
    from Crypto.PublicKey import RSA

    with open('bruce_rsa.pub','rb') as f:
        key = RSA.import_key(f.read())
    print(key.n)
    ```
:::spoiler Kết quả
3931406272922523448436194599820093016241472658151801552845094518579507815990600459669259603645261532927611152984942840889898756532060894857045175300145765800633499005451738872081381267004069865557395638550041114206143085403607234109293286336393552756893984605214352988705258638979454736514997314223669075900783806715398880310695945945147755132919037973889075191785977797861557228678159538882153544717797100401096435062359474129755625453831882490603560134477043235433202708948615234536984715872113343812760102812323180391544496030163653046931414723851374554873036582282389904838597668286543337426581680817796038711228401443244655162199302352017964997866677317161014083116730535875521286631858102768961098851209400973899393964931605067856005410998631842673030901078008408649613538143799959803685041566964514489809211962984534322348394428010908984318940411698961150731204316670646676976361958828528229837610795843145048243492909
:::


### Transparency:
![image](https://hackmd.io/_uploads/SJcke2dmJe.png)
- Ta tìm tên miền phụ của cryptohack.org để có được cờ.
- Cách tìm kiếm trên crt.sh:
    - Truy cập crt.sh
    - Nhập tên miền cryptohack.org rồi search
    - Truy cập tiếp vào thetransparencyflagishere.cryptohack.org sẽ được cờ là: `crypto{thx_redpwn_for_inspiration}`	
