密碼學簡介與簡單生活應用 Introduction to Cryptography & Simple Applications in Life 2010 Spring ADSP 05/07

Outline 密碼學簡介-起源、發展、分類 對稱式金鑰 DES AES 非對稱式金鑰 雜湊函數 密碼學生活應用 RSA 網路安全 浮水印 條碼 一維條碼：code39 二維條碼：QR code 2010 Spring ADSP 05/07

密碼學-起源(1/2) 密碼學 Cryptography-由希臘文’kryptos’(隱藏) 和’graphein’(寫字)組成，代表隱藏的字 西元前五世紀，古希臘採用’斯巴達密碼棒’(scytale) 清末大儒紀曉嵐贈送的對聯 鳳遊禾蔭鳥飛去 馬走蘆邊草不生 禾下加鳳去掉鳥字得禿字，馬置蘆邊去掉草頭得驢字 2010 Spring ADSP 05/07

密碼學-起源(2/2) 電影-唐伯虎點秋香 亦屬於語意密碼的一種 數據保密技術 古今密碼學： 隱藏 特殊通訊技術: 方言 數據保密技術: 金鑰 古今密碼學： 古代：運用技術將要傳遞的訊息隱藏 現代：多指利用數學方法對資料進行加密以及解密的動作 2010 Spring ADSP 05/07

密碼學-分類(1/3) 1. 加密的運算方式 取代(substitution) 凱薩加密法: 將英文字母以後三個取代 Ex: ADSP -> DGVS 易破解,最多25種 置換(transposition) 用code book對照取代 阿拉伯人用頻率破解法 相乘(product) 轉成數字以後，與一組密碼(金鑰)做XOR運算 A →D B →E C →F … Z →C 取代 2010 Spring ADSP 05/07

密碼學-分類(2/3) 2. 處理資料上的差異 資料區段加密法(block cipher) 資料流加密法(stream cipher) 離散的塊狀處理 加密前較易檢驗資料完整性 資料流加密法(stream cipher) 一位元接一位元地即時加密資料 較快，用於位數較小的資料上 2010 Spring ADSP 05/07

密碼學-分類(3/3) 3. 按照金鑰個數 私密金鑰加密 公開金鑰加密 雜湊函數 加密、解密用同一把金鑰 加密、解密用不同金鑰(公鑰、私鑰) 用來檢驗資料完整性 2010 Spring ADSP 05/07

私密金鑰(1/3) DES(Data Encryption Standard) Triple DES 又稱對稱金鑰(Symmetric encryption) 加密與解密用同一把金鑰 EX: 加密10110100 ⊕11100001(金鑰) =01010101 (密文) 解密01010101 ⊕11100001(金鑰) =10110100 (明文) DES(Data Encryption Standard) Triple DES AES(Advanced Encryption Standard) 2010 Spring ADSP 05/07

私密金鑰(2/3) DES Triple DES AES(Rijndael加密法) 由於DES安全性不足，研究發現DES安全性 每次加密或解密的區塊大小均為64位元 8位元錯誤更正，實際可用56位元 傳送端與接收端需有同一把金鑰 Triple DES 由於DES安全性不足，研究發現DES安全性 可經由重複運算而產生 AES(Rijndael加密法) 目前最常用，已取代DES, 3DES 美國公開甄選，最好的加密方式 區塊長度為128位元，密鑰可選 128、196、256位元，安全性正比於密鑰長度 DES - 1 M C K 2 3 2010 Spring ADSP 05/07

私密金鑰(3/3)-DES 演算法: 令明文 按照IP (initial position)表排列，且令 執行16回合運算，第ｉ回運算如下 其中 為XOR運算， (48位元)為 金鑰 (56位元)所產生的subkey 3. 區塊交換 4. ，再將此 送進反IP表， 所得即為密文 5. 解密時先將密文送入反IP表，金鑰由 2010 Spring ADSP 05/07

