SHA-3获胜算法:Keccak评析

第２１卷第２期　北京电子科技学院学报　

２０１３年６月　

Ｖ０１．２１Ｎｏ．２　

Ｊｏｕｒｎａｌ　ｏｆ　Ｂｅｉｊｉｎｇ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｓｔｉｔｕｔｅ　

Ｊｕｎ．２０１３　

ＳＨＡ一３获胜算法：Ｋｅｃｃａｋ评析　

李梦东　邵鹏林２李小龙　

１．北京电子科技学院信息安全系　北京１０００７０　

２．西安电子科技大学通信工程学院西安７１００７０　

摘　要：２０１２年１０月初ＮＩＳＴ确定ＳＨＡ一３获胜算法为Ｋｅｃｃａｋ，为此该算法目前成为人们关注的　

焦点。本文对Ｋｅｃｃａｋ算法的实现过程、性能特点、获胜理由和攻击现状等进行了简评。通过这　

些介绍可达到初步了解Ｋｅｃｃａｋ的目的。　

关键词：Ｈａｓｈ函数；ＳＨＡ一３；ＫｅｃｃａｋＳｐｏｎｇｅ　

中图分类号－ＴＮ９１８　文献标识码：Ａ　文章编号：１６７２—４６４Ｘ（２０１３）０６一ｌ８—０６　

众所周知，由于王小云及其后继者对于ＭＤ　认证加密等功能。　

一

５、ＳＨＡ一１等标准算法的攻击，美国ＮＩＳＴ于　

以下简述了Ｋｅｃｃａｋ算法过程，分析了算法　

２００７年启动了类似１９９７年ＡＥＳ算法征集活动　

安全性能、实现性能等方面，介绍了Ｋｅｃｃａｋ的获　

的ＳＨＡ一３算法竞选。经过五年的三轮筛选过　

胜理由，并对当前针对ｋｅｃｃａｋ的攻击方法的现　

程，ＮＩＳＴ于２０１２年１０月初宣布ＳＨＡ一３竞选的　

最终获胜者是Ｋｅｃｃａｋｌ】　。ＮＩＳＴ对于Ｋｅｃｃａｋ的　

状进行了概述。　

评价是：具有良好的安全性和实现性能，特别是　

１　Ｋｅｃｃａｋ算法简述　

与ＳＨＡ一２完全不同的设计方式，可避免已有的　

攻击方式，而且能够提供ＳＨＡ一２不具备的一些　

Ｋｅｃｃａｋ整体结构为Ｓｐｏｎｇｅ结构＿２　（见图　

性能。　

１），Ｓｐｏｎｇｅ结构即是针对一个固定置换＿厂的迭代　

Ｋｅｃｃａｋ在迭代结构上采用的是Ｓｐｏｎｇｅ结　

过程。置换输入／输出的二进制串称为状态，其　

构，它与传统的ＭＤ迭代结构很不同，依赖于一　长度ｂ＝ｒ＋ｅ，其中ｒ称为比特率，与输入消息块　

个固定的大置换。这为算法提供了良好的实用　

长度相同，该部分比特称为外部状态；ｅ称为容　

性和可证明安全性，理论上可以证明该结构在理　

量，该部分比特称为内部状态。算法的初始状态　

想模型下与随机预言是不可区分的。Ｋｅｃｅａｋ的　

为全零（图１中用方形框表示）。Ｋｅｃｃａｋ规定ｂ　

置换是基于比特级的操作，实现简单，软件实现　

＝

２５・２　，Ｚ：０，１，２，…，６，因此ｂ有｛２５，５０，　

性能与ＳＨＡ一２类似，而硬件实现性能非常优　

异。整个算法具有较大的安全余量和良好的适　

１００，２００，４００，８００，１６００｝共７种规模，在提交　

应性。Ｓｐｏｎｇｅ结构可以容易地调整安全强度和　

ＳＨＡ一３的Ｋｅｃｃａｋ算法中ｂ＝１６００ｂｉｔ。Ｓｐｏｎｇｅ　

处理速度之间的平衡，很方便地产生较大和较小　

结构分为吸收（ａｂｓｔｒａｃｔｉｎｇ）和挤压（ｓｑｕｅｅｚｉｎｇ）两　

