A5-1和DES兩個加密算法的學習

A5-1加密算法

1、基本原理

A5-1加密算法是一種流password，通過密鑰流對明文進行加密。然后用密鑰流進行對密文的解密操作。

這樣的算法主要用于GSM加密。也就是我們平時打電話的時候。通信數據發送到基站，基站發送到還有一個基站，基站發送到接收方。

每次通話的時候，基站會產生一個64位的隨機數，與我們手機sim卡內本身帶的一個password利用一種加密算法生成一個密鑰。這個密鑰就是這次通話過程中使用的主密鑰，此密鑰的生命周期為這一次通話的開始到結束。一旦通話完畢。那么這個密鑰也就沒實用了。

該加密算法把整個通訊的數據劃分為每一幀來進行加密。每一幀是有228位，當中發送端給接收端的數據114位。接收端反饋給發送端的數據有114位。

除了上面提出的基站給出的64的總密鑰，針對每一幀的加密，另一種叫做會話密鑰。這樣的會話密鑰每加密一幀都會改變。會話密鑰的生成是由幀號來決定的。

每一次的會話密鑰都會產生一個228位的亂數來加密這一幀的數據。加密的方式是異或。幀號一共用22位的二進制數來表示，也就是說一次通話僅僅能傳遞2^22次方的通訊數據。由于每一次通話僅僅有這么多幀能夠進行加密數據而且傳遞。

A5-1算法基于三個線性移位反饋寄存器實現的。

三個LFSR的級數各自是19 22 23。

f1(x) = x^19 + x^18 + x^17 + x^14 + 1

f2(x) = x^22 + x^21 + 1

f3(x) = x^23 + x^22 + x^21 + x^8 + 1

三個反饋多項式如上所看到的。

2、所用工具

依據上面所講的。我們基本能夠確定，假設要實現a5-1的加密算法。我們須要哪些工具：

首先是明文，其次是64位的密鑰。三個LFSR。以及幀號。

算法的輸入應該就是三個LFSR的初始值，算法的輸出就是我們加密明文所須要的亂數。

3、實現步驟

算法整體來說分為三個部分。初始化，運算，輸出亂數

A5-1加密算法實現的邏輯結構圖例如以下：

首先是初始化部分：

（1）將三個寄存器內的全部位全都賦值為0

（2）將三個寄存器做64次的移位操作。每第i次操作，寄存器的反饋內容都先與密鑰中的第i位進行異或，然后把這樣異或的結果作為寄存器此次的反饋內容。三個LSFR都要并行的做這種工作64次。

（2）將三個寄存器做22次的移位操作。沒第i次操作，寄存器的反饋項都先與幀序號的第i位進行異或。將異或的結果作為寄存器的終于反饋內容，相同，三個LSFR也都要并行做22次。

上述三步昨晚，A5-1加密算法的初始化操作也就做完了。

另外須要注意的是，A5-1加密算法的LSFR是左移操作，而且。密鑰和幀號都是從最低位到最高位編號。

當初始化步驟完畢的時候，此時三個LSFR的狀態合稱為S0狀態。

接下來是計算和輸出部分：

大家能夠看到，上面的邏輯結構圖中，有一個叫做鐘控的部分，他有三個輸出三個輸入，三個輸入是分別來三個LSFR的某一個固定位，輸入會輸出0或者1.0表示此次這個LSFR不會工作，也就是不會發生移動等等。輸出的是1的話，那么這個LSFR此次就會移動一位而且得出反饋的結果。

也就是說這個鐘控在控制著三個LSFR的工作與否。

首先依據鐘控的方式三個LSFR連續移動100次，可是不輸出亂數，此時應該僅僅是做一個混亂的操作。由于LSFR在移動過程中，每一位寄存器內的數值都會不一樣。所以在鐘控決定每一個寄存器執行與否的結果時也會不同樣。

接下來會三個LSFR會接著進行連續的114次的移動，也是依據鐘控的方式。

這一次的移動過程中，三個寄存器將分別把最高位寄存器的值輸出，然后三個值做異或運算，形成第i個亂數。

這次114次移動會生成一個114位的亂數，用于對手機到基站這一段的數據加密。

