Bài viết được lấy từ https://truongphuoc.wordpress.com/2024/08/05/blockchain-20-3-chu-ky-dien-tu-rsa/

Mở bài

Chữ ký điện tử RSA là chữ ký điện tử đầu tiên được sử dụng. Trong bài viết này chúng ta cùng tìm hiểu về cách chữ ký này hoạt động nhé.

Nhắc lại kiến thức hệ mật RSA

Trong hệ mật RSA, ví dụ ta có

• privatekey: $(N, D)$
• publickey: $(N, E)$
• plaintext: $T$ (T < N)

Công thức mã hóa: $C = T^E \;mod \;N$

Công thức giải mã: $T = C^D\; mod \;N$

Đối với công thức trên thì chỉ người nào biết private key $(N, D)$ bằng bao nhiêu thì mới giải mã được C.

Chúng ta cùng tư duy ngược lại:

• Nếu An sử dụng private key $(N, D)$ để mã hóa, thì cả Bình, Công hoặc bất kỳ ai cũng có thể sử dụng public key để giải mã, tại vì public key là công khai.
• Hay nói cách khác: Nếu An sử dụng private key $(N, D)$ để mã hóa T, ra được C, sau đó gửi cả C và T cho Bình, Công,... Thì bất kỳ ai cũng có thể sử dụng public key của An để giải mã C ra T', sau đó so sánh với T để xác định người gửi có phải An không.
• Lý do: Nếu T' = T suy ra C là bản mờ của T được mã hóa bởi $(N, D)$. Mà chỉ có An mới có private key $(N, D)$, do đó suy ra An là người đã mã hóa T hay An đã ký vào T

Thuật toán ký điện tử RSA

Thuật toán ký điện tử RSA như sau:

Trong hệ mật RSA, có

• public key là $(N, E)$
• private key là $(N, D)$
• Bản cần ký $T$

Công thức ký số:

$S = H(_T)^D\; mod\;N$

Trong đó $H$ là một hàm băm bấy kỳ, $H(_T)$ là giá trị của hàm băm đó.

Công thức xác minh chữ ký:

$H'(_T) = S^E\; mod\; N$

• Nếu $H'(_T) = H(_T)$ suy ra chữ ký hợp lệ.
• Nếu $H'(_T) ≠ H(_T)$ suy ra chữ ký không hợp lệ.

Ví dụ ký và xác minh RSA

Phần lý thuyết chỉ đơn giản thế thôi, giờ chúng ta hãy cùng đi qua ví dụ nha. Chúng ta cùng tiếp tục lấy lại ví dụ trong bài hệ mật RSA. Với

• Public Key $= (N,E) = (3233, 17)$
• Private Key $= (N,D) = (3233, 2753)$

Giả sử thông điệp cần ký của ta là m = 11 sử dụng hàm băm mật mã MD5, ta có như sau:

MD5(11) = 6512bd43d9caa6e02c990b0a82652dca (cơ số 16)
        = 134349327668835346876933282647662472650  (cơ số 10)
Ta thấy 134349327668835346876933282647662472650 lớn hơn N = 3233 rất nhiều.
Nếu ta sử dụng thế này thì khi xác minh H'(T) = S^E mod N thì sẽ luôn không bằng H(T)
Tại vì mod N nên H'(T) luôn nhỏ hơn N.
Ta có thể giảm giá trị của MD5(11) bằng cách mod N
MD5(m) mod N = 134349327668835346876933282647662472650 mod 3233
             = 797

Tiếp tục công thức nào
S = 797^2753 mod 3233
  = 2723

Xác minh chữ ký:
H'(T) = 2723^17 mod 3233
      = 797

Ta thấy H'(T) = MD5(m) mod N = 797
Nên kết luận chữ ký hợp lệ.

Công thức khá dễ dàng và dễ hiểu phải không nào.

Trong thực tế thì sẽ không có MD5(m) mod N như ở trên, ở trên là vì sử dụng N quá nhỏ nên mình chống cháy thôi. Trong thực tế với RSA 1028 bit thì N có giá trị là 1028 bit, tương tự với RSA 2048 bit và RSA 4096 bit. Với một số 1028 bit là một số có khoảng 300 chữ số thập phân, là nó dài thế này này

179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407537058348423606350291648944625587201265339418545245695922593080191170830436878627123364542232876353906219041874354824985666674683225727316588448562544517715525193098736241834389504620962684318490092602963280962017688885682555737004282526116857205128434804143505797387996443095760472888178743823305101951594856776267598088586338158400217105590710344598945856101297869927393402518079569111666651936713600

Trong khi đó những thuật toán băm chỉ có số bit nhỏ hơn nhiều

• MD5: 128 bit
• SHA256: 256 bit
• SHA512: 512 bit
• ...

Bạn có thể thấy ví dụ một con số của MD5(11) ở trên, chỉ là muỗi so với RSA thôi phải không nào.

So sánh ký số RSA và ECDSA

Kết luận

Chúng ta đã đi qua được thuật toán ký số RSA, quả là đơn giản phải không nào. Thuật toán ký số RSA dựa trên hệ mật RSA, nếu có bạn nào đọc tới đây mà vẫn lơ mơ xin xem lại các bài toán học trong mật mã và hệ mật RSA nha.

Link bài viết gốc https://truongphuoc.wordpress.com/2024/08/05/blockchain-20-3-chu-ky-dien-tu-rsa/