Brief Intro to PQC

後量子密碼學簡介

1

國立政治大學資訊安全科技研究中心

2

國立政治大學資訊安全科技研究中心

3

國防大學理工學院

資安事件

4

資訊安全需求

• ISO 27001資訊安全管理系統(Information Security Management System, ISMS)中規範一個系統必須對其機密性、完整性、可用性進行適當規範。
• 機密性(Confidentiality)：防止機密資訊洩漏給未經授權的使用者。
• 完整性(Integrity)：資料內容不能被未經授權者竄改或偽造。
• 可用性(Availability)：確保資訊系統運作過程中的正確性。

5

資訊安全需求

6

資訊系統安全架構

7

Secure Electronic Transaction

8

下

單

發卡銀行

收單銀行

商家

付款閘道

卡片註冊

持卡人

支付認可

支付認可

支付授權

支付授權

支

付

認

可

支

付

授

權

憑證機構

憑證核發

憑證查詢

憑證管理

加密/解密

數位簽章

密碼學發展過程

9

～古希臘

1976

～ 2022

位移式密碼 (Transposition Cipher)

置換式密碼 (Substitution Cipher)

​

DES

AES

公開金鑰密碼學

後量子

密碼學

位移式/置換式密碼

• 凱薩密碼(Caesar Cipher):�將每個字母右移3位做為密文

​

• 密碼棒(Scytale)

10

Playfair密碼

• 國家寶藏2–古籍秘辛

11

來源：左撇子電影博物館https://mike0123783.pixnet.net/blog/post/32974942� https://nationaltreasure.fandom.com/wiki/The_debt_that_all_men_pay

密文

金鑰提示：The debt that all men pay

金鑰分配問題

• Alice要寄一封信給Bob，但不希望信在寄送途中被拆封，因此將信鎖在一個盒子中，並將盒子寄出。
• 但Bob沒有對應的鑰匙可以開盒子的鎖，因此無法拿到信。
• 為了將鎖的鑰匙寄給Bob，並確保鑰匙不會被郵差拿走，因此需要另一個上鎖的箱子來安放這把鑰匙。

12

解決方法

13

Step 1

Step 2

Step 3

金鑰交換協定

• 由Whitefield Diffie與Martin Hellman於1976年提出公開金鑰密碼系統之概念(在這之前的為對稱式密碼學)。
• 在他們的論文中提出了“金鑰交換協定”(Key Exchange Protocol)之概念，利用公開金鑰來幫助通訊雙方可以安全地協議出一把共同的交談金鑰(Session Key)。
• Diffie-Hellman金鑰交換協定被使用於許多網路協定中，如TLS、SSL、HTTPS。

14

公開金鑰密碼系統

15

量子電腦

16

量子電腦

17

量子演算法

18

Shor 演算法

19

Shor 演算法

20

糾纏態

Shor 演算法

21

觀測

量子霸權(Quantum Supremacy)

• 量子霸權：證明量子計算機可以解決某些經典電腦難以解決的問題 (該問題未必需要有實務應用)
• 量子霸權候選
• 質因數分解問題 (Factorization)
• 玻色採樣 (Boson Sampling)
• 隨機量子電路採樣 (Random Quantum Circuit Sampling)
• Google透過隨機量子電路採樣達成量子霸權：利用量子電腦執行隨機選擇的量子閘操作，產生隨機量子態，然後取樣測量量子態。

22

彈珠檯

​

​

​

• 彈珠掉入某個特定槽的機率�為多少?

23

高爾頓釘板 (Galton Box)

24

玻色採樣

25

量子電腦發展

26

量子電腦發展

27

2024/02/29，中研院，5-qubit

2024/02/29，清大，最小量子電腦

量子電腦發展

28

後量子密碼學標準化

• 美國國家標準暨技術研究院(NIST)已正式發表後量子密碼標準
• Round1 (2016)：審查優缺點，82件投稿，69件進入審查，26件獲選
• Round2 (2019)：軟硬體實現評估，8件獲選
• Round3 (2020)：
• 加密：Classic McEliece, CRYSTALS-Kyber, NTRU, Saber
• 簽章：CRYSTALS-Dilithium, Falcon, Rainbow
• 備選：BIKE, FrodoKEM, HQC, NTRU Prime, SIKE, GeMSS, Picnic, SPHINCS+
• Round4 (2022)：CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, SPHINCS+
• Round5?(2025~)：HQC ...�

​

29

後量子密碼遷移

• Mosca's Inequality Theorem: If X+Y>Z, then worry!
• X:機密資料需要保存的時長
• Y:完成量子遷移最短時間
• Z:量子電腦成熟到可以破解傳統加密的時間(Y2Q)

