自然辯證法課程演講公鑰密碼學理論的形成--從科學假說到科學理論

1、-從科學假說到科學理論 公元前5世紀，古希臘斯巴達出現(xiàn)原始的密碼器：最早的換位密碼術。 公元前1世紀，著名的愷撒(caesar)密碼被用于高盧戰(zhàn)爭中：簡單易行的單字母替代密碼。 二次世界大戰(zhàn)中，印第安納瓦霍土著語言被美軍用作密碼。這是密碼學和語言學的成功結合，納瓦霍語密碼成為歷史上從未被破譯的密碼。 1949年以前 密碼學是一種技巧（art） 1949-1975 標志：1949年shannon發(fā)表的保密系統(tǒng)的信息理論，密碼學成為科學 1976以后 標志：1976年diffie和hellman發(fā)表了密碼學新方向。代表了密碼學的新方向：公鑰密碼學 密碼編碼學(cryptography)明文(pla

2、intext)：原始的消息密文(ciphertext)：被偽裝的消息加密(encrypt/encipher)：明文轉換為密文的過程解密(decrypt/decipher)：密文還原為明文的過程算法(algorithm/cipher)：用于加密和解密的數(shù)學函數(shù)密鑰(key)：加密密鑰、解密密鑰加密e解密d公共信道秘密信道kkmmc=ek(m)公鑰密碼學理論的形成 科學問題的提出： 密鑰的安全分發(fā) 科學事實的獲?。?密鑰分發(fā)過程中存在的安全問題 科學假說的形成： 對稱密鑰下的密鑰分發(fā)機制kdc，復雜加密法，非對稱 密鑰算法（dh密鑰交換方法） 科學理論的創(chuàng)立： dh密鑰交換方法、rsa加密算法、其

