發新話題
打印

用Maxima學密碼學-橢圓曲線離散對數問題

推到噗浪
推到臉書

用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\)值非常困難。
以下介紹解離散對數問題和橢圓曲線離散對數問題的各種方法。

TOP

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]\)

TOP

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]\)

TOP

3-1.解離散對數問題的方法-小步和倍增步長的大步(Baby-step and double step width 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
每次步長都是\(\alpha^{-m}\)
將答案改寫成\(x=2^kvq+r\) (\(x\)除以\(2^kv\),商數\(q\),餘數\(r\))
其中\(v\)為偶數,\(k\ge 0\),\(1\le r \le 2^kv\)

\(\alpha^x \equiv \beta \pmod{p}\)
\(\displaystyle \alpha^{2^kvq+r}\equiv \beta \pmod{p}\)
\(\displaystyle \beta \alpha^{-r}\equiv (\alpha^{2^kv})^q \pmod{p}\)
計算\( \beta\alpha^{-r}\)稱為Baby step
計算\((\alpha^{2^kv})^q\)稱為Giant step
每次步長\(\alpha^{2^kv}\)隨著\(k\)值倍增


Lemma 2.1 設\(v\)為正偶數,對每一個正整數\(x\),存在唯一的\(k \ge 0\),\(q\)和\(r\),\(\lfloor\;4^{k-1}\rfloor\;v^2\le 2^kvq <4^kv^2\)和\(1\le r\le 2^kv\),使得\(x=y+r\),\(y=2^kvq\)。

以\(2^x \equiv 108 \pmod{181}\),參數\(v=2\)為例。
--------
當\(k=0\)時
\(BabyStep\):\(1\le r \le 2^0v\),\(1\le r \le 2\),\(r=1,2\)
\(GiantStep\):\(\lfloor\;4^{-1}\rfloor\;v^2\le 2^kvq<4^0v^2\),\(0\le 2^kvq<4\),\(2^kvq=0,2\),倍增步長為2
可能\(x=1,2,3,4\)
--------
當\(k=1\)時
\(BabyStep\):\(1\le r \le 2^1v\),\(1\le r \le 4\),\(r=1,2,3,4\)
\(GiantStep\):\(\lfloor\;4^0\rfloor\;v^2\le 2^kvq<4^1v^2\),\(4\le 2^kvq<16\),\(2^kvq=4,8,12\),倍增步長為4
可能\(x=5,6,\ldots,16\)
--------
當\(k=2\)時
\(BabyStep\):\(1\le r \le 2^2v\),\(1\le r \le 8\),\(r=1,2,3,4,5,6,7,8\)
\(GiantStep\):\(\lfloor\;4^1\rfloor\;v^2\le 2^kvq<4^2v^2\),\(16\le 2^kvq<64\),\(2^kvq=16,24,32,40,48,56\),倍增步長為8
可能\(x=17,18,\ldots,64\)
--------
當\(k=3\)時
\(BabyStep\):\(1\le r \le 2^3v\),\(1\le r \le 16\),\(r=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16\)
\(GiantStep\):\(\lfloor\;4^2\rfloor\;v^2\le 2^kvq<4^3v^2\),\(64\le 2^kvq<256\),\(2^kvq=64,80,96,112,128,144,160,176,192,208,224,240\),倍增步長為16
可能\(x=65,66,\ldots,256\),已經超過全部可能答案\(x=1,2,\ldots,181\)

參考資料:https://www.ams.org/journals/mco ... 5718-97-00880-6.pdf



Baby_stepDoubleGiant_step副程式
(%i1)
Baby_stepDoubleGiant_step(alpha,beta,p,v):=block
([k:0,BabyStep,GiantStep,GiantPower,indexB:1,indexG:1,LengthB,LengthG,x:[]],
if primep(p)=false then
  (print("參數p=",p,"要是質數"),
   return()
  ),
if mod(v,2)=1 then
  (print("參數v=",v,"要是偶數"),
   return()
  ),
do
  (print("當k=",k,"時"),
   print("1≦r≦",2^"k","v,1≦r≦",2^k*v),
   print(alpha^"-1","=",inv_mod(alpha,p),"(mod",p,")"),
   print("BabyStep=[",beta,"*",alpha^"-r","(mod",p,"),",r,"]=",
            BabyStep:create_list([mod(beta*power_mod(alpha,-r,p),p),r],r,1,2^k*v)),
   print("floor(",4^"k-1",")v"^"2","≦",2^"k","vq<",4^"k","v"^2,",",floor(4^(k-1))*v^2,"≦",2^"k","vq<",4^k*v^2),
   print(2^"k","vq=",GiantPower:create_list(2^k*v*q,q,floor(4^(k-1))/2^k*v,2^k*v-1),
          ",倍增步長為",2^k*v),
   print("GiantStep=[",alpha^(2^"k"*"v"*q),"(mod",p,")",",",2^"k"*"v"*q,"]=",
            GiantStep:map(lambda([power],[power_mod(alpha,power,p),power]),GiantPower)),
   print("由小到大排序"),
   print("BabyStep=",BabyStep:sort(BabyStep)),
   print("GiantStep=",GiantStep:sort(GiantStep)),
   print("BabyStep和GiantStep互相比較找出相同值"),
   LengthB:length(BabyStep),
   LengthG:length(GiantStep),
   while indexB<=LengthB and indexG<=LengthG do
     (if BabyStep[indexB][1]=GiantStep[indexG][1] then
        (do
            (print("BabyStep[",indexB,"]=",BabyStep[indexB],"和","GiantStep[",indexG,"]=",GiantStep[indexG],"的第一個值相同"),
             print("得到一解x=",BabyStep[indexB][2],"+",GiantStep[indexG][2],
                   "=",last(x:append(x,[BabyStep[indexB][2]+GiantStep[indexG][2]]))),
             indexG:indexG+1,
             if indexG>LengthG or GiantStep[indexG][1]#GiantStep[indexG-1][1] then
               (return())
            ),
         indexB:indexB+1
        )
      else if BabyStep[indexB][1]<GiantStep[indexG][1] then
        (indexB:indexB+1)
      else
        (indexG:indexG+1)
     ),
   if x=[] then/*沒找到解答*/
     (print("BabyStep和GiantStep沒有相同值"))
   else/*找到解答跳出去*/
     (print("將x=",x,"(mod",p-1,")=",x:mod(x,p-1)),
      print("再刪除相同值x=",x:unique(x)),
      return(x)
     ),
   if 4^k*v^2>p then
     (print("無解"),
      return()
     ),
   k:k+1,/*換下一個k值*/
   print("--------")
  )
)$


\(\alpha^x\equiv \beta \pmod{p}\),初始步長\(v\)要是偶數
(%i5)
alpha:2;
beta:108;
p:181;
v:2;

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

利用Baby_stepDoubleGiant_step方法解離散對數問題
(%i6) x:Baby_stepDoubleGiant_step(alpha,beta,p,v);
當\(k=0\)時
\(1\le r\le 2^k v\),\(1\le r\le 2\)
\(2^{-1} \equiv 91 \pmod{181}\)
\(BabyStep=[ 108 * 2^{-r} \pmod{181}, r ]= [[54,1],[27,2]]\)
\(floor( 4^{k-1} )v^2 \le 2^k vq< 4^k v^2\),\(0 \le 2^k vq< 4\)
\(2^k vq= [0,2]\),倍增步長為 2
\(GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[1,0],[4,2]]\)
由小到大排序
\(BabyStep= [[27,2],[54,1]]\)
\(GiantStep= [[1,0],[4,2]]\)
\(BabyStep\)和\(GiantStep\)互相比較找出相同值
\(BabyStep\)和\(GiantStep\)沒有相同值
--------
當\(k=1\)時
\(1\le r\le 2^k v\),\(1\le r\le 4\)
\(2^{-1} \equiv 91 \pmod{181}\)
\(BabyStep=[ 108 * 2^{-r}\pmod{181},r]=[[54,1],[27,2],[104,3],[52,4]]\)
\(floor( 4^{k-1})v^2 \le 2^k vq< 4^k v^2\),\(4\le 2^k vq< 16\)
\(2^k vq= [4,8,12]\),倍增步長為 4
\(GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[16,4],[75,8],[114,12]]\)
由小到大排序
\(BabyStep=[[27,2],[52,4],[54,1],[104,3]]\)
\(GiantStep=[[16,4],[75,8],[114,12]]\)
\(BabyStep\)和\(GiantStep\)互相比較找出相同值
\(BabyStep\)和\(GiantStep\)沒有相同值
--------
當\(k=2\)時
\(1\le r\le 2^k v\),\(1\le r\le 8\)
\(2^{-1}\equiv 91 \pmod{181}\)
\(BabyStep=[ 108 * 2^{-r} \pmod{181},r]=[[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],[97,7],[139,8]]\)
\(floor( 4^{k-1})v^2 \le 2^k vq< 4^k v^2\),\(16\le 2^k vq< 64\)
\(2^k vq= [16,24,32,40,48,56]\),倍增步長為 8
\(GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[14,16],[145,24],[15,32],[39,40],[29,48],[3,56]]\)
由小到大排序
\(BabyStep=[[13,6],[26,5],[27,2],[52,4],[54,1],[97,7],[104,3],[139,8]]\)
\(GiantStep=[[3,56],[14,16],[15,32],[29,48],[39,40],[145,24]]\)
\(BabyStep\)和\(GiantStep\)互相比較找出相同值
\(BabyStep\)和\(GiantStep\)沒有相同值
--------
當\(k=3\)時
\(1\le r\le 2^k v\),\(1\le r\le 16\)
\(2^{-1}\equiv 91 \pmod{181}\)
\(BabyStep=[ 108 * 2^{-r} \pmod{181},r]=[[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],\)
\([97,7],[139,8],[160,9],[80,10],[40,11],[20,12],[10,13],[5,14],[93,15],[137,16]]\)
\(floor( 4^{k-1})v^2 \le 2^k vq< 4^k v^2\),\(64 \le 2^k vq< 256\)
\(2^kvq=[64,80,96,112,128,144,160,176,192,208,224,240]\),倍增步長為 16
\(GiantStep=[ 2^{2^kvq} \pmod{181},2^kvq]=[[44,64],[73,80],[117,96],[9,112],\)
\([126,128],[135,144],[80,160],[34,176],[114,192],[148,208],[81,224],[48,240]]\)
由小到大排序
\(BabyStep=[[5,14],[10,13],[13,6],[20,12],[26,5],[27,2],[40,11],[52,4],[54,1],[80,10],\)
\([93,15],[97,7],[104,3],[137,16],[139,8],[160,9]]\)
\(GiantStep=[[9,112],[34,176],[44,64],[48,240],[73,80],[80,160],[81,224],[114,192],\)
\([117,96],[126,128],[135,144],[148,208]]\)
\(BabyStep\)和\(GiantStep\)互相比較找出相同值
\(BabyStep[10]=[80,10]\)和\(GiantStep[6]=[80,160]\)的第一個值相同
得到一解\(x=10+160=170\)
將\(x=[170] \pmod{180}=[170]\)
再刪除相同值\(x=[170]\)
(x) \([170]\)

TOP

3-2.解離散對數問題的方法-小步和倍增步長的大步(Baby-step and double step width Giant-step)

若能理解上一篇文章,再回頭看論中的演算法2.2計算\(g\)的order。
\(g^x \equiv 1\pmod{p}\)
\(g^{y+r}\equiv 1 \pmod{p}\)
\(g^y \equiv g^{-r}\pmod{p}\)
計算\(g^{-r}\)稱為Baby step
計算\(g^y\)稱為Giant step

