密码学公钥如何用符号表示

① 公钥算法原理

这是一种不对称加密算法。公钥算法包括快速公钥算法与传统公钥算法。快速公钥算法与传统公钥算法相比具有更广泛地应用前景,对快速公钥系统的研究是当前公钥系统研究的一个热点。

定义
不对称加密算法使用两把完全不同但又是完全匹配的一对钥匙—公钥和私钥。在使用不对称加密算法加密文件时，只有使用匹配的一对公钥和私钥，才能完成对明文的加密和解密过程。加密明文时采用公钥加密，解密密文时使用私钥才能完成，而且发信方（加密者）知道收信方的公钥，只有收信方（解密者）才是唯一知道自己私钥的人。不对称加密算法的基本原理是，如果发信方想发送只有收信方才能解读的加密信息，发信者使用收信者的公钥加密信件，收信者使用自己的私钥钥解密信件。显然，采用不对称加密算法，收发信双方在通信之前，收信方必须将自己早已随机生成的公钥送给发信方，而自己保留私钥。由于不对称算法拥有两个密钥，因而特别适用于分布式系统中的数据加密。广泛应用的不对称加密算法有RSA算法和美国国家标准局提出的DSA。以不对称加密算法为基础的加密技术应用非常广泛。

工作原理
1976 年，Whitfield Diffe 和 Martin Hellman 创建了公钥加密。公钥加密是重大的创新，因为它从根本上改变了加密和解密的过程。

Diffe 和 Hellman 提议使用两个密钥，而不是使用一个共享的密钥。一个密钥（称为“私钥”）是保密的。它只能由一方保存，而不能各方共享。第二个密钥（称为“公钥”）不是保密的，可以广泛共享。这两个密钥（称为“密钥对”）在加密和解密操作中配合使用。密钥对具有特殊的互补关系，从而使每个密钥都只能与密钥对中的另一个密钥配合使用。这一关系将密钥对中的密钥彼此唯一地联系在一起：公钥与其对应的私钥组成一对，并且与其他任何密钥都不关联。

由于公钥和私钥的算法之间存在特殊的数学关系，从而使得这种配对成为可能。密钥对在数学上彼此相关，例如，配合使用密钥对可以实现两次使用对称密钥的效果。密钥必须配合使用：不能使用每个单独的密钥来撤消它自己的操作。这意味着每个单独密钥的操作都是单向操作：不能使用一个密钥来撤消它的操作。此外，设计两个密钥使用的算法时，特意设计无法使用一个密钥确定密钥对中的另一个密钥。因此，不能根据公钥确定出私钥。但是，使得密钥对成为可能的数学原理也使得密钥对具有对称密钥所不具有的一个缺点。这就是，所使用的算法必须足够强大，才能使人们无法通过强行尝试，使用已知的公钥来解密通过它加密的信息。公钥利用数学复杂性以及它的单向特性来弥补它是众所周知的这样一个事实，以防止人们成功地破解使用它编码的信息。

如果将此概念应用于前面的示例，则发件人将使用公钥将纯文本加密成密码。然后，收件人将使用私钥将密码重新解密成纯文本。

由于密钥对中的私钥和公钥之间所存在的特殊关系，因此一个人可以在与许多人交往时使用相同的密钥对，而不必与每个人分别使用不同的密钥。只要私钥是保密的，就可以随意分发公钥，并让人们放心地使用它。使许多人使用同一个密钥对代表着密码学上的一个重大突破，因为它显着降低了密钥管理的需求，大大提高了密码学的可用性。用户可以与任意数目的人员共享一个密钥对，而不必为每个人单独设立一个密钥。

公钥加密是邮件安全中的一个基本要素。如果没有公钥加密，那么是否存在实用的邮件安全解决方案是值得怀疑的，因为在公钥加密出现之前，密钥管理是一件很麻烦的事情。在了解了公钥加密的基本概念之后，接下来便是了解如何借助这些概念来实现邮件安全性。

② 公钥密码→RSA详解

在对称密码中，由于加密和解密的密钥是相同的，因此必须向接收者配送密钥。用于解密的密钥必须被配送给接收者，这一问题称为 密钥配送问题 ，如果使用公钥密码，则无需向接收者配送用于解密的密钥，这样就解决了密钥配送问题。可以说公钥密码是密码学历史上最伟大的发明。

解决密钥配送问题的方法

在人数很多的情况下，通信所需要的密钥数量会增大，例如：1000名员工中每一个人都可以和另外999个进行通信，则每个人需要999个通信密钥，整个密钥数量：
1000 x 999 ÷ 2 = 499500
很不现实，因此此方法有一定的局限性

在Diffic-Hellman密钥交换中，进行加密通信的双方需要交换一些信息，而这些信息即便被窃听者窃听到也没有问题（后续文章会进行详解）。

