【正文】 ash算法采用 ? 具體做法 : – 把原始消息 M分成一些固定長度的塊 Yi – 最后一塊 padding并使其包含消息 M的長度 – 設(shè)定初始值 CV0 – 壓縮函數(shù) f, CVi=f(CVi1,Yi1) – 最后一個(gè) CVi為 hash值 hash函數(shù)模型圖 bbit Y0 nbit IV= CV0 f b Y1 n f b YL1 n CVL1 f CV1 n n IV = initial value 初始值 CVi = chaining value 鏈接值 Yi = ith input block (第 i 個(gè)輸入數(shù)據(jù)塊 ) f = pression algorithm (壓縮算法） n = length of hash code (散列碼的長度 ) b = length of input block(輸入塊的長度 ) CVL …… MD5 雜湊算法 ? 作者： Ron Rivest ? 算法 – 輸入：任意長度的消息 – 輸出： 128位消息摘要 – 處理：以 512位輸入數(shù)據(jù)塊為單位 MD5: 示意圖 MD5步驟 ? 第一步： padding – 補(bǔ)長到 512的倍數(shù) – 最后 64位為消息長度的低 64位 – 一定要補(bǔ)長 (64+1~64+512)，內(nèi)容為 100…0 ? 第二步 – 把結(jié)果分割為 512位的塊： Y0,Y1,…Y L1 ? 第三步 – 初始化 MD buffer， 128位常量 (4個(gè)字 )，進(jìn)入循環(huán)迭代，共 L次 – 每次：一個(gè)輸入 128位，另一個(gè)輸入 512位，結(jié)果輸出 128位，用于下一輪輸入 ? 第四步 – 最后一步的輸出即為散列結(jié)果 128位 MD5的每一步運(yùn)算示意圖 每一輪中 16步的每一步運(yùn)算結(jié)構(gòu) A B C D A B C D + + + CLSs + g X[k] T[i] Function g g(b,c,d) 1 F(b,c,d) (b?c)?(b?d) 2 G(b,c,d) (b?d)?(c?d) 3 H(b,c,d) b?c?d 4 I(b,c,d) c?(b?d) 關(guān)于 MD5 ? MD5使用 littleendian ? 128位 hash值太短 ? MD5不是足夠安全的 – Dobbertin在 1996年找到了兩個(gè)不同的 512bit塊 ,它們在 MD5計(jì)算下產(chǎn)生相同的 hash – 至今還沒有真正找到兩個(gè)不同的消息 ,它們的 MD5的 hash相等 (1990年 10月發(fā)表 ) by Ron Rivest 安全性： 速度： 32位體系結(jié)構(gòu)下計(jì)算速度快。 Len Adlemen于 1977年發(fā)布 ?屬于分組密碼 ?明文和密文在 0 ~ n1之間 ,n是一個(gè)正整數(shù) ?應(yīng)用最廣泛的公鑰密碼算法 ?只在美國申請專利且已于 2022年 9月到期 ?英國的 Clifford Cocks在 1973年發(fā)表了與RSA幾乎一樣的算法 數(shù)論基礎(chǔ) ? Fermat定理 : p素?cái)?shù) ,a是整數(shù)且不能被 p整除 ,則 : ap1 ? 1 (mod p) (證明略 ) ? Euler函數(shù) ?(n)定義為小于 n且與 n互素的正整數(shù)個(gè)數(shù) – p是素?cái)?shù) , 則： ?(p)=p1 – 若 n的因子分解為 n=? Piai, ai0,Pi互不相同 , 則 ?(n)= ? Piai?(11/Pi) – 若 gcd (m ,n)=1 (m、 n的最大公因素是一，既互素 ), 則： ?(mn)=?(m)?(n) – 特別地 ,若 p?q且都是素?cái)?shù) , 則 ?(pq)=(p1)(q1) 數(shù)論基礎(chǔ) (續(xù) ) ? Euler定理 : 若 a與 n為互素的正整數(shù) ,則 a?(n) ? 1 （ mod n） 既 a?(n)+1 ? a（ mod n） ? 推論 : 若 n=pq, p?q都是素?cái)?shù) , k是任意整數(shù) ,對任意0? m ?n ,有 m?(n)+1 ? m （ mod n） 從而 m k?(n)+1 ? mk(p1)(q1)+1 ? m（ mod n） , （ m?(n) ? 1 （ mod n） ； [m?(n) ] k ? 1 （ mod n） m k?(n) ? 1 （ mod n） ； m k?(n)+1 ? mk(p1)(q1)+1?m（ mod n） ） RSA密鑰生成原理 ? n=pq, p?q都是素?cái)?shù) ,?(n)=(p1)(q1)是 n的 Euler數(shù) ? Euler定理推論 : 若 n=pq, p?q都是素?cái)?shù) , k是任意整數(shù) ,則 m k? (n)+1 ? mk(p1)(q1)+1 ? m （ mod n） , 對任意 0? m ?n ? 只要選擇 e,d, 滿足 ed=k?(n)+1,即 ed ? 1 （ mod ?(n)） ? d ? e1 （ mod ?(n)） 則： med ? m k? (n)+1 ? m （ mod n） 加密： Me ? C （ mod n） 解密： Cd =Med =M （ mod n） 公鑰 : KU={e,n}, 私鑰 : KR={d,n} RSA密鑰生成與使用 ? 產(chǎn)生密鑰對 – 選擇兩個(gè)大素?cái)?shù) 100位以上的十進(jìn)制數(shù) p,q , p?q， (保密 ) – 計(jì)算 n=pq, ?(n) =(p1)(q1) (只有知道 p,q才可算出 ?(n) ， 陷門 為 p,q ) – 隨機(jī)選擇整數(shù) e, 使得 gcd(e,?(n))=1 (兩個(gè)隨機(jī)數(shù)互素概率 ~) – 用毆幾里得算法求出 d ? e1 mod ?(n) ， 既 ed=k?(n)+1 （ ed ? 1 mod ?(n) , 即 ed與 ?(n) 互素 ) 參考書： 《 計(jì)算機(jī)密碼應(yīng)用基礎(chǔ) 》 四川大學(xué)數(shù)學(xué)學(xué)院 組