RSA加密原理&密碼學&HASH

密碼學是研究編制密碼和破譯密碼的技術科學。研究密碼變化的客觀規律，應用於編制密碼以保守通信秘密的，稱為編碼學；應用於破譯密碼以獲取通信情報的，稱為破譯學，總稱密碼學。

密碼學的起源可追溯到2000年前。而當今的密碼學是以數學為基礎的。

密碼學溯源

密碼學的歷史大致可以追溯到兩千年前，相傳古羅馬名將凱撒大帝為了防止敵方截獲情報，用密碼傳送情報。凱撒的做法很簡單，就是對二十幾個羅馬字母建立一張對應表。這樣，如果不知道密碼本，即使截獲一段信息也看不懂。

從凱撒大帝時代到上世紀70年代這段很長的時間裡，密碼學的發展非常的緩慢，因為設計者基本上靠經驗。沒有運用數學原理。

重要節點:

• 在 1976 年以前，所有的加密方法都是同一種模式：加密、解密使用同一種算法。在交互數據的時候，彼此通信的雙方就必須將規則告訴對方，否則沒法解密。那麼加密和解密的規則（簡稱密鑰），它保護就顯得尤其重要。傳遞密鑰就成為了最大的隱患。這種加密方式被成為 對稱加密算法 （ symmetric encryption algorithm ）
• 1976 年，兩位美國計算機學家 迪菲（ W.Diffie ）、赫爾曼（ M.Hellman ） 提出了一種嶄新構思，可以在不直接傳遞密鑰的情況下，完成密鑰交換。這被稱為“ 迪菲赫爾曼密鑰交換 ”算法。開創了密碼學研究的新方向.
• 1977 年三位麻省理工學院的數學家 羅納德·李維斯特（ Ron Rivest ）、阿迪·薩莫爾（
  Adi Shamir ）和倫納德·阿德曼（ Leonard Adleman ）一起設計了一種算法，可以實現非對稱加密。這個算法用他們三個人的名字命名，叫做 RSA 算法。

RSA 加密算法

RSA

上世紀 70 年代產生的一種加密算法。其加密方式比較特殊，需要兩個密鑰：公開密鑰簡稱公鑰（ publickey ）和私有密鑰簡稱私鑰（ privatekey ）。公鑰加密，私鑰解密；私鑰加密，公鑰解密。這個加密算法就是偉大的 RSA .

這種算法非常可靠，密鑰越長，它就越難破解。根據已經披露的文獻，目前被破解的最長 RSA 密鑰是 768 個二進制位。也就是說，長度超過 768 位的密鑰，還無法破解（至少沒人公開宣佈）。因此可以認為， 1024 位的 RSA 密鑰基本安全， 2048 位的密鑰極其安全。

( 當然 RSA 的缺陷也很容易想到 : 效率相對較低 , 字節長度限制等 . 因此實際應用中我們往往會結合對稱性加密一起使用 , 關鍵內容使用 RSA )

RSA 數學原理

本小節內容瞭解即可

1. 離散對數問題

問: 三的多少次方模 17 等於 12 ?

• 顯然 , 對於離散對數問題 , 其正向計算得到右邊 12 很簡單. 但是反向運算時 , 就無從下手. 只能窮舉 .
• 而且當模數使用質數 17 時 , 結果固定在 1 ~ 17 之間. 而當 17 這個模數足夠大時 , 就算知道採用的是這個算法 , 也知道 17 這個質數和答案 , 想要再計算出來上圖中這個問號值 , 可以想象到其難度和計算量有多大 .

2. 歐拉函數 φ

歐拉函數 :

給定任意正整數 n , 在小於等於 n 的正整數中 , 能與 n 構成互質關係的正整數個數.
複製代碼

計算這個值的方式叫做歐拉函數，使用： φ(n) 表示

• 例 :chestnut::

φ(8) 有 1,3,5,7 即是 φ(8) = 4

