當前位置:首頁 » 密碼管理 » cjsrsa加密

cjsrsa加密

發布時間: 2023-04-01 13:30:57

1. RSA  加密演算法(原理篇)

前幾天看到一句話,「我們中的很多人把一生中最燦爛的笑容大部分都獻給了手機和電腦屏幕」。心中一驚,這說明了什麼?手機和電腦已經成為了我們生活中的一部分,所以才會有最懂你的不是你,也不是你男朋友,而是大數據。

如此重要的個人數據,怎樣才能保證其在互聯網上的安全傳輸呢?當然要靠各種加密演算法。說起加密演算法,大家都知道有哈希、對稱加密和非對稱加密了。哈希是一個散列函數,具有不可逆操作;對稱加密即加密和解密使用同一個密鑰,而非對稱加密加密和解密自然就是兩個密鑰了。稍微深入一些的,還要說出非對稱加密演算法有DES、3DES、RC4等,非對稱加密演算法自然就是RSA了。那麼當我們聊起RSA時,我們又在聊些什麼呢?今天筆者和大家一起探討一下,有不足的地方,還望各位朋友多多提意見,共同進步。

RSA簡介:1976年由麻省理工學院三位數學家共同提出的,為了紀念這一里程碑式的成就,就用他們三個人的名字首字母作為演算法的命名。即 羅納德·李維斯特 (Ron Rivest)、 阿迪·薩莫爾 (Adi Shamir)和 倫納德·阿德曼 (Leonard Adleman)。

公鑰:用於加密,驗簽。

私鑰:解密,加簽。

通常知道了公鑰和私鑰的用途以後,即可滿足基本的聊天需求了。但是我們今天的主要任務是來探究一下RSA加解密的原理。

說起加密演算法的原理部分,肯定與數學知識脫不了關系。

我們先來回憶幾個數學知識:

φn = φ(A*B)=φ(A)*φ(B)=(A-1)*(B-1)。

這個公式主要是用來計算給定一個任意的正整數n,在小於等於n的正整數中,有多少個與n構成互質的關系。

其中n=A*B,A與B互為質數,但A與B本身並不要求為質數,可以繼續展開,直至都為質數。

在最終分解完成後,即 φ(N) = φ(p1)*φ(p2)*φ(p3)... 之後,p1,p2,p3都是質數。又用到了歐拉函數的另一個特點,即當p是質數的時候,φp = p - 1。所以有了上面給出的歐拉定理公式。

舉例看一下:

計算15的歐拉函數,因為15比較小,我們可以直接看一下,小於15的正整數有 1、2、3、4、5、6、7、8、9、10、11、12、13、14。和15互質的數有1、2、4、7、8、11、13、14一共四個。

對照我們剛才的歐拉定理: 。

其他感興趣的,大家可以自己驗證。

之所以要在這里介紹歐拉函數,我們在計算公鑰和私鑰時候,會用到。

如果兩個正整數m 和 n 互質,那麼m 的 φn 次方減1,可以被n整除。

 其中  .

其中當n為質數時,那麼  上面看到的公式就變成了

 mod n   1.

這個公式也就是著名的 費馬小定理 了。

如果兩個正整數e和x互為質數,那麼一定存在一個整數d,不止一個,使得 e*d - 1 可以被x整除,即 e * d mode x   1。則稱 d 是 e 相對於 x的模反元素。

了解了上面所講的歐拉函數、歐拉定理和模反元素後,就要來一些化學反應了,請看圖:

上面這幅圖的公式變化有沒有沒看明白的,沒看明白的咱們評論區見哈。

最終我們得到了最重要的第5個公式的變形,即紅色箭頭後面的:

 mod n   m。

其中有幾個關系,需要搞明白,m 與 n 互為質數,φn = x,d 是e相對於x的模反元素。

有沒有看到一些加解密的雛形。

從 m 到 m。 這中間涵蓋了從加密到解密的整個過程,但是缺少了我們想要的密文整個過程。

OK,下面引入本文的第四個數學公式:

我們來看一下整個交換流程:

1、客戶端有一個數字13,服務端有一個數字15;

2、客戶端通過計算 3的13次方 對 17 取余,得到數字12; 將12發送給服務端;同時服務端通過計算3的15次方,對17取余,得到數字6,將6發送給客戶端。至此,整個交換過程完成。

3、服務端收到數字12以後,繼續計算,12的15次方 對 17取余,得到 數字10。

4、客戶端收到數字 6以後,繼續計算,6的13次方 對 17 取余,得到數字 10。

有沒有發現雙方,最終得到了相同的內容10。但是這個數字10從來沒有在網路過程中出現過。

好,講到這里,可能有些人已經恍然大悟,這就是加密過程了,但是也有人會產生疑問,為什麼要取數字3 和 17 呢,這里還牽涉到另一個數學知識,原根的問題。即3是17的原根。看圖