演算法2.2
輸入:\(g\in G\),\(|\;g|\;\)的下限\(C+1\)(若已知解答\(x\)不會在\(1\sim C\)之間),初始步長\(v\)(\(v\)要是偶數)
輸出:\(x=|\;g|\;\)
(1) \(x = 0\)
(2) \(s = 1; y = v; u = v\)
(3) \(h = g^{−1}\)
(4) \(a = h^C; b = g^v; c = b\)    /*\(a = g^{−C−r};b = g^y; c = g^u\)*/
(5) \(R=\phi;\)
(6) while (\(x == 0\)) do
(7)  for (\(r = s,s + 1\ldots, u\)) do /*new baby steps*/
(8)   \(a=a*h\)
(9)   if (\(s==1\)) then     /*check if \(1\le x\le v\)*/
(10)    if (\(a==1\)) then
(11)     \(x=r+C\)
(12)     return (\(x\))
(13)     break while
(14)    else
(15)     \(R = R\cup \{\;(a,r)\}\;\)
(16)    fi
(17)   else
(18)    \(R=R\cup \{\;(a,r)\}\;\)
(19)    fi
(20)  od
(21)  while(\(x==0\) and \(y<u^2\))do  /*giant steps*/
(22)   if(there is a number \(r\) such that \((b,r)\in R\)) then
(23)    \(x=y+r+C\)
(24)    return(\(x\))
(25)   else
(26)    \(y=y+u\)
(27)    \(b=b*c\)
(28)   fi
(29)  od
(30)  \(s=u+1;u=2u\)       /*double step-width*/
(31)  \(c=c^2\)
(32) od



計算一個元素g的Order副程式
(%i1)
Order(g,p,C,v):=block
([x,r,s,y,u,h,a,b,c,R],
print("1.變數初始化-------"),
print("x=0"),x:0,
print("s=",s:1),
print("y=v=",y:v),
print("u=v=",u:v),
print("h=g"^"-1","=",g^"-1","≡",h:inv_mod(g,p),"(mod",p,")"),
print("從",g^concat("-",C),"(mod",p,")開始計算,a=h"^"C","=",h,""^C,"≡",a:power_mod(h,C,p),"(mod",p,")"),
print("b=g"^"v","=",g,""^v,"≡",b:power_mod(g,v,p),"(mod",p,")"),
print("c=b=",c:b),
print("R=",R:[]),
while x=0 do
  (print("2.計算BabyStep-------"),
   for r:s thru u do
     (print("計算",g^concat("-",C+r),"(mod",p,")",",a=a*h=",a,"*",h,"≡",a:mod(a*h,p),"(mod",p,")"),
      if s=1 then
        (if a=1 then
           (print("解答x=r+C=",r,"+",C,"=",x:r+C),
            return(x)
           )
         else
           (R:append(R,[[a,r]]),
            print("R=R∪",[a,r])
           )
        )
      else
        (R:append(R,[[a,r]]),
         print("R=R∪",[a,r])
        )
     ),
   print("BabyStep=",R),
   print("3.計算GiantStep-------"),
   while x=0 and y<u^2 do
     (if (r:assoc(b,R))#false then
         (print("計算",g,""^y,"≡",b,"(mod",p,")在R[",r,"]=",R[r],"裡面"),
          print("解答x=y+r+C=",y,"+",r,"+",C,"=",x:y+r+C),
          return(x)
         )
      else
         (print("計算",g,""^y,"≡",b,"(mod",p,")不在R裡面"),
          print("更新次方y=y+u=",y,"+",u,"=",y:y+u),
          print("b=b*c=",b,"*",c,"≡",b:mod(b*c,p),"(mod",p,")")
         )
     ),
    print("s=u+1=",s:u+1),
    print("u=2*u=",u:2*u),
    print("倍增步長c=c"^2,"=",c:c^2)
  ),
return(x)
)$


\(g^x \equiv 1 \pmod{p}\),\(C+1\)下限,初始步長\(v\)要是偶數
(%i5)
g:2;
p:181;
C:10;
v:2;

(g) 2
(p) 181
(C) 10
(v) 2

利用Baby_stepDoubleGiant_step方法計算\(g\)的order
(%i6) x:Order(g,p,C,v);
1.變數初始化-------
\(x=0\)
\(s=1\)
\(y=v=2\)
\(u=v=2\)
\(h=g^{-1}= 2^{-1}\equiv 91\pmod{181}\)
從\(2^{-10}\pmod{181}\)開始計算,\(a=h^C = 91 ^{10} \equiv 108\pmod{181}\)
\(b=g^v = 2 ^2 \equiv 4\pmod{181}\)
\(c=b=4\)
\(R=[]\)
2.計算BabyStep-------
計算\(2^{-11}\pmod{181}\),\(a=a*h= 108 * 91 \equiv 54\pmod{181}\)
\(R=R\cup[54,1]\)
計算\(2^{-12}\pmod{181}\),\(a=a*h= 54 * 91 \equiv 27\pmod{181}\)
\(R=R\cup[27,2]\)
BabyStep=\([[54,1],[27,2]]\)
3.計算GiantStep-------
計算\(2^2 \equiv 4\pmod{181}\)不在R裡面
更新次方\(y=y+u=2+2=4\)
\(b=b*c= 4 * 4 \equiv 16\pmod{181}\)
\(s=u+1=3\)
\(u=2*u=4\)
倍增步長\(c=c^2=16\)
2.計算BabyStep-------
計算\(2^{-13}\pmod{181}\),\(a=a*h= 27 * 91 \equiv 104\pmod{181}\)
\(R=R\cup[104,3]\)
計算\(2^{-14}\pmod{181}\),\(a=a*h= 104 * 91 \equiv 52\pmod{181}\)
\(R=R\cup[52,4]\)
BabyStep=\([[54,1],[27,2],[104,3],[52,4]]\)
3.計算GiantStep-------
計算\(2^4 \equiv 16\pmod{181}\)不在R裡面
更新次方\(y=y+u=4+4=8\)
\(b=b*c= 16 * 16 \equiv 75\pmod{181}\)
計算\(2^8 \equiv 75\pmod{181}\)不在R裡面
更新次方\(y=y+u= 8 + 4 = 12\)
\(b=b*c= 75 * 16 \equiv 114\pmod{181}\)
計算\(2^{12} \equiv 114\pmod{181}\)不在R裡面
更新次方\(y=y+u=12+4=16\)
\(b=b*c= 114 * 16 \equiv 14\pmod{181}\)
\(s=u+1= 5\)
\(u=2*u= 8\)
倍增步長\(c=c^2 = 256\)
2.計算BabyStep-------
計算\(2^{-15}\pmod{181}\),\(a=a*h= 52 * 91 \equiv 26\pmod{181}\)
\(R=R\cup[26,5]\)
計算\(2^{-16}\pmod{181}\),\(a=a*h= 26 * 91 \equiv 13\pmod{181}\)
\(R=R\cup[13,6]\)
計算\(2^{-17}\pmod{181}\),\(a=a*h= 13 * 91 \equiv 97\pmod{181}\)
\(R=R\cup[97,7]\)
計算\(2^{-18}\pmod{181}\),\(a=a*h= 97 * 91 \equiv 139\pmod{181}\)
\(R=R\cup[139,8]\)
BabyStep=\([[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],[97,7],[139,8]]\)
3.計算GiantStep-------
計算\(2^{16} \equiv 14\pmod{181}\)不在R裡面
更新次方\(y=y+u=16+8=24\)
\(b=b*c= 14 * 256 \equiv 145\pmod{181}\)
計算\(2^{24} \equiv 145\pmod{181}\)不在R裡面
更新次方\(y=y+u= 24 + 8 = 32\)
\(b=b*c= 145 * 256 \equiv 15\pmod{181}\)
計算\(2^{32} \equiv 15\pmod{181}\)不在R裡面
更新次方\(y=y+u= 32 + 8 = 40\)
\(b=b*c= 15 * 256 \equiv 39\pmod{181}\)
計算\(2^{40} \equiv 39\pmod{181}\)不在R裡面
更新次方\(y=y+u= 40 + 8 = 48\)
\(b=b*c= 39 * 256 \equiv 29\pmod{181}\)
計算\(2^{48} \equiv 29\pmod{181}\)不在R裡面
更新次方\(y=y+u= 48 + 8 = 56\)
\(b=b*c= 29 * 256 \equiv 3\pmod{181}\)
計算\(2^{56} \equiv 3\pmod{181}\)不在R裡面
更新次方\(y=y+u= 56 + 8 = 64\)
\(b=b*c= 3 * 256 \equiv 44\pmod{181}\)
\(s=u+1= 9\)
\(u=2*u= 16\)
倍增步長\(c=c^2 = 65536\)
2.計算BabyStep-------
計算\(2^{-19}\pmod{181}\),\(a=a*h= 139 * 91 \equiv 160\pmod{181}\)
\(R=R\cup[160,9]\)
計算\(2^{-20}\pmod{181}\),\(a=a*h= 160 * 91 \equiv 80\pmod{181}\)
\(R=R\cup[80,10]\)
計算\(2^{-21}\pmod{181}\),\(a=a*h= 80 * 91 \equiv 40\pmod{181}\)
\(R=R\cup[40,11]\)
計算\(2^{-22}\pmod{181}\),\(a=a*h= 40 * 91 \equiv 20\pmod{181}\)
\(R=R\cup[20,12]\)
計算\(2^{-23}\pmod{181}\),\(a=a*h= 20 * 91 \equiv 10\pmod{181}\)
\(R=R\cup[10,13]\)
計算\(2^{-24}\pmod{181}\),\(a=a*h= 10 * 91 \equiv 5\pmod{181}\)
\(R=R\cup[5,14]\)
計算\(2^{-25}\pmod{181}\),\(a=a*h= 5 * 91 \equiv 93\pmod{181}\)
\(R=R\cup[93,15]\)
計算\(2^{-26}\pmod{181}\),\(a=a*h= 93 * 91 \equiv 137\pmod{181}\)
\(R=R\cup[137,16]\)
BabyStep=\([[54,1],[27,2],[104,3],[52,4],[26,5],[13,6],[97,7],[139,8],\)
\([160,9],[80,10],[40,11],[20,12],[10,13],[5,14],[93,15],[137,16]]\)
3.計算GiantStep-------
計算\(2^{64} \equiv 44\pmod{181}\)不在R裡面
更新次方\(y=y+u= 64 + 16 = 80\)
\(b=b*c= 44 * 65536 \equiv 73\pmod{181}\)
計算\(2^{80} \equiv 73\pmod{181}\)不在R裡面
更新次方\(y=y+u= 80 + 16 = 96 \)
\(b=b*c= 73 * 65536 \equiv 117\pmod{181}\)
計算\(2^{96} \equiv 117\pmod{181}\)不在R裡面
更新次方\(y=y+u= 96 + 16 = 112 \)
\(b=b*c= 117 * 65536 \equiv 9\pmod{181}\)
計算\(2^{112} \equiv 9\pmod{181}\)不在R裡面
更新次方\(y=y+u= 112 + 16 = 128 \)
\(b=b*c= 9 * 65536 \equiv 126\pmod{181}\)
計算\(2^{128} \equiv 126\pmod{181}\)不在R裡面
更新次方\(y=y+u= 128 + 16 = 144 \)
\(b=b*c= 126 * 65536 \equiv 135\pmod{181}\)
計算\(2^{144} \equiv 135\pmod{181}\)不在R裡面
更新次方\(y=y+u= 144 + 16 = 160 \)
\(b=b*c= 135 * 65536 \equiv 80\pmod{181}\)
計算\(2^{160} \equiv 80\pmod{181}\)在\(R[10]=[80,10]\)裡面
解答\(x=y+r+C= 160 + 10 + 10 = 180 \)
\(s=u+1= 17\)
\(u=2*u= 32\)
倍增步長\(c=c^2 = 4294967296\)
(x) 180



