公开密钥算法不能不知道的 4 个概念

1一些密码学基础

发送者和接收者: 发送者想要发送消息给接收者,并且这个消息是安全的(让偷听者不能阅读这个消息)

 

消息和加密:消息被称作 明文。通过某种方法伪装消息以隐藏它的内容的过程称作 加密。被加密的消息被称作 密文。相应的,把密文转变成明文的过程叫作 解密。

 

消息和加密

 

算法和密钥:密码算法也叫 密码,是用于加密和解密的数学函数。如果算法的保密性是针对于保持算法的秘密,这种算法称为受限制算法。按现在的标准,这种受限制算法保密性已经远远不够。现代密码学使用 秘钥来解决了这个问题。有些算法使用两个不同的密钥,即加密密钥和解密密钥不同。这些算法的安全性就是基于密钥的安全性,而不是算法细节的安全性,这就意味着算法可以公开,即使偷听者知道算法,但是不知道具体使用的密钥,就不可能阅读消息。

 

算法和密钥

 

密码系统:由所有可能的明文、密文、密钥、以及算法组成。

 

对称算法:又叫传统密码算法,加密秘钥能从解密密钥中推算出来,反过来也成立。通常加密和解密使用同一个密钥,称作 单密钥算法或者是 秘密密钥算法。

 

公开密钥算法(非对称算法):用作加密的秘钥不同于用作解密的解密秘钥,而且解密秘钥不能通过加密秘钥计算出来(至少在合理假定的长时间内)。之所以叫作公开密钥算法,因为加密秘钥能够公开,但是偷听者只能使用加密秘钥加密信息,只有用相应的解密秘钥才能解密信息。这里,加密密钥又被称作 公开密钥(简称公钥),解密秘钥称作 私人密钥(简称私钥)。

 

混合密码系统:将对称密码和公钥密码结合起来的密码方式称为混合密码系统。

 

密码分析:密码分析是在不知道密钥的情况下,恢复出明文的科学。成功的密码分析能恢复明文或者密钥。也可以发现密码体制的弱点而得到明文和密钥。(密钥通过非密码分析的方式的丢失叫 泄露 )

 

算法的安全性:那么什么样的算法才是安全的呢?如果破译算法的代价大于加密数据的价值;如果破译算法所需要的时间比加密数据保密的时间更长;如果用单密钥加密的数据量比破译算法需要的数据量少得多。那么你可能是安全的。

 

 

2两把钥匙:公钥和私钥

现比特币仍继续使用公开密钥加密(public-key cryptography,也称为非对称加密)方式进行数据加密,实质是一对数学算法相关的公钥密钥解密的关系,使用通过私钥解开公钥(公开的密钥)后获取本真的信息,此过程是非对称加密算法。

公钥的主要作用:加密;验证签名。

私钥的主要作用:签名;解密。

 

特性:

  • 通过私钥可以计算出公钥,反之则不行。

  • 公钥加密:公钥加密的内容可以用私钥来解密——只有私钥持有者才能解密。

  • 私钥签名:私钥签名的内容可以用公钥验证。公钥能验证的签名均可视为私钥持有人所签署。

 

公钥和私钥

 

使用原则:

①  每一个公钥都对应一个私钥。

②  密钥对中,让大家都知道的是公钥,不告诉大家,只有自己知道的,是私钥。

③  如果用其中一个密钥加密数据,则只有对应的那个密钥才可以解密。

④  如果用其中一个密钥可以进行解密数据,则该数据必然是对应的那个密钥进行的加密

 

举个栗子: 

我们来认识两个密码学上的知名人士Alice和Bob,现在他们是一对地下情侣,以及一个自作多情的第三者Eve。

 

Alice和Bob想互相写情书,但是他们不想让Eve偷看到他们互递情书内容,于是他们准备给情书加密。Alice加密后,把情书给Bob看,但是情书已经加密了,Bob看不懂,Alice意识到她还得把解密的密钥给一起发送给Bob。

 

但是如果Alice直接把密文和密钥一起发送给Bob行不行呢?如果一起发送,Eve两个都会拿到就可以像Bob一样看情书的内容了,也就是说,同时发送密钥,Eve也能完成解密。Alice一筹莫展,密钥必须发送给Bob,但又不能发送,哎呀她要纠结死了。

 

后来,Alice想到,既然必须给钥匙,那么我可以准备两把钥匙啊,于是她和Bob商量这么做:

1)两人准备两把配对钥匙,一把用来加密(公钥),一把用来解密(私钥)。

2)Bob把他的公钥发送给Alice,这时被Eve截获,Eve很兴奋,“嗨呀,拿到你们的钥匙了”

3)然后Alice收到Bob的公钥后,用Bob的公钥加密,然后把密文发送给Bob。这时又被Eve截获,“嗨呀,看我破解你的密码,咦?怎么打不开呢?”