公開金鑰(1/3) 又稱非對稱式金鑰 (Asymmetric encryption) 1976年由 Whitfield Diffie 及 Martin Hellman 提出加密與 解密使用不同鑰匙的概念 每個使用者有一把公鑰 一把私鑰 常見演算法： Deffie-Hellman Key Exchange RSA-分解大質數 橢圓曲線演算法(ECC) 2010 Spring ADSP 05/07

公開金鑰(2/3)-RSA 公私鑰產生方式 *：P=3,Q=5,N=15,因數有1,3,5,15 其中P≠Q，計算N=P*Q 根據歐拉函數，小於N且 與N互值數字個數為(P-1)*(Q-1) * 任意選擇 1~N之間的自然數 E， 且E與(P-1)*(Q-1)互質 根據D× E ≡ 1 (mod (P -1)(Q -1)) ** 找到D 銷毀P與Q，D為私鑰，E為公鑰 *：P=3,Q=5,N=15,因數有1,3,5,15 與15互質的數1,2,4,7,8,11,13,14 =(P-1) *(Q-1)=8個 **：15 ≡ 35(mod 10) 餘數相等 Ex：小扁要傳帳號給小九，小九選 P=47 與Q=71, N=P*Q=3337 (P-1)(Q-1)=3220 任選E=79 D=(Z*3220+1)/79, Z=1,2,3,... Z=25 時, D 為整數, 且D=1019 小九只要公佈N,E,自己保留D, 小扁即可用N,E加密再傳給小九 2010 Spring ADSP 05/07

公開金鑰(3/3)-RSA RSA加密公式 RSA解密 d為密鑰, c為密文 n為解密出的明文 e為公鑰，n為明文，c為密文 RSA解密 d為密鑰, c為密文 n為解密出的明文 小扁知道小九公鑰e=79，N=3337，小九知道自己公私鑰 小扁欲傳瑞士帳戶給小九： n=688 232 687 966 668 68879 (mod 3337) ≣1570 23279 (mod 3337) ≣2756 68779 (mod 3337) ≣2091 96679 (mod 3337) ≣2276 66879 (mod 3337) ≣2423 小扁傳 1570 2756 2091 2276 2423給小九 加密 小九收到1570 2756 2091 2276 2423 後，利用自己的密鑰D=1019 15701019 (mod 3337) ≣ 688 27561019 (mod 3337) ≣ 232 20911019 (mod 3337) ≣ 687 22761019 (mod 3337) ≣ 966 24231019 (mod 3337) ≣ 668 解密 2010 Spring ADSP 05/07

私密、公開金鑰比較 1. 實務上常搭配使用： 例如用DES將文章 加密(快)，用RSA將 DES的密鑰加密 2. 如果RSA的N大於100 位數，找到PQ可能要 花70年->代表不可破解 3. 使用硬體設計 DES 比 RSA 快 1000 倍 使用軟體設計 DES 比 RSA 快 100 倍 2010 Spring ADSP 05/07

雜湊函數 Hash Function 又稱單向加密函數，能將任何長度的文件 和資訊轉為特定碼數的代碼，稱為雜湊值 特性： Hash Value or Message Digest 特性： 不可反逆 無法由輸出反推其原輸入值 抗碰撞性(collision resistance)： 兩個訊息的雜湊值一樣機率非常低 擴張性(Diffusion)： 明文一個小改變會影響一個範圍的雜湊值 常見：MD2, MD4, MD5, SHA-0, SHA-1 應用：確保資料完整性, ex：火漆、BT HASH: 39a03831646113d2a2bd4bd31a0fa39295e46bd2 2010 Spring ADSP 05/07

加密流程 將資料經由Hash Function 轉乘雜湊值 將雜湊值以TX-RSA私鑰 做成數位簽章 將數位簽章加於資料後端 利用DES共同金鑰將新資料 加密為密文 利用RX的公開金鑰，用RSA 將DES共同金鑰加密 6. 將5. 的資料附在4.後，傳送 2010 Spring ADSP 05/07

解密流程 利用RX私鑰，將加密後的 DES共同金鑰解密 用共同金鑰將密文轉為資料 用TX公開金鑰，將數位簽 章轉為雜湊值 4. 將2.的資料送進雜湊函數 比對3.與4.的雜湊值，若 一樣代表資料無誤可信 2010 Spring ADSP 05/07

