用于實現嵌入式安全的開源硬件

想像一下你正在排隊等待參加一個重要活動。門票是通過網上購買的，存儲在你的智能手機中。你需要將手機放到某個指定區域上，建立起NFC連接，門票隨之得到確認，大門開啟允許你進入。好消息是，所有這一切都是在匿名情況下發生的。

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

圖1給出了這種ZKPK——本例中的Schnorr協議的簡要示意圖。其中y是x的承諾。在強大的RSA假設下，是很難從y找出x的，即使你知道g和m。

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

圖1： Schnorr ZKPK協議的簡化版本。

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

在嵌入式平臺上計算并行求冪所需時間的例子

在我們的測試裝置(后面會討論到)上，我們比較了硬件加密內核和軟件實現方法的執行時間。

硬件和軟件都計算：

在匿名信任協議中經常使用的并行求冪。

我們規定指數長度在32位和2048位之間變化。基數的長度是固定的，本例中是1024位。軟件運行在嵌入式Linux操作系統上，并在多精度算法中使用了GMP庫。

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

圖2：在嵌入式平臺上分別用硬件卸載和不用硬件卸載時的并行求冪執行時間。

嵌入式安全性測試平臺

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

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

我們開發的平臺如圖3所示，它基于的是賽靈思的ML605評估板。我們增加了恩智浦的PN532開發套件用于NFC通信。運行嵌入式Linux的MicroBlaze用于控制整個系統。使用Linux(本例中用的是PetaLinux發行版)有很大的優勢，即在嵌入式系統中可以用標準庫，比如用于算法的GMP和用于NFC通信的libnfc。

圖3：用于測試和評估匿名信任協議的嵌入式平臺。

使用FPGA可以很方便地增加和開發加密硬件加速器。本文余下部分將討論我們開發用于測試目的的這種IP內核設計。

開源硬件

因此我們想要一個可以用作硬件加速器的加密內核。可能的話，它可以計算：

市場上有多種IP內核可以用來執行單次模冪運算。然而，像DAA或Idemix等協議要求至少兩次這種求冪的產品。這意味著我們仍然必須執行大操作數的多次(模)乘法，這將進一步增長總的執行時間。另外，我們希望能夠改變所有操作數的長度，但不顯著降低性能。也許我們還希望在其它平臺上測試硬件。

這份希望清單促成了開源IP內核的設計，并符合以下規范：

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

然而，這不是一個(完美的)商用產品。我們知道可以實現更快或更小的設計。但每個人都可以自由使用并用這個設計做試驗。這是我們設計的最初目的，也是我們做得盡可能可定制的原因。

目前這個內核還沒有任何JTAG接口或自檢功能。然而，可以對某些測試矢量執行求冪并比較結果來驗證操作是否正確。

一些背景

并行求冪

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

仔細觀察這個算法可以發現，采用要么運行單次乘法(用于預運算和最終乘法)要么自動運行主環的方式只實現一個乘法器并實現控制邏輯是合理的設計選擇。

遵循標準的設計思路，我們將IP內核實現為存儲器映射的外設。內核行為可以通過驅動軟件使用控制寄存器改變(圖4)。由于主環要求4個操作數，因此需要提供內存進行存儲。中斷線允許硬件就某些事件提醒處理器。

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

圖4：我們開發的并行求冪IP內核的框圖。

模乘

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

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

圖5：一個脈動陣列單元計算中間結果a的一個位。

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

圖6：脈動流水線操作。

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

圖7：蒙哥馬利乘法器結構。

性能

乘法器資源使用率取決于操作數(n)的長度和流水線的級數(k)。

對FPGA來說可以表示為：

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

執行乘法的時鐘周期數也取決于n和k：

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

圖8：流水線級長度對最高時鐘頻率的影響。

在使用這個設計時，可以有幾種方法：

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

圖9：流水線級長對最短執行時間的影響。

我們想要盡可能地減小時間與面積乘積。事實上，我們可以專注于最大限度地減小時間與FF數量的乘積，因為LUT數量基本上是常數。下圖顯示了不同流水線級長下的時間與FF數量乘積。當級長為8位時達到最小值。

圖10：流水線級長對時間與面積乘積的影響。

首次測試

基于NFC的ZKPK

作為第一次實際測試，我們實現了基于NFC的簡化Schnorr ZKPK，詳見我們的嵌入式測試平臺介紹。這種個嵌入式平臺是驗證方，而PC(連接有PN532電路板)用作證明方。

下表給出了不同操作數長度下的時序結果。很明顯，當使用我們的硬件IP內核時，操作數長度對總的協議時間基本上沒有影響。增加操作數長度會稍稍增加通信時間(這是預料中的)。然而，驗證所需的時間將大大增加。

我們需要指出的是，通信占總時間的很大一部分。像產生隨機數等一般數據操作也需要一定的時間。然而，我們的IP內核還無法克服這些挑戰。

軟件控制方案對比全自動操作

實現完整的并行求冪內核是一個英明的決策嗎？為什么不只是乘法器和一些控制軟件來實現算法1？因為我們可以將我們的IP內核用作乘法器，我們能夠非常容易的測試它。我們可以在相同的系統上比較這兩種方法。

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

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

小結和未來發展

我們已經表明，這種用于模并行求冪運算的IP內核的可定制VHDL設計是非常適合匿名信任加密系統的嵌入式實現的。我們已經見證了如何調整內核參數來滿足用戶的需要。

除了更為理論性的性能分析外，我們還在實際的嵌入式裝置中使用了這個設計。作為我們未來工作的一部分，我們將繼續為匿名信任證書開發完整的嵌入式應用程序。

進一步開發對象還將導向內核本身。目前內核只提供PLB接口。提供對AXI和Wishbone接口的支持“已經列在任務清單上”。

包括所有乘法與求冪技術文檔和測試基準的完整VHDL設計已經在開源網站OpenCores上公開上線。只要有GNU較寬松通用公共許可(LGPL)協議就能免費下載VHDL源代碼。