的输出值，并且可定义修改的链接模式用以提供　

个阶段。在吸收阶段，输入消息经过填充，分为　

基金项目：本项目为北京电子科技学院重点实验室项目支持。　

作者简介：李梦东，男，教授，硕士生导师，主要研究领域为密码学与纠错编码。　

第２１卷　ＳＨＡ一３获胜算法：Ｋｅｃｃａｋ评析李梦东邵鹏林李小龙　．１９．　

长度为ｒ的各块Ｐ　一，Ｐ　一，Ｐ　，每块分别与各　

次置换的输入状态的ｒ长外部状态异或，而Ｃ长　

内部状态保持不变，形成作为本次置换＿厂的输　

入。在挤压阶段，根据所需的输出长度，从各次置　

换的输出中分别提取ｚ　一，　各子串，连接后形　

成算法输出。实际上Ｓｐｏｎｇｅ结构可以产生任意　

长度的输出。　

图２　Ｋｅｃｃａｋ的状态数组表示方式　

按照ＮＩＳＴ要求，算法输出长度分为２２４、　

２５６、３８４和５１２ｂｉｔ，Ｋｅｃｃａｋ算法的消息块长度ｒ　

是根据输出长度变化的：Ｋｅｃｃａｋ一５１２时消息块　

长度ｒ为５７６ｂｉｔ；Ｋｅｃｃａｋ一３８４时ｒ为８３２ｂｉｔ；Ｋｅｃ—　

ｃａｋ一２５６时ｒ为１０８８ｂｉｔ；Ｋｅｃｃａｋ一２２４时　

为１１５２ｂｉｔ。　

Ｋｅｃｃａｋ的填充方式为：首先添加一个１，之　

后添加数个０，最后添加一个１，即填充方式为　

１０…０１，其中０的个数应使填充后的长度是消息　

分组长度的最小整数倍。　

啡　峙　嗨＊　噌童　

吸收　挤压　

籀　

图１　Ｓｐｏｎｇｅ结构　

Ｋｅｃｃａｋ算法中置换－厂的输入表示为　

５　５　２　的三维比特数组　］［Ｙ］［　］（见图　

２），称为状态数组。当ｂ＝１６００时，数组大小为　

５　５　６４（ｚ＝６）。为了方便，算法将该数组分为　

ｓｌｉｃｅ（各５　５　１ｂｉｔ）、ｐｌａｎｅ（各５：ｌ：１　２　ｚｂｉｔ）、　

ｓｈｅｅｔ（各１％５　２　ｚｂｉｔ）、ｌａｎｅ（各１％１：ｌ：２ｌｂｉｔ）、　

ｒＯＷ（各５　１　ｌｂｉｔ）和ｃｏｌｕｍｎ（各１　５：ｌ＝ｌｂｉｔ）单　

元。置换就是分别这些单元的各比特进行１２＋　

２ｚ轮迭代运算。　

置换　可视为ＳＰ结构，每一轮迭代的轮函　

数为５个变换的复合：Ｒ＝‘。　。仃。Ｐ。０，它们　

进行分别对三维数组的不同方向进行变换，以达　

到混淆和扩散的目的。这５个变换分别是：　

：ａ　Ｅｘ　３　Ｅｙ　３［　］＋－一ａ　Ｅｘｌ　Ｅｙ　３［　］＋∑：＿１００［　一　

１］Ｅｙ　］Ｅｚ３＋∑：＿＝０ｎ［　＋１］Ｅｙ　］Ｅ　一１］。这一　

变换是将每比特附近的两列（ｃｏｌｕｍｎ）比特之和　

迭加到该比特上（　和Ｙ的坐标都是模５的）；　

Ｅ　３　Ｅｙ￣Ｅｚ］卜　］Ｅｙ　Ｊ　】　

其中。　＜２４，满足（：　／／０＇／＝（　）矩阵元　

素为ＧＦ（５）中元素，且　＝Ｙ＝０时ｔ＝一１。这一　

变换是针对每个ｚ方向的ｌａｎｅ的比特循环移位；　

７ｒ：。ｃ　ｃｙ　十—。　ｙ’　，（　）＝（　）（　，），　

