非对称加密RSA/椭圆曲线加密

椭圆曲线加密、共识算法

对称加密与非对称加密的基本概念可以参看《简叙密码发展史(0):密码学概述——基本概念科普》

非对称加密相比对称加密的显著优点在于，对称加密需要协商密钥，而非对称加密可以安全地公开各自的公钥，在N个人之间通信的时候：使用非对称加密只需要N个密钥对，每个人只管理自己的密钥对。而使用对称加密需要则需要N*(N-1)/2个密钥，因此每个人需要管理N-1个密钥，密钥管理难度大，而且非常容易泄漏。

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。也正是因为这个算法的产生，人类终于可以实现非对称加密了：A给B发送信息

1. B要先生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

2. A获取B的公钥，然后用它对信息加密。

3. B得到加密后的信息，用私钥解密。

理论上如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

非对称加密的典型算法就是RSA算法，是Ron Rivest，Adi Shamir，Leonard Adleman于1978年发明，所以用他们仨的姓的首字母缩写表示。

毫不夸张地说，只要有计算机网络的地方，就有RSA算法。这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是232个十进制位，也就是768个二进制位，因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全，当然量子计算机除外。

RSA算法

RSA加密是一个方便更换锁芯，但难以暴力拆卸的锁。

RSA算法的原理

解释RSA算法的原理，其实RSA算法并不难，只需要一点数论知识就可以理解。

• 素数：又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。

• 互质，又称互素。若N个整数的最大公因子是1，则称这N个整数互质。

• 模运算，即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。

• 模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a对模数n的“模反元素”。ab≡1（mod n）

• 欧拉定理：若正整数 a , n 互质，则a^φ(n)≡1(mod n)，其中 φ(n) 是欧拉函数（1~n) 与 n 互质的数。

• 费马小定理：对于质数p，任意整数a，均满足：a^p≡a（mod p）

• 欧拉定理的推论：若正整数a，n互质，那么对于任意正整数b，有a^b≡a^{b mod φ（n）}（mod n）

• 欧拉函数：欧拉函数是小于x的整数中与x互质的数的个数，一般用φ(x)表示。特殊的，φ(1)=1。

欧拉函数的解析

在数论中，对于正整数N,少于或等于N ([1,N]),且与N互质的正整数(包括1)的个数，记作φ(n)。

欧拉函数的性质：

• p^k型欧拉函数:

• 若N是质数p(即N=p), φ(n)= φ(p)=p-p^(k-1)=p-1。

• 若N是质数p的k次幂(即N=p^k)，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)。

• mn型欧拉函数

• 设n为正整数，以φ(n)表示不超过n且与n互素的正整数的个数，称为n的欧拉函数值。若m,n互质，φ(mn)=(m-1)(n-1)=φ(m)φ(n)。

• 特殊性质:

• 若n为奇数时，φ(2n)=φ(n)。

• 对于任何两个互质 的正整数a,n(n>2)有:a^φ(n)=1 mod n (恒等于)此公式即 欧拉定理

• 当n=p 且 a与素数p互质(即:gcd(a,p)=1)则上式有: a^(p-1)=1 mod n (恒等于)此公式即 费马小定理

RSA的诞生

现在我们知道了m^e % n = c是加密，c^d % n = m是解密，m就是原始数据，c是密文，公钥是n和e，私钥是n和d，所以只有n和e是公开的。加密时我们也要知道φ(n)的值，最简单的方式是用两个质数之积得到，别人想破解RSA也要知道φ(n)的值，只能对n进行因数分解，那么我们不想m被破解，n的值就要非常大，就是我们之前说的，长度一般为1024个二进制位，这样就很安全了。

RSA加密过程用简单的话说是这样的：

• 随机选两个很大的质数 p,q

• 计算n=p×q，且n被公开

• 再选一个数字e，需要保证e和(p-1)×(q-1)没有除1之外的公因数。

• 如需加密信息X，计算X^e  mod n

具体 请参考：

如何用通俗易懂的话来解释非对称加密? - 知乎 https://www.zhihu.com/question/33645891/answer/159643267

RSA之所以可以被推广，并且大范围应用，是因为目前我们还没有完全攻陷质数这一领域。我们目前还没有很好的办法分解一个大数。

