高斯正規基底有限場乘法器具容錯架構之電路設計

Abstract

Miller 與 Koblitz曾提出橢圓曲線密碼系統(ECC)的使用。在相同安全等級下，ECC密碼系統的金鑰位元數要比RSA密碼系統少很多。例如：在相同安全等級下，RSA密碼系統的金鑰需使用1024個位元，但ECC密碼系統只需使用160個位元。ECC密碼系統計算速度比RSA密碼系統快。在計算資源有限的設備下，這項優點使得ECC密碼系統的選用，更具吸引力，如：行動智慧型手機。不幸的是智慧型手機上的密碼系統，對於側通道攻擊非常脆弱，包括植入錯誤式破解密碼攻擊法。 ECC密碼系統高度依賴有限場算術運算，特別是伽羅瓦有限場GF(2m)。這些算術運算包括：加法、乘法、乘法反元素與次方。使用互斥或閘，很容易達成加法運算。乘法反元素與次方，比加法與乘法需要耗用更多的時間，但是可以用迭代式乘法達成。因此一個有效率的有限場乘法器是密碼系統應用的基本工具。 近來發展的植入錯誤式破解密碼攻擊法，是針對對稱式與非對稱式加密演算法，將錯誤植入密碼系統，己經被證明是一種有效的破解密碼攻擊方法。側通道攻擊是使用特定故意植入的錯誤，加諸於加密設備中，進行錯誤分析。只要少量的側通道資訊，就能破解這種設備的安全性。加密設備的錯誤輸出，會引起主動攻擊。因此從攻擊者角度思考，最簡單的保護加/解密電路的方法，就是確定是正確的值，才由加密設備輸出。 針對對稱式與非對稱式密碼系統，很多錯誤偵測的機制被提出來，能輸出正確的值。針對有限場算術運算，也有很多錯誤偵測的機制被發展出來，如：同位元預測函數，時間冗餘方式等。然而一些單一錯誤不能被激發，以及對於現有設備已存在的錯誤無法偵測出來。 超大型積體電路(VLSI)通常不易測試，其理由之一，如：高比率的設備接點，這使得在VLSI晶片中的內部訊號線，可控制性與可觀察性非常有限。為解決此測試問題，可測試性設計是常用的方式。所以我們提出自我偵測交互邏輯位元並列輸入並列輸出高斯正規基底乘法器，來達成即時錯誤偵測、即時錯誤修正與離線測試能力。 更進一步，我們需要即時錯誤偵測與即時錯誤修正能力。針對抵抗植入錯誤式破解密碼攻擊法的有限場算術運算，有很多錯誤偵測的機制被發展出來。雖然現存的高斯正規基底乘法器，具有錯誤偵測的能力，但在同一時間，都僅能容忍一個模組發生錯誤，都無法容忍多個模組發生錯誤。 我們提出位元並列輸入並列輸出高斯正規基底容錯乘法器。其容錯機制是利用資料冗餘技術來達成CED、CEC能力，乘法器並沒有經過特殊電路設計。其容錯設計，可適用於N個模組冗餘，而且系統的穩定度能隨著t增加而增加。Miller and Koblitz proposed the use of Elliptic Curve Cryptosystem (ECC). ECCs can use much smaller key bits than RSA to deliver the same level of security. For instance, ECC with a 160-bit key and RSA with a 1024-bit key have the same security level. ECC computes faster than RSA. These benefits make ECC more attractive than RSA for use as cryptosystems on devices with limited resources such as portable smart phones. Unfortunately, cryptosystems on smart phones are highly vulnerable to side-channel attacks, including fault-based attacks. ECC strongly depends on finite field arithmetic operations, especially GF(2m). These GF(2m) operations include addition, multiplication, multiplicative inversion, and exponentiation. Addition in GF(2m) is easily performed using XOR gates. Multiplicative inversion and exponentiation are much more time-consuming than the other two basic operations, addition and multiplication, but can be performed using iterative multiplications. Hence, efficient implementation of multiplication is fundamental in cryptographic applications. Recently developed fault-based cryptanalysis, in which faults are injected into cryptosystems, has been proven to be an effective method of attack against symmetrical and asymmetrical encryption algorithms. The side-channel attacks using differential fault analysis will typically deliberate fault injection into cryptographic devices. The security on these devices can be broken by a small amount of side-channel information. The faulty outputs of cryptographic devices can lead to an active attack. Hence, simple methods for protecting the encryption/decryption circuitry from an attacker are required to confirm accurate outputs of cryptographic devices. Many error-detection schemes have been presented for symmetrical and asymmetrical cryptosystems to output corrected values. Numerous error-detection schemes have been developed for finite field arithmetic operators. For instances: parity prediction function, time-redundancy approach, etc. However, some single faults are not excited and are undetectable by existing error detection approaches. VLSI circuits are usually very difficult to test for various reasons, such as their high device-to-pin ratio, which seriously limits the controllability and observability of internal signal lines in a VLSI chip. To solve this testing problem, design-for-testability (DFT) approaches are commonly employed. So we propose self-checking alternating logic (SCAL) bit-parallel GNB multiplier with type-t over GF(2m) which has both concurrent error detection and off-line testing capabilities. Furthermore, not only concurrent error detection (CED) but also concurrent error correction (CEC) capabilities are needed. Numerous error-detection schemes have been developed for finite field arithmetic operations for resisting fault-based cryptanalysis. Although existing GNB multipliers with CEC capability can correct errors, they only tolerate one module fault at one time; that is, they cannot tolerate multiple module faults. So we propose a fault-tolerant bit-parallel GNB multiplier with type-t over GF(2m). The proposed fault-tolerant scheme utilizes data redundancy technology to achieve CED and/or CEC capabilities without specially designed circuit in multiplier. The proposed GNB multiplier works in NMR and its system reliability increases as t increases.