信息安全与保密实验(2)

《信息安全与保密实验(2)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、学习模幂运算－平方和乘算法姓名：李锦学院：计算机学院班级：计算机二班学号：07095203制作日期：2010.5.2随着各种加解密算法密钥长度的逐步增加，在一些具有安全性需求的芯片设计中，大规格数据运算的硬件实现已成为硬件设计的主要考虑因素和设计难点．比如RSA等基于大数分解的公钥密码算法，虽然目前密钥长度已达1024位，但是仍然不能避免将被破解的厄运，致使密钥还需进一步增加．这种运算规格的增长不仅使加解密运算速度降低，而且增加了硬件实现的难度．1CSTU安全芯片体系结构简介随着人们对安全需求的不断增加，采用固定或单一加解密算法的产品已经无法满足人们的需求，

2、目前的安全产品需要经常更换加解密算法甚至改变整个安全策略．适应这种需求常用的方法是在基本运算器之上，使用软件编程的方式灵活的实现算法的转换．但是面对不断升级的软件破解技术的挑战，以及软件方式的低速率性，各种加解密算法也由软件实现向硬件电路实现过渡．为解决这一矛盾．可支持多种加解密算法的硬件安全产品就应运而生，其中基于可重组方式设计的安全芯片无疑又具有领先优势．CSTU保密终端安全芯片采用了可重组设计思想，综合分析了当前大量使用的DES，AES，IDEA，RSA，MD5等十余种加解密算法的实现过程，支持对称、公钥、摘要密码算法及用户隐秘算法，提供这些算法实现所

3、需的IP平台，不同的用户可以根据自己的需要在平台上进行二次开发，形成自己定义的安全算法及策略．CSTU安全芯片可用于保密电话、安全卡证或移动安全终端等产品中，这些产品的共同特点是对规模要求比较严格，对公钥密码算法的速度要求不高．为提供对公钥密码算法和数字签名算法的支持，大数运算器成为CSTU安全体系中关键的核心IP．根据实际需求，本设计在满足硬件规模尽可能小同时支持尽可能多的运算功能和多种规格的数据运算的条件下，最终保证整个系统的灵活性．2模幂运算模幂运算是RSA的核心算法，最直接地决定了RSA算法的性能。针对快速模幂运算这一课题，西方现代数学家提出了大量的

4、解决方案，通常都是先将幂模运算转化为乘模运算。例如求D=C**15%N，由于：a*b%n=(a%n)*(b%n)%n，所以：C1=C*C%N=C**2%NC2=C1*C%N=C**3%NC3=C2*C2%N=C**6%NC4=C3*C%N=C**7%NC5=C4*C4%N=C**14%NC6=C5*C%N=C**15%N即：对于E=15的幂模运算可分解为6个乘模运算，归纳分析以上方法可以发现对于任意E，都可采用以下算法计算D=C**E%N：D=1WHILEE>=0IFE%2=0C=C*C%NE=E/2ELSED=D*C%NE=E-1RETURND继续分析会发

5、现，要知道E何时能整除2，并不需要反复进行减一或除二的操作，只需验证E的二进制各位是0还是1就可以了，从左至右或从右至左验证都可以，从左至右会更简洁，设E=Sum[i=0ton](E*2**i)，0<=E<=1，则：D=1FORi=nTO0D=D*D%NIFE=1D=D*C%NRETURND这样，模幂运算就转化成了一系列的模乘运算。3.模乘运算对于乘模运算A*B%N，如果A、B都是1024位的大数，先计算A*B，再%N，就会产生2048位的中间结果，如果不采用动态内存分配技术就必须将大数定义中的数组空间增加一倍，这样会造成大量的浪费，因为在绝大多数情况下不会

6、用到那额外的一倍空间，而采用动态内存分配技术会使大数存储失去连续性而使运算过程中的循环操作变得非常繁琐。所以模乘运算的首要原则就是要避免直接计算A*B。设A=Sum[i=0tok](A*r**i)，r=0x10000000，0<=A

7、成：C=0;FORi=nto0C=C*r%NC=C+A*B%NRETURNC这样产生的最大中间结果是A*B或C*r，都不超过1056位，空间代价会小得多，但是时间代价却加大了，因为求模的过程由一次变成了多次。对于孤立的乘模运算而言这种时间换空间的交易还是值得的，但是对于反复循环的乘模运算，这种代价就无法承受，必须另寻出路。蒙哥马利模乘由于RSA的核心算法是模幂运算，模幂运算又相当于模乘运算的循环，要提高RSA算法的效率，首要问题在于提高模乘运算的效率。不难发现，模乘过程中复杂度最高的环节是求模运算，因为一次除法实际上包含了多次加法、减法和乘法，如果在算法中能

8、够尽量减少除法甚至避免除法，则算法的效率会大大提高。