Sha3算法.docx

1、Sha3算法全新的 SHA-3 加密标准 Keccak 英文原文：Keccak: The New SHA-3 Encryption Standard 经过多年的测试和分析，美国政府选择了Keccak算法作为SHA - 3的加密标准，现在我们分析一下它的工作原理以及使用方法。 2012年10月，美国NIST选择了Keccak算法作为SHA - 3的标准算法，Keccak拥有良好的加密性能以及抗解密能力。在本篇文章中，我将简单的阐述Keccak的工作原理，我将分析它的核心代码并告诉你它是如何对一段文本进行哈希处理的。我将其与SHA-1 和 SHA-2进行比较测试。 读者应该有C和Objective

2、-C的编程经验，然后对加密算法基本认知。 正在加载.SHA-1 和 SHA-2 的限制不容忽视的是，SHA-1和SHA-2使用了相同的处理引擎。Merkle-Damgard称，在处理消息文本时，对SHA-1的成功攻击行为会影响到SHA-2的安全。 在SHA-1上举个例子：理论上进行暴力破解至少需要2的80次方（哈希循环的一个周期）才能碰撞破解。但是在2005年2月，王晓云（音译）以及他的同事使用差分路径攻击，只用了2的69次方次就完成了SHA-1的循环碰撞周期，2008年8月，这一方法被Martin Cochran证实。 到了2012年。Mark Stevens使用了一系列的云服务器在执行SH

3、A-1的差分路径攻击，在2的58.5次方次就完成了一次攻击碰撞，他估计，在经过2的61次方次循环后，就可以形成一个完整的哈希碰撞密码库 至于SHA-2, 对有限轮回的SHA-2散列的攻击是唯一成功的一类。对46轮回的SHA-2(512位的变体)和41轮回的SHA-2（512位的变体）的攻击是最有效的。破解256位的变体要花费 2253.6次循环，破解512位的变体要花费2511.5次循环。 事实上,即使还没有宣布一个全轮回的SHA-2被成功攻破， 但毫无疑问，攻击机制正私下的发展。这也是NIST赞助SHA-3竞赛的一个原因，也引起Keccak的发展和近来的采纳。 SHA-3的筛选 筛选SHA-

4、3标准，候选人散列函数必须满足四个由NIST设置的条件。如果一个候选算法未能满足这些条件，它将被淘汰: 候选散列函数必须好实现。它应该消耗最少的资源即使散列大量的消息文本。许多候选算法实际上是无法达到这个要求。 候选算法必须保守安全。它应该抵御已知的攻击，同时保持一个大的安全系数。它应该同SHA-2相同的四个散列大小(224bit、256bit、384bit或512bit)，但如果需要能够支持更长的散列位宽。 候选算法必须接受密码分析。源代码和分析结果公开为感兴趣的第三方审查和评论。在分析过程中发现的任何缺陷都需要解决，通过调整或通过重新设计。 候选算法必须使代码多样性。它不能使用Merkle

5、-Damgard引擎产生消息散列。 这个SHA-3竞争看到51个候选算法进入第一轮评估。这当中14个晋级第二轮。第三轮候选算法只剩下5个。并从这5个中Keccak被宣布为获胜者。 深入Keccak 在写作的时候, NIST还没有发布SHA-3 (FIPS 180-5)的官方文档。 因此, 下面的资料收集于Keccak的参考文档和来源于第三方。 这里有Keccak算法的三个部分 (图1). 图1: Keccak散列函数的基本模块。 Hash()函数作为入口函数。它需要4个输入参数：散列位大小 (n)，消息文本(M)和它的位大小 (N)，和一个哈希变量 (H). 这个哈希变量必须有下面的mallo

6、c（）函数创建： view source print?1HashReturn E; 2char *H; 3n = 224; 4H = (char *)malloc(sizeof(char) * n / 8); 5/. 6E = Hash(n, M, N, H);Init()函数为指定的哈希大小准备内部状态（S）。Update()函数开始压缩或吸收相。在这里根据内部状态组合消息文本， 然后置换. Final()函数开始提取或压缩相。这是位从内部状态提取和组装形成的散列值 。第一个n位组装的散列然后作为消息散列 。四个函数都返回一个错误的结果，返回0说明函数没有出错地执行结束。图2显示了内部状态的

