Tài liệu Kỹ thuật: Tìm hiểu sơ đồ chữ ký điện tử elgamal và lập trình ứng

Khám phá sơ đồ chữ ký điện tử ElGamal và cách lập trình ứng dụng xác thực dữ liệu qua mạng an toàn, bảo mật hiệu quả cho hệ thống.

• Tác giả: Nguyễn Văn Linh
• Người hướng dẫn: Ths. Đặng Văn Cường
• Trường học: Viện Đại học Mở Hà Nội
• Chuyên ngành: Tin học ứng dụng
• Đề tài: Sơ đồ chữ ký điện tử Elgamal và lập trình ứng dụng để xác thực việc trao đổi dữ liệu qua mạng
• Loại tài liệu: Đồ án tốt nghiệp đại học
• Năm xuất bản: 2012
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng Quan Về Chữ Ký Số ElGamal

Chữ ký số ElGamal là một phương pháp xác thực điện tử quan trọng trong bảo mật thông tin. Khác với chữ ký tay truyền thống, chữ ký số gắn với thông báo theo kiểu logic thay vì vật lý, giúp ngăn chặn giả mạo và chối bỏ. Sơ đồ ElGamal được phát triển dựa trên bài toán logarithm rời rạc, mang lại độ bảo mật cao trong các giao dịch trên mạng. Trong bối cảnh công nghệ thông tin phát triển nhanh chóng, việc đảm bảo an toàn dữ liệu và xác thực nguồn gốc thông tin trở nên cấp thiết, đặc biệt đối với các nước đang hiện đại hóa như Việt Nam. Sơ đồ chữ ký điện tử ElGamal cung cấp giải pháp hiệu quả để bảo vệ các giao dịch số và xác minh tính toàn vẹn của dữ liệu truyền tải qua mạng máy tính.

1.1. Khác Biệt Giữa Chữ Ký Tay Và Chữ Ký Số

Chữ ký tay là bộ phận vật lý của tài liệu, được kiểm tra bằng so sánh trực tiếp. Tuy nhiên, phương pháp này dễ bị làm giả. Ngược lại, chữ ký số gắn với thông báo theo kiểu logic, có thể kiểm tra bằng thuật toán công khai. Điều này ngăn chặn khả năng giả mạo và chối bỏ hiệu quả hơn. Bản sao thông báo số được ký là đồng nhất với bản gốc, ergo phải cẩn thận ngăn chặn việc tái sử dụng.

1.2. Thành Phần Cơ Bản Của Sơ Đồ Chữ Ký Số

Sơ đồ chữ ký số gồm hai thành phần chính: thuật toán ký (bí mật) và thuật toán kiểm tra (công khai). Alice ký thông báo X bằng thuật toán Sig để tạo ra chữ ký Sig(x). Thuật toán kiểm tra Ver sau đó xác minh cặp (x, y) là hợp lệ hay không. Định nghĩa hình thức: bộ 5 (P, A, K, s, V) với P là tập bức điện, A là tập chữ ký, K là không gian khóa, s và V là các thuật toán thời gian đa thức.

II. Nền Tảng Toán Học Của ElGamal

Sơ đồ ElGamal dựa trên các nền tảng toán học vững chắc, đặc biệt là bài toán logarithm rời rạc. Để hiểu rõ hơn về độ bảo mật của sơ đồ, cần nắm vững các thuật toán toán học cơ bản. Thuật toán Euclid được sử dụng để tính ước số chung lớn nhất, trong khi thuật toán Euclid mở rộng giúp tìm các hệ số Bézout. Các định lý quan trọng như định lý Fermat nhỏ, định lý Euler hỗ trợ xây dựng các phép toán mã hóa an toàn. Ngoài ra, các thuật toán tính toán số lớn như bình phương và nhân, phép dịch trái, phép dịch phải là những công cụ thiết yếu trong việc triển khai chữ ký ElGamal hiệu quả.

2.1. Bài Toán Logarithm Rời Rạc

Logarithm rời rạc trong Zp là cơ sở lý thuyết của sơ đồ ElGamal. Bài toán này được phát biểu: cho số nguyên tố p, phần tử sinh g và phần tử h trong Zp*, tìm x sao cho g^x ≡ h (mod p). Độ khó của bài toán logarithm rời rạc đảm bảo an toàn mật mã của sơ đồ. Hiện tại, không tồn tại thuật toán thời gian đa thức để giải quyết bài toán này, làm cho ElGamal trở thành lựa chọn bảo mật lý tưởng cho các ứng dụng thực tế.

