密碼學1-2古典密碼課件

第1章密碼學引論

與古典密碼本章重點：掌握常用的古典密碼的加密解密。學時：4-6學時2022/10/1421.4幾種古典密碼隱寫術置換密碼（重點）代替密碼（重點）單表代替密碼多表代替密碼2022/10/143一、隱寫術隱寫術：將秘密消息隱藏在公開消息中，并通過公開渠道來傳送的方法。兩種隱藏明文信息的方法隱寫術密碼編碼學2022/10/144eg：詩情畫意傳“密語”

早妝未罷暗凝眉，

迎戶愁看紫燕飛，

無力回天春已老，

雙棲畫棟不如歸。2022/10/145王先生：來信收悉，你的盛情真是難以報答。我已在昨天抵達廣州。秋雨連綿，每天需備傘一把方能上街，苦矣。大約本月中旬我才能返回，屆時再見。eg：卡丹網格式密碼2022/10/146隱寫術特點簡單，掌握密鑰后，破譯簡單。易被攻擊。2022/10/147傳統(tǒng)的信息隱藏技術

古代信息隱藏的方法可以分為兩種:一種是將機密信息進行各種變換，使非授權者無法理解，這就是密碼術;

另一種是將機密信息隱藏起來，使非授權者無法獲取，如隱寫術等。

可以稱它們?yōu)楣糯艽a術和古代隱寫術。我們可以把它們的發(fā)展看成兩條線:一條是從古代密碼術到現代密碼學;一條是從古代隱寫術到信息隱藏、數字水印、隱通道和匿名通信。

古代隱寫術包括技術性的隱寫術、語言學中的隱寫術和用于版權保護的隱寫術。信息隱藏的發(fā)展歷史2022/10/148

1.技術性的隱寫術

技術性的隱寫術由來已久。大約在公元前440年，隱寫術就已經被應用了。據古希臘歷史學家希羅多德記載，一位希臘貴族希斯泰烏斯為了安全地把機密信息傳送給米利都的阿里斯塔格魯斯，慫恿他起兵反叛波斯人，想出一個絕妙的主意:剃光送信奴隸的頭，在頭頂上寫下密信，等他的頭發(fā)重新長出來，就將他派往米利都送信。類似的方法在20世紀初期仍然被德國間諜所使用。2022/10/149

實際上，隱寫術自古以來就一直被人們廣泛地使用。隱寫術的經典手法實在太多，此處僅列舉一些例子:

(1)使用不可見墨水給報紙上的某些字母作上標記來向間諜發(fā)送消息。

(2)在一個錄音帶的某些位置上加一些不易察覺的回聲。

(3)將消息寫在木板上，然后用石灰水把它刷白。

(4)將信函隱藏在信使的鞋底里或婦女的耳飾中。

(5)由信鴿攜帶便條傳送消息。

2022/10/1410(6)通過改變字母筆畫的高度或在掩蔽文體的字母上面或下面挖出非常小的小孔(或用無形的墨水印制作非常小的斑點)來隱藏正文。

(7)在紙上打印各種小像素點組成的塊來對諸如日期、打印機進行標識，將用戶標識符等信息進行編碼。

(8)將秘密消息隱藏在大小不超過一個句號或小墨水點的空間里。

(9)將消息隱藏在微縮膠片中。2022/10/1411(10)把在顯微鏡下可見的圖像隱藏在耳朵、鼻孔以及手指甲里;或者先將間諜之間要傳送的消息經過若干照相縮影步驟后縮小到微粒狀，然后粘在無關緊要的雜志等文字材料中的句號或逗號上。

(11)在印刷旅行支票時使用特殊紫外線熒光墨水。

(12)制作特殊的雕塑或繪畫作品，使得從不同角度看會顯示出不同的印像。

(13)利用掩蔽材料的預定位置上的某些誤差和風格特性來隱藏消息。比如，利用字的標準體和斜體來進行編碼，從而實現信息隱藏;將版權信息和序列號隱藏在行間距和文檔的其他格式特性之中;通過對文檔的各行提升或降低三百分之一英寸來表示0或1等。2022/10/14122.語言學中的隱寫術

語言學中的隱寫術也是被廣泛使用的一種方法。最具代表性的是“藏頭詩”，作者把表明真情實意的字句分別藏入詩句之中。如電影《唐伯虎點秋香》中唐伯虎的藏頭詩——“我畫藍江水悠悠，愛晚亭上楓葉愁。秋月溶溶照佛寺，香煙裊裊繞經樓?！苯裉?，這一“我愛秋香”的藏頭詩句已成

