Board logo

標題: 用Maxima學密碼學-橢圓曲線離散對數問題 [打印本頁]

作者: bugmens    時間: 2020-3-29 22:16     標題: 用Maxima學密碼學-橢圓曲線離散對數問題

離散對數問題(Discrete Logarithm Problem,DLP)
已知\(\alpha,\beta,p\),\(0<\alpha,\beta<p\),\(GCD(\alpha,p)=1\),\(\alpha^x\equiv \beta \pmod{p}\),當\(p\)很大時,計算\(x\)值非常困難。

橢圓曲線離散對數問題(Elliptic Curve Discrete Logarithm Problem,ECDLP)
(1)令\(E\)為基於有限體\(F_p\)的橢圓曲線,\(P,Q\)為橢圓曲線上的點坐標(\(P,Q\in E(F_p)\))且\(Q=kP,k\in N\),當\(p\)很大時,計算\(k\)值非常困難。
(2)令\(E\)為基於二元體\(F_{2^n}\)的橢圓曲線,\(P,Q\)為橢圓曲線上的點坐標(\(P,Q\in E(F_{2^n})\))且\(Q=kP,k\in N\),當\(n\)很大時,計算\(k\)值非常困難。
以下介紹解離散對數問題和橢圓曲線離散對數問題的各種方法。
作者: bugmens    時間: 2020-4-3 07:41

1.解離散對數問題的方法-小步大步(Baby-step Giant-step)

將答案改寫成\(x=im+j\),其中\(m=\lceil\;\sqrt{p}\rceil\;\),\(0\le i<m\),\(0\le j<m\)
將原本離散對數問題改成
\(\alpha^x \equiv \beta \pmod{p}\)
\(\alpha^{im+j}\equiv \beta \pmod{p}\)
\(\alpha^j\equiv \beta(\alpha^{-m})^i \pmod{p}\)
計算\(\alpha^j\)稱為Baby-step
計算\(\beta(\alpha^{-m})^i\)稱為Giant-step
當某個\(i\)和\(j\)值讓\(\alpha^j\)和\(\beta(\alpha^{-m})^i\)相等時,就代表找到答案\(x=im+j\)

虛擬碼
1.\(m=Ceiling(\sqrt{p})\)
2.for j=0~m-1
 計算\([\alpha^j\pmod{p},j]\)數對放在List中
3.計算\(\alpha^{-m}\)
4.設\(\gamma=\beta\)
5.for i=0~m-1
 檢查目前\(\gamma\)值是否等於List中某個\(\alpha^j\pmod{p}\)
 若是,答案\(x=im+j\)
 若否,計算\(\gamma=\gamma \cdot \alpha^{-m}\)

參考資料:https://en.wikipedia.org/wiki/Baby-step_giant-step



Baby_stepGiant_step副程式
(%i1)
Baby_stepGiant_step(alpha,beta,p):=block
([m,gamma,List,inv_am,i,j,Powerj,x:[]],
print("取Giant步長m=Ceiling(",sqrt(p),")=",m:ceiling(sqrt(p))),
print("Baby step,計算",alpha^"0",",",alpha^"1",",...,",alpha,""^(m-1),"(mod ",p,")"),
print("List=",List:create_list(power_mod(alpha,j,p),j,0,m-1)),
print("(",a^"-1",")"^m,"≡(",alpha^"-1",")"^m,"≡",inv_mod(alpha,p),""^m,"≡",inv_am:power_mod(alpha,-m,p),"(mod ",p,")"),
print("令γ=β=",gamma:beta),
print("Giant step,每次γ值再乘上(α"^"-1",")"^m),
for i:0 thru m-1 do
  (print("當i=",i,"時"),
   Powerj:sublist_indices(List,lambda([aj],aj=gamma))-1,/*檢查List中是否有gamma值*/
   if Powerj#[] then
      (print("List中有γ=",gamma,"值"),
       for j in Powerj do
         (print("j=",j,"次方,找到一解x=i*m+j=",i,"*",m,"+",j,"=",last(x:append(x,[i*m+j])))
         )
      )
  else
      (print("List中沒有γ=",gamma,"值")
      ),
  print("計算γ≡γ*(α"^"-1",")"^m,"≡",gamma,"*",inv_am,"≡",gamma*inv_am,"≡",gamma:mod(gamma*inv_am,p),"(mod ",p,")")
      
  ),
return(x)
)$


