论坛公告:应用容器安全指南(SP800-190)中文版   美国政府宣布禁用卡巴斯基软件   《中华人民共和国网络安全法》讨论帖   新手报到专用帖   【论坛公告】关于本站广告贴泛滥问题的整理通知   

当前时区为 UTC + 8 小时


发表新帖 回复这个主题  [ 1 篇帖子 ] 
作者 内容
 文章标题 : 基于FPGA 的DES 算法S 盒的优化设计
帖子发表于 : 2007-07-26 02:45 
离线
新手

注册: 2007-07-26 02:11
最近: 2007-07-26 02:39
拥有: 0.00 安全币

奖励: 0 安全币
在线: 10 点
帖子: 1
概 述
为了满足工程上实时加密和密钥安全管理的需要
越来越多的加密算法开始采用可编程逻辑器件实现数
据加密标准D E S 及其变形3 - D E S 是当前应用最为广泛
的加密算法在算法中S 盒居于核心的位置关系着
整个加密系统的安全性目前采用C P L D / F P G A 设计
D E S 的过程中对于S 盒模块的实现比较通用的方法
是直接运用C A S E 语句对S 盒进行描述该方法虽具有
代码简单可读性好等优点但却要以牺牲大量的片内
资源为代价同时生成的复杂组合逻辑会造成关键路
径上的延时大量增加
本文旨在通过对S 盒的改进设计以进一步提高整
体系统的加密速度减少片内资源的损耗文中给出了
优化前后的两组实验结果并对其进行了对比和分析
实验结果表明优化后S 盒的资源消耗比优化前减少了
49.2% 延时逻辑级数下降了25% 在XC2S100TQ144 实
验板上系统加密速度达到293.2Mb/s
2 S 盒工作原理
DES 加密系统中S 盒被平均分成8 个子S 盒每个
子S 盒的输入和输出分别为6 位和4 位总共4 8 位输入
和3 2 位输出每个子S 盒的工作原理为6 位输入中的
最高和最低两位组合作为列的值其组合0 0 0 1 1 0
11 分别代表第0 1 2 3 列中间4 位作为行的值共24=16
行经过S 盒转换表得到一个新的4 位输出转换后的
输入输出关系呈现很强的随机性达到有效保护明文的
信息例如假设第8 个子S 盒S8 的输入为(011001)2 通
过转换其输出为(0000)2 表1 仅列出了的转换关系表
3 S 盒的优化设计
3.1 Spartan - 系列FPGA 的Slice 结构
FPGA 中的CLB 用来实现特定的组合和时序逻辑每
个CLB 含2 部分Slices,每个Slice 包括2 个4 输入查找表
结构( L U T 4 ) 的函数发生器F 或G 多路选择器M U X F 5
MUXF6 及一些进位逻辑Slice 内部资源如图1 所示
3.1.1 LUT4 函数发生器
用于实现4 输入的任一函数F 和G 可以被配置成
为SRL16 宏单元16 1 位的同步R A M 或是16 1 位
的R O M 在本设计中将其设置成为R O M 结构
3.1.2 MUXF5
多路选择器具有2 选1 的功能与两个F 或G 一
起用于实现任一5 输入的函数其两个输入端数据I 0
I 1 必须来自相应的F 或G 的输出S E L 为选择信号
表1 S8盒函数转换表