其中矩阵元素为ＧＦ（５）中元素。这一变换是针　

对每个　—Ｙ平面的ｓｌｉｃｅ的比特移位；　

：０［　］卜　］＋（０［　＋１］＋１）ａ　Ｅｘ＋２］这是　

针对每个　方向的ｒｏｗ的非线性运算，等效为５　

５的Ｓ盒；　

‘：０—０＋ＲＣ［ｉ，］，这一变换是加轮常数ＲＣ，逐　

比特进行，且每轮ｉ，的轮常数不同。　

２　Ｋｅｃｃａｋ性能分析　

２．１迭代结构　

Ｋｅｃｃａｋ采用的Ｓｐｏｎｇｅ结构具有可证明安全　

性和良好的适应性。与多数具有明显压缩函数　

・

２Ｏ・　北京电子科技学院学报　２０１３年　

结构的算法不同，Ｓｐｏｎｇｅ结构采用大状态的固　

定置换。在假设置换是理想的情况下，可证明该　

结构与随机预言是不可区分的（ｉｎｄｉｆｅｒｅｎｔｉａ—　

ｂｌｅ），区分复杂度的下界为２　（ｃ即容量，也称　

１０８８ｂｉｔ，以达到原象安全。在进入第三轮后　

Ｋｅｃｃａｋ简化了填充方式。　

２．４软件实现性能　

ＮＩＳＴ根据两组数据进行软件性能评测　ｊ：　

（ａ）ｅＢＡＳＨ。它是测试一般目的计算机上的实　

为安全参数）。这就保证了算法具有抵抗一般　

性攻击（即结构上的攻击）的能力。这种可证明　

性与第三轮其他几种候选算法类似，都是将算法　

安全性归结于置换或压缩函数的安全性之上。　

现性能，分别在ＡＭＤ６４、Ｘ８６、ＡＲＭ—ＮＥＯＮ、３２　

一

ｂｉｔ　ＲＩＳＣ不同类型机器上进行，并对不同级别　

的长消息和短消息进行测试，主要指标为Ｃｙｃｌｅ／　

与此同时Ｓｐｏｎｇｅ结构可以输出任意长度，适用　

能力较强。　

２．２置换　

Ｋｅｃｃａｋ的置换中运算都是比特级的运算　

（即逻辑运算），这些运算可使截断差分、积分攻　

击等不易发生，并且便于硬件实现。除了加常数　

运算　以外，其他运算都具有平移不变性即对称　

性，这使算法具有良好的适用性和实现性能。在　

安全性上，　是唯一的非线性部件，为一个可逆　

的．ｓ盒，代数次数仅为２，这将便于分析差分和　

线性特性，便于加入防护措施以防止差分能量攻　

击。但其逆．ｓ盒具有不同性质；０是为了实现　

ｓｌｉｃｅ之间的扩散性；７ｒ是为了打乱水平和垂直　

方向的规律性；加常数　是为了打破整个置换的　

对称性，保证各轮的变换不同和防止不动点。　

２．３整体安全性能　

Ｋｅｃｃａｋ具有较大的安全余量　］。碰撞和近　

似碰撞的结果最能反映杂凑算法的安全性，Ｋｅｃ　

ｃａｋ的２４轮中（当时）只发现５轮的近似碰撞。　

区分攻击能够反映算法随机性的性能，评选当时　

仅发现Ｋｅｃｃａｋ的１２轮区分器。而针对Ｋｅｃｅａｋ　

的原象攻击方面仅有很少轮数且复杂性很高的　

结果。Ｋｅｃｃａｋ用同一个置换产生所有输出长度　

的摘要输出，好处是易于实现简便变型算法，但　

是为保证安全性，消息分块要随输出长度变化，　

而且摘要越长，执行速度越慢。进入第二轮后，　

Ｋｅｃｃａｋ进行了一些修改：由轮数１２＋ｚ增至１２＋　

２ｌ；２２４ｂｉｔ输出对应的消息块长度从１０２４ｂｉｔ增　

到１１５２ｂｉｔ，２５６ｂｉｔ输出的从１０２４ｂｉｔ增到　

ｂｙｔｅ。对于长消息的测试结果为：Ｋｅｃｃａｋ一２５６　

