今天给各位分享非对称加密效率怎么算的知识,如果能碰巧解决你现在面临的问题,别忘了关注本站。
对称加密算法
对称加密算法是应用较早的加密算法,技术成熟。在对称加密算法中,数据发信方将明文(原始数据)和加密密钥一起经过特殊加密算法处理后,使其变成复杂的加密密文发送出去。收信方收到密文后,若想解读原文,则需要使用加密用过的密钥及相同算法的逆算法对密文进行解密,才能使其恢复成可读明文。在对称加密算法中,使用的密钥只有一个,发收信双方都使用这个密钥对数据进行加密和解密,这就要求解密方事先必须知道加密密钥。
对称加密算法的特点是算法公开、计算量小、加密速度快、加密效率高。不足之处是,交易双方都使用同样钥匙,安全性得不到保证。此外,每对用户每次使用对称加密算法时,都需要使用其他人不知道的惟一钥匙,这会使得发收信双方所拥有的钥匙数量成几何级数增长,密钥管理成为用户的负担。对称加密算法在分布式网络系统上使用较为困难,主要是因为密钥管理困难,使用成本较高。在计算机专网系统中广泛使用的对称加密算法有des、idea和aes。
不对称加密算法
不对称加密算法使用两把完全不同但又是完全匹配的一对钥匙—公钥和私钥。在使用不对称加密算法加密文件时,只有使用匹配的一对公钥和私钥,才能完成对明文的加密和解密过程。加密明文时采用公钥加密,解密密文时使用私钥才能完成,而且发信方(加密者)知道收信方的公钥,只有收信方(解密者)才是唯一知道自己私钥的人。不对称加密算法的基本原理是,如果发信方想发送只有收信方才能解读的加密信息,发信方必须首先知道收信方的公钥,然后利用收信方的公钥来加密原文;收信方收到加密密文后,使用自己的私钥才能解密密文。显然,采用不对称加密算法,收发信双方在通信之前,收信方必须将自己早已随机生成的公钥送给发信方,而自己保留私钥。由于不对称算法拥有两个密钥,因而特别适用于分布式系统中的数据加密。广泛应用的不对称加密算法有rsa算法和美国国家标准局提出的dsa。以不对称加密算法为基础的加密技术应用非常广泛。
上述过程中,出现了公钥(3233,17)和私钥(3233,2753),这两组数字是怎么找出来的呢?参考 RSA算法原理(二)
首字母缩写说明:E是加密(Encryption)D是解密(Decryption)N是数字(Number)。
1.随机选择两个不相等的质数p和q。
alice选择了61和53。(实际应用中,这两个质数越大,就越难破解。)
2.计算p和q的乘积n。
n = 61×53 = 3233
n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。
3.计算n的欧拉函数φ(n)。称作L
根据公式φ(n) = (p-1)(q-1)
alice算出φ(3233)等于60×52,即3120。
4.随机选择一个整数e,也就是公钥当中用来加密的那个数字
条件是1 e φ(n),且e与φ(n) 互质。
alice就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。)
5.计算e对于φ(n)的模反元素d。也就是密钥当中用来解密的那个数字
所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。ed ≡ 1 (mod φ(n))
alice找到了2753,即17*2753 mode 3120 = 1
6.将n和e封装成公钥,n和d封装成私钥。
在alice的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。
上述故事中,blob为了偷偷地传输移动位数6,使用了公钥做加密,即6^17 mode 3233 = 824。alice收到824之后,进行解密,即824^2753 mod 3233 = 6。也就是说,alice成功收到了blob使用的移动位数。
再来复习一下整个流程:
p=17,q=19
n = 17 19 = 323
L = 16 18 = 144
E = 5(E需要满足以下两个条件:1E144,E和144互质)
D = 29(D要满足两个条件,1D144,D mode 144 = 1)
假设某个需要传递123,则加密后:123^5 mode 323 = 225
接收者收到225后,进行解密,225^ 29 mode 323 = 123
回顾上面的密钥生成步骤,一共出现六个数字:
p
q
n
L即φ(n)
e
d
这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。那么,有无可能在已知n和e的情况下,推导出d?
(1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。
(2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
(3)n=pq。只有将n因数分解,才能算出p和q。
结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。
可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道:"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。"
然而,虽然RSA的安全性依赖于大数的因子分解,但并没有从理论上证明破译RSA的难度与大数分解难度等价。即RSA的重大缺陷是无法从理论上把握它的保密性能如何。此外,RSA的缺点还有:
A)产生密钥很麻烦,受到素数产生技术的限制,因而难以做到一次一密。
B)分组长度太大,为保证安全性,n 至少也要 600bits以上,使运算代价很高,尤其是速度较慢,较对称密码算法慢几个数量级;且随着大数分解技术的发展,这个长度还在增加,不利于数据格式的标准化。因此, 使用RSA只能加密少量数据,大量的数据加密还要靠对称密码算法 。
加密和解密是自古就有技术了。经常看到侦探电影的桥段,勇敢又机智的主角,拿着一长串毫无意义的数字苦恼,忽然灵光一闪,翻出一本厚书,将第一个数字对应页码数,第二个数字对应行数,第三个数字对应那一行的某个词。数字变成了一串非常有意义的话:
Eat the beancurd with the peanut. Taste like the ham.
这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫做密钥(cipher code)。发出信息的人根据密钥来给信息加密,而接收信息的人利用相同的密钥,来给信息解密。 就好像一个带锁的盒子。发送信息的人将信息放到盒子里,用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥,这种加密称为对称加密(symmetric encryption)。
如果一对一的话,那么两人需要交换一个密钥。一对多的话,比如总部和多个特工的通信,依然可以使用同一套密钥。 但这种情况下,对手偷到一个密钥的话,就知道所有交流的信息了。 二战中盟军的情报战成果,很多都来自于破获这种对称加密的密钥。
为了更安全,总部需要给每个特工都设计一个不同的密钥。如果是FBI这样庞大的机构,恐怕很难维护这么多的密钥。在现代社会,每个人的信用卡信息都需要加密。一一设计密钥的话,银行怕是要跪了。
对称加密的薄弱之处在于给了太多人的钥匙。如果只给特工锁,而总部保有钥匙,那就容易了。特工将信息用锁锁到盒子里,谁也打不开,除非到总部用唯一的一把钥匙打开。只是这样的话,特工每次出门都要带上许多锁,太容易被识破身份了。总部老大想了想,干脆就把造锁的技术公开了。特工,或者任何其它人,可以就地取材,按照图纸造锁,但无法根据图纸造出钥匙。钥匙只有总部的那一把。
上面的关键是锁和钥匙工艺不同。知道了锁,并不能知道钥匙。这样,银行可以将“造锁”的方法公布给所有用户。 每个用户可以用锁来加密自己的信用卡信息。即使被别人窃听到,也不用担心:只有银行才有钥匙呢!这样一种加密算法叫做非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。
1976年,两位美国计算机学家Whitfield Diffie 和 Martin Hellman,提出了一种崭新构思,可以在不直接传递密钥的情况下,完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应关系即可,这样就避免了直接传递密钥。这种新的加密模式被称为"非对称加密算法"。
1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。
1.能“撞”上的保险箱(非对称/公钥加密体制,Asymmetric / Public Key Encryption)
数据加密解密和门锁很像。最开始的时候,人们只想到了那种只能用钥匙“锁”数据的锁。如果在自己的电脑上自己加密数据,当然可以用最开始这种门锁的形式啦,方便快捷,简单易用有木有。
但是我们现在是通信时代啊,双方都想做安全的通信怎么办呢?如果也用这种方法,通信就好像互相发送密码保险箱一样…而且双方必须都有钥匙才能进行加密和解密。也就是说,两个人都拿着保险箱的钥匙,你把数据放进去,用钥匙锁上发给我。我用同样的钥匙把保险箱打开,再把我的数据锁进保险箱,发送给你。
这样看起来好像没什么问题。但是,这里面 最大的问题是:我们两个怎么弄到同一个保险箱的同一个钥匙呢? 好像仅有的办法就是我们两个一起去买个保险箱,然后一人拿一把钥匙,以后就用这个保险箱了。可是,现代通信社会,绝大多数情况下别说一起去买保险箱了,连见个面都难,这怎么办啊?
于是,人们想到了“撞门”的方法。我这有个可以“撞上”的保险箱,你那里自己也买一个这样的保险箱。通信最开始,我把保险箱打开,就这么开着把保险箱发给你。你把数据放进去以后,把保险箱“撞”上发给我。撞上以后,除了我以外,谁都打不开保险箱了。这就是RSA了,公开的保险箱就是公钥,但是我有私钥,我才能打开。
2.数字签名
这种锁看起来好像很不错,但是锁在运输的过程中有这么一个严重的问题:你怎么确定你收到的开着的保险箱就是我发来的呢?对于一个聪明人,他完全可以这么干:
(a)装作运输工人。我现在把我开着的保险箱运给对方。运输工人自己也弄这么一个保险箱,运输的时候把保险箱换成他做的。
(b)对方收到保险箱后,没法知道这个保险箱是我最初发过去的,还是运输工人替换的。对方把数据放进去,把保险箱撞上。
(c)运输工人往回运的时候,用自己的钥匙打开自己的保险箱,把数据拿走。然后复印也好,伪造也好,弄出一份数据,把这份数据放进我的保险箱,撞上,然后发给我。
从我的角度,从对方的角度,都会觉得这数据传输过程没问题。但是,运输工人成功拿到了数据,整个过程还是不安全的,大概的过程是这样:
这怎么办啊?这个问题的本质原因是,人们没办法获知,保险箱到底是“我”做的,还是运输工人做的。那干脆,我们都别做保险箱了,让权威机构做保险箱,然后在每个保险箱上用特殊的工具刻上一个编号。对方收到保险箱的时候,在权威机构的“公告栏”上查一下编号,要是和保险箱上的编号一样,我就知道这个保险箱是“我”的,就安心把数据放进去。大概过程是这样的:
如何做出刻上编号,而且编号没法修改的保险箱呢?这涉及到了公钥体制中的另一个问题:数字签名。
要知道,刻字这种事情吧,谁都能干,所以想做出只能自己刻字,还没法让别人修改的保险箱确实有点难度。那么怎么办呢?这其实困扰了人们很长的时间。直到有一天,人们发现:我们不一定非要在保险箱上刻规规矩矩的字,我们干脆在保险箱上刻手写名字好了。而且,刻字有点麻烦,干脆我们在上面弄张纸,让人直接在上面写,简单不费事。具体做法是,我们在保险箱上嵌进去一张纸,然后每个出产的保险箱都让权威机构的CEO签上自己的名字。然后,CEO把自己的签名公开在权威机构的“公告栏”上面。比如这个CEO就叫“学酥”,那么整个流程差不多是这个样子:
这个方法的本质原理是,每个人都能够通过笔迹看出保险箱上的字是不是学酥CEO签的。但是呢,这个字体是学酥CEO唯一的字体。别人很难模仿。如果模仿我们就能自己分辨出来了。要是实在分辨不出来呢,我们就请一个笔迹专家来分辨。这不是很好嘛。这个在密码学上就是数字签名。
上面这个签字的方法虽然好,但是还有一个比较蛋疼的问题。因为签字的样子是公开的,一个聪明人可以把公开的签字影印一份,自己造个保险箱,然后把这个影印的字也嵌进去。这样一来,这个聪明人也可以造一个相同签字的保险箱了。解决这个问题一个非常简单的方法就是在看保险箱上的签名时,不光看字体本身,还要看字体是不是和公开的字体完全一样。要是完全一样,就可以考虑这个签名可能是影印出来的。甚至,还要考察字体是不是和其他保险柜上的字体一模一样。因为聪明人为了欺骗大家,可能不影印公开的签名,而影印其他保险箱上的签名。这种解决方法虽然简单,但是验证签名的时候麻烦了一些。麻烦的地方在于我不仅需要对比保险箱上的签名是否与公开的笔迹一样,还需要对比得到的签名是否与公开的笔迹完全一样,乃至是否和所有发布的保险箱上的签名完全一样。有没有什么更好的方法呢?
当然有,人们想到了一个比较好的方法。那就是,学酥CEO签字的时候吧,不光把名字签上,还得带上签字得日期,或者带上这个保险箱的编号。这样一来,每一个保险箱上的签字就唯一了,这个签字是学酥CEO的签名+学酥CEO写上的时间或者编号。这样一来,就算有人伪造,也只能伪造用过的保险箱。这个问题就彻底解决了。这个过程大概是这么个样子:
3 造价问题(密钥封装机制,Key Encapsulation Mechanism)
解决了上面的各种问题,我们要考虑考虑成本了… 这种能“撞”门的保险箱虽然好,但是这种锁造价一般来说要比普通的锁要高,而且锁生产时间也会变长。在密码学中,对于同样“结实”的锁,能“撞”门的锁的造价一般来说是普通锁的上千倍。同时,能“撞”门的锁一般来说只能安装在小的保险柜里面。毕竟,这么复杂的锁,装起来很费事啊!而普通锁安装在多大的保险柜上面都可以呢。如果两个人想传输大量数据的话,用一个大的保险柜比用一堆小的保险柜慢慢传要好的多呀。怎么解决这个问题呢?人们又想出了一个非常棒的方法:我们把两种锁结合起来。能“撞”上的保险柜里面放一个普通锁的钥匙。然后造一个用普通的保险柜来锁大量的数据。这样一来,我们相当于用能“撞”上的保险柜发一个钥匙过去。对方收到两个保险柜后,先用自己的钥匙把小保险柜打开,取出钥匙。然后在用这个钥匙开大的保险柜。这样做更棒的一个地方在于,既然对方得到了一个钥匙,后续再通信的时候,我们就不再需要能“撞”上的保险柜了啊,在以后一定时间内就用普通保险柜就好了,方便快捷嘛。
以下参考 数字签名、数字证书、SSL、https是什么关系?
4.数字签名(Digital Signature)
数据在浏览器和服务器之间传输时,有可能在传输过程中被冒充的盗贼把内容替换了,那么如何保证数据是真实服务器发送的而不被调包呢,同时如何保证传输的数据没有被人篡改呢,要解决这两个问题就必须用到数字签名,数字签名就如同日常生活的中的签名一样,一旦在合同书上落下了你的大名,从法律意义上就确定是你本人签的字儿,这是任何人都没法仿造的,因为这是你专有的手迹,任何人是造不出来的。那么在计算机中的数字签名怎么回事呢?数字签名就是用于验证传输的内容是不是真实服务器发送的数据,发送的数据有没有被篡改过,它就干这两件事,是非对称加密的一种应用场景。不过他是反过来用私钥来加密,通过与之配对的公钥来解密。
第一步:服务端把报文经过Hash处理后生成摘要信息Digest,摘要信息使用私钥private-key加密之后就生成签名,服务器把签名连同报文一起发送给客户端。
第二步:客户端接收到数据后,把签名提取出来用public-key解密,如果能正常的解密出来Digest2,那么就能确认是对方发的。
第三步:客户端把报文Text提取出来做同样的Hash处理,得到的摘要信息Digest1,再与之前解密出来的Digist2对比,如果两者相等,就表示内容没有被篡改,否则内容就是被人改过了。因为只要文本内容哪怕有任何一点点改动都会Hash出一个完全不一样的摘要信息出来。
5.数字证书(Certificate Authority)
数字证书简称CA,它由权威机构给某网站颁发的一种认可凭证,这个凭证是被大家(浏览器)所认可的,为什么需要用数字证书呢,难道有了数字签名还不够安全吗?有这样一种情况,就是浏览器无法确定所有的真实服务器是不是真的是真实的,举一个简单的例子:A厂家给你们家安装锁,同时把钥匙也交给你,只要钥匙能打开锁,你就可以确定钥匙和锁是配对的,如果有人把钥匙换了或者把锁换了,你是打不开门的,你就知道肯定被窃取了,但是如果有人把锁和钥匙替换成另一套表面看起来差不多的,但质量差很多的,虽然钥匙和锁配套,但是你却不能确定这是否真的是A厂家给你的,那么这时候,你可以找质检部门来检验一下,这套锁是不是真的来自于A厂家,质检部门是权威机构,他说的话是可以被公众认可的(呵呵)。
同样的, 因为如果有人(张三)用自己的公钥把真实服务器发送给浏览器的公钥替换了,于是张三用自己的私钥执行相同的步骤对文本Hash、数字签名,最后得到的结果都没什么问题,但事实上浏览器看到的东西却不是真实服务器给的,而是被张三从里到外(公钥到私钥)换了一通。那么如何保证你现在使用的公钥就是真实服务器发给你的呢?我们就用数字证书来解决这个问题。数字证书一般由数字证书认证机构(Certificate Authority)颁发,证书里面包含了真实服务器的公钥和网站的一些其他信息,数字证书机构用自己的私钥加密后发给浏览器,浏览器使用数字证书机构的公钥解密后得到真实服务器的公钥。这个过程是建立在被大家所认可的证书机构之上得到的公钥,所以这是一种安全的方式。
常见的对称加密算法有DES、3DES、aes、RC5、RC6。非对称加密算法应用非常广泛,如SSH,
HTTPS, TLS,电子证书,电子签名,电子身份证等等。
参考 DES/3DES/aes区别
非对称加密(公钥加密):指加密和解密使用不同密钥的加密算法,也称为公私钥加密。假设两个用户要加密交换数据,双方交换公钥,使用时一方用对方的公钥加密,另一方即可用自己的私钥解密。如果企业中有n个用户,企业需要生成n对密钥,并分发n个公钥。假设A用B的公钥加密消息,用A的私钥签名,B接到消息后,首先用A的公钥验证签名,确认后用自己的私钥解密消息。由于公钥是可以公开的,用户只要保管好自己的私钥即可,因此加密密钥的分发将变得 十分简单。同时,由于每个用户的私钥是唯一的,其他用户除了可以通过信息发送者的公钥来验证信息的来源是否真实,还可以通过数字签名确保发送者无法否认曾发送过该信息。
链乔教育在线旗下学硕创新区块链技术工作站是中国教育部学校规划建设发展中心开展的“智慧学习工场2020-学硕创新工作站 ”唯一获准的“区块链技术专业”试点工作站。专业站立足为学生提供多样化成长路径,推进专业学位研究生产学研结合培养模式改革,构建应用型、复合型人才培养体系。
如果要给世界上所有算法按重要程度排个序,那我觉得“公钥加密算法”一定是排在最前边的,因为它是现代计算机通信安全的基石,保证了加密数据的安全。
01 对称加密算法
在非对称加密出现以前,普遍使用的是对称加密算法。所谓对称加密,就是加密和解密是相反的操作,对数据进行解密,只要按加密的方式反向操作一遍就可以获得对应的原始数据了,举一个简单的例子,如果要对字符串"abc"进行加密,先获取它们的ANSCII码为:97 98 99;密钥为+2,加密后的数据就是:99 100 101,将密文数据发送出去。接收方收到数据后对数据进行解密,每个数据减2,就得到了原文。当然这只是一个非常简单的例子,真实的对称加密算法会做得非常复杂,但这已经能够说明问题了。
这样的加密方法有什么缺点呢?首先缺点一:密钥传递困难;想想看如果两个人,分别是Bob和Alice,Bob要给Alice发消息,那Bob就要把密钥通过某种方式告诉Alice,有什么可靠的途径呢?打电话、发邮件、写信...等等方式好像都不靠谱,都有被窃取的风险,也只有两人见面后当面交流这一种方式了;缺点二:密钥数量会随着通信人数的增加而急剧增加,密钥管理将会是一个非常困难的事情。
02 非对称加密算法
1976年,两位美国计算机学家,提出了Diffie-Hellman密钥交换算法。这个算法的提出了一种崭新的构思,可以在不直接传递密钥的情况下,完成解密。这个算法启发了其他科学家,让人们认识到,加密和解密可以使用不同的规则,只要这两种规则之间存在某种对应的关系即可,这样就避免了直接传递密钥。这种新的加密模式就是“非对称加密算法”。
算法大致过程是这样的:
(1)乙方 生成两把密钥(公钥和私钥)。公钥是公开的,任何人都可以获得,私钥则是保密的。
(2)甲方获取乙方的公钥,然后用它对信息加密。
(3)乙方得到加密后的信息,用私钥解密。
如果公钥加密的信息只有私钥解得开,那么只要私钥不泄漏,通信就是安全的。
03 RSA非对称加密算法
1977年,三位数学家Rivest、Shamir 和 Adleman 设计了一种算法,可以实现非对称加密。这种算法用他们三个人的名字命名,叫做RSA算法。
从那时直到现在,RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说,只要有计算机网络的地方,就有RSA算法。这种算法非常可靠,密钥越长,它就越难破解。根据已经披露的文献,目前被破解的最长RSA密钥是768个二进制位。也就是说,长度超过768位的密钥,还无法破解(至少没人公开宣布)。因此可以认为,1024位的RSA密钥基本安全,2048位的密钥极其安全。
公钥加密 - 私钥解密
只有私钥持有方可以正确解密,保证通信安全
私钥加密 - 公钥解密
所有人都可以正确解密,信息一定是公钥所对应的私钥持有者发出的,可以做签名
04 质数的前置知识
RSA的安全性是由大数的质因数分解保证的。下面是一些质数的性质:
1、任意两个质数构成素质关系,比如:11和17;
2、一个数是质数,另一个数只要不是前者的倍数,两者就构成素质关系,比如3和10;
3、如果两个数之中,较大的那个是质数,则两者构成互质关系,比如97和57;
4、1和任意一个自然数都是互质关系,比如1和99;
5、p是大于1的整数,则p和p-1构成互质关系,比如57和56;
6、p是大于1的奇数,则p和p-2构成互质关系,比如17和15
05 RSA密钥生成步骤
举个“栗子“,假如通信双方为Alice和Bob,Alice要怎么生成公钥和私钥呢?
St ep 1:随机选择两个不相等的质数p和q;
Alice选择了3和11。(实际情况中,选择的越大,就越难破解)
S tep 2 :计算p和q的乘积n;
n = 3*11 = 33,将33转化为二进制:100001,这个时候密钥长度就是6位。
Step 3 :计算n的欧拉函数φ(n);
因为n可以写为两个质数相乘的形式,欧拉函数对于可以写成两个质数形式有简单计算方式
φ(n) = (p-1)(q-1)
Step 4 :随机选择一个整数e,条件是1 e φ(n),且e与φ(n) 互质;
爱丽丝就在1到20之间,随机选择了3
Step 5 :计算e对于φ(n)的模反元素d
所谓模反元素,就是指有一个整数d,可以使得ed被φ(n)除的余数为1
Step 6 :将n和e封装成公钥,n和d封装成私钥;
在上面的例子中,n=33,e=3,d=7,所以公钥就是 (33,3),私钥就是(33, 7)。
密钥生成步骤中,一共出现了六个数字,分别为:
素质的两个数p和q,乘积n,欧拉函数φ(n),随机质数e,模反元素d
这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的,可以删除。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。
那么,有无可能在已知n和e的情况下,推导出d?
(1)ed 1 (mod φ(n))。只有知道e和φ(n),才能算出d。
(2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
(3)n=pq。只有将n因数分解,才能算出p和q。
结论是如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。
BUT!
大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。
维基百科这样写道:
"对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。
假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有较短的RSA密钥才可能被暴力破解。到现在为止,世界上还没有任何可靠的攻击RSA算法的方式。
只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。"
06 RSA加密和解密过程
1、加密要用公钥(n,e)
假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。
所谓"加密",就是算出下式的c:
爱丽丝的公钥是 (33, 3),鲍勃的m假设是5,那么可以算出下面的等式:
于是,c等于26,鲍勃就把26发给了爱丽丝。
2、解密要用私钥(n,d)
爱丽丝拿到鲍勃发来的26以后,就用自己的私钥(33, 7) 进行解密。下面的等式一定成立(至于为什么一定成立,证明过程比较复杂,略):
也就是说,c的d次方除以n的余数为m。现在,c等于26,私钥是(33, 7),那么,爱丽丝算出:
因此,爱丽丝知道了鲍勃加密前的原文就是5。
至此,加密和解密的整个过程全部完成。整个过程可以看到,加密和解密使用不用的密钥,且不用担心密钥传递过程中的泄密问题,这一点上与对称加密有很大的不同。由于非对称加密要进行的计算步骤复杂,所以通常情况下,是两种算法混合使用的。
07 一些其它的
在Part 5的第五步,要求一定要解出二元一次方程的一对正整数解,如果不存在正整数解,这该怎么办?
扩展欧几里得算法给出了解答:
对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by;
第五步其实等价于:ed - kφ(n) = 1, e与φ(n)又互质,形式上完全与扩展欧几里得算法的一致,所以一定有整数解存在。
Reference:
目前为止,本书中只讨论到对称加密。假设一个密码系统不只有一个密钥,而是有一对密钥,其中公钥可以自由地发布,而私钥由自己保管。其他人可以使用你的公钥来加密数据,这个信息只有你的私钥可以解密,这个被称为 公钥加密(public-key encryption)
很长一段时间,这都被认为是不可能的。然而从1970年开始,这一类型的算法开始出现。第一个广为流传的是MIT的三位密码学家:Ron Rivest,Adi Shamir 和Leonard Adleman提出的RSA。
公钥算法并不仅仅用来加密,实际上本书之前的部分已经提到过公钥算法而其不是直接用在加密上。有三个与公钥算法相关的主题
从表面来看,公钥加密好像可以淘汰之前提到的对称密钥算法。对于任何事情都可以使用公钥加密,也不需要对称密钥系统中的密钥交换过程。然而在实际的密码学系统中,可以看到到处都是混合的加密,公钥加密在其中起着重要作用,但是大部分的加解密以及认证工作还是基于对成密钥算法的。
目前来看最重要的原因是性能。与流密码(原生的流密码或者其他)算法相比,公钥加密机制实在是太慢了。RSA通常情况下需要2048位也就是256个字节。其加密需要0.29百万次循环,解密需要11.12百万次循环。而对称加密和解密只需要每字节约10次循环。这也意味着在对称密钥算法中,解密256位数据,只需要3000次循环,这个效率是非对称版本的4000次。而目前的密码系统使得对称加密更快了,在aes-GCM硬件加速或者Salsa20/ChaCha20只需要2或者4次每字节,更大程度上提高了性能。
实际的密码系统中还有更多其他的问题。例如对于RSA来说,它不能加密任何比它大的信息,通常情况是小于或者等于4096位,比大部分的需求要小的多。当然最重要的问题依然是上述的速度的问题。
本节简单描述RSA背后的数学问题。其本身并不能产生安全加密机制。之后会看到在其上构造的密码指导OAEP。
为了产生一个key,需要挑选两个大素数p和q,这些数需要随机私密的挑选。将两者相乘的到N,这个是公开的。然后选择一个加密指数e,这个也是公开的。通常这个数是3或者65537.因为这些数的二进制形式中仅有很少量的1。计算指数会更有效。(N,e)是公钥,任何人都可以用公钥来加密消息M,得到密文C。
接下来的问题是解密,有一个解密指数d,可以将C转化会M。如果指导p和q,d很容易计算。可以使用d来解密消息:
RSA的安全性依赖于对于不知道d的人来说解密操作是不可能的,并且在只知道(N,e)的情况下d的计算是非常难的。
类似于很多密码系统,RSA依赖于特定数学问题的难度。给定密文C,和公钥(N,e),反推出明文M。这被称为RSA难题。
最直接的方法是将N分解为p*q。给定p和q,攻击者只需要重复密钥拥有者的过程来计算产生d即可。
幸运的是,没有一个算法可以在合理的时间内分解这么大的数。不幸的是,目前也无法证明该算法一定不存在。更加糟糕的是,有一个理论上的算法,被称为Shor's Algorithm,可以在量子计算机上在合理的时间内分解一个数。目前,量子计算机还离我们有些远,但是未来某天可能就会成为现实。到时候RSA就变得不再有效。
本节中仅仅提到了分解大数这个最直接的方式来攻击RSA。在接下来的部分可以看到一系列针对RSA的实际攻击,其主要依赖于一些具体的实现。
目前,没有已知的实际的攻破RSA的方法。但这不意味着使用RSA的系统没有被攻破过。和其他被攻破的系统一样,应用中有很多组成部分,一旦其中的某部分没有恰当的使用,就会使整个系统变得不可用。更多有关RSA实施的细节的,参考【Bon99】和【AV96】,本部分只提及一些有趣的部分。
Salt是一个用python写的供应系统。它有一个模块叫做 cypto ,它没有使用已有的密码学系统,而是实现了一个自己的,其中使用的RSA和aes由第三方库提供。
很长一段时间里,Salt使用的公钥指数e是1,这也就意味着P e=P 1=P(mod N)。这也就意味着结果的密文就是明文。目前该问题已经被修复,这里只是为了提醒大家,不要实现自己的加密系统。Salt现在支持了SSH作为传输蹭,但是先前提到的DIY的RSA/aes系统依然存在,并且还是默认的传输层。
OAEP是Optimal asymmetric encryption padding的简称,是RSA填充的一种。它的结构类似于下图(文档中这个图有问题,下面是正确的图):
最终产生的需要被加密的数据是X||Y,是n位长,这个n是N的位数。它使用一个随机的块R它的长度是k,在这个标准中,k是一个定值。消息首先需要用0填充被扩充到n-k位。图中左边的长度为n-k位,右边的长度为k。随机块R和以0扩充的M,M||000...使用两个陷阱函数,G和H。陷阱函数都是从一个方向计算非常简单,但是逆转非常的难。世纪中通常为hash函数。
G的输入是k位,输出是n-k位,H的输入是n-k位,输出是k位。
然后结果的X和Y被连接在一起,然后由标准的RSA来进行加密产生密文。
解密的时候,要反过来操作。接收者收到X||Y,他们是指导k的,因为这个是协议里的定值。所以前n-k是X,后k位是Y。
想要得到M,M||000...,需要去计算
可以看出,对于一些H和G来说,需要所有的X和Y才能找到M。对于H和G有很多种基于Hash函数的选择。
绝大多数的公钥加密只能一次加密一小块,一般都远小于要发送的信息。另外这些算法还很慢,比对称加密要慢的多。通常非对称加密用来连接密码系统。
有了公钥密码和密钥交换,是密码学里面两个非常重要的部分,因为人们总是需要与其他人交换私密的信息。有了这两个技术就可以安全地和其他人交流。
目前为止讨论的加密都没有任何形式的身份认证。这也就意味着对消息进行加密和解密,并不能验证得到的消息确实是发送者发送的原本的消息。
没有身份认证的加密可以提供隐私性,但是如之前章节所言,没有身份认证,尽管攻击者不知道任何原文的信息,他任然可以修改加密的信息。接收这些消息会泄漏一些私密的信息,这也就意味着私密性不在。例如之前第7章提到的CBC的填充攻击。
综上所言,出了加密私密的信息之外,还需要对其进行身份认证。通常身份认证都是对消息增加一些额外的可计算的信息。类似于加密,身份认证也分为对称类型的和非对称类型的。对称类型的通常被称为消息认证(message authentication),非对称类型的通常被称为数字签名。
下一章先介绍一下另一个密码学中的重点:hash函数。hash在产生签名和消息认证等过程中都需要用到。
[Bon99] Dan Boneh. Twenty years of attacks on the RSA cryptosystem. Notices of the AMS , 46:203–213, 1999. URL: .
[AV96] Ross Anderson and Serge Vaudenay. Minding your pʼs and qʼs. In In Advances in Cryptology - ASIACRYPT’96, LNCS 1163 , 26–35. Springer� Verlag, 1996. URL: .
非对称加密需要两个密钥:公钥(publickey) 和私钥 (privatekey)。公钥和私钥是一对,如果用公钥对数据加密,那么只能用对应的私钥解密。如果用私钥对数据加密,只能用对应的公钥进行解密。因为加密和解密用的是不同的密钥,所以称为非对称加密。
非对称加密算法的保密性好,它消除了最终用户交换密钥的需要。但是加解密速度要远远慢于对称加密,在某些极端情况下,甚至能比对称加密慢上1000倍。
算法强度复杂、安全性依赖于算法与密钥但是由于其算法复杂,而使得加密解密速度没有对称加密解密的速度快。对称密码体制中只有一种密钥,并且是非公开的,如果要解密就得让对方知道密钥。所以保证其安全性就是保证密钥的安全,而非对称密钥体制有两种密钥,其中一个是公开的,这样就可以不需要像对称密码那样传输对方的密钥了。这样安全性就大了很多。
RSA、Elgamal、背包算法、Rabin、D-H、ECC (椭圆曲线加密算法)。使用最广泛的是 RSA 算法,Elgamal 是另一种常用的非对称加密算法。
收信者是唯一能够解开加密信息的人,因此收信者手里的必须是私钥。发信者手里的是公钥,其它人知道公钥没有关系,因为其它人发来的信息对收信者没有意义。
客户端需要将认证标识传送给服务器,此认证标识 (可能是一个随机数) 其它客户端可以知道,因此需要用私钥加密,客户端保存的是私钥。服务器端保存的是公钥,其它服务器知道公钥没有关系,因为客户端不需要登录其它服务器。
数字签名是为了表明信息没有受到伪造,确实是信息拥有者发出来的,附在信息原文的后面。就像手写的签名一样,具有不可抵赖性和简洁性。
简洁性:对信息原文做哈希运算,得到消息摘要,信息越短加密的耗时越少。
不可抵赖性:信息拥有者要保证签名的唯一性,必须是唯一能够加密消息摘要的人,因此必须用私钥加密 (就像字迹他人无法学会一样),得到签名。如果用公钥,那每个人都可以伪造签名了。
问题起源:对1和3,发信者怎么知道从网上获取的公钥就是真的?没有遭受中间人攻击?
这样就需要第三方机构来保证公钥的合法性,这个第三方机构就是 CA (Certificate Authority),证书中心。
CA 用自己的私钥对信息原文所有者发布的公钥和相关信息进行加密,得出的内容就是数字证书。
信息原文的所有者以后发布信息时,除了带上自己的签名,还带上数字证书,就可以保证信息不被篡改了。信息的接收者先用 CA给的公钥解出信息所有者的公钥,这样可以保证信息所有者的公钥是真正的公钥,然后就能通过该公钥证明数字签名是否真实了。
RSA 是目前最有影响力的公钥加密算法,该算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥,即公钥,而两个大素数组合成私钥。公钥是可发布的供任何人使用,私钥则为自己所有,供解密之用。
A 要把信息发给 B 为例,确定角色:A 为加密者,B 为解密者。首先由 B 随机确定一个 KEY,称之为私钥,将这个 KEY 始终保存在机器 B 中而不发出来;然后,由这个 KEY 计算出另一个 KEY,称之为公钥。这个公钥的特性是几乎不可能通过它自身计算出生成它的私钥。接下来通过网络把这个公钥传给 A,A 收到公钥后,利用公钥对信息加密,并把密文通过网络发送到 B,最后 B 利用已知的私钥,就能对密文进行解码了。以上就是 RSA 算法的工作流程。
由于进行的都是大数计算,使得 RSA 最快的情况也比 DES 慢上好几倍,无论是软件还是硬件实现。速度一直是 RSA 的缺陷。一般来说只用于少量数据加密。RSA 的速度是对应同样安全级别的对称密码算法的1/1000左右。
比起 DES 和其它对称算法来说,RSA 要慢得多。实际上一般使用一种对称算法来加密信息,然后用 RSA 来加密比较短的公钥,然后将用 RSA 加密的公钥和用对称算法加密的消息发送给接收方。
这样一来对随机数的要求就更高了,尤其对产生对称密码的要求非常高,否则的话可以越过 RSA 来直接攻击对称密码。
和其它加密过程一样,对 RSA 来说分配公钥的过程是非常重要的。分配公钥的过程必须能够抵挡中间人攻击。假设 A 交给 B 一个公钥,并使 B 相信这是A 的公钥,并且 C 可以截下 A 和 B 之间的信息传递,那么 C 可以将自己的公钥传给 B,B 以为这是 A 的公钥。C 可以将所有 B 传递给 A 的消息截下来,将这个消息用自己的密钥解密,读这个消息,然后将这个消息再用 A 的公钥加密后传给 A。理论上 A 和 B 都不会发现 C 在偷听它们的消息,今天人们一般用数字认证来防止这样的攻击。
(1) 针对 RSA 最流行的攻击一般是基于大数因数分解。1999年,RSA-155 (512 bits) 被成功分解,花了五个月时间(约8000 MIPS 年)和224 CPU hours 在一台有3.2G 中央内存的 Cray C916计算机上完成。
RSA-158 表示如下:
2009年12月12日,编号为 RSA-768 (768 bits, 232 digits) 数也被成功分解。这一事件威胁了现通行的1024-bit 密钥的安全性,普遍认为用户应尽快升级到2048-bit 或以上。
RSA-768表示如下:
(2) 秀尔算法
量子计算里的秀尔算法能使穷举的效率大大的提高。由于 RSA 算法是基于大数分解 (无法抵抗穷举攻击),因此在未来量子计算能对 RSA 算法构成较大的威胁。一个拥有 N 量子位的量子计算机,每次可进行2^N 次运算,理论上讲,密钥为1024位长的 RSA 算法,用一台512量子比特位的量子计算机在1秒内即可破解。
DSA (Digital Signature Algorithm) 是 Schnorr 和 ElGamal 签名算法的变种,被美国 NIST 作为 DSS (DigitalSignature Standard)。 DSA 是基于整数有限域离散对数难题的。
简单的说,这是一种更高级的验证方式,用作数字签名。不单单只有公钥、私钥,还有数字签名。私钥加密生成数字签名,公钥验证数据及签名,如果数据和签名不匹配则认为验证失败。数字签名的作用就是校验数据在传输过程中不被修改,数字签名,是单向加密的升级。
椭圆加密算法(ECC)是一种公钥加密算法,最初由 Koblitz 和 Miller 两人于1985年提出,其数学基础是利用椭圆曲线上的有理点构成 Abel 加法群上椭圆离散对数的计算困难性。公钥密码体制根据其所依据的难题一般分为三类:大整数分解问题类、离散对数问题类、椭圆曲线类。有时也把椭圆曲线类归为离散对数类。
ECC 的主要优势是在某些情况下它比其他的方法使用更小的密钥 (比如 RSA),提供相当的或更高等级的安全。ECC 的另一个优势是可以定义群之间的双线性映射,基于 Weil 对或是 Tate 对;双线性映射已经在密码学中发现了大量的应用,例如基于身份的加密。不过一个缺点是加密和解密操作的实现比其他机制花费的时间长。
ECC 被广泛认为是在给定密钥长度的情况下,最强大的非对称算法,因此在对带宽要求十分紧的连接中会十分有用。
比特币钱包公钥的生成使用了椭圆曲线算法,通过椭圆曲线乘法可以从私钥计算得到公钥, 这是不可逆转的过程。
Java 中 Chipher、Signature、KeyPairGenerator、KeyAgreement、SecretKey 均不支持 ECC 算法。
DH,全称为"Diffie-Hellman",它是一种确保共享 KEY 安全穿越不安全网络的方法,也就是常说的密钥一致协议。由公开密钥密码体制的奠基人 Diffie 和 Hellman 所提出的一种思想。简单的说就是允许两名用户在公开媒体上交换信息以生成"一致"的、可以共享的密钥。也就是由甲方产出一对密钥 (公钥、私钥),乙方依照甲方公钥产生乙方密钥对 (公钥、私钥)。
以此为基线,作为数据传输保密基础,同时双方使用同一种对称加密算法构建本地密钥 (SecretKey) 对数据加密。这样,在互通了本地密钥 (SecretKey) 算法后,甲乙双方公开自己的公钥,使用对方的公钥和刚才产生的私钥加密数据,同时可以使用对方的公钥和自己的私钥对数据解密。不单单是甲乙双方两方,可以扩展为多方共享数据通讯,这样就完成了网络交互数据的安全通讯。
具体例子可以移步到这篇文章: 非对称密码之DH密钥交换算法
参考:
随着社会的发展,产品的更新速度也是越来越快,算法是方案的核心,保护开发者和消费者的权益刻不容缓,那么加密芯片在其中就扮演了重要的角色,如何选择加密芯片呢?
1.市面上加密芯片种类繁多,算法多种,加密芯片强度参差不齐,加密性能与算法、秘钥密切相关。常见的加密算法有对称算法,非对称算法,国密算法,大部分都是基于I2C、SPI或1-wire协议进行通信。加密芯片还是需要项目实际需求选择,比如对称加密算法的特点是计算量小、加密速度快、加密效率高等。
2.因为单片机软加密性能较弱且非常容易被复制,所以有了加密芯片的产生,大大增加了破解难度和生产成本。目前加密芯片广泛应用于车载电子、消费电子、美容医疗、工业控制、AI智能等行业。
3.韩国KEROS加密芯片专注加密领域十多年,高安全性、低成本,在加密保护领域受到了众多客户的高度赞扬及认可。KEROS采用先进的内置aes256安全引擎和加密功能,通过真动态数据交互并为系统中敏感信息的存储提供了安全的场所,有了它的保护电路,即使受到攻击,这些信息也可以保持安全。其封装SOP8,SOT23-6,TDFN-6集成I2C与1-wire协议满足不同应用需求。CK02AT、CK22AT、CK02AP、CK22AP支持1.8V-3.6V,256bit位秘钥长度,5bytes SN序列号,支持定制化免烧录,加密行业首选。关于非对称加密效率怎么算的介绍到此就结束了,感谢大家耐心阅读。