流密码算法、架构与硬件实现研究*

赵石磊, 刘 玲, 黄 海, 徐 江, 刘志伟, 于 斌

哈尔滨理工大学计算机科学与技术学院, 哈尔滨 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 发起并正在进行的轻量级密码标准化项目征集的目标是带有认证功能的轻量级认证加密算法, 一定程度上反映出, 设计和分析基于流密码的轻量级认证加密算法也是目前及未来非常重要的研究方向.