低功耗AVR微處理器上Quark 哈希算法優(yōu)化實(shí)現(xiàn)

　　以D-Quark 為例，由于其內(nèi)部數(shù)據(jù)寬度為176 比特，我們采用22 個(gè)字節(jié)來(lái)存儲(chǔ)內(nèi)部數(shù)據(jù)，同時(shí)需要704輪來(lái)迭代處理數(shù)據(jù).在普通環(huán)境實(shí)現(xiàn)中，我們可以采用并行化的方法，增大內(nèi)部數(shù)據(jù)存儲(chǔ)空間的方式來(lái)加快處理速度.但在受限硬件環(huán)境下，由于內(nèi)存的限制，三個(gè)變換操作每輪只能輸出一個(gè)比特，在AVR 微處理器環(huán)境下，算法的實(shí)際總輪數(shù)大大增加.

　　在算法的優(yōu)化上，我們采用基于字節(jié)的方式來(lái)提高壓縮函數(shù)的效率.在每一輪迭代過(guò)程中，由于新的輸出值將會(huì)影響到下一輪的運(yùn)算，我們?cè)黾右粋€(gè)額外的字節(jié)用來(lái)存放相關(guān)數(shù)據(jù)，同時(shí)根據(jù)算法每次運(yùn)行需左移一位的特點(diǎn)，我們可以把比特的運(yùn)算變?yōu)樽止?jié)的運(yùn)算.假設(shè)寄存器里存放x0 x1x2 x3 x4 x5 x6 x7八個(gè)比特的值，我們?cè)诋?dāng)前的計(jì)算中需要x0 這個(gè)比特?cái)?shù)，那么下一次計(jì)算中我們需要x1這個(gè)比特?cái)?shù)，由此我們對(duì)寄存器作or 或者and 的操作，就可以同時(shí)更新8 個(gè)比特的值.因此我們可以把的循環(huán)次數(shù)降低1/8.改進(jìn)后的Quark 各子算法在內(nèi)部狀態(tài)存儲(chǔ)上所需的字節(jié)數(shù)和基于字節(jié)的壓縮函數(shù)所需迭代輪數(shù)如下表2 所示.

　　3.2 基于布爾運(yùn)算特點(diǎn)的非線性函數(shù)優(yōu)化基于字節(jié)操作方式優(yōu)化壓縮函數(shù)后， f , g ,h 三個(gè)非線性布爾函數(shù)的變換操作耗時(shí)最長(zhǎng).由于f , g , h 本身是基于比特運(yùn)算的非線性函數(shù)，每次需要對(duì)輸入比特進(jìn)行大量的加法和乘法運(yùn)算.而在AVR 環(huán)境下并沒(méi)有針對(duì)比特的上述算術(shù)操作，因而在實(shí)際計(jì)算需要對(duì)布爾函數(shù)的每一項(xiàng)進(jìn)行運(yùn)算才能得出結(jié)果.在算法的優(yōu)化過(guò)程中，我們基于布爾運(yùn)算的特點(diǎn)，將f , g , h 函數(shù)的計(jì)算過(guò)程通過(guò)同類項(xiàng)和提前約取的方法加以簡(jiǎn)化.我們通過(guò)布爾函數(shù) f （x） = x0 x1x2 + x 0×1 x3 （其中x0 x1 x2 + x 0x 1×3 表示各比特邏輯與之后再進(jìn)行邏輯加運(yùn)算，與Quark中表示方法一致）對(duì)優(yōu)化方法解釋如下：

　　1.如果有x0或x1等于 0,那么無(wú)論x2或x3取何值，整個(gè)函數(shù)的輸出值均為0;2.如果x2或x3等于 0,那么所有包含x2或x3的項(xiàng)都為0;3.如果x2等于 1,那么可以把所有x2從等式中約去，對(duì)輸出結(jié)果沒(méi)有影響.

　　采用上述優(yōu)化方法后，我們?cè)谟?jì)算f , g , h函數(shù)的過(guò)程中能大大簡(jiǎn)化所需要的布爾運(yùn)算次數(shù).

　　優(yōu)化后的Quark 算法的AVR ASM 偽代碼結(jié)構(gòu)如下所示.

　　main:

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

　　call init;call update;call final;ret雖然上述優(yōu)化方法需要額外增加邏輯判斷的開(kāi)銷，但由于f , g , h 布爾函數(shù)是固定的，所以在實(shí)際運(yùn)算的過(guò)程中，增加的邏輯判斷對(duì)算法的優(yōu)化效果仍然比較明顯.

　　3.3 實(shí)驗(yàn)結(jié)果通過(guò)上述優(yōu)化方法，我們基于AVR 匯編語(yǔ)言實(shí)現(xiàn)了Quark 算法.基于Quark 原始論文給出的正確性測(cè)試，優(yōu)化后的算法在實(shí)現(xiàn)上是正確的.Quark算法基于標(biāo)準(zhǔn)輸入消息的相應(yīng)輸出結(jié)果應(yīng)如下所示：

　　為了比較Quark 實(shí)現(xiàn)在ATtiny 設(shè)備上的實(shí)際效率，我們采用ATMEL ATting45 系列微處理器作為實(shí)驗(yàn)平臺(tái)，在平臺(tái)上使用AVR ASM 匯編語(yǔ)言（編譯環(huán)境AVR Studio 6.0）來(lái)實(shí)現(xiàn)D-Quark 和S-Quark 算法.ATtiny45 系列微處理器具有4K 字節(jié)可編程Flash ROM,256 字節(jié)EEPROM,256 字節(jié)SRAM,工作模式下主頻可自適應(yīng)調(diào)整，最大可為20MHz.

　　為了對(duì)比所提出的優(yōu)化方法的效率，我們也按照Quark 原始參考文獻(xiàn)當(dāng)中的標(biāo)準(zhǔn)方法將D-Quark 和S-Quark 在相同平臺(tái)下加以實(shí)現(xiàn)并測(cè)試.各項(xiàng)性能數(shù)據(jù)均由AVR Studio 6.0 測(cè)試給出.

　　4 結(jié)束語(yǔ)

然摩爾定律預(yù)測(cè)計(jì)算機(jī)的計(jì)算速度和存儲(chǔ)能力每18 個(gè)月能增加一倍，但由于制造成本和便攜性的限制，WSN 和RFID 硬件平臺(tái)的計(jì)算能力.存儲(chǔ)能力和能量仍然受到非常大的限制.盡管輕量級(jí)分組密碼算法的研究已經(jīng)引起廣泛的關(guān)注，但仍然存在不少問(wèn)題尚待解決.輕量級(jí)密碼學(xué)作為一個(gè)新興研究分支，需要綜合密碼學(xué).電路設(shè)計(jì)和嵌入式系統(tǒng)等方面的研究方法和成果.Quark 哈希算法采用了面向軟件的設(shè)計(jì)思路，很好的平衡了算法的安全性和軟硬件實(shí)現(xiàn)上的效率與開(kāi)銷.在未來(lái)的工作中，我們將進(jìn)一步地深入分析Quark 哈希算法在受限軟硬件環(huán)境下的具體實(shí)現(xiàn)方法，為Quark 在實(shí)際中提供更充分的性能指標(biāo)和算法實(shí)現(xiàn)參考.