[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Universiti Harvard]
[Ini adalah CS50.] [CS50.TV]
Mari kita lihat di RSA, algoritma yang digunakan secara meluas untuk menyulitkan data.
Algoritma penyulitan seperti Caesar dan sifer VigenĂ¨re tidak sangat selamat.
Dengan cipher Caesar, penyerang hanya perlu cuba 25 kunci yang berbeza
untuk mendapatkan teks mesej.
Walaupun cipher VigenĂ¨re adalah lebih selamat daripada cipher Caesar
kerana ruang carian yang lebih besar untuk kunci, sekali penyerang
tahu panjang kunci dalam cipher VigenĂ¨re,
yang boleh ditentukan melalui analisis corak dalam teks disulitkan,
cipher VigenĂ¨re tidak adalah yang lebih selamat daripada cipher Caesar.
RSA, di sisi lain, tidak terdedah kepada serangan seperti ini.
Cipher Caesar dan VigenĂ¨re cipher menggunakan kekunci yang sama
kepada kedua-dua menyulitkan dan menyahsulit mesej.
Harta tanah ini menjadikan ini sifer kunci algoritma simetri.
Satu masalah asas simetri dengan algoritma utama
adalah bahawa mereka bergantung pada satu menyulitkan dan menghantar mesej
dan satu menerima dan decrypting mesej
telah pun bersetuju terlebih dahulu pada kekunci yang kedua-dua mereka akan menggunakan.
Tetapi kita mempunyai sedikit masalah permulaan di sini.
Bagaimana 2 komputer yang mahu berkomunikasi menubuhkan kunci rahsia antara mereka?
Jika kunci mesti menjadi rahsia, maka kita memerlukan satu cara untuk menyulitkan dan menyahsulit kekunci.
Jika semua yang kita ada adalah kunci kriptografi simetri
maka kita baru sahaja kembali kepada masalah yang sama.
RSA, di sisi lain, menggunakan sepasang kunci,
satu untuk penyulitan dan lain untuk penyahsulitan.
Satu dipanggil kunci awam, dan lain-lain adalah kunci persendirian.
Kunci awam yang digunakan untuk menyulitkan mesej.
Seperti yang anda sangka dengan namanya, kita boleh berkongsi kunci awam kita dengan
sesiapa sahaja yang kita mahu tanpa menjejaskan keselamatan mesej disulitkan.
Mesej disulitkan menggunakan kekunci awam
hanya boleh dibuka dengan kekunci yang sepadan swasta.
Walaupun anda boleh berkongsi kunci awam anda, anda sentiasa perlu menyimpan rahsia peribadi anda yang utama.
dan hanya kunci persendirian boleh digunakan untuk menyahsulit mesej
jika 2 pengguna mahu untuk menghantar mesej disulitkan dengan RSA
belakang dan sebagainya kedua-dua pengguna perlu untuk mempunyai pasangan mereka sendiri kunci awam dan swasta.
Mesej dari 1 pengguna kepada 2 pengguna
hanya menggunakan sepasang utama 2 pengguna, dan mesej daripada 2 pengguna 1 pengguna
hanya menggunakan pasangan kunci pengguna 1.
Hakikat bahawa terdapat 2 kunci berasingan untuk menyulitkan dan menyahsulit mesej
membuat RSA algoritma simetri utama.
Kita tidak perlu untuk menyulitkan kunci awam dalam usaha untuk hantar ke komputer lain
sejak kunci awam anyway.
Ini bermakna bahawa RSA tidak mempunyai masalah permulaan yang sama
sebagai algoritma kekunci simetri.
Jadi jika saya mahu menghantar mesej menggunakan penyulitan RSA
untuk Rob, saya mula-mula akan memerlukan kunci awam Rob.
Untuk menjana sepasang kunci, Rob perlu mengambil 2 nombor perdana yang besar.
Nombor-nombor ini akan digunakan dalam kedua-dua kunci awam dan swasta,
tetapi kunci awam hanya akan menggunakan produk ini 2 nombor,
bukan nombor itu sendiri.
Apabila saya telah disulitkan mesej menggunakan kunci awam Rob
Saya boleh menghantar mesej kepada Rob.
Untuk komputer, nombor pemfaktoran adalah masalah yang sukar.
Kunci awam, ingat, menggunakan produk 2 nombor perdana.
Produk ini kemudian mesti mempunyai hanya 2 faktor,
yang berlaku menjadi nombor yang membentuk kunci persendirian.
Dalam usaha untuk menyahsulit mesej, RSA akan menggunakan kunci persendirian
atau nombor didarab bersama dalam proses mewujudkan kunci awam.
Kerana ia adalah computationally sukar untuk faktor nombor
digunakan dalam kunci awam kepada 2 nombor yang digunakan dalam kunci persendirian
ia adalah sukar bagi penyerang untuk memikirkan kunci persendirian
yang akan diperlukan untuk menyahsulit mesej.
Sekarang mari kita pergi ke beberapa maklumat tahap yang lebih rendah RSA.
Mari kita pertama kali melihat bagaimana kita boleh menjana sepasang kunci.
Pertama, kita perlukan 2 nombor perdana.
Kami akan memanggil-2 nombor p dan q.
Dalam usaha untuk memilih p dan q, dalam amalan kita pseudorandomly akan menjana
nombor besar dan kemudian menggunakan ujian untuk menentukan sama ada atau tidak
nombor-nombor tersebut mungkin perdana.
Kita boleh terus menjana nombor rawak berulang-ulang kali
sehingga kita mempunyai 2 nombor perdana yang boleh kita gunakan.
Di sini mari kita memilih p = 23 dan q = 43.
Ingat, dalam amalan, p dan q harus nombor yang lebih besar.
Setakat yang kita tahu, semakin besar nombor, semakin sukar ia adalah
retak mesej disulitkan.
Tetapi ia juga lebih mahal untuk menyulitkan dan menyahsulit mesej.
Hari ini ia sering disyorkan bahawa p dan q adalah sekurang-kurangnya 1024 bit,
yang meletakkan setiap nombor di lebih 300 digit desimal.
Tetapi kita akan memilih nombor-nombor kecil untuk contoh ini.
Sekarang kita akan membiak p dan q bersama-sama untuk mendapatkan beberapa ke-3,
yang kita akan panggil n.
Dalam kes kita, n = 23 * 43, yang = 989.
Kami telah n = 989.
Seterusnya kita akan membiak p - 1 dengan q - 1
untuk mendapatkan nombor 4, yang kita akan memanggil m.
Dalam kes kita, m = 22 * ââ42, yang = 924.
Kami mempunyai m = 924.
Sekarang kita akan memerlukan e nombor yang agak perdana untuk m
dan kurang daripada m.
Dua nombor adalah agak perdana atau coprime
jika integer hanya positif yang membahagikan kedua-dua mereka sama rata ialah 1.
Dalam erti kata lain, terbesar pembahagi biasa e dan m
mestilah 1.
Dalam amalan, ia adalah perkara biasa untuk e untuk menjadi nombor perdana 65537
selagi bilangan ini tidak berlaku menjadi faktor m.
Bagi kunci kami, kami akan memilih e = 5
sejak 5 adalah agak perdana kepada 924.
Akhirnya, kita akan memerlukan satu nombor yang lebih, yang kita akan panggil d.
D mesti beberapa nilai yang memuaskan persamaan de = 1 (mod m).
Ini m arena menandakan kita akan menggunakan sesuatu yang dinamakan aritmetik modular.
Dalam aritmetik modular, sekali beberapa semakin tinggi daripada beberapa batasan atas
ia akan mengakhiri balik sekitar kepada 0.
Jam A, sebagai contoh, menggunakan aritmetik modular.
Satu minit selepas 1:59, sebagai contoh, adalah 2:00,
bukan 1:60.
Tangan minit telah dibalut di sekeliling kepada 0
apabila mencapai terikat atas 60 tahun.
Jadi, kita boleh mengatakan 60 adalah bersamaan dengan 0 (arena 60)
dan 125 adalah bersamaan kepada 65 adalah bersamaan dengan 5 (arena 60).
Kunci awam kami akan e sepasang dan n
di mana dalam kes ini e adalah 5 dan n ialah 989.
Kunci persendirian kami akan sepasang d dan n,
yang dalam kes kami adalah 185 dan 989.
Notis bahawa asal kita nombor perdana p dan q tidak muncul
mana-mana sahaja dalam kunci kami swasta atau awam.
Sekarang kita mempunyai pasangan kita kunci, mari kita melihat bagaimana kita boleh menyulitkan
dan menyahsulit mesej.
Saya mahu menghantar mesej kepada Rob,
jadi dia akan menjadi satu untuk menjana pasangan kunci ini.
Kemudian saya akan bertanya Rob untuk kunci awam, yang saya akan gunakan
untuk menyulitkan mesej untuk menghantar kepadanya.
Ingat, ia adalah benar-benar ok untuk Rob untuk berkongsi kunci awam dengan saya.
Tetapi ia tidak akan menjadi okay untuk berkongsi kunci persendirian.
Saya tidak mempunyai sebarang idea apa kunci persendirian beliau.
Kita boleh memecahkan m mesej kami kepada ketulan beberapa
semua yang lebih kecil daripada n dan kemudian menyulitkan setiap mereka ketulan.
Kami akan menyulitkan CS50 tali, yang kita boleh memecahkan kepada 4 ketulan,
salah satu surat.
Dalam usaha untuk menyulitkan mesej saya, saya akan perlu untuk menukar ke
beberapa jenis perwakilan angka.
Mari kita menyatukan nilai ASCII dengan watak-watak dalam mesej saya.
Dalam usaha untuk menyulitkan mesej m yang diberikan
Saya akan perlu untuk mengira c = m e (arena n).
Tetapi m mestilah lebih kecil daripada n,
atau lain mesej penuh tidak boleh dinyatakan modulo n.
Kita boleh memecahkan m kepada ketulan beberapa, semua yang lebih kecil daripada n,
dan menyulitkan setiap mereka ketulan.
Menyulitkan setiap ketulan ini, kita akan mendapat c1 = 67 5 (arena 989)
yang = 658.
Bagi sebahagian kedua kami, kami mempunyai 83 hingga 5 (arena 989)
yang = 15.
Bagi sebahagian ketiga kami, kami mempunyai 53 hingga 5 (arena 989)
yang = 799.
Dan akhirnya, untuk sebahagian terakhir kami, kami mempunyai 48 hingga 5 (arena 989)
yang = 975.
Sekarang kita boleh menghantar lebih nilai-nilai disulitkan kepada Rob.
Di sini anda pergi, Rob.
Walaupun mesej kami berada dalam penerbangan, mari kita lihat lain
bagaimana kita mendapat bahawa nilai untuk d.
D nombor kami yang diperlukan untuk memenuhi 5d = 1 (arena 924).
Ini menjadikan d songsang pendaraban 5 modulo 924.
Memandangkan integer 2, a dan b, algoritma Euclid dilanjutkan
boleh digunakan untuk mencari pembahagi terbesar sepunya bagi integer 2.
Ia juga akan memberikan kita 2 nombor lain, x dan y,
yang memuaskan persamaan kapak + oleh = pembahagi terbesar sepunya a dan b.
Bagaimana ini membantu kita?
Nah, memasang dalam e = 5 untuk
dan m = 924 untuk b
kita sudah tahu bahawa nombor-nombor ini adalah coprime.
Pembahagi terbesar sepunya mereka adalah 1.
Ini memberikan kita 5x + 924y = 1
atau 5x = 1 - 924y.
Tetapi jika kita hanya mengambil berat tentang segala-galanya modulo 924
maka kita boleh menggugurkan - 924y.
Fikirkan kembali kepada jam.
Jika tangan minit adalah pada 1 dan kemudian tepat 10 jam lulus,
kita tahu tangan minit masih akan pada 1.
Di sini kita bermula pada 1 dan kemudian membalut di sekitar masa yang tepat y,
jadi kita masih akan berada di 1.
Kami mempunyai 5x = 1 (arena 924).
Dan di sini x ini adalah sama sebagai d kami cari sebelum,
jadi jika kita menggunakan algoritma Euclid dilanjutkan
untuk mendapatkan nombor x, itulah nombor kita harus menggunakan sebagai d kami.
Sekarang mari kita menjalankan algoritma Euclid dilanjutkan untuk 5 =
dan b = 924.
Kami akan menggunakan kaedah yang dipanggil kaedah jadual.
Meja kami akan mempunyai 4 tiang, x, y, d, dan k.
Meja kami bermula dengan 2 baris.
Dalam baris pertama kami mempunyai 1, 0, maka nilai kita, iaitu 5,
dan baris kedua kami adalah 0, 1, dan nilai kita untuk b, yang merupakan 924.
Nilai lajur 4, k, akan menjadi keputusan
membahagikan nilai d berturut-turut di atas dengan nilai d
pada baris yang sama.
Kami mempunyai 5 dibahagikan dengan 924 adalah 0 dengan baki beberapa.
Ini bermakna kita mempunyai k = 0.
Sekarang nilai setiap sel lain akan menjadi nilai 2 barisan sel atas
tolak nilai berturut-turut di atas ia kali k.
Mari kita mulakan dengan d berturut-turut 3.
Kami mempunyai 5-924 * 0 = 5.
Seterusnya kita mempunyai 0 - 1 * 0 ialah 0
dan 1 - 0 * 0 yang 1.
Tidak terlalu buruk, jadi mari kita bergerak ke baris seterusnya.
Mula-mula kita perlu nilai kami k.
924 dibahagikan dengan 5 = 184 dengan bakinya beberapa,
jadi nilai kami untuk k ialah 184.
Sekarang 924-5 * 184 = 4.
1 - 0 * 184 adalah 1 dan 0-1 * 184 adalah -184.
Baiklah, mari kita buat baris seterusnya.
Nilai kami k akan menjadi 1 kerana
5 dibahagikan dengan 4 = 1 dengan baki beberapa.
Mari mengisi di ruangan lain.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Dan 1-184 * 1 adalah 185.
Mari kita lihat apa nilai seterusnya kami k akan menjadi.
Nah, ia kelihatan seperti kita mempunyai 4 dibahagikan dengan 1, yang 4.
Dalam kes ini di mana kita sedang membahagikannya dengan 1 k yang sama dengan
nilai d berturut-turut di atas bermakna bahawa kita sedang dilakukan dengan algoritma kami.
Kita boleh lihat di sini bahawa kita mempunyai x = 185 dan y = -1 dalam baris terakhir.
Mari kita kini kembali kepada matlamat asal kita.
Kami berkata bahawa nilai x akibat daripada menjalankan algoritma ini
akan menjadi songsang pendaraban (arena b).
Ini bermakna bahawa 185 adalah songsang pendaraban of 5 (arena 924)
yang bermaksud bahawa kita mempunyai nilai 185 untuk d.
Hakikat bahawa d = 1 pada baris terakhir
mengesahkan bahawa e coprime m.
Jika ia tidak 1, maka kita akan mempunyai untuk memilih e baru.
Sekarang mari kita lihat jika Rob telah menerima mesej saya.
Apabila seseorang menghantar saya mesej disulitkan
selagi saya telah disimpan kunci persendirian saya rahsia
Saya satu-satunya yang boleh menyahsulit mesej.
Untuk menyahsulit sebahagian c saya boleh mengira mesej asal
adalah sama kepada sebahagian d kuasa (arena n).
Ingatlah bahawa d dan n adalah dari kunci persendirian saya.
Untuk mendapatkan mesej penuh daripada ketulan yang kita menyahsulit setiap ketulan
dan menyatukan keputusan.
Tepat bagaimana selamat adalah RSA?
Sebenarnya, kita tidak tahu.
Keselamatan berdasarkan berapa lama ia akan mengambil penyerang untuk memecahkan mesej
disulitkan dengan RSA.
Ingatlah bahawa penyerang mempunyai akses kepada kunci awam anda,
yang mengandungi kedua-dua e dan n.
Jika penyerang menguruskan faktor n ke nombor perdana 2, p dan q,
maka dia boleh mengira d menggunakan algoritma Euclid dilanjutkan.
Ini memberikan beliau kunci persendirian, yang boleh digunakan untuk menyahsulit mesej apa-apa.
Tetapi berapa cepat kita boleh faktor integer?
Sekali lagi, kita tidak tahu.
Tiada siapa yang telah menemui cara yang cepat melakukannya,
yang bermakna yang diberikan cukup besar n
ia akan mengambil penyerang unrealistically lama
faktor nombor.
Jika seseorang mendedahkan cara yang cepat pemfaktoran integer
RSA akan dipecahkan.
Tetapi walaupun pemfaktoran integer memang perlahan
algoritma RSA masih boleh mempunyai beberapa kecacatan di dalamnya
yang membolehkan untuk penyahsulitan mudah mesej.
Tiada siapa yang telah ditemui dan mendedahkan apa-apa kecacatan lagi,
tetapi itu tidak bermakna seseorang itu tidak wujud.
Secara teori, seseorang boleh menjadi di luar sana membaca semua data yang disulitkan dengan RSA.
Ada lagi sedikit isu privasi.
Jika Tommy menyulitkan beberapa mesej menggunakan kunci awam saya
dan penyerang menyulitkan mesej yang sama menggunakan kunci awam saya
penyerang akan melihat bahawa 2 mesej adalah sama
dan dengan itu tahu apa yang Tommy disulitkan.
Dalam usaha untuk mencegah ini, mesej biasanya berpad dengan cebisan rawak
sebelum disulitkan supaya mesej yang sama disulitkan
beberapa kali akan kelihatan berbeza selagi padding pada mesej adalah berbeza.
Tetapi ingat bagaimana kita perlu berpecah mesej ke dalam ketulan
supaya setiap ketulan adalah lebih kecil daripada n?
Padding ketulan bermakna bahawa kita mungkin perlu berpecah perkara
kepada ketulan yang lebih sejak sebahagian empuk mestilah lebih kecil daripada n.
Penyulitan dan penyahsulitan agak mahal dengan RSA,
dan sebagainya yang memerlukan untuk memecahkan mesej kepada ketulan yang banyak boleh menjadi sangat mahal.
Jika jumlah data yang besar perlu disulitkan dan dibuka
kita boleh menggabungkan faedah algoritma simetri utama
dengan orang-orang RSA untuk mendapatkan kedua-dua keselamatan dan kecekapan.
Walaupun kita tidak akan pergi ke sini,
AES adalah algoritma simetri utama seperti VigenĂ¨re dan Caesar sifer
tetapi lebih sukar untuk retak.
Sudah tentu, kita tidak boleh menggunakan AES tanpa mewujudkan kunci rahsia yang dikongsi bersama
antara 2 sistem, dan kita melihat masalah dengan itu sebelum ini.
Tetapi kini kita boleh menggunakan RSA untuk mewujudkan kunci dikongsi rahsia antara 2 sistem.
Kami akan memanggil komputer menghantar data pengirim
dan komputer menerima data penerima.
Penerima mempunyai pasangan kunci RSA dan menghantar
kunci awam kepada penghantar.
Penghantar menjana kunci AES,
menyulitkan ia dengan kekunci RSA umum penerima,
dan menghantar kunci AES kepada penerima.
Penerima decrypts mesej dengan kunci RSA swasta.
Kedua-dua penghantar dan penerima kini mempunyai kunci dikongsi AES antara mereka.
AES, yang lebih cepat pada penyulitan dan penyahsulitan daripada RSA,
kini boleh digunakan untuk menyulitkan jumlah data yang besar dan menghantar mereka kepada penerima,
yang boleh menyahsulit menggunakan kunci yang sama.
AES, yang lebih cepat pada penyulitan dan penyahsulitan daripada RSA,
kini boleh digunakan untuk menyulitkan jumlah data yang besar dan menghantar mereka kepada penerima,
yang boleh menyahsulit menggunakan kunci yang sama.
Kami hanya memerlukan RSA untuk memindahkan kunci dikongsi.
Kita tidak perlu lagi untuk menggunakan RSA pada semua.
Ia kelihatan seperti saya telah mendapat mesej.
Ia tidak kisah jika sesiapa membaca apa yang kapal terbang kertas sebelum saya ditangkap
kerana saya satu-satunya dengan kunci persendirian.
Mari kita menyahsulit setiap ketulan dalam mesej.
Sebahagian pertama, 658, kami meningkatkan kuasa d, yang adalah 185,
mod n, yang 989, adalah sama kepada 67,
yang merupakan huruf C di ASCII.
Sekarang, ke Sebahagian kedua.
Sebahagian kedua mempunyai nilai 15,
yang kita meningkatkan kuasa 185,
arena 989, dan ini adalah sama kepada 83
yang merupakan S surat dalam ASCII.
Sekarang bagi sebahagian ketiga, yang mempunyai nilai 799, kita meningkatkan kepada 185,
arena 989, dan ini adalah sama kepada 53,
yang merupakan nilai watak 5 dalam ASCII.
Sekarang untuk sebahagian terakhir, yang mempunyai nilai 975,
kita meningkatkan kepada 185, 989 arena,
dan ini adalah sama dengan 48, yang merupakan nilai 0 watak dalam ASCII.
Nama saya adalah Rob Bowden, dan ini adalah CS50.
[CS50.TV]
RSA pada semua.
RSA pada semua. [Ketawa]
Pada semua.