实现基于IDEA算法的加密工具(4)

3.3.密文解密

　　介绍IDEA加密算法的资料本就不多而且对于解密过程往往一笔带过,笔者在编程实现IDEA算法时为此大伤脑筋,好在这块骨头总算被啃下了.下文笔者将结合实现代码介绍一下解密过程,假如读者想亲自动手实现IDEA算法,笔者的”痛苦经验”是可以让你少走些弯路的.

解密操作和加密的步骤基本相同,但是在求密钥时有所区别.

首先从用户输入的128位密钥扩展出52个子密钥,存放在ULONG16 Key[52]数组中,然后对这个52个子密钥进行换位操作,

新位置:
0
1
2
3
4
5
6
7
8
9
10
11
12
13

原位置:
48
49
50
51
46
47
42
44
43
45
40
41
36
38

新位置:
14
15
16
17
18
19
20
21
22
23
24
25
26
27

原位置:
37
39
34
35
30
32
31
33
28
29
24
26
25
27

新位置:
28
29
30
31
32
33
34
35
36
37
38
39
40
41

原位置:
22
23
18
20
19
21
16
17
12
14
13
15
10
11

新位置:
42
43
44
45
46
47
48
49
50
51
　　　　
原位置:
6
8
7
9
4
5
0
1
2
3
　　　　

表中的原位置行的值代表该子密钥在原密钥数组中的位置,比如新密钥数组中的第0号子密钥为原来子密钥组中的第48号子密钥,对子密钥数组换位后,就需要对某些子密钥进行模216+1的乘法逆或模216加法逆的替换,详情见下表(位置是针对换位后的子密钥组)请看下一页
进行加法逆替换的子密钥的位置:

1
2
7
8
13
14
19
20
25

26
31
32
37
38
43
44
49
50

进行乘法逆替换的子密钥的位置:

0
3
6
9

12
15
18
21
24

27
30
33
36
39
42
45
48
51

需要变化的子密钥总共18+18 = 36个,另外的52 – 36 = 16个子密钥不变化.
下面介绍有关x逆元的计算方法.

X模216加法逆比较简单: x -1 = 65536 – x ;

X模216+1乘法法逆和X的关系如下:

(X*X-1 ) %65537 = 1

求解X-1需要一定的计算量,具体的算法实现代码如下:

#define LOW16(x) ((x)&0xffff)

ULONG16 mulInv( ULONG16 x)

{

ULONG16 t0,t1;

ULONG16 q,y;

if ( x<=1)

{

return x;

}

t1 = 0x10001L/x;

y = 0x10001L%x;

if(y == 1)

{

return LOW16(1-t1);

}

t0 = 1 ;

do

{

q = x/y;

x %= y;

t0 += q*t1;

if( x == 1)

{

return t0;

}

q = y/x;

y %=x;

t1 += q*t0;

}while( y != 1);

return LOW16(1-t1);

}