--------------------------------
論文中演算法3.1將計算order和解離散對數問題結合在一起
\(g^x \equiv d \pmod{p}\)
\(g^{y+r}\equiv d \pmod{p}\)
\(d^{-1}g^y\equiv g^{-r}\pmod{p}\)
計算\(g^{-r}\)稱為Baby step
計算\(d^{-1}g^y\)稱為Giant step

輸入:\(d,g \in G(d\ne 1)\),初始步長\(v\)(\(v\)要是偶數)
輸出:執行結果\(t=1\),若\(d \in \langle\;g \rangle\;\),則離散對數問題的解\(x=log_g d\)
   執行結果\(t=0\),若\(d \notin \langle\;g \rangle\;\),則\(g\)的oder為\(x=|\;\langle\;g \rangle\; |\;\)
(1) \(t=2;x=0\)
(2) \(s=1;y=v;u=v\)
(3) \(h=g^{−1}\)
(4) \(a=1;b=g^v;c=b\)   /*\(a=g^{−r},b=g^y,c=g^u\)*/
(5) \(R=\phi\)
(6) \(f=d^{−1}\)
(7) while(\(t==2\))do
(8)  for(\(r=s,s+1\ldots,u\)) do  /*new baby steps*/
(9)   \(a=a*h\)
(10)   \(if(s==1)then\)     /*check if \(1\le x\le v\)*/
(11)    if(\(a==f\))then
(12)     \(x=r;t=1\)
(13)     break while
(14)    else
(15)     if(\(a==1\))then
(16)      \(x=r;t=0\)
(17)      break while
(18)     else
(19)      \(R=R\cup \{\;(a,r) \}\;\)
(20)     fi
(21)    fi
(22)   else
(23)     \(R=R\cup \{\;(a,r) \}\;\)
(24)   fi
(25)  od
(26)  while(\(t==2\) and \(y<u^2\)) do  /*giant steps*/
(27)   if(there is a number \(r\) such /*checking for discrete log.*/
(28)    that \((f*b,r)\in R)\) then
(29)    \(x=y+r;t=1\)
(30)   else
(31)    if (there is a number \(r\) such  /*checking for the order of \(g\)*/
(32)     that \((b,r)\in R\)) then
(33)     \(x=y+r;t=0\)
(34)    else
(35)     \(y=y+u\)
(36)     \(b=b*c\)
(37)    fi
(38)   fi
(39)  od
(40)  \(s=u+1;u=2u\)           /*double step-width*/
(41)  \(c=c^2\)               
(42) od
(43) return(\(t,x\))



利用Baby_stepDoubleGiant_step方法解離散對數問題副程式
(%i1)
DiscreteLogarithm(d,g,p,v):=block
([t,x,s,y,u,h,a,b,c,R,f,r],
print("1.變數初始化------------"),
print("t=",t:2),
print("x=",x:0),
print("s=",s:1),
print("y=v=",y:v),
print("u=v=",u:v),
print("h=","g"^"-1","=",g^"-1","≡",h:inv_mod(g,p),"(mod",p,")"),
print("a=",a:1),
print("b=g"^"v","=",b:g^v),
print("c=b=",c:b),
print("R=",R:[]),
print("f=","d"^"-1","=",d^"-1","≡",f:inv_mod(d,p),"(mod",p,")"),
while t=2 do
  (print("2.計算BabyStep------------"),
   for r:s thru u do
     (print("計算",g^concat("-",r),"(mod",p,"),a=a*h=",a,"*",h,"≡",a:mod(a*h,p),"(mod",p,")"),
      if s=1 then
        (if a=f then
           (print("x=r=",x:r),
            print("t=1",t:1),
            return(x)
           )
         else
           (if a=1 then
              (print("x=r=",x:r),
               print("t=0",t:0),
               return(x)
              )
            else
              (R:append(R,[[a,r]]),
               print("R=R∪",[a,r])
              )
           )
        )
      else
        (R:append(R,[[a,r]]),
         print("R=R∪",[a,r])
        )
     ),
   print("BabyStep=",R),
   print("3.計算GiantStep------------"),
   while t=2 and y<u^2 do
     (if (r:assoc(mod(f*b,p),R))#false then
        (print("計算",d^"-1","*",g,""^y,"(mod",p,"),f*b=",f,"*",b,"≡",mod(f*b,p),"(mod",p,")在R[",r,"]=",R[r],"裡面"),
         print("解答x=y+r=",y,"+",r,"=",x:y+r),
         print("狀態t=",t:1),
         return(x)
        )
      else
        (print("計算",d^"-1","*",g,""^y,"(mod",p,"),f*b=",f,"*",b,"≡",mod(f*b,p),"(mod",p,")不在R裡面"),
         print("更新次方,y=y+u=",y,"+",u,"=",y:y+u),
         print("計算",g,""^y,"(mod",p,"),b=b*c=",b,"*",c,"≡",b:mod(b*c,p),"(mod",p,")")
        )
     ),
    print("s=u+1=",s:u+1),
    print("u=2*u=",u:2*u),
    print("倍增步長,c=c"^2,"=",c:c^2),
    k:k+1
  ),
return([t,x])
)$


\(g^x \equiv d\pmod{p}\),初始步長\(v\)要是偶數
(%i5)
d:108;
g:2;
p:181;
v:2;

(d) 108
(g) 2
(p) 181
(v) 2

利用Baby_stepDoubleGiant_step方法計算g的order或解離散對數問題
(%i6) [t,x]: DiscreteLogarithm(d,g,p,v);
1.變數初始化------------
\(t=2\)
\(x=0\)
\(s=1\)
\(y=v=2\)
\(u=v=2\)
\(h=g^{-1}=2^{-1} \equiv 91 \pmod{181}\)
\(a=1\)
\(b=g^v=4\)
\(c=b=4\)
\(R=[]\)
\(f=d^{-1}=108^{-1} \equiv 119 \pmod{181}\)
2.計算BabyStep------------
計算\(2^{-1} \pmod{181}\),\(a=a*h= 1*91 \equiv 91 \pmod{181}\)
\(R=R\cup [91,1]\)
計算\(2^{-2} \pmod{181}\),\(a=a*h= 91*91 \equiv 136 \pmod{181}\)
\(R=R\cup [136,2]\)
BabyStep\(=[[91,1],[136,2]]\)
3.計算GiantStep------------
計算\(108^{-1}*2^2 \pmod{181}\),\(f*b= 119*4 \equiv 114 \pmod{181}\)不在R裡面
更新次方,\(y=y+u=2+2=4\)
計算\(2^4 \pmod{181}\),\(b=b*c= 4*4 \equiv 16 \pmod{181}\)
\(s=u+1=3\)
\(u=2*u=4\)
倍增步長,\(c=c^2=16\)
2.計算BabyStep------------
計算\(2^{-3} \pmod{181}\),\(a=a*h= 136*91 \equiv 68 \pmod{181}\)
\(R=R\cup [68,3]\)
計算\(2^{-4} \pmod{181}\),\(a=a*h= 68*91 \equiv 34 \pmod{181}\)
\(R=R\cup[34,4]\)
BabyStep\(=[[91,1],[136,2],[68,3],[34,4]]\)
3.計算GiantStep------------
計算\(108^{-1}*2^4 \pmod{181}\),\(f*b= 119*16 \equiv 94 \pmod{181}\)不在R裡面
更新次方,\(y=y+u=4+4=8\)
計算\(2^8 \pmod{181}\),\(b=b*c=16*16 \equiv 75 \pmod{181}\)
計算\(108^{-1}*2^8 \pmod{181}\),\(f*b= 119*75 \equiv 56 \pmod{181}\)不在R裡面
更新次方,\(y=y+u=8+4=12\)
計算\(2^{12} \pmod{181}\),\(b=b*c=75*16 \equiv 114 \pmod{181}\)
計算\(108^{-1}*2^{12} \pmod{181}\),\(f*b= 119*114 \equiv 172 \pmod{181}\)不在R裡面
更新次方,\(y=y+u=12+4=16\)
計算\(2^{16} \pmod{181}\),\(b=b*c=114*16 \equiv 14 \pmod{181}\)
\(s=u+1=5\)
\(u=2*u=8\)
倍增步長,\(c=c^2=256\)
2.計算BabyStep------------
計算\(2^{-5} \pmod{181}\),\(a=a*h= 34*91 \equiv 17 \pmod{181}\)
\(R=R\cup [17,5]\)
計算\(2^{-6} \pmod{181}\),\(a=a*h= 17*91 \equiv 99 \pmod{181}\)
\(R=R\cup [99,6]\)
計算\(2^{-7} \pmod{181}\),\(a=a*h= 99*91 \equiv 140 \pmod{181}\)
\(R=R\cup [140,7]\)
計算\(2^{-8} \pmod{181}\),\(a=a*h= 140*91 \equiv 70 \pmod{181}\)
\(R=R\cup [70,8]\)
BabyStep\(=[[91,1],[136,2],[68,3],[34,4],[17,5],[99,6],[140,7],[70,8]]\)
3.計算GiantStep------------
計算\(108^{-1}*2^{16} \pmod{181}\),\(f*b= 119*14 \equiv 37 \pmod{181}\)不在R裡面
更新次方,\(y=y+u=16+8=24\)
計算\(2^{24} \pmod{181}\),\(b=b*c= 14*256 \equiv 145 \pmod{181}\)
計算\(108^{-1}*2^{24} \pmod{181}\),\(f*b= 119*145 \equiv 60 \pmod{181}\)不在R裡面
更新次方,\(y=y+u=24+8=32\)
計算\(2^{32} \pmod{181}\),\(b=b*c= 145*256 \equiv 15 \pmod{181}\)
計算\(108^{-1}*2^{32} \pmod{181}\),\(f*b= 119*15 \equiv 156 \pmod{181}\)不在R裡面
更新次方,y=y+u= 32 + 8=40
計算\(2^{40} \pmod{181}\),\(b=b*c= 15*256 \equiv 39 \pmod{181}\)
計算\(108^{-1}*2^{40} \pmod{181}\),\(f*b= 119*39 \equiv 116 \pmod{181}\)不在R裡面
更新次方,y=y+u= 40 + 8=48
計算\(2^{48} \pmod{181}\),\(b=b*c= 39*256 \equiv 29 \pmod{181}\)
計算\(108^{-1}*2^{48} \pmod{181}\),\(f*b= 119*29 \equiv 12 \pmod{181}\)不在R裡面
更新次方,y=y+u= 48 + 8=56
計算\(2^{56} \pmod{181}\),\(b=b*c= 29*256 \equiv 3 \pmod{181}\)
計算\(108^{-1}*2^{56} \pmod{181}\),\(f*b= 119*3 \equiv 176 \pmod{181}\)不在R裡面
更新次方,y=y+u= 56 + 8=64
計算\(2^{64} \pmod{181}\),\(b=b*c= 3*256 \equiv 44 \pmod{181}\)
\(s=u+1=9\)
\(u=2*u=16\)
倍增步長,\(c=c^2=65536\)
2.計算BabyStep------------
計算\(2^{-9} \pmod{181},a=a*h= 70*91 \equiv 35 \pmod{181}\)
\(R=R\cup [35,9]\)
計算\(2^{-10} \pmod{181},a=a*h= 35*91 \equiv 108 \pmod{181}\)
\(R=R\cup [108,10]\)
計算\(2^{-11} \pmod{181},a=a*h= 108*91 \equiv 54 \pmod{181}\)
\(R=R\cup [54,11]\)
計算\(2^{-12} \pmod{181},a=a*h= 54*91 \equiv 27 \pmod{181}\)
\(R=R\cup [27,12]\)
計算\(2^{-13} \pmod{181},a=a*h= 27*91 \equiv 104 \pmod{181}\)
\(R=R\cup [104,13]\)
計算\(2^{-14} \pmod{181},a=a*h= 104*91 \equiv 52 \pmod{181}\)
\(R=R\cup [52,14]\)
計算\(2^{-15} \pmod{181},a=a*h= 52*91 \equiv 26 \pmod{181}\)
\(R=R\cup [26,15]\)
計算\(2^{-16} \pmod{181},a=a*h= 26*91 \equiv 13 \pmod{181}\)
\(R=R\cup [13,16]\)
BabyStep\(=[[91,1],[136,2],[68,3],[34,4],[17,5],[99,6],[140,7],[70,8],\)
\([35,9],[108,10],[54,11],[27,12],[104,13],[52,14],[26,15],[13,16]]\)
3.計算GiantStep------------
計算\(108^{-1}*2^{64} \pmod{181}\),\(f*b= 119*44 \equiv 168 \pmod{181}\)不在R裡面
更新次方,y=y+u= 64 + 16=80
計算\(2^{80} \pmod{181}\),\(b=b*c= 44*65536 \equiv 73 \pmod{181}\)
計算\(108^{-1}*2^{80} \pmod{181}\),\(f*b= 119*73 \equiv 180 \pmod{181}\)不在R裡面
更新次方,y=y+u= 80 + 16=96
計算\(2^{96} \pmod{181}\),\(b=b*c= 73*65536 \equiv 117 \pmod{181}\)
計算\(108^{-1}*2^{96} \pmod{181}\),\(f*b= 119*117 \equiv 167 \pmod{181}\)不在R裡面
更新次方,y=y+u= 96 + 16=112
計算\(2^{112} \pmod{181}\),\(b=b*c= 117*65536 \equiv 9 \pmod{181}\)
計算\(108^{-1}*2^{112} \pmod{181}\),\(f*b= 119*9 \equiv 166 \pmod{181}\)不在R裡面
更新次方,y=y+u= 112 + 16=128
計算\(2^{128} \pmod{181}\),\(b=b*c= 9*65536 \equiv 126 \pmod{181}\)
計算\(108^{-1}*2^{128} \pmod{181}\),\(f*b= 119*126 \equiv 152 \pmod{181}\)不在R裡面
更新次方,y=y+u= 128 + 16=144
計算\(2^{144} \pmod{181}\),\(b=b*c= 126*65536 \equiv 135 \pmod{181}\)
計算\(108^{-1}*2^{144} \pmod{181}\),\(f*b= 119*135 \equiv 137 \pmod{181}\)不在R裡面
更新次方,y=y+u= 144 + 16=160
計算\(2^{160} \pmod{181}\),\(b=b*c= 135*65536 \equiv 80 \pmod{181}\)
計算\(108^{-1}*2^{160} \pmod{181}\),\(f*b= 119*80 \equiv 108 \pmod{181}\)在\(R[10]=[108,10]\) 裡面
解答\(x=y+r=160+10=170\)
狀態\(t=1\)
\(s=u+1=17\)
\(u=2*u=32\)
倍增步長,\(c=c^2=4294967296\)
(%o6) \([1,170]\)

