椭圆曲线加密算法之大数计算 - 夏冰加密软件技术博客

公开密钥加密算法总是基于一个数学上的难题，比如RSA加密算法的安全性基于数论中大素数分解的困难性，所以，RSA需采用足够大的整数。因子分解越困难，密码就越难以破译，加密强度就越高。椭圆曲线加密算法的提出正好可以解决这个问题，其依据就是定义在椭圆曲线点群上的离散对数问题的难解性。

一、椭圆曲线加密算法

1、椭圆曲线基本协议

设椭圆曲线为E(Fq)，在加法群中的阶为n，我们设点P0(1，1)为该椭圆曲线上的点，A和B为进行通信的双方用户。该椭圆曲线上的消息加密及解密协议如下：

设素数p和q满足q=p；A的公钥为点Pa=ka×P0，私钥为ka；B的公钥为点Pb=kb×P0，私钥为kb；m为消息。

(1)随机产生k，计算(x,y)=k×Pb；计算R=k×P0；计算c=m×x(modp)；发送密文(R,c)->b。

(2)计算(x,y)=kb×R；计算m=c÷x(modp)，m即为经由解密得到的明文。

2、椭圆曲线加密体制中的有关计算

作为公开密钥加密算法的一种，椭圆曲线加密体制要用到点乘、点加、模乘、模加、模逆、模幂这些基本运算，点加和点乘属于椭圆曲线群上的运算，它们的执行速度直接决定着椭圆曲线的加密速度。为了提高速度，可从采用高速算法或实现并行性两方面解决。

二、大数计算的典型算法

对于大数，大家比较关心的是整型数据类型，因此仅对整型数据类型部分展开讨论。

1、大数的常规运算的实现

对于加减法运算，通过将A、B按位对齐；低位开始逐位相加(减)；对结果做进进(借)位调整即可实现。乘法运算引入sum2、sum1作为中间量；在n的每一位上处理m；通过每一层循环，实现乘法的加法化；对结果做进借位调整。出发运算则要引入al来标识a的长度，bl来标识b的长度；测算a和b的长度；从高位开始，对位做减法，并完成借位；然后高位开始逐位计算商并整理商，产生余数。余数也可作为取模的结果。

2、大数模乘算法

大数模乘算法在密码学领域有广泛的应用，它是公钥密码的基本运算。模乘一般表示为：C=(AB)modN,0≤A,B<N，其中A、B、N都为k比特二进制大整数。

以下是目前具有代表性的几种大数模乘算法：

（1）Blakley的加法型模乘算法

Blakley算法每次计算都对累加中间结果C进行模简化，以使结果小于N。Blakley算法不含乘法和除法，但加法法和模简化过程只能逐位处理,实现效率不够理想。针对Blakley算法，人们相继提出了不少改进方法，这些改进主要可分为二大类：减少乘法过程的加法次数，即减少乘数中非0个数；提高模简化速度等。F.E.Su和T.H.Wang于1996年提出了一种无需大数比较而直接将C限制在范围内的模简化方法，明显提高了效率。围绕减少加法次数，Koc利用窗口技术，通过以m位为一组结合冗余二进制数方法从右到左对乘数重编码和预计算，提出了窗口模乘算法。不久又出现了有符号滑动窗口模乘算法和无符号滑动窗口模乘算法，也是目前较为理想的加法型模乘算法。

（2）Knuth算法

Knuth算法的优点是将商计算转化为一个25位数与t位数的除法，由于算法中仍含除法，实现效率受影响较大。1987年Barrett提出了第一种无除法的估商型模乘算法，其基本思想是用乘法和预计算替代除法。Barrett算法的最大优点在于整个计算不含除法，仅用最基本的字乘和字加即可完成。1992年Quisquater提出了另一种估商型模乘算法，其特点是可快速进行商计算，后来Walter亦提出了类似的思想。Quisquater算法进一步简化了估商计算，但整个模幂过程中需附加一次归范化和反归范化计算。

（3）Montgomery算法

Montgomery算法采用模加右移法，避免了公钥加密中求模算法的除法运算，使运算量大为减少。Montgomery算法不含除法，基本运算为字乘和字加，通过剩余系转换方法计算模乘，极大地提高了模乘计算速度，被广泛应用于各种软硬件实现中，人们也从高效率、低空间、高安全等角度对算法进行了各种改进。Montgomery型算法最后都需对作一次条件减法，由于不同乘数所耗费的时间和能量不同，给时间攻击、能量攻击及电磁攻击留下了余地，为此Walter、Hachez和Quisquater通过深入研究，提出了一种可有效阻止这些攻击的Montgomery型无减法模乘算法，而且实现效率也相当理想。

3、大数分解

大数分解问题涉及到高可信度的计算问题及很多数学技术的进一步研究和运用，包括信息论，竞争的复杂性等。数论学者和计算机学者已经得到了许多实际有效的方法并已经引起人们的普遍关注。大数分解质因子问题涉及到了素数判别和大数分解两方面的内容。

而进行素数判别和大数分解最直接的方法就是试除法，即对于整数n来说，用2,…,n-1去试除，然后判定n是否素数，分解式是什么。作为最简单的一个方法，试除法对较大的数(20位左右)进行分解是要耗费很多时间。费马方法给定n，若n是两数平方差n=a2-b2，则n=(a+b)(a-b)是n的一个因子分解，但该方法只有当n有两个几乎相等的因子时，才比较快。

三、椭圆曲线加密的实现

encryptogram()//加密

{

inti;time_tt;

srand((unsigned)time(&t));

rando(p2);

intproduct〔301〕,quo〔301〕,arith〔201〕;

for(i=1;i<301;i++)　product〔i〕=0;multiply(p1,p2,product);

rando(p3);

division(product,p3,quo,arith);

intp4〔101〕,prod〔301〕;

random(p4);