Bài tập lớn: Xây dựng chương trình mã hóa và giải mã Elgamal chi tiết

Tài liệu bài tập lớn xây dựng chương trình mã hóa và giải mã Elgamal. Trình bày chi tiết thuật toán, cơ sở lý thuyết và code demo ứng dụng.

• Tác giả: Vũ Tuấn Dũng
• Người hướng dẫn: Ths. Trần Phương Nhung
• Trường học: Trường Đại học Công nghiệp Hà Nội
• Chuyên ngành: An toàn và Bảo mật Thông tin
• Đề tài: Xây dựng chương trình mã hóa và giải mã Elgammal
• Loại tài liệu: Bài tập lớn
• Năm xuất bản: 2024
• Địa điểm: Hà Nội

Tóm tắt

I. Giới thiệu về Mã hóa Elgamal và Tầm quan trọng trong Bảo mật Thông tin

Mã hóa Elgamal là một trong những thuật toán mã hóa công khai được sử dụng rộng rãi để bảo vệ thông tin nhạy cảm trong các hệ thống truyền thông. Được phát triển bởi Taher Elgamal vào năm 1984, phương pháp này dựa trên bài toán logarit rời rạc (Discrete Logarithm Problem), đảm bảo độ bảo mật cao. Trong thời đại hiện nay, khi các cuộc tấn công mạng ngày càng tinh vi, Elgamal mã hóa trở thành công cụ không thể thiếu để bảo vệ dữ liệu từ các lỗ hổng bảo mật. Với cơ chế mã hóa bất đối xứng, Elgamal cho phép mọi người có thể mã hóa tin nhắn bằng khóa công khai, nhưng chỉ người sở hữu khóa bí mật mới có thể giải mã. Điều này làm cho Elgamal trở thành lựa chọn lý tưởng cho các ứng dụng bảo mật thông tin hiện đại.

1.1. Lịch sử hình thành và phát triển của Elgamal

Elgamal được tạo ra bởi nhà mật mã học Taher Elgamal vào năm 1984 như một giải pháp mã hóa công khai hiệu quả. Thuật toán này dựa trên độ khó của bài toán logarit rời rạc trong nhóm nhân của trường hữu hạn. Elgamal nhanh chóng được chấp nhận và sử dụng trong các tiêu chuẩn mã hóa quốc tế như DSA (Digital Signature Algorithm). So với RSA, Elgamal cung cấp những ưu điểm riêng biệt trong việc xử lý dữ liệu mã hóa và ký số điện tử.

1.2. Ứng dụng thực tế của Elgamal trong bảo mật hiện đại

Mã hóa Elgamal được áp dụng rộng rãi trong các hệ thống bảo mật thông tin như PGP (Pretty Good Privacy), GnuPG, và nhiều ứng dụng truyền thông an toàn. Nó cũng được sử dụng trong ký số điện tử để xác thực tính xác thực của tài liệu. Với khả năng tạo chuỗi số ngẫu nhiên độc lập cho mỗi lần mã hóa, Elgamal cung cấp mức độ bảo mật cao hơn so với các phương pháp mã hóa xác định khác, làm cho nó trở nên lý tưởng cho các ứng dụng bảo vệ dữ liệu nhạy cảm.

II. Cơ sở Toán học của Thuật toán Elgamal

Cơ sở toán học của Elgamal dựa trên số học modulo và bài toán logarit rời rạc. Thuật toán sử dụng các khái niệm như phần tử sinh, phép lũy thừa modulo, và phần tử nghịch đảo để thực hiện mã hóa và giải mã an toàn. Để hiểu rõ cách thức hoạt động của mã hóa Elgamal, cần nắm vững các phép toán số học trên modulo như phép cộng, trừ, nhân và chia trong không gian modulo. Thuật toán Euclid mở rộng được sử dụng để tìm phần tử nghịch đảo modulo, là yếu tố quan trọng trong quá trình giải mã. Ngoài ra, kiểm tra số nguyên tố Miller-Rabin giúp xác định các số nguyên tố lớn cần thiết cho việc sinh khóa an toàn.

