低功耗AVR微处理器上Quark 哈希算法优化实现

nge 构造当中所定义的rate 值和 capacity 值，P是上述 Quark 压缩函数.mi为输入消息值，在迭代轮数后， zi 为哈希输出值.

　　3 面向低功耗AVR 微处理器的Quark 哈希算法实现3.1 基于字节的压缩函数变换操作Quark 的压缩函数轮数与内部数据宽度有关.

　　以D-Quark 为例，由于其内部数据宽度为176 比特，我们采用22 个字节来存储内部数据，同时需要704轮来迭代处理数据.在普通环境实现中，我们可以采用并行化的方法，增大内部数据存储空间的方式来加快处理速度.但在受限硬件环境下，由于内存的限制，三个变换操作每轮只能输出一个比特，在AVR 微处理器环境下，算法的实际总轮数大大增加.

　　在算法的优化上，我们采用基于字节的方式来提高压缩函数的效率.在每一轮迭代过程中，由于新的输出值将会影响到下一轮的运算，我们增加一个额外的字节用来存放相关数据，同时根据算法每次运行需左移一位的特点，我们可以把比特的运算变为字节的运算.假设寄存器里存放x0 x1x2 x3 x4 x5 x6 x7八个比特的值，我们在当前的计算中需要x0 这个比特数，那么下一次计算中我们需要x1这个比特数，由此我们对寄存器作or 或者and 的操作，就可以同时更新8 个比特的值.因此我们可以把的循环次数降低1/8.改进后的Quark 各子算法在内部状态存储上所需的字节数和基于字节的压缩函数所需迭代轮数如下表2 所示.

　　3.2 基于布尔运算特点的非线性函数优化基于字节操作方式优化压缩函数后， f , g ,h 三个非线性布尔函数的变换操作耗时最长.由于f , g , h 本身是基于比特运算的非线性函数，每次需要对输入比特进行大量的加法和乘法运算.而在AVR 环境下并没有针对比特的上述算术操作，因而在实际计算需要对布尔函数的每一项进行运算才能得出结果.在算法的优化过程中，我们基于布尔运算的特点，将f , g , h 函数的计算过程通过同类项和提前约取的方法加以简化.我们通过布尔函数 f （x） = x0 x1x2 + x 0×1 x3 （其中x0 x1 x2 + x 0x 1×3 表示各比特逻辑与之后再进行逻辑加运算，与Quark中表示方法一致）对优化方法解释如下：

　　1.如果有x0或x1等于 0,那么无论x2或x3取何值，整个函数的输出值均为0;2.如果x2或x3等于 0,那么所有包含x2或x3的项都为0;3.如果x2等于 1,那么可以把所有x2从等式中约去，对输出结果没有影响.

　　采用上述优化方法后，我们在计算f , g , h函数的过程中能大大简化所需要的布尔运算次数.

　　优化后的Quark 算法的AVR ASM 伪代码结构如下所示.

　　main:

　　SRAM_DATA = message;call quark;if digest equal outreturn digest ok;else return digest error;quark:

　　call init;call update;call final;ret虽然上述优化方法需要额外增加逻辑判断的开销，但由于f , g , h 布尔函数是固定的，所以在实际运算的过程中，增加的逻辑判断对算法的优化效果仍然比较明显.

　　3.3 实验结果通过上述优化方法，我们基于AVR 汇编语言实现了Quark 算法.基于Quark 原始论文给出的正确性测试，优化后的算法在实现上是正确的.Quark算法基于标准输入消息的相应输出结果应如下所示：

　　为了比较Quark 实现在ATtiny 设备上的实际效率，我们采用ATMEL ATting45 系列微处理器作为实验平台，在平台上使用AVR ASM 汇编语言（编译环境AVR Studio 6.0）来实现D-Quark 和S-Quark 算法.ATtiny45 系列微处理器具有4K 字节可编程Flash ROM,256 字节EEPROM,256 字节SRAM,工作模式下主频可自适应调整，最大可为20MHz.

　　为了对比所提出的优化方法的效率，我们也按照Quark 原始参考文献当中的标准方法将D-Quark 和S-Quark 在相同平台下加以实现并测试.各项性能数据均由AVR Studio 6.0 测试给出.

　　4 结束语

然摩尔定律预测计算机的计算速度和存储能力每18 个月能增加一倍，但由于制造成本和便携性的限制，WSN 和RFID 硬件平台的计算能力.存储能力和能量仍然受到非常大的限制.尽管轻量级分组密码算法的研究已经引起广泛的关注，但仍然存在不少问题尚待解决.轻量级密码学作为一个新兴研究分支，需要综合密码学.电路设计和嵌入式系统等方面的研究方法和成果.Quark 哈希算法采用了面向软件的设计思路，很好的平衡了算法的安全性和软硬件实现上的效率与开销.在未来的工作中，我们将进一步地深入分析Quark 哈希算法在受限软硬件环境下的具体实现方法，为Quark 在实际中提供更充分的性能指标和算法实现参考.