有沒有發現規律,3的1~16次方,對17取余,得到的整數是從1~16。這時我們稱3為17的原根。也就是說上面的計算過程中有一組原根的關系。這是最早的迪菲赫爾曼秘鑰交換演算法。

解決了為什麼取3和17的問題後,下面繼續來看最終的RSA是如何產生的:

還記得我們上面提到的歐拉定理嗎,其中 m 與 n 互為質數,n為質數,d 是 e 相對於 φn的模反元素。

當迪菲赫爾曼密鑰交換演算法碰上歐拉定理會產生什麼呢?

我們得到下面的推論:

好,到這里我們是不是已經看到了整個的加密和解密過程了。

其中 m 是明文;c 是密文; n 和 e 為公鑰;d 和 n 為私鑰 。

其中幾組數字的關系一定要明確:

1、d是e 相對於 φn 的模反元素,φn = n-1,即 e * d mod n = 1.

2、m 小於 n,上面在講迪菲赫爾曼密鑰交換演算法時,提到原根的問題,在RSA加密演算法中,對m和n並沒有原根條件的約束。只要滿足m與n互為質數,n為質數,且m < n就可以了。

OK,上面就是RSA加密演算法的原理了,經過上面幾個數學公式的狂轟亂炸,是不是有點迷亂了,給大家一些時間理一下,後面會和大家一起來驗證RSA演算法以及RSA為什麼安全。

2. java rsa私鑰加密

java rsa私鑰加密是什麼?讓我們一起來了解一下吧!

java rsa私鑰加密是一種加密演算法。私鑰加密演算法是用私鑰來進行加密與解密信息。私鑰加密也被稱作對稱加密,原因是加密與解密使用的秘鑰是同一個。

RSA加密需要注意的事項如下:

1. 首先產生公鑰與私鑰

2. 設計加密與解密的演算法

3. 私鑰加密的數據信息只能由公鑰可以解密

4. 公鑰加密的數據信息只能由私鑰可以解密

