公钥算法的优化

加密算法的两个重要指标是加密强度和速度。在实现上，可以用各种技术来提高算法速度。
加密算法分为密钥生成和加解密，主要优化加解密部分。
Amdahl定律：优化一段代码的效果，取决于其执行时间占全部执行时间的比例。

优化工作的方向

充分利用CPU特性，如流水线和指令并行

针对加密算法本身做一些优化

编译器也会做一些优化：编译器的优化很保守(保证正确性)，且一些优化对于程序员来说简单，对编译器来说很难

软件优化一般方法

利用指令并行：调整代码顺序，使相近的两条指令的数据不相关
将条件分支指令按照概率和计算量排列次序

如先计算一个定值，先计算一个字符串的长度

避免使用耗时的指令：如左右移指令不能与任何其他指令配对形成流水，阻断了流水线
在循环中避免使用条件跳转指令：条件跳转指令会产生不可预见的指令流，容易分支预测失败

展开加密循环和函数：减少了条件指令和计算指令，将变量转化为常量，减少流水线的阻断和指令预取的作废

限制变量的数量：寄存器有限
变量长度与CPU内部寄存器长度相同:否则，需要用别的指令来辅助存取，增加了指令周期数

优化举例

问题
乘法时，若输入是0，该怎么办？ 乘法输入为0，则将其替换为2的16次方(17位数)，如果乘法输出是2的16次方，则将其替换为0。 正确性：0和2的16次方，在进行异或和加法时，结果一致；但是0没有乘法逆元，2的16次方为17位，故可以定义一个数，以2的16次方的性质(存在逆元)存在，但又能以16位的大小(数0)传递。
乘法的取模操作太耗时！
解决：高低算法：设p的高16是a，低16是b，则
p=a(216+1)+(b−a)⟹p≡b−amod(216+1),即计算(b−a)−[(b−a)>>16]

其他优化

查表法(指令周期大大减少)：预计算和存储一个生成元e的指数对数表，则a*b可表示为:
logea+logeb=logeab,查表得ab

提供128比特寄存器，直接操作128比特块

字节顺序控制

类型：大端寻址，小段寻址

网络地址

问题：不规定哪种顺序，会导致错误
解决：网络字节顺序按大端地址，主机字节顺序任意
问题：字节反转时，如果一个比特一个比特重排，则需n(n为比特数目)次操作
解决：利用指令并行来加速；或用特定快速比特算法。

注意：对于大端寻址而言，高位放在低地址，但单个字节内部的顺序不变