《基于嵌入式系统的rsaecc加密解密协处理器算法及硬件研究》由会员分享，可在线阅读，更多相关《基于嵌入式系统的rsaecc加密解密协处理器算法及硬件研究（66页珍藏版）》请在金锄头文库上搜索。
1、复旦大学硕士学位论文基于嵌入式系统的RSA ( 2 )已 知 Y 和f (x ) 且 相 应 的x 是 存 在 的 ， 根 据 ， 一 f 一 ， (.r ) 无 法 计 算 或 者 无 法 在规定的时间内计算出x 的值; 招)存 在 门 陷 信 息t ， 使 得 在 己 知Y 和f ( x ) 且 相 应的x 是 存 在 的 情 况 下 ， 根据 ， 一 f - (z ) 容 易 计 算 出x 的 值 。根据上述定义， 使用单向陷门函数f 作为加密函 数时， 可将函数f 公开， 即 相当 于 公 钥 ， 而门 陷 信 息t 可以 作 为 私 钥 使 用 由 于加 密函 数 是 公 开 的 ，
2、 所 以任何人都可以将信息 x 加密成Y = f ( x ) ， 只有相应的私钥拥有者才能解密信息。当前已得到密码学界承认的安全而又能有效实现的公钥制密码体制按照所基于的单向函数的不同可分为如表 1 . 1 所示的三类。表 1 . 1加密系统算法分类1 . 2 信息 安全在现代社会的意义信息作为一种重 要的资源。在 现代社会生产、生活中的作 用日 益显示。电脑网络的建立和延伸，打破了传统的行业、地域和发展空间的概念，把地球上茶于嵌入式系统的 R S 八 运用己方的信息和信息系统，使部队全面了解战场情况，对敌实施有效打击，夺取战争的胜利。信息战核心是获取 “ 信息控制权 ， 。 海湾战争中， 美
3、国将带有计算机病毒的微机芯片装入伊拉克从法国购买的用于防空系统的新型打印机中，达到了使伊拉克军事指挥中心计算机失 灵的目 的， 充分显示了现 代高 技术条件下“ 制信息权” 关键作用。 科索沃 战争， 更是美国实施信息战的一次 试验，再次证明信息网络己 成为高 技术战争 的 重要对抗领域。信息战突 破了 传统的地缘概念，无法用领土、 领空、 领海 来 划分， 其特点也更加隐蔽，被 称为 一场 “ 无硝烟” 的战争。由 此可 见， 建立安全的 “ 信息边疆” ，将是确保国家安全的时代主题。纂于嵌入式系统的R S d , 0 。如果n( a - b ) ，则 成为a 和b 模n 同 余， 记为a二
4、b ( m o d n ) ， 整数n 称为模数。若 a二b ( m o d n ) ，则存在 k E Z ，且 a=k n+b。 定义2 . 3( 模运算) 】 a m o d n 的 运算给出了a 对模n 的余 数，这种 运算 称为 模运算。 模运算的结果是从0 到n - 1 的 一个整数。 【 定义 2 . 4( 欧拉函数) 】 欧拉函数 0 ( r ) 定义为 O ( r ) = r ( 1 - 1 / P ,) ( 1 - 1 / P -办 . . . . . . ( 1 - 1 / P ) ， 其中 P , , P . . . . . . P是 r 的 I 1 个质因子。 定义2
5、. 5 ( 模逆元) 】 若n = 1 , ( a , n ) = 1 ，则存在c 使得c a = 1 m o d n , c 称 为二 对模n 的逆， 记做 扩m o d n 。 在己 经指明 模数的 情况 下， 有时也 可记做岁 。基于以 上的定义我们不 加证明 的给出 下列的 定理， 这些构成了R S A 算 法的 数学理论基础。基本上 R S A算法的理论核心就是大数求模问题。 定理 2 . 1 1每一个合数都可以唯一地分解成质因数的乘积。 定理 2 . 2 1 给定整数 r ( r 1 ) ， 对于任意的一对整数 。 和 b ， 式子a - b ( m o d r )和“ x b (
6、 m o d r )有且只有一个成立。【 定理 2 . 3 1 如果a 三 b m o d r ) 成立， 则“ = b 十 k : 一定成立;反 之亦然。 其中A - 为 整数。【 定理2 . 4 1 ( 欧拉定 理) 如果a 与， 是互质的， 且r 的欧 拉函数为(p ( r ) ， 则有:a w ( = ) 二 I ( m o d 小 定理2 . 5 1( 推广的欧 拉定理) 如果a 与 r 是互质的， r 的欧 拉函数 为 ( r ) , k为 整 数，则 有a “ “ “ - I ( m o d r ) o【 定理2 . 6 1 若N=P-9是两 个质数的乘积，则对于任何满足X 为阿
7、贝尔群，F 在“ + 运算下的么元记为0 ;2 ) F 中所有的非 0 元素在“ * ， 运算下也构成阿贝尔群，其么元记为 1 ;3 ) ，* ” 运算对“ + 运 算满足分配率: a * ( b + c ) = a * b + a * c ， 其中a , b , c 是F 上的 元素。那么称代数系统为域 ( F i e l d ) 。如果集合 F中的元素为有限个，则称 是有限 域。 、定 义2 . 8 ( 本 原 多 项 式) : 假 设; (x ) = x “ + p 、 一 ，x 。 一 ， + ， + p Ix + p 。 为G F (2 ) 域 上 阶 数 为 。的既约多项式，如果多
8、项式p ( x ) 可以除尽多项式二 “ + 1 的最小k 值是 k = 2 ， 一 1 ， 那么称p ( x ) 为G F ( 2 ) 域上的 本原多 项式 ( P r i m i t i v e P o l y n o m i a l ) . 本原多项式的根a 称为 F ( 2 ) 上的本原元素 ( P r i m i t i v e E l e m e n t )且 a “ = P . - .a “- , + P , - = a “+ + P , a + P O 【 定义 2 . 9( 标准基) 7: 域G F ( 2 ) 上的任意一个非零元素A 均可通过向量 a o a l， a 2
9、， ,a 0 ; 的 线 性 组合 来 表 示， 记为A = a 十 氏_ 产 m 一 十 + p p+ p o e因而 a 0 , a , a 2 ，二 ， a “ - 构成了G F ( 2 ) 域上的一 组基， 称为标准基 ( S t a n d a r dB a si s) .基于嵌入式系统的2 S A 给定简化的投射 坐标下W e i s t e r a s s 方程式为尹= 犷+ a x 十 b ，此式 必须 满足4 a ， 十 2 7 b 2 :, -, 。 。本文主要 讨论 基于二进制域上的椭圆曲 线加密系统， ， 基于 其它域上椭圆曲 线 的 数 学 表 述 可以 参 考 文
10、献 i 1 U 3 定义 2 . 1 2( 仿射坐标下二进制域上的椭圆曲 线) :定义E ( G F ( 2 “ ) ) 为二 进制域G F ( 2 m ) 上的 非奇异( n o n - s u p e r s i n g u l a r ) 椭圆曲 线， 参数a , b E G F ( 2 0 ) 且b # O .则 对于x , y E G F ( 2 ) ，曲 线上的点P= ( x , Y ) 可以 形成如下方程:Y 2 + x y = x + a x 2 + b ( 2 . 3 . 3 )纂于嵌入式系统的x s a x+ a , x + 1 ) z = a 3 x 6 + 2 a 3
11、a , X 5 + 2 a 3a ,X 0 + 2 a ,a , X 3 + a 里 x + 2 a : a , x + 2 a , a o + a X 2 + 2 a ,a o x + a 2 = a 孑 X 6 + a 全 x + a 户 x + a 子 A 二 ( 1 0 1 1 ) = = A = ( 1 旦 0 旦 1 旦 1 )在硬件设计中，一般可以采用查找表( L U T ) 的方法可以加速这个转换过程。我们可以使用一个 8 6 i t的查找表，通过一个快速的查找表替换为 1 6 b i t 的对应项，这时我们需要一个2 5 6 x 1 6的表格。替换完毕之后，根据上节所述的方法
12、将溢出 部分的值 利用P ( X ) 化简。基于嵌入式系统的R S d i 1B 1e n d f o rS=S+Cr e t u r n S算法3 . 1 0改进的M o n t g o m e r y 算法在整个过程中， 前 n + l遍循环( s + C ) e ( 0 , 5 M) ， 最后第 n + 2次 循环时，墓于嵌入式系统的R $ A 原状态机很难被重用或者部分重用。图 4 . 2描述了一般的基于微程序的系统框图。 地址发生单元通过当前地址和状态信号得出下一个周期的指令地址。一般来说， 都是简单的加一操作， 在遇到跳转时需要根据跳转的触发条件配合寄存器和运算结果得出跳转到特定的
13、地 址。 译码 单元可以 利用R O M 实现， 特点就是可以 大大的降低电 路规模， 同时 如果采用加密的E E P R O M 结构则也会极 大提高系 统的 安全性。基于嵌入式系统的R S ME C C加密解密协处理器算法及硬件研究3 8第四章 基于嵌入式系统的 R S A 前提是各状态寄存器和数据寄存器就绪表 4 . 1指令分类和说明在设 计指令集的时 候主要考虑了 如下的 几个方面问 题。 首 先， 由于 协处理器 的 功能具 有特殊性， 因 此不必要设置过多的通用指令以 期和外界处 理器配合， 只需要能够启动数据传输和算术运算即可。 因此在该指令集设计的时候侧重于寄存器的传输指令，
14、其他的控制指令设计不多。其次，从算法设计方面考虑，由于实现了 算法的内 集成， 因此不需要额外的条件判断和转移指令。 这样的设 计主要是降低了协处理在处理数据过程中对外部主控处理器的依赖， 同时在硬件实现上也比 较简单， 与 外界 的控制信号的 交换也大大减少。 缺点 就是这样的设 计会增加微 程序的复 杂度， 在 微程序设计阶段工 作量比 较大。由于 指令的 长度都是 8 b i t ， 因 此在实际的操作需要做一次内部的 程序入口 映 射， 将此8 b i t 的指 令映射到内部 微程序的 入口 地址， 然后开始微 程序的 控制，整个过程如图 4 . 4 所示。 在写入新的指令后将会做一次
15、指令的映射， 微程序的入 口 地址载 入到地址寄存器中。内部微程序的地址为 1 2 b i t ， 整 个微程序的空间为4 k ， 实际占 用的空间在l k 左右， 足够满足目 前的 系统需 要， 同时 还有足够的空间为以后的系统设计之用。基于嵌入式系统的R S A 6 1 R同 类型的 操作分 割为相对对立的 部分。 在设计中主 要考虑就是在 跳转指令中 数据稳 定性的问 题， 以 及在相邻两个周期如果 存在寄存器读写相关的情况下， 指令的 分配和处理。 容易从图4 , 6 看出， 阴影部分表示的 就是寄 存器准 备好阶段， 在相邻两个周期内 对同一寄 存器进 行操作时， 不存在寄存器的数据
16、冲突， 因为下一 周 期的 执行执行阶 段与写回阶段 交迭， 寄 存器的数 据处于稳定的状态。 但是如 果存 在指令跳转，则 需要在取值译码阶段寄存器数据稳定， 此时需要插入 I d l e 状态获得寄存器的写入时间。图4 . 6流水线下寄存器分配和指令跳转处理从电 路的结 构来看， 整个流水 线的设 计主要与系统中寄存 器的 分配有关。 指 令 经过指令译码后 被写入 控制寄 存器， 而控制寄 存器中分为两 类控 制信号。 一 类是对组合逻辑的控 制信号， 而另一 类就 是寄存器的写 选中信号。 由 于对于寄 存器 来说， 控制信号总是在时钟信号的 沿被采样， 因此寄存器控制信号在执行 上比 组合电 路控制 信号晚 有效一 个时 钟。 具体的结构如图4 . 7 所示。C y c l e 1 I