TOP

4.解離散對數問題的方法-小步和線性增加步長的大步

原本的小步大步小步和倍增步長的大步小步和線性增加步長的大步
將答案改寫成\(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
每次步長都是\(\alpha^{-m}\)
將答案改寫成\(x=2^kvq+r\) (\(x\)除以\(2^kv\),商數\(q\),餘數\(r\))
其中\(v\)為偶數,\(k\ge 0\),\(1\le r \le 2^kv\)

\(\alpha^x \equiv \beta \pmod{p}\)
\(\displaystyle \alpha^{2^kvq+r}\equiv \beta \pmod{p}\)
\(\displaystyle \beta \alpha^{-r}\equiv (\alpha^{2^kv})^q \pmod{p}\)
計算\( \beta\alpha^{-r}\)稱為Baby step
計算\((\alpha^{2^kv})^q\)稱為Giant step
每次步長\(\alpha^{2^kv}\)隨著\(k\)值倍增
將答案改寫成\(x=t_j-i\)
其中\(t_0=2v\),\(t_{j+1}=t_j+j+v+1\)

\(\alpha^x \equiv \beta \pmod{p}\)
\(\alpha^{t_j-i}\equiv \beta \pmod{p}\)
\(\alpha^{t_j} \equiv \beta \alpha^i \pmod{p}\)
計算\(\beta \alpha^i\)稱為Baby Step
計算\(\alpha^{t_j}\)稱為Giant Step
每次步長\(\alpha^{t_j}\)隨著\(j\)值線性增加(\(t_{j+1}=t_j+j+v+1\))


以\(2^n \equiv 1\pmod{181}\),參數\(v=2\)為例。
\(\matrix{ &BabyStep&GiantStep\cr
 &2^0\equiv1\pmod{181}& \cr
 &2^1\equiv2\pmod{181}& \cr
j=0&2^2\equiv4\pmod{181}&t=2v=4\cr
j=j+1=1&2^{j+v}=2^3\equiv8\pmod{181}&t=t+j+v=4+1+2=7,2^7\equiv128\pmod{181}\cr
j=j+1=2&2^{j+v}=2^4\equiv16\pmod{181}&t=t+j+v=7+2+2=11,2^{11}\equiv57\pmod{181}\cr
j=j+1=3&2^{j+v}=2^5\equiv32\pmod{181}&t=t+j+v=11+3+2=16,2^{16}\equiv14\pmod{181}\cr
j=j+1=4&2^{j+v}=2^6\equiv64\pmod{181}&t=t+j+v=16+4+2=22,2^{22}\equiv172\pmod{181}\cr
j=j+1=5&2^{j+v}=2^7\equiv128\pmod{181}&t=t+j+v=22+5+2=29,2^{29}\equiv115\pmod{181}\cr
j=j+1=6&2^{j+v}=2^8\equiv75\pmod{181}&t=t+j+v=29+6+2=37,2^{37}\equiv118\pmod{181}\cr
j=j+1=7&2^{j+v}=2^9\equiv150\pmod{181}&t=t+j+v=37+7+2=46,2^{46}\equiv143\pmod{181}\cr
j=j+1=8&2^{j+v}=2^{10}\equiv119\pmod{181}&t=t+j+v=46+8+2=56,2^{56}\equiv3\pmod{181}\cr
j=j+1=9&2^{j+v}=\color{blue}{2^{11}\equiv57}\pmod{181}&t=t+j+v=56+9+2=67,2^{67}\equiv171\pmod{181}\cr
j=j+1=10&2^{j+v}=2^{12}\equiv114\pmod{181}&t=t+j+v=67+10+2=79,2^{79}\equiv127\pmod{181}\cr
j=j+1=11&2^{j+v}=2^{13}\equiv47\pmod{181}&t=t+j+v=79+11+2=92,2^{92}\equiv177\pmod{181}\cr
j=j+1=12&2^{j+v}=2^{14}\equiv94\pmod{181}&t=t+j+v=92+12+2=106,2^{106}\equiv167\pmod{181}\cr
j=j+1=13&2^{j+v}=2^{15}\equiv7\pmod{181}&t=t+j+v=106+13+2=121,2^{121}\equiv83\pmod{181}\cr
j=j+1=14&2^{j+v}=2^{16}\equiv14\pmod{181}&t=t+j+v=121+14+2=137,2^{137}\equiv76\pmod{181}\cr
j=j+1=15&2^{j+v}=2^{17}\equiv28\pmod{181}&t=t+j+v=137+15+2=154,2^{154}\equiv137\pmod{181}\cr
j=j+1=16&2^{j+v}=2^{18}\equiv56\pmod{181}&t=t+j+v=154+16+2=172,2^{172}\equiv70\pmod{181}\cr
j=j+1=17&2^{j+v}=2^{19}\equiv112\pmod{181}&t=t+j+v=172+17+2=191,\color{blue}{2^{191}\equiv57}\pmod{181}}\)
找到\(2^{11}=2^{191}\equiv 57\pmod{181}\),故\(n=191-11=180\),\(2^{180}\equiv 1\pmod{181}\)



演算法2.1,計算\(g\)的order。
輸入:\(g \in G\),\(v \in Z\),\(v\ge 2\)
輸出:\(n=|\;g|\;\)
(1)if (g == 1) then            /* trivial case */
(2) return (1)
(3)else
(4) n = 0; i = 1; R ={(1, 0),(g,1)}; a = g   /* initialization */
(5) while (n == 0 and i < v) do
(6)  a = g*a; i = i + 1          /* baby steps */
(7)  if (a == 1) then
(8)   n = i              /* found order among baby steps */
(9)   return (n)
(10)  else
(11)   R = R ∪ {(a,i)}         /* update hash table */
(12)  fi
(13) od
(14) j = 0; b = a*a; t = 2*v        /* initialize giant steps (\(t = t_j\)) */
(15) while (n == 0) do
(16)  if (there exists a number i such that (b; i) 2 R) then  /* table lookup */
(17)   n = t - i             /* order of g */
(18)   return (n)
(19)   break while
(20)  else
(21)   a = g*a; j = j + 1; R = R∪{(a,j + v)} /*baby step */
(22)   b = a*b; t = t + j + v        /* giant step */
(23)  fi
(24) od
(25)fi

參考資料:https://www.ams.org/journals/mco ... 5718-99-01141-2.pdf


計算一個元素g的Order副程式
(%i1)
Order(g,p,v):=block
([n,i,R,a],
if g=1 then
  (return(1)
  )
else
  (print("1.變數初始化-------"),
   print("n=",n:0),
   print("i=",i:1),
   print("R=",R:[[1,0],[g,1]]),
   print("a=",a:g),
   print("2.計算i=2~v的BabyStep-------"),
   while n=0 and i<v do
      (print("i=i+1=",i:i+1),
       print("計算",g,""^i,"(mod",p,"),","a=g*a=",g,"*",a,"≡",a:mod(g*a,p),"(mod",p,")"),
       if a=1 then
         (print("解答n=",n:i),
          return(n)
         )
       else
         (print("R=R∪[a,i]=",R:append(R,[[a,i]]))
         )
      ),
   print("3.計算BabyStep和GiantStep-------"),
   print("j=",j:0),
   print("b=a*a=",a,"*",a,"=",b:a^2),
   print("t=2*v=2*",v,"=",t:2*v),
   while n=0 do
      (if (i:assoc(b,R))#false then
         (print("R=",R),
          print("b=",b,"在R[",i+1,"]=",R[i+1],"裡面"),
          print("解答n=t-i=",t,"-",i,"=",n:t-i),
          return(n)
         )
       else
         (print("b=",b,"不在R裡面"),
          print("更新次方j=j+1=",j:j+1),
          print("計算BabyStep,",g^"j+v","=",g,""^(j+v),"(mod",p,"),","a=g*a=",g,"*",a,"≡",a:mod(g*a,p),"(mod",p,")"),
          print("R=R∪",[a,j+v]),R:append(R,[[a,j+v]]),
          print("更新次方t=t+j+v=",t,"+",j,"+",v,"=",t:t+j+v),
          print("計算GiantStep,g"^"t","=",g,""^t,"(mod",p,"),b=a*b=",a,"*",b,"≡",b:mod(a*b,p),"(mod",p,")")
         ),
       print("--------")
      )
  )
)$


\(g^x \equiv 1\pmod{p}\),初始值v
(%i4)
g:2;
p:181;
v:2;

(g) 2
(p) 181
(v) 2

利用Baby_stepLinearGiant_step方法計算g的order
(%i5) n:Order(g,p,v);
1.變數初始化-------
\(n=0\)
\(i=1\)
\(R=[[1,0],[2,1]]\)
\(a=2\)
2.計算i=2~v的BabyStep-------
\(i=i+1= 2\)
計算\(2^2\pmod{181}\),\(a=g*a=2 * 2 \equiv 4\pmod{181}\)
\(R=R\cup[a,i]= [[1,0],[2,1],[4,2]]\)
3.計算BabyStep和GiantStep-------
\(j=0\)
\(b=a*a=4*4=16\)
\(t=2*v=2*2=4\)
\(b=16\)不在R裡面
更新次方\(j=j+1=1\)
計算BabyStep,\(2^{j+v}=2^3\pmod{181}\),\(a=g*a=2*4 \equiv 8\pmod{181}\)
\(R=R\cup [8,3]\)
更新次方\(t=t+j+v=4+1+2=7\)
計算GiantStep,\(g^t=2 ^7\pmod{181}\),\(b=a*b=8*16 \equiv 128\pmod{181}\)
--------
\(b=128\)不在R裡面
更新次方\(j=j+1=2\)
計算BabyStep,\(2^{j+v}=2^4\pmod{181}\),\(a=g*a=2*8 \equiv 16\pmod{181}\)
\(R=R\cup [16,4]\)
更新次方\(t=t+j+v=7+2+2=11\)
計算GiantStep,\(g^t=2^{11}\pmod{181}\),\(b=a*b=16*128 \equiv 57\pmod{181}\)
--------
\(b=57\)不在R裡面
更新次方\(j=j+1=3\)
計算BabyStep,\(2^{j+v}=2^5\pmod{181}\),\(a=g*a=2*16 \equiv 32\pmod{181}\)
\(R=R\cup [32,5]\)
更新次方\(t=t+j+v=11+3+2=16\)
計算GiantStep,\(g^t=2^{16}\pmod{181}\),\(b=a*b=32*57 \equiv 14\pmod{181}\)
--------
\(b=14\)不在R裡面
更新次方\(j=j+1=4\)
計算BabyStep,\(2^{j+v}=2^6\pmod{181}\),\(a=g*a=2*32 \equiv 64\pmod{181}\)
\(R=R\cup [64,6]\)
更新次方\(t=t+j+v=16+4+2=22\)
計算GiantStep,\(g^t=2 ^{22}\pmod{181}\),\(b=a*b=64*14 \equiv 172\pmod{181}\)
--------
\(b=172\)不在R裡面
更新次方\(j=j+1=5\)
計算BabyStep,\(2^{j+v}=2^7\pmod{181}\),\(a=g*a=2*64 \equiv 128\pmod{181}\)
\(R=R\cup [128,7]\)
更新次方\(t=t+j+v=22+5+2=29\)
計算GiantStep,\(g^t=2 ^{29}\pmod{181}\),\(b=a*b=128*172 \equiv 115\pmod{181}\)
--------
\(b=115\)不在R裡面
更新次方\(j=j+1=6\)
計算BabyStep,\(2^{j+v}=2^8\pmod{181}\),\(a=g*a=2*128 \equiv 75\pmod{181}\)
\(R=R\cup [75,8]\)
更新次方\(t=t+j+v=29+6+2=37\)
計算GiantStep,\(g^t=2^{37}\pmod{181}\),\(b=a*b=75*115 \equiv 118\pmod{181}\)
--------
\(b=118\)不在R裡面
更新次方\(j=j+1=7\)
計算BabyStep,\(2^{j+v}=2^9\pmod{181}\),\(a=g*a=2*75 \equiv 150\pmod{181}\)
\(R=R\cup [150,9]\)
更新次方\(t=t+j+v=37+7+2=46\)
計算GiantStep,\(g^t=2^{46}\pmod{181}\),\(b=a*b=150*118 \equiv 143\pmod{181}\)
--------
\(b=143\)不在R裡面
更新次方\(j=j+1=8\)
計算BabyStep,\(2^{j+v}=2^{10}\pmod{181}\),\(a=g*a=2*150 \equiv 119\pmod{181}\)
\(R=R\cup [119,10]\)
更新次方\(t=t+j+v=46+8+2=56\)
計算GiantStep,\(g^t=2^{56}\pmod{181}\),\(b=a*b=119*143 \equiv 3\pmod{181}\)
--------
\(b=3\)不在R裡面
更新次方\(j=j+1=9\)
計算BabyStep,\(2^{j+v}=2^{11}\pmod{181}\),\(a=g*a=2*119 \equiv 57\pmod{181}\)
\(R=R\cup [57,11]\)
更新次方\(t=t+j+v=56+9+2=67\)
計算GiantStep,\(g^t=2^{67}\pmod{181}\),\(b=a*b=57*3 \equiv 171\pmod{181}\)
--------
\(b=171\)不在R裡面
更新次方\(j=j+1=10\)
計算BabyStep,\(2^{j+v}=2^{12}\pmod{181}\),\(a=g*a=2*57 \equiv 114\pmod{181}\)
\(R=R\cup [114,12]\)
更新次方\(t=t+j+v=67+10+2=79\)
計算GiantStep,\(g^t=2^{79}\pmod{181}\),\(b=a*b=114*171 \equiv 127\pmod{181}\)
--------
\(b=127\)不在R裡面
更新次方\(j=j+1=11\)
計算BabyStep,\(2^{j+v}=2^{13}\pmod{181}\),\(a=g*a=2*114 \equiv 47\pmod{181}\)
\(R=R\cup [47,13]\)
更新次方\(t=t+j+v=79+11+2=92\)
計算GiantStep,\(g^t=2^{92}\pmod{181}\),\(b=a*b=47*127 \equiv 177\pmod{181}\)
--------
\(b=177\)不在R裡面
更新次方\(j=j+1=12\)
計算BabyStep,\(2^{j+v}=2^{14}\pmod{181}\),\(a=g*a=2*47 \equiv 94\pmod{181}\)
\(R=R\cup [94,14]\)
更新次方\(t=t+j+v=92+12+2=106\)
計算GiantStep,\(g^t=2^{106}\pmod{181}\),\(b=a*b=94*177 \equiv 167\pmod{181}\)
--------
\(b=167\)不在R裡面
更新次方\(j=j+1=13\)
計算BabyStep,\(2^{j+v}=2^{15}\pmod{181}\),\(a=g*a=2*94 \equiv 7\pmod{181}\)
\(R=R\cup [7,15]\)
更新次方\(t=t+j+v=106+13+2=121\)
計算GiantStep,\(g^t=2^{121}\pmod{181}\),\(b=a*b=7*167 \equiv 83\pmod{181}\)
--------
\(b=83\)不在R裡面
更新次方\(j=j+1=14\)
計算BabyStep,\(2^{j+v}=2^{16}\pmod{181}\),\(a=g*a=2*7 \equiv 14\pmod{181}\)
\(R=R\cup [14,16]\)
更新次方\(t=t+j+v=121+14+2=137\)
計算GiantStep,\(g^t=2^{137}\pmod{181}\),\(b=a*b=14*83 \equiv 76\pmod{181}\)
--------
\(b=76\)不在R裡面
更新次方\(j=j+1=15\)
計算BabyStep,\(2^{j+v}=2^{17}\pmod{181}\),\(a=g*a=2*14 \equiv 28\pmod{181}\)
\(R=R\cup [28,17]\)
更新次方\(t=t+j+v=137+15+2=154\)
計算GiantStep,\(g^t=2^{154}\pmod{181}\),\(b=a*b=28*76 \equiv 137\pmod{181}\)
--------
\(b=137\)不在R裡面
更新次方\(j=j+1=16\)
計算BabyStep,\(2^{j+v}=2^{18}\pmod{181}\),\(a=g*a=2*28 \equiv 56\pmod{181}\)
\(R=R\cup [56,18]\)
更新次方\(t=t+j+v=154+16+2=172\)
計算GiantStep,\(g^t=2^{172}\pmod{181}\),\(b=a*b=56*137 \equiv 70\pmod{181}\)
--------
\(b=70\)不在R裡面
更新次方\(j=j+1=17\)
計算BabyStep,\(2^{j+v}=2^{19}\pmod{181}\),\(a=g*a=2*56 \equiv 112\pmod{181}\)
\(R=R\cup [112,19]\)
更新次方\(t=t+j+v=172+17+2=191\)
計算GiantStep,\(g^t=2^{191}\pmod{181}\),\(b=a*b=112*70 \equiv 57\pmod{181}\)
--------
\(R= [[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],[94,14],[7,15],[14,16],[28,17],[56,18],[112,19]]\)
\(b=57\)在\(R[12]=[57,11]\)裡面
解答\(n=t-i=191-11=180\)
(n) 180

TOP

5-1.低漢明權重(Low Hamming Weight)的離散對數問題-Heiman-Odlyzko方法

原本的離散對數問題\(\alpha^x \equiv \beta \pmod{p}\)的解\(x\)以二進位表示為
\(\displaystyle x=\sum_{i=0}^{m-1}x_i2^i\),\(x_i \in \{\;0,1 \}\;\),\(0\le i \le m-1\),\(m=\lceil\;log_2 ord(\alpha)\rceil\;\),\(ord(\alpha)\)代表\(\alpha\)的order
以\(wt(x)\)表示\(x\)的二進位中有多少個1,稱為\(x\)的漢明權重(Hamming Weight)。實務上以平方-相乘方法計算\(\alpha^x\)時,先將\(x\)表示成二進位,當遇到數字0時計算平方,遇到數字1時計算相乘,因為計算平方快於計算相乘,解\(x\)的二進位以較少的1來減少相乘運算,此時解\(x\)的漢明權重偏少,但\(x\)的漢明權重\(wt(x)=t\)太少時,有方法可以解出\(x\)。

以\(2^x\equiv 108 \pmod{181}\),已知\(x\)的漢明權重為\(t=4\)為例。
\(m=\lceil\;log_2 ord(2)\rceil\;=\lceil\;log_2 180\rceil\;=8\)
\(Z_m=\{\; 0,1,2,3,4,5,6,7\}\;\)
取\(Z_m\)所有元素個數為2(\(\displaystyle |\;Y_1|\;=|\;Y_2|\;=\frac{t}{2}=2\))的子集合\(Y_1\)和\(Y_2\)。
\(\matrix{Y_1或Y_2 & val(Y_1)或val(Y_2) & \alpha^{val(Y_1)}\pmod{181}& \beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1\}\;&2^0+2^1=3&2^3\equiv8&108*2^{-3}\equiv104 \cr
\{\;0,2\}\;&2^0+2^2=5&2^5\equiv32&108*2^{-5}\equiv26 \cr
\{\;0,3\}\;&2^0+2^3=9&2^9\equiv150&108*2^{-9}\equiv160 \cr
\{\;0,4\}\;&2^0+2^4=17&2^{17}\equiv28&108*2^{-17}\equiv159 \cr
\{\;0,5\}\;&2^0+2^5=33&2^{33}\equiv30&108*2^{-33}\equiv76 \cr
\{\;0,6\}\;&2^0+2^6=65&2^{65}\equiv88&108*2^{-65}\equiv174 \cr
\{\;0,7\}\;&2^0+2^7=129&2^{129}\equiv71&108*2^{-129}\equiv78 \cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv64&108*2^{-6}\equiv13 \cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv119&108*2^{-10}\equiv80 \cr
\{\;1,4\}\;&2^1+2^4=18&2^{18}\equiv56&108*2^{-18}\equiv170 \cr
\{\;1,5\}\;&2^1+2^5=34&2^{34}\equiv60&108*2^{-34}\equiv38 \cr
\{\;1,6\}\;&2^1+2^6=66&2^{66}\equiv176&108*2^{-66}\equiv87 \cr
\{\;1,7\}\;&2^1+2^7=130&2^{130}\equiv142&108*2^{-130}\equiv39 \cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv114&108*2^{-12}\equiv20 \cr
\{\;2,4\}\;&2^2+2^4=20&2^{20}\equiv43&108*2^{-20}\equiv133 \cr
\{\;2,5\}\;&2^2+2^5=36&2^{36}\equiv59&108*2^{-36}\equiv100 \cr
\{\;2,6\}\;&2^2+2^6=68&2^{68}\equiv161&108*2^{-68}\equiv67 \cr
\{\;2,7\}\;&2^2+2^7=132&2^{132}\equiv25&108*2^{-132}\equiv55 \cr
\{\;3,4\}\;&2^3+2^4=24&2^{24}\equiv145&108*2^{-24}\equiv178 \cr
\{\;3,5\}\;&2^3+2^5=40&2^{40}\equiv39&108*2^{-40}\equiv142 \cr
\{\;3,6\}\;&2^3+2^6=72&2^{72}\equiv42&108*2^{-72}\equiv106 \cr
\{\;3,7\}\;&2^3+2^7=136&2^{136}\equiv38&108*2^{-136}\equiv60 \cr
\{\;4,5\}\;&2^4+2^5=48&2^{48}\equiv29&108*2^{-48}\equiv166 \cr
\{\;4,6\}\;&2^4+2^6=80&2^{80}\equiv73&108*2^{-80}\equiv180 \cr
\{\;4,7\}\;&2^4+2^7=144&2^{144}\equiv135&108*2^{-144}\equiv37 \cr
\{\;5,6\}\;&2^5+2^6=96&2^{96}\equiv117&108*2^{-96}\equiv168 \cr
\{\;5,7\}\;&2^5+2^7=160&2^{160}\equiv80&108*2^{-160}\equiv119 \cr
\{\;6,7\}\;&2^6+2^7=192&2^{192}\equiv114&108*2^{-192}\equiv20}\)
可找到
\(2^{136}\equiv 108*2^{-34}\equiv 38\pmod{181}\),\(Y_1=\{\;3,7 \}\;,Y_2=\{\;1,5 \}\;\),\(x=136+34=170\)
\(2^{40}\equiv 108*2^{-130}\equiv 39\pmod{181}\),\(Y_1=\{\;3,5 \}\;,Y_2=\{\;1,7 \}\;\),\(x=40+130=170\)
\(2^{34}\equiv 108*2^{-136}\equiv 60\pmod{181}\),\(Y_1=\{\;1,5 \}\;,Y_2=\{\;3,7 \}\;\),\(x=34+136=170\)
\(2^{160}\equiv 108*2^{-10}\equiv 80\pmod{181}\),\(Y_1=\{\;5,7 \}\;,Y_2=\{\;1,3 \}\;\),\(x=160+10=170\)
\(2^{10}\equiv 108*2^{-160}\equiv 119\pmod{181}\),\(Y_1=\{\;1,3 \}\;,Y_2=\{\;5,7 \}\;\),\(x=10+160=170\)
\(2^{130}\equiv 108*2^{-40}\equiv 142\pmod{181}\),\(Y_1=\{\;1,7 \}\;,Y_2=\{\;3,5 \}\;\),\(x=130+40=170\)
\(170=(10101010)_2\)漢明權重為4(4個1)。


