五分鐘知識科普:什麼是 RSA 算法

2021-02-15 五分鐘學算法
RSA 算法歷史

RSA 是 1977 年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。

當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的。

但實際上,在 1973 年,在英國政府通訊總部工作的數學家克利福德·柯克斯(Clifford Cocks)在一個內部文件中提出了一個相同的算法,但他的發現被列入機密,一直到 1997 年才被發表。

RSA 算法基礎知識 密碼學知識

明文:是指沒有加密的文字(或者字符串)。

加密:是以某種特殊的算法改變原有的信息數據,使得未授權的用戶即使獲得了已加密的信息,但因不知解密的方法,仍然無法了解信息的內容。

密文:密文是對明文進行加密後的報文。

對稱加密:對稱是指,在對明文進行加密,對密文執行解密加密過程採用相同的規則(通常將雙方採用的規則稱為"密鑰")。

例如:
  (1)甲方選擇某一種加密規則,對信息進行加密;
  (2)乙方使用同一種規則,對信息進行解密。

非對稱加密:非對稱加密是指通信雙方採用不同的密鑰進行加密解密。

例如:
  (1)乙方生成兩把密鑰(公鑰和私鑰)。公鑰是公開的,任何人都可以獲得,私鑰則是保密的。
  (2)甲方獲取乙方的公鑰,然後用它對信息加密。
  (3)乙方得到加密後的信息,用私鑰解密。

數學知識

互質關係:如果兩個正整數,除了數字 1 之外沒有其他公因子,我們稱這兩個數是互質關係。

同餘定理:給定一個正整數 m,如果兩個整數a和b滿足a-b能夠被m整除,即(a-b)/m得到一個整數,那麼就稱整數 a 與 b 對模 m 同餘,記作 a ≡ b(mod m)。

RSA 算法流程

(1)選擇兩個不相等的質數p和q

例如:選擇兩個不等質數分別為 61 和 53 (實際應用中選擇的質數都相當大)。

(2)計算p和q的乘積n

n = p*q = 61 * 53 = 3233。

(3)計算 n 的歐拉函數 φ(n)

φ(3233) = φ(61 * 53) = φ(61) * φ(53)。

由於 61 為質數,因此 φ(61) = 61 - 1 = 60。同理 φ(53) = 53  - 1 = 52。則 φ(3233) = 60 * 52 = 3120。

(4)隨機選擇一個整數 e ,條件是1< e < φ(n),且 e 與 φ(n) 互質

隨機選擇一個質數e,保證1< e < 3120,這裡選擇e = 17。

(5)計算e對於φ(n)的模反元素d
e * d ≡ 1 (mod φ(n))。其中e = 17,φ(n) = 3120。

設e*d是φ(n)的k的整數倍,餘數為1。則上式可以轉化為:
17 * d = 3120k + 1。繼續轉化得到:
17 * d + 3120y = 1。其中y = -k。

其中,對於d的求解轉化為二元一次方程求解。此方程可以使用擴展歐幾裡得方法進行求解。通過輾轉相除法計算出一組解為(2753,-15)。

解得d = 2753

(6)將n和e封裝成公鑰,n和d封裝成私鑰

加密公鑰為(3233,17),私鑰為(3233,2753)。

RSA 算法分析

那麼 RSA 算法是如何保證安全性的呢?

在 RSA 算法中 n 與 e 是公開的,那麼破解 RSA 加密的步驟即為通過 n 與 e 計算出私鑰 d 的值。

(1)ed ≡ 1 (mod φ(n))。只有知道 e 和 φ(n),才能算出 d 。
(2)φ(n) = (p-1)(q-1)。只有知道 p 和 q ,才能算出 φ(n)。

由此得出密碼破解的實質問題是:從p * q的值n,去求出 (p-1) 和 (q-1)。換句話說,只要求出 p 和 q 的值,我們就能求出 d 的值而得到私鑰。但是,當 p 和 q 是是很大的質數時,從它們的積 p * q 去分解因子 p 和 q ,這是一個公認的數學難題。

