Atitit.md5 實作原理

Atitit.md5 實作原理

1.算法流程圖2

2.MD5算法過程：2

2.1.3.

處理分組資料3

3.MD5加密字元串執行個體5

4.Md5的曆史7

4.1.1.MD27

4.1.2.MD47

4.1.3.MD57

5. 處理P：8

6.參考8

1. 算法流程圖

2. MD5算法過程：

   對MD5算法簡要的叙述可以為：MD5以512位分組來處理輸入的資訊，且每一分組又被劃分為16個32位子分組，經過了一系列的處理後，算法的輸出由四個32位分組組成，将這四個32位分組級聯後将生成一個128位散列值。

    第一步、填充：如果輸入資訊的長度(bit)對512求餘的結果不等于448，就需要填充使得對512求餘的結果等于448。填充的方法是填充一個1和n個0。填充完後，資訊的長度就為N*512+448(bit)；

    第二步、記錄資訊長度：用64位來存儲填充前資訊長度。這64位加在第一步結果的後面，這樣資訊長度就變為N*512+448+64=(N+1)*512位。

    第三步、裝入标準的幻數（四個整數）：标準的幻數（實體順序）是（A=(01234567)

16，B=(89ABCDEF)16，C=(FEDCBA98)16，D=(76543210)16）。如果在程式中定義應該是（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。有點暈哈，其實想一想就明白了。

    第四步、四輪循環運算：循環的次數是分組的個數（N+1） 

1）将每一512位元組細分成16個小組，每個小組64位（8個位元組）

2.1. 3.處理分組資料

MD5以512比特一塊的方式處理輸入的消息文本，每個塊又劃分為十六個32比特的子塊

每一分組的算法流程如下：

第一分組需要将上面四個連結變量複制到另外四個變量中：A到a，B到b，C到c，D到d。從第二分組開始的變量為上一分組的運算結果，即A = a， B = b，

C = c，

D = d。

主循環有四輪（MD4隻有三輪），每輪循環都很相似。第一輪進行16次操作。每次操作對a、b、c和d中的其中三個作一次非線性函數運算，然後将所得結果加上第四個變量，文本的一個子分組和一個常數。再将所得結果向左環移一個不定的數，并加上a、b、c或d中之一。最後用該結果取代a、b、c或d中之一。

主循環有四輪， 每一輪由16次操作組成。F、G、H、I函數   每一輪應用一個函數/* 一共4輪，每一輪使用不同函數*/  

以下是每次操作中用到的四個非線性函數（每輪一個）。

F( X ,Y ,Z ) = ( X & Y ) | ( (~X) & Z )

G( X ,Y ,Z ) = ( X & Z ) | ( Y & (~Z) )

H( X ,Y ,Z ) =X ^ Y ^ Z

I( X ,Y ,Z ) =Y ^ ( X | (~Z) )

（&是與（And），|是或（Or），~是非（Not），^是異或（Xor））

這四個函數的說明：如果X、Y和Z的對應位是獨立和均勻的，那麼結果的每一位也應是獨立和均勻的。

F是一個逐位運算的函數。即，如果X，那麼Y，否則Z。函數H是逐位奇偶操作符。

