# იდეალური დაცულობა და შენონის თეორემა

შიფრი განისაზღვრება სამ სიმრავლეზე:

- $M$ - შეტყობინებების (plaintext) სიმრავლე,
- $K$ - გასაღებების სიმრავლე,
- $C$ - დაშიფრული შეტყობინებების (ciphertext) სიმრავლე.

შიფრი შედგება ორი ალგორითმისგან

(1) დაშიფრვის (encryption) ალგორითმი: $E : K \times M \to C$,
(2) განშიფრვის (decryption) ალგორითმი: $D : K \times C \to M$

და ასრულებს პირობას
$$ D(k,E(k,m)) = m$$
ყველა $k \in K$ და $m \in M$-ისთვის. ეს პირობა ამბობს, თუ შეტყობინება $m$-ს დავშიფრავთ გასაღები $k$-თი და შემდეგ განვშიფრავთ იმავე გასაღებით, შედეგად ისევ მივიღებთ $m$-ს.

შიფრებზე შეგიძლიათ იფიქროთ ასე: ჰაკერმა, რომელიც უთვალთვალებს კომუნიკაციას, იცის სიმრავლეები $M, K, C$ და დაშიფრვა-განშიფრვის ალგორითმები; ერთადერთი საიდუმლო არის გასაღები $k \in K$, რომელსაც კომუნიკაციის ორი მხარე ირჩევს. ამ ლექციაში შეგვიძლია წარმოვიდგინოთ, რომ საიდუმლო გასაღებებზე შეთანხმება უკვე მოხდა და ორ მხარეს აქვს საზიარო საიდუმლო $k \in K$, რომლის გამოყენებით ვეცდებით ჰაკერის თვალთვალისგან დაცულ კომუნიკაციას. (გასაღების გაცვლაზე ვისწავლით კურსის მეორე ნაწილში).

## იდეალური დაცულობა

რას ნიშნავს, რომ კომუნიკაცია დაცულია თვალთვალისგან? ამის მათემატიკურად ჩამოსაყალიბებლად, წარმოვიდგინოთ კომუნიკაცია ჰაკერის თვალსაზრისით. ის ხედავს დაშიფრულ შეტყობინებას $c = E(k, m)$, იცის რომ $m \in M$, $k \in K$ და ისიც, როგორ მუშაობს დაშიფრვის ალგორითმი $E$ და განშიფრვის ალგორითმი $D$. მას აინტერესებს, რა არის $m$.

თუ ჰაკერს შეუძლია იწინასწარმეტყველოს ჩვენი არჩეული გასაღები $k$, მაშინ ის გამოიყენებს $D$-ს და $k$-ს შეტყობინება $m$-ის აღსადგენად. ამ შეტევისგან დასაცავად, შეგვიძლია გამოვიყენოთ საკმარისად დიდი სიმრალვე $K$ (მაგალითად, $2^{128}$ ზომის) და ავირჩიოთ $k \in K$ უნიფორმულად, ანუ ისე რომ ყველა გასაღებს არჩევის თანაბარი ალბათობა ჰქონდეს. ჰაკერს გაუჭირდება $k$-ს გამოცნობა, რადგან ამის ალბათობაა $1/|K|$. $k$-ს უნიფორმულად არჩევას $K$-დან ამ კონსპექტებში აღვნიშნავთ როგორც $k \leftarrow K$.

თუ ჰაკერმა იცის, რომ ზოგი შეტყობინების დაშიფრვით (ნებისმიერი გასაღებით) არასდროს მიიღება $c$, მაშინ მას შეუძლია გამორიცხოს ეს შეტყობინებები. მეტიც, თუ $c$-ს მიღება ზოგი შეტყობინის დაშიფრვის შემთხვევაში დაბალალბათურია, ის მაინც იძენს უპირატესობას $m$-ის გამოცნობაში. ამის გათვალისწინებით, შეგვიძლია განვსაზღვროთ დაცულობის ყველაზე ძლიერი ვარიანტი (ე.წ. იდეალური დაცულობა ანუ perfect secrecy):