實戰演練,具體步驟如下: public class RsaCryptTools {     private static final String CHARSET = "utf-8";     private static final Base64.Decoder decoder64 = Base64.getDecoder();     private static final Base64.Encoder encoder64 = Base64.getEncoder();       /**      * 生成公私鑰      * @param keySize      * @return      * @throws NoSuchAlgorithmException      */     public static SecretKey generateSecretKey(int keySize) throws NoSuchAlgorithmException {         //生成密鑰對         KeyPairGenerator keyGen = KeyPairGenerator.getInstance("RSA");         keyGen.initialize(keySize, new SecureRandom());         KeyPair pair = keyGen.generateKeyPair();         PrivateKey privateKey = pair.getPrivate();         PublicKey publicKey = pair.getPublic();         //這里可以將密鑰對保存到本地         return new SecretKey(encoder64.encodeToString(publicKey.getEncoded()), encoder64.encodeToString(privateKey.getEncoded()));     }     /**      * 私鑰加密      * @param data      * @param privateInfoStr      * @return      * @throws IOException      * @throws InvalidCipherTextException      */     public static String encryptData(String data, String privateInfoStr) throws IOException, InvalidKeySpecException, NoSuchAlgorithmException, InvalidKeyException, NoSuchPaddingException, BadPaddingException, IllegalBlockSizeException {           Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");         cipher.init(Cipher.ENCRYPT_MODE, getPrivateKey(privateInfoStr));         return encoder64.encodeToString(cipher.doFinal(data.getBytes(CHARSET)));     }       /**      * 公鑰解密      * @param data      * @param publicInfoStr      * @return      */     public static String decryptData(String data, String publicInfoStr) throws NoSuchPaddingException, NoSuchAlgorithmException, InvalidKeySpecException, InvalidKeyException, BadPaddingException, IllegalBlockSizeException, UnsupportedEncodingException {         byte[] encryptDataBytes=decoder64.decode(data.getBytes(CHARSET));         //解密         Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");         cipher.init(Cipher.DECRYPT_MODE, getPublicKey(publicInfoStr));         return new String(cipher.doFinal(encryptDataBytes), CHARSET);     }     private static PublicKey getPublicKey(String base64PublicKey) throws NoSuchAlgorithmException, InvalidKeySpecException {         X509EncodedKeySpec keySpec = new X509EncodedKeySpec(Base64.getDecoder().decode(base64PublicKey.getBytes()));         KeyFactory keyFactory = KeyFactory.getInstance("RSA");         return keyFactory.generatePublic(keySpec);     }     private static PrivateKey getPrivateKey(String base64PrivateKey) throws NoSuchAlgorithmException, InvalidKeySpecException {         PrivateKey privateKey = null;         PKCS8EncodedKeySpec keySpec = new PKCS8EncodedKeySpec(Base64.getDecoder().decode(base64PrivateKey.getBytes()));         KeyFactory keyFactory = null;         keyFactory = KeyFactory.getInstance("RSA");         privateKey = keyFactory.generatePrivate(keySpec);         return privateKey;     }       /**      * 密鑰實體      * @author hank      * @since 2020/2/28 0028 下午 16:27      */     public static class SecretKey {         /**          * 公鑰          */         private String publicKey;         /**          * 私鑰          */         private String privateKey;           public SecretKey(String publicKey, String privateKey) {             this.publicKey = publicKey;             this.privateKey = privateKey;         }           public String getPublicKey() {             return publicKey;         }           public void setPublicKey(String publicKey) {             this.publicKey = publicKey;         }           public String getPrivateKey() {             return privateKey;         }           public void setPrivateKey(String privateKey) {             this.privateKey = privateKey;         }           @Override         public String toString() {             return "SecretKey{" +                     "publicKey='" + publicKey + '\'' +                     ", privateKey='" + privateKey + '\'' +                     '}';         }     }       private static void writeToFile(String path, byte[] key) throws IOException {         File f = new File(path);         f.getParentFile().mkdirs();           try(FileOutputStream fos = new FileOutputStream(f)) {             fos.write(key);             fos.flush();         }     }       public static void main(String[] args) throws NoSuchAlgorithmException, NoSuchPaddingException, IOException, BadPaddingException, IllegalBlockSizeException, InvalidKeyException, InvalidKeySpecException {         SecretKey secretKey = generateSecretKey(2048);         System.out.println(secretKey);         String enStr = encryptData("你好測試測試", secretKey.getPrivateKey());         System.out.println(enStr);         String deStr = decryptData(enStr, secretKey.getPublicKey());         System.out.println(deStr);         enStr = encryptData("你好測試測試hello", secretKey.getPrivateKey());         System.out.println(enStr);         deStr = decryptData(enStr, secretKey.getPublicKey());         System.out.println(deStr);     }   }

3. RSA加解密原理以及三種填充模式

如果需要理解RSA的加密原理,需要理解以下理論:

​ 等同於求一元二次方程 23 * d + 192 * y = 1

​ 可以求得其中一解為(d=167,y=-20)

​ 至此就完成了所有的計算

​ 對於上述例子的到公鑰(221,23)和私鑰(221,167)

在上述的計算過程中一共用到了

上面用到的數中只有公鑰部分是公開的,即(221,23)。那麼我們是否可以通過公鑰來推到出私鑰部分,即已知n和e,推到出d?

(1)ed 1(mod (n)),只有知道 (n)才能解出d

(2) (n)= (p) (q)= (p-1) (q-1),只有知道p和q才能得到 (n)

(3)n=p q,就需要對n進行因式分解

那麼如果可以對n因式分解就可以求出d,也就意味著私匙被破解

那麼RSA加密的可靠性就在於對n因式分解的難度,而現在對一個整數n做因式分解並沒有巧妙的演算法,只有通過暴力破解計算。在實際應用中的n取值通常在1024位以上,而公開已知的可因式分解的最大數為768位。所以現階段來說RSA加密是可靠的。

現在我們就可以進行加密和解密了

我們使用上面生成的公鑰(221,23)來加密。如果我們需要加密的信息是m( m必須為整數並且m要小於n ),m取56,可以用以下公式求出加密串c:

c (mod n)

10 (mod 221)

可以求出加密後的結果c為10

密鑰為(221,167),加密結果c=10,可以使用以下公式求出被加密的信息

m (mod n) 即加密結果的d次方除以n的余數為m

56 (mod 221)

RSA加密屬於塊加密演算法,總是在一個固定長度的塊上進行操作。如果被加密的字元串過長,則需要對字元串進行切割,如果字元串過短則需要進行填充。

以下主介紹一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式

此填充模式是最常用的填充模式,在此填充模式下輸入的長度受加密鑰的長度限制,輸入的最大長度為加密鑰的位數k-11。如果公鑰的長度為1024位即128位元組,那麼輸入的長度最多為128-11=117位元組。如果長度小於117就需要填充。如果輸入T的長度為55位元組,填充後的塊為EM,則EM格式如下:

EM= 0x00 || BT || PS || 0x00 || T

在此填充模式下,輸入的長度最多和RSA公鑰長度一樣長,如果小於公鑰長度則會在前面填充0x00。如果公鑰長度是128位元組,輸入T的長度為55位元組,填充後的塊為EM,則EM格式如下:

EM=P || T

參考:
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
https://my.oschina.net/3pgp/blog/749195

4. 用RSA對下列數據實現加密和解密:

分類: 電腦/網路 >> 程序設計 >> 其他編程語言
問題描述:

用RSA對下列數據實現加密和解密:

a. p=3,q=11,e=7;M=5

b. p=7,q=11,e=3;M=9

解析:

拜託:老大,你的家庭作業也來問?

你自己學吧:下面是課文^

RSA加密演算法

該演算法於1977年由美國麻省理工學院MIT(Massachusetts Institute of Technology)的Ronal Rivest,Adi Shamir和Len Adleman三位年輕教授提出,並以三人的姓氏Rivest,Shamir和Adlernan命名為RSA演算法。該演算法利用了數論領域的一個事實,那就是雖然把兩個大質數相乘生成一個合數是件十分容易的事情,但要把一個合數分解為兩個質數卻十分困難。合數分解問題目前仍然是數學領域尚未解決的一大難題,至今沒有任何高效的分解方法。與Diffie-Hellman演算法相比,RSA演算法具有明顯的優越性,因為它無須收發雙方同時參與加密過程,且非常適合於電子函件系統的加密。

RSA演算法可以表述如下:

(1) 密鑰配製。假設m是想要傳送的報文,現任選兩個很大的質數p與q,使得:

(12-1);

選擇正整數e,使得e與(p-1)(q-1)互質;這里(p-1)(q-1)表示二者相乘。再利用輾轉相除法,求得d,使得:

(12-2);

其中x mod y是整數求余運算,其結果是x整除以y後剩餘的余數,如5 mod 3 = 2。

這樣得:

(e,n),是用於加密的公共密鑰,可以公開出去;以及

(d,n),是用於解密的專用鑰匙,必須保密。

(2) 加密過程。使用(e,n)對明文m進行加密,演算法為:

(12-3);

這里的c即是m加密後的密文。

(3) 解密過程。使用(d,n)對密文c進行解密,演算法為:

(12-4);

求得的m即為對應於密文c的明文。

RSA演算法實現起來十分簡捷,據說英國的一位程序員只塌仔用了3行Perl程序便實現了加密和解密運算。

RSA演算法建立在正整數求余運算基礎之上,同時還保持了指數運算的性質,這一點我們不難證明。例如:

(12-5);

(12-6)。

RSA公共密鑰加密演算法的核心是歐拉(Euler)函數ψ。對於正整數n,ψ(n)定義為小於n且與n互質的正整數的個數。例如ψ(6) = 2,這是因為小於6且與6互質的數有1和5共兩個數;再如ψ(7) = 6,這是因為互質數有1,2,3,5,6共6個。

歐拉在公元前300多年就發現了ψ函數的一個十分有趣的性質,那就是對於任意小於n且與n互質的正整數m,總有mψ(n) mod n = 1。例如,5ψ(6) mod 6 = 52 mod 6= 25 mod 6 =1。也就是說,在對n求余的運算下,ψ(n)指數具有周期性。

當n很小時,計算ψ(n)並不難,使用窮舉法即可求出;但當n很大時,計算ψ(n)就十分困難了,其運算量與判斷n是否為質數的情況相當。不過在特殊情況下,利用ψ函數的兩個性質,可以極大地減少運算量。

性質1:如果p是質數,則ψ(p) = (p-1)。

性質2:如果p與q均為質數,則ψ(p·q) = ψ(p)·ψ(q) = (p-1)(q-1)。

RSA演算法正是注意到這兩條性質來設計公共密鑰加密系統的,p與q的乘積n可以作為公共密鑰公布出來,而n的因子p和q則包含在專用密鑰中,可以用來解密。如果解密需要用到ψ(n),衡桐收信方由於知道因子p和q,可以方便地算出ψ(n) = (p-咐衫坦1)(q-1)。如果竊聽者竊得了n,但由於不知道它的因子p與q,則很難求出ψ(n)。這時,竊聽者要麼強行算出ψ(n),要麼對n進行因數分解求得p與q。然而,我們知道,在大數范圍內作合數分解是十分困難的,因此竊密者很難成功。

有了關於ψ函數的認識,我們再來分析RSA演算法的工作原理:

(1) 密鑰配製。設m是要加密的信息,任選兩個大質數p與q,使得 ;選擇正整數e,使得e與ψ(n) = (p-1)(q-1)互質。

利用輾轉相除法,計算d,使得ed mod ψ(n) = ,即ed = kψ(n) +1,其中k為某一正整數。

公共密鑰為(e,n),其中沒有包含任何有關n的因子p和q的信息。

專用密鑰為(d,n),其中d隱含有因子p和q的信息。

(2) 加密過程。使用公式(12-3)對明文m進行加密,得密文c。

(3) 解密過程。使用(d,n)對密文c進行解密,計算過程為:

cd mod n = (me mod n)d mod n

= med mod n

= m(kψ(n) + 1) mod n

= (mkψ(n) mod n)·(m mod n)

= m

m即為從密文c中恢復出來的明文。

例如,假設我們需要加密的明文代碼信息為m = 14,則:

選擇e = 3,p = 5,q = 11;

計算出n = p·q = 55,(p-1)(q-1) = 40,d = 27;

可以驗證:(e·d) mod (p-1)(q-1) = 81 mod 40 = 1;

加密:c = me mod n = 143 mod 55 = 49;

解密:m = cd mod n = 4927 mod 55 = 14。

關於RSA演算法,還有幾點需要進一步說明:

(1) 之所以要求e與(p-1)(q-1)互質,是為了保證 ed mod (p-1)(q-1)有解。

(2) 實際操作時,通常先選定e,再找出並確定質數p和q,使得計算出d後它們能滿足公式(12-3)。常用的e有3和65537,這兩個數都是費馬序列中的數。費馬序列是以17世紀法國數學家費馬命名的序列。

(3) 破密者主要通過將n分解成p·q的辦法來解密,不過目前還沒有辦法證明這是唯一的辦法,也可能有更有效的方法,因為因數分解問題畢竟是一個不斷發展的領域,自從RSA演算法發明以來,人們已經發現了不少有效的因數分解方法,在一定程度上降低了破譯RSA演算法的難度,但至今還沒有出現動搖RSA演算法根基的方法。

(4) 在RSA演算法中,n的長度是控制該演算法可靠性的重要因素。目前129位、甚至155位的RSA加密勉強可解,但目前大多數加密程序均採用231、308甚至616位的RSA演算法,因此RSA加密還是相當安全的。

據專家測算,攻破512位密鑰RSA演算法大約需要8個月時間;而一個768位密鑰RSA演算法在2004年之前無法攻破。現在,在技術上還無法預測攻破具有2048位密鑰的RSA加密演算法需要多少時間。美國Lotus公司懸賞1億美元,獎勵能破譯其Domino產品中1024位密鑰的RSA演算法的人。從這個意義上說,遵照SET協議開發的電子商務系統是絕對安全的。

5. RSA演算法加密

RSA加密演算法是一種典型的非對稱加密演算法,它基於大數的因式分解數學難題,它也是應用最廣泛的非對稱加密演算法,於1978年由美國麻省理工學院(MIT)的三位學著:Ron Rivest、Adi Shamir 和 Leonard Adleman 共同提出。

它的原理較為簡單,假設有消息發送方A和消息接收方B,通過下面的幾個步驟,就可以完成消息的加密傳遞:
消息發送方A在本地構建密鑰對,公鑰和私鑰;
消息發送方A將產生的公鑰發送給消息接收方B;
B向A發送數據時,通過公鑰進行加密,A接收到數據後通過私鑰進行解密,完成一次通信;
反之,A向B發送數據時,通過私鑰對數據進行加密,B接收到數據後通過公鑰進行解密。
由於公鑰是消息發送方A暴露給消息接收方B的,所以這種方式也存在一定的安全隱患,如果公鑰在數據傳輸過程中泄漏,則A通過私鑰加密的數據就可能被解密。
如果要建立更安全的加密消息傳遞模型,需要消息發送方和消息接收方各構建一套密鑰對,並分別將各自的公鑰暴露給對方,在進行消息傳遞時,A通過B的公鑰對數據加密,B接收到消息通過B的私鑰進行解密,反之,B通過A的公鑰進行加密,A接收到消息後通過A的私鑰進行解密。
當然,這種方式可能存在數據傳遞被模擬的隱患,但可以通過數字簽名等技術進行安全性的進一步提升。由於存在多次的非對稱加解密,這種方式帶來的效率問題也更加嚴重。

6. 密碼學基礎(三):非對稱加密(RSA演算法原理)

加密和解密使用的是兩個不同的秘鑰,這種演算法叫做非對稱加密。非對稱加密又稱為公鑰加密,RSA只是公鑰加密的一種。

現實生活中有簽名,互聯網中也存在簽名。簽名的作用有兩個,一個是身份驗證,一個是數據完整性驗證。數字簽名通過摘要演算法來確保接收到的數據沒有被篡改,再通過簽名者的私鑰加密,只能使用對應的公鑰解密,以此來保證身份的一致性。

數字證書是將個人信息和數字簽名放到一起,經由CA機構的私鑰加密之後生成。當然,不經過CA機構,由自己完成簽名的證書稱為自簽名證書。CA機構作為互聯網密碼體系中的基礎機構,擁有相當高級的安全防範能力,所有的證書體系中的基本假設或者前提就是CA機構的私鑰不被竊取,一旦 CA J機構出事,整個信息鏈將不再安全。

CA證書的生成過程如下:

證書參與信息傳遞完成加密和解密的過程如下:

互質關系:互質是公約數只有1的兩個整數,1和1互質,13和13就不互質了。
歐拉函數:表示任意給定正整數 n,在小於等於n的正整數之中,有多少個與 n 構成互質關系,其表達式為:

其中,若P為質數,則其表達式可以簡寫為:

情況一:φ(1)=1
1和任何數都互質,所以φ(1)=1;

情況二:n 是質數, φ(n)=n-1
因為 n 是質數,所以和小於自己的所有數都是互質關系,所以φ(n)=n-1;

情況三:如果 n 是質數的某一個次方,即 n = p^k ( p 為質數,k 為大於等於1的整數),則φ(n)=(p-1)p^(k-1)
因為 p 為質數,所以除了 p 的倍數之外,小於 n 的所有數都是 n 的質數;

情況四:如果 n 可以分解成兩個互質的整數之積,n = p1 × p2,則φ(n) = φ(p1p2) = φ(p1)φ(p2)

情況五:基於情況四,如果 p1 和 p2 都是質數,且 n=p1 × p2,則φ(n) = φ(p1p2) = φ(p1)φ(p2)=(p1-1)(p2-1)

而 RSA 演算法的基本原理就是歐拉函數中的第五種情況,即: φ(n)=(p1-1)(p2-1);

如果兩個正整數 a 和 n 互質,那麼一定可以找到整數 b,使得 ab-1 被 n 整除,或者說ab被n除的余數是1。這時,b就叫做a的「模反元素」。歐拉定理可以用來證明模反元素必然存在。

可以看到,a的 φ(n)-1 次方,就是a對模數n的模反元素。

n=p x q = 3233,3233寫成二進制是110010100001,一共有12位,所以這個密鑰就是12位。

在實際使用中,一般場景下選擇1024位長度的數字,更高安全要求的場景下,選擇2048位的數字,這里作為演示,選取p=61和q=53;

因為n、p、q都為質數,所以φ(n) = (p-1)(q-1)=60×52= 3120

注意,這里是和φ(n) 互互質而不是n!假設選擇的值是17,即 e=17;

模反元素就是指有一個整數 d,可以使得 ed 被 φ(n) 除的余數為1。表示為:(ed-1)=φ(n) y --> 17d=3120y+1,算出一組解為(2753,15),即 d=2753,y=-15,也就是(17 2753-1)/3120=15。

注意,這里不能選擇3119,否則公私鑰相同??

公鑰:(n,e)=(3233,2753)
私鑰:(n,d)=(3233,17)

公鑰是公開的,也就是說m=p*q=3233是公開的,那麼怎麼求e被?e是通過模反函數求得,17d=3120y+1,e是公開的等於17,這時候想要求d就要知道3120,也就是φ(n),也就是φ(3233),說白了,3233是公開的,你能對3233進行因數分解,你就能知道d,也就能破解私鑰。

正常情況下,3233我們可以因數分解為61*53,但是對於很大的數字,人類只能通過枚舉的方法來因數分解,所以RSA安全性的本質就是:對極大整數做因數分解的難度決定了RSA演算法的可靠性。換言之,對一極大整數做因數分解愈困難,RSA演算法愈可靠。

人類已經分解的最大整數是:

這個人類已經分解的最大整數為232個十進制位,768個二進制位,比它更大的因數分解,還沒有被報道過,因此目前被破解的最長RSA密鑰就是768位。所以實際使用中的1024位秘鑰基本安全,2048位秘鑰絕對安全。

網上有個段子:

已經得出公私鑰的組成:
公鑰:(n,e)=(3233,2753)
私鑰:(n,d)=(3233,17)
加密的過程就是

解密過程如下:

其中 m 是要被加密的數字,c 是加密之後輸出的結果,且 m < n ,其中解密過程一定成立可以證明的,這里省略證明過程。

總而言之,RSA的加密就是使用模反函數對數字進行加密和求解過程,在實際使用中因為 m < n必須成立,所以就有兩種加密方法:

對稱加密存在雖然快速,但是存在致命的缺點就是秘鑰需要傳遞。非對稱加密雖然不需要傳遞秘鑰就可以完成加密和解密,但是其致命缺點是速度不夠快,不能用於高頻率,高容量的加密場景。所以才有了兩者的互補關系,在傳遞對稱加密的秘鑰時採用非對稱加密,完成秘鑰傳送之後採用對稱加密,如此就可以完美互補。

7. RSA加解密演算與暴力破解12位

大家都知道RSA是非對稱加密,解密方生成公鑰和密鑰,公鑰公開給加密方加密,密鑰留給自己解密是不公開的。

1.隨機選兩個質數,我們用p、q來代替 (質數的數值越大位數就越多可靠性就越高)
假設我們取了47與59
p = 47
q = 59

2.計算這兩個質數的乘積,用n代替
n = 47 x 59 = 2773

n的長度就是密鑰長度。2773寫成二進制是101011010101,一共有12位,所以這慶陪寬個密鑰就是12位。實際應用中,RSA密鑰一譽亮般是1024位,重要場合則為2048位。

3.計算n的歐拉函數φ(n)
歐拉函數公式:φ(n) = (p-1)(q-1)
代入:φ(2773) = (47 - 1) x (59 - 1) = 46 x 58 = 2668

4.隨機選擇一個整數e,條件是1< e < φ(n),且e與φ(n) 互質
那麼我們就在1到2668之間,隨機選擇了17
e = 17

5.計算e對於φ(n)的模反元素d
模反元素公式: ax ≡ 1 (mod b)
這是歐拉定理推導出來的,若a、b互質則a乘以一個整數除以b的余數是1。這個整數就是a與b的模反元素。
該公式可以寫成:ax - b = 1 則 x = (1 + b) / a

代入: d = (1 + φ(n)) / e = (1 + 2668) / 17 = 157
是一個整數,但很多情況下結果不一定是整數,我們為了計算的方便,在公式里追加一個整數k: x = (1 + kb) / a,加上k來乘以b並不影響余數1的結果。

重新代入: d = (1 + kφ(n)) / e = (1 + k x 2668) / 23
即得到一個線性方程
求解的坐標點(k,d)有很多 (1,157)、(18,2825)、(35,5493) ....
我們隨機出一個坐標點: (1,157)
即:d = 157

6.將n和e封裝成公鑰,n和d封裝成私鑰
即公開的公鑰為:n = 2773,e = 17
保密的私鑰為:n = 2773,d = 157
就是這樣子12位RSA的公私鑰生成好了!

假設我們加密一個字元"A"
再用數值表示,一般用Unicode或ASCII碼表示
轉ASCII碼十進制為65,我們用m來代替明文,c來代替密文
m = 65
RSA加密公式:m e ≡ c (mod n)
RSA加密公式由歐拉函數公式與反模元素公式推導出來

代入:c = 65 17 % 2773 = 601
這樣密文就出來了!

RSA解密公式:c d ≡ m (mod n)
RSA解密公式由歐拉函數公式與反模元素公式推導出來

代入:m = 601 157 % 2773 = 65
這樣明文就出來了!

因為p、q、n、φ(n)、e、d這六個數字之中,公鑰用到了兩個(n和e),其餘四個數字都是不公開的。其中最關鍵的是d,因為n和d組成了私鑰,一旦d泄漏,就等於私鑰泄漏

由此可見推導出d就必須因數分解出p和q
公鑰裡面有n = 2773
那麼暴力破解的方法就是把2773因數分解出兩個相乘的質數。

最簡單的方法就是遍歷窮舉質數的乘積:
<pre>
var distNum = 2773;
var numList = [];
var p = 1;
var q = 1;
for(var i = 1; i < 100; i++) {
var isGetResult = false; // 是亂脊否找到結果
var isUseful = true; // 是否質數
var isHave = false; // 是否在質數列表中存在
for(var j = 0; j < numList.length; j++) {
if(numList[j] == i) {
isHave = true;
break;
}
}
for(var k = 2; k < i; k++ ) {
if(i % k == 0) {
isUseful = false;
break;
}
}
if(!isHave && isUseful) {
numList.push(i); // 加入質數列表
// 匹配乘積
for(var n = 0; n < numList.length; n++) {
if(i != numList[n] && i * numList[n] == distNum) {
p = i;
q = numList[n];
isGetResult = true;
break;
}
}
}
console.log(JSON.stringify(numList));
if(isGetResult) {
console.log('p = ' + p);
console.log('q = ' + q);
break;
}
}
</pre>

運行結果:

RSA加密的可靠性是基於因數分解的計算難度,但隨著量子計算、雲計算的發達,現在用的1024位RSA甚至2048位RSA都面臨著挑戰,據說40個量子比特位相當於一台超級計算機。

您的意見是我改善的東西,歡迎評論提建議,如果對您有幫助,請點個贊,謝謝~~
菲麥前端專題,匯聚前端好文,邀您關注!

8. 如何使用javascript進行RSA/ECB/PKCS1Padding演算法加密

javascript rsa加密/java使用Cipher.getInstance("RSA/ECB/PKCS1Padding")解密
1)伺服器端獲得生成密鑰對;
2)javascript使用公鑰加密;
3)java獲得密文使用私鑰解密;

