鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 网站安全 > 加密解密 > >

数据基础知识谈

来源:互联网 作者:佚名 时间:2015-10-09 06:18
作者:众人 文章来源:看雪学院 用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
作者:众人 文章来源:看雪学院
用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)*D3 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进行解密操作
现在我的考虑是这个数据不能直接的解密,可能解密还应
该有一个解密的密码表,但是解密的密码表应该可以用加
密的密码表算出来,不知道我说的对不对,各位大侠帮小
弟看看,谢谢了,
 
关于一个解密算法的解答

作者?:?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

-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方面的书籍。祝你学习愉快!!
于一个解密算法的解答(补充)

作者?:?zmworm
E-Mail:?zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net

 ? 刚才说的情况是 e'存在的情况,若e'不存在,应该怎样解密呢?

 ? 首先,我们要知道e满足什么条件时,e'存在。我们有以下定理:

 ??? 如果gcd(e,f)=1(即 e,f 互素),那么e有一个模f的乘法逆元。
 ??? [gcd(e,f)=p,表示e,f的最大公约数是p,求最大公约数可以用辗转相除法]

 ? 如果gcd(e,f)=p(p>1) 则 不存在e关于f的乘法逆元。


 ? 现在我们就求乘法逆元不存在时 K*e mod f=d 的解-----------------[e]

 ??? 因为 gcd(e,f)=p 所以 p|e, p|f,设 e"=e/p ,f"=f/p ,m=K*e div f,则
 ??? K*e mod f=d => K*e=m*f+d => K*e"*p=m*f"*p+d => d=K*e"*p-m*f"*p=(K*e"-m*f")*p

 ??? 所以 p|d, 令 d"=d/p ,则
 ??? K*e mod f=d => K*e"*p=m*f"*p+d"*p => K*e"=m*f"+d" => K*e" mod f"=d"

 ??? 而 gcd(e",f")=1,这样我们就可以求e"的逆元e'
 ??? 所以 d"*(e'*e") mod f"=d" =>d"*e'*e"*p mod f"*p=d"p
 ??? 即 (d"*e')*e mod f=d -------------------------------------[f]

 ??? 对比[e] [f] 有 K=d"*e'


 ??? 注意 这只是K的一个解
 ??? 事实上,Ki=d"*e'+(i-1)f"?(i=1..p) 都满足条件, 因为 (d"*e'+if")*e" mod f"=d"

 ??? 也就是说,若gcd(e,f)=p 则K有p个值

 ? [例] 求 满足K*14 mod 96 =12中K的值

 ? 解 因为gcd(14,96)=2,所以k 有两个解
 ? e"=14/2=7 f"=96/2=48 d"=12/2=6
 ? 7关于 48的逆元e'=7 (因为 7*7 mod 48 =1)
 ? 所以 Ki=d"*e'+(i-1)f"=6*7+(i-1)*48 (i=1,2)
 ? 解得 K1=42 K2=90

若不存在逆元的解密算法为

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)
关于一个解密算法的解答(对K的补充说明)

作者?:?zmworm
E-Mail:?zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net


(1)若不存在逆元,求K时
 ? Ki=d"*e'+(i-1)f"
 ? 若 d"*e' 大于 f"时需要进行模运算 即Ki=[(d"*e') mod f"]+(i-1)f"

(2)前面的方法我们已经可以求出至少一组明文,如果您想求出所有满足条件的解,你还要继续往下看。

 ? 细心的您一定发现了我们前面所求得K都是小于f的,而事实上
 ? 若K满足K*e mod f=d ,则所有的Ki=K+i*f(i=1..n) 也满足Ki*e mod f=d
 ? 那么说满足K*e mod f=d的 K应该有无数多个。

 ? 在数学中的确如此,
 ? 在计算机中则不同,要根据字长设字长为n,对每一个K
 ? 应该有 2^n div f 或(2^n div f)+1个
 ? 只要Ki=K+i*f <2^n 都满足
 ? Ki=K+i*f >2^n 就会发生溢出错误了。
于一个解密算法的解答(此算法的具体例子)

作者?:?zmworm
E-Mail:?zmworm@sohu.com
HomePage: ZMWorm.Yeah.Net?

[习题]
以下各变量的字长均为8位

用A1=96?B1=96 C1=97 D1=97?
  A2=7?B2=14 C2=21 D2=28
  A3=33?B3=34 C3=35 D3=36
算法?
  (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
对M1,M2,M3,M4 进行加密操作

求得
  (M1 xor 33 xor?0)*7?mod 96=86
  (M2 xor 34 xor 86)*14 mod 96=80?
  (M3 xor 35 xor 80)*21 mod 97=93
  (M4 xor 36 xor 93)*28 mod 97=25?
即密文为?N1=86 N2=80 N3=93 N4=25

问所有可能的明文M1 M2 M3 M4



gcd(7,96)=1 所以K1 有一个解
7模96的乘法逆元为55 (因为 7*55 mod 96=1)
所以K1=55*N1 mod 96 =26
K1所有可能情况是 26 ,26+96=122 ,122+96=218,
M1=26 xor 33 xor 0=59
M1=122 xor 33 xor 0=91
M1=218 xor 33 xor 0=251

M1 的所有可能是 59, 91, 251


gcd(14,96)=2,所以k 有两个解
e"=14/2=7 f"=96/2=48 d"=80/2=40
7关于 48的逆元e'=7 (因为 7*7 mod 48 =1)
所以 K2[i]i=d"*e'+(i-1)f"=[(40*7) mod 48]+(i-1)*48 (i=1,2)
解得 K2[1]=40 K2[2]=88
K2所有可能情况是 40 ,40+96=136 ,136+96=232, 88 88+96=184
M2=40 xor 34 xor 86=92
M2=136 xor 34 xor 86=252
M2=232 xor 34 xor 86=156
M2=88 xor 34 xor 86=44
M2=184 xor 34 xor 86=204

M2的所有可能是 92, 252, 156, 44, 206

gcd(21,97)=1 所以K1 有一个解
模96的乘法逆元为37 (因为 37*21 mod 97=1)
所以K1=37*N3 mod 97 =46
K1所有可能情况是 46 ,46+97=143 ,143+97=240,
M3=46 xor 35 xor 80=93
M3=143 xor 35 xor 80=252
M3=240 xor 35 xor 80=136

M2的所有可能是 93, 252, 136


M4 留为作业 ,自己求。答案不确定可以问我。
 
网友评论
<