加解密算法之非对称密钥加密
2021-06-04 17:30:28 
阿炯
公开密钥密码学(英语：Public-key cryptography)也称非对称式密码学(英语：Asymmetric cryptography)是密码学的一种算法，它需要两个密钥，一个是公开密钥，另一个是私有密钥；公钥用作加密，私钥则用作解密。使用公钥把明文加密后所得的密文，只能用相对应的私钥才能解密并得到原本的明文，最初用来加密的公钥不能用作解密。由于加密和解密需要两个不同的密钥，故被称为非对称加密；不同于加密和解密都使用同一个密钥的对称加密。公钥可以公开，可任意向外发布；私钥不可以公开，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供，也不会透露给被信任的要通信的另一方。
基于公开密钥加密的特性，它还能提供数字签名的功能，使电子文件可以得到如同在纸本文件上亲笔签署的效果。
公开密钥基础建设透过信任数字证书认证机构的根证书、及其使用公开密钥加密作数字签名核发的公开密钥认证，形成信任链架构，已在TLS实现并在万维网的HTTP以HTTPS、在电子邮件的SMTP以SMTPS或STARTTLS引入。另一方面，信任网络则采用去中心化的概念，取代了依赖数字证书认证机构的公钥基础设施，因为每一张电子证书在信任链中最终只由一个根证书授权信任，信任网络的公钥则可以累积多个用户的信任。PGP就是其中一个例子。
流桯图显示非对称加密过程是单向的，其中一条密钥加密后只能用相对应的另一条密钥解密。
概述
加密
非对称加密往往需要密码学安全伪随机数生成器的协助来产生一对密钥，其中一个可以随便公开，称为公钥；另一个不公开，称为私钥，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供。
如果任何人使用公钥加密明文，得到的密文可以透过不安全的途径(如网络)发送，只有对应的私钥持有者才可以解密得到明文；其他人即使从网络上窃取到密文及加密公钥，也无法(在数以年计的合理时间内)解密得出明文。典型例子是在网络银行或购物网站上，因为客户需要输入敏感消息，浏览器连接时使用网站服务器提供的公钥加密并上传数据，可保证只有信任的网站服务器才能解密得知消息，不必担心敏感个人信息因为在网络上发送而被窃取。
在现实世界上可作比拟的例子是，一个传统保管箱，开门和关门都是使用同一条钥匙，这是对称加密；而一个公开的邮箱，投递口是任何人都可以寄信进去的，这可视为公钥；而只有信箱主人拥有钥匙可以打开信箱，这就视为私钥。
加密过程
非对称加密往往需要密码学安全伪随机数生成器的协助来产生一对密钥，其中一个可以随便公开，称为公钥；另一个不公开，称为私钥，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供。
在非对称加密中，爱丽丝使用鲍伯的公钥加密明文，得到密文，而只有鲍伯因为持有私钥才可以解密，得到明文。
数字签名
如果某一用户使用他的私钥加密明文，任何人都可以用该用户的公钥解密密文；由于私钥只由该用户自己持有，故可以肯定该文件必定出自于该用户；公众可以验证该用户发布的数据或文件是否完整、中途有否曾被篡改，接收者可信赖这些数据、文件确实来自于该用户，这被称作数字签名，大部分国家已经立法承认数字签名拥有等同传统亲笔签名的法律效力。公钥可以透过数字证书认证机构签授的电子证书形式公布，接收者透过信任链形成一套完整的公开密钥基础建设。例如，从网上下载的安装程序，大部分都带有程序制作者的数字签名，可以证明该程序的确是该作者(公司)发布的而不是第三方伪造的且未被篡改过(身份认证/验证)。而现时的网上银行或购物网站都会使用HTTPS，避免沟通过程中的信息泄露。
与对称密码学的比较
对称密码是指在加密和解密时使用同一个密钥的方式，公钥密码则是指在加密和解密时使用不同密钥的方式。
对称密钥加密牵涉到密钥管理的问题，尤其是密钥交换，它需要通信双方在通信之前先透过另一个安全的渠道交换共享的密钥，才可以安全地把密文透过不安全的渠道发送；对称密钥一旦被窃，其所作的加密将即时失效；而在互联网，如果通信双方分隔异地而素未谋面，则对称加密事先所需要的“安全渠道”变得不可行；非对称加密则容许加密公钥随便散布，解密的私钥不发往任何用户，只在单方保管；如此，即使公钥在网上被截获，如果没有与其匹配的私钥，也无法解密，极为适合在互联网上使用。
另一方面，公钥解密的特性可以形成数字签名，使数据和文件受到保护并可信赖；如果公钥透过数字证书认证机构签授成为电子证书，更可作为数字身份的认证，这都是对称密钥加密无法实现的。公钥加密在在计算上相当复杂，性能欠佳、远远不比对称加密；因此在一般实际情况下，往往通过公钥加密来随机创建临时的对称秘钥，亦即对话键，然后才通过对称加密来传输大量、主体的数据。
该思想最早由瑞夫·墨克(Ralph C. Merkle)在1974年提出，之后在1976年。惠特菲尔德·迪菲(Whitfield Diffie)与马丁·赫尔曼(Martin Hellman)两位学者以单向函数与单向暗门函数为基础，为发讯与收讯的两方创建密钥。
常见的公钥加密算法有：RSA、ElGamal、Rabin(RSA的特例)、DSA、ECDSA。使用最广泛的是RSA算法(由发明者Rivest、Shmir和Adleman姓氏首字母缩写而来)是著名的公开秘钥加密算法。
RSA加密算法
RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。
对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的。
1983年9月12日麻省理工学院在美国为RSA算法申请了专利，这个专利于2000年9月21日失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认。
签名消息
RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她的私钥“加密”(如同前面“加密消息”的步骤)这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥“解密”(如同前面“解密消息”的步骤)这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么Bob就可以知道发信人持有Alice的私钥，以及这个消息在传播路径上没有被篡改过。
比起AES、3DES和其它对称算法来说，RSA要慢得多。实际的运用(如TLS)一般结合了对称加密(如AES)和非对称加密(如RSA)两者。
数字签名算法(DSA)
DSA是用于数字签名的联邦信息处理标准之一，基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal签名方案的变体。
美国国家标准技术研究所(NIST)于1991年提出将DSA用于其数字签名标准(DSS)，并于1994年将其作为FIPS 186采用，已对初始规范进行了四次修订。DSA已获得专利，但NIST已将此专利在全球范围内买断式授权。
DSA的椭圆曲线密码学版本是ECDSA。椭圆曲线数字签名算法(英语：Elliptic Curve Digital Signature Algorithm，缩写：ECDSA)是一种基于椭圆曲线密码学的公开金钥加密算法。
DSA算法工作在框架公钥加密、模算数和离散对数问题，这被认为是难解问题。该算法使用由公钥和私钥组成的密钥对。私钥用于生成消息的数字签名，并且可以通过使用签名者的相应公钥来验证这种签名。数字签名提供信息鉴定(接收者可以验证消息的来源)，完整性(接收方可以验证消息自签名以来未被修改)和不可否认性(发送方不能错误地声称它们没有签署消息)。
DSA 算法包含了四种操作：密钥生成、密钥分发、签名、验证。
本站相关参考：
理解密钥与数字证书
RSA算法与DSA算法的区别
椭圆曲线数字签名算法ECDSA介绍
公开密钥基础建设(PKI)与数字签名
基于公开密钥加密的特性，它还能提供数字签名的功能，使电子文件可以得到如同在纸本文件上亲笔签署的效果。
公开密钥基础建设透过信任数字证书认证机构的根证书、及其使用公开密钥加密作数字签名核发的公开密钥认证，形成信任链架构，已在TLS实现并在万维网的HTTP以HTTPS、在电子邮件的SMTP以SMTPS或STARTTLS引入。另一方面，信任网络则采用去中心化的概念，取代了依赖数字证书认证机构的公钥基础设施，因为每一张电子证书在信任链中最终只由一个根证书授权信任，信任网络的公钥则可以累积多个用户的信任。PGP就是其中一个例子。
流桯图显示非对称加密过程是单向的，其中一条密钥加密后只能用相对应的另一条密钥解密。
概述
加密
非对称加密往往需要密码学安全伪随机数生成器的协助来产生一对密钥，其中一个可以随便公开，称为公钥；另一个不公开，称为私钥，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供。
如果任何人使用公钥加密明文，得到的密文可以透过不安全的途径(如网络)发送，只有对应的私钥持有者才可以解密得到明文；其他人即使从网络上窃取到密文及加密公钥，也无法(在数以年计的合理时间内)解密得出明文。典型例子是在网络银行或购物网站上，因为客户需要输入敏感消息，浏览器连接时使用网站服务器提供的公钥加密并上传数据，可保证只有信任的网站服务器才能解密得知消息，不必担心敏感个人信息因为在网络上发送而被窃取。
在现实世界上可作比拟的例子是，一个传统保管箱，开门和关门都是使用同一条钥匙，这是对称加密；而一个公开的邮箱，投递口是任何人都可以寄信进去的，这可视为公钥；而只有信箱主人拥有钥匙可以打开信箱，这就视为私钥。
加密过程
非对称加密往往需要密码学安全伪随机数生成器的协助来产生一对密钥，其中一个可以随便公开，称为公钥；另一个不公开，称为私钥，必须由用户自行严格秘密保管，绝不透过任何途径向任何人提供。
在非对称加密中，爱丽丝使用鲍伯的公钥加密明文，得到密文，而只有鲍伯因为持有私钥才可以解密，得到明文。
数字签名
如果某一用户使用他的私钥加密明文，任何人都可以用该用户的公钥解密密文；由于私钥只由该用户自己持有，故可以肯定该文件必定出自于该用户；公众可以验证该用户发布的数据或文件是否完整、中途有否曾被篡改，接收者可信赖这些数据、文件确实来自于该用户，这被称作数字签名，大部分国家已经立法承认数字签名拥有等同传统亲笔签名的法律效力。公钥可以透过数字证书认证机构签授的电子证书形式公布，接收者透过信任链形成一套完整的公开密钥基础建设。例如，从网上下载的安装程序，大部分都带有程序制作者的数字签名，可以证明该程序的确是该作者(公司)发布的而不是第三方伪造的且未被篡改过(身份认证/验证)。而现时的网上银行或购物网站都会使用HTTPS，避免沟通过程中的信息泄露。
与对称密码学的比较
对称密码是指在加密和解密时使用同一个密钥的方式，公钥密码则是指在加密和解密时使用不同密钥的方式。
对称密钥加密牵涉到密钥管理的问题，尤其是密钥交换，它需要通信双方在通信之前先透过另一个安全的渠道交换共享的密钥，才可以安全地把密文透过不安全的渠道发送；对称密钥一旦被窃，其所作的加密将即时失效；而在互联网，如果通信双方分隔异地而素未谋面，则对称加密事先所需要的“安全渠道”变得不可行；非对称加密则容许加密公钥随便散布，解密的私钥不发往任何用户，只在单方保管；如此，即使公钥在网上被截获，如果没有与其匹配的私钥，也无法解密，极为适合在互联网上使用。
另一方面，公钥解密的特性可以形成数字签名，使数据和文件受到保护并可信赖；如果公钥透过数字证书认证机构签授成为电子证书，更可作为数字身份的认证，这都是对称密钥加密无法实现的。公钥加密在在计算上相当复杂，性能欠佳、远远不比对称加密；因此在一般实际情况下，往往通过公钥加密来随机创建临时的对称秘钥，亦即对话键，然后才通过对称加密来传输大量、主体的数据。
该思想最早由瑞夫·墨克(Ralph C. Merkle)在1974年提出，之后在1976年。惠特菲尔德·迪菲(Whitfield Diffie)与马丁·赫尔曼(Martin Hellman)两位学者以单向函数与单向暗门函数为基础，为发讯与收讯的两方创建密钥。
常见的公钥加密算法有：RSA、ElGamal、Rabin(RSA的特例)、DSA、ECDSA。使用最广泛的是RSA算法(由发明者Rivest、Shmir和Adleman姓氏首字母缩写而来)是著名的公开秘钥加密算法。
RSA加密算法
RSA加密算法是一种非对称加密算法，在公开密钥加密和电子商业中被广泛使用。RSA是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出的。当时他们三人都在麻省理工学院工作。RSA 就是他们三人姓氏开头字母拼在一起组成的。
1973年，在英国政府通讯总部工作的数学家克利福德·柯克斯(Clifford Cocks)在一个内部文件中提出了一个与之等效的算法，但该算法被列入机密，直到1997年才得到公开。
对极大整数做因数分解的难度决定了 RSA 算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的 RSA 钥匙才可能被强力方式破解。到目前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被破解的。
1983年9月12日麻省理工学院在美国为RSA算法申请了专利，这个专利于2000年9月21日失效。由于该算法在申请专利前就已经被发表了，在世界上大多数其它地区这个专利权不被承认。
签名消息
RSA也可以用来为一个消息署名。假如Alice想给Bob传递一个署名的消息的话，那么她可以为她的消息计算一个散列值(Message digest)，然后用她的私钥“加密”(如同前面“加密消息”的步骤)这个散列值并将这个“署名”加在消息的后面。这个消息只有用她的公钥才能被解密。Bob获得这个消息后可以用Alice的公钥“解密”(如同前面“解密消息”的步骤)这个散列值，然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话，那么Bob就可以知道发信人持有Alice的私钥，以及这个消息在传播路径上没有被篡改过。
比起AES、3DES和其它对称算法来说，RSA要慢得多。实际的运用(如TLS)一般结合了对称加密(如AES)和非对称加密(如RSA)两者。
数字签名算法(DSA)
DSA是用于数字签名的联邦信息处理标准之一，基于模算数和离散对数的复杂度。DSA是Schnorr和ElGamal签名方案的变体。
美国国家标准技术研究所(NIST)于1991年提出将DSA用于其数字签名标准(DSS)，并于1994年将其作为FIPS 186采用，已对初始规范进行了四次修订。DSA已获得专利，但NIST已将此专利在全球范围内买断式授权。
DSA的椭圆曲线密码学版本是ECDSA。椭圆曲线数字签名算法(英语：Elliptic Curve Digital Signature Algorithm，缩写：ECDSA)是一种基于椭圆曲线密码学的公开金钥加密算法。
DSA算法工作在框架公钥加密、模算数和离散对数问题，这被认为是难解问题。该算法使用由公钥和私钥组成的密钥对。私钥用于生成消息的数字签名，并且可以通过使用签名者的相应公钥来验证这种签名。数字签名提供信息鉴定(接收者可以验证消息的来源)，完整性(接收方可以验证消息自签名以来未被修改)和不可否认性(发送方不能错误地声称它们没有签署消息)。
DSA 算法包含了四种操作：密钥生成、密钥分发、签名、验证。
本站相关参考：
理解密钥与数字证书
RSA算法与DSA算法的区别
椭圆曲线数字签名算法ECDSA介绍
公开密钥基础建设(PKI)与数字签名