Math Pro 數學補給站 » 數學軟體 » 用maxima學對稱密碼學－簡化的DES(S-DES)

bugmens 發表於 2018-8-5 15:14

用maxima學對稱密碼學－簡化的DES(S-DES)

因為\(DES\)運算過程比較複雜，Edward F.Schaefer提出簡化的\(DES\)(\(S-DES\))作為教學用途，在簡化的版本中，使用的明文大小為\(8bit\)，
密鑰大小為\(10bit\)，輸出\(8bit\)的密文，加密過程僅有兩回合。

以下流程圖和範例來說明\(S-DES\)是如何運作
1.S-DES架構
[img]https://math.pro/db/attachment.php?aid=4646&k=cf0a3ba8debe93a7323f31367e6e0ca2&t=1533451637&noupdate=yes[/img]

2.以密鑰\(key=1100011110\)，示範如何產生子密鑰\(K_1=11101000\)和\(K_2=10100111\)
[img]https://math.pro/db/attachment.php?aid=4647&k=73f3cb556d809139aaeb23df50ff8028&t=1533451637&noupdate=yes[/img]

3.以明文\(plaintext=00101000\)，示範如何產生密文\(ciphertext=10001010\)
[img]https://math.pro/db/attachment.php?aid=4648&k=f087096de8f9929b939abc60a5e1c5b3&t=1533451637&noupdate=yes[/img]

圖取自[url]http://mercury.webster.edu/aleshunas/COSC%205130/G-SDES.pdf[/url]

[url]http://desalgorithm.yolasite.com[/url]有提供完整的\(S-DES\)動畫，讓學習者可以了解整個運作過程，本文章的範例取自這裡。
另外近代密碼學與其應用(鍾慶豐)和世界第一簡單密碼學(三谷政昭、佐藤伸一)也有\(S-DES\)的介紹。

參考資料
Edward F. Schaefer:A Simplified Data Encryption Standard Algorithm. Cryptologia 20(1): 77-84 (1996)

[color=green]初始排列(initial permutation),將8bit重新排列
IP(b1,b2,b3,b4,b5,b6,b7,b8)=(b2,b6,b3,b1,b4,b8,b5,b7)
IP^-1(b1,b2,b3,b4,b5,b6,b7,b8)=(b4,b1,b3,b5,b7,b2,b8,b6)[/color]
[color=red](%i1)[/color]
[color=blue]initial_permutation(b,inverse):=block
([IP],
if length(b)#8 then
  (print("bit長度要為8"),
   return([])
  ),
if inverse=true then
    (IP:[b[4],b[1],b[3],b[5],b[7],b[2],b[8],b[6]],
     print("將8bit重新排列"),
     print("IP^-1",matrix(["b1","b2","b3","b4","b5","b6","b7","b8"],b),"=",
                        matrix(["b4","b1","b3","b5","b7","b2","b8","b6"],IP)),
     return(IP)
    )
else
    (IP:[b[2],b[6],b[3],b[1],b[4],b[8],b[5],b[7]],
     print("將8bit重新排列"),
     print("IP",matrix(["b1","b2","b3","b4","b5","b6","b7","b8"],b),"=",
                   matrix(["b2","b6","b3","b1","b4","b8","b5","b7"],IP)),
     return(IP)
    )
)$[/color]

[color=green]向左平移(left shift),將10bit分成左5bit和右5bit,各向左平移1bit或2bit
LS1(b1,b2,b3,b4,b5,b6,b7,b8,b9,b10)=(b2,b3,b4,b5,b1,b7,b8,b9,b10,b6)
LS2(b1,b2,b3,b4,b5,b6,b7,b8,b9,b10)=(b3,b4,b5,b1,b2,b8,b9,b10,b6,b7)[/color]
[color=red](%i2)[/color]
[color=blue]left_shift(b,n):=block
([LS1,LS2],
if length(b)#10 then
  (print("bit長度要為10"),
   return([])
  ),
if n=1 then
  (LS1:[b[2],b[3],b[4],b[5],b[1],b[7],b[8],b[9],b[10],b[6]],
   print("將10bit分成左5bit和右5bit,各向左平移1bit"),
   print("LS1",matrix(["b1","b2","b3","b4","b5","b6","b7","b8","b9","b10"],b),"=",
                   matrix(["b2","b3","b4","b5","b1","b7","b8","b9","b10","b6"],LS1)),
   return(LS1)
  ),
if n=2 then
  (LS2:[b[3],b[4],b[5],b[1],b[2],b[8],b[9],b[10],b[6],b[7]],
   print("將10bit分成左5bit和右5bit,各向左平移2bit"),
   print("LS2",matrix(["b1","b2","b3","b4","b5","b6","b7","b8","b9","b10"],b),"=",
                  matrix(["b3","b4","b5","b1","b2","b8","b9","b10","b6","b7"],LS2)),
   return(LS2)
  )
)$[/color]

