Try   HackMD

密碼學簡介(一)_Cryptography

本文主要想透過簡單的方式來介紹密碼學，主要想透過為什麼 (why) 和 如何做 (how) 為出發點來介紹，也會詳盡的介紹其背後的數學理論，用得最多的有代數 (Algebra) 及數論 (Number Theory)。

在密碼學中，主要分為兩種密碼系統，對稱式密碼學 (Symmetric-key Cryptography)與非對稱式密碼學 (Asymmetric-key Crptography)，同時非對稱式密碼學又稱公開金鑰密碼學 (Public-key Cryptography)，以下將進行簡單的介紹。

對稱式密碼學 (Symmetric Cryptography)

簡單來說對稱式的加解密是透過"同一把"密鑰 (secret-key)來達成通訊，在兩個人進行通訊(或多人)的情況中，都是經由"同一把"密鑰來把明文 (plaintext) 加密，或是把密文 (ciphertext) 解密。

  • Definition of notations:
    • m: plaintext or message
    • c: ciphertext
    • ek(): a symmetric-key encryption algorithm, using key "k" to encrypt.
    • dk(): a symmetric-key decryption algorithm, using key "k" to decrypt.
Created with Raphaël 2.2.0AliceAliceBobBobplaintext : mencryption use key "k" :  e_k(m) = ctry to decrypt :  d_k(c) = m

著名的對稱式密碼演算法有

AES、DES…，並且要搭配操作模式 (mode of operation)，有機會再為大家一一介紹。

  • 問題探討 :
      1. 兩個人或者多人在進行通訊前，必須先協定出一把共有的密鑰，這必須透過安全的通道才能達到(secure-channel)。
      1. 若是多人進行通訊，但不想使用同一把key會造成麻煩，例如:現在有Alice和其他三人，Alice當然可以一次和其他三個人協定一把共有密鑰，但若Alice現在只想傳遞訊息給其中人一，就必須在另外和此人協定一把不一樣的密鑰。若是N個人都想倆倆可以進行通訊，key的數量將會是
        C2n         ，大概是
        O(N2)         的等級。

種種因素和考量，人們有了想法，有沒有可能加密和解密是不同把密鑰呢? 答案是有的，也就是我們接下來要介紹的非對稱式密碼系統。

非對稱式密碼學 (Asymmetric Cryptography)

在我們進入非對稱式密碼系統的世界中，我們先不講出公鑰和私鑰 (key-pair)的概念，我們思考一個情境，Alice 和 Bob 手中各有兩把不一樣的鑰匙，記做

kA、kB，假設有一個保險箱上有兩個鎖頭，我們可以透過把 plaintext 鎖入保險箱中來模擬加密行為，如何在不在各自需要拿到對方的密鑰前提下完成加解密呢?

  • 以下給出一個想法:
      1. 由Alice出發，把明文放入保險箱，用自己的鑰匙鎖上，並把保險箱送給Bob。
      1. Bob 拿到後鎖上自己的鎖，再把保險箱交還給Alice。(Note: 此時保險箱上有兩個鎖)
      1. Alice 拿到後，解開自己的鎖，並再把保險箱交還給 Bob。(Note: 此時保險箱上只有一個鎖)
      1. 到這一步，Bob 就可以透過自己的密鑰來解開保險箱，並拿出明文。
Note: 此過程兩人都不需要知道對方的密鑰。

這個例子，便是一個簡單的非對稱式密碼的實現 (當然上述運輸保險箱只是為了描述 xd)。實際上非對稱式的密碼系統，每一個用戶 (這裡假設 : user A) 手上會有一組 key-pair

(priA,pubA) ， 分別對應到私鑰及公鑰，私鑰及是使用者自己需要保管好的，只要私鑰經過洩露了，公鑰也隨之被破解。而其公鑰便是可以公開給其他使用者的資訊，藉由公開的公鑰，可以和其他使用者進行安全的通訊。

  • Definition of notations:
    • m: plaintext or message
    • c: ciphertext
    • ek(): a symmetric-key encryption algorithm, using key "k" to encrypt.
    • dk(): a symmetric-key decryption algorithm, using key "k" to decrypt.
    • (priA,pubA):key-pair of user A
    • (priB,pubB):key-pair of user B
