1樓：玄星
1. 先簡單整理整理簽名演算法的框架，看看有哪些組成部分吧。
一般，乙個簽名演算法含有三個子演算法，依次是金鑰產生演算法、簽字演算法和驗證演算法。其中，
--- Gen負責根據需要（比如要求金鑰有1024-bit等）產生一對金鑰pk和sk；
--- Sign負責用私鑰sk來給訊息簽名；
--- Vrfy負責用公鑰pk來驗證訊息；
（在絕大多數數情況下，）有
也就是說，如果簽名是真的，則一定能通過檢驗。
Gen至少要求能高效計算，比如若產生素數本身就是個指數時間的複雜問題，RSA簽名就不會被實現了。
2. 現在考慮攻擊者可以如何攻擊這個簽名方案，從而確定如何把難題「嵌入」簽名所需要的安全性場景。
2.1 攻擊者嘗試從公鑰pk裡恢復私鑰sk。
防止這個的發生其實是一種最弱的安全性要求了。典型的比如教科書上的RSA簽名，因為因數分解的複雜性假設的存在，所以直接恢復sk很困難。
類似，所有的、安全的單向函式F,可滿足 pk = F(sk)，原則上都可以用在金鑰產生演算法裡。【注1】所以，如果難題有類似的這種性質，比如離散對數問題、格上的LWE問題都可以有類似的演化來作為Gen(即金鑰產生演算法)的一部分。
2.2 攻擊者嘗試從簽名裡恢復私鑰sk。
這也是乙個很弱的安全性要求。單向的難題也是在這裡用到，即從二元函式G(sk, m)中，即使已知G(sk, m)的值和m的值，仍舊很難恢復出正確的sk。Sign至少得是這樣的（單向）二元函式。
2.2 攻擊者嘗試從已知的多個明文和其對應的簽名中算出乙個新的、有效的簽名。【注2】
這裡在滿足2.1之後，還至少要求明文、簽名對不可以有類似同態的關係。
比如textbook RSA裡有，所以如果攻擊者拿到m1和m2的簽名，馬上就可以偽造出m1 m2這個明文的簽名，而無須知道sk是多少。這也就是textbook RSA為什麼不安全的原因之一。
因此，Sign演算法必須打破類似同態的這些性質，引入Hash和padding是常用的手段。
當已經有了基本的Gen和Sign的雛形，接下來就可以用一些通用的構建方法了。這一方面有很多研究文章發表。
綜上，簽名的基本設計流程是：
從乙個難題本身出發，構建基本的單向函式或其他primitive(如hash、MAC等)，然後用已知的、或者獨創的轉換來嘗試設計數字簽名。其後通過發現安全性證明中仍舊存在的漏洞，引入其他的工具或者難題進行「修補」，直到滿足安全性要求為止。
【注1】因簽名演算法整體設計同時也牽涉到Sign和Vrfy，所以強調是「原則上」。
【注2】具體來說是selective CMA和adaptive CMA兩種安全性，此處不展開。
怎麼培養數學難題的思維，快速想到難題思路？
心夢無痕 我認為高中數學題就是多練題，意思就是熟能生巧，當然了，最重要的是要學會覆盤，每天做過的題你的覆盤總結，認識到自己的缺陷，然後彌補。然後是堅持不懈，每天都規定好自己做多少的題量，確定好，就一直堅持下去，不要被外物打擾。 佳一楊老師 第一點 熟練度 適度練習，見全題型 數學講究見多識廣，很多題...
怎麼提高做數學難題效率？
愛提提 提高思維最好的方法是自己多思考，把同一類題目的套路慢慢總結出來，形成自己的解題模板，再去做題，效率就會非常高。如果自己思考太慢，提高不夠理想，那麼就要借助老師的指導來啟發你，幫助你一遍一遍地完善思維。一般很多同學會選擇一對一的老師輔導，但這樣的成本往往比較高，而且時間也會不夠。你也可以找找愛...
不會做數學難題怎麼辦？
別再討好比利 在平時學習過程中整理錯題集，或者好題集等等，把遇到不會的難題記錄下來 多記錄一些難題，你看到同型別的題目可以知道怎麼做，熟練度也會提高，長時間下去你就不用怕不會做難題了 遇到沒見過難題可以用鉛筆在圖上寫寫畫畫，幾何題看看能不能添幾道有用的輔助線，比如說看到中點想倍長中線 中位線，看到角...