[color=green]4bit重新排列(permutation4)
P4(b1,b,2,b3,b4)=(b2,b4,b3,b1)[/color]
[color=red](%i3)[/color]
[color=blue]permutation4(b):=block
([P4],
if length(b)#4 then
  (print("bit長度要為4"),
   return([])
  ),
print("將4bit重新排列"),
P4:[b[2],b[4],b[3],b[1]],
print("P4",matrix(["b1","b2","b3","b4"],b),"=",
              matrix(["b2","b4","b3","b1"],P4)),
return(P4)
)$[/color]

[color=green]10bit取其中8bit重新排列(permutation8)
P8(b1,b,2,b3,b4,b5,b6,b7,b8,b9,b10)=(b6,b3,b7,b4,b8,b5,b10,b9)[/color]
[color=red](%i4)[/color]
[color=blue]permutation8(b):=block
([P8],
if length(b)#10 then
  (print("bit長度要為10"),
   return([])
  ),
print("將10bit取其中8bit重新排列"),
P8:[b[6],b[3],b[7],b[4],b[8],b[5],b[10],b[9]],
print("P8",matrix(["b1","b2","b3","b4","b5","b6","b7","b8","b9","b10"],b),"=",
              matrix(["b6","b3","b7","b4","b8","b5","b10","b9"],P8)),
return(P8)
)$[/color]

[color=green]10bit重新排列(permutation10)
P10(b1,b,2,b3,b4,b5,b6,b7,b8,b9,b10)=(b3,b5,b2,b7,b4,b10,b1,b9,b8,b6)[/color]
[color=red](%i5)[/color]
[color=blue]permutation10(b):=block
([P10],
if length(b)#10 then
  (print("bit長度要為10"),
   return([])
  ),
P10:[b[3],b[5],b[2],b[7],b[4],b[10],b[1],b[9],b[8],b[6]],
print("將10bit重新排列"),
print("P10",matrix(["b1","b2","b3","b4","b5","b6","b7","b8","b9","b10"],b),"=",
                matrix(["b3","b5","b2","b7","b4","b10","b1","b9","b8","b6"],P10)),
return(P10)
)$[/color]

