3G的AKA协议中F1至F5的服务网络端

1 引言
1.1 课题背景
第二代（2G）及2.5代（2.5G）移动通信系统，如GSM/GPRS，是当前正在广泛运行的移动通信系统，而第三代移动通信系统（3G）是当前通信领域研究开发的热点。在3G系统中，除了要开放语音业务外，还要开放电子商务、电子贸易、网络服务等新型的业务。为此，需要在网络系统中增加安全保护措施。若信息在网络中传输没有任何保护措施，就容易受到攻击或被窃听、被修改等，而直接影响用户的利益；若未经授权的业务直接接入到网络中来，也会影响运营商的利益。因此，如何保证系统的高安全性就显得十分重要。
1.2 国内外研究现状
在国际上，ETSI与3GPP两个基于GSM/GPRS网络和WCDMA与TD/SCDMA系统标准化的组织，特别是ETSI的SAGE与3GPP的S3工作组专门对网络安全方面的规范进行了研究。通过标准的制定和不断的研究，使得3G安全体系结构内的网络接入安全规范日趋成熟，无线链路的保密性和完整性算法也有一部分实现了标准化，但AKA协议中用到的相关算法却无需进行标准化，而由运营商或制造商自行确定。在国内，发展相对缓慢一点，但仍然取得了不小的成就。尽管各国的3G发展的进程不尽相同，但现有的移动通信网络向能够提供移动多媒体业务的3G网络演进是通信业发展的必然趋势。3G时代正在向我们靠近。 【www.think58.com计算机毕业论文网】 think58 [资料来源：http://www.THINK58.com]
1.3 本课题研究的意义
此毕业设计是对3G中的一个安全协议（AKA）的服务网络端的实现加以分析和研究，以达到考查学生的专业基础知识和综合运用以及动手等多方面的能力，当然也包括以前所学的一些关于数论基础、网络、编程、信息安全等知识，同时也使学生了解当前移动通讯发展的新方向，理论联系实际，这才是当代大学生最重要但也是比较缺乏的一种能力，通过此次锻炼可以很好的锻炼学生的实际动手能力，又引导学生进行了一次模拟实际产品的开发，这是对学生在毕业前的一次重要考核，同时也为学生能很快的适应工作岗位奠定了良好的基础。
1.4 本课题的研究方法
设计思路：采用AES加密算法，在VC++中，用C语言实现。
首先，了解3GPP中的一些基本知识，搞清楚AKA协议，重点弄清f1-f5的算法以及实现。然后运用AES加密（Rijndael算法）的知识，并在基于32位处理器即PC的平台上，完成代码上的实现。最后，通过与公认的案例进行比对以验证代码的正确性，进而完成整个设计。
其次，由于此次设计采用Rijndael为核心算法，因此还对AES相关数学基础知识，实现原理作了详细的分析。
2 相关数学基础
2.1 有限域GF (28)
有限域GF(28)中的元素可以用许多不同的方式来表示，但是不同的表示方式对现实的复杂度是有影响的。AES选择用多项式表示有限域GF(28)中的元素。GF(28)中的所有元素为所有系数在GF(2)中并小于8的多项式。由b7b6b5b4b3b2b1b0构成的一个字看成是多项式

b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 (1-1)
其中bi∈GF(2),0<=i<=7。因此，GF(28)中的一个元素可以看成是一个字节。
有限域GF(28)中的两个元素相加，结果是一个多项式，其系数是两个元素中的对应系数的模2相加。显然，有限域GF(28)中的两个元素的加法与两个字节的按位模2加是一致的。两个字节的按位模2加用由表示。
有限域GF(28)中两个元素的乘法为模二元域GF(2)上的一个8次不可约多项式的多项式乘法，乘法用•表示。一个多项式是不可约，如果它除1和其自身之外没有其他的因子。对于AES，这个不可约多项式为
m(x)= x8+ x4+x3+x+1 (1-2)
m(x)用二进制表示为0000000100011011(两个字节)，用十六进制表示为OxOllb。
乘法。满足结合律，0x01(十六进制表示)是乘法单位元。对任何系数在二元域GF(2)中并且次数小于8的多项式b(x)，利用欧几里德算法可以计算a(x)和c(x)使得
a(x)b(x)+c(x)m(x)=1 (1-3)
因此
a(x)b(x)modm(x)=1 (1-4)
这就说明b(x)的逆元素为
b-1(x)=a(x)modm(x) (1-5)
另外，对任意a(x),b(x),c(x)∈GF(28)
a(x)•(b(x)+c(x))=a(x)•b(x)+a(x)•c(x) (1-6)
由上面的讨论不难看出，在按位模2加运算和乘法•运算下，256个可能字节值的集合构成了有限域GF(28)。

本文来自think58

[资料来源：http://think58.com]

考虑用x乘以多项式
b(x)= b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0 (1-7)得到
b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x (1-8)
将上面的结果模m(x)求余就得到x• b(x)。如果b7= 0，则式(1-8)就是x•b(x)。如果b7=1，则必须从式(2-8)中减去m(x)，结果为x•b(x)。用x乘以一个多项式简称为x乘。由此得出，x(十六进制表示为0x02)乘可以用字节内左移一位和紧接着的一个与1b的按位模2加来实现，x的更高的乘法可以乘以通过重复这种运算来实现。通过中间结果相加，任意乘可以用这中方法来实现。
2.2 数在GF (28)中的多项式
数在GF(28)中的多项式，多项式的系数可以定义为GF(28)中的元素。通过这种方法，一个4字节的字对应于一个次数小于4的多项式。
对相应系数的简单相加可以实现多项式加法。由于GF(28)中的加法为按位模2加，所以两个4字节的加法就是按位模2加。
乘法比较复杂，假设
a(x)=a3x3+a2x2+a1x+a0 (1-9)
和
b(x)=b3x3+b2x2+b1x+b0 (1-10)
为GF(28)上两个多项式，它们的乘积为:
c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0 (1-11)
其中：
c0= a0+b0
c2= c0•b0a1•b1a0•b2
c3= a3•b0a2•b1a1•b2a0•b3

think58 [来源：http://www.think58.com]

c4= a3•b1a2•b2a1•b3
c5= a3•b2a2•b3
c6= a3•b3
显然，c(x)不再可以表示一个4字节的字。通过对c(x)模一个4次多项式求余可以得到一个次数小于4的多项式。在AES中，这一模多项式为:
M(x)=x4+1 (1-12)
AES中两个GF(28)上的多项式的乘法定义为模M(x)乘法，这种乘法可以用⊙表示。
设
d(x)=a(x)⊙b(x)=d3x3+d2x2+d1x+d0 (1-13)
由上面的讨论可以知道:
d0=a0•b0a3•b1a2•b2a1•b3
d1=a1•b0a0•b1a0•b2a2•b3
d2=a2•b0a1•b1a0•b2a3•b3
d3=a3•b0a2•b1a1•b2a0•b3
可以看出，用一个固定的多项式a(x)与多项式b(x)做⊙运算可以写成矩阵乘法，即
(1-14)
其中矩阵是一个循环矩阵。由于x4+1不是GF(28)上的不可约化多项式，所以被一个固定多项式相乘不一定可以，AES选择一个有逆元的固定多项式:
a(x)={03}x3+{01}x2+{01}x+{02} (1-15)
a-1(x)={0b}x3+{0d}x2+{09}x+{0e} (1-16)
a(x)⊙a-1(x)= a-1(x)⊙a(x)={01} (1-17)
考虑用多项式x乘b(x)，显然
x⊙b(x)=b2x3+b1x2+c1x+c0 (1-18)

内容来自think58

假设
c(x)=x⊙b(x)=c3x3+c2x2+c1x+c0 (1-19)
则用矩阵形式表示为
(1-20)
因此，用x或者x的方幂GF(28)上的多项式等于一个4字节的左循环移位。
3 AES算法的设计准则及设计原理
3.1 分组密码通用准则
Rijndael算法是分组密码，也具有分组密码的一般设计准则，分组密码的设计就是要求算法能在密钥控制下置换，对输入的明文进行加密变换。好的分组密码应该是既难破译、高效又容易实现。
(1)安全性准则
安全性原则主要是指由香农提出的混乱和扩散原则。
混乱原则是指人们所设计的密码应使得密钥和明文以及密文之间的依赖关系相当复杂，以至于这种依赖关系对密码分析者来说无法利用。
扩散原则是指人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字，以防止对密钥进行逐段破译，而且明文的每一位数字也应该影响密文的许多位数字，以便隐蔽明文数字的统计特性。
当然这种密码体制必须能抵抗现在所有的己知密码攻击。
(2)效率性准则
效率准则是与安全性准则互补的，指的是算法在执行加/解密时所要占用的资源量，加密/解密在软件的实现中，主要与所要求的内存和存储程序所占用的内存有关，在硬件的实现中，与要求的芯片的面积有关。 [资料来源：www.THINK58.com]
(3)易实现准则
分组密码可以用软件和硬件来实现。硬件实现的优点是可获得较高的加密解密速度，软件实现的优点是灵活性强、代价低。
软件实现的设计原则是尽量使用子模块和简单的运算。密码运算在子模块上进行，要求子模块的长度能适应软件编程，如8,16和32比特等。在软件实现中，按比特运算是难于实现的，应尽量避免使用，而对子模块所进行的密码运算易于用软件实现，当然最好使用一些标准处理器所具有的基本指令，如加法、乘法和移位等。
3.2 Rijndael算法的设计原则和结构
Joan Daemen和Vincent Rijmen，在设计Rijndael算法时主要考虑了以下准则:
(1)简单性准则
简单性是Rijndael算法的设计宗旨，Rijndael算法的简单性，便于阐述和理解密码算法以何种方式来抗击已知类型的密码攻击，简单性的设计准则还有利于多种方法实现。
(2)对称性准则
Rijndael算法设计的对称性，是用多种方式实现的，可以分为各轮之间的对称性、轮变换内部的对称性和各步之间的对称性。
①各轮之间的对称性
各轮之间的对称性的好处是在密钥的控制下对同一个轮交换进行循环迭代，优点是只要描述一轮变换即可将整个规范描述清楚，在软件实现中也可以仅对一轮进行编程。

think58 [资料来源：http://THINK58.com]

②轮变换内部的对称性
轮变换内部的对称性是指对状态中所有比特均用相似方法处理。
③D一盒的对称性
④S一盒的对称性
⑥加密和解密的对称性
所以，Rijndael算法在综合了分组密码的设计准则的同时，也有其自身的设计准则,这些设计准则的优越性，提高了算法的实现速度，降低了算法的复杂度，算法还有其它的设计准则，这些设计准则在算法的原理描述中，在特定的环境中给予描述。
Rijndael算法的加密过程包括一个初始密钥加法，记着AddRoundKey,接着进行Nr一1次轮变换Round，最后再使用一个轮变换FinalRound。初始的密钥加法和每个轮变换均以状态State和一个轮密钥作为输入。第i轮的轮密钥记为Expandedkey[i]，初始密钥加法的输入记为Expandedkey[0]。从Cipherkey导出Expandedkey的过程记为KeyExpansion Rijndael的高级语言。