\(\alpha^x \equiv \beta\pmod{p}\),\(x=\)?
(%i4)
alpha:2;
beta:108;
p:181;

(alpha) 2
(beta) 108
(p) 181

利用Baby_stepGiant_step方法解離散對數問題
(%i5) x:Baby_stepGiant_step(alpha,beta,p);
取Giant步長\(m=Ceiling(\sqrt{181})=14\)
Babystep,計算\(2^0,2^1,\ldots,2^{13}\pmod{181}\)
\(List=[1,2,4,8,16,32,64,128,75,150,119,57,114,47]\)
\((\alpha^{-1})^{14}\equiv(2^{-1})^{14}\equiv91^{14}\equiv52\pmod{181}\)
令\(\gamma=\beta=108\)
Giantstep,每次\(\gamma\)值再乘上\((\alpha^{-1})^{14}\)
當\(i=0\)時
List中沒有\(\gamma=108\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv108*52\equiv5616\equiv5\pmod{181}\)
當\(i=1\)時
List中沒有\(\gamma=5\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv5*52\equiv260\equiv79\pmod{181}\)
當\(i=2\)時
List中沒有\(\gamma=79\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv79*52\equiv4108\equiv126\pmod{181}\)
當\(i=3\)時
List中沒有\(\gamma=126\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv126*52\equiv6552\equiv36\pmod{181}\)
當\(i=4\)時
List中沒有\(\gamma=36\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv36*52\equiv1872\equiv62\pmod{181}\)
當\(i=5\)時
List中沒有\(\gamma=62\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv62*52\equiv3224\equiv147\pmod{181}\)
當\(i=6\)時
List中沒有\(\gamma=147\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv147*52\equiv7644\equiv42\pmod{181}\)
當\(i=7\)時
List中沒有\(\gamma=42\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv42*52\equiv2184\equiv12\pmod{181}\)
當\(i=8\)時
List中沒有\(\gamma=12\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv12*52\equiv624\equiv81\pmod{181}\)
當\(i=9\)時
List中沒有\(\gamma=81\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv81*52\equiv4212\equiv49\pmod{181}\)
當\(i=10\)時
List中沒有\(\gamma=49\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv49*52\equiv2548\equiv14\pmod{181}\)
當\(i=11\)時
List中沒有\(\gamma=14\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv14*52\equiv728\equiv4\pmod{181}\)
當\(i=12\)時
List中有\(\gamma=4\)值
j=2次方,找到一解\(x=i*m+j=12*14+2=170\)
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv4*52\equiv208\equiv27\pmod{181}\)
當\(i=13\)時
List中沒有\(\gamma=27\)值
計算\(\gamma\equiv\gamma*(\alpha^{-1})^{14}\equiv27*52\equiv1404\equiv137\pmod{181}\)
(x) \([170]\)
作者: bugmens    時間: 2020-4-5 22:03

2.解離散對數問題的方法-小步大步(Baby-step giant-step)

相同原理提供另一種實作
虛擬碼
1.\(m=Ceiling(\sqrt{p})\)
2.計算\(\alpha^{-m}\)
3.for j=0~m-1
 計算\([\alpha^j \pmod{p},j]\)數對放在BabyStep List中
4.for i=0~m-1
 計算\([\beta(\alpha^{-m})^i \pmod{p},i]\)數對放在GiantStep List中
