想像一下你正在排隊(duì)等待參加一個(gè)重要活動(dòng)。門票是通過網(wǎng)上購買的，存儲(chǔ)在你的智能手機(jī)中。你需要將手機(jī)放到某個(gè)指定區(qū)域上，建立起NFC連接，門票隨之得到確認(rèn)，大門開啟允許你進(jìn)入。好消息是，所有這一切都是在匿名情況下發(fā)生的。

在這類應(yīng)用中，你的匿名信息可以通過使用最近開發(fā)的匿名信任協(xié)議(如IBM的Idemix或微軟的U-Prove)得到保護(hù)。這些協(xié)議基于知識(shí)的零知識(shí)證明(ZKPK)。你可以證明你擁有某個(gè)屬性的知識(shí)而不用透露具體數(shù)值。這種屬性與所謂的承諾中的公鑰是捆綁在一起的。

圖1給出了這種ZKPK——本例中的Schnorr協(xié)議的簡(jiǎn)要示意圖。其中y是x的承諾。在強(qiáng)大的RSA假設(shè)下，是很難從y找出x的，即使你知道g和m。

仔細(xì)觀察協(xié)議我們會(huì)發(fā)現(xiàn)x仍然是隱藏的。驗(yàn)證方只知道y是正確的承諾。我們還能發(fā)現(xiàn)，協(xié)議主要由通信和算法組成——這正是我們研究的對(duì)象。

圖1： Schnorr ZKPK協(xié)議的簡(jiǎn)化版本。

----------------------------------------------------------------------------------------------------------------------------------------------

在嵌入式平臺(tái)上計(jì)算并行求冪所需時(shí)間的例子

在我們的測(cè)試裝置(后面會(huì)討論到)上，我們比較了硬件加密內(nèi)核和軟件實(shí)現(xiàn)方法的執(zhí)行時(shí)間。

硬件和軟件都計(jì)算：

在匿名信任協(xié)議中經(jīng)常使用的并行求冪。

我們規(guī)定指數(shù)長(zhǎng)度在32位和2048位之間變化?；鶖?shù)的長(zhǎng)度是固定的，本例中是1024位。軟件運(yùn)行在嵌入式Linux操作系統(tǒng)上，并在多精度算法中使用了GMP庫。

處理器和IP內(nèi)核都以相同速度(100MHz)運(yùn)行。我們發(fā)現(xiàn)，兩種方法的執(zhí)行時(shí)間都隨指數(shù)長(zhǎng)度成比例的增加。然而，采用硬件卸載方式的運(yùn)算要快10至50倍。

圖2：在嵌入式平臺(tái)上分別用硬件卸載和不用硬件卸載時(shí)的并行求冪執(zhí)行時(shí)間。

嵌入式安全性測(cè)試平臺(tái)

我們很快發(fā)現(xiàn)，當(dāng)這些ZKPK在嵌入式系統(tǒng)上實(shí)現(xiàn)時(shí)，通信和算法都會(huì)引起瓶頸(見例子)。我們不希望用戶保持NFC連接超過比方說5秒鐘，不然會(huì)與通過“接觸”交換數(shù)據(jù)的NFC概念發(fā)生沖突。

為了詳細(xì)研究這個(gè)問題，我們構(gòu)建了一個(gè)測(cè)試平臺(tái)(見圖3)，以便我們能夠方便地改變協(xié)議的不同方面。例如，如果我們將算法卸載到硬件加速器來提升算法速度會(huì)怎么樣？或者操作數(shù)的長(zhǎng)度對(duì)通信和算法的速度有何影響？

我們開發(fā)的平臺(tái)如圖3所示，它基于的是賽靈思的ML605評(píng)估板。我們?cè)黾恿硕髦瞧值腜N532開發(fā)套件用于NFC通信。運(yùn)行嵌入式Linux的MicroBlaze用于控制整個(gè)系統(tǒng)。使用Linux(本例中用的是PetaLinux發(fā)行版)有很大的優(yōu)勢(shì)，即在嵌入式系統(tǒng)中可以用標(biāo)準(zhǔn)庫，比如用于算法的GMP和用于NFC通信的libnfc。

圖3：用于測(cè)試和評(píng)估匿名信任協(xié)議的嵌入式平臺(tái)。

