Что было бы противником времени O (n) для такой схемы

Предположим, у нас есть блочный шифр. $$E:\{0,1\}^k \text{ x } \{0,1\}^{2k} \rightarrow \{0,1\}^{2n} \quad \text{ с } \ четверка k,n\geq128$$ K — это алгоритм генерации ключей, который возвращает случайный k-битный ключ. Пусть SE = (K,Enc,Dec) будет симметричной схемой шифрования с алгоритмами шифрования и дешифрования, как описано ниже в коде. Ввод сообщения в Enc представляет собой n-битную строку, а зашифрованный текст, вводимый в Dec, представляет собой 4n-битную строку.

Защита Enc(K,M):
    если len(M) != n_bytes : 
        возврат Нет
    
    A1 = случайная_строка (n_bytes)
    A2 = исключающие_строки (M, A1)
    С = []
    C.append(E(K,( A1 + "\x00" * n_bytes )))
    C.append(E(K,( A2 + "\xFF" * n_bytes )))
    вернуться присоединиться (С)


Деф Дек(К,С):
    если len(C) != 4 * n_bytes : 
        возврат Нет

    C = разделить (C, 2 * n_bytes)
    X1 = E_I(K,C[0]) #X1 = A1 || P1 в псевдокоде
    X2 = E_I(K,C[1]) #X2 = A2 || P2 в псевдокоде
    X1 = split(X1,n_bytes) #A1 равно X1[0] ; P1 – это X1[1]
    X2 = split(X2,n_bytes) #A2 равно X2[0] ; P2 – это X2[1]

    если (X1[1] != "\x00" * n_bytes) или (X2[1] != "\xFF" * n_bytes) :
        возврат Нет
    
    M = xor_strings(X1[0],X2[0])
    вернуть М

#ЭТО КУДА ИДЕТ ПРОТИВОПОЛОЖНЫЙ КОД ----- НЕОБХОДИМО ЗАПОЛНИТЬ ЭТО
защита A (enc):
    """
    :param enc: Это оракул, предоставленный игрой.
    возврат: поддельный зашифрованный текст
    """
    проходят

#below проверяет код, чтобы убедиться, что указан правильный противник.
если __name__ == '__main__':    
    к = 128
    п = 128
    k_bytes = k//8
    n_bytes = n//8
 
    EE = BlockCipher(k_bytes, 2*n_bytes)
    E = EE.шифровать
    E_I = EE.decrypt

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

    print ("Когда k=128, n=128:")
    print ("Преимущество вашего противника A2 равно ~" + str(s.compute_advantage()))

    к = 256
    п = 128
    k_bytes = k//8
    n_bytes = n//8

    EE = BlockCipher(k_bytes, 2*n_bytes)
    E = EE.шифровать
    E_I = EE.decrypt

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

    print ("Когда k=256, n=128:")
    print ("Преимущество вашего противника A2 равно ~" + str(s.compute_advantage()))

Какой O(n)-time Adversary может показать, что SE не является безопасным INT-CTXT, делая не более 2 запросов с Advantage = 1 - 2^(-n)

Вот Latex-версия схемы шифрования и дешифрования для удобства чтения:

Шифрование:

$\underline{ Алг E_K(M)}$

$\текст{если} |М| \neq n \text{ затем возврат } \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)$

$\текст{возврат} C$

Расшифровка:

$\underline{ Алг D_K(M)}$

$\текст{если} |С| \neq 4n \text{ затем возврат } \perp$

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

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

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

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

$\text{возврат} M$

Вот что я пробовал до сих пор:

защита A (enc):

    половина = n_bytes // 2
 
    C1 = enc (случайная_строка (n_bytes))
    C2 = enc("\x00" * n_bytes)
    C_split1 = C1[:половина]
    C_split2 = C2[половина:]
       
    вернуть C_split1 + C_split2;

но получить вывод:

При k=128, n=128:
Преимущество вашего противника A2 составляет ~ 0,0
При k=256, n=128:
Преимущество вашего противника A2 составляет ~ 0,0
```