密码系统简介

1資訊安全導論課程教材現代密碼：拉開數學序幕現代密碼：拉開數學序幕中興資科詹進科 (jkjancs.nchu.edu.tw)中興資管陳育毅 (chenyuyinchu.edu.tw)2資訊安全導論課程教材拉開數學序幕課程模組大綱拉開數學序幕課程模組大綱 回顧凱撒加密法(Caesar Cipher)回顧凱撒加密法(Caesar Cipher)-以數字表示 數學公式的變化 模乘法 數學小魔女一書有更完整的說明 在繼續介紹數論之前看個影片吧3資訊安全導論課程教材回顧凱撒加密法回顧凱撒加密法(Caesar Cipher)abcdzyxefabcdzyxefabcdzyxefabcdzyxef凱撒大帝凱撒大帝前方軍士前方軍士m e e t p h h w pmwtm e e t 明文：明文：meet me after the toga party密文：密文：phhw ph diwhu wkh wrjd sduwbpmwthh4資訊安全導論課程教材回顧凱撒加密法回顧凱撒加密法(Caesar Cipher)000102032524230405000102032524230405000102032524230405000102032524230405凱撒大帝凱撒大帝前方軍士前方軍士12040419150707221512221912040419明文：明文：meet me after the toga party密文：密文：phhw ph diwhu wkh wrjd sduwb151222190707若把英文字母改成以若把英文字母改成以 0025 數字表示數字表示5資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M+K)mod 26解密解密(Decryption)的公式的公式M=(C-K)mod 26回顧凱撒加密法回顧凱撒加密法(Caesar Cipher)000102032524230405000102032524230405000102032524230405000102032524230405h120404191507072212040419明文：明文：meet me after the toga party密文：密文：phhw ph diwhu wkh wrjd sduwb6資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M+K)mod 26解密解密(Decryption)的公式的公式M=(C-K)mod 26數學公式的變化數學公式的變化 模乘法模乘法 Sarah Flannery如果加密的公式換成如果加密的公式換成C=(M K)mod 26而解密是而解密是，這樣可行嗎？，這樣可行嗎？1999年愛爾蘭、歐洲青少年科學家首獎7資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M 5)mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery加密公式若是這樣的模乘法，加密公式若是這樣的模乘法，推算所有的可能，明文與密文推算所有的可能，明文與密文對應關係如右為對應關係如右為一對一對應一對一對應。若字母編碼若字母編碼0025，每個號碼，每個號碼都會對應到另一個都會對應到另一個0025之間之間的的號碼，也就是說任一明文號碼，也就是說任一明文字母會對應到某個密文字母。字母會對應到某個密文字母。1999年愛爾蘭、歐洲青少年科學家首獎8資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M 5)mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery1204041908202017明文：明文：meet me after the toga party密文：密文：iuur iu azruh rju rsea xahrq112 560 8 226 4 520 22620 4 520 22620 119 595 22617這樣就是加密啦！這樣就是加密啦！接下來，告訴你要怎麼解密接下來，告訴你要怎麼解密舉例來說舉例來說9資訊安全導論課程教材數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery明文：明文：meet me after the toga party密文：密文：iuur iu azruh rju rsea xahrq加密加密(Encryption)的公式的公式C=(M 5)mod 2612040419這樣就是加密啦！這樣就是加密啦！接下來，告訴你要怎麼解密接下來，告訴你要怎麼解密解密解密(Decryption)的公式的公式M=(C 5)mod 2608202017舉例來說舉例來說10資訊安全導論課程教材解密解密(Decryption)的公式的公式M=(C 5)mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery明文：明文：meet me after the toga party密文：密文：iuur iu azruh rju rsea xahrq08202017解密還不簡單解密還不簡單剛剛加密是乘以剛剛加密是乘以 5，那解密就除以那解密就除以 5 吧！吧！8 51.6糟糕，這樣糟糕，這樣#$%&不對！不對！哦，我搞錯了哦，我搞錯了除以除以5，就是乘以，就是乘以1/5，也就是要乘以也就是要乘以5的乘法反元素的乘法反元素，可是在可是在mod 26的情況下，的情況下，1/5不是不是5的乘法反元素。的乘法反元素。我再找找我再找找11資訊安全導論課程教材數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery明文：明文：meet me after the toga party密文：密文：iuur iu azruh rju rsea xahrq08202017120404198 221168 22612 220 221420 226 4 220 221420 226 4 117 221357 2261921才是才是5 mod 26的乘法反元素的乘法反元素解密解密(Decryption)的公式的公式 M=(C )mod 26 2112資訊安全導論課程教材解密解密(Decryption)的公式的公式 M=(C 21)mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery解解密公式若是這樣的模乘法，密公式若是這樣的模乘法，推算所有可能，密文對應回到推算所有可能，密文對應回到明文也正是明文也正是一對一對應一對一對應回去回去。也就是說解密的也就是說解密的 Key 是是21(加密與解密的加密與解密的Key不同哦不同哦)13資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M )mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery前面的例子也可以說是運氣好，前面的例子也可以說是運氣好，找到找到5與與21兩把兩把Key做模乘法能做模乘法能一對一對應。一對一對應。我們再來試一個例子，如果加密我們再來試一個例子，如果加密Key改為改為4，就沒有一對一對應。，就沒有一對一對應。也就是一個密文字母可能由兩種也就是一個密文字母可能由兩種明文字母對應而來，就無法判別明文字母對應而來，就無法判別如何解密回去，如何解密回去，這樣會失敗的！這樣會失敗的！414資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M K)mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery前面成功例子選前面成功例子選5與與21兩把兩把Key不是我運氣好，實際上是因為不是我運氣好，實際上是因為我懂數學，知道要能成功做出我懂數學，知道要能成功做出一對一對應的充分必要條件一對一對應的充分必要條件Key值必須與值必須與mod值互質值互質。解密解密(Decryption)的公式的公式M=(C K-1)mod 2615資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M K)mod 26數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery雖然用了乘法代替雖然用了乘法代替Caesar加密加密的加法，可是的加法，可是我沒說這個方法我沒說這個方法比比Caesar加密更安全唷加密更安全唷！因為！因為同樣使用暴力破解試同樣使用暴力破解試25次即可次即可解開密文。解開密文。不過，我能讓它更安全點不過，我能讓它更安全點解密解密(Decryption)的公式的公式M=(C K-1)mod 2616資訊安全導論課程教材加密加密(Encryption)的公式的公式C=(M K)mod 676數學公式的變化數學公式的變化 模乘法模乘法Sarah Flannery在在Playfair加密法課程中，我加密法課程中，我們看到加解密過程以兩個字母們看到加解密過程以兩個字母為單位，兩兩字母合在一起編為單位，兩兩字母合在一起編碼就有碼就有26 26=676種種(0675)可可能的數字，以這樣為單位，能的數字，以這樣為單位，Key可選擇的範圍就更大，當可選擇的範圍就更大，當然用暴力破解也就需要試更多然用暴力破解也就需要試更多次。所以如果以更多字母為單次。所以如果以更多字母為單位做加密，會越來越安全吧！位做加密，會越來越安全吧！解密解密(Decryption)的公式的公式M=(C K-1)mod 67617資訊安全導論課程教材數學小魔女一書有更完整的說明數學小魔女一書有更完整的說明Sarah Flannery到目前為止，雖然還沒有介紹到到目前為止，雖然還沒有介紹到怎麼設計出夠安全的現代密碼。怎麼設計出夠安全的現代密碼。可是很重要的，我們可是很重要的，我們全部都是用全部都是用數學來思考的數學來思考的，而這也就是現代，而這也就是現代密碼學的發展基礎，後續我們會密碼學的發展基礎，後續我們會一步步更深入介紹，這次例子的一步步更深入介紹，這次例子的完整說明可參考數學小魔女完整說明可參考數學小魔女一書。一書。