使用FPGA可以很方便地增加和開發(fā)加密硬件加速器。本文余下部分將討論我們開發(fā)用于測(cè)試目的的這種IP內(nèi)核設(shè)計(jì)。

開源硬件

因此我們想要一個(gè)可以用作硬件加速器的加密內(nèi)核?？赡艿脑挘梢杂?jì)算：

市場(chǎng)上有多種IP內(nèi)核可以用來執(zhí)行單次模冪運(yùn)算。然而，像DAA或Idemix等協(xié)議要求至少兩次這種求冪的產(chǎn)品。這意味著我們?nèi)匀槐仨殘?zhí)行大操作數(shù)的多次(模)乘法，這將進(jìn)一步增長(zhǎng)總的執(zhí)行時(shí)間。另外，我們希望能夠改變所有操作數(shù)的長(zhǎng)度，但不顯著降低性能。也許我們還希望在其它平臺(tái)上測(cè)試硬件。

這份希望清單促成了開源IP內(nèi)核的設(shè)計(jì)，并符合以下規(guī)范：

● 針對(duì)嵌入式平臺(tái)的開源IP內(nèi)核(控制要求的軟件)
● VHDL代碼獨(dú)立于器件和制造商，并得到良好歸檔
● 基數(shù)g0、g1和模數(shù)m的長(zhǎng)度可以在綜合前自由選取
● 為指數(shù)準(zhǔn)備了一個(gè)FIFO，因此e0和e1的長(zhǎng)度可以完全取決于控制軟件
● 將流水線式蒙哥馬利乘法器作為IP內(nèi)核的核心，并具有自由選擇的級(jí)長(zhǎng)，從而允許調(diào)整內(nèi)核獲得想要的速度/面積
● 操作數(shù)RAM專門針對(duì)并行求冪進(jìn)行了優(yōu)化

然而，這不是一個(gè)(完美的)商用產(chǎn)品。我們知道可以實(shí)現(xiàn)更快或更小的設(shè)計(jì)。但每個(gè)人都可以自由使用并用這個(gè)設(shè)計(jì)做試驗(yàn)。這是我們?cè)O(shè)計(jì)的最初目的，也是我們做得盡可能可定制的原因。

目前這個(gè)內(nèi)核還沒有任何JTAG接口或自檢功能。然而，可以對(duì)某些測(cè)試矢量執(zhí)行求冪并比較結(jié)果來驗(yàn)證操作是否正確。

一些背景

并行求冪

最直接也是高效的模冪運(yùn)算方法是通過重復(fù)平方和乘法運(yùn)算獲得最終結(jié)果。這種方法很容易擴(kuò)展到并行求冪運(yùn)算。下面就是這種算法的描述，其中Mont()表示蒙哥馬利乘法。這是一種用硬件執(zhí)行模乘運(yùn)算的有效方法，我們對(duì)此還將進(jìn)一步討論。我們假設(shè)R2 (= 22n ,n是m的長(zhǎng)度)可以通過控制軟件提供甚至計(jì)算。

仔細(xì)觀察這個(gè)算法可以發(fā)現(xiàn)，采用要么運(yùn)行單次乘法(用于預(yù)運(yùn)算和最終乘法)要么自動(dòng)運(yùn)行主環(huán)的方式只實(shí)現(xiàn)一個(gè)乘法器并實(shí)現(xiàn)控制邏輯是合理的設(shè)計(jì)選擇。

遵循標(biāo)準(zhǔn)的設(shè)計(jì)思路，我們將IP內(nèi)核實(shí)現(xiàn)為存儲(chǔ)器映射的外設(shè)。內(nèi)核行為可以通過驅(qū)動(dòng)軟件使用控制寄存器改變(圖4)。由于主環(huán)要求4個(gè)操作數(shù)，因此需要提供內(nèi)存進(jìn)行存儲(chǔ)。中斷線允許硬件就某些事件提醒處理器。

普通32位總線接口可以很容易擴(kuò)展到多種流行的總線標(biāo)準(zhǔn)，如AXI或Wishbone。下面給出了最終設(shè)計(jì)的框圖(n代表操作數(shù)的寬度)。

圖4：我們開發(fā)的并行求冪IP內(nèi)核的框圖。

模乘

