L2003212010_邬小洪_KASUMI算法的研究与VC实现

分类号：TP309.7 U D C：D10621-408-(2007)6152-0密 级：公 开 编 号：2003212010成都信息工程学院学位论文KASUMI算法的研究与VC实现论文作者姓名：邬 小 洪申请学位专业：计算机科学与技术申请学位类别：工学学士指导教师姓名（职称）：吴震(讲师)论文提交日期：2007年6月10日KASUMI算法的研究与VC实现摘要随着通信技术的高速发展，第三代移动通信系统（3G）将成为人们生活中重要的通信方式，3G系统中业务信息的安全性以及网络资源使用的安全性将越来越重要。为了对3G系统提供安全性，3G的国际组织3GPP（3rd Generation Partnership Project）在3G的安全结构中定义了两个标准化的核心算法f8和f9。f8算法是加密算法，f9是完整性算法，这两个算法都是基于KASUMI算法的。KASUMI算法是基于日本三菱公司的分组密码MISTY1算法，是它的改进版本，它是一种分组加密算法。 本文主要研究的是第三代移动通信技术中的一种核心加密算法：KASUMI算法；详尽介绍KASUMI算法的原理、组成部分以及怎样在VC中实现。关键字：KASUMI算法；3G；安全性；FeistelThe Research and Implementation of Kasumi Algorithm with VCAbstractAs the development of communication technology is arriving at a bewildering rate, the third generation of mobile telecommunication system (3G) is doomed to dominate our way of that. Meanwhile, how to maintain the security of operating information and network resources will be playing an ever-increasing role. In order to provide 3G with steady security, its international organization 3GPP （3rd Generation Partnership Project）has defined two standardized key arithmetic: f8 and f9. The arithmetic f8 belongs to encrypted one, while f9 has kept its integrality. But they are both based on the arithmetic of KASUMI. The article is mainly focusing on the arithmetic of KASUMI, which is the key to the encrypted third generation of mobile telecommunication. And it sheds light on the theory, composition as well as how it can be carried out in VC in detail.Key words：KASUMI;3G;Security;Feistel目 录论文总页数：26页1 引言12 KASUMI算法概述12.1 KASUMI算法的总体结构12.2 KASUMI算法的组成函数22.2.1 f函数22.2.2 FI函数32.2.3 FO函数32.2.4 FL函数42.2.5 S-box42.3 KAUSMI算法的密钥生成52.4 KAUSMI算法的安全性63 KASUMI算法流程73.1 密钥产生83.2 FI函数93.3 FO函数103.4 FL函数114 系统设计124.1 KASUMI算法程序实现124.1.1 KASUMI算法程序实现的加密解决方案124.1.2 KASUMI算法程序实现的解密解决方案134.2 人机界面设计135 关键代码分析155.1 FI函数的程序实现155.2 FO函数的程序实现165.3 FL函数的程序实现175.4 密钥产生程序实现175.5 f函数的程序实现(加密时的函数)185.6 f函数的程序实现(解密时的函数)196 软件整体测试与系统缺陷206.1 软件测试环境配置206.2 软件测试界面介绍206.3 软件测试结果216.3.1 软件的加密速度226.3.2 KASUMI算法加密/解密案例236.4 系统缺陷23结 论24参考文献24致 谢25声 明26 1 引言随着通信技术的高速发展，第三代移动通信系统（3G）将成为人们生活中重要的通信方式，3G系统中业务信息的安全性以及网络资源使用的安全性将越来越重要。为了对3G系统提供安全性，3G的国际组织3GPP（3rd Generation Partnership Project）在3G的安全结构中定义了两个标准化的核心算法f8和f9。f8算法是加密算法，f9是完整性算法，这两个算法都是基于KASUMI算法的。KASUMI算法是基于日本三菱公司的分组密码MISY1算法，是它的改进版本，它是一种分组加密算法。本文主要目的是研究KASUMI算法，并在VC环境下实现它。KASUMI算法的实现是在Microsoft Visual C+6.0环境下实现的，但是源代码确实利用C语言编写的，因为C语言编写的程序比C+编写的程序普遍效率要高。本系统最终完成后具有以下功能：（1）满足算法的要求，明文只能输入64位二进制位，密钥只能输入128位二进制位；但在本软件中对输入做了相应的处理，输入的时候只能输入十六进制符号，其余报错。（2）此软件只是为了验证KASUMI算法的正确性，所以在输入的时候可以随机输入，以方便快速验证。（3）为了避免加密结果的偶然性，增加了解密功能；如果解密结果与原文不符，说明加密不正确。2 KASUMI算法概述2.1 KASUMI算法的总体结构KASUMI算法是一个Feistel结构的分组加密算法，密钥长度为128比特，对一个64比特的输入分组进行八轮的迭代运算，产生长度为64比特的输出。轮函数保括一个输入输出为32比特的非线性混合函数F0和一个输入输出为32比特的线性混合函数FL。函数F0由一个输入输出为16比特的非线性混合函数FI进行3轮重复运算而构成。而函数FI是由使用非线性的S-盒S7和S9构成的4轮结构。KASUMI算法对64比特的分组应用128比特的密钥进行加密，生成64比特的输出，具体实现如下：输入数据Indata被分为32比特的左右两部分L0和R0,即Indata= L0|R0对整数i，1 =i = 8定义Ri=Li-1 Li=Ri-1 fi(Li-1,RKi)即每轮KASUMI算法的操作：将第i-1轮的输出的左半部Li-1作为第i轮的右半部Ri;而第i轮的左半部由第i-1轮输出的右半部Ri-1与第i轮的轮函数fi的输出结果进行异或运算得到。（RKi为第i轮的子密钥） 经过8轮的迭代后，得到64比特的输出（L8|R8），如图：2.1所示。2.2 KASUMI算法的组成函数2.2.1 f函数轮函数fi对32比特的输入Indata，在32比特的轮密钥RKi的控制下，得到32比特的输出。而轮密钥由三个子密钥（KLi,KOi,KIi）组成。轮函数自身由两个子 FL和FO构成，与之相关的子密钥分别为KLi(FL应用的密钥),KOi,KIi（FO应用的密钥），如图2-1所示。轮函数fi在不同的奇偶轮有不同的表达形式：对于1，3，5，7轮：fi（Indata，RKi）= FO(FL(Indata,KLi),KOi，KIi)对于2，4，6，8轮：fi（Indata，Ki）= FL(FO(Indata，KOi,KIi),KLi)这里 KOi, KIi , KLi 是子密钥，是由 key schedule产生的。keyschedule对128位密钥K进行操作，为每个周期函数生成128位的子密钥。 图2-1 f函数 图2-2 FI函数 图2-3 FL函数 图2-4 FO函数2.2.2 FI函数函数FI由16比特的输入数据I和16比特的子密钥KIi,j构成。输入数据Indata分为两个不等长的部分，9比特的L0和7比特的R0，即Indata=L0|R0。同样地密钥KIi,j也被分为7比特的KIi,j,1和9比特的KIi,j,2两部分，即KIi,j=KIi,j,1|KIi,j,2。在函数中使用了两个S-盒，S7将7比特的输入映射为7比特的输出，S9将9比特的输入映射为9比特的输出。函数中使用了两个辅助函数ZE（）和TR（）。ZE（x）表示在7比特的数据x尾部（最右边）添加2个零，将7比特转换为9比特。TR（x）表示9比特的数据x的头部（最左边）删除两个比特数据，将9比特转换为7比特。函数FI也是Feistel结构，其中每轮的操作定义如下：L1=R0， R1=S9L0 ZE（R0），L2=R1KIi,j,2, R2=S7L1 TR(R1) KIi,j,1,L3=R2, R3=S9L2 ZE(R2),L4=S7L3 TR (R3), R4=R3函数FI的输出为16比特的值（L4|R4），如图2-2所示。2.2.3 FO函数输入函数由32比特的输入数据Indata和两组分别为48比特的子密钥：KOi和KIi构成。32比特的输入数据同样被分为左右两部分，即Indata=L0|R0。48比特的子密钥被分为三组16比特的子密钥：KOi=KOi,1|KOi,2|KOi,3和KIi=KIi,1|KIi,2|KIi,3对于整数j，1=j =3Rj=FI(Lj-1 KOi,j,KIi,j) Rj-1,Lj=Rj-1最后得到函数FO的32比特的输出（L3|R3）。具体实现如图2-4所示。2.2.4 FL函数函数FL包含一个32比特的输入数据Indata和一个32比特的子密钥KLi。子密钥KLi被分为16比特的左右两个子密钥，KLi,1和KLi,2即KLi=KLi,1|KLi,2同样输入数据也被分为两个16比特的左右两部分，即Indata=L|R定义：R=RROL（LKLi,1） (ROL():循环左移1位)L=LROL (RKLi,2)共同构成函数FL的输出32比特（L | R）。具体实现见图2-3。输出的右半部R，由输入数据的左半部L与子密钥的左半部KLi,1进行按位与的运算，再进行循环左移一位，然后再与输入数据的右半部R进行异或（模2加）运算得到。输出的左半部L，由输出数据的右半部R，与子密钥的右半部KLi，2进行按位或的运算，再进行循环左移一位，然后再与输入数据的左半部L进行异或（模2加）运算得到。2.2.5 S-box两个S-boxes 既可以由组合逻辑实现，也可以通过查找表来实现。在本设计中由于考虑到加密的速度，所以才用了查表的方法来实现。S7和S9表如下：S7 = 54, 50, 62, 56, 22, 34, 94, 96, 38, 6, 63, 93, 2, 18,123, 33,55,113, 39,114, 21, 67, 65, 12, 47, 73, 46, 27, 25,111,124, 81,53, 9,121, 79, 52, 60, 58, 48,101,127, 40,120,104, 70, 71, 43,20,122, 72, 61, 23,109, 13,100, 77, 1, 16, 7, 82, 10,105, 98,117,116, 76, 11, 89,106, 0,125,118, 99, 86, 69, 30, 57,126, 87,112, 51, 17, 5, 95, 14, 90, 84, 91, 8, 35,103, 32, 97, 28, 66,102, 31, 26, 45, 75, 4, 85, 92, 37, 74, 80, 49, 68, 29,115, 44,64,107,108, 24,110, 83, 36, 78, 42, 19, 15, 41, 88,119, 59, 3;S9 = 167,239,161,379,391,334, 9,338, 38,226, 48,358,452,385, 90,397,183,253,147,331,415,340, 51,362,306,500,262, 82,216,159,356,177,175,241,489, 37,206, 17, 0,333, 44,254,378, 58,143,220, 81,400, 95, 3,315,245, 54,235,218,405,472,264,172,494,371,290,399, 76,165,197,395,121,257,480,423,212,240, 28,462,176,406,507,288,223,501,407,249,265, 89,186,221,428,164, 74,440,196,458,421,350,163,232,158,134,354, 13,250,491,142,191, 69,193,425,152,227,366,135,344,300,276,242,437,320,113,278, 11,243, 87,317, 36, 93,496, 27,487,446,482, 41, 68,156,457,131,326,403,339, 20, 39,115,442,124,475,384,508, 53,112,170,479,151,126,169, 73,268,279,321,168,364,363,292, 46,499,393,327,324, 24,456,267,157,460,488,426,309,229,439,506,208,271,349,401,434,236, 16,209,359, 52, 56,120,199,277,465,416,252,287,246, 6, 83,305,420,345,153,502, 65, 61,244,282,173,222,418, 67,386,368,261,101,476,291,195,430, 49, 79,166,330,280,383,373,128,382,408,155,495,367,388,274,107,459,417, 62,454,132,225,203,316,234, 14,301, 91,503,286,424,211,347,307,140,374, 35,103,125,427, 19,214,453,146,498,314,444,230,256,329,198,285, 50,116, 78,410, 10,205,510,171,231, 45,139,467, 29, 86,505, 32, 72, 26,342,150,313,490,431,238,411,325,149,473, 40,119,174,355,185,233,389, 71,448,273,372, 55,110,178,322, 12,469,392,369,190, 1,109,375,137,181, 88, 75,308,260,484, 98,272,370,275,412,111,336,318, 4,504,492,259,304, 77,337,435, 21,357,303,332,483, 18, 47, 85, 25,497,474,289,100,269,296,478,270,106, 31,104,433, 84,414,486,394, 96, 99,154,511,148,413,361,409,255,162,215,302,201,266,351,343,144,441,365,108,298,251, 34,182,509,138,210,335,133,311,352,328,141,396,346,123,319,450,281,429,228,443,481, 92,404,485,422,248,297, 23,213,130,466, 22,217,283, 70,294,360,419,127,312,377, 7,468,194, 2,117,295,463,258,224,447,247,187, 80,398,284,353,105,390,299,471,470,184, 57,200,348, 63,204,188, 33,451, 97, 30,310,219, 94,160,129,493, 64,179,263,102,189,207,114,402,438,477,387,122,192, 42,381, 5,145,118,180,449,293,323,136,380, 43, 66, 60,455,341,445,202,432, 8,237, 15,376,436,464, 59,461;2.3 KAUSMI算法的密钥生成KASUMI算法使用一个128比特的密钥，而在算法中的每一轮所使用的子密钥都是由这个128比特的密钥衍生而来的。每轮的密钥通过两组16比特的数组Kj和Kj,(j=1到8)以如下的方法生成：128比特的密钥被分为每组16比特的8个组：K=K1|K2|K3|K4|K5|K6|K7|K8第二组密钥Kj，由Kj以如下方法生成：Kj，=KjCj（j=1到8，Cj是表2-1所示的16进制的常量）表2-1 常量参数每轮的密钥由Kj和Kj，以表2-2所定义的规则生成。表2-2 每轮子密钥2.4 KAUSMI算法的安全性KASUMI算法是一种分组密码，目前它主要应用于第三代移动通信的安全算法f8和f9之中。f8算法是用来对UE（移动用户设备）和RNC（无线网络控制器）之间的无线链路上的用户数据和信令数据加密，以保证其安全性。UE和RNC中都有f8算法。f8是一个密钥流发生器，它通过KASUMI算法生成64比特为一组的密钥流，将明文数据流与密钥流进行异或（模2加）运算，得到密文流，解密是只要将同样的密钥流与密文流进行异或（模2加）运算，即可得到明文数据流。f9算法原理与此类似，通过KASUMI算法生成完整性消息认证码（MAC-1），对UE和RNC之间的无线链路上的信令数据进行完整性保护和信令数据来源进行认证。对信令数据（MESSAGE）使用f9算法算出完整性消息认证码（MAC-1），将其附加在MESSAGE的后面，一起在无线链路上发送到接收端。接收端也将收到的MESSAGE用f9算法进行跟发送端一样的计算，算出消息认证码（XMAC-1），将XMAC-1和收到发送端的MAC-1进行比较，验证数据的完整性。KASUMI算法是基于分组密码的设计，目前对于分组密码的设计而言，由于出现了差分和线性密码攻击，对抗这些攻击具有可证明的安全性。KASUMI算法也是基于同样的原则而设计的。它的可证明安全性是来源于算法中的被证明具有可证明安全性的较小的构成部件，Feistel结构的KASUMI算法正是通过重复迭代调用较小的函数FO和FI来保证其安全性。它的安全性来源于它的四个非线性的函数：S7，S9，FI和FO。S7和S9这两个S盒具有非线性映射特性。他们映射后的每一个输出比特依赖于输入比特，具有很好的扩散性。除了S9，只要一个输入比特改变，输出比特都会改变。只是因为S9中具有线性结构，S7满足雪崩效应，而S9不是。在3GPP在测试中没有发现函数FI和FO的线性结构，两个函数的每一个输出比特依赖于每一个输入比特，都满足雪崩效应。KASUMI算法降低到4轮已经可以满足密钥-密文，明文-密文的雪崩效应了。在3GPP组织的测评中，KASUMI算法可以对抗目前的大部分密码攻击方法：差分密码分析（差分选择明文攻击、差分相关密钥攻击、不可能差分攻击），截断差分密码分析，高阶差分密码分析，线性密码分析；而且对于使用仪器的攻击：定时攻击，简单能量攻击，差分能量攻击也具有很好的安全性，尤其是在3G的特殊环境中。3 KASUMI算法流程KASUMI算法程序的实现语言是多种多样的，如：C、C+、JAVA等等程序设计语言。本文KASUMI算法程序的实现是利用C语言来实现的，下面就简要的介绍一下算法的流程：FL函数F0函数FI函数密钥生成32位输入128位输入密钥KL密钥KI密钥KO64位输出64位输入32位输入异或F0函数FL函数异或FI函数密钥KI密钥KO密钥KL。第一轮与第二轮第三轮与第八轮图3-1 KASUMI算法流程图备注:图3-1中，第1、3、5、7轮相同，第2、4、6、8轮相同，所以只将第一轮与第二轮给出。通过上图可以清晰地看出KASUMI算法的一个总体流程，下面就详细介绍KASUMI算法的子流程图： 3.1 密钥产生KASUMI算法的密钥K的长度为128位，但是KASUMI的每一次循环都要从K中导出128位子密钥，在每一次循环中，都会产生8个子密钥，它们是：KLi,1n、KLi,2n 、KOi,1n、KOi,2n、KOi,3n、KIi,1n、KIi,2n、KIi,3n （1 = n 7);/通过移位获取16位数据的高9位seven = (u16)(indata & 0x7F); /通过移位获取16位数据的低7位nine = (u16)(S9nine seven);seven = (u16)(S7seven (nine & 0x7F);seven = seven (subkey 9);nine = nine (subkey & 0x1FF);nine = (u16)(S9nine seven);seven = (u16)(S7seven (nine & 0x7F);indata = (u16)(seven 16);/移位得到高16位right = (u16) indata;/强制转换成16位，即取低16位left = left KOi1n;left = FI( left, KIi1n );left = left right;right = right KOi2n;right = FI( right, KIi2n );right = right left;left = left KOi3n;left = FI( left, KIi3n );left = left right;indata = (u32)right) 16) + left;/移位合并return( indata );FO函数的输入由一个32位的数据输入indata和两个子密钥组成：一个48位的KO和一个48位的KI。32位的数据输入indata被分成两半，left和right，其中：indata = left | right 。并且48位的子密钥分成3个16位的子密钥，其中：KOi = KOi,1 | KOi,2 | KOi,3KIi = KIi,1 | KIi,2 | KIi,3对每一个整数j(1= j 16) ;/移位的高16位right = (u16)(indata) ; /强制转换成16位，即取低16位a = (u16) (left & KLi1n) ;right = right ROL16(a , 1) ;b = (u16)(right | KLi2n) ;left = left ROL16(b , 1) ;indata = (u32)left) 16) + right ;/移位合并return( indata );FL函数的输入由32位的数据输入indata和32位的子密钥KL组成，子密钥分为两个16位的子密钥KLi,1和KIi,2，其中，KL = KLi,1 | KLi,2。输入的数据indata被分成两个16位的部分，left和right，其中，indata = left | right 。5.4 密钥产生程序实现 void KeySchedule( u8 *k ) /常数表static u16 C = 0x0123,0x4567,0x89AB,0xCDEF, 0xFEDC,0xBA98,0x7654,0x3210 ;u16 key8, Kprime8;WUYA *k16;int n;k16 = (WUYA *)k;/循环产生数组Kjfor( n=0; n8; +n ) keyn = (u16)(k16n.b808) + (k16n.b81);/循环产生数组Kjfor( n=0; n8; +n ) Kprimen = (u16)(keyn Cn);/通过for循环产生每一轮子密钥for( n=0; n8; +n ) KLi1n = ROL16(keyn,1);KLi2n = Kprime(n+2)&0x7;KOi1n = ROL16(key(n+1)&0x7,5);KOi2n = ROL16(key(n+5)&0x7,8);KOi3n = ROL16(key(n+6)&0x7,13);KIi1n = Kprime(n+4)&0x7;KIi2n = Kprime(n+3)&0x7;KIi3n = Kprime(n+7)&0x7;5.5 f函数的程序实现(加密时的函数)void Kasumi( u8 *data )u32 left, right, temp;DWUYA *d;int n;d = (DWUYA*)data;left = (u32)d0.b80) 24) + (u32)d0.b81) 16)+ (d0.b82 8) + (d0.b83) ;right = (u32)d1.b80) 24) + (u32)d1.b81) 16)+ (d1.b82 8) + (d1.b83) ;n = 0 ;do temp = FL( left , n ) ;temp = FO( temp , n+ ) ;right = right temp ;temp = FO( right, n ) ;temp = FL( temp , n+ ) ;left = left temp ;while( n 24) ;d1.b80 = (u8)(right24);d0.b81 = (u8)(left 16) ;d1.b81 = (u8)(right 16) ;d0.b82 = (u8)(left 8) ;d1.b82 = (u8)(right 8) ;d0.b83 = (u8)(left) ;d1.b83 = (u8)(right) ;5.6 f函数的程序实现(解密时的函数)void JieMiKasumi( u8 *dataj )u32 left, right, temp;DWORD_D *d;int n;d = (DWORD_D*)dataj;right= (u32)d0.b80) 24) + (u32)d0.b81) 16) + (d0.b82 8) + (d0.b83);left = (u32)d1.b80) 24) + (u32)d1.b81) 16) + (d1.b82 8) + (d1.b83);n = 0;do temp = FO( left, (7-n);temp = FL( temp, (7-n);right = right temp;n+;temp = FL( right, (7-n);temp = FO( temp, (7-n);left = left temp;n+;while( n 24);d0.b80 = (u8)(right 24);d1.b81 = (u8)(left 16);d0.b81 = (u8)(right 16);d1.b82 = (u8)(left 8);d0.b82 = (u8)(right 8);d1.b83 = (u8)(left);d0.b83 = (u8)(right);KASUMI算法加密时的f函数与解密时的f函数从表面看似乎是相同的，但是从它的流程去分析就能看出他们的不同点。KASUMI算法是feistel结构的，对于feistel结构的加密算法，其解密时都是通过密钥与密文异或就得到了原文，但是在KASUMI算法中，在第八轮feistel结构循环后，其左右的输出再一次进行了交换，所以在解密时也要做相应的交换。首先是将输入的64位密文的高32位与低32位交换，即：现在的低32位为现在的高32位，高32位为现在的低32位。其次是在解密时应该从feistel结构的第八轮开始解密，即：与加密时的轮次相反。最后输出的结构再次进行交换，将输出的64位原文的高32位与低32位交换，即：现在的低32位为现在的高32位，高32位为现在的低32位。6 软件整体测试与系统缺陷6.1 软件测试环境配置CPU:AMD Athlon(tm) XP 2000+,1.67GHz；内存：512M