[color=green]排列代換(permute_substitute)
計算Π_F(L,R)=(L⊕F(R,S),R)[/color]
[color=red](%i6)[/color]
[color=blue]permute_substitute(b,SubKey):=block
([L,R,S,S0,S1,row,column,left,leftbits,right,rightbits,fourbits,eightbits],
if length(b)#8 then
  (print("bit長度要為8"),
   return([])
  ),
print("將8bit分成左4bit和右4bit",
       ",Lbits=",Lbits:[b[1],b[2],b[3],b[4]],
       ",Rbits=",Rbits:[b[5],b[6],b[7],b[8]]),
print("將Rbits=",Rbits,"擴展成8bit"),
RX:[Rbits[4],Rbits[1],Rbits[2],Rbits[3],Rbits[2],Rbits[3],Rbits[4],Rbits[1]],
print("RX",matrix(["b1","b2","b3","b4"],Rbits),"=",
              matrix(["b4","b1","b2","b3","b2","b3","b4","b1"],RX)),
print("和子密鑰SubKey=",SubKey,"進行xor運算"),
print("RX⊕SubKey=",matrix(RX,SubKey,["－","－","－","－","－","－","－","－"],S:mod(RX+SubKey,2)),"=",S),
print("將8bit分成左4bit=",[S[1],S[2],S[3],S[4]],"和右4bit=",[S[5],S[6],S[7],S[8]]),
print("左4bit=",[S[1],S[2],S[3],S[4]],"進SBox0替換"),
print("第1,4個bit=",[S[1],S[4]],"轉十進位為第",row:S[1]*2+S[4],
    "列,第2,3個bit=",[S[2],S[3]],"轉十進位為第",column:S[2]*2+S[3],"行"),
print("S0=",S0:matrix([1, 0, 3, 2],[3, 2, 1, 0],[0, 2, 1, 3],[3, 1, 3, 2]),
        ",S0[",row,",",column,"]=",left:S0[row+1,column+1],
        ",轉成二進位leftbits=",leftbits:[floor(left/2),mod(left,2)]),
print("右4bit=",[S[5],S[6],S[7],S[8]],"進SBox1替換"),
print("第1,4個bit=",[S[5],S[8]],"轉十進位為第",row:S[5]*2+S[8],
    "列,第2,3個bit=",[S[6],S[7]],"轉十進位為第",column:S[6]*2+S[7],"行"),
print("S1=",S1:matrix([0, 1, 2, 3],[2, 0, 1, 3],[3, 0, 1, 0],[2, 1, 0, 3]),
        ",S1[",row,",",column,"]=",right:S1[row+1,column+1],
        ",轉成二進位rightbits=",rightbits:[floor(right/2),mod(right,2)]),
print("組合成4bit,[leftbits,rightbits]=",fourbits:flatten([leftbits,rightbits])),
P4:permutation4(fourbits),
print("再和前面的Lbits=",Lbits,"進行xor運算"),
print("Lbits⊕P4=",matrix(Lbits,P4,["－","－","－","－"],Lbits:mod(Lbits+P4,2)),"=",Lbits),
print("再和前面的Rbits組合成8bit,[Lbits,Rbits]=",eightbits:flatten([Lbits,Rbits])),
return(eightbits)
)$[/color]

[color=green]產生子密鑰SubKey1和SubKey2[/color]
[color=red](%i7)[/color]
[color=blue]subkey(Key):=block
([SubKey1,SubKey2],
if length(Key)#10 then
  (print("subkey副程式Key長度要為10"),
   return([])
  ),
Key:permutation10(Key),
Key:left_shift(Key,1),
SubKey1:permutation8(Key),
print("得到子密鑰SubKey1=",SubKey1),
print("－－－－－－－－－－－"),
print("取LS1結果",Key),
Key:left_shift(Key,2),
SubKey2:permutation8(Key),
print("得到子密鑰SubKey2=",SubKey2),
print("－－－－－－－－－－－"),
return([SubKey1,SubKey2])
)$[/color]

[color=green]交換(switch),將8bit的前4bit和後4bit交換[/color]
[color=red](%i8)[/color]
[color=blue]switch(b):=block
([SW],
if length(b)#8 then
  (print("bit長度要為8"),
   return([])
  ),
SW:[b[5],b[6],b[7],b[8],b[1],b[2],b[3],b[4]],
print("將8bit的前4bit和後4bit交換"),
print("SW",matrix(["b1","b2","b3","b4","b5","b6","b7","b8"],b),"=",
               matrix(["b5","b6","b7","b8","b1","b2","b3","b4"],SW)),
return(SW)
)$[/color]

[color=green]S-DES加密[/color]
[color=red](%i9)[/color]
[color=blue]SDESencrypt(P,Key):=block
([C,SubKey1,SubKey2],
print("密鑰Key=",Key,"產生子密鑰SubKey1和SubKey2"),
[SubKey1,SubKey2]:subkey(Key),
print("明文P=",P,"進行加密"),
C:initial_permutation(P,false),
print("－－－－－－－－－－－"),
print("第1回合fk運算"),
C:permute_substitute(C,SubKey1),
print("－－－－－－－－－－－"),
C:switch(C),
print("－－－－－－－－－－－"),
print("第2回合fk運算"),
C:permute_substitute(C,SubKey2),
print("－－－－－－－－－－－"),
C:initial_permutation(C,true),
print("密文C=",C),
return(C)
)$[/color]

