流密碼算法、架構與硬件實現研究*

趙石磊, 劉 玲, 黃 海, 徐 江, 劉志偉, 于 斌

哈爾濱理工大學計算機科學與技術學院, 哈爾濱 150080

1 引言

網絡的發展帶來海量的機密信息傳輸, 密碼學在日常生活中發揮著越來越重要的作用, 現代密碼學發展的核心是保護數據信息的機密性、完整性、認證性和不可否認性等[1]. 現代密碼體制一般分為對稱密碼體制和非對稱密碼體制兩大類, 其中對稱密碼又分為分組密碼和流密碼. 流密碼因其具有良好保密性、輕量化和加密速度快等特點得到了廣泛的應用.

流密碼通常用于安全網絡通信中保護通信數據, 尤其在軍事、政府部門等領域. 應用比較廣泛的流密碼算法有: GSM 系統的A5/1 算法[2], 3GPP 標準中用于移動通信的SNOW 3G[3]和ZUC 算法[4],IEEE 802.11 中規定的安全機制WEP、SSL/TLS 等標準協議采用的RC4 算法[5], 用于藍牙加密系統的E0 算法[6], 還有目前應用極為廣泛的ChaCha20 算法[7]等. 谷歌選擇ChaCha20 算法和Bernstein 的Poly1305 消息驗證碼來代替TLS 中的RC4, ChaCha20-Poly1305 AEAD 密碼套件已經在TLS 1.3 中標準化[8], ChaCha20 還被用于FreeBSD、OpenBSD、NetBSD、Linux 內核等各種操作系統[9]. 近年來,隨著通信和網絡飛速發展, 流密碼算法的應用越來越廣泛. 為了滿足現代應用的需求, 具有加密功能和消息驗證功能的認證加密算法和適用于資源受限環境(如射頻識別(radio frequency identification, RFID)標簽、傳感器網絡等) 的輕量級加密算法得到了人們的關注, 基于流密碼設計的認證加密算法和輕量級流密碼算法也成為流密碼研究的重點對象, 一系列此類流密碼算法被提出, 如ACORN、Grain-128AEAD、Fruit-80、WAGE 等.

本文對傳統流密碼算法和近年來提出的基于流密碼算法的認證加密算法和輕量級加密算法進行了分析, 對部分流密碼算法的計算算子進行歸納, 設計一個面向流密碼算法的通用的可重構計算密碼處理架構.本文組織結構如下: 第2 節對流密碼進行梳理, 包括對流密碼相關項目及標準的總結、流密碼設計構建塊的分析、流密碼設計的分類及典型流密碼算法的結構分析等; 第3 節分析流密碼算法的實現思想及其可重構特性, 總結基本運算操作的使用情況, 設計面向流密碼算法的可重構計算密碼處理架構; 第4 節嘗試從不同角度展望流密碼的發展趨勢.

2 流密碼概述

1917 年, Vernam 密碼體制被提出, 后來Mauborgne 基于該體制提出了改進方案, 也就是“一次一密” 密碼體制, 這可以看作流密碼的最早起源[10]. 1949 年, Shannon 證明“一次一密” 密碼體制是理論安全加密體制[11], 但是, 其密鑰流必須完全隨機生成, 長度至少與明文相同, 不能多次使用, 這在實際應用中存在很大困難, 而且, 密鑰的生成、分配和管理是一個不容忽視的問題. 因此, 人們設計了各種流密碼算法來代替“一次一密” 體制[12].

2.1 流密碼相關項目及標準

自現代密碼發展開始, 為了保護信息安全, 各個國家對密碼理論與技術的研究都十分重視, 許多國家和地區發起了很多大大小小的密碼相關的項目、競賽等, 其中相當一部分涉及流密碼算法, 如圖1 所示.

圖1 流密碼相關項目Figure 1 Projects related to stream ciphers

2000 年, 歐盟啟動了NESSIE 項目[13], 該項目為期3 年, 旨在促進美國NIST 組織的分組密碼AES標準化的最后階段, 同時發起了一項獨立的公開呼吁, 通過評估所提交的加密原語, 提出一個各種類型的強大的密碼原語組合. NESSIE 共評估了6 個流密碼算法, 分別是BMGL、Leviathan、LILI-128、SNOW 1.0、SOBER-t16 和SOBER-t32, 但這6 個算法在安全性方面存在一些問題, 最終均未入選[13].

2004 年,由歐盟資助的ECRYPT 宣布了eSTREAM 項目[14],其發起建立在2000 年提交給NESSIE的6 個流密碼算法都失敗的基礎上, 目的是促進設計更適合廣泛應用的高效、緊湊的流密碼. eSTREAM持續到2008 年, 共征集到34 個算法, 經過多次安全和性能評估, 最終選擇了其中7 種. 具體來講, 征集的流密碼算法分為更適合于具有高吞吐量要求的軟件應用的流密碼算法和適用于如有限的存儲、門數、功耗等資源受限的硬件應用的流密碼算法, 最終面向軟件的勝選算法為Salsa20/12、SOSEMANUK、Rabbit、HC-128, 面向硬件的勝選算法為Grain v1、Trivium、MICKEY v2.

