第2章密碼學(xué)概述2.1基本概念2.2密碼體制分類2.3代換密碼2.4換位密碼2.5古典密碼 2.1基本概念

密碼學(xué)(Cryptology)是研究信息系統(tǒng)安全保密的科學(xué),是對(duì)信息進(jìn)行編碼以實(shí)現(xiàn)隱蔽信息的一門學(xué)問。采用密碼方法可以隱蔽和保護(hù)需要保密的消息,使未授權(quán)者不能提取信息。相對(duì)于密碼學(xué)學(xué)科的定義,這里我們給出信息安全學(xué)科的定義,即信息安全就是利用密碼學(xué)中提供的算法來實(shí)現(xiàn)信息在存儲(chǔ)、傳輸、處理等過程中不被損壞的一門學(xué)科。一個(gè)密碼算法通常包括兩部分:加密算法和解密算法。對(duì)明文進(jìn)行加密時(shí)所采用的一組規(guī)則稱做加密算法;對(duì)密文進(jìn)行解密時(shí)所采用的一組規(guī)則稱做解密算法。加密和解密算法的操作通常都是在一組密鑰的控制下進(jìn)行的,這組密鑰分別被稱做加密密鑰和解密密鑰。

根據(jù)密鑰可以將密碼體制分為兩類:傳統(tǒng)密碼體制所用的加密密鑰和解密密鑰相同,因此也稱其為單鑰或?qū)ΨQ密碼體制;若加密密鑰和解密密鑰不相同,從一個(gè)難以推出另一個(gè),則稱為雙鑰或非對(duì)稱密碼體制。不管是哪一類密碼體制,密鑰都是其安全保密的關(guān)鍵,它的產(chǎn)生和管理是密碼學(xué)中的重要研究課題。一個(gè)保密系統(tǒng)由以下部分組成:

(1)明文消息空間M;

(2)密文消息空間C;

(3)密鑰空間K1和K2,在單鑰體制下K1=K2=K,此時(shí)密鑰k∈K需經(jīng)安全的密鑰信道由發(fā)方傳給收方;

(4)加密變換 ,M→C,其中k1∈K1,由加密器完成;

(5)解密變換∈D,C→M,其中k2∈K2,由解密器實(shí)現(xiàn)。

我們稱六元組為一個(gè)保密系統(tǒng)。(2.1.1)接收端利用通過安全信道送來的密鑰k(單鑰體制下)或本地密鑰發(fā)生器產(chǎn)生的解密密鑰k2∈K2(雙鑰體制下)控制解密操作D,對(duì)收到的密文進(jìn)行變換而得到恢復(fù)的明文消息:(2.1.2)

對(duì)攻擊者而言,如其選定變換函數(shù)h對(duì)截獲的密文c進(jìn)行變換,則得到的明文是明文空間中的某個(gè)元素m′,滿足:且(2.1.3)防止消息被篡改、刪除、重放和偽造的一種有效方法是使發(fā)送的消息具有被驗(yàn)證的能力,使接收者或第三者能夠識(shí)別和確認(rèn)消息的真?zhèn)?通常將實(shí)現(xiàn)這類功能的密碼系統(tǒng)稱做認(rèn)證系統(tǒng)。其最主要的技術(shù)是數(shù)字簽字。一個(gè)安全的認(rèn)證系統(tǒng)應(yīng)滿足下述條件:

(1)意定的接收者能夠檢驗(yàn)和證實(shí)消息的合法性與真實(shí)性。

(2)消息的發(fā)送者對(duì)所發(fā)送的消息不能抵賴。

(3)除了合法的消息發(fā)送者外,其他人不能偽造合法的消息。

(4)必要時(shí)可由第三者作出仲裁。

信息系統(tǒng)的安全除了上述保密性和認(rèn)證性外,還有一個(gè)重要方面就是它的完整性。完整性是指在有自然和人為干擾的條件下,系統(tǒng)保持恢復(fù)消息和原來發(fā)送消息一致性的能力。

2.2密碼體制分類

根據(jù)密鑰個(gè)數(shù),密碼體制一般可分為兩大類,即單鑰體制(One－keySystem)和雙鑰體制(Two－keySystem)。當(dāng)然,最近研究人員還提出了一些多密鑰體制(Multi－keySystem),主要用于安全組播。因?yàn)槎嗝荑€體制是一個(gè)新生事物,作為與傳統(tǒng)的單鑰和雙鑰體制并列的一種獨(dú)立體制還沒有得到大多數(shù)研究人員的認(rèn)同(盡管也沒有人反對(duì)多密鑰體制),所以這里我們暫不介紹多密鑰體制,在第5章中再作詳細(xì)介紹。

單鑰體制的加密密鑰和解密密鑰相同,系統(tǒng)的安全性主要取決于密鑰的保密性,必須通過安全、可靠的途徑(如信使遞送)將密鑰送至接收端。單鑰體制對(duì)明文消息進(jìn)行加密有兩種方式:一是明文消息按字符(如二元數(shù)字)逐位地加密,稱之為流密碼;另一種是將明文消息分組(含有多個(gè)字符),逐組進(jìn)行加密,稱之為分組密碼。

