Bài giảng An toàn thông tin - Chương II: Mã hóa

2Mã hóa bất đối xứng ASYMMETRIC CIPHERSChương IIMÃ HÓA(Cryptography)NỘI DUNGMở đầuMã hóa khóa công khai (Public-Key Cryptosystems)Thuật toán RSAMột số mã hóa khóa công khai khác1-2( Cryptography and Network Security: Principles and Practices (3rd Ed.) – Chapter 9, 10)Trần Thị Kim ChiĐặt vấn đềKhuyết điểm của mã hóa đối xứng:Vấn đề trao đổi khóa giữa người gửi và người nhận: Cần phải có một kênh an toàn để trao đổi khóa sao cho khóa phải được giữ bí mật chỉ có người gửi và người nhận biết. Điều này tỏ ra không hợp lý khi mà ngày nay, khối lượng thông tin luân chuyển trên khắp thế giới là rất lớn. Việc thiết lập một kênh an toàn như vậy sẽ tốn kém về mặt chi phí và chậm trễ về mặt thời gian.Tính bí mật của khóa: không có cơ sở quy trách nhiệm nếu khóa bị tiết lộ.3Trần Thị Kim ChiÝ tưởng Vào năm 1976 Whitfield Diffie và Martin Hellman đã tìm ra một phương pháp mã hóa khác mà có thể giải quyết được hai vấn đề trên, đó là mã hóa khóa công khai (public key cryptography) hay còn gọi là mã hóa bất đối xứng (asymetric cryptography).Whitfield Diffie và Martin Hellman đưa ra 2 phương án sau:4Trần Thị Kim ChiÝ tưởng Phương án 1: người nhận (Bob) giữ bí mật khóa K2, còn khóa K1 thì công khai cho tất cả mọi người biết.Alice muốn gởi dữ liệu cho Bob thì dùng khóa K1 để mã hóa. Bob dùng K2 để giải mã. Ở đây Trudy cũng biết khóa K1, tuy nhiên không thể dùng chính K1 để giải mã mà phải dùng K2. Do đó chỉ có duy nhất Bob mới có thể giải mã được. Điều này bảo đảm tính bảo mật của quá trình truyền dữ liệu. Ưu điểm của phương án này là không cần phải truyền khóa K1 trên kênh an toàn.5Trần Thị Kim ChiÝ tưởng Phương án 2: người gửi (Alice) giữ bí mật khóa K1, còn khóa K2 thì công khai cho tất cả mọi người biết. Alice muốn gởi dữ liệu cho Bob thì dùng khóa K1 để mã hóa. Bob dùng K2 để giải mã. Ở đây Trudy cũng biết khóa K2 nên Trudy cũng có thể giải mã được. Do đó phương án này không đảm bảo tính bảo mật. Tuy nhiên lại có tính chất quan trọng là đảm bảo tính chứng thực và tính không từ chối. Vì chỉ có duy nhất Alice biết được khóa K1, nên nếu Bob dùng K2 để giải mã ra bản tin, thì điều đó có nghĩa là Alice là người gửi bản mã. Nếu Trudy cũng có khóa K1 để gửi bản mã thì Alice sẽ bị quy trách nhiệm làm lộ khóa K1. Trong phương án này cũng không cần phải truyền K2 trên kênh an toànMã bất đối xứng kết hợp 2 phương án trên6Trần Thị Kim ChiMã hóa công khai(Public-Key Cryptosystems)Mã bất đối xứng là một dạng của hệ thống mật mã mà trong đó mã hóa (encryption) và giải mã (decryption) được thực hiện bằng cách dùng hai khóa (Key) khác nhauMột là khóa công khai (Public key) và một là khóa bí mật (Private key). Nó cũng được gọi tên là MÃ HÓA KHÓA CÔNG KHAI (Public-key Encryption)Có hai mode làm việc :Bảo mật : Mã bằng public key  giải mã bằng private keyXác thực : Mã bằng private key giải mã bằng public key7Trần Thị Kim ChiMã hoá bất đối xứng(asymmetric cipher model)Key 1PlaintextMessageEncryptionAlgorithmDecryptionAlgorithmKey 2PlaintextMessageTransmitted CiphertextSơ đồ mã hóa bất đối xứngMã hoá bất đối xứng“An intro to PKI and few deploy hints”“Py75c%bn&*)9|fDe^bDzjF@g5=&nmdFgegMs”“An intro to PKI and few deploy hints”Hai khoá khác nhauMã hoáGiải mãinput : văn bản thuần tuýVăn bản mật mãoutput : văn bản thuần tuýRSARSAMã hóa công khai(Public-Key Cryptosystems)Mã đối xứng có thể dùng để bảo mật (Confidentiality), chứng thực (Authentication), hoặc cả hai.Hiện nay, mã hóa khóa công khai được ứng dụng rộng rãi trong nhiều lĩnh vực, trong đó bao gồm: trao đổi, phân phối khóa, chữ ký số, bảo mật dữ liệu. Một số thuật toán mã hóa đối xứng: Diffie-Hellman, El-Gamal, RSA, ECC 10Trần Thị Kim ChiMã hóa công khai(Public-Key Cryptosystems)Mã hóa khóa công khai được dùng rộng rãi nhất là mã RSA. Độ khó của việc tấn công được dựa vào độ khó của việc tìm thừa số nguyên tố (Prime factors) của một số composite number (hợp số).11Trần Thị Kim ChiHai vấn đề của Khóa bí mậtHai cơ chế của mã hóa khóa công khai12Mã hóa công khai(Public-Key Cryptosystems)Trần Thị Kim ChiVấn đề phân phối khóa: Khó đảm bảo chia sẻ mà không làm lộ khóa bí mậtTrung tâm phân phối khóa có thể bị tấn công.Không thích hợp cho chữ ký số: Bên nhận có thể làm giả thông điệp và nói rằng nhận từ bên gửi.Mã hóa công khai(Public-Key Cryptosystems)Trần Thị Kim Chi1-13Mã hóa khóa công khaiPublic-Key CryptosystemsMã hóa khóa công khai (Public-Key Cryptosystems)Phát minh bởi Whitfield Diffie & Martin Hellman - Stanford Unit, vào năm 1976Mục tiêu là khắc phục điểm yếu của mã hóa đối xứngMột số ứng dụng cụ thể: SSL, VPN, SSH.Phương pháp: dùng hai khóa khác nhau cho quá trình mã hóa và giải mãC = E(P, K1) và P = D(C, K2)14Trần Thị Kim ChiTên gọi:Mã hóa hóa công khai (Public-key Cryptosystems)Mã hóa hai khóa (two-key Cryptosystems)Mã hóa bất đối xứng (asymmetric Cryptosystems)Hai khóa:Một khóa public-key, có thể biết bất cứ ai, và có thể được dùng để mã hóa thông điệp.Khóa private-key, chỉ được biết bởi người nhận, dùng để giải mã thông điệpBất đối xứng là bởi vì:Người mã hóa thông điệp không thể giải mã thông điệp do chính mình mã hóaNgười thẩm tra chữ ký không thể tạo ra chữ kýMã hóa công khai(Public-Key Cryptosystems)Trần Thị Kim Chi1-15Giải thuật khóa công khai gồm 6 thành phần:Đầu vào của giải thuật: Bản rõ (thông điệp có thể đọc)Giải thuật mật hóaKhóa công khai và bí mật: một cặp khóa được chọn sao cho 1 khóa dùng để mã hóa và 1 khóa dùng để giải mã.Bản mã: thông điệp đầu ra ở dạng không đọc được, phụ thuộc vào bản rõ và khóa. Nghĩa là với cùng một thông điệp, 2 khóa khác nhau sinh ra 2 bảng mã khác nhauGiải thuật giải mãGiải thuật Mã hóa công khai(Public-Key Cryptosystems)Trần Thị Kim Chi1-16Public-key encryption scheme: EncryptionTrần Thị Kim Chi1-17Public-key encryption scheme: AuthenticationTrần Thị Kim Chi1-18Đặc điểm Public-Key CryptosystemsKhông thể tính toán để tìm khóa giải mã (decryption key) khi chỉ biết thuật toán và khóa mã hóa (encryption key)Một trong hai khóa có thể dùng cho việc mã hóa (encryption), Khóa còn lại dùng cho giải mã (đối với thuật toán RSA)Trần Thị Kim Chi1-19So sánhConventional Encryption (Mã hóa thông thường)Cùng thuật toán với cùng khóa được dùng cho việc mã hóa và giải mãSender và Receiver phải cùng chia sẻ thuật toán và khóaKhóa phải giữ bí mậtKhông thể hoặc ít nhất không thực thế để giải mã một thống điệp nếu những thông tin khác có sẳn. Sự hiểu biết về thuật toán cộng với các mẫu ciphertext phải đủ thì mới xác định ra được khóa.Public-key EncryptionMột thuật toán được dùng để mã hóa và giải mã với một cặp khóa, một khóa dành cho mã hóa và một dành do giải mãSender và receiver phải có một trong cặp khóa (không giống nhau)Một trong hai khóa phải được giữ bí mậtKhông thể hoặc ít nhất không thực thế để giải mã một thống điệp nếu những thông tin khác có sẳn. Sự hiểu biết về thuật toán + một trong hai khóa + các mẫu ciphertext phải đủ thì mới có thể xác định được khóa còn lại.Trần Thị Kim Chi1-20Public-Key Cryptosystems: SecrecyTrần Thị Kim Chi1-21Public-Key Cryptosystems: AuthenticationTrần Thị Kim Chi1-22Thông điệp mã hóa được coi là một digital signature Public-Key Cryptosystems: Secrecy and AuthenticationTrần Thị Kim Chi1-23Public-Key ApplicationCó thể phân thành 3 loại: Mã hóa/giải mã (Encryption/decryption): Sender mã hóa thông điệp bằng khóa public key của người nhận. Chữ ký số (Digital signatures) – cung cấp chứng thực (authentication): Sender mã hóa thông điệp bằng khóa public key của người nhận. Chữ ký được lưu bằng một thuật toán áp đặt vào message hoặc gắn vào một khối nhỏ dữ liệu mà là một hàm của messageTrao đổi khóa (Key exchange): Hai bên hợp tác để trao đổi khóa phiên (session key)Trần Thị Kim Chi1-24Public-Key ApplicationMột vài thuật toán thì phù hợp cho tất cả các ứng dụng, loại khác thì chỉ dành riêng cho một loại ứng dụngTrần Thị Kim Chi1-25Phá mã Public-keyTấn công vét cạn (Brute Force attack): Luôn luôn là có thể về mặt lý thuyết  Sử dụng khóa đủ lớn (>512 bits) khóa lớn ảnh hưởng đến tốc độ của việc mã hóa và giải mãTìm Private key khi biết Public key:Chưa được chứng minh tính khả thi của phương pháp này26Trần Thị Kim ChiAn ninh Public-Key CryptosystemsAn toán của hệ mã hóa khóa công khai dựa trên dộ khó của việc giải bài toán ngược.Tính bền của sự an toàn này còn phụ thuộc vào phương pháp tấn công của các thám mãTrần Thị Kim Chi1-27Ưu điểm mã hóa khóa công khaiĐơn giản trong việc lưu chuyển khóa: Chỉ cần đăng ký một khóa công khai  mọi người sẽ lấy khóa này để trao đổi thông tin với người đăng ký  không cần thêm kênh bí mật truyền khóa.Mỗi người chỉ cần một cặp khóa (PR, KU) là có thể trao đổi thông tin với tất cả mọi người.Là tiền đề cho sự ra đời của chữ ký số và các phương pháp chứng thực điện tử.28Trần Thị Kim ChiHạn chế của mã Public keysTốc độ xử lýCác giải thuật khóa công khai chủ yếu dùng các phép nhân chậm hơn nhiều so với các giải thuật đối xứngKhông thích hợp cho mã hóa thông thườngThường dùng trao đổi khóa bí mật đầu phiên truyền tinTính xác thực của khóa công khaiBất cứ ai cũng có thể tạo ra một khóa công khaiChừng nào việc giả mạo chưa bị phát hiện có thể đọc được nội dung các thông báo gửi cho người kiaCần đảm bảo những người đăng ký khóa là đáng tin29Trần Thị Kim ChiNhắc lại lý thuyết số1. Phép chia modulo:Phép chia modulo là phép chia lấy phần dư. Ví dụ: 27 mod 8 = 3, 35 mod 9 = 8.Một cách tổng quát:Trần Thị Kim Chi1-30Nhắc lại lý thuyết số1. Phép chia modulo:Nếu hai số a, b có cùng số dư trong phép chia cho n thì ta nói rằng a và b là đồng dư trong phép chia modulo cho n, phép so sánh đồng dư được ký hiệu bằng dấu :Ví dụ với n = 4 ta có 4 lớp tương đương sau:Trần Thị Kim Chi1-31Nhắc lại lý thuyết số2. Một số tính chất của phép modulo:Cho a, b và n là các số nguyên, phép modulo có các tính chất:Trần Thị Kim Chi1-32Nhắc lại lý thuyết số3. Ước số:Nếu a mod n =0 (viết cách khác a 0 mod n) thì có nghĩa là a chia hết cho n, hay n là ước số của a.Ước số chung lớn nhất của hai số: ký hiệu gcd(a, b) . Để tìm USCLN của hai số a, b, chúng ta có thể dùng thuật toán Euclid .Trần Thị Kim Chi1-33Ước số chung lớn nhất(Greatest Common Divisor –gcd)Cho hai số a, b ∈ Z \{0}, c ∈ Z là ước số chung (common divisor) của a và b nếu c|a và c|bC được gọi là ước số chung lớn nhất (greatest common divisor), ký hiệu gcd(a, b), nếu nó là số nguyên lớn nhất được chia hết bởi cả a và b. Ví dụ: gcd(12,18) =6, gcd(-18,27) = 934Thuật toán Euclid tìm gcd(a,b)35Ví dụ: Tìm gcd(2740,1760) gcd (2740, 1760) = 2036Ví dụ: Tìm gcd(25,60) gcd(25,60)=537Nguyên tố cùng nhau (co-prime hay relatively prime )Hai số nguyên a, b ∈ Z \{0} được gọi là nguyên tố cùng nhau nếu gcd(a, b)=1.Ví dụ: (5,8) , (9,14) là các cặp nguyên tố cùng nhau38Phần tử nghịch đảo của phép nhân modulo:Nếu hai số nguyên a và n nguyên tố cùng nhau, thì tồn tại số nguyên w sao cho:	a.w  1 mod nTa gọi w là phần tử nghịch đảo của a trong phép modulo cho n và ký hiệu là a-139Nghịch đảo nhânmultiplicative inverseNếu tồn tại 1 số b ∈ Zn sao cho ab ≡ 1(mod n) thì b được gọi là nghịch đảo nhân của a modulo n Ký hiệu 40Nghịch đảo nhânmultiplicative inverseĐiều kiện để số a có nghịch đảo nhân khi và chỉ khi gcd(a, n)=1Ví dụ: a=22, n=25 Gcd(22,25)= 1  a có nghịch đảo nhân 8 = 22-1 (mod 25) vì 8.22 = 176 = 1 (mod 25)  8 là nghịch đảo nhân của 22 modulo 2541Cách tìm nghịch đảo nhânCách 1: dùng giải thuật Euclid mở rộng	au + pv = 1 với u,v số nguyên	u=a-1 mod p 42Thuật toán Euclid mở rộng(extended Euclidean algorithm)Cho 2 số nguyên a và b, tìm 2 số nguyên khác s và t sao cho:Thực hiện phép mod cả 2 vế	 (s x n + t x b) mod n = 1 mod n	[(s x n) mod n] + [(txb) mod n] = 1 mod n	0 + [(txb) mod n] = 1	 ( t x b ) mod n = 1  t chính là nghịch đảo nhân của bThuật toán này vừa có thể tính được gcd(a,b) vừa tính được các giá trị s và t43Thuật toán Euclid mở rộng(extended Euclidean algorithm)44Thuật toán Euclid mở rộng(extended Euclidean algorithm)45Ví dụ: a = 161 và b = 28, tìm gcd (a, b) và giá trị s và t.Giải: r = r1− q × r2; s = s1−q × s2; t = t1− q × t2  gcd (161, 28) = 7, s = −1 và t = 6.46Ví dụ: Tìm nghịch đảo nhân của 23 trong Z100.t = t1− q × t2 gcd(100, 23) là 1; nghịch đảo nhân của 23 là -13 hoặc 87.47Ví dụ: Tìm nghịch đảo nhân của 12 trong Z26.gcd(26, 2) là 2; nghịch đảo nhân không tồn tại48Cách tìm nghịch đảo nhânCách 2: dùng giải thuật tính số mũ nhanh (với p là số nguyên tố)	a1  ap-2 (mod p) 49Phần tử nghịch đảo của phép nhân modulo:Ví dụ:Trong bảng trên không tồn tại số a-1 nào sao cho a.a-1  1 mod 10. Vậy không tồn tại phần tử nghịch đảo.Để tính chúng ta dùng thuật toán Euclid mở rộng50a-1x7 mod 10a-1x2 mod 10Bài tập tìm nghịch đảo nhânCho n = 5 và a = 2. Tim nghịch đảo nhânVì gcd(2, 5) = 1, do đó 2 sẽ có nghịch đảo nhân modulo 5  3 = 2-1 (mod) 5 vì 2·3 ≡ 1 (mod 5).gcd(4, 15) = 1 vì vậy 4 có nghịch đảo nhân modulo 15. Vì 4 · 4 ≡ 1 (mod 15) nên 4 = 4-1 (mod 15)512. Hệ mã hóa RSAĐề xuất bởi Rivest, Shamir & Adleman – MIT, 1977 Là hệ mã hóa khóa công khai phổ biến nhấtLà cơ chế mã hóa khối, plaintext và ciphertext là các số nguyên từ 0 đến n-1. Kích cỡ n thường là 1024 bits, hoặc 309 chữ số thập phân (nghĩa là n hãy thực hiện giải mã để tìm ra thông điệp bản rõ ban đầu. 77Trần Thị Kim ChiBài tập7. 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: 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ác số  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. 78Trần Thị Kim ChiBài tập8. 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 79Trần Thị Kim Chi3. Mã khóa công khai khác3.1 Trao đổi khóa Diffie-Hellman (Diffie-Hellman Key Exchange)3.2 Mật mã Elgamal (Elgamal Cryptographic System)3.3 Mật mã ECC (Elliptic Curve Cryptography)Trần Thị Kim Chi1-80Trao đổi khóa Diffie-HellmanGiải thuật mật mã khóa công khai đầu tiênĐề xuất bởi Whitfield Diffie và Martin Hellman vào năm 1976Chỉ dùng để trao đổi khóa bí mật một cách an ninh trên các kênh thông tin không an ninhKhóa bí mật được tính toán bởi cả hai bênAn ninh phụ thuộc vào độ phức tạp của việc tính log rời rạc81Trần Thị Kim ChiTrao đổi khóa Diffie-Hellman82Trần Thị Kim ChiTrao đổi khóa Diffie-Hellman83Trần Thị Kim ChiTrao đổi khóa Diffie-Hellman84Trần Thị Kim ChiTrao đổi khóa Diffie-Hellman85Trần Thị Kim ChiMật mã ElGamalĐược đề xuất năm 1985, dựa vào độ phức tạp của bài toán logarit rời rạc.Mã ElGamal được dùng trong số tiêu chuẩn như: Digital Signature Standard (DSS) và S/MIME e-mail standardAn ninh của ElGamal dựa trên độ khó của việc tính logarit rời rạcTrần Thị Kim Chi1-86Mật mã ElGamalQuá trình tạo khóa của A sử dụng hệ ElGamal gồm các bước chính sau:A, B thống nhất số nguyên tố q và phần tử sinh q: Bên tạo khóa (A) chọn giá trị bí mật Xa (Xa<q-1) và tính giá trị Ya=XA mod q. Khi đó, bộ khóa K={PU,PR} của A, với khóa công khai PU={q, ,YA} và khóa cá nhân PR={XA} Trần Thị Kim Chi1-87 : Mật mã ElGamalQuá trình B sử dụng bộ khóa của A trong việc truyền dữ liệu M (M<q):B chọn giá trị k (k<q) và tính toán khóa K =(YA)K mod q, C1= k mod q, C2 =KM mod q. Khi đó (C1,C2) là bản mã được truyền điQuá trình bên nhận (A) giải mã: Tính khóa K = (C1)XA mod qTìm bản gốc theo công thức: M =(C2K-1)mod qTrần Thị Kim Chi1-88 : Mật mã đường cong EllipticECC- Elliptic Elliptic Curve CryptographyƯu điểm: ECC sử dụng khoá có độ dài nhỏ hơn so với RSA.  làm tăng tốc độ xử lý một cách đáng kể; với cùng một độ dài khoá thì ECC có nhiều ưu điểm hơn so với các giải thuật khácCó thể dụng cả 3 ứng dụng: bảo mật, trao đổi khóa, chữ ký số. An ninh ECC dựa trên vấn đề logarit đường cong ellipticTính tin cậy vẫn chưa cao bằng RSATrần Thị Kim Chi1-89So sánh chiều dài khóa ứng với an toàn tương đươngSymmetric scheme(key size in bits)ECC-based scheme(size of n in bits)RSA/DSA(modulus size in bits)5611251280160102411222420481282563072192384768025651215360Trần Thị Kim Chi1-90Câu hỏi và bài tậpKhái niệm mã hóa khóa công khai, cơ chế, các thành phần của hệ mã hóa công khaiCác đặc điểm và yêu cầu của hệ mã hóa công khaiNêu nguyên tắc của mã hóa khóa công khai? Tại sao trong mã hóa khóa công khai không cần dùng đến kênh an toàn để truyền khóa?Trong mã hóa khóa công khai, khóa riêng và khóa công khai có phải là 2 khóa tùy ý, không liên quan? Nếu có liên quan, tại sao không thể tính khóa riêng từ khóa công khai?91Trần Thị Kim ChiCâu hỏi và bài tậpNgoài vấn đề truyền khóa, mã hóa khóa công khai còn ưu điểm hơn mã hóa đối xứng ở điểm nào?Nêu nhược điểm của mã hóa khóa công khai.Hãy nêu các vấn đề về RSACho các cặp số nguyên tố sau: (13,23); (11,19); (23,29). Hãy thực hiện các bước phát sinh khóa để đưa ra khóa công khai, khóa bí mậtDùng các cặp khóa trên để mã hóa thông điệp có chiều dài 88Thế nào là độ an toàn của một thuật toán mã hóa?92Trần Thị Kim ChiTHANKS YOU