1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Vigenère Cipher]

2
00:00:02,000 --> 00:00:04,000
[Nate Hardison - Universiti Harvard]

3
00:00:04,000 --> 00:00:07,000
[Ini adalah CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
Meet Alice.

5
00:00:09,000 --> 00:00:11,260
Alice mempunyai tertarik pada Bob.

6
00:00:11,260 --> 00:00:15,030
Mujurlah untuk Alice, Bob juga mempunyai mata untuknya.

7
00:00:15,030 --> 00:00:17,700
Malangnya bagi percintaan tunas mereka,

8
00:00:17,700 --> 00:00:20,580
bukan sahaja ibu bapa Alice mencela Bob,

9
00:00:20,580 --> 00:00:23,820
tetapi rakan Alice terbaik, Evelyn, mempunyai menghancurkan rahsia mengenai Bob

10
00:00:23,820 --> 00:00:27,290
dan mementingkan diri mahu untuk memastikan mereka selain di semua kos.

11
00:00:27,290 --> 00:00:31,280
Untuk menghantar mesej rahsia antara satu sama lain bahawa ibu bapa Alice tidak boleh memahami,

12
00:00:31,280 --> 00:00:34,140
>> Alice dan Bob telah menggunakan cipher Caesar,

13
00:00:34,140 --> 00:00:37,410
yang berfungsi dengan beralih abjad dengan beberapa huruf tertentu

14
00:00:37,410 --> 00:00:39,800
sebagai satu cara untuk menjana abjad baru.

15
00:00:39,800 --> 00:00:44,130
Setiap huruf dalam abjad asal kemudiannya digantikan oleh surat yang sepadan

16
00:00:44,130 --> 00:00:46,920
dalam abjad baru beralih.

17
00:00:46,920 --> 00:00:50,240
Nombor kegemaran Alice adalah 3, yang Bob tahu,

18
00:00:50,240 --> 00:00:52,450
jadi dia menggunakan 3 sebagai kunci beliau.

19
00:00:52,450 --> 00:00:55,430
Apabila dia perubahan abjad Inggeris oleh 3 huruf,

20
00:00:55,430 --> 00:01:00,680
A menjadi D, B menjadi E, C menjadi F,

21
00:01:00,680 --> 00:01:02,670
dan sebagainya.

22
00:01:02,670 --> 00:01:07,460
>> Apabila dia sampai ke akhir abjad huruf X, Y, dan Z -

23
00:01:07,460 --> 00:01:09,970
dia hanya wrap keliling kembali ke permulaan abjad

24
00:01:09,970 --> 00:01:14,850
dan pengganti X dengan A Y, dengan B, dan Z dengan C.

25
00:01:14,850 --> 00:01:18,550
Jadi apabila Alice pergi untuk menyulitkan mesej rahsia kepada Bob,

26
00:01:18,550 --> 00:01:21,520
iaitu "Jumpa saya di taman pada 11:00,"

27
00:01:21,520 --> 00:01:23,790
dia hanya membuat penggantian yang sesuai.

28
00:01:23,790 --> 00:01:30,900
M menjadi P, E menjadi H, dan sebagainya sehingga dia tak disulitkan mesej teks biasa

29
00:01:30,900 --> 00:01:34,350
dijadikan teks cipher disulitkan:

30
00:01:34,350 --> 00:01:37,280
"Phhw ph dw wkh sdun dw hohyhq dp"

31
00:01:37,280 --> 00:01:39,370
pastinya tidak membunyikan paling romantis,

32
00:01:39,370 --> 00:01:41,650
tetapi Alice percaya bahawa ia akan lakukan.

33
00:01:41,650 --> 00:01:45,140
>> Alice memberikan mesej kepada Evelyn untuk menyampaikan ke rumah Bob.

34
00:01:45,140 --> 00:01:50,030
Tetapi Evelyn bukannya mengambil ia kembali ke biliknya dan cuba untuk memecahkan kod.

35
00:01:50,030 --> 00:01:55,470
Salah satu perkara pertama Evelyn notis adalah bahawa huruf H berlaku 7 kali dalam mesej,

36
00:01:55,470 --> 00:01:58,930
banyak kali lebih daripada mana-mana surat lain.

37
00:01:58,930 --> 00:02:01,960
Mengetahui bahawa huruf E adalah yang paling biasa dalam bahasa Inggeris,

38
00:02:01,960 --> 00:02:05,390
berlaku hampir 13% masa,

39
00:02:05,390 --> 00:02:09,910
Evelyn tekaan bahawa H telah digantikan dengan E untuk membuat mesej rahsia

40
00:02:09,910 --> 00:02:14,030
dan cuba menggunakan kunci 3 untuk menyahsulit.

41
00:02:14,030 --> 00:02:19,700
>> Dalam masa beberapa minit, Evelyn angka keluar rancangan Alice dan evilly panggilan ibu bapa Alice.

42
00:02:19,700 --> 00:02:22,700
Kalaulah Alice dan Bob diambil CS50, mereka akan dikenali ini

43
00:02:22,700 --> 00:02:25,750
analisis frekuensi serangan pada cipher Caesar,

44
00:02:25,750 --> 00:02:28,310
yang membolehkan ia dipecahkan agak cepat.

45
00:02:28,310 --> 00:02:32,590
Mereka juga akan diketahui bahawa cipher mudah tertakluk kepada serangan kasar-kuasa,

46
00:02:32,590 --> 00:02:35,940
mana Evelyn boleh cuba semua kemungkinan satu daripada 25 kunci,

47
00:02:35,940 --> 00:02:38,440
atau perubahan abjad Inggeris,

48
00:02:38,440 --> 00:02:40,490
dalam usaha untuk mentafsirkan mesej.

49
00:02:40,490 --> 00:02:43,710
Mengapa 25 kunci dan bukan 26?

50
00:02:43,710 --> 00:02:49,010
>> Nah, cuba mengalihkan mana-mana surat sebanyak 26 jawatan, dan anda akan melihat mengapa.

51
00:02:49,010 --> 00:02:52,280
Bagaimanapun, kasar-kuasa serangan akan diambil Evelyn sedikit lagi

52
00:02:52,280 --> 00:02:56,070
tetapi tidak cukup lama untuk menjaga beliau dari thwarting rancangan Alice dan Bob,

53
00:02:56,070 --> 00:02:58,660
terutamanya jika Evelyn mempunyai bantuan komputer

54
00:02:58,660 --> 00:03:02,640
yang boleh rip melalui semua 25 kes dalam sekelip mata.

55
00:03:02,640 --> 00:03:06,170
Jadi, masalah ini juga dibelenggu lain yang digunakan cipher Caesar,

56
00:03:06,170 --> 00:03:10,300
dan oleh itu orang mula bereksperimen dengan sifer penggantian lebih kompleks

57
00:03:10,300 --> 00:03:14,190
yang menggunakan nilai anjakan berganda bukan hanya satu.

58
00:03:14,190 --> 00:03:18,080
Salah satu yang paling terkenal daripada ini dipanggil Vigenère cipher.

59
00:03:18,080 --> 00:03:19,980
Bagaimana kita mendapatkan nilai anjakan berganda?

60
00:03:19,980 --> 00:03:24,630
Nah, bukannya menggunakan nombor sebagai kunci, kita gunakan perkataan bagi kekunci.

61
00:03:24,630 --> 00:03:27,940
Kami akan menggunakan setiap huruf di kunci untuk menjana nombor,

62
00:03:27,940 --> 00:03:33,670
dan kesannya adalah bahawa kita akan mempunyai pelbagai Caesar gaya cipher kunci untuk memindahkan surat.

63
00:03:33,670 --> 00:03:36,620
>> Mari kita lihat bagaimana kerja-kerja ini dengan menyulitkan mesej Alice Bob:

64
00:03:36,620 --> 00:03:39,010
Jumpa saya di taman pada 11:00

65
00:03:39,010 --> 00:03:42,610
Saya, secara peribadi, rasa daging lazat,

66
00:03:42,610 --> 00:03:44,480
jadi mari kita menggunakan bahawa sebagai kunci.

67
00:03:44,480 --> 00:03:48,220
Jika kita mengambil mesej tak disulitkan, format teks biasa,

68
00:03:48,220 --> 00:03:51,020
kita lihat bahawa ia adalah 25 huruf.

69
00:03:51,020 --> 00:03:55,020
Bacon mempunyai hanya 5 huruf, jadi kita perlu mengulangi ia 5 kali

70
00:03:55,020 --> 00:03:57,200
untuk membuat ia sepadan panjang teks dataran.

71
00:03:57,200 --> 00:03:59,880
>> Bacon daging daging daging bacon.

72
00:03:59,880 --> 00:04:02,300
Sebagai ringkas diketepikan, jika bilangan huruf dalam teks biasa

73
00:04:02,300 --> 00:04:05,780
tidak membahagikan rapi oleh bilangan huruf dalam kunci,

74
00:04:05,780 --> 00:04:08,260
kita hanya berakhir ulangan akhir utama kami awal,

75
00:04:08,260 --> 00:04:11,800
menggunakan hanya huruf kita diperlukan untuk membuat segala-galanya perlawanan sehingga.

76
00:04:11,800 --> 00:04:14,590
Sekarang kita pergi tentang mencari nilai anjakan.

77
00:04:14,590 --> 00:04:19,100
>> Kami akan melakukan ini dengan menggunakan kedudukan setiap huruf utama kami - bacon -

78
00:04:19,100 --> 00:04:21,560
A untuk abjad Z.

79
00:04:21,560 --> 00:04:26,060
Sejak kami ahli-ahli sains komputer, kita suka untuk mula mengira pada sifar bukan 1,

80
00:04:26,060 --> 00:04:30,230
jadi kita akan mengatakan bahawa kedudukan huruf pertama bacon - B -

81
00:04:30,230 --> 00:04:33,840
adalah dalam kedudukan 1 dalam A sifar diindeks kepada abjad Z,

82
00:04:33,840 --> 00:04:38,300
bukan 2, dan kedudukan A adalah sifar, bukan 1.

83
00:04:38,300 --> 00:04:42,450
Menggunakan algoritma ini, kita boleh mencari nilai anjakan untuk setiap huruf.

84
00:04:42,450 --> 00:04:45,330
>> Untuk menyulitkan teks biasa dan menjana teks cipher,

85
00:04:45,330 --> 00:04:49,070
kita hanya beralih setiap huruf dalam teks dataran dengan jumlah yang ditetapkan,

86
00:04:49,070 --> 00:04:54,140
seperti yang kita lakukan dengan cipher Caesar, membungkus dari Z kembali kepada A jika perlu.

87
00:04:54,140 --> 00:04:57,880
M mendapat beralih oleh 1 tempat untuk menjadi N.

88
00:04:57,880 --> 00:05:02,350
E pertama tidak beralih pada semua, tetapi kita beralih E kedua dengan 2 tempat ke G

89
00:05:02,350 --> 00:05:06,200
dan T sebanyak 14 tempat untuk H.

90
00:05:06,200 --> 00:05:08,610
Jika kita bekerja melalui teks dataran, kita berakhir dengan,

91
00:05:08,610 --> 00:05:12,580
"Negh ZF av HUF pcfx bt gzrwep oz."

92
00:05:12,580 --> 00:05:16,620
Sekali lagi, tidak sangat romantis-membunyikan tetapi pasti samar.

93
00:05:16,620 --> 00:05:19,750
Jika Alice dan Bob telah diketahui tentang Vigenère cipher,

94
00:05:19,750 --> 00:05:23,330
mereka akan telah selamat dari mata prying Evelyn ini?

95
00:05:23,330 --> 00:05:24,870
Apa yang anda fikir?

96
00:05:24,870 --> 00:05:27,450
Anda mahu log masuk ke dalam akaun bank anda jika bank anda memutuskan untuk menggunakan

97
00:05:27,450 --> 00:05:32,720
>> Vigenère cipher untuk menyulitkan komunikasi anda menggunakan kata laluan anda sebagai kunci anda?

98
00:05:32,720 --> 00:05:34,810
Jika saya anda, saya tidak akan.

99
00:05:34,810 --> 00:05:38,720
Dan manakala Evelyn mungkin sibuk cukup lama untuk Alice dan Bob untuk mempunyai mereka memenuhi-up,

100
00:05:38,720 --> 00:05:41,600
ia tidak berbaloi untuk Alice dan Bob untuk peluang ia.

101
00:05:41,600 --> 00:05:45,780
Vigenère cipher adalah agak mudah untuk memecahkan jika anda tahu panjang kekunci

102
00:05:45,780 --> 00:05:48,490
kerana kemudian anda boleh merawat teks cipher disulitkan

103
00:05:48,490 --> 00:05:52,840
sebagai produk Caesar beberapa sifer terjalin.

104
00:05:52,840 --> 00:05:55,950
>> Mencari panjang kekunci tidak terlalu keras, sama ada.

105
00:05:55,950 --> 00:06:00,520
Jika asal mesej teks biasa adalah cukup lama bahawa sesetengah perkataan berlaku beberapa kali,

106
00:06:00,520 --> 00:06:04,420
akhirnya anda akan melihat pengulangan tanaman sehingga dalam teks cipher disulitkan,

107
00:06:04,420 --> 00:06:10,010
seperti dalam contoh ini, di mana anda lihat MONCY muncul dua kali.

108
00:06:10,010 --> 00:06:13,800
Selain itu, anda boleh melakukan serangan kasar-kuasa pada cipher.

109
00:06:13,800 --> 00:06:17,220
Ini tidak mengambil jauh lebih lama daripada serangan kasar-kuasa pada cipher Caesar,

110
00:06:17,220 --> 00:06:20,670
yang boleh dilakukan hampir serta-merta dengan komputer

111
00:06:20,670 --> 00:06:27,130
kerana bukan 25 kes untuk memeriksa anda telah mendapat 26 ⁿ - 1 kemungkinan,

112
00:06:27,130 --> 00:06:29,580
di mana n adalah panjang kekunci tidak diketahui.

113
00:06:29,580 --> 00:06:34,040
>> Ini adalah kerana setiap surat dalam kunci boleh mana-mana 26 huruf,

114
00:06:34,040 --> 00:06:38,280
A hingga Z, dan orang bijak akan cuba untuk menggunakan kunci yang tidak boleh ditemui dalam kamus,

115
00:06:38,280 --> 00:06:44,280
yang bermaksud bahawa anda akan mempunyai untuk menguji semua kombinasi surat pelik, seperti ZXXXFF,

116
00:06:44,280 --> 00:06:47,690
dan tidak hanya beberapa ratus ribu perkataan dalam kamus.

117
00:06:47,690 --> 00:06:53,200
Tolak 1 datang ke dalam matematik kerana anda tidak mahu menggunakan kunci dengan hanya A,

118
00:06:53,200 --> 00:06:56,200
kerana dengan abjad sifar diindeks kami yang akan memberi anda kesan yang sama

119
00:06:56,200 --> 00:06:59,620
sebagai menggunakan cipher Caesar dengan kunci sifar.

120
00:06:59,620 --> 00:07:04,120
Bagaimanapun, 26 ⁿ - 1 tidak mendapat besar agak cepat,

121
00:07:04,120 --> 00:07:08,080
tetapi semasa anda pasti tidak mahu untuk cuba memecahkan cipher dengan tangan cara ini,

122
00:07:08,080 --> 00:07:11,080
ini memang boleh dilakukan dengan komputer.

123
00:07:11,080 --> 00:07:14,030
Nasib baik untuk Alice dan Bob, dan untuk perbankan dalam talian,

124
00:07:14,030 --> 00:07:17,890
cryptographers telah membangunkan cara yang lebih selamat untuk menyulitkan mesej rahsia

125
00:07:17,890 --> 00:07:19,690
dari prying mata.

126
00:07:19,690 --> 00:07:22,400
>> Walau bagaimanapun, itulah satu topik untuk masa yang lain.

127
00:07:22,400 --> 00:07:26,210
Nama saya adalah Nate Hardison. Ini adalah CS50.