在对称密码中，加密密钥和解密密钥是相同的，但公钥密码中，加密密钥和解密密钥却是不同的。只要拥有加密密钥，任何人都可以加密，但没有解密密钥是无法解密的。

公钥密码中，密钥分为加密密钥（公钥）和解密密钥（私钥）两种。

公钥和私钥是一一对应的，一对公钥和私钥统称为密钥对，由公钥进行加密的密文，必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系——数学上的关系——因此公钥和私钥是不能分别单独生成的。

发送者：Alice      接收者：Bob      窃听者：Eve
通信过程是由接收者Bob来启动的

公钥密码解决了密钥配送的问题，但依然面临着下面的问题

RSA是目前使用最广泛的公钥密码算法，名字是由它的三位开发者，即Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的（Rivest-Shamir-Adleman）。RSA可以被使用公钥密码和数字签名（此文只针对公钥密码进行探讨，数字签名后续文章敬请期待）1983年在美国取得了专利，但现在该专利已经过期。

在RSA中，明文、密钥和密文都是数字，RSA加密过程可以用下列公式来表达

密文 = 明文 ^E mod N

简单的来说，RSA的密文是对代表明文的数字的 E 次方求mod N 的结果，换句话说：将明文和自己做 E 次乘法，然后将结果除以 N 求余数，这个余数就是密文。

RSA解密过程可以用下列公式来表达

明文 = 密文 ^D mod N
对表示密文的数字的 D 次方求mod N 就可以得到明文，换句话说：将密文和自己做 D 次乘法，在对其结果除以 N 求余数，就可以得到明文
此时使用的数字 N 和加密时使用的数字 N 是相同的，数 D 和数 N 组合起来就是RSA的解密密钥，因此 D 和 N 的组合就是私钥 。只要知道 D 和 N 两个数的人才能够完成解密的运算

根据加密和解密的公式可以看出，需要用到三个数—— E 、 D 和 N 求这三个数就是 生成密钥对 ，RSA密钥对的生成步骤如下：

准备两个很大的质数 p 和 q ，将这两个数相乘，结果就是 N
N = p x q

L 是 p-1 和 q-1 的最小公倍数，如果用lcm( X , Y )来表示 “ X 和 Y 的最小公倍数” 则L可以写成下列形式
L = lcm ( p - 1， q - 1)

E 是一个比1大、比 L 小的数。 E 和 L 的最大公约数必须为1，如果用gcd( X , Y )来表示 X 和 Y 的最大公约数，则 E 和 L 之间存在下列关系：
1 < E < L
gcd( E , L ) = 1 （是为了保证一定存在解密时需要使用的数 D ）

1 < D < L
E x D mod L = 1

p = 17
q = 19
N = p x q = 17 x 19 = 323

L = lcm ( p - 1， q - 1) = lcm (16,18) = 144

gcd( E , L ) = 1
满足条件的 E 有很多：5，7，11，13，17，19，23，25，29，31...
这里选择5来作为 E ,到这里我们已经知道 E = 5    N = 323 这就是公钥

E x D mod L = 1
D = 29 可以满足上面的条件，因此：
公钥： E = 5     N = 323
私钥： D = 29    N = 323

要加密的明文必须是小于 N 的数，这是因为在加密运算中需要求 mod N 假设加密的明文是123
明文 ^E mod N = 123 ⁵ mod 323 = 225（密文）

对密文225进行解密
密文 ^D mod N = 225 ²⁹ mod 323 = 225 ¹⁰ x 225 ¹⁰ x 225 ⁹ mod 323 = (225 ¹⁰ mod 323) x (225 ¹⁰ mod 323) x (225 ⁹ mod 323) = 16 x 16 x 191 mod 323 = 48896 mod 323 = 123（明文）

如果没有mod N 的话，即：

明文 = 密文 ^D mod N

通过密文求明文的难度不大，因为这可以看作是一个求对数的问题。
但是，加上mod N 之后，求明文就变成了求离散对数的问题，这是非常困难的，因为人类还没有发现求离散对数的高效算法。

只要知道 D ，就能够对密文进行解密，逐一尝试 D 来暴力破译RSA，暴力破解的难度会随着D的长度增加而加大，当 D 足够长时，就不能再现实的时间内通过暴力破解找出数 D

目前，RSA中所使用的 p 和 q 的长度都是1024比特以上， N 的长度为2048比特以上，由于 E 和 D 的长度可以和N差不多，因此要找出 D ，就需要进行2048比特以上的暴力破解。这样的长度下暴力破解找出 D 是极其困难的

E x D mod L = 1           L = lcm ( p - 1， q - 1)
由 E 计算 D 需要使用 p 和 q ，但是密码破译者并不知道 p 和 q

