沙-3-功能可逆性澄清

Question

沙-3-功能可逆性澄清

我刚刚完成了SHA-3 (224,256,384,512)的非常缓慢和笨重的python实现。这项训练不是为速度而设计的。我唯一的目标是深入了解SHA-3系列函数的下划线功能，并以我认为可读的方式记录它。

参考资料包括：

沙三文件-

https://pdfs.semanticscholar.org/8450/06456ff132a406444fa85aa7b5636266a8d0.pdf http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.202.pdf

Theta()文件-

有人能简短地解释一下SHA3 3中压缩框的“θ步”吗？

中期价值文件-

http://csrc.nist.gov/groups/ST/toolkit/examples.html

在这一过程中，我发现两套SHA-3文件之间存在各种差异，关于FIPS 202，有些领域，特别是3.2.2和3.2.3，文件可以同时使用编辑和澄清(海事组织)。在这些方面，令我不满意的是，我求助于反向提供的中间值来派生pi()和rho()，因为最终更容易破译所提供的文档。

因此，以下内容直接引用FIPS 202第4节关于海绵状结构的内容：

“在证券交易委员会中指定的SHA-3功能。6是海绵结构的实例，其中的基本函数f是可逆的，即置换，尽管海绵结构不要求f是可逆的。“

这一点在pi()和rho()的可逆性中都很明显。考虑到SHA-3的约束，iota()也是可逆的。从功能上讲，它只是一个具有圆形常量的XOR操作。

对θ()和chi()的分析将花费更长时间。

我会在这里住一段时间

什么准则使Keccak圆函数的θ步长可逆？

我的具体问题是:为什么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)

Answer 1

假设我们的算法是不可逆转的。在这种情况下，我们能保证状态不会缩小到某个子域吗？我们能证明摘要大小或容量所提供的安全级别吗？

当使用不可逆转的函数时，我们不能跨越摘要消息对的空间。证明安全等级的唯一方法是使用可逆子函数.输入和子函数的输出之间的一对一关系被用来提供这个演示。