b.明文m1m2對應的密文c1c2的確定：m1和m2同行或同列，則c1為m1后的字符，c2為m2后的字符；若m1和m2既不同行也不同列，則c1c2在m1m2所確定的矩形的其他兩個角上，c1和m1同行，c2和m2同行。

例：

?

• [p]1*n≡([c]1*n*[k]-1m*n)(mod 26)62333333
• 所使用的矩陣必須為非奇異矩陣
• 安全性:能較好抵抗統計分析法，對抗唯密文攻擊的強度較高，但易受已知明文攻擊。

?

?

?

• 逆矩陣的求法：

步驟說明：b1b6確定行，b2b3b4b5確定列，將48位變成32位

特點：

加密和解密運算不一致，加密器不能同時用做解密器

生成程序或文檔的“數字指紋”

用于安全運輸和存儲口令

?雪崩效應

迭代結構：

1.將輸入消息分成L個固定長度的分組，每個分組為b位，最后一個分組包含輸入消息的總長度，若不足b位需要填充，

2.壓縮函數f:有兩個輸入，一個是前一次迭代的n位輸出，成為鏈接變量；一個是消息的b位分組，并產生一個n位的輸出，即散列值。

?

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

第一分組需要將上面四個鏈接變量復制到另外四個變量中：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中之一。

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

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）

現定義：

FF(a ,b ,c ,d ,Mj ,s ,ti ) 操作為 a = b + ( (a + F(b,c,d) + Mj + ti) << s)

GG(a ,b ,c ,d ,Mj ,s ,ti ) 操作為 a = b + ( (a + G(b,c,d) + Mj + ti) << s)

HH(a ,b ,c ,d ,Mj ,s ,ti) 操作為 a = b + ( (a + H(b,c,d) + Mj + ti) << s)

II(a ,b ,c ,d ,Mj ,s ,ti) 操作為 a = b + ( (a + I(b,c,d) + Mj + ti) << s)

注意：“<<”表示循環左移位，不是左移位。

這四輪（共64步）是：

第一輪

FF(a ,b ,c ,d ,M0 ,7 ,0xd76aa478 )

FF(d ,a ,b ,c ,M1 ,12 ,0xe8c7b756 )

FF(c ,d ,a ,b ,M2 ,17 ,0x242070db )

FF(b ,c ,d ,a ,M3 ,22 ,0xc1bdceee )

FF(a ,b ,c ,d ,M4 ,7 ,0xf57c0faf )

FF(d ,a ,b ,c ,M5 ,12 ,0x4787c62a )

FF(c ,d ,a ,b ,M6 ,17 ,0xa8304613 )

FF(b ,c ,d ,a ,M7 ,22 ,0xfd469501)

FF(a ,b ,c ,d ,M8 ,7 ,0x698098d8 )

FF(d ,a ,b ,c ,M9 ,12 ,0x8b44f7af )

FF(c ,d ,a ,b ,M10 ,17 ,0xffff5bb1 )

FF(b ,c ,d ,a ,M11 ,22 ,0x895cd7be )

FF(a ,b ,c ,d ,M12 ,7 ,0x6b901122 )

FF(d ,a ,b ,c ,M13 ,12 ,0xfd987193 )

FF(c ,d ,a ,b ,M14 ,17 ,0xa679438e )

FF(b ,c ,d ,a ,M15 ,22 ,0x49b40821 )

第二輪

GG(a ,b ,c ,d ,M1 ,5 ,0xf61e2562 )

GG(d ,a ,b ,c ,M6 ,9 ,0xc040b340 )

GG(c ,d ,a ,b ,M11 ,14 ,0x265e5a51 )

GG(b ,c ,d ,a ,M0 ,20 ,0xe9b6c7aa )

GG(a ,b ,c ,d ,M5 ,5 ,0xd62f105d )

GG(d ,a ,b ,c ,M10 ,9 ,0x02441453 )

GG(c ,d ,a ,b ,M15 ,14 ,0xd8a1e681 )

GG(b ,c ,d ,a ,M4 ,20 ,0xe7d3fbc8 )

GG(a ,b ,c ,d ,M9 ,5 ,0x21e1cde6 )