2000 年, 日本政府提出了CRYPTREC 項目[15], 其目的是評估和推薦一些密碼算法用于日本電子政務系統. CRYPTREC 密碼表包括三部分: 電子政府推薦密碼表、候選推薦密碼表、監控密碼表, 評估推薦的流密碼算法有KCipher-2、MUGI、Enocoro、MULTI-S01 等. 2013 年, CRYPTREC 成立了輕量級密碼學工作組, 旨在為日本電子政務系統和某些應用程序評估輕量級密碼解決方案. 2015 年, 工作組發布了輕量級密碼學及應用現狀的評估報告, 報告中評估的輕量級密碼算法多數為分組密碼.

2013 年, 由NIST 資助, Bernstein 等人發起了CAESAR 競賽[16], 該競賽主要征集優于AESGCM 且適合廣泛應用的認證加密算法,認證加密算法可以同時實現數據機密性、完整性、數據源認證[17].CAESAR 競賽持續到2019 年, 最終有6 個算法勝出, 分別是針對輕量級硬件應用的Ascon 和ACORN、針對高性能軟件應用的AEGIS-128 和OCB 以及面向縱深防御體系、健壯性良好的Deoxys-II 和COLM.其中AEGIS-128 整體采用了流密碼的框架, ACORN 是基于流密碼設計的認證加密算法[17].

2013 年, NIST 發起了一項輕量級密碼(lightweight cryptography, LWC) 標準化的項目, 以征集、評估和標準化適用于當前NIST 密碼標準性能不可接受的受限環境的輕量級密碼算法, 從而確保受限環境中的機密性、真實性和完整性[18]. 2015 年, NIST 舉辦了首屆輕量級密碼學研討會. 2018 年, NIST 宣布了輕量級密碼標準化的最終提交要求和評估標準, 并呼吁提供相關數據認證加密和可選散列功能的密碼算法. 2019 年, LWC 標準化項目共征集到57 種算法, 第一輪共評估了56 種算法, 但是只有32 種被選中繼續進行第二輪. 2021 年3 月, NIST 宣布ASCON、Elephant、GIFT-COFB、Grain128-AEAD、ISAP、Photon-Beetle、Romulus、Sparkle、TinyJambu、Xoodyak 等10 個輕量級密碼算法入圍決賽, 預計最后一輪持續大約12 個月. 其中入圍決賽的Grain-128 AEAD 是基于流密碼設計的輕量級認證加密算法.

在國內, 2011 年, 我國自主研發的流密碼算法ZUC 正式被3GPP SA 全會通過, 成為3GPP LTE機密性和完整性算法第三套加密標準核心算法, 被采納為國際加密標準, 即第四代移動通信加密標準[4].2018 年, ZUC 算法研制組提出了與ZUC-128 高度兼容的ZUC-256 流密碼算法, 提供5G 應用環境下256 bit 密鑰的安全性[19].

表1 列出了上述幾個項目及涉及到流密碼算法的ISO/IEC 標準的相關信息.

表1 流密碼相關項目及標準化Table 1 Projects and standardization related to stream ciphers

2.2 流密碼的設計結構

一般認為, 一個安全的流密碼所生成的密鑰流序列具備長周期、高線性復雜度、良好統計特性等特點[1], 在設計流密碼時也是以這些特點作為基礎的, 核心部件的安全程度對算法整體安全性產生重要影響.下面介紹流密碼設計中的一些構建塊.

2.2.1 流密碼構建塊

從NESSIE 等標準化項目征集到的流密碼以及公開的各種流密碼來看, 流密碼設計中的構建塊大致包括反饋移位寄存器(feedback shift register,FSR)、布爾函數、狀態表、ARX 結構、細胞自動機(cellular automata, CA)、混沌映射、T 函數、PANAMA 結構、置換濾波生成器、海綿結構、非線性濾波函數、非線性組合函數、鐘控、S 盒、有限狀態機(finite state machine, FSM) 等. 流密碼的構建塊有的用來產生狀態序列, 有的用作非線性部分. 圖2 給出了常見的流密碼構建塊.

圖2 流密碼構建塊Figure 2 Building blocks of stream ciphers

FSR. FSR 是流密碼設計中非常常用的構建塊, 可以生成具有良好特性的狀態序列, 根據反饋函數的不同可以分為線性反饋移位寄存器(linear feedback shift register, LFSR)、非線性反饋移位寄存器(nonlinear feedback shift register,NFSR)、帶進位的反饋移位寄存器(feedback with carry shift register,FCSR). LFSR 有兩種表示形式: Fibonacci LFSR 和Galois LFSR, LFSR 生成的序列是線性的, 不能直接作為密鑰流序列輸出, 需要其他構建塊提高其線性復雜度; NFSR 生成的序列是非線性的, 所以NFSR本身也可作為設計流密碼的非線性構建塊; FCSR 有三種表示形式: Fibonacci FCSR、Galois FCSR 和Ring FCSR[24], FCSR 類似于LFSR, 可以生成具有良好偽隨機性的狀態序列, 另外, FCSR 的狀態轉移函數是非線性的, 生成的狀態序列的線性復雜度較高, 但是FCSR 生成的序列具有可預測性, 所以也不能直接作為密鑰流使用. FSR 的硬件結構簡單, 可以很容易地使用基本邏輯門來構造, 很適合于硬件實現.

