[Powered by Google Translate] [Vigenère Cipher] [Nate Hardison - Universiti Harvard] [Ini adalah CS50. - CS50.TV] Meet Alice. Alice mempunyai tertarik pada Bob. Mujurlah untuk Alice, Bob juga mempunyai mata untuknya. Malangnya bagi percintaan tunas mereka, bukan sahaja ibu bapa Alice mencela Bob, tetapi rakan Alice terbaik, Evelyn, mempunyai menghancurkan rahsia mengenai Bob dan mementingkan diri mahu untuk memastikan mereka selain di semua kos. Untuk menghantar mesej rahsia antara satu sama lain bahawa ibu bapa Alice tidak boleh memahami, 

Alice dan Bob telah menggunakan cipher Caesar, yang berfungsi dengan beralih abjad dengan beberapa huruf tertentu sebagai satu cara untuk menjana abjad baru. Setiap huruf dalam abjad asal kemudiannya digantikan oleh surat yang sepadan dalam abjad baru beralih. Nombor kegemaran Alice adalah 3, yang Bob tahu, jadi dia menggunakan 3 sebagai kunci beliau. Apabila dia perubahan abjad Inggeris oleh 3 huruf, A menjadi D, B menjadi E, C menjadi F, dan sebagainya. 

Apabila dia sampai ke akhir abjad huruf X, Y, dan Z - dia hanya wrap keliling kembali ke permulaan abjad dan pengganti X dengan A Y, dengan B, dan Z dengan C. Jadi apabila Alice pergi untuk menyulitkan mesej rahsia kepada Bob, iaitu "Jumpa saya di taman pada 11:00," dia hanya membuat penggantian yang sesuai. M menjadi P, E menjadi H, dan sebagainya sehingga dia tak disulitkan mesej teks biasa dijadikan teks cipher disulitkan: "Phhw ph dw wkh sdun dw hohyhq dp" pastinya tidak membunyikan paling romantis, tetapi Alice percaya bahawa ia akan lakukan. 

Alice memberikan mesej kepada Evelyn untuk menyampaikan ke rumah Bob. Tetapi Evelyn bukannya mengambil ia kembali ke biliknya dan cuba untuk memecahkan kod. Salah satu perkara pertama Evelyn notis adalah bahawa huruf H berlaku 7 kali dalam mesej, banyak kali lebih daripada mana-mana surat lain. Mengetahui bahawa huruf E adalah yang paling biasa dalam bahasa Inggeris, berlaku hampir 13% masa, Evelyn tekaan bahawa H telah digantikan dengan E untuk membuat mesej rahsia dan cuba menggunakan kunci 3 untuk menyahsulit. 

Dalam masa beberapa minit, Evelyn angka keluar rancangan Alice dan evilly panggilan ibu bapa Alice. Kalaulah Alice dan Bob diambil CS50, mereka akan dikenali ini analisis frekuensi serangan pada cipher Caesar, yang membolehkan ia dipecahkan agak cepat. Mereka juga akan diketahui bahawa cipher mudah tertakluk kepada serangan kasar-kuasa, mana Evelyn boleh cuba semua kemungkinan satu daripada 25 kunci, atau perubahan abjad Inggeris, dalam usaha untuk mentafsirkan mesej. Mengapa 25 kunci dan bukan 26? 

Nah, cuba mengalihkan mana-mana surat sebanyak 26 jawatan, dan anda akan melihat mengapa. Bagaimanapun, kasar-kuasa serangan akan diambil Evelyn sedikit lagi tetapi tidak cukup lama untuk menjaga beliau dari thwarting rancangan Alice dan Bob, terutamanya jika Evelyn mempunyai bantuan komputer yang boleh rip melalui semua 25 kes dalam sekelip mata. Jadi, masalah ini juga dibelenggu lain yang digunakan cipher Caesar, dan oleh itu orang mula bereksperimen dengan sifer penggantian lebih kompleks yang menggunakan nilai anjakan berganda bukan hanya satu. Salah satu yang paling terkenal daripada ini dipanggil Vigenère cipher. Bagaimana kita mendapatkan nilai anjakan berganda? Nah, bukannya menggunakan nombor sebagai kunci, kita gunakan perkataan bagi kekunci. Kami akan menggunakan setiap huruf di kunci untuk menjana nombor, dan kesannya adalah bahawa kita akan mempunyai pelbagai Caesar gaya cipher kunci untuk memindahkan surat. 

Mari kita lihat bagaimana kerja-kerja ini dengan menyulitkan mesej Alice Bob: Jumpa saya di taman pada 11:00 Saya, secara peribadi, rasa daging lazat, jadi mari kita menggunakan bahawa sebagai kunci. Jika kita mengambil mesej tak disulitkan, format teks biasa, kita lihat bahawa ia adalah 25 huruf. Bacon mempunyai hanya 5 huruf, jadi kita perlu mengulangi ia 5 kali untuk membuat ia sepadan panjang teks dataran. 

