Mã hóa RSA và Chữ ký số – Viblo

Bài gốc: https://manhhomienbienthuy.github.io/2017/02/20/he-ma-hoa-rsa-va-chu-ky-so.html tác giả)

Ở bài viết trước chúng ta đã tìm hiểu về chứng chỉ https và ssl. Trong số đó, chúng tôi đã biết rằng chứng chỉ ssl yêu cầu xác thực chữ ký số. Trên thực tế, không chỉ trong chứng chỉ SSL, chữ ký số cũng là một công nghệ rất quan trọng, có ứng dụng trong nhiều lĩnh vực khác nhau. Trong bài viết này, chúng ta sẽ xem xét kỹ hơn về chữ ký điện tử cũng như cách tạo và xác minh chúng.

Mật mã bất đối xứng, còn được gọi là mật mã khóa công khai, là một hệ thống mã hóa sử dụng một cặp khóa để mã hóa và giải mã: khóa chung để mã hóa và khóa riêng để giải mã.

Trong hệ thống mã hóa này, bất kỳ ai cũng có thể sử dụng khóa chung để mã hóa tin nhắn và gửi cho người nhận. Nhưng rõ ràng chủ sở hữu của khóa riêng sẽ giữ bí mật và chỉ anh ta mới có thể giải mã được.

Thông thường, cặp khóa được tạo này sẽ cố gắng gây khó khăn (gần như không thể) để lấy khóa riêng từ khóa chung. Vì vậy, bất kỳ kẻ tấn công nào lấy được khóa chung (dễ dàng) đều không thể lấy được khóa riêng được sử dụng để giải mã.

Tuy nhiên, thực tế phũ phàng hơn nhiều. Hoàn toàn không có thuật toán nào đạt được lý tưởng như vậy. Các thuật toán tạo khóa hiện tại chỉ bảo vệ chống lại các kỹ thuật bẻ khóa thông thường sử dụng máy tính cá nhân. Với sự phát triển của siêu máy tính và máy tính lượng tử, hệ thống mật mã bất đối xứng cũng đang phải đối mặt với nhiều thách thức.

Chữ ký số là một dạng chữ ký điện tử. Nó là một dạng dữ liệu được sử dụng để xác thực các dữ liệu khác. Chúng ta sẽ xem cách xác thực hoạt động trong phần tiếp theo.

Chữ ký số sử dụng một hệ thống mã hóa bất đối xứng. Trong hầu hết các trường hợp, nó thậm chí còn kiểm tra tính toàn vẹn của dữ liệu. Chữ ký điện tử tương tự như chữ ký viết tay theo nhiều cách, nhưng khó cài đặt và sử dụng hơn nhiều.

Trong phần tiếp theo, chúng ta sẽ tìm hiểu cách sử dụng hệ thống mã hóa bất đối xứng cổ điển rsa cho chữ ký điện tử.

RSA là một hệ thống mã hóa bất đối xứng được phát triển bởi Ron Rivest, Adi Shamir và Leonard Adleman (tên của họ cũng là tên viết tắt của ba tác giả), được sử dụng rộng rãi trong công nghệ mật mã và chữ ký điện tử. . Trong hệ thống mật mã này, khóa công khai có thể được chia sẻ công khai cho mọi người. Hoạt động của rsa dựa trên 4 bước chính: tạo khóa, chia sẻ khóa, mã hóa và giải mã.

Khóa cơ bản của sinh khóa trong rsa là tìm bộ ba số tự nhiên e, d, n sao cho:

Một điểm nữa không thể không kể đến đó là tính an toàn của d phải được đảm bảo để dù biết e, n hay cả m thì cũng không tìm thấy d.

Khóa rsa cụ thể được tạo như sau:

• Chọn 2 số nguyên tố p và q
• Tính n = pq. Sau này n sẽ được sử dụng làm mô đun trong khóa công khai và khóa riêng.
• Tính các số giả nguyên tố bằng cách sử dụng phi hàm Carmichael như sau: λ(n) = bcnn(λ(p), λ(q)) = bcnn(p − 1, q − 1). Giá trị này sẽ được giữ kín.
• Chọn một số tự nhiên e trong khoảng (1, λ(n)) sao cho ucln(e, λ(n)) = 1, tức là e và λ(n) nguyên tố cùng nhau.
• Tính số d sao cho d ≡ 1/e (mod λ(n)) hoặc dễ viết hơn là de ≡ 1 (mod λ(n)). Số d được gọi là nghịch đảo modulo của e (modulo mod λ(n)).

