資訊安全算法整理

DES加密：

明文（64）密鑰（56）密文（64）

明文——>IP置換——>輪函數（16）——>逆IP置換——>密文

輪函數：Li = Ri-1 Ri = Li -1 異或 F(Ri-1,ki)

F(Ri-1,ki):E擴充，密鑰加，分組，s盒代換，P置換

密鑰編排算法：分為C0 D0 28 + 28 然後循環左移，1 2 9 16 移動一位其餘移動兩位

懶得寫了，crtl + c

AES加密:

密鑰加

輪函數10輪：

位元組代換s盒：

行移位：0 1 2 3

列混合：和c（x）做多項式乘法

密鑰加

輸出變換

密文

DSA

參數選取

選取大素數p 和 p 的一個素數因子 q

計算g = pow(h,(p-1) * q的逆)mod p【h∈（1，p-1）】

選取x 計算公鑰 y = pow(g,x) mod p【x∈（0，q）】

公鑰 y g p q私鑰 x

簽名過程

随機選取一個小于q的數字k

r = pow(g,k) mod p mod q

s = k的逆 * (H(m)+ x * r) mod q

驗證過程

w = s的逆 mod q

u1 = H(m) * w mod q

u2 = r * w mod q

v = pow(g,u1) * pow(y,u2) mod p mod q

判斷v 和 r

pow(y,u2) = pow(g,x * r * w)mod p mod q

ELGMAL算法

選取大素數p

選擇一個本原元g

選擇一個x 計算y = pow(g,x) mod p

y g p 作為公開密鑰

x 作為私密密鑰

加密過程：發送者選擇一個ri

c1 = pow(g,ri) mod p c2 = M * pow(y,ri) mod p

解密過程：因為 y = pow(g,x) mod p

是以M = c2 / pow(c1,x)

ELGMAL的數字簽名

選取素數p

本原元g

選擇一個x

y = pow(g,x) mod p

y g p 公鑰 x私鑰

加密

r = pow(g,k) mod p

s = (h(m) - x * r) * k的逆 mod p

驗證

pow(r,s) * pow(y,r) = pow(g,h(m)) mod p

橢圓曲線公鑰密碼體制

由已知式子計算并選擇一個生成元G

選擇一個XA作為私密密鑰

PA = XA * G

PA作為公鑰

加密過程：

發送方選擇一個k 發送{KG,PM + KPA}

解密過程：

第二個 - 第一個 * 密鑰

= PM + KPA(K * XA * G) - K * G * XA

計算兩個點相加的公式

x3 = pow(λ，2） - x1 - x2

y3 = λ* (x1 - x3) - y1 

λ = (y2 - y1) / (x2 - x1) = (y2 - y1) * (x2 - x1)的逆 當 兩個點不相同的時候

λ = (3 * pow(x1,2） +  a) * （2 * y1 的逆）

#略

橢圓曲線數字簽名：

橢圓曲線已知

選擇一個生成元G

選擇一個數d 計算Q  = d * G

公鑰為 p Ep G Q 私鑰 d

簽名過程

選取一個k

KG = (u,v)

然後

r = u mod p

s = K的逆 * (H(m) + rd) mod p

驗證過程同DSA

w = s的逆mod p

u1 = H(m) * w mod p

u2 = r * w mod p

計算u1 * P + u2 * Y = (u,v)則（r,s）簽名有效

RC4：

S表初始化 填 0~255

K表初始化 填密鑰 不夠長則重複

I從0~255

J = J + SI + KI

交換 SI SJ

I從0~255

J = J + SI

交換SI和SJ

t = SI + SJ

z = St

RSA加密算法

選擇兩個大素數P Q

φ（n） = （P -1） * （Q - 1）

取e gcd(e,φ（n）) = 1

d為e的逆 = e-1 mod φ（n）

e n 為公鑰 d為私鑰

加密c = pow(m,e) mod n

解密m = pow(c,d) mod n

超遞增背包問題

已知超遞增背包A

選擇k 和 t

使得gcd(t,k) = 1

B = t * A mod k

B k為公鑰 t 為私鑰

加密過程 ： C = B * X MOD K

解密過程 ： M'= t逆 * C mod k

對每個數按照超遞增背包規則來計算

超遞增背包：包括為1 不包括為0 從大到小

CBC-MAC

将明文分組 n 個

P1 和 IV異或然後在密鑰K下進行DES加密

P2...PN和前一輪生成的異或然後進行加密

Pn生成的Cn處理截斷後生成的即為MAC（消息認證碼）

HMAC

1.補充K得到B

2.B異或ipad

3.接上TEXT

4.Hash上面得到的

5.B異或opad

6.第五步接上第四步

7.hash

總公式 H(B異或OPAD || H(B異或IPAD || TEXT))

秘密共享：

秘密是S

參與保管的成員有n個

要求至少t個人才能重構該消息

標明一個足夠大的素數p

随機標明t-1個模數s1,s2,...,st-1得到多項式

s(x) = S + s1x + .. + st-1 pow (x,t-1) mod p

随機選取n個數

對每個整數計算得到yi

（xi,yi）發給n個成員

恢複秘密：

計算多項式f(x) = ∑k∈[1,t] yk * 求積 j∈[1,t]且！=k (x-xj)/(xk - xj)

常數項f（0）為所求的秘密S

構造矩陣

1,對應的數

2,~~

3,~~

4,~~

5,~~

無中心密鑰配置設定

A->B發一個請求和随機數N1

B->A發一個響應，用Ek(AB)加密包括了新的密鑰KS || F(N1) ||IDB || N2

A->B先驗證F(N1)IDB，然後用新的KS加密發送F(N2)

B驗證F(N2)

有中心的

三種

A->KDC KDC->TA

A->KDC KDC->TA TB

A->KDC KDC->A TA B TB

A->KDC帶随機數N1請求

A->KDC帶時間戳TKDC生存期L請求