在多元公鑰密碼學中，為什麼我們不能使用相同的公鑰進行簽名和加密？
在多元公鑰密碼學中，為什麼我們不能使用相同的公鑰進行簽名和加密？
我讀到公共多項式的簽名 $ P:\mathbb{F}^n\rightarrow \mathbb{F}^m $ 有 $ n\geq m $ 而對於加密 $ m\geq n $ .
對於簽名方案，函式 $ P $ 需要是滿射的，即對於輸出空間的每個元素，至少存在一個產生該輸出的輸入。這樣簽名者就能夠對對應於任何輸出值的數據進行簽名，即對於任何給定的目標值 $ h $ , 簽名者可以找到 $ x $ 這樣 $ P(x)=h $ . 如果函式不是滿射的，就會有一些簽名者無法生成有效簽名的值，即 $ h $ 沒有 $ x $ 存在。一個簡單的計數論證表明，由於這個原因 $ n\ge m $ 對於簽名方案。
對於加密方案，函式 $ P $ 需要是單射的，即對於每個可能的輸出，最多有一個輸入產生它。這是為了使解密器可以明確地恢復消息，即給定 $ m $ 找到獨一無二的 $ x $ 這樣 $ f(x)=m $ . 如果該函式不是單射的，則可能會產生解密無法唯一解密的消息，即存在一些消息 $ m $ 為此 $ f(x_1)=f(x_2)=m $ 並且解密器無法判斷預期的消息是否是 $ x_1 $ 或者 $ x_2 $ . 一個簡單的計數論證再次表明 $ m\ge n $ 用於公鑰加密方案。
我們還看到使用 $ P $ 對於簽名和加密， $ P $ 必須是雙射的（存在 $ P $ 和 $ m=n $ 它們不是雙射的，因此既不適合簽名也不適合加密）。雖然確實存在雙射多元映射，但很難找到一個我們可以有效且安全地隱藏逆映射的映射。出於這個原因，簽名和加密功能通常是分開的。
這是否也與普通模數攻擊有關？至少對於類似 RSA 的加密。基本上，如果 p、q 和 r 是素數（並且很大），則整數 pq 很難單獨因式分解，整數 pr 也是如此。但是 GCD(pq, pr) 很容易，並且會破壞兩個密鑰，因此您不能重用密鑰。