2.2. Các Thuật Toán Hỗ Trợ

Thuật toán Euclid tính GCD(a,b) hiệu quả trong thời gian O(log n). Thuật toán Euclid mở rộng không chỉ tìm GCD mà còn xác định hệ số Bézout, giúp tính toán phần tử nghịch đảo modulo. Các phép toán số lớn như nhân, dịch trái/phải được tối ưu hóa để xử lý khóa có độ dài từ 512 đến 2048 bit. Thuật toán bình phương và nhân giúp tính lũy thừa modulo nhanh chóng, là yếu tố quan trọng trong ký và xác minh chữ ký.

III. Cơ Chế Hoạt Động Của Sơ Đồ ElGamal

Sơ đồ chữ ký ElGamal hoạt động theo ba bước chính: sinh khóa, ký và xác minh. Quá trình sinh khóa bao gồm chọn số nguyên tố lớn p, phần tử sinh g của nhóm nhân Zp*, và bí mật cá nhân a. Khóa công khai là (p, g, y) với y = g^a mod p. Để ký một thông báo x, người ký tính tóm lược hash, chọn số ngẫu nhiên k, và tính hai giá trị (r, s). Người xác minh có thể kiểm tra chữ ký bằng cách dùng khóa công khai mà không cần bí mật. Độ mật của sơ đồ được đảm bảo bởi bài toán logarithm rời rạc và tính ngẫu nhiên trong quá trình ký. Một biến thể của ElGamal là chuẩn chữ ký số DSA, được sử dụng rộng rãi trong các ứng dụng thực tế.

3.1. Quá Trình Sinh Khóa Và Ký

Sinh khóa ElGamal đòi hỏi lựa chọn số nguyên tố p lớn (thường 1024-2048 bit), phần tử sinh g, và bí mật a ngẫu nhiên. Khóa công khai y = g^a mod p được công bố, bí mật a được giữ kín. Khi ký thông báo x, tính hash H(x), chọn k ngẫu nhiên (0 < k < p-1), rồi tính r = g^k mod p và s = (H(x) + ar)/k mod (p-1). Chữ ký là cặp (r, s). Tính ngẫu nhiên của k đảm bảo mỗi chữ ký là khác biệt, tăng cường bảo mật chứng thư số.

3.2. Xác Minh Chữ Ký Và Độ Bảo Mật

Xác minh chữ ký ElGamal dùng khóa công khai (p, g, y) để kiểm tra cặp (r, s). Tính g^H(x) mod p và y^r * r^s mod p, so sánh kết quả. Nếu bằng nhau, chữ ký hợp lệ. Độ mật của sơ đồ phụ thuộc vào độ khó của bài toán logarithm rời rạc. Hiến tại không tồn tại thuật toán hiệu quả để tìm a từ y mà không có bí mật k. Chuẩn DSA là phiên bản Mỹ của ElGamal, sử dụng nhóm con nguyên tố để cải thiện hiệu suất.

IV. Ứng Dụng Lập Trình ElGamal

Lập trình ứng dụng chữ ký ElGamal là bước quan trọng để triển khai sơ đồ này trong thực tế. Hàm Hash và tóm lược thông báo đóng vai trò thiết yếu, giúp chuyển đổi thông báo dài thành giá trị độ dài cố định, thường dùng SHA-256 hoặc MD5. Mô phỏng chương trình chữ ký số bao gồm các lớp xử lý: lớp SoLon quản lý số lớn và phép toán modular, lớp GUI cung cấp giao diện người dùng. Cài đặt yêu cầu máy ảo JRE (Java Runtime Environment), cho phép chạy chương trình trên mọi nền tảng. Hướng dẫn sử dụng giúp người dùng sinh khóa, ký tài liệu và xác minh chữ ký một cách dễ dàng. Ứng dụng này có thể sử dụng để xác thực trao đổi dữ liệu qua mạng an toàn, bảo vệ tính toàn vẹn và không chối bỏ trong các giao dịch điện tử.

4.1. Hàm Hash Và Xử Lý Dữ Liệu

Hàm Hash chuyển đổi thông báo độc lập dài thành chuỗi bit cố định, thường 160-256 bit. SHA-256 là tiêu chuẩn hiện đại, cung cấp độ an toàn cao. Hàm hash phải thỏa ba tính chất: dễ tính, kháng tiền ảnh và kháng va chạm. Tóm lược thông báo được tính trước khi ký, giảm kích thước dữ liệu cần xử lý. Lớp SoLon xử lý số lớn, hỗ trợ phép cộng, trừ, nhân, chia modulo. Lớp GUI cung cấp giao diện thân thiện cho người dùng, giúp tạo khóa, ký và xác minh dễ dàng.