布爾函數. 布爾函數是流密碼中非常重要的構建塊, 1917 年, Vernam 密碼中就出現了布爾邏輯結構,布爾函數在LFSR 中的應用是其在流密碼中真正作為研究對象的始源[25]. Berlekamp-Massey 算法的提出使人們意識到LFSR 產生的狀態序列的線性性質對密碼分析沒有任何免疫力, 需要提高LFSR 狀態序列的線性復雜度才能滿足流密碼的安全性. 布爾函數的性質使其在流密碼的設計與分析中起著關鍵作用,其主要性質歸納起來有平衡性、對稱性、高代數次數、高非線性、相關免疫性、彈性階、自相關性、擴散性等[26]. 布爾函數包括單輸出布爾函數和多輸出布爾函數, 流密碼中用于提高LFSR 狀態序列線性復雜度的非線性濾波函數和非線性組合函數, 對其研究可以歸結為對布爾函數的研究; 另外, 在流密碼中對用于提高非線性的S 盒的研究可歸結為對多輸出布爾函數的研究[27]. 不同密鑰流生成器中布爾函數應該滿足不同的性質才能保證生成的密鑰流具有更高的安全性, 在進行流密碼設計時, 可以選擇目前公認的各方面性質較為平衡的布爾函數作為構建塊[28]. 對NFSR 中非線性反饋函數的研究是布爾函數的一個很重要的研究方向[25].

狀態表. 將流密碼的狀態序列存儲到狀態表中, 由非線性函數更新狀態表中的狀態序列. 狀態表作為設計流密碼的構建塊, 其軟件實現速度快、硬件存儲消耗較高.

ARX 結構. ARX 是指模加(modular add)、循環移位(rotation) 和邏輯異或(xor) 三種運算, 三種運算的實現速度較快, 可以將ARX 三種混合運算應用到流密碼的設計中.

CA.1985 年,Wolfram 將CA 應用在密碼學領域[29],自此CA 在密碼學方面的研究逐漸開展[30–32].CA 是自動機理論中研究的一種離散計算模型, 由規則的細胞網格組成, 每個細胞都處于有限數量的狀態之一, 通過某種固定規則, 根據細胞的當前狀態和其鄰域中的細胞的狀態來確定每個細胞的新狀態, 二維細胞自動機可以用來構造偽隨機數發生器[33].

混沌映射. 1982 年, OISHI 等將混沌系統應用到流密碼中[34], 混沌映射具有明顯的偽隨機性和不規則狀態, 可以使用混沌映射的控制參數和初始條件作為流密碼的密鑰, 從更廣泛的角度來看, 混沌映射與密碼系統之間的相似性是設計基于混沌映射的流密碼算法的主要動機, 混沌理論可以很好地對對稱密碼中的擴散和混淆進行建模[35].

T 函數. T 函數是Klimov 和Shamir[36]提出的一種能夠在任意長的字上混合布爾運算和算術運算的密碼構建塊, 屬于一類可逆映射, T 函數因其雙射特性可以用于流密碼中產生狀態序列[37], 可以在軟件上快速實現, 利用T 函數生成的狀態序列具有長周期、良好的非線性和非代數性, Klimov 和Shamir 指出T 函數可以作為LFSR 的替代, 作為基于軟件的密鑰流生成器的構建塊[36].

PANAMA 結構. 1998 年, Daemen 提出了流密碼算法PANAMA[38], PANAMA 采用了一種新的設計結構, PANAMA 結構的內部狀態機由內部狀態S(狀態a和緩沖區b) 及其更新函數F(狀態a和緩沖區b的更新函數分別為ρ和λ) 組成[38]. 由(a,b)、(ρ,λ) 和從S提取輸出序列的輸出濾波器f組成的密鑰流生成器如果滿足以下條件, 則稱為PANAMA 式密鑰流生成器:ρ包括SPN 變換, 類似于分組密碼的輪函數, 并使用緩沖區b的一部分作為參數a(t+1)=ρ(a(t),b(t));λ是線性變換, 并使用狀態a的一部分作為參數b(t+1)=λ(b(t),a(t));f每輪提取輸出狀態a的一部分(通常不超過1/2)[39].

