[Powered by Google Translate] [RSA] [羅布·鮑登] [和湯米MacWilliam] [哈佛大學] 這是CS50。[CS50.TV] 讓我們來看看RSA，一種廣泛使用的算法對數據進行加密。 凱撒和維瓊內爾的密碼的加密算法，如不是很安全。 隨著愷撒密碼，攻擊者只需要嘗試25種不同的鍵 得到消息的純文本。 ，雖然維瓊內爾密碼是比愷撒密碼更安全 因為較大的搜索空間為鑰匙，一旦被攻擊者 知道在維瓊內爾密碼的密鑰長度， 這可通過分析圖案的加密文本中確定， 維瓊內爾密碼是不是比愷撒密碼更安全的。 另一方面，RSA，這樣的攻擊是不容易的。 ，凱撒密碼和維瓊內爾的密碼使用相同的密鑰 來加密和解密消息。 這種特性使這些加密的對稱密鑰算法。 對稱密鑰算法的一個基本問題 是，他們依靠加密和發送郵件 和一個接收和解密的消息 前期已經同意，他們都將使用的關鍵。 但是，我們在這裡有一點啟動的問題。 2台電腦，想傳達如何建立它們之間的密鑰？ 如果該鍵必須是秘密的，那麼我們需要一種方法來加密和解密的關鍵。 如果我們所擁有的是對稱密鑰加密 我們剛剛回來的同樣的問題。 RSA中，另一方面，使用一對密鑰， 一個用於加密和另一個用於解密。 一個被稱為公共密鑰，而另一個是私有密鑰。 使用公共密鑰來加密消息。 正如你可能猜到了它的名字，我們可以分享我們的公鑰 任何人，我們要在不影響安全加密郵件的情況下。 使用公共密鑰加密的消息 只能與與其對應的私鑰進行解密。 雖然你可以分享你的公鑰，你應該始終保持你的私鑰的秘密。 ，由於私鑰應保持秘密，只有私鑰 可用於解密消息，2用戶如果想發送消息 與RSA加密來回 兩個用戶都需要有自己的公鑰和私鑰對。 從用戶1，用戶2的消息，只使用用戶2鍵對， 消息來自用戶2，用戶1僅使用用戶的密鑰對。 事實上，有2個獨立的密鑰來加密和解密消息 使RSA非對稱密鑰算法。 我們並不需要進行加密的公共密鑰，以發送到另一台計算機 以來的密鑰是公開的了。 這意味著，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在所有。 [笑聲] 在所有。