[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Harvard University]
[Ini adalah CS50.] [CS50.TV]
Mari kita lihat RSA, algoritma banyak digunakan untuk mengenkripsi data.
Algoritma enkripsi seperti Caesar dan cipher VigenĂ¨re tidak sangat aman.
Dengan cipher Caesar, penyerang hanya perlu untuk mencoba 25 kunci yang berbeda
untuk mendapatkan teks biasa pesan.
Sementara cipher VigenĂ¨re lebih aman daripada cipher Caesar
karena ruang pencarian yang lebih besar untuk kunci, setelah penyerang
mengetahui panjang kunci dalam cipher VigenĂ¨re,
yang dapat ditentukan melalui analisis pola dalam teks terenkripsi,
cipher VigenĂ¨re tidak yang jauh lebih aman dibandingkan dengan cipher Caesar.
RSA, di sisi lain, tidak rentan terhadap serangan seperti ini.
Cipher Caesar dan VigenĂ¨re cipher menggunakan kunci yang sama
untuk kedua mengenkripsi dan mendekripsi pesan.
Properti ini membuat algoritma ini cipher kunci simetris.
Masalah mendasar dengan algoritma kunci simetrik
adalah bahwa mereka bergantung pada satu enkripsi dan mengirim pesan
dan satu yang menerima dan mendekripsi pesan
untuk telah disepakati sebelumnya pada tombol mereka akan sama-sama menggunakan.
Tapi kami memiliki sedikit masalah startup di sini.
Bagaimana 2 komputer yang ingin berkomunikasi membangun kunci rahasia antara mereka?
Jika kunci harus rahasia, maka kita perlu cara untuk mengenkripsi dan mendekripsi kunci.
Jika semua yang kita miliki adalah kriptografi kunci simetrik
maka kita baru saja kembali ke masalah yang sama.
RSA, di sisi lain, menggunakan sepasang kunci,
satu untuk enkripsi dan satu lagi untuk dekripsi.
Salah satu disebut kunci publik, dan yang lainnya adalah kunci pribadi.
Kunci publik digunakan untuk mengenkripsi pesan.
Seperti yang Anda duga dengan namanya, kita bisa berbagi kunci publik kami dengan
siapa pun yang kita inginkan tanpa mengorbankan keamanan pesan terenkripsi.
Pesan dienkripsi menggunakan kunci publik
hanya dapat didekripsi dengan kunci pribadi yang sesuai.
Meskipun Anda dapat berbagi kunci publik Anda, Anda harus selalu menjaga rahasia kunci pribadi Anda.
dan hanya kunci pribadi dapat digunakan untuk mendekripsi pesan
jika 2 pengguna ingin mengirim pesan dienkripsi dengan RSA
bolak-balik kedua pengguna harus memiliki pasangan sendiri utama mereka publik dan swasta.
Pesan dari pengguna ke pengguna 1 2
hanya menggunakan pasangan kunci pengguna 2, dan pesan dari pengguna ke pengguna 2 1
hanya menggunakan pasangan kunci pengguna 1 itu.
Fakta bahwa ada 2 tombol terpisah untuk mengenkripsi dan mendekripsi pesan
membuat RSA algoritma kunci asimetrik.
Kita tidak perlu untuk mengenkripsi kunci publik untuk mengirimkannya ke komputer lain
karena kuncinya adalah masyarakat pula.
Ini berarti bahwa RSA tidak memiliki masalah startup yang sama
sebagai algoritma kunci simetrik.
Jadi jika saya ingin mengirim pesan menggunakan enkripsi RSA
untuk Rob, saya pertama kali akan membutuhkan kunci publik Rob.
Untuk menghasilkan sepasang kunci, Rob perlu memilih 2 bilangan prima besar.
Angka-angka ini akan digunakan dalam kedua kunci publik dan swasta,
namun kunci publik hanya akan menggunakan produk ini 2 angka,
bukan nomor sendiri.
Setelah saya sudah dienkripsi pesan menggunakan kunci publik Rob
Saya dapat mengirim pesan ke Rob.
Untuk komputer, nomor anjak piutang merupakan masalah yang sulit.
Kunci publik, ingat, menggunakan produk dari 2 bilangan prima.
Produk ini kemudian harus hanya memiliki 2 faktor,
yang kebetulan menjadi angka yang membentuk kunci pribadi.
Dalam rangka untuk mendekripsi pesan, RSA akan menggunakan kunci pribadi
atau nomor dikalikan bersama-sama dalam proses menciptakan kunci publik.
Karena itu komputasi sulit untuk faktor nomor
digunakan dalam kunci publik ke 2 nomor yang digunakan dalam kunci pribadi
sulit bagi penyerang untuk mengetahui kunci pribadi
yang akan diperlukan untuk mendekripsi pesan.
Sekarang mari kita pergi ke beberapa rincian tingkat yang lebih rendah dari RSA.
Mari kita pertama melihat bagaimana kita bisa menghasilkan sepasang kunci.
Pertama, kita akan membutuhkan 2 bilangan prima.
Kita akan menyebutnya 2 nomor p dan q.
Dalam rangka untuk memilih p dan q, dalam prakteknya kita pseudorandomly akan menghasilkan
jumlah besar dan kemudian menggunakan tes untuk menentukan apakah atau tidak
angka-angka mungkin prima.
Kita bisa terus menghasilkan angka acak berulang-ulang
sampai kita memiliki 2 bilangan prima yang dapat kita gunakan.
Berikut mari kita memilih p = 23 dan q = 43.
Ingat, dalam prakteknya, p dan q harus nomor jauh lebih besar.
Sejauh yang kami ketahui, semakin besar angka, semakin sulit
untuk memecahkan pesan terenkripsi.
Tapi itu juga lebih mahal untuk mengenkripsi dan mendekripsi pesan.
Hari itu sering direkomendasikan bahwa p dan q adalah minimal 1024 bit,
yang menempatkan setiap angka di lebih dari 300 digit desimal.
Tapi kita akan memilih angka-angka kecil untuk contoh ini.
Sekarang kita akan kalikan p dan q bersama-sama untuk mendapatkan nomor 3,
yang akan kita sebut n.
Dalam kasus kami, n = 23 * 43, yang = 989.
Kami memiliki n = 989.
Selanjutnya kita akan kalikan p - 1 dengan q - 1
untuk memperoleh nomor 4, yang akan kita sebut m.
Dalam kasus kami, m = 22 * ââ42, yang = 924.
Kami memiliki m = 924.
Sekarang kita akan membutuhkan e angka yang relatif prima terhadap m
dan kurang dari m.
Dua angka yang relatif prima atau coprime
jika bilangan bulat hanya positif yang membagi mereka berdua merata adalah 1.
Dengan kata lain, pembagi umum terbesar dari e dan m
harus 1.
Dalam prakteknya, itu umum untuk e menjadi bilangan prima 65.537
asalkan jumlah ini tidak terjadi menjadi faktor m.
Untuk kunci kami, kami akan memilih e = 5
sejak 5 relatif prima terhadap 924.
Akhirnya, kita perlu satu lagi nomor, yang akan kita sebut d.
D harus ada nilai yang memenuhi persamaan de = 1 (mod m).
Ini m mod menandakan kita akan menggunakan sesuatu yang disebut aritmatika modular.
Dalam aritmatika modular, setelah mendapat nomor lebih tinggi daripada beberapa batas atas
itu akan membungkus kembali sekitar ke 0.
Sebuah jam, misalnya, menggunakan aritmatika modular.
Satu menit setelah 01:59, misalnya, adalah 2:00,
tidak 1:60.
Jarum menit telah melilit ke 0
setelah mencapai batas atas 60.
Jadi, kita dapat mengatakan 60 adalah setara dengan 0 (mod 60)
dan 125 adalah setara dengan 65 adalah setara dengan 5 (mod 60).
Kunci publik kami akan menjadi pasangan e dan n
di mana dalam hal ini e adalah 5 dan n adalah 989.
Kunci pribadi kita akan menjadi pasangan d dan n,
yang dalam kasus kita adalah 185 dan 989.
Perhatikan bahwa kami asli bilangan prima p dan q tidak muncul
di mana saja di kunci kami privat atau publik.
Sekarang bahwa kita memiliki sepasang kunci kami, mari kita lihat bagaimana kita dapat mengenkripsi
dan mendekripsi pesan.
Saya ingin mengirim pesan kepada Rob,
sehingga ia akan menjadi satu untuk menghasilkan sepasang kunci.
Lalu aku akan meminta Rob untuk kunci publik, yang saya akan menggunakan
untuk mengenkripsi pesan untuk mengirim kepadanya.
Ingat, itu benar-benar oke untuk Rob berbagi kunci publik dengan saya.
Tapi itu tidak akan baik-baik saja untuk berbagi kunci pribadinya.
Saya tidak tahu apa kunci pribadinya adalah.
Kita dapat mematahkan m pesan kita menjadi beberapa potongan
semua lebih kecil dari n dan kemudian mengenkripsi masing-masing potongan.
Kami akan mengenkripsi CS50 string, yang kita dapat memecah menjadi 4 potongan,
satu per surat.
Dalam rangka untuk mengenkripsi pesan saya, saya harus mengubahnya menjadi
semacam representasi numerik.
Mari kita menggabungkan nilai-nilai ASCII dengan karakter dalam pesan saya.
Dalam rangka untuk mengenkripsi pesan yang diberikan m
Saya harus menghitung c = m ke e (mod n).
Tapi m harus lebih kecil dari n,
atau pesan penuh tidak dapat dinyatakan modulo n.
Kita dapat mematahkan m menjadi beberapa potongan, yang semuanya lebih kecil dari n,
dan mengenkripsi masing-masing potongan.
Enkripsi masing-masing potongan, kita mendapatkan c1 = 67 ke 5 (mod 989)
yang = 658.
Untuk potongan kedua kami memiliki 83 ke 5 (mod 989)
yang = 15.
Untuk potongan ketiga kami memiliki 53 ke 5 (mod 989)
yang = 799.
Dan akhirnya, untuk potongan terakhir kami kami memiliki 48 ke 5 (mod 989)
yang = 975.
Sekarang kita bisa mengirim lebih dari nilai-nilai terenkripsi ke Rob.
Di sini Anda pergi, Rob.
Sementara pesan kita dalam penerbangan, mari kita lihat lagi
bagaimana kami mendapat bahwa nilai d.
Kami nomor d diperlukan untuk memenuhi 5d = 1 (mod 924).
Hal ini membuat d invers perkalian dari 5 modulo 924.
Mengingat 2 bilangan bulat, a dan b, algoritma Euclidean diperpanjang
dapat digunakan untuk menemukan pembagi umum terbesar dari 2 bilangan bulat.
Ini juga akan memberi kita 2 nomor lainnya, x dan y,
yang memenuhi persamaan ax + by = pembagi umum terbesar dari a dan b.
Bagaimana hal ini membantu kita?
Nah, memasukkan e = 5 untuk
dan m = 924 untuk b
kita sudah tahu bahwa angka-angka coprime.
Terbesar pembagi umum mereka adalah 1.
Ini memberi kita 5x + 924y = 1
atau 5x = 1 - 924y.
Tetapi jika kita hanya peduli tentang segala sesuatu modulo 924
maka kita bisa drop - 924y.
Pikirkan kembali ke jam.
Jika jarum menit pada 1 dan kemudian tepat 10 jam berlalu,
kita tahu sisi menit masih akan berada di 1.
Di sini kita mulai pada 1 dan kemudian membungkus kali persis y,
jadi kami masih akan berada di 1.
Kami memiliki 5x = 1 (mod 924).
Dan di sini x ini adalah sama dengan d kita cari sebelumnya,
jadi jika kita menggunakan algoritma Euclidean diperpanjang
untuk mendapatkan nomor x, itulah jumlah yang harus kita gunakan sebagai d kami.
Sekarang mari kita jalankan algoritma Euclidean diperpanjang untuk = 5
dan b = 924.
Kita akan menggunakan metode yang disebut metode tabel.
Meja kami akan memiliki 4 kolom, x, y, d, dan k.
Meja kami dimulai dengan 2 baris.
Pada baris pertama kita punya 1, 0, maka nilai kita, yang adalah 5,
dan baris kedua adalah 0, 1, dan nilai kami untuk b, yaitu 924.
Nilai kolom 4, k, akan menjadi hasil
membagi nilai d pada baris di atasnya dengan nilai d
pada baris yang sama.
Kami memiliki 5 dibagi dengan 924 adalah 0 dengan sisa beberapa.
Itu berarti kita memiliki k = 0.
Sekarang nilai setiap sel lainnya akan menjadi nilai dari 2 baris sel di atasnya
dikurangi nilai dari baris di atas kali k.
Mari kita mulai dengan d di baris ke-3.
Kami memiliki 5-924 * 0 = 5.
Selanjutnya kita memiliki 0 - 1 * 0 yang 0
dan 1 - 0 * 0 yang adalah 1.
Tidak terlalu buruk, jadi mari kita beralih ke baris berikutnya.
Pertama kita perlu nilai kami k.
924 dibagi dengan 5 = 184 dengan sisa beberapa,
sehingga nilai kami untuk k adalah 184.
Sekarang 924-5 * 184 = 4.
1 - 0 * 184 adalah 1 dan 0 - 1 * 184 adalah -184.
Baiklah, mari kita lakukan baris berikutnya.
Nilai kami akan k 1 karena
5 dibagi dengan 4 = 1 dengan sisa beberapa.
Mari kita mengisi kolom lainnya.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
Dan 1 - 184 * 1 adalah 185.
Mari kita lihat apa nilai berikutnya kami akan k.
Yah, sepertinya kita memiliki 4 dibagi oleh 1, yaitu 4.
Dalam kasus di mana kita membaginya dengan 1 seperti k yaitu sebesar
nilai d pada baris di atas berarti bahwa kita sudah selesai dengan algoritma kami.
Kita bisa lihat di sini bahwa kita memiliki x = 185 dan y = -1 pada baris terakhir.
Sekarang mari kita kembali ke tujuan asli kami.
Kami mengatakan bahwa nilai x sebagai hasil dari menjalankan algoritma ini
akan menjadi invers perkalian dari (mod b).
Itu berarti bahwa 185 adalah invers perkalian dari 5 (mod 924)
yang berarti bahwa kita memiliki nilai 185 untuk d.
Kenyataan bahwa d = 1 di baris terakhir
memverifikasi e yang coprime ke m.
Jika bukan 1 maka kita akan harus memilih e baru.
Sekarang mari kita lihat apakah Rob telah menerima pesan saya.
Ketika seseorang mengirim saya pesan terenkripsi
selama saya sudah menyimpan kunci pribadi saya rahasia
Saya satu-satunya yang dapat mendekripsi pesan.
Untuk mendekripsi c sepotong saya bisa menghitung pesan asli
adalah sama dengan potongan untuk d listrik (mod n).
Ingat bahwa d dan n dari kunci pribadi saya.
Untuk mendapatkan pesan penuh dari potongan yang kita mendekripsi potongan masing-masing
dan menggabungkan hasilnya.
Persis bagaimana aman adalah RSA?
Yang benar adalah, kita tidak tahu.
Keamanan didasarkan pada berapa lama waktu yang dibutuhkan seorang penyerang untuk memecahkan pesan
dienkripsi dengan RSA.
Ingat bahwa penyerang memiliki akses ke kunci publik Anda,
yang berisi baik e dan n.
Jika penyerang berhasil faktor n menjadi 2 nya bilangan prima, p dan q,
maka dia bisa menghitung d dengan menggunakan algoritma Euclidean diperpanjang.
Ini memberinya kunci pribadi, yang dapat digunakan untuk mendekripsi pesan apapun.
Tapi seberapa cepat kita bisa faktor bilangan bulat?
Sekali lagi, kita tidak tahu.
Tak seorang pun telah menemukan cara cepat untuk melakukannya,
yang berarti yang diberikan cukup besar n
itu akan mengambil penyerang realistis lama
untuk faktor nomor.
Jika seseorang mengungkapkan cara cepat bilangan bulat anjak
RSA akan rusak.
Tetapi bahkan jika faktorisasi integer secara inheren lambat
algoritma RSA masih bisa memiliki cacat beberapa di dalamnya
yang memungkinkan untuk dekripsi pesan mudah.
Tak seorang pun telah menemukan dan mengungkapkan seperti cacat belum,
tapi itu bukan berarti salah satu tidak ada.
Secara teori, seseorang bisa berada di luar sana membaca semua data dienkripsi dengan RSA.
Ada lagi sedikit masalah privasi.
Jika Tommy mengenkripsi beberapa pesan menggunakan kunci publik saya
dan penyerang mengenkripsi pesan yang sama dengan menggunakan kunci publik saya
penyerang akan melihat bahwa 2 pesan adalah identik
dan dengan demikian tahu apa Tommy dienkripsi.
Untuk mencegah hal ini, pesan biasanya diisi dengan bit acak
sebelum dienkripsi sehingga pesan yang sama dienkripsi
beberapa kali akan terlihat berbeda asalkan padding pada pesan yang berbeda.
Tapi ingat bagaimana kita harus membagi pesan ke dalam potongan
sehingga potongan masing-masing lebih kecil dari n?
Pelapis potongan berarti bahwa kita mungkin harus membagi hal-hal
menjadi potongan-potongan lebih karena potongan empuk harus lebih kecil dari n.
Enkripsi dan dekripsi relatif mahal dengan RSA,
sehingga perlu untuk memecah pesan menjadi potongan-potongan yang bisa sangat mahal.
Jika volume data yang besar perlu dienkripsi dan didekripsi
kita bisa menggabungkan manfaat dari algoritma kunci simetrik
dengan orang-orang dari RSA untuk mendapatkan baik keamanan dan efisiensi.
Meskipun kami tidak akan masuk ke sini,
AES merupakan algoritma kunci simetrik seperti VigenĂ¨re dan Caesar cipher
tetapi jauh lebih sulit untuk retak.
Tentu saja, kita tidak dapat menggunakan AES tanpa membangun kunci rahasia bersama
antara 2 sistem, dan kami melihat masalah dengan itu sebelumnya.
Tapi sekarang kita dapat menggunakan RSA untuk membangun kunci rahasia bersama antara 2 sistem.
Kami akan memanggil komputer pengirim data pengirim
dan komputer menerima data penerima.
Penerima memiliki sepasang kunci RSA dan mengirimkan
kunci publik ke pengirim.
Pengirim menghasilkan kunci AES,
mengenkripsi dengan kunci publik RSA penerima,
dan mengirim kunci AES ke penerima.
Penerima dekripsi pesan dengan kunci RSA pribadi.
Kedua pengirim dan penerima sekarang memiliki kunci AES bersama antara mereka.
AES, yang jauh lebih cepat pada enkripsi dan dekripsi dari RSA,
sekarang dapat digunakan untuk mengenkripsi data dalam jumlah besar dan mengirimnya ke penerima,
yang dapat mendekripsi menggunakan tombol yang sama.
AES, yang jauh lebih cepat pada enkripsi dan dekripsi dari RSA,
sekarang dapat digunakan untuk mengenkripsi data dalam jumlah besar dan mengirimnya ke penerima,
yang dapat mendekripsi menggunakan tombol yang sama.
Kita hanya perlu RSA untuk mentransfer kunci bersama.
Kita tidak perlu lagi menggunakan RSA sama sekali.
Sepertinya aku punya pesan.
Tidak peduli apakah ada orang membaca apa yang ada di pesawat kertas sebelum aku menangkapnya
karena aku satu-satunya dengan kunci pribadi.
Mari kita mendekripsi setiap potongan dalam pesan.
Potongan pertama, 658, kami menaikkan dengan kekuatan d, yaitu 185,
mod n, yaitu 989, sama dengan 67,
yang merupakan huruf C dalam ASCII.
Sekarang, ke potongan kedua.
Potongan kedua memiliki nilai 15,
yang kita meningkat menjadi kekuatan 185,
mod 989, dan ini sama dengan 83
yang merupakan huruf S dalam ASCII.
Sekarang untuk potongan ketiga, yang memiliki nilai 799, kami meningkat menjadi 185,
mod 989, dan ini sama dengan 53,
yang merupakan nilai dari karakter ASCII 5 di.
Sekarang untuk potongan terakhir, yang memiliki nilai 975,
kami meningkat menjadi 185, mod 989,
dan ini sama dengan 48, yang merupakan nilai dari 0 karakter dalam ASCII.
Nama saya Rob Bowden, dan ini adalah CS50.
[CS50.TV]
RSA sama sekali.
RSA sama sekali. [Tertawa]
Sama sekali.