置換濾波生成器. 置換濾波生成器是在Eurocrypt 2016 上提出的一種新的流密碼結構, 它由三部分組成: 用于存儲密鑰的寄存器、由偽隨機數生成器(由公共向量初始化) 參數化的置換生成器, 生成密鑰流的濾波函數. 與濾波生成器相比, 置換濾波生成器中LFSR 被密鑰寄存器替換, 換句話說, 寄存器不再通過LFSR 更新, 而是使用偽隨機位置換進行更新, 也就是在每個周期, 即每次濾波函數輸出一位時, 偽隨機置換被應用于寄存器, 并且非線性濾波函數作用于被置換的密鑰寄存器的輸出. 這種結構的優點是始終將非線性濾波函數直接作用于密鑰位, 使得輸出噪聲始終是一個常數, 并且具有很強的同態能力[40]. 從目前的分析來看, 這類結構對濾波函數的選擇要求很高, 否則很容易被分析而導致大量密鑰信息泄漏[41].

海綿結構. 海綿結構是Bertoni 和Daemen 在ECRYPT 2007 上提出的一種模型[42], 是一種基于定長置換和填充規則的操作模式, 海綿結構構建將可變長度的輸入映射到可變長度輸出的函數, 這樣的函數稱為海綿函數. 海綿函數是具有固定輸出長度的散列函數和具有固定輸入長度的流密碼的泛化, 它通過迭代地應用內部置換來對有限狀態進行操作, 該內部置換與輸入數據或輸出數據進行交錯[43]. 海綿函數使用隨機置換, 接受可變長度的輸入和輸出, 這一點使其適合作為設計流密碼的構建塊[44]. 用作流密碼構建塊時, 輸入是初始密鑰和初始向量, 然后在壓縮階段輸出得到密鑰流. 海綿結構的優點是設計相對簡單, 靈活性較高[43].

非線性濾波函數、非線性組合函數、鐘控、S 盒、FSM 一般用作流密碼非線性部分的構建塊, 非線性部分主要用來引入或提高狀態序列的非線性. 非線性濾波函數、非線性組合函數、鐘控、FSM 主要是針對基于LFSR 設計的流密碼而引入的, 目的是為了降低LFSR 序列線性的弱點, 引入非線性. 非線性濾波函數和非線性組合函數主要通過作用于LFSR 序列來破壞其線性特性; 鐘控是通過對LFSR 進行不規則的時鐘控制來提高其非線性; FSM 是計算的數學模型, 在任何給定時刻都可以處于有限狀態之一, FSM由其狀態列表、初始狀態和觸發每次轉換的輸入來定義, 可以根據某些輸入從一種狀態轉換為另外一種狀態[45]; 對稱密碼算法中最常見的混淆方式就是利用S 盒, 因為S 盒輸入的微小變化就會導致輸出的復雜變化, 許多流密碼也使用S 盒來引入非線性.

2.2.2 流密碼設計分類

流密碼由狀態更新函數和輸出函數組成, 流密碼的狀態序列在加密期間不斷更新, 使得被加密消息在不同位置的比特以不同的狀態加密, 輸出函數根據狀態序列生成密鑰流序列, 并執行加密和解密[27]. 狀態更新的基本要求是應以足夠大的周期生成狀態, 利用流密碼的構建塊可以設計狀態更新函數生成狀態序列, 然后利用非線性構建塊提高狀態序列的線性復雜度, 以生成高安全級別的密鑰流序列[46]. 目前流密碼主流的設計結構有基于LFSR 的設計、基于NFSR 的設計、基于狀態表驅動的設計、基于分組密碼的設計幾類. 圖3 給出了流密碼的設計分類.

圖3 流密碼的設計分類Figure 3 Design classification of stream ciphers

基于LFSR 的設計. 20 世紀40 年代電子計算機被發明, 計算技術的進步使密碼學家可以使用比計數器更安全的操作來設計流密碼, 基于LFSR 設計的流密碼就出現在此時期[46]. Rueppel[27]將密鑰流生成器分為驅動部分和非線性部分, 驅動部分主要用來將初始密鑰擴散成具有良好周期性和統計特性的狀態序列, 非線性部分對驅動部分的輸出序列進行非線性運算, 提高其線性復雜度和不可預測性, 從而生成最終密鑰流. 驅動部分一般利用LFSR 產生狀態序列, LFSR 序列為線性, 則非線性部分采用各種非線性構建塊(如非線性濾波函數、非線性組合函數等布爾函數或時鐘控制等) 來掩蓋其線性, 以生成高度非線性的密鑰流. 根據所采用的非線性構建塊的不同, 出現了非線性濾波生成器、非線性組合生成器、鐘控生成器等各種密鑰流生成器[47]. 如何利用非線性布爾函數掩蓋LFSR 序列的線性是保證這類流密碼安全性的首要目標, 這類流密碼的結構代表了傳統流密碼的設計思想, 對其理論分析也比較成熟. 圖4 所示為常見的基于LFSR 的流密碼算法.

圖4 基于LFSR 的流密碼算法Figure 4 Stream cipher algorithms based on LFSR

