Cryptosystems

發佈日期: 作者:

cryptosystems(密碼學)，依金鑰異同可分為

  • symmetric cryptosystems(對稱式加密系統)
  • asymmetric cryptosystems(非對稱式加密系統)

cryptanalysis(密碼分析)，破解密碼的技術,可分為

  • unconditionally secure(無條件安全)：不管截獲多少密文或任何方法仍然沒有足夠資訊導出明文資料 ex:one-time pad
  • computationally secure(計算安全)：以目前或未來預測之科技,在合理資源設備下,要破解密碼系統要一段很長的時間

Symmetric Cryptosystems

也稱symmetric Encryption(對稱式加密),one-key cryptosystems

好的加密方法特性

  • 提高金鑰強度（例如從DES的56位元提升到AES的128/192/256位元），則可提高加密演算法複雜度，暴力破解難度就會指數級上升
  • 符合the avalanche effect(崩塌效應)，換句話說，明文或鑰匙細微變動會造成密文的重大變化

基本架構

  • KEY數量: 1把
    • 加解密用同一把KEY
  • 參與物件
    • P=明文
    • C=密文
    • key=金鑰
  • 加解密架構
    • C=key(P)
    • P=key(C)

優缺點

優點：速度快　

缺點：管理key不易,只提供保密性與某種程度確認性

加密技巧：

取代Substitution(將字元用符號代替)

  • 　caesar加密法：每個字母用後面第三個取代
  • 　monoalphabetic加密法：每個訊息採用一種對應方式
  • 　playfair：將雙字元明文視為單一元素,再將其轉成雙字元密文
  • 　hill:將連續的m個明文字元代換成m個密文字元
  • 　polyalphabetic:處理明文訊息時同時使用好幾個不同的monoalphabetic取代法

置換Transposition(重新排列)

  • 　rail fence(柵欄法):將明文寫成一連串的對角線形式,再一列一列地讀出
  • 　Simple Columnar Transposition(簡單分欄換位技術):將明文放入矩陣中,在隨機確定各欄輸出次序,即產生密文　
  • 　one-time pad:與訊息等長的隨機鑰匙,不重覆使用,絕對地安全

One-Time Pad（一次性密碼本）

加解密金鑰用過一次就丟掉，在現代大規模通訊環境幾乎沒有實用性，但是在某些特殊場景（軍事、情報、極機密點對點通訊）仍然有實作應用。例如，情報人員隨身攜帶印刷好的 One-Time Pad 密碼本，通訊雙方事先分發一模一樣的密碼本，每組密鑰只用一次，用紙筆手工加解密。

優點：可達到無條件安全（Unconditionally Secure），即使運算資源無限也無法破解。

缺點：實作上有困難

無法破解的原因：密文與明文之間不存在任何統計相關性，密文看起來與隨機數據無異，無法透過頻率分析等傳統手段還原明文。

加密原理

block cipher(區段加密法):每次加解密以區塊為單位 
將一段明文分成多個大小相同的block(通常為64bit),一次對一個block加密,運作模式分為以下
　ECB(electronic codebook mode,電子書模式):或稱ECM,分成區塊後大小不足則補滿,在將各別區塊加密
　CBC(cipher block chaining,密文塊串連模式):若相同區塊重覆,可產生不同密文塊
　CFB(ciphertext feedback,密文反饋模式):可當串流加密器用,便能以較少位元數加密
　OFB(output feedback,輸出反饋模式):可當串流加密器用,使用輸出做反饋值而不是密文,較不安全

stream cipher(資料流加密法):每次加解密以bit或byte為單位 
一次加密資料流中的一個位元或位元組,可用來做即時加密,但可能遭到鍵值流重複使用攻擊

使用block ciper的有以下:

  • feistel:區段加密法,對64位元區段加密,執行16回合,以shannon加密法的取代重排為基礎
  • DES(data encryption standard,資料加密標準)：56 bits key,64bits block size,16回合
  • triple DES:用3把鑰匙是168bits key,用2把鑰匙是112bits key,64bits block size,48回合,且架構為EDE加密解密加密
  • AES(進階加密標準)：128,192,256bits key,小於128bit可變block size,10,12,14回合,NIST選rijndael演算法做為AES,快速簡單
  • CAST-128:128位元key
  • IDEA(國際資料加密演算法):128bits key,64bit block size,8回合,很好但有專利,應用在pgp
  • blowfish:可變key<448bit,64bits block size,16回合,快速,小巧,簡單,可變安全性,對64位元區段加密
  • RC5：可變key<2048bit,128-256bits key,64bits block size,小於255可變回合,區段加密法,快速簡單,記憶體消耗少,採移位輪轉circular bit shifts,有專利
  • twofish:128,192,256bits key,123bits block size,非常強,廣為使用

使用stream cipher有以下:

  • RC4：1994外洩,快速簡單,可變鑰匙長度8-2048,用在SSL/TSL,WEP

Asymmetric Cryptsystems

也稱Asymmetric Encryption(非對稱式加密),Public-key Cryptography(公開鑰匙密碼學)

可用做數位簽章，金鑰交換，加解密

Trap-Door One-Way Function是公鑰密碼學的核心，依賴number theory(數論)中的計算困難問題，如質因數分解、離散對數、橢圓曲線數學問題等

基本架構

  • 金鑰數量：2把
    • 公鑰（Public Key）：用於加密或驗證簽章
    • 私鑰（Private Key）：用於解密或產生簽章
  • 金鑰成對使用
    • 用公鑰加密 → 對應私鑰才能解密
    • 用私鑰簽章 → 任何人皆可用公鑰驗證
  • 參與物件定義
    • P：明文（Plaintext）
    • C：密文（Ciphertext)
    • publickey：公鑰（Public Key）
    • privatekey：私鑰（Private Key）
    • M：訊息（Message）
    • S：數位簽章（Signature）