演算法1
1. INPUT: \(\alpha,\beta \in G\), an integer \(m\) and an even integer \(t\)
2. For all \(Y_1 \subseteq Z_m\) such that \(|\;Y_1|\;=t/2\), compute \(\alpha^{val(Y_1)}\)
3. Sort the list of ordered pairs \((val(Y_1),\alpha^{val(Y_1)})\) by their second coordinates
4. For all \(Y_2 \subseteq Z_m\) such that \(|\;Y_1|\;=t/2\), compute \((\beta(\alpha^{val(Y_2)})^{-1})\)
5. Sort the list of ordered pairs \((val(Y_2),\beta(\alpha^{val(Y_2)})^{-1})\) by their second coordinates
6. If possible, find \(Y_1,Y_2\) such that \(\alpha^{val(Y_1)}=\beta(\alpha^{val(Y_2)})^{-1}\)
7. If the previous step is successful, output \(log_{\alpha}\beta=(val(Y_1)+val(Y_2))\pmod{ord(\alpha)}\). Otherwise, output fail.

參考資料:https://citeseerx.ist.psu.edu/vi ... p=rep1&type=pdf


從L中取n個元素的子集合副程式
(%i1)
Combination(L,n):=block
([c:[],s],
if length(L)>n then
  (for r in L do
     (s:delete(r,L),
      c:unique(append(c,Combination(s,n)))
     )
  )
else
  (c:[L]),
return(c)
)$