Khóa chung là bộ (n, e) và khóa riêng là bộ (n, d). Chúng ta cần lưu khóa và các số nguyên tố p và q thật cẩn thận, vì từ chúng chúng ta có thể dễ dàng tính ra khóa.

Trong thực tế, chúng ta thường chọn e nhỏ hơn để mã hóa và giải mã nhanh hơn. Một giá trị thường được sử dụng là e = 65537. Ngoài ra, chúng ta có thể sử dụng hàm không phải Euler φ(n) = (p − 1)(q − 1) để tính số giả nguyên tố và sử dụng nó. Làm λ(n). Vì φ(n) là bội số của λ(n), nên một số d với de ≡ 1 (mod φ(n)) cũng sẽ thỏa mãn d ≡ 1/e (mod λ(n)). Tuy nhiên, một số tác dụng phụ của việc này là d thường sẽ trở nên lớn hơn mức cần thiết.

mã hóa và giải mã

Trong phần này, chúng ta sẽ tìm hiểu cách mã hóa bằng khóa chung (n, e) và giải mã bằng khóa riêng (n, d).

Nếu có bản rõ m thì nó được biến đổi thành số tự nhiên m trong khoảng (0, n) sao cho m và n nguyên tố cùng nhau. Điều này có thể dễ dàng thực hiện bằng cách thêm các kỹ thuật đệm. Tiếp theo, chúng tôi chuyển đổi m, sang c như sau:

Sau đó gửi giá trị c đến người nhận.

Bộ thu sẽ giải mã từ c thành đầu ra m như sau:

Tin nhắn từ m có thể nhận được bằng cách đảo ngược phần đệm

Hãy lấy một ví dụ đơn giản:

Ta chọn e = 5 vì ucln(5, 24) = 1 và cuối cùng là d = 29 vì ed – 1 = 29×5 – 1 chia hết cho 24.

Giả sử m = 32 (khoảng trắng), chúng tôi mã hóa m thành

giải mã c để lấy m

Đây là gạo chính gốc. Bạn có thể mth các giá trị khác nhau và xem thuật toán có đúng không. Tất nhiên, nó đã được chứng minh. Chứng minh rằng rsa hoạt động chính xác là một vấn đề toán học khá phức tạp, không được thảo luận chi tiết trong bài viết này.

Tính bảo mật của RSA phụ thuộc phần lớn vào khả năng phân tích lượng lớn dữ liệu của nó. Vì chúng tôi công khai thông tin này nên việc tiết lộ thông tin cá nhân là không thể tránh khỏi nếu quá trình phân tích thừa số nguyên tố diễn ra đơn giản.

Do đó, khi sinh khóa ta cần chọn ngẫu nhiên các số nguyên tố p và q. Bản thân hai số nguyên tố cũng rất lớn và để làm cho việc phân tích trở nên khó khăn hơn, hai số nguyên tố sẽ không có cùng độ dài. PC có thể sẽ không thể thực hiện công việc một cách hiệu quả trong tương lai gần.

Tuy nhiên, với sự phát triển của công nghệ, ngày càng có nhiều siêu máy tính ra đời. Cùng với các máy tính lượng tử của chúng tôi, các phép tính có thể được thực hiện ở tốc độ cao hơn nhiều, điều này có thể phá vỡ tính bảo mật của rsa.

Thuật toán của Shor đã được phát triển từ năm 1993 và đã chỉ ra rằng máy tính lượng tử có thể giải các bài toán phân tích thừa số trong thời gian đa thức. May mắn thay, đây chỉ là những lý thuyết, vì máy tính lượng tử còn lâu mới hoàn hảo và trong nhiều năm tới.

