密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法

Slides:



Advertisements
Similar presentations
3.1 信息加密技术概述 3.2 密码技术 3.3 密钥管理 3.4 网络加密技术 习题与思考题 参考文献 实训指南
Advertisements

單元九:單因子變異數分析.
公開金鑰密碼系統 (Public-Key Cryptosystems)
電子商務安全防護 線上交易安全機制.
質數的應用 – RSA加密演算法 國立中央大學 資工系 江振瑞.
CH9 資通安全 系統安全與網路安全及其重要性 加、解密技術 訊息鑑別與雜湊函數 數位簽章法 憑證與公開金鑰基礎架構 確保網站安全技術
密碼學與網路安全 第9章 公開金鑰密碼學與RSA
公共金鑰基礎建設之介紹與應用 指導老師:吳有龍 老師 姓名:潘祈良 B 科系:進修資管四B.
文件訊息鑑別 (Message Authentication)
密碼學概論 Speaker:謝凱評.
第六章 加密技術應用 6-1 建立信任關係 6-2 對稱金鑰加密技術 6-3 不對稱金鑰加密技術 6-4 雜湊加密技術 6-5 加密工具程式
電子資料保護 吳啟文 100年6月7日.
06資訊安全-加解密.
密码学基础 电子科技大学•计算机学院.
電子戶籍謄本申辦及驗證實務作業與問題討論
計算機概論 蘇俊銘 (Jun Ming Su) 資料加密技術簡介 計算機概論 蘇俊銘 (Jun Ming Su)
質數的應用 – RSA加密演算法 (一個價值21億美元的演算法)
認識倍數(一) 設計者:建功國小 盧建宏.
密碼學簡介與簡單生活應用 Introduction to Cryptography & Simple Applications in Life 2010 Spring ADSP 05/07.
主題五 CPU Learning Lab.
資訊安全-資料加解密 主講:陳建民.
亞洲大學的數位學習資源與應用 鍾仁宗老師 101年12月4日.
密碼學 黃胤誠.
第三章 公钥基础设施PKI 本章学习重点掌握内容: 密码学基本术语 密码体制分类 私钥密码体制的主要特点 公钥密码体制的主要特点
公開金鑰密碼系統 Public Key Cryptosystem
Module 2:電子商務之安全.
CH19資訊安全 認識資訊安全與其重要性 了解傳統與公開金鑰密碼系統, 以及基本的安全性觀念 了解訊息鑑別與雜湊函數 了解數位簽章法
資電學院 計算機概論 F7810 第十七章 資訊安全 陳邦治編著 旗標出版社.
資訊安全基礎 by Chuck Easttom 第 7 章 加密.
4B冊 認識公倍數和最小公倍數 公倍數和最小公倍數的關係.
SSL加解密原理 姓名:林子鈞 指導老師:梁明章老師
基礎密碼學 非對稱式金鑰加密法 樹德科技大學 資訊工程系 林峻立 助理教授.
電子商務安全 主講人:張真誠 教授 國立中正大學 資訊工程研究所.
二、相關知識 1. 比較器 比較器是一種組合邏輯電路,它可以用來執行一個數值大於、等於、或小於另一個值。 (1) 位元比較器
OpenID與WordPress使用說明
基礎密碼學 數位簽章及其應用 樹德科技大學 資訊工程系 林峻立 助理教授.
Wavelet transform 指導教授:鄭仁亮 學生:曹雅婷.
雜湊與MAC演算法 Hash and MAC Algorithms
密碼學概論 電機四 b 吳秉寰.
1.3 在整除性問題之應用 附加例題 3 © 文達出版 (香港 )有限公司.
Introduction to FinTech
網路安全技術 OSI七層 學生:A 郭瀝婷 指導教授:梁明章.
密碼學 網多實驗第二組 B 翁秉義.
Chapter 5 公開金鑰基礎建設 Public Key Infrastructure (PKI) (Part 2)
為何電子商務的安全性令人擔憂? 電子商務資訊安全 實體商務也擔心安全-但數位化的偽造數量會更多更快
公開金鑰密碼系統 (Public-Key Cryptosystems)
學習單元:N6 數的性質 學習單位:N6-3 用短除法求H.C.F. 和 L.C.M. 學習重點 : 1. 複習因數分解法求
網頁資料知多少? 事 實 ? 謠言?.
Definition of Trace Function
小學四年級數學科 8.最大公因數.
密碼學 Chapter 3 基於電腦的對稱性金鑰密碼學演算法
緩衝區溢位攻擊 學生:A 羅以豪 教授:梁明章
密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法
淺淺談密碼學 2018/12/27.
資訊安全技術 課程簡介.
資訊安全和資訊倫理宣導 永康區復興國小教務處.
電腦概論考題分析 佛學資訊組 碩一 張榮顯.
電子商務交易安全 A 楊凱翔.
MiRanda Java Interface v1.0的使用方法
moica.nat.gov.tw 內政部憑證管理中心
網路安全技術 A 林建宏 指導教授:梁明章老師
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
為何電子商務的安全性令人擔憂? 第二節 電子商務資訊安全 實體商務也擔心安全-but數位化的偽造數量會很多 網際網路是互聯的(匿名與距離性)
13194: DPA Number II ★★☆☆☆ 題組:Problem Set Archive with Online Judge
資料表示方法 資料儲存單位.
因數與倍數.
NFC (近場通訊, Near Field Communication) 靜宜大學資管系 楊子青
Chapter 4 Multi-Threads (多執行緒).
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
Presentation transcript:

