(tranquil music)
- [Voiceover] Consider the following game.
Eve instructs Bob to go into
a room. (door creaks shut)
Bob finds the room empty,
except for some locks,
an empty box, and a single deck of cards.
Eve tells Bob to select a card
from the deck and hide it as best he can.
The rules are simple.
Bob cannot leave the room with anything,
cards and keys all stay in the room,
and he can put, at most,
one card in the box.
Eve agrees that she has
never seen the locks.
He wins the game if Eve is
unable to determine his card.
So what is his best strategy?
Well, Bob selected a
card, six of diamonds,
and threw it in the box. (box clicks shut)
First he considered the
different types of locks.
Maybe he should lock the
card in the box with the key.
Though, she could pick locks, so he
considers the combination lock.
The key is on the back, so if he locks it
and scratches it off, it
seems like the best choice.
But suddenly he realizes the problem.
The remaining cards on the table
leak information about his choice,
since it's now missing from the deck.
The locks are a decoy. (metal jangles)
He shouldn't separate
his card from the deck.
He returns his card to the deck
but can't remember the
position of his card.
So he shuffles the deck to randomize it.
Shuffling is the best
lock, because it leaves
no information about his choice.
His card is now equally likely
to be any card in the deck.
He can now leave the cards
openly, in confidence.
Bob wins the game, because
the best Eve can do
is simply guess, as he has left
no information about his choice.
Most importantly, even if we give Eve
unlimited computational power,
she can't do any better than a guess.
This defines what we
call "perfect secrecy."
On September first, 1945,
29-year-old Claude Shannon
published a classified paper on this idea.
Shannon gave the first mathematical proof
for how and why the one time
pad is perfectly secret.
Shannon thinks about encryption schemes
in the following way.
Imagine Alice writes a message
to Bob, 20 letters long.
(paper ruffling)
This is equivalent to picking
one specific page from the message space.
The message space can be
thought of as a complete
collection of all possible
20 letter messages.
(paper ruffling)
Anything you can think of that's
20 letters long is a page in this stack.
Next, Alice applies a
shared key, which is a list
of 20 randomly generated
shifts between one and 26.
The key space is the complete collection
of all possible outcomes,
so generating a key is
equivalent to selecting a page
from this stack at random.
When she applies the shift
to encrypt the message,
she ends up with a cipher text.
The cipher text space represents
all possible results of an encryption.
When she applies the key, it maps
to a unique page in this stack.
Notice that the size of the message space
equals the size of the key space
equals the size of the cipher text space.
This defines what we
call "perfect secrecy,"
for if someone has access to
a page of cipher text only,
the only thing that they know is that
every message is equally likely.
So no amount of computational power
could ever help improve a blind guess.
Now the big problem, you're
wondering, with the time pad,
is we have to share these
long keys in advance.
To solve this problem, we
need to relax our definition
of secrecy by developing a
definition of pseudo-randomness.
(white noise)
(প্রশান্তিময় সুর)
[নেপথ্যকণ্ঠে] নিচের খেলাটি দেখো।
ইভ, ববকে একটি রুমের ভিতরে যেতে
নির্দেশ দেয়। (দরজা কড়কড় শব্দে বন্ধ হল)
বব কিছু তালা, একটি খালি বাক্স
এবং একটি তাসের বান্ডিল ছাড়া,
রুমটি খালি দেখতে পায়।
ইভ, ববকে বান্ডিল থেকে একটি কার্ড
নির্বাচন করতে বলে এবং এটাকে যতটা
সম্ভব ভালো করে লুকাতে বলে।
নিয়মগুলো একদম সহজ।
সব কার্ড এং চাবি রুমেই থাকবে,
বব কোন কিছু নিয়ে রুম ত্যাগ করতে পারবে না,
এবং বাক্সে সে সর্বোচ্চ একটি
কার্ড রাখতে পারবে।
ইভ বলেছে, সে তালাগুলো আগে দেখেনি।
সে খেলাটা জিতে যাবে যদি ইভ তার
কার্ডটি বের করতে ব্যর্থ হয়।
তাহলে তার সবচেয়ে ভালো কৌশল কি হবে?
ভালো, বব একটি কার্ড
বাছাই করলো, রুইতন এর ৬,
এবং এটা বাক্সে রাখলো। (বাক্স বন্ধ হল)
প্রথমে সে বিভিন্ন ধরনের
তালা দিয়ে চেষ্টা করলো।
হয়তো তার উচিত ছিল বাক্সে
চাবিসহ তালা লাগানো।
যা হোক, ইভ তালা বাছাই করতে পারে, তাই বব
কম্বিনেশন তালা দিয়ে লক করলো।
চাবি ঘুরিয়ে, তাহলে সে যদি
এটা দিয়ে তালা দেয়
এবং এটা মুছে ফেলে, তাহলে এটাই
সবচেয়ে ভালো উপায় মনে হচ্ছে।
কিন্তু হঠাৎ সে সমস্যাটি
উপলব্ধি করতে পারলো।
টেবিলে থাকা বাকী কার্ডগুলো তার বাছাই
করা সম্পর্কে তথ্য ফাঁস করবে।
কারণ এটা এখন এখানে পাওয়া যাবে না।
তালাগুলো একটা ফাঁদ। (ধাতুর কর্কশ শব্দ)
বান্ডিল থেকে তার কার্ড
পৃথক করা ঠিক হবে না।
সে তার কার্ড বান্ডিলে ফেরত দিলো
কিন্তু তার কার্ডের অবস্থান
মনে করতে পারলো না।
তাই সে এটা এলোমেলো করার
জন্য বান্ডিল অদলবদল করলো।
অদলবদল করা সবচেয়ে বড় লক, কারণ এটা
তার বাছাই সম্পর্কে কোন তথ্য রাখবে না।
তার কার্ড এখন বান্ডিলের অন্য
কার্ডের মত একই রকম।
সে এখন নিশ্চিন্তে কার্ডটি খোলা রাখতে পারে।
বব খেলাটি জিতেছে কারণ সে যেহেতু
তার বাছাই সম্পর্কে কোন তথ্য রাখেনি,
তাই ইভ বড়জোড় শুধু অনুমান করতে পারে।
সবচেয়ে গুরুত্বপূর্ণ হল,
এমনকি আমরা যদি ইভকে
হিসাব করার সীমাহীন ক্ষমতাও দিয়ে দিতাম,
সে শুধু অনুমান ছাড়া আরও
ভালো কিছু করতে পারতো না।
এটাকে আমরা “পারফেক্ট সিক্রেসি” বলি।
১৯৪৫ সালের পহেলা সেপ্টেম্বরে,
২৯ বছর বয়সী ক্লদে শ্যানোন
এই ধারণার উপর একটি বিশেষায়িত
লিখা প্রকাশ করেছিলেন।
শ্যানোন প্রথম গাণিতিক প্রমাণ দেয় কেন এবং
কিভাবে যে কোন সময়ের
প্যাড পারফেক্টলি সিক্রেট হবে।
শ্যানোন নিম্নলিখিত উপায়ে
এনক্রিপশন পদ্ধতি চিন্তা করেছে।
মনে করো, এ্যালিস ববকে একটি
২০টি অক্ষরের মেসেজ লিখেছে।
(কাগজের তরঙ্গায়ন)
এটা মেসেজের স্থান থেকে একটি
নির্দিষ্ট পৃষ্ঠা তোলার সমান।
মেসেজের স্থান সম্ভাব্য ২০ অক্ষরের মেসেজের
সম্পূর্ণ রাশি হিসেবে ধারণা করা হতে পারে।
(কাগজের তরঙ্গায়ন)
এই স্তুপের যে কোনটি তুমি ঐ
২০ অক্ষরের কাগজ মনে করতে পারো।
পরবর্তীতে, এ্যালিস একটি
চাবি ব্যবহার করলো,
যা এক এবং ২৬ এর মধ্যে ২০ বার এলোমেলোভাবে
স্থান পরিবর্তনে প্রস্তুতকৃত একটি তালিকা।
চাবির স্থান হল সম্ভাব্য
সব ফলাফলের সম্পূর্ণ সংগ্রহ,
তাহলে একটি চাবি তৈরি হল এলোমেলোকৃত
এই স্তুপ থেকে একটি পৃষ্ঠা
নির্ধারণ করার সমতুল্য।
যখন মেসেজ এনক্রিপ্ট করতে সে
স্থান পরিবর্তন পদ্ধতি প্রয়োগ করলো,
সে একটি সংকেত বাক্য দিয়ে শেষ করলো।
সংকেত বাক্যের স্থান একটি এনক্রিপশনের
সকল সম্ভাব্য ফলাফল উপস্থাপন করে।
যখন সে চাবি প্রয়োগ করে, এটা এই স্তুপের
একটি একক পৃষ্ঠাতে অংকন করে।
লক্ষ্য করো যে মেসেজ স্থানের আকার
সমান চাবির স্থানের আকার
সমান হল সংকেত বাক্য স্থানের আকার।
এটাকে আমরা “পারফেক্ট সিক্রেসি” বলি,
যদি কারো শুধু সংকেত বাক্যের
পৃষ্ঠাতে প্রবেশের অধিকার থাকে,
তারা একটা বিষয়ই জানে যে
প্রত্যেকটি মেসেজ সমতুল্য।
সুতরাং কোন হিসাব ক্ষমতাই একটি
অস্পষ্ট অনুমান কে সাহায্য করতে পারবে না।
এখন বড় সমস্যা হল, তুমি
সময় কে নিয়ে বিস্মিত হবে,
আমাদের অগ্রিম এই দীর্ঘ চাবি
শেয়ার করতে হতে পারে।
এই সমস্যার সমাধানে, আমাদের
সুডো-এলোমেলোকরণ এর সংজ্ঞা তৈরির মাধ্যমে
সিক্রেসির সংজ্ঞা শিথিল করতে হবে ।
(ঝিরঝির শব্দ)
Představte si takovouto hru:
Eve poví Bobovi, aby šel do pokoje.
Bob zjistí, že v pokoji nic není,
kromě několika zámků, prázdné skříňky a balíku karet.
Eve řekne Bobovi, aby vybral kartu
a co nejlépe ji ukryl.
Pravidla jsou jednoduchá.
Bob nemůže z místnosti nic odnést.
Nesmí sebou vzít ani karty nebo klíče.
a do skříňky může dát jen jednu kartu.
Eve odpřísáhla, že zámky nikdy ani neviděla.
Bob vyhraje, když Eve nedokáže určit jeho kartu.
Jak by tedy měl postupovat?
Bob si vybral károvou šestku
a vložil ji do skříňky.
Nejdříve přemýšlel nad různými zámky.
Možná by měl zamknout kartu v krabičce zámkem s klíčem.
Jenže Eve dokáže zámky vypáčit.
Zvažuje i použití kombinačního zámku.
Kód je na zadní straně,
takže uzamčení a seškrábání kódu zní jako nejlepší možnost.
Ale pak si uvědomí problém.
Karty, které zůstaly na stole poskytují informaci o jeho volbě,
protože jedna karta v balíku chybí.
Zámky jsou návnada.
Neměl by kartu oddělit od balíku.
Vrátí tam tedy svoji kartu.
Ale nepamatuje si její pozici v balíku.
Tak zamíchá kartami, aby byly rozmístěné náhodně.
Míchání je nejlepším zámkem,
neboť nezanechává žádné informace o jeho volbě.
Teď může být jeho karta jakoukoliv kartou v balíku.
Může takto karty bezpochyby zanechat.
Bob hru vyhraje,
protože Eve může jen hádat.
Bob totiž nezanechal žádnou informaci o jeho volbě.
Ale hlavně,
i kdyby měla Eve neomezenou výpočetní sílu,
stále by mohla jen hádat.
To se nazývá dokonalé zabezpečení.
1. září 1945 zveřejnil 29 letý Claude Shannon
tajnou práci o této myšlence.
Shannon poprvé matematicky dokázal,
proč a jak je Vernamova šifra úplně bezpečná.
Shannon o šifrování přemýšlel takto:
Představte si, že Alice píše Bobovi zprávu o 20 písmenech.
To je jakoby vybrala 1 specifickou stránku z prostoru zpráv.
Prostor zpráv si můžeme představit jako
kompletní soubor všech zpráv o 20 písmenech.
Vše, co má délku 20 písmen
je stránkou v této hromadě.
Následně Alice použije společný klíč,
tedy seznam 20 náhodných posunů mezi 1 a 26.
Prostor klíčů je sbírka všech možných výstupů.
Takže vytvoření klíče je stejné
jako náhodný výběr z hromady.
Když Alice použije posuny na šifrování,
vznikne šifrovaný text.
Prostor šifrovaných zpráv reprezentuje
všechny možné výsledky šifrování.
Když použije klíč,
dostane se k jedinečné stránce v hromadě.
Všimněte si, že velikost prostoru zpráv
je stejná jako velikost prostoru klíčů i prostoru výsledných zašifrovaných zpráv.
To definuje takzvané dokonalé zabezpečení.
Pokud má někdo přístup k zašifrovanému textu,
tak jedinou věc, kterou ví je, že každá zpráva je stejně pravděpodobná.
Takže žádná výpočetní síla nám nepomůže zpřesnit naše hádání.
Velký problém Vernamovy šifry je způsob předchozího předání dlouhého klíče.
Abychom tento problém vyřešili,
musíme zvolnit u naší definice zabezpečení
vytvořením definice pseudo-náhodnosti.
(musica)
Immaginate: Bob va in una stanza vuota,
ha lucchetti, carte ed una scatola vuota
Bob sceglie una carta dal mazzo
e la nasconde.
Le regole sono semplici: Bob non può
portare nulla con sé uscendo dalla stanza
e al più può mettere una carta
nella scatola
Eva non ha mai visto i lucchetti
Bob vince se Eva non riesce ad
indovinare la carta da lui scelta
Quale strategia è ottimale?
Bob seleziona, diciamo, il 6 di quadri
e lo mette nella scatola
Poi osserva i diversi tipi di lucchetto
Forse deve infilare la chiave del
lucchetto nella scatola
O forse è meglio scegliere un lucchetto
a combinazione
Combinazione è scritta sul retro, se la
graffia via forse è la strategia migliore
D'un colpo realizza che le carte restanti
sul tavolo riveleranno la sua scelta
perché una mancherà dal mazzo
I lucchetti sono un diversivo
Non deve estrarre la carta,
deve invece lasciarla nel mazzo
Non ricorda la posizione della carta e
mischia il mazzo in modo casuale
Mescolare è il miglior lucchetto. Non fa
trapelare informazione sulla vostra scelta
Ora la carta scelta può essere
una qualsiasi
Ora può lasciare le carte in vista
Bob vince perché Eva può solo tirare a
sorte dato che Bob non ha lasciato tracce
Pure se Eva avesse una potenza di calcolo
illimitata, può solo tirare a sorte
Questa è la definizione di
SEGRETEZZA PERFETTA
Il 1 Settembre 1945 C. Shannon pubblicò
un articolo classificato al riguardo.
Shannon dimostrò che il codice
di Vernam è perfettamente segreto
Shannon ragiona nei seguenti termini:
Immaginiamo che Alice scriva un messaggio
lungo 20 caratteri a Bob
Questa situazione è come scegliere
una pagina dallo spazio dei messaggi
che può pensarsi è come l'insieme di tutti
i possibili messaggi lunghi 20 caratteri
Qualunque cosa a cui possiate pensare, se
è lunga 20 caratteri, è pagina della pila
Alice utilizza una chiave condivisa,
che è una lista di 20 traslazioni casuali
Lo spazio delle chiavi è l'insieme
di ogni possibile risultato
Scegliere una chiave è equivalente a
scegliere una pagina nella pila
Traslando la sequenza del messaggio
originario genera il messaggio cifrato
Lo spazio dei testi cifrati rappresenta
tutti i risultati possibili della codifica
Applicando la chiave, ella sceglie una
pagina specifica in questo insieme
Lo spazio dei messaggi ha la stessa
dimensione dello spazio delle chiavi
Questa proprietà definisce la
segretezza perfetta
chi ha solo il messaggio cifrato sa solo
che ogni messaggio è parimenti probabile
Questo vuol dire che niente può aiutarci
visto che dobbiamo tirare a caso
Problema col codice di Vernam è doversi
scambiare le chiavi in anticipo
Per risolvere questo problema è necessario
introdurre il concetto di pseudo-casualità
こんなゲームを考えてみましょう。
イヴがボブに部屋に行くように指示しました。
部屋には、いくつかの鍵と、空っぽの箱、
一組のトランプカードの他には
何もありません。
イヴはボブにカードを1枚選んで
思いつく最高の隠し方で隠せと言いました。
ルールは簡単。
ボブは部屋の外に何かを持ちだしてはいけません。
カードと鍵は全て部屋の中になければいけません。
また、箱の中にカードを1枚しか入れてはいけません。
イヴは鍵を持っていません。
イヴが、隠されたカードが分からないならボブの勝ちです。
どうするのが最善でしょう?
ボブはダイヤの6を選びました。
そして箱に入れました。
最初、彼は何種類かある鍵を見て
南京錠でカードの入った箱に鍵をしようと考えました。
しかし、イヴはピッキングできます。
そこで、彼はダイヤル錠を選びました。
ダイヤル番号は鍵の後ろに書いてありますが、
それさえ消してしまえばピッキングは困難です。
これは最もいい選択のように思えます。
しかし、彼は問題点に気づきました。
テーブルの上に残されたカードを見て
どのカードが無いのか考えれば、
選んだカードがわかってしまいます。
箱の鍵はおとりでした。
選んだカードを山と別の場所におくべきでないのです。
ボブはカードを山に戻しました。
しかし、彼は選んだカードがどこにあったかわかりません。
なのでシャッフルして、十分にまぜました。
混ぜることが一番の隠し方なのです。
なぜなら、何を選んだかの情報がどこにも残らないからです。
混ぜたことで選ばれたカードは他のカードと
「同様に確からしく」なりました。
あとはカードの山を堂々と置いておけばよいのです。
これでボブの勝ちです。
イブはどんな情報も得られないので、
彼女にできることは、ただの推測しかありません。
最も重要なのは、
どんなに強力な計算能力を持っていたとしても、
イヴは推測以上のことはできないということです。
このことを、「完全秘匿(ひとく)」といいます。
1945年9月1日、29歳のクロード・シャノンが
このことを取り扱った論文を発表しました。
シャノンはどうしてワンタイムパッドがどうして解読不可能かを
始めて数学的に証明しました。
シャノンは暗号化の方法についてこのように考えました。
アリスが20字の文をボブに送る
という場面を考えてみましょう。
これはある一枚の紙を
「平文空間」から選び出すのと同じ事です。
ここでの「平文空間」とは、
20文字でできる全ての組み合わせの集合体です。
考えられるどんな20文字の文章も、
このなかに含まれています。
つぎにアリスは、1~26の数を20個使った
全ての組み合わせの表を用いて
「鍵空間」を作ります。
「鍵空間」は、あり得るすべての暗号の寄せ集めです。
つまり、暗号の鍵を作るのはこの「鍵空間」から
どれか1枚を無作為に選ぶのと同じ事です。
アリスが文章を暗号化し終えると、
最初の平文の代わりに「暗号文」が残ります。
「暗号文空間」は、ある暗号化を施した時の
あり得るすべての結果を表しています。
アリスが暗号の鍵を使うと、
全ての山の中から特定のページを指し示すことができます。
このとき、
「平文空間」 と 「鍵空間」 と 「暗号文空間」
このとき、
「平文空間」 と 「鍵空間」 と 「暗号文空間」
3つの大きさはすべて同じになります。
これが、「完全秘匿(ひとく)」です。
もし誰かが、「暗号文空間」のみに
アクセスできたとしても、
知ることができるのは、
あらゆる文章が「同様に確からしい」ということだけです、
どんなに計算能力があったとしても、
元の文を探る推測の助けにはなりません。
ワンタイムパッドの問題は、
膨大な長さの暗号化表を
共有しておかなければならないという点です。
この問題を解決するためには、
「秘匿性」について少し妥協して、
「疑似乱数」を使うことになります。
[მუსიკა]
განიხილეთ ეს თამაში
ევა აცნობებს ბობს, რომ შევიდეს ოთახში
ბობი ხედავს, რომ ოთახში არაფერია,
გარდა რამდენიმე ბოქლომის
ცარიელი ყუთის და კარტის დასტისა
ევა სთხოვს ბობს აირჩიოს ერთი
კარტი დასტიდან
და დამალოს ისე, როგორც შეუძლია
წესები მარტივია
ბობს არ შეუძლია ოთახიდან რაიმეს გატანა
კარტები, გასაღებები და სხვა ყველაფერი
ოთახში უნდა დარჩეს
ხოლო ყუთში მაქსიმუმ ერთი
კარტის ჩადება შეუძლია
ევა პირობას დებს, რომ არასოდეს
უნახავს საკეტები
ბობი თამაშს მოიგებს, თუ ევა ვერ
აღმოაჩენს მის კარტს
რა არის საუკეთესო სტრატეგია ბობისთვის ?
ბობმა აირჩია კარტი, აგურის ექვსიანი
და ჩააგდო ყუთში
თავიდან განიხილა განსხვავებული
სახის საკეტები
შეუძლია კარტი ყუთში
ჩაკეტოს გასაღებთ
თუმცა, შესაძლოა ევამ იცის
საკეტების გატეხვა,
ამიტომ ბობი გადაწყვეტს კომბინაციური
საკეტის გამოყენებას
გასაღები უკანაა და ყუთის დაკეტვა
და გასაღების გადაგდება, ყველაზე
კარგ ვარიანტად მოსჩანს
თუმცა უცებ ბობი ხვდება პრობლემას
მაგიდაზე დარჩენილი კარტები გასცემენ
ინფორმაციას მისი არჩევანის შესახებ
რადგან მის მიერ არჩეული კარტი
აღარაა დასტაში
საკეტები სინამდვილეში სატყუარას
წარმოადგენს
მან კარტი დასტისაგან არ უნდა
გამოყოს
ის თავის კარტს დასტაში აბრუნებს
მაგრამ ვერ იხსენებს კარტის პოზიციას
ამიტომ ბობი არევს კარტის დასტას
რომ შემთხვევითად აქციოს
დასტის არევა ყველაზე კარგი საკეტია
რადგან არ ტოვებს ინფორმაციას
ბობის არჩევანის შესახებ
ამ შემთხვევაში, მისი კარტი შეიძლება იყოს
ამ დასტის ნებისმიერი კარტი
ახლა, შეუძლია თავდაჯერებულად
დამალვის გარეშე დატოვოს კარტები
ბობი იგებს თამაშს, რადგან საუკეთესო
რაც ევას ძალუძს
არის მხოლოდ ვარაუდის გამოთქმა,
რადგან ბობმა
საკუთარი არჩევანის შესახებ
არანაირი ინფორმაცია არ დატოვა
რაც ყველაზე მთავარია, თუ ევას მივცემთ
უსაზღვრო კომპიუტერულ შესაძლებლობებს
ვარაუდის გარდა სხვა გზა მაინც არ ექნება
ეს გამოხატავს იმას, რასაც ჩვენ
"სრულყოფილ საიდუმლოს"
1945 წლის პირველ სექტემბერს
29 წლის კლოდ შენონმა
ამ იდეის შესახებ გამოსცა
სისტემატიზებული ნაშრომი
შენონმა პირველმა დაამტკიცა მათემატიკურად
რატომ და როგორ არის ვერნამის შიფრი
სრულყოფილად გასაიდუმლებული
შენონი დაშიფვრის სქემების შესახებ
ამგვარად ფიქრობდა:
წარმოიდგინეთ, რომ ალისა ბობს სწერს
20 ასოიან წერილს
ეს შეტყობინებათა სივრციდან ერთი
კონკრეტული გვერდის შერჩევის ეკვივალენტურია
შეტყობინებათა სივრცე შეიძლება აღვიქვათ
როგორც ყველა 20 ასოიანი წერტილის
საერთო სივრცე
ნებისმიერი რამ, რისი წარმოდგენაც შეგიძლიათ
და შედგება 20 ასოსაგან
იქნება ამ დასტის ნაწილი
შემდგომ, ალისა იყენებს საზიარო გასაღებს,
რაც წარმოადგენს ოც შემთხვევით ცვლილებას
ერთიდან 26-მდე რომელიმე
რიცხვის შესაბამისად
გასაღებთა სივრცე არის ყველა შესაძლო
შედეგის სრული კოლექცია
ამიტომ, გასაღების შედგენა უტოლდება ამ
დასტიდან ერთი გვერდის შემთხვევით შერჩევას
როდესაც ალისა იყენებს ცვლილებას
შეტყობინების დასაშიფრად
ის შედეგად ირებს შიფრის ტექსტს
შიფრის ტექტსი სივრცე წარმოადგენს
დაშიფვრის ყველა შესაძლო ვარიანტს
როდესაც ალისა იყენებს გასაღებს,
ის ამ დასტის უნიკალურ წევრს აღნიშნავს
დაუკვირდით, რომ შეტყობინების სივრცე
უტოლდება გასაღების სივრცის ზომას
რაც აგრეთვე უტოლდება
შიფრის სივრცის ზომას
შედეგად მივიღეთ ე.წ
"სრულყოფილი საიდუმლოება"
რადგან, თუ ვინმეს ექნება წვდომა
შიფრის ტექსტის გვერდზე
ერთადერთი, რაც ეცოდინებათ ისაა, რომ ყველა
შეტყობინება ერთნაირად შესაძლებლია
გამოდის რომ, კომპიუტერული შესაძლებლობების
არცერთ დონეს არ ძალუძს
ბრმა ვარაუდის შედეგის გაუმჯობესება
ახლა კი დიდი პრობლემა, ვერნამის
შიფრის გამოყენებისას
იძულებული ვართ ეს გრძელი
გასაღებები წინასწარ გავაზიაროთ
ამ პრობლემის გადასაწყვეტად, უნდა
შემოვიტანოთ ფსევდო-შემთხვევითობის ცნება
(고요한 음악)
[해설] 다음 게임을 자세히 생각해보세요
이브는 밥이 방으로 들어가도록 지도합니다
(문 삐걱거리며 닫힘)
밥은 방이 비어있는 것을 발견합니다
몇 개의 자물쇠와
빈 상자 하나, 카드 한 무더기를 제외하고요
이브는 밥에게 카드 한 장을 고르고
그가 할 수 있는 한 가장 잘 숨겨보라고 이야기 합니다
규칙은 간단합니다
밥은 무엇도 가지고 나갈 수 없고,
카드와 열쇠를 모두 방안에 두어야 하며
상자에는 최대 한 장의 카드를 넣을 수 있습니다
이브는 그녀가 자물쇠를 본 적 없다는 데에 동의합니다
이브가 그의 카드를 짐작할 수 없다면 그는 게임에서
이기게 됩니다
그렇다면 밥의 최고의 전략은 무엇일까요?
밥은 6 다이아몬드 카드를 골랐고
상자에 던져 넣었습니다 (박스 딸깍하며 닫힌다)
먼저 그는 다양한 종류의 자물쇠를 고려했습니다
그는 열쇠를 이용하여 카드를 박스에 잠가 넣을 수도
있겠죠
하지만, 이브가 자물쇠를 고를 수 있기 때문에
밥은 번호 자물쇠를 고려합니다
열쇠가 뒤에 있기 때문에, 만약에 그가 잠구고
지워버리면, 가장 좋은 선택이 될 것처럼 보입니다
하지만 그는 갑자기 문제점을 깨닫습니다
테이블 위에 남아 있는 카드가
그의 선택에 관한 정보를 누설하고 있다는거죠
이제 카드더미에 들어있지 않으니까요
자물쇠는 유인용이었던 겁니다 (금속 쨍그랑한다)
그는 그의 카드를 팩에서 빼면 안되는 것이죠
그는 그의 카드를 팩으로 돌려 놓지만
그가 고른 카드의 위치를 기억하지 못합니다
그래서 그는 카드더미를 섞어 순서를 임의로 바꿉니다
섞는 것은 가장 좋은 자물쇠죠, 왜냐하면
그의 선택에 대한 정보를 남기지 않기 때문입니다
그의 카드는 이제 무더기 속 아무 카드라도
될 수 있습니다
그는 이제 자신감을 가지고 카드를 공개적으로 놔둘 수 있습니다
밥이 게임에서 이기게 됩니다, 왜냐하면
그가 선택에 대해 아무런 정보도 남기지 않았기에
이브가 할 수 있는 전부는 그저 예상하는 것 뿐이죠
가장 중요한 것은, 만일 우리가 이브에게
무한한 계산적 힘을 준다고 하더라도
그녀가 할 수 있는 최선은 상상하는 것이라는 겁니다
이것은 우리가 "완전 비밀성" 이라고 부르는 것을 정의합니다
1945년 9월 1일, 29살의 클라우드 섀넌 은
이 아이디어를 가지고 기밀 서류를 발행했습니다
섀넌은 일회용 암호표가 어떻게, 그리고 왜
완전히 비밀로 유지되는지에 대한 첫 수학적 근거를 제시했습니다
섀넌은 암호 시스템에 대해서
다음과 같이 생각합니다
앨리스가 밥에게 20자 길이의 메시지를 쓴다고
상상해 봅시다
(종이에 물결이 인다)
이것은 메시지 공간에서
하나의 특정 페이지를 고르는 것과 같습니다
메시지 공간은 모두 사용 가능한 20자 메시지의
온전한 모음으로 생각될 수 있습니다
(종이에 물결이 인다)
당신이 20자 길이로 생각 할 수 있는 모든 것은
이 묶음에서 하나의 페이지 입니다
다음으로 앨리스는 공유키를 적용하는데, 이는
1과 26 사이에서 임의로 발생하는 20개의 변화의
목록입니다
키 스페이스는 모든 가능한 결과의
온전한 모음이라, 키를 만들어내는 것은
임의로 이 묶음에서 페이지하나를 고르는 것과
마찬가지이죠
그녀가 메시지를 암호화하기 위해 변화를 적용할때
숫자 텍스트와 맞닥뜨리게 되죠
숫자 텍스트 공간은
암호화의 가능한 모든 결과를 나타냅니다
그녀가 키를 적용할 때 그 키는 이 묶음에서
독특한 페이지로의 지도를 그립니다
'메시지 공간' 의 크기는
키 공간의 크기와 같고
숫자 텍스트 공간의 크기와도 같다는 걸 알아두세요
이것은 우리가 "완벽한 비밀성" 이라고 부르는 것을 정의합니다
만약 누군가가 숫자 텍스트에만 접속 할 수 있다면
그들이 아는 유일한 것은
모든 메시지가 동등하게 가능성이 있다는 것이죠
그러므로 어떤 계산적 힘도
어림짐작을 개선시킬 순 없다는 겁니다
이제 당신이 궁금해하는, 암호표에 관한 문제는
우리가 이 암호들을 공유해야한다는 것이죠
이 문제를 해결하기 위해서 우리는 비밀성에 대한 우리의 정의를 완화해야 합니다
의사 랜덤의 정의를 개발함으로써요
(백색소음)
ျငိမ္သက္ေအးခ်မ္းေသာ ဂီတ
ေအာက္ပါ ဂိမ္း ကိုစဥ္းစားပါ။
ဧဝက Bob ကိုအခန္းထဲသြားဖို႔ေျပာတယ္
Bob ကအခန္းထဲမွာ ေသာ့တခၽိဳ႕ကလြဲျပီး ရွင္းေနတာေတြ႕တယ္
ေသတၱာလြတ္တလံုး နဲ႔ ဖဲခ်ပ္တထုပ္
ဧဝက ကတ္တကတ္ေရြးဖို႔ Bob ကိုေျပာတယ္
ထိုေရြးထားေသာကတ္ကို Bob ကေသခ်ာဖြက္ရမယ္
ဂိမ္းစည္းမၽဥ္းကေတာ့ ရွင္းပါတယ္
Bob ကအခန္းထဲကေန ဘာတခုမွယူမလာရဘူး
ကတ္တြ ေသာ့ေတြ အကုန္ထားခဲ့ရမယ္
Bobဟာ ေသတၱာထဲမွာ ဖဲကတ္တခၽပ္အမ်ားဆံုးထည့္ထားနိင္ပါတယ္
ဧဝက ေသာ႔ေတြကိုတခါမွမျမင္ဖူးထားဘူးလို႔ေျပာပါတယ္
ဧဝက Bobဖြက္တဲ႔ဖဲခ်ပ္ကိုမေျပာနိုင္ရင္ ဒီဂိမ္း ကို သူမရွုံးပါမယ္
Pomyślcie o następującej grze.
Ewa każe Bobowi wejść do pokoju.
Bob widzi, że nie ma tam nic
poza kilkoma kłódkami,
pustym pudełkiem i talią kart.
Ewa każe Bobowi wybrać kartę z talii
i jak najlepiej ją ukryć.
Zasady są proste. Bob nie może
niczego stamtąd wynieść;
karty i kluczyki zostają w pokoju;
do pudełka można włożyć
co najwyżej jedną kartę.
Ewa mówi, że nigdy
nie widziała tych kłódek.
Bob wygra, jeśli Ewa nie zdoła
określić, którą wybrał kartę.
Jaka będzie najlepsza strategia?
Bob wybrał kartę, szóstkę karo,
i wrzucił ją do pudełka.
Najpierw pomyślał
o różnych typach zamków.
Może powinien zamknąć kartę
w pudełku na klucz?
Ale Ewa może mieć wytrych,
więc Bob myśli o zamku cyfrowym.
Klucz jest z tyłu. Najlepiej będzie
zamknąć i pomieszać cyfry.
Nagle Bob coś sobie uświadamia:
pozostałe karty na stole
przekażą informację o jego wyborze,
bo teraz jednej brakuje.
Zamki służą odwróceniu uwagi!
Nie powinien wyciągać
karty z talii.
Wkłada ją z powrotem.
Nie pamięta, gdzie dokładnie była.
Tasuje więc karty
dla większej losowości.
Tasowanie to najlepszy zamek,
bo nie pozostawia
informacji o wyborze.
Teraz jego karta
może być każdą w talii.
Bob może zostawić karty na wierzchu.
Bob wygrywa, ponieważ Ewa
może co najwyżej zgadywać.
Nie pozostawił informacji
o swoim wyborze.
Co ważniejsze, nawet jeśli damy Ewie
nieograniczoną moc obliczeniową,
będzie ona mogła tylko zgadywać.
To właśnie jest tzw.
„tajność doskonała”.
1 września 1945 r.
29-letni Claude Shannon
opublikował utajniony
artykuł na ten temat.
On pierwszy
matematycznie dowiódł,
że szyfr z kluczem jednorazowym
jest doskonale tajny.
Oto, jak Shannon myślał
o schematach szyfrowania.
Wyobraźcie sobie, że Alicja pisze
20-literową wiadomość do Boba.
To ekwiwalent wybrania
jednej kartki
z przestrzeni wiadomości.
A przestrzeń wiadomości
to kompletny zbiór
wszystkich możliwych
wiadomości 20-literowych.
Wszystko 20-literowe, co przyjdzie wam
do głowy, jest kartką w tym stosie.
Teraz Alicja stosuje wspólny klucz,
listę 20 losowo wygenerowanych
podstawień między 1 a 26.
Przestrzeń kluczy jest zbiorem
wszystkich możliwych wyników,
więc wygenerowanie klucza
to ekwiwalent
losowego wyboru strony z tego stosu.
Alicja stosuje klucz
do zakodowania wiadomości
i uzyskuje szyfrogram.
Przestrzeń szyfrogramów to wszystkie
możliwe wyniki szyfrowania.
Zastosowanie klucza odeśle Alicję
do jednej kartki z tego stosu.
Zauważcie, że przestrzeń
wiadomości
ma wielkość przestrzeni kluczy
i przestrzeni szyfrogramów.
To definiuje „tajność doskonałą”.
Bo jeśli ktoś ma dostęp wyłącznie
do strony z szyfrogramem,
to wie tylko, że każda wiadomość
jest równie prawdopodobna.
Żadna moc obliczeniowa
nie poprawi skuteczności zgadywania.
Problem z kluczem jednorazowym
jest taki, że musimy
wcześniej przekazać
sobie długie klucze.
By rozwiązać ten problem,
musimy zmienić definicję tajności,
wprowadzając pseudolosowość.
(Musica tranquila)
[Voz] Considere o seguinte jogo
Eve diz para Bob entrar em uma sala
(porta fecha)
Bob acha a sala vazia
Exceto por alguns cadeados
uma caixa vazia e um baralho
Eve diz para Bob escolher uma carta
do baralho e esconder o melhor
que ele puder
As regras são simples
Bob não pode sair da sala com nada
Cartas e chaves ficam na sala
e ele pode colocar, no máximo,
uma carta na caixa.
Eve concorda que ela nunca viu os cadeados
Ele ganha o jogo se Eve não
for capaz de adivinhar sua carta.
Então, qual é a melhor estratégia?
Bem, Bob escolhe uma carta,
seis de ouros
e joga na caixa.(caixa fecha)
Primeiro ele considera os
diferentes tipos de cadeados
Talvez ele deva travar a carta
na caixa com o cadeado de chave.
Embora, ela pode pegar outro cadeado,
então ele
considerou a combinação de trava
A chave está atrás, então se ele fechar
e arranhar parece ser a melhor escolha
Mas de repente ele percebe o problema
As cartas que ficaram na mesa
deixa pistas da sua escolha
desde que agora está faltando no baralho
Os cadeados são uma armadilha
Ele não deveria separar sua
carta do baralho.
Ele devolve a carta
ao baralho
mas não pode lembrar a posição
da sua carta
Então ele embaralha as cartas
Embaralhar é a melhor escolha,
porque não deixa
nenhuma informação sobre sua escolha
Agora sua carta pode ser
qualquer uma no baralho
Agora ele pode deixar as cartas abertas
Bob ganha o jogo, porque
o melhor que Eve pode fazer
é tentar advinhar, e ele não
deixou nenhuma informação sobre
sua escolha
Mais importante, mesmo se nós
déssemos
a Eve um poder de computação ilimitado
ela só poderia tentar advinhar
Isto define o que chamamos de
"segredo perfeito"
Em primeiro de setembro de 1945,
Claude Shannon, 29 anos
publicou um artigo desta ideia
Shannon deu a primeira prova matemática
de como e porque chave de
uso único de uma vez é o segredo perfeito
Shannon pensou em esquemas de criptografia
assim
Imagina que Alice escreve uma mensagem
para Bob, com 20 letras.
(som de papel)
Isto é como pegar
uma página do espaço de mensagens
O espaço de mensagens pode ser
pensado como a coleção
de todas mensagens possíveis
com 20 letras
(som de papel)
Qualquer coisa que você
imaginar com 20 letras desta pilha
Agora, Alice aplica uma chave
compartilhada
que é uma lista aleatória de 20
unidades entre 1 e 26
O espaço da chave é a coleção completa
de todas as possíveis saídas
então gerar a chave é
como selecionar uma página da pilha
aleatóriamente
Quando ela aplica o deslocamento na
mensagem encriptada
ela termina com um texto criptografado
Este texto criptografado representa
todas os possíveis resultados da
encriptação
Quando ela alica a chave, ela mapeia
para uma única página na pilha
Veja como o tamanho do espaço da mensagem
é igual ao tamanho do da chave
e igual ao tamanho do espaço do texto.
Isto define o que chamamos de
segredo perfeito
Se alguém tiver acesso a uma página
com texto criptografado
a única coisa que ele saberá é
todas as mensagens são parecidas
Nenhum poder computacional
poderia ajudar a advinhar
Agora o grande problema, você deve
perguntando
nós enviamos estas grandes chaves antes?
Para resolver este problema,nós
precisamos relaxar nossa definição
de segredo desenvolvendo uma
definição de pseudo-aleatoriedade
Lição apresentada por:
Brit Cruise
Considere o seguinte jogo:
Eva instrui Bob para entrar em uma sala.
Bob encontra a sala vazia,
com exceção de alguns cadeados,
uma caixa vazia, e um baralho de cartas.
Eva diz Bob para selecionar uma carta
a partir do baralho e escondê-lo
da melhor maneira possível.
As regras são simples:
Bob não pode sair da sala
com qualquer coisa,
cartões e chaves têm que ficar
tudo dentro no quarto,
e ele pode colocar, no máximo,
uma carta na caixa.
Eva concorda que ela nunca
viu os cadeados.
Ele ganha o jogo se Eva não for capaz
de descobrir a sua carta.
Então, qual é a sua melhor estratégia?
Bob selecionou um carta, seis de ouro,
e jogou-o na caixa.
Primeiro, ele considerou os diferentes
tipos de cadeados.
Talvez ele deve trancar a carta na caixa
com o cadeado com a chave dentro.
No entanto, ela poderia escolher os
cadeados, então ele
considera o cadeado com combinação.
A senha está na parte de trás, por isso,
se ele trancá-lo
e riscar a senha, parece ser
a melhor escolha.
Mas, de repente, ele percebe o problema.
As cartas restantes na mesa
deixa informações sobre sua escolha,
uma vez que agora está faltando
uma carta no baralho.
Os cadeados são um chamariz.
Ele não deveria separar
sua carta do baralho.
Ele retorna a sua carta para o baralho
mas não consegue lembrar a
posição da sua carta.
Assim, ele pega o baralho com as cartas
e as embaralha.
Embaralhar é o melhor bloqueio,
porque não deixa
nenhuma informação sobre sua escolha.
A carta agora tem a mesma probabilidade de
ser qualquer carta do baralho.
Ele agora pode deixar as cartas
abertamente, em confiança.
Bob ganha o jogo, porque o melhor
que Eva pode fazer
é simplesmente adivinhar como ele deixou
pois não há informações sobre sua escolha.
O mais importante, mesmo que
se desse à Eva
poder computacional ilimitado,
ela não pode fazer nada melhor
do que um palpite.
Isso define o que chamamos de
"sigilo perfeito."
Em 1º de Setembro de 1945,
com 29 anos Claude Shannon
publicou um documento confidencial
sobre esta ideia.
Shannon deu a primeira prova matemática
para saber como e por que uma chave de uso
único é perfeitamente secreta.
Shannon pensa sobre esquemas
de criptografia
da seguinte maneira:
Imagine que Alice escreve uma
mensagem para Bob de 20 letras.
Isto é equivalente a selecionar
uma página específica do
espaço da mensagem.
O espaço de mensagem pode ser pensado
como uma completa
coleção de todas as possíveis
mensagens com 20 letras.
Qualquer coisa que você pode
pensar que tem
20 letras, é uma página nesta pilha.
Em seguida, Alice aplica uma chave
partilhada, que é uma lista
de 20 letras gerada aleatoriamente
em turnos entre 1 e 26.
O espaço da chave é a coleção completa
de todos os resultados possíveis,
assim gerando uma chave que é
equivalente a selecionar uma página a
partir desta pilha de forma aleatória.
Quando ela se aplica a mudança para
criptografar a mensagem,
ela acaba com um texto encriptado.
O espaço de texto encriptado representa
todos os resultados possíveis
de uma encriptação.
Quando ela aplica-se a chave, que mapeia
para uma página única nesta pilha.
Note-se que o tamanho do
espaço de mensagem
é igual ao tamanho do espaço da chave
e é igual ao tamanho do espaço
do texto encriptado.
Isso define o que chamamos
de "sigilo perfeito"
pois, se alguém tem acesso a uma página
de apenas texto encriptado,
a única coisa que eles sabem é que
cada mensagem é a mesma probabilidade.
Assim, nenhuma quantidade
de poder computacional
jamais poderia ajudar a melhorar
um palpite cego.
Agora, o grande problema, que você
deve estar se perguntando
com essa chave de uso único, temos que
compartilhar elas com antecedência.
Para resolver este problema, precisamos
relaxar nossa definição de sigilo
através do desenvolvimento de
uma definição de pseudo-aleatoriedade.
Traduzido por [Fernando dos Reis]
Revisado por [Alef Almeida]
(sakin müzik)
Şimdiki oyuna bir kafa yorun.
Eve, Bob'a bir odaya girmesini söyler.
Bob odanın birkaç kilit, boş bir kutu
ve bir deste oyun kartı dışında
boş olduğunu görür.
Eve, Bob'a desteden bir kat seçmesini
ve elinden gelen en iyi şekilde
saklamasını söyler.
Kurallar basit.
Bob odadan herhangi bir şey çıkartamaz.
Kartlar ve anahtarlar odada kalacak,
ve kutuya en fazla bir kart koyabilir.
Eve kilitleri daha önce görmediğini onaylar.
Eğer Eve kartı doğru tahmin edemezse
Bob kazanır.
Bob'un en iyi stratejisi nedir?
Bob karo altıyı seçti
ve kutuya koydu.
Önce çeşitli kilitleri gözden geçirdi.
Belkide anahtarı kartla beraber kutuya kilitlemeliydi.
Ama Eve'in anahtarsızda kilidi açma
ihtimali vardı.
Bob şifreli kilidi düşündü.
Şifresi arkasındaydı. Kilitleyip
şifreyi kazıması en iyi ihtimal
gibi gözüküyordu.
Ama birden asıl sorunu farketti.
Seçtiği kart artık destede olmadığı için
masada kalan kartlar
yaptığı seçim hakkında bilgi sızdırıyor.
Kilitler sadece bir tuzak.
Kartını desteden ayırmamalı.
Kartını desteye geri koyarken
kartın ilk pozisyonunu hatırlayamadı.
O da kartların sırasının gelişigüzel
olması için desteyi karıştırdı.
Yaptığı seçim hakkında hiç bir iz
bırakmadığı için
karıştırmak en iyi kilittir.
Şu an destedeki herhangi bir kartın
seçtiği kart olması ihtimali aynıdır.
Artık kartları kendinden emin
bir şekilde açıkta bırakarak çıkabilir.
Bob yaptığı seçim hakkında geride
hiç bilgi bırakmadığından dolayı
Eve'in yapabileceği en başarılı yolun
sadece tahmin etmek olduğu için
Bob kazanır.
En önemlisi, Eve'e
sınırsız işlem gücü versek bile
yapabileceği en iyi şey
tahminden öteye gidemez.
Bu bizim "mükemmel gizlilik" dediğimiz şeydir.
1 Eylül 1945'te,
29 yaşındaki Claude Shannon
bu fikirle ilgili gizli bir
makale yayınladı.
Shannon, tek kullanımlık şerit'in
nasıl ve neden
mükemmel gizliliğe sahip olduğunun
matematiksel ilk ispatını verdi.
Shannon, şifreleme şemasını
şu şekilde düşündü.
Alice'in Bob'a 20 harflik bir mesaj
yazdığını hayal edin.
(sayfalar çevriliyor)
Bu mesaj alanından
belirli bir sayfa seçmeye eşittir.
Mesaj alanı, 20 harf uzunluğundaki
bütün mesaj olasılıklarının
toplamı olarak düşünülebilir.
(sayfalar çevriliyor)
20 harf uzunluğundaki
düşünebileceğiniz bütün
herşey bu yığında.
Sonra Alice 1 ve 26 arası
rakamlara sahip 20 karakter uzunluğunda
paylaşılan bir şifreyi uygular.
Şifre alanı bütün sonuçların
bir koleksiyonudur.
Bu nedenle bir şifre oluşturmak
bu yığından rastgele bir
sayfa seçmeye eşittir.
Karakter kaydırmayı metni
şifrelemek için uyguladığı zaman
şifreli bir metin elde eder.
Şifreli metin alanı bir şifrelemenin
mümkün olan tüm sonuçlarını temsil eder.
Şifreyi uyguladığı zaman
bu yığındaki özgün bir sayfayla eşleşir.
Mesaj alanının yüksekliğinin
şifre alanına ve
şifreli metin alanına eşit
olduğuna dikkat edin.
Bu "mükemmel gizlilik" dediğimiz şeydir
ve sadece şifreli metne
erişebilen biri için
bildiği tek şey bu olduğu için
her mesaj aynı olasılıktadır.
Hiç bir işlem gücü
rastgele bir seçimin ötesine götüremez.
Şimdi tek seferlik şifre için
merak edebileceğiniz
en büyük problem, bu uzun şifreleri
önceden paylaşmak zorunda olmamız.
Bu problemi çözmek için
sözde-rastlantısallık tanımını oluşturarak
gizlilik tanımımızı esnetmeliyiz.
(beyaz gürültü)