SHA-1演算法在FPGA上的實作-2

在上一篇文章中，我詳細介紹了SHA-1演算法的計算程序，SHA-1演算法主要由訊息填充(Message Padding)和哈希計算(Hash Function Engine)兩部分組成，訊息塊標準長度規定為512bits一組，訊息填充在實作程序中需要區分長度不足一個訊息塊( < 512 bits)、長度超過一個訊息塊( > 512 bits)與長度剛好為一個訊息塊( = 512 bits)的時候，在這一篇文章中，我將介紹訊息填充以及哈希計算的FPGA實作思路，

訊息填充（Message Padding）

在SHA-1演算法當中，輸入訊息的處理是需要重點考慮的幾個部分之一，SHA-1演算法要求輸入的訊息塊將被分割成512bits為一組，即16個字（每個字長度為32bits），在整個演算法當中，每個字參與一輪計算，一共80輪，前16輪使用原本的“字”，后64輪使用擴展后的“字”，具體的擴展方法在上一篇文章中有提到，這里不再贅敘，

上圖是我節選自網路的一張PPT，它形象的介紹了在SHA-1演算法中訊息填充的方法，值得注意的是，Message Padding中特意在原始訊息后，填充“0”之前，使用了一個“1” bit，這里使用“1”，而不是全部使用“0”來填充的原因是考慮到了二義性，
對應在SHA-1演算法的訊息填充步驟中，在填充的原始訊息后加“1”的原因就是，如果我們的填充函式只是簡單地添加零位，直到填充的訊息具有正確的長度，那么這將導致以下形式的沖突，Hash(M) = Hash(M||0)，也就是出現了兩個數，經過了Hash計算后得出了同一個哈希值，Hash Function的缺陷之一就是可能會出現兩個數，比如上述的訊息（M）和訊息（M||0），注意，（M||0）指的是訊息（M）后拼接了一個0,在哈希運算中映射到同一個哈希值，這就意味著了Hash函式被Attacked，密碼被攻破，敵手不需要知道SHA-1的初始值（IV）以及原始訊息，只需要用類似的方式碰撞出相同的Hash值，就可以通過驗證，獲取資訊，“1”bit的存在意義就是在加密后，不會如同長度為1-512bits的“0”一般，被敵手輕易查獲，

// Message Padding fsm 
always @(posedge clk or negedge rst_n)
begin
	if(!rst_n) begin
		current_state <= s_IDLE;
	end
	else begin
		current_state <= next_state;
	end
end
always @ (*) 
begin
	case(current_state)
		s_IDLE: i_start && i_last 		? 		next_state = s_PAD 	:
				i_start                	? 		next_state = s_OP		:
													next_state = s_IDLE	;
		s_OP:	w_alg_done				?			next_state = s_PAD	:
																next_state = s_OP		;
		s_PAD:	w_blen_512 && (w_len < 'h38) ?	next_state = s_PAD	:
																				next_state = s_DONE;
		s_DONE: next_state = s_IDLE;
		default: next_state = s_IDLE;
	endcase
end

在上面這個狀態機中，我考慮了填充長度不足一個訊息塊（448 bits)以及該訊息塊是最后一個訊息塊的情況，具體情況還有，訊息塊長度為訊息單位長度的整數倍的情況、訊息塊長度為0的情況，可以請讀者自己酌情添加，

哈希計算（Hash Function）

哈希函式SHA-1的具體計算在上一篇中已經詳細介紹，這里不再贅述，直接給出代碼，

SHA-1 Function

在SHA-1演算法的計算輪次中，使用到了三種不同的函式，分別是Ch(x,y,z)、Parity(x,y,z)、Maj(x,y,z)，以及ROTLⁿ(x)具體的代碼實作展示如下：

// ch(x,y,z) 
function [31:0] sha1_ch();
input [31:0] x,y,z;
begin
	sha1_ch = (x & y) ^ (~x & z);