之后再進行一次100次的移動和114次的移動，結果和上面說的同樣。終于產生的114位密鑰用于基站到手機這段的通訊數據加密。

關于鐘控：

鐘控將第一個寄存器的第八位，第二個寄存器的第10位，第三個寄存器的第10位。

抽取這三個位用于控制三個LSFR的動作與否。他們決定的原則類似少數服從多數。三位一共同擁有8中排列方式，當三位中1的個數多余0的個數時，那么這三位是1的相應的寄存器將會移動， 為0的不會，假設三位數中0的個數多余1的個數時。那么三位之中是0的相應的寄存器將會移動。

依據上面的步驟就能夠算出當我們把通訊數據分割成每一幀，然后對每一幀進行加密傳輸的時候。所須要的那個加密的亂數是怎么得來的。至于加密過程非常easy。就是明文和亂數的異或操作。

DES加密算法

假設說A5-1是流password的加密算法的話，那么DES就是分組password體制中典型的一個算法。

分組password的主要思想。就是把明文和密鑰都分成一定長度的很多斷數據，為了保證每個明文都只唯獨一個密鑰。須要做的就是分組的密鑰長度要大于等于分組的明文長度。通過分組加密，每一組使用的密鑰都不同樣，這就是主要的分組password。

分組password的安全性除了收到一些密鑰長度參數的影響之外。最重要的兩個原則就是混亂原則和擴散原則。

混亂原則要求明文和密文在邏輯上的關系越復雜越好。為了保證混亂原則的實行。我們將盡可能使用非線性的變換。

擴散原則，我理解是這樣的，在設計password的時候，通過實行混亂原則。使得我們的password會在整個序列的某基礎發生混亂，那么擴散原則要做的，就是要通過移位的方式，將這樣的混亂最大化。讓明文和密鑰的變化盡可能多的影響密文的生成。這樣的思想最典型的體現，就是S-P網絡。

分組password中的一個非常典型的樣例就是DES算法：

DES算法也是分組password的一個案例，它屬于分組password中的迭代分組password。即用簡單的加密措施先構造出一個加密函數來，之后不斷的進行乘積迭代。兩個簡單的方式乘積在一起的話。會形成一個更加復雜的password函數，DES正式利用這種思想來實現。

DES加密算法的實現須要幾個工具：

1.分組長度2.密鑰長度3.迭代次數4.子密鑰長度

DES默認分組長度為64bit,密鑰長度也是64bit,迭代次數為16，子密鑰的長度為48位

DES加密算法的輸入是一組64bit的明文，輸出是64bit的密文

算法運行過程中有3步：初始變換， 16輪迭代， 初始逆變換

要注意的是。DES的算法中的比特序號是從1開始。而且是從左邊開始。

DES算法中的初始變換：

初始變化實際上就是對明文序列進行順序打亂操作。

他會依照一個特定的表格進行對比移動。

初始逆置換是對16次迭代后的結果序列進行移位操作，也是有一個對比表，告訴你移動的規則。

DES算法中的圈函數：

從上面的DES算法的邏輯結構圖中能夠看出。他李永樂Feistel模型進行迭代password的實現。那么這個迭代有一個圈函數

Li = Ri-1 ?Ri = Li-1^f(Ri-1, ki)(i = 1, 2, ...)

在進行完初始置換之后，我們得到一個長度為2w的序列，也就是64位的明文序列。把他們一分為二，分為左半部分和右半部分，在進行第一次迭代的時候。右半部分變為下一次迭代的左半部分，左半部分與F函數的結果進行按位異或形成下一輪迭代的右半部分。最后在迭代到第16次的時候。不在進行這種左右交換操作，直接轉換為相應的部分。

那么非常顯然，整個算法的核心就在于F函數的內容

F函數：

F函數的輸入有兩部分，一個是這一輪的子密鑰48bit，另外一個是序列的右半部分的32bit。

F(R,K) = P(S(E(Ri)^Ki))

上述表達式告訴我們F函數一共同擁有四個步驟，先是對R進行E盒的變換，E盒又稱為是擴展變換盒

1、E盒