第一個(gè)發(fā)展階段的密碼體制稱為古典密碼,其特點(diǎn)如下:

(1)密碼學(xué)還不是科學(xué),而是藝術(shù)。

(2)出現(xiàn)了一些密碼算法和加密設(shè)備。

(3)密碼算法的基本手段出現(xiàn),針對(duì)的是字符。

(4)簡單的密碼分析手段出現(xiàn)。

(5)數(shù)據(jù)的安全基于算法的保密。圖2.2.1

Phaistos圓盤圖2.2.2

20世紀(jì)初期使用的加密機(jī)第二個(gè)階段的技術(shù)背景是:計(jì)算機(jī)使得基于復(fù)雜計(jì)算的密碼成為可能。其相關(guān)技術(shù)的發(fā)展主要包括三個(gè)標(biāo)志性成果:1949年Shannon的“TheCommunicationTheoryofSecretSystems”，1967年DavidKahn的“TheCodebreakers”，1971~1973年IBMWatson實(shí)驗(yàn)室的HorstFeistel等人的幾篇技術(shù)報(bào)告。該階段的主要特點(diǎn)是:數(shù)據(jù)的安全基于密鑰的保密,而不是算法的保密。

第三個(gè)階段的飛躍思想為:1976年Diffie和Hellman在其論文“NewDirectionsinCryptography”中提出的不對(duì)稱密鑰密碼。此后,1977年Rivest、Shamir和Adleman提出了RSA公鑰算法。20世紀(jì)90年代逐步出現(xiàn)了橢圓曲線等其他公鑰算法。該階段的主要特點(diǎn)是:公鑰密碼使得發(fā)送端和接收端無密鑰傳輸?shù)谋Ｃ芡ㄐ懦蔀榭赡堋Ｔ诘谌A段,除了提出公鑰加密體制外,在對(duì)稱算法方面也有很多成功的范例,主要包括:1977年DES算法正式成為標(biāo)準(zhǔn);20世紀(jì)80年代出現(xiàn)“過渡性”的“PostDES”算法,如IDEA、RCx、CAST等;20世紀(jì)90年代對(duì)稱密鑰密碼進(jìn)一步成熟,Rijndael、RC6、MARS、Twofish、Serpent等出現(xiàn);2001年Rijndael成為DES的替代者,被作為高級(jí)加密標(biāo)準(zhǔn)AES。

2.3代換密碼

2.3.1簡單的代換密碼

【例2.3.1】簡單的代換密碼。令M=C=Z26,所包含元素表示為A=0,B=1,…,Z=25。將加密算法εk(m)定義為下面的Z26上的一個(gè)置換:那么相應(yīng)的解密算法υk(c)為明文消息:proceedmeetingasagreed加密為下面的密文消息(空間并不改變)cqkzyyrjyyowftvlvtqyyr在這個(gè)簡單的代換密碼例子中,消息空間M和C都是字母表Z26。換句話說,一個(gè)明文或密文消息是字母表中的一個(gè)單個(gè)字符。由于這個(gè)原因,明文消息串proceedmeetingasagreed并不是單個(gè)消息,而是包含了22個(gè)消息,同樣,密文消息串cqkzyyrjyyowftvlvtqyyr也包含22個(gè)消息。密碼的密鑰空間大小為26!>4×1026,與消息空間的大小相比是非常大的。

然而,事實(shí)上這種密碼是非常脆弱的,因?yàn)槊恳粋€(gè)明文字符被加密成唯一的密文字符。這一弱點(diǎn)致使這種密碼對(duì)于稱為頻度分析(FrequencyAnalysis)的一種密碼分析(Cryptanalysis)技術(shù)來說是相當(dāng)脆弱的。頻度分析揭示出一個(gè)事實(shí),那就是自然語言包含大量的冗余。這里我們不討論簡單代換密碼的安全性。歷史上出現(xiàn)過幾種特殊的簡單代換密碼,最簡單且最著名的密碼稱為移位密碼。在移位密碼中,K=M=C,令N=|M|,則加密和解密映射定義為(2.3.1)其中。 。當(dāng)M為拉丁字母表的大寫字母時(shí)，也就是 ，移位密碼也稱為凱撒密碼，這是因?yàn)镴uliusCaesar使用了該密碼當(dāng)時(shí)的情形。不難看出,利用K中密鑰與M中消息之間的不同算術(shù)運(yùn)算可以設(shè)計(jì)不同的簡單代換密碼,這些密碼稱為單表密碼(MonoalphabeticCipher)。單表密碼是指對(duì)于一個(gè)給定的加密密鑰,明文消息空間中的每一元素將被代換為密文消息空間中的唯一元素。因此,單表密碼不能抵抗頻度分析攻擊。