[color=green]S-DES解密[/color]
[color=red](%i10)[/color]
[color=blue]SDESdecrypt(C,Key):=block
([P,SubKey1,SubKey2],
print("密鑰Key=",Key,"產生子密鑰SubKey1和SubKey2"),
[SubKey1,SubKey2]:subkey(Key),
print("密文C=",C,"進行解密"),
P:initial_permutation(C,false),
print("－－－－－－－－－－－"),
print("第1回合fk運算"),
P:permute_substitute(P,SubKey2),
print("－－－－－－－－－－－"),
P:switch(P),
print("－－－－－－－－－－－"),
print("第2回合fk運算"),
P:permute_substitute(P,SubKey1),
print("－－－－－－－－－－－"),
P:initial_permutation(P,true),
print("明文P=",P),
return(P)
)$[/color]

[color=green]明文和密鑰[/color]
[color=red](%i12)[/color]
[color=blue]Plaintext:[0,0,1,0,1,0,0,0];
Key:[1,1,0,0,0,1,1,1,1,0];[/color]
[color=red](%o12)[/color]　\(\matrix{\left[0,0,1,0,1,0,0,0\right] \cr \left[1,1,0,0,0,1,1,1,1,0\right]}\)

[color=green]加密得到密文[/color]
[color=red](%i13)[/color]　[color=blue]Ciphertext:SDESencrypt(Plaintext,Key);[/color]
密鑰\( Key=\left[1,1,0,0,0,1,1,1,1,0\right]\)產生子密鑰\(SubKey1\)和\(SubKey2\)
將\(10bit\)重新排列
\(P10 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10\cr1&1&0&0&0&1&1&1&1&0}\right]=
\left[ \matrix{b3&b5&b2&b7&b4&b10&b1&b9&b8&b6\cr0&0&1&1&0&0&1&1&1&1}\right]\)
將\(10bit\)分成左\(5bit\)和右\(5bit\),各向左平移\(1bit\)
\(LS1 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10\cr 0&0&1&1&0&0&1&1&1&1}\right]=
\left[ \matrix{b2&b3&b4&b5&b1&b7&b8&b9&b10&b6\cr 0&1&1&0&0&1&1&1&1&0}\right]\)
將\(10bit\)取其中\(8bit\)重新排列
\(P8 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10\cr0&1&1&0&0&1&1&1&1&0}\right]=
\left[ \matrix{b6&b3&b7&b4&b8&b5&b10&b9\cr1&1&1&0&1&0&0&1}\right]\)
得到子密鑰\(SubKey1=\left[1,1,1,0,1,0,0,1\right]\)
－－－－－－－－－－－
取\(LS1\)結果\(\left[0,1,1,0,0,1,1,1,1,0\right]\)
將\(10bit\)分成左\(5bit\)和右\(5bit\),各向左平移\(2bit\)
\(LS2 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10\cr0&1&1&0&0&1&1&1&1&0}\right]=
\left[ \matrix{b3&b4&b5&b1&b2&b8&b9&b10&b6&b7\cr1&0&0&0&1&1&1&0&1&1}\right]\)
將\(10bit\)取其中\(8bit\)重新排列
\(P8 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10\cr1&0&0&0&1&1&1&0&1&1}\right]=
\left[ \matrix{b6&b3&b7&b4&b8&b5&b10&b9\cr1&0&1&0&0&1&1&1}\right]\)
得到子密鑰\(SubKey2=\left[1,0,1,0,0,1,1,1\right]\)
－－－－－－－－－－－
明文\(P=\left[0,0,1,0,1,0,0,0\right]\)進行加密
將\(8bit\)重新排列
\(IP \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8\cr0&0&1&0&1&0&0&0}\right]=
\left[ \matrix{b2&b6&b3&b1&b4&b8&b5&b7\cr0&0&1&0&0&0&1&0}\right]\)
－－－－－－－－－－－
第1回合\(fk\)運算
將\(8bit\)分成左\(4bit\)和右\(4bit\),\(Lbits=\left[0,0,1,0\right],Rbits=\left[0,0,1,0\right]\)
將\(Rbits=\left[0,0,1,0\right]\)擴展成\(8bit\)
\(RX \left[ \matrix{b1&b2&b3&b4\cr0&0&1&0}\right]=
\left[ \matrix{b4&b1&b2&b3&b2&b3&b4&b1\cr0&0&0&1&0&1&0&0}\right]\)
和子密鑰\(SubKey=\left[1,1,1,0,1,0,0,1\right]\)進行\(xor\)運算
\(RX⊕SubKey= \left[ \matrix{0&0&0&1&0&1&0&0\cr1&1&1&0&1&0&0&1\cr－&－&－&－&－&－&－&－\cr1&1&1&1&1&1&0&1}\right]=\left[1,1,1,1,1,1,0,1\right]\)
將\(8bit\)分成左\(4bit=\left[1,1,1,1\right]\)和右\(4bit=\left[1,1,0,1\right]\)
左\(4bit=\left[1,1,1,1\right]\)進\(SBox0\)替換
第1,4個\(bit=\left[1,1\right]\)轉十進位為第3列,第2,3個\(bit=\left[1,1\right]\)轉十進位為第3行
\(S0=\left[ \matrix{1&0&3&2 \cr 3&2&1&0 \cr 0&2&1&3 \cr 3&1&3&2 }\right],S0 \left[ 3,3 \right] =2\),轉成二進位\(leftbits=\left[1,0\right]\)
右\(4bit=\left[1,1,0,1\right]\)進\(SBox1\)替換
第1,4個\(bit=\left[1,1\right]\)轉十進位為第3列,第2,3個\(bit=\left[1,0\right]\)轉十進位為第2行
\(S1=\left[ \matrix{0&1&2&3 \cr 2&0&1&3 \cr 3&0&1&0 \cr 2&1&0&3} \right],S1 \left[ 3,2 \right] =0\),轉成二進位\(rightbits=\left[0,0\right]\)
組合成\(4bit,\left[leftbits,rightbits\right]=\left[1,0,0,0\right]\)
將\(4bit\)重新排列
\(P4 \left[ \matrix{b1&b2&b3&b4\cr1&0&0&0}\right]=
\left[ \matrix{b2&b4&b3&b1\cr0&0&0&1}\right]\)
再和前面的\(Lbits=\left[0,0,1,0\right]\)進行\(xor\)運算
\(Lbits⊕P4=\left[ \matrix{0&0&1&0\cr0&0&0&1\cr－&－&－&－\cr0&0&1&1}\right]=\left[0,0,1,1\right]\)
再和前面的\(Rbits\)組合成\(8bit,\left[Lbits,Rbits\right]=\left[0,0,1,1,0,0,1,0\right]\)
－－－－－－－－－－－
將\(8bit\)的左\(4bit\)和右\(4bit\)交換
\(SW \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8\cr0&0&1&1&0&0&1&0}\right]=
\left[ \matrix{b5&b6&b7&b8&b1&b2&b3&b4\cr0&0&1&0&0&0&1&1}\right]\)
－－－－－－－－－－－
第2回合\(fk\)運算
將\(8bit\)分成左\(4bit\)和右\(4bit,Lbits=\left[0,0,1,0\right],Rbits=\left[0,0,1,1\right]\)
將\(Rbits=\left[0,0,1,1\right]\)擴展成\(8bit\)
\(RX \left[ \matrix{b1&b2&b3&b4\cr0&0&1&1}\right]=
\left[ \matrix{b4&b1&b2&b3&b2&b3&b4&b1\cr1&0&0&1&0&1&1&0}\right]\)
和子密鑰\(SubKey=\left[1,0,1,0,0,1,1,1\right]\)進行\(xor\)運算
\(RX⊕SubKey= \left[ \matrix{1&0&0&1&0&1&1&0\cr1&0&1&0&0&1&1&1\cr－&－&－&－&－&－&－&－\cr0&0&1&1&0&0&0&1}\right]=\left[0,0,1,1,0,0,0,1\right]\)
將\(8bit\)分成左\(4bit=\left[0,0,1,1\right]\)和右\(4bit=\left[0,0,0,1\right]\)
左\(4bit=\left[0,0,1,1\right]\)進\(SBox0\)替換
第1,4個\(bit=\left[0,1\right]\)轉十進位為第1列,第2,3個\(bit=\left[0,1\right]\)轉十進位為第1行
\(S0=\left[ \matrix{1&0&3&2\cr3&2&1&0\cr0&2&1&3\cr3&1&3&2}\right],S0\left[1,1\right]=2\),轉成二進位\(leftbits=\left[1,0\right]\)
右\(4bit=\left[0,0,0,1\right]\)進\(SBox1\)替換
第1,4個\(bit=\left[0,1\right]\)轉十進位為第1列,第2,3個\(bit=\left[0,0\right]\)轉十進位為第0行
\(S1=\left[ \matrix{0&1&2&3\cr2&0&1&3\cr3&0&1&0\cr2&1&0&3}\right],S1 \left[1,0\right]=2 \),轉成二進位\(rightbits=\left[1,0\right]\)
組合成\(4bit,\left[leftbits,rightbits \right]=\left[1,0,1,0\right]\)
將\(4bit\)重新排列
\(P4 \left[ \matrix{b1&b2&b3&b4\cr1&0&1&0}\right]=
\left[ \matrix{b2&b4&b3&b1\cr0&0&1&1}\right]\)
再和前面的\(Lbits=\left[0,0,1,0\right]\)進行\(xor\)運算
\(Lbits⊕P4= \left[ \matrix{0&0&1&0\cr0&0&1&1\cr－&－&－&－\cr0&0&0&1}\right]=\left[0,0,0,1\right]\)
再和前面的\(Rbits\)組合成\(8bit,\left[Lbits,Rbits\right]=\left[0,0,0,1,0,0,1,1\right]\)
－－－－－－－－－－－
將\(8bit\)s重新排列
\(IP^{-1}\left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8\cr0&0&0&1&0&0&1&1}\right]=\left[ \matrix{b4&b1&b3&b5&b7&b2&b8&b6\cr1&0&0&0&1&0&1&0}\right]\)
密文\(C=\left[1,0,0,0,1,0,1,0\right]\)
[color=red](%o13)[/color]　\(\left[1,0,0,0,1,0,1,0\right]\)