例子:從[0,1,2,3]中取2個元素的子集合,共C(4,2)=6個
(%i2) Combination([0,1,2,3],2);
(%o2) \([[0,1],[0,2],[0,3],[1,2],[1,3],[2,3]]\)

解低漢明權重的離散對數問題Heiman-Odlyzko方法副程式
(%i3)
LowHammingWeightDLP1(alpha,beta,p,t):=block
([m,order,Zm:[],Y:[],valY:[],lenY,inv_alpha,ListY1:[],ListY2:[],indexY1:1,indexY2:1,x1:0,x2:0,x:0],
if mod(t,2)#0 then
  (print("t要是偶數"),return()),
print("ord(",alpha,")=",order:zn_order(alpha,p),",",alpha^string(order),"≡1(mod",p,")"),
print("m=Ceiling(log2",order,")=",m:ceiling(log(order)/log(2))),
print("Zm=",Zm:makelist(i,i,0,m-1)),
print("從Zm取元素個數為","t"/2,"=",t/2,"個的子集合Y,共C(",m,",",t/2,")=",lenY:m!/((m-t/2)!*(t/2)!),"個"),
print("Y=",Y:Combination(Zm,t/2)),
print("val(Y)=Σ2"^"y","=",valY:create_list(apply("+",y),y,2^Y)),
print("計算[",alpha^"val(Y1)",",","val(Y1)]數對"),
print("ListY1=",ListY1:create_list([power_mod(alpha,valY[ i ],p),valY[ i ]],i,1,lenY)),
inv_alpha:inv_mod(alpha,p),
print("計算[",beta,"*",alpha^"-val(Y2)",",","val(Y2)]數對"),
print("ListY2=",ListY2:create_list([mod(beta*power_mod(inv_alpha,valY[ i ],p),p),valY[ i ]],i,1,lenY)),
print("由小到大排序"),
print("ListY1=",ListY1:sort(ListY1)),
print("ListY2=",ListY2:sort(ListY2)),
print("ListY1和ListY2互相比較找出相同值"),
while indexY1<=lenY and indexY2<=lenY do
  (if ListY1[indexY1][1]=ListY2[indexY2][1] then
     (x1: ListY1[indexY1][2],x2: ListY2[indexY2][2],
      print(alpha^string(x1),"≡",beta,"*",alpha^concat("-",x2),"≡",ListY1[indexY1][1],"(mod",p,")"),
      indexY1:indexY1+1,
      indexY2:indexY2+1
     )
   else if ListY1[indexY1][1]<ListY2[indexY2][1] then
     (indexY1:indexY1+1)
    else
     (indexY2:indexY2+1)
  ),
if x1=0 and x2=0 then
  (print("無解"),
   return()
  )
else
  (return(x:mod(x1+x2,order)))
)$


\(\alpha^x \equiv \beta\pmod{p}\),已知x的漢明權重\(t=4\)
(%i7)
alpha:2;
beta:108;
p:181;
t:4;

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

解低漢明權重的離散對數問題-Heiman-Odlyzko方法
(%i8) x: LowHammingWeightDLP1(alpha,beta,p,t);
\(ord(2)=180\),\(2^{180}\equiv 1 \pmod{181}\)
\(m=Ceiling(log_2 180)=8\)
\(Zm=[0,1,2,3,4,5,6,7]\)
從\(Zm\)取元素個數為\(\displaystyle \frac{t}{2}=2\)個的子集合\(Y\),共\(C(8,2)=28\)個
\(Y=[[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7],\)
  \([2,3],[2,4],[2,5],[2,6],[2,7],[3,4],[3,5],[3,6],[3,7],[4,5],[4,6],[4,7],[5,6],[5,7],[6,7]] \)
\(val(Y)=Σ2^y = [3,5,9,17,33,65,129,6,10,18,34,66,130,12,20,36,68,132,24,40,72,136,48,80,144,96,160,192] \)
計算\([ 2^{val(Y1)},val(Y1)]\)數對
\(ListY1= [[8,3],[32,5],[150,9],[28,17],[30,33],[88,65],[71,129],[64,6],[119,10],[56,18],[60,34],[176,66],[142,130],[114,12],\)
     \([43,20],[59,36],[161,68],[25,132],[145,24],[39,40],[42,72],[38,136],[29,48],[73,80],[135,144],[117,96],[80,160],[114,192]] \)
計算\([ 108 * 2^{-val(Y2)},val(Y2)]\)數對
\(ListY2= [[104,3],[26,5],[160,9],[159,17],[76,33],[174,65],[78,129],[13,6],[80,10],[170,18],[38,34],[87,66],[39,130],[20,12],\)
     \([133,20],[100,36],[67,68],[55,132],[178,24],[142,40],[106,72],[60,136],[166,48],[180,80],[37,144],[168,96],[119,160],[20,192]] \)
由小到大排序
\(ListY1= [[8,3],[25,132],[28,17],[29,48],[30,33],[32,5],[38,136],[39,40],[42,72],[43,20],[56,18],[59,36],[60,34],[64,6],\)
     \([71,129],[73,80],[80,160],[88,65],[114,12],[114,192],[117,96],[119,10],[135,144],[142,130],[145,24],[150,9],[161,68],[176,66]] \)
\(ListY2= [[13,6],[20,12],[20,192],[26,5],[37,144],[38,34],[39,130],[55,132],[60,136],[67,68],[76,33],[78,129],[80,10],[87,66],\)
     \([100,36],[104,3],[106,72],[119,160],[133,20],[142,40],[159,17],[160,9],[166,48],[168,96],[170,18],[174,65],[178,24],[180,80]] \)
\(ListY1\)和\(ListY2\)互相比較找出相同值
\(2^{136} \equiv 108 * 2^{-34} \equiv 38\pmod{181}\)
\(2^{40} \equiv 108 * 2^{-130} \equiv 39\pmod{181}\)
\(2^{34} \equiv 108 * 2^{-136} \equiv 60\pmod{181}\)
\(2^{160} \equiv 108 * 2^{-10} \equiv 80\pmod{181}\)
\(2^{10} \equiv 108 * 2^{-160} \equiv 119\pmod{181}\)
\(2^{130} \equiv 108 * 2^{-40} \equiv 142\pmod{181}\)
(x) 170

TOP

5-2.低漢明權重(Low Hamming Weight)的離散對數問題-Coppersmith方法

從上一篇文章可以發現Heiman-Odlyzko方法的關鍵在於列舉解\(x=(10101010)_2\)中1的可能位置\(Y_1,Y_2\),\(Y_1,Y_2\)各有\(C(m,\frac{t}{2})=C(8,2)=28\)種,當\(\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}\)時,解\(x=val(Y_1)+val(Y_2)\pmod{ord(\alpha)}\)。