φ(7) 有 1,2,3,4,5,6 即是 φ(8) = 6

• 問 :

那麼 φ(56) 是多少 ?

先別急著一個個去數 , 我們來看下 歐拉函數的特點 .

1. 當 n 是質數的時候， φ(n) = n-1
2. 當 n 可以分解成兩個互質的整數之積，如 n = A*B 則 ： φ(A*B)=φ(A)* φ(B)

因此 :

如果 N 是兩個質數 P1 和 P2 的乘積則 φ(N) = φ(P1) * φ(P2) = (P1-1)*(P2-1)

那麼顯然 φ(56) = φ(7) * φ(8) = 4 * 6 = 24

而 φ(63) = φ(7) * φ(9) = (7-1) * (9-1) = 48

3. 歐拉定理

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

小提示: 關於定理 , 不需要我們去證明它 , 只用記住就好.

3.1 費馬小定理

費馬小定理 就是在歐拉定理的基礎上 , 而當 n 為質數時 (φ(n)結果就是n-1 .)

那麼 :

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

4. 公式轉換

• 首先根據歐拉定理

• 
  
• 由於 1 的 k 次方恆等於 1 , 那麼

• 由於 1*m ≡ m , 那麼

• 在接下來第四部之前 , 我們要先提一個概念 : 模反元素

如果兩個正整數 e 和 x 互質，那麼一定可以找到整數 d ，使得 ed-1 被 x 整除。那麼 d 就是 e 對於 x 的 模反元素

那麼換算成公式 就是:

• 轉換一下寫法

注意比較第五步和第三步中紅框部分. 也就是說當 x 等於 Φ(n) 時 :

( 其中 d 是 e 相對於 φ(n) 的模反元素 , 因為 x = Φ(n) 嘛)

注意 : 公式推導第一步時 我們歐拉定理的前提是 m 和 n 互質 , 但是由於模反元素的關係 , 其實只要滿足 m < n 上述結果依然成立.

重頭戲來了 , 用實際場景來看下迪菲赫爾曼密鑰交換過程

原理:

結合我們剛剛第五步之後得出的

因此:

( 其中 d 是 e 相對於 φ(n) 的模反元素 , 因為 x = Φ(n) , 那麼同樣 , e 和 φ(n) 是互質關係 )

大家可以自己去實驗一下 . 例如: m = 3 , n = 15 , φ(n) = 8 , e = 3 , d = 11 .

到了這裡 , 我們就得到了RSA算法的原理 . 那麼我們對應起來介紹一下

RSA算法的原理

• 1、 n 會非常大，長度一般為 1024 個二進制位。（目前人類已經分解的最大整數， 232 個十進制位， 768 個二進制位）
• 2、由於需要求出 φ(n) ，所以根據歐函數特點，最簡單的方式 n 由兩個質數相乘得到: 質數： p1 、 p2 . 那麼 Φ(n) = (p1 -1) * (p2 - 1)
• 3、最終由 φ(n) 得到 e 和 d 。 總共生成 6 個數字： p1、p2、n、φ(n)、e、d
• 其中 n 和 e 組成公鑰 .
• n 和 d 組成私鑰 .
• m 為明文 .
• c 為密文 .

( 除了公鑰用到了 n 和 e 其餘的 4 個數字是不公開的。 )

HASH 算法

HASH 介紹

Hash ，一般翻譯做 “ 散列 ”，也有直接音譯為“ 哈希 ”的，就是把任意長度的輸入通過散列算法變換成固定長度的輸出，該輸出就是散列值。這種轉換是一種壓縮映射，也就是，散列值的空間通常遠小於輸入的空間，不同的輸入可能會散列成相同的輸出，所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數

HASH 特點