对于RSA来说，有一点非常重要，那就是 质数 p 和 q 不能被密码破译这知道 。把 p 和 q 交给密码破译者与把私钥交给密码破译者是等价的。

p 和 q 不能被密码破译者知道，但是 N = p x q 而且 N 是公开的， p 和 q 都是质数，因此由 N 求 p 和 q 只能通过 将 N 进行质因数分解 ，所以说：
一旦发现了对大整数进行质因数分解的高效算法，RSA就能够被破译

这种方法虽然不能破译RSA，但却是一种针对机密性的有效攻击。

所谓中间人攻击，就是主动攻击者Mallory混入发送者和接收者的中间，对发送者伪装成接收者，对接收者伪装成发送者的攻击，在这里，Mallory就是“中间人”

这种攻击不仅针对RSA，而是可以针对任何公钥密码。在这个过程中，公钥密码并没有被破译，所有的密码算法也都正常工作并确保了机密性。然而，所谓的机密性并非在Alice和Bob之间，而是在Alice和Mallory之间，以及Mallory和Bob之间成立的。 仅靠公钥密码本身，是无法防御中间人攻击的。

要防御中间人攻击，还需要一种手段来确认所收到的公钥是否真的属于Bob，这种手段称为认证。在这种情况下，我们可以使用公钥的 证书 (后面会陆续更新文章来进行探讨)

网络上很多服务器在收到格式不正确的数据时都会向通信对象返回错误消息，并提示“这里的数据有问题”，然而，这种看似很贴心的设计却会让攻击者有机可乘。 攻击者可以向服务器反复发送自己生成的伪造密文，然后分析返回的错误消息和响应时间获得一些关于密钥和明文的信息。

为了抵御这种攻击，可以对密文进行“认证”，RSA-OAEP(最优非对称加密填充)正是基于这种思路设计的一种RSA改良算法。

RSA-OAEP在加密时会在明文前面填充一些认证信息，包括明文的散列值以及一定数量的0，然后用RSA进行加密，在解密的过程中，如果解密后的数据的开头没有找到正确的认证信息，则可以判定有问题，并返回固定的错误消息（重点是，不能将具体的错误内容告知开发者）
RSA-OAEP在实际应用中，还会通过随机数使得每次生成的密文呈现不同的排列方式，从而进一步提高安全性。

随着计算机技术的进步等，以前被认为是安全的密码会被破译，这一现象称为 密码劣化 ，针对这一点：

③ 1.密码学之RSA

计算56的欧拉函数

 φ(56) =  φ(8)*  φ(7) = 4 * 6 = 24

一、当n是质数的时候，φ(n)=n-1。

二、如果n可以分解成两个互质磨仿的整数之积，如n=A*B则：

φ(A*B)=φ(A)* φ(B)

根据以上两点得到：

如果N是两个质数P1 和 P2的乘积则

φ(N)=φ(P1)* φ(P2)=(P1-1)*(P2-1)

如果两个正整数m和n互质，那么m的φ(n)次方减去1，可以被n整除。

 欧拉定理的特殊情况：如果两个正整数m和n互质，而且n为质数！那么φ(n)结果就是n-1。

公式转换

3 φ(5) mod 5  --->  3 **4 mod 5 = 81 mod 5 = 1

3 φ(5) mod 5  --->  3 **(4 * 2) mod 5 = 6561 mod 5 = 1

3 φ(5) mod 5  --->  3 **(4  + 1) mod 5 = 243 mod 5 = 3

如果两个正整数e和x互质，那么一定可以找到整首卜数d，使得 ed-1

被x整除。  那么d就是e对于x的“模反元素”

e = 3 , x = 5

e*d mod x  = 1  -->  3*d mod 5 = 1 , d 可以为 2、7 ， 2、7 就是3相对于5的模反元素

e*d = k *x + 1   --> 瞎芹纤 3*7 = k*5 + 1, k 可以为 4

m = 4, n = 15 , φ(n) = φ(3) * φ(5) = 8,  e = 3,  d 可以为 11 、19 （d 是求出来的， e*d mod φ(n) = 1 --> 3*d mod 8 = 1 ,  --->  3*d - 1 = 8*k ---> d = 3, 11, 19）  e和φ(n)互质

4**33 mod 15 = 4   ,   5**33 mod 15 = 5  ,   6**33 mod 15 = 6

结论 m<n 都满足条件 ， m **(e*d) mod n = m

3 ** 15 mod 17 = 6   ,  6 **13 mod 17  = 10  ----> (3 ** 15) ** 13 mod 17 = 10

3 ** 13 mod 17 = 12  ,  12 **15 mod 17  = 10  ----> (3 ** 13) ** 15 mod 17 = 10

