[整理]重新整理答案，修正表格错位问题 (2千字)

关于一个解密算法的解答
作者  ：  zmworm
E-Mail:  zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net

blueboy问如下问题：
用A1 B1 C1 D1 对M1,M2,M3,M4 加密
  A2 B2 C2 D2
  A3 B3 C3 D3
算法
  (M1 xor A3 xor  0)*A2 mod A1=N1  N1 and FFFF=S1
  (M2 xor B3 xor S1)*B2 mod B1=N2  N2 and FFFF=S2
  (M3 xor C3 xor S2)*C2 mod C1=N3  N3 and FFFF=S3
  (M4 xor D3 xor S3)*D2 mod D1=N4  N4 and FFFF=S4
最后生成的明文为N1,N2,N3,N4
现在已知N1,N2,N3,N4, A1,B1,....C3,D3
知道M1,M2,M3,M4为WORD类型,其他的为整数类型
问应该怎么对N1,N2,N3,N4进行解密操作
现在我的考虑是这个数据不能直接的解密,可能解密还应
该有一个解密的密码表,但是解密的密码表应该可以用加
密的密码表算出来,不知道我说的对不对,各位大侠帮小
弟看看,谢谢了，
答案如下：
因为是字长是WORD，所以
N1=S1
N2=S2
N3=S3
N4=S4
所以加密变换化简为[a]
(M1 xor A3 xor  0)*A2 mod A1=N1
(M2 xor B3 xor N1)*B2 mod B1=N2
(M3 xor C3 xor N2)*C2 mod C1=N3 
(M4 xor D3 xor N3)*D2 mod D1=N4
设
K1=(M1 xor A3 xor  0)
K2=(M2 xor B3 xor N1)
K3=(M3 xor C3 xor N2)
K4=(M4 xor D3 xor N3)

加密变换化简为[b]
K1*A2 mod A1=N1
K2*B2 mod B1=N2
K3*C2 mod C1=N3 
K4*D3 mod D1=N4
只要我们能求出Ki，Mi也就可求了 因为
M1=(K1 xor A3 xor  0)
M2=(K2 xor B3 xor N1)
M3=(K3 xor C3 xor N2)
M4=(K4 xor D3 xor N3)
所以问题的关键是求 Ki 注意到[b]中每一等式中只有Ki未知，其他量都已知。不妨设
K*e mod f = d (e,f,d为已知量）[c]
设e'为 e 关于f的乘法逆元
（什么是乘法逆元？若e'满足e*e' mod f =1 则称e'为 e 关于f的乘法逆元）
则有
e'*e mod f= 1
根据模运算性质有
d*(e'*e) mod f=d*1=d    [d]
对比 [c] [d] 不难发现
K=d*e' mod f
所以问题转为求e的乘法逆元e'
用扩展的欧几里德算法 可以求e' .算法描述如下
ExtendedEuclid(e,f)
1 （X1,X2,X3):=(1,0,f)
2  (Y1,Y2,Y3):=(0,1,e)
3  if (Y3=0) then return  e'=null//无逆元
4  if (Y3=1) then return  e'=Y2  //Y2为逆元
5  Q:=X3 div Y3
6  (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)
7 （X1,X2,X3):=(Y1,Y2,Y3)
8  (Y1,Y2,Y3):=(T1,T2,T3)
9  goto 3
看不明白算法？我们举个例子：求7关于96的乘法逆元。

扩展辗转相除法图示

-41 mod 96 =55 所以55就是7关于96的逆元。
让我们检验一下55*7 mod 96 =1
最后我们取求K的例子，K*7 mod 96 = 13 求K
因为7的乘法逆元是55 所以  K=13*55 mod 96=715 mod 96=43  K=43
检验 43*7 mod 96=288 mod 96 =13
总结解密算法:
K1=:A2'*N1 mod A1
K2=:B2'*N2 mod B1
K3=:C2'*N3 mod C1 
K4=:D2'*N4 mod D1
M1=(K1 xor A3 xor  0)
M2=(K2 xor B3 xor N1)
M3=(K3 xor C3 xor N2)
M4=(K4 xor D3 xor N3)
小结：通过这道问题的解答，我们学习到一些新的知识，知道了什么是乘法逆元，乘法逆元在密码学中的作用也重要，RSA算法就用到了乘法逆元，感兴趣的话，你可以参考RSA方面的书籍。祝你学习愉快！！