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.