Giáo trình Đại số hiện đại - Chương 12: Điều khiển khóa và giao thức mật mã

Chương 12
ĐIỀU KHIỂN KHÓA VÀ GIAO THỨC MẬT MÃ
Điều khiển khóa
Tổng quan về điều khiển khóa
Cơ chế mật mã đảm bảo hiệu quả bảo mật thông tin với điều kiện giải quyết được bài toán về điều khiển khóa. Chúng ta thấy, trong hệ mật mã cần phải sử dụng khóa mật (ngoại trừ hàm băm). Chiều dài khóa thì phải đủ lớn, và bản thân khóa cũng phải được chọn lựa ngẫu nhiên và phân bố đều từ không gian khóa. Nếu đảm bảo được điều kiện này thì sẽ tránh được tấn công đơn giản nhất, như trên cơ sở dự đoán khóa mật hay trên cơ sở véc cạn khóa. Khi mà chiều dài khóa không đủ lớn thì hệ mật dù có phức tạp đến đâu cũng không thể đảm bảo được độ an toàn cao. Sử dụng thuật toán mật mã an toàn là điều cần thiết, nhưng chưa đủ để đảm bảo độ an toàn cao của hệ mật.
Thông thường thì thám mã thường tấn công lên hệ thống khóa hơn là tấn công trực tiếp lên thuật toán của hệ mật. Cho nên điều khiển hệ thống khóa là một thành phần quan trọng xác định được độ an toàn của hệ mật sử dụng.
Điều khiển khóa trong hệ mật gồm các chức năng sau:
Tạo ra khóa mật mã;
Phân phối và chứng thực khóa mật;
Chứng thực khóa công cộng;
Sử dụng khóa;
Bảo quản khóa;
Thay thế khóa;
Hủy khóa;
Xóa khóa;
Một trong các chức năng (bài toán) trên phải được giải quyết hiệu quả trên tất cả các giai đoạn của chu kỳ sống khóa. Thời gian sống của khóa được chia ra làm 2 loại: Dài hạn và ngắn hạn. Điều khiển khóa có các mục đích sau:
Ngăn chặn được việc sử dụng khóa mật và khóa công khai bất hợp pháp.
Chống lại mối đe dọa tổn hại đến khóa mật và tổn hại đến chứng thực khóa công khai và khóa mật.
Tạo khóa. Việc tạo khóa cho hệ mật bất đối xứng được thực hiện sao cho đảm bảo được các tính chất của toán học và đồng thời khóa phải được lựa chọn ngẫu nhiên từ tập hợp khóa rất lớn, tập hợp này cũng có những tính chất toán học xác định (chú ý rằng trong một số hệ mật bất đối xứng quá trình lựa chọn khóa có thể chọn ngẫu nhiên và phân bố đều trên cơ sở tập hợp khóa có thể, tức là không có mốt sự tính toán nào về tính chất toán học, mặc dầu trong hệ mật bất đối xứng sử dụng các tham số, mà các tham số này cần có những tính chất toán học nhất định). Chất lượng khóa mật trong hệ mật đối xứng là dãy bít ngẫu nhiên với chiều dài khóa cho trước mà không cần tính toán bất kỳ một tính chất toán học nào. Nguyên tắc cơ bản để tạo khóa là lựa chọn đều trên toàn bộ không gian khóa (tập hợp có thể của khóa). Việc tạo khóa có chất lượng có thể sử dụng một trong các phương pháp sau: 1) Sử dụng chương trình với việc ứng dụng thuật toán biến đổi ngẫu nhiên ; 2) Sử dụng thiết bị điện tử với sự hộ trợ bộ cảm biến nhiễu.
Phân bố khóa mật mã dựa trên các quy tắt đặc biệt và sơ đồ. Khi thực hiện bài toán này sử dụng kênh mật, các thuật toán mật mã bảo vệ thông tin khóa (mật mã khóa) và các giao thức chuyển khóa theo kênh mở.
Chứng thực khóa. Dù khóa mật hay khóa công khai, hệ mật trước khi bắt đầu hoạt động thì các khóa này phải được chứng nhận, tức là xác định được ai là chủ của khóa. 
Sử dụng khóa- tức là ứng dụng khóa đối với việc thực hiện hệ mật cụ thể với mục đích bảo vệ và/hoặc chứng nhận thông tin, cũng như xác thực chữ ký của người dùng.
Bảo quản khóa. Việc bảo quản khóa được thực hiện mà không dùng phương pháp mật mã, tuy nhiên có thể dùng phương pháp mã hóa như cơ chế phụ bảo vệ khóa. Khóa mật cần lưu trong thiết bị dưới dạng mật mã để tránh trường hợp đọc và sao chép. Không chỉ lưu khóa dưới dạng bản mã mà những thông tin của khóa cũng như thông tin người sử dụng khóa cũng nên lưu dưới dạng mật mã.
Thay thế khóa – việc thay thế khóa thực hiện sau khi thời hạn hoạt động của khóa kết thúc. Ví dụ, khóa phiên được thay thế sau khi kết thúc phiên giao dịch. Mỗi khóa nên có một chu kỳ nhất định, tránh trường hợp thám mã đã tìm ra được khóa mà vô tình ta không biết. Thay thế khóa liên quan đến việc bảo đảm xóa khóa cũ và thực hiện mã với khóa mới.
Hủy bỏ khóa – Đây là quá trình ngừng hoạt động của khóa, trong trường hợp khóa bị tấn công trong khi khóa vẫn còn thời hạn hoạt động. Khi hủy bỏ khóa công khai thì cần phải thông báo cho các thành viên hệ mật.
Xóa khóa- Việc xóa khóa cần đảm được không thể khôi phục thông tin khóa với bất kỳ vật lưu nào và không thể bị đánh cắp trong quá trình xóa.
Sơ đồ tạo khóa chuẩn ANSI X9.17
Sơ đồ chuẩn ANSI dùng để tạo ra số ngẫu nhiên, trên cơ sở ứng dụng thuật toán mật mã. Sơ đồ được miêu tả trên hình 12.1, ở đây E là mà thuật toán mã hóa DES, K là khóa khởi tạo hay còn gọi là khóa châm ngòi, V0 là giá trị khởi tạo mật, Ti là data time, Ri là khóa phiên. Và rõ ràng ở đây ta có thể chọn bất kỳ một thuật toán mã khối nào khác vị dụ như chuẩn mã Liên Xô, Blowfish hay AES. Thứ tự khóa phiên được hình thành tương ứng với phương trình sau:
.
Giá trị mới của Vi+1 được xác định như sau:
Hình 12.1. Sơ đồ tạo khóa chuẩn ANSI X9.17
Có thể tạo V0 như sau. Chọn Vi là một giá trị khởi tạo nào đó, ví dụ Vi=Ti+j, j là số nào đó. Thực hiện quá trình tạo khóa như trên và ta thu được Vi+1, và ta chọn V0=Vi+1. Và để nâng cao tính an toàn, chúng ta có thể sử dụng các khoá tham gia vào hàm mã hóa là khác nhau.
Sơ đồ phân phối khóa
Chúng ta đã tìm hiểu về mã hóa đối xứng và bất đối xứng. Việc dùng mật mã bất đối xứng thì không cần đến sự trao đổi khóa mật, khắc phục được nhược điểm của mã đối xứng, thế nhưng mã khóa bất đối xứng lại có nhược điểm là tốc độ chậm rất nhiều lần so với mã đối xứng. Ngoài ra khi sử dụng khóa cũng cần phải chứng thực khóa này là của ai để tránh trường hợp kẻ giả danh. Bởi vậy nếu như có một phương pháp trao đổi khóa mật hiệu quả thì sẽ khắc phục được nhược điểm của mât mã đối xứng. Và chương này chúng ta tìm hiểu các vấn đề này.
Để trao đổi khóa giữa các bên có thể trao đổi khóa trực tiếp qua kênh mật, hoặc dùng giao thức thỏa thuận khóa hoặc sơ đồ phân phối khóa.
Chúng ta phân biệt giữa sơ đồ phân phối khóa và giao thức thỏa thuận khóa. Sơ đồ phân phối là cấu trúc tổ chức hệ thống điều khiển khóa, còn giao thức là tổ hợp các thao tác (lệnh) giữa hai hay nhiều bên tham gia, nhằm đảm bảo giữa họ hình thành khóa mật chung. Chúng ta thấy với giao thức phân phối khóa thì khóa được trao đổi trực tiếp giữa hai hay nhiều bên tham gia. Còn dùng sơ đồ thì thông qua trung tâm phân phối khóa.
Trong phân lớn người dùng hệ mật đối xứng thường thì họ thường trao đổi bằng sử dụng trung tâm phân phối khóa tin cậy. Còn đa số người sử dụng hệ mật bất đối xứng họ thực hiện phân phối khóa nhờ đến trung tâm chứng thực khóa.
Trung tâm phân phối khóa
Bài toán phân phối khóa là cực kỳ quan trọng. Bây giờ chúng ta đi tìm hiểu một số phương pháp phân phối hiệu quả.
Giả sử trong một sơ đồ đơn giản hai bên liên hệ với nhau, mỗi phiên giao dịch có thể sử dụng một khóa. Nếu như hệ thống mật mã có N thành viên trong mạng thì cần phải phân bố khóa giữa các thành viên sử dụng ít nhất là N(N-1)/2 khóa. Khi mà số lượng N thành viên lớn thì đây trở nên bài toán nan giải. Để giải quyết vấn đề này người ta đưa ra hàng loạt giải pháp, mà một trong các giải pháp phức tạp nhất và tốn tiền nhất là dùng kênh mật. 
Hình 12.2. Sơ đồ phân phối khóa của Trung tâm
Một trong các phương án được đưa ra là dùng trung tâm phân phối khóa, đây là một phần chung của mạng. Trung tâm phân phối cung cấp cho tất cả các thành viên các khóa mật khác nhau Ki (i=1,2,,N), các thành viên sử dụng khóa này chỉ liên lạc với trung tâm mà thôi. Khóa mật chung giữa hai bên i và j được thực hiện như sau (hình 12.2). Bên Ai muốn liên kết với bên Aj, thì Ai chuyển đến trung tâm khóa liên hệ của minh là kij, khóa này được mã hóa bằng ki. Trung tâm nhận được bản mã từ Ai sẽ giải mã bằng khóa ki, nhận thấy chỉ thị cần liên kết Ai với Aj, thì trung tâm thực hiện mã hóa kij bằng kj, sau đó chuyển bản mã này đến Aj. Aj giải mã bằng khóa kj của mình và nhận được khóa kij. Sau bước liên kết mật này thì mọi việc sau đó có thể thực hiện theo kênh công cộng. Trong sơ đồ này chúng ta thấy chỉ cần sử dụng N khóa.
Chúng ta thấy rằng việc lựa chọn khóa mật giữa các bên cũng phải tuân thủ các nguyên tắc nêu ra ở trên, nên đùa hỏi các bên tham gia cần có những kinh nghiệm và các thiết bị chuyên nghiệp để tạo ra khóa phiên. Một trong các giải pháp đưa ra là hai bên Ai và Aj muốn liên kết với nhau thì hai bên yêu cầu trung tâm phân phối khóa phiên. Trung tâm tạo ra khóa kij và chuyển đến Ai và Aj dưới dạng bản mã bằng khóa ki và kj tương ứng.
Nếu như số lượng thành viên trong mạng quá lớn thì trung tâm có thể thực hiện theo mô hình thứ cấp, tức là có một trung tâm chính và các trung tâm vệ tinh của nó.
Khi tạo ra khóa, trung tâm cũng cần có những thông tin đi kèm, những thông tin đó có thể là:
Thời gian tạo ra khóa;
Kiểu khóa và tên gọi;
Thời hạn hoạt động của khóa;
Đối tượng hình thành khóa;
Thông tin về người gởi và người nhận;
Chứng nhận về người nhận khóa vv
Truy cập đến khóa chỉ có những người có chủ quyền và các tổ chức liên quan đến người sử dụng, sự lưu trử và sử dụng các thiết bị lưu trử cũng phải hết sức cẩn thận. Chúng ta thấy nếu có một mối đe dọa nào đến trung tâm thì sẽ ảnh hưởng đến tất cả các thành viên tham gia.
Ngoài ra cũng còn một vấn đề lớn là chứng thực khóa mật. Cần phải đảm bảo điều này để quá trình chuyển khóa chỉ giao đến những người có liên quan, loại trừ trường hợp kẻ gian lợi dụng. Việc chứng thực được thực hiện khi trung tâm phân phối khóa mật qua kênh mật.
Ngoài cách thực hiện phân phối khóa theo trung tâm như trên chúng ta đi tìm hiểu một số sơ đồ phân phối khóa trước, tức là việc thực hiện các tham số để thành lập khóa mật được thực hiện trước thời điểm hai bên muốn liên kết với nhau. Cụ thể ở đây chúng ta tìm hiểu sơ đồ Blom, sơ đồ Deffie-Hellman và sơ đồ trên cơ sỡ đường cong Elliptíc.
Sơ đồ phân phối khóa trước Blom
Chúng ta gọi TA là tổ chức y tín nào đó. Giả sử trong mạng có n người sử dụng. Cho GF(p) là trường hữu hạn, là số nguyên tố. Cho k là số nguyên , . Giá trị k để hạn chế kích thước lớn nhất sơ đồ vẫn an toàn. Trung tâm phân phối khóa (TA) sẽ chuyển cho k+1 của trường GF(p) cho mỗi người sử dụng. Sơ đồ Blom đảm bảo hai bên U và V muốn thiết lập khóa mật thì họ dễ dạng xây dựng được trên cơ sở các tham số do TA cung cấp. Và sơ đồ Blom còn đảm bảo được tập nhiều nhất k người sử dụng trong mạng không liên kết với U, V không đủ khả năng xác định được bất kỳ thông tin nào về khóa mật của U và V. Chúng ta xem trường hợp k=1, tức là TA trao 2 phần tử của trường GF(p) cho mỗi người sử dụng. Và tác giả cũng đã chứng mình được rằng khi k=1 thì sơ đồ cũng an toàn không điều kiện trước bất kỳ người sử dụng cá biệt nào. Chúng ta xem sơ đồ Blom với k=1.
Sơ đồ Blom được miêu tả với các bước sau:
Chọn số nguyên tố p công khai. Mỗi người sử dụng chọn phần tử rGF(p) và công khai. Các phần tử r khác nhau.
TA chọn 3 phần tử ngẫu nhiên a,b,cGF(p) và thiết lập đa thức:
f(x,y)=a+b(x+y)+cxy mod p.
Với mỗi người sử dụng U. TA tính đa thức:
gU(x)=f(x,r) mod p.
và truyền gU(x) đến U trên kênh an toàn. 
Nếu U và V muốn liên lạc với nhau, họ sẽ dùng khóa chung:
KU,V=KV,U=f(rU,rV)=a+b(rU+rV)+crUrV mod p
Cụ thể U tính như sau:
KU,V=f(rU,rV)=gU(rV)
Còn V tính như sau:
KV,U=f(rU,rV)=gV(rU)
Ví dụ: Giả sử có 3 người sử dụng là U, V và W và các phần tử công khai của 3 người lần lượt là: rU=12, rV=7, rW=1. Chọn p=17. Giả sử TA chọn a=8, b=7 và c=2, lúc này đa thức f(x,y) được xác định như sau:
f(x,y)=8+7(x+y)+2xy
TA tính các đa thức riêng cho 3 người sử dụng U, V và W như sau:
gU(x)=7+14x
gV(x)=6+4x
gW(x)=15+9x
Giả sử U và V muốn liên lạc với nhau:
U tính: KU,V=gU(rV)=7+14.7 mod 17=3
V tính: KV,U=gV(rU)=6+4.12 mod 17=3
Sơ đồ phân phối khóa trước Diffie – Hellman 
Sơ đồ phân phối khóa Diffie- Hellman hình thành dựa trên bài toán logarithm rời rạc. Chúng được hình thành như sau. 
Trên trường GF(p), p là số nguyên tố được chọn đủ lớn để bài toán logarith là không giải được, là phần tử nguyên thủy của GF(p). Các giá trị p và công khai.
Gọi ID(U) là thông tin định danh của người sử dụng U trong mạng, ví dụ như tên, địa chỉ.Mỗi người U có một số mũ mật aU với 0aUp-2, và từ giá trị mật này tính ra giá trị công khai tương ứng:
.
Thông tin cá nhân của mỗi người sử dụng U sẽ được xác thực nhờ dấu xác nhận của TA và được TA kí bằng thuật toán ký SigTA và thẩm tra chữ ký bằng thuật toán VerifyTA. Dấu xác nhận của U được định nghĩa như sau:
C(U)=(ID(U),bU,SigTA(ID(U),bU))
Dấu xác thực có thể công khai hoặc mỗi người tự lưu dấu xác thực của mình. Chữ ký của SigTA trên dấu xác nhận cho phép những người tham gia mạng xác định được thông tin của người dùng U.
Bây giờ U và V muốn liên lạc với nhau, họ dễ dàng tính ra khóa mật chung như sau:
U dùng khóa mật aU của mình va giá trị công khai bV của V để tính: .
V dùng khóa mật aV của mình va giá trị công khai bU của U để tính: .
Ví dụ:
Giả sử p=25307, còn là phần tử nguyên thủy của trường GF(p), những tham số công khai. Giả sử U chọn aU=3578. Sau đó U tính giá trị công khai:
,
đặt trên dấu xác nhận của U. Giả sử V chọn aV=19956. Và V cũng tính giá trị công khai:
,
đặt trên dấu xác thực của V.
Bây giờ U và V muốn liên lạc với nhau thi U và V tính ra khóa mật:
U tính: 
.
V tính:
.
Sơ đồ phân phối khóa trước trên cơ sỡ đường cong Elliptíc
Tương tự sơ đồ phân phối Diffie-Hellman, nhưng là trên cơ sở đường cong Eliptic. Sơ đồ được hình thành như sau:
Chọn các tham số a,b và p cho đường cong elliptic E. Chọn điểm khởi tạo P(x,y) thuộc đường cong E có bậc là n. Các tham số này công khai.
Người sử dụng U chọn tham số mật là dU, 0<dU<n và tính giá trị công khai
QU(xU,yU)=dUP.
Tương tự sơ đồ phân phối Diffie-Hellman, những thông tin của U sẽ được xác thực nhờ dấu xác nhận của TA và được TA kí bằng thuật toán ký SigTA và thẩm tra chữ ký bằng thuật toán VerifyTA. Dấu xác nhận của U được định nghĩa như sau:
C(U)=(ID(U),dU,SigTA(ID(U),dU)).
Bây giờ U và V muốn liên lạc với nhau, họ dễ dàng tính ra khóa mật chung như sau:
U dùng khóa mật dU của mình va giá trị công khai QV của V để tính: .
V dùng khóa mật dV của mình va giá trị công khai QU của U để tính: .
Sơ đồ phân phối khóa trực tiếp Deffie-Hellman 
Giao thức này tương tự sơ đồ phân phối khóa Deffie- Hellman, nhưng ở đây là sự liên hệ trực tiếp giữa các bênh muốn liên kết với nhau. Chúng ta giả sử U và V là các bênh muốn liên kết với nhau.
Chọn p là số nguyên tố đủ lớn để bài toán logarith rời rạc không giải được. Và là phần tử nguyên thủy của nhóm 
Chúng ta xem sơ đồ thỏa thuận giữa U và V như sau:
U chọn tham số mật cho mình là aU, với 
U tính và gởi bU cho V.
V chọn tham số mật cho mình là aV, với 
V tính và gởi bV cho V.
U tính: 
.
V tính: 
 .
