基于环面自同构的公钥加密算法

公开密钥加密算法，也称为非对称算法，其主要特征为加密密钥与解密密钥不同，加密密钥是可以公开的，并且很难从加密密钥计算出解密密钥，所以，公钥加密算法被广泛应用，接下来，我就给大家介绍一种基于环面自同构的公钥加密算法。

一、环面自同构

环面自同构（TorusAutomorphisms）是一种典型的混沌映射，其表达式如下：

其中，A是一个形如的2×2的矩阵；a，b，c，d皆为整数；且detA=1；mod1表示只取小数部分，即xi，yi∈（0，1）。

k=a+d为A的迹，则特征多项式为f（λ）=λ2-kλ+1，其较大的一个特征值为：

当k2-4>0即k<2时（只考虑k为正），自同构A具有强烈的混沌特性。环面自同构的周期轨道，它由坐标为ξ=p1/q1，η=p2/q2的有理点组成，其中pi，qi为整数。使pi，qi互素，g为q1，q2的最小公倍数。去分母，使M成为Z2（整数向量的网格）上的映射。

因此，将映射（1）扩展到[0，N）×[0，N）上。设xi=Xi/N，yi=Yi/N，x≤Xi，Yi<N，且Xi，Yi为整数。则：

也即是：

所以，可以改写映射（1）为：

其中X，Y，N为整数，而其他参数与映射（1）要求相同。

将素数分为3类。在映射（2）中N为素数的情况下，它的周期根据这3类素数，有着3种不同类型的周期轨道。确定方式如下：

定义整数d，

其中k2-4=n2D，D为square-free。

若L（d，N）=-1，素数N为inert，映射（2）的周期为N+1的因子。若L（d，N）=1，素数N为splits，映射（2）的周期为N-1的因子。若L（d，N）=0，素数N为ramifies，若k≡2（modN），映射（2）的周期为N或1；若k≡-2（modN）则为2N或2。其中L（d，N）是勒让德符号。

二、基于环面自同构的公钥加密算法

笔者提出的公开密钥加密算法与RSA相似，其安全性都是基于大数因式分解的难度，所不同的是利用混沌映射进行迭代，并利用了该映射的周期性。

因为映射（2）是周期性的，所以：

即：

1、加密算法的描述

加密算法的描述主要分成3个部分，即密钥产生，加密和解密。

密钥产生：

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

（2）计算N=pq，φ=（p3-p）（q3-q）；

（3）随即选取整数e，使得1<e<φ，并且gcd（e，φ）=1；

（4）用欧几里德扩展算法计算d，以满足ed≡1modφ。

此时，Alice的公开密钥为（N，e），私人密钥（N，d）。加密：

1）Bob获取Alice的公开密钥（N，e）；

2）将需要加密的信息表达成整数m1，m2，且0≤m1，m2<N；

3）计算，

4）将密文ca，cb，cc，cd传送给Alice。

解密：

1）Alice接收到密文ca，cb，cc，cd；

2）计算，

3）则信息m1=pa，m2=pd。

值得注意的是，公式（4）中，矩阵中1和m1m2-1的位置是可以任意交换的，这不影响信息的加密和解密的效果。

2、加密算法的证明

设T为映射（2）的周期，即AkT+1=A（modN）。由上节可知，如果N为素数，则映射（2）的周期T可以看成（N+1）（N-1）N即N3-N的因子：

若N=p，则映射（2）的周期Tp是p3-p的因子；因为φ=（p3-p）（q3-q），Tp也就必是φ的因子。又ed=1modφ，所以ed=1+k<=1+k1Tp。因此：

Aed=A1+kφ=A1+k1Tp=A（modp）。

同理可得:

Aed=A1+kφ=A1+k2Tq=A（modq）。

根据中国剩余定理，N=pq，所以Aed=A1+kφ=A1+k′T=A（modN）。

3、简单的例子

下面举一个例子来进行说明：Alice随机选取2个大素数p=3391和q=3793，计算N=12862063，φ=2127805021604586885120。Alice选取的e=65537，通过欧几里德扩展算法计算d=36493169420076531713。Alice的公开密钥就是（N，e），私人密钥就是（N，d）。

为了加密消息m=12345674567890，Bob将消息表示为m1=1234567，m2=4567890，再使用Alice提供的公钥（N，e），根据公式（4）运算，得出ca=10495137，cb=8311873，cc=5249972，cd=10914291。Bob将密文ca，cb，cc，cd传给Alice。Alice则根据公式（5）和私人密钥（N，d）来计算出m1=1234567，m2=4567890，再将其组合成为m=12345674567890。

4、软件实现

我们所说的公钥算法步骤简洁，运算简单，与RSA相似，容易软件实现。但是需要注意的是，本加密算法的安全性基于因式分解2个大素数的乘积，在运算中需要涉及大整数的存储和运算。程序语言中提供的整数类型是不能满足需求的，所以需要单独定义。

其次，本加密算法最主要的运算就是矩阵的乘方。采用快速矩阵乘法算法将大大加快运算速度。

计算矩阵A的n次方：X=I；

for（i=n.bitsnumber（）；i>0；i--）

{

X=X2；

if（n.bitat（i）==1）

X=XA；

}

其中：n.bitsnumber（）表示取n的二进制的位数；n.bi2tat（i）则表示n的第i位的值。

三、加密算法的安全性

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

在特定的条件下，RSA的实现细节的漏洞会导致对算法的攻击：选择密文攻击，公共模数攻击，低加密指数攻击以及低解密指数攻击。

RSA的选择密文攻击对笔者提出的基于环面自同构的算法是无效的。这种攻击方式主要有3种形式：明文破译、骗取仲裁签名和伪造合法签名。这3种形式都利用了指数运算保持了输入的乘积结构，也即是：

但是对于我们的加密算法，X和Y都是二阶矩阵，显然（XY）dmodN=XdYdmodN是不成立的，因为矩阵的乘法是不具有可交换性的。

公共模数攻击依然有效。设M为含有消息m1，m2的矩阵，2个加密密钥为e1，e2，公共模数N。经过加密运算得出密文矩阵为C1，C2。由于e1，e2互素，可以找到r和s，满足re1+se2=1。假设r为负，则：（C-11）-r×Cs2=MmodN。因此。在一组用户之间共享模数N是不安全的。

采用小的e，d可以加快加密和解密的速度，而且所需的存贮空间小；但是如果e，d太小，则容易受到低指数攻击，包括低加密指数攻击和低解密指数攻击。例如，对于加密密钥e，如果消息相同，利用e个消息就可以进行低加密指数攻击。因此，一定要选择较大的e，d，且保证MemodN≠Me。

因此通过精心考虑基于环面自同构的公钥加密算法实现的细节是可以避免这些安全漏洞的。