5.將BabyStep和GiantStep的List由小到大重新排序
6.兩個List互相比較找出相同值
 若有,答案\(x=im+j\)
 若沒有,答案無解

參考資料:Computational Number Theory and Modern Cryptography



Baby_stepGiant_step副程式
(%i1)
Baby_stepGiant_step(alpha,beta,p):=block
([m,inv_am,BabyStep,GiantStep,indexB:1,indexG:1,i,j,x:[]],
print("取Giant步長m=Ceiling(",sqrt(p),")=",m:ceiling(sqrt(p))),
print("(",a^"-1",")"^m,"≡(",alpha^"-1",")"^m,"≡",inv_mod(alpha,p),""^m,"≡",inv_am:power_mod(alpha,-m,p),"(mod ",p,")"),
print("BabyStep=",BabyStep:create_list([power_mod(alpha,j,p),j],j,0,m-1)),
print("GiantStep=",GiantStep:create_list([mod(beta*power_mod(inv_am,i,p),p),i],i,0,m-1)),
print("由小到大排序"),
print("BabyStep=",BabyStep:sort(BabyStep)),
print("GiantStep=",GiantStep:sort(GiantStep)),
print("BabyStep和GiantStep互相比較找出相同值"),
print("一開始indexB=1,indexG=1"),
while indexB<=m and indexG<=m do
   (if BabyStep[indexB][1]=GiantStep[indexG][1] then
      (do
          (i:GiantStep[indexG][2],j:BabyStep[indexB][2],/*第2個值是i和j*/
           print("BabyStep[",indexB,"]=",BabyStep[indexB],"第1個值等於",
                   "GiantStep[",indexG,"]=",GiantStep[indexG],"第1個值,得到一解x=i*m+j=",i,"*",m,"+",j,"=",last(x:append(x,[i*m+j]))),
           print("GiantStep移到下一組,indexG=indexG+1=",indexG:indexG+1),
           if indexG=m or GiantStep[indexG][1]#GiantStep[indexG-1][1] then
              (return())
          ),
        print("BabyStep移到下一組,indexB=indexB+1=",indexB:indexB+1)
      )
    else if BabyStep[indexB][1]<GiantStep[indexG][1] then
      (print("BabyStep[",indexB,"]=",BabyStep[indexB],"第1個值小於",
               "GiantStep[",indexG,"]=",GiantStep[indexG],"第1個值,BabyStep移到下一組,indexB=indexB+1=",indexB:indexB+1)
      )
    else
      (print("BabyStep[",indexB,"]=",BabyStep[indexB],"第1個值大於",
               "GiantStep[",indexG,"]=",GiantStep[indexG],"第1個值,GiantStep移到下一組,indexG=indexG+1=",indexG:indexG+1)
      )
   ),
return(x)
)$


\(\alpha^x \equiv \beta \pmod{p}\),\(x=\)?
(%i4)
alpha:2;
beta:108;
p:181;

(alpha) 2
(beta) 108
(p) 181