現(xiàn)在我們的工作將簡(jiǎn)化為設(shè)計(jì)一個(gè)乘法器，并且它能根據(jù)我們的需要方便地進(jìn)行定制。當(dāng)操作數(shù)長(zhǎng)度大于512位(對(duì)我們的應(yīng)用來說這是顯然的情況)時(shí)，一種被稱為脈動(dòng)陣列蒙哥馬利的乘法器(2)是最有效的實(shí)現(xiàn)。此外，它很容易轉(zhuǎn)換成硬件，從而簡(jiǎn)化生成通用描述的任務(wù)。

Mont(x,y)可以通過計(jì)算x的每一位的中間結(jié)果(a)進(jìn)行運(yùn)算。因此在經(jīng)過n位后，乘法運(yùn)算就完成了。a的每一位都可以用加法器和乘法器進(jìn)行運(yùn)算，最后一起形成脈動(dòng)陣列單元(圖5)。當(dāng)大量單元級(jí)聯(lián)時(shí)，為了中斷進(jìn)位鏈，我們將它們組成級(jí)。這樣我們就可以控制設(shè)計(jì)的最大可達(dá)到頻率，而這個(gè)頻率主要受限于這個(gè)進(jìn)位鏈。另外，還允許流水線運(yùn)算。作為蒙哥馬利算法一部分的右移操作可以確保a永遠(yuǎn)不會(huì)大于n+2位。

圖5：一個(gè)脈動(dòng)陣列單元計(jì)算中間結(jié)果a的一個(gè)位。

流水線操作見下圖所示(圖6)。每個(gè)圓代表一級(jí)。圓內(nèi)的數(shù)字代表當(dāng)時(shí)由那個(gè)級(jí)正在執(zhí)行的步驟(x的哪一位)。非活動(dòng)級(jí)用虛線表示。我們可以看到，一個(gè)級(jí)只能每2τc計(jì)算一步。這是右移操作的原因。τc表示一個(gè)級(jí)實(shí)際完成一個(gè)步驟所花的時(shí)間。在本例中，τc就是1個(gè)時(shí)鐘周期。

圖6：脈動(dòng)流水線操作。

移位寄存器用于將x的位移進(jìn)脈動(dòng)流水線。兩個(gè)額外加法器在必要時(shí)計(jì)算m+y(這是脈動(dòng)陣列要求的)和a-m(確保結(jié)果小于m)。最終乘法器結(jié)構(gòu)如下所示(圖7)。

圖7：蒙哥馬利乘法器結(jié)構(gòu)。

性能

乘法器資源使用率取決于操作數(shù)(n)的長(zhǎng)度和流水線的級(jí)數(shù)(k)。

對(duì)FPGA來說可以表示為：

對(duì)于大的n來說，整個(gè)IP內(nèi)核只使用另外一小部分FF和LUT比如用于控制邏輯和總線接口。然而，它也需要多個(gè)RAM單元來存儲(chǔ)操作數(shù)。

執(zhí)行乘法的時(shí)鐘周期數(shù)也取決于n和k：

不過如前所述，級(jí)數(shù)——因此這些級(jí)的長(zhǎng)度——對(duì)乘法器的最大可達(dá)時(shí)鐘頻率也有影響。這可以從圖7看出來(n=2048)。

圖8：流水線級(jí)長(zhǎng)度對(duì)最高時(shí)鐘頻率的影響。

在使用這個(gè)設(shè)計(jì)時(shí)，可以有幾種方法：

1．我們預(yù)先知道我們的工作頻率。然后就足以選擇級(jí)數(shù)以便讓時(shí)鐘頻率至少能那么高。選擇更多的級(jí)數(shù)只會(huì)導(dǎo)致耗用更多的資源(觸發(fā)器)。
2．盡量縮短運(yùn)算時(shí)間。這將由級(jí)數(shù)和最大時(shí)鐘頻率來確定。如果我們認(rèn)為設(shè)計(jì)將在這個(gè)頻率運(yùn)行(理論上)，我們可以獲得下圖所示的運(yùn)算時(shí)間(n=1536)。我們可以看到，對(duì)我們的器件(Virtex 6)來說，當(dāng)級(jí)長(zhǎng)為4位時(shí)可以獲得最短運(yùn)算時(shí)間。

圖9：流水線級(jí)長(zhǎng)對(duì)最短執(zhí)行時(shí)間的影響。