基于NFSR 的設計. 自eSTREAM 項目以來, 出現了很多流密碼的設計理念與方法, 其中比較典型的一類是基于NFSR 設計的流密碼. 這類設計是把NFSR 的非線性反饋與非線性輸出相結合來提供良好的序列特性和安全性[12]. 在硬件上, NFSR 比LFSR 稍復雜, NFSR 對密碼分析的抵抗能力較強, 基于NFSR 設計的流密碼的安全級別取決于分析設計本身的難度, 由于目前還沒有簡單且精確的準則來構建強大的非線性布爾函數, 所以較難設計出性能良好的NFSR[46]. 目前關于NFSR 的理論研究還比較少, 還沒有統一的模式對這類流密碼算法進行安全性分析[25]. 對NFSR 的非線性反饋函數的研究是一個值得深入的研究方向. 圖5 所示為常見的基于NFSR 的流密碼算法.

基于狀態表驅動的設計. 基于狀態表驅動設計流密碼的思想來源于1987 年Rivest 設計的RC4 流密碼算法, 該類設計是利用狀態表的轉換和選擇來構造流密碼, 換句話說, 就是將很多操作進行預計算, 產生隨機排列, 存儲在狀態表中, 便于在計算中使用. 基于狀態表驅動設計的流密碼算法包含較大的狀態表且狀態隨時間持續變化, 所以硬件實現代價較高, 但是軟件實現速度較快. 圖6 所示為常見的基于狀態表驅動的流密碼算法.

基于分組密碼的設計. 基于分組密碼的設計可以利用成熟的分組密碼部件、結構, 或者利用已有的成熟的分組密碼理論來構造流密碼[12]. 可以利用分組密碼的某些操作模式生成密鑰流序列, 比如當分組密碼以輸出反饋模式、密文反饋模式、計數器模式運行時可以用作流密碼使用; 可以利用分組密碼的設計結構, 比如采用分組密碼的Feistel 結構、SPN 結構等; 可以利用分組密碼的非線性部件S 盒; 可以利用分組密碼中行移位、列混淆的設計思想; 可以直接輸出分組密碼的某些中間狀態, 通過簡單運算作為密鑰流輸出[27,41]. 基于分組密碼設計的流密碼算法軟件實現速度很快, 這類流密碼算法的內部狀態較大, 而且不存在移位寄存器, 很難用傳統的分析方法對其進行評估[12]. 圖7 所示為常見的基于分組密碼設計的流密碼算法.

圖5 基于NFSR 的流密碼算法Figure 5 Stream cipher algorithms based on NFSR

圖6 基于狀態表驅動的流密碼算法Figure 6 Stream cipher algorithms based on state table driver

圖7 基于分組密碼設計的流密碼算法Figure 7 Stream cipher algorithms based on block cipher

流密碼的設計方法靈活多變, 設計結構也趨于多樣化, 除了上述主流設計結構外, 還有一些基于其他結構設計的流密碼. 如基于FCSR 的流密碼、基于CA 的流密碼、基于混沌映射的流密碼、基于T 函數的流密碼、基于PANAMA 結構的流密碼、基于置換濾波生成器的流密碼、基于海綿結構的流密碼等.

按時間順序對基于上述不同設計結構的典型流密碼算法進行舉例, 包括算法的結構、初始密鑰Key及初始向量IV 的長度等. 如表2–6 所示.

流密碼通過不斷變化的內部狀態進行采樣來生成密鑰流, 該狀態通常是在初始密鑰Key 和IV 的作用下進行初始化. 大多數流密碼算法的初始密鑰長度集中在80 bit、128 bit、256 bit. 傳統加密主要用于高端設備領域, 如服務器、臺式計算機、平板電腦、智能手機等[48], 傳統流密碼算法的初始密鑰長度一般為128 bit 或256 bit. 現在, 隨著物聯網的發展, 像RFID 標簽、嵌入式系統、工業控制器、無線傳感器網絡、智能卡等小型計算設備變得越來越普遍, 傳統加密很難在這類資源受限的設備中實現, 所以對輕量級加密的需求明顯增加, 輕量級加密是專門為資源受限的設備量身定制的解決方案, 由于許多受限設備的性質, 比如有限的存儲、門數等, 在輕量級應用中, 功耗和能耗是相關的性能指標, 而且高吞吐量可能不是主要的設計目標, 大多數應用程序需要中等吞吐量. 輕量級流密碼算法的初始密鑰長度相對較短, 通常為80 bit. eSTREAM 項目中面向硬件的勝選算法Grain v1、Trivium、MICKEY 2.0 可以看作是出現較早的適用于受限硬件設備的輕量級流密碼算法.

表2 基于LFSR 的流密碼算法Table 2 Stream cipher algorithms based on LFSR

表3 基于NFSR 的流密碼算法Table 3 Stream cipher algorithms based on NFSR

表4 基于狀態表驅動的流密碼算法Table 4 Stream cipher algorithms based on state table driver

表5 基于分組密碼設計的流密碼算法Table 5 Stream cipher algorithms based on block cipher

