Về một hệ chữ ký số

K y u công trình khoa h c 2015 – Ph n I<br /> <br /> VỀ MỘT HỆ CHỮ KÝ SỐ<br /> TS. Nguyễn Công Sứ<br /> Khoa Toán-Tin, Đại học Thăng Long<br /> Email: congsu1945@yahoo.com.vn<br /> Tóm tắt: Một chữ ký bằng tay "thông thường" gắn liền với một văn bản được sử dụng<br /> để xác định người tạo ra và chịu trách nhiệm về văn bản đó. Chữ ký được sử dụng trong các<br /> sự việc hàng ngày như viết thư, rút tiền từ ngân hàng, ký một hợp đồng, vv ... Hệ chữ ký số là<br /> phương thức ký các văn dạng diện tử. Do đó, một văn bản đã được ký có thể truyền qua mạng<br /> thông qua các máy tính và thiết bị hỗ trợ. Một hệ chữ ký số gồm 02 thành phần: một thuật<br /> toán ký và một thuật toán xác minh chữ ký. Một người A có thể ký văn bản x sử dụng (khóa bí<br /> mật của mình) theo hàm<br /> <br /> . Kết quả của chữ ký<br /> <br /> (x) có thể được kiểm tra bởi một thuật<br /> <br /> toán xác minh công khai<br /> . Đối với một cặp (x, y), trong đó x là văn bản và y là chữ ký<br /> của x, thuật toán sẽ kiểm tra và trả về “Đúng” hoặc “Sai” phụ thuộc y là chữ ký hợp lệ của x<br /> hay không. Trong bài viết này, chúng tôi trình bày kết quả tìm hiểu và triển khai một hệ chữ<br /> ký số.<br /> Từ khóa:Chữ ký số, R.S.A, Mật mã, Mã hóa. Khóa bí mật. Khóa công khai. Hệ mật<br /> phi đối xứng.<br /> 1. Khái niệm về chữ ký số<br /> Chữ ký suy cho cùng là một hành động tác động vào văn bản nhằm đảm bảo để cả chủ<br /> nhân của chữ ký lẫn người nhận văn bản được ký tin tưởng rằng:<br /> •<br /> •<br /> <br /> Nội dung của văn bản đã ký đã được người ký đồng ý và không thể từ chối<br /> trách nhiệm về chủ quyền của văn bản.<br /> Chữ ký trong văn bản không thể bị làm giả mạo bởi một người nào khác.<br /> <br /> Tuy nhiên điểm khác biệt giữa chữ ký truyền thống thường được ký trên các văn bản<br /> “viết tay” và chữ ký điện tử thường được ký trên các văn bản điện tử để lưu trữ, hoặc truyền<br /> trên mạng máy tính là:<br /> •<br /> <br /> •<br /> <br /> Chữ ký truyền thống là một phần vật lý tách rời với văn bản (nó chỉ được gắn<br /> vào phần dưới của văn bản), còn chữ ký điện tử lại được ``gắn'' với từng yếu tố<br /> của văn bản.<br /> Chữ ký thông thường được kiểm tra bởi các phương tiện vật lý, hóa học,… nói<br /> chung là các thủ pháp xác thực mà độ tin tưởng của các kết quả kiểm tra lại<br /> chính là vấn đề cần phải kiểm tra, trong khi đó chữ ký số lại có thể và chỉ có<br /> thể kiểm tra bằng chính thuật toán kiểm tra, có thể công khai với mọi người và<br /> độ tin tưởng của thuật toán thì đã được chứng minh.<br /> <br /> Như vậy bất kỳ người nào cũng có khả năng (đương nhiên với sự am hiểu cần thiết)<br /> kiểm tra sự đúng đắn của không chỉ chữ ký mà cả chính văn bản đã được ký (bằng điều đó,<br /> người ký đã hoàn toàn có khả năng ngăn cản việc giả mạo cả văn bản lẫn chữ ký của mình).<br /> Ngoài ra chữ ký điện tử còn tránh được việc sử dụng lại hoặc “cắt, dán” vào văn bản<br /> khác như thường xảy ra với chữ ký thông thường.<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 93<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> Để có thể thấy rõ những vấn đề trên, chúng ta cần tìm hiểu qua về bản chất toán học<br /> của chữ ký điện tử. Trước hết là định nghĩa hình thức về lược đồ chữ ký số:<br /> Định nghĩa 1.1.Lược đồ chữ ký số là bộ 5 thành phần (P,A,K,S,V) trong đó:<br /> 1. P: tập hữu hạn tất cả các bản ghi có thể có.<br /> 2. A: tập hữu hạn các chữ ký có thể có.<br /> 3. K: không gian khóa, đó là tập tất cả các khóa1 có thể có.<br /> <br /> , có một thuật toán<br /> <br /> 4. Với mỗi khóa<br /> <br /> ứng<br /> <br /> và một thuật toán kiểm tra tương<br /> <br /> , trong đó:<br /> :<br /> còn<br /> <br /> :<br /> <br /> là các ánh xạ sao cho phương trình sau đây thỏa mãn với mỗi bản tin<br /> mỗi chữ ký<br /> <br /> Cặp<br /> <br /> và<br /> <br /> :<br /> <br /> được gọi là bản lưu đã được ký.<br /> <br /> Chú ý rằng với mỗi<br /> <br /> , các thuật toán<br /> <br /> ,<br /> <br /> là các ánh xạ với thời gian đa<br /> <br /> thức (độ phức tạp đa thức). Ngoài ra<br /> là ánh xạ công khai, còn<br /> là bí mật.Với mỗi x<br /> cho trước, một người nào khác với chủ nhân A của chữ ký không thể tính được ra y sao cho<br /> . (Nếu một người khác nào đó (C) lại có thể tính ra một cặp (x, y) sao cho<br /> và x không phải văn bản đã được ký trước đó bởi A thì chữ ký y được coi<br /> là giả mạo, tức là chữ ký đó không phải là của A).<br /> 2. Thuật toán tạo chữ ký số - Hệ chữ ký số R.S.A<br /> 2.1. Hệ mật phi đối xứng<br /> Các hệ mật phi đối xứng, còn gọi là các hệ mật hai khóa, hay khóa công khai là công<br /> cụ hữu hiệu để thiết kế một hệ chữ ký số (về vấn đề này đã được bàn kỹ trong lĩnh vực mật<br /> mã cả trên phương diện lý thuyết lẫn thực hành). Đó là một hệ mật (hệ thống mật mã) đặc<br /> trưng bởi hai điều kiện cốt lõi sau:<br /> 1. Khóa mã và khóa dịch mã phải khác nhau.<br /> 2. Giữa hai khóa bị ràng buộc bởi một quan hệ toán học đặc biệt sao cho việc xác<br /> định một khóa từ khóa kia là “rất khó” về phương diện tính toán, và vì vậy một khóa có thể<br /> cho công khai (gọi là khóa công khai - ký hiệu K1), khóa còn lại phải giữ ”tuyệt<br /> đối” bí mật (gọi là khóa bí mật - ký hiệu K2).<br /> <br /> 1<br /> Khái niệm khóa (key) ở đây khác với khái niệm mật khẩu (password) ở chỗ khóa cần phải tham gia vào quá<br /> trình mã hóa, biển đổi thông tin.<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 94<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> 2.2. Hàm một phía và hàm một phía có cửa sập<br /> Vấn đề trọng tâm của hệ mật phi đối xứng lại nằm ở khái niệm hàm một phía và hàm<br /> một phía có cửa sập trong toán học. Đó là:<br /> Định nghĩa 2.1.Hàm2<br /> <br /> được gọi là một phía nếu:<br /> <br /> 1. Tồn tại một thuật toán đa thức để tính<br /> <br /> .<br /> <br /> 2. Từ giá trị y, việc tính được x để<br /> (hay là tính được<br /> chỉ với xác suất rất nhỏ và do vậy coi là không tính được trong thực tế.<br /> <br /> )<br /> <br /> Tuy nhiên sự tồn tại hàm một phía cũng chỉ là điều kiện cần để có được hệ mật phi đối<br /> xứng, bởi lẽ việc khó, hoặc “không tính được”x từ y sẽ dẫn đến việc mà mã không thể giải mã<br /> được (yêu cầu bắt buộc với hệ mật). Tình trạng trên sẽ được giải quyết nếu hàm<br /> hàm một phía có “cửa sập”. Đó là:<br /> Định nghĩa 2.2.Hàm một phía<br /> <br /> là<br /> <br /> được gọi là có “cửa sập” nếu khi đưa một<br /> <br /> thông tin bổ sung nào đó vào f thì việc tính ngược x từ y (<br /> ) trở nên dễ dàng, ngoài<br /> ra việc tìm ra thông tin bổ xung từ y cũng khó tương đương với việc tìm ra x.<br /> Yêu cầu về tính có “cửa sập” của hàm một phía có vẻ như là một yêu cầu bất khả thi.<br /> Tuy nhiên rất may là cho đến nay, Toán học đã chỉ ra rằng thực tế là đang tồn tại không ít<br /> những hàm như vậy. Mà đặc biệt thú vị ở chỗ, những hàm đó lại gắn với các bài toán khá cổ<br /> điển trong toán học (đương nhiên không phải là tất cả).<br /> 2.3. Hàm một phía có “cửa sập” R.S.A<br /> Định nghĩa 2.3. Cho hai số nguyên tố lớn p và q, gọi<br /> <br /> và hàm Euler của<br /> <br /> (số các số nguyên tố với n và nhỏ hơn n). Khi đó: nếu lấy một số<br /> a sao cho tồn tại<br /> <br /> thì với mỗi<br /> <br /> hàm:<br /> (1)<br /> <br /> là hàm một phía3.<br /> Tuy nhiên đây là hàm một phía có cửa sập với “tham số cửa sập” là<br /> Thật vậy: Do biết<br /> <br /> .<br /> <br /> và do đó tính được<br /> <br /> và vì vậy là<br /> <br /> bằng thuật toán đa thức Euler mở rộng. Đến đây, việc tính ngược<br /> (2)<br /> được thay bởi<br /> <br /> 2<br /> <br /> Ở đây ta đồng nhất khái niệm hàm với ánh xạ.<br /> thì thuật toán tốt nhất có thể để tính được<br /> Vào thời điểm hiện tại, nếu<br /> khối lượng thời gian vượt khỏi khả năng của công nghệ tính toán.<br /> <br /> 3<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> cần một<br /> <br /> 95<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> cũng như phép tính thuận (1) là dễ.<br /> Dễ dàng chỉ ra rằng việc tính ra<br /> từ n và a cũng tương đương với việc tính ra p và<br /> q và việc tính logarit trong trường số nguyên.<br /> Như vậy ở đây p, q là tham số cửa sập trong hàm một phía n = p.q. Và do<br /> vậy<br /> <br /> .<br /> 2.4. Hệ chữ ký số R.S.A<br /> <br /> Hệ chữ ký số R.S.A là hệ chữ ký được thiết kế dựa trên hàm một phía có cửa sập<br /> R.S.A hay hệ một phía phi đối xứng R.S.A tương tự như với hệ mật R.S.A. Khi đó:<br /> Định nghĩa 2.4. Hệ chữ ký số R.S.A là hệ chữ ký số mà<br /> 1.<br /> 2.<br /> .<br /> 3. Khóa công khai<br /> <br /> . Khi đó với<br /> <br /> còn khóa bí mật<br /> thì:<br /> <br /> Như vậy theo lược đồ trên thì khi bên A (người ký văn bản) muốn ký văn bản<br /> mình để gửi cho bên B, anh ta phải thực hiện liên tiếp các bước sau:<br /> 1. Chọn<br /> <br /> từ đó tính ra<br /> <br /> sao cho<br /> 2. Công khai hóa<br /> kiểu danh bạ điện thoại).<br /> 3. Thực hiện việc ký<br /> <br /> Khi đó chữ ký của A trên<br /> <br /> rồi chọn tiếp<br /> <br /> .<br /> (thường lưu sẵn trong danh bạ khóa công khai -<br /> <br /> bằng thuật toán ký:<br /> <br /> sẽ là cặp<br /> <br /> được gửi đến cho B.Bất kỳ người nào,<br /> <br /> chứ không phải chỉ riêng B, đều có thể kiểm tra chữ ký của A trên<br /> khai<br /> <br /> của<br /> <br /> bằng cách lấy khóa công<br /> <br /> của A từ danh bạ khóa công khai để thực hiện thuật toán kiểm tra<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 96<br /> <br /> K y u công trình khoa h c 2015 – Ph n I<br /> <br /> Một câu hỏi đặt ra là liệu có chăng khả năng một người nào đó tạo được<br /> <br /> ngẫu nhiên mà là chữ ký ứng với<br /> <br /> một cách<br /> <br /> . Điều đó là có thể (dù với xác suất rất nhỏ). Tuy nhiên có<br /> <br /> thể ngăn cản khả năng này bằng một thủ pháp hữu hiệu là bổ xung vào<br /> một “độ dư ngẫu<br /> nhiên” và sử dụng hàm đặc biệt - hàm Hash4và khi đó lược đồ ký một văn bản sẽ là:<br /> Signing a message digest:<br /> Message<br /> <br /> x<br /> <br /> Message digest<br /> Signature<br /> <br /> z = h(x)<br /> <br /> y=<br /> <br /> Ở đây h(x) là một hàm hash của x.<br /> 3. Thiết kế một hệ chữ ký số thực tế<br /> Chữ ký số nói riêng và mật mã nói chung, suy cho cùng là một khoa học của các<br /> phương pháp toán học và các thủ pháp (protocol). Điều đó có nghĩa là khoa học của các quy<br /> tắc toán học chặt chẽ, phổ dụng (công khai) với các thủ thuật mẹo mực (nhưng lại cũng cần có<br /> chứng minh chặt chẽ).<br /> Do vậy không có, hay nói chính xác là không thể có một tài liệu nào trình bày đủ chi<br /> tiết về cách thức xây dựng một hệ chữ ký thực tế, thích dụng.<br /> Xây dựng một hệ chữ ký số đủ đáp ứng một số yêu cầu cơ bản về mức độ xác thực dữ<br /> liệu trong trường Đại hoc Thăng Long là nhiệm vụ cụ thể, mới và mang tính đặc thù, nhưng<br /> lại cần phù hợp với các quy định cả về phương diện hành chính lẫn luật pháp.<br /> Do vậy việc thiết kế hệ chữ ký số dùng “thử nghiệm”trong trường Đại học Thăng<br /> Long đã được xây dựng thành một chương trình nghiên cứu bao gồm các đề tài sau:<br /> Đề tài thứ nhất:Xây dựng hệ quản lý chứng thư số hay hạ tầng cơ sở khóa công khai,<br /> chữ ký số và các thủ tục xác thực khác.<br /> Đề tài thứ hai:Tạo các số ngẫu nhiên, các cặp số nguyên tố mạnh cho một không gian<br /> khóa đủ dùng khi xây dụng hệ chữ ký số R.S.A.<br /> Đề tài thứ ba:Hàm băm - Hàm băm mật mã (Hash) trong hệ thống chữ ký số có độ<br /> xác thực cao.<br /> Đề tài thứ tư:Các thuật toán và thủ tục mã, ký, kiểm tra chữ ký và kỹ thuật đảm bảo<br /> cho việc ký văn bản bằng hệ chữ ký số R.S.A.<br /> Sau gần một năm học tập, nghiên cứu, thử nghiệm, cuối cùng chúng ta có thể khẳng<br /> định các kết quả sau:<br /> <br /> 4<br /> <br /> Hàm Hash sẽ được trình bày trong báo cáo riêng.<br /> <br /> Trư ng Đ i h c Thăng Long<br /> <br /> 97<br /> <br />