密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法 Computer-based Asymmetric Key Cryptographic Algorithms (Part 1)

前言 對稱性金鑰密碼學是快速且有效率的 對加密的訊息,發送方和接收方在對稱性金鑰密碼學中使用相同金鑰,要同意這一把金鑰並未讓任何其他人知道是一件非常困難的事 非對稱性金鑰密碼學可以解決這個問題

非對稱性金鑰密碼學的簡史 在1970年間,史丹佛大學的學生 Whitfield Diffie 遇見他的教授 Martin Hellman,他們開始思考金鑰交換的問題,經過一些研究與複雜的數學分析,他們開始興起非對稱性金鑰密碼學的想法 許多專家認為這在密碼學史上或許是唯一的真正改個概念,因此,Diffie 和 Hellman 被當成非對稱性金鑰密碼學之父

非對稱性金鑰密碼學的簡史 非對稱性金鑰密碼學榮耀的爭論 英國通訊電子安全組織 (Communication Electronic Security Group, CSEG) 秘密的單位 1960, Jame Ellis, 提出概念 1973, Jame Ellis與Cliffird Cocks, 設計出演算法 1974, Malcolm, 發展出非對稱性金鑰密碼學 1997,公開的文件發現CSEG早在1970 美國國家安全局 (National Security Agency, NSA) 1970, 也在發展非對稱金鑰密碼系統

非對稱性金鑰密碼學的簡史 在1977年,Ron Rivest、Adi Shamir 和Len Adleman 在 MIT 時發展出第一個主要的非對稱性金鑰密碼學系統 基於 Diffie 和 Hellman 理論的框架 並在 1978 年發表他們的結果。這個機制被稱為 RSA演算法

非對稱性金鑰密碼學的簡史 RSA 是被廣泛接受的公開金鑰機制 解決了金鑰協議和分配的問題

非對稱性金鑰密碼學總覽 非對稱性金鑰密碼學 (Asymmetric Key Cryptography) 公開金鑰密碼學 (Public Key Cryptography) 金鑰對 (key pair) 公開金鑰 (public key) 散佈給任何人都可以取得 用於加密 私密金鑰 (private key) 個人保存 用於解密

非對稱性金鑰密碼學的運作 當A想要寄出訊息給B,A使用B的公開金鑰加密訊息。(因為A知道B的公開金鑰) A寄出這個訊息給B。(已經用B的公開金鑰加密的訊息) B使用B的私密金鑰解密A的訊息。(只有B知道自己的私密金鑰) 只有B才有解開密文訊息的私密金鑰,故傳輸過程中的訊息對任何人是沒有意義的。

非對稱性金鑰密碼學的運作

非對稱性金鑰密碼學的運作 若B要傳送訊息給A 使用相同的步驟,但是B使用A的公開金鑰加密訊息,A收到B傳送過來的密文訊息,A使用A的私密金鑰解開密文。

私密與公開金鑰 私密金鑰:用於解密 公開金鑰:用於加密

RSA演算法 RSA演算法為目前最受歡迎的非對稱性金鑰密碼學演算法 RSA基於整數因數分解的問題 RSA使用大質數來產生金鑰

質數 所謂質數是指只能被 1 和自己整除的數 例如 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,…

RSA演算法原理 基於數學事實,整數因數分解問題 找大質數並相乘是容易,但要從乘積中進行因數分解是非常困難的

RSA演算法的使用流程

RSA金鑰產生步驟 選擇兩個大質數 P 和 Q 計算 N = P * Q 選擇公開金鑰 E,使它不是一個 (P – 1) 和 (Q – 1) 的因數 選擇私密金鑰 D,使下列的恒等式為真 (D * E) mod (P – 1) * (Q – 1) = 1