9. 對於加密的總結(AES,RSA)

跟第三方聯調的時候會碰到各種加密演算法,所以總結一下。

AES不是將拿到的明文一次性加密,而是分組加密,就是先將明文切分成長度相等的塊,每塊大小128bit,再對每一小塊進行加密。那麼問題就來了,並不是所有的原始明文串能被等分成128bit,例如原串大小200bit,那麼第二個塊只有72bit,所以就需要對第二個塊進行填充處理,讓第二個塊的大小達到128bit。常見的填充模式有

不進行填充,要求原始加密串大小必須是128bit的整數倍;

假設塊大小8位元組,如果這個塊跟8位元組還差n個位元組,那麼就在原始塊填充n,直到滿8位元組。例:塊{1,2,3},跟8位元組差了5個位元組,那麼補全後的結果{1,2,3,5,5,5,5,5}後面是五個5,塊{1,2,3,..7}跟8位元組差了1個位元組,那麼補全後就是{1,2,3,...,7,1},就是補了一個1。

如果恰好8位元組又選擇了PKCS5Padding填充方式呢?塊{1,2,3...8}填充後變成{1,2,3...8,8...8},原串後面被補了8個8,這樣做的原因是方便解密,只需要看最後一位就能算出原塊的大小是多少。

跟PKCS5Padding的填充方式一樣,不同的是,PKCS5Padding只是對8位元組的進行填充,PKCS7Padding可以對1~256位元組大小的block進行填充。openssl里aes的默認填充方式就是PKCS7Padding

