# Một số hệ mật cơ bản


## Hệ mật vernam

Decrypt: `HELLO`
Key: `PWKAX`
Encrypt: `WAV??`

Đối với hệ mật này chỉ đơn giản là việc cộng plain-text với key trong trường modulo 26 để lấy ra kí tự tương ứng trong cipher-text.

Ví dụ ở trên:

E:

---------------------------------------------

P:H(7)    E(4)     L(11)     L(11)    O(14)
K:P(15)   W(22)    K(10)     A(0)     X(23)
---------------------------------------------
C:W(22)   A(0)     V(21)     L(11)    L(11)

---------------------------------------------

D:

## MDV - Shift cipher

Về cơ bản thì mình thấy nó cũng như vernam khác mỗi một tí là về key là một số thuộc trường Z*26, tính toán trong trường modulo 26.


Quan sát vào hàm e và d ta có thể hiểu rõ được cách mã hóa và giải mã

---------------------------------------------
P:H(7)    E(4)     L(11)     L(11)    O(14)
K:5
---------------------------------------------
C:M(12)   J(9)     Q(16)     Q(16)    T(19)

---------------------------------------------


Việc giải mã thì làm ngược lại.

## Mã Affine

Đối với hệ mật này thì sẽ sử dụng một cặp k=(a,b) để thực hiện mã hóa với hàm ax+b trong Z*26

Yêu cầu: GCD(a, 26) = 1 - Do việc giải mã cần tính (y - b)*a^(-1)



Việc mã hóa thì giống hệt như các loại trên

Đối với việc giải mã:


Cơ bản chỉ cần tính a^(-1) modulo 26 => tìm x sao cho ax đồng dư với 1 -> tính x.

Bài toán tìm khóa khi biết các từ của plain text và ánh xạ tương ứng ở cipher text -> giải hệ phương trình để tìm key là cặp a, b tương ứng

Có thể dựa vào bảng thống kê tần suất để dò key

# Hệ mật đa biểu

## Hệ vigenere


Key ở đây cũng tương ứng là một cụm từ -> chuyển thành dãy số tương ứng với bảng chữ cái tương ứng sau đó cũng thực hiện cộng trong trường modulo 26 -> được kết quả chuyển thành các chữ cái tương ứng trong bảng ta được cipher text.

Tương ứng, thì việc decrypt thì ngược lại.


## Hệ mật Hill


Mã này sẽ thực hiện chuyển plain text thành một ma trận để nhân với ma trận khóa mã người dùng chọn sao cho ma trận này có thể nghịch đảo được để có thể giải mã ngược lại.

Cách tính ma trận nghịch đảo của mã trận vuông 2x2:

tính định thức: detA = 1*4-2*3 tương ứng với vị trí trong ma trận như toán tuyến tính.

-> yêu cầu là detA != 0

Lúc này ma trận nghịch đảo là detA.(4, -3, -2, 1) (đảo đường chéo chính và phụ đồng thời đổi dấu đường chéo phụ).


Ví dụ:

`july`

key: 

Encrypt: thực hiện chuyển đổi từng kí tự trong chuỗi thành mã số tương ứng trong bảng chữ cái -> xếp thành ma trận: ở đây sẽ có 2 cách chọn ma trận là 1*2 và 2*2.

Sau đó thực hiện nhân với ma trận khóa thu được ma trận kết quả và tương ứng là bản cipher-text.

Decrypt: Thực hiện ngược lại quá trình trên

# Hệ mật thay thế không tuần hoàn

## Hệ mật khóa chạy

Như mục lớn đã nói hệ mật này thay vì sử dụng khóa lặp lại tuần hoàn thì nếu khóa ngắn hơn plain text(thường là vậy). Thì khóa sẽ được cộng thêm bằng bản plain-text sau đó thực hiện cộng modulo tương tự trong Z*26


## Hệ mật OTP


Ta thấy là từng kí tự trong plain-text sẽ được xor với khóa và ánh xạ tương ứng tạo ra từng kí tự trong cipher-text

Việc decrypt thì xor ngược lại là ra plain-text.

## Hệ mật hoán vị


Lúc này khóa nằm trong tập các hoán vị có thể có của m.


## Hệ mật tích

Là sự kết hợp của nhiều hệ mật khác nhau hoặc giống nhau

# Mã khối

Có 2 nguyên tắc thiết kể mã khối(theo Shannon):

+ Tính xáo trộn
+ Tính khuếch tán