​

​

• 「Harvest now, decrypt later」
• Q-day: 雲端安全聯盟(CSA)Y2Q倒數

​

30

後量子密碼遷移

• 2023年NIST發布後量子遷移指引
• Quantum Readiness: Cryptographic Discovery
• Quantum Readiness: Testing Draft Standards for Interoperability and Performance
• 後量子密碼遷移指引(數產署)
1. 建立量子準備計畫(標準化)
2. 盤點加密資產清單
3. 與技術供應商討論量子準備計畫
4. 確認供應鏈的量子準備程度
• 系統遷移是十分困難的，特別是對於大規模且軟硬體兼具的系統

31

SHA1->SHA3

• SHA1(Secure Hash Algorithm 1)
• 1995: NIST頒布標準
• 2004: NIST建議以SHA2取代SHA1
• 2005: SHA1從理論層面被破解
• 2015: NIST建議聯邦政府停止使用SHA1
• 2017: NIST與荷蘭國家數學和電腦科學研究學會(CWI)找到實務上可以使用的碰撞演算法
• 2017: GOOGLE Chrome停止支援發布SHA1的憑證
• SHA2: 2001頒布
• SHA3: 2012決選，2015頒布

32

SHA1->SHA3

33

34

後量子密碼—晶格密碼學

35

晶格密碼學：Lattice-Based Cryptography

後量子密碼—晶格密碼學

36

最近向量問題： 給定格點找其鄰近點� 給定任意點找其最近格點

後量子密碼—多變量密碼學

37

後量子密碼—編碼密碼學

• 以糾錯碼(Error Correction Code)為基底的密碼系統

38

解碼問題：Syndrome Decoding Problem

找一個誤差來解釋出錯處

找一個小誤差來解釋出錯處

後量子密碼—雜湊密碼學

39

後量子密碼—同源密碼學

• 同源密碼學：Isogeny-Based Cryptography
• 同源映射：保留某些運算性質(代數結構)的映射

​

40

isogeny

後量子密碼—同源密碼學

41

Alice

Bob

+

+

+

+

NIST後量子密碼標準化

• Selected Algorithms in 2022 ：
• CRYSTALS-Kyber (FIPS 203): Lattice-based Encryption
• CRYSTALS-Dilithium (FIPS 204): Lattice-based Signature
• FALCON: Lattice-based Signature
• SPHINCS+ (FIPS 205): Hash-based Signature

42

NIST後量子密碼標準化

43

Thanks for Listening!

44

Fast IDentity Online

45

Source: TWCA: https://www.twca.com.tw/product/c0281542-f034-4ba9-8164-c517ebc5e0c0

身分驗證

公私鑰/生物特徵

位移式/置換式密碼

• 福爾摩斯-�The Adventure of the Dancing Men

​

​

• 名偵探柯南-�月亮、星星與太陽的秘密

46

來源：https://deductionpedia.weebly.com/blog/the-adventure-of-dancing-man-code

簡單替代法

• 共濟會密碼(豬圈密碼)

47

A P P L E

Playfair密碼

48

規則1：明文在同一列

明文字母兩兩一組，依照5x5密碼表上的排列方式進行轉換

規則2：明文在同一行

規則3：不在同列/行

Playfair密碼

49

Playfair密碼

• 還原矩陣
• 重複字母去除
• J與Q擇一去除

50

Playfair密碼

• 密文：ME IK QO TX CQ� TE ZX CO MW QC� TE HN FB IK ME� HA KR QC UN GI� KM AV
• 明文：la bo ul ay el� ad yw il lx le� ad to ci bo la� te mp le so fg� ol d
• Laboulaye lady will lead to cibola temples of gold

51

Enigma密碼機

52

密碼分析(Cryptanalysis)

• 頻率分析：由於每個字母皆會唯一對應到另一個字母(或符號)，因此字母出現頻率不會改變。

53

現代密碼系統

• 古典密碼系統多仰賴語言學及文字學，容易受頻率分析攻擊。
• 某些語言系統(如中文)不易使用置換法或替代法。
• 現代密碼系統以“位元”(bit)為處理單位進行加密。
• ASCII CODE: A -> 0100 0001
• Big 5 (繁體中文)
• Unicode (萬國碼)

​

54

DES加密標準

• Data Encryption Standard
• 1972年美國國家標準技術研究院(NIST)開始徵集。
• 1974年由IBM公司提交之魔王密碼(Lucifer)中選。
• DES為區塊密碼，對一定大小的明文或密文進行加解密。
• DES支援之區塊大小為64位元，其中8位元為錯誤更正用。
• 缺點為金鑰長度過短(56位元)。

55

DES演算法

56

Encryption

Decryption