AES有多種加密模式,包括:ECB,CBC,CTR,OCF,CFB,最常見的還是ECB和CBC模式。

最簡單的一種加密模式,每個塊進行獨立加密,塊與塊之間加密互不影響,這樣就能並行,效率高。
雖然這樣加密很簡單,但是不安全,如果兩個塊的明文一模一樣,那麼加密出來的東西也一模一樣。

openssl的相關函數:

CBC模式中引入了一個新的概念,初始向量iv。iv的作用就是為了防止同樣的明文塊被加密成同樣的內容。原理是第一個明文塊跟初始向量做異或後加密,第二個塊跟第一個密文塊做異或再加密,依次類推,避免了同樣的塊被加密成同樣的內容。

openssl相關函數:

敲黑板!! 所以跟第三方對接的時候,如果對面說他們用aes加密,務必對他們發起靈魂三問:

簽名的作用是讓接受方驗證你傳過去的數據沒有被篡改;加密的作用是保證數據不被竊取。

原理:你有一個需要被驗簽的原串A。

步驟一:選擇hash演算法將A進行hash得到hash_a;

步驟二:將hash_a進行加密,得到加密值encrypt_a;

步驟三:將原串A和加密的encrypt_a發給第三方,第三方進行驗簽。第三方先解密encrypt_a,得到一個hash值hash_a1,然後對原串A使用同樣的hash演算法進行hash,得到的即為加密前的hash_a,如果hash_a = hash_a1, 那麼驗簽成功。