RSA加解密步驟 在加密中,從明文 PT 計算密文 CT CT = PTE mod N 將密文 CT 寄給接收方 在解密中,從密文 CT 計算明文 PT PT = CTD nod N

範例(步驟1, 2) 選擇兩個大質數 P 和 Q P = 47, Q = 71 計算 N = P * Q N = 47 * 71 = 3337

範例(步驟3) 選擇公開金鑰 E,使它不是一個 (P – 1) 和 (Q – 1) 的因數 (47 – 1) * (71 – 1) = 46 * 70 = 3220 3220 的因數為 2, 2, 5, 7, 23 3220 = 2 * 2 * 5 * 7 * 23 選擇 E 不包含上述因數 Ex: 4 (含2), 15 (含5), 14 (含2, 7), 69 (含23)不可選 E = 79

範例(步驟4) 選擇私密金鑰 D,使下列的恒等式為真 (D * E) mod (P – 1) * (Q – 1) = 1 在恆等式替換 E = 79, P = 47, Q = 71 (D * 79) mod (47 – 1) * (71 – 1) = 1 (D * 79) mod (46 * 70) = 1 (D * 79) mod 3220 = 1 經過計算 D = 1019 (1019 * 79) mod 3220 = 80501 mod 3220 = 1

範例(步驟5) 在加密中,從明文 PT 計算密文 CT CT = PTE mod N 假設明文 PT = 688 E = 79, N = 3337 CT = 68879 mod 3337 = 1570 得到密文 1570

範例(步驟6) 將密文 CT 寄給接收方 傳送 1570 給對方

範例(步驟7) 在解密中,從密文 CT 計算明文 PT PT = CTD nod N 取得密文 CT = 1570 D = 1019, N = 3337 PT = 15701019 mod 3337 = 688 解回明文 688

實例 E = 5 D = 77 N = 119 字母編碼 A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, ……, Z = 26

RSA的關鍵 RSA的演算法很簡單,因此關鍵在金鑰 金鑰的產生由 P, Q (兩個質數) 得來 N = P * Q 且產生公開金鑰(E)與私密金鑰(D) N, E 是公開的 攻擊者可由 N, E 來推得 D?

RSA的關鍵 RSA的關鍵在於當 P, Q 選擇數字很大時 要將 N 分解成 P, Q 是很困難的 因此要找到 D 必須依賴 P, Q, E

RSA金鑰長度 1997年以後設計的系統採 政府機關公開金鑰基礎建設憑證政策 一般使用者:1024位元 憑證認證機構:2048位元 100年1月1日起簽發使用2048位元憑證 原先1024位元憑證使用至到期為止

RSA已知的攻擊 針對RSA的攻擊是基於大數因數分解 1999年,RSA-155(512 bits)被成功分解 花了五個月時間(約8000 MIPS 年)和224 CPU hours 在一台有3.2G中央內存的Cray C916計算機上完成 2002年,RSA-158也被成功因數分解 2009年12月12日, RSA-768 (768 bits, 232 digits)也被成功分解 已經威脅到1024位元的安全性

RSA-158 395058745832651445264197678006144819960207764603049364 541393760515793556265294506836097278424682195350935443 05870490251995655335710209799226484977949442955603 = 338849583746672139436839320467218152281583036860499304 8084925840555281177 × 116588234066712599031483765583832708181310122581463926 00439520994131344334162924536139

RSA-768 123018668453011775513049495838496272077285356959533479 219732245215172640050726365751874520219978646938995647 494277406384592519255732630345373154826850791702612214 291346167042921431160222124047927473779408066535141959 7459856902143413 = 334780716989568987860441698482126908177047949837137685 689124313889828837938780022876147116525317430877378144 67999489 × 367460436667995904282446337996279526322791581643430876 426760322838157396665112792333734171433968102700927987 36308917

對稱性與非對稱性金鑰密碼學之間的比較

運算速度的比較 使用硬體設計 DES 比 RSA 快 1000 倍 使用軟體設計 DES 比 RSA 快 100 倍

兩個世界中的最佳 結合兩個密碼學機制,以得到兩者中的優點,但不犧牲兩者中的任何特色,我們需要確認符合下列的目標 解決方案應該完全安全 加密和解密的過程不需要花很長時間。 產生的密文不應太大 解決方案應該控制在能讓大多數人簡單地使用,無須多餘的複雜度 解決方案必須能解決金鑰分配問題

結合方法 使用對稱性金鑰演算法加解密訊息 使用非對稱性金鑰演算法來傳遞金鑰 同時傳遞訊息密文與金鑰包裝 金鑰包裝 (key wrapping) 同時傳遞訊息密文與金鑰包裝 數位信封 (digital envelope)