2.1. Số học modulo và các phép toán cơ bản

Số học modulo là nền tảng của mã hóa Elgamal. Cho số nguyên a và số nguyên dương n, phép chia a cho n thu được: a = q×n + r, trong đó 0 ≤ r < n. Phép modulo trả về phần dư r, ký hiệu (a mod n). Các phép toán modulo bao gồm cộng, trừ, nhân theo quy tắc: (a±b) mod n = ((a mod n) ± (b mod n)) mod n. Phép lũy thừa modulo (a^b mod n) được tối ưu hóa bằng thuật toán bình phương và nhân để xử lý các số lớn hiệu quả.

2.2. Bài toán logarit rời rạc và độ khó tính toán

Bài toán logarit rời rạc là nền tảng của tính bảo mật Elgamal. Cho nhóm nhân modulo Z*p và phần tử sinh g, tìm x sao cho g^x ≡ y (mod p) là bài toán khó. Với các số nguyên tố p lớn (1024 bit trở lên), không có thuật toán thời đa thức được biết đến để giải quyết bài toán này. Độ khó này bảo vệ khóa bí mật khỏi các cuộc tấn công. Số nguyên tố an toàn và phần tử sinh bậc cao được chọn cẩn thận để đảm bảo mức độ bảo mật tối đa.

III. Quy trình Sinh khóa và Mã hóa trong Elgamal

Quá trình sinh khóa Elgamal bao gồm ba bước chính: chọn số nguyên tố an toàn p lớn, tìm phần tử sinh g có bậc lớn, và chọn khóa bí mật x ngẫu nhiên. Khóa công khai được tính bằng y = g^x mod p. Quá trình mã hóa Elgamal yêu cầu người gửi chọn số ngẫu nhiên k cho mỗi tin nhắn m, rồi tính C1 = g^k mod p và C2 = m × y^k mod p. Bộ (C1, C2) là bản mã hóa. Quá trình giải mã sử dụng khóa bí mật x để tính m = C2 / (C1^x) mod p. Cơ chế này đảm bảo rằng chỉ người sở hữu khóa bí mật mới có thể giải mã tin nhắn thành công.

3.1. Các bước sinh khóa công khai và khóa bí mật

Sinh khóa Elgamal bắt đầu bằng việc chọn số nguyên tố lớn p (1024 bit hoặc hơn) thông qua kiểm tra Miller-Rabin. Tiếp theo, tìm phần tử sinh g có bậc (p-1) hoặc (p-1)/2 trong nhóm Z*p. Khóa bí mật x được chọn ngẫu nhiên từ khoảng [2, p-2]. Khóa công khai y được tính bằng y = g^x mod p sử dụng thuật toán bình phương và nhân. Cặp (p, g, y) tạo thành khóa công khai, trong khi x là khóa bí mật cần được giữ kín tuyệt đối.

3.2. Chi tiết quá trình mã hóa và giải mã dữ liệu

Mã hóa Elgamal nhận bản rõ m và khóa công khai (p, g, y). Người gửi chọn số ngẫu nhiên k từ [2, p-2], tính C1 = g^k mod p và C2 = m × y^k mod p, gửi (C1, C2). Giải mã sử dụng khóa bí mật x: tính s = C1^x mod p, rồi m = C2 × s^(-1) mod p. Điều này hoạt động vì s = g^(kx) = y^k, nên C2 × s^(-1) = m × y^k × (y^k)^(-1) = m. Tính ngẫu nhiên k đảm bảo bản mã hóa khác nhau ngay cả với cùng bản rõ.

IV. Hướng dẫn Xây dựng Chương trình Mã hóa Elgamal

Xây dựng chương trình Elgamal yêu cầu thực hiện các module chính như sinh khóa, mã hóa, giải mã và xử lý file. Chương trình có thể được phát triển bằng nhiều ngôn ngữ lập trình như Python, Java, JavaScript. Giao diện người dùng (GUI) giúp người dùng dễ dàng thực hiện các thao tác mã hóa và giải mã mà không cần hiểu sâu về toán học phức tạp. Thư viện cryptography hoặc thư viện số học có sẵn có thể hỗ trợ tính toán phép lũy thừa modulo và kiểm tra số nguyên tố hiệu quả. Quản lý file cho phép lưu/tải khóa công khai, khóa bí mật, và dữ liệu mã hóa một cách an toàn.