GG(d ,a ,b ,c ,M14 ,9 ,0xc33707d6 )

GG(c ,d ,a ,b ,M3 ,14 ,0xf4d50d87 )

GG(b ,c ,d ,a ,M8 ,20 ,0x455a14ed )

GG(a ,b ,c ,d ,M13 ,5 ,0xa9e3e905 )

GG(d ,a ,b ,c ,M2 ,9 ,0xfcefa3f8 )

GG(c ,d ,a ,b ,M7 ,14 ,0x676f02d9 )

GG(b ,c ,d ,a ,M12 ,20 ,0x8d2a4c8a )

第三輪

HH(a ,b ,c ,d ,M5 ,4 ,0xfffa3942 )

HH(d ,a ,b ,c ,M8 ,11 ,0x8771f681 )

HH(c ,d ,a ,b ,M11 ,16 ,0x6d9d6122 )

HH(b ,c ,d ,a ,M14 ,23 ,0xfde5380c )

HH(a ,b ,c ,d ,M1 ,4 ,0xa4beea44 )

HH(d ,a ,b ,c ,M4 ,11 ,0x4bdecfa9 )

HH(c ,d ,a ,b ,M7 ,16 ,0xf6bb4b60 )

HH(b ,c ,d ,a ,M10 ,23 ,0xbebfbc70 )

HH(a ,b ,c ,d ,M13 ,4 ,0x289b7ec6 )

HH(d ,a ,b ,c ,M0 ,11 ,0xeaa127fa )

HH(c ,d ,a ,b ,M3 ,16 ,0xd4ef3085 )

HH(b ,c ,d ,a ,M6 ,23 ,0x04881d05 )

HH(a ,b ,c ,d ,M9 ,4 ,0xd9d4d039 )

HH(d ,a ,b ,c ,M12 ,11 ,0xe6db99e5 )

HH(c ,d ,a ,b ,M15 ,16 ,0x1fa27cf8 )

HH(b ,c ,d ,a ,M2 ,23 ,0xc4ac5665 )

第四輪

II(a ,b ,c ,d ,M0 ,6 ,0xf4292244 )

II(d ,a ,b ,c ,M7 ,10 ,0x432aff97 )

II(c ,d ,a ,b ,M14 ,15 ,0xab9423a7 )

II(b ,c ,d ,a ,M5 ,21 ,0xfc93a039 )

II(a ,b ,c ,d ,M12 ,6 ,0x655b59c3 )

II(d ,a ,b ,c ,M3 ,10 ,0x8f0ccc92 )

II(c ,d ,a ,b ,M10 ,15 ,0xffeff47d )

II(b ,c ,d ,a ,M1 ,21 ,0x85845dd1 )

II(a ,b ,c ,d ,M8 ,6 ,0x6fa87e4f )

II(d ,a ,b ,c ,M15 ,10 ,0xfe2ce6e0 )

II(c ,d ,a ,b ,M6 ,15 ,0xa3014314 )

II(b ,c ,d ,a ,M13 ,21 ,0x4e0811a1 )

II(a ,b ,c ,d ,M4 ,6 ,0xf7537e82 )

II(d ,a ,b ,c ,M11 ,10 ,0xbd3af235 )

II(c ,d ,a ,b ,M2 ,15 ,0x2ad7d2bb )

II(b ,c ,d ,a ,M9 ,21 ,0xeb86d391 )

所有這些完成之后，將a、b、c、d分別在原來基礎上再加上A、B、C、D。

即a = a + A，b = b + B，c = c + C，d = d + D

然后用下一分組數據繼續運行以上算法。

1、將消息摘要轉換成位字符串

因為在Sha-1算法中，它的輸入必須為位，所以我們首先要將其轉化為位字符串，我們以“abc”字符串來說明問題，因為'a'=97, 'b'=98, 'c'=99，所以將其轉換為位串后為：

01100001 01100010 01100011

2、對轉換后的位字符串進行補位操作