2010 年底，国家密码管理局公布了我国自主研制的“椭圆曲线公钥密码算法”（SM2 算法）。

2012 年以来，国家密码管理局以《中华人民共和国密码行业标准》的方式，陆续公布了 SM2/SM3/SM4 等密码算法标准及其应用规范。其中“SM”代表“商密”，即用于商用的、不涉及国家秘密的密码技术。

• SM2算法：SM2椭圆曲线公钥密码算法是我国自主设计的公钥密码算法，包括SM2-1椭圆曲线数字签名算法，SM2-2椭圆曲线密钥交换协议，SM2-3椭圆曲线公钥加密算法，分别用于实现数字签名密钥协商和数据加密等功能。SM2算法与RSA算法不同的是，SM2算法是基于椭圆曲线上点群离散对数难题，相对于RSA算法，256位的SM2密码强度已经比2048位的RSA密码强度要高。椭圆曲线参数并没有给出推荐的曲线，曲线参数的产生需要利用一定的算法产生。但在实际使用中，国密局推荐使用素数域256 位椭圆曲线，其曲线方程为y^2= x^3+ax+b（其中p是大于3的一个大素数，n是基点G的阶，Gx、Gy 分别是基点G的x与y值，a、b是随圆曲线方程y^2= x^3+ax+b的系数）。

• SM3算法：SM3杂凑算法是我国自主设计的密码杂凑算法，适用于商用密码应用中的数字签名和验证消息认证码的生成与验证以及随机数的生成，可满足多种密码应用的安全需求。为了保证杂凑算法的安全性，其产生的杂凑值的长度不应太短，例如MD5输出128比特杂凑值，输出长度太短，影响其安全性SHA-1算法的输出长度为160比特，SM3算法的输出长度为256比特，因此SM3算法的安全性要高于MD5算法和SHA-1算法。

• SM4算法：SM4分组密码算法是我国自主设计的分组对称密码算法，用于实现数据的加密/解密运算，以保证数据和信息的机密性。要保证一个对称密码算法的安全性的基本条件是其具备足够的密钥长度，SM4算法与AES算法具有相同的密钥长度分组长度128比特，因此在安全性上高于3DES算法。

国产密码算法（国密算法）是指国家密码局认定的国产商用密码算法，目前主要使用公开的SM2、SM3、SM4三类算法，分别是非对称算法、哈希算法和对称算法。

• 国密证书：这里的国密证书指的是使用国密算法（SM2-with-SM3）的标准 X509 格式证书，证书使用 SM3 作为哈希算法，使用 SM2 作为数字签名算法

• 国密 SSL：采用国密算法，符合国密标准的安全传输协议，也就是 SSL/TLS 协议的国密版本

椭圆曲线加密是整个非对称加密下的一个部分。

椭圆曲线：

椭圆曲线有多种表示形式:

• 维尔斯特拉斯通用式： y³= x³+ax+b，这个式子是最常见的形式

• 维尔斯特拉斯一般式：y²+ ay = x³+bx² +cx +d

• 勒让德标准式：y² =x(x-1)(x-λ)

后面待整理…………，我还没消化好椭圆曲线

ECDH加密算法（Encryption with ECDH）

ECDH是Diffie-Hellman algorithm基于椭圆曲线的变种，更像是一个key-agreement protocol，而不是一个加密算法。因为，ECDH仅仅定义了各种密钥如何产生以及在各方之间如何交换，具体如何用这些密钥来对数据进行加密由用户自己决定。

后面待整理………

参考文章：

非对称加密算法--RSA加密原理及运用 https://www.jianshu.com/p/ad3d1dea63af

椭圆曲线加密概览 https://zhuanlan.zhihu.com/p/38920372

ECC椭圆曲线加密算法：ECDH 和 ECDSA https://zhuanlan.zhihu.com/p/66794410

ECC椭圆曲线加密算法：介绍 https://zhuanlan.zhihu.com/p/36326221

椭圆曲线密码学简介（二）：有限域的椭圆曲线及离散对数问题 https://zhuanlan.zhihu.com/p/104531745

椭圆曲线密码学简介（三）：ECDH加密算法和ECDSA数字签名算法 https://zhuanlan.zhihu.com/p/107599962

转载本站文章《非对称加密RSA/椭圆曲线加密》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/encryption/8619.html