Created with Raphaël 2.2.0AliceAliceBobBobplaintext : mencryption use key "k" : e_{pub_B}(m) = ctry to decrypt :  d_{pri_B}(c) = m

既然有了非對稱式的密碼系統，那是不是許有問題都被解決了呢? 其實不然，非對稱式的密碼系統出現引發了後續很多的問題，像是著名的中間人攻擊(man-in-the-middle-attack)，及後面的數位簽章 (Digital Signature)、公開金鑰基礎建設(Public Key Infrastructure, PKI)…等等。有機會將為各位一一說明，但再繼續探討下去之前，我們需要一個數學的工具，下次將會為大家介紹一些基本的數學。

推薦密碼學書籍

  • [1] Understanding Cryptography : A Textbook for Students and Practitioners, Christof Paar, Jan Pelzl
  • [2] serious Cryptography A Practical Introduction to Modern Encryption by Jean-Philippe Aumasson
  • [3] An Introduction to Mathematical Cryptography, Jeffrey Hoffstein
    Jill Pipher Joseph H. Silverman
  • [4] Introduction to Cryptography, Johannes A. Buchmann
  • [5] MATHEMATICS OF PUBLIC KEY CRYPTOGRAPHY STEVEN D. GALBRAITH
tags: Cryptography 密碼學
Last changed by 
 
JayChang
0
1
995

Read more

DES Algorithm

對稱式密碼學，主要分為兩個大項，stream cipher 和 block cipger，下文主要會介紹block cipher其中的一個例子：DES 。 123 (Figure comes from Understanding Cryptography : A Textbook for Students and Practitioners, Christof PaarJan Pelzl) Stream 可以想像是一次加密1個 bits，block ciphper 則是一次加密多個bits，我們稱這多個bits為一個block。 兩大主要概念被在許多密碼演算法可見。 Confusion ： an encryption operation where the relationship between key and ciphertext is obscured.

Apr 11, 2024
List of Articles

Crytprography 密碼學簡介(一)_Cryptography The introduction to Cryptography 密碼學簡介(二)_Cryptography The introduction to Algebra used in Cryptography

Jul 25, 2021
Elliptic Curve Cryptorgraphy

This article will introduce the cryptographic system based on elliptic curve. We will go through detail as possible. Finally, we will present elliptic curve digital signature (ECDSA) aglgortihm, which is widely used in blockchain for signing transaction. 1. The group of points on elliptic curve In this section, we define group of points on elliptic curve. The basic concept of group and can be referred to this link. First, we define the ellitpic curve over $\mathbb{Z}_p$ $\textit{Definition: Elliptic Curve}$ $E$ $\textit{The elliptic curve over } \mathbb{Z}_p, \quad p>3, \textit{is the set of all paris } (x,y)\in \mathbb{Z}_p \textit{, which fulfill}$ $$y^2\equiv x^3 + a \cdot x +b \textit{ (mod } p)$$

Jul 25, 2021
rand() function in C lib

Due to the issue about the random function recently, I survey some related topics. In fact, rand() in C lib is not secure enough to be used in cryptographic or privacy problem. This kind of random function we called random number generator (RNG), and we called the random function, which strong enough in cryptographic scenario, cryptographically-secure pseudorandom number generator (CSPRNG). In the following, I will list some drawbacks about PRNG. And in order to imagine easily, we just regard PRNG as rand() in C lib for convenience. 1. The rand() is deterministic Everyone has the experience about calling rand(), when we need a random number. Before calling it, we may need to choose the "seed" used to decide random number. In the common situation, we usually call "srand(time(NULL))"" first. That is the problem! If we try to use this random number in implementation required security or privacy, it may cause system be vulnerable. For example, if we use this method to construction "private key". And an attacker know which "year" you generated this random number. The complexity an attacker using brute-force key search is about $2^{25}$. (NOTE: we use time as seed) This complexity keeps decreasing as the more precise time an attacker known. (e.x. year, month, even day). The simple solution is that using another way to generate "seed", but it is still not ensure security if the bad PRNG be applied.

Jul 18, 2021
Read more from JayChang
Published on HackMD