属于中等水平，和ＳＨＡ一２类似，但比不上　

ＢＬＡＫＥ一５１２和所有尺寸的Ｓｋｅｉｎ。Ｋｅｃｃａｋ一　

５１２属于低档水平；对于短消息的测试结果：　

Ｋｅｃｃａｋ一２５６和Ｋｅｃｃａｋ一５１２基本都属于中等水　

平；（ｂ）ＸＢＸ。它是测试嵌人式微处理器上的性　

能，包含了８种平台，测试指标同时考虑使用面　

积（ＲＡＭ和ＲＯＭ的个数）和速度性能，结果为：　

Ｋｅｃｃａｋ一２５６为中上等（ＢＬＡＫＥ最好，Ｓｋｅｉｎ其　

次），但Ｋｅｃｃａｋ一５１２属于下等。不过由于Ｋｅｃ．　

ｃａｋ算法特点，可以利用未来将普遍采用的矢量　

旋转指令（ｖｅｃｔｏｒ　ｒｏｔａｔｅ　ｉｎｓｔｒｕｃｔｉｏｎｓ）来提高Ｋｅｃ．　

ｃａｋ一５１２的速度。　

２．５硬件实现性能　

ＮＩＳＴ采用了ＡＳＩＣ和ＦＰＧＡ两种测试平　

台　，测试指标主要为ｔｈｒｏｕｇｈｏｕｔ／ａｒｅａ。测试结　

果表明：Ｋｅｃｃａｋ是五个第三轮候选算法中唯一　

一

个超过ＳＨＡ一２的，这表明它的硬件性能很　

好，而且能量损耗最小，具有和ＳＨＡ一２相同的　

每比特能量消耗量。　

２．６应用方面　

Ｋｅｃｃａｋ可以方便地实现ＭＡＣ；可以作为流　

密码使用，输出长度可灵活变化　；其ｄｕｐｌｅｘｉｎｇ　

模式，可以实现伪随机数发生器和认证加密。　

３　ＮＩＳＴ选择Ｋｅｃｃａｋ的理由　

３．１　Ｋｅｃｃａｋ具有较大的安全余量　

这意味着出现实际有效的攻击的可能性很　

小。在第三轮的五个候选算法中，关于Ｇｒｏｅｓｔｌ、　

第２１卷　ＳＨＡ一３获胜算法：Ｋｅｃｃａｋ评析李梦东邵鹏林李小龙　．２１．　

ＢＬＡＫＥ和Ｓｋｅｉｎ的攻击文章最多，这一方面说　

明：可能由于Ｇｒｏｅｓｔｌ采用ＡＥＳ部件，ＢＬＡＫＥ和　

ＮＩＳＴ接受，如此则可进一步提高Ｋｅｃｃａｋ的适用　

性。另外Ｋｅｃｃａｋ认证加密模式是一个较好的附　

加性能，这是Ｓｐｏｎｇｅ构造的非常自然的扩展。　Ｓｋｅｉｎ采用ＳＨＡ一２类似的ＡＲＸ部件，研究者易　

于分析；另一方面也说明对于这些算法的研究比　

较深入。而针对Ｋｅｃｃａｋ的分析文章相对较少，　

关于ＪＨ的最少　。截止到目前的分析表明：　

４　Ｋｅｃｃａｋ的攻击现状　

当Ｋｅｃｃａｋ成为ＳＨＡ一３获胜者之后，必然　

会引起更多的关注和分析。目前关于Ｋｅｃｃａｋ的　

ＢＬＡＫＥ、Ｋｅｃｃａｋ和Ｓｋｅｉｎ的安全余量较大，而　

Ｇｒｏｅｓｔｌ和ＪＨ相对而言安全余量较少（已出现全　

攻击方式主要有：利用差分技术的碰撞攻击和部　

轮ＪＨ和９０％轮Ｇｒｏｅｓｔｌ的区分攻击）。　

虽然与ＢＬＡＫＥ、Ｇｒｏｅｓｔｌ和Ｓｋｅｉｎ相比，Ｋｅｃ．　

ｃａｋ的分析还不够深入，但它也接受了一定量的　

分析。Ｋｅｃｃａｋ基本上是个全新的和与以往非常　