4)Bob拿到Alice给他的密文后,用自己的私钥对密文解密。(从此以后,Alice和Bob的地下恋情就不怕被Eve曝光了,我们只是在谈论学习,你是不会懂的。Eve还是一脸懵逼)

 

以上就是公钥密码在传输过程中的原理。

 

 

3RSA算法

1、RSA算法

RSA是第一个比较完善的公开密钥算法,它既能用于加密,也能用于数字签名。RSA以它的三个发明者Ron Rivest, Adi Shamir,LeonardAdleman的名字首字母命名,这个算法经受住了多年深入的密码分析,虽然密码分析者既不能证明也不能否定RSA的安全性,但这恰恰说明该算法有一定的可信性,目前它已经成为最流行的公开密钥算法。

 

这套密码系统,是当今世界上、史上最强加密系统,没有之一,我们日常所有的与金钱有关的信息往来,全部用这套系统加密。RSA算法的一个最大的优点就是,我不怕被人知道我的加密方法,我不怕告诉别人我的一个密钥,因为告诉你也没用。RSA的安全基于大数分解的难度。其公钥和私钥是一对大素数(100到200位十进制数或更大)的函数。从一个公钥和密文恢复出明文的难度,等价于分解两个大素数之积(这是公认的数学难题)。

RSA的公钥、私钥的组成,以及加密、解密的公式可见于下表:

 

RSA算法

 

2、举个栗子,看看这个系统是怎样工作的。

假设两个人:庞涓和孙膑,庞涓要给孙膑一个特别的数字m=520,当然不能让别人知道了,那样太尴尬了对吧。

  • 第一步,孙膑选择两个不相等的质数。如p=61和q=53

  • 第二步,计算两个质数的乘积,n=pq=61×53=3233

  • 第三步,计算n的欧拉函数,φ(n)=60×52=3120(关于欧拉函数,另文撰写)

  • 第四步,随机选择一个整数e,1<e<φ(n),且e与φ(n)互质,庞涓选了e=17

  • 第五步,解不定方程ex+φ(n)y=1,即17x+3120y=1得x=2753,y=-15(关于这个方程的解法,另文撰写,数字小的话直接试试就好),则d=2753

  • 公布公钥(n,e)=(3233,17),保护好自己的私钥(n,d)=(3233,2753)

  • 第六步,加密。计算me除以n的余数,即c=mod(52017,3233)=1077。(这个计算用Excel就可以完成,不需要计算器)于是庞涓将c=1077发给了孙膑。

  • 第七步,解密。孙膑拿到c=1077后,用自己的私钥(n,d)=(3233,2753)来解密。计算cd除以n的余数,即mod(10772753,3233)=520(孙膑脸上泛着幸福的红晕)

这个加密系统中,私钥(n,d)是最关键的,要保护好,一旦丢失,就等于失去秘密。

 

问题:有没有可能由(n,e)倒推出(n,d)呢?

  • 要知道d,由第五步得,必须知道φ(n)

  • 要知道φ(n),由第三步得,必须分解质因数n=pq

  • 要倒推出d,必须对n进行分解质因数。而对于大整数n的分解质因数,数学上毫无办法,惟一能实现的办法就是暴力破解,也就是一个质数一个质数去试。目前公开能分解的最大整数是1230 1866 8453 0117 7551 3049 4958 3849 6272 0772 8535 6959 5334 7921 9732 2452 1517 2640 0507 2636 5751 8745 2021 9978 6469 3899 5647 4942 7740 6384 5925 1925 5732 6303 4537 3154 8268 5079 1702 6122 1429 1346 1670 4292 1431 1602 2212 4047 9274 7377 9408 0665 3514 1959 7459 8569 0214 3413

 

这是个232位整数,也是暴力破解的上限,当然以后量子计算机出现了,估计这个上限还会增加,但只要数学没有突破,无非就是密码长一定罢了。

 

如此完成了一个完整的信息传递过程。我们看到,如果不知道d,其他人是无论如何也算不出m=520的,而要知道d,就必须对n进行分解质因数,而这又是极端困难。即便本例,n只有区区3233四位数,分解质因数就已经非常困难,不得不借助计算机了。

 

RSA算法其实是三个步骤。

  • 计算公钥和私钥。随机选择质数p,q,n=pq,随机选择与φ(n)互质的数e,解方程ex+φ(n)y=1,其中d=x

  • 加密,c=mod(me,n)

  • 解密,m=mod(cd,n)

 

3、RSA算法的特点

算法简单,计算容易,破解困难,这是RSA加密的最大特点。缺点嘛……密码实在太长了,1000位以下的密码根本就不放心。一般金融需要至少1024位,国防需要2048位。其次,这个算法的全部依托是现在的数学水平,假如哪天某个数学家突破了这个难题,他很容易就能分解大整数,这个人就太可怕了,不敢想象。

 

 

