Tôi cho rằng hệ thống chữ ký được đề xuất sẽ nhận một thông điệp $M$, chuyển đổi nó thành một số nguyên $m$ ít hơn $n$ bằng cách thêm vào một hằng số cố định $c$ ở bên trái biểu thức của $M$ như là $i$ chữ số trong một số cơ sở $b\ge2$ (cơ sở 10 trong câu hỏi) do đó $m:=c\,b^i+M$, sau đó xây dựng chữ ký $\sigma=\mathrm{Sig}(M)$ mỗi RSA trong sách giáo khoa với khóa riêng $(n,d)$, đó là $\sigma:=m^d\bmod n$; và xác minh đưa ra $(n,e)$ và $(M,\sigma)$ (hoặc chỉ $\sigma$) tính toán $\sigma^e\bmod n$ sau đó kiểm tra đó là $c\,b^i+M$. Hiện tại, tôi không xác định nếu $i$ là cố định, hoặc phụ thuộc vào $M$ (và làm thế nào).
Bằng cách thêm tiền tố đã biết, kẻ tấn công chỉ có thể giả mạo tin nhắn bằng vũ lực và kết quả là tính bảo mật của sơ đồ này tỷ lệ thuận với độ dài của tiền tố.
Để đề xuất này có bất kỳ cơ hội nào là đúng, chúng ta phải thêm "lên đến điểm tiền tố $c$ trở nên lớn đến mức nhân tử hóa của $n$ trở thành cuộc tấn công dễ dàng nhất". Tôi giả định điều này sau đây.
Đề xuất đó có vẻ đúng (nhưng chúng tôi không có bằng chứng) nếu chúng tôi coi định nghĩa về bảo mật cho chữ ký Sự tồn tại không thể giả mạo trong cuộc tấn công bằng tin nhắn đã biết, trong đó đối thủ có khóa công khai $(n,e)$ cộng với một số hợp lệ $(M_j,\sigma_j)$ cặp cho ngẫu nhiên $M_j$, và cố gắng thể hiện một $(M,\sigma)$ cặp cho $M$ không ai trong số $M_j$.
Nhưng điều đó là không chính xác nếu chúng ta lấy Sự tồn tại không thể giả mạo trong cuộc tấn công bằng tin nhắn được chọn, trong đó đối thủ được phép truy vấn chữ ký $\sigma_j$ của bất kỳ tin nhắn $M_j$ của sự lựa chọn của họ, trước khi triển lãm $(M,\sigma)$ như trên. Vấn đề là, theo mô hình bảo mật này, có những cuộc tấn công tốt hơn so với vũ phu.
- Tấn công dễ dàng nếu chúng ta cho phép $i$ là số chữ số của $M$ ở cơ sở $b$ (có thể có hoặc không triệt tiêu các số 0 đứng đầu) và sử dụng một số mũ công khai nhỏ $e$ (ví dụ: 3): kẻ tấn công tìm thấy chữ ký của bất kỳ tin nhắn nào $M$ nó thấy phù hợp (lên đến một số giới hạn kích thước) từ chữ ký của tin nhắn $M'=M\,b^e$ nếu $M$ đủ ngắn để đáp ứng $c\,b^{i'}+M'=c\,b^{i+e}+M\,b^e<n$ yêu cầu, kể từ khi $\mathrm{Sig}(M')\,b^{-1}\bmod n=\mathrm{Sig}(M)$.
- Đối với cố định $i$, mọi thứ khó khăn hơn, nhưng Desmedt và Odlyzko tấn công cho phép giả mạo với độ khó thấp hơn nhiều so với vũ phu, không tăng gấp đôi khi chúng tôi cho phép $c$ lớn gấp đôi và thậm chí là cấp số nhân với $\log_2(c)$.
- Cuộc tấn công trước đó trở nên dễ dàng hơn nếu chúng ta cho phép $i$ cố định cho một $c$, nhưng bằng kích thước của $c$ ở cơ sở $b$.
Biết tiền tố không phải là một lợi thế để ép buộc các tin nhắn (ngoài thực tế là kẻ tấn công biết đầu ra cần trông như thế nào).
Động lực của chữ ký là cho phép xác minh mà không có thông tin bí mật và việc đặt tiền tố bí mật đi ngược lại điều đó. Tôi sẽ cho rằng nó tuy nhiên.
Sau đó, tuyên bố đó là chính xác ngoại trừ các cuộc tấn công chỉ có khóa không thực tế, nhưng hãy tranh luận vì lý do khiến nó đúng: kẻ thù biết ít nhất một $(M_0,\sigma_0)$ cặp ngoài khóa công khai $(n,e)$, và do đó họ có thể dễ dàng tìm thấy tiền tố $c$ bằng máy tính ${\sigma_0}^e\bmod n$.
