哈希演算法及其拓展

  • 2019 年 10 月 26 日
  • 筆記

本篇是iOS逆向開發的遞進篇-關於哈希演算法、數字簽名及對稱加密等，下面我們著重講解此內容，希望對大家有所幫助！！！

 

 一、哈希

1.1 基本內容

哈希表也稱為散列表（Hash table），是根據關鍵碼值（key，value），直接進行訪問的數據結構。通過把關鍵碼映射到表中的一個位置來進行訪問記錄，用來加快查找速度。映射函數也稱之為散列函數，存放記錄數組稱為散列表。

假設沒有記憶體限制，直接可以將鍵作為數組的索引，那麼所有的查找僅僅需要一次即可完成。但是這種理想的情況也不會一直出現，因為牽扯到記憶體問題。從另一個角度來說，如果沒有時間來限制，我們也可以使用無序數組並進行順序查找，這樣也會使用較少的記憶體。

使用哈希查找演算法分為兩個步驟：

  1. 使用Hash函數將被要查找的鍵轉化為數組中的一個索引。理想情況下，不同的鍵都可以轉為不同的索引值。但這僅僅是理想情況下，在實際的開發運算中，我們還是要處理兩個或者多個鍵值散列到同個索引值的情況。
  2. 要處理碰撞衝突的過程。

目前本人部落格關於講述哈希思想查找元素的部落格有：https://www.cnblogs.com/guohai-stronger/p/11506990.html，還會持續更新此類演算法思想有關的題目。

 

1.2 哈希函數的兩種解決碰撞的方式

1.2.1 拉鏈法（separate chaining）

 拉鏈法簡單說就是鏈表+數組。將鍵來通過Hash函數映射為大小為M的數組下標索引，數組的每個元素指向鏈表，鏈表的每個節點存儲著哈希出來的索引值為節點下標的鍵對值。

舉一個例子：

給定一組數據為{45，27，55，24，10，53,32，14，23，01，42，20}，假設散列表長度為13，用拉鏈法解決構造的哈希表。拉鏈法表示如下：

上面就是拉鏈法的圖示，下面我們講解拉鏈法的程式碼實現：

public class SeparateChainingHashST<Key, Value> {      //SequetialSearchST      private int N;//鍵值對總數      private int M;//散列表的大小      private SequentialSearchST<Key, Value>[] st;//存放鏈表對象的數組      public SeparateChainingHashST() {//默認的構造函數會使用997條鏈表          this(997);      }      public SeparateChainingHashST(int M) {          //創建M條鏈表          this.M = M;          //創造一個(SequentialSearchST<Key, Value>[])類型的,長度為M的數組          st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];          for(int i = 0; i < M; i++) {              //為每一個數組元素申請一個空間              st[i] = new SequentialSearchST();          }      }      private int hash(Key key) {          return (key.hashCode() & 0x7fffffff) % M;      }      public Value get(Key key) {          return (Value)st[hash(key)].get(key);      }      public void put(Key key, Value val) {          st[hash(key)].put(key, val);      }      public void delete(Key key) {          st[hash(key)].delete(key);      }      public Iterable<Key> keys(){          Queue<Key> queue = new Queue<Key>();          for(int i = 0; i < M; i++) {              System.out.println("第" + i +"個元素的鏈表");              for(Key key : st[i].keys()) {                  queue.enqueue(key);                  System.out.print(key + " " + get(key) + " ,");              }              System.out.println();          }          return queue;      }      public static void main(String[] args) {          SeparateChainingHashST<String, Integer> st = new SeparateChainingHashST<String, Integer>(5);          for (int i = 0; i < 13; i++) {              String key = StdIn.readString();              st.put(key, i);          }          for (String s : st.keys())              StdOut.println(s + " " + st.get(s));          st.delete("M");          StdOut.println("*************************************");          for (String s : st.keys()) {               StdOut.println(s + " " + st.get(s));          }      }  }

上面就是拉鏈表的基本內容，如果想進一步了解，可以查看數據結構相關書籍。

 

1.2.2 開放定址法

開放定址法包括線性探測法和平方探測法。

開放定址法是由關鍵碼得到的哈希地址一旦發生了衝突，假如已經存在了元素，就會去尋找下一個空的哈希地址，只需要哈希表足夠的大，空的哈希地址總能找到，並將元素存入進去。

 

1.3 哈希的特點

