① 在FPGA上快速实现MD5算法的新方法论文
在FPGA上快速实现MD5算法的新方法论文
摘 要 文章介绍了一种在FPGA上快速实现MD5算法的新方法,给出了优化设计的原理、实现的具体方法及其重要模块的设计实现方案。
关键词 MD5;FPGA;Verilog语言;集成电路;关键路径
1 引言
随着电子商务和网络通信的发展,网络信息安全的重要性越来越显着,信息加密、数字签名、数据的完整性认证、身份验证等成为信息安全领域的重要内容。MD5算法本身是为数字签名应用而设计的,随后也应用在信息验证技术当中。作为应用最广泛的安全散列算法,MD5算法的高效实现就成为研究的需要,MD5算法本身可以采用软件实现,但其性能受到处理器件性能的制约不能满足网络通信带宽日益增长的要求,因而通过硬件实现高速MD5 运算就成为需要。
2 MD5算法介绍
MD5 算法可以对任何长度不超过 264二进制位的消息产生128 位的单向散列消息摘要输出, RFC1321 标准中的MD5 算法主要步骤如下:
在一些初始化处理后,MD5以512位分组来处理输入文本,每一分组又划分为16个32位子分组。算法的输出由四个32位分组组成,将它们级联形成一个128位散列值。
(1)附加填充比特:填充消息使其长度恰好为一个比512位的倍数仅小64位的数。即对报文进行填充使报文的长度(比特数)与448模512同余。填充方法是附一个1在消息后面接所要求的多个比特0。
(2)附加长度值:在其后附上64位的消息长度(填充前)。如果消息长度大于 264,仅使用该长度的低64比特。这样,该域包含的长度值为初始长度模264 的值。
这两步的作用是使消息长度恰好是512位的整数倍(算法的其余部分要求如此),同时确保不同的消息在填充后不相同。
(3)初始化寄存器:四个32位初始化变量为:
它们也被称为链接变量(chaining variable)
(4)进行算法的主循环:这一步是算法的核心,它是一个包含四个大循环的64步函数,四个大循环结构相同,但每次使用的逻辑函数不同,每一个大循环由对512比特的16步操作组成,即每16步为一轮大循环。
每次操作如下(设 Ai+1、Bi+1 、Ci+1 、Di+1 为第 +1个时钟周期时打入寄存器的值):
以一下是每轮中用到的四个非线性函数(每轮一个)。
常数ti可以如下选择:在第i步中,ti是4294967296*abs(sin(i))的整数部分,i的单位是弧度。Wi是512位消息分组中的一个,Si是每次循环移位的次数。对每次而言也是固定的常数。
(5)结果输出:所有64步完成之后,将第64步的输出加到四个初始化变量上作为新的初始化变量,进行下一个512比特分组的运算,直到所有分组处理完毕,单次操作图如下:
图1. MD5算法单步操作图
3 算法优化
由上图可以看到,硬件实现时,MD5算法每一步操作中的关键路径在于B的求取(其他三个变量都是直接传递),这个关键路径包括了四个模 232加法运算、三输入变量的逻辑运算、"两个查找表运算及一个循环左移运算,而在FPGA设计中,加法运算最为耗时,四个加法运算至少需要三个加法器级联完成,加法运算严重制约了整个操作的速度,可见要加快算法运行速度就必须在简化这一关键路径上下工夫,经过观察我们发现,在
中 对每个周期都是已知的常数,是输入的512比特的一个32位分组,这样,在512比特输入初始化完成后,也可看作固定常数,
Ai是第i时钟周期里寄存器D 的值,而 Di的值又是第i-1周期里的Ci-1 ,即Ai 的`值是第i-1周期里Ci-1的值。
若在第i周期设中间寄存器变量 ,并令
那么在第i+1周期,
就可以表示为
操作就可以用下面几个式子代替:
其中, Ai+1没有参与任何运算,因此上式可以接着化简为
这样一来,原来一个周期内需要完成三级加法和相应的组合逻辑,现在只需要完成两级加法和部分组合逻辑就行了,大大提高了算法速度,只要在运算开始时加-个周期的初始化即可,简化后的系统框图如下:
图2. 改进后的单步操作图
4 结果比较
由上文中的算法分析部分不难看出,传统的实现方式关键路径是3级32比特加法器延迟和组合逻辑的延迟,而改进的实现方式减少了一级加法器的延迟,并把组合逻辑的延迟分散到不同路径上,因此,采用改进的实现方式大约可以将速度提高到原来的1.5倍左右。同时,为了实现数据的初始化,需要提前一个周期计算出寄存器A的值,因此整个算法的实现需要65个周期。我们采用 VerilogHDL 描述,选择Altera Stratix II EP2S15F672C5 FBGA芯片,在QuartusII6.0上验证通过。由于在FPGA中,连线延时也很关键,而这部分延时不能像加法延时那样通过预先计算并存储在寄存器中来消除一部分,所以实际的MD5改进算法与传统型相比较,速度的提高约为1.3,资源方面由于只是增加了一个时钟节拍,寄存器数量和组合逻辑并没有增加,所以改进型在资源方面和传统型相当。下表为算法改进前后在资源、频率、流量上的比较。
表1. 改进前后资源比较
5 结束语
由表1可见,改进型MD5算法实现,使用的资源并没有明显增加,但速度的改善十分明显,基本实现了用较少的资源得到较高速率的目标,证明了结构的正确性和合理性。实验结果也说明,这种利用寄存器来减少加法器级联从而减少关键路径的实现方法也可用于一般的FPGA硬件设计中。
参考文献
[1] R.Rivest. The MD5 Message-Digest Algorithm,RFC1321 1992。
[2] Jarvinen K, Tommiska M,Skytta J.Hardware implementation analysis of the MD5 hash algorithm.System Sciences,2005.HICSS’05.Proceedings of the 38th Annual Hawaii International conference on 03-06 Jan.2005:298
[3] Bruce Schneier. 应用密码学.北京:机械工业出版社,2000:188~194
[4] William Stallings. 密码编码学与网络安全:原理与实践.北京:电子工业出版社,2001: 216~222。
[5] 夏宇闻.Verilog 数字系统设计教程.航空航天大学出版社,2005
;
② 阿里面试官:恕我直言,搞懂这10道算法题,轻松拿20K不是问题
01打怪兽
难度:容易
现在有3只怪兽,他们的都有自己的血量a,b,c(1<=a,b,c<=100),当Tom打死第一怪兽的时候花费的代价为0,其余的怪兽的代价为当前的怪兽的血量减去上一个怪兽的血量的绝对值。问Tom打死这些怪兽所需要的最小代价
02数组变换
难度:中等
给出一个长度为 n 的数组,和一个正整数 d。 你每次可以选择其中任意一个元素 a[i] 将其变为 a[i] + d 或 a[i] - d,这算作一次操作。你需要将所有的元素全部变成相等元素,如果有解,请输出最小操作次数,如果无解请输出-1。
01超级区间
难度:中等
Tom现在有一个长度为n的数组,Jerry给Tom定义了一种超级区间,如果区间[l,r]满足(a[l]+…+a[r])>=k,则区间[l,r]被称为超级区间,现在Jerry想让Tom告诉他数组中有多纤岩少个超级区间。
02能量半径
难度:中等
codancer来到了一个能量平面上的中心,坐标为(0,0),接下来巫师Tom会在q个坐标上放置能量点,每个信凳能量点的能量值为1,为了打败哥斯拉,他需要至少k点的能量,因此他想确定一个最小的整数半径r使得codancer能够从这个圆心为(0,0),半径为r的圆形区域内得到至少k个能量值,请你帮他确定最小的整数半径r。
01找出二叉搜索树的第2大的数
难度:容易
给定一个二叉搜索树,找出其第二大的数。
02字符配对
难度:中等
给你一个字符串,字符串中仅包含"A","B",现在有四种字符串"AA","AB","BA","BB",每种字符串都有他们的权值,问从给出的字符串中能够得到的最大权值为多少(一个字符只能属于一个子字符串)?
01斐波那契字符串
难度:中等
Tom发现了一种神奇的字符串-斐波那契字符串,定义f[1]=0,f[2]=1,对于所有的i>2都有f[i]=f[i-2]+f[i-1],其中“+”代表拼接,比如01+10=0110,现在对于字符串f[n],请判断f[n]的第k项是0,还是1?
01Hikari and Interstellar Experience
难度:容易
在无垠的宇宙中,有 n 个星球,第 i 个星球有权值vi 。由于星球之间距离极远,因此想在有限的时间内在星际间旅行,就必须要在星球间建立传送通道。 任意两个星球之间均可以建立传送通道毁坦御,不过花费并不一样。 第 i 个星球与第 j 个星球的之间建立传送通道的花费是lowbit(vi ⊕ vj) ,其中⊕为二进制异或,而lowbit(x)为 x 二进制最低位的值,例如lowbit(5) = 1,lowbit(8) = 8 。 特殊地,lowbit(0) = 0。 Hikari 想在这 n 个星球间穿梭,于是――你需要告诉 Hikari,要使这 n 个星球相互可达,需要的花费最少是多少?
02二进制字符串
难度:中等
Tom得到了一个二进制字符串s,即s只由Ɔ'和Ƈ'组成,现在令d(t)代表二进制字符串t在十进制下的值。 那么d(“011”)=3,d(“0001000”)=4,如果t的长度等于d(t),那么就称t是奇妙串,现在Tom想知道s中有多少个子串是奇妙串?
01小明的数学作业
难度:容易
众所周知,小明是一个数学小能手,有一天数学老师给了小明一个长度为n(2<=n<=5000)的序列,其中第i个数是ai(0<=ai<=1e9),数学老师想知道这个序列排序后,其中最长的等差子序列的长度是多长,聪明的你能帮小明解决这个问题吗?
02Codancer上楼
codancer来到了一栋大楼前,现在他要上楼。
如果codancer从第x层走楼梯到第y层(y>x),那么他所花费的时间是a[x]+a[x+1]+…+a[y];
如果他从x层坐电梯到第y层,那么他所花费的时间是c+(b[x]+b[x+1]+…+b[y]),因为他等电梯的时间为c。
现在codancer想知道从第1层到第n层需要最少需要多长时间?
01变换的秘钥
难度:中等
Tom最开始有一个密钥s1,s1是长度为n的由小写字母组成的字符串。Jerry也有一个长度为n的由小写字母组成的密钥s2。现在有m组关系,每组关系由两个数字[u,v]构成(1<=u,v<=26),表示26个字母表中的第u个小写字母可以直接转换为第v个小写字母。假设u=1,v=2,那么说明字母'a'可以直接转换为字母'b'。现在Tom对于s1的每个字母使用无数次转换,请判断s1能否转换为s2?
01最大边权和
难度:简单
现在有n个点(1<=n<=1000),每个点都有一个值称为点权ai(ai为偶数,1<=ai<=1000),现在可以将任意两个点相连,连起来以后这条边也有一个值称为边权,这个边的边权为这两个点的点权之和的一半。现在需要你添加n-1条边,问将这n个点连通以后(连通是指任意两个点都能互相到达)的最大的边权和是多少?
02钱庄
难度:中等
钱庄每天能够收到很多散钱,第i个散钱的值2 wi。为了便于管理,钱庄每天都会向中央银行申请兑换钱币,假设钱庄有一些散钱使得2 k1+2 k2+...+2 km=2^x(x为非负整数),那么就可以将这些散钱兑换成一个大钱币,问在钱庄收到的这些散钱最终最少能变成几个钱币?
01codancer的旅行
难度:困难
期末考试终于结束啦,Codancer开始了他的旅行,现在整个地图上有n个城市,这些城市之间有n-1条道路相连,每条道路都有一个距离,并且保证整个图是连通的,即这个地图可以看作是一棵树,现在假设Codancer要从城市A到城市B,那么他的路费就是从A-B的路径上边权最大的边的权值wmaxx元。现在Codancer有k元,他想知道他能选择那些(A,B)并且A<B使得codancer能够到达?
HashMap是一个用于存储Key-Value键值对的集合,每一个键值对也叫做Entry。这些个键值对(Entry)分散存储在一个数组当中,这个数组就是HashMap的主干。
01全奇数组
难度:中等
codancer现在有n个正整数a[1],a[2]…a[n],Tom告诉codancer他可以进行下列操作,选择某个偶数x,把这n个数中全部等于x的数字除2,Tom想知道把这n个数字全部变成奇数最少需要几次这样的操作?
以上十道算法题你都能搞定嘛?备战大厂每日刷一道算法题来提升自己,坚持坚持再坚持,必然会有收获。为大家整理一份781页的高分宝典,知识较为全面,可分享给想要学习提升自己的朋友。
领取方式:私信【面试宝典】或点击右方链接: https://shimo.im/docs/QVy8HrQgPYkx9Ddg/ 即可免费领取,喜欢本文不妨关注+转发支持一下~~
③ 求 机器学习周志华pdf
链接:
提取码: 8b5m
《机器学习》展示了机器学习中核心的算法和理论,并阐明了算法的运行过程。

④ 在加密算法中属于公钥密码体制的是什么
算法介绍:
现有矩阵M,N和P,P=M*N。如果M(或N)的行列式为零,则由P和M(或P和N)计算N(或M)是一个多值问题,特别是M(或N)的秩越小,N(或M)的解越多。
由以上问题,假设Tom和Bob相互通信,现做如下约定:
1. 在正式通信之前,二人约定一个随机奇异矩阵M。
2. Tom和Bob各自选取一个n*n的随机矩阵作为他们的私有密钥,设Tom的为A,Bob的为B。
3. 然后Tom计算矩阵Pa=A*M作为他的公钥,Bob计算矩阵Pb=M*B作为他的公钥。
4. 当Tom向Bob发送消息时,计算加密矩阵K=A*Pb,用K对消息加密后发送到Bob端,Bob收到消息后,计算解密矩阵K’= Pa*B,由以上代数关系可以看出,K= K’,也既加密和解密是逆过程,可以参照对称加密标准AES。
5. Bob向Tom发送消息时,计算解密矩阵K= Pa*B,加密。Tom收到消息后计算解密矩阵K=A*Pb,原理同上。
算法分析:
由以上介绍可容易看出,此算法比RSA和ECC的加密效率要高4-6个数量级,且加密强度在增大n的基础上,可获得与以上两算法相当的加密强度。
该算法仍在论证阶段,欢迎此方面高手携手参与或提出缺点.
email:cms@msn.com