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

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

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

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

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

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

　　優(yōu)化后的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雖然上述優(yōu)化方法需要額外增加邏輯判斷的開(kāi)銷(xiāo)，但由于f , g , h 布爾函數是固定的，所以在實(shí)際運算的過(guò)程中，增加的邏輯判斷對算法的優(yōu)化效果仍然比較明顯.

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

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

　　為了對比所提出的優(yōu)化方法的效率，我們也按照Quark 原始參考文獻當中的標準方法將D-Quark 和S-Quark 在相同平臺下加以實(shí)現并測試.各項性能數據均由AVR Studio 6.0 測試給出.

　　4 結束語(yǔ)

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