質數的應用 – RSA加密演算法 國立中央大學 資工系 江振瑞

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個巨大合成數

有關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) 應用: 在簡化冪的模運算的時候，當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

The End