end
endfunction
// parity(x,y,z)
function [31:0] sha1_parity();
input [31:0] x,y,z;
begin
	sha1_parity = x ^ y ^ z;
end
endfunction
// maj(x,y,z)
function [31:0] sha1_maj();
input [31:0] x,y,z;
begin
	sha1_maj = (x & y) ^ (x & z) ^ (y & z);
end
endfunction
// ROTL
function [31:0] sha_rotl();
input [31:0] x;
input integer n;
sha_rotl = (x << n) | (x >> 32 - n);
endfunction

SHA-1 Constants

在SHA-1演算法中，每20輪有一個K值參與計算，一共4個K值，K值為常量，實作代碼如下：

function [31:0] sha1_find_k();
input x;
reg [31:0] p_K [0:3];
begin
	{p_K[0], p_K[1], p_K[2], p_K[3]} = 
		{32'h5a827999, 32'h6ed9eba1, 32'h8f1bbcdc, 32'hca62c1d6};
end
endfunction

Hash IV (Initial Value)

Hash 演算法能實作不固定長度的訊息塊通過運算轉化為固定長度的訊息摘要，在SHA-1中，這個固定長度為5個字，160bits，最初的值可根據官方參考，展示如下：

H[0] = 32'h67452301 ;
H[1] = 32'hefcdab89 ;
H[2] = 32'h98badcfe ;
H[3] = 32'h10325476 ;
H[4] = 32'hc3d2e1f0 ;

SHA-1 Processing

經過訊息塊的分組&填充處理，并擴展之后，SHA-1演算法的最終實作參考如下：

module	sha1_round(
	input					clk,
	input					rst_n,
	input					i_first,
	input	[511:0]		i_msg,
	output	[159:0]		o_digest
);
reg	[31:0]		T;
reg	[31:0]		W;
reg	[31:0]		WT;
integer i;

always @ (posedge clk) begin
if(first) begin
	H[0] = 32'h67452301 ;
	H[1] = 32'hefcdab89 ;
	H[2] = 32'h98badcfe ;
	H[3] = 32'h10325476 ;
	H[4] = 32'hc3d2e1f0 ;
end
else begin
	W[4] = W[3];
	W[3] = W[2];
	W[2] = sha1_rotl(W[1], 30);
	W[1] = W[0];
	W[0] = T;
end
end
always @ (posedge clk)begin
for(i = 0; i<5; i++) begin
	W[i] = H[i];
end
end
	
always @ (posedge clk) begin
for(i = 0; i<20; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_ch(h[1],H[2],H[3]) + H[4] + sha1_find_k(0) + WT[i];
end
for(i = 20; i<40; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_parity(h[1],H[2],H[3]) + H[4] + sha1_find_k(1) + WT[i];
end
for(i = 40; i<60; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_maj(h[1],H[2],H[3]) + H[4] + sha1_find_k(2) + WT[i];
end
for(i = 60; i<80; i++)begin
	T = sha1_rotl(H[0], 5) + sha1_parity(h[1],H[2],H[3]) + H[4] + sha1_find_k(4) + WT[i];
end
end

always @ (posedge clk) begin
	for(i = 0; i<16; i++)begin
		WT[i] = i_msg[i+:32];
	end
	for(i=16; i<80; i++)begin
		WT[i] = (WT[i-3] << 1) | (WT[i-3] >> 31) ^ (WT[i-8] << 1) | (WT[i-8] >> 31) ^ (WT[i-14] << 1) | (WT[i-14] >> 31) ^ (WT[i-16] << 1) | (WT[i-16] >> 31);
	end
end
assign o_digest = {W[5], W[4], W[3], W[2], W[1], W[0]};
endmodule

總結

在該章中，我使用Verilog HDL代碼實作了SHA-1演算法中演算法的具體計算以及訊息的填充，所有的代碼都是憑借記憶手打，僅供參考，如果有疑問，可以留言，歡迎相互交流，