公开密钥加密算法,也称为非对称算法,其主要特征为加密密钥与解密密钥不同,加密密钥是可以公开的,并且很难从加密密钥计算出解密密钥,所以,公钥加密算法被广泛应用,接下来,我就给大家介绍一种基于环面自同构的公钥加密算法。
一、环面自同构
环面自同构(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。
因此通过精心考虑基于环面自同构的公钥加密算法实现的细节是可以避免这些安全漏洞的。
小知识之勒让德符号
勒让德符号,或二次特征,是一个由阿德里安-马里·勒让德在1798年尝试证明二次互反律时引入的函数。这个符号是许多高次剩余符号的原型;其它延伸和推广包括雅可比符号、克罗内克符号、希尔伯特符号,以及阿廷符号。
筑牢安全防线:安企神企业助力特种设备机械企业数据防泄密解决方案
西安苛菲特机械设备有限公司 西安苛菲特机械设备有限公司致力于特种设备的发展,专业从事特种设备的研发、制造和销售。目前已成为有色冶金特种设备、大型船舶特种设备、煤化工特种设备的领军品牌,并在业内得到了“ 特种设备专家”的称号。公司以打造国内一流特种设备为使命,主要产品定型为高品质特种(高温、高压、高合金)流量控...
安企神软件——为中国铁道建筑集团有限公司筑牢数据防泄密系统
01公司介绍中国铁建是中国乃至全球最具实力、最具规模的特大型综合建设集团之一,入选世界500强企业、全球225家最大承包商之一等荣誉。公司以工程承包为主业,集勘察、设计、投融资、施工、设备安装、工程监理、技术咨询、外经外贸于一体,经营业务遍及除台湾省外全国31个省市(自治区)、世界20多个国家和地区,企业总资产820亿...
强化终端安全,安企神软件与涂料制造企业共创安全未来
西安经建油漆有限责任公司规模化、专业化、现代化涂料制造企业西安经建油漆有限责任公司,年涂料生产能力20万吨,为中国中西部实力较强、产能较大的涂料制造企业。公司成立伊始便积极承担起重点建设项目及国防军事工业、航空航天工业提供配套涂料科研开发及生产任务。多次受到中国航天科技集团总公司的通令嘉奖,为我国航天事业跻身世界前列做...
全球著名减震器制造商——天纳克携手安企神共筑安全制造新防线
天纳克(北京)汽车减振器有限公司天纳克(北京)汽车减振器有限公司成立于1995年,是天纳克在中国最早投资的合资企业。公司集设计、开发、生产及销售汽车减振器于一身。作为天纳克全球网络的一部分,能充分享受天纳克全球的技术积累经验和国际领先的设计理念,加之先进的生产设备和工艺技术。天纳克(北京)汽车减振器有限公司完全能保证为...
强强联合!安企神软件携手瀚颐共筑汽车行业终端安全防线
瀚颐上海汽车电子科技有限公司EAST瀚颐中国团队成立于2015年。是国际AUTOSAR软件联盟的研发伙伴单位。具备汽车电子硬件设计、软件开发、CAN网络集成、系统集成测试以及项目管理的全面研发能力。专注于汽车电子以及相关产业并拥有25年以上的专业经验,拥有来自于德国和中国业内专家和高管组成的顾问团队,并向全球汽车行业客...