[Powered by Google Translate] [RSA]
[罗布·鲍登] [和汤米MacWilliam] [哈佛大学]
这是CS50。[CS50.TV]
让我们来看看RSA，一种广泛使用的算法对数据进行加密。
凯撒和维琼内尔的密码的加密算法，如不是很安全。
随着恺撒密码，攻击者只需要尝试25种不同的键
得到消息的纯文本。
，虽然维琼内尔密码是比恺撒密码更安全
因为较大的搜索空间为钥匙，一旦被攻击者
知道在维琼内尔密码的密钥长度，
这可通过分析图案的加密文本中确定，
维琼内尔密码是不是比恺撒密码更安全的。
另一方面，RSA，这样的攻击是不容易的。
，凯撒密码和维琼内尔的密码使用相同的密钥
来加密和解密消息。
这种特性使这些加密的对称密钥算法。
对称密钥算法的一个基本问题
是，他们依靠加密和发送邮件
和一个接收和解密的消息
前期已经同意，他们都将使用的关键。
但是，我们在这里有一点启动的问题。
2台电脑，想传达如何建立它们之间的密钥？
如果该键必须是秘密的，那么我们需要一种方法来加密和解密的关键。
如果我们所拥有的是对称密钥加密
我们刚刚回来的同样的问题。
RSA中，另一方面，使用一对密钥，
一个用于加密和另一个用于解密。
一个被称为公共密钥，而另一个是私有密钥。
使用公共密钥来加密消息。
正如你可能猜到了它的名字，我们可以分享我们的公钥
任何人，我们要在不影响安全加密邮件的情况下。
使用公共密钥加密的消息
只能与与其对应的私钥进行解密。
虽然你可以分享你的公钥，你应该始终保持你的私钥的秘密。
和只有私钥可以用来解密消息
如果2用户要发送邮件加密的RSA
来回两个用户都需要有自己的公钥和私钥对。
从用户1，用户2的消息
只使用用户2用户1用户2的密钥对和消息
只用用户1的密钥对。
事实上，有2个独立的密钥来加密和解密消息
使RSA非对称密钥算法。
我们并不需要进行加密的公共密钥，以发送到另一台计算机
以来的密钥是公开的了。
这意味着，RSA不具有相同的启动问题
对称密钥算法。
所以，如果我想使用RSA加密发送消息
给抢了，我需要先抢夺的公共密钥。
要生成一对密钥，罗布需要选择2个大素数。
这些数字将被用于公共和私营键，
但公共密钥将只使用这两个数字的乘积，
而不是数字本身。
一旦我使用Rob的公共密钥加密的消息
我可以将消息发送到罗布。
对于计算机，保号是一个困难的问题。
公共密钥，请记住，使用2个素数的乘积。
本产品必须有2个因素，
这恰好弥补的私钥的数字。
为了对消息进行解​​密，RSA将使用此私钥
或数字相乘，在这个过程中创建的公共密钥。
因为它的计算因素的号码
使用公共密钥的私钥在使用2号
这是很难找出攻击者的私钥
将是必要的对消息进行解​​密。
现在，让我们进入一些低级别的细节RSA。
让我们先来看看我们如何能够产生一对密钥。
首先，我们需要2个素数。
我们会打电话给这两个数p和q。
为了挑选p和q，在实践中，我们将伪随机生成
大量，然后使用一个测试，用于确定是否
这些数字可能是素数。
我们可以不断产生随机数一遍又一遍
直到我们有2个素数，我们可以使用。
下面让我们挑P = 23，Q = 43。
记住，在实践中，p和q要大得多号码。
据我们所知，较大的数字，就越难
破解加密的邮件。
但它也更昂贵的加密和解密信息。
今天，它经常被推荐，p和q是至少为1024位，
这使每个数字在300位十进制数字。
但在这个例子中，我们将选择这些小的数字。
现在，我们将乘p和q一起获得第3号，
我们称之为N。
在我们的例子中，N = 23 * 43 = 989。
我们有N = 989。
接下来，我们将乘用q p - 1 - 1
获得第4号，我们会打电话给米。
在我们的案例中，M = 22 *​​ 42 = 924。
我们有m = 924。
现在我们需要一个数e是互质米
和小于m。
两个数是互质或互素
如果只有正整数，将他们都均匀为1。
换言之，e和m的最大公约数
必须是1。
在实践中，这是常见的电子商务是素数65537
只要该数量不发生的m是一个因素。
对于我们的钥匙，我们将选择E = 5
自5是相对素数到924。
最后，我们需要更多的数量，我们将调用D。
D必须有一定的价值，满足方程= 1（MOD米）。
这个mod m表示，我们将使用一种叫做模块化算术。
在模块化算术，一旦得到高于一些上限
它会换回来大约为0。
时钟，例如，采用模块化算术。
一分钟后，1:59，例如，是凌晨2点，
1:60。
分针缠0
在到达一个上限的60。
因此，我们可以说60是等于0（MOD 60）
和125是相当于65是相当于5（模60）。
将是对我们的公共密钥e和n
在这种情况下，e是5和n为989。
我们的私有密钥将是对d和n，
在我们的例子中是185和989。
请注意，我们的原素数p和q不出现
在我们的私人或公共密钥的任何地方。
现在，我们有我们的密钥对，让我们来看看我们如何能够加密
和解密的消息。
我想将消息发送到罗布，
因此，他将是一个生成此密钥对。
然后，我会问罗布他的公钥，我将使用
对消息进行加密，发送给他。
请记住，这是完全可行的罗布与我分享他的公钥。
但它不会是好的分享自己的私有密钥。
我没有任何想法，他的私人密钥是什么。
成若干块，我们可以打破我们的消息m
所有小于n，然后加密这些块。
我们将加密的字符串的CS50，我们可以分手分为4块，
每一个字母。
为了加密我的消息，我需要把它转换成
某种形式的数字表示。
让我们连接我的消息中的字符的ASCII值。
为了加密一个给定的消息m
我需要计算C = M，E（mod n）的。
但是，m必须是小于n，
否则完整的邮件不能被表示模n。
我们可以打破分成几个块，所有这一切都是小于n，m，最高
并加密这些块。
这些块进行加密，我们可以得到C1 = 67 5（MOD 989）
= 658。
我们的第二块，我们有83到5（MOD 989）
= 15。
对于我们的第三块，我们有53到5（MOD 989）
= 799。
最后，我们的最后一个块，我们有48到5（MOD 989）
= 975。
现在，我们可以送过来抢这些加密的值。
在这里，你走了，罗伯。
虽然我们的信息是在飞行中，让我们再看看
我们如何得到该值的d。
我们的数d 5D = 1（模924），以满足需要。
这使D的乘法逆模924。
考虑到2的整数，a和b，扩展的欧几里德算法
可以用来找到这些2个整数的最大公约数。
它也将给予我们2其他数目，x和y，
满足方程ax + = a和b的最大公约数。
这是如何帮助我们呢？
好了，堵在E = 5的
和m = 924为b
我们已经知道，这些数字是互质的。
他们的最大公约数是1。
这为我们提供了5倍+ 924y = 1
或5x = 1 - 924y。
但是，如果我们只关心一切模924
那么我们就可以删除 - 924y。
回想一下时钟。
如果分针是1，然后正好是10小时，
我们知道分针将仍然是1。
在这里，我们从1开始，然后绕究竟y次，
所以我们仍然会在1。
我们有5倍= 1（模924）。
在这里x是我们正在寻找之前的D一样，
因此，如果我们使用扩展的欧几里德算法
得到这个数x，这是我们要利用我们的D数。
现在，让我们来运行扩展的欧几里德算法为A = 5
和b = 924。
我们将使用的方法称为表的方法。
我们的表将有4个列，的x，y，D，和k。
我们的餐桌上开始2行。
在第一行中，我们有1，0，那么我们的价值的，这是5，
和我们的第二行是0，1，我们为b的值，它是924。
的值的第4列，K，结果将是
d的值除以d的值在它的上面的行中的
在同一行上。
我们有5除以924的一些其余为0。
这意味着我们有k = 0。
现在的值的每一个其他小区，将小区2的值，它上面的行
减去的排它上面的时间k的值。
让我们开始与d排在第三。
我们有5个 - 924 * 0 = 5。
下一步，我们0 - 1 0 0
和1 - 0 * 0，它是1。
太糟糕了，让我们移动到下一行。
首先，我们需要我们的k值。
924除以5 = 184，还有剩余，
因此，我们对k的值是184。
现在924 - 5 * 184 = 4。
1 - 0 * 184为1和0 - 1 * 184 -184。
好吧，让我们做的下一行。
我们的k值是1，因为
还有剩余5除以4 = 1。
让我们填写在其他列中。
5 - 4 * 1 = 1。
0 - 1 * 1 = -1。
1 - 184 * 1是185。
让我们来看看什么将是我们的下一个k值。
嗯，它看起来像我们有4个1分，这是4。
，除以1我们在这种情况下，使得k等于
在上述行d的值意味着我们已经完成了我们的算法。
我们可以看到，在这里，我们有x = 185和y = -1的最后一排。
现在，让我们来回到我们原来的目标。
我们说，x的值作为结果，运行该算法
将的乘法逆元（模b）。
这意味着，185是5的乘法逆（MOD 924）
这意味着，我们有一个值185为d。
一个事实，即d = 1的最后一排
验证E是互质米。
如果不是1，那么，我们就必须选择一个新的电子邮件。
现在，让我们来看看如果罗布已收到我的消息。
当有人向我发送加密的邮件
只要我保持我的私钥的秘密
我只有一个人可以解密该消息。
要解密块C我可以计算出原始邮件
等于至d功率（mod n）的组块。
请记住，D和N是从我的私钥。
要得到一个完整的消息，从它的块中，我们每个块进行解密
连接的结果。
究竟如何安全的RSA？
事实是，我们不知道。
安全性的基础上多久会采取攻击者破解的消息
与RSA加密。
请记住，一个攻击者访问你的公共密钥，
其中包含e和n。
如果攻击者设法n分解成2个质数，p和q，
然后她可以使用扩展的欧几里德算法计算d。
这给她的私人密钥，该密钥可以用来解密任何消息。
但是，如何能迅速因素整数？
同样，我们不知道。
没有人做一个快速的方法，
这意味着，由于大n足够
攻击者不切实际的长
以因素的号码。
如果有人发现一种快速的方式分解整数
RSA将被打破。
但是，即使整数分解本质上是慢
RSA算法仍然有一些缺陷
允许容易解密的消息。
没有人发现，发现这样的缺陷，
但是，这并不意味着不存在。
从理论上讲，有人可以在那里阅读所有与RSA加密的数据。
还有另外一个位的隐私问题。
如果Tommy一些消息，用我的公钥进行加密，
攻击者使用我的公钥加密相同的消息
攻击者会看到的消息是相同的
，从而知道汤米加密。
为了防止这一点，消息通常与随机比特填充
之前被加密，以使加密的相同的消息
多次外观会有所不同，只要在邮件上的填充是不同。
但是，请记住我们是如何分割成块的消息
使每个组块是小于n？
填充块，意味着我们可能需要分开
成甚至更多的块，因为该填充块必须是小于n。
与RSA加密和解密是相对昂贵的，
需要分手的消息分成许多块可以是非常昂贵的。
如果将大量的数据需要进行加密和解密
我们可以结合对称密钥算法的好处
与RSA的安全性和效率。
虽然我们不会进入这里，
AES是一种对称密钥算法，像维琼内尔和凯撒密码
但更难破解。
当然，我们不能没有建立一个共享密钥使用AES
2个系统之间，我们看到了与之前的问题。
但是，现在我们可以使用RSA的2个系统之间建立共享的密钥。
我们会打电话给计算机发送数据的发送者
计算机接收的数据的接收器。
接收器有一个RSA密钥对，发送
发送者的公钥。
发送者产生一个AES密钥，
与接收方的RSA公共密钥加密，
和AES密钥发送到接收器。
接收器与RSA私人密钥对消息进行解​​密。
发送方和接收器，它们之间有一个共同的AES密钥。
AES，这是快得多比RSA加密和解密，
现在可以使用大容量的数据进行加密，并将它们发送到接收机，
谁可以解密使用相同的密钥。
AES，这是快得多比RSA加密和解密，
现在可以使用大容量的数据进行加密，并将它们发送到接收机，
谁可以解密使用相同的密钥。
我们只需要RSA转移的共享密钥。
我们不再需要使用RSA在所有。
它看起来像我已经得到了消息。
这不要紧，如果任何人读什么在纸张上飞机前，我发现它
因为我是唯一一个用私钥。
让我们来解密在消息中的每个组块。
第一个块，658，提高到d的权力，这是185，
模n，这是989，是等于67，
这是在ASCII字母“C”。
现在，到了第二块。
第二块值15，
我们提出的第185电源，
MOD 989，这是等于83
这是在ASCII字母S。
现在，我们的第三块，它的价值799提高到185，
MOD 989，这是等于53，
它的价值在ASCII字符5。
现在，最后一个块，它的值是975，
我们募集到185，MOD 989，
该值是48，这是值的ASCII字符0。
我的名字是罗布·波顿，这是CS50。
[CS50.TV]
RSA在所有。
RSA在所有。 [笑声]
在所有。