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

Presentation on theme: "質數的應用 – RSA加密演算法 (一個價值21億美元的演算法)"— Presentation transcript:

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

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

3 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

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

5 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電腦上完成。

6 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或以上的金耀。

7 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 (明文)

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

9 歐拉函數 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

10 歐拉定理 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)。

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

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

13 The End