4椭圆曲线密码算法

椭圆曲线密码学(英语:Elliptic curve cryptography,缩写为 ECC),一种建立公开密钥加密的算法,基于椭圆曲线数学。椭圆曲线在密码学中的使用是在1985年由Neal Koblitz和Victor Miller分别**提出的。在区块链网络中,ECC通常被应用在数字签名等环节。

 

椭圆曲线密码学的主要优势是在某些情况下它比其他的方法使用更小的密钥——比如RSA加密算法——提供相当的或更高等级的安全。椭圆曲线密码学的另一个优势是可以定义群之间的双线性映射,基于Weil对或是Tate对;双线性映射已经在密码学中发现了大量的应用,例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。

 

双线性映射解释:在数论中,一个双线性映射是由两个向量空间上的元素,生成第三个向量空间上一个元素之函数,并且该函数对每个参数都是线性的。 椭圆曲线加密算法本质是数标轴上曲线的方程式计算,通过数的计算得到加密/解密。 

 

例如:公开密钥算法总是要基于一个数学上的难题。比如RSA 加密算法依据的是:给定两个素数p、q很容易相乘得到n,而对n进行因式分解却相对困难。那椭圆曲线上有什么难题呢?

 

假设如下方程等式:

   K=kG [其中 K,G为Ep(a,b)上的点,k为小于n(n是点G的阶)的整数]

 

不难发现,给定k和G,根据加法法则,计算K很容易;但给定K和G,求k就相对困难了。这就是椭圆曲线加密算法采用的难题。我们把点G称为基点(base point),k(k<n,n为基点G的阶)称为私有密钥(privte key),K称为公开密钥(public key)。

 

我们看下图,下图描述一个利用椭圆曲线进行加密通信的过程:

 

椭圆曲线密码算法

 

用户A选定一条椭圆曲线Ep(a,b),并取椭圆曲线上一点,作为基点G。

 

用户A选择一个私有密钥k,并生成公开密钥K=kG。

 

用户A将Ep(a,b)和点K,G传给用户B。

 

用户B接到信息后,将待传输的明文编码到Ep(a,b)上一点M(编码方法很多,这里不作讨论),并产生一个随机整数r(r<n)。

 

用户B计算点C1=M+rK;C2=rG。

 

用户B将C1、C2传给用户A。

 

用户A接到信息后,计算C1-kC2,结果就是点M。因为

 

C1-kC2=M+rK-k(rG)=M+rK-r(kG)=M

再对点M进行解码就可以得到明文。

 

在这个加密通信中,如果有一个偷窥者H ,他只能看到Ep(a,b)、K、G、C1、C2 而通过K、G求k 或通过C2、G求r 都是相对困难的。因此,H无法得到A、B间传送的明文信息。

 

密码学中,描述一条Fp上的椭圆曲线,常用到六个参量:

       T=(p,a,b,G,n,h)。

  • (p 、a 、b 用来确定一条椭圆曲线,

  • G为基点,

  • n为点G的阶,

  • h 是椭圆曲线上所有点的个数m与n相除的整数部分)

 

这几个参量取值的选择,直接影响了加密的安全性。参量值一般要求满足以下几个条件:

  • p 当然越大越安全,但越大,计算速度会变慢,200位左右可以满足一般安全要求;

  • p≠n×h;

  • pt≠1 (mod n),1≤t<20;

  • 4a3+27b2≠0 (mod p);

  • n 为素数;

  • h≤4。

 

ECC是RSA的强有力竞争者,其与RSA相比有以下优点:

  • 安全性能更高:如160位ECC与1024位RSA有相同的安全强度;

  • 计算量小、处理速度快:在私钥的处理速度上(解密和签名),ECC远比RSA快得多;

  • 存储空间占用小:ECC的密钥尺寸和系统参数与RSA相比要小得多,所以占用的存储空间也小得多;

  • 带宽要求低:这一优势使ECC具有更广泛的应用前景。

ECC的这些优点使其必将取代RSA,成为通用的公开密钥算法。目前,SET协议(安全电子交易协议)的制定者已把它作为下一代SET协议中不可缺少的公开密钥算法。

 

尽管ECC有以上优势,但仍存在两大技术难题

第一,怎么选取合适曲线;

第二,怎么快速实现椭圆曲线密码。

所以,在严谨的密码学体制下还需进一步研究,以攻克更多技术难题,最终保障用户信息安全。

免责声明:信息仅供参考,不构成投资及交易建议。投资者据此操作,风险自担。
如果觉得文章对你有用,请随意赞赏收藏
相关推荐
相关下载
登录后评论
Copyright © 2019 宽客在线