表6 基于其他結構設計的流密碼算法Table 6 Stream cipher algorithms based on other structures

3 流密碼算法的實現

密碼處理器作為密碼算法的實現載體, 為信息安全提供基礎設施服務[87]. 流密碼算法的實現包括硬件實現和軟件實現. 對于嵌入到系統軟件的加密程序而言, 軟件實現效率更高; 對于高速網絡中數據流的傳輸而言, 硬件實現效率更高. 流密碼算法的實現主要利用實現密碼應用的各類集成電路載體實現, 包括通用處理器(general purpose processor, GPP)、專用集成電路(application specific integrated circuit,ASIC)、可編程邏輯門陣列(field programmable gate array, FPGA)、可重構計算密碼處理器幾種形式.利用GPP 可以實現多種流密碼算法, 靈活性較高, 但GPP 基于指令流驅動, 實現速度比較慢. ASIC 主要針對特定目標流密碼算法設計專用的硬件電路來實現, 速度快、功耗低、面積小, 但一旦流片, 將無法改變電路的功能, 靈活性較差, 安全性低. 利用FPGA 可以實現各種流密碼算法, 靈活性很高, 速度比較折中, 介于GPP 和ASIC 之間, 但FPGA 的配置信息比較繁瑣, 不能實時改變, 而且資源有限, 資源豐富的FPGA 成本又比較高. 隨著網絡信息技術的發展, 一個常用的信息安全解決方案可能會用到很多種密碼算法, 為了支持應用或協議中盡量多的流密碼算法, 需要密碼處理器有足夠的靈活性, 此外, 芯片設計的兩個核心指標是性能和功耗, 性能功耗比, 也就是能量效率, 自然成為比純粹的性能更為合理嚴格的指標, 安全性也是密碼處理器中一項很重要的指標. 可重構計算密碼處理器是一種性能、功耗、速度、靈活性合理折中的密碼算法實現方式, 主要面向領域, 面積有時會冗余, 但現代工藝允許不關心面積冗余這一弊端[88].所以從應用和協議的角度來看, 在保證一定處理速度的情況下又能夠滿足一個信息安全解決方案對多種流密碼算法的需求, 可重構計算密碼處理器是一種很好的選擇. 表7 總結了上述流密碼實現方式的優缺點.

表7 GPP、ASIC、FPGA、可重構計算密碼處理器比較Table 7 Comparison of GPP, ASIC, FPGA, and reconfigurable computing cryptographic processor

3.1 流密碼算法特征分析

雖然根據設計方法和結構可以將流密碼細分為很多類, 但很多流密碼算法有相似的密碼處理結構和操作類型, 所以不同的流密碼算法存在大量的共性邏輯. 如前所述, 主要的設計結構有基于LFSR 的流密碼算法、基于NFSR 的流密碼算法、基于狀態表驅動的流密碼算法和基于分組密碼設計的流密碼算法, 對主流的四類設計中典型的流密碼算法如A5/1、E0、Grain、Trivium、ZUC、SNOW、RC4、ChaCha20等進行研究, 分析算法狀態更新和密鑰生成所采用的構建塊, 從利用可重構計算思想實現流密碼算法的角度出發, 對算法的結構特征、操作特征和計算算子進行總結歸納, 發現它們有多種類型的共性邏輯, 包括LFSR、NFSR、邏輯運算(包括異或、與、或、非)、算術運算(包括加法、模加、模乘)、移位(包括邏輯左移、邏輯右移、循環左移、循環右移)、S 盒、有限域GF(2n) (n=8,16,32,64) 乘法運算等. 對有限域GF(2n) 乘法運算進一步分解, 可以得到更簡單、重用程度更高的基本操作, 如S 盒、異或、加法、乘法、移位等[87]. 如表8 所示對典型流密碼算法特征進行了分析總結, 其中操作位寬和輸出位寬以bit 為單位;nXOR 表示n-bit 按位邏輯異或;nAND 表示n-bit 按位邏輯與;nOR 表示n-bit 按位邏輯或;nNAND表示n-bit 按位與非;表示循環右移;表示循環左移;?表示邏輯右移, S 盒一列中n×m表示n-bit 輸入,m-bit 輸出的查找表運算.

通過分析典型流密碼算法, 對其狀態更新部分和密鑰生成部分的結構進行分解, 可以分為有限域GF(2) 和GF(2n) 兩種情況進行分析: GF(2) 上流密碼算法的數據操作位寬一般為1 bit, 一次產生1 bit 密鑰, 主要計算算子為邏輯運算, 包括邏輯異或、邏輯與等. GF(2n) 上流密碼算法的數據操作位寬一般為字節或字節的整數倍, 這些流密碼算法的非線性部分一般由多種非線性變換相互結合, 涉及到的計算算子較復雜, 包括邏輯運算、算術運算、移位、S 盒等. 整體來看, 基于LFSR 和基于NFSR 的流密碼算法用到了FSR 構建塊, 不同流密碼算法FSR 的個數和級數不同, FSR 個數大多不超過4, 級數大多不超過160 bit, FSR 總容量不超過1024 bit; 流密碼算法中的邏輯運算和算術運算的操作粒度大多為單比特、字節或字節的整數倍, 一般為1～32 bit; 很多流密碼算法使用了邏輯移位和循環移位, 移位的位數一般不超過32 bit; 不同流密碼算法中的S 盒的輸入輸出位寬不同, 輸入位寬以8 bit 居多, 輸出位寬差別較大,主要包括4 bit、8 bit、16 bit、32 bit 四種.