3、他公鑰加密算法 古典密碼 現(xiàn)代密碼學： 流密碼分組密碼 密碼學新方向：公鑰密碼學 用于加密 用于密鑰交換 用于數(shù)字簽名caesar密碼 破譯以下密文：密文：phhw ph diwho wkh sduwb明文：meet me after the party 字母表：字母表：(密碼本）密碼本）密文：密文：d e f g h i j k l m n o p q r s t uvwx y zabc 明文：明文：a b c d e f g h i j k l m n o p q r s t u v w x y z i ： 0 1 2 3 4 5 6 7 8 9. 設密鑰為k：加密算法：c=e(k,p)=

4、(p+k)mod(26)解密算法：p=d(k,c)=(c-k)mod(26) 25個可能的密鑰k, k1，25英文中字母的使用頻率 02468101214a b c d e f g hi j k l mnop qr s t u v wx y z頻率頻率e使用最多；使用最多；然后是然后是t r n i o a s其他字母使用較少其他字母使用較少最少的是最少的是j k q x z攻破古典密碼的有效方法：字母頻率統(tǒng)計分析古典密碼弱點： 密鑰空間較小 安全性基于算法細節(jié) 不抗頻率分析密鑰分發(fā)：手工分發(fā) kerchoffs原則(1883)：加密算法應建立在算法的公開不影響明文和密鑰的安全的基礎上。 古典

5、密碼 現(xiàn)代密碼學： 流密碼分組密碼 密碼學新方向：公鑰密碼學 用于加密 用于密鑰交換 用于數(shù)字簽名對稱密碼算法分類 流密碼 (stream cipher) 每次加密數(shù)據(jù)流的一位或一字節(jié)，連續(xù)加密。ci=kipi 分組密碼 (block cipher) 加密算法的主要工作混淆和擴散 特點：對明文分組進行加密，密鑰長度56bits以上 例：des算法、aes算法、三重des算法 對稱加密的密鑰分配 破解算法的可能性大大降低，但是密鑰分發(fā)成為主要問題 在對稱加密系統(tǒng)中，通常要求通信的雙方alice和bob共享密鑰。 實現(xiàn)的方式：alice確定一個密鑰，并親自交給bob一個可信的第三方(trudy)負

6、責確定密鑰，并親自交個alice和bob。alice和bob之前已經建立了秘密通道，則alice使用該秘密通道將新密鑰發(fā)送給bob。trudy和alice以及bob間有秘密通道，則trudy利用秘密通道將密鑰發(fā)送給alice和bob。密鑰分發(fā)過程中的安全問題：截斷截斷 監(jiān)聽監(jiān)聽篡改篡改 偽裝偽裝安全攻擊 古典密碼 現(xiàn)代密碼學： 流密碼分組密碼 密碼學新方向：公鑰密碼學 用于加密 用于密鑰交換 用于數(shù)字簽名公鑰密碼學公鑰密碼學 公鑰密碼體制的建立 經典公鑰加密算法-rsa算法 數(shù)字簽名和認證協(xié)議（保證通信雙方的真實性、公鑰的真實性） 1976年，迪菲（diffie）和赫爾曼(hellman)兩人

7、（論文“new direction in cryptography”），把密鑰分為加密的公鑰和解密的私鑰，這是密碼學的一場革命。 1977年，美國的里維斯特(ronald rivest)、沙米爾(adi shamir)和阿德爾曼(len adleman)，提出第一個較完善的公鑰密碼體制rsa體制 密碼學革命的代表人物：diffie(1944-)1965年，獲得麻省理工學院數(shù)學學士學位1976年，和hellman聯(lián)合發(fā)表密碼學新方向1991年，任職于sun公司1992年，1992年瑞士聯(lián)邦理工學院授予博士頭銜。 diffie考慮的問題：1.加密過程中密鑰分發(fā)問題手工分發(fā)不符合實際情況，而kdc的

8、存在意味著通信雙方的隱私會被第三方監(jiān)視。2.“數(shù)字簽名”問題：尋找一個正確判斷消息來源的方法，即象手寫簽名一樣，以保證消息卻是出自特定的人。1.alice把消息放到箱子里，用自己的鎖鎖上發(fā)送給bob2.bob收到箱子后加上自己的鎖，在把箱子返回給alice3.alice除掉自己的鎖，再把箱子寄給bob4.bob除掉自己的鎖，讀取消息復雜加密法復雜加密法復雜加密法復雜加密法1.alice把消息放到箱子里，用自己的鎖鎖上發(fā)送給bob2.bob收到箱子后加上自己的鎖，在把箱子返回給alice3.alice除掉自己的鎖，再把箱子寄給bob4.bob除掉自己的鎖，讀取消息復雜加密法復雜加密法1.alic

9、e把消息放到箱子里，用自己的鎖鎖上發(fā)送給bob2.bob收到箱子后加上自己的鎖，在把箱子返回給alice3.alice除掉自己的鎖，再把箱子寄給bob4.bob除掉自己的鎖，讀取消息復雜加密法復雜加密法1.alice把消息放到箱子里，用自己的鎖鎖上發(fā)送給bob2.bob收到箱子后加上自己的鎖，在把箱子返回給alice3.alice除掉自己的鎖，再把箱子寄給bob4.bob除掉自己的鎖，讀取消息一種新型算法：不對稱密鑰（公鑰密碼） 加密步驟：每一用戶產生一對密鑰，用來加密和解密信息每一用戶將其中一個密鑰存于公開的寄存器或其他可訪問的文件中，該密鑰稱為公鑰，另一密鑰是私有的。每一用戶可以擁有若干其

10、他用戶的公鑰。若bob要發(fā)消息給alice，則bob用alice的公鑰對信息加密。alice收到消息后，用其私鑰對消息解密。由于只有alice知道其自身的私鑰，所以其他的接收者均不能解密出消息。利用這種方法，通信各方均可訪問公鑰，而私鑰是各通信方在本地產生的，所以不必進行分配。只要用戶的私鑰受到保護，保持秘密性，那么通信就是安全的。關鍵：合適的單向陷門函數(shù) 現(xiàn)實生活中的例子單向路：只允許沿著一個方向走（加密），但你不能沿著反方向走（解密）。電話號碼本：很容易根據(jù)人名找到電話號碼（加密），但是根據(jù)號碼找對應的人很難（解密）。 單向函數(shù)：函數(shù)值計算很容易逆計算是不可行的。 單向陷門函數(shù)：函數(shù)值計算

11、很容易若知道某種附加的信息，則逆計算是可行的，否則不可行。 問題在于：理論上可行，但是現(xiàn)實中找不到這樣一個合適的能夠使不對稱密碼成為可能的函數(shù)。 公開這一思想以尋找合適的函數(shù)。 rsa三人組：里維斯特（計算機學家）、沙摩爾（計算機學家）和阿德爾曼（數(shù)學家）公鑰密碼學的八卦：據(jù)說公鑰密碼學是他們創(chuàng)立的 公鑰密碼學據(jù)說是他們最早發(fā)明的馬爾科姆威廉姆生1975年和前者合作發(fā)現(xiàn)了dh密鑰交換方法克利福德.科克思1973年發(fā)現(xiàn)了rsa算法詹姆斯.埃利斯1969年提出公鑰算法模型 數(shù)字簽名 數(shù)字簽名具有認證的功能 算法：dss、dsa 認證協(xié)議 相互認證 單向認證 其它公鑰加密算法 橢圓曲線密碼學 針對公