Bảo mật thông tin - Bài 4: Mã hóa công khai

1 BẢO MẬT THÔNG TIN BÀI 4: MÃ HÓA CÔNG KHAI Nguyễn Hữu Thể Nội dung  Lý thuyết số học  Mã hóa công khai  Mã hóa RSA  Demo giải thuật RSA 2 Lý thuyết số học  Phép chia modulo  Ước số  Số nguyên tố  Số nguyên tố cùng nhau  Phần tử nghịch đảo của phép chia modulo  Ước chung lớn nhất 3 Phép chia modulo 4 Ước số, số nguyên tố, số nguyên tố cùng nhau 5 Phần tử nghịch đảo của phép chia modulo 6 Ước chung lớn nhất - Thuật toán Euclid 7 Mã hóa khóa công khai  Mã hóa khóa công khai (public key cryptography)  Còn gọi là mã hóa bất đối xứng (asymetric cryptography).  Whitfield Diffie và Martin Hellman đã đề xuất 1976 Bước đột phá quan trọng trong lĩnh vực mã hóa. 8 Mã hóa khóa công khai  Sử dụng hai loại khóa trong cùng một cặp khóa:  Khóa công khai (public key) được công bố rộng rãi => dùng mã hóa thông tin.  Khóa riêng (private key) => dùng giải mã thông tin đã được mã hóa bằng khóa công khai. 9 Mã hóa khóa công khai 10 RSA  Là phương pháp mã hóa khóa công khai.  Ron Rivest, Adi Shamir và Len Adleman tại học viện MIT đề xuất năm 1977.  Hiện nay đang được sử dụng rộng rãi. 11 RSA  Giải thuật RSA thao tác trên các khối (blocks) trong đó bản rõ (plaintext) và bản mã (ciphertext) được chia ra thành nhiều khối, mỗi khối là một số nguyên trong khoảng từ 0 đến n– 1.  Để tăng tính bảo mật, n thường được chọn khá lớn.  n càng lớn thời gian để mã hóa và giải mã càng lớn.  Kích thước của n thường là 1024 bits hay 309 chữ số trong hệ thập phân 12 Mô tả giải thuật RSA  Bản rõ được chia thành từng khối để mã hóa, mỗi khối có giá trị nhỏ hơn n.  Kích thước các khối phải nhỏ hơn hoặc bằng log2(n); trong thực tế mỗi khối có kích thước k bits, với 2k< n ≤2k+1  Với một khối M của bản rõ, khối C của bản mã (tương ứng với khối M) được tính như sau: và để giải mã khối C, ta sử dụng công thức: 13 Mô tả giải thuật RSA  Cả người gởi và người nhận đều phải biết n.  Người gởi (có nhiệm vụ mã hóa bản rõ) biết giá trị của e, và chỉ có người nhận mới biết giá trị của d.  Khóa công khai (public key) KU={e, n}  Khóa bí mật (private key) KR = {d, n} 14 Giải thuật RSA 15 Giải thuật RSA  Giả sử người dùng A đã công bố khóa công khai của mình và người dùng B muốn gởi cho A thông điệp M. B sẽ dùng khóa công khai của A (gồm 2 số e và n) để mã hóa thông điệp M theo công thức:  Sau đó B gởi bản mã C cho A. Khi A nhận được C, A sẽ dùng khóa cá nhân của mình (gồm 2 số d và n) để giải mã:  Như thế A sẽ nhận được bản rõ của thông điệp M mà B muốn gởi cho anh ta. Vì d được giữ bí mật và chỉ có mình A biết d nên ngoài A ra không ai có thể giải mã được C. 16 Giải thuật RSA - Ví dụ 1 Sinh khóa: kích thước bit là 3 bit. Chọn 23 < p.q =<23+1 1. Chọn hai số nguyên tố: p= 5, q= 3. 2. Tính n = pq= 5 x 3 = 15 3. Tính hàm Euler ϕ(n) = (p – 1)(q – 1) = 4 × 2 = 8 Chọn e sao cho 1 < e < ϕ(n) và nguyên tố cùng nhau với ϕ(n) = 8; ta chọn e = 3. 4. Tính d sao cho 1 < d < ϕ(n) và ed ≡ 1 mod ϕ(n). - Tính được d = 3, vì 3 × 3 mod 8 = 1. 5. Nhận được khóa công khai KU = {e, n} = {3, 15} 6. Khóa bí mật KR = {d, n} = {3, 15}. Mã hóa: M = 2. Tính: C=M^e mod n = 2^3 mod 15 = 8 Giải mã: M = C^d mod n = 8^3 mod 15 = ((8^2 mod 15)(8 mod 15))mod 15 = (64 mod 15)(8 mod 16) mod 15 = 4 * 8 mod 15 = 2 17 Giải thuật RSA - Ví dụ 2 Sinh khóa: kích thước bit là 4 bit. Chọn 24 < p.q =<24+1 1. Chọn hai số nguyên tố: p= 7, q= 3. 2. Tính n = pq= 7 x 3 = 21 3. Tính hàm Euler ϕ(n) = (p – 1)(q – 1) = 6 × 2 = 12 Chọn e sao cho 1 < e < ϕ(n) và nguyên tố cùng nhau với ϕ(n) = 12; ta chọn e = 5. 4. Tính d sao cho 1 < d < ϕ(n) và e.d ≡ 1 mod ϕ(n) hay e.d mod ϕ(n) = 1 - Tính được d = 5, vì 5 × 5 mod 12 = 1 5. Nhận được khóa công khai KU = {e, n} = {5, 21} 6. Khóa bí mật KR = {d, n} = {5, 21}. Mã hóa: M = 2. Tính: C=Me mod n = 25 mod 21 = 11 Giải mã: M = Cd mod n = 115 mod 21 = ((112 mod 21)(112 mod 21) (111 mod 21))mod 21 = ((121 mod 21) (121 mod 21)11) mod 21 = 16x16x11 mod 21 = 2 18 19 Demo RSA Số nguyên rất nhỏ Demo RSA – Số nguyên rất nhỏ int[] sinhKhoaRSA(){ //Chọn 2 số nguyên tố p, q. Có thể viết hàm phát sinh ngẫu nhiên SNT int p = 3, q = 5; int n, e, d, phi; int a[] = new int[3]; n = p*q; phi = (p-1)*(q-1); e = timSNTCungNhau(phi); d = timNghichDaoModulo(e, phi); a[0] = n; a[1] = e; a[2] = d; return a; //trả về mảng lưu các khóa n, e, d } Demo RSA – Số nguyên rất nhỏ int maHoaRSA(int M, int e, int n){ //Mã hóa C = M^e mod n. Hàm pow: C^d < 10^19 là kích thước kiểu long long C = (long)Math.pow(M, e) % n; return (int)C; } int giaiMaRSA(int C, int d, int n){ //Mã hóa M = C^d mod n. Hàm pow: C^d < 10^19 là kích thước kiểu long long M = (long)Math.pow(C, d) % n; return (int)M; } 21 Demo RSA – Số nguyên rất nhỏ public static void main(String[] args) { RSA rsa = new RSA(); //Tạo biến đối tượng rsa thuộc lớp RSA int M = 3; //Văn bản rõ. M < p.q int a[] = rsa.sinhKhoaRSA(); int n, e, d; n = a[0]; e = a[1]; d = a[2]; System.out.println("n = " + n); System.out.println("e = " + e); System.out.println("d = " + d); int C = rsa.maHoaRSA(M, e, n); System.out.println("C = " + C); int MM = rsa.giaiMaRSA(C, d, n); System.out.println("MM = "+MM); } 22 n = 15 e = 3 d = 3 C = 12 MM = 3 23 Demo RSA Số nguyên nhỏ + BigInteger Demo RSA – Số nguyên nhỏ + BigInteger Viết lại phương thức mã hóa với kiểu dữ liệu BigInteger cho lũy thừa long maHoaRSA(int M, int e, int n){ //Mã hóa C = M^e mod n //Cách 1: Dùng class BigInteger của Java /*BigInteger MM = null; BigInteger nn = null; MM = BigInteger.valueOf(M); MM = MM.pow(e); nn = BigInteger.valueOf(n); MM = MM.mod(nn); long C = MM.longValue(); */ //Cách 2: Dùng class BigInteger của Java, rút gọn. long C = BigInteger.valueOf(M).pow(e).mod(BigInteger.valueOf(n)).longValue(); return C; } 24 Demo RSA – Số nguyên nhỏ + BigInteger Viết lại phương thức giải mã với kiểu dữ liệu BigInteger cho lũy thừa long giaiMaRSA(long C, int d, int n){ //Mã hóa M = C^d mod n long M = BigInteger.valueOf(C).pow(d).mod(BigInteger.valueOf(n)).longValue(); return M; } 25 Demo RSA – Số nguyên nhỏ + BigInteger Phương thức mã hóa và giải mã chuỗi nhiều ký tự String maHoaChuoiRSA(String M, int e, int n){ String kq = ""; for (int i = 0; i < M.length(); i++) { kq += (char)maHoaRSA(M.charAt(i), e, n); } return kq; } String giaiMaChuoiRSA(String C, int d, int n){ String kq = ""; for (int i = 0; i < C.length(); i++) { kq += (char)giaiMaRSA(C.charAt(i), d, n); } return kq; } 26 Demo RSA – Số nguyên nhỏ + BigInteger public static void main(String[] args) { RSA rsa = new RSA(); //Tạo biến đối tượng rsa thuộc lớp RSA int M = 70; //Văn bản rõ M < p.q System.out.println("M = " + M); int a[] = rsa.sinhKhoaRSA(); //Sinh khóa p = 13, q = 7 int n, e, d; n = a[0]; e = a[1]; d = a[2]; System.out.println("n = " + n + ", e = " + e + ", d = " + d); long C = rsa.maHoaRSA(M, e, n); System.out.println("C = " + C); long MM = rsa.giaiMaRSA(C, d, n); System.out.println("MM = "+MM); //Mã hóa chuỗi ký tự String M1= "TAN CONG EMAIL"; String kq1 = rsa.maHoaChuoiRSA(M1, e, n); System.out.println("Chuỗi mã hóa: " + kq1); String kq2 = rsa.giaiMaChuoiRSA(kq1, d, n); System.out.println("Chuỗi giải mã = " + kq2); } 27 28 Demo RSA Số nguyên lớn Giải thuật RSA – Code số nguyên lớn //Thuật toán RSA áp dụng trên các số nguyên lớn (BigInteger trong Java) import java.math.BigInteger; import java.security.SecureRandom; public class RSAWithBigInteger { private final static SecureRandom random = new SecureRandom(); private BigInteger privateKey_d; private BigInteger publicKey_e; private BigInteger modulus; public static final int KEY_SIZE = 1024; 29 Giải thuật RSA - Code //Constructor. Tạo khóa bí mật và khóa công khai có chiều dài KEY_SIZE public RSAWithBigInteger() { BigInteger p = BigInteger.probablePrime(KEY_SIZE, random); BigInteger q = BigInteger.probablePrime(KEY_SIZE, random); BigInteger phi = (p.subtract(BigInteger.ONE)).multiply(q .subtract(BigInteger.ONE)); modulus = p.multiply(q); publicKey_e = new BigInteger("70001"); // Đảm bảo rằng e và phi là nguyên tố cùng nhau while (!publicKey_e.gcd(phi).equals(BigInteger.ONE)) { publicKey_e = publicKey_e.nextProbablePrime(); } privateKey_d = publicKey_e.modInverse(phi); } 30 Giải thuật RSA - Code /* c = m^e mod n */ BigInteger encrypt(BigInteger message) { return message.modPow(publicKey_e, modulus); } /* m = c^d mod n */ BigInteger decrypt(BigInteger encrypted) { return encrypted.modPow(privateKey_d, modulus); } 31 Giải thuật RSA - Code public static void main(String[] args) { RSAWithBigInteger key = new RSAWithBigInteger(); System.out.println(key); // VD1: Tạo một sốnguyên lớn ngẫu nhiên để mã hóa và giải mã BigInteger message = new BigInteger(KEY_SIZE - 1, random); /* VD2: Tạo một thông điệp bằng cách biến đổi chuỗi thông điệp sang số nguyên lớn. String s = "test"; byte[] bytes = s.getBytes(); BigInteger message = new BigInteger(bytes); */ BigInteger encrypt = key.encrypt(message); BigInteger decrypt = key.decrypt(encrypt); System.out.println("message = " + message); System.out.println("encrypted = " + encrypt); System.out.println("decrypted = " + decrypt); } 32 Giải thuật RSA - Code  public = 70001  private = 17347259822064975327945070398281827308439365098415908425990346638576600832254440451588851087704385854239 78952366209725400123335648687820641928685919251717299376796681101904804066792462013289097640737946358016 72259928816497204843801231726567276157861492613550898836437940632148252329856740147250978512040429022867 43826448371361674478322001692574324823651160625614071794322630344806495743441346484427849649575202931677 46333837299278642107645684353579995875273450087503021451152603696339357056279330761347823835239638293584 5428770968695857709034631800991852169589464670556769211510087140699853811405869564331374964986809  modulus = 17779030099184057889803705259807706965023411022594281280328988668496810220328298063742421999537264669369 98735664002679136967740131825246083595407725121732663850824211560803475636953179798132532817225179470396 16694737662459127044566404914883177381392107647635854078995802143321617711926643344134284224555161303834 93904399590798559679943796746447064795413526848417628632601523214279881105642527932475513873730341977742 04019641015040173121495638649215377223892957519280811619222671099080192925059213191616944490977501171749 7590679293486082156099204781495282294608619670561874280476807068409147467866406126677340806803383  message = 46837059675147378905058652720908531267537350857420936283369653210906950594550894333844830278511573087096 63873509787367648719587864711006606002566372657497827133968724108982698314273253643609774729871442569230 1679803252274527472687811527823201946796183159125331413769266793769451396216398628109075946170173528  encrypted = 68709612144290454980208960241378779026243646178188464697231340002942280288982616266622281152132397363344 87231969921428412776264384374942610926657060520411208437000165656473879280594102593351957708042156964618 70418042855172861928630103329354334619236896339953450329456087860159867010367261030563586554432607490386 27806528076635536264964687731981904585079237044564533180409993260236818648857288097054284331432469162266 12614202352532404416099747848509803470311328600173908697489187724989806464715558939277973476201470362285 512202402233276082141906212635838564292639920383160799562359451709479977148086291302344825781914  decrypted = 46837059675147378905058652720908531267537350857420936283369653210906950594550894333844830278511573087096 63873509787367648719587864711006606002566372657497827133968724108982698314273253643609774729871442569230 1679803252274527472687811527823201946796183159125331413769266793769451396216398628109075946170173528 RSA 34 RSA 35 Bảng liệt kê các mốc phá mã RSA 36