  • 演算法是公開的
  • 對相同的數據運算，得到的結果是一樣的
  • 對不同的數據運算，如用MD5得到的結果默認為128位，32個字元（16進位）
  • 這玩意沒辦法進行逆運算
  • 資訊摘要，資訊的指紋，都是用來數據識別的

 

1.4 哈希用途加密方式

1.4.1 用戶密碼的加密

1.4.1.1 直接使用MD5加密
//密碼      NSString * pwd = @"123456";        //MD5 直接加密 e10adc3949ba59abbe56e057f20f883e      //不足：不夠安全了。可以反查詢！    pwd = pwd.md5String;

我們也可以通過終端，通過輸入md5 -s “內容”，如下得到md5，32個字元

1.4.1.2 加鹽
//足夠複雜！  static NSString * salt = @"(*(*(DS*YFHIUYF(*&DSFHUS(*AD&";  pwd = [pwd stringByAppendingString:salt].md5String;

運用加鹽方式弊端： 鹽都是是固定的，把它寫死在程式裡面，一旦泄露就會不安全了！

1.4.1.3 HMAC
/** HMAC       *  使用一個密鑰加密，並且做兩次散列！       *  在實際開發中，密鑰（KEY）來自於伺服器（動態的）！       *  一個帳號，對應一個KEY，而且還可以跟新！       */      pwd = [pwd hmacMD5StringWithKey:@"hank"];

在我們日常開發中，如果一個是有非常好的後台開發素質，會在登錄註冊介面返回來一個時間戳，對於這個時間戳可以很好地運用到HMAC中

通過上面：

假如將時間戳運用到裡面中，和HMAC哈希值拼接此時的時間戳（直到分，不到秒）發給伺服器，然後伺服器根據客戶端發來的字元，進行解析；如果此時這個過程到了下一分鐘（201812032050 58s發，伺服器收到已經201812032051 20s ），伺服器會做一個分鐘-1進行驗證

 

1.4.2 搜索引擎

我們在搜索幾個詞語時，假如在資料庫檢索“國孩”，“真的”，“很帥”，對於我們搜索其中的任何一個詞，都可以通過哈希檢索出來，哈希內部是怎麼做到的呢？

下面是三個詞在md5下的32位字元值：

 哈希通過將“國孩”，“真的”，“很帥”的哈希值進行想加，得到了也是一個32位字元串

 

1.4.3 版權

對於很多源文件上傳至某個平台上時，該平台會給源文件設置唯一一個哈希值，如果有盜版上傳至該平台，會被拒絕

 

二、數字簽名

數字簽名是對原始數據的HASH值，用非對稱RSA加密

明文數據和HASH值如果通過直接傳遞就會有篡改的風險，因此我們要對數據加密。但是明文數據是比較大的，不太適合運用RSA非對稱加密，那麼數據的HASH值是比較小，這個數據如果用來校驗，這樣就完全可以使用RSA進行加密。當我們在數據傳遞的時候，可以通過將明文數據+RSA加密的校驗數據一起發送給對方，RSA加密的校驗數據，稱之為簽名。

 

下面我們來講述一下數字簽名驗證的過程：當對方拿到數據之後，如何驗證呢？

  • 首先傳遞數據時會將原始的數據和數字簽名共同發送
  • 對方拿到數據之後，先進行校驗，拿到了原始數據，經過同樣的HASH演算法得到數據的HASH值
  • 緊接著通過非對稱加密，將數字簽名中的校驗HASH解密出來
  • 對比兩個HASH值是否是一致的，這樣就可以很好地判斷數據是否被人篡改啦

上面是過程，下面有一份圖解：

 

三、對稱加密

對稱加密就是明文通過密鑰得到密文，然後密文通過密鑰解密得到明文。

常見演算法：

  • DES：數據加密的標準（用的比較少）
  • 3DES：（數據三次DES加密，強度增強了）
  • AES：（高級密碼標準）–鑰匙串訪問用到了

應用模式如下圖解：

總結，上面就是關於哈希的基本內容和拓展，希望對大家對關於理解哈希有更深的感觸！！！下一篇我們將繼續講述iOS逆向開發的另一篇—-應用簽名和重簽名。

 

VirMach 便宜 VPS

QNews

QNews