RSA非對稱加密演算法 (一) 運作方式

這是一種非對稱加密的演算法，非對稱加密就是指加密和解密使用不同的key
利用這種方式，再加上公正第三者就形成數位簽章的架構

以cable modem 的secure firmware upgrade為例
1.最頂層的人DOCSIS，大家都信任他，並保存它散佈出來的public key
2.今天有個叫MCA的公司要出一版image，他就產生一對key，private key留著，public key丟出來，
再加上一些屬性描述丟給DOCSIS簽名(*1)，取得CVC，之後再把CVC,image,以及MCA對這個image的簽
名包成CM可以吃的格式丟出來
3.CM收到這一堆東西後就可以開始驗證簽名(*2)，確認簽名是對的才會進行下一步，開始更新image(*3)




(*1)簽名就是把需要被驗證的內容算出hash候用private key加密後附上去
(*2)驗證簽名是用簽名者的public key解出簽名內容，再和需要被驗證的內容的hash比較，若相同則這個內容是可以信任的
(*3)CM secure firmware upgrade除了驗證簽名外還有一些內容要檢查，詳情在...
(**)CM還有用到另一種非對稱加密(Diffie-Hellman)用來產生snmpv3需要的pre share key



接下來紀錄一下RSA key的產生和簡單的例子(實際應用時以下所取的值會有一些規則用來加強安全性)


http://zh.wikipedia.org/wiki/RSA加密演算法

1.隨意選擇兩個大的質數p和q，p不等於q，計算N=pq。
2.根據歐拉函式，求得r= φ(N) = φ(p)φ(q) = (p-1)(q-1)
歐拉函式φ(N)，指的是小於N的正整數中與N互質的個數
例如φ(15)=φ(3*5)=(3-1)(5-1)=8
小於15與15互質的數有{1,2,4,7,8,11,13,14}這8個

3.選擇一個小於r的整數e，求得e關於模r的模反元素，命名為d。（模反元素存在，若且唯若e與r互質
e關於模r的模反元素，指的是 ed (mod r) = 1，d就是e的模反元素，可利用e,r作輾轉相除法求出

4.將p和q的記錄銷毀。(N,e)是公鑰，(N,d)是私鑰
使用openssl產生的key當中並沒有銷毀p q，保留p q可以在將來解密時加快速度

加密: 將m用(N,e)加密成C

C ≡ m^e (mod N)

解密: 將C用(N,d)運算就能算出原本的m

m ≡ C^d (mod N)

先不証明，直接舉簡單的例子試算
1. 取 p=5 q=11, N=5*11=55
2. φ(55)=(5-1)(11-1)=40
3. 取e=7,則d=23 7*23 (mod 40)=1

驗證輸入0~54加密後再解密是否能得到原來的值

#從bignum.kit取出的library
load bigint.dll 

set p 5
set q 11
set n [bigint::mul $p $q]
set r [bigint::mul [bigint::sub $p 1] [bigint::sub $q 1]]
set e 7
set d [bigint::invert $e $r]

# 這些變數經過bigint的運算後值會亂跳,所以迴圈的判斷式全部用上bigint運算
for {set i [bigint::convert 0]} {[bigint::cmp $n $i]} {set i [bigint::add $i 1]} {
  set c [bigint::powm $i $e $n]
  set m [bigint::powm $c $d $n]
  puts "i=$i\tc=$c\tm=$m"
}

從結果可以看出所有的數經過加密再解密會變回原本的值