多項式算術運算的製作方法
2023-05-29 03:51:06 1
專利名稱：多項式算術運算的製作方法
技術領域：
本發明涉及用於執行多項式算術的微處理器指令，具體說涉及用於執行多項式乘法運算的微處理器指令。
背景當業界朝向更龐大更複雜的指令集發展時，開發出了精簡指令集計算機(RISC)體系結構。通過簡化指令集設計，RISC體系結構使得應用例如流水線和高速緩衝技術更為容易，從而提高了系統的性能。
RISC體系結構一般具有在指令格式上幾乎沒什麼變化的固定長度指令(例如16位，32位或64位)。指令集體系結構(ISA)中的每個指令可具有總處於相同位置的源寄存器。例如，32位ISA可具有總由位16-20和21-25指定的源寄存器。對每條指令而言，這允許無需任何複雜的指令解碼就可讀取指定寄存器。
概述加密的系統(「密碼系統」)越來越多地用於確保交易安全，對通信加密，對用戶進行認證以及保護信息。許多專用密鑰密碼系統(例如數字加密算法(DES))，在計算上相對簡單，並且常常可簡化為對數據塊進行一系列異或(XOR)、循環和置換運算的硬體解決方案。而另一方面，公共密鑰密碼系統比專用密鑰密碼系統在數學上更巧妙且在計算上更困難。
雖然不同的公共密鑰密碼系統方案依據不同的數學基礎，但是它們往往都需要在數量級為1024位的大數值範圍內進行整數運算。擴展精度運算常常基於模數(即以某個值域為模進行的運算)，而在某些情況下則是基於二進位多項式而非二進位補碼。例如，RSA公共密鑰密碼系統採用擴展精度模取冪來對信息加密和解密，而橢圓曲線密碼系統採用擴展精度模多項式乘法對信息加密和解密。
公共密鑰密碼系統已經廣泛用於用戶認證和安全密鑰交換，而專用密鑰密碼系統廣泛用於加密通信通道。隨著公共密鑰密碼系統的應用增多，希望能夠提高擴展精度模算術運算的性能。
一般而言，指令集體系結構包括用於執行多項式算術的指令。該指令包括一個或多個將此指令識別為用於執行多項式算術運算的指令的操作碼。此外，該指令識別一個或多個寄存器。通過使用所識別的寄存器來執行多項式算術運算，從而可對該指令加以處理。
實現可提供執行二進位多項式加法的指令，該指令可採用乘法器來實施。多項式算術運算的結果可存於一個或多個結果寄存器中。多項式算術運算可包括乘法，其中，使所標識的寄存器的內容相乘。運算還可以包括多項式的乘加運算，其中，所標識的寄存器的內容相乘然後加到一個或多個結果寄存器中。結果寄存器可包括高階寄存器和低階寄存器。可對存於寄存器中的多項式進行多項式算術運算。多項式可編碼為係數的二進位表示。
以下附圖和說明書中對一個或多個實現加以闡述。從說明書和附圖以及權利要求中可明顯看出本發明的其他特徵和優點。
圖1是可用於RISC體系結構中的五級流水線示例的框圖，圖2是包括執行核心和乘/除運算單元的處理器核心的框圖。
圖3A和3B是執行多項式乘法和加法的例示指令的指令編碼。
詳細說明許多公共密鑰密碼系統採用擴展精度模運算來對數據加密和解密。例如，多數橢圓曲線(EC)密碼系統大量採用二進位多項式乘法和加法來對數據加密和解密。橢圓曲線密碼系統的性能可通過修改編程CPU乘法器以響應新定義的專用於多項式運算的指令來加以提高。
當(如IEEE1363-2000標準所推薦的那樣)採用定義於GF(2163)上的橢圓曲線時，所需的主要運算是在GF(2163)域上的乘法運算。在2163個元素中每一個元素可表示為係數為0或1的至多163次冪的多項式。在此表示中，兩個元素可以採用簡單的按位異或相加，而兩個多項式a(X)和b(X)可通過計算a(X)b(X)mod P(X)而得到相乘的結果，乘積a(X)b(X)是326次多項式，P(X)是IEEE1363-2000標準規定的既約多項式。
多項式乘法與模數乘法具有相同的形式，在整數範圍內執行abmod p，不同之處在於(1)常規的加法由異或替代；和(2)常規的32位乘法由32位不帶進位的乘法替代。因此，可採用移位和異或而不是移位和加法運算來執行多項式模數乘法運算。
參考圖1，可用來實現多項式乘法運算的示範性的微處理器結構包括五級流水線，其中，指令可在每個時鐘周期發出並在固定的時間例如5個時鐘周期內執行。每條指令的執行分成5步取指(IF)級1001，讀寄存器(RD)級1002，算術/邏輯單元(ALU)級1003，存儲(MEM)級1004和寫回(WB)級1005。在IF級1001中，從指令高速緩衝器中取出指定指令。所取指令的一部分用於指定可用於執行指令的源寄存器。在讀寄存器(RD)級1002中，系統將指定源寄存器的內容取出。所取得的值可用在ALU級1003中執行算術或邏輯運算。在MEM級1004中，執行指令可讀/寫數據高速緩衝器中的存儲器。最後，在WB級1005中，通過執行指令而獲得的值可寫回到某個寄存器中。
因為有些運算，例如浮點運算和整數乘/除運算未必能夠在一個時鐘周期內完成，某些指令僅僅開始指令的執行。在經過足夠的時鐘周期後，另一指令可用於取回結果。例如，當整數乘法指令花費5個時鐘周期時，一條指令可啟動乘法計算，而另一條指令可在乘法運算完成後將乘積裝入寄存器中。如果在需要結果的時候乘法運算還未完成，流水線可停止直到結果可得。
參考圖2，作為示例給出示範性的RISC體系結構。處理器核心2000(也稱為「微處理器核心」)包括如下單元執行單元2010、乘/除運算單元(MDU)2020、系統控制協處理器(CPO)2030、存儲管理單元2040、高速緩存控制器2050和總線接口單元(BIU)2060。
執行單元2010是在處理器核心2000內執行指令的主要機構。執行單元2010包括寄存器陣列2011和算術邏輯單元(ALU)2012。在一種實現中，寄存器陣列2011包括32個可用於例如標量整數運算和地址計算的32位通用寄存器。可將包括兩個讀埠和一個寫埠的寄存器陣列2011完全旁路，以使流水線中的運算延遲最小。ALU2012支持邏輯和算術運算，例如加法、減法和移位。
MDU 2020執行乘法和除法運算。在一種實現中，MDU 2020包括32位乘16位(32×16)Booth編碼的(Booth-encoded)乘法器(未顯示)、結果寄存器(HI寄存器2021和LO寄存器2022)、除法狀態機以及執行這些功能的所需的所有多路復用器和控制邏輯。在一種流水線式實現中，每時鐘周期可將32×16乘法運算發送給MDU2020，以便每個時鐘周期32位的數可同16位的數相乘。但是直到乘法運算完成後HI/LO寄存器(2021和2022)中才有可用結果。可用MFHI和MFLO指令來訪問結果。這些指令將結果從HI寄存器2021和LO寄存器2022中分別移至指定的寄存器。例如「MFHI $7」將HI寄存器2021的內容移至通用寄存器$7中。
乘-加(MADD/MADDU)和乘-減(MSUB/MSUBU)這兩條指令可用於執行乘-加和乘-減運算。MADD指令使兩個數相乘後再將乘積加到HI寄存器2021和LO寄存器2022的當前內容中。然後將結果存於HI/LO寄存器(2021和2022)中。類似地，MSUB指令使兩個操作數相乘後再將乘積從HI寄存器2021和LO寄存器2022中減去，然後將結果存於HI/LO寄存器(2021和2022)中。MADD和MSUB指令對符號數執行運算。MADDU和MSUBU指令對無符號數執行類似運算。
參考圖3A，提供了多項式乘法(MULTP)指令3010的示範性的指令編碼。MULTP指令3010有兩個寄存器欄位，即rs 3011和rt3012，用於指定包含將要參與相乘的多項式的源寄存器。在乘運算完成之後，結果存在HI寄存器2021和LO寄存器2022中。MULTP指令3010還包括一個或多個用於識別將要執行的運算的操作碼3013。在一些實現中，可以不用指令欄位的一部分，例如欄位3014。
在一種實現中，由rs 3011和rt 3012標識的寄存器包含二進位多項式(即模2化簡的多項式係數)。因此，各係數或為「1」或為「0」。在32位寄存器中對多項式進行編碼，其中每一位表示一個多項式係數。例如將多項式「x4+x+1」編碼為「10011」，因為x3和x2的係數為「0」，其餘係數為「1」。
MULTP指令3010允許將兩個多項式相乘。例如，(x4+x+1)(x+1)＝x5+x4+x2+2x+1。模2化簡多項式得到x5+x4+x2+1。如果多項式以上述二進位編碼，那麼同一乘法可表示為(10011)(11)＝110101。
指令和操作數的長度可任意改變；所描述的32位設計僅為一個例子。在32位的實現中，存於rs 3011中的32位字的值可以同存於rt 3012中的32位字的值進行多項式的乘法，即將兩個操作數均作為二進位多項式值，以產生64位的結果。低階32位字可放在LO寄存器2022中，高階32位字結果可放在HI寄存器2021中。在某些實現中，不會發生運算異常。如果由rs 3011和rt 3012所指定的寄存器不包含32位帶符號擴展的值，那麼運算的結果可能無法預料。
參考圖3B，提供了多項式乘加(MADDP)指令3020的示範性指令編碼。MADDP指令3020有兩個參數欄位，即rs 3021和rt 3022，用於指定源寄存器，該源寄存器包含要執行乘法運算並採用多項式加法(異或)加到HI 2021和LO 2022的內容中的多項式。乘法和加法運算完成之後，其結果存在HI寄存器2021和LO寄存器2022中。MADDP指令3020還可包括一個或多個識別所要執行的運算的操作碼3023。在一些實現中，可以不用指令段的一部分，例如欄位3024。
MADDP指令3020執行如上討論的乘法運算。二進位多項式加法類似於按位異或運算。例如，二進位多項式加(x4+x+1)+(x+1)的結果是x4+2x+2。模2化簡係數得到x4，x4可表示為「10000」。
同樣地，指令和操作數的長度可任意改變。在一種實現中，存於rs 3021的32位字的值可與存於rt 3022中的32位字的值作基於多項式的乘法運算，即把兩個操作數均作為二進位多項式的值，從而得到64位結果。然後該結果可採用多項式加法加到HI寄存器2021和LO寄存器2022中的內容中。64位的結果包括低階32位字和高階32位字。低階32位字可放在LO寄存器2022中，高階32位字結果可放在HI寄存器2021中。如果由rs 3021和rt 3022指定的寄存器不包含32位帶符號擴展的值，那麼運算的結果可能無法預料。
多項式算術的實現除可採用硬體(如在微處理器或微控制器內)實現，還可用軟體實現，所述軟體設置在例如經配置用於存儲軟體(即計算機可讀程序代碼)的計算機可用(如可讀的)媒體中。所述程序代碼可使本說明書所公開的系統和技術的功能或構造或者二者均得以實現。例如，這可以通過使用通用程式語言(如C，C++)、硬體描述語言(HDL)(包括Verilog HDL、VHDL、AHDL(Altera HDL)等)、或者其它可用的編程和/或電路捕獲工具來完成。程序代碼可配置在任何已知的計算機可用媒體中，包括半導體、磁碟片、光碟(例如CD-ROM，DVD-ROM)，以及配置為實現於計算機可用(如可讀)傳輸媒體(如載波和任何別的包括數字的、光學的或基於模擬的媒體)中的計算機數據信號。這樣，代碼可通過包括網際網路和企業內部網的通信網絡來傳輸。
應理解，上述系統和技術所完成的功能和/或所提供的結構可以用於程序代碼來實現的核心(如微處理器核心)來表示，並且可轉換成作為集成電路產品一部分的硬體。所述系統和技術還可體現為硬體和軟體的組合。因此，其它實現方式也在以下權利要求範圍之內。
權利要求
1.一種在指令集體系結構中用於執行多項式算術的指令，所述指令為所述指令集體系結構的一部分並包括一個或多個將所述指令識別為用於執行多項式算術運算的指令的操作碼；和一個或多個寄存器標識符；其中，使用所述一個或多個寄存器標識符來執行所述多項式算術運算從而處理所述指令。
2.如權利要求1所述的指令，其特徵在於，所述多項式算術運算為二進位多項式加法。
3.如權利要求2所述的指令，其特徵在於，所述二進位多項式加法採用乘法器來執行。
4.如權利要求1所述的指令，其特徵在於，所述多項式算術運算的結果存於一個或多個結果寄存器中。
5.如權利要求4所述的指令，其特徵在於，所述多項式算術運算包括將由所述一個或多個寄存器標識符標識的所述寄存器中的內容相乘而得到一個中間值；以及將所述一個或多個結果寄存器的內容與所述中間值相加而得到結果。
6.如權利要求5所述的指令，其特徵在於，所述結果存於所述一個或多個結果寄存器中。
7.如權利要求1所述的指令，其特徵在於，所述多項式算術運算的結果存於高階結果寄存器和低階結果寄存器中。
8.如權利要求1所述的指令，其特徵在於，所述多項式算術運算為多項式乘法。
9.如權利要求8所述的指令，其特徵在於，由所述一個或多個寄存器標識符識別的各寄存器包含有多項式。
10.如權利要求9所述的指令，其特徵在於，將每個多項式編碼為係數的二進位表示。
11.如權利要求1所述的指令，其特徵在於，所述指令集包括RISC指令集。
12.一種使用指令來執行多項式算術的方法，所述方法包括接收指令，所述指令包括一個或多個將所述指令識別為用於執行多項式算術運算的指令的操作碼；和一個或多個寄存器標識符；和通過處理所述指令利用所述一個或多個寄存器標識符來執行多項式算術運算。
13.如權利要求12所述的方法，其特徵在於，執行所述多項式算術運算包括執行二進位多項式加法。
14.如權利要求13所述的方法，其特徵在於，執行所述二進位多項式加法包括使用乘法器。
15.如權利要求12所述的方法，其特徵在於還包括將所述多項式算術運算的結果存於一個或多個結果寄存器中。
16.如權利要求15所述的方法，其特徵在於，執行所述多項式算術運算包括將由所述一個或多個寄存器標識符標識的所述寄存器中的內容相乘而得到一個中間值；和將所述一個或多個結果寄存器的內容與所述中間值相加而得到結果。
17.如權利要求16所述的方法，其特徵在於還包括將所述結果存於所述一個或多個結果寄存器中。
18.如權利要求12所述的方法，還包括將所述多項式算術運算的結果存於高階結果寄存器和低階結果寄存器中。
19.如權利要求12所述的方法，其特徵在於，執行所述多項式算術運算包括執行多項式乘法。
20.如權利要求19所述的方法，其特徵在於，由所述一個或多個寄存器標識符識別的媒體各寄存器包含多項式。
21.如權利要求20所述的方法，其特徵在於，將每個多項式編碼為係數的二進位表示。
22.如權利要求12所述的方法，其特徵在於，所述指令為指令集的一部分，並且所述指令集包括RISC指令集。
23.一種包括用軟體實現的微處理器核心的計算機可讀媒體，所述微處理器核心包括用於執行多項式算術的指令，所述指令包括將所述指令識別為一個或多個用於執行多項式算術運算的指令的操作碼；和一個或多個寄存器標識符；其中，通過使用一個或多個寄存器標識符來執行所述多項式算術運算從而處理所述指令。
24.如權利要求23所述的計算機可讀媒體，其特徵在於，所述多項式算術運算為二進位多項式加法。
25.如權利要求24所述的計算機可讀媒體，其特徵在於，所述二進位多項式加法採用乘法器來執行。
26.如權利要求23所述的計算機可讀媒體，其特徵在於，所述多項式算術運算的結果存於一個或多個結果寄存器中。
27.如權利要求26所述的計算機可讀媒體，其特徵在於，所述多項式算術運算包括將由所述一個或多個寄存器標識符標識的所述寄存器中的內容相乘而得到一個中間值；和將所述一個或多個結果寄存器的所述內容與所述中間值相加而得到結果。
28.如權利要求27所述的計算機可讀媒體，其特徵在於，所述結果存於所述一個或多個結果寄存器中。
29.如權利要求23所述的計算機可讀媒體，其特徵在於，所述多項式算術運算的結果存於高階結果寄存器和低階結果寄存器中。
30.如權利要求23所述的計算機可讀媒體，其特徵在於，所述多項式算術運算是多項式乘法。
31.如權利要求30所述的計算機可讀媒體，其特徵在於，由所述一個或多個寄存器標識符識別的各寄存器包含多項式。
32.如權利要求31所述的計算機可讀媒體，其特徵在於，將每個多項式編碼為係數的二進位表示。
33.如權利要求23所述的計算機可讀媒體，其特徵在於，所述指令是指令集的一部分，並且所述指令集包括RISC指令集。
34.一種在公共密鑰密碼系統中用公共密鑰對信息加密的方法，所述方法包括用於執行多項式算術的指令，所述指令包括一個或多個將所述指令識別為用於執行多項式算術運算的指令的操作碼；和一個或多個寄存器標識符；其中，通過使用所述一個或多個寄存器標識符來執行所述多項式算術運算從而處理所述指令。
35.如權利要求34所述的方法，其特徵在於，所述多項式算術運算是二進位多項式加法。
36.如權利要求35所述的方法，其特徵在於，所述二進位多項式加法使用乘法器來執行。
37.如權利要求34所述的方法，其特徵在於，所述多項式算術運算的結果存於一個或多個結果寄存器中。
38.如權利要求37所述的方法，其特徵在於，所述多項式算術運算包括將由所述一個或多個寄存器標識符標識的所述寄存器中的內容相乘而得到一個中間值；和將所述一個或多個結果寄存器的內容與所述中間值相加而得到結果。
39.如權利要求38所述的方法，其特徵在於，所述結果存於所述一個或多個結果寄存器中。
40.如權利要求34所述的方法，其特徵在於，所述多項式算術運算的結果存於高階結果寄存器和低階結果寄存器中。
41.如權利要求34所述的方法，其特徵在於，所述多項式算術運算是多項式乘法。
42.如權利要求41所述的方法，其特徵在於，由所述一個或多個寄存器標識符標識的媒體各寄存器包含多項式。
43.如權利要求42所述的方法，其特徵在於，將每個多項式編碼為係數的二進位表示。
44.如權利要求34所述的方法，其特徵在於，所述指令是指令集的一部分，並且所述指令集包括RISC指令集。
45.一種在微處理器中用於執行多項式算術的指令，所述指令包括一個或多個將所述指令識別為用於執行多項式算術運算的指令的操作碼；和一個或多個寄存器標識符；其中，通過使用所述一個或多個寄存器標識符來執行所述多項式算術運算從而處理所述指令。
46.如權利要求45所述的指令，其特徵在於，所述多項式算術運算是二進位多項式加法。
47.如權利要求46所述的指令，其特徵在於，所述二進位多項式加法採用乘法器來執行。
48.如權利要求45所述的指令，其特徵在於，所述多項式算術運算包括將由所述一個或多個寄存器標識符標識的所述寄存器中的內容相乘而得到一個中間值；和將所述一個或多個結果寄存器的內容與所述中間值相加而得到結果。
49.如權利要求45所述的指令，其特徵在於，所述多項式算術運算是多項式乘法。
50.一種提供了一條或多條用於執行多項式算術的指令的微處理器，所述微處理器包括指令存儲器；執行單元，所述執行單元從所述指令存儲器中取微處理器指令並處理所取指令；和多項式算術單元，如果所取指令是所述一條或多條用於執行多項式算術的指令之一，則所述多項式算術單元在處理所取指令中由所述執行單元使用。
51.如權利要求50所述的微處理器，其特徵在於，所述微處理器還包括乘/除單元。
52.如權利要求51所述的微處理器，其特徵在於，所述多項式算術單元是所述乘/除單元的部件。
53.如權利要求50所述的微處理器，其特徵在於，所述多項式算術單元可用於執行二進位多項式加法。
54.如權利要求50所述的微處理器，其特徵在於，所述多項式算術單元可用於執行二進位多項式乘法。
55.如權利要求50所述的微處理器，其特徵在於，所述微處理器還包括用於存儲來自所述多項式算術單元的結果的結果寄存器。
56.如權利要求55所述的微處理器，其特徵在於，通過執行二進位多項式乘法運算以確定中間結果並將所述中間結果加到所述結果寄存器中，所述多項式算術單元可用於執行二進位多項式乘-加操作。
全文摘要
提供了指令集體系結構(ISA)中的多項式運算指令(3010)。還提供了多項式乘－加(MADDP)指令和多項式乘(MULTP)指令(3013)。
文檔編號G09C1/00GK1503939SQ02808541
公開日2004年6月9日 申請日期2002年2月15日 優先權日2001年2月21日
發明者M·斯特裡貝克, K·D·基斯塞爾, P·帕裡爾, M 斯特裡貝克, 基斯塞爾, 鋃 申請人:美普思科技有限公司