Hình ảnh một dãy số nguyên tố mã hóa năm 2024

  • 1. BẢO MẬT HỆ THỐNG THÔNG TIN NHÓM 10  NGUYỄN MINH ĐẠT – N20DCCN095  ĐÀO QUỐC LUẬN – N20DCCN117
  • 2. về hệ mã hóa công khai RSA  Các thành của hệ mã hóa công khai RSA  Cách tạo khóa và một số ví dụ mã hóa RSA  Độ an toàn của hệ mã hóa công khai RSA  Ứng dụng của hệ mã hóa RSA  Nhận xét và kết luận  Demo chương trình
  • 3. hóa công khai RSA là một trong những thuật toán mã hóa phổ biến nhất hiện nay, được phát minh vào năm 1977 bởi ba nhà khoa học máy tính là Ron Rivest, Adi Shamir và Leonard Adleman tại Massachusetts Institute of Technology (MIT) tại Mỹ.  Trước đó, các hệ thống mã hóa đối xứng được sử dụng để mã hóa dữ liệu, trong đó cùng một khóa được sử dụng để mã hóa và giải mã. Tuy nhiên, vấn đề với các hệ thống mã hóa đối xứng là phải đảm bảo rằng khóa được sử dụng không bị rò rỉ cho bất kỳ ai ngoại trừ người nhận và gửi. Điều này trở thành một vấn đề lớn trong việc đảm bảo an toàn của thông tin.
  • 4. phát minh bởi ba nhà khoa học máy tính này như là một phương pháp mới cho việc mã hóa thông tin mà không cần chia sẻ khóa bí mật. Thay vào đó, RSA sử dụng một cặp khóa - một khóa công khai được chia sẻ công khai với mọi người, và một khóa bí mật chỉ được giữ bởi người sở hữu khóa.  RSA hoạt động dựa trên tính chất toán học của các số nguyên tố lớn. Quá trình mã hóa bắt đầu bằng cách chọn hai số nguyên tố lớn và tính toán tích của chúng. Tích này sẽ được sử dụng như là một phần của khóa công khai. Sau đó, tính một số khác được sử dụng để tính toán khóa bí mật. Khi một tin nhắn được mã hóa, nó sẽ được chuyển đổi thành một số nguyên và sau đó được mã hóa bằng khóa công khai. Khi tin nhắn được nhận, nó sẽ được giải mã bằng khóa bí mật.
  • 5. thành một trong những phát minh quan trọng trong lịch sử của mật mã học và đã đóng một vai trò quan trọng trong việc xây dựng nên các ứng dụng an toàn thông tin hiện đại. Nó cũng đã thúc đẩy sự phát triển của lý thuyết mã hóa công khai và là cơ sở cho nhiều thuật toán mã hóa công khai khác.  RSA được sử dụng rộng rãi trong các ứng dụng mật mã, bao gồm trao đổi khóa, chứng thực và chữ ký số. Nó cũng được sử dụng trong các ứng dụng an ninh web, bao gồm HTTPS, TLS và SSL. RSA là một trong những thuật toán mã hóa đáng tin cậy nhất và được sử dụng rộng rãi trong các ứng dụng bảo mật thông tin.
  • 6. hóa công khai RSA sử dụng một cặp khóa - một khóa công khai và một khóa bí mật. • Khóa công khai: là một chuỗi số nguyên được công khai để bất kỳ ai có thể sử dụng để mã hóa tin nhắn. Kí niệu: (e, n) • Khóa bí mật: là một chuỗi số nguyên được giữ bí mật bởi người sử dụng và được sử dụng để giải mã tin nhắn. Kí hiệu: (d, n)  Thao tác mã hóa và giải mã trong hệ mã hóa công khai RSA được thực hiện như sau: • Mã hóa: Người gửi sử dụng khóa công khai của người nhận để mã hóa tin nhắn. Để mã hóa, người gửi chuyển đổi tin nhắn thành một số nguyên và sử dụng khóa công khai của người nhận để tính toán một số nguyên mã. Số nguyên mã hóa sẽ được gửi đến người nhận. • Giải mã: Người nhận sử dụng khóa bí mật của mình để giải mã tin nhắn. Để giải mã, người nhận tính toán một số nguyên giải mã. Số nguyên giải mã sẽ chính là tin nhắn ban đầu.
  • 7. trong hệ mã hóa công khai RSA bao gồm các bước sau đây: • Bước 1: Chọn hai số nguyên tố lớn ngẫu nhiên p và q (p != q) • Bước 2: Tính n = p*q. • Bước 3: Tính φ(n) = (p-1)*(q-1). • Bước 4: Chọn một số nguyên tố e sao cho 1 < e < φ(n) và e là số nguyên tố cùng nhau với φ(n). • Bước 5: Tính d, sao cho (d*e) mod φ(n) = 1. Tức là d là nghịch đảo modulo của e mod φ(n).
  • 8. bước tính toán trên ta thu được 2 khóa: ◦ Khóa công khai (public key): (e, n) ◦ Khóa bí mật (private key): (d, n)  Sau khi có được 2 khóa như trên ta có thể tiến hành mã hóa và giải mã theo công thức sau: ◦ Mã hóa: c = m^e mod n (c là mã hóa của thông điệp m) ◦ Giải mã: m = c^d mod n (m là thông điệp đã được giải mã)
  • 9. là những điều cần lưu ý khi tạo khóa: ◦ Các số nguyên tố p và q thường được chọn bằng phương pháp thử xác suất bằng các thuật toán sinh số nguyên tố lớn phổ biến hiện nay như thuật toán Miller-Rabin, eliptic,… ◦ Sử dụng thuật toán bình phương và nhân để tính nhanh các phép tính lũy thừa của một số modulo với n ◦ Sử dụng giải thuật Euclid mở rộng để tính nhanh d và e
  • 10. có một thông điệp m = 23 và muốn gửi cho Alice một cách bí mật. Nhưng vì khoảng cách địa lý giữa 2 bên quá lớn nên Bob không thể trực tiếp gửi cho Alice được, do đó Bob đã quyết định gửi mã thông điệp này cho Alice qua mạng Intenet. Bạn hãy giúp Bob bằng một cách nào đó để thông điệp của Bob được bảo mật và không bị bên thứ 3 đọc được. Bài giải: Ta sẽ dùng hệ mã hóa để mã hóa thông tin cho Bob cụ thể ở đât là hệ mã hóa RSA.
  • 11. = 11, q = 31  Tính n = p*q = 11*31 = 341  Tính φ(n) = (p-1)(q-1) = (11-1)(31-1) = 300  Chọn e = 7 (vì 1 < e < φ(n) và gcd(e, φ(n) ) = 1)  Tính d: ◦ Sử dụng giải thuật Euclid mở rộng ta có phương trình đi-ô-phăng: k* φ(n) + e*d = gcd(e, φ(n))  300x + 7y = 1
  • 12. bảng sau:  Dựa bảng trên ta được d = 43  Vậy ta được 2 khóa (e, n) = (7, 341) và (d, n) = (43, 341) Bước i ri ri+1 ri+2 qi+1 yi yi+1 yi+2 1 300 7 6 42 0 1 -42 2 7 6 1 1 1 -42 43 3 6 1 0 6
  • 13. mã hóa thông điệp của Bob trước khi gửi đi (m = 23) c= m^e mod n = 23^7 mod 341 ◦ Áp dụng thuật toán bình phương và nhân ta có: 7 = 1112 Vậy c = 122 b[i] p = 𝒑𝟐 p = p mod 341 p*23 p = mod 341 1 1 1 23 23 1 529 188 4324 232 1 53824 287 6601 122
  • 14. được c = 2 mà Bob đã gửi tới, sau đó tiến hành giải mã để xem được thông điệp m m = c^d mod n = 122^43 mod 341 ◦ Áp dụng thuật toán bình phương và nhân ta có:  43 = 1010112 Vậy m = 23 trùng khớp với thông điệp m mà Bob đã gửi b[i] p = 𝒑𝟐 p = p mod 341 P*122 p = mod 341 1 1 1 122 122 1 14884 221 26962 23 0 529 188 188 1 35341 221 26962 23 0 529 188 188 1 35341 221 26962 23
  • 15. hóa công khai RSA là một trong những hệ thống mã hóa được sử dụng rộng rãi và phổ biến nhất hiện nay. Tuy nhiên, nó cũng đối mặt với những mối đe dọa đáng kể từ các cuộc tấn công của kẻ tấn công thông minh và năng động.  Độ an toàn của hệ mã hóa RSA phụ thuộc vào độ dài khóa. Trong hầu hết các trường hợp, độ an toàn của RSA được đảm bảo bởi độ dài khóa được sử dụng. Điều này có nghĩa là nếu khóa đủ dài, thì việc giải mã sẽ trở nên rất khó khăn, thậm chí là không thể thực hiện được trong thời gian ngắn.
  • 16. máy tính mạnh nhất thế giới là Fugaku, được phát triển bởi Riken và Fujitsu ở Nhật Bản. Theo thông tin được công bố, Fugaku có thể thực hiện khoảng 442,01 nghìn tỷ phép tính mỗi giây (442,01 petaflops).  Tuy nhiên, thời gian giải mã RSA phụ thuộc vào độ dài của khóa. Dưới đây là bảng thống kê thời gian ước tính để giải mã RSA với máy tính mạnh nhất hiện nay với các khóa có độ dài khác nhau:
  • 17. thống kê trên, có thể thấy độ an toàn của hệ mã RSA là rất cao và rất khó bị tấn công. Độ dài khóa Thời gian giải mã 1024 bit Khoảng 400 triệu năm 2048 bit Khoảng 3,6 tỷ năm 3072 bit Khoảng 200 tỷ năm 4096 bit Khoảng 3 triệu tỷ năm
  • 18. là một số hình thức tấn công phổ biến đối với RSA: ◦ Tấn công brute-force: Kẻ tấn công cố gắng giải mã RSA bằng cách thử tất cả các khóa có thể có. Điều này yêu cầu một lượng tính toán lớn và là không khả thi đối với các khóa đủ dài. ◦ Tấn công phân tích theo giá trị riêng: Kẻ tấn công cố gắng tính toán các giá trị riêng của khóa công khai RSA và từ đó tính toán khóa bí mật. Tuy nhiên, việc tính toán các giá trị riêng cần một lượng tính toán lớn và không khả thi đối với các khóa đủ dài. ◦ Tấn công phân tích theo chu kỳ: Kẻ tấn công sử dụng thuật toán Euclid mở rộng để tìm thấy khóa bí mật RSA dựa trên một chu kỳ của khóa công khai. Tuy nhiên, để thành công, kẻ tấn công cần phải biết chu kỳ này, điều này là rất khó trong các hệ thống RSA đúng.
  • 19. hóa công khai RSA có nhiều ứng dụng, trong đó có các ứng dụng chung như: ◦ Chứng thực: RSA được sử dụng để chứng thực truy cập vào các hệ thống, tài khoản ngân hàng trực tuyến, email và các dịch vụ trực tuyến khác. Khi đăng nhập, hệ thống sẽ sử dụng khóa công khai RSA để mã hóa thông tin và gửi cho người dùng, người dùng sẽ sử dụng khóa bí mật RSA để giải mã thông tin và chứng thực truy cập. ◦ Trao đổi khóa: RSA được sử dụng để tạo ra các khóa để bảo vệ thông tin khi trao đổi qua mạng. Khi hai bên muốn trao đổi thông tin một cách an toàn, họ sẽ sử dụng hệ thống RSA để tạo ra các khóa, sau đó sử dụng khóa đó để mã hóa và giải mã thông tin khi truyền qua mạng.
  • 20. số: RSA được sử dụng để tạo chữ ký số, một cách để xác minh tính xác thực của một tài liệu. Khi một tài liệu được ký bằng khóa bí mật RSA, người nhận có thể sử dụng khóa công khai RSA để xác minh tính xác thực của tài liệu.
  • 21. và giải mã tập tin: RSA cũng được sử dụng để mã hóa và giải mã các tập tin, để bảo vệ thông tin trên đĩa cứng hoặc truyền qua mạng. Khi sử dụng RSA để mã hóa và giải mã tập tin, người dùng sẽ tạo ra một cặp khóa công khai và bí mật RSA, sau đó sử dụng khóa đó để mã hóa và giải mã thông tin trong tập tin.
  • 22. tin đã được nêu ra trước đó ta có thể rút ra những ưu và nhược điểm của hệ mã hóa RSA như sau:  Ưu điểm: ◦ Bảo mật cao: RSA có độ an toàn rất cao, đặc biệt là với các khóa dài. Hiện nay, RSA vẫn được coi là một trong những thuật toán mã hóa công khai bảo mật nhất. ◦ Dễ triển khai: RSA được sử dụng rộng rãi và được tích hợp vào nhiều phần mềm mã nguồn mở, giúp việc triển khai nó trên các nền tảng khác nhau trở nên dễ dàng. ◦ Tính linh hoạt: RSA có thể được sử dụng cho nhiều mục đích khác nhau như mã hóa, giải mã, chứng thực, trao đổi khóa và chữ ký số. ◦ Khóa công khai được chia sẻ công khai: Khóa công khai có thể được chia sẻ công khai và sử dụng để mã hóa thông điệp, giúp việc trao đổi thông tin trở nên dễ dàng và an toàn.
  • 23. Tốn kém về tài nguyên: RSA có độ phức tạp tính toán cao, đặc biệt là khi sử dụng khóa dài, làm cho việc mã hóa và giải mã trở nên tốn kém về tài nguyên. ◦ Kích thước khóa lớn: RSA yêu cầu kích thước khóa lớn hơn so với các thuật toán mã hóa bí mật, điều này có thể ảnh hưởng đến tốc độ của việc mã hóa và giải mã. ◦ Dễ bị tấn công bằng thuật toán tìm kiếm nguyên tố lớn: RSA sử dụng việc tính toán nguyên tố lớn, vì vậy nó có thể bị tấn công bằng các thuật toán tìm kiếm nguyên tố lớn. ◦ Khó khắc phục nếu bị tấn công: Nếu khóa bị tấn công thành công, thì việc khắc phục có thể rất khó khăn và tốn kém về thời gian và tài nguyên.
  • 24. 3 chức năng như sau: ◦ Tạo khóa: bao gồm 2 khóa public key và private key ◦ Mã hóa và giải mã thông tin: Chương trình sẽ cho phép mã hóa với public key và giải mã bằng private key ◦ Chữ ký số: Chương trình cho phép người dùng ký số lên văn bản bất kì và cũng cho phép người dùng có thể xác nhận chữ ký đó.