經典。

又如紹興才子徐文才在杭州西湖賞月時揮毫寫下了一首七言絕句——“平湖一色萬頃秋，湖光渺渺水長流。秋月圓圓世間少，月好四時最宜秋?！?022/10/1413

每句的第一個字連起來正好是“平湖秋月”。我國還有一種很有趣的信息隱藏方法，即消息的發(fā)送者和接收者各有一張完全相同的帶有許多小孔的掩蔽紙張，而這些小孔的位置是被隨機選擇并戳穿的。發(fā)送者將掩蔽紙張放在一張紙上，將秘密消息寫在小孔位置上，移去掩蔽紙張，然后根據紙張上留下的字和空格編寫一篇掩飾性的文章。接收者只要把掩蔽紙張覆蓋在該紙張上就可立即讀出秘密消息。直到16世紀早期，意大利數學家Cardan重新發(fā)展了這種方法，該方法現在被稱為卡登格子隱藏法。國外著名的例子是GiovanniBoccaccio(1313~1375年)創(chuàng)作的《Amorosa

visione》，據說是世界上最長的藏頭詩，他先創(chuàng)作了三首十四行詩，總共包含大約1500個字母，然后創(chuàng)作另外一首詩，使連續(xù)三行詩句的第一個字母恰好對應十四行詩的各字母。2022/10/14143.用于版權保護的隱寫術

版權保護與侵權的斗爭從古到今一直在延續(xù)著。

Lorrain(1600~1682年)是17世紀一個很有名的畫家，當時出現了很多模仿和假冒他的畫，他使用了一個特殊的方法來保護畫的版權。他自己創(chuàng)作了一本稱為《Liber

Veritatis》的素描集的書，它的頁面是交替出現的，四頁藍色后緊接著四頁白色，不斷重復，大約包含195幅畫。2022/10/1415

我國是最早發(fā)明印刷術的國家，而且許多西方國家也承認印刷術來自中國。書籍作為流通的商品且利潤豐厚，在漫長的歲月中不進行版權保護是無法想像的，也是不符合事實的。從法令來看，北宋哲宗紹圣年間(1095年)已有“盜印法”，中國自宋代就確有版權保護的法令。從實物來看，現存宋代書籍中可以證實版權問題。如眉山程舍人宅刊本《東都事略》，其牌記有:“眉山程舍人宅刊行，已申上司，不許覆板。”這就相當于“版權所有，不準翻印”。1709年英國國會制定的“圣安妮的法令”，承認作者是受保護的主體，這被認為是第一部“版權法”。2022/10/1416數字信息隱藏技術的發(fā)展

1992年，國際上正式提出信息隱藏的概念;1996年，在英國劍橋大學牛頓研究所召開了第一屆信息隱藏學術會議，標志著信息隱藏學的正式誕生。此后，國際信息隱藏學術會議在歐美各國相繼召開，至今已舉辦九屆之多。

作為隱秘通信和知識產權保護等的主要手段，信息隱藏從正式提出到現在十多年的時間里引起了各國政府、大學和研究機構的重視，取得了巨大的發(fā)展。美國的麻省理工學院、普渡大學、英國的劍橋大學、NEC研究所、IBM研究所都進行了大量的研究。在國內，許多高等院校和研究機構也對信息隱藏技術進行了深入的研究。從1999年開始，我國已召開了六屆全國性的信息隱藏學術研討會。2022/10/1417

國家863計劃智能計算機專家組會同中國科學院自動化研究所模式識別國家重點實驗室和北京郵電大學信息安全中心還召開了專門的“數字水印學術研討會”。

隨著理論研究的進行，相關的應用技術和軟件也不斷推出。如美國Digimarc公司在1995年開發(fā)了水印制作技術，是當時世界上唯一一家擁有這一技術的公司，并在Photoshop4.0和CoreDraw7.0中進行了應用。日本電器公司、日立制作所、先鋒、索尼和美國商用機器公司在1999年宣布聯合開發(fā)統(tǒng)一標準的基于數字水印技術的DVD影碟防盜版技術。DVD影碟在理論上可以無限制地復制高質量的畫面和聲音，因此迫切需要有效的防盜版技術。該技術的應用使消費者可以復制高質量的動態(tài)圖像，但以贏利為目的的大批量非法復制則無法進行。2000年，德國在數字水印保護和防止偽造電子照片的技術方面取得了突破。以制作個人身份證為例，一般要經過掃描照片和簽名、輸入制證機、打印和塑封等過程。2022/10/1418

