椭圆曲线密码算法及芯片实现方法研究

论文摘要

椭圆曲线密码(ECC)是1985年提出的一种公钥密码算法。在保证相同安全强度下,ECC与另一种公钥密码算法RSA相比,所需的密钥长度更短、存储信息更少、硬件实现效率更高。因此,具有广阔的应用情景。在许多安全标准如IPsec、WAPI中,都包含了ECC的使用。ECC的研究主要包括安全和实现效率两方面。安全的问题在理论上主要围绕离散对数问题、椭圆曲线参数的选取及攻击算法研究等,而在工程上则涉及时间分析攻击、功耗分析攻击、电磁分析攻击和差错分析攻击等。实现效率的问题主要是标量乘k⊙P的计算问题(k为一个大整数而P为椭圆曲线上的一个点),研究的领域包括椭圆曲线标量乘算法研究、有限域运算研究、软硬件体系架构设计和硬件底层数据通路优化等。作为21世纪前后热门研究领域之一,ECC的研究取得了重多的成果,理论上的安全问题已基本得到澄清,现有研究多是针对提高实现效率和在工程上防止攻击等问题而展开。论文在简短回顾ECC研究领域的既有成果基础之上,主要针对特征为2有限域ECC的标量乘实现、有限域乘法器和安全扫描链设计展开了研究,并给出了详实的数据,也对ECC相关技术作了探讨。在前人成果的基础上,主要做了以下的工作并获得了一些成果:1.提出了非平衡模归约算法。基于非平衡模归约算法,设计了一种ECC的可配置加速器。加速器采用类CPU的流水线设计,使用有限状态机产生指令以控制整个算法的流程;采用基于分段运算的域可扩展设计的方法设计运算单元,支持多种不同有限域的运算。2.提出了一种在特征为2有限域上的并行快速实现ECC标量乘运算的方法。该方法利用硬件动态指令调度技术,同时采用指令级并行和线程级并行,提高并行运算的性能。3.提出一种针对一类椭圆曲线密码的硬件实现的攻击方法,并相应提出一种防止该类攻击的简单有效的密码芯片的安全扫描方法,使得在保持高测试覆盖率的同时,并不降低芯片的安全性。4.提出一类有限域乘法器的归一化设计架构并进行复杂度分析。架构可实现参数化的部分并行乘法器,分析结果为应用时的参数选取提供参考。

论文目录

• 摘要
• Abstract
• 目录
• 表格索引
• 图索引
• 1 绪论
• 1.1 椭圆曲线密码的研究背景和意义
• 1.2 椭圆曲线密码的研究现状
• 1.3 研究思路
• 1.4 论文结构安排
• 2 椭圆曲线密码简介
• 2.1 有限域
• 2.2 椭圆曲线
• 2.3 椭圆曲线离散对数问题
• 2.4 椭圆曲线密码相关协议介绍
• 2.5 椭圆曲线密码标量乘运算
• 2.5.1 自左自右扫描位标量乘算法
• 2.5.2 NAF扫描位标量乘算法
• 2.5.3 窗口NAF标量乘算法
• 2.5.4 特征为2有限域中射影Montgomery标量乘算法
• 2.5.5 固定基窗口标量乘算法
• 2.5.6 固定基混合标量乘算法
• 2.5.7 算法的分析比较
• 3 ECC标量乘算法的硬件实现
• 3.1 ECC标量乘的设计基本架构
• 3.2 ECC可配置加速器
• 3.2.1 非平衡模归约算法
• 3.2.2 指令集设计和运算单元
• 3.2.3 VLSI实现结果
• 3.2.4 RSA运算支持
• 3.2.5 加速器设计小结
• 3.3 ECC硬件动态调度加速器
• 3.3.1 ECC并行运算的探讨
• 3.3.2 并行运算架构设计
• 3.3.3 设计的FPGA实现
• 3.3.4 硬件动态调度加速器小结
• 4 有限域乘法器研究
• 4.1 多项式乘法器研究
• 4.1.1 Karatsuba算法
• 4.1.2 Karatsuba乘法器的复杂度分析
• 4.1.3 Karatsuba乘法器的实现
• 4.2 有限域乘法器研究
• 4.2.1 三项式有限域乘法器
• 4.2.2 五项式有限域乘法器
• 4.2.3 任意多项式有限域乘法器
• 5 ECC芯片的测试安全研究
• 5.1 密码芯片的扫描链测试概述
• 5.2 扫描链导致的安全问题分析
• 5.3 一类椭圆曲线密码芯片的攻击方法
• 5.4 密码芯片安全扫描链设计
• 5.5 小结
• 6 ECC相关技术研究
• 6.1 参数化分段线性混沌映射
• 6.1.1 混沌映射
• 6.1.2 分段参数的选择
• 6.1.3 应用考虑
• 6.2 SHA-256算法的快速实现
• 6.2.1 SHA-256算法简介
• 6.2.2 算法分析
• 6.2.3 架构设计和实现结果
• 7 结论与展望
• 7.1 论文总结
• 7.2 工作展望
• 致谢
• 参考文献
• 攻读学位期间发表/录用的学术论文