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

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

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

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

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

　　采用上述優(yōu)化方法后，我們在計算f , g , h函數(shù)的過程中能大大簡化所需要的布爾運算次數(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)化方法需要額外增加邏輯判斷的開銷，但由于f , g , h 布爾函數(shù)是固定的，所以在實際運算的過程中，增加的邏輯判斷對算法的優(yōu)化效果仍然比較明顯.

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

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

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

　　4 結(jié)束語

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