網路安全 digital signature, Authentication, 應用 SSL (Secure Sockets Layer), SET…etc 加解密技術 DES,RSA 密碼學/演算法 Symmetric / Asymmetric Cryptography 2010 Spring ADSP 05/07

生活應用 密碼學與資料隱藏 網路安全 展頻通訊 浮水印 條碼 影像浮水印 聲音浮水印 一維條碼 二維條碼 2010 Spring ADSP 05/07

一維條碼(1/2) ‧生活中隨處可見一維條碼 ‧取代KEY IN的動作 ‧條碼基本構造： 1. 起始碼- 讀取器判別開始 2. 資料碼- 照編碼方式 3. 檢查碼- 確保資料正確 4. 終止碼- 條碼結束 2010 Spring ADSP 05/07

一維條碼(2/2) Code39 一字元由5條黑色線條,4條白色線條, 總共9條線所組成,裡頭有3條是粗的線條 故稱code 3 (of ) 9 字元與相對值 0→0,…9→9 A→10,…Z→35 特殊位元 - → 36 . → 37… %→42 檢查碼 相對值總和 mod 43 2010 Spring ADSP 05/07

二維條碼(1/2) 一維條碼用寬度記錄資訊 二維條碼的長度與寬度都記錄資訊 Ex: QR code (Quick Response) a. 三個角用來定位，較不受旋轉影響 b. 依照圖的大小最多能存數千個字 2010 Spring ADSP 05/07

二維條碼(2/2)- QR 起源於日本, 為了追蹤汽車零件 在日本已相當普遍 2000年國際QR碼標準認可 應用非常廣泛 文字、網頁、商品資訊、店家資訊 電子票券、車票, ex: ibon上買的高鐵車票 公車站牌上QR碼，掃一下可知 班車時刻與路線並存於手機 Demo http://www.ipeen.com.tw/ 愛評網 中文WIKI網址的QR碼 2010 Spring ADSP 05/07

QR code in Life (1/4) 小扁與小珍想去吃瑞士料理 連上了愛評網 2010 Spring ADSP 05/07

QR code in Life (2/4) 出現QR code之後 小扁用手機裡的應用程式一拍 2010 Spring ADSP 05/07

QR code in Life (3/4) 解密成功!! 下一步可以選擇發送簡訊給小珍 或用地址與GPS結合開始導航 延伸： Ex: 讀到sms00+0912345678 自動發送簡訊到0912345678 2010 Spring ADSP 05/07

QR code in Life (4/4) 2010 Spring ADSP 05/07

QR code參考網址 QR軟體下載網站(英文) http://reader.kaywa.com/  中文QR公司(可下載軟體、製做QR碼) http://www.quickmark.com.tw/cht/basic/index.asp 新營旅遊服務中心 http://blog.xuite.net/tainan950101/icenter/30660679 QR介紹 http://blog.xuite.net/chenni037/food/17495915?ref=rel Google結合QR碼 http://www.google.com/help/maps/favoriteplaces/business/barcode.html http://www.youtube.com/watch?v=zuVSpG-ZdkU  愛評網 http://www.ipeen.com.tw/ 2010 Spring ADSP 05/07

Reference [1] Rivest, R.; A. Shamir; L. Adleman (1978). "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Communications of the ACM 21 (2): 120–126. [2] Biham, Eli and Adi Shamir (1991). "Differential Cryptanalysis of DES-like Cryptosystems". Journal of Cryptology 4 (1): 3–72. [3] Biham, Eli and Adi Shamir, Differential Cryptanalysis of the Data Encryption Standard, Springer Verlag, 1993. [4] http://en.wikipedia.org/wiki/Main_Page [5] "QR Code Standardization | QR Code.com". Denso-wave.com. Retrieved 2009-04-23. [6] http://140.127.31.90/ISMS/Lecture/資安技術/密碼學原理與應用.pdf 2010 Spring ADSP 05/07