基於因式分解和離散對數的簽名方案的安全性
我看過這篇論文：Ismail 和 Tahat基於多個硬數理論問題的新簽名方案：
在本文中，我們提出了一種基於兩個硬數論問題的新簽名方案，即因式分解和離散對數。
似乎它是一種更加安全的簽名方案。尋找關於它實際上是多麼有用/安全的想法/見解。
雖然我看不到任何直接的弱點，但我也看不出它如何比 DSA 增加顯著的價值（雖然速度明顯較慢）。
它聲稱基於兩個難題，離散對數和因式分解。但是，它並沒有提供任何特別的證據證明如果您可以偽造簽名，您就可以解決這兩個問題。它看起來也不太可能。如果你能解決尋找價值的問題 $ K $ 在哪裡 $ K^K = x \bmod p $ （對於固定 $ x $ )，你可以鍛造（通過選擇一個隨機的 $ \nu $ , 計算 $ x = g^{\nu^e}y^{h(M)^2} $ 然後解決 $ K $ )，而且這個問題似乎不太可能簡化為離散對數或分解問題。
此外，雖然離散對數和因子分解確實是不同的問題，但它們是相關的。該論文聲稱“因式分解和離散對數不太可能同時有效地求解”，但實際上，一項進展可以同時解決這兩個問題並不是那麼不可信。例如，數字域篩的顯著加速可以解決這兩個問題（因為可以修改該算法以解決這兩個問題）。或者，如果有人製造了一台量子電腦，那麼這兩個問題都會得到解決。
此外，他們的算法的執行速度似乎不如 DSA（這不是一種特別有效的簽名算法）。原因如下：他們的算法可以被視為 DSA 的變體，除了它們在復合子組（而不是 DSA 工作的素子組）中工作。問題是：他們的子組必須很大（因為必須很難分解他們的子組；否則他們所依賴的問題之一很容易）。因此，他們需要在 2048 位子組中工作，而不是使用 256 位子組（我們可能會使用 DSA）。因為計算所花費的時間，比如說， $ K^K $ 與子組的大小成正比，他們的方案將比 DSA 花費 8 倍的時間。
此外，有時他們的算法描述有點愚蠢。採取他們的簽名生成算法；他們列出的三個步驟似乎可以概括為 $ \nu = (Kr - xh(M)^2)^d $ . 這種替代公式比將時間減半更好（因為您不必計算模平方根，我們執行一個模冪運算步驟；他們執行兩次）；你不必擔心如果 $ Kr $ 恰好不是二次餘數。我能想到使用他們的公式的唯一原因是增加某種側通道阻力；但是，如果您對此感到擔憂，那麼，必須有一種更便宜的方法。