質數的應用 – RSA加密演算法 (一個價值21億美元的演算法)

Slides:



Advertisements
Similar presentations
變數與函數 大綱 : 對應關係 函數 函數值 顧震宇 台灣數位學習科技股份有限公司. 對應關係 蛋餅飯糰土司漢堡咖啡奶茶 25 元 30 元 25 元 35 元 25 元 20 元 顧震宇 老師 台灣數位學習科技股份有限公司 變數與函數 下表是早餐店價格表的一部分: 蛋餅 飯糰 土司 漢堡 咖啡 奶茶.
Advertisements

天国护照 《使徒信经》 系列活动课程.
第一單元 建立java 程式.
公開金鑰密碼系統 (Public-Key Cryptosystems)
質數的應用 – RSA加密演算法 國立中央大學 資工系 江振瑞.
密碼學與網路安全 第9章 公開金鑰密碼學與RSA
Chapter 1: 概論 1.1 密碼學術語簡介及假設
密碼學概論 Speaker:謝凱評.
4量子通信与加密.
量子计算机 林晓菲
電子資料保護 吳啟文 100年6月7日.
06資訊安全-加解密.
密码学基础 电子科技大学•计算机学院.
電子戶籍謄本申辦及驗證實務作業與問題討論
动漫课题 动漫power对青少年的影响.
崇拜即將開始,請大家安靜片刻, 預備心靈敬拜上帝。
第五組 做16歲、兩首詩 楊郁珊 陳怡蓁 吳政穎 洪珮綺.
計算機概論 蘇俊銘 (Jun Ming Su) 資料加密技術簡介 計算機概論 蘇俊銘 (Jun Ming Su)
公開鑰匙加密演算法 密碼學大革命 public key所想要解決的問題 public key密碼系統特性
穩定是指偏離平衡時能夠回復平衡的特性,控制則是改變飛行狀態的機制。
RSA-256bit Digital Circuit Lab TA: Po-Chen Wu.
密碼學簡介與簡單生活應用 Introduction to Cryptography & Simple Applications in Life 2010 Spring ADSP 05/07.
計算機概論 蘇木春 中央大學資工系.
RSA Cryptosystem Theorem 1.3: For n = p * q p,q 均是質數
網路與多媒體實驗 第一組報告 B 鄧鎮海 B 葉穎達
二、現代的加解密法:RSA 非對稱式密碼系統的一種。
密碼學 黃胤誠.
第三章 公钥基础设施PKI 本章学习重点掌握内容: 密码学基本术语 密码体制分类 私钥密码体制的主要特点 公钥密码体制的主要特点
公開金鑰密碼系統 Public Key Cryptosystem
本章大綱 9.1 Sequence數列 9.2 Infinite Series無窮級數
網站建置與資訊安全 電子商務資訊安全.
CH19資訊安全 認識資訊安全與其重要性 了解傳統與公開金鑰密碼系統, 以及基本的安全性觀念 了解訊息鑑別與雜湊函數 了解數位簽章法
資電學院 計算機概論 F7810 第十七章 資訊安全 陳邦治編著 旗標出版社.
秘密金鑰密碼系統 (Secret Key Cryptosystems)
密碼學與網路安全 第8章 數論介紹.
SSL加解密原理 姓名:林子鈞 指導老師:梁明章老師
基礎密碼學 非對稱式金鑰加密法 樹德科技大學 資訊工程系 林峻立 助理教授.
第三章 數據保密系統.
Cryptography 密碼學簡介 B 電機三 蕭旭君.
密碼學概論 電機四 b 吳秉寰.
第一章 直角坐標系 1-1 數系的發展.
密碼學 Chapter 4 基於電腦的非對稱性金鑰密碼學演算法
第一單元 建立java 程式.
公開金鑰密碼系統 (Public-Key Cryptosystems)
RSA and Rabin.
資訊安全 與 線上付款機制 Part 1: 網路資訊安全.
第三章 暴力法.
公钥密码学与RSA.
DES算法.
應用加密技術 A 譚惠心 指導教授:梁明章教授.
Class & Object 靜宜大學資工系 蔡奇偉副教授 ©2011.
資訊安全技術 課程簡介.
資訊安全和資訊倫理宣導 永康區復興國小教務處.
電腦概論考題分析 佛學資訊組 碩一 張榮顯.
電子商務資訊安全 網路資訊安全.
網路安全技術 A 林建宏 指導教授:梁明章老師
10394: Twin Primes ★★★☆☆ 題組:Problem Set Archive with Online Judge
※歡迎挑戰,兩人(隊)中先完成連線即算過關!
_14RSA加密的基本原理 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
( )下列何者正確? (A) 7< <8 (B) 72< <82 (C) 7< <8 (D) 72< <82 C 答 錯 對.
資料表示方法 資料儲存單位.
因數與倍數.
資料結構與C++程式設計進階 期末考 講師:林業峻 CSIE, NTU 7/ 15, 2010.
張仁俊 (Jen-Chun Chang) 國立台北大學 資訊工程學系 通訊工程研究所 電機工程研究所
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Computer Security and Cryptography
11621 : Small Factors ★★☆☆☆ 題組:Problem Set Archive with Online Judge
第三章 比與比例式 3-1 比例式 3-2 連比例 3-3 正比與反比.
ABAP Basic Concept (2) 運算子 控制式與迴圈 Subroutines Event Block
Presentation transcript:

