论文部分内容阅读
自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基于双基数链的标量乘算法进行比较,实验结果证明我们的算法显著优于前人算法。