1
00:00:00,000 --> 00:00:10,101
[MUSIC PLAYING]

2
00:00:10,101 --> 00:00:12,700
ZAMYLA CHAN: Let's implement
Vigenere, a slightly more

3
00:00:12,700 --> 00:00:14,710
secure cipher than Caesar.

4
00:00:14,710 --> 00:00:19,670
The plain text is enciphered using
a string instead of an integer.

5
00:00:19,670 --> 00:00:22,970
Each alphabetical character in
plain text is shifted by a

6
00:00:22,970 --> 00:00:24,450
letter in the keyword.

7
00:00:24,450 --> 00:00:30,860
In this example, the keyword ohai, O
corresponds to a shift of 14; H to a

8
00:00:30,860 --> 00:00:36,910
shift of 7; A, shift of
0; and I a shift of 8.

9
00:00:36,910 --> 00:00:40,710
If you've successfully implemented your
Caesar cipher, it'll be a nice

10
00:00:40,710 --> 00:00:43,510
framework from which you
can implement Vigenere.

11
00:00:43,510 --> 00:00:47,140
As you can see, running a Vigenere
cipher with a single character as a

12
00:00:47,140 --> 00:00:51,830
keyword is the same thing
as a Caesar cipher.

13
00:00:51,830 --> 00:00:55,170
The same steps apply to Vigenere
as they did in Caesar.

14
00:00:55,170 --> 00:01:01,240
The keyword is the second command line
argument, so you access it with argv1.

15
00:01:01,240 --> 00:01:05,400
Then you need to verify that the key
word is indeed all alphabetical.

16
00:01:05,400 --> 00:01:09,040
Here is where is alpha
can come in handy.

17
00:01:09,040 --> 00:01:13,550
If you have a valid keyword, you get the
strength from the user, and then

18
00:01:13,550 --> 00:01:15,820
you're ready to encipher.

19
00:01:15,820 --> 00:01:20,840
The Vigenere cipher formula is similar
to Caesar formula, except now k

20
00:01:20,840 --> 00:01:27,650
becomes k subscript j, indicating
the j-th letter of the keyword.

21
00:01:27,650 --> 00:01:29,640
Let's step through this process.

22
00:01:29,640 --> 00:01:34,060
Say you wanted to send a message to your
crash, I like you, but you don't

23
00:01:34,060 --> 00:01:35,190
want everyone to know.

24
00:01:35,190 --> 00:01:39,800
So you use a Vigenere cipher with the
keyword panda, because, well, you also

25
00:01:39,800 --> 00:01:41,160
like pandas.

26
00:01:41,160 --> 00:01:47,140
The first letter, I, will be shifted
by p, giving x, 15 letters after I,

27
00:01:47,140 --> 00:01:52,850
because 15 p is the 16th
letter of the alphabet.

28
00:01:52,850 --> 00:01:56,750
The next letter in the plain text is
a space, so that won't be shifted.

29
00:01:56,750 --> 00:02:00,420
And the index of the keyword
won't change.

30
00:02:00,420 --> 00:02:05,440
Then the next letter in plain text is
l, shifted by a, which doesn't shift

31
00:02:05,440 --> 00:02:10,930
the plain text letter at all, because
a is the 0th letter of the alphabet.

32
00:02:10,930 --> 00:02:14,980
The process continues, advancing the
keyword character every time there's a

33
00:02:14,980 --> 00:02:16,840
letter in the plain text.

34
00:02:16,840 --> 00:02:21,850
Once the last letter in the keyword is
reached, the keyword wraps around and

35
00:02:21,850 --> 00:02:25,890
shifts to the next plain
text letter by p.

36
00:02:25,890 --> 00:02:27,170
X lvne noh.

37
00:02:27,170 --> 00:02:29,180
How romantic.

38
00:02:29,180 --> 00:02:33,120
So given a character, how do you convert
that into the corresponding

39
00:02:33,120 --> 00:02:34,590
cipher shift?

40
00:02:34,590 --> 00:02:37,870
Try comparing the ASCII
values to the shift.

41
00:02:37,870 --> 00:02:41,530
Maybe you can find a relationship
between the letters and their

42
00:02:41,530 --> 00:02:44,550
alphabetical index using ASCII math.

43
00:02:44,550 --> 00:02:48,850
Can you add or subtract one character
from another to get

