公钥加密算法之实数域扩散离散Chebyshev多项式文件加密

我们利用RSA公钥加密算法和EIGamal公钥加密算法的算法结构，提出基于有限域离散Chebyshev多项式的公钥加密算法。该算法结构类似于RSA加密算法，其安全性基于大数因式分解的难度或者与ElGamal的离散对数难度相当，能够抵抗对于RSA的选择密文攻击，并且易于软件实现。

一、实数域扩展离散Chebyshev多项式

1、Chebyshw多项式及其性质

Chebyshev多项式是由Tn(x)= cos(n*arccosx)，（-1≤x≤1）所定义的n次多项式，其递推关系为：

且有T0(x)=1，T1(x)=x。

可以证明Cbebyshev多项式具有以下的重要特性。

(1)半群特性

(2)混沌特性

当n>1时，n次Chebyshev多项式映射Tn[-1，1]→[-1，1]的Lyapunov指数λ=In n>0，所以它是混沌映射，其分布函数为：

2、实数域扩散离散的Chebyshw多项式

由于Chebyshev多项式是代数多项式，因此可以很容易地把式(1)扩展到实数域，得到实数域扩散离散Chebyshev多项式Fn(x)的定义如下：

设n∈N，实数|x| >1。P为非零实数且|p|>1。实数域扩散离散Chebyshev多项式迭代关系表达式为：

且有Fo(x)=1 mod p，F1（x）=x mod p，本文有关Chebyshev多项式Fn（x）的讨论和计算都在实数域上进行。

实数域扩散离散的Chebyshev多项式还保留着其原来作为加解密基础算法的半群特性。根据半群特性在实数域中的定义，可知其在有限域上可表示为：

公钥加密算法之实数域扩散离散Chebyshev多项式加密

由于半群特性的存在，使得有限域Chebyshev多项式可以用来构造公钥体系。

二、实数域扩散离散的Chebyshey多项式的公钥算法

提出的公开密钥加密算法与RSA加密算法相似，其安全性都是基于大数因式分解的难度，所不同的是它利用混沌映射进行迭代，并利用实数域扩散离散的Chebyshev多项式的半群特性。加密算法的描述主要分成3个部分，即密钥产生、加密和解密。

1、密钥产生

①Alice随机选取2个大素数p和q，它们具有相同的长度；

②计算N=bq和φ=(p2-1)(q2-1)；

③随即选取整数e，使得1<e<φ声并且gcd(e，φ)=1；

④用欧几里德扩展算法计算d，以满足ed-1 modφ；

⑤随机选择一个整数x0，且x0>1，计算Fd（x0）= Fd（x0）mod N。

此时，Alice的公开密钥为（N，e，x0，Fd（x0），私人密钥为(N，d)。

2、加密

Bob为了加密消息M。须完成以下步骤：

①获得经过认证的Alice的公钥（N，e，x0，Fd（x0）；

②将消息变换成一个整数M；

③计算Fed（x0）=Fe(Fd (xo)）mod N．X=M．Fed（x0）和Fe（x0）=Fe（x0）mod N；

④发送密文C→（Fe（x0），X）给Alice。

3、解密

①Alice收到密文C=（Fe（x0），X）；

②使用密钥(N，d)计算Fde（x0）=Fd（Fe（x0））mod_N;

③求M=X/Fd．e（xn）。

整数e和整数d在传统的RSA加密算法里面称为加密指数和解密指数，相应的N为模数。与RSA相比，我们提出的算法有两个步骤与RSA算法是不同的。在步骤(2)③中，我们使用实数域扩散离散的Chebyshev多项式的迭代来加密明文，即Fde（x0）=Fd（Fe（x0））modN和M=X/Fd*e(x0)而RSA加密算法使用C=Me (mod N)进行加密；在步骤(3)②中，我们同样使用实数域扩散离散的Chebyshev多项式的迭代来解密密文，即Fde（x0）=Fd（Fe（x0））modN和M=X/Fd*e(x0)，而传统的RSA使用M=D(mod N)来解密密文。

三、加密算法性能分析

1、合理性分析

Chebyshev多项式迭代公式为：

由n维Chebyshev多项式的半群特性，得：

式中，R∈Z，s∈Z。

将上式取模为任一个大于1的整数N得：

尽管x的取值范围有所变化，但是这不改变上述的半群特性，正因为这样，上述新算法显然是正确的。因为：

所以M= X/Fd (Fe(x0)mod N。

2、安全性分析

加密算法与RSA有着相同的结构，要破解提出的算法，首先要得到私钥(N，d)，因此其安全性与RSA相当。理论上，RSA的安全性取决于因式分解模N的困难性，这从技术上来说是不正确的，因为在数学上至今还未证明分解模数就是攻击RSA的最佳方法，也来证明分解大整数就是NP问题，而事实上，人们设想了一些非因子分解的途径来攻击RSA体制，但这些方法都不比分解N来得容易。因此，所提加密算法的安全性是可靠的。

同时根据Chebyshev多项式迭代关系，Fn(x)的多项式又表达为：