我們想要盡可能地減小時(shí)間與面積乘積。事實(shí)上，我們可以專注于最大限度地減小時(shí)間與FF數(shù)量的乘積，因?yàn)長(zhǎng)UT數(shù)量基本上是常數(shù)。下圖顯示了不同流水線級(jí)長(zhǎng)下的時(shí)間與FF數(shù)量乘積。當(dāng)級(jí)長(zhǎng)為8位時(shí)達(dá)到最小值。

圖10：流水線級(jí)長(zhǎng)對(duì)時(shí)間與面積乘積的影響。

首次測(cè)試

基于NFC的ZKPK

作為第一次實(shí)際測(cè)試，我們實(shí)現(xiàn)了基于NFC的簡(jiǎn)化Schnorr ZKPK，詳見我們的嵌入式測(cè)試平臺(tái)介紹。這種個(gè)嵌入式平臺(tái)是驗(yàn)證方，而PC(連接有PN532電路板)用作證明方。

下表給出了不同操作數(shù)長(zhǎng)度下的時(shí)序結(jié)果。很明顯，當(dāng)使用我們的硬件IP內(nèi)核時(shí)，操作數(shù)長(zhǎng)度對(duì)總的協(xié)議時(shí)間基本上沒有影響。增加操作數(shù)長(zhǎng)度會(huì)稍稍增加通信時(shí)間(這是預(yù)料中的)。然而，驗(yàn)證所需的時(shí)間將大大增加。

我們需要指出的是，通信占總時(shí)間的很大一部分。像產(chǎn)生隨機(jī)數(shù)等一般數(shù)據(jù)操作也需要一定的時(shí)間。然而，我們的IP內(nèi)核還無法克服這些挑戰(zhàn)。

軟件控制方案對(duì)比全自動(dòng)操作

實(shí)現(xiàn)完整的并行求冪內(nèi)核是一個(gè)英明的決策嗎？為什么不只是乘法器和一些控制軟件來實(shí)現(xiàn)算法1？因?yàn)槲覀兛梢詫⑽覀兊腎P內(nèi)核用作乘法器，我們能夠非常容易的測(cè)試它。我們可以在相同的系統(tǒng)上比較這兩種方法。

即使我們將操作數(shù)存儲(chǔ)在IP內(nèi)核的RAM中(因此沒有額外的總線業(yè)務(wù)量)，全自動(dòng)操作的速度仍要比軟件控制方案快一個(gè)數(shù)量級(jí)(見圖2)。這是意料之中的。Linux不是一種實(shí)時(shí)操作系統(tǒng)。在操作系統(tǒng)處理中斷之前，或者應(yīng)用程序訪問它們需要的資源(本例中為我們的存儲(chǔ)器映射外設(shè))之前，可能需要等待一定的時(shí)間。如果你知道一次求冪要求大約(7/4)t乘法(見算法1)，這種“損失時(shí)間”會(huì)很快累加起來。

如果你知道將乘法器轉(zhuǎn)變成并行求冪內(nèi)核所需的額外邏輯只由FIFO和一些計(jì)數(shù)器組成，那么我們可以說額外的硬件是比較值得的。

小結(jié)和未來發(fā)展

我們已經(jīng)表明，這種用于模并行求冪運(yùn)算的IP內(nèi)核的可定制VHDL設(shè)計(jì)是非常適合匿名信任加密系統(tǒng)的嵌入式實(shí)現(xiàn)的。我們已經(jīng)見證了如何調(diào)整內(nèi)核參數(shù)來滿足用戶的需要。

除了更為理論性的性能分析外，我們還在實(shí)際的嵌入式裝置中使用了這個(gè)設(shè)計(jì)。作為我們未來工作的一部分，我們將繼續(xù)為匿名信任證書開發(fā)完整的嵌入式應(yīng)用程序。

進(jìn)一步開發(fā)對(duì)象還將導(dǎo)向內(nèi)核本身。目前內(nèi)核只提供PLB接口。提供對(duì)AXI和Wishbone接口的支持“已經(jīng)列在任務(wù)清單上”。

包括所有乘法與求冪技術(shù)文檔和測(cè)試基準(zhǔn)的完整VHDL設(shè)計(jì)已經(jīng)在開源網(wǎng)站OpenCores上公開上線。只要有GNU較寬松通用公共許可(LGPL)協(xié)議就能免費(fèi)下載VHDL源代碼。