Câu chuyện về mã hóa ? Phát minh vĩ đại của con người trong thế kỉ 20 ? Mã hóa bất đối xứng RSA và ứng dụng trong thực tế cho https
Posted on February 10, 2023 • 12 minutes • 2487 words
Mở đầu:
Lời tựa :
Câu chuyện của mã hóa:
Mình bắt đầu kể câu chuyện ở đầu thế kỉ 20 khi con người bắt đầu sử dụng các thiết bị điện tử phục vụ cho việc giao tiếp với nhau như một nhu cầu thiết yếu của cuộc sống .
Ngay từ khi những nhà khoa học đại tài của chúng phát hiện ra trong 2 mạch điện cô lập với nhau dưới những điều kiện nhất định : một mạch điện có dòng điện đi qua có thể tạo ra dòng điện cảm ứng ở mạch điện còn lại. Chỉ với như vậy Guglielmo marconi đã phát minh ra Sóng vô tuyến . Khi đã giải quyết được việc khoảng cách trao đổi thông tin giữa những ví trí địa lý. Điều tất yếu còn lại sẽ liên quan đến việc làm thế nào ta bảo vệ thông tin khi truyền thông tin liên lạc . Vậy việc mã hóa trong cuộc sống hiện tại thì liên quan ntn nào đến bạn và tại sao người ta lại có thể bảo vệ thông tin liên lạc của bạn qua internet ? Hãy theo chân mình để khám phá từ sơ khai cho đến hiện tại nhé!
Guglielmo marconi
Định nghĩa Mã hóa
Trước hết mình sẽ định nghĩa hóa theo cách hiểu đơn giản nhất là việc biến đổi thông tin trở thành thành một dạng thông tin khác khiến cho việc bảo vệ thông tin được diễn ra . Khi thông tin được mã hóa thì việc sở hữu thông tin đó “kẻ thứ 3” cũng không thể sử dụng nó .
Mã hóa bao gồm 2 loại chính mã hóa đối xứng và mã hóa bất đối xứng:
Mã hóa đối xứng là sử dụng khóa đối xứng cho mã hóa và giải mã ( sử dụng khóa đối xứng nhau => là dùng 1 khóa )
Ví dụ : Sử dụng 1 thông tin chìa khóa(K) để mã hóa một thông tin(M) -> sinh ra thông tin mã hóa(M’) .Sau đó sử dụng thông tin chìa khóa đó(K) để giải mã thông tin mã hóa (M’) -> nhận được thông tin gốc trước khi mã hóa (M)
Mã hóa bất đối xứng là sử dụng khóa bất đối xứng việc mã hóa và giải mã ( dùng 2 khóa không giống nhau . 1 khóa cho mã hóa 1 khóa cho giải mã)
Ví dụ : Khóa công khai (K public ) và Khóa bí mật (K private) . Ta có thông tin gốc (M) sẽ bị khóa công khai (K public ) mã hóa -> sinh ra thông tin mã hóa (M’) . Sau đó thông tin mã hóa (M’) sẽ được khóa bí mật (K private) giải mã -> nhận dược thông tin gốc (M)
Câu chuyện thực tế
Như các đã biết trong phần định nghĩa. Mã hóa sẽ được chia theo phần mã hóa đối xứng và bất đối xứng. Trong hai loại này thì mã hóa đối xứng được sử dụng từ rất sớm vì nó đơn giản chỉ dùng 1 thông tin để mã hóa và giải mã ( ý tưởng mã hóa đối xứng đơn giản nên được biết đến rất sớm vd mình mã hóa “5” với khóa chung là “3” thì 5 +3 = 8 . thì khi giải mã sẽ lấy 8 - 3 =5 . tức là mã hóa như nào thì giải mã sẽ suy ngược lại ) . Trong chiến tranh thế giới thứ I và II mã hóa đối xứng được sử dụng phổ biến trong thông tin lạc giữa các bên . Nhưng yếu điểm chết người của mã hóa đối xứng là phân phối chìa khóa mã an toàn ( sử dụng 1 khóa để mã hóa và giải mã nên cả 2 đầu sử dụng đều phải có được khóa đó ). Trong chiến tranh người ta đã từng tạo ra những cuốn “sổ khóa” chỉ dành riêng cho việc phân phối chìa khóa và phải gặp mặt trực tiếp để đưa sổ . Đây là một công việc có chi phí rất cao cũng như có rủi ro khi bị lộ cuốn sổ chứa thông tin chìa khóa.
Nếu như hiện tại khi thực hiện chuyển khoản ngân hàng bạn chỉ cần ngồi nhà thực hiện 1 nút chạm cho việc gửi thông tin chuyển khoản thì tại những năm 1970 trước đó ngân hàng phải tuyển dụng những nhân viên đặc biệt . Họ rong ruổi khắp thế giới với những chiếc vali chứa đầy thông tin về các khóa mã và giao đến tận tay khách hàng để có thể thực hiện giao dịch trực tuyến.
Thách thức đưa ra :
Nếu không thể giải quyết bài toán an toàn thông tin khi trao đổi thông tin qua mạng . thì internet liệu có thể phát triển rực rỡ như hiện tại ? và nếu để mã hóa thông tin mà chi phí cao như việc đưa tận tay khóa mã thì người ta có gọi thế kỉ 21 là thế kỉ kỹ thuật số nữa không?
Làm sao để phân phối được chìa khóa mã một cách an toàn ?
Với thách thức được đưa ra như vậy con người gần như phải dành ra cả 1 thế kỉ để trả lời cho bài toán phân phối chìa khóa . Rất nhiều nhà toán học và nhà tạo mã lỗi lạc đã tin rằng đây là điều không thể. Không có bất kì phương trình toán học nào tồn tại để giải quyết bài toán không gặp mặt trực tiếp mà vẫn có thể trao đổi khóa một cách an toàn.
Giải quyết thách thức diffie-hellman :
Để giải quyết cho vấn đề mang tính thế kỉ này phải tới năm 1976 diffie , hellman và merkle mới đưa ra câu trả lời cho việc thống nhất chìa khóa mã hóa đối xứng mà không cần gặp mặt trực tiếp . Họ sử dụng các khái niệm toán học về số học đồng dư hay còn gọi là số học môđun cùng phương trình số mũ để tạo ra hàm số một chiều (hàm số đó là : Y^x (mod P)).
Khái quát đơn giản mỗi người gửi và nhận tự sinh 1 con số bí mật và sử dụng hàm số này để “trộn”. Sinh ra “dữ liệu đã trộn” và gửi dữ liệu đã trộn cho nhau . dựa vào con số bí mật của mình và dữ liệu đã trộn của đối phương sinh ra 1 số thống nhất dùng chung -> đây chính là khóa mã .
Note:
Số bí mật <=> Secret colours
Hàm số một chiều <=> Common paint
Dữ liệu trộn = Secret colour + Common paint.
Giải thích toán học:
VD: 1 . người gửi A chọn số bí mật A = “3” và người nhận B chọn số B = “6” cả 2 người đều giữ kín số bí mật số này và hàm một chiều họ thống nhất công khai là 7^x (mod 11)
2 . người A trộn A = “3” với hàm 1 chiều ta có 7^3 (mod 11) <=> 343 % 11 = 2(gọi giá trị này là @ ) . người B trộn B = “6” với hàm 1 chiều ta có 7^6 (mod 11) <=> 117649 % 11 = 4 (gọi giá trị này là $ ) . sau đó 2 người trao đổi @ và $ cho nhau
3 . Vậy Người gửi A sử dụng số bí mật A và $ tính toán như sau $^A (mod 11) <=> 4^3 % 11 = 9
4 . Vậy người nhận B sử dụng số bí mật B và @ tính toán như sau @^B (mod 11) <=> 2^6 % 11 = 9
5 . Kết thúc quá trình trao đổi khóa và khóa đối xứng được thống nhất sử dụng trong mã hóa là 9
Nhưng yếu điểm của phương pháp này là hai người là cùng phải online để có thể hoàn thành quá trình trao đổi khóa . Phát minh của diffie-hellman là tiền đề bắt buộc để Rivest , Shamir và Adleman tạo ra Mã hóa đối xứng thuật toán RSA để giải quyết hoàn hảo hơn cho phần trao đổi khóa ( RSA vẫn đang được dùng trong việc trao đổi khóa trong https hiện nay) .
RSA là gì ? Nguyên lý của Mã hóa bất đối xứng
Diffie đã đưa ra ý tưởng tuyệt vời Mã hóa bất đối xứng gồm 2 khóa : công khai và bí mật . Người nhận sẽ công khai khóa công khai bất đối xứng của mình trên mạng . Người gửi sẽ lấy khóa công khai của người nhận để mã hóa thông tin , người nhận lấy được thông tin đã được mã hóa bằng chính khóa công khai của mình và dùng khóa bí mật của mình để giải mã . Và ý tưởng tuyệt vời này đã được Rivest , Shamir và Adleman áp dụng tạo nên thuật toán RSA
Vậy thực chất RSA là gì ? tại sao có thể làm được việc khóa bí mật có thể giải mã được thông tin của khóa công khai? và nó giải quyết được vấn đề gì khi mà mã hóa xứng không làm được làm được?
Về mặt toán học nguyên lý:
Rivest , Shamir và Adleman đã sử dụng số nguyên tố và hàm một chiều để tạo ra các thông tin về khóa công khai và khóa bí mật được mô tả như sau :
1 . Người nhận B chọn ra 2 số bí mật “p” và “q” và số “e” bất kì. Rồi nhân p*q với nhau được giá trị N (p * q = N) .
2 . Người nhận B công bố “N” và “e” ra ngoài là khóa công khai . Người nhận B lưu lại “p” và “q” là khóa bí mật .
3 . Người gửi A lấy khóa công khai của B sử dụng hàm số 1 chiều để mã hóa thông tin : C = M^e (mod N) trong đó e và N là khóa công khai của người nhận . còn M là thông tin cần mã hóa tạo ra C là thông tin đã mã hóa từ M .
4 . Người nhận nhận thông tin C từ người gửi sử dụng khóa bí mật “p” và “q” để giải mã thông tin C ra M . dựa vào một số “d” đặc biệt được tính bằng công thức 1 = e x d ( mod ( bcnn(p-1,q-1) ) ) sau khi có “d” người áp dụng công thức M = C^d (mod N) để tính ra M
Note:
- bcnn(p-1,q-1) <=> bội chung nhỏ nhất của p-1 và q-1
- Với số N càng lớn thì thuật toán rsa càng an toàn
Example: Ta cần mã hóa/giải mã theo thuật toán rsa với ký tự “A” (đại diện theo hệ thập phân ký tự có giá trị là 65)Áp dụng các bước như trên mô tả :
1 . Chọn ra 2 số bí mật p = “61” và q = “53” và số công khai e = “17” . Rồi nhân p*q với nhau được giá trị N = “3233”
2 . N = “3233” và e = “17” là khóa công khai . Lưu lại p = “61” và q = “53” là khóa bí mật .
3 . Lấy khóa công khai của B sử dụng hàm số 1 chiều để mã hóa thông tin giá trị “A” là 65 với công thức : C = M^e (mod N) <=> C = (65^17) % 3233 = 2790 .
Sau khi mã hóa ta có giá trị mã hóa là 2790
4 . Ta có bcnn(p-1,q-1) <=> bcnn(60,52) = 780 .
Tính “d” bằng công thức . 1 = (e x d) % 780 <=> 1 = (17 x d ) % 780 <=> d = 413
Áp dụng công thức giải mã M = C^d (mod N) <=> M = ( 2790 ^ 413 ) % 3233 = 65
Vậy sau khi giải mã ta có giá trị 65 . Đổi ra ký tự “A”
Vậy ta đã chứng minh được nguyên lý được cách hoạt động của RSA .
Kết luận với toán mã hóa đối xứng để gửi thông tin cần phải áp trao đổi khóa dùng chung trước . Còn với RSA thì việc này là k cần thiết chỉ cần sử dụng khóa công khai là có thể giao tiếp một cách an toàn rồi .
Đi tới hiện đại và ứng dụng của https
Mặc dù mã hóa bất đối xứng có thể mã hóa mà không cần trao đổi khóa như mã hóa đối xứng .Nhưng giá thành khi sử dụng mã hóa bất đối xứng cần tính toán nhiều hơn để mã hóa và giải mã cùng 1 thông tin. Với độ an toàn của 2 loại đối xứng và bất đối xứng là tương đương . Như vậy người ta lợi dụng ưu nhược điểm của từng loại và kết hợp với nhau như sau :
Người gửi A và người nhận B.
1 . Người A và B sử dụng mã hóa đối xứng để mã hóa thông tin giữa người gửi và người nhận (vì thông tin được trao đổi mã hóa giải mã liên tục nên chọn loại mã hóa ít chi phí hơn ) Nhưng mã hóa đối xứng thì cần phải thống nhất khóa dùng chung . Bởi vậy ta sẽ lợi dụng ưu điểm của mã hóa bất đối xứng để thống nhất khóa dùng chung.
2 . Người A gửi “khóa dùng chung mã hóa đối xứng” cho người nhận B . Thông tin khóa dùng chung được mã hóa bằng “khóa công khai người nhận” B và chỉ người nhận B giải mã được bằng “khóa bí mật người nhận B” .
3 . Sau khi giải mã người nhận B và A đều có được thông tin khóa dùng chung và sử dụng thuật toán mã hóa đối xứng cùng khóa xác định để giao tiếp mã hóa / giải mã với nhau
Ứng dụng phổ biến nhất là https .
Https được hiểu cơ bản là giao thức truyền tải thông tin có mã hóa . Vậy khi bạn vào một trang web bất kì với giao thức https thực chất là bạn đã thiết lập khóa mã dùng chung chỉ có bạn và trang web đó biết theo cách thức mình đã nói như trên để giao tiếp mã hóa / giải mã .
Và đó là điều kì diệu luôn xảy ra quanh bạn mà ít khi được bạn chú ý
Hoàng Kiên 10/02/2023