Bacon daging daging daging bacon. Sebagai ringkas diketepikan, jika bilangan huruf dalam teks biasa tidak membahagikan rapi oleh bilangan huruf dalam kunci, kita hanya berakhir ulangan akhir utama kami awal, menggunakan hanya huruf kita diperlukan untuk membuat segala-galanya perlawanan sehingga. Sekarang kita pergi tentang mencari nilai anjakan. 

Kami akan melakukan ini dengan menggunakan kedudukan setiap huruf utama kami - bacon - A untuk abjad Z. Sejak kami ahli-ahli sains komputer, kita suka untuk mula mengira pada sifar bukan 1, jadi kita akan mengatakan bahawa kedudukan huruf pertama bacon - B - adalah dalam kedudukan 1 dalam A sifar diindeks kepada abjad Z, bukan 2, dan kedudukan A adalah sifar, bukan 1. Menggunakan algoritma ini, kita boleh mencari nilai anjakan untuk setiap huruf. 

Untuk menyulitkan teks biasa dan menjana teks cipher, kita hanya beralih setiap huruf dalam teks dataran dengan jumlah yang ditetapkan, seperti yang kita lakukan dengan cipher Caesar, membungkus dari Z kembali kepada A jika perlu. M mendapat beralih oleh 1 tempat untuk menjadi N. E pertama tidak beralih pada semua, tetapi kita beralih E kedua dengan 2 tempat ke G dan T sebanyak 14 tempat untuk H. Jika kita bekerja melalui teks dataran, kita berakhir dengan, "Negh ZF av HUF pcfx bt gzrwep oz." Sekali lagi, tidak sangat romantis-membunyikan tetapi pasti samar. Jika Alice dan Bob telah diketahui tentang Vigenère cipher, mereka akan telah selamat dari mata prying Evelyn ini? Apa yang anda fikir? Anda mahu log masuk ke dalam akaun bank anda jika bank anda memutuskan untuk menggunakan 

Vigenère cipher untuk menyulitkan komunikasi anda menggunakan kata laluan anda sebagai kunci anda? Jika saya anda, saya tidak akan. Dan manakala Evelyn mungkin sibuk cukup lama untuk Alice dan Bob untuk mempunyai mereka memenuhi-up, ia tidak berbaloi untuk Alice dan Bob untuk peluang ia. Vigenère cipher adalah agak mudah untuk memecahkan jika anda tahu panjang kekunci kerana kemudian anda boleh merawat teks cipher disulitkan sebagai produk Caesar beberapa sifer terjalin. 

Mencari panjang kekunci tidak terlalu keras, sama ada. Jika asal mesej teks biasa adalah cukup lama bahawa sesetengah perkataan berlaku beberapa kali, akhirnya anda akan melihat pengulangan tanaman sehingga dalam teks cipher disulitkan, seperti dalam contoh ini, di mana anda lihat MONCY muncul dua kali. Selain itu, anda boleh melakukan serangan kasar-kuasa pada cipher. Ini tidak mengambil jauh lebih lama daripada serangan kasar-kuasa pada cipher Caesar, yang boleh dilakukan hampir serta-merta dengan komputer kerana bukan 25 kes untuk memeriksa anda telah mendapat 26 ⁿ - 1 kemungkinan, di mana n adalah panjang kekunci tidak diketahui. 

Ini adalah kerana setiap surat dalam kunci boleh mana-mana 26 huruf, A hingga Z, dan orang bijak akan cuba untuk menggunakan kunci yang tidak boleh ditemui dalam kamus, yang bermaksud bahawa anda akan mempunyai untuk menguji semua kombinasi surat pelik, seperti ZXXXFF, dan tidak hanya beberapa ratus ribu perkataan dalam kamus. Tolak 1 datang ke dalam matematik kerana anda tidak mahu menggunakan kunci dengan hanya A, kerana dengan abjad sifar diindeks kami yang akan memberi anda kesan yang sama sebagai menggunakan cipher Caesar dengan kunci sifar. Bagaimanapun, 26 ⁿ - 1 tidak mendapat besar agak cepat, tetapi semasa anda pasti tidak mahu untuk cuba memecahkan cipher dengan tangan cara ini, ini memang boleh dilakukan dengan komputer. Nasib baik untuk Alice dan Bob, dan untuk perbankan dalam talian, cryptographers telah membangunkan cara yang lebih selamat untuk menyulitkan mesej rahsia dari prying mata. 

Walau bagaimanapun, itulah satu topik untuk masa yang lain. Nama saya adalah Nate Hardison. Ini adalah CS50.