E盒的作用就是把32位的數據擴展稱為48位的數據，我認為是由于密鑰是48位，所以必需要擴展一下要變換的明文序列，由于分組password的加密原則強調過。分組password的加密。密鑰是必須大于等于要加密的明文的。

把32位的序列分成8組，每組序列在開頭和結尾處分別加入開頭和結尾元素相鄰的元素。每一組加入2位，一共八組，田間16位。即擴展為48位。這是一種非線性的擴展。然后接下來就是與這一輪的子密鑰Ki進行按位異或操作。

2、S盒

S盒宏觀上的一個作用，是把剛剛異或生成的48位結果變換成32位。首先把48位的生成結果分成8組。每組6位。每6位分別作為S盒的輸入，這樣一共同擁有8個S盒并行工作。將6位輸入變為4位輸出。終于得到32位的結果。

對于每個S盒來說，有a1~~~a6的二進制比特輸入。有這種一個表格存在：

如今S盒一共同擁有6位的輸入，a0a1a2a3a4a5a6

我如今算的是S1盒的輸出。首先計算2a1+a6最后的十進制結果是多少，這個結果代表了行數。

之后計算8a2+4a3+2a4+a5最后的十進制結果代表了列數。拿到行數和列數之后，在表格中找到相應的數字。這里注意，假設我算出來的是1 3，那么我在找的時候，也是找表格中相應的標號是1行3列的元素，由于我們能夠看到表格中的標號是從0開始的。

比如，假設計算的s1，得出的結果是1行3列，那么結果應該是4.查表得到這個結果之后。表格能夠保證，得出的結果4位二進制數十全然能夠表示的，所以將這個十進制數化為4位二進制數就完畢了S盒的一部分操作，之后每個S盒都依照這種原則操作，之前異或的48位結果就會順利的變成32位。

3、P盒

P盒也是很easy，就是依據一個表格進行一個移位操作。表格到時候會詳細給出。

經過上述的計算，我們能夠順利的得到F函數的計算結果。F函數的計算過程圖例如以下：

經過上述的計算我們能夠準確的得到F函數的詳細結果，那么下輪迭代的右半部分也就是R1就能夠由上一層的左半部分和F函數的結果異或得到。不知道為什么的，能夠翻上去看一下DES實現的邏輯框圖。

DES的算法基本運行流程就是這種。那么另一個問題可能我們沒有考慮到，我們擁有的是一個64位的初始密鑰。那么每一次的子密鑰是怎么生成的呢？

DES子密鑰的生成：

DES的初始密鑰一共同擁有64位，當中密鑰的每個字節的最后一位都用作奇偶校驗，所以說，實際的有效密鑰長度為56位。

DES子密鑰的生成邏輯框圖例如以下：

首先。64位的初始密鑰進來，最先要運行的就是置換選擇操作1.

那么置換選擇操作詳細的內容是什么呢：

置換選擇操作1有兩個步驟：

（1）將64位中每個密鑰字節的最后一位丟棄

（2）將剩余的56位依照表格的規則打亂順序。生成一個亂序的56位序列

之后將輸出的56比特的有效密鑰序列一分為二。分為D0和C0兩部分（生成C0D0到此為止僅僅能算是密鑰生成算法的初始化操作,不能算作一次迭代）。之后從第一次開始的每一次的迭代中，分別要對上一次的Di-1 Ci-1兩部分進行循環左移操作，循環左移的次數和所在的迭代次數有關，比方D0C0--->D1C1是第一次迭代要循環左移1位。D2C2--->D3C2要左移2兩位,詳細的移位次數會有個明白的表格告訴大家。

每一次迭代的循環移位操作之后得到的兩部分DiCi，將進行置換選擇2的操作。置換選擇2與1類似。都是打亂順序。丟掉一部分元素，最后形成一個48位的序列。就是上面DES算法中第i次迭代所須要的子密鑰。可是本次迭代生成的Di和Ci不會改變，由于他們將會用于下一次子密鑰的生成操作。由于DES須要16次的迭代。那么子密鑰的生成自然也須要16輪的迭代。

也就是說。什么樣算一次迭代操作呢，從循環位移。一直到置換選擇2，再到終于生成第i次的子密鑰ki算作是一次迭代，之前生成d0c0的部分不算。