4.1. Cách triển khai các function chính trong chương trình

Chương trình mã hóa Elgamal cần các function cốt lõi như: (1) generate_prime(n) - sinh số nguyên tố ngẫu nhiên n bit, (2) find_generator(p) - tìm phần tử sinh, (3) generate_keys(p, g) - sinh (khóa công khai, khóa bí mật), (4) encrypt(m, p, g, y) - mã hóa bản rõ, (5) decrypt(c1, c2, x, p) - giải mã bản mã, (6) mod_inverse(a, n) - tính phần tử nghịch đảo modulo. Mỗi function sử dụng thuật toán tối ưu như bình phương và nhân cho phép lũy thừa và Euclid mở rộng cho tính nghịch đảo.

4.2. Thiết kế giao diện và xử lý tương tác người dùng

Giao diện chương trình Elgamal nên bao gồm các nút bấm (button) chính: "Sinh khóa", "Mã hóa", "Giải mã", "Lưu file", "Mở file". Vùng nhập liệu cho phép nhập bản rõ hoặc bản mã hóa. Vùng hiển thị kết quả cho phép xem khóa công khai, bản mã hóa và bản rõ sau giải mã. Xử lý sự kiện đảm bảo khi người dùng bấm "Mã hóa", chương trình sẽ kiểm tra dữ liệu đầu vào, thực hiện mã hóa và hiển thị kết quả. Quản lý file cho phép lưu/tải khóa và dữ liệu mã hóa an toàn.

Trích đoạn nội dung tài liệu

CHƯƠNG 1: CƠ SỞ TOÁN HỌC 1.1 Số học trên modulo 1.1 Định nghĩa modulo Cho một số nguyên a và số nguyên dương n bất kỳ, thực hiện phép chia a cho n thì thu được thương số q và phần dư r thỏa mãn mối quan hệ sau: a = q.x +r 0≤r<n Ví dụ minh họa trên bảng 1. Minh họa thương số và phần dư khi thực hiện phép chia a cho n a = 13 n=4 13 = 3 x 4 + 1 q=3 r=1 a = -13 n=4 -13 = (-4) x 4 + q = -4 r=3 3 Tóm lại, cho một số nguyên a và số nguyên dương n thì ta định nghĩa a mod n là phần dư của phép chia a cho n. Ví dụ: 13 mod 4 = 1 và -13 mod 4 = 3 Hai số nguyên a và b được gọi là đồng dư modulo với n nếu (a mod n) = (b mod n) và được ký hiệu như sau: a ≡ b (mod n) Ví dụ: 13 ≡ 5 (mod 4) vì 13 mod 4=1 và 5 mod 4 = 1 7 ≡ −13 (mod 4) vì 7 mod 4 = 3 và −13 mod 4 = 3 1.2 Ước số 8 Ta nói rằng a chia hết cho số b khác không nếu tồn tại số m nào đó để a = m.b, trong đó m, a, b là các số nguyên. a chia hết cho b được kí hiệu là b|a và b được gọi là ước số của a.

