Cryptography 密碼學簡介 B91901139 電機三 蕭旭君
Cryptography 緣起 名詞解釋 常見的加密解密法 密碼學的應用 未來發展
History Cryptology Cryptography Cryptanalysis 達到資訊的秘密性、可鑑定性 Cryptology Cryptanalysis = ”隱藏(Kryptos)”+”訊息(logos)” 研究秘密通訊之學問 破解密碼系統、偽造訊息
Terminology Cipher text 明文 m 明文 m 密文 c Encrypt 加密 E(m) Decrypt 解密 D(c)
Terminology 公共鑰匙 私密鑰匙 Eve 發送者 接收者 竊密者
Terminology Symmetric vs. Asymmetric ex. y=3x-2 => x=(y+2)/3 y=11x (mod 53) => x=?? Unconditional Security vs. Computational Security 怎樣才算安全?...... 無法在合理的時間內，用合理的資源解出的密碼
Historical Ciphers 傳統加密方式主要分為兩大類： 有名的傳統加密法：DES、FEAL Transposition 換位 Substitution 代換 有名的傳統加密法：DES、FEAL
Transposition Method 依照某種特定規則重新排列明文 Ex. I am a student I m s u e t a a t d n
Substitution Method Shift Cipher (Caesar’s Cipher) I CAME I SAW I CONQUERED H BZLD H TZV H BNMPTDSDC
Substitution Method(cont’d) However…easy to break!!
Public Key System - RSA named after its inventors Ron Rivest, Adi Shamir and Len Adleman Base on Number Theory y=ex (mod N) => x=?? 沒有private key 很難求出x 有多難？ 大數的質因數分解 要解出N=pq 其中p q為兩大質數
Public Key System - RSA 位元 時間(1GHz/s) 30 1 秒 60 1 年 100 1000 億年!! 若對N=pq的每一種可能加以檢驗，則我們需要… 事實上，運用平行處理及一些篩選法則，可以大幅提升檢驗的效率。 但仍難以在可接受的時間內破解。 位元 時間(1GHz/s) 30 1 秒 60 1 年 100 1000 億年!! 由於RSA用到指數運算，加密的過程耗費較多的時間，現行系統多先用RSA傳送private key，再合併使用其他加密方式。
Public Key System - RSA US10,000 RSA-576=1881 9881292060 7963838697 2394616504 3980716356 3379417382 7007633564 2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573 4031879550 6569962213 0516875930 7650257059 =(3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317) *(4727721 4610743530 2536223071 9730482246 3291469530 2097116459 8521711305 2071125636 3590397527) 2002年10月7日，以破解加密術而著稱的Distributed.net宣佈破解了美國RSA資料安全實驗室開發的64位密匙—RC5-64 為了檢測 RSA 技術的安全性，一家專門研究RSA 技術的公司 RSA Security 提供獎金給成功分解公佈的 8 個巨大合成數的人。 在2003年12月3日，一個德國機構成功分解了RSA-576 全球33.1萬名電腦高手+4年的時間!!
Application Digital Signatures 數位簽署 Digital Cash 電子錢包 Timestamping Services 電子時戳 Election 電子投票系統
Digital Signature 確保文件是由發送者送出 事後發送者無法否認，可由第三者確認 先用私密金匙加密，再用公共金匙解密
A match – making Protocol 要如何達成共同的決議，而不用公開表述自己的意見？ Ex. A和B透過朋友C認識，相處了一天後，想知道彼此的心意，但又不敢先表態…
Future Work 量子電腦 0和1的狀態能同時並存，稱為疊加(superposition)。量子平行處理的概念，一個原子可以同時代表兩個狀態 Ex.三個原子可同時代表 000 001 010 011 100 101 110 111 龐大運算能力對現今的密碼系統是個致命的威脅 對系統的時間、振幅、相位要求嚴格
Future Work 量子密碼術 Step 1 兩種發送光子的模式 每一種都有兩個正交的偏振方向
Future Work Step 2 Bob 隨機選擇兩種模式中的一種偵測光子 如果Bob和Alice選擇的模式相同， 反之，偵測到的位元不可預測(可能為0或1) 若Eve試圖竊聽，根據量子力學，會改變傳送光子的狀態， Alice和Bob可以選擇一些位元比較，驗證是否遭竊聽
Quantum Cryptography Step 3 Bob告訴Alice他選擇濾片的模式 Alice回答Bob哪些是正確的 把這些正確偵測到的位元取出，做為加密的密碼
Quantum Cryptography
Reference Nigel Smart, Cryptography : An Introduction, McGraw-Hill, 2003 張紹勳,蔡志敏. 演算法 入門與進階, 松崗出版社 科學人月刊 no.36 量子傳訊 絕對機密 近代密碼學及其應用，松崗出版社 http://www.rsasecurity.com/rsalabs/node.asp?id=2093