rsa使用私鑰對信息加密來做簽名,使用公鑰解密去驗簽。
openssl相關函數:

注意:兩個函數中的m,是原串hash後的值,type表示生成m的演算法,例如NID_sha256表示使用sha256對原串進行的hash,返回1為簽名成功或者驗簽成功,-1位為失敗。

再次敲黑板!! 所以如果第三方說使用rsa驗簽,要讓對方告知他們的hash演算法。

首先明確,私鑰加密不等於簽名。加密的時候,使用使用公鑰加密,第三方使用你的私鑰進行解密。
openssl里公鑰加密函數為RSA_public_encrypt,私鑰解密函數為RSA_private_decrypt,具體的可以自己去查看下官方文檔。

rsa也涉及到了填充方式,所以對接的時候也要問清楚

在使用公鑰進行加密時,會發現每次加密出的結果都不一樣,但使用私鑰加密時,每次的結果都一樣,網上查了一圈,說是因為填充方式的原因。

官方文檔說明:

那麼為什麼一定要使用私鑰做簽名,公鑰做加密,而不是公鑰做簽名,私鑰做加密呢?
舉個栗子:

10. RSA 加密解密

RSA 是一種非對稱加密演算法,很多表單的密碼都採用 RSA 加密。
使用 RSA 一般需要先產生一對公鑰和私鑰,當採用公鑰叢橘畢伍寬加密時,使用私鑰解密;採用私鑰加密時,使用公鑰解密。