Ví dụ các ước số dương của 15 là 1, 3, 5 và 15.3 Các phép toán trên modulo (A + B) % C = ((A % C) + (B % C)) % C (A - B) % C = ((A % C) - (B % C)) % C (A * B) % C = ((A % C) * (B % C)) % C (A / B) % C = ((A % C) * (B-1 % C)) % C  Nếu (a + b) ≡ (a + c) mod n thì b ≡ c mod n.c) mod n, thì b ≡ c mod n, khi a là nguyên tố cùng nhau với n. Ví dụ: (11 * 19) mod 7 = (11 mod 7 * 19 mod 7) mod 7 = 20 mod 7 = 6 Bảng 1.2 sau minh họa phép toán số học cộng, nhân, số đối và số nghịch đảo trên modulo 8. Số đối của số nguyên x là số nguyên y sao cho (x + y) mod 8 = 0, số nghịch đảo của số nguyên x là số nguyên y sao cho (x. Như vậy, để tìm các số đối của các số nguyên ở cột bên trái bảng cộng bằng cách quét lần lượt các phần từ trong dòng để tìm phần tử 0 và khi đó phần tử ở dòng đầu tiên ứng với cột này là số đối.

Tương tự, để tìm giá trị nghịch đảo của số bên trái của bảng nhân bằng cách quét lần lượt các phần tử trong dòng để tìm phần tử 1 và khi đó phần tử đầu tiên ứng với cột này là số nghịch đảo. Các phép toán số học trên modulo 8 + 0 1 2 3 4 5 6 7 X 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 1 2 3 4 5 6 7 0 1 0 1 2 3 4 5 6 7 2 2 3 4 5 6 7 0 1 2 0 2 4 6 0 2 4 6 3 3 4 5 6 7 0 1 2 3 0 3 6 1 4 7 2 5 4 4 5 6 7 0 1 2 3 4 0 4 0 4 0 4 0 4 9 5 5 6 7 0 1 2 3 4 5 0 5 2 7 4 1 6 3 6 6 7 0 1 2 3 4 5 6 0 6 4 2 0 6 4 2 7 7 0 1 2 3 4 5 6 7 0 7 6 5 4 3 2 1 x -x x-1 0 0 - 1 7 1 2 6 - 3 5 3 4 4 - 5 3 5 6 2 - 7 1 7 1.4, Ước chung lớn nhất (GCD) - Khái niệm: Ước chung lớn nhất của 2 số nguyên dương a và b là số lớn nhất mà cả a và b cùng chia hết. 10 ● Giải thuật Euclid Ví dụ: Tìm GCD(4864, 3458) = ? 4864 = 1*3458 + 1406 3458 = 2*1406 + 646 1406 = 2*646 + 76 646 = 5*114 + 38 76 = 2*38 + 0 Vậy GCD(4864, 3458) = 38 Thuật toán trên có thể được mở rộng để không những chỉ tính được GCD của 2 số nguyên a, b mà còn tính được các số nguyên x và y thỏa mãn ax + by = d  Giải thuật Euclid mở rộng Giải thuật Euclid mở rộng được sử dụng để giải một phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) có dạng: ax + by = c (a, b, c ∈ Z; x, y ∈ Z là ẩn) Điều kiện cần và đủ để phương trình này có nghiệm (nguyên) là 𝐺𝐶𝐷(𝑎,𝑏) là ước của c ₋ Khẳng định này dựa trên mệnh đề: Nếu d = gcd(a, b) thì tồn tại các số nguyên x, y sao cho: a.y = d ₋ Thuật toán: Input: Hai số nguyên không âm a và b với a ≥ b 11 Output: d = GCD(a, b) và các số nguyên x và y thỏa mãn ax + by = d Hình 1. Thuật toán euclid mở rộng VD: Bảng sau chỉ ra các bước của thuật toán với giá trị vào a= 814 và b= 187 Bảng 1.

Minh họa thuật toán Euclid mở rộng Vậy, gcd(814, 187) = 11, và (814) * 3 + (187) * (-13) = 11 12 1.2 Một số thuật toán trên Zn 1.1 Tìm số nghịch đảo Định nghĩa: Phần tử nghịch đảo + Cho a e Zn + Phần tử nghịch đảo (ngược theo phép nhân) của a mod n là một số nguyên xe Z, sao cho: ax = 1 mod n) + Nếu x tồn tại thì nó là duy nhất, a được gọi là khả nghịch. Phần tử nghịch đảo của a được ký hiệu là a-. (2) Nếu d > 1 thì a-1 mod n không tồn tại. Ngược lại return(x).