Coppersmith方法將解\(x\)二進位切成兩等份,每個等份再分別列舉1的可能位置,
\(\{\;0,1,2,3 \}\;\)任取2個的子集合\(Y_1\),\(\{\;4,5,6,7 \}\;\)任取2個的子集合\(Y_2\)
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1\}\;&2^0+2^1=3&2^3\equiv 8&\{\;4,5\}\;&2^4+2^5=48&108*2^{-48}\equiv 166\cr
\{\;0,2\}\;&2^0+2^2=5&2^5\equiv 32&\{\;4,6\}\;&2^4+2^6=80&108*2^{-80}\equiv 180\cr
\{\;0,3\}\;&2^0+2^3=9&2^9\equiv 150&\{\;4,7\}\;&2^4+2^7=144&108*2^{-144}\equiv 37\cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv 64&\{\;5,6\}\;&2^5+2^6=96&108*2^{-96}\equiv 168\cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv 119&\{\;5,7\}\;&2^5+2^7=160&108*2^{-160}\equiv 119\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;6,7\}\;&2^6+2^7=192&108*2^{-192}\equiv 20}\)
可找到
\(2^{10}\equiv 108*2^{-160}\equiv 119 \pmod{181}\),\(Y_1=\{\;1,3 \}\;\),\(Y_2=\{\;5,7 \}\;\),\(x=10+160=170\)


再以\(2^{142}\equiv 79\pmod{181}\)為例,解\(x=(142)_{10}=(10001110)_2\),1的分佈不平均。
\(\{\;0,1,2,3 \}\;\)任取2個的子集合\(Y_1\),\(\{\;4,5,6,7 \}\;\)任取2個的子集合\(Y_2\)
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;0,1\}\;&2^0+2^1=3&2^3\equiv 8&\{\;4,5\}\;&2^4+2^5=48&79*2^{-48}\equiv 165\cr
\{\;0,2\}\;&2^0+2^2=5&2^5\equiv 32&\{\;4,6\}\;&2^4+2^6=80&79*2^{-80}\equiv 11\cr
\{\;0,3\}\;&2^0+2^3=9&2^9\equiv 150&\{\;4,7\}\;&2^4+2^7=144&79*2^{-144}\equiv 136\cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv 64&\{\;5,6\}\;&2^5+2^6=96&79*2^{-96}\equiv 143\cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv 119&\{\;5,7\}\;&2^5+2^7=160&79*2^{-160}\equiv 139\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;6,7\}\;&2^6+2^7=192&79*2^{-192}\equiv 142}\)
找不到\(Y_1,Y_2\)使得\(\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}\)

Coppersmitth方法將\(Y_1,Y_2\)各平移1個元素再重新列舉
\(\{\;1,2,3,4 \}\;\)任取2個的子集合\(Y_1\),\(\{\;5,6,7,0 \}\;\)任取2個的子集合\(Y_2\)
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;1,2\}\;&2^1+2^2=6&2^6\equiv 64&\{\;0,5\}\;&2^0+2^5=33&79*2^{-33}\equiv 69\cr
\{\;1,3\}\;&2^1+2^3=10&2^{10}\equiv 119&\{\;0,6\}\;&2^0+2^6=65&79*2^{-65}\equiv 77\cr
\{\;1,4\}\;&2^1+2^4=18&2^{18}\equiv 56&\{\;0,7\}\;&2^0+2^7=129&79*2^{-129}\equiv 47\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;5,6\}\;&2^5+2^6=96&79*2^{-96}\equiv 143\cr
\{\;2,4\}\;&2^2+2^4=20&2^{20}\equiv 43&\{\;5,7\}\;&2^5+2^7=160&79*2^{-160}\equiv 139\cr
\{\;3,4\}\;&2^3+2^4=24&2^{24}\equiv 145&\{\;6,7\}\;&2^6+2^7=192&79*2^{-192}\equiv 142}\)
找不到\(Y_1,Y_2\)使得\(\alpha^{val(Y_1)}\equiv \beta \alpha^{-val(Y_2)}\pmod{p}\)

再將\(Y_1,Y_2\)各平移1個元素再重新列舉
\(\{\;2,3,4,5 \}\;\)任取2個的子集合\(Y_1\),\(\{\;6,7,0,1 \}\;\)任取2個的子集合\(Y_2\)
\(\matrix{Y_1&val(Y_1)&\alpha^{val(Y_1)}\pmod{181}&Y_2&val(Y_2)&\beta \alpha^{-val(Y_2)}\pmod{181}\cr
\{\;2,3\}\;&2^2+2^3=12&2^{12}\equiv 114&\{\;0,1\}\;&2^0+2^1=3&79*2^{-3}\equiv 123\cr
\{\;2,4\}\;&2^2+2^4=20&2^{20}\equiv 43&\{\;0,6\}\;&2^0+2^6=65&79*2^{-65}\equiv 77\cr
\{\;2,5\}\;&2^2+2^5=36&2^{36}\equiv 59&\{\;0,7\}\;&2^0+2^7=129&79*2^{-129}\equiv 47\cr
\{\;3,4\}\;&2^3+2^4=24&2^{24}\equiv 145&\{\;1,6\}\;&2^1+2^6=66&79*2^{-66}\equiv 129\cr
\{\;3,5\}\;&2^3+2^5=40&2^{40}\equiv 39&\{\;1,7\}\;&2^1+2^7=130&79*2^{-130}\equiv 114\cr
\{\;4,5\}\;&2^4+2^5=48&2^{48}\equiv 29&\{\;6,7\}\;&2^6+2^7=192&79*2^{-192}\equiv 142}\)
可找到
\(2^{12}\equiv 79 *2^{-130}\equiv 114\pmod{181}\),\(Y_1=\{\;2,3 \}\;\),\(Y_2=\{\;1,7 \}\;\),\(x=12+130=142\)


Splitting families
假設\(m\)和\(t\)都是偶數且\(0<t<m\),定義\((m,t)\)的splitting system是符合以下2點的數對\((X,\cal{B})\)
1.集合\(X\)有\(m\)個元素,集合\(\beta\)有\(\displaystyle \frac{m}{2}\)個\(X\)的子集合,\(\cal{B}\)稱為區塊(blocks)。
2.對所有\(X\)的子集合\(Y\),\(Y\)有\(t\)個元素,存在一個區塊\(B\)使得\(B\)和\(Y\)的交集個數為\(\displaystyle \frac{t}{2}\)。

Coppersmith也提供一種產生\(\displaystyle (\frac{m}{2};m,t)\)的splitting system方法。
令\(X=Z_m\),定義\(B_i=\{\;i+j\pmod{m}:0\le j\le m/2-1\}\;\),\(\cal B\)\(=\{\;B_i:0\le i \le m/2-1\}\;\)

以\(m=8,t=4\)為例
\(X=Z_m=\{\;0,1,2,3,4,5,6,7\}\;\),\(B_0=\{\;0,1,2,3\}\;\),\(B_1=\{\;1,2,3,4\}\;\),\(B_2=\{\;2,3,4,5\}\;\),\(B_3=\{\;3,4,5,6\}\;\),\(\cal B\)\(=\{\;B_0,B_1,B_2,B_3\}\;\)
子集合\(Y=\{\;0,2,4,6\}\;\)有4個元素,存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。
子集合\(Y=\{\;1,3,5,7\}\;\)有4個元素,存在\(B_0,B_1,B_2,B_3\)和\(Y\)交集2個元素。
子集合\(Y=\{\;0,1,6,7\}\;\)有4個元素,存在\(B_0\)和\(Y\)交集2個元素。
子集合\(Y=\{\;0,2,5,7\}\;\)有4個元素,存在\(B_0\)和\(Y\)交集2個元素。
子集合\(Y=\{\;4,5,6,7\}\;\)有4個元素,存在\(B_2,B_3\)和\(Y\)交集2個元素。

演算法2
1. INPUT:\(\alpha,\beta \in G\), even integers \(m\) and \(t\), and an \((N; m, t)\)-SS, \((Z_m,\cal{B})\), where \(\cal B\)\(= \{\;B_i : 0 \le i \le N − 1\}\;\).
2. For \(i = 0,\ldots,N−1\), perform the following steps:
(a) For all \(Y_1\subseteq B_i\) such that \(|\;Y_1|\; = t/2\), compute \(\alpha^{val(Y_1)}\)
(b) Sort the list of ordered pairs \((val(Y_1), \alpha^{val(Y_1)})\) by their second coordinates
(c) For all \(Y_2 \subseteq Z_m\backslash\; B_i\) such that \(|\;Y_2|\; = t/2\), compute \(\beta(\alpha^{val(Y_2)})^{−1}\)
(d) Sort the list of ordered pairs \((val(Y_2), \beta(\alpha^{val(Y_2)})^{−1})\) by their second coordinates
(e) If possible, find \(Y_1\), \(Y_2\) such that \(\alpha^{val(Y_1)} = \beta(\alpha^{val(Y_2)})^{−1}\).
(f) If the previous step is successful, output \(log_{\alpha}\beta=val(Y_1)+val(Y_2) \pmod{ord(\alpha)}\)and QUIT. Otherwise, proceed to the next iteration of the FOR loop.

演算法3則隨機產生集合\(B\),其中包含\(\displaystyle \frac{m}{2}\)個子集合,其餘步驟和演算法1,2相同。
演算法 3
1. INPUT: \(\alpha,\beta \in G\), and even integers \(m\) and \(t\).
2. REPEAT the following steps:
(a) Let \(B\) be a random \(\displaystyle \frac{m}{2}\)-subset of \(X\)
(b) For all \(Y_1 \subseteq B\) such that \(|\;Y_1|\;=t/2\), compute \(\alpha^{val(Y_1)}\)
(c) Sort the list of ordered pairs \((val(Y_1), \alpha^{val(Y_1)})\) by their second coordinates
(d) For all \(Y_2 \subseteq Z_m\backslash\;B\) such that \(|\;Y_2|\;=t/2\), compute \(\beta(\alpha^{val(Y_2)})^{−1}\)
(e) Sort the list of ordered pairs \((val(Y_2),\beta(\alpha^{val(Y_2)})^{−1})\) by their second coordinates
(f) If possible, find \(Y_1\), \(Y_2\) such that \(\alpha^{val(Y_1)} =\beta(\alpha^{val(Y_2)})^{−1}\).
(g) If the previous step is successful, output \(log_{\alpha}\beta=val(Y_1)+val(Y_2) \pmod{ord(\alpha)}\) and QUIT. Otherwise, proceed to the next iteration of the REPEAT loop.

參考資料:https://citeseerx.ist.psu.edu/vi ... p=rep1&type=pdf


從L中取n個元素的子集合副程式
(%i1)
Combination(L,n):=block
([c:[],s],
if length(L)>n then
  (for r in L do
     (s:delete(r,L),
      c:unique(append(c,Combination(s,n)))
     )
  )
else
  (c:[L]),
return(c)
)$