## DES (Data Encryption Standard)


Input: Xâu bit có độ dài là 64 bit, khóa có độ dài 56 bit.
Output: Xâu bit mã hóa y đai 64 bit.


Ta có thể giải thích thuật toán ở đây -> khởi tạo điều kiện -> chia làm 2 phần left 32 bits + right 32 bits

Tiếp theo sẽ khởi tạo một khóa K1 sau đó right được kết hợp với key sau đó cộng xor với left từ đó kết quả sẽ trở thành right 32bits của vòng sau và right 32 bits của vòng 1 lại chuyển thành left 32bits của vòng 2 -> tương tự như vậy đến vòng 16 sẽ trả ra một chuỗi 64 bits là output của thuật toán DES.

Plain-text: x
Tạo xâu x0 theo hoán vị IP => lúc này x0= IP(x) = L0R0

Với L0 R0 lần lượt là 32 bits đầu và cuối

Sử dụng hoán vị ngược IP^(-1) cho xâu bit R16L16 -> sẽ thu được cipher-text.

-> y = encryption = IP^(-1)(R16L16) -> ở đây ta đã đảo ngược theo phép hoán vị left và right.

Hàm f mà ta thấy ở trên hình trên -> thực hiện phân tích quá trình:

Xâu bit A 32 bits, J dài 56 bits sau khi được xử lý sẽ cho ra xâu bits có độ dài 32 bits -> đây là bước sau ra sau khi chia ra làm 2 nửa 23 bits và trước khi cộng xor đổi vế.


Đi vào chi tiết hàm f này:

Đang xét Vòng 1:

Đầu vào là right 32bits tức là A -> sau khi được tăng bit thì lên 48 bits sau đó J độ dài 48 bits được cộng với đầu ra sau khi thực hiện biến đổi đầu ra sẽ là 32 bit để được cộng xor với left 32 bits.


### Tính chất của DES

+ Tác dụng đồng loạt: khi ta thay đổi 1 bit trong khóa sẽ gây ra tác động làm thay đổi nhiều bit trên cipher-text -> không thể đoán khóa được.
+ Tính chất bù
+ Khóa yếu: có 4 khóa yếu


+ Khóa nửa yếu: có 6 khóa nửa yếu


+ Không là nhóm dưới phép hợp hàm

### Biến thể DES

#### Double DES


Có thể thấy có 2 khóa và 2^56 cách lựa chọn cho từng khóa K1, K2.

#### Triple DES


Khá giống như mô hình double DES mỗi cái là có thêm 1 khóa K3.

## Thuật toán AES

Do DES có thể tấn công bẻ khóa về mặt lý thuyết nên họ phát triển ra AES.

Mạnh và nhanh hơn Triple DES

Các phép toán cộng và nhận được thực hiện trên các byte nằm trong trường hữu hạn GF(2^8)


Phép cộng trong đây thì xor.


### Mã nâng cao chuẩn mã AES - Rijndael

Có 128/192/256 bits và 128 bit khối dữ liệu
Chia dữ liệu thành 4 nhóm - 4 bytes



Quan sát ví dụ:



Bước subbyte sẽ thực hiện thay thế theo cột và hàng tương ứng với box.

Như 00 -> thì ta sẽ lấy hàng 0 cột 0 trong hộp thế S-box tức là 63

Ngược lại 63 sẽ lấy hàng 6 cột 3 trong hộp thế ngược InvS-box được 00


Shiftrows sẽ thực hiện dịch tương ứng dòng 1 dịch 0 dòng 2 dịch 1 vòng 3 dịch 2 vòng 4 dịch 3 sang trái.

Do đó khi thực hiện decryption sẽ phải dịch tương ứng sang phải.

Mid-column:


Sẽ lấy ra từng cột state sau đó nhân với ma trận khóa.





# Các chế độ hoạt động của mã khối

## Cấp của phần tử

Cấp của phần tử a trong nhóm G chính là số nguyên dương nhỏ
nhất m thỏa mãn: am = e, trong đó e là phần tử đơn vị của G
Kí hiệu cấp của nhóm G là ord(G) hoặc |G|; cấp của phần tử a là
ord(a) hoặc |a|.

## Nhóm xyclic

G là một nhóm xyclic nếu chứa 1 phần tử a sao cho mọi phần tử của G đều là lũy thừa nguyên nào đó của a.

a được gọi là phần tử sinh(hay phần tử nguyên thủy của nhóm G)