[color=green]解密得到明文[/color]
[color=red](%i14)[/color]　[color=blue]P:SDESdecrypt(Ciphertext,Key);[/color]
密鑰\( Key=\left[1,1,0,0,0,1,1,1,1,0\right] \)產生子密鑰\(SubKey1\)和\(SubKey2\)
將\(10bit\)重新排列
\(P10 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10 \cr 1&1&0&0&0&1&1&1&1&0}\right]=\left[ \matrix{b3&b5&b2&b7&b4&b10&b1&b9&b8&b6 \cr 0&0&1&1&0&0&1&1&1&1}\right]\)
將\(10bit\)分成左\(5bit\)和右\(5bit\),各向左平移\(1bit\)
\(LS1 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10 \cr 0&0&1&1&0&0&1&1&1&1}\right]=\left[ \matrix{b2&b3&b4&b5&b1&b7&b8&b9&b10&b6 \cr 0&1&1&0&0&1&1&1&1&0}\right]\)
將\(10bit\)取其中\(8bit\)重新排列
\(P8 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10 \cr 0&1&1&0&0&1&1&1&1&0}\right]=\left[ \matrix{b6&b3&b7&b4&b8&b5&b10&b9 \cr 1&1&1&0&1&0&0&1}\right]\)
得到子密鑰\(SubKey1=[1,1,1,0,1,0,0,1] \)
－－－－－－－－－－－
取\(LS1\)結果\([0,1,1,0,0,1,1,1,1,0]\)
將\(10bit\)分成左\(5bit\)和右\(5bit\),各向左平移\(2bit\)
\(LS2 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10 \cr 0&1&1&0&0&1&1&1&1&0}\right]=\left[ \matrix{b3&b4&b5&b1&b2&b8&b9&b10&b6&b7 \cr 1&0&0&0&1&1&1&0&1&1}\right]\)
將\(10bit\)取其中\(8bit\)重新排列
\(P8 \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8&b9&b10 \cr 1&0&0&0&1&1&1&0&1&1}\right]=\left[ \matrix{b6&b3&b7&b4&b8&b5&b10&b9 \cr 1&0&1&0&0&1&1&1}\right]\)
得到子密鑰\(SubKey2=[1,0,1,0,0,1,1,1] \)
－－－－－－－－－－－
密文\(C=\left[1,0,0,0,1,0,1,0\right] \)進行解密
將\(8bit\)重新排列
\( IP \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8 \cr 1&0&0&0&1&0&1&0}\right]=
\left[ \matrix{b2&b6&b3&b1&b4&b8&b5&b7 \cr 0&0&0&1&0&0&1&1}\right]\)
－－－－－－－－－－－
第1回合\(fk\)運算
將\(8bit\)分成左\(4bit\)和右\(4bit,Lbits=[0,0,0,1],Rbits=[0,0,1,1]\)
將\(Rbits=[0,0,1,1]\)擴展成\(8bit\)
\( RX \left[ \matrix{b1&b2&b3&b4 \cr 0&0&1&1}\right]=\left[ \matrix{b4&b1&b2&b3&b2&b3&b4&b1 \cr 1&0&0&1&0&1&1&0}\right]\)
和子密鑰\(SubKey=[1,0,1,0,0,1,1,1] \)進行\(xor\)運算
\(RX⊕SubKey=\left[ \matrix{1&0&0&1&0&1&1&0 \cr 1&0&1&0&0&1&1&1 \cr －&－&－&－&－&－&－&－ \cr 0&0&1&1&0&0&0&1} \right] = [0,0,1,1,0,0,0,1]\)
將\(8bit\)分成左\(4bit=[0,0,1,1] \)和右\(4bit=[0,0,0,1] \)
左\(4bit= [0,0,1,1] \)進\(SBox0\)替換
第1,4個\(bit=[0,1]\)轉十進位為1列,第2,3個\(bit=[0,1]\)轉十進位為1行
\(S0=\left[ \matrix{1&0&3&2 \cr 3&2&1&0 \cr 0&2&1&3 \cr 3&1&3&2}\right] ,S0[1,1]=2 \),轉成二進位\(leftbits=[1,0] \)
右\(4bit= [0,0,0,1] \)進\(SBox1\)替換
第1,4個\(bit=[0,1]\)轉十進位為第1列,第2,3個\(bit=[0,0]\)轉十進位為第0行
\(S1=\left[ \matrix{0&1&2&3 \cr 2&0&1&3 \cr 3&0&1&0 \cr 2&1&0&3}\right] ,S1[1,0]=2 \),轉成二進位\(rightbits=[1,0] \)
組合成\(4bit,[leftbits,rightbits]= [1,0,1,0] \)
將\(4bit\)重新排列
\( P4 \left[ \matrix{b1&b2&b3&b4 \cr 1&0&1&0}\right]=\left[ \matrix{b2&b4&b3&b1 \cr 0&0&1&1}\right]\)
再和前面的\(Lbits= [0,0,0,1] \)進行\(xor\)運算
\(Lbits⊕P4=\left[ \matrix{0&0&0&1 \cr 0&0&1&1 \cr －&－&－&－ \cr 0&0&1&0} \right] = [0,0,1,0] \)
再和前面的\(Rbits\)組合成\(8bit,[Lbits,Rbits]= [0,0,1,0,0,0,1,1] \)
－－－－－－－－－－－
將\(8bit\)的左\(4bit\)和右\(4bit\)交換
\( SW \left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8 \cr 0&0&1&0&0&0&1&1}\right]=\left[ \matrix{b5&b6&b7&b8&b1&b2&b3&b4 \cr 0&0&1&1&0&0&1&0}\right]\)
－－－－－－－－－－－
第2回合\(fk\)運算
將\(8bit\)分成左\(4bit\)和右\(4bit\) ,\(Lbits= [0,0,1,1] ,Rbits=[0,0,1,0] \)
將\(Rbits=[0,0,1,0]\)擴展成\(8bit\)
\( RX \left[ \matrix{b1&b2&b3&b4 \cr 0&0&1&0}\right]=\left[ \matrix{b4&b1&b2&b3&b2&b3&b4&b1 \cr 0&0&0&1&0&1&0&0}\right]\)
和子密鑰\(SubKey=[1,1,1,0,1,0,0,1] \)進行\(xor\)運算
\(RX⊕SubKey=\left[ \matrix{0&0&0&1&0&1&0&0 \cr 1&1&1&0&1&0&0&1 \cr －&－&－&－&－&－&－&－ \cr 1&1&1&1&1&1&0&1}\right] = [1,1,1,1,1,1,0,1] \)
將\(8bit\)分成左\(4bit=[1,1,1,1] \)和右\(4bit=[1,1,0,1] \)
左\(4bit=[1,1,1,1] \)進\(SBox0\)替換
第1,4個\(bit=[1,1]\)轉十進位為第3列,第2,3個\(bit=[1,1]\)轉十進位為第3行
\(S0=\left[ \matrix{1&0&3&2 \cr 3&2&1&0 \cr 0&2&1&3 \cr 3&1&3&2}\right],S0[3,3]=2 \),轉成二進位\(leftbits=[1,0] \)
右\(4bit= [1,1,0,1] \)進\(SBox1\)替換
第1,4個\(bit=[1,1]\)轉十進位為第3列,第2,3個\(bit=[1,0]\)轉十進位為第2行
\(S1=\left[ \matrix{0&1&2&3 \cr 2&0&1&3 \cr 3&0&1&0 \cr 2&1&0&3}\right],S1[3,2]=0\),轉成二進位\(rightbits=[0,0] \)
組合成\(4bit,[leftbits,rightbits]= [1,0,0,0] \)
將\(4bit\)重新排列
\( P4 \left[ \matrix{b1&b2&b3&b4 \cr 1&0&0&0}\right]=\left[ \matrix{b2&b4&b3&b1 \cr 0&0&0&1}\right]\)
再和前面的\(Lbits=[0,0,1,1] \)進行\(xor\)運算
\(Lbits⊕P4=\left[ \matrix{0&0&1&1 \cr 0&0&0&1 \cr －&－&－&－ \cr 0&0&1&0}\right] = [0,0,1,0] \)
再和前面的\(Rbits\)組合成\(8bit,[Lbits,Rbits]= [0,0,1,0,0,0,1,0] \)
－－－－－－－－－－－
將\(8bit\)重新排列
\(IP^{-1}\left[ \matrix{b1&b2&b3&b4&b5&b6&b7&b8 \cr 0&0&1&0&0&0&1&0}\right]=\left[ \matrix{b4&b1&b3&b5&b7&b2&b8&b6 \cr 0&0&1&0&1&0&0&0}\right]\)
明文\(P= [0,0,1,0,1,0,0,0] \)
[color=red](%o14)[/color]　\([0,0,1,0,1,0,0,0]\)

