- Các sơ đồ định danh 9.1 Giới thiệu.. - đợc thành có thể giải đợc. - Một bài toán nh vậy là bài toán xây dựng các sơ đồ định danh mật. - Thực tế, các kiểu sơ đồ này thờng không đợc thực hiện theo cách an toàn. - Trong các giao thức thực hiện trên điện thoại, bất kì kẻ nghe trộm nào cũng có thể dùng thông tin định danh cho mục đích riêng của mình. - Những ngời này cũng có thể là ngời nhận thông tin. - Mục đích của sơ đồ định danh là: ai đó “nghe” nh Alice t xng danh với Bob không thể tự bịa đặt mình là Alice. - Một vài sơ đồ định danh nh vậy đã đợc nêu ra. - Một mục đích thực tế là tìm một sơ đồ đủ đơn giản để có thể thực hiện đợc trên thẻ thông minh, đặc biệt là thẻ tín dụng gắn thêm một chíp có khả. - tính toán lẫn bộ nhớ nhỏ đến mức có thể. - Trong các phần sau sẽ mô tả một số sơ đồ định danh thông dụng nhất. - Tuy nhiên, trớc hết hãy xét một sơ đồ rất đơn giản dựa trên hệ thống mã khoá riêng bất kì, chẳng hạn nh DES. - Mọi sơ đồ định danh thực sự đều là các giao thức “Yêu cầu và đáp ứng” song các sơ đồ hiệu quả nhất lại không yêu cầu các khoá. - 9.2 Sơ đồ định danh Schnorr.. - Ta bắt đầu bằng việc mô tả sơ đồ định danh Schnorr - là một trong những sơ đồ định danh thực tiễn và đáng chú ý nhất. - Ta sẽ chọn các tham số cho sơ đồ nh sau:. - Nếu Bob luôn dùng cùng một r thì Olga có thể mạo danh Alice bằng phơng pháp mô tả ở trên).. - sơ đồ định danh Schnorr. - Tiếp theo ta hãy xem xét cách ai đó có thể mạo danh Alice.. - Nếu sơ đồ chữ kí của TA là an toàn, Olga sẽ không thể làm giả chữ kí s’ (mà sau này sẽ bị Bob xác minh).. - định danh). - Có thể chứng minh một định lí chính xác hơn về tính an toàn của giao thức nh sau:. - Khi đó Olga có thể tính a trong thời gian đa thức.. - Chứng minh. - Với một phần ε trên 2 t yêu cầu r, Olga có thể tính giá trị y (sẽ. - Vì ε ≥ 1/2 t-1 nên ta có 2 t / ε ≥ 2 và bởi vậy, Olga có thể tính đợc các giá trị y 1 ,y 2 ,r 1 và r 2 sao cho. - 1 và Olga có thể tính:. - khi đó có thể tính:. - Tuy nhiên nó sẽ hoàn toàn không an toàn vì sau đó Olga có thể mạo danh Alice.. - Nói chung, có thể hình dung tình huống khi Alice chứng minh danh tính của mình với Olga trong một số tình huống khác nhau. - định giá trị a để sau đó có thể mạo danh Alice. - thức thực hiện giao thức và sau đó thực hiện một lợng tính toán đa thức thì giao thức có thể đợc gọi là an toàn.. - Hiện tại vẫn cha chứng minh đợc rằng giao thc Schnorr là an toàn, song trong phần tiếp sau, ta sẽ đa ra một cải tiến về sơ đồ này (do Okmoto đa ra) mà có thể chứng minh đợc nó là an toàn khi cho trớc giả thuyết tính toán nào đó.. - Sơ đồ Schnorr đã đợc thiết kế với tốc độ nhanh và hiệu quả. - Vì mục đích thảo luận, ta hãy giả sử rằng, ID(Alice) là chuỗi 512 bit, v cũng gồm 512 bit, còn s bằng 320 bit nến DSS đợc dùng nh sơ đồ chữ kí. - Có thể mô tả thông tin đợc liên lạc ở dạng đồ hình nh sau. - 9.3 Sơ đồ định danh của Okamoto.. - Trong phần này ta sẽ đa ra một biến thể của sơ đồ Schnorr do Okamoto đa ra. - Sơ đồ cải tiến này Zp không giải đợc.. - Để thiết lập sơ đồ, TA chọn p và q nh trong sơ đồ Schnorr. - ai có thể giải đợc (thậm chí Alice và Olga liên minh với nhau) để tính ra giá trị c. - Nh trớc đây, TA chọn sơ đồ chữ kí số và hàm hash. - Dới đây là một ví dụ về sơ đồ Okamoto.. - đồ của Okamoto và Schnorr là ở chỗ, ta có thể chứng minh rằng sơ. - đầy đủ trong sơ đồ Schnorr.. - Khi đó, Olga có thể tính các giá trị b 1 ,b 2 trong thời gian đa thức sao cho. - Chứng minh:. - Với phần ε trên 2 t yêu cầu có thể r, Olga có thể tính các giá trị y 1 , y 2 , z 1 , z 2 , r và s với r ≠ s và:. - Sơ đồ định danh Okamoto.. - Khi đó, Alice và Olga có thể cùng nhau tính log α 1 α 2 trong thời gian đa thức với xác suất 1-1/q.. - c = log α 1 α 2 = (a 1 -b 1 )(b 2 -a 2 ) -1 mod q có thể tính đợc trong thời gian đa thức.. - Nghĩa là A gồm tất cả các cặp đợc sắp có thể và chúng có thể là các số mũ mật của Alice. - Có thể biểu diễn y 1 và y 2 nh sau:. - nếu ta chứng minh rằng Olga có thể giả danh Alice thì Olga có thể tính một cặp trong A khác với cặp của Alice (với xác suất cao). - Nh vậy Alice và Olga có thể cùng nhau tìm hai cặp trong A và tính c - cho mâu thuẫn nh mong muốn.. - giá trị thực tế này là log α 1 α 2 mà có thể xác minh bằng cách tính:. - biết nào chứng tỏ sơ đồ Schnorr an toàn (thậm chí giả thiết rằng, bài toán logarithm rời rạc không giải đợc) song ta cũng không biết bất kì nhợc điểm nào của sơ đồ này. - Thực sự sơ đồ Schnorr đợc a thích hơn sơ đồ Okamoto do nó nhanh hơn.. - 9.4 Sơ đồ định danh Guillou - quisquater.. - Trong phần này sẽ mô tả một sơ đồ định danh khác do Guillou và Quisquater đa ra dựa trên RSA.. - Việc thiết lập sơ đồ nh sau: TA chọn 2 số nguyên tố p và q và lập tích n =pq. - Cuối cùng TA chọn sơ đồ chữ kí và hàm hash.. - Ta sẽ chứng minh rằng, sơ đồ Guillou - Quisquater là đúng đắn và đầy đủ. - Tuy nhiên, sơ đồ không đợc chứng minh là an toàn (mặc dù giả thiết hệ thống mã. - Giả sử b. - Hình 9.7: Sơ đồ định danh Guillou - Quisquater.. - Ta sẽ chứng minh sơ đồ là. - Khi đó Olga có thể tính u trong thời gian đa thức.. - Với γ nào đó, Olga có thể tính giá trị y 1 , y 2 , r 1 , r 2 với r 1 ≠ r 2 sao cho:. - r1- r2 <b và b là số nguyên tố nên t = (r 1 - r 2 ) -1 mod b tồn tại và Olga có thể tính nó trong thời gian đa thức bằng thuật toán Euclidean. - Olga có thể dùng công thức này để tính u trong thời gian đa thức.. - Cuối cùng cô có thể nhận đợc giá trị u mật nh sau:. - Sơ đồ định danh Guillou - Quisquater có thể chuyển thành sơ đồ định danh dựa trên tính đồng nhất. - định danh, Alice cần biết giá trị u, giá trị này chỉ TA là có thể tính đợc (giả thiết hệ thống mã khoá công khai RSA là an toàn). - Hình 9.9: Sơ đồ định danh dựa trên tính đồng nhất Guillou - Quisquater.. - 9.5 Chuyến sơ đồ định danh thành sơ đồ chữ kí.. - Có một phơng pháp chuẩn để chuyển sơ đồ định danh thành sơ đồ chữ kí. - Trong sơ đồ chữ kí thực hiện theo phơng pháp này, thông báo không bị chặt ra (băm) trớc khi đợc kí: Quá. - Sau đây sẽ minh hoạ biện pháp này bằng việc chuyển sơ đồ Schnorr thành sơ đồ chữ kí (hình 9.10). - Trong quá trình chuyển từ sơ đồ định danh thành sơ đồ chữ. - Song trong phạm vi của sơ đồ chữ kí, ta cần cac bản tóm lợc thông báo có kích thớc lớn hơn nhiều để ngăn chặc sự tấn công thông qua việc tìm kiếm các va chạm trong hàm hash.. - Hình 9.10: Sơ đồ chữ kí Schnorr.. - Sơ đồ định danh Schnorr nêu trong tài liệu [Sc91], sơ đồ Okamoto đợc đa ra trong [OK93] còn sơ đồ Guillou - quisquater có thể tìm thấy trong [GQ88]. - Một sơ đồ khác chứng minh sự an toàn dới giả thiết tính toán hợp lý là của Brickell và McCurley [BM92].. - Các sơ đồ định danh phổ biến khác chứa đựng trong sơ đồ Fiege - Fiat - Shamir [FFS88] và sơ đồ nhân hoán vị [SH90]. - Sơ đồ Fiege - Fiat - Shamir đợc chứng minh là an toàn nhờ dùng kĩ thuật tri thức không.. - Phơng pháp xây dựng sơ đồ chữ kí từ các sơ đồ định danh là do Fiat và Shamir đa ra [FS87]. - Chúng cũng đợc mô tả và phiên bản dựa trên tính đồng nhất của sơ đồ định danh của chính họ.. - Các tổng quan về các sơ đồ định danh này đã đợc công bố trong công trình của Burmester, Desmedt và Beth [BDB92] và công trình của Waleffe và Quisquater [DWQ93].. - Xét sơ đồ định danh sau đây: Alice sở hữu khoá mật n = pq, p và q là những số nguyên tố và p ≡ q ≡ 3 (mod 4). - Hãy giải thích tại sao sơ đồ này không an toàn.. - Giả sử Alice đang dùng sơ đồ Schnorr với q = 1201, p =122503, t. - Giả thiết, Alice dùng sơ đồ Schnorr với p, q, t nh trong bài tập 9.2. - v=51131 và giả sử Olga có thể nghiên cứu thấy rằng:. - Hãy chỉ ra cách Olga có thể tính số mũ mật a của Alice.. - Giả sử Alice đang dùng sơ đồ Okamoto với q = 1201, p = 122503, t= 10, α 1 =60497 và α 2 = 17163. - 9.5/ Cũng giả thiết rằng Alice dùng sơ đồ Okamoto với p, q, t, α 1 và α 2. - Giả sử rằng, Alice đang dùng sơ đồ Quisquater với p = 503, q = 379 và b= 509.. - Giả sử Alice đang dùng sơ đồ Quisquater với n = 199543, b = 523 và v=146152. - v b = v 257 36056 b (mod n) Hãy nêu cách Olga có thể tính u.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt