記輸出為[G`, G, p, q, g]，其中p為大素數，G`為模p的有限循環整數群，階為p-1；q為大素數，為G的階，G為G`的子群（模亦是p），生成元為g（G`的一個元素），另外滿足如下條件：
1. 1<q的位長<p的位長，p、q隨機選取，p同余于1 mod q，即q整除p-1，q為p-1的素因子
2. 1<g<=p-1，隨機選取，測試它的(p-1)/q次冪是否等于1 mod p，若等于則重新選取，直到不等于
3. 上面選定的g，遍歷1到q的冪模p，就得到G的各元素
數學基礎：一個有限群，對每個元素它的階整除群的階，它的群階冪次方等于單位元；一個有限循環群，它的生成元個數為群階的歐拉數，若群階是素數，則所有非1的元素都是生成元
結論：這種計算子群的方法由于保證階為素數且只要超過160位長，就可避免針對階為合數的質因子分解并利用中國剩余定理求離散對數的已知最好攻擊，具有中長期安全強度
posted on 2023-09-06 22:28
春秋十二月 閱讀(357)
評論(0) 編輯 收藏 引用 所屬分類:
Algorithm