[color=green]檢查是否和原來的明文相同[/color]
[color=red](%i15)[/color]
[color=blue]if P=Plaintext then
  (print("和原來明文相同"))
else
  (print("和原來明文不同"));[/color]
[color=red](%o15)[/color]　和原來明文相同

bugmens 發表於 2018-8-12 13:40

省略運算過程，僅顯示運算結果
請下載[url=https://math.pro/db/attachment.php?aid=4656&k=e1246f0875dd14359f1e6eb173023a06&t=1534052317]SDES.zip[/url]，解壓縮後將SDES.mac放到C:\maxima-5.41.0\share\maxima\5.41.0目錄下

[color=green]要先載入SDES.mac才能使用SDESencrypt和SDESdecrypt指令[/color]
[color=red](%i1)[/color]　[color=blue]load("SDES.mac");[/color]
[color=red](%o1)[/color]　[i]C:\maxima-5.41.0\share\maxima\5.41.0\SDES.mac[/i]

[color=green]明文和密鑰[/color]
[color=red](%i3)[/color]
[color=blue]Plaintext:[0,0,1,0,1,0,0,0];
Key:[1,1,0,0,0,1,1,1,1,0];[/color]
[color=red](Plaintext)[/color]　\([0,0,1,0,1,0,0,0]\)
[color=red](Key)[/color]　\([1,1,0,0,0,1,1,1,1,0]\)

[color=green]加密得到密文[/color]
[color=red](%i4)[/color]　[color=blue]Ciphertext:SDESencrypt(Plaintext,Key);[/color]
[color=red](Ciphertext)[/color]　\([1,0,0,0,1,0,1,0]\)

[color=green]解密得到明文[/color]
[color=red](%i5)[/color]　[color=blue]P:SDESdecrypt(Ciphertext,Key);[/color]
[color=red](P)[/color]　\([0,0,1,0,1,0,0,0]\)

[color=green]檢查是否和原來的明文相同[/color]
[color=red](%i6)[/color]
[color=blue]if P=Plaintext then
  (print("和原來明文相同"))
else
  (print("和原來明文不同"));[/color]
[color=red](%o6)[/color]　和原來明文相同

查看完整版本: 用maxima學對稱密碼學－簡化的DES(S-DES)