﻿ Math Pro 數學補給站

1.S-DES架構

2.以密鑰$$key=1100011110$$，示範如何產生子密鑰$$K_1=11101000$$和$$K_2=10100111$$

3.以明文$$plaintext=00101000$$，示範如何產生密文$$ciphertext=10001010$$

http://desalgorithm.yolasite.com有提供完整的$$S-DES$$動畫，讓學習者可以了解整個運作過程，本文章的範例取自這裡。

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

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)

(%i1)
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)
)
)$向左平移(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) (%i2) 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) ) )$

4bit重新排列(permutation4)
P4(b1,b,2,b3,b4)=(b2,b4,b3,b1)

(%i3)
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)
)$10bit取其中8bit重新排列(permutation8) P8(b1,b,2,b3,b4,b5,b6,b7,b8,b9,b10)=(b6,b3,b7,b4,b8,b5,b10,b9) (%i4) 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) )$

10bit重新排列(permutation10)
P10(b1,b,2,b3,b4,b5,b6,b7,b8,b9,b10)=(b3,b5,b2,b7,b4,b10,b1,b9,b8,b6)

(%i5)
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)
)$排列代換(permute_substitute) 計算Π_F(L,R)=(L⊕F(R,S),R) (%i6) 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) )$

(%i7)
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])
)$交換(switch),將8bit的前4bit和後4bit交換 (%i8) 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) )$

S-DES加密
(%i9)
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)
)$S-DES解密 (%i10) 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) )$

(%i12)
Plaintext:[0,0,1,0,1,0,0,0];
Key:[1,1,0,0,0,1,1,1,1,0];

(%o12)　$$\matrix{\left[0,0,1,0,1,0,0,0\right] \cr \left[1,1,0,0,0,1,1,1,1,0\right]}$$

(%i13)　Ciphertext:SDESencrypt(Plaintext,Key);

$$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]$$

$$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]$$

$$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]$$

－－－－－－－－－－－

$$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]$$

$$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]$$

－－－－－－－－－－－

$$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]$$
－－－－－－－－－－－

$$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]$$

$$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]$$

$$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]$$

$$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]$$

$$P4 \left[ \matrix{b1&b2&b3&b4\cr1&0&0&0}\right]= \left[ \matrix{b2&b4&b3&b1\cr0&0&0&1}\right]$$

$$Lbits⊕P4=\left[ \matrix{0&0&1&0\cr0&0&0&1\cr－&－&－&－\cr0&0&1&1}\right]=\left[0,0,1,1\right]$$

－－－－－－－－－－－

$$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]$$
－－－－－－－－－－－

$$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]$$

$$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]$$

$$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]$$

$$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]$$

$$P4 \left[ \matrix{b1&b2&b3&b4\cr1&0&1&0}\right]= \left[ \matrix{b2&b4&b3&b1\cr0&0&1&1}\right]$$

$$Lbits⊕P4= \left[ \matrix{0&0&1&0\cr0&0&1&1\cr－&－&－&－\cr0&0&0&1}\right]=\left[0,0,0,1\right]$$

－－－－－－－－－－－

$$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]$$

(%o13)　$$\left[1,0,0,0,1,0,1,0\right]$$

(%i14)　P:SDESdecrypt(Ciphertext,Key);

$$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]$$

$$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]$$

$$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]$$

－－－－－－－－－－－

$$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]$$

$$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]$$

－－－－－－－－－－－

$$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]$$
－－－－－－－－－－－

$$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]$$

$$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]$$

$$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]$$

$$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]$$

$$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⊕P4=\left[ \matrix{0&0&0&1 \cr 0&0&1&1 \cr －&－&－&－ \cr 0&0&1&0} \right] = [0,0,1,0]$$

－－－－－－－－－－－

$$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]$$
－－－－－－－－－－－

$$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]$$

$$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]$$

$$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]$$

$$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]$$

$$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⊕P4=\left[ \matrix{0&0&1&1 \cr 0&0&0&1 \cr －&－&－&－ \cr 0&0&1&0}\right] = [0,0,1,0]$$

－－－－－－－－－－－

$$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]$$

(%o14)　$$[0,0,1,0,1,0,0,0]$$

(%i15)
if P=Plaintext then
(print("和原來明文相同"))
else
(print("和原來明文不同"));

(%o15)　和原來明文相同

(%o1)　C:\maxima-5.41.0\share\maxima\5.41.0\SDES.mac

(%i3)
Plaintext:[0,0,1,0,1,0,0,0];
Key:[1,1,0,0,0,1,1,1,1,0];

(Plaintext)　$$[0,0,1,0,1,0,0,0]$$
(Key)　$$[1,1,0,0,0,1,1,1,1,0]$$

(%i4)　Ciphertext:SDESencrypt(Plaintext,Key);
(Ciphertext)　$$[1,0,0,0,1,0,1,0]$$

(%i5)　P:SDESdecrypt(Ciphertext,Key);
(P)　$$[0,0,1,0,1,0,0,0]$$

(%i6)
if P=Plaintext then
(print("和原來明文相同"))
else
(print("和原來明文不同"));

(%o6)　和原來明文相同

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