7、数据结构。命名为spongeState的这个C结构包含8个域，其中两个是固定数组(以红色标出）。state数组域存储真正的状态字节,而dataQueue数组域存储着将被组合和变换的消息字节。 图2：保存Keccak哈希函数的内部状态的结构 capacity域是散列容量(用c表示)。它的值设置为散列大小的两倍(2*n)。rate域是每个循环处理的消息位长度。它设置为1600-c这个值。bitInQueue域是保留在dataQueue数组域中的消息位长度。fixedOutputlength域是期望的散列大小(用n表示)。squeezing域是模式标志。当设置为0时，keccak处在压缩模式。当设置

8、为1时，keccak是处在解压缩模式。另外 filedbitsAvailableForSqueezing保存的是组合为最终消息散列的状态位长度。 Keccak使用了24个变换循环来缩减消息文本为散列值。每个循环连续调用了五个模块，如图3所示。 图3：每个变换循环调用的模块模块把内部状态转化为5x5的每个元素为64位的数组。它计算每列中同位的部分，然后使用异或（XOR）操作符对它们进行组合。然后它按照下面的方式把获得的同位结果和每个状态位异或: Sijk = parity(S0.4j-1k) parity(S0.4j+1k-1)where i = 0.4; j = 0.4; k = 0.63模块

9、按照三角数的排列对每个64位元素循环移动。不过循环移动把元素S00排除在外。模块变换64位元素。变换遵循下面所示的固定赋值模式: Sj2*i + 3*j = Sij模块给变换循环增加了非线性特性。它仅仅使用了三个逐位操作符：与（AND），非（NOT）和异或（XOR）来组合行元素。然后按照下面的方式把结果写入状态数组里: Sijk = Sij + 1k & Sij + 2k模块打破了由其他模块所产生的任何对称。它是这样做的，把数组中的一个元素与一循环常量异或。这个模块有24个循环常量供选择。这些常量由Keccak内部定义。不过，由于 Keccak的C源代码太大不能全部罗列在这儿了。SHA-3评估

10、 那么SHA-3与它的前任SHA-1和SHA-2比较又如何呢？为了回答这个问题，我对这三个哈希函数进行四个独立的测试： 第一个测试是冲突测试。这儿，我准备了一些消息文本，并且让这些哈希函数处理每个文本。一个良好设计的哈希函数应当对每个文本生成一个唯一的散列值，甚至在两个文本仅仅有一个字符的差别时。如果冲突发生了，那么冲突应该是非常罕见的，并且复杂度至少是2n。 第二个测试是运行位测试。这个测试揭示了位怎样分布在哈希值上才是良好的。理想情况下，一个哈希值应当具有相互平衡数目的1和0。如果我们把哈希划分为两相等的部分，并计算每一半中1的数目，我们应当得到相等的数量。如果有一半比另一半多出1的数量，

11、这意味着有一个潜在的不对称，它可能转换为一个可能的冲突。 下一个测试是雪崩或者瀑布测试。这个测试用于测量哈希函数对文本信息变化的反应能力。理想情况下，一个消息字节的变化应该能引起约半个散列字节的变化；并且这个变化应当顺着哈希值一致地发生。太大或者太小的变化就可能说明有冲突。 最后一个测试是耗时测试。这个用来测量哈希函数处理消息文本的速度。一个良好的哈希函数处理一个大信息文本耗时不超过半秒。更长的哈希耗时是不期望的，除非这个函数做为高流量服务的一部分。 表1显示了SHA-3与前两任相比较的情况。测试的机器是苹果的MacBook，带有2G赫兹的Intel 酷睿2 Duo处理器和2GB的DDR2内存

12、。操作系统是MacOS X 10.6.7。测试的消息是来自威廉.莎士比亚的戏剧哈姆雷特的摘要-生存还是死亡独白，由33行文本总共260个单词组成。由于SHA-1仅仅生成160位散列值，而SHA-2和SHA-3的输出限制在224位，所以它们生成大小相比较最接近。 表1：比较SHA-3与其前任 与SHA-1和SHA-2相比较，SHA-3有一个更小点的联动率。对每个消息字节的更改它仅仅更改三个哈希字节。SHA-3显示轻微的位倾斜。它的消息散列的右半部分比左半部分多出12个1位。SHA-3比SHA-2快些，哈希测试文本少花费了2.80纳秒。 表2显示了当生成四个不同大小的散列的时候SHA-3的执行情况

13、。使用同样的机器和同样的消息文本获得的测试结果。 表2：生成四个不同大小的散列时SHA-3的执行情况 这儿，对所有四个大小的散列SHA-3仍然显示了小的联动率。这似乎是Keccak和它的海绵引擎的特性。SHA-3也显示了轻微的倾斜。消息散列的三个都是右半部分比左半部分有更多的1位。然而，512位散列值的左半部分比右半部分有更多的1位。SHA-3仍然快些，产生512位消息散列花费了2.010纳秒。这比256位的SHA-2快2.003纳秒。 这个表没有显示任何冲突测试结果，因为测试本身没有发现冲突。测试的消息可能太短或者太多变化而不能引起冲突。不过，更大点的文本，尤其是具有微小变化的更大文本，对这

14、些哈希函数的一个可能引起至少一个冲突。Xcode项目FooSHA3可用做参考。 部署SHA-3 SHA-3仍然没有进入大多数主流平台。某些平台（如MacOS X和IOS）仍然依赖libcrypto库，这个库只支持SHA-1和SHA-2。把SHA-3部署到你所期望的平台的一种方法是编译这个哈希算法为静态库。然后把新的库安装到/urs/lib或者/usr/share目录下，在这儿假设你对这些目录具有写的权限。不过还有另一种方法去部署SHA-3，这种方法可以工作在Mac OS X和IOS上，即以框架捆绑包的形式部署。 框架捆绑包是一个层次性的文件集合，这些文件一起才形成一个动态库。不像大多数捆绑包，

15、框架捆绑包是透明的；它的内容像其他普通目录的内容一样可以随意浏览。框架捆绑包可以位于常见的目录（比如/Libray/Framworks），或者把框架捆绑包拷贝到应用捆绑包里，然后把它当作私有资源来用。对框架捆绑包的访问是通过NSBunble类或者通过核心基础的捆绑服务来实现的。清单1显示了如何给NSString类增加SHA-3支持。这儿，类SHA3String 声明了两个方法原型（行8-9）。类方法sha3AsCstring使用实例方法cStringUsingEncoding:(行25)提取原始的消息字节。它声明标准的ASCII做为所期望的文本编码。这个方法计算了消息字节数，并且创建哈希变量t

16、Hash（行29-30）。 然后传递字节数，消息文本和哈希变量给入口函数Hash()(行33)。Hash()函数返回512位的消息散列值，接着sha3AsCstring 重新强制转换这个散列值为一个常量字符串（行36）。顺便说明一下，BitSequence是Keccak对char类型的自定义。 清单1 view source print?01/ - File:SHA3Category.h 02/ 03#import 04#import 05#import KeccakNISTInterface.h 0607interface NSString (SHA3String) 08- (const c

17、har *)sha3AsCstring; 09- (NSData *)sha3AsData; 10/. 11end 1213/ - File: SHA3Category.m 14/ 15implementation NSString (SHA3String) 16/ Return the SHA-3 hash as a C-string 17- (const char *)sha3AsCstring 18 19const char *tTemp; 20const BitSequence *tData; 21BitSequence *tHash; 22NSUInteger tLen; 2324/