3.2 可重構計算流密碼處理架構

根據對不同流密碼算法的結構特征、操作特征和計算算子的統計, 分析數據存儲、重構粒度、運算單元(process element, PE)、互連網絡、運算單元陣列、配置信息等關鍵技術, 設計一種通用的面向四類主流設計結構的流密碼算法的可重構計算密碼處理架構, 包括可重構數據通路和可重構控制器兩部分. 可重構數據通路負責流密碼數據流的處理, 可重構控制器負責可重構數據通路的配置切換和調度[87]. 所設計的可重構計算流密碼處理架構結構框圖如圖8 所示.

可重構數據通路包括可重構反饋移位寄存器陣列、抽頭抽取結構、可重構運算單元陣列、配置接口、反饋數據選擇、密鑰流數據選擇、輸入數據存儲器、密鑰流存儲器幾個主要模塊. 各模塊設計及功能具體描述如下:

可重構反饋移位寄存器陣列主要用來存儲流密碼的狀態向量, 共包含32 個32 bit 的移位寄存器單元陣列, 可以根據配置信息實現寄存器單元之間不同方式的級聯以及不同方向、不同粒度的移位, 支持1 bit、8 bit、16 bit、32 bit 一共4 種操作粒度. 可重構反饋移位寄存器陣列的反饋輸入為可重構運算單元陣列的輸出數據.

表8 流密碼算法特征分析Table 8 Analysis of algorithm characteristics of stream ciphers

圖8 可重構計算流密碼處理架構結構框圖Figure 8 Block diagram of reconfigurable computing stream cipher processing architecture

抽頭抽取結構負責從可重構反饋移位寄存器陣列中抽取數據并送入可重構運算單元陣列進行運算, 共32 個. 可重構反饋移位寄存器陣列中每個32 bit 的移位寄存器單元陣列為一組, 共32 組, 每個抽頭抽取結構先從32 組32 bit 數據中抽取出一組, 然后根據具體流密碼算法的操作粒度, 對抽取出的32 bit 數據進行再一次抽取選擇, 比如操作粒度為1 bit 時, 用一個32 選1 的多路選擇器抽取出任意1 bit, 高位補0拼為32 bit. 通過這種結構實現任意不同位置抽頭的抽取.

可重構運算單元陣列是可重構計算流密碼處理架構中的核心模塊, 主要負責流密碼中的數據運算. 其結構框圖如圖9 所示.

圖9 可重構運算單元陣列結構框圖Figure 9 Structure diagram of reconfigurable operation unit array

由12 行4 列PE 和PE 行之間的互連網絡組成, 根據對流密碼計算粒度的統計分析將PE 的重構粒度設計為32 bit, 以更好的滿足不同操作位寬的流密碼. 運算單元的設計包括邏輯運算單元(logical operation unit, LOU)、算術運算單元(arithmetic operation unit, AU)、移位單元(shift unit, SU)、查找表單元(lookup table unit, LTU)4 種不同的功能單元. 每個PE 都包含LOU、AU、SU, 因為在流密碼中S 盒使用頻率較低而且面積較大, 所以每4 行PE 作為一個PE 組共享一個LTU. LOU 有四個輸入, 可以實現四輸入中任意兩個輸入操作數最多三級的任意基本邏輯操作, 包括異或(XOR)、與(AND)、或(OR) 等; AU 有四個輸入, 由一個32 位的加法器組成, 可以實現模28、模216、模232、模231-1幾種基數的加法運算; SU 有三個輸入, 由兩個32 位的桶形移位器組成, 可以實現最多64 bit 輸入操作數的32 bit 以內任意位數的邏輯左移、邏輯右移、循環左移、循環右移; LTU 有三個輸入, 由4 個8 bit 進8 bit 出的S 盒運算單元組成, S 盒運算單元用SRAM 實現, 支持最大8 bit 輸入, 32 bit 輸出的查找表運算. 因為異或邏輯在流密碼中使用非常頻繁, 所以為了加快計算效率, 在AU、SU、LTU 的輸入和輸出添加了異或操作, 從而在進行算術運算、移位或查找表運算之前或之后可以與另一個輸入操作數進行異或操作. 每個PE 有4 個32 bit 的輸入, 1 個32 bit 的輸出, PE 的輸入可以來自于抽頭抽取結構的輸出數據、與之相鄰上一行4 個PE 的輸出數據、LTU 的輸出數據. 另外為了在PE 之間可以實現流水操作, 在每個PE 的輸出端設置一個32 bit 的寄存器用于緩存每個PE 的計算結果, 如果需要流水處理, 就寄存一級, 如果不需要就對寄存器進行旁路. PE 行之間的互連網絡采用CrossBar 方式進行互連, 實現相鄰行與行之間的全互連.

