<div id="7x91n"></div>
    <progress id="7x91n"><tr id="7x91n"><ruby id="7x91n"></ruby></tr></progress>

    <em id="7x91n"></em>
      <progress id="7x91n"></progress>

      <dl id="7x91n"><ins id="7x91n"></ins></dl>

          <div id="7x91n"></div>

          <dl id="7x91n"></dl>

          <dl id="7x91n"><ins id="7x91n"><thead id="7x91n"></thead></ins></dl>

            <div id="7x91n"><tr id="7x91n"></tr></div>

            <div id="7x91n"></div>
            <div id="7x91n"></div>
            <dl id="7x91n"></dl><dl id="7x91n"><ol id="7x91n"></ol></dl>
            首頁 > 編程語言 > 詳細

            用實例給新手講解RSA加密算法

            時間:2018-09-23 11:00:14      閱讀:37      評論:0      收藏:0      [點我收藏+]

            標簽:問題   簡單   們的   自然   信息加密   加密算   優秀   傳遞   log   

            用實例給新手講解RSA加密算法

            2009年06月24日14:04  來源:技術分享圖片
            技術分享圖片我有話說 技術分享圖片查看評論(2) 技術分享圖片好文我頂(3)
             

            技術分享圖片
            圖為 RSA公開密鑰算法的發明人,從左到右Ron Rivest, Adi Shamir, Leonard Adleman. 照片攝于1978年

               RSA加密算法是最常用的非對稱加密算法,CFCA在證書服務中離不了它。但是有不少新來的同事對它不太了解,恰好看到一本書中作者用實例對它進行了簡化而生動的描述,使得高深的數學理論能夠被容易地理解。我們經過整理和改寫特別推薦給大家閱讀,希望能夠對時間緊張但是又想了解它的同事有所幫助。
               RSA是第一個比較完善的公開密鑰算法,它既能用于加密,也能用于數字簽名。RSA以它的三個發明者Ron Rivest, Adi Shamir, Leonard Adleman的名字首字母命名,這個算法經受住了多年深入的密碼分析,雖然密碼分析者既不能證明也不能否定RSA的安全性,但這恰恰說明該算法有一定的可信性,目前它已經成為最流行的公開密鑰算法。
              RSA的安全基于大數分解的難度。其公鑰和私鑰是一對大素數(100到200位十進制數或更大)的函數。從一個公鑰和密文恢復出明文的難度,等價于分解兩個大素數之積(這是公認的數學難題)。 
              RSA的公鑰、私鑰的組成,以及加密、解密的公式可見于下表:
            技術分享圖片

              可能各位同事好久沒有接觸數學了,看了這些公式不免一頭霧水。別急,在沒有正式講解RSA加密算法以前,讓我們先復習一下數學上的幾個基本概念,它們在后面的介紹中要用到:

            一、 什么是“素數”?
              素數是這樣的整數,它除了能表示為它自己和1的乘積以外,不能表示為任何其它兩個整數的乘積。例如,15=3*5,所以15不是素數;又如,12=6*2=4*3,所以12也不是素數。另一方面,13除了等于13*1以外,不能表示為其它任何兩個整數的乘積,所以13是一個素數。素數也稱為“質數”。

            二、什么是“互質數”(或“互素數”)?
              小學數學教材對互質數是這樣定義的:“公約數只有1的兩個數,叫做互質數。”這里所說的“兩個數”是指自然數。
              判別方法主要有以下幾種(不限于此):
            (1)兩個質數一定是互質數。例如,2與7、13與19。
            (2)一個質數如果不能整除另一個合數,這兩個數為互質數。例如,3與10、5與 26。
            (3)1不是質數也不是合數,它和任何一個自然數在一起都是互質數。如1和9908。
            (4)相鄰的兩個自然數是互質數。如 15與 16。
            (5)相鄰的兩個奇數是互質數。如 49與 51。
            (6)大數是質數的兩個數是互質數。如97與88。
            (7)小數是質數,大數不是小數的倍數的兩個數是互質數。如 7和 16。
            (8)兩個數都是合數(二數差又較大),小數所有的質因數,都不是大數的約數,這兩個數是互質數。如357與715,357=3×7×17,而3、7和17都不是715的約數,這兩個數為互質數。等等。

            三、什么是模指數運算? 
              指數運算誰都懂,不必說了,先說說模運算。模運算是整數運算,有一個整數m,以n為模做模運算,即m mod n。怎樣做呢?讓m去被n整除,只取所得的余數作為結果,就叫做模運算。例如,10 mod 3=1;26 mod 6=2;28 mod 2 =0等等。 
              模指數運算就是先做指數運算,取其結果再做模運算。如技術分享圖片
              好,現在開始正式講解RSA加密算法。
            算法描述:
            (1)選擇一對不同的、足夠大的素數p,q。
            (2)計算n=pq。
            (3)計算f(n)=(p-1)(q-1),同時對p, q嚴加保密,不讓任何人知道。
            (4)找一個與f(n)互質的數e,且1<e<f(n)。
            (5)計算d,使得de≡1 mod f(n)。這個公式也可以表達為d ≡e-1 mod f(n)
            這里要解釋一下,≡是數論中表示同余的符號。公式中,≡符號的左邊必須和符號右邊同余,也就是兩邊模運算結果相同。顯而易見,不管f(n)取什么值,符號右邊1 mod f(n)的結果都等于1;符號的左邊d與e的乘積做模運算后的結果也必須等于1。這就需要計算出d的值,讓這個同余等式能夠成立。
            (6)公鑰KU=(e,n),私鑰KR=(d,n)。
            (7)加密時,先將明文變換成0至n-1的一個整數M。若明文較長,可先分割成適當的組,然后再進行交換。設密文為C,則加密過程為:技術分享圖片
            (8)解密過程為:技術分享圖片。 

            實例描述:
              在這篇科普小文章里,不可能對RSA算法的正確性作嚴格的數學證明,但我們可以通過一個簡單的例子來理解RSA的工作原理。為了便于計算。在以下實例中只選取小數值的素數p,q,以及e,假設用戶A需要將明文“key”通過RSA加密后傳遞給用戶B,過程如下:
            (1)設計公私密鑰(e,n)和(d,n)。
            令p=3,q=11,得出n=p×q=3×11=33;f(n)=(p-1)(q-1)=2×10=20;取e=3,(3與20互質)則e×d≡1 mod f(n),即3×d≡1 mod 20。
            d怎樣取值呢?可以用試算的辦法來尋找。試算結果見下表:
            技術分享圖片
              通過試算我們找到,當d=7時,e×d≡1 mod f(n)同余等式成立。因此,可令d=7。從而我們可以設計出一對公私密鑰,加密密鑰(公鑰)為:KU =(e,n)=(3,33),解密密鑰(私鑰)為:KR =(d,n)=(7,33)。
            (2)英文數字化。
              將明文信息數字化,并將每塊兩個數字分組。假定明文英文字母編碼表為按字母順序排列數值,即:
            技術分享圖片
              則得到分組后的key的明文信息為:11,05,25。
            (3)明文加密 
              用戶加密密鑰(3,33) 將數字化明文分組信息加密成密文。由C≡Me(mod n)得:
            技術分享圖片
              因此,得到相應的密文信息為:11,31,16。
            4)密文解密。
              用戶B收到密文,若將其解密,只需要計算技術分享圖片,即:
            技術分享圖片
              用戶B得到明文信息為:11,05,25。根據上面的編碼表將其轉換為英文,我們又得到了恢復后的原文“key”。 
               你看,它的原理就可以這么簡單地解釋!
               當然,實際運用要比這復雜得多,由于RSA算法的公鑰私鑰的長度(模長度)要到1024位甚至2048位才能保證安全,因此,p、q、e的選取、公鑰私鑰的生成,加密解密模指數運算都有一定的計算程序,需要仰仗計算機高速完成。

            最后簡單談談RSA的安全性

               首先,我們來探討為什么RSA密碼難于破解? 
               在RSA密碼應用中,公鑰KU是被公開的,即e和n的數值可以被第三方竊聽者得到。破解RSA密碼的問題就是從已知的e和n的數值(n等于pq),想法求出d的數值,這樣就可以得到私鑰來破解密文。從上文中的公式:d ≡e-1 (mod((p-1)(q-1)))或de≡1 (mod((p-1)(q-1))) 我們可以看出。密碼破解的實質問題是:從Pq的數值,去求出(p-1)和(q-1)。換句話說,只要求出p和q的值,我們就能求出d的值而得到私鑰。
               當p和q是一個大素數的時候,從它們的積pq去分解因子p和q,這是一個公認的數學難題。比如當pq大到1024位時,迄今為止還沒有人能夠利用任何計算工具去完成分解因子的任務。因此,RSA從提出到現在已近二十年,經歷了各種攻擊的考驗,逐漸為人們接受,普遍認為是目前最優秀的公鑰方案之一。
              然而,雖然RSA的安全性依賴于大數的因子分解,但并沒有從理論上證明破譯RSA的難度與大數分解難度等價。即RSA的重大缺陷是無法從理論上把握它的保密性能如何。
              此外,RSA的缺點還有:A)產生密鑰很麻煩,受到素數產生技術的限制,因而難以做到一次一密。B)分組長度太大,為保證安全性,n 至少也要 600 bits 以上,使運算代價很高,尤其是速度較慢,較對稱密碼算法慢幾個數量級;且隨著大數分解技術的發展,這個長度還在增加,不利于數據格式的標準化。因此,使用RSA只能加密少量數據,大量的數據加密還要靠對稱密碼算法。

             

            原文出處:http://bank.hexun.com/2009-06-24/118958531.html

             

            用實例給新手講解RSA加密算法

            標簽:問題   簡單   們的   自然   信息加密   加密算   優秀   傳遞   log   

            原文:https://www.cnblogs.com/HaiHong/p/9691969.html

            (0)
            (0)
               
            舉報
            評論 一句話評論(0
            0條  
            登錄后才能評論!
            ? 2014 bubuko.com 版權所有 魯ICP備09046678號-4
            打開技術之扣,分享程序人生!
                         

            魯公網安備 37021202000002號

            福建省餐饮许可现场