18、 extract the message data 25tTemp = self cStringUsingEncoding:NSASCIIStringEncoding; 26tData = (const BitSequence *)tTemp; 2728/ prepare the hash variable 29tLen = strlen(tTemp); 30tHash = malloc(sizeof(BitSequence) * 32); 3132/ hash the message data 33Hash(512, tData, tLen, tHash); 3435/ return the

19、 hash result 36tTemp = (const char *)tHash; 37return (tTemp); 38 3940/ Return the SHA-3 hash as an NSData object 41- (NSData *)sha3AsData 42 43const char *tHash; 44NSUInteger tLen; 45NSData *tData; 4647/ generate the SHA-3 hash 48tHash = self sha3AsCstring; 4950/ prepare the hash object 51tLen = str

20、len(tHash); 52tData = NSData dataWithBytes:tHash 53length:tLen; 5455/ return the hash object 56return (tData); 57 5859/. 60end类方法sha3AsData返回NSData对象形式的消息散列值。它依靠sha3AsCstring来处理消息字节（行48）。然后使用工厂方法dataWithBytes:length: 创建这个对象（行52-53）。清单2显示出SHA-3是一个单例模式的类. 单例模式提供一个公共的全局访问点来访问SHA-3算法。它自己操纵自己的内存管理,所以，不需要

21、显式的处理。 清单2 view source print?001/ - File:SHA3Single.h 002/ 003#import 004#import KeccakNISTInterface.h 005006/ Define the enum constants 007typedef enum _SHA3_SIZE 008SIZE_224 = 224, SIZE_256 = 256, 009SIZE_384 = 384, SIZE_512 = 512 010SHA3_SIZE; 011012013/ Declare the class interface 014interface S

22、HA3Single : NSObject 015 016private017NSUInteger pSize; 018 019property (readwrite) NSUInteger hashSize; 020021+ (id)defaultGenerator; 022+ (id)generatorForSize:(NSUInteger)aSize; 023024- (void)hashMessage:(const char *)aMesg 025into:(BitSequence *)aHash; 026- (void)hashObject:(id)aMesg 027into:(Bit

23、Sequence *)aHash; 028end 029030/ - File: SHA3Single.m 031/ 032/ Declare the static global 033static SHA3Single *gHash; 034035/ Define the singleton class 036implementation SHA3Single 037synthesize hashSize = pSize; 038039/ Create the default SHA3 generator 040+ (id)defaultGenerator 041 042synchroniz

24、ed(self) 043 044/ check the static global 045if (gHash = nil) 046 047/ create the instance 048gHash = super alloc init; 049050/ set the output hash size 051gHash.hashSize = SIZE_512; 052 053 054055/ return the singleton instance 056return (gHash); 057 058059/ Create a custom SHA3 generator 060+ (id)

25、generatorForSize:(NSUInteger)aSize 061 062synchronized(self) 063 064/ check the static global 065if (gHash = nil) 066 067/ create the instance 068gHash = super alloc init; 069070/ set the output hash size 071gHash.hashSize = aSize; 072 073 074075/ return the singleton instance 076return (gHash); 077 078079- (void)hashMessage:(const char *)aMesg 080into:(BitSequence *)aHash 081 082NSUInteger tLen; 083084/ generate the SHA-3 hash 085tLen = strlen(aMesg); 086Hash(self.hashSize, 087(const BitSequen