Hash
SHA-3 子功能可逆性說明
SHA-3 子功能可逆性說明
我剛剛完成了一個非常緩慢且笨拙的 SHA-3 (224,256,384,512) python 實現。練習不是為速度而設計的。我唯一的目標是深入了解 SHA-3 系列函式的下劃線功能，並以我認為可讀的方式對其進行記錄。
參考文獻包括以下內容：
SHA-3 文件-
https://pdfs.semanticscholar.org/8450/06456ff132a406444fa85aa7b5636266a8d0.pdf http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf
Theta() 文件-
任何人都可以簡要解釋 SHA3 中壓縮框的“theta step”嗎？
中間值文件-
http://csrc.nist.gov/groups/ST/toolkit/examples.html
在此過程中，我發現兩組 SHA-3 文件之間存在各種差異，關於 FIPS 202，某些領域，特別是 3.2.2 和 3.2.3，文件可以同時使用編輯和澄清（IMO） . 在這些領域，令我不滿意的是，我求助於反轉提供的中間值來導出 pi() 和 rho()，因為最終解密提供的文件更容易。
因此，以下內容直接引用自 FIPS 202 第 4 節關於海綿結構的內容：
“SHA-3 函式，在 Sec. 圖 6 是海綿構造的實例，其中基礎函式 f 是可逆的，即置換，儘管海綿構造並不要求 f 是可逆的。”
這在 pi() 和 rho() 的可逆性中很明顯。並且鑑於 SHA-3 iota() 的約束也是可逆的。從功能上講，它只是一個帶有捨入常數的 XOR 操作。
分析 theta() 和 chi() 需要更長的時間。
我會在這裡住一段時間：
什麼標準使 Keccak 圓函式的 theta 步是可逆的？
我的具體問題：為什麼 SHA-3 設計者不讓每個子功能都不可逆？
我的好奇程式碼。
def bin_8bit(dec): return(str(format(dec,'08b'))) def bin_32bit(dec): return(str(format(dec,'032b'))) def bin_4bit(dec): return(str(format(dec,'04b'))) def bin_64bit(dec): return(str(format(dec,'064b'))) def hex_return(dec): return(str(format(dec,'08x'))) def hex_double(dec): return(str(format(dec,'02x'))) def hex_single(dec): return(str(format(dec,'01x'))) def dec_return_bin(bin_string): return(int(bin_string,2)) def dec_return_hex(hex_string): return(int(hex_string,16)) def L_P(SET,n): to_return=[] j=0 k=n while k<len(SET)+1: to_return.append(SET[j:k]) j=k k+=n return(to_return) def s_l(bit_string): bit_list=[] for i in range(len(bit_string)): bit_list.append(bit_string[i]) return(bit_list) def l_s(bit_list): bit_string='' for i in range(len(bit_list)): bit_string+=bit_list[i] return(bit_string) def rotate_left(bit_string,n): if n==0: return(bit_string) bit_list = s_l(bit_string) count=0 while count <= n-1: list_main=list(bit_list) var_0=list_main.pop(0) list_main=list(list_main+[var_0]) bit_list=list(list_main) count+=1 return(l_s(list_main)) def rotate_right(bit_string,n): if n==0: return(bit_string) bit_list = s_l(bit_string) count=0 while count <= n-1: list_main=list(bit_list) var_0=list_main.pop(-1) list_main=list([var_0]+list_main) bit_list=list(list_main) count+=1 return(l_s(list_main)) def shift_right(bit_string,n): bit_list=s_l(bit_string) count=0 while count <= n-1: bit_list.pop(-1) count+=1 front_append=['0']*n return(l_s(front_append+bit_list)) def mod_32_addition(input_set): value=0 for i in range(len(input_set)): value+=input_set[i] mod_32 = 4294967296 return(value%mod_32) def xo(bit_string_1,bit_string_2): xor_list=[] for i in range(len(bit_string_1)): if bit_string_1[i]=='0' and bit_string_2[i]=='0': xor_list.append('0') if bit_string_1[i]=='1' and bit_string_2[i]=='1': xor_list.append('0') if bit_string_1[i]=='0' and bit_string_2[i]=='1': xor_list.append('1') if bit_string_1[i]=='1' and bit_string_2[i]=='0': xor_list.append('1') return(l_s(xor_list)) def and_2str(bit_string_1,bit_string_2): and_list=[] for i in range(len(bit_string_1)): if bit_string_1[i]=='1' and bit_string_2[i]=='1': and_list.append('1') else: and_list.append('0') return(l_s(and_list)) def or_2str(bit_string_1,bit_string_2): or_list=[] for i in range(len(bit_string_1)): if bit_string_1[i]=='0' and bit_string_2[i]=='0': or_list.append('0') else: or_list.append('1') return(l_s(or_list)) def not_str(bit_string): not_list=[] for i in range(len(bit_string)): if bit_string[i]=='0': not_list.append('1') else: not_list.append('0') return(l_s(not_list)) def init_array(): int_bits = L_P(L_P('0'*1600,64),5) return(int_bits) def sub_str_concat(list_of_lists): to_return=[] for i in range(len(list_of_lists)): insert='' for x in range(len(list_of_lists[i])): insert+=list_of_lists[i][x] to_return.append(insert) return(to_return) def str_concat(list_of_strings): to_return='' for i in range(len(list_of_strings)): to_return+=list_of_strings[i] return(to_return) def list_concat(list_of_lists): to_return=[] for i in range(len(list_of_lists)): to_return+=list_of_lists[i] return(to_return) def flip_string(a_string): to_return='' for i in range(1,len(a_string)+1): to_return+=a_string[-i] return(to_return) def message_append(str_msg): return(str_msg+'01') def sha_3_rate(output_len): if output_len==224: return(1152) if output_len==256: return(1088) if output_len==384: return(832) if output_len==512: return(576) def pad(x,m): j=(-m-2)%x return('1'+'0'*j+'1') def trunc(string,index): return(string[0:index]) def message_processing(bit_string,digest_len): msg_bs = message_append(bit_string) p = msg_bs + pad(sha_3_rate(digest_len),len(msg_bs)) to_split = L_P(p,8) new_hex=[] for i in range(len(to_split)): new_hex.append(hex_double(int(flip_string(to_split[i]),2))) back_append = 200-len(new_hex) new_hex = new_hex+['00']*back_append total_string='' for i in range(len(new_hex)): total_string+=new_hex[i] to_insert = L_P(total_string,16) to_return=[] for i in range(len(to_insert)): to_return.append(flip_string(L_P(to_insert[i],2))) return(to_return) def message_expansion(hex_list): to_convert='' for i in range(len(hex_list)): to_convert+=bin_8bit(int(hex_list[i],16)) return(to_convert) def theta(s): c_xz=[] for i in range(5): c_xz.append(xo(xo(xo(xo(s[i],s[i+5]),s[i+10]),s[i+15]),s[i+20])) d_xz=[] for i in range(5): d_xz.append(xo(c_xz[(i-1)%5],rotate_left(c_xz[(i+1)%5],1))) a_xyz=[] for i in range(5): a_xyz.append([xo(s[i],d_xz[i]), xo(s[i+5],d_xz[i]), xo(s[i+10],d_xz[i]), xo(s[i+15],d_xz[i]), xo(s[i+20],d_xz[i])]) a_xyz=list_concat(a_xyz) order_return=[] for i in range(5): order_return.append([a_xyz[i],a_xyz[i+5],a_xyz[i+10],a_xyz[i+15],a_xyz[i+20]]) return(list_concat(order_return)) def rho(s): off_set=[0,1,190,28,91, 36,300,6,55,276, 3,10,171,153,231, 105,45,15,21,136, 210,66,253,120,78] to_return=[] for i in range(len(s)): to_return.append(rotate_left(s[i],off_set[i])) return(to_return) def pi(s): index=[0,6,12,18,24, 3,9,10,16,22, 1,7,13,19,20, 4,5,11,17,23, 2,8,14,15,21] to_return=[] for i in range(len(index)): for x in range(len(s)): if index[i]==x: to_return.append(s[x]) return(to_return) def chi(s): def sf(find_list,set_main): return(set_main.index(find_list)) sm=[[0,0],[1,0],[2,0],[3,0],[4,0], [0,1],[1,1],[2,1],[3,1],[4,1], [0,2],[1,2],[2,2],[3,2],[4,2], [0,3],[1,3],[2,3],[3,3],[4,3], [0,4],[1,4],[2,4],[3,4],[4,4]] to_return=[] for i in range(25): to_return.append(xo(s[i],and_2str(not_str(s[sf([(sm[i][0]+1)%5,sm[i][1]],sm)]),s[sf([(sm[i][0]+2)%5,sm[i][1]],sm)]))) return(to_return) def iota(s,i_r): def rc(t): def xor_bit(a,b): return('1' if ((a == '1') ^ (b == '1')) else '0') if t%255==0: return('1') r=['1','0','0','0','0','0','0','0'] for i in range(1,(t%255)+1): r = ['0'] + r r[0] = xor_bit(r[0],r[8]) r[4] = xor_bit(r[4],r[8]) r[5] = xor_bit(r[5],r[8]) r[6] = xor_bit(r[6],r[8]) r = trunc(r,8) return(r[0]) to_index=[] for x in range(24): to_check='' RC = ['0']*64 for i in range(7): RC[(2**i)-1]=rc(i+(7*x)) to_index.append(flip_string(str_concat(RC))) s[0]=xo(s[0],to_index[i_r]) return(s) def message_bit_return(string_input): bit_list=[] for i in range(len(string_input)): bit_list.append(bin_8bit(ord(string_input[i]))) return(l_s(bit_list)) def processing(message_string): to_invert=L_P(message_bit_return(message_string),8) to_return=[] for i in range(len(to_invert)): to_return.append(flip_string(to_invert[i])) return(str_concat(to_return)) def sha_3(to_hash,digest_len): x = L_P(message_expansion(L_P(str_concat(message_processing(processing(to_hash),digest_len)),2)),64) for i in range(24): x = iota(chi(pi(rho(theta(x)))),i) to_flip=[] for i in range(digest_len/64): to_flip.append(x[i]) to_convert=[] for i in range(len(to_flip)): to_convert.append(L_P(to_flip[i],8)) bin_list=[] for i in range(len(to_convert)): bin_list.append(flip_string(to_convert[i])) bin_list=L_P(str_concat(bin_list),4) to_return=[] for i in range(len(bin_list)): to_return.append(hex_single(int(bin_list[i],2))) to_return=str_concat(to_return) return(to_return)
散列函式通常是通過將問題分成兩部分來設計的：
- 一個固定大小的核心函式。這在大多數雜湊中稱為壓縮函式，但在 Keccak 中稱為排列。
- 域擴展器——一種使用固定大小核心函式來處理任意長度輸入的算法。在 SHA-2 等較舊的雜湊中，這是 Merkle-Damgård 構造；在 Keccak 是海綿結構。
核心功能通常通過密碼分析來評估；密碼學家試圖在實踐中實際破解它。另一方面，域擴展器通常通過安全證明進行評估：密碼學家試圖找到一個數學論據，表明如果生成的散列函式不安全，則不是域擴展器的錯。
Bertoni、Daemen、Peeters 和 Assche 的論文“Cryptographic Sponge Functions”包含海綿結構的安全證明。他們使用兩種核心函式進行證明：
- **隨機變換：**任何隨機選擇的函式 $ b $ -bit 塊作為它的域和範圍。
- 隨機排列：在 $ b $ 位塊——即具有相同域和範圍的可逆函式。
他們得出結論（第 65 頁）：
值得注意的是，使用隨機排列
$$ in the sponge construction’s security proof $$與使用隨機變換相比，會產生更好的 [隨機預言不可微分性] 約束。
原因非常技術性，但您的問題的答案是：海綿結構的安全證明告訴我們，使用排列作為其核心功能效果更好。