H922(Fri) 資訊安全

H922(Fri) 資訊安全

cryptography and network security principles and practice

使用Python程式語言
 *大學全面教Python

$ python
Python 2.7.3 (default, Oct 26 2016, 21:04:23)
...

>>> 10 // 3       # 取商
3
>>> 10 / 3
3
>>> 10 / 3.0
3.3333333333333335
>>> 10 % 3     # 取餘
1

 >>> 50**23     # 整數 沒有位數限制 ?!
1192092895507812500000000000000000000000L

RSA加密演算法

https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95

RSA加密演算法是一種非對稱加密演算法。在公開金鑰加密和電子商業中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當時他們三人都在麻省理工學院工作。RSA就是他們三人姓氏開頭字母拼在一起組成的。...


 以下均為整數

1. 找兩個夠大的質數 ${\displaystyle p}$和${\displaystyle q}$，兩者不相等，計算N=。
2.   = ( - 1)( - 1)
3. 讓 < ${\displaystyle r}$${\displaystyle e}$，兩者互質。並求${\displaystyle d}$, 令${\displaystyle ed\equiv 1{\pmod {r}}}$
4. 將${\displaystyle p}$和${\displaystyle q}$的記錄銷毀

${\displaystyle (N,e)}$

 (N, e)公鑰public key，(N, d) 是私鑰 (private key 或是 secret key)

公鑰(N, e)公開給別人用來加密用
私鑰(N, d)要保存好,用來解密用
A傳訊息給B

1. 明文 (未加密)
 A的 Text ==> 未加密(明文) ==>  傳送  ===> B 收到Text
 優點: 簡單不需要額外成本(加密/解密)...
 缺點: 訊息被取得,修改,違造...等問題

  2. 對稱加密
A的 Text ==> 加密(Key(Text)) ==>  傳送  ===> B 收到Key(Text),                                                                 B使用同一個Key解密 
 優點: 加解密 演算法 較容易 實作
 缺點: 雙方取得同一個Key的問題
 3. 非對稱加密
   A的 Text ==> 用B的公鑰加密 ==>  傳送  ===> B 收到密文,用B(自已)私鑰解開.
 優點: 加解密 公私鑰不同
 缺點: 加解密 演算法複雜且費時

 -----------------------------------------------------------------------------------------------
第一步 質數 問題 ...



Fermat little theorem 費馬小定理
https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

整數 1<a<p,  如果 p是質數, 則a ^p   除p 取餘 等於 a

${\displaystyle a^{p}\equiv a{\pmod {p}}.}$

例:   1 < a <  p,   a ^p = xxx,   xxx / p 餘 a
例: a = 2, p = 7,   2⁷ = 128,  128 / 7 餘 2
例: a = 3, p = 7,   3⁷ = 2187,  2187 / 7 餘 3

         a ^p / p 餘 a ,      同除 a
         a ^p-1 / p 餘 1  

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}.}$

例:   1 < a <  p,   a ^p-1 = xxx,   xxx / p 餘 1
例: a = 2, p = 7,   2^7-1 = 64,  64 / 7 餘 1
例: a = 3, p = 7,   3^7-1 = 729 ,  729 / 7 餘 1

--------------------------------------------------------------

使用Python

例: a = 2, p = 7,   2^7-1 = 64,  64 / 7 餘 1

 a ^p-1
可以使用 a**(p-1) 或 pow(a, p-1)

加入取餘之後,可以直接使用....
pow(a, p-1, p)
表示 a ^p-1 除 p 取餘   ==>  a ^p-1 mod p
註: pow(a, p-1) %7 與 pow(a, p-1, p)
 運算過程不太一樣, 一個要算出a**(p-1)真正的值
它可能非常的大要算很久 例: 723456234767 ** 234654778345234237

 pow(a, p-1, p) 可以邊取餘 邊算次方
 例: pow(5, 6, 7)
在算 5的6次方時,
1. 算5的2次方, 5*5 = 25 (超過7)先取餘 ,結果為 4.
2. 算5的3次方, 4*5 = 20 (超過7)先取餘 ,結果為 6.
3. 算5的4次方, 6*5 = 30 (超過7)先取餘 ,結果為 2.
4. 算5的5次方, 2*5 = 10 (超過7)先取餘 ,結果為 3.
5. 算5的6次方, 3*5 = 15 (超過7)先取餘 ,結果為 1.
 結果(餘數)為 1
運算過程不用真的算出 5的6次方的值.