密碼學 網多實驗第二組 B92901016 翁秉義.

Presentation on theme: "密碼學 網多實驗第二組 B92901016 翁秉義."— Presentation transcript:

1 密碼學 網多實驗第二組 B 翁秉義

2 Outline 簡介 歷史 方法 理論

3 簡介 密碼學 Cryptology 隱藏(kryptos) 訊息(logos)

4 簡介 – 名詞解釋 明文(plaintext) 密文(encrypted; cipher text) Encrypt / decrypt
任何人都讀得懂的文字 密文(encrypted; cipher text) 用特殊方法使文章內容變得混亂，使得只有少數持有「鑰匙」的人才能看得懂的訊息 Encrypt / decrypt 加密 / 解密

5 簡介 – 名詞解釋 Key 鑰匙 明文與密文的對應關係

6 簡介 – 四大目標 秘密性 完整性 鑑定性 不可否認性 防止竊聽 內容不可被更改 確定資訊確實是由發送者所傳送而非偽造
發送方在事後不可否認其傳送過的資訊

7 歷史 密碼學的歷史已有四千多年 密碼學經常作為軍事用途

8 歷史 – Caesar Cipher 兩千年前，Julius Caesar (凱薩)使用了一種簡單的替換密碼 運用在Gallic Wars

9 歷史 – Caesar Cipher 每個字母用其後三個字母替代 一般情況： A  D; B  E; …
只要每個字母都有一對一的關係即可

10 歷史 – Caesar Cipher 阿拉伯人發明頻率攻擊方法

11 歷史 – Vigenère Cipher 改進：Blaise de Vigenère 發明多字母替換密碼(polyalphabetic substitution cipher) Vigenère cipher 逐漸被各國採用

12 歷史 – Vigenère Cipher Vigenère cipher 明文：ABCDEFGHIJKLMNOPQRSTUVWXYZ
組一：ZYXWVUTSRQPONMLKJIHGFEDCBA 組二：LMNOPQRSTUVWXYZABCDEFGHIJK 明文：I CAME I SAW I CONQUERED 密文：R NZXV T HLD T XZMBFPIPW 密文： RNZXVTHLDTXZMBFPIPW

13 歷史 – Vigenère Cipher Vigenère cipher 機器： Jefferson cylinder

14 歷史 – Vigenère Cipher 1854年， Vigenère cipher 首次被 Charles Babbage 攻破，但没有公開 Friedrich Kasiski 於1863年攻破 Vigenère cipher，並公開了

15 歷史 – 公開金鑰 近代：電腦發明 1976年，公開金鑰密碼學觀念發表 1978年，Knapsack公開密碼系統提出
同年，RSA公開密碼系統提出 1982年，Knapsack被Shamir破解。 Shamir – RSA的發明人之一 RSA一直未被破解

16 歷史 – 公開金鑰 Shamir

17 歷史 – 公開金鑰 1994年，RSA129被Lenstra領導小組破解。 “We are happy to announce that…”

18 方法 古典密碼學 替換 變位 近代密碼學 量子密碼學

19 古典密碼學 – 機器 密碼機 德國發明，用於二次大戰

20 古典密碼學 – 程式 火星文產生器 V2.0 Designed By Br' ZetA 2002 阿光  ◇┼◣◢♂┬▏┤◢

21 古典密碼學 – 變位法 《數位密碼》丹．布朗

22 例1 – 密文 密文： PFEE SESN RETM MFHA IRWE OOIG MEEN NRMA ENET SHAS DCNS IIAA IEER BRNK FBLE LODI

23 PFEE SESN RETM MFHA IRWE OOIG MEEN NRMA ENET SHAS DCNS IIAA IEER BRNK FBLE LODI

24 例1 – 排列 P F E E S E S N R E T M P F H A I R W E O O I G
M E E N N R M A E N E T S H A S D C N S I I A A I E E R B R N K F B L E L O D I

25 例1 – 明文 明文： PRIME DIFFERENCE BETWEEN ELEMENTS RESPONSIBLE FOR HIROSHIMA AND NAGASAKI Prime difference between elements responsible for 広島 and 長崎? 還得去找問題的答案…= =

26 古典密碼學 – 變位法 變位

27 三國時代 XD

28

29

30 理論 – 單向 / 雙向函數 y = f(x)… 雙向函數 y = f(x) = 2x + 1
從y反推x？  f-1 = (y – 1) / 2 只要有 f 就可以很簡單地推出 f-1  不好！

31 理論 – 單向 / 雙向函數 y = f(x)… 單向函數 單向暗門函數 幾乎不可能從 y 反推 x
有一 f-1，使得x = f-1(y) 很容易被計算 在只有 f 的狀況下，幾乎不可能推出 f-1 在不知道 f-1 的狀況下，幾乎不可能從 y 反推 x

32 理論 – 單向 / 雙向函數 古典密碼學 雙向函數 藉由隱藏 f 來防止竊聽者推出 f-1 近代密碼學 單向暗門函數 因此，f 是公開的