密码学简介解读课件

Cryptography密碼學簡介B91901139電機三蕭旭君Cryptography密碼學簡介1Cryptography緣起名詞解釋常見的加密解密法密碼學的應用未來發展Cryptography緣起2HistoryCryptology

=”隱藏(Kryptos)”+”訊息(logos)”CryptographyCryptanalysis研究秘密通訊之學問達到資訊的秘密性、可鑑定性破解密碼系統、偽造訊息HistoryCryptology=”隱藏(Krypto3Terminology明文m密文cCiphertext明文mEncrypt加密E(m)Decrypt解密D(c)Terminology明文m密文cCiphertext4TerminologyEve發送者接收者竊密者公共鑰匙私密鑰匙TerminologyEve發送者接收者竊密者公共鑰匙私密鑰5TerminologySymmetricvs.Asymmetric ex.y=3x-2=>x=(y+2)/3 y=11x(mod53)=>x=??UnconditionalSecurity vs.ComputationalSecurity 怎樣才算安全?......無法在合理的時間內，用合理的資源解出的密碼TerminologySymmetricvs.Asymm6HistoricalCiphers傳統加密方式主要分為兩大類：Transposition換位Substitution代換有名的傳統加密法：DES、FEALHistoricalCiphers傳統加密方式主要分為兩大7TranspositionMethod依照某種特定規則重新排列明文Ex. Iamastudent

Imsuet aatdnTranspositionMethod依照某種特定規則重新8SubstitutionMethodShiftCipher(Caesar’sCipher) ICAMEISAWICONQUERED HBZLDHTZVHBNMPTDSDCSubstitutionMethodShiftCiphe9SubstitutionMethod(cont’d)However…easytobreak!!SubstitutionMethod(cont’d)How10PublicKeySystem-RSAnamedafteritsinventorsRon

Rivest,AdiShamirandLenAdlemanBaseonNumberTheoryy=ex(modN)=>x=??沒有privatekey很難求出x有多難？ 大數的質因數分解要解出N=pq其中pq為兩大質數PublicKeySystem-RSAnameda11PublicKeySystem-RSA位元時間(1GHz/s)301秒601年1001000億年!!事實上，運用平行處理及一些篩選法則，可以大幅提升檢驗的效率。但仍難以在可接受的時間內破解。若對N=pq的每一種可能加以檢驗，則我們需要…由於RSA用到指數運算，加密的過程耗費較多的時間，現行系統多先用RSA傳送privatekey，再合併使用其他加密方式。PublicKeySystem-RSA位元時間(1G12PublicKeySystem-RSA2002年10月7日，以破解加密術而著稱的D宣佈破解了美國RSA資料安全實驗室開發的64位密匙—RC5-64為了檢測RSA技術的安全性，一家專門研究RSA技術的公司RSASecurity提供獎金給成功分解公佈的

8個巨大合成數的人。

在2003年12月3日，一個德國機構成功分解了RSA-576全球33.1萬名電腦高手+4年的時間!!RSA-576=188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059=(398075086424064937397125500550386491199064362342526708406385189575946388957261768583317)*(472772146107435302536223071973048224632914695302097116459852171130520711256363590397527)US10,000PublicKeySystem-RSA2002年1013密码学简介解读课件14ApplicationDigitalSignatures數位簽署DigitalCash電子錢包TimestampingServices電子時戳Election 電子投票系統ApplicationDigitalSignatures15DigitalSignature確保文件是由發送者送出事後發送者無法否認，可由第三者確認先用私密金匙加密，再用公共金匙解密DigitalSignature確保文件是由發送者送出16Amatch–makingProtocol要如何達成共同的決議，而不用公開表述自己的意見？Ex.A和B透過朋友C認識，相處了一天後，想知道彼此的心意，但又不敢先表態…Amatch–makingProtocol要如何達成17FutureWork量子電腦0和1的狀態能同時並存，稱為疊加(superposition)。量子平行處理的概念，一個原子可以同時代表兩個狀態Ex.三個原子可同時代表 000001010011100101110111龐大運算能力對現今的密碼系統是個致命的威脅對系統的時間、振幅、相位要求嚴格FutureWork量子電腦18FutureWork量子密碼術Step1兩種發送光子的模式每一種都有兩個正交的偏振方向FutureWork量子密碼術Step119FutureWorkStep2Bob隨機選擇兩種模式中的一種偵測光子如果Bob和Alice選擇的模式相同，Bob就會接收到正確的位元；反之，偵測到的位元不可預測(可能為0或1)若Eve試圖竊聽，根據量子力學，會改變傳送光子的狀態，Alice和Bob可以選擇一些位元比較，驗證是否遭竊聽FutureWorkStep220QuantumCryptographyStep3Bob告訴Alice他選擇濾片的模式Alice回答Bob哪些是正確的把這些正確偵測到的位元取出，做為加密的密碼QuantumCryptographyStep321QuantumCryptographyQuantumCryptography22ReferenceNigelSmart,Cryptography:AnIntroduction,McGraw-Hill,2003張紹勳,蔡志敏.演算法入門與進階,松崗出版社科學人月刊no.36量子傳訊絕對機密近代密碼學及其應用，松崗出版社/rsalabs/node.asp?id=2093ReferenceNigelSmart,Cryptogr23Cryptography密碼學簡介B91901139電機三蕭旭君Cryptography密碼學簡介24Cryptography緣起名詞解釋常見的加密解密法密碼學的應用未來發展Cryptography緣起25HistoryCryptology

=”隱藏(Kryptos)”+”訊息(logos)”CryptographyCryptanalysis研究秘密通訊之學問達到資訊的秘密性、可鑑定性破解密碼系統、偽造訊息HistoryCryptology=”隱藏(Krypto26Terminology明文m密文cCiphertext明文mEncrypt加密E(m)Decrypt解密D(c)Terminology明文m密文cCiphertext27TerminologyEve發送者接收者竊密者公共鑰匙私密鑰匙TerminologyEve發送者接收者竊密者公共鑰匙私密鑰28TerminologySymmetricvs.Asymmetric ex.y=3x-2=>x=(y+2)/3 y=11x(mod53)=>x=??UnconditionalSecurity vs.ComputationalSecurity 怎樣才算安全?......無法在合理的時間內，用合理的資源解出的密碼TerminologySymmetricvs.Asymm29HistoricalCiphers傳統加密方式主要分為兩大類：Transposition換位Substitution代換有名的傳統加密法：DES、FEALHistoricalCiphers傳統加密方式主要分為兩大30TranspositionMethod依照某種特定規則重新排列明文Ex. Iamastudent

Imsuet aatdnTranspositionMethod依照某種特定規則重新31SubstitutionMethodShiftCipher(Caesar’sCipher) ICAMEISAWICONQUERED HBZLDHTZVHBNMPTDSDCSubstitutionMethodShiftCiphe32SubstitutionMethod(cont’d)However…easytobreak!!SubstitutionMethod(cont’d)How33PublicKeySystem-RSAnamedafteritsinventorsRon

Rivest,AdiShamirandLenAdlemanBaseonNumberTheoryy=ex(modN)=>x=??沒有privatekey很難求出x有多難？ 大數的質因數分解要解出N=pq其中pq為兩大質數PublicKeySystem-RSAnameda34PublicKeySystem-RSA位元時間(1GHz/s)301秒601年1001000億年!!事實上，運用平行處理及一些篩選法則，可以大幅提升檢驗的效率。但仍難以在可接受的時間內破解。若對N=pq的每一種可能加以檢驗，則我們需要…由於RSA用到指數運算，加密的過程耗費較多的時間，現行系統多先用RSA傳送privatekey，再合併使用其他加密方式。PublicKeySystem-RSA位元時間(1G35PublicKeySystem-RSA2002年10月7日，以破解加密術而著稱的D宣佈破解了美國RSA資料安全實驗室開發的64位密匙—RC5-64為了檢測RSA技術的安全性，一家專門研究RSA技術的公司RSASecurity提供獎金給成功分解公佈的

8個巨大合成數的人。

在2003年12月3日，一個德國機構成功分解了RSA-576全球33.1萬名電腦高手+4年的時間!!RSA-576=188198812920607963838697239461650439807163563379417382700763356422988859715234665485319060606504743045317388011303396716199692321205734031879550656996221305168759307650257059=(398075086424064937397125500550386491199064362342526708406385189575946388957261768583317)*(472772146107435302536223071973048224632914695302097116459852171130520711256363590397527)US10,000PublicKeySystem-RSA2002年1036密码学简介解读课件37ApplicationDigitalSignatures數位簽署DigitalCash電子錢包TimestampingServices電子時戳Election 電子投票系統ApplicationDigitalSignatures38DigitalSignature確保文件是由發送者送出事後發送者無法否認，可由第三者確認先用私密金匙加密，再用公共金匙解密DigitalSignature確保文件是由發送者送出39Amatch–makingProtocol要如何達成共同的決議，而不用公開表述自己的意見？Ex.A和B透過朋友C認識，相處了一天後，想知道彼此的心意，但又不敢先表態…Amatch–makingProtocol要如何達成40FutureWork量子電腦0和1的狀態能同時並存，稱為疊加(superposition)。量子平行處理的概念，一個原子可以同時代表兩個狀態Ex.三個原子可同時代表 000001010011100