Sơ đồ phân phối khóa trực tiếp Diffie-Hellman mở rộng
Sơ đồ phân phối khóa Diffie-Hellman dễ dàng áp dụng cho việc phân phối khóa khi có ba hoặc nhiều bên tham gia. Chúng ta xem trường hợp đơn giản là có 3 người Alice, Bob và Davic tham gia trao đổi khóa. Sơ đồ được miêu tả như sau:
Alice chọn ngẫu nhiên số nguyên x, và tính:
Bob chọn ngẫu nhiên số nguyên y, và gởi cho Davic số:
Davic chọn ngẫu nhiên số nguyên z, và gởi cho Alice số:
Alice gởi cho Bob số:
Bob gởi cho Davic số:
Davic gởi cho Alice số:
 ... iên có phần bí mật. Rõ ràng rằng khi liên kết tất cả các người có phần bí mật thì sẽ khôi phục được bí mật. Thế nhưng bài toán này đặt ra tình huống trên thực tế, một số người trong số đó vì lý do sức khỏe hay đi công tác, số người còn lại vẫn có thể khôi phục được khóa mật để đảm bảo công việc. Cho nên bài toán ở đây là có khả năng khôi phục được khóa mật trong trường hợp không tham gia của tẩt cả thành viên, nhưng chỉ khôi phục được khóa mật khi và chỉ khi số lượng thành viên tham gia khôi phục phải lớn hơn hoặc bằng ngưỡng nào đó.
