1、Cryptography密碼學簡介B91901139 電機三 蕭旭君Cryptographyl緣起l名詞解釋l常見的加密解密法l密碼學的應用l未來發展HistoryCryptology=”隱藏隱藏(Kryptos)”+”訊息訊息(logos)”CryptographyCryptanalysis研究秘密通訊之學問研究秘密通訊之學問達到資訊的秘密性、可鑑定性達到資訊的秘密性、可鑑定性破解密碼系統、偽造訊息破解密碼系統、偽造訊息Terminology明文明文 m密文密文 cCipher text明文明文 mEncrypt加密加密 E(m)Decrypt解密解密 D(c)TerminologyEve發
2、送者發送者接收者接收者竊密者竊密者公共鑰匙公共鑰匙私密鑰匙私密鑰匙TerminologylSymmetric vs.Asymmetricex.y=3x-2 =x=(y+2)/3 y=11x(mod 53)=x=?lUnconditional Security vs.Computational Security怎樣才算安全?.無法在合理的時間內，用合理的資源解出的密碼無法在合理的時間內，用合理的資源解出的密碼Historical Ciphersl傳統加密方式主要分為兩大類：lTransposition 換位lSubstitution 代換l有名的傳統加密法：DES、FEALTranspositi
3、on Methodl依照某種特定規則重新排列明文lEx.I am a studentI m s u e ta a t d nSubstitution MethodlShift Cipher(Caesars Cipher)I CAME I SAW I CONQUEREDH BZLD H TZV H BNMPTDSDCSubstitution Method(contd)lHowevereasy to break!Public Key System-RSAlnamed after its inventors RonRivest,Adi Shamir and Len AdlemanlBase on N
4、umber Theory y=ex(mod N)=x=?沒有private key 很難求出xl有多難？大數的質因數分解 要解出N=pq 其中p q為兩大質數Public Key System-RSA位元時間(1GHz/s)301 秒601 年1001000 億年!事實上，運用平行處理及事實上，運用平行處理及一些篩選法則，可以大幅一些篩選法則，可以大幅提升檢驗的效率。提升檢驗的效率。但仍難以在可接受的時間但仍難以在可接受的時間內破解。內破解。若對N=pq的每一種可能加以檢驗，則我們需要由於由於RSA用到指數運算，用到指數運算，加密的過程耗費較多的時間，加密的過程耗費較多的時間，現行系統多先用現
5、行系統多先用RSA傳送傳送private key，再合併使用，再合併使用其他加密方式。其他加密方式。Public Key System-RSAl2002年10月7日，以破解加密術而著稱的D宣佈破解了美國RSA資料安全實驗室開發的64位密匙RC5-64l為了檢測 RSA 技術的安全性，一家專門研究RSA 技術的公司 RSA Security 提供獎金給成功分解公佈的 8 個巨大合成數的人。在2003年12月3日，一個德國機構成功分解了RSA-576全球全球33.1萬名電腦高手萬名電腦高手+4年的時間年的時間!RSA-576=1881 9881292060 7963838697 239461650
6、4 3980716356 3379417382 7007633564 2298885971 5234665485 3190606065 0474304531 7388011303 3967161996 9232120573 4031879550 6569962213 0516875930 7650257059=(3980750 8642406493 7397125500 5503864911 9906436234 2526708406 3851895759 4638895726 1768583317)*(4727721 4610743530 2536223071 9730482246 3291
7、469530 2097116459 8521711305 2071125636 3590397527)US10,000ApplicationlDigital Signatures 數位簽署lDigital Cash 電子錢包lTimestamping Services 電子時戳lElection 電子投票系統Digital Signaturel確保文件是由發送者送出l事後發送者無法否認，可由第三者確認l先用私密金匙加密，再用公共金匙解密A match making Protocol要如何達成共同的決議，而不用公開表述自己的意見？要如何達成共同的決議，而不用公開表述自己的意見？Ex.A和B透過朋
8、友C認識，相處了一天後，想知道彼此的心意，但又不敢先表態Future Workl量子電腦l0和1的狀態能同時並存，稱為疊加(superposition)。量子平行處理的概念，一個原子可以同時代表兩個狀態lEx.三個原子可同時代表000 001 010 011 100 101 110 111l龐大運算能力對現今的密碼系統是個致命的威脅l對系統的時間、振幅、相位要求嚴格Future Workl量子密碼術Step 1兩種發送光子的模式每一種都有兩個正交的偏振方向Future WorkStep 2Bob 隨機選擇兩種模式中的一種偵測光子如果Bob和Alice選擇的模式相同，Bob就會接收到正確的位元；
9、反之，偵測到的位元不可預測(可能為0或1)若Eve試圖竊聽，根據量子力學，會改變傳送光子的狀態，Alice和Bob可以選擇一些位元比較，驗證是否遭竊聽Quantum CryptographyStep 3Bob告訴Alice他選擇濾片的模式Alice回答Bob哪些是正確的把這些正確偵測到的位元取出，做為加密的密碼Quantum CryptographyReferencelNigel Smart,Cryptography:An Introduction,McGraw-Hill,2003l張紹勳,蔡志敏.演算法 入門與進階,松崗出版社l科學人月刊 no.36 量子傳訊 絕對機密l近代密碼學及其應用，松崗出版社lhttp:/
