TLDR: cuộc tấn công được coi là không dễ dàng. Có thể, hoặc không, tùy thuộc vào giả thuyết chưa được nêu ra.
Trước tiên, chúng tôi sẽ diễn đạt lại câu hỏi¹.
Chúng tôi giả sử một hệ thống mã hóa bất đối xứng, tương tự như RSA trong sách giáo khoa, với
- tạo khóa của cặp khóa công khai/riêng tư $(\mathrm{pk},\mathrm{sk})$,
- mã hóa $c:=E_\mathrm{pk}(p)$ ở đâu $p$ là bản rõ, $c$ là bản mã
- giải mã phù hợp $p:=D_\mathrm{sk}(c)$ mà làm việc cho tất cả $c$ thu được như $E_\mathrm{pk}(p)$
- ở đâu $p$ và $c$ là từ một khoảng chung $[0,n)$, với $n$ nhúng vào $\mathrm{pk}$ và $\mathrm{sk}$.
Chúng tôi cho rằng hệ thống mã hóa này an toàn theo cuộc tấn công bằng văn bản đã biết.
Chúng tôi giả định một lý tưởng hàm băm $\operatorname{Hash}$ với đầu ra trong $[0,h)$, với $h\le n$ cho tất cả $(\mathrm{pk},\mathrm{sk})$ hệ thống mã hóa tạo ra.
Chúng tôi rút ra một chữ ký số sơ đồ ở đâu
- tạo khóa giống như trong mã hóa
- chữ ký của tin nhắn $m$ Là $s=D_\mathrm{sk}(\operatorname{Hash}(m))$
- thủ tục xác minh $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ đầu ra Vượt qua nếu $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$, hoặc Hỏng nếu không thì.
Tôi nhấn mạnh rằng đây không phải là cách thông thường để tạo chữ ký: không có sơ đồ chữ ký nào được sử dụng rộng rãi khá khớp với nhau² và nhiều cách như DSA, ECDSA, EdDSA rất khác nhau.
Câu hỏi hỏi liệu hacker có thể chọn $m$ và $s$ như vậy mà $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ đầu ra Vượt qua, đó là như vậy mà $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$.
Tin vui: hệ thống chữ ký xác nhận thành công khi tin nhắn và chữ ký không bị thay đổi. Đối số: vì bộ mã hóa đầu vào và đầu ra $E_\mathrm{pk}$ giống nhau và có chức năng giải mã $D_\mathrm{sk}$ điều đó đảo ngược $E_\mathrm{pk}$ cho tất cả $p$, cả hai $E_\mathrm{pk}$ và $D_\mathrm{sk}$ là các hoán vị của tập hợp đó, cái này là nghịch đảo của cái kia. Như vậy đối với tất cả $c$ trong tập hợp đó nó giữ $E_\mathrm{pk}(D_\mathrm{sk}(c))=c$. Áp dụng điều này với $c=\operatorname{Hash}(m)$, mà điều kiện $h\le n$ làm cho có thể cho tất cả $m$, chúng tôi hiểu điều đó $E_\mathrm{pk}(s)=E_\mathrm{pk}(D_\mathrm{sk}(\operatorname{Hash}(m)))=\operatorname{Hash}(m)$, vì thế $\mathrm{Vrfy}_\mathrm{pk}(m,s)$ đầu ra Vượt qua.
Thêm một tin tốt nữa: không dễ dàng gì đối với những kẻ thù đang nắm giữ $\mathrm{pk}$ chọn $m$ và $s$ như vậy mà $\operatorname{Hash}(m)=E_\mathrm{pk}(s)$. Dường như không có gì đơn giản để làm việc:
- Khi đối thủ đầu tiên chọn tùy ý $m$và tính toán $c=\operatorname{Hash}(m)$, điều đó $c$ giống như ngẫu nhiên, ngoại trừ việc nằm trong tập hợp con thấp hơn $[0,h)$ của $[0,n)$. Lần tới khi họ cố gắng tìm $s$ với $c=E_\mathrm{pk}(s)$, về cơ bản họ đang phải đối mặt với vấn đề giải mã bản mã tùy ý và điều đó thật khó (có thể chứng minh rằng việc giải mã một bản mã tùy ý phải khó theo giả thuyết KPA mà chúng tôi đã đưa ra về mật mã).
- Khi đối thủ đầu tiên chọn tùy ý $s$ và tính toán $E_\mathrm{pk}(s)$, chúng nhận được một giá trị tùy ý $c$ Trong $[0,n)$. Không có bảo hiểm mà $c$ nằm trong phạm vi $[0,h)$ (và nếu không thì nó không thể là hàm băm của bất kỳ tin nhắn nào $m$). Ngay cả khi đối thủ có thể vượt qua rào cản đó bằng cách chọn $s$ để có thể $c$ nằm trong phạm vi $[0,h)$ (mà sách giáo khoa RSA cho phép, ví dụ: bằng cách thực hiện $s=0$ hoặc $s=1$), một hàm băm lý tưởng sao cho khó tìm thấy về mặt tính toán $m$ băm thành một giá trị nhất định tùy ý $c$ trong phạm vi đầu ra của hàm băm: đó là điện trở tạo ảnh trước đầu tiên của hàm băm.
- Khi đối thủ có được một $(m,s)$ cặp vượt qua xác minh, họ có thể cố gắng tìm $m'$ khác với $m$ với $\operatorname{Hash}(m')=\operatorname{Hash}(m)$, điều này sẽ đảm bảo rằng $(m',s)$ vượt qua xác minh. Nhưng một hàm băm lý tưởng là rất khó tính toán để thực hiện điều này: đó là khả năng chống ảnh hưởng thứ hai của hàm băm.
- Đối thủ có thể cố gắng tạo ra hai thông điệp riêng biệt $m$ và $m'$ với $\operatorname{Hash}(m)=\operatorname{Hash}(m')$, lấy chữ ký $s$ của $m$, và do đó sẽ giả mạo khác $(m',s)$ vượt qua xác minh. Điều đó dễ dàng hơn nhiều so với các cuộc tấn công trước đó (ví dụ: điều đó khả thi với SHA-1 là $\operatorname{Hash}$, khi không có cuộc tấn công nào trước đó khả thi), nhưng vẫn có một hàm băm lý tưởng sao cho khó có thể tính toán được điều này: đó là khả năng chống va chạm của hàm băm.
Những điều trên không cấu thành bằng chứng hợp lệ về bảo mật và tệ hơn: sẽ là sai lầm khi kết luận hệ thống chữ ký là an toàn. Đặc biệt, với $h=2^{256}$ (ví dụ: hàm băm là SHA-256) và khi hệ thống mã hóa là RSA trong sách giáo khoa, hệ thống chữ ký này dễ bị giả mạo. Giả sử một hệ thống có phiếu giảm giá $m$ của hình thức
MỘT Phiếu giảm giá trị giá $123.456,78, tham chiếu 4C0D5F62CAF6AF32
Giả sử người ký kiểm tra xem một đề xuất $m$ là một phiếu giảm giá được định dạng tốt, tham chiếu của nó là duy nhất, được thanh toán theo giá đã chỉ định và trong các điều kiện này, các dấu hiệu $m$. Các Desmedt và Odlyzko tấn công hãy để đối thủ chơi trò chơi đó, bằng cách mua chữ ký của các phiếu giảm giá có giá trị thấp và sử dụng các chữ ký này để tìm chữ ký của phiếu giảm giá có giá trị cao.
Tin tốt hơn: với một số giả thuyết được thêm vào, có thể chứng minh rằng hệ thống chữ ký này là an toàn. Một giả thuyết phù hợp với RSA là $h$ có gần như nhiều bit như $n$. Hệ thống chữ ký này được gọi là Băm tên miền đầy đủ. Bằng chứng rất khó, đến nỗi khi FDH lần đầu tiên được xem xét bởi Mihir Bellare và Peter Rogaway: bảo mật chính xác của chữ ký số - Cách ký với RSA và Rabin, Trong thủ tục tố tụng của Eurocrypt 1996, họ không thể chứng minh mức độ bảo mật thỏa đáng (và nghĩ ra một hệ thống chữ ký phức tạp hơn: RSA-PSS, cơ sở của chữ ký được sử dụng rộng rãi RSASSA-PSS). Nhiều năm sau, Jean-Sébastien Coron đã đạt được mức độ bảo mật tốt hơn: Về bảo mật chính xác của Full Domain Hash, Trong thủ tục tố tụng của Crypto 2000 (nhưng chữ ký RSA đã ổn định và FDH không được sử dụng rộng rãi).
¹ Sự khác biệt chính với công thức của câu hỏi:
- Chúng tôi ký bằng giải mã, không phải mã hóa, bởi vì mã hóa bằng khóa riêng và có thể giải mã bằng khóa chung mâu thuẫn với mục tiêu của mã hóa. Ngoài ra, nó không hoạt động trong thực tế, kể cả với RSA như đã triển khai, ngay cả khi chúng tôi xóa các bước đệm: định dạng của khóa chung là $(n,e)$ thường có giới hạn kích thước cho $e$, định dạng của khóa riêng là $(n,e,d,p,q,d_p,d_q,q_\text{inv})$và cố gắng chuyển khóa chung vào vị trí dự kiến có khóa riêng hoặc ngược lại, sẽ không thành công.
- Chúng tôi chỉ định một bộ bản mã hữu hạn có cùng kích thước với bộ bản rõ, do đó mã hóa xác định, nếu không, việc tạo hoặc xác minh chữ ký đôi khi sẽ thất bại trong sử dụng bình thường.
- Chúng tôi đặt thông báo làm đầu vào của quy trình xác minh, vì đó là cách xác định chữ ký trong lý thuyết và triển khai thực tế hiện đại.
² RSASSA-PKCS1-v1_5 là người duy nhất tôi biết đến gần, tuy nhiên nó $\operatorname{Hash}$ được xây dựng bằng cách nối một tiền tố tùy thuộc vào kích thước bit của $n$ và $H(m)$, ở đâu $H$ là một hàm băm tiêu chuẩn, chẳng hạn như SHA-256, do đó $\operatorname{Hash}$ không phải là một hàm băm lý tưởng, vì nó dự kiến sẽ xuất hiện giống như ngẫu nhiên trên miền đầu ra của nó.
