高级算法

2024-06-15

高级算法（精选4篇）

高级算法篇1

摘要：介绍了AES数据加密结构,以及相关的有限域的知识及简单运算,提出了一种用FPGA高速实现AES算法的方案。AES加密算法密码模块作为安全保密系统的重要组成部分,其核心任务就是加密数据。AES以其高效率、低开销、实现简单等特点被广泛应用于密码模块的研制中。

关键词：AES,Rijndael,分组加密算法,FPGA,轮变换

1. 引言

随着计算机和通信网络的广泛应用,信息的安全性已受到人们的普遍重视。信息安全已不仅仅局限于政治、军事以及外交等领域,而且也与人们的日常生活息息相关。现在密码学理论和技术已得到了迅速发展,它是信息科学和技术中的一个重要研究领域。目前随着密码分析技术的不断发展,超期服役的DES算法已被攻破,DES密钥长度为56位,存在密钥过短的缺陷,3DES是一种由DES衍生出来的算法,虽然增加了密钥长度,但3DES的加密和解密时间消耗较大。Rijndael数据加密算法成为AES算法的标准以来,经过多年来的分析和测试,至今没有发现AES的明显缺点,也没有找到明显的安全漏洞。标准的商品化CPU和DSP无法跟上数据加密算法的计算要求。基于FPGA高度优化的可编程的硬件安全性解决方案提供了并行处理能力,并且可以达到所要求的加密处理性能基准。

2. 算法说明

2.1 算法概要

AES是分组密钥,算法输入128位数据,密钥长度也是128位。用Nr表示对一个数据分组加密的轮数。每一轮都需要一个与输入分组具有相同长度的扩展密钥Expandedkey(i)的参与。由于外部输入的加密密钥K长度有限,所以在算法中要用一个密钥扩展程序(Keyexpansion)把外部密钥K扩展成更长的比特串,以生成各轮的加密和解密密钥。

Rijndael算法由加密、解密和密钥编排三个算法组成。加密算法是把明文经过Nr+1轮变换得到密文,AES具有128比特的分组长度,对于128,192,256位密钥长度的Rijndael算法,Nr分别取10,12,14。密钥编排是对初始密钥进行扩展以产生各轮变换所需要的轮密钥。

2.2 AES密钥调度

密钥调度包括两个部分:密钥扩展和轮密钥选取。密钥扩展是指把Nk比特初始密钥映射为所谓的扩展密钥,而轮密钥选取则是从扩展密钥中选择出Nb比特的轮密钥。

2.3 以加密为例的轮变换

轮变换由字节替代、字节位移、列混合和轮密钥加法4个模块组成。字节代替(ByteSub)变换是一个非线性的字节代替,它在每个状态字上独立地进行运算。代替表(或S盒)是可逆的,且是由两个变换的合成而构造出来的。对于128字节的密钥长度的AES轮变换的字节移位可见图2。

列混合对状态矩阵的列独立进行变换,将状态的列看作是有限域GF(28)上的多项式a(x),与多项式c(x)=03x3+01x2+01x+02相乘(模x4+1)。令b(x)=c(x)×a(x),写成矩阵形式为:

3. AES的FPGA实现

由AES原理可以看出,通过FPGA实现AES算法,各部运算可以分解为最基本的查找和异或。

用伪代码表示的Rijndael加密算法,如提前进行密钥扩展,Rijndael加密算法描述可变为:

本设计是用FPGA实现AES加密/解密。命名为wb_aescomtroller.V文件包含数据输入输出,接口转换,控制;其它的各个模块均以独立的V文件描述,如sbox.V文件描述的是字节替换表模块(Byte Substitution,S-盒)。以下以加密为例,详述其过程。

加密开始时,首先由输入密钥开始密钥扩展,由此也决定将要进行循环的轮数。根据输入密钥长度的不同,进行不同轮数的循环。首先是执行密钥加(RoundKey-Add),之后进行Nr轮的运算(最后一轮没有列混合)。

每一轮的开始首先是轮密钥加(RoundKey-Add),本设计中,用了一个128*8的存储器,在加密模块开始时(即数据输入时)同时开始工作,扩展后的密钥存入寄存器组,通过输入密钥的长度和计数器来决定当前输入的、将要进行轮密钥加的128位密钥。字节替换(Byte-Sub)用查找表的方式实现。列混合(Mix-Col)主要是XTime和xor运算,可以分为最简单的xor运算。明文(plaintext)经过Nr轮的运算,即得到密文(ciphertext)输出。

在ModelsimSE6.0软件仿真平台上,编译project里面的所有V文件,经仿真,把工程上的测试文件test_bench_top加入wave,仿真输出波形,可见图6和图7所示。