4.2. Cài Đặt Và Hướng Dẫn Sử Dụng

Cài đặt JRE là bước đầu tiên, cho phép chạy chương trình Java trên bất kỳ máy tính nào. Mã nguồn lớp SoLon quản lý các phép toán số lớn cần thiết cho ElGamal. Code lớp GUI cung cấp các nút bấm và trường nhập liệu giúp sinh khóa, ký tài liệu. Hướng dẫn sử dụng bao gồm: 1) Sinh cặp khóa (khóa công khai/bí mật), 2) Nhập thông báo cần ký, 3) Tính chữ ký, 4) Xác minh chữ ký. Ứng dụng này giúp bảo vệ trao đổi dữ liệu trên mạng, đảm bảo xác thực nguồn gốc và tính toàn vẹn.

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

CHƯƠNG 1: TỐNG QUAN VỀ CHỮ KÝ số. Giới thiệu chung về chữ ký số. Như chúng ta đã biết, chừ ký viết tay “thường lệ” gắn với tài liệu được dùng đế chi ra người ký nó. Chữ ký được sứ dụng hàng ngày như viết thư, ký hợp đồng.

Ở đây chúng ta tìm hiểu về một loại chữ ký hoàn toàn khác đó là chữ ký số. Nó là phương pháp ký thông báo được lưu dưới dạng điện từ và thông báo được ký có thế truyền trên mạng máy tính. Chừ ký tay và chữ ký số dù có chung nhiệm vụ là ký nhưng có sự khác biệt cơ bán giữa chúng. - Thứ nhất, về việc ký tài liệu: với chữ ký tay thì chữ ký là bộ phận vật lý của tài liệu được ký.

Tuy nhiên, chừ ký số không gắn với thông báo được ký theo kiếu vật lý mà gắn với thông báo theo kiếu logic, do đó thuật toán được dùng phải “trói” chữ ký với thông báo theo một cách nào đó. - Thứ hai, về việc kiêm tra: chữ ký tay được kiếm tra bàng cách so sánh nó với những cái khác (những chữ ký đã được xác thực). Ví dụ, một người ký một tấm séc mua hàng, người bán hàng phải so sánh nó với chữ ký nằm sau thẻ tín dụng đề kiềm tra. Tuy nhiên, phương pháp này không an toàn lắm vi nó tương đối dễ dàng làm giả bời chữ ký cùa người khác hoặc bị chối bó bời chính người ký.

Khác với chữ ký tay, chữ ký số có thể được kiếm tra bằng cách dùng thuật toán kiếm tra công khai đã biết. Vì vậy bất kỳ người nào đều có thế kiếm tra chữ ký số, và việc sử dụng sơ đồ (lược đồ) ký an toàn sẽ ngăn chặn khả năng làm già và chối bỏ. - Điều khác nhau cơ bân giữa chữ ký tay và chữ ký số là “bàn sao” thông báo số được ký là đồng nhất với bàn gốc. Trong khi đó, bàn sao tài liệu giấy đã ký thường là khác với bàn gốc.

Điều này có nghĩa là phải cẩn thận để ngăn chặn việc một thông báo đã ký số bị sứ dụng lại. Ví dụ, ncu Alice ký thông báo số cho Bob rút 1000$ từ tài khoản ngân hàng của minh, Alice chi muốn Bob làm điều đó I lần. Do đó, thông báo đó phải chứa thông tin để ngăn chặn Bob làm lại việc đó nhiều lần. Sơ đồ chữ ký số gồm hai thành phần: một thuật toán ký và một thuật toán kiểm tra.

Alice có thề ký thông báo X nhờ thuật toán (bí mật) Sig. Chữ ký thu được Sig(x) sau đó 4 có thể được kiểm tra bàng thuật toán kiềm tra công khai Ver. Khi cho cặp (x,y) thuật toán kiếm tra trả lời “đúng” hoặc “sai” phụ thuộc vào việc ký có đích thực không? Dinh nghĩa sơ đồ chữ ký điên tử Là một bộ 5(P, A, K, s, V) thòa mãn các điều kiện dưới đây: 1) p là tập hữu hạn các bức điện (thông điệp, bản rõ) có thể. 2) A là tập hữu hạn các chữ ký có thế.