上述新技術是在打印證件前，在照片上附加一個暗藏的數字水印。具體做法是在照片上對某些不為人注意的部分進行改動，處理后的照片用肉眼看與原來幾乎一樣，只有用專用的掃描器才能發(fā)現水印，從而可以迅速、無誤地確定證件的真?zhèn)?。該系統(tǒng)既可在照片上加上牢固的水印，也可以經改動使水印消失，使任何偽造企圖都無法得逞。由歐盟委員會資助的幾個國際研究項目也正致力于實用的水印技術研究，歐盟期望能使其成員國在數字作品電子交易方面達成協(xié)議，其中的數字水印系統(tǒng)可以提供對復制品的探測追蹤。在數字作品轉讓之前，作品創(chuàng)作者可以嵌入創(chuàng)作標志水印;作品轉讓后，媒體發(fā)行者對存儲在服務器中的作品加入發(fā)行者標志;在出售作品拷貝時，還要加入銷售標志。2022/10/1419

經過多年的努力，信息隱藏技術的研究已經取得了許多成果。從技術上來看，隱藏有機密信息的載體不但能經受人的感覺檢測和儀器設備的檢測，而且還能抵抗各種人為的蓄意攻擊。但總的來說，信息隱藏技術尚未發(fā)展到可大規(guī)模使用的階段，仍有不少理論和技術性的問題需要解決。到目前為止，信息隱藏技術還沒有形成自身的理論體系。比如，如何計算一個數字媒體或文件所能隱藏的最大安全信息量等。盡管信息隱藏技術在理論研究、技術開發(fā)和實用性方面尚不成熟，但它的特殊作用，特別是在數字版權保護方面的獨特作用，可以說是任何其他技術無法取代的，信息隱藏技術必將在未來的信息安全體系中獨樹一幟。2022/10/1420古典密碼學置換密碼代替密碼2022/10/1421二、置換密碼又稱換位密碼，指根據一定的規(guī)則重新排列明文。

特點：保持明文的所有字符不變，只是打亂了位置和次序。分類：列置換密碼周期置換密碼2022/10/14221、列置換密碼：將明文按照固定寬度n按行寫出，而后按照密鑰的規(guī)則按列換位。eg1：已知明文是‘Beijing2008OlympicGames’，密鑰k=6，e=(14)(56)。加密過程是：step1:將明文m按照寬度k分行。M=Beijing2008OlympicGamesstep2:將明文m按照e換行，得密文C=jeiBni020gO8pymlcieamGs2022/10/1423eg2：已知明文是‘thistext’，密鑰k=4，e=(2413)。加密過程：將明文按照4個字符一組分組，不足的部分填充*得：thistext第2個字符移位到位置4，第4個字符移到位置1，第1個字符移到位置3，第3個字符移到位置2；則密文：“sith

txte”(2)周期置換密碼：將明文m按照固定長度分組，對每組的字串按照某個置換重新排位從而得到密文。2022/10/1424練習ex：已知采用周期置換密碼加密，密鑰k=6,e=(15623)。如果明文是‘statek’，那么密文是什么？aKttSe如何解密？？？？2022/10/1425三、單表代換密碼就是明文中的字母由其他字母、數字或符號所取代的一種方法。算法：建立一個代換表，加密時將明文字符通過代換表代換為相應的密鑰文字。具體的代替表稱之為密鑰。2022/10/1426eg：設代換的對應關系如下：abcdefghijklmnopqrstuvwxyzidmefzoaphxbscqrltuyjvnwgk從代換的對應關系可知s→u，e→f，…，y→g因此以代換為密鑰對security加密得到密文ufmjtpyg2022/10/1427三、單表代換密碼字母與十進制數字的對應關系：2022/10/1428其中：m是明文，c是密文。3是加密所用的密鑰，加密時，每個字母向后移3位，解密時，每個字母向前移3位（均為循環(huán)移位）。1、凱撒密碼2022/10/1429eg1：通過愷撒（Caesar）密碼對明文加密：please則密文為：sohdvh2022/10/1430

eg2：設明文為：security，試用Caesar密碼對其進行加密，然后再進行解密。加密過程如字母s對應的數字為18，將18使用加密算法進行加密E3(18)≡18+3(mod26)≡21數字21對應的字母為v，所以security的密文為vhfxulwb(2)解密過程D3(21)≡21-3(mod26)≡182022/10/14312、移位變換特點：加密方法簡單。窮舉即可破譯。2022/10/14323、基于密鑰的單表代換密碼具體算法：選取一個字符串作為密鑰，除去密鑰中重復的字母，剩余字母按照順序寫在此字母之后生成字母表。特點：破譯難度較高。密鑰更改靈活。2022/10/1433eg：已知密鑰為‘magicnet’，對明文help加密。step1:生成字母表abcd

