Điều gì sẽ là đối thủ thời gian O(n) cho loại kế hoạch này

Giả sử chúng ta có một mật mã khối $$E:\{0,1\}^k \text{ x } \{0,1\}^{2k} \rightarrow \{0,1\}^{2n} \quad \text{ với } \ quad k,n\geq128$$ K là thuật toán tạo khóa trả về khóa k-bit ngẫu nhiên. Đặt SE = (K,Enc,Dec) là sơ đồ mã hóa đối xứng với các thuật toán mã hóa và giải mã như được mô tả bên dưới trong mã. Đầu vào thông báo cho Enc là một chuỗi n-bit và đầu vào bản mã cho Dec là một chuỗi 4n-bit.

def Enc(K,M):
    nếu len(M) != n_bytes : 
        trở lại Không có
    
    A1 = chuỗi_ngẫu nhiên(n_byte)
    A2 = xor_strings(M,A1)
    C = []
    C.append(E(K,( A1 + "\x00" * n_byte )))
    C.append(E(K,( A2 + "\xFF" * n_byte )))
    tham gia trở lại (C)


def Dec(K,C):
    if len(C) != 4 * n_bytes : 
        trở lại Không có

    C = split(C,2 * n_byte)
    X1 = E_I(K,C[0]) #X1 = A1 || P1 trong mã giả
    X2 = E_I(K,C[1]) #X2 = A2 || P2 trong mã giả
    X1 = split(X1,n_byte) #A1 is X1[0] ; P1 là X1[1]
    X2 = split(X2,n_byte) #A2 is X2[0] ; P2 là X2[1]

    if (X1[1] != "\x00" * n_bytes) hoặc (X2[1] != "\xFF" * n_bytes):
        trở lại Không có
    
    M = xor_strings(X1[0],X2[0])
    trả lại M

#ĐÂY LÀ NƠI CÓ MÃ ĐỐI THOẠI ----- CẦN ĐIỀN MẪU NÀY
def A(enc):
    """
    :param enc: Đây là lời tiên tri được cung cấp bởi trò chơi.
    trở lại: một bản mã giả mạo
    """
    vượt qua

#below là để kiểm tra mã xem có đưa đúng đối thủ hay không
nếu __name__ == '__main__':    
    k = 128
    n = 128
    k_byte = k // 8
    n_byte = n//8
 
    EE = BlockCipher(k_byte, 2*n_byte)
    E = EE.encrypt
    E_I = EE.decrypt

    g = GameINTCTXT(2, Enc, Dec, k_byte)
    s = CTXTSim(g, A2)

    print("Khi k=128, n=128:")
    print ("Lợi thế của đối thủ A2 của bạn là ~" + str(s.compute_advantage()))

    k = 256
    n = 128
    k_byte = k // 8
    n_byte = n//8

    EE = BlockCipher(k_byte, 2*n_byte)
    E = EE.encrypt
    E_I = EE.decrypt

    g = GameINTCTXT(2, Enc, Dec, k_byte)
    s = CTXTSim(g, A2)

    print("Khi k=256, n=128:")
    print ("Lợi thế của đối thủ A2 của bạn là ~" + str(s.compute_advantage()))

Đối thủ thời gian O(n) có thể chỉ ra rằng SE không an toàn với INT-CTXT, thực hiện tối đa 2 truy vấn với Lợi thế = 1 - 2^(-n)

Đây là phiên bản Latex của lược đồ Mã hóa và Giải mã để dễ đọc:

mã hóa:

$\underline{ Alg E_K(M)}$

$\text{if } |M| \neq n \text{ sau đó quay lại } \perp$

$A[1] \leftarrow{$} \{0,1\}^n; A[2] \leftarrow M \oplus A[1]$

$C[1] \leftarrow E_K (A[1] || 0^n)$

$C[2] \leftarrow E_K (A[2] || 0^n)$

$\text{return } C$

giải mã:

$\underline{ Alg D_K(M)}$

$\text{if } |C| \neq 4n \text{ sau đó quay lại } \perp$

$C[1]C[2] \leftarrow C$

$A[1] || P[1] \leftarrow E^{-1}_K(C[1]) ; A[2] || P[2] \leftarrow E^{-1}_K(C[2])$

$\text{if }(P[1] \neq 0^n \text{ hoặc } P[2] \neq 1^n) \text{ then return } \perp$

$M \leftarrow A[1] \oplus A[2]$

$\text{return } M$

Đây là những gì tôi đã cố gắng cho đến nay:

def A(enc):

    một nửa = n_byte // 2
 
    C1 = enc(random_string(n_byte))
    C2 = enc("\x00" * n_byte)
    C_split1 = C1[:half]
    C_split2 = C2[một nửa:]
       
    trả về C_split1 + C_split2;

nhưng nhận được đầu ra:

Khi k=128, n=128:
Lợi thế của đối thủ A2 của bạn là ~0,0
Khi k=256, n=128:
Lợi thế của đối thủ A2 của bạn là ~0,0
```