因此,结合上图5和图6,可以发现384比特的tmo序列的前面128bits被提取为密文;中间128bits作为明文以及加密输入码;后面的128bits作为密钥。仿真输出后,发现加密后输出码流test_out与ciph一致,从加密码流再经解密的输出码流test_out2与最初输入码流plain一致,即设计输出结果符合整个设计要求,AES算法得以实现,结果正确。

4. 结束语

本文讨论了用FPGA实现AES算法的设计方案,重点详述了AES算法的原理以及FPGA实现步骤。通过用Verilog语言编写实现程序,在ModelSim SE6.0软件平台上进行编译、仿真,使得以Rijndael数据加密算法的AES高级加密标准得到很好的体现。实验结果表明,本设计基于FPGA可编程逻辑器件的实现方法提供了并行处理能力,达到设计所要求的加密处理性能基准。

参考文献

[1]夏宇闻.Verilog数字系统设计教程(第二版)[M].北京航空航天大学出版社,2008.

[2]储奕锋.AES算法的FPGA实现[J].开发研究与设计技术.2007:191-193.

[3]张延伟等.VerilogHDL程序设计实例详解[M].人民邮电出版社,2008.

[4]吴鹏,李开成.基于FPGA的Rijndael算法实现的研究[J].计算机与通信信号.2007(120):46-48.

[5]唐金艺.AES算法FPGA实现分析[J].计算机安全.2008(6):14-20.

[6]苏国强,郑小平等.基于低成本FPGA的AES算法实现[J].甘肃高师学报.2009(14):17-19.

[7]刘腕,何道君等,FPGA设计与应用[M].清华大学出版社,2006.

高级算法篇2

1、负责分析仪器产品的应用算法设计与实现，并最终在产品上调试以达到指定目标;

2、跟踪市场及用户对产品的需求变化，对产品算法进行持续改进，满足客户要求;

3、设计相关应用开发实验，并对实验数据进行分析;

4、对相关领域的新算法进行调研、跟踪学习，并提出产品算法开发规划建议。

任职要求：

1. 分析化学、计算机、数学、仪器科学及相关专业统招硕士及以上学历，本科毕业需3年以上相关领域工作经验;

2. 熟练掌握c/c++，python或matlab(其中之一即可),有很好的数据结构认识，算法和编程能力;

3. 熟练掌握化学计量学相关算法，并对分子光谱理论、数据处理方法、实验技巧及工程化应用技术深入理解;

高级算法篇3

一、AES算法加密过程

AES是旨在取代DES的21世纪加密标准。根据NIST颁布的官方文件, AES算法是一种区块对称密钥加密机制, 它由加密 (解密) 算法和密钥扩展算法两部分组成。加密算法将明文与子密钥进行若干轮迭代, 密钥扩展算法将用户主密钥扩展成若干个子密钥, 扩散的密钥与块数据运算后形成密文, 以抵御攻击。AES算法块分组长度为128位, 密钥长度可为128、192、256位, 扩充后的密钥组数分别为11、13、15组, 轮循环次数分别为11、13、15轮, 每轮循环均使用4组密钥, 每组密钥长度均为32位 (4字节) 。AES加密轮循环:初始轮 (Initial Round) , 转换轮 (Transformation Rounds, 除去初始轮和最终轮外, 转换轮数分别为9、11、13轮, 每轮包括SubBytes、ShiftRows、MixColumns、AddRoundKey) , 最终轮 (Final Round, 没有MixColumns) 。下表列出了块大小、密钥长度、密钥组数与轮循环次数的关系:

现以16字节 (128位) 长度的密钥为例, AES加密操作具体实现代码如下:

从上述代码可以看出, AES加密采取了区块 (分组) 方式, 区块大小为16字节, 区块数据存放在二维数组 (阵列) state[4][4]中, 加密操作全部都是对state[4][4]中的数据进行操作, 操作过程可以分为以下三个阶段:

第一阶段:明文数据准备阶段。在这一阶段, 代码state[r][c] = input[r+4*c]将明文数据各字节input[4]按照下表的方式拷贝到state[4][4]二维数组中:

例如, 假设input[16]={32, 43, f6, a8, 88, 5a, 30, 8d, 31, 31, 98, a2, e0, 37, 07, 34},

则拷贝以后, state[4][4]={32, 88, 31, e0, 43, 5a, 31, 37, f6, 30, 98, 07, a8, 8d, a2, 34}。

第二阶段:加密轮循环阶段。包括初始轮、转换轮和最终轮。初始轮具体操作由代码AddRoundKey (state, w[0]) 实现:

即将经第一阶段排序后的明文数据state[4][4]与第1组密钥进行异或运算, 假如第1组密钥k[0][4][4]={2b, 28, ab, 09, 7e, ae, f7, cf, 15, d2, 15, 4f, 16, a6, 88, 3c}, 那么运算结果如下:

转换轮共有9轮循环, 每轮包括SubBytes (state) 、ShiftRows (state) 、MixColumns (state) 和AddRoundKey (state, w[i]) 。字节替换操作SubBytes (state) 具体代码为:

将state[r][c]作为索引, 取数组sBox[]中的元素赋值给state[r][c]。例如:如果state[0][0]=0x19, sBox[state[0][0]]即为sBox[25], 对应值为0xd4, 实际上即是替换表第1行第9列上的元素, 如此类推。

行字节移位操作将state中第1、2、3、4行上的字节向左 (低位) 移动0、1、2、3个字节, 移出的字节依次放回右边 (高位) 。行字节移位操作方式如下图所示:

列混合变换MixColumns (state) 操作具体代码为:

按照第0、1、2、3列和第0、1、2、3行的顺序, t[r]取每个元素的值作为函数FFmul的参数, 先在函数FFmul中进行有限域乘法和加法运算, 再将结果进行异或运算, 以对state中从state[0][0]至state[3][3]的所有元素进行置换。

函数FFmul先计算参数b (state中的元素) 与0x01、0x02、0x04、0x08相乘的值, 再根据参数a (0x01、0x02、0x03、0x09、0x0b、0x0d、0x0e) 用异或运算求和:

前面的for循环是进行域乘法运算。如果是与0x01相乘, 算法与算术中与1相乘相同, 结果bw[0]即是被乘数b本身;如果是与0x02相乘, 结果bw[1]是将被乘数bw[0]向左位移1位的值;如果是与0x04相乘, 结果bw[2]是将被乘数bw[1]再向左位移1位的值;如果是与0x08相乘, 结果bw[3]是将被乘数bw[2]再向左位移1位的值。为防止结果出现“域溢出”, 如果位移后所得的值大于或等于0x80, 还要与0x1b进行异或运算。后面的for循环是进行域加法运算, 实际上只是异或运算。根据参数a (0x01、0x02、0x03、0x09、0x0b、0x0d和0x0e共七个常数, 加密时用前三个常数, 解密时用后四个常数) 向右位移i位并与0x01位与运算的结果确定是否进行异或运算。假设a为0x02, 即00000010, 当i等于0时, if条件为假, res为0;当i等于1时, if条件为真, res与bw[1]进行异或运算, 即得到与0x02相乘的结果。假设a为0x03, 即00000011, 当i等于0时, if条件为真, res与bw[0]进行异或运算;当i等于1时, if条件仍为真, res再与bw[1]进行异或运算, 两次异或运算得到的值即为与0x03相乘的结果。以此类推, 七个常数与state中的元素相乘和相加运算情况见下表:

转换轮中的AddRoundKey (state, w[i]) 操作与初始轮相同, 只是取下一组 (第2～10组) 密钥与state中的数据进行异或运算。

最终轮包括SubBytes (state) 、ShiftRows (state) 和AddRoundKey (state, w[i]) , 但没有MixColumns (state) 。各模块操作与之前均相同, 只是异或运算所使用的是最后一组密钥, 即第11组密钥k[10][4][4]。

第三阶段:密文数据输出阶段。这是第一阶段的逆过程, 对本块 (组) 16字节明文加密后的数据重新进行排序, 并将结果输出。假设加密后数据为state[4][4]={39, 02, dc, 19, 25, dc, 11, 6a, 84, 09, 85, 0b, 1d, fb, 97, 32}, 那么重新排序后输出结果为input[16]={39, 25, 84, 1d, 02, dc, 09, fb, dc, 11, 85, 97, 19, 6a, 0b, 32}。

二、AES算法解密过程

AES算法解密过程是整个加密过程的逆过程。如果密钥长度为128位, AES对数据的解密过程为:

解密过程也可以分为三个阶段:密文数据准备阶段、解密轮循环阶段和明文数据输出阶段。解密过程的第一阶段与加密过程的第三阶段是互逆的, 第三阶段与加密过程的第一阶段是互逆的。在解密过程的第二阶段, 密钥的使用顺序是W[10]……W[0], 与加密时相反。需要特别注意的是, 在解密轮循环阶段, 字节替换操作函数InvSubBytes (state) 中所使用的替换表与加密时不同:

将state[r][c]作为索引, 取数组invsBox[]中的元素赋值给state[r][c]。例如:如果state[0][0]=0xd4, sBox[state[0][0]]即为sBox[212], 对应值为0x19, 实际上即是替换表第d行第4列上的元素, 正好与加密时相反, 如此类推。

另外需要注意的是, 列混合变换InvMixColumns (state) 操作中, 与加密时不同, FFmul函数的参数为0x0e、0x0b、0x0d和0x09, 操作结果与加密时相反:

三、AES算法密钥扩展

在AES算法中, 可以使用128位 (16字节) 、192位 (24字节) 或256位 (32字节) 长度的密钥对数据进行加密, 三种长度的密钥分别被扩展成11组、13组、15组。128位 (16字节) 长度的密钥扩展程序如下:

第1组密钥w[0][r][c]直接使用原始密钥, 密钥扩展程序只是将128位 (16字节) 原始密钥重新进行排序:

第2～11组密钥w[1][r][c]-w[10][r][c]用以下方式得到:对于第2～11组第1列密钥w[1≤i≤10][r][0], t[r]首先取前1组第4列密钥w[i-1][r][3], 然后再通过sBox对t[r]进行置换;对于第2～11组第2、3、4列密钥w[1≤i≤10][r][1≤c≤3], t[r]直接取本组第1、2、3列密钥。之后, 将前1组每列4行密钥w[i-1][r][c]与t[r] (t[0]、t[1]、t[2]、t[3]) 进行异或运算, 即得到第2～11组密钥w[1][r][c]-w[10][r][c]。

四、AES算法安全性分析

数据加密是维护数据安全的重要手段。作为DES的继承者, AES已经被工业界、银行业和行政部门作为事实上的密码标准, 并逐渐取代DES在IPSec、SSL和ATM中的加密功能。在这种情况下, 除了要求能够高效实现以外, AES算法的安全性问题显得尤为突出。正如DES算法使输入与输出之间呈现非线性映射关系一样, AES算法每次以16字节 (128位) 数据块State[4][4]为对象, 通过将数据与密钥进行异或运算、对数据进行置换、将数据行列进行变换等操作, 最大限度地模糊输出对输入的依赖, 从而有效地保护数据安全。

(一) AES加密算法将密钥的位数提高到16字节 (128位) 以上, 极大地增加了破解密文的难度。由于AES算法是在公众广泛参与和专家严密论证的基础上产生的, 是一个已经公开的算法, 因此, AES算法密钥本身特别是密钥长度对保护数据安全十分重要。但到目前为止, 要强行遍历搜索所有可能的16字节 (128位) 以上的密钥, 即使最快的计算机系统在有效时间内也是无法做到的。

(二) AES加密算法除对数据进行普通替代和置换外, 还引入了域乘法和加法运算, 以增加加密强度。列混合变换MixColumns (state) 所进行的域乘法和加法运算是基于名为GF (28) 有限域理论的。G代表这一数学理论的发明者法国数学家伽罗华 (Galois, 公元1811年～公元1832年) ;F即Field, 表示数学域;28=256, 表示有限域范围位于集合{0x00…0xff}之中。虽然AES算法中的GF (28) 域乘法和加法运算仅在state[4][4]中的元素与0x01、0x02、0x03、0x09、0x0b、0x0d和0x0e七个常数之间进行, 乘法和加法也只是移位和异或运算, 但是, 将数学原理巧妙地应用于密码分析实践之中, 这种加密方式有效地增加了对数据的加密强度。

(三) AES 算法强调通过大量轮数来增加加密数据的复杂性。根据密钥长度, AES 算法对16字节 (128位) 数据的加密轮数分别是11、13和15轮, 当前的密码分析研究表明, 迭代型分组密码抗击密码分析攻击的能力随着加密轮数的增加而增加。AES算法通过轮变换产生的高扩散性, 归功于它在所有状态比特上的均匀结构, 每个状态比特均依赖于两轮之前的所有状态比特, 或者说, 一个状态比特的改变均可能对两轮之后的半数状态比特产生影响。研究表明, 捷径攻击比穷尽密钥搜索攻击更有效。目前, 尚未发现能够对具有6轮以上的经AES算法加密的数据有效的捷径攻击。如果考虑还有4轮以上的安全余量, 捷径攻击AES算法成功的可能性就更小。

虽然到目前为止还没有已知的密码分析攻击可以破解AES加密的数据, 但是, 由于AES算法密钥扩展过程中, 某一轮的密钥都是由前一轮的密钥推导而来的, 如果我们知道了某轮密钥的部分字节, 就有可能递推出本轮密钥的其它字节。当泄露的密钥信息达到一定程度时, 或许就可以通过穷举法获得某一轮的密钥, 进而获得全部轮子密钥。

参考文献

[1].Federal Information Processing Standards Publication197, No-vember26, 2001.Announcing the Advanced Encryption Standard.Http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf.

[2].[美]Richard Spillman.经典密码学与现代密码学[M].叶远健, 曹英, 张长富译.北京:清华大学出版社, 2005

[3].[美]David Salomon.数据保密与安全[M].蔡建, 梁志敏译.北京:清华大学出版社, 2005