Care ar fi un adversar de timp O(n) pentru acest tip de schemă

Să presupunem că avem un cifru bloc $$E:\{0,1\}^k \text{ x } \{0,1\}^{2k} \rightarrow \{0,1\}^{2n} \quad \text{ cu } \ quad k,n\geq128$$ K este algoritmul de generare a cheilor care returnează o cheie aleatorie de k biți. Fie SE = (K,Enc,Dec) schema de criptare simetrică cu algoritmi de criptare și decriptare, așa cum este descris mai jos în cod. Mesajul introdus la Enc este un șir de n biți, iar textul cifrat introdus pentru Dec este un șir de 4n biți.

def Enc(K,M):
    dacă len(M) != n_octeți : 
        return Niciunul
    
    A1 = șir_aleatoriu (n_octeți)
    A2 = xor_strings(M,A1)
    C = []
    C.adăugați(E(K,( A1 + "\x00" * n_octeți )))
    C.apend(E(K,( A2 + "\xFF" * n_octeți )))
    returnează alăturarea (C)


def Dec(K,C):
    dacă len(C) != 4 * n_bytes : 
        return Niciunul

    C = împărțit (C, 2 * n_octeți)
    X1 = E_I(K,C[0]) #X1 = A1 || P1 în pseudocod
    X2 = E_I(K,C[1]) #X2 = A2 || P2 în pseudocod
    X1 = split(X1,n_bytes) #A1 este X1[0] ; P1 este X1[1]
    X2 = split(X2,n_bytes) #A2 este X2[0] ; P2 este X2[1]

    dacă (X1[1] != "\x00" * n_octeți) sau (X2[1] != "\xFF" * n_octeți):
        return Niciunul
    
    M = xor_strings(X1[0],X2[0])
    întoarce M

#ACESTA ESTE UNDE MERGE CODUL ADVERSAR ----- TREBUIE SĂ UMPLEȚI ACEST
def A(enc):
    """
    :param enc: Acesta este oracolul oferit de joc.
    return: un text cifrat falsificat
    """
    trece

#de mai jos este să testați codul pentru a vedea dacă este dat adversarul corect
if __name__ == '__main__':    
    k = 128
    n = 128
    k_octeți = k//8
    n_octeți = n//8
 
    EE = BlockCipher(k_bytes, 2*n_bytes)
    E = EE.criptare
    E_I = EE.decriptează

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

    imprimare ("Când k=128, n=128:")
    print ("Avantajul adversarului tău A2 este ~" + str(s.compute_advantage()))

    k = 256
    n = 128
    k_octeți = k//8
    n_octeți = n//8

    EE = BlockCipher(k_bytes, 2*n_bytes)
    E = EE.criptare
    E_I = EE.decriptează

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

    imprimare ("Când k=256, n=128:")
    print ("Avantajul adversarului tău A2 este ~" + str(s.compute_advantage()))

Ce O(n)-time Adversary poate arăta că SE nu este sigur INT-CTXT, făcând cel mult 2 interogări cu Advantage = 1 - 2^(-n)

Iată o versiune Latex a schemei de criptare și decriptare pentru o citire ușoară:

Criptare:

$\subliniază{ Alg E_K(M)}$

$\text{dacă } |M| \neq n \text{ apoi returnează } \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{întoarce } C$

Decriptare:

$\subliniază{ Alg D_K(M)}$

$\text{dacă } |C| \neq 4n \text{ apoi returnează } \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{dacă }(P[1] \neq 0^n \text{ sau } P[2] \neq 1^n) \text{ atunci returnează } \perp$

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

$\text{întoarce } M$

Iată ce am încercat până acum:

def A(enc):

    jumătate = n_octeți // 2
 
    C1 = enc(șir_aleatoriu(n_octeți))
    C2 = enc("\x00" * n_octeți)
    C_split1 = C1[:half]
    C_split2 = C2[jumătate:]
       
    returnează C_split1 + C_split2;

dar obțineți rezultat:

Când k=128, n=128:
Avantajul adversarului tău A2 este ~0,0
Când k=256, n=128:
Avantajul adversarului tău A2 este ~0,0
```