不一样的算法，与ＳＨＡ一２完全无关。而　

ＢＬＡＫＥ和Ｓｋｅｉｎ的部件使用与ＳＨＡ一２类似的　

ＡＲＸ运算，因此人们怀疑ＳＨＡ一２的分析工具　

将来很可能用于它们。而Ｋｅｃｃａｋ的新颖结构和　

运算则不存在这样的隐患。（但仍需要对其新　

颖结构和比特级运算进行深入分析。）　

３．２　Ｋｅｃｃａｋ具有可接受的软件性能和优异的硬　

件性能　

Ｋｅｃｃａｋ面向硬件的设计，完全基于简单的　

比特级运算和扩散，使其具有良好的性能和实现　

效率。Ｋｅｃｃａｋ的软件性能大致与ＳＨＡ～２相仿，　

在第三轮五个候选算法中属于中上等水平，但其　

硬件性能则是最优秀的，比ＳＨＡ一２好很多，不　

需要ＳＨＡ一２所需的３２ｂｉｔ或者６４ｂｉｔ加法或者　

密钥扩展过程。而且Ｋｅｃｃａｋ提供了良好的性能　

权衡能力，可视情况在安全性、实现性能和简便　

变型等方面进行取舍。　

３．３　Ｋｅｃｃａｋ的适应能力强　

Ｋｅｃｃａｋ成为获胜者，得益于它的十分简单　

轻巧的设计，和可用于广泛环境的适应能力。　

Ｓｐｏｎｇｅ扩展方式使之易于分析为提高性能而改　

变消息分组长度所产生的对安全性影响问题，可　

以扩展输出长度以适用于诸如ＲＳＡ全域杂凑函　

数等场合。Ｋｅｃｃａｋ也可以提供８００比特置换，　

若从安全角度再进行深入研究的话，则可被　

分碰撞攻击；利用Ｂｉｃｌｉｑｕｅ等技术的原象或第二　

原象攻击；零和区分攻击和旋转区分攻击等。　

ｄ．１碰撞和近似碰撞攻击　

Ｉ．Ｄｉｎｕｒ等　从已有的２轮低重量的状态差　

分开始，反向扩展１轮产生目标状态差分，再由　

目标差分算法从初始值开始进行正向１轮扩展，　

产生了４轮Ｋｅｃｃａｋ一２２４实际碰撞，在ＰＣ机上　

仅用时２—３分钟，产生４轮的Ｋｅｃｃａｋ一２５６实　

际碰撞用时１５—３０分钟；产生５轮的近似碰撞　

（只差５、１０ｂｉｔ）耗时几天时间。２０１３年，Ｉ．Ｄｉｎｕｒ　

等　又采用目标内部差分算法提高了上述结　

果，对５轮的Ｋｅｃｃａｋ一２５６产生了碰撞攻击，复　

杂度为２“　。并结合ｓｑｕｅｅｚｅ攻击产生了３轮的　

Ｋｅｃｃａｋ一５１２实际性攻击，产生了４轮Ｋｅｃｃａｋ一　

３８４的碰撞，复杂度为２Ｍ　。　

Ｊ．Ｄａｅｍｅｎ等　提出了有效产生给定重量的　

Ｋｅｃｃａｋ—ｆ［１６００］的所有差分路径的方法。利用　

计算机程序搜索得到了重量为３６时３轮的所有　

差分轨迹，确认了Ａ．Ｄｕｃ等＿　ｌ找到的重量为３２　

的３轮轨迹是最轻的；指出６轮的轨迹中重量没　

有小于７４的。提出了一种新技术将变换的性　

质和差分轨迹重量相关连，在为恒等映射时，采　

用有效的状态表示方法，构建了ｉｎ—ｋｅｒｎｅｌ　

轨迹。　

４．２原象攻击　

Ｎａｙａ—Ｐｌａｓｅｎｃｉａ等　采用中间相遇的方法，　

提出了２轮Ｋｅｃｃａｋ一２２４和Ｋｅｃｃａｋ一２５６的原　

象和第二原象攻击，时间复杂度为２”，存储复杂　

度为２扣。这是一种可以实际实现的攻击。　

・

２２・　北京电子科技学院学报　

