学位论文 > 优秀研究生学位论文题录展示

椭圆曲线标量乘法快速实现研究

作　者: 王圆圆
导　师: 殷新春
学　校: 扬州大学
专　业: 计算机应用技术
关键词: ECC 标量乘法边际信道攻击双基数链底层域混合坐标
分类号: TN918.2
类　型: 硕士论文
年　份: 2007年
下　载: 111次
引　用: 4次
阅　读: 论文下载

内容摘要

自1985年Koblitz和Miller分别独立提出椭圆曲线密码体制(Elliptic Curve Cryptology, ECC)后,由于ECC本身计算速度快,存储空间小,带宽要求低,特别适用于Smart卡和无线应用环境等优点,很快得到了广大研究者的关注。标量乘法是ECC实现过程中最基本、最耗时的运算,研究标量乘法有两个切入点:一是研究标量k的有效表示;二是寻求底层域快速运算算法,在前人工作的基础上,本文主要对以下几点进行了详细研究。(1)从底层域快速算法出发,结合抵抗边际信道攻击的方法,对传统标量乘法Fixed-base comb算法进行改进,给出了一个安全、快速的Fixed-base comb算法。根据其特点,利用牺牲乘法操作以降低求逆操作的方法,分别用2kP、2P+Q的快速算法对Fixed-base comb算法的预计算阶段和赋值阶段进行改进,显著地提高了计算效率:在素数域上预计算阶段提高70%~80%,而赋值阶段提高38%~43%,同时,改进算法通过对k的预处理,使得算法能够抵抗边际信道攻击。(2)利用底层域2kP、3kP、2P±Q、3P±Q快速算法给出了新的基于双基数链的标量乘法快速算法。借助于双基数表示的稀疏性质和底层域快速算法的优势,新算法大大减少了底层运算中求逆操作的次数,有效提高了算法的执行效率。实验证明,相同双基数表示下,该算法优于Dimitrov给出的基于双基数链的算法:素数域上,密钥长度160bit时算法效率提高19%-22%,192bit提高22%-25%,224bit提高26%-30%,256bit提高35%左右。(3)定义了双基数系统的一个子集,给出了近似规范双基数子集表示法的贪婪算法,并在此基础上构造了新的标量乘算法。同带符号双基数系统一样,该子集能表示所有整数,而其固有的2-整数递增的特质,使得它相比其它求双基数表示的算法大大节省了时间。同时,双基数子系统将预计算空间从n2降低到3n-2,节省了大量预计算量和存储空间。由于搜索空间的降低,整数Sub-NCSDBNR个数稍微多于其NCSDBNR个数,所以在基于Sub-NCSDBNR的标量乘法算法中,结合目前最新研究成果直接计算、混合坐标进行优化,给出了使用预计算表和不使用预计算表两个标量乘快速算法。前者适合固定基点的标量乘,后者固定基点随机点均适用。最后,对新算法从运算量、存储空间上分别与传统固定基窗口算法和Dimitrov基于双基数链的标量乘算法进行比较,实验结果证明我们的算法显著优于前人算法。

全文目录

摘要  2-3
Abstract  3-7
第1章引言  7-14
  1.1 椭圆曲线密码的研究背景和意义  7-10
  1.2 标量乘法的研究思路与热点  10-12
  1.3 本文的主要工作与结构安排  12-14
第2章椭圆曲线代数与标量乘算法  14-25
  2.1 椭圆曲线的定义  14-16
  2.2 椭圆曲线加法群的运算法则  16-19
    2.2.1 y~2 = x~3+ax +b 的加法规则  17-18
    2.2.2 y~2+x y = x~3+ax~2+b 的加法规则  18-19
    2.2.3 y~2+c y = x~3+ax+b 的加法规则  19
  2.3 经典标量乘算法  19-25
    2.3.1 二元法  20-21
    2.3.2 非相邻表示型  21-22
    2.3.3 窗口方法  22-25
第3章改进的FIXED-BASE COMB 安全快速算法  25-35
  3.1 FIXED-BASE COMB 算法介绍  25-26
  3.2 2~KP 与2P+Q 快速算法  26-27
  3.3 边际信道攻击  27-30
  3.4 改进的FIXED-BASE COMB 算法  30-32
  3.5 改进算法的性能分析  32-34
  3.6 本章小结  34-35
第4章新的基于双基数链的标量乘法快速算法  35-47
  4.1 双基数表示与双基数链  35-40
  4.2 本章中用到的底层域快速算法  40-41
  4.3 新的DBNS 快速算法  41-43
  4.4 实例与比较  43-46
  4.5 本章小结  46-47
第5章基于双基数子集表示的快速标量乘算法  47-59
  5.1 双基数子集与双基数系统  47-52
  5.2 混合坐标  52-53
  5.3 基于双基数子集表示的标量乘算法  53-55
    5.3.1 使用预计算表  53-54
    5.3.2 不使用预计算表  54-55
  5.4 算法性能分析  55-57
  5.5 本章小结  57-59
第6章结束语  59-60
参考文献  60-67
致谢  67-68
攻读硕士学位期间发表的论文及参加的科研项目  68-69
攻读硕士学位期间参加的学术会议和研讨班  69

椭圆曲线标量乘法快速实现研究

内容摘要

全文目录

相似论文