B O M T THÔNG TIN BÀI 4: MÃ HÓA CÔNG KHAI Nguyễn Hữu Thể 1 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 Demo RSA Số nguyên rất nhỏ 19 Demo RSA ậ Số nguyên rất nhỏ int[] sinhKhoaRSA(){ //Chọn 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); } n = 15 e=3 d=3 C = 12 MM = 3 22 Demo RSA Số nguyên nhỏ + BigInteger 23 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 : 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 : 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 } 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]; Demo RSA ậ Số nguyên nhỏ + BigInteger 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 Demo RSA Số nguyên lớn 28 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       public = 70001 Gi i thu t RSA - Code 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