• 算法是公開的
• 對相同數據運算,得到的結果是一樣的
• 對不同數據運算,如 MD5 得到的結果默認是 128 位, 32 個字符（ 16 進制標識）
• 這玩意沒法逆運算 ( 因此 HASH 並不用於加解密 )
• 信息摘要，信息“指紋”，是用來做數據識別的

HASH 主要用途

• 用戶密碼的加密
• 搜索引擎 (根據 hash 值來匹配搜索內容 等)
• 版權
• 數字簽名
• 雲盤文件審核 / 同文件識別
• ...等等

HASH 安全性探討

由於相同數據 hash 得到的結果是一樣的 . 那麼市面上大量萬億級 hash 結果記錄數據庫的存在 , 這個不可逆的算法 也另類的變成了可解密的存在.

因此 , 我們使用時經常有以下幾種操作 :

1. 加鹽 (早期比較普遍的做法)
2. 嵌套 hash
3. 動態鹽
4. HMAC (也可以說成動態鹽的一種吧)
5. ... 等等

HMAC 加密方案

HMAC 使用一個密鑰加密 , 並且做了兩次散列 . 在實際開發中 , 密鑰往往來自於服務器下發給客戶端 並且可能是根據賬戶綁定的 . 並需要結合實際業務需求來設定註冊與登錄邏輯 (新設備授權等方式來決定服務器是否可以下發密鑰給客戶端)

看到這可能大家也跟我一樣 都有個疑問 .

疑問

我不管你是如何 嵌套 加鹽 HMAC 等什麼方式去對密碼做處理. 既然你登錄是一個賬號一個加密後的密碼. 我抓包工具抓到就可以直接調用接口實現登錄.

是啊 , 那不就 GG 了?

這就牽扯到接口安全的問題 , 其處理方法有很多種, 例如所有請求用 HTTPS , 並且使用對稱性加密和非對稱性加密結合等等方式對數據進行加密.

當然再安全的加密算法也有被破解的風險. 因此以下這種方式 , 大家可以理解參考一下 , 它能比較有效的解決抓包問題 :

解答

1. 註冊時

• 同樣使用 HMAC 的模式 , 也就是註冊時 , 客戶端把用戶名傳給服務器 .
• 服務器隨機生成一個密鑰返回給客戶端 , 並綁定這個密鑰到用戶表改用戶裡.
• 客戶端拿這個 key 將用戶明文密碼進行 HMAC 散列後發給服務器保存.

1. 登錄時

• 登錄時將用戶 HMAC 之後的 hash 值 加上精確到分的時間戳 ( 時間統一為服務器下發時間 , 相信大家項目也都是使用了服務器時間. ) 然後進行散列.
• 服務器收到請求 , 分別驗證當前時間和前一分鐘時間加上之前存儲的 HMAC 後的密碼進行 hash . 兩次有一次成功即為登錄成功.

思考:

為什麼以上方式可以有效防護到接口被抓包的情況 ?

1. 用戶 HMAC 之後的 hash 值 只有在註冊該賬戶時被傳輸過一次 .
2. 抓到接口中 時間戳加 HMAC 之後的 hash 值進行散列 很難猜出嵌套方式.
3. 使用抓到的接口中的源數據 ( 時間戳加 HMAC 之後的 hash 值 ) 每次都不一樣 , 而且有效期只有最多 1 分 59 秒,最少一分鐘 (有效期可靈活控制) 也就是說抓包人員抓到請求源數據後 , 必須在兩分鐘以內登錄 , 否則就會失效.

HASH 題外話

可能有小夥伴碰到過上傳雲盤的文件被和諧的情況 , 並且改了名字或者後綴名重新傳還是不行. 其實這就是 HASH 的一種運用場景 . 要 理解 HASH 是對二進制數據進行散列 . 那麼改名字和後綴名其文件二進制是不會變化的 .

但是壓縮是可以的 .

也就是說壓縮是會改變內存大小 , 其內部二進制散列之後的結果也會變化 . 同樣 base64也是會改變二進制數據的.