# Thuật toán euclide

Đây là thuật toán ta đã biết từ lâu để tính ước chung lớn nhất của a và b.


# Thuật toán euclide mở rộng


ở đây ta có thể thực hiện debug cho đến khi nào b = 0 thì x2 sẽ là nghịch đảo modulo.

# Tính hàm euler

Phân tích số ra thừa số nguyên tố:

if(n is prime){
    phi(n) = n - 1;
} else {
    phi(n) = n.(tích(1 - 1/p))
}

# Nhóm nhân Z*n

`Zn = {a thuộc Zn| (a, n) = 1}`


# Tính chất phần tử sinh


# giải hệ phương trình đồng dư


# Jacobi



Nhớ tính chất là ok.

ví dụ:


## Tính căn bậc 2 của a mod p





# Thuật toán bước lớn bước nhỏ

Tìm logarit cơ số alpha


ví dụ:


# Hệ mật KCK

## Hệ mật RSA


Mô tả:
Thực hiện chon ngẫu nhiên 2 p và q là số nguyên tố lớn

-> lúc này n là tích p và q là số cực lớn -> tính phi(n) chọn khóa e sao cho gcd của e và phi(n) bằng 1 sau đó khóa d sẽ là khóa decrypt với giá trị là e^(-1) mod phi(n).


Ví dụ:



lúc này có nhiều cách có thể tính d và hay dùng nhất là cách dùng định lý euclide mở rộng như ta đã tìm hiểu ở trên.


Sau khi xác định được key để en và de là d và e thì tùy ý ta có thể xác định qua lại giữa plain-text và cipher-text khi biết 1 trong 2.

+ Trường hợp cho biết bản tin m:

Ví dụ m = 47, c = m^e mod n

-> ta xác định m = 47, e = 211, n = 1517
Tiếp theo sẽ biến đổi 211 thành hệ nhị phân -> sử dụn bình phương có lặp xác định:


Ngược lại với việc giải mã:


## Hệ mật Rabin

Định nghĩa: với mỗi x ta tính y là ánh xạ mã hóa tương ứng với y = x^2 mod n.

=> giải mã x = d(y) = căn bậc 2 của y modulo n.



## Hệ mật xếp ba lô Merkle - Hellman


Hệ mật sẽ có 1 dãy siêu tăng M và W thỏa mãn là số nguyên tố cùng nhau => thực hiện phép hoán vị pi

Lúc này ta thực hiện mã hóa bản tin m:

Tìm dãy khóa công khai bằng việc tính W.Mpi(i) mod M với Mpi(i) là giá trị của phần tử hoán vị.

Mã hóa nhân bản tin với dãy siêu tăng là được tổng c lúc này c là cipher text.

Gửi c cho bên nhận => thực hiện decrypt lại c.

Tính W^(-1).c mode M

-> giải bài toán xếp balo với dãy lúc đầu

Sử dụng phép hoán vị để xác định lại các bit tương ứng của bản tin m.

## Hệ mật ElGamal




# Hệ mật trên đường cong Elliptic



Đầu tiên ta sẽ xác định z = y^2 trong trường mod n

Trong Z*n thì x sẽ chạy từ 0 đến n-1 -> lần lượt thử và tính z = y^2 mod n -> sau đó xác định xem z có thặng dư bậc 2 trong modulo n không nếu (jacobi = 1) có thì có điểm (x, y) là điểm năm trên đường cong eliptic.

## Hệ đường cong Elliptic




Note:

Public key: mọi người đều biết để mã hóa mẩu tin và kiểm chứng chữ ký.
Private key: chỉ người nhận biết, để giải mã bản tin hoặc tạo chữ ký

# Hàm băm

Hàm băm sẽ băm một chuỗi kí tự thành một chuỗi khác có độ dài cố định và không để giải mã lại được.

Đây còn được gọi là mã hóa một chiều

## Các kiểu tấn công hàm băm

Tấn công vét cạn
Tấn công vào tính chất kháng tiền anhrm khánh tiền ảnh có nghĩa là tìm 1 chuỗi sao cho băm ra chuỗi giống với chuỗi có sẵn.
Kháng va chạm => vì hai bản tin có thể có độ dài khác nhau nhưng hà băm sẽ băm ra 1 chuỗi hash cố định do đó sẽ có thể xảy ra việc 2 bản tin khác nhau sẽ cho ra cùng 1 bản hash giống nhau

## Tấn công ngày sinh nhật