加密/解密架構

  • 加密：C = publickey(P)
  • 解密：P = privatekey(C)
  • 說明：用某個公鑰加密後，必須用對應私鑰解密。

數位簽章架構

  • 簽章：S = privatekey(M)
  • 驗章：M = publickey(S)
  • 說明：私鑰產生簽章，公鑰驗證來源及完整性，具不可否認性。

優缺點

優點：解決金鑰傳遞的安全性問題，支援數位簽章與身份驗證功能

缺點：計算資源消耗大，加解密速度較對稱加密慢

常見非對稱式加密算法

RSA（Rivest-Shamir-Adleman）

  • 最常用的非對稱加密法
  • 基於質因數分解困難度
  • 1978 年由 Ron Rivest、Adi Shamir、Leonard Adleman 共同提出

ECC（Elliptic Curve Cryptography，橢圓曲線密碼學）

  • 相同安全等級下所需金鑰長度遠小於RSA
  • 於1993年提出，計算效率高，但因歷史較短，早期可信度爭議較大

Knapsack Algorithm（背包加密法）

  • 1978年由Ralph Merkle提出
  • 已遭破解，現不再使用

其他應用技術

Diffie-Hellman（金鑰交換協議）

  • 1976年提出，基於離散對數困難問題
  • 用於安全交換金鑰，但本身無認證機制，易受中間人攻擊

ElGamal加密系統

  • 1985年提出，將Diffie-Hellman延伸應用於加密與數位簽章
  • 依賴離散對數問題的困難性

Schnorr數位簽章

  • 1989年提出，運算效率極高
  • 基於離散對數問題

DSA（Digital Signature Algorithm）

  • NIST於1991年公佈
  • 為Schnorr與ElGamal簽章演算法的變種
  • 為美國政府數位簽章標準

Hybrid Encryption

混合加密機制（Hybrid Encryption）是一種結合對稱加密（Symmetric Encryption）和非對稱加密（Asymmetric Encryption）的加密方式，旨在利用兩者的優勢來實現高效且安全的數據傳輸。它在實際應用中廣泛使用，例如 TLS/SSL 協議、電子郵件加密（如 PGP）和 VPN 等。

混合加密機制通過以下步驟實現安全通信：

  1. 使用非對稱加密傳輸對稱鑰匙：利用非對稱加密（如 RSA 或 Diffie-Hellman）安全地交換一個臨時的對稱加密鑰匙（通常稱為會話鑰匙，session key）。
  2. 使用對稱加密傳輸數據：使用交換得到的對稱鑰匙（例如 AES 鑰匙）對大量數據進行高效加密和解密。

這種方式結合了：

  • 對稱加密的優勢：速度快、計算效率高，適合加密大量數據。
  • 非對稱加密的優勢：解決了鑰匙分發的安全問題，無需預先共享秘密鑰匙。

確認性技術

防止訊息被惡意更改以及確認身份，常見方法如下

  1. 訊息加密：
    • 使用對稱式加密（如 AES，雙方共享同一把密鑰）或公開鑰匙加密（如 RSA，使用公鑰和私鑰）來加密訊息。
    • 加密後，即使訊息被攔截，未經解密也難以篡改，提供基本的完整性保護。
  2. MAC（訊息確認碼，Message Authentication Code）：
    • 利用訊息內容和一個共享的私鑰，通過特定演算法生成一個確認碼（MAC），並附在訊息後。
    • 接收方用相同的訊息和私鑰重新計算 MAC，與收到的 MAC 比對。如果一致，證明訊息未被篡改。
    • 雙方必須使用相同的密鑰。
    • 常見的有HMAC（Hash-based Message Authentication Code，基於雜湊的訊息認證碼）
  3. 雜湊函數（Hash Function）：
    • 不需要密鑰，直接將任意長度的訊息（m）輸入雜湊函數，生成一個固定長度的認證值（h(m)，也稱為雜湊值或摘要）。
    • 接收方用相同的雜湊函數對收到的訊息重新計算雜湊值，並與傳來的雜湊值比對，確認訊息是否完整。
    • 常見的雜湊函數有 SHA-256、MD5 等。
    • hash的更多說明參考https://systw.net/note/archives/2445

MAC運作原理

  1. 發送方：
    • 輸入：訊息（m） + 共享的密鑰（k）
    • 使用 MAC 演算法（例如 HMAC-SHA256）計算：MAC = MAC_algorithm(m, k)
    • 將訊息（m）和 MAC 一起發送給接收方
  2. 接收方：
    • 收到：訊息（m’）和 MAC
    • 用相同的密鑰（k）和收到的訊息（m’）重新計算：MAC’ = MAC_algorithm(m’, k)
    • 比對 MAC 和 MAC’ 是否相同：
      • 相同：訊息未被篡改，驗證通過
      • 不同：訊息可能被修改，驗證失敗

HASH和MAC的主要區別

特性雜湊函數 (Hash)MAC (訊息確認碼)
是否需要密鑰不需要需要（雙方共享密鑰）
功能僅驗證訊息完整性驗證完整性 + 來源真實性
安全性任何人都可以計算相同的雜湊值只有擁有密鑰的人才能生成/驗證 MAC
篡改防護如果攻擊者知道雜湊值，可替換訊息和雜湊值攻擊者無密鑰，無法生成正確的 MAC
常見應用檔案完整性檢查、密碼儲存網路通訊（TLS）、API 簽章、交易驗證