質數的應用 – RSA加密演算法 (一個價值21億美元的演算法) 國立中央大學 資工系 教授 江振瑞

RSA的發明人 (由左而右: Ronald Rivest, Adi Shamir, Leonard Adleman)

RSA的歷史 RSA加密演算法(RSA cryptography)在1977年由在MIT工作的羅納德·李維斯特(Ronard Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出,後來三人共同成立RSA Security Inc,在2006年被EMC公司以21億美元併購。 但是早在1973年,在英國政府通訊總部工作的數學家克利福德·柯克斯(Clifford Cocks)在一個內部檔案中提出了一個相同的演算法,他的發現被列入機密,一直到1997年才公開發表。 1983年MIT在美國為RSA演算法申請專利,這個專利在2000年9月21日到期。 2002年,Rivest、Shamir與Adleman三人獲得ACM圖靈獎(Turing Award),這是Nobel Prize of Computing。 Founded as an independent company in 1982, RSA Security, Inc. was acquired by EMC Corporation in 2006 for US$2.1 billion and operates as a division within EMC. RSA Security公司提出了8個巨大合成數 易安信公司(EMC Corporation;NYSE:EMC)為美國一家跨國資訊科技企業,主要提供數據存儲、資訊安全、虛擬化、雲計算等用於存儲、管理、保護和分析大量數據的產品和服務。EMC公司創建於1979年,總部設在麻薩諸塞州霍普金頓市。 英特爾前高管理察·伊根(Richard Egan)與大學室友羅傑·馬里諾(Roger Marino)在1979年創建公司。公司名稱EMC代表創始人的首寫字母,第三和第四創始人分別為Connelly和Curly,因此有EMC2。執行長Joseph Tucci在EMC World 2012大會上提到,公司的全稱是EMC Corporation。該公司的標誌參考愛因斯坦質能方程,亦採用指數2。 產品儲存系統、解決方案營業額▲232億美金(2013)[1]稅後盈餘▲29億美金(2013)[1]員工人數60,000 (2012)[2]子公司VMware RSA Security Pivotal

有關RSA RSA是一種非對稱加密演算法(asymmetric cryptography)或公開金鑰加密演算法(public key cryptography),是現今使用最廣泛的加密演算法之一。 RSA的觀念是每個使用者都擁有一把公鑰(public key)與一把對應的私鑰(private key),公鑰可以公開發布並隨意網路上傳輸並作為加密鑰匙(或稱加密金鑰),而私鑰則由使用者自行保存,並作為解密金鑰。 因為加密與解密使用的金鑰不同,因此稱為非對稱加密法;又因為加密金鑰可以公開發布,因此稱為公開金鑰加密法。

RSA的安全性 RSA加密演算法的安全性建立於對極大整數因數分解(factorization)的難度上。因此RSA是計算安全的(computationally secure)。 假如我們能夠找到快速針對大整數因數分解的演算法,那麼RSA的安全性就會極劇下降。 但找目前尚未找到在傳統計算機上執行的有效演算法可以做到快速地的大整數因數分解。現今只有短的RSA金鑰(例如長度512位元)才可能以強力方式(brute force)破解。 未來若量子計算機(quantum computer)能夠發展成功,則在其上執行秀爾演算法(Shor’s algorithm)則可快速進行大整數因數分解。 1999年,RSA-155 (512 bits)被成功分解,花了五個月時間(約8000 MIPS年)和224 CPU hours在一台有3.2G中央記憶體的Cray C916電腦上完成。

RSA金鑰的長度 RSA Security公司提出了8個巨大合數(composite number): RSA-640、RSA-704、RSA-768、RSA-896、RSA-1024、RSA-1536、RSA-2048,提供獎金開放給大眾進行質因數分解,用來驗證RSA的安全性。 這些合成數為兩個極大質數的乘積,一般的計算機根本無法在短時間內進行極大整數因數分解。在2009年12月12日,編號為RSA-768的合成數(768 bits, 232 digits)宣告分解成功,這一事件威脅了現在普遍通行的1024-bit金鑰的安全性,這代表使用者應儘快升級到2048-bit或以上的金耀。

RSA金鑰產生演算法 1. 選兩個相異大質數p和q,並計算n = pq //p和q最好長度相當,而且為100位數以上 2. 計算Euler’s Totient函數Ø(n)=(p-1)(q-1),並選一個與Ø(n)互質數 e,(e, n)為公鑰 //e: encryption //一般取e=3或65537; 加密法為C = Me mod n 3. 求出d,滿足 ed  1 (mod Ø(n)),(d, n)為私鑰 //d: decryption; 解密法為 M = Cd mod n C: ciphertext (密文) M: plaintext (明文)

RSA金鑰產生演算法簡單範例 1. 選兩個相異質數p=11和q=13,並計算n = pq=143 2. 計算Euler函數Ø(n)=(p-1)(q-1)=120,並選一個與Ø(n)互質數 e=23,(e, n)=(23, 143)為公鑰 //加密法為C = Me mod n //將明文訊息文字"X"加密: C=8823 mod 143=121 3. 求出d=47,滿足 ed  1 (mod Ø(n)),(d, n)=(47,143)為私鑰 //解密法為 M = Cd mod n //將密文訊息文字“y“解密: M= 12147 mod 143=88

歐拉函數 Euler’s function or Euler function or Euler totient function or Euler phi function 歐拉函數Ø(n): 小於或等於n的正整數中與n互質的總個數 範例: Ø(8)=4,因為1, 3, 5, 7均和8互質 範例: Ø(5)=4=5-1,因為1, 2, 3, 4均和5互質(5是質數,比5小的都與5互質) 歐拉函數特例: n = p  q 若p與q互質,則Ø(n) = Ø(pq) = Ø(p)Ø(q) = (p-1)(q-1) 範例: p與q互質且p=11, q=13, n = 11  13 = 143 Ø(143) = Ø(11  13) = Ø(11)  Ø(13) = (11-1)  (13-1) = 120

歐拉定理 Euler’s theorem or Euler theorem or Fermat–Euler theorem or Euler's totient theorem 歐拉定理: 若n與a為正整數,且n與a互質(即gcd(a, n)=1),則 aØ(n)  1 (mod n) 應用: 可用在簡化冪的模n運算,具體的說,當a和n互質時,可對a的指數取模Ø(n) 範例: 計算7666的個位數時,可將問題視為求7666除以10的餘數。因為7和10互質,且Ø(10)=4,故由歐拉定理可知74  1 (mod 10)。所以7666  74x166+2  72  49  9 (mod 10)。

歐拉 李昂哈德‧ 歐拉(Leonhard Euler,1707/4/15-1783/9/18)是一位瑞士數學家和物理學家。 1736: 解決柯尼斯堡七橋問題(一筆畫問題),是最早運用圖論(graph theory)和拓撲學(topology)的典範。(FE+V=2) 歐拉函數(n): 小於並n且與n互質的自然數的個數。(與RSA公鑰密碼演算法有關) 歐拉公式: 歐拉恆等式: 歐拉-馬歇羅尼常數 Source: http://en.wikipedia.org/wiki/File:Leonhard_Euler.jpg

RSA加解密系統相關演算法 大質數尋找演算法 模乘法反元素演算法 快速模冪(modular power)計算演算法 大質數尋找隨機演算法 質數檢驗演算法 模乘法反元素演算法 快速模冪(modular power)計算演算法

The End