該可重構數據通路的緩存結構包括輸入數據存儲器和密鑰流存儲器, 均連接外部數據接口, 負責與外部數據的交互. 輸入數據存儲器用來存儲從外部數據接口讀取到的要參與運算的數據, 可重構運算單元陣列完成運算后, 如果在流密碼的狀態更新階段, 反饋數據選擇模塊從PE 輸出端選擇要反饋數據, 反饋回可重構反饋移位寄存器繼續參與狀態的更新; 如果在流密碼的密鑰流生成階段, 密鑰流數據選擇模塊從PE 輸出端選擇密鑰流數據存儲到密鑰流存儲器并將其輸出到外部接口. 可重構運算單元陣列在進行流密碼算法的數據流運算操作時產生的中間結果數據也可以反饋回可重構運算單元陣列進行緩存, 需要時再通過抽頭抽取結構抽出.

可重構控制器中配置管理單元接收并解析外部配置信息, 生成內部配置信息和頂層控制信號. 配置存儲器用于保存內部配置信息. 配置接口訪問配置存儲器并將內部配置信息輸出到可重構數據通路[87], 完成對可重構反饋移位寄存器陣列、抽頭抽取結構、可重構運算單元陣列的具體配置. 同時, 配置接口輸出可重構數據通路的狀態信號, 根據狀態信號產生控制碼, 控制可重構運算單元陣列的資源調度.

對于流密碼的數據相關性而言, 從整個算法加解密的層次來看, 流密碼算法是串行執行的, 因此不能將任務分解成多個子任務并行執行; 從算法的內部結構來看, 流密碼算法各個構建塊之間存在讀后寫相關,比如兩個反饋移位寄存器級聯時, 下一級寄存器要先讀取到上一級寄存器的值, 并更新本身狀態后, 上一級寄存器才能更新自己的狀態. 對于流密碼的并行性而言, 流密碼算法各個構建塊之間存在并行性, 像基于LFSR 的流密碼算法的反饋移位寄存器和非線性部分之間是并發執行的, 各個構建塊都需要同時執行,并更新本身的狀態, 因此在利用可重構計算密碼處理器實現流密碼時可以開發其并行性[87].

4 發展趨勢

從算法設計的角度來看, 傳統面向比特的流密碼已經很難滿足當今通信應用的需求, 特別是在軟件實現方面, 為了提高處理器軟件中密鑰流的生成速度, 流密碼算法逐漸傾向于面向字設計. 設計結構也逐漸多樣化, 越來越多的流密碼算法不僅基于某一種結構, 而是將不同結構結合起來進行設計, 以便提高安全性, 比如基于LFSR 的流密碼, 也會在非線性部分利用一些分組密碼的組件, 像S 盒等. 流密碼算法設計的關注點主要集中在所采用的密碼構建塊和基本操作上, 本質上遵循Shannon 的混淆和擴散范式, 在設計流密碼時既要保證能夠對現有攻擊具有免疫性, 又要保證易于評估其他密碼屬性, 還要使設計在安全性、性能和資源需求之間達到良好的平衡[48].

從算法實現的角度來看, 在實現流密碼算法時, 要在所需的性能和資源之間進行權衡, 性能主要指功耗、能耗、延遲、吞吐量等方面; 硬件實現所需的資源通常指面積、等效門或邏輯塊, 軟件實現所需的資源通常體現在寄存器的數量、RAM 和ROM 的規模上, 資源需求即成本, 因為增加更多的門或者內存會增加設備的生產成本. 從流密碼算法加解密的角度來看, 算法是串行的, 從其內部結構來看, 算法的各個組件之間存在并行性, 利用可重構計算密碼處理器實現時可以開發流密碼算法的并行性.

從算法發展的角度來看, 基于流密碼算法的輕量級認證加密算法的設計、分析與實現是一個熱點. 近年來對稱密碼界將注意力集中在更有效地提供消息加密和認證的專用認證加密方案上[17]. 另外, 如何在資源受限的設備上使用安全有效的密碼算法是一個具有挑戰性的問題, 目前關于輕量級密碼算法還沒有嚴格的標準, 但輕量級密碼算法的常見表現是對目標設備的資源要求很低[48]. 所以, 為了滿足物聯網時代廣泛應用的資源受限設備, 輕量級密碼算法的設計和分析也是一個研究熱點. 由NIST 發起并正在進行的輕量級密碼標準化項目征集的目標是帶有認證功能的輕量級認證加密算法, 一定程度上反映出, 設計和分析基于流密碼的輕量級認證加密算法也是目前及未來非常重要的研究方向.