比如當p * q大到1024位時,迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務。

雖然理論上 RSA 是可以破解的,但是隨著密鑰長度增加,破解的代價是不可接受的。

因此,只要密鑰長度足夠長,用 RSA 加密的信息實際上是不能被解破的。目前被破解的最長 RSA 密鑰就是 768 位。

RSA 算法總結

RSA 的安全性依賴於大數分解,因此 RSA 算法加密安全性較高。但是,RSA 算法為保證安全性,會大大提升密鑰長度,導致運算速度變慢。這導致它在大量數據加密時並不適用。

相關焦點

  • CTF密碼學之RSA攻擊算法
    前言:學習完基本數論後,我們開始學習 RSA 的各種攻擊算法及其數學原理。希望大家在學習的過程中更多的去關注攻擊算法實現的原理,而不僅僅只在於 copy 攻擊代碼。import rsa            #rsa模塊from gmpy2 import*    #gmpy2模塊
  • CTF|玩轉RSA加密算法(一)
    RSA是一種非對稱加密算法,它由 公鑰(n/e),私鑰(n/d),明文M和密文C組成。
  • ECC+RSA雙證書解決方案
    什麼是ECC  ECC是Elliptic Curves Cryptography的縮寫,意為橢圓曲線密碼編碼學。和RSA算法一樣,ECC算法也屬於公開密鑰算法。
  • RSA 加密是什麼原理?
    雖然剛才舉例說明了 RSA 算法能對數據進行加密解密,但是我們如何證明 RSA 算法是嚴格成立的?這時候就得藉助一些數學工具了。首先介紹一點點背景知識:背景知識1:歐拉定理:n 是一個正整數,a 和 n 互質,ϕ(n) 表示 1 到 n 中和 n 互質數的個數,也就是上述步驟3中的 L,那麼如下公式成立:翻譯過來就是:a 的 ϕ(n) 次方對 n 取餘數,結果是1。
  • 什麼是 RSA 算法
    非對稱加密算法RSA借鑑了這種思想,使用公鑰和私鑰來完成加解密,但是又避免了密鑰傳輸,RSA算法的公鑰是公開的,使用公鑰加密的信息,必須使用對應的私鑰才能解密。3. RSA算法RSA算法可以說是地球上最重要的算法之一,是數據通信和網絡安全的基石。
  • 圖解|什麼是RSA算法
    非對稱加密算法RSA借鑑了這種思想,使用公鑰和私鑰來完成加解密,但是又避免了密鑰傳輸,RSA算法的公鑰是公開的,使用公鑰加密的信息,必須使用對應的私鑰才能解密。3. RSA算法RSA算法可以說是地球上最重要的算法之一,是數據通信和網絡安全的基石。
  • RSA算法詳解
    RSA算法用到的數學知識特別多,所以在中間介紹這個算法生成私鑰和公鑰的過程中會穿插一些數學知識。生成步驟如下:1.尋找兩個不相同的質數隨意選擇兩個大的質數p和q,p不等於q,計算N=p*q;什麼是質數?
  • 密碼學_RSA算法原理詳解
    RSA算法簡介:     RSA算法 是一種公鑰加密算法,RSA算法相比別的算法思路非常清晰,但是想要破解的難度非常大
  • RSA 加密算法主要公式
    RSA 是非對稱的加密算法,其中它有一些相關的數學公式。讓我們從一道題開始了解 RSA 的數學公式。
  • 用實例給新手講解RSA加密算法
    RSA是第一個比較完善的公開密鑰算法,它既能用於加密,也能用於數字籤名。RSA以它的三個發明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名,這個算法經受住了多年深入的密碼分析,雖然密碼分析者既不能證明也不能否定RSA的安全性,但這恰恰說明該算法有一定的可信性,目前它已經成為最流行的公開密鑰算法。
  • TLS/SSL 協議-非對稱加密(RSA)原理
    前面文章學習過 對稱加密的原理,在通信雙方發送完加密的密文之後,需要發送密鑰給對方才能解密,這就要求發送密鑰的信息通道安全可靠,才能保證數據的安全性,而非對稱加密算法1977 年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)、倫納德·阿德曼(Leonard Adleman)一起提出,因此命名為 RSA 算法:
  • 算法是什麼:計算機領域中算法的科普
    當你使用搜尋引擎(例如Google Chrome、Mozilla Firefox等)的時候,後臺發生了什麼?當你詢問虛擬助手(例如Alexa、Google助手或Siri)的時候,後臺發生了什麼?它們怎麼會知道答案?為何它們會顯示正確答案?所有這些都要感謝算法。
  • 如何給產品經理解釋什麼是 RSA 加密(一)
    > 我們之前兩篇文章已經介紹了如何在 Python 下面使用 RSA 加密,以及 python-rsa
  • 網絡安全加密——DES、AES、RSA、Base64、MD5加密原理介紹,代碼實現
    本專題將連續的、全方位的、深入地闡述網絡安全加密的原理及實用案例分析,希望對學習網絡安全的你有幫助,覺得有用記得轉發給身邊需要的朋友哈~~ 學好密碼技術變身信息安全保護神,科普式教學的《現代密碼學》全新上線,乾貨+視頻,學習效果槓槓滴,別說小編沒告訴你~特別感謝本期作者——時間已靜止。
  • 數據傳輸安全:RSA加密算法及其數學原理
    所以,明文傳輸在網絡中是非常不安全的.針對於此,數據加密就誕生了.RSA是計算機網絡中最常見的加密算法,它是一種非對稱加密算法.什麼是非對稱加密算法,先了解一個對稱加密算法.RSA加密(非對稱加密)「非對稱加密算法需要兩個密鑰:公開密鑰(publickey:簡稱公鑰)和私有密鑰(privatekey:簡稱私鑰)。公鑰與私鑰是一對,如果用公鑰對數據進行加密,只有用對應的私鑰才能解密。因為加密和解密使用的是兩個不同的密鑰,所以這種算法叫作非對稱加密算法。
  • 五分鐘了解機器學習十大算法
    本文為有志於成為數據科學家或對此感興趣的讀者們介紹最流行的機器學習算法。機器學習是該行業的一個創新且重要的領域。我們為機器學習程序選擇的算法類型,取決於我們想要實現的目標。現在,機器學習有很多算法。因此,如此多的算法,可能對於初學者來說,是相當不堪重負的。
  • 非對稱加密算法——RSA加密原理及數學推導
    一、  RSA是什麼?看到標題的第一瞬間,先想一下,RSA是什麼呢?百度百科是這麼說的:RSA是一種非對稱的加密機制。是一種公開密鑰密碼體制。所謂的公開密鑰密碼體制就是使用不同的加密密鑰與解密密鑰,是一種「由已知加密密鑰推導出解密密鑰在計算上是不可行的」密碼體制。
  • 衢州科普微信平臺科普知識答題送話費開始啦!
    自2016年1月1日起,衢州市科協開通「衢州科普」微信平臺,開展科普知識答題,每天在5分鐘內回答5道題,每答對一題得10分,每月積滿
  • RSA加密算法數學原理和實現(筆記)
    如 53(mod7)=125(mod7)=6好,現在開始正式講解RSA加密算法。算法描述:(1)選擇一對不同的、足夠大的素數p,q。(2)計算n=pq。(3)計算f(n)=(p-1)(q-1),同時對p, q嚴加保密,不讓任何人知道。(4)找一個與f(n)互質的數e(5)計算d,使得de≡1 mod f(n)。
  • 五分鐘帶你了解哈希算法
    「生日攻擊」是什麼?我們曾經聽過,如果你把23個人放在一個房間,就會有50%的概率,其中的2人會有同樣的生日?將這個數字提升到70人在一個房間,就會有99.9%的概率。這就是我們所說的鴿巢原理,也就說如果把100個各自放到99個箱子,你就必須在1個盒子裡面放2個鴿子。換句話說,固定的輸出意味著collisions 可能會找到固定的排序。