באוניברסיטת בן גוריון יש 2 מערכות הצפנה חדישות: מערכת DES-5 בעלת 5 מפתחות (כל אחד בגודל 56 ביטים) כך שהצפנתה מופעלת באופן הבא: C=DEC_K1(ENC_K2(ENC_K3(DEC_K4(ENC_K5(M)))) כמו כן, נתון כי: K2=K3 K4=K5 ומערכת DES-2 בעלת שני מפתחות (כל אחד בגודל 56 ביטים). לא ידוע כלום על המפתחות שלה. מה יעילות הזמן של לפרוץ את שתי המערכות בהתקפת Brute-Force?

Let's break down the problem and explain why the correct answer is as follows: Understanding DES-5 System: The encryption for DES-5 is structured as: 𝐶 = DEC 𝐾 1 ( ENC 𝐾 2 ( ENC 𝐾 3 ( DEC 𝐾 4 ( ENC 𝐾 5 ( 𝑀 ) ) ) ) ) C=DEC K1 ​ (ENC K2 ​ (ENC K3 ​ (DEC K4 ​ (ENC K5 ​ (M))))) Given: K2 = K3 and K4 = K5, this reduces the system to 3 unique keys: 𝐾 1 K1, 𝐾 2 / 𝐾 3 K2/K3, and 𝐾 4 / 𝐾 5 K4/K5. Since each key is 56 bits, brute-forcing a single key requires testing 2 56 2 56 possible keys. For DES-5, with 3 unique keys to brute-force, the total number of combinations is: Time complexity for DES-5 = 𝑂 ( 2 56 ) × 𝑂 ( 2 56 ) × 𝑂 ( 2 56 ) = 𝑂 ( 2 3 × 56 ) = 𝑂 ( 2 168 ) Time complexity for DES-5=O(2 56 )×O(2 56 )×O(2 56 )=O(2 3×56 )=O(2 168 ) Thus, the brute-force time complexity for DES-5 is O(2^168). Understanding DES-2 System: For the DES-2 system, it uses 2 unknown keys, each 56 bits long. To brute-force both keys, you would have to try all combinations of the two keys, resulting in a time complexity of: Time complexity for DES-2 = 𝑂 ( 2 56 ) × 𝑂 ( 2 56 ) = 𝑂 ( 2 2 × 56 ) = 𝑂 ( 2 112 ) Time complexity for DES-2=O(2 56 )×O(2 56 )=O(2 2×56 )=O(2 112 ) Thus, the brute-force time complexity for DES-2 is O(2^112). Answer: Method A (DES-5) has a brute-force time complexity of O(2^{168}), or O(2^{3 \times 56}). Method B (DES-2) has a brute-force time complexity of O(2^{112}), or O(2^{2 \times 56}). This matches the correct answer: Method A: O(2^{3 \times 56}) Method B: O(2^{2 \times 56})