efgh

ijkl

mnop

qrst

uvwx

yz

magicnet

bdfh

jklo

pqrs

uvwx

yzstep2：按照字母表替換明文字符。明文：help

密文：tcho如何解密？2022/10/14344、仿射加密—擴展的移位變換加密：解密：密鑰為0~25之間的數字對(a,b)。要求：a與26的最大公約數必須為1，即gcd(a,26)=1。

a-1是a的逆元，即a-1*a(mod26)=1。2022/10/1435eg：仿射加密。設(a,b)=(7,21)，對明文‘security’加密。對‘vlxijh’解密。s=18,7*18+21(mod26)=17,sre=4,7*4+21(mod26)=23,exc=2,7*2+21(mod26)=9,cj……y=24,7*24+21(mod26)=7,yhsecurity對應的密文：rxjfkzyh2022/10/1436eg：仿射加密。設(a,b)=(7,21)，對明文‘security’加密。對‘vlxijh’解密。7-1mod26=?7*15mod26=17-1mod26=15v=21,15(21-21)mod26=0,val=11,15(11-21)mod26=6,lg……h(huán)=7,15(7-21)mod26=24,hyvlxijh對應的明文：agency2022/10/14370-25內所有與26互素元素的乘法逆元1-13-15-17-19-111-115-117-119-121-123-125-119211531972311517252022/10/1438練習ex:仿射加密。設(a,b)=(3,21)，對明文‘book’加密解密。單表代換分析密鑰空間增加(26!)，窮舉搜索這么多的密鑰很困難但這并不表示該密碼不容易破解破解這類密碼的突破點是由于語言本身的特點是充滿冗余的，每個字母使用的頻率不相等

而單表代換密碼沒有改變字母相對出現的頻率明文字母的統(tǒng)計特性在密文中能夠反映出來,當通過統(tǒng)計密文字母的出現頻率，可以確定明文字母和密文字母之間的對應關系英文字母統(tǒng)計特性英文單字母的相對頻率表單字母按照出現頻率的大小可以分為下面5類：

(1)e：出現的頻率大約為0.127(2)t,a,o,I,n,s,h,r：出現的頻率大約在0.06-0.09之間

(3)d,l：出現的頻率約為0.04(4)c,u,m,w,f,g,y,p,b：出現的頻率大約在0.015-0.028之間

(5)v,k,j,x,q,z：出現的頻率小于0.01英文字母統(tǒng)計特性雙字母和三字母組合都有現成的統(tǒng)計數據，常見的雙字母組合和三字母組合統(tǒng)計表能夠幫助破解密文。頻率最高的30個雙字母（按照頻率從大到小排列）：

thheineranreedones

stenattonthand

oueangasortiisetitar

tesehiof

頻率最高的20個3字母（按照頻率從大到小排列）：

theingandherereent

thanthwasethfordthhatsheioninthissth

ers

ver英文字母統(tǒng)計特性破解舉例例1

已知下面的密文式由單表代換生產的：UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZVUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSXEPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ，試破譯該密文首先統(tǒng)計密文中字母出現的頻率，然后與英文字母出現頻率比較。密文中字母的相對頻率統(tǒng)計如下：破解舉例將統(tǒng)計結果與頻率表進行比較，可以猜測密文中P與Z可能是e和t，密文中的S,U,O,M出現頻率比較高，可能與明文字母中出現頻率相對較高的a,o,I,n,s,h,r這些字母對應密文中出現頻率很低的幾個字母C,K,L,N,R,I,J可能與明文字母中出現頻率較低的字母v,k,j,x,q,z對應。就這樣邊試邊改，最后得到明文如下：itwasdisclosedyesterdaythatseveralinformalbutdirectcontactshavebeenmadewithpoliticalrepresentativesofthevietconginmoscow破解舉例在嘗試過程中，如果同時使用雙字母和三字母的統(tǒng)計規(guī)律，那么更容易破譯密文。如上面的密文中出現最多的雙字母是ZW，它可能對應明文雙字母出現頻率較大的th，那么ZWP就可能是the，這樣就更容易試出明文。破解舉例2022/10/1447以一些表依次對明文消息的字母序列進行代換的加密方法。明文中的同一個字母，由于出現的位置不同用不同的字母代替。四、多表代換密碼2022/10/14481、Playfair密碼算法設計：將明文字母按照兩個字母一組分組，然后將這些組按照字母矩陣替換為密文字母組合?；谝粋€5×5字母矩陣該矩陣使用密鑰來構造。2022/10/14491、Playfair密碼矩陣構造方法：從左至右，從上至下依次填入關鍵詞的字母，若字母重復則略過，然后再以字母表順序依次填入其他的字母。字母I和J被算作一個字母。表中的第1列看做是第5列的右邊1列，第1行看做第5行的下1行。2022/10/1450加密算法：P1、P2同行：對應的C1和C2分別是緊靠P1、P2右端的字母。其中第一列被看作是最后一列的右方。P1、P2同列：對應的C1和C2分別是緊靠P1、P2下方的字母。其中第一行看作是最后一行的下方。P1、P2不同行、不同列：C1和C2是由P1和P2確定的矩形的其它兩角的字母，并且C1和P1、C2和P2同行。P1＝P2：則插入一個字母于重復字母之間，并用前述方法處理.若明文字母數為奇數時：則在明文的末端添加某個事先約定的字母作為填充。2022/10/1451eg1：已知密鑰是：‘PLAYFAIR