執行結果如下:

在實際應用中,我們可以先執行 genKeyPair 先生成一對密鑰,將該對密鑰保存在配置文件中,然後在加密時,調用 encrypt(str, publicKey) 方法使用公鑰對文本進行加密,在解密時,調用 decrypt(strEn, privateKey) 方法使用私鑰對文本進行解密,滲芹即可。

熱點內容
公司的電腦要什麼配置 發布:2023-06-01 03:26:11 瀏覽:935
10萬元的車應有哪些配置和功能 發布:2023-06-01 03:23:12 瀏覽:457
強大演算法 發布:2023-06-01 03:21:06 瀏覽:613
壓縮文件去除密碼 發布:2023-06-01 03:20:16 瀏覽:507
安卓設置伺服器地址 發布:2023-06-01 03:16:21 瀏覽:255
伺服器為什麼只讀模式 發布:2023-06-01 03:15:43 瀏覽:20
我的世界如何刪除伺服器地皮 發布:2023-06-01 03:12:05 瀏覽:676
資料庫間連 發布:2023-06-01 03:11:58 瀏覽:461
中餐廳第五季ftp 發布:2023-06-01 03:01:40 瀏覽:387
最難破譯的密碼叫什麼 發布:2023-06-01 03:01:25 瀏覽:33