Giáo trình An toàn và bảo mật thông tin - Nguyễn Khanh Văn
Tóm tắt Giáo trình An toàn và bảo mật thông tin - Nguyễn Khanh Văn: ... 0 A B C D E F G H I J K L M N O P Q R S T U V 1 B C D E F G H I J K L M N O P Q R S T U V W 2 C D E F G H I J K L M N O P Q R S T U V W X 3 D E F G H I J K L M N O P Q R S T U V W X Y 4 E F G H I J K L M N O P Q R S T U V W X Y Z 5 F G H I J K L M N O P Q R S T U V W X Y Z A 6 G H I J K L M ... Hình 2.2 Sơ đồ cơ bản của DES: đầu vào của DES là khối độ dài 64 bits, đầu ra 64 bits và khóa là 56 bits. Hình 2.3 Sơ đồ giải thuật sinh mã DES với cấu trúc 16 vòng lặp Sơ đồ hình vẽ 2.3 cho thấy DES được cấu tạo bởi 16 bước lặp với bước lặp cơ sở gọi hàm DES 32 Bits 64 Bits 32 Bits f 3... toàn Thông tin ĐHBKHN-2012 Chương III - 1 - CHƯƠNG 3 Hê thông mât mã khóa công khai 1. Giới thiệu Như đã nêu, các hệ thống mật mã đã giới thiệu cho đến giờ đều được gọi là các hệ mật mã khóa đối xứng (Symmtric Key Cryptosystems) do vai trò hai bên gửi và nhận tin đều như nhau vì đều sở hữu...
thành công nhất là RSA và Elgamal. Nói chung thuật toán PKC là chậm và không thích hợp cho mật mã trên dòng (online) với truyền tin tốc độ cao, vì vậy chỉ thường được sử dụng khi cần đến tính an toàn cao và chấp nhận tốc độ chậm. Ngoài ra người ta thường sử dụng kết hợp PKC và SKC (symmetric key cryptosystems) với PKC có tác dụng “khởi động mồi” cho SKC: dùng PKC để thiết lập thuật toán tạo ra khoá bí mật thống nhất chung giữa hai bên truyền tin sau đó sử dụng khoá bí mật trên cho pha truyền tin chính bằng SKC sau đó. 3. Hệ thống khóa công khai RSA RSA là hệ mật mã khóa công khai phổ biến và cũng đa năng nhất trong thực tế, phát minh bởi Rivest, Shamir & Adleman (1977). Nó là chuẩn mật mã bất thành văn đối với PKC, cung cấp đảm bảo tính mật, xác thực và chữ ký điện tử. Cơ sở thuật toán RSA dựa trên tính khó của bài toán phân tích các số lớn ra thừa số nguyên tố: không tồn tại thuật toán thời gian đa thức (theo độ dài của biểu diễn nhị phân của số đó) cho bài toán này. Chẳng hạn, việc phân tích một hợp số là tích của 2 số nguyên tố lớn hàng trăm chữ số sẽ mất hàng ngàn năm tính toán với một máy PC trung bình có CPU khoảng trên 2Ghz. Ý tưởng (Motivation) Các nhà phát minh có lựa chọn khá giản dị là xây dựng thuật toán sinh/giải mã trên cơ sở phép toán lấy luỹ thừa đồng dư trên trường Zn = {0,1,2,..n-1}. Chẳng hạn, việc sinh mã cho tin X sẽ được thực hiện qua: Y = Ở đây ta dùng ký hiệu a = b + n nghĩa là a = b + k* n với a Zn còn k = 1,2,3,..., ví dụ 7 = 33 + 10) còn việc giải mã: X = (e – khóa sinh mã, d – khóa giải mã) Như vậy để hai hàm sinh mã và giải mã này là hàm ngược của nhau, e và d phải được chọn sao cho: Xed = X+ n Người ta đã tìm được cách xây dựng cặp số (e,d) này trên cơ sở công thức như sau: + n (định lý Ơ - le) Trong đó (n) hàm số cho biết số lượng các số thuộc Zn mà nguyên tố cùng nhau với n. Người ta cần chọn e*d sao cho chia (n) dư 1, hay d= e-1 + (n), khi đó ta sẽ có điều cần thiết: Xed = Xk.(n)+1 =(X(n))d * X = 1*X =X nX e nY d 1)( nX Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 8 - (n) có thể tính được khi đã biết công thức phân tích thừa số nguyên tố của n, cụ thể là nếu đã biết n = p*q (p.q là số nguyên tố) thì (n) = (p-1) (q-1). Nói cách khác nếu như cho trước một số e thì nếu đã biết công thức phân tích thừa số nguyên tố của n ta có thể dễ dàng tìm được d sao cho d = e-1 + (n) hay là Xed = X + n, còn nếu không biết thì rất khó. Vừa rồi là phần trình bày dẫn dắt về cội nguồn của thuật toán, sau đây là thuật toán cụ thể. Thuật toán RSA Xây dựng: Chọn các tham số 1. Chọn hai số nguyên tố lớn p và q. Tính n = p x q và m = (n) = (p = 1) x (q-1). 2. Chọn e, 1 e m -1, sao cho gcd (e, m) = 1. 3. Tìm d sao cho e * d = 1 (mod m), tức là tính d = e-1 (mod m), giải theo thuật toán gcd mở rộng đã trình bày ở phần trước. Khóa công khai (Public key) là (e, n) Khoá dùng riêng (Private key) là d, p, q) Giả sử X là một khối tin gốc (plaintext), Y là một khối mã tương ứng của X, và là các thành phần công khai và riêng của khoá của Alice Mã hoá. Nếu Bob muốn gửi một thông báo mã hoá cho Alice thì anh ta chỉ việc dùng khoá công khai của Alice để thực hiện: Giải mã: Khi Alice muốn giải mã Y, cô ta chỉ việc dùng khoá riêng zA = d để thực hiện như sau: Ví dụ 3.5 Chọn p = 11 và q = 13 n=11*13=143 m= (p-1)(q-1) =10 *12=120 e=37 gcd (37,120) =1 Sử dụng thuật toán gcd để tìm sao cho e * d =1 120, ta tìm được d= 13 (e*d =481) Để mã hoá một xâu nhị phân, ta phải “bẻ” ra thành nhiều đoạn độ dài là u bit, sao cho 2u ≤ 142. Do đó u = 7. Mỗi đoạn như vậy sẽ là một con số nằm trong khoản 0 - 127 và ta có thể tính mã Y theo công thức: Chẳng hạn với X = (0000010) =2, ta có Y= (00001100) Giải mã như sau: ),( AA Zz nXXEY eZ A )( nYYD dzA )( 120 eXY 14312)( 37 XXEZ 143212)( 13 YDX z Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 9 - Để tiện cho việc giao dịch trên mạng có sử dụng truyền tin mật, người ta có thể thành lập các Public Directory (thư mục khoá công khai), lưu trữ các khoá công khai của các user. Thư mục này được đặt tại một điểm công cộng trên mạng sao cho ai cũng có thể truy nhập tới được để lấy khoá công khai của người cần liên lạc. User (n,e) Alice Bob Cathy . . . (85,23) (117,5) (4757,11) . . . Một số ứng dụng cơ bản (của các hệ thống mật mã khóa công khai nói chung) a. Bảo mật trong truyền tin (Confidentiality) A sẽ gửi cho B. B dễ dàng giải mã bằng khóa bí mật zB b. Chứng thực + Alice ký lên tin cần gửi bằng cách mã hoá với khoá bí mật của cô ta và gửi cho Bob + Khi Bob muốn kiểm tra tính tin cậy của tin nhận được, anh ta chỉ việc tính và kiểm tra nếu X = X’ thì xác thực được tính tin cậy (authenticity) của X. Chú ý 1: Trong quá trình này cả việc kiểm tra (i) tính toàn vẹn của thông báo và việc (ii) xác thực danh tính của người gửi được thực hiện cùng một lúc. Ta có (i) là vì chỉ cần một bit của tin mà bị thay đổi thì sẽ lập tức bị phát hiện ngay do chữ ký không khớp. Ngoài ra có (ii) vì không ai có thể tạo ra được thông báo đó ngoài Alice, người duy nhất biết zA. Chú ý 2: Alice có thể ký vào giá trị băm (hash) của X thay vì ký thẳng lên X. Khi đó toàn bộ mã mà Alice sẽ chuyển cho Bob là . H là một hàm băm công khai. Phương pháp này là hiệu quả hơn do tiết kiệm (hàm băm luôn cho ra một xâu độ dài cố định và thông thường ngắn hơn rất nhiều so với xâu đầu vào). c. Kết hợp tính mật và tin cậy. Chúng ta có thể làm như sau để kết hợp cả hai khả năng a và b như trên. A gửi cho B B phục hồi X như sau: Để có bằng chứng nhằm đối phó với việc Alice có thể sau này phủ nhận đã gửi thông báo (non-repudiation) thì Bob phải lưu giữ Một số vấn đề xung quanh thuật toán RSA Vấn đề chọn p và q: + p và q phải là những số nguyên tố lớn, ít nhất là cỡ 100 chữ số. )(XE BZ )(XD Az ))(,(),( XDXSX Az ))(()(' XDEXEX AAA zZZ )))((,( XHDX Az ))(( XDEY AB zZ ))))(((())(( XDEDEYDEX ABBABA zZzZzZ )(XD Az Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 10 - + p và q phải lớn cỡ xấp xỉ nhau ( về độ dài cùng 100 chữ số chẳng hạn). Bài tập: Tại sao lại có điều kiện thứ 2? Một vài con số về tốc độ thuật toán trong cài đặt: So sánh với DES thì RSA: + Có tốc độ chậm hơn rất nhiều. Thường thì, RSA chậm ít nhất là 100 lần khi cài đặt bằng phần mềm, và có thể chậm hơn từ 1000 đến 10,000 lần khi cài đặt bằng phần cứng (còn tùy cách cài đặt) + Kích thước của khoá mật lớn hơn rất nhiều. Nếu như p và q cần biểu diễn cỡ 300 bits thì n cần 600 bits. Phép nâng lên luỹ thừa là khá chậm so với n lớn, đặc biệt là nếu sử dụng phần mềm (chương trình). Người ta thấy rằng thực hiện một phép nhân cỡ m + 7 nhịp Clock khi kích thước n là m bit. Về bài toán phân tích ra thừa số nguyên tố Giải thuật tốt nhất vẫn là phương pháp sàng số. Một ước lượng về thời gian thực hiện của giải thuật là: L(n) Trong đó log2n cho số biết số bit cần để biểu diễn n, số cần phân tích ra thừa số nguyên tố. Từ đó rút ra, nếu tăng n lên thêm 50 bit (quãng 15 chữ số thập phân) thì thời gian làm phân tích ra thừa số nguyên tố tăng lên 10 lần. Vào những năm cuối của thế kỷ 20, người ta đã ước lượng thấy, với n=200, L(n) 55 ngàn năm. Đối với khả năng thực hiện bằng xử lý song song, một trong các kết quả tốt nhất về phân tích TSNT với số lớn cho biết đã phân tích một số có 129 chữ số, phân bố tính toán trên toàn mạng Internet và mất trọn 3 tháng. Như đã nêu, những số nguyên khó phân tích thừa số nhất là những hợp số là tích của 2 số nguyên tố có độ lớn xấp xỉ nhau (vì vậy các số nguyên tố p và q thường được chọn như vậy trong RSA). Từ điển Bách khoa mở, Wikipedia trên Internet, cho biết số nguyên có dạng như vậy lớn nhất cho đến nay mà được phân tích thừa số thành công, ký hiệu là RSA- 768, có 768 bit hay 232 chữ số thập phân. Nó được phân tích thành công vào ngày 12/12/2009 nhờ sự cộng tác của nhiều cơ sở nghiên cứu hiện đại trong vòng 2 năm trời. Lượng tính toán thực hiện trên nguyên lý xử lý song song được so sánh tương đương với 2000 năm chạy liên tục của một cấu hình xử lý 2.2 GHz AMD Opteron RSA-768 = 12301866845301177551304949583849627207728535695953347921973224521517264005 07263657518745202199786469389956474942774063845925192557326303453731548268 50791702612214291346167042921431160222124047927473779408066535141959745985 6902143413 RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793 878002287614711652531743087737814467999489 n2log50 1 7.9 10 Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 11 - × 36746043666799590428244633799627952632279158164343087642676032283815739666 511279233373417143396810270092798736308917 Vấn đề đi tìm số nguyên tố lớn: Một thuật toán để tạo ra tất cả các số nguyên tố là không tồn tại, tuy nhiên có những thuật toán khá hiệu quả để kiểm tra xem một số cho trước có phải là nguyên tố hay không (bài toán kiểm tra tính nguyên tố). Thực tế, việc tìm các số nguyên tố lớn cho RSA là một vòng lặp như sau: 1. Chọn một số ngẫu nhiên p nằm trong một khoảng có độ lớn yêu cầu (tính theo bit) 2. Kiểm tra tính nguyên tố của p, nếu là nguyên tố thì dừng lại, nếu không thì quay lại bước 1. Những thuật toán tất định để kiểm tra tính nguyên tố là khá tốn thời gian và đòi hỏi được thực hiện trên máy tính có tốc độ cao. Tuy nhiên người ta cũng còn sử dụng các thuật toán xác suất, có khả năng ‘đoán’ rất nhanh xem một số có phải nguyên tố không. Các thuật toán xác suất này không đưa ra quyết định đúng tuyệt đối, nhưng cũng gần như tuyệt đối; tức là xác suất báo sai có thể làm nhỏ tùy ý, chỉ phụ thuộc vào thời gian bỏ ra. Xét ví dụ một thuật toán xác suất, dựa trên phương pháp sau đây của Lehmann. Phương pháp Lehmann: Giả sử n là một số lẻ, với mỗi số nguyên a ta hãy ký hiệu: G(a,n) = Ví dụ: Với n=7, ta có 23=1, 33=6, 43=1, 53=6, 63=1; tức là G= 1,6. Theo Lehmann, nếu n là một số lẻ thì G(a,n)=1,n-1 với mọi a nguyên khi và chỉ khi n là số nguyên tố. Tuy nhiên với n hợp số, khả năng G(a,n)=1,n-1 vẫn xảy ra với xác suất 50% cho mỗi số nguyên a nguyên tố cùng nhau với n lựa chọn bất kỳ. Từ kết quả này, ta có phép thử như sau khi cần xác định tính nguyên tố của một số nguyên n: 1. Chọn ngẫu nhiên một số a Zn* 2. If (gcd(a,n) >1) return (“là hợp số”) else 3. If ( return (“ có thể là nguyên tố”) else return (“là hợp số”) Nếu như thực hiện phép thử này 100 lần và luôn thu được câu trả lời “có thể là nguyên tố” thì xác suất n không phải là số nguyên tố (‘đoán nhầm’) sẽ chỉ là 2-100. na n 2 1 )1||1( 2 1 2 1 nn aaIf Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 12 - Để có thể tìm được số lớn với tính nguyên tố chắc chắn tuyệt đối, người ta có thể sử dụng phương pháp xác suất này để loại bỏ nhanh chóng các hợp số và chỉ thực hiện phép kiểm tra tất định cuối cùng với các số đã đáp ứng tốt ở phép thử. Giải thuật tính luỹ thừa nhanh Luỹ thừa có thể được tính như thông thường bằng phép nhân liên tục tuy nhiên tốc độ sẽ chậm. Luỹ thừa trong trường Zn (modulo n) có thể tính nhanh hơn nhiều bằng giải thuật sau đây. Giải thuật này sử dụng hai phép tính là tính bình phương và nhân. Để tính X (modul n): 1. Xác định các hệ số i trong khai triển của trong hệ nhị phân: = 020 + 121 + 222 + ... + k2k 2. Dùng vòng lặp k bước để tính k giá trị n, với i=1,k : 3. Từ bước 1, ta tính được X n bằng cách đem nhân với nhau các giá trị n đã tính ở bước 2 nếu như i tương ứng của nó là 1: Ví dụ 3.6: Xét RSA với n =179, e =73. Với X= 2 ta có Y= 273 179 73 = 64+8+1 = 26+23+20. Y=264+8+1 = 264 28 21 Điểm yếu của giải thuật RSA Trong hệ RSA, không phải tất cả các thông tin đều được che giấu tốt, tức là mọi khoá đều tốt và đều làm bản rõ thay đổi hoàn toàn. Ví dụ 3.7: n = 35 = 5 x 7, m = 4 x 6 e = 5 (GCD (5,24) = 1) X = 8 Y = Xe 35 = 8 = X! Đối với bất kỳ khoá nào tồn tại ít nhất 9 bản rõ bị ‘phơi mặt’, tuy nhiên đối với n 200 điều đó không còn quan trọng. Mặc dù vậy phải chú ý là nếu e không được chọn cẩn thận thì có thể gần đến 50% bản rõ bị lộ. i X 2 11 222 224 2 ... kkk XXX XXX XXX i X 2 1, 0,1 )( 2 2 i i i i i X X Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 13 - Ví dụ 3.8: Với n = 35, e = 17 1, 6, 7, 8, 13, 14, 15, 20, 21, 27, 28, 29, 34 không che được Người ta cho rằng có thể tránh được tình huống này nếu số nguyên tố được chọn là AN TOÀN. Một số nguyên tố được gọi là AN TOÀN nếu p=2p’+1 trong đó p’ cũng là số nguyên tố. Đánh giá về an toàn của thuật toán RSA Sự an toàn của thành phần khoá mật (private key) phụ thuộc vào tính khó của việc PTTSNT các số lớn. Ký hiệu Z= (e,n) là khoá công khai. Nếu biết PTTSNT của n là n=pq thì sẽ tính được m=(n) =(p-1)(q-1). Do đó tính được d=e-1(mod m) theo thuật toán GCD mở rộng. Tuy nhiên nếu không biết trước p,q thì như đã biết không có một thuật toán hiệu quả nào để PTTSNT đối với n, tức là tìm được p,q, khi n lớn. Nghĩa là không thể tìm được m và do đó không tính được d. Chú ý: Độ an toàn của RSA chưa chắc hoàn toàn tương đương với tính khó của bài toán PTTSNT, tức là có thể tồn tại phép tấn công phá vỡ được RSA mà không cần phải biết PTTSNT của n, chẳng hạn nếu như có kẻ thành công trong các dạng tấn công sau: 1. Đi tìm thành phần khóa mật Kẻ thù biết X và Y với Y=Dz(X). Để tìm d nó phải giải phương trình: X = Ydn Hay là tính d = logYX 2. Đi tìm bản rõ: Kẻ thù biết Y và e, để tìm được bản rõ X nó phải tìm cách tính căn thức bậc e theo đồng dư, để giải phương trình Y=Xe Một số dạng tấn công có điều kiện quan trọng: đối với một số hệ cài đặt rơi vào một số điều kiện đặc biệt có thể trở nên kém an toàn với người sử dụng. 1. Common modulus attack: Khi một nhóm user sử dụng các khoá công khai Z=(e,n) khác nhau ở thành phần e nhưng giống nhau ở modul đồng dư n. Khi đó, nếu kẻ thù tóm được hai đoạn bản mã mà: + của cùng một bản rõ được mã hoá bởi khoá PK khác nhau (từ hai user khác nhau) + hai thành phần e tương ứng là nguyên tố cùng nhau thì nó sẽ có cách để giải được bản mã. Cụ thể là nếu kẻ thù biết e1,e2,n,Y1,Y2 1ܻ = ܺభ ± ݊ 2ܻ = ܺమ ± ݊ Vì (e1,e2)=1 nên nó có thể tìm được a và b sao cho: a*e1+b*e2 = 1 Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 14 - Suy ra kẻ thù có thể tìm được X từ: 1ܻ ∗ 2ܻ = ܺభ⋅ ∗ ܺమ⋅ = ܺభ⋅+మ⋅ = ܺ Tóm lại nên tránh sử dụng chung modul đồng dư (common modulus) giữa những user cùng một nhóm làm việc nào đó. 2. Low exponent attack: Tấn công này xảy ra với điều kiện là giá trị e đã được chọn nhỏ (e mà nhỏ thì thuật toán mã hoá trong truyền tin mật cũng như kiểm định chữ ký sẽ nhanh hơn). Nếu kẻ thù có thể tìm được e(e+1)/2 bản mã mà được mã hoá từ những bản rõ phụ thuộc tuyến tính thì hệ thống sẽ bị nguy hiểm. Tuy nhiên nếu các bản rõ này mà không có quan hệ với nhau thì không sao. Vì vậy nên ghép thêm vào các bản rõ những xâu nhị phân ngẫu nhiên để đảm bảo cho chúng là không bị phụ thuộc. 3. Low decryption attack: Nếu thành phần khóa mật d mà đủ nhỏ thì có thể bị kẻ thù tìm thấy được Một số hệ PKC khác Rabin Hệ Rabin cũng xây dựng trên việc lấy n=pq làm bí mật. N được coi là khoá công khai (PK) còn (p,q) là khoá bí mật (SK). Mã hoá là việc thực hiện: Y=X2 (mod n) còn giải mã là việc tính căn bậc hai: X= (mod n) (*) Có thể thấy, nếu biết n=pq thì dễ dàng tìm được nghiệm cho phương trình này, còn nếu không thì việc tìm nghiệm là khó tương đương với bài toán PTTSNT số n. Khi biết N=pq thì (*) được giải ra có bốn nghiệm2, do đó để xác định được đâu là bản rõ gốc phải có mẹo để chọn được đúng giá trị cần thiết trong số 4 nghiệm đó Hệ Rabin có một số ưu điểm so với RSA: + Tính an toàn được chứng minh hoàn toàn tương đương với bài toán PTTSNT, nói cách khác tính ATBM của Rabin là có thể chứng minh được (provable) + Ngoại trừ trường hợp RSA hoạt động với e nhỏ còn thuật toán sinh mã của Rabin nhanh hơn nhiều so với RSA là hệ đòi hỏi phải tính luỹ thừa. Thời gian giải mã thì tương đương nhau Nhược điểm: Vì phương trình giải mã cho 4 nghiệm nên làm khó dễ việc giải mã. Thông thường, bản rõ trước khi được mã hoá cần được nối thêm vào đuôi một chuỗi số xác định để làm dấu vết nhận dạng (chẳng hạn nối thêm 20 số 0 – như vậy trong số 4 nghiệm giải ra, chuỗi nào tận cùng bằng 20 con 0 thì đúng là bản rõ cần nhận). 2 Do phần này chỉ có mục đích giới thiệu tóm tắt nên ở đây không đi sâu hơn vào công thức tính nghiệm Y Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 15 - Vì lý do này nên Rabin thường được dùng chủ yếu cho chứng thực (chữ ký điện tử). El-Gamal Tạo khoá: Alice chọn một số nguyên tố p và hai số nguyên ngẫu nhiên g và u, cả hai đều nhỏ hơn p. Sau đó tính y =gu (mod p) Bây giờ khóa công khai của Alice được lấy là (p,g,y), khoá mật là u. Sinh mã: 1. Nếu Bob muốn mã hoá một tin X để truyền cho Alice thì trước hết anh ta chọn một số ngẫu nhiên k sao cho (k,p-1) =1 2. Tính a=gk (mod p) b=ykX (mod p) Mã là Y=(a,b) và có độ dài gấp đôi bản rõ. Giải mã: Alice nhận được Y= (a,b) và giải ra X theo công thức sau: (mod p) Ví dụ 3.9: p=11, g=3, u=6. Thế thì y=36=3 (mod 11). Khoá công khai là (p,g,y)=(11,3,3) còn khoá bí mật là u=6. Để mã hoá cho tin X=6, Bob chọn ngẫu nhiên k=7 và tính a=37=9(mod 11), b=376 = 10 (mod 11) Mã là (a,b) = (9,10) Bây giờ Alice nhận được (a,b) sẽ giải mã như sau X = b/(au) = 10/(97) = 10 5 =6 (mod 11) BÀI TẬP CHƯƠNG 1. Hãy hoàn thiện nốt một chứng minh tính đúng đắn của thuật toán GCD với phần bắt đầu như sau: Chú ý rằng tại mỗi bước lặp thứ i ta có thể biểu diễn các giá trị hiện thời như sau (chỉ số i viết trên là chỉ giá trị tại bước lặp thứ i) ݊1 = ܽ1 × ݊1 ܾ1 × ݊2 ݊2 = ܽ2 × ݊1 ܾ2 × ݊2 Lấy đẳng thức trên trừ đi q lần đẳng thức dưới, trong đó q là thương số của phép chia giá trị hiện thời (vòng lặp i) của n1 và n2, ta được: ݊2+1 = ݊1 − ݍ() × ݊2 Chú ý rằng: ݊1+1 = ݊2 Từ đó sẽ suy ra: ܽ2+1 = ܽ1 − ݍ() × ܽ2 ua b X Nguyễn Khanh Văn & Trần Đức Khánh Mật mã và An toàn Thông tin ĐHBKHN-2012 Chương III - 16 - 2. Chọn một số ngẫu nhiên M trong khoảng từ 5 đến 20. Thực hiện các công việc sau: a) Bạn hãy xây dựng một vector siêu tăng có 5 thành phần trong đó có một thành phần có giá trị đúng bằng M của bạn và thành phần cuối cùng là 60. Hãy cho xem các phép tính để kiểm tra tính siêu tăng. b) Dựa trên vector này bạn hãy xây dựng một hệ khoá công khai theo phương pháp của Merkle-Hellman (nguyên tắc từ bài toán đóng thùng). Hãy sử dụng thuật toán GCD mở rộng để tính giá trị nghịch đảo đồng dư. c) Viết M của bạn dưới dạng nhị phân và gọi X là giá trị 5 bit cuối cùng. Bạn hãy sử dụng hệ khóa công khai vừa xây dựng ở trên để tính mã Y từ X. d) Với giá trị Y tìm được ở câu trên, hãy cho biết cách giải mã để thu được tin X ban đầu. 3. Cho p=11, q=17 trong hệ RSA. Chọn một số ngẫu nhiên M trong khoảng từ 5 đến 20. Hãy thực hiện các công việc sau: a) Xây dựng khoá công khai và bí mật của hệ (chú ý áp dụng thuật toán GCD mở rộng). b) Tính MÃ của tin M c) Nếu sử dụng hệ này để làm chữ ký, xác định chữ ký cho M nói trên (chú ý dùng giải thuật nhạnh để tính lũy thừa đồng dư). d) Nếu muốn gửi một thông báo M vừa có đảm bảo xác thực vừa có tính mật, cần thực hiện cụ thể thế nào? 4. Hãy lập luận chứng minh cụ thể là bài toán đóng thùng với một vector mang là siêu tăng sẽ luôn là dễ nếu có nghiệm 5. Biết rằng hàm (n) có nhân tính, có nghĩa là (m*n) = (m) * (n) với mọi m và n nguyên mà gcd(m,n)=1. Hãy chứng minh rằng (n)= (p-1)* (q-1) khi n= p*q với p, q là số nguyên tố
File đính kèm:
- giao_trinh_an_toan_va_bao_mat_thong_tin_nguyen_khanh_van.pdf