Trong trường hợp tổng quát bài toán phân chia bí mật được hình thành như sau. Cần phân chia bí mật S cho n người lưu giữ (P1,P2,,Pn), mỗi người Pi giữ một phần thông tin xi có quan hệ với S, sao cho bất kỳ t () trong số n người có thể khôi phục được bí mật S nếu như , ở đây k là ngưỡng. Thế nhưng số lượng thành viên liên kết nhỏ hơn k thì không thể khôi phục được S cho dù giữa họ có một tài nguyên lớn để tính toán.
Để hiểu về sơ đồ chia sẻ bí mật chúng ta tìm hiểu sơ đồ đơn giản sau. Giả sử M là thông tin mật, biểu diễu dưới dạng nhị phân chiều dài m. Sơ đồ phân chia bí mật thực hiện cho ba người A, B,C có dạng sau:
Nhà phân phối D chọn hai dãy bít ngẫu nhiên RA và RB chiều dài m và tính: .
D chuyển cho thành viên A dãy thông tin RA, cho thành viên B là RB và cho thành viên C là dãy RC.
Để đọc được thông tin M, thi A, B, C cần phải liên kết ba thành phần bí mật của mình là RA, RB và RC và tính .
Sơ đồ chia sẽ bí mật Shamir 
Sơ đồ này ra đời năm 1979, tác giả của nó la Shamir. Sơ đồ này được cho như sau:
Một nhà phân phối D muốn chia sẽ bí mật S cho n thành viên, với n+1, p là số nguyên tố đủ lớn,ví dụ p có độ lớn là 512 bít. Và D muốn xây dựng ngưỡng bằng k, bằng cách D chọn một đa thức ngẫu nhiên a(x) có bậc là k-1, trong đa thức này hằng số là S. Sơ đồ này cho như sau:
D chọn n phần tử x1,,xn trong Zp, với với và với . Mỗi thành viên Pi sẽ có một giá trị xi. Các giá trị xi là công khai.
D muốn chia sẽ khóa . D chọn ngẫu nhiên và độc lập k-1 phần tử a1,,ak-1 thuộc Zp. Các giá trị ai là bí mật.
Với , D tính yi=a(xi), trong đó
a(x)=S+
D trao yi cho Pi, với .
Bây giờ chúng ta xem xét liệu có một nhóm B gồm k thành viên có thể khôi phục được bí mật S hay không. Giả sử rằng các thành viên của nhóm B là muốn xác định bí mật S. Nhóm này biết rằng:
Với và a(x). Đa thức a(x) có bậc lớn nhất là k-1 nên có thể viết a(x) dưới dạng sau:
ở đây a1,,ak-1 thuộc Zp là các phần tử mật do D chọn và . Chúng ta thu được hệ phương trình tuyến tính gồm k phương trình như sau:
Hệ này có thể viết lại như sau:
Đặt ,
Chúng ta thấy ma trân A là ma trận Vandermonde. Định thức của ma trận này được tính theo công thức sau:
detA=
Vì với nên không có thành phần nào của tích trên là bằng không. Ma tích này tính trong Zp nên detA0, nên hệ có nghiệm duy nhất.
Và rõ ràng nếu như có một nhóm có số lượng thành viên nhỏ hơn k muốn khôi phục k, thì họ sẽ thành lập một hệ mới có t ẫn nhưng số lượng phương trình nhỏ hơn số ẩn nên hệ họ thu được không thể có nghiệm duy nhất.
Ví dụ:
Giả sử p=17, k=3,w=5 và các giá trị công khai xi=i, , giả sử D chọn các tham số bí mật và tính ra các giá trị y1,y5. Giả sử nhóm B={P1,P3,P5}, tương ứng với các giá trị của nhóm là y1=8, y2=10 và y5=11.
Khi đó nhóm B thu được hệ 3 phương trình tuyến tính sau:
Giải hệ này ta thu được nghiệm duy nhất là a0=13; a1=10; a2=2. Vậy khóa S=13.
Sơ đồ chia sẽ bí mật trên cơ sỡ định lý phần dư Trung Hoa
Chúng ta lựa chọn một số tập hợp gồm các cặp số nguyên tố cùng nhau có kích thước đủ lớn. Giá trị n tương ứng với số lượng thành viên mà nhà phân phối muốn chia sẽ bí mật. Chúng ta tính tích của k số nhỏ nhất từ tập trên. Giả sử tích này bằng N. Chúng ta tính tiếp tích k-1 số lớn nhất từ tập trên. Giả sử tích này bằng M. Số k gọi là ngưỡng của sơ đồ trên cơ sỡ tập hợp , nếu như M<N. Chúng ta chọn số bí mật S thỏa mãn điều kiện . Bí mật được chia cho các thành viên dưới dạng một cặp số (ri,mi), ở đây ri là phần dư của phép chia S cho mi.
Nếu như thành viên có mảnh bí mật (ri,mi) liên kết với nhau để khôi phục bí mật S, bằng cách giải hệ phương trình đồng dư:
Sử dụng định lý Trung hoa để giải hệ trên và tìm ra nghiệm x0 thỏa mãn điều kiện . Chúng ta dễ dàng chứng minh x0=S. Rõ ràng theo cách xây dựng sơ đồ phân chia S thỏa mãn hệ đồng dư thức đã cho, với điều kiện . Áp dụng định lý Trung hoa thì hệ trên có nghiệm duy nhất, nghiệm này nhỏ hơn tích modulo và thỏa mãn hệ, có nghĩa là x0=S.
Bây giờ chúng ta chứng minh rằng với t’< k thành viên giữ phần bí mật, họ không thể khôi phục được khóa mật S nhờ giải hệ phương trình đồng dư sau:
Giả sử là số không âm nhỏ nhất thỏa mãn hệ trên: . Bởi vì t’<k nên chúng ta có < M < S. Dầu biết rằng S=+Q, với Q là số tự nhiên nào đó, nhưng tương ứng với sự chọn tập hợp thì số Q là rất lớn, và trên thực tế là khó có thể xác định được, thực sự như vậy, chúng ta có bất đẳng thức sau< M < S<N, có nghĩa là chúng ta có:
M < +Q< N
M-< Q < N-
.
Để xác định Q cần phải xác định tất cả các số nguyên trong khoảng từ đến . Có nghĩa là xác định -các số khác nhau. Nếu như lựa chọn tập hợp để thương N/M biểu diễn dưới dạng nhị phân từ 129 đến 130 bít thì trên thực tế khó xác định được số Q.
Ví dụ:
Nhà phân phối D muốn chia sẽ S cho 5 thành viên P1,P5, với ngưỡng là k=3. D chọn tập hợp . Tính M=m4m5=10403, N=m1m2m3=941094. Chọn S=571875. D tính ra 5 cặp mảnh bí mật (ri,mi) để phân chia cho 5 thành viên liên quan, với tập . Bây giờ P1,P4 và P5 muốn kết hợp lại với nhau để khôi phục S. Thì họ giải hệ phương trình đồng dư thức sau:
Giải hệ trên thu được nghiệm x0=571875=S.
Giao thức mật mã
Tổng quan về giao thức mật mã
Trong mật mã thông thường sử dụng cụm từ “thuật toán” và “giao thức”. Thuật toán là một trong những định nghĩa cơ bản trong chương trình và trong toán học tính toán, còn giao thức là sự liên hệ. Hay diễn đạt nôm na thì chúng ta hiểu thuật toán là tổ hợp các lệnh, tác động, chỉ thị, phép tính nhằm biến đổi dữ liệu ban đầu thành dữ liệu khác. Còn giao thức chúng ta có thể hiểu là tập hợp các tác động (lệnh, phép tính, thuật toán, chỉ thị), nó được hai hay nhiều bên tham gia thực hiện tuần tự với mục đích nhận được kết quả nhất định, tức là các tác động tuần tự của hai hay nhiều bên tham gia nhằm giải quyết một nhiệm vụ (bài toán) xác định. 
Để giao thức nhận được một kết quả mong muốn cần phải có các tính chất sau:
Tính hiệu chỉnh của giao thức: Tức là tổ hợp các tác động trong giao thức cần phải đảm bảo để nhận được kết quả cần thiết trong tất cả các tình huống có thể.
Tính hoàn thiện và duy nhất: Tức là giao thức cần phải phân hoạch được tác động của từng đối tượng tham gia giao thức đối với tất cả tình huống có thể.
Tính thống nhất: Tức là các kết quả nhận được từ các đối tượng tham gia giao thức khác nhau không phải đối lập nhau.
Sự am hiểu và trách nhiệm của các đối tượng tham gia giao thức: Tức là, mỗi thành viên tham gia giao thức cần hiểu được giao thức và tất cả các bước mà cần thực hiện; Và mỗi người tham gia giao thức phải chịu trách nhiệm về những hậu quả mà mình làm.
Giao thức mật mã – đây là giao thức, mà trong đó sử dụng mật mã để biến đổi dữ liệu. Mặc dầu các giao thức mật mã thường sử dụng các thuật toán mật mã khác nhau, nhưng bảo mật không phải là mục đích bắt buộc của giao thức mật mã. Ví dụ như các bên tham gia giao thức có thể đồng thời ký một hiệp đồng nào đó; thực hiện bốc xăm điện tử; xác định danh tính người tham gia.
Khóa tạm thời (time – lock puzzles)
Có thể để được hay không thông điệp M vào tương lai và tin tưởng rằng không ai có thể đọc được trong thời gian dài, ví dụ 50 hay 100 năm. Mật mã sẽ giải quyết câu trả lời này bằng cách ứng dụng bài toán phân tích một số thành nhân tử, mà bài toán này không thể giải được trong thời gian cho phép. Sơ đồ xây dựng khóa thời gian được miêu tả như sau:
Bản tin M được mã hóa bằng thuật toán mã đối xứng an toàn bởi khóa K: C=EK(M). Bản mã C cho phép mọi người tìm hiểu.
Khóa K được mã hóa bởi sơ đồ: Q=K+b mod n, ở đây , với là căn nguyên tố theo modulo n, n là số được tính bằng tích của hai số nguyên tố đủ lớn p và q, nghĩa là n=pq, t là số lệnh cần thiết để tính b, cũng chính là thời gian để tìm ra khóa K. Tương tự như bản mã C, Q cũng chia sẽ cho mọi người. (Khi mà biết được sự phân tích số n ra thừa số thì dễ dàng tínhd được hàm Euler , từ đây dễ dàng tính ra b, và từ đây tính ra K).
Khóa K xóa đi. Sau giai đoạn này thì khởi động quá trình tìm kiếm khóa, quá trình này thực hiện bằng t các giá trị thử nghiệm khác nhau K’=Q-b’, b’ là dãy giá trị tăng dần theo công thức truy hồi: với gía trị ban đầu .
Thuật toán tìm khóa K:
Kiểm tra xem giải mã bản mã C theo khóa K’ có đúng không, . Nếu như M’=DK’(C) tương ứng với bản tin thì dừng.
Thay đổi gía trị b’ theo công thức và quay trở về bước 1.
Số lượng thí nghiệm cho phép xác định được tham số t để xác định được thời gian tìm ra khóa K.
Chú ý, giống như trong sơ đồ mật mã RSA, việc chọn modulo n từ tích hai số p và q cũng phải lựa chọn các số q, và p đủ lớn, sao cho phân tích q-1 và p-1 ra thừa số, thì tồn tại ít nhất một ước nguyên tố lớn.
Chơi bài xì Poker
Chúng ta xem trường hợp đơn giản của trò chơi là có con bài và hai người chơi. Trò chơi được thiết lập như sau. Có 2 người chơi A và B và ba con bài K, C, D. Cần phải phân bố các con bài sao cho mỗi người chơi A và B có một con và còn lại một con được giữ mật. Trương trường hợp này cần thỏa mãn các điều kiện sau:
mỗi người chơi chỉ biết con bài của mình, nhưng không biết con bài đối phương và con bài thứ ba.
Mỗi người chơi với xác suất nhận được con bài bất kỳ là như nhau.
Để thực hiện sơ đồ giao thức cho trò chơi, chúng ta thực hiện các bước sau đây:
Các người chơi thỏa thuận để chọn số nguyên tố p.
Tính toán giá trị hàm phi Euler .
Mỗi con bài được thay bằng các số tương ứng: , với .
Người chơi A chọn số CA, thỏa mãn và nguyên tố cùng nhau với . Tính phần tử nghịch đảo dA của CA, tức là thỏa mãn .
Tương tự người chơi B cũng có cặp số CB, dB, thỏa mãn .
Quá trình chia bài được diễn ra các bước sau:
Ba con bài ở chổ người chơi A, mỗi con bài được mã hóa theo CA như sau:
A chuyển các số u1, u2, u3 sang cho người chơi B.
B chọn một cách may rủi một trong 3 số u1, u2, u3 giả sử chọn u2 và gởi u2 cho A.
A xem con bài của mình bằng cách tính giá trị hàm: .
Còn 2 số u1 và u3 được B mã theo quy tắc của mình:
B chuyển hai số v1 và v3 cho A.
A chọn một cách may rủi một trong 2 con v1 và v3, giả sử A chọn v3 và tính:và A gởi w3 cho B.
B xem con bài của mình bằng cách tính gía trị hàm .
Như vậy hai bên A và B có những con bài của riêng mình, còn một con bài thứ 3 mà cả hai bên đều không biết.
Tiền điện tử
Một lĩnh vực ứng dụng khác của giao thức mật mã là tiền điện tử. Tiền điện tử bắt đầu được sử dụng vào những năm cuối thập niên 90.
Khái niệm tiền điện tử: Tiền điện tử (e-money hay còn được gọi là digital cash) là một hệ thống cho phép người sử dụng cho có thể thanh toán khi mua hàng hoặc sử dụng các dịch vụ nhờ truyền đi các con số từ máy tính này tới máy tính khác. Giống như serial trên tiền giấy, số serial của tiền điện tử là duy nhất. Mỗi "tờ" tiền điện tử được phát hành bởi một ngân hàng và được biểu diễn cho một lượng tiền thật nào đó. Tính chất đặc trưng của tiền điện tử cũng giống như tiền giấy thật, nó vô danh và có thể sử dụng lại. Tức là, người mua hàng sẽ trả một số tiền nào đó cho người bán hàng và không sẽ có bất cứ phương thức nào để lấy thông tin về người mua hàng. Đó cũng là một đặc điểm khác biệt giữa tiền điện tử và hệ thống thanh toán thẻ tín dụng. 
Để sử dụng được tiền điện tử cần các điều kiện sau:
Tồn tại người mua, người bán và ngân hàng
Người mua và người bán có tài khoản trong ngân hàng
Để tạo ta tiền điện tử có thể sử dụng hệ thống RSA. Cụ thể các tham số hệ thống được hình thành như sau:
Ngân hàng tạo ra 2 số nguyên tố lớn p và q, tính N=pq, 
Ngân hàng lựa số c làm tham số mật, sao cho thỏa mãn :UCLN(c, )=1.
Ngân hàng tính tham số công khai d, thỏa mãn phương trình .
Tham số (N,d) là công khai với mọi người.
Để đơn giản, chúng ta giả sử rằng việc thanh toán chỉ dùng đồng tiền có mệnh giá như nhau. 
Quá trình thanh toán tiền diễn ra các bước sau:
Người mua tạo ra số ngẫu nhiên n thỏa mãn điều kiện. Đây là số serial của đồng tiền, và gởi số này đến ngân hàng.
Ngân hàng sẽ kiểm tra sự tồn tại tài khoản của người mua và ký lên đồng bạc của người mua theo quy tắc và cấp trị giá của đồng bạc này từ tài khoản của người mua. Cặp là tiền điện tử và ngân hàng gởi tiền này cho người mua hàng.
Người mua hàng sẽ gởi tiền điện tử này cho người chủ bán hàng. Người chủ sẽ kiểm tra tính xác thực của đồng tiền theo quy tắc , nếu n=n’ thì tiền trên là đúng.
Người chủ sẽ chuyển tiền này đến ngân hàng, ngân hàng sẽ chuyển trị giá đồng bạc này lên tài khoản của người chủ.
Với cách thực hiện như giao thức này thì tồn tại một số khuyết điểm:
Ngân hàng nhận được số serial của đồng tiền hai lần, đầu tiên là từ người mua hàng và lần thứ hai là từ người bán hàng, cho nên có thể kiểm soát được thông tin của người mua hàng.
Vì trao đổi thông tin diễn ra trên kênh công cộng, nên tội phạm có thể nhặt lấy chữ ký của ngân hàng gởi cho người mua hàng và có thể chuyển cho người bán hàng và có thể nhận được hàng.
Để khắc phục các điểm yếu trên chúng ta dùng một phương pháp ký, có tên là chữ ký mờ, mà chúng ta đã tìm hiểu ở phần chữ ký số. Giao thức thanh toán tiền diễn ra như sau:
Người mua hàng tạo ra số ngẫu nhiên r là nguyên tố cùng nhau với N, và số serial của tiền, giống như trong sơ đồ trước. Sau đó người mua hàng tính giá trị theo thuật toán Euclide mở rộng.
Người mua hàng biến đổi số serial của đồng tiền theo quy tắc: , và gởi n’ đến ngân hàng.
Ngân hàng ký lên số serial bị biến đổi này theo quy tắc: và chuyển cho người mua hàng chữ ký và lấy tài khoản người mua tương ứng với trị giá của đồng tiền.
Người mua hàng tính chữ ký thức của ngân hàng của đồng tiền như sau
Tiền điện tử chuyển đến cho người bán hàng và quá trình tiếp theo tương tự như trong sơ đồ trước.
Chú ý: ở bước 1 của sơ đồ, khi chuyển đến ngân hàng thì người mua hàng không chỉ chuyển đến n’ mà là chữ ký của bộ ba (withdrawal, anA, n’)a, ở đây withdrawal là lệnh lấy tiền từ tài khoản, anA là số tài khoản của người bán hàng, a là khóa mật của người bán hàng. Tương tự đối với người bán hàng, khi chuyển đến ngân hàng, anh ta chuyển chữ ký của bộ ba (deposit, anB,nc)b, ở đây deposit là lệnh chuyển tiền vào tài khoản, anB là số tài khoản của người bán hàng, b là khóa mật của người bán hàng.
Hai sơ đồ trên tồn tại nhược điểm do tính chất nhân của hệ RSA, nhược điểm thể hiện như sau: Nếu như người mua có hai đồng tiền điện tử , thì người bán hàng có thể hình thành lên đồng tiền thứ ba từ hai đồng tiền này như sau: ,,. Để khắc phục điểm yếu này thì ta dùng hàm hash H để tính giá trị của số serial n:, và ngân hàng sẽ ký lên :, và tiền điện tử lúc này là cặp . Người chủ sẽ kiểm tra tính chân thực của chữ ký, tính giá trị hàm Hash của số n nhận được và rà soát lại những gì nhận được.
df