**განმარტება:** შიფრი $(E,D)$, რომელიც მოქმედებს $(M,K,C)$-ზე იდეალურად დაცულია, თუ ნებისმიერი $c \in C$-სთვის და ნებისმიერი ორი შეტყობინება $m_1, m_2 \in M$-ისთვის, სრულდება $\text{Pr}(c = E(k,m_1) \mid k \leftarrow K) = \text{Pr}(c = E(k,m_2) \mid k \leftarrow K)$.

აქ $\text{Pr}(A \mid k \leftarrow K)$ არის ხდომილება $A$-ს ალბათობა იმ პირობით, რომ $k$ უნიფორმულად არჩეულია $K$-დან.

## One-Time Pad

ახლა ავაგებთ იდეალურად დაცულ შიფრს სახელად One Time Pad (OTP).

ამ კურსში $M, K, C$ ძირითადად იქნება ორობითი სტრინგების სიმრავლეები. $n$ სიგრძის ორობითი სტრინგების სიმრავლეს აღვნიშნავთ $\{0,1\}^n$-ით. დავუშვათ, $M = K = C = \{0,1\}^n$ და განვსაზღვროთ შემდეგი შიფრი:

- $E(k,m) = m \oplus k$ და
- $D(k,c) = c \oplus k$

სადაც $\oplus$ აღნიშნავს ბიტურ xor-ს. პირობა $D(k,E(k,m)) = m$ სრულდება რადგან xor არის შებრუნებადი ოპერაცია: $(m \oplus k) \oplus k = m$. იდეალური დაცულობის საჩვენებლად, საკმარისია დავამტკიცოთ, რომ $\text{Pr}(c = E(k,m) \mid k \leftarrow K) = 1 / |K| = (1/2)^n$ ნებისმიერი $m \in M$-სა და $c \in C$-სთვის. რადგან xor მოქმედებს დამოუკიდებლად ყოველ ბიტზე, შევხედოთ $i$-ურ პოზიციას: გვაქვს
$$\text{Pr}(c_i = k_i \oplus m_i \mid k \leftarrow K) = \text{Pr}(k_i = c_i \oplus m_i \mid k \leftarrow K) = 1/2$$ რადგან $c_i$ არის ფიქსირებული მნიშვნელობა (0 ან 1), ხოლო $k_i$ არის უნიფორმულად არჩეული ერთი ბიტი (იფიქრეთ: მონეტის აგდების შედეგი). რადგან ეს ხდომილებები დამოუკიდებელია ყველა $1 \leq i \leq n$-ისთვის, ალბათობა იმისა, რომ ის შესრულება ყველა $i$-სთვის არის $(1/2)^n$.

როგორც ხედავთ, ამ შიფრს სჭირდება საკმაოდ გრძელი გასაღები (როგორც მინიმუმ, შეტყობინების სიგრძის). პრაქტიკული თვალსაზრისით, ეს დიდი პრობლემაა - წარმოიდგინეთ, რომ 40GB-იანი ფაილის დაცულად გაგზავნა გჭიედებათ. ამისთვის 40GB ნამდვილი რენდომის დაგენერირება და გაცვლა მოგიწევთ OTP-ს გამოყენების შემთხვევაში. შენონმა დაამტკიცება, რომ იდეალური დაცულობის პირობებში ეს შეზღუდვა გარდაუვალია.

**თეორემა**: თუ შიფრს, რომელიც მოქმედებს $(M,K,C)$-ზე აქვს იდეალური დაცულობა, მაშინ $|K| \geq |M|$.

ამ თეორემის მორალი ჩვენთვის არის ის, რომ იდეალური დაცულობა ზედმეტად მკაცრი მოთხოვნაა, და კურსის შემდეგ ნაწილებში ვნახავთ, როგორ შეგვიძლია შემოვიღოთ უფრო პრაქტიკული განმარტებები. ამისთვის ჰაკერის უფრო რეალისტურ მოდელს შემოვიღებთ, რომელშიც ის არ არის ყოვლისშემძლე (როგორც იდეალური დაცულობის შემთხვევაში), არამედ შეზღუდულია თავის გამოთვლით ძალაში.