然而,由于簡單代換密碼的簡易性,它們已經(jīng)被廣泛應(yīng)用于現(xiàn)代單鑰加密算法中。我們后面將會(huì)看到簡單代換密碼在數(shù)據(jù)加密標(biāo)準(zhǔn)(DES)和高級(jí)加密標(biāo)準(zhǔn)(AES)中所起到的核心作用。幾個(gè)簡單密碼算法相結(jié)合就可以產(chǎn)生一個(gè)安全的密碼算法,這一點(diǎn)已經(jīng)得到了公認(rèn),這就是簡單密碼仍被廣泛應(yīng)用的原因。此外,簡單代換密碼在密碼協(xié)議上也有廣泛的應(yīng)用。2.3.2多表密碼

如果M中的明文消息元可以代換為C中的許多(可能是任意多)密文消息元,則這種代換密碼就稱做多表密碼。

由于維吉尼亞密碼是多表密碼中最著名的密碼,因此我們將以它為例來說明多表密碼。

維吉尼亞密碼是基于串的代換密碼,其密鑰是由多于一個(gè)的字符所組成的串。令m為密鑰長度,那么明文串被分為m個(gè)字符的小段,也就是說,每一小段是m個(gè)字符的串,可能的例外就是串的最后一小段不足m個(gè)字符。其加密算法與密鑰串和明文串之間的移位密碼相同,每次的明文串都使用重復(fù)的密鑰串;其解密算法與移位密碼的解密運(yùn)算相同。

【例2.3.2】維吉尼亞密碼。令密鑰串是gold,利用編碼規(guī)則a=0,b=1,…,z=25,則這個(gè)密鑰串的數(shù)字表示是(6,14,11,3)。明文串:proceedmeetingasagreed的維吉尼亞加密運(yùn)算如下(這種運(yùn)算就是逐字符模26加):明文：1517142443124419密鑰：61411361411361411密文：2152551018141510184明文：81360180617443密鑰：3614113614113614密文：1119201121620271017因此密文串為vfzfksopkseltulvguchkr其他著名的多表密碼還包括書本密碼(也稱做Beale密碼,即密鑰串是已協(xié)商好的書中的原文)和Hill密碼。2.3.3弗納姆密碼

弗納姆密碼是最簡單的密碼體制之一。如果我們假定消息是長為n的比特串:那么密鑰也是長為n的比特串:其中:符號(hào)“∈U”表示均勻隨機(jī)地選取k。一次加密1比特,通過將每個(gè)消息比特和相應(yīng)的密鑰比特進(jìn)行比特XOR(異或)運(yùn)算來得到密文串c=c1c2…cn,即其中,1≤i≤n。這里運(yùn)算定義為因?yàn)楱捠悄?加,所以減法等于加法,故解密與加密相同?？紤]到M=C=K={0,1}*,則弗納姆密碼是代換密碼的特例。一次一密弗納姆密碼也稱為一次一密鑰密碼。

2.4換位密碼

通過重新排列消息中元素的位置而不改變?cè)乇旧韥碜儞Q一個(gè)消息的密碼稱做換位密碼(也稱做置換密碼)。換位密碼是古典密碼中除代換密碼外最重要的一類,它廣泛應(yīng)用于現(xiàn)代分組密碼的構(gòu)造。

考慮明文消息中的元素是Z26中的字符時(shí)的情形,令b為一固定的正整數(shù),它表示消息分組的大小,M=C=(Z26)b,K是所有的置換,也就是(1,2,…,b)的所有重排。因?yàn)棣小蔏,[JP]所以置換π=(π(1),π(2),…,π(b))是一個(gè)密鑰。對(duì)于明文分組(x1,x2,…,xb)∈M,這個(gè)換位密碼的加密算法是:令π-1表示π的逆,也就是π-1(π(i))=i(i=1,2,…,b),那么這個(gè)換位密碼相應(yīng)的解密算法是:對(duì)于長度大于分組長度b的消息,該消息可被分成多個(gè)分組,然后逐個(gè)分組重復(fù)同樣的過程。由于長度為b的消息分組共有b！種不同的密鑰,因此一個(gè)明文消息分組能夠變換加密為b！種可能的密文。然而,因?yàn)樽帜副旧聿⑽锤淖?所以換位密碼對(duì)于抗頻度分析技術(shù)也是相當(dāng)脆弱的。

【例2.4.1】換位密碼。令b=4,π=(π(1),π(2),π(3),π(4))=(2,4,1,3),那么明文消息:proceedmeetingasagreed首先分為6個(gè)分組,每個(gè)分組為4個(gè)字符:proceedmeetingasagreed然后可以變換加密成下面的密文:rcpoemedeietgsnagearde

2.5古典密碼

古典密碼的兩個(gè)基本工作原理——代換和換位,是構(gòu)造現(xiàn)代對(duì)稱加密算法的核心技術(shù)。

對(duì)于基于字符的代換密碼,因?yàn)槊魑南⒖臻g就是字母表,每一個(gè)消息就是字母表中的一個(gè)字符,所以加密就是逐個(gè)字符地將每一個(gè)明文字符代換為一個(gè)密文字符,代換取決于密鑰。在加密一個(gè)長字符串時(shí),如果密鑰是固定的,那么在明文消息中同一個(gè)字符將被加密成密文消息中一個(gè)固定的字符。

多表密碼和換位密碼