４．３区分攻击（随机性攻击）　

Ｃ．Ｂｏｕｒａ等　采用零和子集划分的方式对　

Ｋｅｃｃａｋ进行了区分攻击。零和攻击可以看作积　

体的算法规格说明等内容将随后公布。　

Ｋｅｃｃａｋ作为ＳＨＡ一３的获胜者，已经引起人　

们更广泛的关注，对它的分析日益增多。Ｋｅｃｃａｋ　

基于比特级的置换将会受到更为深入地研究，将　

与基于ＡＲＸ、基于字节型Ｓ盒的置换进行充分　

分攻击的推广，即是利用输入和输出的和为零的　

子集进行区分攻击。他们针对Ｋｅｃｃａｋ的１７轮、　

１９轮和２０轮置换产生了零和划分，尺寸（复杂　

度）分别为２”　、２¨　和２　。在［１Ｏ］中他们又　

比较。Ｓｐｏｎｇｅ结构的特点和进一步应用也会受　

到同样关注。　

提出了针对全轮Ｋｅｃｃａｋ置换的零和划分，复杂　

度为２幅　。可以看到这种攻击的复杂性是很　

大的。　

Ａ．Ｄｕｃ等　找到了Ｋｅｃｃａｋ目前最好的（重　

量最轻的）５轮差分路径，针对０变换的零核特　

性，利用ｕｎａｌｉｇｎｅｄｒｅｂｏｕｎｄ技术，构造了８轮区分　

器，复杂度为２　钾。这比零和区分器的复杂度　

小很多。这里所谓“ｕｎａｌｉｇｎｅｄ”是指：Ｋｅｃｃａｋ不　

像存在截断差分的ＡＥＳ那样容易处理ｒｅｂｏｕｎｄ　

过程，因为其１个活跃行经过１轮后会影响多个　

ｓｌｉｃｅ。　

Ｐ．Ｍｏｒａｗｉｅｃｋｉ等＿】　采用旋转攻击方法，提　

出了５轮Ｋｅｃｃａｋ的区分攻击，复杂度仅为２　，　

但是对于更多轮数则遇到了较大困难。另外，这　

一

攻击方式与其他区分攻击不同之处在于：可以　

产生４轮原象攻击，复杂度为理论值减少２　倍。　

５结束语　

ＮＩＳＴ的ＳＨＡ一３征集活动是杂凑函数研究　

的一件大事，类似当年ＡＥＳ征集活动，它有力促　

进了整个领域的设计和分析水平。　

进入第三轮的五个算法都是很优秀的算法，　

具有各自的优势和特点，例如ＢＬＡＫＥ和Ｓｋｅｉｎ　

的安全余量也较大，其软件实现性能是这些算法　

中最为突出的。ＮＩＳＴ综合考虑了算法的各方面　

因素，最终选定了Ｋｅｃｃａｋ作为ＳＨＡ一３标准。　

Ｋｅｃｃａｋ能够获胜，不仅是由于其安全性能良好，　

更重要的是因为其新颖的结构设计、优秀的整体　

实现性能和良好的适应能力。作为ＳＨＡ一３的　

最终标准，ＮＩＳＴ允许其进行一些微小改动，其具　

参考文献：　

［１］Ｇ．Ｂｅｒｔｏｎｉ，ｅｔ　ａｌ，Ｔｈｅ　Ｋｅｃｃａｋ　Ｒｅｆｅｒｅｎｃｅ，Ｊａｎｕａｒ－　

Ｙ，２０１　１，ｈｔｔｐ：／／Ｋｅｃｃａｋ．ｎｏｅｋｅｏｎ．ｏｒｇ．　

［２］Ｇ．Ｂｅｒｔｏｎｉ，Ｊ．Ｄａｅｍｅｎ　ｅｔ　ａｌ，Ｃｒｙｐｔｏｇｒａｐｈｉｃ　

ｓｐｏｎｇｅ　ｆｕｎｃｔｉｏｎｓ，Ｊａｎｕａｒｙ，２０１１，ｈｔｔｐ：／／　

ｓｐｏｎｇｅ．ｎｏｅｋｅｏｎ．ｏｒｇ／．　