44
00:02:48,850 --> 00:02:51,630
you the desired result?

45
00:02:51,630 --> 00:02:55,480
Remember that the shifts for uppercase
and lowercase letters are the same.

46
00:02:55,480 --> 00:02:59,510
So perhaps you'll need to identify two
similar formulas to represent the

47
00:02:59,510 --> 00:03:03,570
shift, one for an uppercase
keyword character, and one

48
00:03:03,570 --> 00:03:06,510
for a lowercase one.

49
00:03:06,510 --> 00:03:10,630
Next, remember that the keyword advances
only if the character in

50
00:03:10,630 --> 00:03:13,520
plain text is a letter and that
the case of the plain

51
00:03:13,520 --> 00:03:16,020
text must be preserved.

52
00:03:16,020 --> 00:03:20,280
So if we look at the formula for the
Vigenere shift, there are two index

53
00:03:20,280 --> 00:03:22,880
variables, i and j.

54
00:03:22,880 --> 00:03:26,795
One keeps track of the position in plain
text, and the other the position

55
00:03:26,795 --> 00:03:27,910
in the keyword.

56
00:03:27,910 --> 00:03:32,960
But your plain text may be much longer
than your keyword, in which case your

57
00:03:32,960 --> 00:03:38,290
keyword index needs to wrap around back
to the beginning of the keyword.

58
00:03:38,290 --> 00:03:39,870
How do you do this?

59
00:03:39,870 --> 00:03:43,740
Let's look back at the
modulo operator.

60
00:03:43,740 --> 00:03:47,280
Modulo is defined is the remainder
of dividing two numbers.

61
00:03:47,280 --> 00:03:50,680
But what's an actual practical
use of modulo?

62
00:03:50,680 --> 00:03:54,340
Well, say you have a large group of
people, and you need to divide into

63
00:03:54,340 --> 00:03:55,100
three groups.

64
00:03:55,100 --> 00:03:59,500
One way to divide people into groups
is to have them count off.

65
00:03:59,500 --> 00:04:03,520
You number the groups group
number 1, 2, and 3.

66
00:04:03,520 --> 00:04:08,510
The first person will say 1,
the next 2, the next 3.

67
00:04:08,510 --> 00:04:12,860
The person after that will say 1,
because there isn't a group 4, and the

68
00:04:12,860 --> 00:04:15,880
count starts over from there.

69
00:04:15,880 --> 00:04:18,209
You can use modulo to
do the same thing.

70
00:04:18,209 --> 00:04:22,680
This time, the groups will
be group 0, 1, and 2.

71
00:04:22,680 --> 00:04:26,960
The first person, number
1 modulo 3, is 1.

72
00:04:26,960 --> 00:04:29,830
Person 2 modulo 3 is 2.

73
00:04:29,830 --> 00:04:32,460
Person 3 modulo 3 is 0.

74
00:04:32,460 --> 00:04:38,470
Person 4 modulo 3 gives 1, and so
the groups can wrap around.

75
00:04:38,470 --> 00:04:44,700
So if you take an index and modulo
that index by a maximum size, the

76
00:04:44,700 --> 00:04:49,820
result will never be greater than or
equal to the size, meaning that you

77
00:04:49,820 --> 00:04:52,330
can increase the index as
much as you'd like.

78
00:04:52,330 --> 00:04:57,400
And as long as you modulo the index by
some number, you won't get a number

79
00:04:57,400 --> 00:04:58,510
larger than that.

80
00:04:58,510 --> 00:05:04,500
So we have 10 people instead of 5, and
they would all get assigned to groups

81
00:05:04,500 --> 00:05:07,480
number 0, 1, or 2.

82
00:05:07,480 --> 00:05:11,680
Try to apply this to wrapping over the
keyword, except instead of sorting

83
00:05:11,680 --> 00:05:16,050
people into group numbers you want the
index of the keyword so that you can

84
00:05:16,050 --> 00:05:19,080
get the right character for the
shift without exceeding the

85
00:05:19,080 --> 00:05:21,836
length of the string.

86
00:05:21,836 --> 00:05:24,790
With that, you have your
Vigenere cipher.

87
00:05:24,790 --> 00:05:27,790
My name is Zamyla, and this is CS50.

88
00:05:27,790 --> 00:05:32,566