* Các bước tính a-1 mod n: 13 14 Ví dụ 1: n = 173, a = 1024 Dòng r0 r1 r2 q t0 t1 0 1024 173 159 5 0 1 1 173 159 14 1 1 1019 2 159 14 5 11 1019 6 3 14 5 4 2 6 953 4 5 4 1 1 953 148 5 4 1 0 4 148 805 15 Bảng 1. Minh họa cho ví dụ tính phần tử nghịch đảo Vậy 173-1 = 805 (trong Z1024) 1.2 Ak mod n Tính giá trị biểu thức z = Ak mod n ₋ Thuật toán “bình phương và nhân” ₋ Biểu diễn k dạng nhị phân bibi - 1bi - 2…b1b0, bi ∈ {0, 1} Hình 1. Các bước của thuật toán bình phương và nhân Ví dụ: Bảng sau chỉ ra các bước tính toán ak mod n, với a = 7, k = 560 = 1000110000, n = 561 Bảng 1. Các bước tính của thuật toán bình phương và nhân Giá trị f cuối cùng = 1, là đáp số cần tìm 1.3 Lý thuyết số 16 ● Các số nguyên tố Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ có ước số là 1 và chính nó.

Chúng không thể được viết dưới dạng tích của các số khác. I là số nguyên tố, nhưng không quan tâm đến nó. Xét các số nhỏ hơn 10 ta có: 2, 3, 5, 7 là số nguyên tố, vì chúng không có ước số khác 1 và chính nó; 4, 6, 8, 9, 10 không phải là số nguyên tổ. Có thể nói 2 là số chẵn duy nhất là số nguyên tố.

Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là vô hạn. Sau đây là danh sách các số nguyên tố nhỏ hơn 200: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 ● Phân tích thừa số nguyên tố ₋ Một trong những bài toán cơ bản của số học là phân tích ra thừa số nguyên tố số a, tức là viết nó dưới dạng tích của các số nguyên tố. Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán nhân các số để nhận được tích.

₋ Ta có kết luận, mọi số nguyên dương đều có phân tích duy nhất thành tích các lũy thừa của các số nguyên tố; Ví dụ: 91 = 7 * 13; 3600 = 24 * 32 * 52 17 ₋ Thông thường để tìm phân tích trên, ta phải kiểm tra tính chia hết cho các số nguyên tố từ nhỏ đến lớn và thực hiện phép chia liên tiếp cho các số nguyên tố, rồi gộp thành lũy thừa của các số nguyên tố. ● Số nguyên tố cùng nhau và GCD ₋ Hai số nguyên dương a và b không có ước chung nào ngoài 1, được gọi là nguyên tố cùng nhau. ₋ Ví dụ: 8 và 15 là nguyên tố cùng nhau, vì ước của 8 là 1, 2, 4, 8, còn ước của 15 là I, 3, 5, 15. Chỉ có 1 là ước chung của 8 và 15.

₋ Ngược lại có thể xác định ước chung lớn nhất bằng cách trong các phân tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó. Ta có phân tích: 300 = 21 * 31 * 52 và 18 = 21 * 32. ₋ Hay với mọi số nguyên tốp và số nguyễn a không là bội của p, ta luôn có: ap = a mod p ₋ Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn 18 Ví dụ. Vi 5 và 7 là các số nguyên tố.

2 và 3 không là bội tương ứng của 7 và 5, nên theo định lý Fermat ta có: 27 - 1 mod 7 = 1 (= 26 mod 7 = 64 mod 7 = 1) 35 - 1 mod 5 = 1 (= 34 mod 5 = 81 mod 5 = 1) (-2)11 - 1 mod 11 = 1 (= 210 mod 11 = 1024 mod 11 = 1) ₋ Kết quả trên được dùng trong khoa công khai. Nó cũng được sử dụng để kiểm tra tính nguyên tố của một số nguyên p nào đó, bằng cách lấy ngẫu nhiên các số a và kiểm tra xem có tính chất nêu trên không, kết luận là p nguyên tố cảng thuyết phục nếu phép thử trên dùng với nhiều lần chọn ngẫu nhiên các số a. ● Hàm Euler ₋ Cho n là một số nguyên dương.