［３］Ｓｈｕ—ｊｅｎ　Ｃｈａｎｇ，ｅｔ　ａｌ，Ｔｈｉｒｄ—Ｒｏｕｎｄ　Ｒｅｐｏａ　ｏｆ　

ｔｈｅ　ＳＨＡ——３　Ｃｒｙｐｔｏｇｒａｐｈｉｃ　Ｈａｓｈ　Ａｌｇｏｒｉｔｈｍ　Ｃｏｍ－－　

ｐｅｔｉｔｉｏｎ，Ｎｏｖｅｍｂｅｒ，２０１２，ｈｔｔｐ：／／ｄｘ．ｄｏｉ．ｏｒｇ／　

１０．６０２８／ＮＩＳＴ．ＩＲ．７８９６．　

［４］Ｉ．Ｄｉｎｕｒ，Ｏ．Ｄｕｎｋｅｌｍａｎ　ａｎｄ　Ａ．Ｓｈａｍｉｒ，Ｎｅｗ　ａｔ—　

ｔａｃｋｓ　ｏｎ　Ｋｅｃｃａｋ一２２４　ａｎｄ　Ｋｅｃｃａｋ一２５６，ＦＳＥ’　

２０１２，２０１２．　

［５］Ｉ．Ｄｉｎｕｒ，Ｏ．Ｄｕｎｋｅｌｍａｎ　ａｎｄ　Ａ．Ｓｈａｍｉｒ，Ｃｏｌｌｉｓｉｏｎ　

Ａｔｔａｃｋｓ　ｏｎ　Ｕｐ　ｔｏ　５　Ｒｏｕｎｄｓ　ｏｆ　ＳＨＡ——３Ｕｓｉｎｇ　Ｇｅｎ—－　

ｅｒａｌｉｚｅｄ　Ｉｎｔｅｍａ１　Ｄｉｆｆｅｒｅｎｔｉａｌｓ，ＦＳＥ’２０１３，２０１３．　

［６］Ａ．Ｄｕｃ，Ｊ．Ｇｕｏ，Ｔ．Ｐｅｙｒｎ　ａｎｄ　Ｌ．Ｗｅｉ，Ｕｎａｌｉｇｎｅｄ　

Ｒｅｂｏｕｎｄ　Ａｔｔａｃｋ：Ａｐｐｌｉｃａｔｉｏｎ　ｔｏ　Ｋｅｃｃａｋ，ＦＳＥ’　

２０１２，２０１２．　

［７］Ｊ．Ｄａｅｍｅｎ　ａｎｄ　Ｇ　Ｖａｎ　Ａｓｓｃｈｅ，Ｄｉｆｆｅｒｅｎｔｉａｌ　Ｐｒｏｐａ—　

ｇａｔｉｏｎ　ａｎａｌｙｓｉｓ　ｏｆ　Ｋｅｃａａｋ，ＦＳＥ’２０１２，２０１２．　

［８］Ｍ．Ｎａｙａ—Ｐｌａｓｅｎｃｉａ，Ａ．Ｒｅｏｃｋ，ａｎｄ　Ｗ．Ｍｅｉｅｒ，　

Ｐｒａｃｔｉｃａｌ　Ａｎａｌｙｓｉｓ　ｏｆ　Ｒｅｄｕｃｅｄ—Ｒｏｕｎｄ　Ｋｅｃｃａｋ，　

ＩＮＤＯＣＲＹＰＴ　２０１１，２０１１．　

［９］Ｃ．Ｂｏｕｒａ　ａｎｄ　Ａ．Ｃａｎｔｅａｕｔ，Ｚｅｒｏ—Ｓｕｍ　Ｄｉｓｔｉｎ－　

ｇｕｉｓｈｅｒｓ　ｆｏｒ　Ｉｔｅｒａｔｅｄ　Ｐｅｒｍｕｔａｔｉｏｎｓ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ　

ｔｏ　Ｋｅｃｃａｋ—ｆ　ａｎｄ　Ｈａｍｓｉ一２５６，ＳＡＣ’　

２０１０，２０１０．　

［１０］Ｃ．Ｂｏｕｒａ，Ａ．Ｃａｎｔｅａｕｔ　ａｎｄ　Ｃ．Ｄｅ　Ｃａｎｎｉｅｒｅ，　