結合方法 (1/7)

結合方法 (2/7)

結合方法 (3/7)

結合方法 (4/7)

結合方法 (5/7)

結合方法 (6/7)

結合方法 (7/7)

數位簽章 使用RSA加解密演算法 公開私密金鑰 訊息傳遞者使用「公開金鑰」對訊息進行「加密(簽章) 」 訊息接收者使用「私密金鑰」對密文進行「解密(驗證) 」

數位簽章的基礎 公開金鑰 (簽章) 私密金鑰 (驗證)

訊息的隱藏與驗證 訊息的隱藏 訊息的驗證 假如 A 是一個訊息的發送方,B 是接收方,A 使用 B 的公開金鑰加密訊息,並寄出加密訊息給 B 若密文訊息被 C 竊取則 C 無法解密 訊息的驗證 假如 A 是一個訊息的發送方,B 是接收方,A 使用 A 的公開金鑰加密訊息,並寄出加密訊息給 B B 可用 A 的私密金鑰將訊息解密 若密文訊息 C 被竄改則 B 解密失敗

訊息摘要 若將訊息使用公開金鑰加密作為簽章的驗證,則當明文很大時,速度非常緩慢 使用數位信封的方式進行簽章 使用對稱性金鑰(K1)加密訊息(PT)為密文(CT) 使用私密金鑰(K2)加密K1 建立數位信封傳送CT與加密後的K1 使用公開金鑰(K3)解開得到K1 使用K1解密密文(CT)得到訊息(PT)

訊息摘要 真實情況使用更有效率的作法 訊息摘要是一個訊息的指印(fingerprint)或是總結 類似 訊息摘要(message digest) 雜湊(hash) 訊息摘要是一個訊息的指印(fingerprint)或是總結 類似 縱向冗餘核對 (Longitudinal Redundancy Check, LRC) 回合冗餘核對 (Cyclic Redundancy Check, CRC) 用來確認資料的完整性

縱向冗餘核對(LRC) Longitudinal Redundancy Check, LRC 於一組字元相對應的位元串後附加一個同位元 計算行(垂直)中 1 的個數 個數為奇數稱為「奇同位元」(odd parity),標示為 1 個數為偶數稱為「偶同位元」(even parity),標示為 0

縱向冗餘核對(LRC) 同位元位元

縱向冗餘核對(LRC) 訊息傳遞先透過縱向冗餘核對(LRC)產生區塊的同位元位元 LRC(指同位元位元)則為原始訊息的指印 若相同則合理相信資料沒有被修改

訊息摘要的概念 訊息摘要基於LRC(或其他檢查碼技術)相同概念但作法更多元 概念 例如 透過設計的運算規則產生指印 指印無法透漏原始訊息的相關訊息 例如 原始訊息:4000 運算:除以1000 指印:4 訊息被改變無法得到正確的指印 只知道指印無法推得與原始訊息的關係 4+0+0+0 = 4 4000 / 1000 = 4 ……

訊息摘要簡單的例子 運算規則:取一個數與上次結果相乘並只留下各位數

訊息摘要的概念

訊息摘要的概念 資料區塊進行一個訊息摘要演算法(雜湊運算),會產生訊息摘要(或雜湊),其大小會小於原始訊息 訊息摘要不會很小且無法直接計算 訊息摘要通常包含128位元或更多 兩個訊息摘要要相同的機會是0到2128的任何數 訊息摘要長度要很長是有目的的 縮小兩個訊息摘要相同的範圍

訊息摘要的要求 給予一個訊息,應該要很容易找出對應的訊息摘要 對於同一個訊息,每次運算出的訊息摘要必須相同 給予一個訊息摘要,找出其原始訊息是很困難的 給予任兩個訊息,兩個的訊息摘要一定是不相同的 給予一個訊息與訊息摘要,不可能找到另一個訊息會產生相同的訊息摘要

訊息摘要的要求

訊息摘要的要求

訊息摘要的要求

訊息摘要的要求

碰撞 當給予兩個訊息,兩個的訊息摘是相同的時,稱為碰撞 訊息摘要演算法通常會產生訊息摘要的長度 任兩個訊息發生訊息摘要碰撞的機率 128位元 160位元 任兩個訊息發生訊息摘要碰撞的機率 1 / 2128 1 / 2160 實際發生碰撞非常罕見

訊息摘要的例子

訊息摘要演算法 原始訊息摘要演算法 (MD) 安全雜湊演算法 (SHA) 訊息鑑別碼 (MAC) 雜湊訊息鑑別碼 (HMAC)

The End