2024年11月10日
符號含義
E 表示滿足橢圓曲線Weierstrass方程上的點群
K 代數閉域，用來限制Weierstrass方程的系數與E中的點
E(K) 定義在K上的點群E
E/K 定義在K上的橢圓曲線E
End(E) E上的自同態環
域擴張分析
End(E)模與Z代數
極點首項系數
除子映射及同構
同種映射同態性的解釋
Hasse定理之引理證明的補充
撓曲線及其個數
有限域上的橢圓曲線
一種確定型群階計算法
奇素域上的算法應用
GF域上的群階計算
Schoof算法正確性根本
一種計算橢圓曲線群的階的確定型多項式時間算法，確定型是因為算法內部沒有隨機選擇/概率拋幣操作，多項式時間是因為域
k的乘法與求逆總次數是O((logq)^6)
（
q為
k的大小，乘法與求逆相對加減運算顯著耗時）。具體原理及流程詳見參考文獻[1]中5.2節。這里給出筆者的一些思考
1. Hasse定理（Frobenius自同態方程式）在扭點群上的限制亦成立，這決定了t模l的一個同余方程成立，且在模l的最小非負剩余系下解是唯一的
2. 孫子定理保證了某取值范圍內的一個t模L（L為各素因子l的乘積）的唯一解，即由t模L各個素因子l的同余方程構成的同余方程組的解是唯一的
3. L必須大于t取值上限的2倍。這是為了算法求得的解滿足上述2（否則在更小的L內得到的解不唯一，因L與t上限或下限間的某數可以與t模L同余）
4. 素因子l的選擇排除2與橢圓曲線特征p。這是因為算法構造所依賴的一個引理之前提條件：為奇素數保證l次除子多項式屬于k[X]，即引理論斷有意義；
不等于p保證檢測一個多項式f是否零多項式的充要條件成立，即可以用l次除子多項式去整除f來判斷。另l為素數保證了與其它除子多項式（及其冪次）互素
另外發現了算法的一處瑕疵，即第4步預計算除子多項式與Frobenius自同態的復合少了兩個值，這導致第5步可能崩潰，當依賴的后續兩個復合多項式沒被計算時。
這個糾正可通過修改第4步擴大2個值，或第5步通過除子多項式的遞推公式按需計算
扭點的階計算正確性根本
在密碼學中的應用
選取原則
1. 排除超奇異橢圓曲線。這是為避免MOV等約化攻擊，約化攻擊時間復雜度是亞指數
2. 有限域的選擇要使E(Fq)的群階足夠大。這是為了緩解Shanks及Pollard ρ攻擊
3. E(Fq)存在階為大素數的子群。這是為了抵抗Pohlig-Hellman攻擊
對于第1點，就排除了char(K)=2或3且j(E)=0對應的如下標準形式曲線
Y2+α3Y=X3+α4X+α6（α3≠0） 與 Y2=X3+α4X+α6
一種典型方案
橢圓曲線及有限域的選擇使得|E(Fq)|=cm，且char(Fq) ∤ q+1-cm。其中m是一個大素數（通常不低于256位二進制長度，提供中長期安全性），c小于m。
m階子群的生成元可通過以下方法確定：隨機選擇E上的一個有理點P，如果Q=cP為零元（即無窮遠點），則重復選擇，直到其不等于零元。
一旦找到了生成元，那么子群就可以構造出來了。下面分析正確性
參考文獻
[1] 橢圓曲線及其在密碼學中的應用—導引 Andreas Enge
[2] 算法數論 裴定一、祝躍飛
[3] The Arithmetic of Elliptic Curves Joseph H. Silverman
[4] 標識密碼學 程朝輝
[5] 代數學基礎與有限域 林東岱
[6] 抽象代數I 趙春來 徐明曜
[7] 代數與數論 李超 周悅
posted @
2024-11-10 21:45 春秋十二月 閱讀(282) |
評論 (0) |
編輯 收藏
2024年9月7日
原本算法
摘抄參考文獻1中附錄的算法流程如下
例子測驗
改正后的算法
改正之前，先理清原本算法判別不可約多項式所用的原理。其原理是若f(x)可約，當且僅當存在次數i<=d=[deg(f(x))/2]的不可約因子g(x)，而此時gcd(x
q^i-x, f(x))≠1。
根據
參考文獻2（詳見如下定理），x
q^i-x是所有i次不可約多項式的乘積，因此它必定包含g(x)而與f(x)存在公因子。不可約判別算法的思想應該是遍歷次數1到d的所有不可約多項式
（沒必要檢測大于d的不可約多項式，因為若f(x)可約則其分解因子中必定存在不大于d的不可約多項式），檢測輸入多項式與它們是否存在公因子。所以這個原理是正確的，只是實現不對，
略作改正如下（類c語言描述）
重新測驗
參考文獻
[1] 算法數論 裴定一、祝躍飛
[2] 代數學基礎與有限域 林東岱
posted @
2024-09-07 23:07 春秋十二月 閱讀(304) |
評論 (0) |
編輯 收藏
2024年8月30日
通用算法
先摘抄參考文獻[1]中的算法流程如下
正確性分析
下面證明以上算法用到的事實結論，提煉為如下幾個引理
算法構造思想
用到二次剩余知識，即一個待求平方元ɑ可以且只能表示為兩個平方因子的乘積，其中一因子為任意隨機選取的非平方因子β的偶數冪，
另一因子為葉子群H的一元素r，H作為陪集劃分根群（有限域乘法群）得到β生成的集合即商群G/H的一個代表元系。這樣一來，將開方轉化為β與r的乘方運算，
迭代的過程就是為求那個具體的代表元β
e中的指數e（注意e必為偶數），從G
s-2到G
0=H，迭代結束后r被唯一確定，r的開方等于r的(t+1)/2次方（因為t是H的階且為奇數，r
t+1=r）。
觀察算法流程，可以發現如果分解q-1后得到s=1，那么就沒必要選取非平方元β了（這時令β=1），直接跳到第6步得到結果。僅當s≠1才隨機選取β。這樣改進后可加快算法運行
例子測驗
特殊算法
當q是素數且q≡3(mod 4)時，存在更快的算法及測驗如下
posted @
2024-08-30 22:22 春秋十二月 閱讀(424) |
評論 (0) |
編輯 收藏
2024年8月15日
基本原理
再來看Terr算法用到的如下定理
定理 （基于
參考文獻1改正后的描述）
對每一正整數t，存在唯一確定的一組整數k和j，0<=k<j，使得t=Tj+1-k，其中T0=0，Tn=Tn-1+n-1，n>=1
如果t=0，那么j在區間[0,1)，故只能取0，此時k=0與條件k<j矛盾，若允許k=j，則不保證唯一，比如t=1 => j=1, k=0 或 j=2, k=2。
所以參考文獻1中原來定理的描述“對每一非負整數t”是錯誤的。下面列舉一些實例驗證j與k的唯一解
t=1 => j=1, k=0
t=2 => j=2, k=1
t=3 => j=2, k=0
t=4 => j=3, k=2
t=5 => j=3, k=1
t=6 => j=3, k=0
算法偽代碼
例子測驗
參考文獻
[1] 代數學基礎與有限域 林東岱
posted @
2024-08-15 22:35 春秋十二月 閱讀(698) |
評論 (0) |
編輯 收藏
2024年6月29日
私鑰分組加密
上圖的證明中，r
(j)兩兩不同的概率計算是關鍵，下面給出詳細過程
另外兩個分布統計的不同意味著計算可分辨（反之則計算不可分辨），亦即r(j)至少兩個相同的概率。
Construction 5.3.9一次只能加密與密鑰等長的明文，如果要加密更長的明文，怎么辦？一個簡單直接
的方法是將明文分成多個大小為n的塊，對每個塊調用上述加密步驟，那么就得到形如下的密文塊序列
密文塊序列從
Proposition 5.3.10的證明中可知是計算不可分辨的，滿足
「多組消息安全性
」。但對于解密
需要存儲每一塊的隨機數，因此比較占空間，所以衍生出下面更高效的方案
Construction 5.3.12
私密通用加密
語義安全性分析
抗主動攻擊安全性
以上兩種構造因滿足
「多組消息安全性
」，故滿足
CPA與
CCA1，具體的證明可參考Oded Goldreich《密碼學基礎》的
Proposition 5.4.12、
Proposition 5.4.18。
但不滿足
CCA2，因為攻擊者拿到挑戰密文后，可以修改它再發出解密質疑，得到回答的明文從而異或求解
fk(
ri)，最后與挑戰密文異或求解挑戰明文
對于通用加密構造的CCA2攻擊細節如下
posted @
2024-06-29 17:00 春秋十二月 閱讀(620) |
評論 (0) |
編輯 收藏
2024年5月16日
定義
Berlekamp分解算法
AES有限域
不可約性證明
非本原性驗證
找出本原元
不可約多項式個數
線性移位寄存器m序列
根據參考文獻1知線生移位寄存器產生m序列的充要條件是特征多項式f(x)為本原多項式。而確立有限域上的本原多項式，主要有兩種方法：
一種方法是根據
Fq上所有次數為n的本原多項式的乘積正好等于割圓多項式Q
e，其中e=q
n-1，從而所有次數為n的本原多項式可以通過分解Q
e得到。
另一種方法是通過構造本原元再求本原元的極小多項式，先素因子分解q
n-1=p
1p
2...p
k，如果對每一p
i都有ord(
αi)=p
i，那么
α=
α1α2...
αk的階就是q
n-1，
因此是
Fq上的本原元，則f(x)=(x-
α)(x-
α2)...(x-
αr)，r=q
n-1（因為
α是本原元，所以n是使
αq^n=
α成立的最小正整數）。
求解本原多項式
假設線性移位寄存器的級數為4，這里使用上述二種方法求
F16上的本原多項式，過程如下
分解割圓多項式法 
構造極小多項式法 
本原多項式個數
m序列示例
參考文獻
[1] 代數學基礎與有限域 林東岱
posted @
2024-05-16 13:41 春秋十二月 閱讀(898) |
評論 (0) |
編輯 收藏
2024年4月4日
【適用前提】大整數N=pq的素因子p<q<2p，解密指數d<(1/3)N
1/4
【攻擊方法】 1）用歐幾里得算法計算e/N的各個漸近分數k
i/d
i，i>=1，直至d
i>=(1/3)N
1/4，記錄此時的i為m。令i=1
2）計算T=(e*d
i-1)/k
i，若T不為整數則轉到4），否則轉到3）
3）解方程f(x)=x
2-(N-T+1)x+N=0的根，如果有正整數根且兩個根皆小于N，則輸出p、q，并返回成功。否則轉到4）
4）遞增i，若i<m則轉回2），否則返回失敗
該方法即
Wiener算法用到了關于連分數的一個
定理：若α為任一實數，有理數p/q適合|α-(p/q)|<1/(2q2)，則p/q必為α的某一漸近分數。證明詳見參考文獻[2]。
由定理可知攻擊方法是可行的，必能找到使f(x)=0有合理解的某漸近分數。下面證明：攻擊迭代次數的上界為
【證明】
【例子】N = 9449868410449，e = 6792605526025，d<(1/3)N
1/4≈584，試分解N
參考文獻
[1] 公鑰密碼學的數學基礎 王小云、王明強、孟憲萌
[2] 算法數論 裴定一、祝躍飛
posted @
2024-04-04 18:19 春秋十二月 閱讀(628) |
評論 (0) |
編輯 收藏
2024年3月20日
群結構
定理1：若G為一個循環群，則G內每個滿足ord(
α)=s的元素
α都是擁有s個元素的循環子群的生成元
證明：
定理2：若G為一個階為n的有限循環群，g為對應的生成元，則對整除n的每個整數k，G都存在一個唯一的階為k的循環子群H。
這個子群是由g
n/k生成的。H是由G內滿足條件
αk=1的元素組成的，且G不存在其它子群
證明：
推論：從上述兩定理可知有限循環群、子群及生成元的關系如下
例子：依據上述推論得如下
生成元判定算法
輸入：循環群G、某子群的階k
1）若k=1，則直接輸出e。否則轉到2）
2）隨機從G-{e}中選擇一元素x
3）若x
k≠e，則轉回2）。否則若k為素數，則跳到5）；若k為合數，則轉到4）
4）遍歷整除k的真因子d，若x
d=e，則轉回2）
5）輸出x
posted @
2024-03-20 22:49 春秋十二月 閱讀(621) |
評論 (0) |
編輯 收藏
2024年3月12日
混合線性同余發生器（MLCG）
X
n ≡ αX
n-1 + c mod m 0<X
0, α, c<m，X
0為種子，n=1、2、3...
定理 如果下列3個條件都滿足，則 MLCG達到滿周期(即周期d=m)
(1) (c, m)=1，即 c、m互素
(2) 對 m的任一素因子p，有α≡1 mod p
(3) 如果4|m，則 α≡1 mod 4
該定理的證明在
參考文獻[2]中證明并用到如下兩個引理：
引理5 設p為素數，α∈Z+且pα>2，如果 x=1(mod pα)，x≠1(mod pα+1)；則xp=1(mod pα+1)， xp≠1(mod pα+2)
該引理給出了求一個整數的階的判別方法，是理解MLCG周期等于m的充要條件之關鍵。
本文闡述為什么p是使x
p=1(mod p
α+1)成立的最小正整數，以及一般情形m=p
w(w≥1)是使x
m=1(mod p
α+w)成立的最小正整數；為什么前提條件是p
α>2。
◆ 先論證不存在一個整數1≤b<p使得x
b=1(mod p
α+1)成立
◆ 再證不存在一個整數1≤b<m使得x
b=1 (mod p
α+w)成立
◆ 為什么前提條件是pα>2
如果pα=2，x=1(mod 2)且x≠1(mod 22)。令x=1+2q，2 ∤ q。有x2=(1+2q)2=1+4q+4q2，注意到q是奇數，則x2=1(mod22)，x2=1(mod23)。故得不到引理的結論
引理6（改寫的等價形式） 如果 α=1(mod 4)，則(αm - 1)/(α - 1)=0(mod m) ，m=2w，w>1
其實這里當
α=1(mod 2)且
α≠1(mod 4)，結論也是成立的。比如取
α=3，m=16，則 (3
16 -1)=81
4 -1=(-15)
4 -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32)，
即(3
16 -1)/(3-1)=0(mod 16)。但只有當
α=1(mod 4)時，m才是使結論成立的最小正整數。論證如下
參考文獻
[1] 現代密碼學第4版 楊波
[2] 混合線性同余發生器的周期分析 張廣強、張小彩
posted @
2024-03-12 17:30 春秋十二月 閱讀(1383) |
評論 (0) |
編輯 收藏