Sha-1算法標準規定，必須對消息摘要進行補位操作，即將輸入的數據進行填充，使得數據長度對512求余的結果為448，填充比特位的最高位補一個1，其余的位補0，如果在補位之前已經滿足對512取模余數為448，也要進行補位，在其后補一位1即可。總之，補位是至少補一位，最多補512位，我們依然以“abc”為例，其補位過程如下：

初始的信息摘要：01100001 01100010 01100011

第一步補位： ? ?01100001 01100010 01100011 1

..... ......

補位最后一位： ?01100001 01100010 01100011 10.......0(后面補了423個0)

而后我們將補位操作后的信息摘要轉換為十六進制，如下所示：

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000

3、附加長度值

在信息摘要后面附加64bit的信息，用來表示原始信息摘要的長度，在這步操作之后，信息報文便是512bit的倍數。通常來說用一個64位的數據表示原始消息的長度，如果消息長度不大于2^64，那么前32bit就為0，在進行附加長度值操作后，其“abc”數據報文即變成如下形式：

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000018

因為“abc”占3個字節，即24位 ，換算為十六進制即為0x18。

4、初始化緩存

一個160位MD緩沖區用以保存中間和最終散列函數的結果。它可以表示為5個32位的寄存器(H0,H1,H2,H3,H4)。初始化為：

H0 = 0x67452301

H1 = 0xEFCDAB89

H2 = 0x98BADCFE

H3 = 0x10325476

H4 = 0xC3D2E1F0

如果大家對MD-5不陌生的話，會發現一個重要的現象，其前四個與MD-5一樣，但不同之處為存儲為big-endien format.

5、計算消息摘要

在計算報文之前我們還要做一些基本的工作，就是在我們計算過程中要用到的方法，或定義。

(1)、循環左移操作符Sn(x),x是一個字，也就是32bit大小的變量，n是一個整數且0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n)

(2)、在程序中所要用到的常量，這一系列常量字k(0)、k(1)、...k(79)，將其以十六進制表示如下：

Kt = 0x5A827999 ?(0 <= t <= 19)

Kt = 0x6ED9EBA1 (20 <= t <= 39)

Kt = 0x8F1BBCDC (40 <= t <= 59)

Kt = 0xCA62C1D6 (60 <= t <= 79)

(3)、所要用到的一系列函數

?Ft(b,c,d) ?((b&c)|((~b)&d)) ? ?(0 <= t <= 19)

?Ft(b,c,d) (b^c^d) ? ? ? ? ? ? (20 <= t <= 39)

?Ft(b,c,d) ((b&c)|(b&d)|(c&d)) ?(40 <= t <= 59)

?Ft(b,c,d) (b^c^d) ? ? ? ? ? ? ? (60 <= t <= 79)

(4)、計算

計算需要一個緩沖區，由5個32位的字組成，還需要一個80個32位字的緩沖區。第一個5個字的緩沖區被標識為A，B，C，D，E。80個字的緩沖區被標識為W0, W1,..., W79

另外還需要一個一個字的TEMP緩沖區。

為了產生消息摘要，在第4部分中定義的16個字的數據塊M1, M2,..., Mn

會依次進行處理，處理每個數據塊Mi 包含80個步驟。

現在開始處理M1, M2, ... , Mn。為了處理 Mi,需要進行下面的步驟

(1). 將 Mi 分成 16 個字 W0, W1, ... , W15, ?W0 是最左邊的字

(2). 對于 t = 16 到 79 令 Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-16).

(3). 令 A = H0, B = H1, C = H2, D = H3, E = H4.

(4) 對于 t = 0 到 79，執行下面的循環

TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;

E = D; D = C; C = S30(B); B = A; A = TEMP;

(5). 令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.?

在處理完所有的 Mn, 后，消息摘要是一個160位的字符串，以下面的順序標識

H0 H1 H2 H3 H4.

對于SHA256,SHA384,SHA512。你也可以用相似的辦法來計算消息摘要。對消息進行補位的算法完全是一樣的。

? ? ? ? ? ? ? ? ? ? ? ? ? （隨機數的選取可以使同一明文在不同時間加密成不同密文）

來源于生日攻擊的思想，

小步為 序列1：g1,···,gj,···,gm(1≤j≤m)

