一种新的实用安全加密标准算法——Camellia算法

一种新的实用安全加密标准算法——Camellia算法摘要介绍了ＮＥＳＳＩＥ标准中的分组密码算法——Ｃａｍｅｌｌｉａ算法的加、解密过程，并对其在各种软、硬件平台上的性能进行了比较，结果表明Ｃａｍｅｌｌｉａ算法在各种平台上均有着较高的效率。Ｃａｍｅｌｌｉａ算法与其它技术相结合将在信息安全领域产生更广泛的应用。关键词ＮＥＳＳＩＥ分组密码算法加密继２０００年１０月美国推出二十一世纪高级数据加密标准ＡＥＳ后，２００３年２月欧洲最新一代的安全标准ＮＥＳＳＩＥＮｅｗＥｕｒｏｐｅａｎＳｃｈｅｍｅｓｆｏｒＳｉｇｎａｔｕｒｅｓ、ＩｎｔｅｇｒｉｔｙａｎｄＥｎｃｒｙｐｔｉｏｎ出台。ＮＥＳＳＩＥ是欧洲ＩＳＴＩｎｆｏｒｍａｔｉｏｎＳｏｃｉｅｔｙＴｅｃｈｎｏｌｏｇｉｅｓ委员会计划的一个项目。Ｃａｍｅｌｌｉａ算法以其在各种软件和硬件平台上的高效率这一显著特点成为ＮＥＳＳＩＥ标准中两个１２８比特分组密码算法之一另一个为美国的ＡＥＳ算法。Ｃａｍｅｌｌｉａ算法由ＮＴＴ和ＭｉｔｓｕｂｉｓｈｉＥｌｅｃｔｒｉｃＣｏｒｐｏｒａｔｉｏｎ联合开发。作为欧洲新一代的加密标准，它具有较强的安全性，能够抵抗差分和线性密码分析等已知的攻击。与ＡＥＳ算法相比，Ｃａｍｅｌｌｉａ算法在各种软硬件平台上表现出与之相当的加密速度。除了在各种软件和硬件平台上的高效性这一显著特点，它的另外一个特点是针对小规模硬件平台的设计。整个算法的硬件执行过程包括加密、解密和密钥扩展三部分，只需占用８．１２Ｋ０．１８μｍＣＯＭＳ工艺ＡＳＩＣ的库门逻辑。这在现有１２８比特分组密码中是最小的。１Ｃａｍｅｌｌｉａ算法的组成Ｃａｍｅｌｌｉａ算法支持１２８比特的分组长度，１２８、１９２和２５６比特的密钥与ＡＥＳ的接口相同。本文以１２８比特密钥为例对Ｃａｍｅｌｌｉａ算法进行详细介绍。Ｃａｍｅｌｌｉａ算法１２８比特密钥的加、解密过程共有１８轮，采用Ｆｅｉｓｔｅｌ结构，加、解密过程完全相同，只是子密钥注入顺序相反。而且密钥扩展过程和加、解密过程使用相同的部件。这使得Ｃａｍｅｌｌｉａ算法不论是在软件平台还是硬件平台只需更小的规模和更小的存储即可。１Ｃａｍｅｌｌｉａ算法所采用的符号列表及其含义Ｂ８比特向量Ｗ３２比特向量Ｌ６４比特向量Ｑ１２８比特向量ｘｎ比特向量ｘＬ向量ｘ的左半部分ｘＲ向量ｘ的右半部分＜＜＜比特循环左移｜｜两个操作数的连接比特的异或操作ｘ比特位取补操作∪比特位的或操作∩比特位的与操作２Ｃａｍｅｌｌｉａ算法所采用的变量列表及其含义Ｍ１２８１２８比特明文组Ｃ１２８１２８比特密文组Ｋ主密钥ｋｗｔ６４ｋｕ６４ｋｌｖ６４子密钥３Ｃａｍｅｌｌｉａ算法所采用的变换函数·Ｆ变换Ｆ变换见式１是Ｃａｍｅｌｌｉａ算法中最主要的部件之一，而且Ｆ变换被加、解密过程和密钥扩展过程所共用１２８比特密钥的加、解密各用１８次，密钥扩展用４次。Ｃａｍｅｌｌｉａ算法的Ｆ变换在设计时采用１轮的ＳＰＮＳｕｂｓｔｉｔｕｔｉｏｎＰｅｒｍｕｔａｔｉｏｎＮｅｔｗｏｒｋ，包括一个Ｐ变换线性和一个Ｓ变换非线性。在Ｆｅｉｓｔｅｌ型密码使用一轮ＳＰＮ作轮函数时，对更高阶的差分和线性特性概率的理论评估变得更加复杂，在相同安全水平下的运行速度有所提高。范文先生网收集整理·Ｐ变换Ｃａｍｅｌｌｉａ算法的Ｐ变换见式２是一个线性变换。为了通信中软、硬件实现的高效性，它适合采用异或运算，并且其安全性能足以抵抗差分和线性密码分析。其在３２位处理器、高端智能卡上的应用，跟在８位处理器上一样。·Ｓ变换Ｃａｍｅｌｌｉａ算法采用的Ｓ盒见式３是一个ＧＦ２８上的可逆变换，它加强了算法的安全性并且适用于小硬件设计。众所周知，ＧＦ２８上函数的最大差分概率的最小值被证明为２－６，最大线性概率的最小值推测为２－６。Ｃａｍｅｌｌｉａ算法选择ＧＦ２８上能够获得最好的差分和线性概率的可逆函数作Ｓ盒，而且Ｓ盒每个输出比特具有高阶布尔多项式，使得对Ｃａｍｅｌｌｉａ进行高阶差分攻击是困难的。Ｓ盒在ＧＦ２８上输入、输出相关函数上的复杂表达式，使得插入攻击对Ｃａｍｅｌｌｉａ无效。ＳＬ→Ｌ18,18,18,18,18,18,18,18→*118,228,338,448,258,368,478,1888其中，ｓ２ｙ８＝ｓ18=05+8+06２８＝ｓ2ｘ８=18＜＜＜１３ｓ３ｙ８＝ｓ３ｘ８＝ｓ１ｘ８＞＞＞１ｓ４ｙ８＝ｓ４ｘ８＝ｓ１ｘ８＜＜＜１算法中构造了四个不同的Ｓ盒，提高了Ｃａｍｅｌｌｉａ算法抵抗阶段差分攻击的安全性。为了在小硬件上设计实现，ＧＦ２８上的元素可以表示成系数为ＧＦ２４上的多项式。这样，在实现Ｓ盒时，只需运用子域ＧＦ２４上很少的操作。ｓ１变换中所采用的ｆ、ｈ、ｇ函数分别如４、５、６式所示。ｂ１,ｂ２,ｂ３,ｂ４,ｂ５,ｂ６,ｂ７,ｂ８＝ｇａ１,ａ２,ａ３,ａ４,ａ５,ａ６,ａ７,ａ８其中,ｂ８＋ｂ７α＋ｂ６α２＋ｂ５α３＋ｂ４＋ｂ３α＋ｂ２α２＋ｂ１α３β＝１／ａ８＋ａ７α＋ａ６α２＋ａ５α３＋ａ４＋ａ３α＋ａ２α２＋ａ１α３６规定６式中ＧＦ２的８次方上运算＝1０，β是ＧＦ２的８次方上方程ｘ８＋ｘ６＋ｘ５＋ｘ３＋１＝０的根，ａ＝β２３８＝β６＋β５＋β３＋β２是ＧＦ２的４次方上方程ｘ４＋ｘ＋１＝０的根。当然根据性能要求，在具体实现加密算法时，Ｓ盒的实现电路也可以直接查表的方式进行。·ＦＬ／ＦＬ－１变换Ｃａｍｅｌｌｉａ算法每六圈加入一次ＦＬ／ＦＬ－１变换，用来打乱整个算法的规律性。加入ＦＬ／ＦＬ－１变换的另一个好处是可以抵抗未知的密码攻击方法，而且加入ＦＬ／ＦＬ－１变换并不影响Ｆｅｉｓｔｅｌ结构加、解密过程相同。ＦＬＬ×Ｌ→ＬＸＬ３２｜｜ＸＲ３２，ｋｌＬ３２｜｜ｋｌＲ３２７ＹＲ３２∪ｋｌＲ３２，ＹＬ３２｜｜ＸＬ３２∩ｋｌＬ３＜＜＜１+ＹＲ３２ＦＬ－１Ｌ×Ｌ→ＬＹＬ３２｜｜ＹＲ３２，ｋｌＬ３２｜｜ｋｌＲ３２８ＹＲ３２∪ｋｌＲ３２，ＹＬ３２｜｜ＸＬ３２∩ｋｌＬ３２＜＜＜１+ＹＲ３２２Ｃａｍｅｌｌｉａ算法的加、解密及密钥扩展实现过程１加、解密过程Ｃａｍｅｌｌｉａ算法的整个加密过程有１８轮Ｆｅｉｓｔｅｌ结构，在第６轮和第１２轮之后加入了ＦＬ／ＦＬ－１变换层，用来打乱算法的规律性，并且在第１轮之前和最后１轮之后使用了１２８比特的异或操作。解密过程与加密过程完全相同，只是圈密钥注入顺序与加密相反。１２８比特密钥Ｃａｍｅｌｌｉａ算法的加密过程如图１所示。２密钥扩展Ｃａｍｅｌｌｉａ算法的密钥扩展遵循了严格的设计准则，如实现简单且与加、解密过程共用部件，密钥配置时间小于加密时间，支持在线密钥生成，没有等效密钥，能够抵抗相关密钥攻击和滑动攻击等。整个过程只需通过三个中间变量，ＫＬ１２８＝Ｋ１２８，Ｋ１２８＝０ＫＡ的简单移位即可得到子密钥ｋｗｔ６４ｔ＝１，…，４，ｋｕ６４ｕ＝１，…，１８和ｋｌｖ６４ｖ＝１，…，４，且中间生成过程与加密过程共用了部件Ｆ如图１、２所示。３Ｃａｍｅｌｌｉａ算法的安全性设计者用差分扩散概率和线性相关概率的保守上界证明了任何含ＳＰＮ网络的十六圈Ｃａｍｅｌｌｉａ密码对差分密码分析和线性密码分析都是安全的；此外，通过对活动Ｓ盒的计数说明十二圈Ｃａｍｅｌｌｉａ中没有概率大于２－１２８的差分特征和线性特征；带或不带ＦＬ层的十圈Ｃａｍｅｌｌｉａ都具有伪随机置换特性，能够抵抗截断差分攻击和线性密码分析；设计者还声称Ｃａｍｅｌｌｉａ能够抵抗不可能差分攻击、Ｂｏｏｍｅｒａｎｇ攻击、高阶差分攻击、相关密钥攻击、插入攻击、Ｓｌｉｄｅ攻击、线性和攻击及Ｓｑｕａｒｅ攻击。在密钥的安全性上，一方面不存在等效密钥；另一方面，子密钥来自主密钥的加密结果ＫＡ和ＫＢ，改变主密钥并不能获得预想的ＫＡ和ＫＢ，反之亦然，因而无法控制和预测子密钥之间的关系，从而相关密钥攻击难以成功。由于密钥长度不少于１２８比特，以当前的计算能力还无法对Ｃａｍｅｌｌｉａ成功实施诸如密钥穷举搜索攻击、时间存储权衡攻击、字典攻击和密钥匹配等类型的强力攻击。４Ｃａｍｅｌｌｉａ算法在各种平台上的性能比较评测一个分组密码的好坏，除了要求其具有高的安全性外，还要求算法在应用平台上实现简单。Ｃａｍｅｌｌｉａ算法在设计时充分考虑到了这一点，下面给出其在各种平台上的性能参数。评测算法在软件平台上实现性能时，首要考虑其速度，其次还要看算法实现时所需的存储空间，表１前半部分给出了Ｃａｍｅｌｌｉａ算法在常用的３２位处理器上各种软件平台的实现性能。高的加密速度和低的存储需求，表明Ｃａｍｅｌｌｉａ算法可以有效地应用于各种软件系统中。从表１后半部分可以看出Ｃａｍｅｌｌｉａ算法在高端和低端的智能卡平台上同样有着良好的性能；由于Ｃａｍｅｌｌｉａ算法的密钥扩展与加、解密过程有共用部分，所以其硬件平台所需的芯片面积大大减少，降低了硬件成本，便于推广应用，详细参数见表２。表1算法在软件和智能卡平台上的性能环境语言速度加、解密合计合计7001282562-241564114203001605122-++6666108946115122562-1614\\805112102171022329908053595171910616986870516219900471208\表2算法在硬件平台上的性能环境设计速度芯片面积加、解密单元合计018μ27850024490018μ1881254430401899426227421780从本文可以看出，分组密码加密算法发展到今天，不论是从安全性还是从实用性的角度都越来越强。ＮＥＳＳＩＥ标准中的Ｃａｍｅｌｌｉａ加密算法充分考虑到了各种因素，既保证了算法的安全性又考虑到其在各种平台上的实现效率，尤其是针对小硬件的设计思想，使其有着广泛的应用前景。