RSA
密钥产生
选择两个素数，p和q 计算n=pq 计算z=(p-1)(q-1) 选择e使得：gcd(e, z)=1 且 e<z 确定d使得d*e mod z =1 且 d<z 公钥KU={e, n}，私钥KR={d, n}
为了保证安全性，RSA算法实际使用的密钥长 度多达几百至上千bit
密钥产生
RSA
加解密运算
加密算法为C=Me mod n 解密算法为M=Cd mod n
实现RSA算法
密钥产生算法远没有加解密算法常用， 故一般只考虑用硬件加速加解密算法， 即加速模幂(modular exponentiation)运 算。 高速实现模幂运算是一个数学问题，有 很多相关的研究。
实现RSA算法
加密解密算法RC 加密解密算法 实现的调研报告
仲力 王宇旸
概述
密码学有对称密码学和公钥密码学两大 分支。目前我们重点调研了对称密码学。
在对称密码学中，加密方和解密方使用相同 的密钥。 DES和AES是目前最主要的对称加 密算法。 在公钥密码学中，加密方和解密方使用不同 的密钥。 RSA和ECC是目前最主要的公钥加 密算法。
Loop Unrolling
Multiplexer
Register
Combinational Logic k-rounds loop unrolling Combinational Logic
...
Combinational Logic
Internal Pipelining
Multiplexer
Register 1
Pipeline Stage 1 k Round
Register 2
Pipeline Stage 2 ... Register k
Pipeline Stage k
k-stage external pipelining
4种结构的速度比较
speedba = 1 / (#rounds*clock_period) speedul / speedba = (1 + t)/(1+t/k)，其中 t=(m+r)/c k-round internal pipelining，理想情况下， clock_period可以比basic结构提高k倍（仅对非 反馈模式有效）。 对k-round external pipelining，理想情况下， 速度比相同clock_period的basic结构提高k倍 （仅对非反馈模式有效）。
是否需要在一块芯片（或FPGA）上同时实现加 解密算法
Feistel结构的算法，同时实现加解密算法比只实现 加密算法增加的area不到10%；非Feistel结构的算 法area增加较多(AES算法会增加60%的area) 对于RC系统，如果需要同时实现加解密算法，有两 种方法 :（1）使用动态可重构；（2）在一个配置 里同时实现加解密功能。方法2在加解密功能切换 速度比1快，但会消耗更多的area，而1可以利用这 些area对吞吐率进行优化。
4种结构的area比较
Basic结构消耗的area最少。 Internal pipelining只比Basic结构增加了 少量的area（用于pipeline stage间的寄 存器）。 k-round unrolling/external pipeling大约 会增加k倍的area。
其他影响硬件实现的因素
公钥密码学
在公钥密码学概念提出后的几十年中，只有两 个满足这些条件的算法（RSA, 椭圆曲线密码 体制）为人们普遍接受。 公钥密码学的安全性一般要依赖于某种计算难 题：
RSC基于大数因数分解难题 ECC基于椭圆曲线上的离散对数难题
公钥密码学算法要比对称密码学算法慢几个数 量级。
RSA简介
RSA是目前使用最广泛的公钥密码学算法
其他影响硬件实现的因素
是否要实现子密钥生成算法 如何实现子密钥生成算法
算好所有的子密钥存在寄存器中，以后不再 重复计算（loop unrolling/external pipelining结构必须使用这种方式） on-the-fly的计算方式（可以省去保存子密 钥的寄存器）
NIST对5种AES候选算法硬件实 现的评估
内容安排
对称密码学
DES AES 对称密码学综述 (5min) (5min) (10min) (5min) (5min) (5min)
公钥密码学
RSA 椭圆曲线密码学(ECC)
小结和进一步的调研方向
对称密码学——DES算法
DES算法特征
DES设计时只考虑方便硬件实现。因此很 方便用硬件实现，但难以用软件有效的 实现。 DES使用64位分组和56位密钥。 DES算法是Feistel结构，因此加密算法和 解密算法是相同的，只是子密钥的使用 次序相反。
AES算法(Rijndael)
AES算法
AES是NIST从5种候选算法(MARS, RC6, Rijndael, Serpent, TwoFish)中评选出来的，能 够高速的在各种软硬件平台上实现是重要的选 择标准。 最终Rijndael当选。 AES使用128位分组，128、192或256位密钥， 使用不同长度的密钥时算法执行的轮数不同。 AES不是Feistel结构的，其加解密算法不相同。
ReБайду номын сангаасister 1
Pipeline Stage 1 One Round
Register 2
Pipeline Stage 2 ... Register k
Pipeline Stage k
k-stage internal pipelining
External Pipelining
Multiplexer
Xor软件硬件都很容易做 置换函数e和P软件很难有效的实现；而硬件只 需要定制相应的数据通路，很容易实现。 S-Box运算软硬件均可用查表实现；但软件只 能串行地查8个表，而硬件可以并行查表。 数据长度不规整(6,4,48bit)，不利于软件有效 实现。
DES小结
DES难以用软件有效的实现，但很容易用 硬件实现 3DES算法要做3次DES运算，软件实现的 速度更低
模幂运算可以分解为多个模乘运算 如何分解，用最少的模乘来实现模幂
如计算x4, 可以计算x4=x*x*x*x, 这需要4次 模乘；也可以x2=x*x, x4 = x2 * x2, 只需要 两次模乘。 这是一个加法链问题：对序列a0, a1, ... ar, 其中a0=1, ar =e, 对任意的k, 都存在i,j<k使得 ai+aj=ak，求满足上述提条件的最短序列。
1938（非反馈 模式）
对称密码学算法硬件实现综述
硬件实现的指标
吞吐率(Throughput) 消耗的硬件资源(Area) 效能(Efficiency=Throughput/Area) 延迟(Latency)
硬件实现的4种不同的设计目标：
最小化资源消耗 在无限的资源下最大化吞吐率 在固定的资源下最大化吞吐率 最大化效能
MixColumns是1个矩阵乘法运算(两个 4*4的8bit方阵相乘，其中一个方阵是常 数)。用到的加法和乘法是定义在有限域 GF(28)上的，加法实际是Xor；乘法可以 通过移位和Xor操作方便的实现，对软件 也可以通过查表法加速实现。
AES中运算的特点
AES所有的操作数长度都是8bit的2n倍， 并且没有复杂的位运算，因此很容易在 各种平台上（8位、32位、64位机，智能 卡等）用软件有效的实现。 研究表明，AES算法有很高的指令集并行 性（ILP），可以很好的利用现代CPU的 流水线、超标量等技术。
AES算法中主要的运算
AddRoundKey是一个128bit分组和128bit 子密钥的Xor操作； SubBytes是16次S-Box操作，AES使用的 一个8bit输入8bit输出的S-Box； ShiftRows是3次32bit的循环移位操作(分 别是循环左移8位、16位和24位）；
AES算法中主要的运算
Rijndael和Serpent的吞吐率和效能都很 高。 RC6和Twofish的吞吐率效能处于平均水 平，但可以在很小的area上实现。 MARS的吞吐率、效能都是最差的，不太 适合硬件实现（主要原因有异种的循环 结构，大的S-Box等）。
公钥密码学
公钥密码学
公钥密码算法应满足的条件
产生一对密钥（KU,KR）在计算上是容易的 已知公钥KU和明文M，计算密文C是容易的 用私钥KR解密接收到的密文C是是容易的 已知公钥KU，攻击者要确定私钥KR在计算 上是不可行的 已知公钥KU和密文C，攻击者要恢复明文M 在计算上是不可行的
实现RSA算法
已证明加法链问题是NP完全问题 有多种求次优解的启发式算法：
Binary Method m-ary Method Factor Method Power Tree Method
实现RSA算法
实现模乘运算，有以下路线
先作乘，再取模 Blakley's method Montgomery's method
AES也很容易用硬件实现
平台 450MHz Pentium II 优化技术 吞吐率(Mbits/s) 针对MMX指令集优 243 化 300（反馈模式）
40MHz Xilinx 2-round loop VirtexXCV100 unrolling 0BG560-4 5-round external 同上 pipelining & one internal pipeline
密钥产生需要做以下工作：
确定两个大素数p和q 选择e, 并计算d
目前选择素数一般是随机挑选一个奇数n，再 用Miller-Rabin等概率算法判断n是否是素数。 求e和d一般使用扩展Euclid算法：随机选择e<z， 用扩展Euclid算法求gcd(z, e)，并且当gcd(z, e)=1时，扩展Euclid算法还能同时求出d。