利用Baby_stepGiant_step方法解離散對數問題
(%i5) Baby_stepGiant_step(alpha,beta,p);
取Giant步長\(m=Ceiling(\sqrt{181})=14\)
\((a^{-1})^{14}\equiv(2^{-1})^{14}\equiv 91^{14}\equiv52\pmod{181}\)
\(BabyStep=[[1,0],[2,1],[4,2],[8,3],[16,4],[32,5],[64,6],[128,7],[75,8],[150,9],[119,10],[57,11],[114,12],[47,13]]\)
\(GiantStep=[[108,0],[5,1],[79,2],[126,3],[36,4],[62,5],[147,6],[42,7],[12,8],[81,9],[49,10],[14,11],[4,12],[27,13]]\)
由小到大排序
\(BabyStep=[[1,0],[2,1],[4,2],[8,3],[16,4],[32,5],[47,13],[57,11],[64,6],[75,8],[114,12],[119,10],[128,7],[150,9]]\)
\(GiantStep=[[4,12],[5,1],[12,8],[14,11],[27,13],[36,4],[42,7],[49,10],[62,5],[79,2],[81,9],[108,0],[126,3],[147,6]]\)
BabyStep和GiantStep互相比較找出相同值
一開始\(indexB=1,indexG=1\)
\(BabyStep[1]=[1,0]\)第1個值小於\(GiantStep[1]=[4,12]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=2\)
\(BabyStep[2]=[2,1]\)第1個值小於\(GiantStep[1]=[4,12]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=3\)
\(BabyStep[3]=[4,2]\)第1個值等於\(GiantStep[1]=[4,12]\)第1個值,得到一解\(x=i*m+j=12*14+2=170\)
GiantStep移到下一組,\(indexG=indexG+1=2\)
BabyStep移到下一組,\(indexB=indexB+1=4\)
\(BabyStep[4]=[8,3]\)第1個值大於\(GiantStep[2]=[5,1]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=3\)
\(BabyStep[4]=[8,3]\)第1個值小於\(GiantStep[3]=[12,8]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=5\)
\(BabyStep[5]=[16,4]\)第1個值大於\(GiantStep[3]=[12,8]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=4\)
\(BabyStep[5]=[16,4]\)第1個值大於\(GiantStep[4]=[14,11]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=5\)
\(BabyStep[5]=[16,4]\)第1個值小於\(GiantStep[5]=[27,13]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=6\)
\(BabyStep[6]=[32,5]\)第1個值大於\(GiantStep[5]=[27,13]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=6\)
\(BabyStep[6]=[32,5]\)第1個值小於\(GiantStep[6]=[36,4]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=7\)
\(BabyStep[7]=[47,13]\)第1個值大於\(GiantStep[6]=[36,4]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=7\)
\(BabyStep[7]=[47,13]\)第1個值大於\(GiantStep[7]=[42,7]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=8\)
\(BabyStep[7]=[47,13]\)第1個值小於\(GiantStep[8]=[49,10]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=8\)
\(BabyStep[8]=[57,11]\)第1個值大於\(GiantStep[8]=[49,10]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=9\)
\(BabyStep[8]=[57,11]\)第1個值小於\(GiantStep[9]=[62,5]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=9\)
\(BabyStep[9]=[64,6]\)第1個值大於\(GiantStep[9]=[62,5]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=10\)
\(BabyStep[9]=[64,6]\)第1個值小於\(GiantStep[10]=[79,2]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=10\)
\(BabyStep[10]=[75,8]\)第1個值小於\(GiantStep[10]=[79,2]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=11\)
\(BabyStep[11]=[114,12]\)第1個值大於\(GiantStep[10]=[79,2]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=11\)
\(BabyStep[11]=[114,12]\)第1個值大於\(GiantStep[11]=[81,9]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=12\)
\(BabyStep[11]=[114,12]\)第1個值大於\(GiantStep[12]=[108,0]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=13\)
\(BabyStep[11]=[114,12]\)第1個值小於\(GiantStep[13]=[126,3]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=12\)
\(BabyStep[12]=[119,10]\)第1個值小於\(GiantStep[13]=[126,3]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=13\)
\(BabyStep[13]=[128,7]\)第1個值大於\(GiantStep[13]=[126,3]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=14\)
\(BabyStep[13]=[128,7]\)第1個值小於\(GiantStep[14]=[147,6]\)第1個值,BabyStep移到下一組,\(indexB=indexB+1=14\)
\(BabyStep[14]=[150,9]\)第1個值大於\(GiantStep[14]=[147,6]\)第1個值,GiantStep移到下一組,\(indexG=indexG+1=15\)
(%o5) \([170]\)




歡迎光臨 Math Pro 數學補給站 (https://math.pro/db/) 論壇程式使用 Discuz! 6.1.0