所以 ：  (3 ** 15)** 13 mod 17 = (3 ** 13) ** 15 mod 17  --->

m **e mod n = c ,  c ** d mod n = m **(e *d) mod n，  m ** (e *d) mod n = m  ( d和φ(n)的模反元素 )

m **e mod n = c 加密

c **d mod n = m 解密

m = 3 , n = 15, φ(n) = 8, e = 3 (与φ(n) 互质)，d = 11、19

3 ** 3 mod 15 = 12  , 12 ** 11 mod 15 = 3

12 * 3 mod 15 = 3 ,  3 ** 11 mod 15 = 12

m 小于 n, d 是 e 相对于φ(n)的模反元素

公钥： n 和 e

私钥： n 和 d

明文:   m

密文:   c

n 长度 1024 以上，所以 n 是由 p1 和 p2 两个质数相乘得到的，为了好算。

1、n会非常大，长度一般为1024个二进制位。（目前人类已经分解的最大整数，232个十进制位，768个二进制位）

2、由于需要求出φ(n)，所以根据欧函数特点，最简单的方式n

由两个质数相乘得到: 质数：p1、p2  ,  Φ(n) = (p1 -1) * (p2 - 1)

3、最终由φ(n)得到e 和 d 。

总共生成6个数字：p1、p2、n、φ(n)、e、d

除了公钥用到了n和e 其余的4个数字是不公开的。

目前破解RSA得到d的方式如下：

1、要想求出私钥d  。由于e*d = φ(n)*k + 1。要知道e和φ(n);

2、e是知道的，但是要得到 φ(n)，必须知道p1 和 p2。

3、由于 n=p1*p2。只有将n因数分解才能算出。

1. 相对来说比较安全（非对称加密的，私钥不用传递）

2. 效率不高

3. 加密数据小

由于Mac系统内置OpenSSL(开源加密库),所以我们可以直接在终端上使用命令来玩RSA.

OpenSSL中RSA算法常用指令主要有三个：

$ openssl genrsa -out private.pem 1024

$ cat private.pem  （查看显示出来的是 base64的编码）

$ openssl rsa -in private.pem -pubout -out public.pem

$ openssl rsa -in private.pem -text -out private.txt

$ openssl rsautl -encrypt -in message.txt -inkey public.pem -pubin -out enc.txt  加密

$ openssl rsautl -decrypt -in enc.txt -inkey private.pem -out dec.txt   解密

$ openssl req -new -key private.pem -out rsacert.csr   生成csr文件

$ openssl x509 -req -days 3650 -in rsacert.csr -signkey private.pem -out rsacert.crt   签名

$ openssl pkcs12 -export -out p.p12 -inkey private.pem -in rsacert.crt 生成p12

  base64 可以将任意的二进制数据进行编码。 编码成为65个字符组成的文本文件。

  0~9a ~ z， A ~ Z + / =

 $base64 源文件 -o 目标文件    编码

 $base64 源文件 -o 目标文件 -D 解码

  101001 010101 010100 010101

  A 字节  =  =

  010000 010000 000000 000000  (将二进制数据以每6个二进制为一组进行编码， 6位正好是64个二进制)

例如 ： A 的ASCII 码为65， 占1个字节，8个二进制位 01000001 ，---> 010000 010000 000000 000000 （补两组0是为了字节对齐）

$ openssl x509 -outform der -in rsacert.crt -out rsacert.der  （在ios中不能直接使用，需将crt 文件生成一个der文件）

将der 和 p12文件拖入项目中，导入 RSACryptor

- (void)viewDidLoad {

    [super viewDidLoad];

    //1.加载公钥

    [[RSACryptor sharedRSACryptor] loadPublicKey: [[NSBundle mainBundle] pathForResource:@"rsacert.der" ofType:nil]];

    //2.加载私钥

    [[RSACryptor sharedRSACryptor] loadPrivateKey:[[NSBundle mainBundle] pathForResource:@"p.p12" ofType:nil] password:@"123456"];

}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent*)event{

    //1.加密

    NSData * result = [[RSACryptor sharedRSACryptor] encryptData:[@"hello" dataUsingEncoding:NSUTF8StringEncoding]];

    NSLog(@"加密的结果是:%@",[result :0]);

    //2.解密

    NSData * jiemi = [[RSACryptor sharedRSACryptor] decryptData:result];

    NSLog(@"解密的结果：%@",[[NSString alloc] initWithData:jiemi encoding:NSUTF8StringEncoding]);

}

// 填充模式  kSecPaddingNone 每次解密结果是固定的

// kSecPaddingPKCS1 是随机变化的。

#define kTypeOfWrapPadding        kSecPaddingNone