Một câu hỏi thú vị là liệu vai trò của khóa công khai và khóa riêng có thể hoán đổi cho nhau hay không. tức là chúng ta có mã hóa bằng khóa riêng và giải mã bằng khóa chung không? Câu trả lời là có. Tuy nhiên, không ai làm điều đó vì nó quá dễ dàng: lấy khóa riêng từ khóa chung thì khó, nhưng lấy khóa chung từ khóa riêng thì dễ. Nếu chúng tôi đưa khóa riêng của mình cho người khác (để họ mã hóa nó), một người đàn ông ở giữa có thể dễ dàng tìm ra khóa chung và thay đổi hoàn toàn cuộc trò chuyện của chúng tôi. Điều đó quá nguy hiểm.

Tuy nhiên, trong một số trường hợp, chúng tôi đảo ngược vai trò của khóa riêng và khóa chung như thế này. Đây là nơi chúng tôi sử dụng chữ ký điện tử.

Việc sử dụng hệ thống mã hóa rsa để ký và xác thực chữ ký số cũng tương tự như quá trình mã hóa và giải mã ở trên. Tuy nhiên, vai trò của khóa công khai và khóa riêng thay đổi một chút.

Để tạo chữ ký, người gửi sẽ sử dụng khóa riêng và người nhận sẽ sử dụng khóa chung để xác thực chữ ký.

Tuy nhiên, do độ dài của tin nhắn nên cần có thời gian để mã hóa toàn bộ tin nhắn. Vì vậy, trong thực tế, chữ ký điện tử thường sử dụng phương pháp mã hóa giá trị băm của thông điệp. Điều này mang lại nhiều lợi ích, chẳng hạn như:

• Hàm băm là hàm một chiều, vì vậy ngay cả khi bạn có hàm băm, bạn cũng không có cách nào biết được thông báo ban đầu trông như thế nào.
• Độ dài hàm băm là cố định và thường nhỏ, vì vậy các số 0 chiếm nhiều không gian.
• Băm cũng có thể được sử dụng để kiểm tra xem một tin nhắn nhận được đã hoàn tất chưa?

Chữ ký số có giá trị hơn chữ viết tay. Có lẽ vì điều này mà chữ ký điện tử phức tạp hơn một chút so với chữ viết tay truyền thống.

xác định nguồn

Mã hóa bất đối xứng cho phép ký bằng khóa riêng mà chỉ chủ sở hữu mới biết. Sau khi người nhận nhận được gói tin, nó sẽ xác minh chữ ký bằng khóa công khai được giải mã, sau đó tính toán hàm băm của thông điệp gốc và so sánh nó với hàm băm trong gói tin nhận được. Hai chuỗi này phải khớp với nhau. Tất cả các hệ thống mật mã rsa vẫn có một số thách thức về bảo mật, nhưng nó vẫn rất an toàn.

dữ liệu nguyên vẹn

Các tin nhắn được gửi bởi chủ sở hữu khóa riêng rất khó bị giả mạo. Bởi vì nếu thông báo thay đổi, hàm băm cũng phải thay đổi. Tất nhiên, một kẻ nghe trộm trên mạng có thể tìm cách đọc được tin nhắn gốc và hàm băm của nó. Nhưng anh ta không thể thay đổi tin nhắn vì anh ta không có khóa riêng để sửa đổi chữ ký điện tử cho phù hợp.

Chữ ký số là không thể hủy bỏ

Trong các giao dịch, các gói dữ liệu được ký điện tử, giúp dễ dàng tìm thấy nguồn của chữ ký. Vì khóa riêng là bí mật và chỉ chủ sở hữu của nó biết nên họ không thể phủ nhận rằng chữ ký không phải do họ cấp. Tương tự như trên, rsa hay bất kỳ hệ thống mã hóa nào khác đều có vấn đề về bảo mật nên không thể đảm bảo độ chính xác tuyệt đối.

Công nghệ luôn thay đổi từng ngày và các giao dịch điện tử, đặc biệt là thương mại điện tử không ngừng diễn ra từng ngày từng giây. Chữ ký điện tử là một kỹ thuật cho phép xác định chủ sở hữu của dữ liệu cụ thể và kiểm tra tính toàn vẹn của dữ liệu.

Ở nước ta, chữ ký số được sử dụng rộng rãi trong hoạt động ngân hàng và kế toán. Nhưng trong tương lai gần, khi chúng ta tiến tới một thế giới không có bút và giấy, chữ ký điện tử có thể trở nên phổ biến hơn.