0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
00 1101 0010 1000 0100 0110 1111 1011 0001 1010 1001 0011 1110 0101 0000 1100 0111
01 0001 1111 1101 1000 1010 0011 0111 0100 1100 0101 0110 1011 0000 1110 1001 0010
10 0111 1011 0100 0001 1001 1100 1110 0010 0000 0110 1010 1101 1111 0011 0101 1000
11 0010 0001 1110 0111 0100 1010 1000 1101 1111 1100 1001 0000 0011 0101 0110 1011
O
F
O
G
MUXF5
MUXF6
S
D
CK
EC
R
Q
S
D
CK
EC
R
Q
CY
CY
Look-Up
Table
Look-Up
Table
I0
I1
SEL
I0
I1
SEL
F1
F2
F3
F4
I0
I1
I2
I3
G1
G2
G3
G4
I0
I1
I2
I3
图1 Spartan-II Slice 内部资源结构图
万方数据
2004.12 Microcontrollers & Embedded Systems 75
经验交流EXPERIENCE EXCHANGE
3.1.3 MUXF6
与M U X F 5 具有类似的功能不同的是其输入I0
I1 必须来自相关的MUXF5 输出与4 个F 或G 及2 个MUXF5
一起可以实现多达6 输入的任意组合逻辑
3.2 优化设计思想
根据图1 的Slice 结构在1 个Slice 内可以实现5 输
入到1 输出的任意组合逻辑记为5~1 相邻的两个Slices
(1 个CLB 内)则可以用来实现6~1 的任意函数而在S 盒
中每个子S 盒的功能相当于一个6 ~ 4 的输入/ 输出转
换表为便于实现可以将其分解为4 个6 ~ 1 的子模块
分别予以实现具体
的优化设计思想如
下将基于LUT4 的F 和
G 设置成1 6 1 位的
R O M 每个子S 盒中间
的4 位{4:1}输入作为该
R O M 的寻址地址由于需要4 位的数据输出因此需4
个L U T 4 最高与最低位组合的列值有4 种可能这样
每个子S 盒共需16 个LUT4 输入的最低位{0}充当MUXF5
的选择信号实现2 选1 的功能MUXF5 共需16/2 8
个最高位{ 5 }作为M U X F 6 的选择信号与前面的2 个
MUXF5 一起可以实现4 到1 的多路选择器共需16/4
4 个M U X F 6 因此要实现1 个子S 盒的全部功能仅
需16 个LUT4 8 个MUXF5 和4 个MUXF6 即可优化方
案的原理图如图2 所示
图2 中MUXF5 与MUXF6 是FPGA 中的多路选择器
功能单一而LUT4 则可以用来实现设计中绝大部分的组
合逻辑功能相对而言在大型设计中LUT4 显得更为宝
贵LUT4 MUXF5 和MUXF6 之间具有专用的布线路径
其线上的延时要比LUT4-LUT4 之间的延时小VHDL 编程
时全部采用LUT4 MUXF5 和MUXF6 元件例化描述之间
的连接关系LUT4 中ROM 的内容通过INIT 属性设置或通
过约束设定其值可以从S 盒转换表中求得
4 实验结果及分析
为便于时序分析在图2 的首尾两端分别增加了两个
寄存器组用以形成一个完整的周期路径优化后的S 盒
的综合结果与期望的完全一致资源消耗达到最小两组
实验部分结果对比如表2 所列
表2 数据表明改进后的S 盒无论在面积消耗上还
是在速度上都得到了明显改善
(1)资源消耗
硬件描述语言VHDL 属于高级语言当算法相对复杂
而代码过于简洁往往会给综合过程带来巨大困难直接
采用CASE 语句多达512 种的输入分支加上输入输出
间转换关系又过于复杂导致XST 综合工具未能发现S 盒
隐含的转换规律将某些较底层的元件指定到MUXF6 上
通过将大量的LUT4 综合成LUT2 LUT2_L LUT3 LUT3_L
等形式来完成相当于MUXF5 和MUXF6 的功能其结果
是MUXF6 专用资源的白白
浪费同时又消耗了大量
的L U T 4 而在优化方案
中由于采用了底层原语
例化XST 根据程序的要
求自动指定到相应元件
中达到期望的设计结

(2)组合逻辑延时
综合路径显示组合
逻辑延时级数由优化前的
4 级降为了3 级减去两
端寄存器的时钟到输出时
间tCKO 和tSETOP 建立时间
优化前后分别为6.246ns 和 3.700ns 的延时
分析影响时钟工作速度的关键路径发现与LUT4 的输出
延时(tio 0.549ns)相比MUXF5 和MUXF6 的输出延时仅
为0.315ns 和0.316ns 而且相邻之间存在专用布线网
Din(5 Downto 0)
4个LUT4
图2 单个子S 盒优化设计原理图
表2 优化前后实验结果对比
资源消耗
设计方法
LUT4/
LUT4_L
LUT3/
LUT3_L
LUT2/
LUT2_L
共需
LUT4
MUXF5 MUXF6 逻辑级数 延时/ns
CASE 语句描述 167/22 33/15 9/16 252 59 0 4 6.246
底层原语描述 128/0 0/0 0/0 128 64 32 3 3.700
万方数据
76 2004.12
经验交流EXPERIENCE EXCHANGE
胡塘硕士研究生主要研究方向为数字系统设计数据加
密刘文波副教授主要研究方向为密码学数字系统设
计混沌分形理论及应用于盛林教授博士生导师主
要研究方向为数字信号处理数字系统设计混沌分形理
论及应用胡晓松高级工程师主要从事数字系统现场集
成技术的研究
收稿日期2004-07-07
线上的延时几乎为0 相反LUT4-LU4 之间的延时则高达
1.035ns 因此优化后的S 盒在速度上也得到了改善
最后将整个DES 设计下载到XC2S100TQ144 上进
行实现最高时钟频率达73.3MHz 加密速度为293.2Mb/s
比优化前的245.2Mb/s 提高了近19.6
结 语
本文避开直接采用C A S E 语句的V H D L 编程而是
采用硬件原语的形式对S 盒进行设计虽然增加了编程
时代码的录入量但却显著提高了综合质量并加快了
系统的实现速度通过对底层元件的例化加深了对S
盒工作原理的理解在采用C P L D / F P G A 进行算法实现
和其它应用中经常会遇到与S 盒类似的设计问题因
此本文设计中的基本思想及一些技巧仍可继续加以


附件:
基于FPGA的DES算法S盒的优化设计.pdf [82.38 KiB]

注意:所有附件下载均需支付10安全币,不足10安全币不能下载!重复下载以前下载过的附件不再需要安全币。
回到顶部
 奖励本帖 用户资料  
 
显示帖子 :  排序  
发表新帖 回复这个主题  [ 1 篇帖子 ] 

当前时区为 UTC + 8 小时


在线用户

正在浏览此版面的用户:没有注册用户 和 1 位游客


不能 在这个版面发表主题
不能 在这个版面回复主题
不能 在这个版面编辑帖子
不能 在这个版面删除帖子
不能 在这个版面提交附件

前往 :  
cron
华安信达(CISPS.org) ©2003 - 2012