Khóa luận An toàn thông tin trong lĩnh vực tài chính

khai với một định danh người sử dụng thường được thực hiện bởi các giao thức thực hiện hạ tầng khoá công khai (PKI). Các giao thức này cho phép kiểm tra mối quan hệ giữa khóa và người được cho là sở hữu khóa thông qua một bên thứ ba được tin tưởng. Mô hình tổ chức của hệ thống kiểm tra có thể theo phân lớp (các nhà cung cấp chứng thực số-X.509) hoặc theo thống kê (mạng lưới tín nhiệm-PGP, GPG) hoặc theo mô hình tín nhiệm nội bộ (SPKI). Không phụ thuộc vào bản chất của thuật toán hay giao thức, việc đánh giá mối quan hệ giữa khoá và người sở hữu khóa vẫn phải dựa trên những đánh giá chủ quan của bên thứ ba bởi vì khóa là một thực thể toán học còn người sở hữu và mối quan hệ thì không. Hạ tầng khoá công khai chính là các thiết chế để đưa ra những chính sáchcho việc đánh giá này. 2.2.2. Hệ mật RSA & Elgamal 2.2.2.1. Hệ mật RSA a. Mô tả sơ lược Thuật toán RSA có hai khoá: khoá công khai (hay khóa công cộng) và khoá bí mật (hay khóa cá nhân). Mỗi khóa là những số cố định sử dụng trong quá trình mã hóa và giải mã. Khóa công khai được công bố rộng rãi cho mọi người và được dùng để mã hoá. Những thông tin được mã hóa bằng khóa công khai chỉ có thể được giải mã bằng khóa bí mật tương ứng. Nói cách khác, mọi người đều có thể mã hóa nhưng chỉ có người biết khóa cá nhân (bí mật) mới có thể giải mã được. Ta có thể mô phỏng trực quan một hệ mật mã khoá công khai như sau : Bob muốn gửi cho Alice một thông tin mật mà Bob muốn duy nhất Alice có thể đọc được. Để làm được điều này, Alice gửi cho Bob một chiếc hộp có khóa đã mở sẵn và giữ lại chìa khóa. Bob nhận chiếc hộp, cho vào đó một tờ giấy viết thư bình thường và khóa lại (như loại khoá thông thường chỉ cần sập chốt lại, sau khi sập chốt khóa ngay cả Bob cũng không thể mở lại được-không đọc lại hay sửa thông tin trong thư được nữa). Sau đó Bob gửi chiếc hộp lại cho Alice. Alice mở hộp với chìa khóa của mình và đọc thông tin trong thư. Trong ví dụ này, chiếc hộp với khóa mở đóng vai trò khóa công khai, chiếc chìa khóa chính là khóa bí mật. b. Tạo khóa Giả sử Alice và Bob cần trao đổi thông tin bí mật thông qua một kênh không an toàn (ví dụ như Internet). Với thuật toán RSA, Alice đầu tiên cần tạo ra cho mình cặp khóa gồm khóa công khai và khóa bí mật theo các bước sau: Chọn 2 số nguyên tố lớn và với , lựa chọn ngẫu nhiên và độc lập. Tính: . Tính: giá trị hàm số Ơle . Chọn một số tự nhiên e sao cho và là số nguyên tố cùng nhau với . Tính: d sao cho. Khóa công khai bao gồm: n, môđun, và e, số mũ công khai (cũng gọi là số mũ mã hóa). Khóa bí mật bao gồm: n, môđun, xuất hiện cả trong khóa công khai và khóa bí mật, và d, số mũ bí mật (cũng gọi là số mũ giải mã). Một dạng khác của khóa bí mật bao gồm: p and q, hai số nguyên tố chọn ban đầu, d mod (p-1) và d mod (q-1) (thường được gọi là dmp1 và dmq1), (1/q) mod p (thường được gọi là iqmp) Dạng này cho phép thực hiện giải mã và ký nhanh hơn với việc sử dụng định lý số dư Trung Quốc (tiếng Anh: Chinese Remainder Theorem - CRT). Ở dạng này, tất cả thành phần của khóa bí mật phải được giữ bí mật. Alice gửi khóa công khai cho Bob, và giữ bí mật khóa cá nhân của mình. Ở đây, p và q giữ vai trò rất quan trọng. Chúng là các phân tố của n và cho phép tính d khi biết e. Nếu không sử dụng dạng sau của khóa bí mật (dạng CRT) thì p và q sẽ được xóa ngay sau khi thực hiện xong quá trình tạo khóa. Mã hóa Giả sử Bob muốn gửi đoạn thông tin M cho Alice. Đầu tiên Bob chuyển M thành một số m < n theo một hàm có thể đảo ngược (từ m có thể xác định lại M) được thỏa thuận trước. Quá trình này được mô tả ở phần #Chuyển đổi văn bản rõ. Lúc này Bob có m và biết n cũng như e do Alice gửi. Bob sẽ tính c là bản mã hóa của m theo công thức: Hàm trên có thể tính dễ dàng sử dụng phương pháp tính hàm mũ (theo môđun) bằng (thuật toán bình phương và nhân) Cuối cùng Bob gửi c cho Alice. Giải mã Alice nhận c từ Bob và biết khóa bí mật d. Alice có thể tìm được m từ c theo công thức sau: Biết m, Alice tìm lại M theo phương pháp đã thỏa thuận trước. Quá trình giải mã hoạt động vì ta có . Do ed ≡ 1 (mod p-1) và ed ≡ 1 (mod q-1), (theo Định lý Fermat nhỏ) nên: và Do p và q là hai số nguyên tố cùng nhau, áp dụng định lý số dư Trung Quốc, ta có: . hay: . Ví dụ Sau đây là một ví dụ với những số cụ thể. Ở đây chúng ta sử dụng những số nhỏ để tiện tính toán còn trong thực tế phải dùng các số có giá trị đủ lớn. Lấy: p = 61 — số nguyên tố thứ nhất (giữ bí mật hoặc hủy sau khi tạo khóa) q = 53 — số nguyên tố thứ hai (giữ bí mật hoặc hủy sau khi tạo khóa) n = pq = 3233 — môđun (công bố công khai) e = 17 — số mũ công khai d = 2753 — số mũ bí mật Khóa công khai là cặp (e, n). Khóa bí mật là d. Hàm mã hóa là: encrypt(m) = me mod n = m17 mod 3233 với m là văn bản rõ. Hàm giải mã là: decrypt(c) = cd mod n = c2753 mod 3233 với c là văn bản mã. Để mã hóa văn bản có giá trị 123, ta thực hiện phép tính: encrypt(123) = 12317 mod 3233 = 855 Để giải mã văn bản có giá trị 855, ta thực hiện phép tính: decrypt(855) = 8552753 mod 3233 = 123 Cả hai phép tính trên đều có thể được thực hiện hiệu quả nhờ giải thuật bình phương và nhân. c. Chuyển đổi văn bản rõ Trước khi thực hiện mã hóa, ta phải thực hiện việc chuyển đổi văn bản rõ (chuyển đổi từ M sang m) sao cho không có giá trị nào của M tạo ra văn bản mã không an toàn. Nếu không có quá trình này, RSA sẽ gặp phải một số vấn đề sau: Nếu m = 0 hoặc m = 1 sẽ tạo ra các bản mã có giá trị là 0 và 1 tương ứng Khi mã hóa với số mũ nhỏ (chẳng hạn e = 3) và m cũng có giá trị nhỏ, giá trị me cũng nhận giá trị nhỏ (so với n). Như vậy phép môđun không có tác dụng và có thể dễ dàng tìm được m bằng cách khai căn bậc e của c (bỏ qua môđun). RSA là phương pháp mã hóa xác định (không có thành phần ngẫu nhiên) nên kẻ tấn công có thể thực hiện tấn công lựa chọn bản rõ bằng cách tạo ra một bảng tra giữa bản rõ và bản mã. Khi gặp một bản mã, kẻ tấn công sử dụng bảng tra để tìm ra bản rõ tương ứng. Trên thực tế, ta thường gặp 2 vấn đề đầu khi gửi các bản tin ASCII ngắn với m là nhóm vài ký tự ASCII. Một đoạn tin chỉ có 1 ký tự NUL sẽ được gán giá trị m = 0 và cho ra bản mã là 0 bất kể giá trị của e và N. Tương tự, một ký tự ASCII khác, SOH, có giá trị 1 sẽ luôn cho ra bản mã là 1. Với các hệ thống dùng giá trị e nhỏ thì tất cả ký tự ASCII đều cho kết quả mã hóa không an toàn vì giá trị lớn nhất của m chỉ là 255 và 2553 nhỏ hơn giá trị n chấp nhận được. Những bản mã này sẽ dễ dàng bị phá mã. Để tránh gặp phải những vấn đề trên, RSA trên thực tế thường bao gồm một hình thức chuyển đổi ngẫu nhiên hóa m trước khi mã hóa. Quá trình chuyển đổi này phải đảm bảo rằng m không rơi vào các giá trị không an toàn. Sau khi chuyển đổi, mỗi bản rõ khi mã hóa sẽ cho ra một trong số khả năng trong tập hợp bản mã. Điều này làm giảm tính khả thi của phương pháp tấn công lựa chọn bản rõ (một bản rõ sẽ có thể tương ứng với nhiều bản mã tuỳ thuộc vào cách chuyển đổi). d. Tạo chữ ký số cho văn bản Thuật toán RSA còn được dùng để tạo chữ ký số cho văn bản. Giả sử Alice muốn gửi cho Bob một văn bản có chữ ký của mình. Để làm việc này, Alice tạo ra một giá trị băm (hash value) của văn bản cần ký và tính giá trị mũ d mod n của nó (giống như khi Alice thực hiện giải mã). Giá trị cuối cùng chính là chữ ký điện tử của văn bản đang xét. Khi Bob nhận được văn bản cùng với chữ ký điện tử, anh ta tính giá trị mũ e mod n của chữ ký đồng thời với việc tính giá trị băm của văn bản. Nếu 2 giá trị này như nhau thì Bob biết rằng người tạo ra chữ ký biết khóa bí mật của Alice và văn bản đã không bị thay đổi sau khi ký. Cần chú ý rằng các phương pháp chuyển đổi bản rõ giữ vai trò quan trọng đối với quá trình mã hóa cũng như chữ ký điện tử và không được dùng khóa chung cho đồng thời cho cả hai mục đích trên. e. An ninh Độ an toàn của hệ thống RSA dựa trên 2 vấn đề của toán học: bài toán phân tích ra thừa số nguyên tố các số nguyên lớn và bài toán RSA. Nếu 2 bài toán trên là khó (không tìm được thuật toán hiệu quả để giải chúng) thì không thể thực hiện được việc phá mã toàn bộ đối với RSA. Phá mã một phần phải được ngăn chặn bằng các phương pháp chuyển đổi bản rõ an toàn. Bài toán RSA là bài toán tính căn bậc e môđun n (với n là hợp số): tìm số m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai và c là bản mã. Hiện nay phương pháp triển vọng nhất giải bài toán này là phân tích n ra thừa số nguyên tố. Khi thực hiện được điều này, kẻ tấn công sẽ tìm ra số mũ bí mật d từ khóa công khai và có thể giải mã theo đúng quy trình của thuật toán. Nếu kẻ tấn công tìm được 2 số nguyên tố p và q sao cho: n = pq thì có thể dễ dàng tìm được giá trị (p-1)(q-1) và qua đó xác định d từ e. Chưa có một phương pháp nào được tìm ra trên máy tính để giải bài toán này trong thời gian đa thức (polynomial-time). Tuy nhiên người ta cũng chưa chứng minh được điều ngược lại (sự không tồn tại của thuật toán). Xem thêm phân tích ra thừa số nguyên tố về vấn đề này. Tại thời điểm năm 2005, số lớn nhất có thể được phân tích ra thừa số nguyên tố có độ dài 663 bít với phương pháp phân tán trong khi khóa của RSA có độ dài từ 1024 tới 2048 bít. Một số chuyên gia cho rằng khóa 1024 bít có thể sớm bị phá vỡ (cũng có nhiều người phản đối việc này). Với khóa 4096 bít thì hầu như không có khả năng bị phá vỡ trong tương lai gần. Do đó, người ta thường cho rằng RSA đảm bảo an toàn với điều kiện n được chọn đủ lớn. Nếu n có độ dài 256 bít hoặc ngắn hơn, nó có thể bị phân tích trong vài giờ với máy tính cá nhân dùng các phần mềm có sẵn. Nếu n có độ dài 512 bít, nó có thể bị phân tích bởi vài trăm máy tính tại thời điểm năm 1999. Vì vậy hiện nay người ta khuyến cáo sử dụng khóa có độ dài tối thiểu 2048 bít. f. Các vấn đề đặt ra trong thực tế Quá trình tạo khóa Việc tìm ra 2 số nguyên tố đủ lớn p và q thường được thực hiện bằng cách thử xác suất các số ngẫu nhiên có độ lớn phù hợp (dùng phép kiểm tra nguyên tố cho phép loại bỏ hầu hết các hợp số). p và q còn cần được chọn không quá gần nhau để phòng trường hợp phân tích n bằng phương pháp phân tích Fermat. Ngoài ra, nếu p-1 hoặc q-1 có thừa số nguyên tố nhỏ thì n cũng có thể dễ dàng bị phân tích và vì thế p và q cũng cần được thử để tránh khả năng này. Bên cạnh đó, cần tránh sử dụng các phương pháp tìm số ngẫu nhiên mà kẻ tấn công có thể lợi dụng để biết thêm thông tin về việc lựa chọn (cần dùng các bộ tạo số ngẫu nhiên tốt). Yêu cầu ở đây là các số được lựa chọn cần đồng thời ngẫu nhiên và không dự đoán được. Đây là các yêu cầu khác nhau: một số có thể được lựa chọn ngẫu nhiên (không có kiểu mẫu trong kết quả) nhưng nếu có thể dự đoán được dù chỉ một phần thì an ninh của thuật toán cũng không được đảm bảo. Một ví dụ là bảng các số ngẫu nhiên do tập đoàn Rand xuất bản vào những năm 1950 có thể rất thực sự ngẫu nhiên nhưng kẻ tấn công cũng có bảng này. Nếu kẻ tấn công đoán được một nửa chữ số của p hay q thì chúng có thể dễ dàng tìm ra nửa còn lại (theo nghiên cứu của Donald Coppersmith vào năm 1997) Một điểm nữa cần nhấn mạnh là khóa bí mật d phải đủ lớn. Năm 1990, Wiener chỉ ra rằng nếu giá trị của p nằm trong khoảng q và 2q (khá phổ biến) và d < n1/4/3 thì có thể tìm ra được d từ n và e. Mặc dù e đã từng có giá trị là 3 nhưng hiện nay các số mũ nhỏ không còn được sử dụng do có thể tạo nên những lỗ hổng (đã đề cập ở phần chuyển đổi văn bản rõ). Giá trị thường dùng hiện nay là 65537 vì được xem là đủ lớn và cũng không quá lớn ảnh hưởng tới việc thực hiện hàm mũ. Tốc độ RSA có tốc độ thực hiện chậm hơn đáng kể so với DES và các thuật toán mã hóa đối xứng khác. Trên thực tế, Bob sử dụng một thuật toán mã hóa đối xứng nào đó để mã hóa văn bản cần gửi và chỉ sử dụng RSA để mã hóa khóa để giải mã (thông thường khóa ngắn hơn nhiều so với văn bản). Phương thức này cũng tạo ra những vấn đề an ninh mới. Một ví dụ là cần phải tạo ra khóa đối xứng thật sự ngẫu nhiên. Nếu không, kẻ tấn công (thường ký hiệu là Eve) sẽ bỏ qua RSA và tập trung vào việc đoán khóa đối xứng. Phân phối khóa Cũng giống như các thuật toán mã hóa khác, cách thức phân phối khóa công khai là một trong những yếu tố quyết định đối với độ an toàn của RSA. Quá trình phân phối khóa cần chống lại được tấn công đứng giữa (man-in-the-middle attack). Giả sử Eve có thể gửi cho Bob một khóa bất kỳ và khiến Bob tin rằng đó là khóa (công khai) của Alice. Đồng thời Eve có khả năng đọc được thông tin trao đổi giữa Bob và Alice. Khi đó, Eve sẽ gửi cho Bob khóa công khai của chính mình (mà Bob nghĩ rằng đó là khóa của Alice). Sau đó, Eve đọc tất cả văn bản mã hóa do Bob gửi, giải mã với khóa bí mật của mình, giữ 1 bản copy đồng thời mã hóa bằng khóa công khai của Alice và gửi cho Alice. Về nguyên tắc, cả Bob và Alice đều không phát hiện ra sự can thiệp của người thứ ba. Các phương pháp chống lại dạng tấn công này thường dựa trên các chứng thực khóa công khai (digital certificate) hoặc các thành phần của hạ tầng khóa công khai (public key infrastructure - PKI). Tấn công dựa trên thời gian Vào năm 1995, Paul Kocher mô tả một dạng tấn công mới lên RSA: nếu kẻ tấn công nắm đủ thông tin về phần cứng thực hiện mã hóa và xác định được thời gian giải mã đối với một số bản mã lựa chọn thì có thể nhanh chóng tìm ra khóa d. Dạng tấn công này có thể áp dụng đối với hệ thống chữ ký điện tử sử dụng RSA. Năm 2003, Dan Boneh và David Brumley chứng minh một dạng tấn công thực tế hơn: phân tích thừa số RSA dùng mạng máy tính (Máy chủ web dùng SSL). Tấn công đã khai thác thông tin rò rỉ của việc tối ưu hóa định lý số dư Trung quốc mà nhiều ứng dụng đã thực hiện. Để chống lại tấn công dựa trên thời gian là đảm bảo quá trình giải mã luôn diễn ra trong thời gian không đổi bất kể văn bản mã. Tuy nhiên, cách này có thể làm giảm hiệu suất tính toán. Thay vào đó, hầu hết các ứng dụng RSA sử dụng một kỹ thuật gọi là che mắt. Kỹ thuật này dựa trên tính nhân của RSA: thay vì tính cd mod n, Alice đầu tiên chọn một số ngẫu nhiên r và tính (rec)d mod n. Kết quả của phép tính này là rm mod n và tác động của r sẽ được loại bỏ bằng cách nhân kết quả với nghịch đảo của r. Đỗi với mỗi văn bản mã, người ta chọn một giá trị của r. Vì vậy, thời gian giải mã sẽ không còn phụ thuộc vào giá trị của văn bản mã. Tấn công lựa chọn thích nghi bản mã Năm 1981, Daniel Bleichenbacher mô tả dạng tấn công lựa chọn thích nghi bản mã (adaptive chosen ciphertext attack) đầu tiên có thể thực hiện trên thực tế đối với một văn bản mã hóa bằng RSA. Văn bản này được mã hóa dựa trên tiêu chuẩn PKCS #1 v1, một tiêu chuẩn chuyển đổi bản rõ có khả năng kiểm tra tính hợp lệ của văn bản sau khi giải mã. Do những khiếm khuyết của PKCS #1, Bleichenbacher có thể thực hiện một tấn công lên bản RSA dùng cho giao thức SSL (tìm được khóa phiên). Do phát hiện này, các mô hình chuyển đổi an toàn hơn như chuyển đổi mã hóa bất đối xứng tối ưu (Optimal Asymmetric Encryption Padding) được khuyến cáo sử dụng. Đồng thời phòng nghiên cứu của RSA cũng đưa ra phiên bản mới của PKCS #1 có khả năng chống lại dạng tấn công nói trên. 2.2.2.2. Hệ mật Elgamal a. Hệ mật El - Gamal Hệ mật El - Gamal, ra đời vào năm 1985 và hiệnn nay đã được sử dụng khá rộng rãi . Sự an toàn của hệ mật El - Gamal được dựa trên độ khó của việc tính loga rời rạc. Việc lập và giải mã của hệ được tiến hành như sau . B (Bob) chọn một số nguyên tố p và một căn nguyên thuỷ g mod p, tức một phần tử g sao cho các luỹ thừa g0, g1, ..., gp-2 đều là những số phân biệt modulo p và bao gồm tất cả những lớp đồng dư khác không modulo p. B cũng chọn một số nguyên a Î { 1, ... , p-2 } và tính h = ga (mod p). Khoá công khai của B là (p, g, h) còn số a đựoc giữ bí mật . A (Alice) cần gửi một bản rõ x cho B với x được mã hoá như một số nguyên dương £ p-1. A chọn ngẫu nhiên một số nguyên dương k £ p-1, tính y1 = gk(mod p) và y2 = xhk (mod p) và có được bản mã là cặp (y1, y2) . Chú ý là · Bản mã dài gấp hai lần bản rõ; · Với mỗi bản rõ, có thể có p-1 bản mã khác nhau, mỗi bản mã ứng với một phép chọn ngẫu nhiên số k nói ở trên. Khi nhận được bản mã (gk, xhk) mod p, B tiến hành giải mã như sau. Vì đã biết a là số thoả mãn tính chất h = ga nên B có thể tính hk º (ga)k º (gk)a mod p mà không cần biết số bí mật k của A . Bây giờ A có thể tính x bằng việc “chia” y2 = xhk cho hk . Nói một cách chính xác hơn, A dùng thuật toán Euclid suy rộng để tìm nghịch đảo của hk mod p, rồi nhân y2 với nghịch đảo đó để có được bản rõ x . Kẻ trộm tin là E (Eve) khi chặn được bản mã, phải đối mặt với bài toán sau : · Hoặc là phải tìm số a sao cho h º ga (mod p) để sau đó có thể dùng phương pháp giải mã như B đã làm; · Hoặc là phải tìm số k sao cho y1 = gk (mod p) để sau đó có thể tính trực tiếp hk và từ đó tìm được x . Cả hai cách tiếp cận nói trên đều đòi hỏi E phải giải bài toán loga rời rạc, như đã biết là bài toán khó, và cho tới nay chưa có cách nào tốt hơn để phá vỡ hệ mật El - Gamal. Cũng cần lưu ý là, nếu E có đủ các tài nguyên cần cho việc tính toán (chẳng hạn thời gian và thiết bị) để giải một bài toán loga rời rạc thì E sẽ dùng chúng để giải bài toán thứ nhất (tức tính số a) vì nếu giải được bài toán đó thì E sẽ biết được khoá bí mật của B và có thể đọc được tất cả các thông báo gửi cho B. Còn như nếu giải bài toán thứ hai thì chỉ tìm được số ngẫu nhiên k của A, là số thay đổi theo mỗi thông báo, và như vậy vẫn cùng việc này sẽ phải làm nhiều làn. Sau đây là một thí dụ minh hoạ. Giả sử B chọn số ngẫu nhiên p = 83, căn nguyên thuỷ g = 2 và số a = 30. Như vậy h = 230 mod 83 = 40 . Khoá công khai của B là (83, 2, 40). Bây giờ , giả sử bản rõ của A là 54 và số ngẫu nhiên được A chọn là k = 13 . Khi đó bản mã của A sẽ là (gk, xhk) mod p = (58, 71). Nhận được bản mã trên, B sẽ tính 5830 mod 83 = 9. Bằng thuật toán Euclid suy rộng, nghịch đảo của 9 tính được là 37, và như vậy bản rõ là 37.71 mod 83 = 54. b. Chữ ký số El - Gamal . Vì bản mã trong hệ mật El - Gamal dài gấp đôi bản rõ và phụ thuộc vào việc chọn số ngẫu nhiên k, nên lựoc đồ El - Gamal cho chữ ký số có phức tạp hơn , chẳng hạn so với việc dùng hệ RSA. Giả sử khoá công khai El - Gamal của A là (p, g, h), với p là một số nguyên tố, và g là một căn nguyên thuỷ mod p. Khi đó h º ga (mod p), trong đó chỉ có A là người biết được số a . Để ký một thông báo x Î {1, 2, ... , p-1 }, A chọn một số ngẫu nhiên k sao cho gcd (k, p-1) = 1. Dùng thuật toán Euclid suy rộng, A tính được nghịch đảo l của k mod (p-1) và sau đó, tính tiếp z1 = gk mod p, z2 = ( x - az1) l mod (p-1) . Thông báo được ký là (x, z1, z2) . Lưu ý là , cũng giống như trong trường hợp mã hoá, thông báo được ký này dài gấp ba lần thông báo chưa được ký và còn phụ thuộc vào số ngẫu nhiên k được chọn. Bây giờ, A mã hoá thông báo được ký này bằng khoá công khai của B và gửi nó cho B. Nhận đựơc, B giải mã thông báo và tìm được ba thành phần. Thành phần thứ nhất là bản rõ x. Các thành phần thứ hai và thứ ba bao gồm chữ ký. B chấp nhận chữ ký là hợp lệ nếu  Ta cần chứng minh rằng: 1. Nếu A làm đúng theo giao thức, điều kiện trên sẽ được thoả mãn ; 2. E (người trộm tin) không thể giả mạo chữ ký (có nghĩa không thể tạo ra (x, z1, z2) thoả mãn điều kiện nêu trên mà không phải giải một bài toán loga rời rạc. Phần thứ nhất chỉ là việc kiểm tra Lưu ý là gp-1 º 1 (mod p) , nên các luỹ thừa của p có thể được đọc theo mod p-1 . Do có kl º 1 (mod p - 1) , nên Khi đó , với những tính toán đơn giản, có Phần thứ hai phức tạp hơn và ta không trình bầy ở đây. Rõ ràng là E không thể thực hiện những tính toán như A đã làm khi không biết được số a. Và như vậy, chắc chắn là E không có cách nào khác để có thể giả mạo chữ ký được . Thí dụ sau đây cho một minh hoạ về cách sử dụng chữ ký số El - Gamal. Cho khoá công khai của A là (107, 2, 15), với số bí mật a là 11. Như vậy , khi lấy 2 là một căn nguyên thuỷ mod 107, ta có ga º 211 = 15 (mod 107). Giả sử A cần gửi thông báo x = 10 cho B và ký thông báo đó . A chọn k = 17, là số nguyên tố cùng p - 1 = 106, và có nghịch đảo bằng 25. Chữ ký số là (z1, z2), trong đó z1 = 217 mod 107 = 104 , z2 = ( 10 - 11.104) .25 mod 106 = 58 . Sau đó, A mã hoá bản rõ ( 10, 104, 58 ) với khoá công khai của B và gửi nó cho B. Nhận được, B giải mã thông báo và thu được (10, 104, 58). B kiểm tra xem phải chăng 15104. 10458 º 210 (mod 107), và thấy là đúng.Khi đó B biết chắc chắn là thông báo được gửi đến từ A. c. Vấn đề tìm căn nguyên thuỷ. Hệ mật El - Gamal đòi hỏi mỗi người dùng phải chọn một số nguyên tố p và một căn nguyên thuỷ g mod p. Vậy phải tìm một căn nguyên thuỷ như thế nào? Có hai cách tiếp cận đã được dùng. Cách tiếp cận thứ nhất xuất phát từ nhận xét là đối với thao tác của phương pháp, việc g phải là một căn nguyên thuỷ không phải là cốt yếu. Điều quan trọng là g phải có nhiều luỹ thừa mod p khác nhau. Như vậy tất cả những gì mà B phải làm là tìm một số g và kiểm tra rằng không có gi º 1 (mod p) với mọi i không quá lớn ! Cách tiếp cận thứ hai dựa trên nhận xét là có những số nguyên tố đặc biệt mà với chúng có thể dễ dàng tìm được một căn nguyên thuỷ. Có một cách làm như sau . Một cặp số nguyên tố (p, q) được gọi là cặp Sophie Germain nếu p = 2q + 1. Những cặp số nguyên tố như vậy có rất nhiều và ý tưởng này do Sophie Germain đưa ra vào năm 1825. Để tìm một cặp số Sophie Germain, có thể tìm trước một số nguyên tố q và sau đó kiểm tra xem p = 2q + 1 có là nguyên tố hay không. Ta có mệnh đề sau: Mệnh đề 1. Cho (q, p) là một cặp Sophie Germain. Giả sử rằng 1 < g < p - 2 . Khi đó g là một căn nguyên thuỷ mod p nếu và chỉ nếu gq º -1 (mod p) Xem như bài tập trong những ngày Xuân Bính Tuất, độc giả hãy thử chứng minh mệnh đề 1. Trở lại thí dụ đã xét ở trên, ta thấy (41, 83) là một cặp Sophie Germain. Áp dụng bổ đề 1, để kiểm tra xem 2 có phải là một căn nguyên thuỷ mod 83 không, ta chỉ cần xem 241 º -1 (mod 83) hay không ? Điều này là đúng và có thể được tính trực tiếp hoặc sử dụng một công cụ đã có của lý thuyết số 2.2.3. Chữ ký số Khi nhận được một văn bản bằng giấy, các khía cạnh sau đây thường được xem xét từ phía người nhận: Ai là người viết ra, có trách nhiệm với văn bản này? Từ khi được gửi đi từ người viết đến khi nhận được từ người đọc, nội dung văn bản có bị thay đổi gì không? Người viết văn bản không chối bỏ những nội dung mà mình đã viết ra và gửi đi Từ khi được gửi đi từ người viết đến khi nhận được từ người đọc, nội dung văn bản không bị đọc bởi một người thứ ba khác? Nếu được diễn giải dưới góc độ chuyên môn của an toàn thông tin (Information Security), văn bản này được xem xét dưới các khía cạnh: Tính xác thực của người gửi – Authentication Tính toàn vẹn của văn bản – Integrity Tính chống từ chối, chống chối bỏ - Non-repudiation Tính bí mật, tính riêng tư – Privacy Quay lai một văn bản bằng giấy, các vấn đề trên được giải quyết như thế nào: Ai là người viết ra, có trách nhiệm với văn bản này: kiểm tra họ, tên người ký văn bản Từ khi được gửi đi từ người viết đến khi nhận được từ người đọc, nội dung văn bản có bị thay đổi gì không: xem xét các chữ kỹ nháy trên từng trang, tính liên tục của đánh số trang,... Người viết văn bản không chối bỏ những nội dung mà mình đã viết ra và gửi đi: kiểm tra chữ ký cuối cùng của văn bản là chữ ký hợp lệ của người gửi, so sánh chữ ký này với chữ ký mẫu mà mình đã có Từ khi được gửi đi từ người viết đến khi nhận được từ người đọc, nội dung văn bản không bị đọc bởi một người thứ ba khác: kiểm tra phong bì đựng văn bản có còn nguyên trạng không? Khi trao đổi một "văn bản" trong môi trường điện tử (một email, một đoạn dữ liệu trong giao dịch, một file dữ liệu,....) cả 4 khía cạnh nêu trên cũng cần được xem xét trong điều kiện không có "chữ ký", "phong bì", ... Tuy nhiên các vấn đề nêu trên đã được giải quyết về mặt công nghệ khi các tiến trình và giải thuật sử dụng khoá đối xứng (asymmetric key) được phát triển và hoàn thiện. Tiến trình xử lý sẽ như sau: Đoạn dữ liệu cần được bảo mật được đưa qua hàm băm (hashing), kết quả của hàm băm là một đoạn bit đảm bảo 2 tính chất: Tính duy nhất: mỗi một đoạn dữ liệu khác nhau thì sẽ có một đoạn bit khác nhau, không trùng lặp, có độ dài không đổi Tính một chiều: từ đoạn bit đặc trưng này, không suy ngược lại được nối dung đoạn văn bản Đoạn bit đặc trưng này được mã hoá bằng khoá bí mật của người gửi và được đính kèm vào "văn bản", rồi gửi đến người nhận – đoạn bit được mã hoá này chính là chữ ký số (digital signature) Hình 1: Minh họa tiến trình chữ ký sốTừ phía người nhận, khi nhận được "văn bản" kèm chữ ký số, tiến trình kiểm tra sẽ như sau: Lấy đoạn dữ liệu gốc, đưa qua hàm băm đã nói ở trên, thu được một đoạn bit là kết quả băm Lấy đoạn bit được mã hoá (chữ ký số), giải mã bằng khoá công khai của người gửi, thu được đoạn bit đặc trưng So sánh đoạn bit vừa thu được với đoạn bit thu được trong bước 1, nếu 2 đoạn trùng nhau và tin rằng khoá công khai chắc chắn là do người gửi phát hành thì kết luận: Dữ liệu nhận được có tính toàn vẹn (vì kết quả băm là duy nhât, một chiều) Dữ liệu nhận được là do chính người gửi gửi đi vì chỉ duy nhất anh ta mới có khoá bí mật phù hợp với khoá công khai đã được sử dụng để giải mã. Như vậy tính chống từ chối và tính