解低漢明權重的離散對數問題Coppersmith方法副程式
(%i2)
LowHammingWeightDLP2(alpha,beta,p,t):=block
([m,order,Beta,inv_alpha,i,Y1,Y2,valY1,valY2,lenY1,lenY2,ListY1,ListY2,indexY1:1,indexY2:1,x1:0,x2:0,x:0],
if mod(t,2)#0 then
  (print("t要是偶數"),return()),
print("ord(",alpha,")=",order:zn_order(alpha,p),",",alpha^string(order),"≡1(mod",p,")"),
print("m=Ceiling(log2",order,")=",m:ceiling(log(order)/log(2))),
if mod(m,2)#0 then
  (print("m要是偶數"),return()),
print("Zm=",create_list(i,i,0,m-1)),
print("Bi={i+j (mod m):0≤j≤m/2-1},β={Bi:0≤i≤m/2-1}"),
print("β=",Beta:create_list(create_list(mod(i+j,m),i,0,m/2-1),j,0,m/2-1)),
print("--------"),
inv_alpha:inv_mod(alpha,p),
for i:1 thru m/2 do
  (print("B",i-1,"=",Beta[ i ]),
   print("從B",i-1,"取元素個數為","t"/2,"=",t/2,"個的子集合Y1,共C(","m"/2,",","t"/2,")=C(",m/2,",",t/2,")=",lenY1: (m/2)!/((t/2)!*(m/2-t/2)!),"個"),
   print("Y1=",Y1:Combination(Beta[ i ],t/2)),
   print("val(Y1)=Σ2"^"y","=",valY1:create_list(apply("+",y),y,2^Y1)),
   print("計算[",alpha^"val(Y1)",",val(Y1)]數對"),
   print("ListY1=",ListY1:create_list([power_mod(alpha,valY1[ i ],p),valY1[ i ]],i,1,lenY1)),
   print("Zm\\B",i-1,"=",mod(Beta[ i ]+m/2,m)),
   print("從Zm\\B",i-1,"取元素個數為","t"/2,"=",t/2,"個的子集合Y1,共C(","m"/2,",","t"/2,")=C(",m/2,",",t/2,")=",lenY2: (m/2)!/((t/2)!*(m/2-t/2)!),"個"),
   print("Y2=",Y2:Combination(sort(mod(Beta[ i ]+m/2,m)),t/2)),
   print("val(Y2)=Σ2"^"y","=",valY2:create_list(apply("+",y),y,2^Y2)),
   print("計算[",beta,"*",alpha^"-val(Y2)",",","val(Y2)]數對"),
   print("ListY2=",ListY2:create_list([mod(beta*power_mod(inv_alpha,valY2[ i ],p),p),valY2[ i ]],i,1,lenY2)),
   print("由小到大排序"),
   print("ListY1=",ListY1:sort(ListY1)),
   print("ListY2=",ListY2:sort(ListY2)),
   indexY1:1,indexY2:1,x1:0,x2:0,
   while indexY1<=lenY1 and indexY2<=lenY2 do
     (if ListY1[indexY1][1]=ListY2[indexY2][1] then
        (print("ListY1和ListY2互相比較找到相同值"),
         x1: ListY1[indexY1][2],x2: ListY2[indexY2][2],
         print(alpha^string(x1),"≡",beta,"*",alpha^concat("-",x2),"≡",ListY1[indexY1][1],"(mod",p,")"),
         print("x=",x1,"+",x2,"=",x:mod(x1+x2,order)),
         indexY1:indexY1+1,
         indexY2:indexY2+1
        )
      else if ListY1[indexY1][1]<ListY2[indexY2][1] then
        (indexY1:indexY1+1)
       else
        (indexY2:indexY2+1)
     ),
   if x1=0 and x2=0 then
      (print("ListY1和ListY2互相比較沒找到相同值")),
   print("--------")
  ),
if x=0 then
  (print("無解"),
   return()
  )
else
  (return(x))
)$


\(\alpha^x \equiv \beta \pmod{p}\),已知\(x\)的漢明權重\(t=4\)
(%i6)
alpha:2;
beta:79;
p:181;
t:4;

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

解低漢明權重的離散對數問題-Coppersmith方法
(%i7) x: LowHammingWeightDLP2(alpha,beta,p,t);
\(ord(2)=180\),\(2^{180}\equiv 1\pmod{181}\)
\(m=Ceiling(log_2 180)=8\)
\(Zm= [\;0,1,2,3,4,5,6,7]\;\)
\(Bi=\{\; i+j \pmod{m}:0 \le j \le m/2-1 \}\;\),\(\beta=\{\;Bi:0 \le i \le m/2-1 \};\)
\(\beta=[\;[\;0,1,2,3]\;,[\;1,2,3,4]\;,[\;2,3,4,5]\;,[\;3,4,5,6]\;]\;\)
--------
\(B0=[\;0,1,2,3]\;\)
從\(B0\)取元素個數為\(\displaystyle \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y1=[\;[\;0,1]\;,[\;0,2]\;,[\;0,3]\;,[\;1,2]\;,[\;1,3]\;,[\;2,3]\;]\;\)
\(val(Y1)=Σ2^y = [\;3,5,9,6,10,12]\;\)
計算\([\; 2^{val(Y1)},val(Y1)]\;\)數對
\(ListY1=[\;[\;8,3]\;,[\;32,5]\;,[\;150,9]\;,[\;64,6]\;,[\;119,10]\;,[\;114,12]\;]\;\)
\(Zm\backslash\; B0=[\;4,5,6,7]\;\)
從\(Zm \backslash\;B0\)取元素個數為\(\displaystyle \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y2=[\;[\;4,5]\;,[\;4,6]\;,[\;4,7]\;,[\;5,6]\;,[\;5,7]\;,[\;6,7]\;]\;\)
\(val(Y2)=Σ2^y=[\;48,80,144,96,160,192]\;\)
計算\([\;79 * 2^{-val(Y2)}, val(Y2)]\;\)數對
\(ListY2=[\;[\;165,48]\;,[\;11,80]\;,[\;136,144]\;,[\;143,96]\;,[\;139,160]\;,[\;142,192]\;]\;\)
由小到大排序
\(ListY1=[\;[\;8,3]\;,[\;32,5]\;,[\;64,6]\;,[\;114,12]\;,[\;119,10]\;,[\;150,9]\;]\;\)
\(ListY2=[\;[\;11,80]\;,[\;136,144]\;,[\;139,160]\;,[\;142,192]\;,[\;143,96]\;,[\;165,48]\;]\;\)
\(ListY1\)和\(ListY2\)互相比較沒找到相同值
--------
\(B1 = [\;1,2,3,4]\;\)
從\(B1\)取元素個數為\(\displaystyle  \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y1= [\;[\;1,2]\;,[\;1,3]\;,[\;1,4]\;,[\;2,3]\;,[\;2,4]\;,[\;3,4]\;]\;\)
\(val(Y1)=Σ2^y = [\;6,10,18,12,20,24]\;\)
計算\([\; 2^{val(Y1)},val(Y1)]\;\)數對
\(ListY1=[\;[\;64,6]\;,[\;119,10]\;,[\;56,18]\;,[\;114,12]\;,[\;43,20]\;,[\;145,24]\;]\;\)
\(Zm\backslash\;B1 = [\;5,6,7,0]\;\)
從\(Zm\backslash\;B1\)取元素個數為\(\displaystyle  \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y2= [\;[\;0,5]\;,[\;0,6]\;,[\;0,7]\;,[\;5,6]\;,[\;5,7]\;,[\;6,7]\;]\;\)
\(val(Y2)=Σ2^y = [\;33,65,129,96,160,192]\;\)
計算\([\; 79 * 2^{-val(Y2)}, val(Y2)]\;\)數對
\(ListY2=[\;[\;69,33]\;,[\;77,65]\;,[\;47,129]\;,[\;143,96]\;,[\;139,160]\;,[\;142,192]\;]\;\)
由小到大排序
\(ListY1=[\;[\;43,20]\;,[\;56,18]\;,[\;64,6]\;,[\;114,12]\;,[\;119,10]\;,[\;145,24]\;]\;\)
\(ListY2=[\;[\;47,129]\;,[\;69,33]\;,[\;77,65]\;,[\;139,160]\;,[\;142,192]\;,[\;143,96]\;]\;\)
\(ListY1\)和\(ListY2\)互相比較沒找到相同值
--------
\(B2=[\;2,3,4,5]\;\)
從\(B2\)取元素個數為\(\displaystyle  \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y1=[\;[\;2,3]\;,[\;2,4]\;,[\;2,5]\;,[\;3,4]\;,[\;3,5]\;,[\;4,5]\;]\;\)
\(val(Y1)=Σ2^y=[\;12,20,36,24,40,48]\;\)
計算\([\; 2^{val(Y1)},val(Y1)]\;\)數對
\(ListY1=[\;[\;114,12]\;,[\;43,20]\;,[\;59,36]\;,[\;145,24]\;,[\;39,40]\;,[\;29,48]\;]\;\)
\(Zm\backslash\;B2 = [\;6,7,0,1]\;\)
從\(Zm\backslash\;B2\)取元素個數為\(\displaystyle \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y2= [\;[\;0,1]\;,[\;0,6]\;,[\;0,7]\;,[\;1,6]\;,[\;1,7]\;,[\;6,7]\;]\;\)
\(val(Y2)=Σ2^y = [\;3,65,129,66,130,192]\;\)
計算\([\; 79 * 2^{-val(Y2)}, val(Y2)]\;\)數對
\(ListY2=[\;[\;123,3]\;,[\;77,65]\;,[\;47,129]\;,[\;129,66]\;,[\;114,130]\;,[\;142,192]\;]\;\)
由小到大排序
\(ListY1=[\;[\;29,48]\;,[\;39,40]\;,[\;43,20]\;,[\;59,36]\;,[\;114,12]\;,[\;145,24]\;]\;\)
\(ListY2=[\;[\;47,129]\;,[\;77,65]\;,[\;114,130]\;,[\;123,3]\;,[\;129,66]\;,[\;142,192]\;]\;\)
\(ListY1\)和\(ListY2\)互相比較找到相同值
\(2^{12}\equiv 79 * 2^{-130}\equiv 114 \pmod{181}\)
\(x=12+130=142\)
--------
\(B3 = [\;3,4,5,6]\;\)
從\(B3\)取元素個數為\(\displaystyle  \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y1= [\;[\;3,4]\;,[\;3,5]\;,[\;3,6]\;,[\;4,5]\;,[\;4,6]\;,[\;5,6]\;]\;\)
\(val(Y1)=Σ2^y = [\;24,40,72,48,80,96]\;\)
計算\([\; 2^{val(Y1)},val(Y1)]\;\)數對
\(ListY1=[\;[\;145,24]\;,[\;39,40]\;,[\;42,72]\;,[\;29,48]\;,[\;73,80]\;,[\;117,96]\;]\;\)
\(Zm\backslash\;B3 = [\;7,0,1,2]\;\)
從\(Zm\backslash\;B3\)取元素個數為\(\displaystyle  \frac{t}{2}=2\)個的子集合\(Y1\),共\(\displaystyle C(\frac{m}{2},\frac{t}{2})=C(4,2)=6\)個
\(Y2= [\;[\;0,1]\;,[\;0,2]\;,[\;0,7]\;,[\;1,2]\;,[\;1,7]\;,[\;2,7]\;]\;\)
\(val(Y2)=Σ2^y = [\;3,5,129,6,130,132]\;\)
計算\([\; 79 * 2^{-val(Y2)}, val(Y2)]\;\)數對
\(ListY2=[\;[\;123,3]\;,[\;76,5]\;,[\;47,129]\;,[\;38,6]\;,[\;114,130]\;,[\;119,132]\;]\;\)
由小到大排序
\(ListY1=[\;[\;29,48]\;,[\;39,40]\;,[\;42,72]\;,[\;73,80]\;,[\;117,96]\;,[\;145,24]\;]\;\)
\(ListY2=[\;[\;38,6]\;,[\;47,129]\;,[\;76,5]\;,[\;114,130]\;,[\;119,132]\;,[\;123,3]\;]\;\)
\(ListY1\)和\(ListY2\)互相比較沒找到相同值
--------
(x) 142

TOP

發新話題