3) K là tập không gian khóa (tập hữu hạn các khóa có thể). 4) Với mồi khóa k e K tồn tại một thuật toán ký Sigk e s và một thuật toán xác minh Verk e V. Mỗi Sigk: p ->A và Verk: PxA->{TRUE,FALSE} là những hàm sao cho mỗi bức điện X e p và một chữ ký y e A thỏa mãn phương trinh dưới đây: ,,. Với mỗi k e K, các hàm Sigk và Verk là các hàm thời gian đa thức.

Verk là hàm công khai, Sigk là hàm bí mật tránh trường hợp Oscar có thể giả mạo chữ ký của Alice đế ký thông báo. Với mỗi X chi duy nhất Alice tính được chữ ký y sao cho: Ver(x,y) = TRUE Sơ đồ chữ ký phái an toàn. Bởi vì người thám mã Oscar có thế kiêm tra tất cã các khả năng cùa chữ ký y nhờ thuật toán kiếm tra công khai Vcr() cho tới khi tìm được chữ ký đúng. Do đó, nếu đú thời gian cần thiết thì Oscar có thế giả mạo được chữ ký của Alice.

Vi vậy, mục đích của chúng ta là tìm được các sơ đo chữ ký sao cho Oscar không đủ thời gian thực tế đổ thử hết các trường họp. Một số vấn đề toán học.1 Thuật toán Euclid. Thuật toán Euclid là một giải thuật giúp tính ước số chung lớn nhất (UCLN) của hai số một cách hiệu quâ. Nhà toán học Hy Lạp co Euclid đã đưa ra thuật toán này trong cuốn sách toán nổi tiếng Elements vào khoáng năm 300 trước Công Nguyên.

Trước khi tìm hiểu thuật toán ta xét ví dụ: tính UCLN của 33 và 213 Trước hết phân tích 213 theo 33 ta có 213 = 33 * 6 + 15 Nhận xét: • Bất kỳ số nào chia hết bởi 213 và 33 thì cũng sẽ bị chia hết bởi 213-33*6=15. • Tương tự, số chia hết bởi 33 và 15 cũng chia hết bới 33*6+15=213 => UCLN(33,213)=UCLN(33,15). Bài toán trớ thành tim UCLN của 33 và 15. Lặp lại quy trinh như trên cho đến khi không còn số dư: 33 = 15*2 + 3 (15 và 3 được dùng cho vòng lặp kế) 15=3*5 (không còn dư, kết thúc, nhận 3 làm kết quả) Cuối cùng ta có : 3 = UCLN(33,15) = UCLN(33,213).

Bồ đề: Giả sử a = bq +r với a, b, q, r là các số nguyên, ta có: nri l.A _ í b nẻu r - 0 UCLN(a,b) = s [UCLN(b,r) nẽur^o Mã giả: UCLN(a,b: nguyên dương) BEGIN While b>0 begin x:=a mod b a:=b b:=x end return X 6 1.2 Thuật toán Euclid mỏ’ rộng. Thuật toán Euclid mờ rộng được sử dụng đồ giải phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) ax + by = c Trong đó a, b, c là các hàng số nguyên, X, y là các an so nguyên. Điều kiện để phương trình trên có nghiệm (nguyên) là UCLN(a,b) là ước của c. Khắng định này dựa trên mệnh đề sau: Nếu d = UCLN(a, b) thì tồn tại các sô nguyên x,y sao cho ax + by = d Giải thuật Euclid mờ rộng là kết họp cúa quá trình tìm UCLN(a,b) trong thuật toán Euclid với việc tim cặp so X, y thòa mãn phương trình Đi-ô-phăng.

Giả sử cho hai số tự nhiên a, b với a>b>0. Đặt r0= a, F|=b, chia r0 cho t| được số dư 1’2 và thương nguyên qi. Nếu r2 = 0 thì dừng lại, nếu r2ị 0 thì chia r, cho r2 được số dư r3 và thương nguyên q2. Vi dãy r, là giảm thực sự nên sau hữu hạn bước ta có so dư rm= 0.

r0 = q,r1 + r2, 0< r2< n r, = q2r2 + r3, 0< r3< r2 tin-1 tỊmrm + rm+i, 0< rm+]< rm Tin qm+ltin+l trong đó số dư cuối cùng khác 0 là rm+1 = d. Bài toán đặt ra là tìm X, y sao cho ax + by = rra+ I=d. Đe làm điều này, ta tìm X, y theo công thức truy hồi, nghĩa là sẽ tìm Xị, yi sao cho aXị + byi = Fj với i = 0, 1. 1 = b = T| nghĩa là 7 Xo= 1, X| = 0 và yo= 0, yi = 1 (1) Tổng quát: ax, + by, = r, với i = 0, 1.