假設Mj表示消息的第j個子分組（從0到15），常數ti是4294967296*abs( sin(i) ）的整數部分，i

取值從1到64，機關是弧度。（4294967296=232）

  處理P：

輪次              函數

1                                       (b  AND  c)  OR ( (NOT  b) AND  ( b ) )

2                                       (b  AND  d)  OR (c  AND  （NOT  d）)

3                                       b  XOR  c  XOR  d

4                                       c  XOR  (b  OR ( NOT  d))

      T[k]等于4294967296*abs(sin(k))所得結果的證書部分，其中k用弧度來表示。(這樣做是為了通過正弦函數和幂函數來進一步消除變換中的線性)

/*

 * 主循環  512bit 16group

 */

private void MainLoop(int group[]) {

int F,g;

int a =Atemp;

int b =Btemp;

int c =Ctemp;

int d =Dtemp;

//主循環有四輪， 每一輪由16次操作組成。F、G、H、I函數   每一輪應用一個函數

/* 一共4輪，每一輪使用不同函數*/  

for (int i = 0; i < 64;

i++) {

if (i < 16) {

F = (b &c) | ((~b)

& d);

g =i;

}

else if (i < 32) {

F = (d &b) | ((~d)

& c);

g = (5 *i + 1) % 16;      //1  6   11  0 5 10

 15  4  9

else if (i < 48) {

F =b ^

c ^

d;

g = (3 *i + 5) % 16;

else {

F =c ^ (b |

(~d));

g = (7 *i) % 16;

int tmp =d;

d =c;

c =b;

int mov_bits_count =s[i];

b =b + shift(a +

F +

K[i]

+ group[g],

mov_bits_count);

a =tmp;

//、、将A、B、C、D分别加上AA、BB、CC、DD，然後用下一塊資料繼續進行算法。

Atemp =a +

Atemp;

Btemp =b +

Btemp;

Ctemp =c +

Ctemp;

Dtemp =d +

Dtemp;

3. MD5加密字元串執行個體

現以字元串“jklmn”為例。

該字元串在記憶體中表示為：6A 6B 6C 6D 6E（從左到右為低位址到高位址，後同），資訊長度為40 bits， 即0x28。

對其填充，填充至448位，即56位元組。結果為：

6A 6B 6C 6D 6E 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

剩下64位，即8位元組填充填充前資訊位長，按小端位元組序填充剩下的8位元組，結果為。

6A 6B 6C 6D 6E 80 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 28 00 00 00 00 00 00 00

（totaol  64位元組，512 bits）

初始化A、B、C、D四個變量。

将這64位元組512bit填充後資料分成16個小組，每個小組4個byte,32bit（程式中對應為16個數組），即：

M0：6A 6B 6C 6D（這是記憶體中的順序，按照小端位元組序原則，對應數組M(0)的值為0x6D6C6B6A，下同）

M1：6E 80 00 00

M2：00 00 00 00

.....

M14：28 00 00 00

M15：00 00 00 00

經過“3.分組資料處理

”後，a、b、c、d值分别為0xD8523F60、0x837E0144、0x517726CA、0x1BB6E5FE

在記憶體中為a：60 3F 52 D8

b：44 01 7E 83

c：CA 26 77 51

d：FE E5 B6 1B

a、b、c、d按記憶體順序輸出即為最終結果：603F52D844017E83CA267751FEE5B61B。這就是字元串“jklmn”的MD5值。

4. Md5的曆史

4.0.1. MD2

Rivest在1989年開發出MD2算法。在這個算法中，首先對資訊進行資料補位，使資訊的位元組長度是16的倍數。然後，以一個16位的檢驗和追加到資訊末尾，并且根據這個新産生的資訊計算出散列值。後來，Rogier和Chauvaud發現如果忽略了檢驗将和MD2産生沖突。MD2算法加密後結果是唯一的（即不同資訊加密後的結果不同）。

4.0.2. MD4

為了加

MD5

強算法的安全性，Rivest在1990年又開發出MD4算法。MD4算法同樣需要填補資訊以確定資訊的比特位長度減去448後能被512整除（資訊比特位長度mod 512 = 448）。然後，一個以64位​

​二進制​​表示的資訊的最初長度被添加進來。資訊被處理成512位damg?rd/merkle疊代結構的區塊，而且每個區塊要通過三個不同步驟的處理

4.0.3. MD5

1991年，Rivest開發出技術上更為趨近成熟的​​md5算法​​。它在MD4的基礎上增加了"安全-帶子"（safety-belts）的概念。雖然MD5比MD4複雜度大一些，但卻更為安全。這個算法很明顯的由四個和MD4設計有少許不同的步驟組成。在​​MD5算法​​中，資訊-摘要的大小和填充的必要條件與MD4完全相同。Den boer和Bosselaers曾發現MD5算法中的假沖突（pseudo-collisions），但除此之外就沒有其他被發現的加密後結果了。

5.  處理P：

6. 參考

Java主要實作算法

MD5_百度百科.html