第２１卷　ＳＨＡ一３获胜算法：Ｋｅｃｃａｋ评析李梦东邵鹏林李小龙　・２３・　

Ｈｉｇｈｅｒ—ｏｒｄｅｒ　ｄｉｆｆｅｒｅｎｔｉａｌ　ｐｒｏｐｅｒｔｉｅｓ　ｏｆ　Ｋｅｃｃａｋ　ｔａｔｉｏｎａｌ　ｃｒｙｐｔａｎａｌｙｓｉｓ　ｏｆ　ｒｏｕｎｄ—ｒｅｄ

ｕｃｅｄ　Ｋｅｃ—　

ａｎｄ　Ｌｕｆｆａ，ＦＳＥ’２０１１，２０１１　ｃａｋ，ＦＳＥ’２０１３，２０１３　

［１　１］Ｐ．Ｍｏｒａｗｉｅｃｋｉ，Ｊ．Ｐｉｅｐｒｚｙｋａｎｄ　Ｍ．Ｓｒｅｂｒｎｙ，Ｒｏ—　

Ａ　Ｓｈｏｒｔ　Ｒｅｖｉｅｗ　

ｏｎ　ＳＨＡ一３　Ｗｉｎｎｅｒ：Ｋｅｃｃａｋ　

Ｌｉ　Ｍｅｎｇｄｏｎｇ　

Ｓｈａｏ　Ｐｅｎｇｌｉｎ。Ｌｉ　Ｘｉａｏｌｏｎｇ　

１．Ｄｅｐａｒｔｍｅｎｔ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｅｃｕｒｉｔｙ，Ｂｅｉｊｉｎｇ　Ｅｌｅｃｔｒｏｎｉｃ　Ｓｃｉｅｎｃｅ　ａｎｄ　

Ｔｅｃｈｎｏｌｏｇｙ　Ｉｎｓｔｉｔｕｔｅ，Ｂｅｉｊｉｎｇ　１０００７０，Ｃｈｉｎａ；　

２．Ｓｃｈｏｏｌ　ｏｆ　Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｘｉｄｉａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉａｎ，７１００７１，Ｃｈｉｎａ　

Ａｂｓｔｒａｃｔ：Ａｂｓｔｒａｃｔ：Ｓｉｎｃｅ　ＮＩＳＴ　ｃｌａｉｍｅｄ　Ｋｅｃｃａｋ　ｗａｓ　ｔｈｅ　ｗｉｎｎｅｒ　ｏｆ　ＳＨＡ一３　Ｃｏｍｐｅｔｉｔｉｏｎ　ｏｎ　Ｏｃｔｏｂｅｒ　

２，　

２０１２；ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ　ｈａｓ　ｂｅｃｏｍｅ　ｔｈｅ　ｆｏｃｕｓ　ｏｆ　ａｔｔｅｎｔｉｏｎｓ．Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ　ａ　ｂｒｉｅｆ　ｄｉｓｃｕｓｓｉｏｎ　ｉｓ　ｇｉｖｅｎ　ｏｎ　

ｔｈｅ　

ａｌｇｏｒｉｔｈｍｉｃ　ｐｒｏｃｅｄｕｒｅｓ，ｐｒｏｐｅｒｔｉｅｓ，ｗｉｎｎｉｎｇ　ａｄｖａｎｔａｇｅｓ　ａｎｄ　ｓｅｃｕｒｉｔｙ　ｓｔａｔｕｓ　ａｂｏｕｔ　Ｋｅｃｃａｋ．Ｔｈｒｏｕｇｈ　ｔｈｅ　

ａｎａｌｙｓｉｓ，ｗｅ　ｃａｎ　ｈａｖｅ　ａ　ｂｅｔｔｅｒ　ｕｎｄｅｒｓｔａｎｄｉｎｇ　ｏｆ　Ｋｅｃｃａｋ．　

Ｋｅｙｗｏｒｄｓ：Ｈａｓｈ　Ｆｕｎｃｔｉｏｎ；ＳＨＡ一３；Ｋｅｃｃａｋ；Ｓｐｏｎｇｅ　

（责任编辑：王曼珠）