axi+i + byi-ị = ri+, với i = 0, 1. Khi đó từ n = qi+in+i + ri+2 suy ra ri-qi+lri+] =ri+2 (aXj + by,) - qi+i(axi+i + byi+i) = ri+2 a(xj - Xj+1 qi+i) + b(y, - qi+iyi+i) = ri+2 từ đó, có the chọn xi+2 = Xi - xi+1 qi+1 (2) yi+2 = y. - qi+ơi+1 (3) Khi i = m - 1 ta có được Xm+| và ym+l. Các công thức (1), (2), (3) là công thức truy hồi để tính X, y.

Ớ đây ta nghiên cứu thuật toán Euclid mở rộng đế tìm phần tử nghịch đảo theo modulo. (định lý về sự tồn tại của phần tử nghịch đảo): nếu UCLN (a,m) = 1 thi tồn tại duy nhất một phần tử b sao cho UCLN(b,m) = 1, là phần tữ nghịch đáo cùa a, nghĩa là thỏa mãn: ab = (ab) mod m =1 8 Mã giá: Procedure EuclidExtended (a,m) int y0=0,yl:=l; While a>() do { r:= m mod a if r=0 then Break q:= m div a y:= yO-yl*q m:=a a:=r yO:=yl yl:=y } If a>l Then Return "A không khả nghịch theo modulo m" else Return " Nghịch đào modulo m của a là y" *Nếu y>0 thỉ y là kết quà của a'1 mod m *Nếu y<0 thi m+y là kết quả của a'1 mod m 1.3 Nhóm Cyclic Định nghĩa 1.1: Nhóm G được gọi là nhóm cyclic nếu tồn tại một phần tử a sao cho với mồi b e G có một số nguyên i sao cho b = al. Phần tử a như vậy được gọi là phần tử sinh cùa G. Tính chất: • Neu a là phần tử sinh của Z* thi z„ = {a‘ mod n I 0 < i < </>(n)}.

• a là phần từ sinh cùa tập Z’n khi đó b = a 1 mod n cũng là phần tử sinh cùa z„ khi và chi khi UCLN^i, ự>(n)) = 1.4 Một số định lý quan trọng khác. (định lý Lagrange): giả sử G là một nhóm cấp n và g e G. Khi đó cấp của g là ước cùa n. (định lý Euler) Va 6 Z*N = ZN - {0} và UCLN(a, N) = 1 ta có a^ = l(mod N) Có nghĩa là a't’W chính là giá trị nghịch đáo cùa a trên ZN.

Neu p là so nguyên tố thì Z‘plà nhóm cyclic. Một số thuật toán tính toán số lớn. Trong sơ đồ chữ ký số nói chung, thì vai trò cùa số lớn và cụ thề là các số nguyên tố lớn là đặc biệt quan trọng. Nó là một trong những chìa khóa đế đâm bão độ an toàn cùa sơ đồ chữ ký.

Mặc dù các ngôn ngữ lập trình cung cap cho chúng ta nhưng kiểu số nguyên thủy rất lớn, nhưng thực chất vẫn chưa đáp ứng được nhu càu của sơ đồ chừ ký. Vì vậy trong đồ án này, chúng ta sẽ tự tạo ra một cấu trúc dữ liệu số lớn và làm việc trên nó. Ở đây ta sẽ xây dựng số lớn với cơ số là 256 (8 bit) và độ dài tối đa là 100 chữ số: Máng phần tử I 0-255 I 0-255 I 0-255 I. 99 Cách thể hiện một số lớn Sau đây ta sẽ xây dựng các phép toán cơ bản trên số lớn được định nghĩa này.

Đe cộng hai số lớn ta làm các bước sau đây: B1 Cộng hai phần tử ở vị trí thấp nhất. B2 Giá trị phép cộng lưu vào một biến nhớ, giá trị lưu vào mãng tổng tại vị trí đó gán bàng phép chia lấy dư cùa biến nhớ cho 256. B3 Cộng lần lượt hai phần tử ờ các vị trí tiếp theo và {biến nhớ chia cho 256}. B4 Lặp lại bước 2 và 3 cho đến hết.