1
00:00:00,000 --> 00:00:04,710


2
00:00:04,710 --> 00:00:07,650
For over 400 years,
the problem remained.

3
00:00:07,650 --> 00:00:11,760
How could Alice design a cipher
that hides her fingerprint,

4
00:00:11,760 --> 00:00:14,580
thus stopping the
leak of information?

5
00:00:14,580 --> 00:00:18,150
The answer is randomness.

6
00:00:18,150 --> 00:00:20,890
Imagine Alice rolled
a 26 sided die

7
00:00:20,890 --> 00:00:23,360
to generate a long
list of random shifts,

8
00:00:23,360 --> 00:00:26,810
and shared this with Bob
instead of a code word.

9
00:00:26,810 --> 00:00:28,860
Now, to encrypt
her message, Alice

10
00:00:28,860 --> 00:00:31,970
uses the list of
random shifts instead.

11
00:00:31,970 --> 00:00:34,010
It is important that
this list of shifts

12
00:00:34,010 --> 00:00:38,440
be as long as the message,
as to avoid any repetition.

13
00:00:38,440 --> 00:00:41,250
Then she sends it to Bob, who
decrypts the message using

14
00:00:41,250 --> 00:00:44,085
the same list of random
shifts she had given him.

15
00:00:44,085 --> 00:00:46,870


16
00:00:46,870 --> 00:00:49,460
Now Eve will have a problem,
because the resulting

17
00:00:49,460 --> 00:00:53,210
encrypted message will have
two powerful properties.

18
00:00:53,210 --> 00:00:56,765
One, the shifts never fall
into a repetitive pattern.

19
00:00:56,765 --> 00:00:59,350


20
00:00:59,350 --> 00:01:02,860
And two, the encrypted message
will have a uniform frequency

21
00:01:02,860 --> 00:01:04,230
distribution.

22
00:01:04,230 --> 00:01:07,050
Because there is no frequency
differential and therefore

23
00:01:07,050 --> 00:01:09,736
no leak, it is now
impossible for Eve

24
00:01:09,736 --> 00:01:10,735
to break the encryption.

25
00:01:10,735 --> 00:01:14,090


26
00:01:14,090 --> 00:01:18,080
This is the strongest
possible method of encryption,

27
00:01:18,080 --> 00:01:21,520
and it emerged towards the
end of the 19th century.

28
00:01:21,520 --> 00:01:25,860
It is now known as
the one-time pad.

29
00:01:25,860 --> 00:01:28,990
In order to visualize the
strength of the one-time pad,

30
00:01:28,990 --> 00:01:32,320
we must understand the
combinatorial explosion

31
00:01:32,320 --> 00:01:34,600
which takes place.

32
00:01:34,600 --> 00:01:37,600
For example, the Caesar
Cipher shifted every letter

33
00:01:37,600 --> 00:01:42,970
by the same shift, which was
some number between 1 and 26.

34
00:01:42,970 --> 00:01:44,970
So if Alice was to
encrypt her name,

35
00:01:44,970 --> 00:01:48,770
it would result in one of
26 possible encryptions.

36
00:01:48,770 --> 00:01:52,290
A small number of possibilities,
easy to check them all,

37
00:01:52,290 --> 00:01:55,280
known as brute force search.

38
00:01:55,280 --> 00:01:58,060
Compare this to the one-time
pad, where each letter would

39
00:01:58,060 --> 00:02:01,690
be shifted by a different
number between 1 and 26.

40
00:02:01,690 --> 00:02:04,000
Now think about the number
of possible encryptions.

41
00:02:04,000 --> 00:02:08,050
It's going to be 26 multiplied
by itself five times, which

42
00:02:08,050 --> 00:02:10,360
is almost 12 million.

43
00:02:10,360 --> 00:02:13,030
Sometimes it's
hard to visualize,

44
00:02:13,030 --> 00:02:15,850
so imagine she wrote her
name on a single page,

45
00:02:15,850 --> 00:02:20,900
and on top of it stacked
every possible encryption.

46
00:02:20,900 --> 00:02:24,520
How high do you
think this would be?

47
00:02:24,520 --> 00:02:28,750
With almost 12 million
possible five-letter sequences,

48
00:02:28,750 --> 00:02:32,110
this stack of paper
would be enormous,

49
00:02:32,110 --> 00:02:35,130
over one kilometer high.

50
00:02:35,130 --> 00:02:38,240
When Alice encrypts her
name using the one-time pad,

51
00:02:38,240 --> 00:02:42,240
it is the same as picking
one of these pages at random.

52
00:02:42,240 --> 00:02:44,720
From the perspective of
Eve, the code breaker,

53
00:02:44,720 --> 00:02:46,910
every five letter
encrypted word she

54
00:02:46,910 --> 00:02:51,600
has is equally likely to
be any word in this stack.

55
00:02:51,600 --> 00:02:55,240
So this is perfect
secrecy in action.

56
00:02:55,240 --> 00:02:55,867