大步為 序列2：y,y*g-m,···，y*g-im

找到gj≡y*g-im(mod p),即找到y=gj+im(mod p),即x=j+im私鑰被找到

時間復雜度：O(p1/2)

3.指數積分法

?背包問題：∑aixi=b，這是一個NP完全類問題

特例：超遞增序列（每一個元素都比先前的元素和大） 可將背包問題轉化為P類問題

?數論中的歐拉定理，安全性依賴于大整數的素因子分解的困難性

歐拉定理：若a和n互素，則aΦ(n)≡1(mod n)

密鑰生成算法

加密和解密

（1）生成公私密鑰

• 選取兩個大素數p和q，至少要1024位
• 計算n=p*q
• 隨機選取整數e在(1≤e≤Φ(n))作為公鑰，要求滿足gcd(e,Φ(n))=1
• 用Euclid擴展算法計算私鑰d，滿足d*e≡1(mod Φ(n)),則e和n是公鑰，d是私鑰

（3）明文加密?
　c=E(m)=me(mod n)
（4）密文解密。
? ?m=D(c)=cd(mod n)

?1.算法正確性的證明

2.攻擊

? ? ? ? ? ?2.針對算法參數的攻擊

? ? ? ? ? ? ? ? ? ? ? ?1.對素數p和q選取時的限制；p和q長度相差不大，大小相差要大，否則難以抵御除法的攻擊；p-1和q-1都應有大的素因子。

? ? ? ? ? ? ? ? ? ? ? ?2.共模攻擊（因此不同用戶不用使用相同的p和q）

? ? ? ? ? ? ? ? ? ? ? ?3.低指數攻擊

韋爾斯特拉方程 ：E:y2+axy+by=x3+cx2+dx+e。密碼學中，常采用的橢圓曲線為：?E:y2=x3+ax+b，并要求4a3+27b2≠0

Hasse定理：如果E是有限域GF(p)上的橢圓曲線，N是E上的點(x,y)（其中x,yξGF(p)）的個數，則：|N-(p+1)|≤2(p)?

橢圓曲線上的點集合Ep（a,b）對于如下定義的加法規則構成一個Abel群：

點乘規則：

• 如果k為整數，kP=P+···+P ? ?（k個P相加）
• 如果s和t為整數，(s+t)P=sP+tP,s(tP)=t(sP)

橢圓曲線點的計算：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?

?

?

? ? ? ?公鑰為(E,n,G,PB)，私鑰為nB。

?160位的ECC密鑰和1024位的RSA和1024位的ElGamal的安全性等同。

?不是以一一對應的陷門單向函數為基礎，同一密文可能有多種明文；

隨機選取兩個大素數p和q，并且p≡q≡3mod4，將p和q作為私鑰，n=pq作為公鑰?

?

? 這里，先選擇e再確定d的原因是：加密的重要性大于解密的重要性。

? ? ? ? ? ?簽名者的公鑰是(p,g,y)，私鑰是x。

簽名者選擇隨機數k,1≤k≤q-1，然后進行如下計算：

　　　　　　　　　　　　r≡gk(mod p)

　　　　　　　　　　　　e=h(m,r)

　　　　　　　　　　　　s≡(xe+k)(mod q)

簽名為(e,s),其中h為安全的Hash函數。

??

?

?安全性和ElGaml類似

收到m和簽名值(r,s)后，計算

　　w≡s-1(mod q)??

　　u1≡h(m)w(mod q)

　　u2≡rw(mod q)

　　v=(gu1yu2mod p)mod q

比較v和r，相同則簽名有效，否則無效。

?

?

??選擇E上一點G∈E，G的階為滿足安全要求的素數n，即nG=O。

? 選取一個隨機數d∈[1,n-1]，計算Q使得Q=dG，那么公鑰為(n,Q)，私鑰為d。

?

????????ECDSA安全性依賴于基于橢圓曲線的有限群上的離散對數難題，與RSA和有限域離散對數的數字簽名相比，在相同的安全強度條件下，有如下特點

　　　　　　簽名長度短、密鑰存儲空間小，特別是用于存儲空間有限、帶寬受限、要求高速實現的場合。