【正文】 通過分析明文對的差值對密文對的差值的影響來恢復(fù)某些密鑰比特 ? 線形密碼分析 ? 線形密碼分析本質(zhì)上是一種已知明文攻擊方法 ,其基本思想是通過尋找一個給定密碼算法的有效的線形近似表達式來破譯密碼系統(tǒng) . 公開密鑰密碼體制 ? 由 Deffie和 Hellman于 1976年提出，又稱為非對稱（雙鑰）密碼體制。加解密密鑰不同，加解密算法也不相同，加密密鑰可以公開。 ? 優(yōu)缺點： ? 加密速度低（比 DES芯片慢 1000倍）； ? 簡化密鑰管理； ? 可以提供比傳統(tǒng)密碼體制更多的安全服務(wù)（如數(shù)字簽名、訪問授權(quán)、身份認證等）； ? 尋找更有效的算法難度大。 公開密鑰密碼體制 ? 設(shè)計雙鑰體制的關(guān)鍵是首先要尋求一個合適的單向陷門函數(shù)。 ? 單向函數(shù)求逆困難，例如： y=ax，設(shè) x=100，則利用高速計算機計算 y可在，然而反向由 y計算 x（即 x=logay），用相同的計算機則需 1600年左右。 ? 而當知道陷門信息后，求逆易于實現(xiàn)。 ? 因此其中一個（如 x）可作為加密密鑰，陷門信息可作為解密密鑰。 數(shù)學(xué)基礎(chǔ)－數(shù)論 ? 模運算 ? 素數(shù) ? 最大公因子 ? 求模逆元 ? 費馬小定理 ? 歐拉 φ函數(shù) ? … 模運算 ?模運算 ,“時鐘算術(shù) ” 學(xué)生甲說 10： 00到家，而他遲到 13個小時，那么他什么時候回家？他的父親等了他幾個小時？ 這就是模 12運算， 23模 12等于 11： （ 10＋ 13） mod 12＝ 23 mod 12 ＝ 11 mod 12 另一種寫法認為 23和 11的模 12運算相等： 23≡11（ mod 12） （ ≡： 三元等號，同余 ） 模運算 如果 a=b+kn對某些整數(shù) k成立，那么 : a≡b (mod n) 稱為 a與 b模 n同余 模運算 化簡運算： (a+b)mod n=((a mod n)+(b mod n)) mod n (ab)mod n=((a mod n)(b mod n)) mod n (a*b)mod n=((a mod n)*(b mod n)) mod n (a*(b+c))mod n=(((a*b) mod n)+((a*c) mod n))) mod n 模運算 ?A8 mod n=(A*A*A*A*A*A*A*A) mod n ?化簡為： ?((A2 mod n)2 mod n)2 mod n 素數(shù) ? 素數(shù)是這樣一種數(shù)：比 1大，其因子只有 1和它本身。 ? 2， 3， … 27568391。 ? 素數(shù)是無限的。 ? 密碼學(xué)常用比較大的素數(shù)（ 512位，甚至更長）。 最大公因子 ? 兩個數(shù)互素是指：當他們除了 1以外沒有共同的因子，換句話說，如果 a和 n的最大公因子等于 1，那么可寫作： Gcd(a,n)=1 求模逆元 ? 4的乘法逆元是 1/4，因為 4 1/4=1。 ? 模的逆元： (a x) mod n=1 ? 也可寫作： a1≡x (mod n) 費馬小定理 ? 如果 m是一個素數(shù)，且 a不是 m的倍數(shù)，那么，根據(jù)費馬小定律有： am1≡1(mod m) 歐拉 φ函數(shù) ? Φ(n)表示模 n的余數(shù)化簡集中元素的數(shù)目。換句話說 Φ(n)表示與 n互素的小于 n的正整數(shù)的數(shù)目（ n1）。 ? 如果 n是素數(shù)，那么 Φ(n)=n1；如果 n=pq，且 p與q互素，那么 Φ(n)=(p1)(q1)。 費馬小定理的歐拉推廣 aΦ(n)≡1(mod m) 公鑰密碼算法 1） RSA密碼體制 RSA密碼是由 Rivest, Shamir和 Adleman三位學(xué)者于 1977年聯(lián)合提出的雙密鑰（公鑰）密碼系統(tǒng)， RSA是由他們的名字的首字母命名。 是迄今理論上最為成熟完善的一種公鑰密碼體制。 RSA密碼基于計算復(fù)雜性原理獲得加密強度，但其缺點是系統(tǒng)的安全取決于所用的兩個大素數(shù)，如果能找出一種快速方法分解這兩個大素數(shù)，系統(tǒng)很容易被攻破。 ? 選擇兩個素數(shù) p和 q，令 n=p q。 ? 隨即選擇加密密鑰 e，使得 e和 (p1)(q1)互素，則 n， e作為公鑰。 ? 求出正數(shù) d使其滿足： ed=1 mod Φ(n)=(p1)(q1) 即： d=e1 mod((p1)(q1)) 則 d作為密鑰 ， p和 q舍棄，但不可泄漏。 ? 加密： C=Me (mod n) ? 解密： M=Cd (mod n) ? 由于： Cd=( Me)d=Med=Mk(p1)(q1)+1 =M Mk(p1)(q1) =M 1=M RSA算法描述 RSA加 、 解密算法 (1978 Rivest,Shamir,Adelman) ? 分組大小為 k, 2k n ? 2k+1 ? 公鑰 n（ 兩素數(shù) p和 q的乘積 ） （ 推薦 p,q等長 ） e（ 與 (p1)(q1)互素 ） ed?1(mod(p1)(q1)) ? 私鑰 d（ e1 mod(p1)(q1) ) ? 加密 c=me mod n ? 解密 m=cdmod n 用戶首先選擇一對不同的素數(shù) p， q，計算 n=pq，f(n)=(p1)(q1). 并找一個與 f(n)互素的數(shù) d，并計算其逆 a, 即da=1 mod f(n)。 則密鑰空間 K=(n,p,q,a,d )。 加密過程為 ma mod n=c， 解密過程為 cd mod n=m。 其中 m,c分別為明文和密文 . n和 a公開，而 p， q， d是保密的。 舉例 ? 取兩個質(zhì)數(shù) p=11， q=13， p和 q的乘積為n=p q=143， 算出另一個數(shù) d=(p1) (q1)=120；再選取一個與 d=120互質(zhì)的數(shù) ， 例如 e=7， 則公開密鑰 =（ n， e） =（ 143， 7） 。 ? 對于這個 e值，可以算出其逆： a=103。因為e a=7 103=721，滿足 e a mod d =1；即 721 mod 120=1成立。則秘密密鑰 =（ n，a） =（ 143， 103）。 ?設(shè)張小姐需要發(fā)送機密信息 （ 明文 ） m=85給李先生 ， 她已經(jīng)從公開媒體得到了李先生的公開密鑰 （ n， e） =（ 143， 7） ， 于是她算出加密值： ?c= me mod n=857 mod 143=123并發(fā)送給李先生 。 ?李先生在收到密文 c=123后 ， 利用只有他自己知道的秘密密鑰計算： m= ca mod n =123103 mod 143=85，所以 ， 李先生可以得到張小姐發(fā)給他的真正的信息 m=85，實現(xiàn)了解密 。 RSA的安全性 ? 就目前的計算機水平用 1024位的密鑰是安全的， 2048位是絕對安全的。 RSA實驗室認為，512位的 n已不夠安全，應(yīng)停止使用，現(xiàn)在的個人需要用 668位的 n，公司要用 1024位的 n，極其重要的場合應(yīng)該用 2048位的 n。 RSA算法的脆弱性 公開密鑰算法 P、 q選擇不當，則變換周期性、封閉性而泄密 例： p=17， q=11， e=7，則 n=187。設(shè) m=123，則 C1=1237 mod 187=183 C2=1837 mod 187=72 C3=727 mod 187=30 C4=307 mod 187=123 明文 m經(jīng)過 4次加密，恢復(fù)成明文。 總之， RSA對用戶要求太苛刻，密鑰不能常更換。