Giáo trình An toàn và bảo mật thông tin (Phần 2)

Nội dung text: Giáo trình An toàn và bảo mật thông tin (Phần 2)

1. Chƣơng IV: Các hệ mã mật khóa công khai CHƢƠNG IV: CÁC HỆ MÃ MẬT KHÓA CÔNG KHAI Trong cá c hê ̣ mã mâṭ khó a bí mâṭ nế u chú ng ta biế t khó a và hà m mã hó a chú ng ta có thể tìm đƣợc khóa và hàm giải mã một cách nhanh chóng (thờ i gian đa thƣ́ c). Môṭ hê ̣ mã mâṭ khó a bí mâṭ là môṭ hê ̣ mã mâṭ mà tấ t cả moị ngƣờ i đề u biế t hà m mã hóa và khóa mã hóa nhƣng không tồn tại một t huâṭ toá n thờ i gian đa thƣ́ c để có thể tính đƣợc khó a giả i mã tƣ̀ cá c thông tin đó. 1. Khái niệm hệ mã mật khóa công khai Các hệ mã đƣợc trình bà y trong cá c chƣơng trƣớ c đƣợc goị là cá c hê ̣ mã khó a bí mâṭ , khóa đối xứng, hay cá c hê ̣ mã truyề n thố ng (conventional). Các hệ mã này có các điểm yếu sau đây: Nế u số lƣợng ngƣờ i sƣ̉ dụng lớn thì số khóa sẽ tăng rấ t nhanh, chẳ ng haṇ vớ i n ngƣờ i sƣ̉ duṇ g thì số khó a sẽ là n *(n-1)/2 do đó rấ t khó quản lý, phƣ́ c tap̣ và không an toà n. Dƣ̣a trên cá c hê ̣ mã nà y không thể xây dƣ̣ng cá c khá i niêṃ và dic̣ h vu ̣ nhƣ chƣ̃ ký điện tử, dịch vụ xác thực hóa ngƣời dùng cho các ứng dụng thƣơng mại điện tƣ̉ . Vào năm 1975 Diffie và Hellman trong môṭ công trình củ a mình (môṭ bà i bá o) đã đề xuấ t ra cá c ý tƣở ng cho phé p xây dƣ̣ng lên cá c hê ̣ mã hoaṭ đôṇ g theo cá c nguyên tắ c mớ i gắ n liề n vớ i cá c bên truyề n tin chƣ́ không gắ n vớ i cá c căp̣ truyề n tin. Nguyên tắ c hoaṭ đôṇ g củ a cá c hê ̣ mã là mỗi bên tham gia truyề n tin sẽ có 2 khóa, môṭ khó a goị là khó a bí mâṭ và môṭ khó a đƣợc goị là khó a công khai. Khóa bí mật là khóa dùng để giải mã và đƣợc giữ bí mật (KS), khóa công khai là khóa dùng để sinh mã đƣợc công khai hó a để bấ t cƣ́ ai cũng có thể sƣ̉ duṇ g khó a nà y gƣ̉ i tin cho ngƣờ i chủ củ a hê ̣ mã (KP). Ngày nay chúng ta có thể thấy rất rõ nguyên tắc này trong việc gửi email , mọi ngƣờ i đề u có thể gƣ̉ i email tớ i môṭ điạ chi ̉ email nà o đó , nhƣng chi ̉ có ngƣờ i chủ sở hƣ̃ u của địa chỉ email đó mới có thể đọc đƣợc nội dung của bức thƣ , còn những ngƣời khác thì không. Vớ i cá c hê ̣ mã khó a công khai viêc̣ phân phố i khó a sẽ trở nên dễ dà ng hơn qua cá c kênh cung cấ p khó a công côṇ g , số lƣợng khó a hê ̣ thố ng quả n lý cũng sẽ ít hơn (là n khóa cho n ngƣời dùng). Các dịch vụ mới nhƣ chữ ký điện tử , thỏa thuận khóa cũng đƣợc xây dƣ̣ng dƣ̣a trên cá c hê ̣ mã nà y. Các yêu cầu của loại hệ mã này: - Viêc̣ sinh KP, KS phải dễ dàng - Viêc̣ tính E(KP, M) là dễ dàng - Nế u có C = E(KP, M) và KS thì việc tìm bản rõ cũng là dễ - Nế u biế t KP thì việc dò tìm KS là khó - Viêc̣ khôi phuc̣ bả n rõ tƣ̀ bả n mã là rấ t khó Khi A muố n truyề n tin cho B , A sẽ sƣ̉ duṇ g khó a K P của B để mã hóa tin tức và truyề n bả n mã tớ i cho B, B sẽ sƣ̉ duṇ g khó a bí mâṭ củ a mình để giả i mã và đoc̣ tin: 77
2. Chƣơng IV: Các hệ mã mật khóa công khai Khóa công Khóa bí mật khai (KP) (KS) Plaintext Plaintext A Mã hóa Giải mã B Ciphertext Hình 4.1: Mô hình sƣ̉ duṇ g 1 của các hệ mã khóa công khai PKC Ciphertext = E(KP,Plaintext) ,Plantext = D(KS, E(KP,Plaintext)) (1) Khóa bí mật Khóa công (KS) khai (KP) Plaintext Plaintext A Mã hóa Giải mã B Signed Message Hình 4.2: Mô hình sƣ̉ duṇ g 2 của các hệ mã khóa công khai PKC Ciphertext = D(KS, Plaintext), Plaintext = E(KP, D(KS, Plaintext)) (2) Mô hình (2) đƣợc sƣ̉ duṇ g c ho cá c hê ̣ chƣ̃ ký điêṇ tƣ̉ cò n mô hình (1) đƣợc sƣ̉ dụng cho các hệ mã mật . Các hệ mã này đƣợc gọi là các hệ mã khóa công khai PKC (Public Key Cryptosystems) hay cá c hê ̣ mã bấ t đố i xƣ́ ng (Asymmetric Encryption Scheme). 2. Nguyên tắ c cấ u taọ củ a cá c hê ̣ mã mâṭ khó a công khai Các hệ mã khóa công khai đƣợc xây dựng dựa trên các hàm đƣợc gọi là các hàm 1 phía hay hàm 1 chiề u (one–way functions). Hàm một chiều f : X Y là m môṭ hà m mà nế u biế t x X ta có thể dễ dà ng tính đƣợc y = f(x). Nhƣng vớ i y bấ t kỳ Y viêc̣ tìm x X sao cho y = f(x) là khó. Có nghĩa là -1 viêc̣ tìm hà m ngƣợc f là rất khó. Ví dụ nếu chúng ta có các số nguyên tố P 1, P2, , Pn thì việc tính N = P1 * P2 * * Pn là dễ nhƣng nếu có N thì việc phân tích ngƣợc lại là một bài toán khó với N lớn. Để thuâṇ tiêṇ cá c hà m môṭ phía đƣợc sƣ̉ duṇ g trong c ác hệ mã PKC thƣờng đƣợc trang bi ̣cá c cƣ̉ a bẫy (trapdoor) giúp cho việc tìm x thỏa mã y = f(x) là dễ dàng nếu chúng ta biế t đƣợc cƣ̉ a bẫy nà y. Hàm của bẫy (trapdoor function): là một hàm một chiều trong đó việc tính f -1 là rấ t nhanh khi chú ng ta biế t đƣợc cƣ̉ a bẫy củ a hà m . Ví dụ việc tìm nghiệm của bài toán xếp balô 0/1 trong hê ̣ mã xế p balô Knapsack mà chú ng ta sẽ hoc̣ trong phầ n tiế p theo là môṭ hàm một phía (viêc̣ mã hó a rấ t nhanh và dễ d àng nhƣng tìm vectơ nghiệm tƣơng ứng là khó) nhƣng nế u ta biế t cƣ̉ a bẫy (Vectơ xế p balô siêu tăng A‟ ) thì việc giải bài toán lại rất dễ dà ng. 3. Môṭ số hê ̣ mã khó a công khai 3.1. Hê ̣ mã knapsack Bài toán xếp ba lô tổng quát: 78
3. Chƣơng IV: Các hệ mã mật khóa công khai Cho M, N và A1, A2, , AN là các số nguyên dƣơng tìm các số xi không âm sao cho: N M =  xAii* i 1 Vecto A = (A1, A2, , AN) đƣợc goị là vecto xế p balô cò n vectơ X = (x1, x2, , xN) là vectơ nghiêṃ . Môṭ trƣờ ng hợp riêng đá ng quan tâm củ a bà i toá n xế p ba lô tổ ng quá t là trƣờ ng hợp mà xi {0, 1}. Khi đó ta có bà i toá n xế p ba lô 0, 1. Vecto xế p ba lô siêu tăng : Trong trƣờ ng hợp vecto (A1, A2, , AN) đƣợc sắ p laị thành (A‟1, A‟2, , A‟N) sao cho: A'  i ta có :  j = A‟i  i. Do đó viêc̣ giả i bà i toá n xế p ba lô 0/1 trở nên dễ dà ng hơn rấ t nhiề u. Hê ̣ mã knapsack do Merkle và Hellman đƣa ra và o năm 1978. Cách xây dựng: ‟ ‟ ‟ ‟ ‟ 1. Chọn 1 vecto siêu tăng A = (a 1, a 2, , a N), chọn 1 số M > 2 * a N, chọn ngẫu nhiên 1 số u < M và (u, M) = 1 ‟ 2. Xây dƣ̣ng Vecto A = (a1, a2, , aN) trong đó ai = (a i * u) mod M -1 3. Khóa: KP = (A, M), KS = (u, u ) 4. Không gian cá c bả n rõ là không gian moị dãy N bit P = (x1, x2, , xn). N Mã hóa: C = (  axii* )mod M i 1 ‟ -1 ‟ ‟ Giải mã: tính C = C * u mod M sau đó giả i bài toán xếp ba lô 0/1 vớ i A , C tƣ̀ đó tìm đƣợc P = (x1, x2, , xn). ‟ -1 Ví dụ 1: Cho hê ̣ mã Knapsack có A = (2, 3, 6, 12, 25), N = 5, M = 53, u = 46, u = 15. a) Hãy tìm các khóa của hệ mã trên b) Mã hóa và giải mã bản mã tƣơng ứng của bản rõ M = 01001. 3.2. Hê ̣ mã RSA Hê ̣ mã RSA đƣợc đăṭ tên dƣ̣a theo cá c chƣ̃ cá i đầ u củ a 3 tác giả của hệ mã là Rivest, Shamir và Adleman. Đây là thuật toán mã hóa nổi tiếng nhất và cũng là thuật toán đƣợc ứng dụng thực tế nhất. Để cài đặt RSA ban đầu mỗi ngƣời dùng sinh khóa công khai và khóa bí mật của mình bằng cách: 79
4. Chƣơng IV: Các hệ mã mật khóa công khai chọn hai số nguyên tố lớnngẫu nhiên( cỡ gần100 chữ số) khác nhau p và q tính N = p*q chọn một số e nhỏ hơn N và (e, (N)) = 1, e đƣợc goị là số mũ lâp̣ mã tìm phần tử ngƣợc của e trên vành module (N), d là số mũ giả i ma ̃ khóa công khai là KP = (e, N) -1 khóa bí mật là KS = K P = (d, p, q) Việc thiết lập khóa này đƣợc thực hiện 1 lần khi một ngƣời dùng thiết lập (thaythế) khóa công khai của họ. Mũ e thƣờng là khá nhỏ (đễ mã hóa nhanh), và phải là nguyên tố cùng nhau với (N). Các giá trị thƣờng đƣợc chọn cho e là 3 hoăc̣ 216 – 1 = 65535. Tuy nhiên khi e nhỏ thì d sẽ tƣơng đố i lớ n . Khoá bí mật là (d, p, q). Các số p và q thƣờng có giá trị xấp xỉ nhau nhƣng không đƣợc bằng nhau . Chú ý là việc để lộ một trong các thành phần trên sẽ làm cho hệ mã hóa trở thành không an toà n. Sử dụng RSA để mã hóa một thông điệp M: Ce =M (mod N) (0<= M < N) giải mã: M = Cd (mod N) Thuật toán mã hóa RSA làm việc đƣợc bởi vì nó dựa trên cơ sở toán học là sự tổng quát định lý Ferma nhỏ của Ơclit: X(N) = 1 (mod N). Trong thuật toán RSA chúng ta chọn e và d là nghịch đảo của nhau trên vành Z(N) với e đƣợc chọn trƣớc. Do đó chúng ta sẽ có e.d  1 mod (N), suy ra: M = Cd = M e.d = M1+q.(N) = M . (M(N))q = M mod N Công thức này đảm bảo việc giải mã sẽcho kết quả đúng là bản rõ ban đầu (chú ý là điều này chỉ đúng khi p khác q). Ví dụ 1: Cho hệ mã RSA có N = p*q = 11 * 47 = 517, e = 3. Hãy tìm các khóa công khai và bí mật của hệ mã trên Mã hóa bản rõ M = 26. Đầu tiên ta tính đƣợc (N) = 460 = 10 * 46, do (3,460) = 1 nên áp dụng thuật toá n Ơclit mở rộng ta tìm đƣợc d = 307. Vậy khóa công khai của hệ mã KP = (e, N) = (3, 517), khóa bí mật là KS = (d, p, q) = (307, 11, 47). Mã hóa M = 26 ta có C = Me mod N = 263 mod 517 = 515. Độ an toàn của RSA Độ an toàn của RSA phụ thuộc vào độ khó của việc tính(N) và điều này đòi hỏi chúng ta cần phân tích N ra thừa số nguyên tố. Thuật toán phân tích số nguyên tốhiệu quả nhất hiện nay là Brent-Pollard, chúng ta hãy xem xét bảng thống kê sau để thấy đƣợc tốc độ hoạt động của nó: Số chữ số trong hệ thập phân của N Số các thao tác Bit để phân tích N 80
5. Chƣơng IV: Các hệ mã mật khóa công khai 20 7.20e+03 40 3.11e+06 60 4.63e+08 80 3.72e+10 100 1.97e+12 120 7.69e+13 140 2.35e+15 160 5.92e+16 180 1.26e+18 200 2.36e+19 Bảng 4.1: Tố c đô ̣ củ a thuâṭ toá n Brent-Pollard Các nghiên cứu vềấn v đề phân tích các số nguyên lớn hiện nay tiến triển rất chậm, các tiến bộ lớn nhất cũng chỉ là các cải tiến về thuật toán và có thể nói rằng trừ khi có các đột phá trong việc phân tích các số 1024 bit, RSA là an toàn trong thời điểm hiệnnay. Các nhà mật mã học phát minh ra hệ mã RSA đã đƣa ra một giải thƣởng trị giá100 $ vào năm 1977. Đó là một hệ mã với số N có 129 chữ số,thách thức này đã đƣợc phá. Trên thực tế để cài đặt RSA cần phải thực hiện các thao tác modulo với các số 300 chữ số (hay 1024 bit) mà hiện nay các máy tính mới chỉ thao tác với cácsố nguyên 64 bit, điều này dẫn đến nhu cầu cần các thƣ viện số học nhân chính xác để làm việc với cácsố nguyên lớn này. Ngoài ra việc sử dụng RSA cần tới các số nguyên tố lớn nên chúng ta cũng phải có một cơ sở dữ liệu các số nguyên tố. Để tăng tốc cho RSA chúng ta có thể sử dụng một số phƣơng pháp khác chẳng hạn nhƣ cải tiến các phép tính toán nhân hai số lớn hoặc tăng tốc việc tìm bản mã, bảnrõ. Đối với phép nhân 2 số n bit thông thƣờng chúng ta cần thực hiện O(n2) phép tính bit. Thuật toán nhân các số nguyên Schonhage – Strassen cho phép chúng ta thực hiện phép nhân 2 số với độ phức tạp là O(nlog n) với các bƣớc nhƣ sau: Chia mỗi số nguyên thành các khối, sử dụng các khối này nhƣ các hệ số của một đa thức. Tính các đa thức này tại một số các điểm thích hợp, và nhân các kếtquảthu đƣợc. Nội suy các kết quả này hình thành các hệ số của đa thức tích Kết hợp các hệ số để hình thành nên tích của hai số banđầu Biến đổi Fourier rời rạc, và lý thuyết chặp có thể đƣợc sử dụng để tăng tốcđộ của quá trình nội .suy 81
6. Chƣơng IV: Các hệ mã mật khóa công khai Một cách khác nữa để tăng tốc việc nhân các số lớn trong hệ mã RSA làsử dụng các phần cứng chuyên dụng với các thuật toán song song. Nhƣ đã trình bày ở phần trƣớc khi mã hóa chúng ta thƣờng chọn e nhỏ để đẩy nhanh quá trình mã hóa nhƣng điều này cũng đồng nghĩa là việc giải mã sẽ chậm dosố mũ lớn. Một cải tiến đáng kể trong tốc độ giải mã RSA có thể nhận đƣợc bằng cáchsử dụng định lý phần dƣ Trung Hoa làm việc với modulo p và q tƣơng ứng thay vì N. Vì p và q chỉ bằng một nửa của N nên tính toán sẽ nhanh hơn nhiều. Định lý phần dƣ Trung Hoa đƣợc sử dụng trong RSA bằng cách tạo ra hai phƣơng trình từ việc giải mã M = Cd (mod N) nhƣ sau: d mod (p-1) M1 = M mod p = (C mod p) d mod (q-1) M2 = M mod q = (C mod q) Sau đó ta giải hệ: M = M1 mod p M = M2 mod q Hệ này có nghiệm duy nhất theo định lý phần dƣ Trung Hoa M = [(M2 + q – M1)u mod q] p + M1 Trong đó p.u mod q = 1 Việc sử dụng định lý phần dƣTrung Hoa là một phƣơng pháp đƣợc sử dụng rộng rãi và phổ biến để tăng tốc độ giải mã củaRSA. Hiêṇ tƣợng lô ̣ bả n rõ Môṭ hiêṇ tƣợng cầ n lƣu ý kh i sƣ̉ duṇ g cá c hê ̣ mã RSA là hiêṇ tƣợng lô ̣ bả n rõ . Ta 17 hãy xét hệ mã RSA có N = p*q = 5*7, e = 17, khi đó vớ i M = 6 ta có C = 6 mod N = 6. e Tƣơng tƣ̣ vớ i hê ̣ mã RSA có N = p*q = 109*97, e = 865, vớ i moị M ta đề u có M mod N = M. Theo tính toá n thì vớ i môṭ hê ̣ mã RSA có N = p*q và e bấ t kỳ , số lƣợng bả n rõ sẽ bi ̣ lô ̣ khi mã hó a sẽ là (1 + (e-1, p-1))*(1 + (e-1, q-1)). Trong số cá c hê ̣ mã khó a công khai thì có lẽ hê ̣ mã RSA (cho tớ i thờ i điể m hiêṇ taị ) là hệ mã đƣợc sử dụng rộng rãi nhất.Tuy nhiên do khi là m viêc̣ vớ i dƣ̃ liêụ đầ u và o (thông điêp̣ mã hó a , bản rõ) lớ n thì khố i lƣợng tính toá n rấ t lớ n nên trên thƣ̣c tế ngƣờ i ta hay dùng hệ mã này để mã hóa các dữ liệu c ó kích thƣớc nhỏ, hoăc̣ có yêu cầ u bả o mâṭ cao , chẳ ng haṇ nhƣ cá c khó a phiên (session key) trong cá c phiên truyề n tin . Khi đó hê ̣ mã RSA sẽ đƣợc sƣ̉ duṇ g kế t hợp vớ i môṭ hê ̣ mã khố i khá c , chẳ ng haṇ nhƣ AES , theo mô hình lai ghép nhƣ sau: 82
7. Chƣơng IV: Các hệ mã mật khóa công khai Khóa công Khóa bí mật khai của B của B C1 C1 Khóa Khóa RSA RSA phiên K phiên K C2 C2 P AES AES P A - ngƣời gửi B - ngƣời nhận Hình 4.3: Mô hình ƣ́ ng duṇ g lai ghé p RSA vớ i cá c hê ̣ mã khố i 3.3. Hê ̣ mã El Gamal Hệ mã El Gamal là một biến thể của sơ đồ phân phối khoá Diffie– Hellman. Hệ mã này đƣợc El Gamal đƣa ra vào năm 1985. Giống nhƣ sơ đồ phân phối khóa Diffie – Hellman tính an toàn của nó dựa trên tính khó giải của bài toán logarit rờirạc. Nhƣợc điểm chính của nó là kích thƣớc thông tin sau khi mã hóa gửi đi sẽ tăng gấp đôi sovới thông tin gốc. Tuy nhiên so với RSA, El Gamal không có nhiều rắc rối về vấn đề bản ềquy n sử dụng. Ban đầu ngƣời ta sẽ chọn một số nguyên tố lớn p và hai số nguyên tuỳ ý nhỏ hơnp * là a (a là môṭ phầ n tƣ̉ nguyên thủ y củ a Z P) và x (x là của ngƣời nhận, bí mật) sau đó tính: y = ax mod p Để mã hóa một thông điệp M(là một số nguyên trên ZP) thành bản mã C ngƣời gửi chọn một số ngẫu nhiên k nhỏ hơn p và tính khóa mã hóaK: K = yk mod p Sau đó tính cặp bản mã: k C1 = a mod p C2 = K.M mod p Và gửi bản mã C = (C1, C2) đi (chú ý là sau đó ksẽ bị huỷ). Để giải mã thông điệp đầu tiên ta cần tínhlại khóa mã hóa thông điệp K: x k.x K = C1 mod p = a mod p Sau đó tính M bằng cách giải phƣơng trình sau đây: -1 M = C2 . K mod p Việc giải mã bao gồm việc tính lại khóa tạm thời K (rất giốngvới mô hình của Diffie – Hellman đƣa ra). Khóa công khai của hệ mã là (p, a, y), khóa bí mật làx. Ví dụ: Cho hệ mã El Gamal có P = 97, a = 5, x = 58. 83
8. Chƣơng IV: Các hệ mã mật khóa công khai Tìm khóa của hệ mã trên. Mã hóa bản rõ M = 3 với k đƣợc chọn bằng 36. 58 Trƣớc hết ta tính y = 5 mod 97 = 44, từ đó suy ra KP = (P, a, y) = (97, 5, 44) và KS = (58). Để mã hóa thông điệp M = 3 ta tính khóa K = 4436 mod 97 = 75 sau đó tính: 36 C1 = 5 = 50 mod 97 C2 = 75.3 mod 97 = 31 mod 97 Vậy bản mã thu đƣợc là C = (50, 31). Vấn đề đối với các hệ mã khóa côngkhai nói chung và El Gamal nói riêng là tốc độ (do phải làm việc với các số nguyên lớn), bên cạnh đó dung lƣợng bộ nhớ dành choviệc lƣu trữ các khóa cũng lớn. Với hệ mãEl Gamal chúng ta cần gấp đôi bộ nhớ để chứa bản mã so với các hệ mã khác. Ngoài ra do việc sử dụng các số nguyên tố nên việc sinh khóa và quản lý khóa cũng khó khăn hơn với các hệ mã khối. Trên thực tế các hệ mã khóa công khai thƣờng đƣợc sử dụng kết hợp với các hệ mã khối (mã hóa khóa của hệmã) hoặc ể đ mã hóa các thông tin có dung lƣợng nhỏ và là một phần quan trọng của một phiên truyền tin nào đó. Thám mã đối với hệ mã El Gamal Để thƣ̣c hiêṇ thá m mã hê ̣ mã El Gamal chú ng ta cầ n giả i bà i toá n Logaritm rờ i rac̣ . Ở đây chúng ta sẽ xem xét hai thuật toán có thể áp d ụng để giải bài toán này , vớ i đô ̣ phƣ́ c tap̣ và khả năng á p duṇ g khá c nhau. Thuâṭ toá n Shank Thuâṭ toá n nà y cò n có tên khá c là thuâṭ toá n cân bằ ng thờ i gian – bô ̣ nhớ (Time- Memory Trade Off), có nghĩa là nếu chúng ta có đủ bô ̣ nhớ thì có thể sƣ̉ duṇ g bô ̣ nhớ đó để làm giảm thời gian thực hiện của thuật toán xuống. * Input: số nguyên tố p, phầ n tƣ̉ nguyên thủ y a củ a Z p , số nguyên y. x Output: cầ n tìm x sao cho a mod p = y. Thuâṭ toán: Gọi m = [(p-1)1/2] (lấ y phầ n nguyên). mj Bƣớ c 1: Tính a mod p vớ i 0 ≤ j ≤ m-1. mj mj Bƣớ c 2: Sắ p xế p cá c căp̣ (j, a mod p) theo a mod p và lƣu và o danh sá ch L1. -i Bƣớ c 3: Tính ya mod p vớ i 0 ≤ i ≤ m-1. -i mj Bƣớ c 4: Sắ p xế p cá c căp̣ (i, ya mod p) theo a mod p và lƣu và o danh sá ch L2. mj -i Bƣớ c 5: Tìm trong hai danh sách L 1 và L2 xem có tồ n taị căp̣ (j, a mod p) và (i, ya mod p) nào mà amj mod p = ya-i mod p (tọa độ thứ hai của hai cặp bằng nhau). mj Bƣớ c 6: x = (mj + i) mod (p-1). Kế t quả nà y có thể kiể m chƣ́ ng tƣ̀ công thƣ́ c a mod p = ya-i mod p => amj + i mod p = y mod p => x = (mj + i) mod (p-1). 84
9. Chƣơng IV: Các hệ mã mật khóa công khai 1/2 Độ phức tạp của thuật toán phụ thuộc vào m = [(p-1) ], vớ i giá tri ̣củ a m , chúng ta cầ n tính cá c phầ n tƣ̉ thuôc̣ hai danh sá ch L 1 và L 2, đều là các phép toán lũy thừa phụ thuôc̣ và o j và i , i và j laị phu ̣ thuôc̣ và o m nên có thể nhâṇ thấ y là thuâṭ toá n nà y chi ̉ có thể á p duṇ g trong nhƣ̃ ng trƣờ ng hợp mà p nhỏ. Thuâṭ toán Pohlig-Hellman Có những trƣờng hợp đặc biệt mà bài toán Logarithm rời rạc có thể giải quyết với 1/2 đô ̣ phƣ́ c tap̣ nhỏ hơn O(p ), chẳ ng haṇ nhƣ khi p – 1 chỉ có các ƣớc nguyên tố nhỏ. Môṭ thuâṭ toá n là m viêc̣ vớ i cá c trƣờ n g hợp nhƣ vâỵ đã đƣợc Pohlig và Hellman đƣa ra và o năm 1978. Giả sử p – 1 = 2n. * (p-1)/2 Gọi a là phần tử nguyên thủy của Z p , p là môṭ số lẻ và a mod p = -1. Gọi m là m số nguyên thuôc̣ khoả ng [0, p-2] mà chúng ta cầ n tìm để y = a mod p. Giả sử m đƣợc n-1 biể u diễn thà nh daṇ g nhi ̣phân m = m0 + 2m1 + 4m2 + + 2 mn-1. Khi đó : p 1 p 1 p 1 p 1 21n m0 10 nÕu m 2m 2m0 2 m 1 2 m 2 2 mn 1 2 2 0 y ()() a a a 11 nÕu m0 (p-1)/2 Viêc̣ tính y mấ t nhiề u nhấ t 2[log2p] bƣớ c và sẽ cho ta m 0. Khi xá c điṇ h đƣợc y 1 -m = ya 0, ta lăp̣ laị thao tá c tƣơng tƣ̣ để tính m1: p 1 p 1 p 1 n 2 m1 10 nÕu m 4m1 2 m 2 2 mn 1 2 2 1 c1 () a a 11 nÕu m1 Quá trình tính toán cứ thể tiếp diễn cho tới khi chúng ta tìm đƣợc m i. Độ phức tạp 2 của thuật toán là: n(2[log2p] + 2) ~ O((log2p) ). 3.4. Các hệ mã mật dựa trên cá c đƣờ ng cong Elliptic Hầ u hế t cá c sả n phẩ m và cá c chuẩ n sƣ̉ duṇ g cá c hê ̣ mã khó a công khai để mã hó a và chữ ký điện tử hiện nay đều sử dụng hệ mã RSA . Tuy nhiên vớ i sƣ̣ phá t triể n củ a ngành thám mã và năng lực ngày càng tăng nhanh chóng của các hệ thống máy tính , đô ̣ dài khóa để đảm bảo an toàn cho hệ mã RSA cũng ngày càng tăng nhanh chóng , điề u này làm giảm đáng kể hiệu năng của các hệ thống sử dụng hệ mã RSA , đăc̣ biêṭ là vớ i các ứng dụng thƣơng mại điện tử trực tuyến hay các hệ thống realtime đòi hỏi thời gian xƣ̉ lý nhanh chó ng . Gầ n đây môṭ hê ̣ mã mớ i đã xuấ t hiêṇ và có khả năng thay thế cho RSA, đó là cá c hê ̣ mã khó a công khai dƣ̣a trên c ác đƣờng cong Elliptic – ECC (Elliptic Curve Cryptography). Điể m hấ p dẫn nhấ t củ a cá c hê ̣ mã dƣ̣a trên cá c đƣờ ng cong Elliptic là nó cho phép đạt đƣợc tính an toàn tƣơng đƣơng với RSA trong khi kích thƣớc khóa sử dụng lại nhỏ hơn rấ t nhiề u, làm giảm số phép tính sử dụng khi mã hóa, giải mã và do đó đạt đƣợc hiêụ năng và tố c đô ̣ cầ n thiế t . Trên lý thuyế t tính an toà n củ a ECC không cao bằ ng so vớ i RSA và cũng khó giả i thích môṭ cá ch dễ hiể u hơn so vớ i RSA hay Diffie -Hellman. Cơ sở toán học đầy đủ của các hệ mã dựa trên đƣờng cong Elliptic vƣợt ra ngoài phạm vi của tài liệu này , trong phầ n nà y chú ng ta sẽ chi ̉ xem xé t cá c vấ n đề cơ bả n củ a cá c đƣờ ng cong Elliptic và các hệ mã ECC. 85
10. Chƣơng IV: Các hệ mã mật khóa công khai 3.4.1. Nhóm Abel Nhóm Abel G , thƣờ ng đƣợc ký hiêụ là {G, •} là một tập hợp với một phép toán hai ngôi ký hiêụ là •, kế t qủ a thƣ̣c hiêṇ củ a phé p toá n vớ i hai phầ n tƣ̉ a , b G, ký hiệu là (a • b) cũng là một phầ n tƣ̉ thuôc̣ G, tính chất này gọi là đóng đối với tập G. Đối với phép toán • cá c mêṇ h đề sau đề u thỏ a mãn: (A1):  a, b G thì (a • b) G, tính đóng (Closure) (A2):  a, b, c G thì a • (b • c) = (a • b) • c, tính kết hợp (Associate) (A3): Tồ n taị e G: e • a = a • e = a  a G, e đƣợc goị là phầ n tƣ̉ đơn vi ̣củ a tâp̣ G. (A4):  a G, luôn  a‟ G: a • a‟ = a‟ • a = e, a‟ là phần tử nghịch đảo của a. (A5):  a, b G: a • b = b • a, tính giao hoán (Commutative). Rấ t nhiề u cá c hê ̣ mã khó a công khai dƣ̣a trên cá c nhó m Abel. Chẳ ng haṇ , giao thƣ́ c trao đổ i khó a Diffie -Hellman liên quan tớ i viêc̣ nhân cá c căp̣ số nguyên khá c không theo modulo q (nguyên tố ). Các khóa đƣợc sinh ra bởi phép tính lũy thƣ̀ a trên nhó m. Đối với các hệ mã ECC, phép toán cộng trên các đƣờng cong Elliptic đƣợc sử dụng là phép toán cơ bản. Phép nhân đƣợc định nghĩa là sự lặp lại của nhiều phép cộng : a x k = (a + a + + a). Viêc̣ thá m mã liên quan tới việc xác định giá trị của k với các thông tin công khai là a và (a x k). Môṭ đƣờ ng cong Elliptic là môṭ phƣơng trình vớ i hai biế n và cá c hê ̣ số . Các đƣờng cong sƣ̉ duṇ g cho cá c hê ̣ mã mâṭ có cá c biế n và cá c hê ̣ thố ng là cá c phầ n tƣ̉ thuôc̣ về môṭ trƣờ ng hƣ̃ u haṇ , điề u nà y taọ thà nh môṭ nhó m Abel . Trƣớ c hế t chú ng ta sẽ xem xé t các đƣờng cong Elliptic trên trƣờng số thực. 3.4.2. Các đƣờng cong Elliptic trên trƣờ ng số thƣ̣c Các đƣờn g cong Elliptic không phả i là cá c đƣờ ng Ellipse . Tên goị đƣờ ng cong Elliptic đƣợc đăṭ vì loaị đƣờ ng cong nà y đƣợc mô tả bở i cá c phƣơng trình bâc̣ ba , tƣơng tƣ̣ nhƣ cá c phƣơng trình đƣợc dù ng để tính chu vi củ a môṭ Ellipse . Ở dạng chung nhấ t phƣơng trình bâc̣ 3 biể u diễn môṭ đƣờ ng cong Elliptic có daṇ g: y2 + axy + by = x3 + cx2 + dx + e. Trong đó a , b, c, d, e là cá c số thƣ̣c , x và y là cá c biế n thuôc̣ trƣờ ng số thƣ̣c . Vớ i mục đích để hiểu về các hệ mã EC C chú ng ta chi ̉ xé t cá c daṇ g đƣờ ng cong Elliptic có dạng: 2 3 y = x + ax + y (phƣơng trình 1) Các phƣơng trình này đƣợc gọi là các phƣơng trình bậc ba , trên cá c đƣờ ng cong Elliptic chú ng ta điṇ h nghiã môṭ điể m đăc̣ biêṭ goị là điể m O hay điể m taị vô cù ng (point at infinity). Để vẽ đƣờ ng cong Elliptic chú ng ta cầ n tính cá c giá tri ̣theo phƣơng trình: y x3 ax b Vớ i mỗi giá tri ̣cu ̣ thể củ a a và b , sẽ cho chúng ta hai giá trị của y (môṭ âm và môṭ dƣơng) tƣơng ƣ́ ng vớ i môṭ giá tri ̣củ a x , các đƣờng cong dạng này luôn đối xứng qua đƣờ ng thẳ ng y = 0. Ví dụ về hình ảnh của một đƣờng cong Elliptic: 86
11. Chƣơng IV: Các hệ mã mật khóa công khai Hình 4.4: Các đƣờng cong Elliptic trên trƣờng số thực Chúng ta xem xét tập điểm E (a, b) chƣ́ a tấ t cả các điểm (x, y) thỏa mãn phƣơng trình 1, cùng với điểm O. Sƣ̉ duṇ g cá c căp̣ (a, b) khác nhau chúng ta có các tập E (a, b) khác nhau. Sƣ̉ duṇ g ký hiêụ nà y ta có hình vẽ minh họa trên là biểu diễn của hai tập hợp E(1, 0) và E(1, 1) tƣơng ƣ́ ng. 3.4.3. Mô tả hình hoc̣ củ a phé p công̣ trên cá c đƣờ ng cong Elliptic Vớ i mỗi căp̣ (a, b) cụ thể chúng ta có thể thành lập một nhóm trên tập E (a, b) vớ i các điều kiêṇ sau: 4ab32 27 0 (điề u kiêṇ 1). 87
12. Chƣơng IV: Các hệ mã mật khóa công khai Vớ i điề u kiêṇ bổ sung nà y ta điṇ h nghiã phé p côṇ g trên đƣờ ng cong Elliptic , mô tả về măṭ hình hoc̣ nhƣ sau: nế u ba điể m trên môṭ đƣờ ng cong Elliptic taọ thà nh môṭ đƣờ ng thẳ ng thì tổng của chúng bằng O. Vớ i điṇ h nghiã nà y cá c luâṭ củ a phé p côṇ g trên đƣờ ng cong Elliptic nhƣ sau: 1. O là phần tử trung hòa của phép cộng .  P E(a, b): P + O= P. Trong cá c mêṇ h đề sau chú ng ta giả sƣ̉ P, Q ≠ O. 2. P = (x, y) thì phầ n tƣ̉ đố i củ a P, ký hiệu là P, sẽ là (x, -y) và P + (P) = P P = O. P và P nằ m trên môṭ đƣờ ng thẳ ng đƣ́ ng 3. Để côṇ g hai điể m P và Q không có cù ng hoà ng đô ̣ x , vẽ một đƣờng thẳng nố i chú ng và tìm giao điể m R . Dễ dà ng nhâṇ thấy chỉ có một điểm R nhƣ vậy , tổ ng củ a P và Q là điểm đối xứng với R qua đƣờng thẳng y = 0. 4. Giao điể m củ a đƣờ ng thẳ ng nố i P vớ i đố i củ a P , tƣ́ c P, đƣợc xem nhƣ cắ t đƣờ ng cong taị điể m vô cƣ̣c và đó chính là O. 5. Để nhân đôi môṭ điể m Q, ta vẽ môṭ tiế p tuyế n taị Q vớ i đƣờ ng cong và tìm giao điể m S: Q + Q = 2Q = S. Vớ i 5 điề u kiêṇ nà y E(a, b) là một nhóm Abel. 3.4.4. Mô tả đaị số về phép cộng Trong phầ n nà y chú ng ta sẽ trình bà y môṭ số kế t quả cho phé p tính toá n trên cá c đƣờ ng cong Elliptic. Vớ i hai điể m phân biêṭ P = (xP, yP) và Q = (xQ, yQ) không phả i là đố i của nhau , đô ̣ dố c củ a đƣờ ng nố i l giƣ̃ a chú ng là Ä = (yQ, yP). Có chính xác một điểm khác mà l giao với đƣờn g cong, và đó chính là đối của tổng giữa P và Q . Sau môṭ số phép toán đại số chúng ta có thể tính ra R = P + Q nhƣ sau: 2 xRPQ y x yRPPR y () x y Phép toán nhân đôi đối với P đƣợc tính nhƣ sau: 2 3xaP 2 xxRP ( ) 2 2yP 2 3xaP yRPRP ( )( x x ) y 2yP 3.4.5. Các đƣờng cong Elliptic trên ZP Các hệ mã ECC sử dụng các đƣờng cong Elliptic với các biến và các hệ số giới hạn thuôc̣ về môṭ trƣờ ng hƣ̃ u haṇ . Có hai họ các đƣờng cong Elliptic có thể sử dụng với các m hê ̣ mã ECC: các đƣờng cong nguyên tố trên ZP và các đƣờng cong nhị phân trên GF(2 ). Môṭ đƣờ ng cong nguyên tố trên Z P, chúng ta sử dụng phƣơng trình bậc ba mà các biến và các hệ số của nó đều là các giá trị nguyên nằm từ 0 tớ i p-1 và các phép tính đƣợc thƣ̣c hiêṇ theo modulo P . Trên đƣờ ng cong nhi ̣phân , các biến và các hệ số là các giá trị n n trên GF(2 ). và các tính toán đƣợc thực hiện trên GF (2 ). Các nghiên cứu về lý thuyế t đã cho thấ y cá c đƣờ ng cong nguyên tố là phù hợp nhấ t cho cá c ƣ́ ng duṇ g phầ n mề m vì nhƣ̃ ng phƣ́ c tap̣ trong tính toá n đố i vớ i cá c đƣờ ng cong nhi ̣phân , nhƣng đố i vớ i cá c ƣ́ ng dụng phần cứng thì việc sử dụng các đƣờng cong nhi ̣phân laị tố t hơn vì cơ chế là m viêc̣ của các mạch, các con chíp rất phù hợp với các tính toán trên trƣờng nhị phân. 88
13. Chƣơng IV: Các hệ mã mật khóa công khai Vớ i cá c đƣờ ng cong Elliptic trên Z P chúng ta định nghĩa lại phƣơng trình biểu diễn nhƣ sau: 2 3 y mod p = (x + ax + y) mod p. (phƣơng trình 2) Chẳ ng haṇ cá c giá tri ̣a = 1, b = 1, x = 9, y = 9, y = 7, p = 23 thỏa mãn phƣơng trình trên. Các giá trị hệ số a , b và cá c biế n số x , y đề u thuôc̣ Z P. Tâp̣ EP(a, b) gồ m tấ t cả cá c căp̣ (x, y) thỏa mãn phƣơng trình phƣơng trình 2. Ví dụ với p = 23, a = b = 1, ta có tâp̣ E23(1, 1): (0, 1) (6, 4) (12, 19) (0, 22) (6, 19) (13, 7) (1, 7) (7, 11) (13, 16) (1, 16) (7, 12) (17, 3) (3, 10) (9, 7) (17, 20) (3, 13) (9, 16) (18, 3) (4, 0) (11, 3) (18, 20) (5, 4) (11, 20) (19, 5) (5, 19) (12, 4) (19, 18) Bảng 4.2: Biể u diễn củ a tâp̣ E23(1, 1) 89
14. Chƣơng IV: Các hệ mã mật khóa công khai Các qui tắc về phép cộng cũng đƣợc định nghĩa tƣơng tự đối với các đƣờng cong Elliptic nguyên tố : Điề u kiêṇ : (4a3 + 27b2) mod p ≠ 0. 1. P + O = P 2. Nế u P = (xP, yP) thì P +(xP, yP) = O, điể m (xP, yP) đƣợc goị là đố i củ a P , ký hiêụ là P. Chẳ ng haṇ trên E23(1, 1), P = (13, 7) ta có P = (13, 7) nhƣng 7 mod 23 = 16 nên P = (13, 16), cũng thuộc E23(1, 1). 3. Vớ i hai điể m phân biêṭ P = (xP, yP) và Q = (xQ, yQ), R = P + Q = (xR, yR) đƣợc điṇ h nghiã nhƣ sau: 2 xRPQ ( x x )mod p yRPRP ( ( x x ) y )mod p Trong đó : yyQP ( )modp ,( P Q ) xxQP  2 3xaP ( )modp ,() p Q ) 2yP 4. Phép nhân đƣợc định nghĩa là tổng của các phép cộng , chẳ ng haṇ 4P = P + P + P + P. Ví dụ với P = (3, 10) và Q = (9, 7) trên E23(1, 1) ta có : 7 10 3 1  ( )mod 23 ( )mod 23 ( )mod 23 11 nên 9 3 6 2 2 xR = (11 - 3 - 9 ) mod 23 = 17 yR = (11(3 - 17) - 10) mod 23 = 20. Nên P + Q = (17, 20). Để tìm 2P ta tính: 3(32 ) 1 5 1  ( ) mod 23 ( ) mod 23 ( ) mod 23 6 2 10 20 4 Chú ý là để thực hiện phép tính cuối cùng ta lấy phần tử nghịch đảo của 4 trên Z23 sau đó nhân vớ i tƣ̉ số là 1. 2 xR=(6 (3 - 7) - 10) mod 23 = 30 mod 23 = 7 yR = (6(3 - 7) - 10) mod 23 = 34 mod 23 = 12 Kế t luâṇ : 2P = (7, 12). Để xá c điṇ h đô ̣ an toà n củ a cá c hê ̣ mã mâṭ dƣ̣a trên cá c đƣờ ng cong Elliptic , ngƣờ i ta thƣờ ng dƣ̣a trên môṭ con số là số phầ n điể m trên môṭ nhó m Abel hƣ̃ u haṇ , gọi là N , đƣợc điṇ h nghiã trên môṭ đƣờ ng cong Elliptic . Trong trƣờ ng hợp nhó m hƣ̃ u haṇ EP(a, b), ta có cá c câṇ củ a N là : p 1 2 p N p 1 2 p , con số nà y xấ p xi ̉ bằ ng số phầ n tƣ̉ củ a ZP (bằ ng p). 3.4.6. Các đƣờng cong Elliptic dựa trên các trƣờng hữu hạn GF(2m) m m Số phầ n tƣ̉ củ a trƣờ ng hƣ̃ u haṇ GF (2 ) là 2 , các phép toán đƣợc trang bị trên GF(2m) là phép toán cộng và phép toán nhân đƣợc thực hiện với các đa thức . Đối với các m đƣờ ng cong Elliptic dƣ̣a trên GF (2 ), chúng ta sử dụng một phƣơng trình bậc ba với các m biế n và cá c tham số có giá tri ̣thuôc̣ GF (2 ), các phép tính đƣợc thực hiện tuân theo các phép toán trên GF(2m). 1. Phƣơng trình biể u diễn 90
15. Chƣơng IV: Các hệ mã mật khóa công khai So vớ i cá c hê ̣ mã mâṭ dƣ̣a trên cá c đƣờ ng cong trên Z P, dạng biểu diễn của các hệ m mã dựa trên GF(2 ) tƣơng đố i khá c: 2 3 2 y + xy = x + ax + b (phƣơng trình 3) m Trong đó cá c biế n x, y và cá c hê ̣ số a, b là cá c phầ n tƣ̉ củ a GF(2 ) và các phép tính toán đƣợc thực hiện tuân theo các qui tắc trên GF(2m). m Chúng ta ký hiệu E2 (a, b) là tất cả các cặp số nguyên (x, y) thỏa mãn phƣơng trình phƣơng trình 3 và điểm vô cùng O. 4 4 Ví dụ: chúng ta có thể sử dụng GF(2 ) vớ i đa thƣ́ c bấ t khả qui f(x) = x + x + 1. Phầ n 4 4 tƣ̉ sinh củ a GF(2 ) là g thỏa mãn f(g) = 0, g = g + 1, hay ở daṇ g nhi ̣phân là 0010. Chúng ta có bả ng lũy thƣ̀ a củ a g nhƣ sau: g0 = 0001 g4 = 0011 g8 = 0101 g12 = 1111 g1 = 0010 g5 = 0110 g9 = 1010 g13 = 1101 g2 = 0100 g6 = 1100 g10 = 0111 g14 = 1001 g3 = 1000 g7 = 1011 g11 = 1110 g15 = 0001 Chẳ ng haṇ g5 = g4 g = (g+1)g = g2 + g = 0110. 2 3 4 2 4 Xét đƣờng cong Elliptic y + xy = x + g x + 1, trong trƣờ ng hợp nà y a = g và b = 0 5 3 g = 1. Môṭ điể m nằ m trên đƣờ ng cong là (g , g ): (g3)2 + (g5)(g3) = (g5)3 + (g4)(g5)2 + 1  g6 + g8 = g15 + g14 + 1  1100 + 0101 = 0001 + 1001 + 0001  1001 = 1001 4 4 Bảng sau là các điểm trên E2 (g , 1): (0, 1) (g5, g3) (g9, g13) (1, g6) (g5, g11) (g10, g) (1, g13) g6, g8) (g10, g8) (g3, g8) (g6, g14) (g12,0) (g3, g13) (g9, g10) (g12, g12) Hình biểu diễn tƣơng đƣơng: 91
16. Chƣơng IV: Các hệ mã mật khóa công khai 4 4 Hình 4.5: Hình biểu diễn E2 (g , 1) m Môṭ nhó m Abel có thể điṇ h nghiã dƣ̣a trên E2 (a, b) vớ i điề u kiêṇ b≠0. Các luật thực m hiêṇ vớ i phé p côṇ g,  a, b E2 (a, b): 1. P + O = P 2. Nế u P = (xP, yP) thì P + (xP, xP + yP) = O. Điể m (xP, xP + yP) là điểm đối của P, ký hiệu là P. 3. Nế u P = (xP, yP) và Q = (xQ, yQ) và P≠Q, P≠Q thì R = P + Q = (xR, yR) đƣợc xác định bằng các công thức sau: x 2 x x a R PQ yR () xPRRP x x y a Trong đó : yy  QP xxQP 4. Nế u P = (xP, yP) thì R = 2P = (xR, yR) đƣợc xá c điṇ h bằ ng cá c công thƣ́ c sau: xa 2 R 2 yR xPR ( 1) x Trong đó : yP  xP xP 92
17. Chƣơng IV: Các hệ mã mật khóa công khai 3.4.7. Hê ̣ mã mâṭ dƣ̣a trên cá c đƣờ ng cong Elliptic Phép toán cộng trên đƣờng cong Elliptic tƣ ơng ƣ́ ng vớ i phé p nhân theo modulo trong hê ̣ mã RSA , còn phép toán nhân (côṇ g nhiề u lầ n ) trên đƣờ ng cong Elliptic tƣơng ứng với phép lũy thừa theo modulo trong hệ mã RSA . Tƣơng tƣ̣ nhƣ bà i toá n cơ sở củ a hê ̣ mã RSA là bà i toá n phân tích ra dạng thừa số nguyên tố của một số nguyên lớn , các hê ̣ mã dƣ̣a trên cá c đƣờ ng cong Elliptic cũng có cá c bà i toá n cơ sở là môṭ bà i toá n khó giải, gọi là bài toán Logarithm trên đƣờng cong Elliptic: Xét phƣơng trình Q = kP trong đó P, Q EP(a, b) và k < p. Viêc̣ tính Q nế u biế t P và k là môṭ bà i toá n dễ (thƣ̣c hiêṇ theo cá c công thƣ́ c). Nhƣng viêc̣ xá c điṇ h k vớ i giá tri ̣P, Q cho trƣớ c laị là bà i toá n khó . Chúng ta xem xét ví dụ (Certicom Website www.certicom.com): E23(9, 17) đƣợc xá c 2 3 điṇ h bở i phƣơng trình y mod 23 = (x + 9x + 17) mod 23. Vớ i Q = (4, 5) và P = (16, 5) thì k thỏa mãn Q = kP sẽ bằ ng bao nhiêu ? Phƣơng pháp đơn giản nhất là nhân P lên nhiề u lầ n cho tớ i khi bằ ng Q: P = (16, 5), 2P = (20, 20), 3P = P = (16, 5); 2P = (20, 20); 3P = (14, 14); 4P = (19, 20); 5P = (13, 10); 6P = (7, 3); 7P = (8, 7); 8P (12, 17); 9P = (4, 5). Nhƣ vâỵ k = 9. Trên thƣ̣c tế cá c hê ̣ mã sẽ đả m bảo giá trị k là đủ lớn để phƣơng pháp vét cạn nhƣ trên là không thể thực hiện đƣợc. 3.4.8. Phƣơng phá p trao đổ i khó a Diffie-Hellman dƣ̣a trên cá c đƣờ ng cong Elliptic Ban đầ u ngƣờ i ta choṇ môṭ số nguyên lớ n q , có thể là một số nguyên tố p hay có m dạng 2 tƣơng ƣ́ ng vớ i cá c phƣơng trình biể u diễn và cá c tham số a , b. Viêc̣ lƣ̣a choṇ này cho chúng ta tập hợp E q(a, b). Tiế p theo choṇ môṭ điể m G = (x1, y1) EP(a, b) có bậc n rấ t lớ n, bâc̣ n củ a điể m G là số nguyên nhỏ nhấ t thỏ a mãn nG = O. Eq(a, b) và G là các tham số công khai cho hê ̣ mã mâṭ dƣ̣a trên đƣờ ng cong Elliptic tƣơng ƣ́ ng vớ i cá c tham số p, a, b. Phƣơng phá p trao đổ i khó a giƣ̃ a hai ngƣờ i dù ng A và B có thể thƣ̣c hiêṇ nhƣ sau: 1. A choṇ môṭ số nguyên nA nhỏ hơn n. Đó chính là khó a riêng củ a A. Sau đó sinh khó a công khai PA = nA x G, khóa này là một điểm trên Eq(a, b). 2. Tƣơng tƣ̣ B cũng choṇ môṭ khó a riêng nB và tính khóa công khai PB. 3. A sinh môṭ khó a bí mật K = nA x PB. B sinh khó a bí mâṭ K = nB x PA. Dễ dà ng kiể m chƣ́ ng cá c khó a bí mâṭ củ a A và B tính đƣợc đề u bằ ng nhau : nA x PB = nA x (nB x G) = nB x (nA x G) = nB x PA. Hình minh họa các bƣớc: 93
18. Chƣơng IV: Các hệ mã mật khóa công khai Hình 4.6: Phƣơng phá p trao đổ i khó a Diffie-Hellman dƣ̣a trên ECC Để tấ n công phƣơng phá p trao đổ i khó a trên , kẻ tấn công cần phải tính đƣợc giá trị k vớ i cá c giá tri ̣công khai là G và kG, và đây chính là bài toán Logarithm trên đƣờng cong Elliptic, môṭ bà i toá n khó . 2 3 Ví dụ: p = 211, E211(0, 4) tƣơng ƣ́ ng vớ i phƣơng trình biể u diễn y = x + 4, ta choṇ G = (2, 2). Do 240G = O nên n = 240. A choṇ khó a riêng là n A = 121, khóa công khai tƣơng ƣ́ ng củ a A sẽ là P A = 121(2, 2) = (115, 48). Khóa riêng của B là n B = 203 nên khó a công khai cù a B là P B = 203(2, 2) = ( 130, 203). Khóa bí mật (chia sẻ ) giƣ̃ a A và B là 121(130, 203) = 203(115, 48) = (161, 69). 3.4.9. Thuâṭ toá n mã hó a và giả i mã Có nhiều cách mã hóa/giải mã đã đƣợc nghiên cứu với các hệ mã trên các đƣờng cong Elliptic, ở đây chúng ta sẽ xem xét cách đơn giản nhất . Thuâṭ toá n mã hó a ban đầ u sẽ thực hiện phép biến đổi tiền xử lý từ input là một bản rõ m thành dạng một điểm P m. Điể m Pm sẽ đƣợc mã hóa thành bản mã và sau đó giải mã . Thƣ̣c chấ t viêc̣ tiề n xƣ̉ lý nà y không đơn giả n vì không phả i tấ t cả cá c toạ đô ̣ có daṇ g (x, y) đều thuộc E P(a, b). Có 94
19. Chƣơng IV: Các hệ mã mật khóa công khai nhiề u cá ch khá c nhau cho viêc̣ tiề n xƣ̉ lý nà y , chúng ta không bàn kỹ tới chúng ở đây nhƣng thƣ̣c tế là có môṭ và i cá ch dễ hiể u để thƣ̣c hiêṇ viêc̣ đó . Giố ng nhƣ đố i vớ i hê ̣ trao đổ i khó a , chúng ta cần một điểm G và một nhóm Elliptic Eq(a, b) làm tham s ố. Mỗi ngƣờ i dù ng A lƣ̣a choṇ môṭ khó a riêng n A và sinh một khóa công khai PA = nA x G. Để mã hó a môṭ thông điêp̣ P m để gửi tới cho B , A sẽ choṇ môṭ số nguyên dƣơng ngẫu nhiên k và sinh bả n mã Cm gồ m môṭ căp̣ điể m: Cm = {kG, Pm + kPB}. Chú ý là ở đây A sử dụng khóa công khai của B . Để giả i mã bả n mã , B sẽ nhân điể m thƣ́ nhấ t vớ i khó a bí mâṭ củ a B và lấ y kế t quả nhâṇ đƣợc trƣ̀ đi điể m thƣ́ hai: Pm + kPB nB(kG) = Pm + k(nBG) nB(kG) = Pm. A đã che đi giá trị của Pm bằ ng cá ch côṇ g kPB vào Pm. Chỉ có duy nhất A biết giá trị k, nên thâṃ chí biế t khó a công khai P B, không ai có thể loaị bỏ măṭ na ̣ kP B để tìm ra P m. Tuy nhiên giá tri ̣củ a C m cũng gồm một đầu mối để B (ngƣờ i duy nhấ t giƣ̃ khó a riêng n B) có thể dựa vào đầu mối đó mà tìm ra Pm. 2 3 Ví dụ: p = 751, EP(1, 188) tƣơng ƣ́ ng vớ i phƣơng trình y = x + x + 188, G = (0, 376). Giả sử A muốn gửi một thông điệp tƣơng ứng với Pm = (562, 201) và A lựa chọn k = 386, khóa công khai của B là PB = (201, 5). Chúng ta có 386(0, 376) = (676, 558) và (562, 201) + 386(201, 5) = (385, 328). Bản mã sẽ là Cm = {(676, 558), (385, 328)}. 3.4.10. Độ an toàn của các hệ mã mật dựa trên các đƣờng cong Elliptic Độ an toàn của các hệ mã ECC phụ thuộc vào việc xác định đƣợc giá trị của k dựa trên cá c giá tri ̣kP và P. Bài toán này đƣợc gọi là bài toán Logarithm trên các đƣờng cong Elliptic. Thuâṭ toá n nhanh nhấ t để giả i bà i toán này là thuật toán của Pollard . Bảng sau cho chú ng ta sƣ̣ so sá nh tƣơng quan giƣ̃ a cá c hê ̣ ma:̃ Symmetric Scheme ECC-Based Scheme RSA/DSA (modulus (key size in bits) (size of n in bits) size in bits) 56 112 512 80 160 1024 112 224 2048 128 256 3072 92 384 7680 256 512 15360 Nguồ n: Certicom Bảng 4.3: Bảng so sánh các hệ mã ECC với hệ mã RSA 95
20. Chƣơng IV: Các hệ mã mật khóa công khai Có thể thấy là so với RSA , các hệ mã ECC có ƣu thế hơn về độ dài khóa sử dụng , đăc̣ biêṭ là khi chú ng ta sƣ̉ duṇ g cá c khó a có đô ̣ dà i nhỏ thì ECC cò n có ƣu thế về tố c đô ̣ (số phé p tính) xƣ̉ lý trong mã hó a và giả i ma.̃ 4. Bài tập Bài tập 4.1: Cho N = 1517. Hãy tính 131435 mod N. Bài tập 4.2: Trong hệ mã RSA có N = p * q = 103 * (219 – 1) thì có thể sử dụng tối đa là bao nhiêu gía trị của e để làm khóa mã hóa, giải thích. Bài tập 4.3: Trong hệ mã RSA có N = p*q = 103 * 113 sẽ có bao nhiêu trƣờng hợp lộ bản rõ. Bài tập 4.4: Trong hệ chữ ký điện tử ElGamma có p = 231 – 1 khi ký lên một văn bản có thể sử dụng tối đa bao nhiêu gía trị k, giải thích. Bài tập 4.5: Cho hệ mã ElGamma có p = 31, a = 11 và x = 6. Để mã hóa M = 18 ngƣời ta chọn k = 7. Hãy thực hiện tính toán và đƣa ra bản mã kết quả. Bài tập 4.6: Cho hệ RSA óc n = 1363, biết phi(n) = 1288 hãy mã hóa bản rõ M = 2007. Bài tập 4.7: Tƣơng tự Câu 1 với n = 215629 và phi(n) = 214684 hãy giải mã bản mã M = 2007. Bài tâp̣ 4.8: Giả sử có 4 tổ chức sử dụng 4 hệ mã RSA để truyền thông với nhau. GọiN1, N2, N3, N4 lần lƣợt là các tham số tƣơng ứng mà họ sử dụng và(Ni, Nj) = 1  i j và i, j Z5/{0}. Cả bốn hệ RSA này đều có số mũ lập mã là e = 3. Một thông điệp m sau khimã hóa bằng 4 hệ mã trên nhận đƣợc 4 bản mã tƣơng ứng làC1, C2, C3, C4. Hãy tìm m. Bài tâp̣ 4.9: Cho hệ mã Knapsack có A = {11, 15, 30, 60}, M = 150 và u = 77. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Để mã hóa các thông điệp viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi từ các ký tự thành các xâu nhị phân nhƣsau: Ký tự Xâu bít Ký tự Xâu bít Ký tự Xâu bít Ký tự Xâu bít A 00000 H 00111 O 01110 V 10101 B 00001 I 01000 P 01111 W 10110 C 00010 J 01001 Q 10000 X 10111 D 00011 K 01010 R 10001 Y 11000 E 00100 L 01011 S 10010 Z 11001 F 00101 M 01100 T 10011 G 00110 N 01101 U 10100 Khi đó ví dụ xâu ABCD sẽ đƣợc chuyển thành 00000 00001 00010 00011 và cắt thành các xâu có độ dài 4 để thực hiện mã hóa. Kết quả thu đƣợc bản mã là mộtdãycác số ZM. Hãy thực hiện mã hóa xâu P = “ANTI”. c) Giả sử bản mã thu đƣợc làC = . Hãy thực hiện giải mã bản mã trên để thu đƣợc thông điệp banđầu. Bài tập 4.10: Cho hệ mã Knapsack có A = {7, 13, 31, 53}, M = 173 và u = 97. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. 96
21. Chƣơng IV: Các hệ mã mật khóa công khai b) Để mã hóa các thông điệp viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi từ các ký tự thành các xâu nhị phân nhƣ sau: Ký tự Xâu bít Ký tự Xâu bít Ký tự Xâu bít Ký tự Xâu bít A 00000 H 00111 O 01110 V 10101 B 00001 I 01000 P 01111 W 10110 C 00010 J 01001 Q 10000 X 10111 D 00011 K 01010 R 10001 Y 11000 E 00100 L 01011 S 10010 Z 11001 F 00101 M 01100 T 10011 G 00110 N 01101 U 10100 Khi đó ví dụ xâu ABCD sẽ đƣợc chuyển thành 00000 00001 00010 00011 và cắt thành các xâu có độ dài 4 để thực hiện mã hóa. Kết quả thu đƣợc bản mã là một dãy các số ZM. Hãy thực hiện mã hóa xâu P = “AUNT”. c) Giả sử bản mã thu đƣợc là C = . Hãy thực hiện giải mã bản mã trên để thu đƣợc thông điệp banđầu. Bài tập 4.11: Cho hệ mã Knapsack có A = {2, 3, 7, 13, 29, 57}, M = 151 và u = 71. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Để mã hóa các thông điệp viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi từ các ký tự thành các xâu nhị phân nhƣ sau: Ký tự Xâu bít Ký tự Xâu bít Ký tự Xâu bít Ký tự Xâu bít A 00000 H 00111 O 01110 V 10101 B 00001 I 01000 P 01111 W 10110 C 00010 J 01001 Q 10000 X 10111 D 00011 K 01010 R 10001 Y 11000 E 00100 L 01011 S 10010 Z 11001 F 00101 M 01100 T 10011 G 00110 N 01101 U 10100 Khi đó ví dụ xâu ABCDEF sẽ đƣợc chuyển thành 00000 00001 00010 00011 00100 00101 và cắt thành các xâu có độ dài 6 để thực hiện mã hóa. Kết quả thuđƣợc bản mã là một dãy các số ZM. Hãy thực hiện mã hóa xâu P = “ANSWER”. c) Giả sử bản mã thu đƣợc là C = . Hãy thực hiện giải mã bản mã trên để thu đƣợc thông điệp ban đầu. Bài tập 4.12: Cho hệ mã RSA có p = 31, q = 41, e = 271. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Để mã hóa các thông điệp đƣợc viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi các ký tự thành các số thập phân có hai chữ số nhƣsau: Ký tự A B C D E F G H I J K L M Mã hóa 00 01 02 03 04 05 06 07 08 09 10 11 12 Ký tự N O P Q R S T U V W X Y Z Mã hóa 13 14 15 16 17 18 19 20 21 22 23 24 25 97
22. Chƣơng IV: Các hệ mã mật khóa công khai Khi đó ví dụ xâu ABC sẽ đƣợc chuyển thành 00 01 02 và sau đó cắt thành cácsố có 3 chữ số 000 (bằng 0) và 102 để mã hóa. Bản mã thu đƣợc là một tập cácsố ZN. Hãy thực hiện mã hóa xâu P = ”SERIUS”. c) Giả sử bản mã thu đƣợc là C = hãy thực hiện giải mã để tìm ra thông điệp bản rõ ban đầu. Bài tập 4.13: Cho hệ mã RSA có p = 29, q = 43, e = 11. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Để mã hóa các thông điệp đƣợc viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi các ký tự thành các số thập phân có hai chữ số nhƣsau: Ký tự A B C D E F G H I J K L M Mã hóa 00 01 02 03 04 05 06 07 08 09 10 11 12 Ký tự N O P Q R S T U V W X Y Z Mã hóa 13 14 15 16 17 18 19 20 21 22 23 24 25 Khi đó ví dụ xâu ABC sẽ đƣợc chuyển thành 00 01 02 và sau đó cắt thành các số có 3 chữ số 000 (bằng 0) và 102 để mã hóa. Bản mã thu đƣợc là một tập cácsố ZN. Hãy thực hiện mã hóa xâu P = ”TAURUS”. c) Giả sử bản mã thu đƣợc là C = hãy thực hiện giải mãđể tìm ra thông điệp bản rõ ban đầu. Bài tập 4.14: Cho hệ mã RSA có n = 1363, e = 57. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Giả sử bản rõ P = 102 hãy mã hóa và đƣa ra bản mãC. c) Giả sử hệ mã trên đƣợc dùng làm hệ chữ ký điện tử, hãy tính chữ kývới thông điệp M = 201. * Bài tập 4.15: Cho hệ mã ElGamma có p = 83, a = 5 là một phần tử nguyên thuỷ củaZP , x = 37. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Để mã hóa bản rõ P = 72 ngƣời ta chọn k = 23, hãy mã hóa và đƣa ra bảnmã. * c) Hãy tìm tất cả các phần tử nguyên thuỷ của ZP . Bài tập 4.16: Cho hệ mã mật ElGamma có p = 1187, a = 79 là một phần tử nguyên thuỷ * của PZ , x = 113. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Để mã hóa các thông điệp đƣợc viết bằng tiếng Anh ngƣời ta dùng một hàm chuyển đổi các ký tự thành các số thập phân có hai chữ số nhƣsau: Ký tự A B C D E F G H I J K L M Mã hóa 00 01 02 03 04 05 06 07 08 09 10 11 12 Ký tự N O P Q R S T U V W X Y Z Mã hóa 13 14 15 16 17 18 19 20 21 22 23 24 25 98
23. Chƣơng IV: Các hệ mã mật khóa công khai Khi đó ví dụ xâu ABC sẽ đƣợc chuyển thành 00 01 02 và sau đó cắt thành cácsố có 3 chữ số 000 (bằng 0) và 102 để mã hóa. Bản mã thu đƣợc là một tập các cặp số(C1, C2) ZP. Hãy thực hiện mã hóa xâu m = ”TAURUS” với các giá trị 13 . Hãy giải mã và đƣa ra thông điệp ban đầu. Bài tập 4.17: Cho bả n mã nhâṇ đƣợc bằ ng cá ch sƣ̉ duṇ g môṭ hê ̣ mã RSA nhƣ sau: 11437 6198 16611 2405 18636 2679 12205 24142 6375 2134 16611 2405 9529 7260 7834 15094 4667 24027 762 5878 5206 16683 5359 10888 4168 3536 23229 20351 15580 6704 7977 374 6525 4287 14402 527 12887 21628 11884 9402 15470 1339 10420 18051 23125 7747 135 22007 20049 9984 13199 15176 1379 8313 19574 7989 22869 406 10057 21758 3918 23991 14237 7989 3947 19529 15728 5601 3527 7200 7601 13282 21160 6291 15994 7785 8982 3045 6596 16796 4663 2405 20302 11929 17125 14533 21001 8351 11571 22082 11040 8687 6704 3330 5630 19650 13024 Khóa công khai có n = 24637 và e = 3. a) Hãy xác định p, q và d. b) Giải mã bản mã để nhận đƣợc bản rõ (là các số trên Z24637). c) Chuyể n bả n rõ nhâṇ đƣợc thà nh daṇ g văn bả n tiế ng Anh , biế t rằ ng mỗi số nguyên trên Z24637 biể u diễn môṭ bô ̣ 3 chƣ̃ cá i theo qui tắ c sau: DOG 3 × 262 + 14× 26 + 6 = 2398 CAT 2 × 262 + 0× 26 + 19 = 1371 ZZZ 25 × 262 + 25× 26 + 25 = 17575 Bài tập 3.18: Cho hê ̣ mã ElGamal có p = 71 và a = 7. a) Giả sử khóa công khai của B là Y B = 3 và A chọn số ngẫu nhiên k = 2, hãy xác điṇ h bả n mã tƣơng ƣ́ ng vớ i bả n mã M = 30. b) Giả sử A chọn một giá trị ngẫu nhiên k khác và bản mã tƣơng ứng với M = 30 bây giờ là C = (59, C2). Hãy xác định C2? Bài tập 3.19: Cho hê ̣ mã dƣ̣a trên đƣờ ng cong Elliptic có cá c tham số là E 11(1, 6) và G = (2, 7). Khóa bí mật của B là nB = 7. a) Hãy xác định khóa công khai của B? b) Giả sử cần mã hóa bản rõ P m = (10, 9) và số ngẫu nhiên k = 3. Hãy xác định bản mã Cm. c) Minh hoạ quá trình giả i mã vớ i Cm nhâṇ đƣợc ở phầ n b. Sƣ̉ duṇ g môṭ trong cá c ngôn ngƣ̃ lâp̣ trình C, C++, Java hoăc̣ C# để làm các bài tập sau: 99
24. Chƣơng IV: Các hệ mã mật khóa công khai Bài tập 3.20: Viế t chƣơng trình cà i đăṭ thuâṭ toá n mã hó a và giả i mã củ a hê ̣ mã Knapsack. Bài tập 3.21: Viế t chƣơng trình cà i đăṭ thuâṭ toá n mã hóa và giải mã của hệ mã RSA. Bài tập 3.22: Viế t chƣơng trình cà i đăṭ thuâṭ toá n mã hó a và giả i mã củ a hê ̣ mã El Gammal. Bài tập 3.23: Viế t chƣơng trình mã hó a và giả i mã File vớ i thuâṭ toá n mã hó a và giả i mã RSA. Bài tập 3.24: Viế t chƣơng trình truyề n file qua hê ̣ thố ng maṇ g sƣ̉ duṇ g thuâṭ toá n mã hó a RSA. Bài tập 3.25: Viế t chƣơng trình chia sẻ file trên maṇ g cuc̣ bô ̣ sƣ̉ duṇ g hê ̣ mã RSA. Bài tập 3.26: Viế t chƣơng trình phân phố i khó a dƣ̣a trên hê ̣ mã RSA. 100
25. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm CHƢƠNG V: CHƢ̃ KÝ ĐIÊṆ TƢ̉ VÀ HÀ M BĂM 1. Chƣ̃ ký điêṇ tƣ̉ 1.1. Khái niệm về chữ ký điện tử Kể từ khi con ngƣời phát minh ra chữ viết, các chữ ký thƣờng luôn đƣợc sửdụng hàng ngày, chẳng hạn nhƣ ký một biên nhận trên một bức thƣnhận tiền từ ngân hàng, ký hợp đồng hay một văn bản bất kỳ nào đó. Chữ ký viết tay thông thƣờng trêntàiliệu thƣờng đƣợc dùng để xác định ngƣời ký nó. Sơ đồ chữ ký điện tử là một phƣơng pháp ký một văn bản hay lƣu bức điện dƣới dạng điện tử. Chẳng hạn một bức điện có chữ ký đƣợc lƣu hành trên mạng máy tính. Chữ ký điện tử từ khi ra đời đã có nhiều ứng dụng rộng rãi trong các giao dịch thƣơng mại, từ việc xác minh chữ ký cho đến các thẻ tín dụng, cácsơđồ định danh và các sơ đồ chia sẻ bí mật Sau đây, chúng ta sẽ tìm hiểu một số sơ đồ chữ ký quan trọng. Song trƣớc hết, chúng ta sẽ thảo luận một vài điểm khác biệt cơ bản giữa chữ ký thông thƣờng và chữ ký điện tử. Đầu tiên là vấn đề ký một tài liệu. Với chữ ký thông thƣờng nó là một phần vậtlý của tàiiệu. l Tuy nhiên, một chữ ký điện tử không gắn theo kiểu vật lý vào bức điệnnên thuật toán đƣợc dùng phải là “không nhìn thấy” theo cách nào đó trên bức điện. Thứ hai là vấn đề kiểm tra. Chữ ký thông thƣờng đƣợc kiểm tra bằng cách sosánh nó với các chữ ký xác thực khác. Ví dụ, ai đó ký một tấm séc để mua hàng, ngƣời bánsẽ so sánh chữ ký trên mảnh giấy đó với chữ ký nằm ở mặt sau thẻ tín dụng để kiểm tra. Mặt khác, chữ ký số có thể kiểm tra bằng một thuật toán kiểm tra một cách côngkhai. Nhƣ vậy, bất kỳ ai cũng có thể kiểm tra đƣợc chữ ký điện tử. Việc sử dụng một sơ đồký an toàn có thể ngăn chặn đƣợc khả năng giả mạo. Sự khác biệt cơ bản giữa chữ ký điện tử và chữ ký thông thƣờng là ở chỗ: mộtbản copy tài liệu có chữ ký đƣợc đồng nhất với bản gốc. Nóicách khác, tài liệu có chữ ký trên giấy thƣờng có thể khác biệt với bản gốc điều này để ngăn chặn một bức điện đƣợcký khỏi bị dùng lại. Ví dụ, nếu B ký một bức điện xácminh cho A rút 100$ từ tài khoản của mình, anh ta chỉ muốn A có khả năng làm điều đó một lần. Vì thế, bản thân bức điện phải chứa thông tin để khỏi bị dùng lại, chẳng hạn nhƣ dùng dịch vụ gán nhãn thời gian (Time Stamping Service). Một sơ đồ chữ ký điện tử thƣờng chứa hai thành phần: thuật toán ký sig() vàthuật toán xác minh ver(). B có thể ký một bức điện x dùng thuật toán ký an toàn (bí mật). Kết quả chữ ký y = sig(x) nhận đƣợc có thể đƣợc kiểm tra bằng thuật toán xác minh công khai ver(y). Khi cho trƣớc cặp (x, y), thuật toán xác minh cho giá tri TRUE hay FALSE tuỳ thuộc vào việc chữ kýƣợc đ xác thực nhƣ thế nào. Vậy thế nào là chữ ký điện tử? Chúng ta có một số định nghĩa nhƣsau: Là một định danh điện tử đƣợc tạo ra bởi máy tính đƣợc các tổ chức sửdụng nhằm đạt đƣợc tính hiệu quả và có hiệu lực nhƣ là các chữ kýtay. Là một cơ chế xác thực hóa cho phép ngƣời tạo ra thông điệp đính kèm một mã số vào thông điệp giống nhƣ là việc ký một chữ ký lên một vănbảnbình thƣờng. 101
26. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Các chữ ký điện tử đƣợc sinh và sử dụng bởi các hệ chữ ký (sơ đồ) điện tử,dƣới đây là định nghĩa một hệ chữ ký điện .tử Định nghĩa: Một sơ đồ chữ ký điêṇ tử là bộ 5 (P, A, K, S, V) thoả 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 khoá (tập hữu hạn các khoá có thể). 4) Với mỗi khoá K K tồn tại một thuật toán ký sigK S và một thuật toán xác minh verK V. Mỗi sigk: P → A và verK: P x A → {TRUE, FALSE} là những hàm sao cho mỗi bức điện x P và mỗi chữ ký y A thoả mãn phương trình dưới đây: TRUE nếu y = sig(x) Ver (x, y) = FALSE nếu y ≠ sig(x). [5] Với mỗi K K, hàm sigK và verK là các hàm đa thức thời gian. Hàm verK sẽ là hàm công khai còn hàm sigK là bí mật. Không thể dễ dàng tính toán để giả mạo chữ kýcủaB trên bức điện x, nghĩa là với x cho trƣớc chỉ có B mới có thể tính đƣợc y để ver(x, y)= TRUE. Một sơ đồ chữ ký không thể an toàn vô điều kiện vì một ngƣời C nào đó cóthể kiểm tra tất cả chữ số y trên bức điện x nhờ dùng thuật toán ver() công khai cho tớikhi anh ta tìm thấy chữ ký đúng. Vì thế, nếu có đủ thời gian, C luôn có thể giả mạo chữ ký của B. Nhƣ vậy mục đích của chúng ta là tìm các sơ đồ chữ ký điện tử an toàn vềmặt tính toán. Chú ý rằng ai đó có thể giả mạo chữ ký của B trên một bức điện“ngẫu nhiên” x bằng cách tính x = eK(y) với y nào đó; khi đó y = sigK(x). Một biện pháp xung quanh vấn đề khó khăn này là yêu cầu các bức điện chứa đủ phần dƣđể chữ ký giả mạo kiểu này không phù hợp với toàn bộ nội dung của bức điệnxtrừ một xác suất rất nhỏ. Có thể dùng các hàm Băm (hash function) nhƣ MD4, MD5 trong việc tính kết nối các sơ đồ chữ ký điện tử sẽ loạitrừ phƣơng pháp giả mạo này (sẽ trình bày trong các phần sau của tài liệu). 1.2. Hệ chữ ký RSA Dựa vào ƣu điểm của hệ mã RSA, nếu thiết lập đƣợc sơ đồ chữ kýdựatrên bài toán phân tích ra thừa số nguyên tố thì độ an toàn của chữ ký sẽ rất cao. Việc thiết lậpsơ đồ xác thực chữ ký RSA rất đơn giản, ta chỉ cần đảo ngƣợc hàm mã hoá và giải mã.Sau đây là sơ đồ chữ ký RSA. Cho n = p*q, trong đó p, q là các số nguyên tố. Đặt P = A = Zn và định nghĩa: K = {(n, p, q, a, b): n=p*q, p và q là các số nguyên tố, ab ≡ 1 (mod  (n))}. Các giá trị n và b là công khai; còn p, q, a là bí mật. Với K = (n, p, q, a, b), ta xác định: 102
27. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm a sigK(x) = x mod n và b verK(x,y) = TRUE x ≡ y (mod n) với x, y Zn. [5] Thông thƣờng, chữ ký đƣợc kết hợp với hàm mã hoá công khai. Giả sử A muốngửi một bức điện đã đƣợc mã hoá và đã đƣợc ký đến cho B. Với bản rõ x cho trƣớc,Asẽ tính toán chữ ký của mình y = sigA(x) và sau đó mã hoá cả x và y sử dụng khoá công khai eB của B, kết quả nhận đƣợc là z=eB(x, y). Bản mã z sẽ đƣợc gửi tới B, khi B nhận đƣợc z, đầu tiên anh ta giải mã với hàm giải mãdB của mình để nhận đƣợc (x, y). Sau đó anh ta dùng hàm xác minh công khai của Ađể kiểm tra xem verA(x,y) = TRUE hay không. Song nếu đầu tiên A mã hoá x , rồi sau đó mới ký lên bản mã nhận đƣợc thìsao? Khi đó, A sẽ tính: y = sigA(eB(x)) A sẽ truyền cặp (z, y) tới B, B sẽ giải mã z và nhận đƣợc x, sau đó xác minh chữký y trên x nhờ dùng verA. Một vấn đề nảy sinh nếu A truyền (x, y) kiểu này thì một ngƣời thứ ba C có thể thay chữ ký y của A bằng chữ ký của chính mình: y‟ = sigC(eB(x)) Chú ý rằng, C có thể ký lên bản mã eB(x) ngay cả khi anh ta không biết bản rõ x. Khi đó nếu C truyền (z, y‟) đến B, chữ ký của C đƣợc B xác minh bằng verC và do đó, B cho rằng bản rõ x xuất phát từ C. Do khó khăn này, hầu hết ngƣời sử dụng đƣợc khuyến nghị “ký trƣớc khi mã”. 1.3. Hệ chữ ký ElGammal Hệ chữ ký ElGammal đƣợc đƣa ra vào 1985. Một phiên bản sửa đổi hệ này đƣợc Học viện Quốc gia tiêu chuẩn và kỹ thuật (NIST) đƣa ra nhƣ một chuẩn của chữ kýđiện tử. Hệ chữ ký ElGammal đƣợc thiết kế riêng biệt cho mục đích chữ ký, trái ngƣợc với RSA thƣờng đƣợc sử dụng cho cả mục đích mã hoá công khai và chữ ký.Hệ chữ ký ElGammal là không xác định, nghĩa là có rất nhiều giá trị chữ ký cho cùng một bức điện cho trƣớc. Thuật toán xác minh phải có khả năng nhận bất kỳ giá trị chữ ký nàonhƣlà việc xác thực. Sơ đồ chữ ký ElGammal đƣợc miêu tả nhƣ sau: * Cho p là một số nguyên tố như là bài toán logarit rời rạc trong Zp, α Zp là một * * phần tử nguyên tử và P = Zp , A = (Zp )*Zp-1, và định nghĩa: K = {(p, α, a, β) : β ≡ αa (mod p)} trong đó giá trị p, α và β là công khai, còn a là bí mật. * Với K = (p, α, a, β) và chọn một số ngẫu nhiên k Zp-1 , định nghĩa: sigK(x, k) = (, ) trong đó:  = αk mod p  = (x - a*)k-1 mod (p – 1). * Với x,  Zp và  Zp-1, định nghĩa: ver(x, , ) = TRUE β ≡ αx (mod p). [5] 103
28. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Nếu chữ ký là đúng thì việc xác nhận thành công khi: β ≡ αaαk (mod p) ≡ αx (mod p). trong đó: a + k ≡ x (mod p -1). B sẽ tính toán chữ ký bằng việc sử dụng cả giá trị bí mật a (một phần của khoá)và số bí mật ngẫu nhiên k (giá trị để ký bức điện). Việc xác minh có thể thực hiện đƣợcchỉ với các thông tin đƣợc công khai: Ví dụ: Chúng ta chọn p = 467,α = 2, a = 127. Ta tính: β = αa mod p = 2127 mod 467 = 132. Bây giờ B muốn ký lên bức điện x = 100 và anh ta chọn một giá trị ngẫu nhiênk= 213 (chú ý là UCLN(213, 466) = 1 và 213-1 mod 466 = 431). Sau đó tính:  = 2213 mod 467 = 29  = (100 – 127*29)431 mod 466 = 51. Bất cứ ai cũng có thể kiểm tra chữ ký này bằng cách tính: 132292951 ≡ 189 (mod 467) 2100 ≡ 189 (mod 467). Giả sử kẻ thứ ba C muốn giả mạo chữ ký của B trên bức điện x mà không biếtsốbí mật a. Nếu C chọn một giá trị và cố gắng tìm , anh ta phải tính một hàm logarit rời rạc x -   logα  . Mặt khác, nếu đầu tiên anh ta chọn  để cố gắng tìm  thì anh ta phải tính   = αx (mod p). Cả hai việc này đều không thể thực hiện đƣợc. Tuy nhiên có một lý thuyết mà C có thể ký lên một bức điện ngẫu nhiên bằng cách chọn đồng thời ,  và x. Cho i, j là số nguyên với 0 ≤ i, j ≤ p- 2, và UCLN(j, p - 1) = 1. Sau đó tính:  = αiβj mod p  = - j-1 (mod p-1) x = - ij-1 (mod p-1). Nhƣ vậy, ta xem (, ) là giá trị chữ ký cho bức điện x. Việc xác minh sẽ thực hiện nhƣ sau: i j i j 1 β ≡   ( i  j )  j (mod p) i j 1 i j i j ≡   ij    (mod p) 1 i j ≡ ij  (mod p) 1 ≡  ij (mod p) ≡ αx (mod p). Ví dụ: Nhƣ ví dụ trên, ta chọn p = 467, α = 2, β = 132. Kể thứ ba C sẽ chọn i = 99 và j = 179. Anh ta sẽ tính: 104
29. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm  = 299132179 mod 467 = 117  = -117*151 mod 466 = 41 x = 99*44 mod 466 = 331 Cặp giá trị (117, 41) là giá trị chữ ký cho bức điện 331. Việc xác minh đƣợcthực hiện nhƣ sau: 13211711741 ≡ 303 (mod 467) 2331 ≡ 303 (mod 467). Một phƣơng pháp thứ hai có thể giả mạo chữ ký là sử dụng lại chữ ký của bứcđiện trƣớc đó, nghĩa là với cặp (, ) là giá trị chữ ký của bức điện x, nó sẽ đƣợc C kýcho nhiều bức điện khác. Cho h, i và j là các số nguyên, trong đó 0≤ i, j, h ≤ p-2 và UCLN(h - j, p-1) = 1. λ = hαiβj mod p μ = λ(h - j)-1 mod (p-1) x‟ = λ(hx + i)(h - j)-1 mod (p-1). Ta có thể kiểm tra: βλλμ = αx‟ mod p. Và do đó, (λ, μ) là cặp giá trị chữ ký của bức điện x‟. Điều thứ ba là vấn đề sai lầm của ngƣời ký khi sử dụng cùng một giá trị k trong việc ký hai bức điện khác nhau. Cho (, 1) là chữ ký trên bức điện x1 và (, 2) là chữ ký trên bức điện2 x . Việc kiểm tra sẽ thực hiện: β 1 ≡ α x1 (mod p) β  2 ≡ α x 2 (mod p). Do đó: x1 x2  1  2 (mod p) . k Đặt  = α , khi đó: x1 - x2 = k(1 - 2) (mod p-1). Bây giờ đặt d = UCLN(1 - 2, p - 1). Vì d | (1 - 2) và d | (p - 1) nên nó cũng chia hết cho (x1 - x2). Ta đặt tiếp: x x x‟ = 1 2 d   ‟ = 1 2 d p 1 p‟ = d Cuối cùng, ta đƣợc: x‟ ≡ k‟ (mod p‟). Vì UCLN(‟, p‟) = 1 nên ta có:  = (‟)-1 mod p‟ Nhƣ vậy, giá trị k sẽ đƣợc xác định nhƣ sau: 105
30. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm k = x‟ (mod p‟) = x‟ + ip‟ (mod p) Với 0 ≤ i ≤ -d 1, ta có thể tìm đƣợc giá trị k duy nhất bằng hàm kiểm tra:  ≡ αk mod p. 1.4. Chuẩn chữ ký điện tử (Digital Signature Standard) 1.4.1. Thuật toán chữ ký điện tử (Digital Signature Algorithm) Tháng 8/1991, NIST đã đƣa ra thuật toán chữ ký điện tử (DSA) là cơ sở cho chuẩn chữ ký điện tử. Đây là một biến thể của thuật toán ElGammal. 1) Chọn một số nguyên tố q với 2159 < q < 2160. 2) Chọn t sao cho 0 ≤ t ≤ 8 và chọn một số nguyên tố p, trong đó 2511+64t < p < 512+64t 2 và q phải chia hết (p-1) (hay q là môṭ ướ c nguyên tố củ a p-1). * 3) Bây giờ, tạo ra một số α duy nhất cho q trong trường Zp . * (p-1)/q - Chọn một giá trị g Zp và tính α = g mod p. - Nếu α = 1 thì quay lại bước trên. (chọn lại giá trị g cho phù hợp) 4) Chọn một số nguyên ngẫu nhiên a để 1 ≤ a ≤ q-1. 5) Tính y = aα mod p. 6) Như vậy , khoá để ký là (p, q, α, y) được công khai và a là khoá bí mật. 1.4.2. Chuẩn chữ ký điện tử Chuẩn chữ ký điện tử (DSS) đƣợc sửa đổi từ hệ chữ ký ElGammal. Nó đƣợc công bố tại hội nghị Tiêu chuẩn xử lý thông tin Liên Bang (FIPS) vào 19/05/1994 và trở thành chuẩn vào 01/12/1994. DSS sử dụng một khoá công khai để kiểm tra tính toàn vẹncủa dữ liệu nhận đƣợc và đồng nhất với dữ liệu của ngƣời gửi. DSS cũng có thể sử dụngbởi ngƣời thứ ba để xác định tính xác thực của chữ ký và dữ liệu trong nó. Đầu tiên chúngta hãy tìm hiểu động cơ của sự thay đổi này, sau đó sẽ tìm hiểu thuật toán củaDSS. Trong rất nhiều trƣờng hợp, một bức điện có thể đƣợc mã hoá và giải mã mộtlần, vì vậy nó đáp ứng cho việc sử dụng của bất kỳ hệ thống bảo mật nào đƣợc biết làan toàn lúc bức điện đƣợc mã hoá. Nói cách khác, một bức điện đƣợc ký đảm nhiệmchức năng nhƣ một văn bản hợp pháp, chẳng hạn nhƣ các bản hợp đồng, vì vậynócũng giống nhƣ việc cần thiết để xác minh chữ ký sau rất nhiều năm bức điện đƣợc ký. Điều này rất quan trọng cho việc phòng ngừa về độ an toàn của chữ ký đƣợc đƣa ra bởimột hệ thống bảo mật. Vì hệ chữ ký ElGammal không đảm nhận đƣợc điều này, việc thực hiện này cần một giá trị lớn modulo p.Tất nhiên p nên có ít nhất 512-bit, và nhiều ngƣời cho rằng độ dài của p nên là 1024-bit nhằm chống lại việc giả mạo trong tƣơng lai. Tuy nhiên, ngay cả một thuật toán modulo 512-bit dùng để ký cũng phải thực hiện việc tính toán đến -1024 bit. Cho ứng dụng tiềm năng này, có rất nhiều card thông minh đƣợc đƣa ra, nhằm thực hiện một chữ ký ngắn hơn nhƣ mong muốn. DSS đã sửa đổihệ chữ ký ElGammal cho phù hợp theo cách này một cách khéo léo, để mỗi 160-bit bức điện đƣợc ký sử dụng một chữ ký 320-bit, nhƣng việc tính toán đƣợc thực hiện với 512-bit * modulo p. Cách này đƣợc thực hiện nhờ việc chianhỏZp thành các trƣờng có kích thƣớc 2160. Việc thay đổi này sẽ làm thay đổi giá trị: 106
31. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm  = (x + α)k-1 mod(p - 1). Điều này cũng làm cho giá trị kiểm tra cũng thay đổi: αxβ ≡  (mod p). (1.4.2.1) Nếu UCLN(x + α, p - 1) = 1 thì sẽ tồn tại -1 mod (p - 1), do đó (6.1) sẽ biến đổi thành: 1 1 x   ≡  (mod p). (1.4.2.2) Đây chính là sự đổi mới của DSS. Chúng ta cho q là một số nguyên tố160-bit sao cho q | (p-1), và α là một số thứ q của 1 mod p, thì βvà cũng là số thứ q của 1 mod p. Do đó α, β và  có thể đƣợc tối giản trong modulo p mà không ảnh hƣởng gì đến việc xác minh chữ ký. Sơ đồ thuật toán nhƣ sau: Cho p là một số nguyên tố 512-bit trong trường logarit rời rạc Zp; q là một số nguyên * * tố 160-bit và q chia hết (p-1). Cho α Zp ; P = Zp , A = Zq*Zq, và định nghĩa: K = {(p, q, α, a, β) : β ≡ αa (mod p)} trong đó giá trị p, q, α và β là công khai, còn a là bí mật. Với K = (p, α, a, β) và chọn một số ngẫu nhiên k (1 ≤ k ≤ q-1), định nghĩa: sigK(x, k) = (, ) trong đó:  = (αk mod p) mod q  = (x + a*)k-1 mod q. * Với x Zp và ,  Zq, việc xác minh được thực hiên bằng cách tính: -1 e1 = x mod q -1 e2 =  mod q ver(x, , ) = TRUE ( e1  e2 mod p) mod q = . [5] Chú ý rằng, với DSS thì  0 (mod q) vì giá trị: -1 mod q cần cho việc xác minh chữ ký (điều này cũng tƣơng tự nhƣ việc yêu cầu UCLN(, p-1) = 1 để (1.4.2.1) → (1.4.2.2)). Khi B tính một giá trị  ≡ 0 (mod q) trong thuật toán ký, anh ta nên bỏ nó đi và chọn một số ngẫu nhiên k mới. Ví dụ: Chúng ta chọn q = 101 và p = 78*q + 1 = 7879 và g = 3 là một nguyên tố trong Z7879. Vì vậy , ta có thể tính: α = 378 mod 7879 = 170. Chọn a = 75, do đó: β = αa mod 7879 = 4567. Bây giờ, B muốn ký một bức điện x = 1234, anh ta chọn một số ngẫu nhiên k=50. Vì vậy : k-1 mod 101 = 99. 107
32. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Tiếp đó: = (17050 mod 7879) mod 101 = 2518 mod 101 = 94  = (1234 + 75*94)99 mod 101 = 97. Cặp chữ ký (94, 97) cho bức điện 1234 đƣợc xác thƣcnhƣ sau: -1 = 97-1 mod 101 = 25 e1 = 1234*25 mod 101 = 45 e2 = 94*25 mod 101 = 27 (17045456727 mod 7879) mod 101 = 2518 mod 101 = 94. Kể từ khi DSS đƣợc đề xuất vào năm 1991, đã có nhiều phê bình đƣa ra. Chẳng hạn nhƣ kích cỡ của moduloe p bị cố định 512-bit, điều mà nhiều ngƣời không muốn. Vì vậy, NIST đã thay đổi chuẩn này để có thể thay đổi kích thƣớc moduloe (chiabởi64) thành một dãy từ 512 đến 1024-bit. Ngoài ra, một sự phê bình khác về DSS là chữ ký đƣợc tạo ra nhanh hơn sovới việc xác minh nó. Trái ngƣợc với hệ chữ ký RSA thì việc xác minh công khai là rất nhanh chóng (mà ta biết trong thƣơng mại điện tử việc xác minh là rất quan trọng và đòi hỏithời gian thực hiện phải nhanh chóng). 1.5. Mô hình ƣ́ ng duṇ g củ a chƣ̃ ký điêṇ tƣ̉ Khác với chữ ký thông thƣờ ng trên thƣ̣c tế , các chữ ký điện tử là một thông tin ở dạng số hóa đƣợc tạo ra từ văn bản sử dụng hệ chữ ký điện tử và không phải là một phầ n củ a văn bả n . Do đó sau khi đƣợc taọ ra , chƣ̃ ký điêṇ tƣ̉ sẽ đƣợc gƣ̉ i đi cù ng vớ i thông điêp̣ , ngƣờ i nhâṇ nhâṇ đƣợc thông điêp̣ và chƣ̃ ký tƣơng ƣ́ ng sẽ thƣ̣c hiêṇ thuâṭ toán kiểm tra xem chữ ký có đúng là chữ ký của ngƣời gửi lên văn bản nhận đƣợc hay không. Mô hình ƣ́ ng duṇ g nà y có thể đƣợc minh hoạ qua hình vẽ sau: Khóa công Khóa bí mật khai của B của B Khóa C1 C1 Khóa RSA RSA phiên K phiên K C2 C2 P, S AES AES P, S Khóa bí mật Khóa công của A khai của B Kiểm tra P Ký S P chữ ký A - ngƣời gửi B - ngƣời nhận Hình 5.1: Mô hình ƣ́ ng duṇ g củ a chƣ̃ ký điêṇ tƣ̉ 108
33. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm 2. Hàm Băm (Hash Function) 2.1. Khái niệm Ta thấy rằng các hệ chữ ký đƣợc miêu tả ở trên chỉ cho phép ký các bức điện ngắn. Ví dụ nhƣ trong DSS, 160-bit bức điện đƣợc ký với 320-bit. Nhƣ vậy với những bức điện hàng Megabyte thì chúng ta phải làm thế nào! Một cách đơn giản để giải quyết vấn đề này là chia bức điện lớn thành nhữngđoạn nhỏ 160-bit, và sau đó ký lên mỗi đoạn nhỏ đó, điều này cũng tƣơng tự nhƣ mã hoá một chuỗi dài bản rõ bằng việc mã hoá từng ký tự bản rõ sử dụng cùng mộtkhoá. Nhƣng có một vài vấn đề trong việc tạo chữ ký điện tử. Đầu tiên là với một bứcđiện dài, chúng ta sẽ kết thúc với một lƣợng chữ ký khổng lồ. Ngoài ra, điều bất tiện là hầu hết các hệ chữ ký đều rất chậm. Nghiêm trọng hơn là với rất nhiều đoạn đƣợc ký nhƣvậysẽ dẫn đến khi sắp xếp lại và có thể một vài đoạn bị bỏ đi (mất đi tính toànvẹn). Để giải quyết tất cả các rắc rốinày, ngƣời ta sử dụng hàm Băm (hash function). Định nghĩa: Một hàm Băm H sẽ lấy ở đầu vào một thông tin X có kích thƣớc biến thiên vàsinh kết quả là một chuỗi có độ dài cố định, đƣợc gọi là cốt của bức điện (message digest). Ví dụ nhƣ khi B muốn ký một bức điện x (độ dài bất kỳ), đầu tiên anh ta tính cốt của bức điện z = h(x) (độ dài cố định) và sau đó ký y=sigK(z). Anh ta phát cặp (x,y) lên kênh truyền, bây giờ việc kiểm tra có thể thực hiện bằng việc tính lại cốt của bức điện z=h(x), sau đó kiểm tra verK(z,y) có bằng TRUE hay không. x z = h(x) y = sigK(z) x.y verK(y) 0: true x.y 1: false z = h(x) Hình 5.2: Sơ đồ chữ ký sử dụng hàm Băm 2.2. Đặc tính của hàm Băm Một vấn đề cần bàn ở đây là tính đụng độ của hàm Băm. Theo nguyên lý Diricle: nếu có n+1 con thỏ được bỏ vào n cái chuồng thì phải tồn tại ít nhất một cái chuồng mà trong đó có ít nhất là hai con thỏ ở chung [9]. Rõ ràng với không gian giá trị Băm nhỏ hơn rất nhiều so với không gian tin về mặt kích thƣớc thì chắc chắn sẽ tồn tại đụng độ, nghĩa là có hai tin x x‟ mà giá trị Băm của chúng là giống nhau, tức h(x) = h(x‟). Sau đây chúng ta sẽ xét các dạng tấn công có thể có, từ đó rút ra các tính chất của hàm Băm: 109
34. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Dạng tấn công thứ nhất là ngƣời C bắt đầu với một bức điện đƣợc ký có giátrị(x, y), trong đó y = sigK(h(x)) (cặp (x, y) có thể là bất kỳ bức điện trƣớc đó mà B đãký).Sau đó, C tính z = h(x) và cố gắng tìm x‟ x để h(x‟) = h(x). Nếu C làm đƣợc điều này thì cặp (x‟, y) sẽ là một bức điện đƣợc ký có giá trị (một bức điện giả mạo có giátrị).Để ngăn cản việc này, hàm Băm h phải thoả mãn tính chất sau: Tính chất 1: Một hàm Băm h có tính phi đụng độ cao khi với một bức điện x cho trước , không tìm ra một bức điện x’ x sao cho h(x’) = h(x). [5] Một dạng tấn công khác mà ngƣời C có thể làm là:đầu tiên anh ta tìm 2 bức điện x x‟ sao cho h(x) = h(x‟). Sau đó C đƣa bức điện x cho B và thuyết phục B ký vào cốt bức điện h(x); và vì vậy, anh ta tìm đƣợc y. Nhƣ vậy, cặp (x‟, y) là một cặp chữ ký giả cógiá trị. Điều này là nguyên nhân mà việc thiết kế hàm Băm phải thoả mãn tính chất 2nhƣ sau: Tính chất 2: Một hàm Băm h có tính đụng độ cao khi không thể tìm ra những bức điện x và x’ sao cho x’ x và h(x’) = h(x). [5] Dạng tấn công thứ 3 là chọn một giá trị cốt z ngẫu nhiên. Ngƣời C sẽ tính mộtchữ ký với một giá trị ngẫu nhiên z, sau đó anh ta tìm một bức điện x sao cho z = h(x). Nếu anh ta làm đƣợc điều này thì cặp (x, y) là cặp chữ ký giả có giá trị. Nhƣ vậy một tínhchất nữa mà h cần thoả mãn là tính một chiều: Tính chất 3: Một hàm Băm h có tính một chiều khi với cốt của một bức điện z cho trước không thể tìm được một bức điện x sao cho h(x) = z. [5] 2.3. Birthday attack Nhƣ đã biết, một dạng tấn công có khả năng đối với các hệ chữ ký điện tửcódùng hàm Băm là tìm cách tạo ra những văn bản x và x‟có nội dung khác nhau (một có lợi và một là bất lợi cho bên ký) mà giá trị Băm giống nhau. Kẻ địch có thể tìm cách tạoramột số lƣợng rất lớn các văn bản có nội dung không thay đổi nhƣng khác nhau về biểu diễn nhị phân (đơn giản là việc thêm bớt khoảng trắng hay dùng nhiều từ đồng nghĩa để thay thế ), sau đó sử dụng một chƣơng trình máy tính để tính giá trị Băm của các văn bảnđó và đem so sánh với nhau để hi vọng tìm ra một cặp văn bản đụng độ (sử dụng phƣơng pháp thống kê). Nhƣng việc này đòi hỏi số văn bản cần đƣợc tính giá trị Băm phải lớn hơnkích thƣớc không gian Băm rất nhiều. Chẳng hạn nhƣ nếu hàm Băm có không gian Băm 64- bit thì số lƣợng văn bản cần đƣợc đem ra nạp vào chƣơng trình phải ít nhất264 (với một máy tính có thể thực hiện việc Băm 1triệu bức điện trong 1 giây, thì phải mất 6000.000 năm tính toán [6]) Tuy nhiên nếu kẻ địch thử với lƣợng văn bản ít hơn nhiều, trong phạm vi có thể tính đƣợc thì xác suất để tìm đƣợc đụng độ sẽ nhƣ thế nào? Câu trả lời là “có thể thựchiện đƣợc”. Bản chất của hiện tƣợng này đƣợc minh hoạ rõ thông qua phát biểu sau, thƣờng đƣợc gọi là nghịch lý ngày sinh (birthday paradox): 110
35. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Trong một nhóm có 23 người bất kỳ , xác suất để có hai người có cùng ngày sinh nhật ít nhất là ½.[5] Một cách tổng quát, giả sử một hàm Băm có n giá trị Băm khác nhau, nếu chúng ta có k giá trị Băm từ k thông tin khác nhau đƣợc chọn ngẫu nhiên, thì xác suất để không xảy ra đụng độ là: 1 2 k 1 k 1 i (1- )(1- ) (1- ) =  (1 ) . n n n i 1 n i k 1 i k 1 i k(k 1) Với 1 , thì  (1 ) e n e 2n . Do đó, xác suất để xảy ra đụng độ ít n i 1 n i 1 k (k 1) nhất là 1 e 2n . Giả sử gọi xác suất trên là  ta có : kk( 1) 2n 1 e  (*) 2 1 1 Suy ra : k k2 n log , suy ra: kn 2 log ( ) 1  1  1 Theo công thƣc ( ) này khi giá trị e rất gần với 1 thì log vẫn kha nho nên k la ́ 1  ́ ̉ ̀ tỉ lệ với n . Vớ i ε = 0.5 ta có k≈1.1774 ( ). Ví dụ: Vớ i k = 23 là số ngƣời, n = 365 là số ngày trong năm thì xác xuất tồn tại hai ngƣời có cùng sinh nhật sẽ là  = 1 – 2,7-0,7 0,5075. Và đây chính là nghịch lý ngày sinh đã phát biểu ở trên. Hoăc̣ chú ng ta có thể thay n = 365 vào công thức ( ) sẽ nhận đƣợc k = 22.49 ≈23. Nghịch lý ngày sinh hay công thƣ́ c (*) cho phé p chú ng ta dƣ̣ đoá n đƣợc chăṇ dƣớ i của số lƣợng phép thử cần thực hiêṇ để tìm ra đuṇ g đô ̣ củ a môṭ hà m băm . Môṭ hà m băm 20 40-bit sẽ là không an toà n vì chi ̉ cầ n thƣ̉ 2 (khoảng 1 tỉ) phép thử chúng ta đã có xác suấ t đuṇ g đô ̣ là 50%. Tƣơng tƣ̣, với một hàm Băm có không gian Băm 64-bit nêu trên thì số phé p thƣ̉ để có xác suất đụng độ là 50% sẽ là 232, điều này là có khả năng thức hiện đƣợc. Ví dụ với loại máy tính nêu trên chỉ mất khoảng 1 giờ tính toán. Hàm băm đƣợc coi là an toàn là các hàm băm 128 bit (nhƣ MD5 ) vì khi đó s ố 64 lƣợng phé p thƣ̉ sẽ là 2 . Tuy nhiên hiêṇ nay vớ i sƣ̣ phá t triể n củ a cá c thuâṭ toá n thá m mã hàm băm mới đƣợc phát hiện các hàm băm 128 cũng đƣợc khuyến nghị là không nên sƣ̉ duṇ g trong cá c hê ̣ thố ng bả o mâṭ mớ i . Các hàm băm đƣợc khuyế n nghi ̣thay thế cho MD5 là các hàm băm 164 bit nhƣ DSS, SHA2. 2.4. Một số hàm Băm nổi tiếng 2.4.1. MD5 (Message Digest) Ronald Rivest là ngƣời đã phát minh ra các hàm Băm MD2, MD4 (1990) và MD5 (1991). Do tính chất tƣơng tự của các hàm Băm này, sau đây chú ng ta sẽ xem xé t hàm 111
36. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Băm MD5, đây là một cải tiến của MD4 và là hàm Băm đƣợc sử dung rộngrãinhất, nguyên tắ c thiế t kế củ a hà m băm nà y cũng là nguyên tắ c chung cho rấ t nhiề u cá c hà m băm khá c. a. Miêu tả MD5: Đầu vào là những khối 512-bit, đƣợc chia cho 16 khối con -32 bit. Đầu ra của thuật toán là một thiết lập của 4 khối 32-bit để tạo thành một hàm Băm 128-bit duy nhất. Đầu tiên, ta chia bức điện thành các khối 512-bit, với khối cuối cùng (đặt là x và x< 512-bit) của bức điện, chúng ta cộng thêm một bit 1 vào cuối của x, theo sau đó là cácbit 0 để đƣợc độ dài cần thiết (512 bit). Kết quả là bức điện vào là một chuỗi Mcóđộdài chia hết cho 512; vì vậy ta có thể chia M ra thành các N word 32-bit (N word này sẽ chia hết cho 16). Bây giờ, ta bắt đầu tìm cốt của bức điện với 4 khối32-bit A, B, C và D (đƣợc xem nhƣ thanh ghi) : A = 0x01234567 B = 0x89abcdef C = 0xfedcba98 D = 0x76543210. ngƣời ta thƣờng gọi A, B, C, D là các chuỗi biến số (chaining variables). Bức điện đƣợc chia ra thành nhiều khối 512-bit, mỗi khối 512-bit lại đƣợc chia ra 16 khối 32-bit đi vào bốn vòng lặp của MD5. Giả sử ta đặt a, b, c và d thay cho A, B, C vàD đối với khối 512-bit đầu tiên của bức điện. Bốn vòng lặp trong MD5 đều có cấu trúc giống nhau. Mỗi vòng thực hiện 16 lần biến đổi: thực hiện với một hàm phi tuyến của 3trong4 giá trị a, b, c và d; sau đó nó cộng kết quả đến giá trị thứ 4, tiếp đó cộng với một khốicon 32-bit và một hằng số. Sau đó, nó dịch trái một lƣợng bit thay đổi vàcộng kết quả vào một trong 4 giá trị a, b, c hay d. Kết quả cuối cùng là một giá trị mới đƣợc thay thếmột trong 4 giá trị a, b, c hay d. Khối của bức điện A A B Vòng Vòng Vòng Vòng B C 1 2 3 4 C D D Hình 5.3: Sơ đồ vòng lặp chính của MD5 112
37. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm M t a j i b Hàm phi c <<< s tuyến d Hình 5.4: Sơ đồ một vòng lặp MD5 Có bốn hàm phi tuyến, mỗi hàm này đƣợc sử dụng cho mỗi vòng: F(X,Y,Z ) = (X  Y)  ((X)  Z) G(X,Y,Z ) = ((X  Z)  (Y  (Z))) H(X,Y,Z ) = X  Y  Z I(X,Y,Z ) = Y  (X  (Z)). trong đó:  là XOR,  là AND,  là OR, và  là NOT. Những hàm này đƣợc thiết kế sao cho các bit tƣơng ứng của X, Y và Z là độclập và không ƣu tiên, và mỗi bit của kết quả cũng độc lập và ngang bằng nhau. Nếu jM là một biểu diễn của khối con thứ j (j = 16) và <<<slà phép dịch trái của s bit, thì các vòng lặp có thể biểu diễn nhƣ sau: FF(a,b,c,d,Mj,s,ti) đƣợc biểu diễn a = b + ((a + F(b,c,d) j+ M + ti) <<< s) GG(a,b,c,d,Mj,s,ti) đƣợc biểu diễn a = b + ((a + G(b,c,d) j+ M + ti) <<< s) HH(a,b,c,d,Mj,s,ti) đƣợc biểu diễn a = b + ((a + H(b,c,d) + jM + ti) <<< s) II(a,b,c,d,Mj,s,ti) đƣợc biểu diễn a = b + ((a + I(b,c,d) j+ M + ti) <<< s). Bốn vòng (64 bƣớc) sẽ thực hiện nhƣ sau: Vòng 1: FF (a, b, c, d, M0, 7, 0x76aa478) FF (d, a, b, c, M1, 12, 0xe8c7b756) FF (c, d, a, b, M2, 17, 0x242070db) FF (b, c, d, a, M3, 22, 0xc1bdceee) FF (a, b, c, d, M4, 7, 0xf57c0faf) FF (d, a, b, c, M5, 12, 0x4787c62a) FF (c, d, a, b, M6, 17, 0xa8304613) FF (b, c, d, a, M7, 22, 0xfd469501) FF (a, b, c, d, M8, 7, 0x698098d8) FF (d, a, b, c, M9, 12, 0x8b44f7af) 113
38. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm FF (c, d, a, b, M10, 17, 0xffff5bb1) FF (b, c, d, a, M11, 22, 0x895cd7be) FF (a, b, c, d, M12, 7, 0x6b901122) FF (d, a, b, c, M13, 12, 0xfd987193) FF (c, d, a, b, M14, 17, 0xa679438e) FF (b, c, d, a, M15, 22, 0x49b40821). Vòng 2: GG (a, b, c, d, M1, 5, 0x61e2562) GG (d, a, b, c, M6, 9, 0xc040b340) GG (c, d, a, b, M11, 14, 0x265e5a51) GG (b, c, d, a, M0, 20, 0xe9b6c7aa) GG (a, b, c, d, M5, 5, 0xd62f105d) GG (d, a, b, c, M10, 9, 0x02441453) GG (c, d, a, b, M15, 14, 0xd8a1e681) GG (b, c, d, a, M4, 20, 0xe7d3fbc8) GG (a, b, c, d, M9, 5, 0x21e1cde6) GG (d, a, b, c, M14, 9, 0xc33707d6) GG (c, d, a, b, M3, 14, 0xf4d50d87) GG (b, c, d, a, M8, 20, 0x455a14ed) GG (a, b, c, d, M13, 5, 0xa9e3e905) GG (d, a, b, c, M2, 9, 0xfcefa3f8) GG (c, d, a, b, M7, 14, 0x676f02d9) GG (b, c, d, a, M12, 20, 0x8d2a4c8a). Vòng 3: HH (a, b, c, d, M5, 4, 0xfffa3942) HH (d, a, b, c, M8, 11, 0x8771f681) HH (c, d, a, b, M11, 16, 0x6d9d6122) HH (b, c, d, a, M14, 23, 0xfde5380c) HH (a, b, c, d, M1, 4, 0xa4beea44) HH (d, a, b, c, M4, 11, 0x4bdecfa9) HH (c, d, a, b, M7, 16, 0xf6bb4b60) HH (b, c, d, a, M10, 23, 0xbebfbc70) HH (a, b, c, d, M13, 4, 0x289b7ec6) HH (d, a, b, c, M0, 11, 0xeaa127fa) HH (c, d, a, b, M3, 16, 0xd4ef3085) HH (b, c, d, a, M6, 23, 0x04881d05) HH (a, b, c, d, M9, 4, 0xd9d4d039) HH (d, a, b, c, M12, 11, 0xe6db99e5) HH (c, d, a, b, M15, 16, 0x1fa27cf8) HH (b, c, d, a, M2, 23, 0xc4ac5665). Vòng 4: II (a, b, c, d, M0, 6, 0xf4292244) II (d, a, b, c, M7, 10, 0x432aff97) 114
39. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm II (c, d, a, b, M14, 15, 0xab9423a7) II (b, c, d, a, M5, 21, 0xfc93a039) II (a, b, c, d, M12, 6, 0x655b59c3) II (d, a, b, c, M3, 10, 0x8f0ccc92) II (c, d, a, b, M10, 15, 0xffeff47d) II (b, c, d, a, M1, 21, 0x85845dd1) II (a, b, c, d, M8, 6, 0x6fa87e4f) II (d, a, b, c, M15, 10, 0xfe2ce6e0) II (c, d, a, b, M6, 15, 0xa3013414) II (b, c, d, a, M13, 21, 0x4e0811a1) II (a, b, c, d, M4, 6, 0xf7537e82) II (d, a, b, c, M11, 10, 0xbd3af235) II (c, d, a, b, M2, 15, 0x2ad7d2bb) II (b, c, d, a, M9, 21, 0xeb86d391). Những hằng số ti đƣợc chọn theo quy luật sau: ở bƣớc thứ i giá trị ti là phần nguyên của 322 *abs(sin(i)), trong đó i = [0 63] đƣợc tính theo radian. Sau tất cả những bƣớc này a, b, c và d lần lƣợt đƣợc cộng với A, B, C và Dđểcho kết quả đầu ra; và thuật toán tiếp tục với khối dữ liệu512-bit tiếp theo cho đến hết bức điện. Đầu ra cuối cùng là một khối 128-bit của A, B, C và D, đây chính là hàm Băm nhận đƣợc. b. Tính bảo mật trong MD5: Ron Rivest đã phác hoạ những cải tiến của MD5 so với MD4 nhƣ sau: Vòng thứ 4 đƣợc thêm vào (còn MD4 chỉ có 3 vòng). Mỗi bƣớc đƣợc cộng thêm một hằng số duy nhất. Hàm G ở vòng 2 thay đổi từ ((X  Y)  (X  Z)  (Y  Z)) thành ((X  Z)  (Y  (Z))) nhằm giảm tính đối xứng của G (giảm tính tuyến tính). Mỗi bƣớc đƣợc cộng kết quả của bƣớc trƣớc nó, làm cácquátrình có tính liên kết, phụ thuộc lẫn nhau. Việc các khối con bị thay đổi khi vào vòng 2 và vòng 3 làm cho khuôn dạng cấu trúc vòng lặp thay đổi theo. Số lƣợng lƣợng bit dịch trái của mỗi vòng đƣợc tối ƣu và các bƣớc dịch ởmỗi vòng là khác nhau. Năm 1993, den Boer và Bosselaers đã tìm ra đụng độ trong việc sử dụng hàm nén (vòng 2 và 3) của MD5. Điều này phá vỡ quy luật thiết kế MD5 là chống lại sự đụngđộ, nhƣng MD5 vẫn là hàm Băm đƣợc sử dụng rộng rãi hiện nay. 2.4.2. SHA (Secure Hash Algorithm) Năm 1995, tổ chức NIST cùng NSA đã thiết kế ra thuật toán hàm Bămantoàn (SHA) sử dụng cho chuẩn chữ ký điện tử DSS. SHA đƣợc thiết kế dựa trên những nguyên tắc của MD4/MD5, tạo ra -160 bit giá trị Băm. a. Miêu tả SHA: 115
40. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Cũng giống với MD5, bức điện đƣợc cộng thêm một bit 1và các bit 0 ở cuối bức điện để bức điện có thể chia hết cho 512. SHA sử dụng 5 thanh ghi dịch: A = 0x67452301 B = 0xefcdab89 C = 0x98badcfe D = 0x10325476 E = 0xc3d2e1f0 Bức điện đƣợc chia ra thành nhiều khối 512-bit. Ta cũng đặt là a, b, c, d và e thay cho A, B, C, D và E đối với khối- 512 bit đầu tiên của bức điện. SHA có bốn vòng lặp chính với mỗi vòng thực hiện 20 lần biến đổi: bao gồm thực hiện với một hàm phi tuyến của3 trong 5 giá trị a, b, c, d và e; sau đó cũng đƣợc cộng và dịch nhƣ trongMD5. SHA xác lập bốn hàm phi tuyến nhƣ sau: ft(X,Y,Z) = (X  Y)  ((X)  Z) với 0 ≤ t ≤ 19 ft(X,Y,Z) = X  Y  Z với 20 ≤ t ≤ 39 ft(X,Y,Z) = (X  Y)  (X  Z)  (Y  Z) với 40 ≤ t ≤ 59 ft(X,Y,Z) = X  Y  Z với 60 ≤ t ≤ 79. Bốn hằng số sử dụng trong thuật toán là: 1/2 Kt = 2 /4 = 0x5a827999 với 0 ≤ t ≤ 19 1/2 Kt = 3 /4 = 0x6ed9eba1 với 20 ≤ t ≤ 39 1/2 Kt = 5 /4 = 0x8f1bbcdc với 40 ≤ t ≤ 59 1/2 Kt = 10 /4 = 0xca62c1d6 với 60 ≤ t ≤ 79. Các khối bức điện đƣợc mở rộng từ 16 word 32-bit (M0 đến 15M ) thành 80 word 32- bit (W0 đến W79) bằng việc sử dụng thuật toán mở rộng: Wt = Mt với 0 ≤ t ≤ 15 Wt = (Wt-3  Wt-8  Wt-14  Wt-16) với 16 ≤ t ≤ 79. Ta có thể miêu tả một vòng lặp của SHA nhƣ sau: 116
41. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm Wt K t ei-1 ei di-1 di Hàm phi ci-1 tuyến ci bi-1 <<< 30 bi ai-1 <<< 5 ai Hình 5.5: Sơ đồ một vòng lặp của SHA Nếu gọi Wt là biểu diễn của khối con thứ t của bức điện đƣợc mở rộng, và <<<slà biểu diễn dịch trái s bit, thì vòng lặp chính của SHA nhƣ sau: a = A, b = B, c = C, D = D, e = E, for t = 0 to 79 { TEMP = (a <<< 5) + ft(b, c, d) + e +Wt + Kt, e = d, d = c, c = b <<< 30, b = a, a = TEMP, } A = A + a, B = B + b, C = C + c, D = D + d, E = E + e, Thuật toán tiếp tục với khối 512-bit tiếp theo cho tới khi hết bức điện, và kết quả sau cùng trong 4 thanh ghi A, B, C, D và E chính là hàm Băm SHA 160-bit. b. Tính bảo mật trong SHA: Để hiểu rõ hơn về tính bảo mật của SHA, ta hãy so sánh SHA với MD5 để cóthể tìm ra những điểm khác nhau của hai hàm Băm này: MD5 và SHA đều cộng thêm các bit “giả” để tạo thành những khối chia hết cho 512-bit, nhƣng SHA sử dụng cùng một hàm phi tuyến f cho cả bốn vòng. 117
42. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm MD5 sử dụng mỗi hằng số duy nhất cho mỗi bƣớc biến đổi, SHA sử dụng mỗi hằng số cho mỗi vòng biến đổi, hằng số dịch này là một số nguyên tố đối vớiđộ lớn của word (giống với MD4). Trong hàm phi tuyến thứ 2 của MD5 có sự cải tiến so với MD4, SHA thì sử dụng lại hàm phi tuyến của MD4, tức (X Y)  (X  Z)  (Y  Z). Trong MD5 với mỗi bƣớc đƣợc cộng kết quả của bƣớc trƣớc đó. Sự khác biệt đối với SHA là cột thứ 5 đƣợc cộng (không phải b, c hay d nhƣtrong MD5), điều này làm cho phƣơng pháp tấn công của Boer-Bosselaers đối với SHA bị thất bại (den Boer và Bosselaers là hai ngƣời đã phá thành công 2 vòng cuối trong MD4). Cho đến nay, chƣa có một công bố nào đƣợc đƣa ra trong việc tấn công SHA, bởi vì độ dài của hàm Băm SHA là 160-bit, nó có thể chống lại phƣơng pháp tấn công bằng vét cạn (kể cả birthday attack) tốt hơn so với hàm Băm MD5 128-bit. 2.5. Một số ƣ́ ng duṇ g củ a hàm Băm Nhƣ đã trình bà y ở phầ n đầ u chƣơng , ứng dụng chính của các hàm băm là sƣ̉ dụng với các hệ chữ ký điện tử , trong đó thay vì ký trƣ̣c tiế p lên cá c văn bả n , thông điêp̣ (mà trong đa số trƣờng hợp là rất lớn, tố c đô ̣ châṃ ) ngƣờ i ta sẽ ký lên giá tri ̣băm đaị diêṇ cho toà n bô ̣ văn bả n đó . Điề u nà y đăc̣ biêṭ quan troṇ g và hiêụ quả bở i vì chú ng ta biế t rằ ng cá c hê ̣ chƣ̃ ký điêṇ tƣ̉ đề u là m viêc̣ vớ i cá c phé p tính số hoc̣ số lớ n nên bả n thân chúng đã tƣơng đối chậm, viêc̣ sƣ̉ duṇ g giá tri ̣băm thay cho toà n bô ̣ v ăn bả n là giả i phá p toàn diện khắc phục đƣợc yếu điểm này của các hệ chữ ký điện tử . Ngoài việc xử dụng vớ i cá c hê ̣ chƣ̃ ký điêṇ tƣ̉ hà m băm cò n đƣợc sƣ̉ duṇ g và o cá c muc̣ đích khá c nhƣ : xác thƣ̣c hó a thông điêp̣ , xác thƣ̣c hó a ngƣờ i dù ng. Đối với các ứng dụng không cần giữ bí mật thông điệp mà chỉ cần đảm bảo thông điêp̣ không bi ̣thay đổ i trên đƣờ ng truyề n ngƣờ i ta sẽ sƣ̉ duṇ g hà m băm cho muc̣ đích xá c thƣ̣c tính nguyên veṇ củ a thông điệ p đó . Chẳ ng haṇ chú ng ta có môṭ phầ n mề m mã nguồ n mở ở daṇ g setup muố n phân phố i cho ngƣờ i dù ng , rõ ràng việc gửi phần mềm đó tớ i má y tính củ a ngƣờ i dù ng là không cầ n phả i mã hó a , tuy nhiên nế u nhƣ phầ n mề m đó bị thay đổ i trên đƣờ ng truyề n (chẳ ng haṇ nhƣ bi ̣gắ n thêm cá c spyware , virus ) thì sẽ rấ t nguy hiể m . Để đả m bả o chú ng ta sẽ cung cấ p giá tri ̣băm củ a phầ n mề m đó (khi đó phầ n mề m chính là thông điêp̣ ). Ngƣờ i dù ng sẽ download cả ph ần mềm và giá trị băm nhâṇ đƣợc , sau đó tiế n hà nh băm laị , đố i sá nh giá tri ̣băm nhâṇ đƣợc vớ i giá tri ̣băm đƣợc cung cấ p cù ng vớ i phầ n mề m , nế u hai giá tri ̣nà y khớ p nhau thì có thể đả m bả o phầ n mề m không bi ̣sƣ̉ a đổ i trên đƣờ ng truyề n. Hiêṇ nay đa số cá c phầ n mề m mã nguồ n mở đề u đƣợc phân phố i theo cá ch nà y. Trong cá c hê ̣ thố ng yêu cầ u có xá c thƣ̣c ngƣờ i dù ng nhƣ cá c hê ̣ quả n tri ̣cơ sở dƣ̃ liêụ , hê ̣ điề u hà nh , các ứng dụng web , ứng dụng dạng desktop application , để lƣu mật khẩ u ngƣờ i dù ng ngƣờ i ta cũng sƣ̉ duṇ g cá c hà m băm hoăc̣ cá c hê ̣ mã trong cá c vai trò của hàm băm (không sƣ̉ duṇ g khó a ). Khi đó mỗi tà i khoả n củ a ngƣờ i dù ng thay vì lƣu dƣớ i daṇ g tên truy c ập (username) và mật khẩu (password) sẽ đƣợc lƣu dƣới dạng : tên ngƣờ i dù ng, giá trị băm của mật khẩu . Khi môṭ ngƣờ i dù ng đăng nhâp̣ và o hê ̣ thố ng , hê ̣ thố ng sẽ lấ y tên truy câp̣ , mâṭ khẩ u ho ̣ nhâp̣ và o , kiể m tra xem có tên truy câp̣ nà o nhƣ vâỵ hay không . Nế u có sẽ tiế n hà nh băm giá tri ̣mâṭ khẩ u do ngƣờ i dù ng nhâp̣ và o , đố i 118
43. Chƣơng V: Chƣ̃ ký điêṇ tƣ̉ và hà m băm sánh với giá trị băm tƣơng ứng lƣu trong cơ sở dữ liệu (có thể ở dạng file text , xml, hay file cơ sở dƣ̃ liêụ củ a môṭ hê ̣ quả n trị cơ sở dữ liệu nào đó). Nế u kế t quả đố i sá nh là khớ p thì ngƣời dùng đó là hợp lệ , ngƣợc laị nế u không khớ p có nghiã là sai mâṭ khẩ u . Hiêṇ nay tấ t cả cá c hê ̣ quả n tri ̣cơ sở dƣ̃ liêụ đề u đƣợc trang bi ̣cá c hà m băm để cho phép ngƣờ i dù ng taọ ra cá c giá tri ̣băm củ a mâṭ khẩ u ngƣờ i dù ng và lƣu laị cá c giá tri ̣băm nà y. Viêc̣ lƣu cá c giá tri ̣băm đả m bả o chú ng ta không bi ̣lô ̣ mâṭ khẩ u do mâṭ khẩ u đƣợc lƣu ở dạng nguyên bản trên má y tính hoăc̣ khi truyề n qua hê ̣ thố ng maṇ g . Hê ̣ điề u hà nh Unix sƣ̉ duṇ g nguyên tắ c lƣu mâṭ khẩ u nhƣ trên vớ i hà m băm là hê ̣ mã DES đƣợc lăp̣ laị 25 lầ n, mâṭ khẩ u củ a ngƣờ i dù ng đƣợc sƣ̉ duṇ g nhƣ khó a củ a hê ̣ mã, bản rõ đem mã hóa là xâu 64 bit 0. Ngày nay với sự phát triển mạnh mẽ của thƣơng mại điện tử , các giao dịch đều đƣợc thƣ̣c hiêṇ tƣ̀ xa, trên cá c hê ̣ thố ng maṇ g nên viêc̣ ƣ́ ng duṇ g củ a cá c hê ̣ chƣ̃ ký điêṇ tƣ̀ và đi kè m vớ i đó là cá c hà m băm ngà y cà ng trở nên quan troṇ g . Mọi thông tin trong các giao dịch thƣơng mại điện tử đều cần đƣợc bảo vệ bằng các chữ ký , hàm băm. Vì thế có thể nó i rằ ng đôi khi cá c hà m băm cò n quan troṇ g hơn cả cá c hê ̣ mã mâṭ . 3. Bài tập Bài tâp̣ 5.1: Cho hệ chữ ký điện tử ElGamma có p = 1019, a = 191 là một phầntử * nguyên thuỷ của ZP , x = 37. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ chữ ký trên. b) Để ký lên bản rõ M = 102 ngƣời ta chọn k = 143, hãy thực hiện ký đƣa ra chữký tƣơng ứng. c) Kiểm tra xem cặp (K, S) = (251, 507) có là chữ ký lên văn bản M = 127 hay không. Bài tập 5.2: Cho hệ chƣ̃ ký điêṇ tƣ̉ RSA có p = 31, q = 41, e = 271. a) Hãy tìm khóa công khai KP, và khóa bí mật KS của hệ mã trên. b) Hãy tính chữ ký cho thông điêp̣ M = 100. Bài tập 5.3: Cho thuâṭ toá n chƣ̃ ký điêṇ tƣ̉ DSA có q = 11, p = 67, α = 9, β = 62, khóa bí mâṭ a = 4, để ký lên văn bản M = 8, ngƣờ i ta choṇ k = 2. Hãy xác định chữ ký lên văn bản M. Bài tập 5.4: Cho hê ̣ chƣ̃ ký điệ n tƣ̉ RSA có p = 47, q = 71, e= 79. Hãy xác định chữ ký của hệ mã lên thông điệp M = 688. Sƣ̉ duṇ g môṭ trong cá c ngôn ngƣ̃ lâp̣ trình C, C++, Java hoăc̣ C# để làm các bài tập sau: Bài tập 5.5: Cài đặt hệ chữ ký điện tử RSA. Bài tâp̣ 5.6: Cài đặt hệ chữ ký điện tử El Gammal. Bài tập 5.7: Cài đặt hàm băm MD5. Bài tập 5.8: Cài đặt hàm băm SHA. Gợi ý : Có thể sử dụng các thƣ viện số lớn nhƣ MIRACL hoăc̣ cá c thƣ viêṇ mã nguồ n mở nhƣ Crypto++ (chi tiế t tại địa chỉ website: Cryptolib ( chi tiế t taị điạ chi ̉ website 119
44. Chƣơng VI: Quản lý khóa CHƢƠNG VI: QUẢN LÝ KHÓA 1. Quản lý khoá trong các mạng truyền tin Trong các chƣơng trƣớc, ta đã làm quen với các phƣơng pháp lập mã và cácbài toán quan trọng khác liên quan đến việc truyền tin bảo mật trên các mạng truyền tin công cộng nói chung. Ta cũng đã thấy rằng các hệ mật mã khoá công khaicông khai có nhiều ƣu việt hơn các hệ mật mã đối xứng trong việc làm nền tảng cho các giải pháp antoàn thông tin, và đặc biệt đối với các hệ mã khoá đối xứng thì việc thực hiện đồi hỏinhững kênh bí mật để chuyển khoá hoặc trao đổi khoá giữa các đối tác,thì về nguyên tắc, đối với các hệ mã hoá với khoá công khai không cần có những kênh bí mật nhƣ vậy, vìcác khoá công khai có thể đƣợc truyền hay trao đổi cho nhau một cách công khai qua các kênh truyền tin công cộng. Tuy nhiên, trên thực tế, để bảo đảm chocác hoạt động thông tin đƣợc thật sự an toàn, không phải bất cứ thông tin nào về các khoá công khai củamột hệ mã, của một thuật toán kiểm tra chữ ký, của một giao thức xác nhận thông báohay xác nhận danh tính cũng phát công khai một cách tràn lan trênmạng công cộng, mặc dù là công khai nhƣng ngƣời ta cũng muốn là những ai cần biết thì mới nên biết mà thôi. Do đó, mặc dù sử dụng các hệ có khoá công khai, ngƣời ta cũng muốn có những giao thức thực hiện việc trao đổi khoá giữa các đối tác thực sự cónhucầu giao lƣu thông tin với nhau, kể cả trao đổi khoá công khai. Việc trao đổi khoá giữa các chủ thể trongmột cộng đồng nào đó có thể đƣợc thiết lập một cách tự do giữa bất cứ hai ngƣời nàokhicó nhu cầu trao đổi thông tin, hoặc có thể đƣợc thiết lập mộtcách tƣơng đối lâu dài trong thời gian nào đó trong cả cộng đồng với sự điều phối của một cơ quan đƣợc uỷ thácTA. Việc trao đổi khoá trong trƣờng hợp thứ nhất ta gọi đơn giản là thoả thuận khoá,còn trong trƣờng hợp thứ hai ta gọi là phân phối khoá; TA lànơi thực hiện việc phân phối, cũng là nơi quản lý khoá. Việc thoả thuận khoá nói chung không cần có sự tham giacủa một TA nào và chỉ có thể xảy ra khi các hệ bảo mật mà ta sử dụng là hệ có khoácông khai, còn việc phân phối khoá thì có thể xảy ra đối vớicác trƣờng hợp sử dụng các hệ khoá đối xứng cũng nhƣ các hệ có khoá công khai. Việc phân phối khoá với vai tròquản trị khoá của một TA là một việc bình thƣờng, đã tồn tại rất lâu trƣớc khi có các hệmậtmã khoá công khai . Ta sẽ bắt đầu vớ i một vài hệ phân phối khoá nhƣ vậy, sau đó sẽ giới thiệu một số hệ phân phối hoặc trao đổi khoá khi dùng các sơ đồ an toàn và bảo mậtvới khoá công khai. 2. Một số hệ phân phối khoá 2.1. Sơ đồ phân phối khoá Blom Giả sử ta có một mạng gồm có n ngƣời dùng và mỗi ngƣời dùng đó đều có nhu cầu trao đổi thông tin bí mật với mọi ngƣời trong mạng. Giả sử sơ đồ mật mã đƣợc sửdụng là một sơ đồ mật mã khoá đối xứng (chẳng hạn nhƣ DES). Toàn bộ mạngcầncó n(n 1) khoá khác nhau cho chừng ấy cặp ngƣời dùng khácnhau trong mạng. Một cơ 2 quan uỷ thác TA quản lý chừng ấy khoá và phải chuyển cho mỗi ngƣời dùng(n-1) khoá chung với (n-1) ngƣời còn lại trong mạng; nhƣ vậy TA phải truyền bằng những kênh bí mật tất cả là n(n-1) lƣợt khoá đến tất cả n ngƣời dùng. 120
45. Chƣơng VI: Quản lý khóa Năm 1985, Blom đề nghi ̣môṭ sơ đồ phân phố i khoá , mà sau đây ta gọi là sơ đồ Blom, trong trƣờ ng hợp đơn giả n nhấ t đƣợc mô tả nhƣ sau: TA chọn một số nguyên tố p ≥ n, và chọn cho mỗi ngƣời dùng Amộtsố rA Z p . Số p và các số rA đƣợc công bố công khai. Sau đó, TA chọn ba số ngẫu nhiên a, b, c Z p và lập đa thức: f (x, y) a b(x y) cxy mod p Với mỗi ngƣời dùng A, TA tính g A (x) f (x,rA ) aA bA x mod p , trong đó aA a brA mod p , bA b crA mod p . TA chuyển bí mật cặp số (aA, bA) cho A. Nhƣ vậy, A biết g A (x) aA bA x . So với việc TA phải truyền bí mật n(n-1) lƣợt khoá trên thì với sơ đồ Blom, TA chỉ phải truyền n lƣợt các cặp số (aA, bA) mà thôi. Sau khi đã thực hiện xong các công việc chuẩn bị đó, bây giờ nếu hai ngƣời dùng A và B muốn tạo khoá chung để truyền tin bằng mật mã cho nhau thì khoá chungKA,B đó sẽ là: K A,B g A (rB ) g B (rA ) f (rA ,rB ), mà mỗi ngƣời A và B tính đƣợc bằng những thông tin mình đã có. Nhƣ vậy, theo sơ đồ phân phối này, TA phân phối cho mọi ngƣời dùng một phần bí mật của khoá, hai ngƣời dùng bất kỳ phối hợp phần bí mật của riêng mình với phầncông khai của ngƣời kia để cùng tạo nên khoá bí mật chung cho hai ngƣời. Sơ đồ này làan toàn theo nghĩa sau đây: bất kỳ một ngƣời thức ba C nào (kể cả C là một ngƣời tham gia trong mạng) có thể đƣợc phát hiện đƣợc khoá bí mật riêng của hai ngƣời A và B.Thực vậy, dù C có là ngƣời tham gia trong mạng đi nữa, thì cái mà C biết nhiều lắm là haisố aC, bC do TA cấp cho. Ta chứng minh rằng với những gì mà C biết thì bất kỳ giá trị  Z p nào cũng có thể đƣợc chấp nhận làKA,B. Những gì mà C biết , kể cả chấp nhận  K A,B , đƣợc thể hiện thành: a b(rA rB ) crArB  a brC aC b crC bC Nếu xem a, b, c là ẩn số, ta cóđịnh thức các hệ số ở vế phải là: 1 rA rB rArB 1 rC 0 (rC rA )(rC rB ), 0 1 rC Theo giả thiết chọn các số r, định thức đó khác 0, do đó hệ phƣơng trình luôncó nghiệm (a, b, c), tức việc chấp nhận  là giá trị của KA,B là hoàn toàn có thể. Bất kỳ giá trị 121