IS

A

DIGRAM

CIPHER’。如果明文是‘playfaircipher’，為其加密。明文兩個一組：playfa

ir

cipher對應密文為:LAYFPYRSMRAMCD2022/10/1452ex：用Playfair算法加密明文“playfaircipher”,密鑰是fivestars。練習2022/10/14532022/10/1454

明文playfaircipher密文qkbwitvaasokvb2022/10/1455Playfair密碼的特點有676種雙字母組合，因此識別各種雙字母組合要困難得多。各個字母組的頻率要比單字母呈現出大得多的范圍，使得頻率分析困難得多。Playfair密碼仍然使許多明文語言的結構保存完好，使得密碼分析者能夠利用。2022/10/14562、維吉尼亞密碼算法設計：設N是某固定的正整數，已知密鑰有N個字符，K=(k1,k2,…,kN)。將明文M按照N個字符一組分段，分為L段，M=(m1,m2,…,mL)。求密文C，其中Cij=kj+mij,i<=L,j<=N。2022/10/1457eg：已知密鑰字是CIPHER，n＝6。假定明文串是：‘thissystem’。3、相應的密文串將是:

vpxzwpubtt加密過程：1、密鑰字轉換為數字為：281574172、將明文串轉化為數字串，按6個一組分段，然后加上密鑰字模26。19 7 8 18 18 242 8 15 7 4 1721 15 23 25 22 1518 19 4 122 8 15 720 1 19 192022/10/1458解密過程：1、密鑰字轉換為數字。2、將密文串轉化為數字串，按密鑰字個數分組，然后減去密鑰字模26。ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJABCDEFGHIJKLMNOPQRSTUVWXYZBCDEFGHIJKLMNOPQRSTUVWXYZACDEFGHIJKLMNOPQRSTUVWXYZABDEFGHIJKLMNOPQRSTUVWXYZABCEFGHIJKLMNOPQRSTUVWXYZABCDFGHIJKLMNOPQRSTUVWXYZABCDEGHIJKLMNOPQRSTUVWXYZABCDEFHIJKLMNOPQRSTUVWXYZABCDEFGIJKLMNOPQRSTUVWXYZABCDEFGHJKLMNOPQRSTUVWXYZABCDEFGHI…………Vigenere替換表密鑰:deceptive明文:wearediscoveredsaveyourself密文:明文密鑰deceptivedeceptivedeceptivewearediscoveredsaveyourselfzicvtwqngrzgvtwavzhcqyglmgj練習：Vigenere密碼使用Vigenere密碼加密單詞explanation，密鑰為leg。密鑰：legleglegle明文：explanation密文：PBVWETLXOZRVigenere密碼的安全性

維吉尼亞密碼是將每個明文字母映射為幾個密文字母如果密鑰字的長度是m，明文中的一個字母能夠映射成這m個可能的字母中的一個密文中字母出現的頻率被隱蔽了，它的安全性明顯比單表代換密碼提高了維吉尼亞密碼的密鑰空間比較大，對于長度是m的密鑰字，密鑰空間為26m

當m=5，密鑰空間所含密鑰的數量大于1.1x107

2022/10/14623、Hill密碼明文：密文：其中，

……2022/10/1463矩陣形式：加密：解密：2022/10/1464示例eg1：逆矩陣mod26的含義。k=11837k-1=7182311kk-1=11*7+8*2311*18+8*113*7+7*233*18+7*11=261286=1018