Một số thuật toán cơ bản được ứng dụng trong an toàn thông tin (Phần 1)
Bài đăng này đã không được cập nhật trong 3 năm
I. Giới thiệu
Thuật toán hay giải thuật là các phương pháp để giải quyết vấn về toán học và khoa học máy tính, một tập hợp hữu hạn các hướng dẫn được xác định rõ ràng, có thể thực hiện được bằng máy tính, thường để giải quyết một lớp vấn đề hoặc để thực hiện một phép tính.
Lập trình chính là để yêu cầu, chỉ thị máy thực hiện, giải quyết 1 công việc, bài toán cụ thể nào đó của cuộc sống. Mỗi bài toán thực tế sẽ có cách giải quyết khác nhau. Am hiểu và sử dụng đúng thuật toán, sẽ giúp bạn giải quyết một cách dễ dàng, cùng với độ chính xác cao trong thời gian ngắn nhất.
Vậy thì trong an toàn thông tin chúng ta đã/sẽ sử dụng thuật toán như thế nào để giải quyết được các vấn đề.
II. Tính toán trên trường số lớn Fp
VD: Thời gian cần thiết để phân tích số nguyên n ra thừa số nguyên tố bằng thuật toán nhanh nhất hiện nay:
Số chữ số thập phân | Số phép tính bits | Thời gian |
---|---|---|
giờ | ||
ngày | ||
năm | ||
năm | ||
năm | ||
năm |
1. Giải thích về trường hữu hạn
- Trường là một tập hợp với 2 phép toán (+, .) thỏa mãn các tính chất số học thông thường:
- là nhóm Abel với phép cộng
- (F \ {0}, .) là nhóm Abel với phép nhân
- Tính phân phối:
- Trường hữu hạn (còn gọi là trường Galois) là những trường có hữu hạn số phần tử, số này gọi là bậc của trường đó.
- Các phép toán trên trường hữu hạn:
- Có thể nói là có các phép toán cộng, trừ, nhân, chia số khác 0
- Phép trừ được coi như là cộng với số đối của phép cộng
- Phép chia là nhân với số đối của phép nhân
- Số lượng phần tử của một trường hữu hạn được gọi là cấp hoặc bậc của nó.
- Trường hữu hạn F cấp q nếu và chỉ nếu q là lũy thừa nguyên tố pm (trong đó p là số nguyên tố, m là số nguyên dương). Nếu thì F được gọi là trường nguyên tố, nếu được gọi là trường mở rộng.
- Trường nguyên tố với các phép toán (+, .) thực hiện theo modulo p.
- VD:
- = {0, 1, 2, 3, ..., 28}
- Phép toán cộng: vì
- Phép trừ: vì
- Phép nhân: $17.20 = 214 vì
- Phép lấy nghịch đảo: vì .
2. Phép tính cộng và trừ
- Các thuật toán cộng, trừ, nhân, chia, ... giới thiệu trong chương này phù hợp với triển khai phần mềm
- Ta giả thiết nền tảng triển khai có kiến trúc W – bit trong đó W là bội số của 8 (phổ biến là 64 – 32 bit), các hệ thống máy có công suất thấp có thể có W nhỏ hơn, VD: hệ thống nhúng W = 16 bit, thẻ thông minh W = 8 bit.
- Các bit của một W-bit là từ U được đánh số từ phải qua trái bắt đầu từ 0 đến W -1.
- Ta có = {0 ... p - 1}.
- Tính là độ dài bit của p và là độ dài từ của p
- Biểu diễn của phần tử a được lưu trữ trong một mảng của t các từ W bit, trong đó bit ngoài cùng bên phải của là bit có trọng số thấp nhất.
... |
---|
- Biểu diễn như một mảng A của các từ W-bit: VD: cho W= 8, xét , hãy biểu diễn số a = 23456789 dưới dạng mảng:
import math
a = 23456789
W = 8
p = 2147483647
def solve(a, W, p):
result = []
m = round(math.log2(p))
t = round(m/W)
n = [pow(2, i*W) for i in range(t)]
for i in n[::-1]:
result.append(math.floor(a/i))
a = a%i
return result
if __name__ == "__main__":
print(solve(a, W, p))
Còn tiếp....
All rights reserved