[Powered by Google Translate] [RSA]
[Rob Bowden] [Tommy MacWilliam] [Đại học Harvard]
[Đây là CS50.] [CS50.TV]
Chúng ta hãy nhìn vào RSA, một thuật toán được sử dụng rộng rãi cho việc mã hóa dữ liệu.
Thuật toán mã hóa như Caesar và các thuật toán mật mã Vigenère không phải là rất an toàn.
Với mật mã Caesar, một kẻ tấn công chỉ cần thử 25 phím khác nhau
để có được đồng bằng văn bản của tin nhắn.
Trong khi mật mã Vigenère là an toàn hơn so với thuật toán mã hóa Caesar
vì không gian tìm kiếm lớn hơn cho các phím, một khi một kẻ tấn công
biết chiều dài của khoá mật mã Vigenère,
mà có thể được xác định thông qua việc phân tích các mẫu trong các văn bản được mã hóa,
mật mã Vigenère là không phải là an toàn hơn nhiều hơn so với các thuật toán mã hóa Caesar.
RSA, mặt khác, không phải là dễ bị tấn công như thế này.
Caesar thuật toán mã hóa và mật mã Vigenère sử dụng cùng khóa
cho cả hai mã hóa và giải mã tin nhắn.
Điều này làm cho các thuật toán mật mã khóa đối xứng.
Một vấn đề cơ bản với các thuật toán khóa đối xứng
là họ dựa vào một trong những mã hóa và gửi tin nhắn
và một trong những tiếp nhận và giải mã thông điệp
đã đồng ý trả trước trên chính họ sẽ sử dụng cả hai.
Nhưng chúng tôi có một chút của một vấn đề khởi động ở đây.
Làm thế nào để 2 máy tính muốn giao tiếp thiết lập một khóa bí mật giữa chúng?
Nếu khóa phải là bí mật, sau đó chúng ta cần một cách để mã hóa và giải mã khoá.
Nếu tất cả những gì chúng ta có là mật mã khóa đối xứng
sau đó chúng tôi đã chỉ cần trở lại cùng một vấn đề.
RSA, mặt khác, sử dụng một cặp khóa,
một cho việc mã hóa và một để giải mã.
Một được gọi là khóa công khai, và các khác là các khóa riêng.
Khóa công khai được sử dụng để mã hóa thông điệp.
Như bạn có thể đoán theo tên của nó, chúng ta có thể chia sẻ khóa công khai của chúng tôi với
bất cứ ai chúng tôi muốn mà không ảnh hưởng đến sự an toàn của một tin nhắn mã hóa.
Tin nhắn mã hóa bằng cách sử dụng một khóa công khai
chỉ có thể được giải mã với khóa riêng của nó tương ứng.
Trong khi bạn có thể chia sẻ chìa khóa công cộng của bạn, bạn nên luôn luôn giữ bí mật khóa riêng của bạn.
và chỉ có khóa riêng có thể được sử dụng để giải mã thông điệp
nếu 2 người muốn gửi tin nhắn được mã hóa với RSA
qua lại cả hai người dùng cần phải có cặp khóa công cộng và tư nhân của riêng mình.
Thông điệp từ người sử dụng 1 người dùng 2
chỉ sử dụng người dùng 2 cặp khóa, và tin nhắn từ người sử dụng 2 người sử dụng 1
chỉ sử dụng cặp khóa người sử dụng 1.
Thực tế là có 2 phím riêng biệt để mã hóa và giải mã tin nhắn
làm cho RSA một thuật toán khoá bất đối xứng.
Chúng ta không cần mã hóa khóa công khai để gửi đến một máy tính khác
kể từ khi chính là công anyway.
Điều này có nghĩa là RSA không có cùng một vấn đề khởi động
như các thuật toán khóa đối xứng.
Vì vậy, nếu tôi muốn gửi một tin nhắn bằng cách sử dụng mã hóa RSA
Rob, tôi lần đầu tiên sẽ cần khóa công khai của Rob.
Để tạo ra một cặp khóa, Rob cần phải chọn 2 số nguyên tố lớn.
Những con số này sẽ được sử dụng trong cả khóa công cộng và tư nhân,
nhưng khóa công khai sẽ chỉ sử dụng sản phẩm của 2 số này,
không phải là bản thân các con số.
Sau khi đã mã hóa tin nhắn bằng cách sử dụng khóa công khai của Rob
Tôi có thể gửi tin nhắn tới Rob.
Đối với máy tính, số bao thanh toán là một vấn đề khó khăn.
Chìa khóa công cộng, hãy nhớ, sử dụng sản phẩm của 2 số nguyên tố.
Sản phẩm này sau đó phải có chỉ có 2 yếu tố,
xảy ra được những con số mà tạo nên các khóa riêng.
Để tin giải mã, RSA sẽ sử dụng khóa riêng
hoặc các con số nhân với nhau trong quá trình tạo khóa công khai.
Bởi vì đó là tính toán yếu tố trong các số
được sử dụng trong một khóa công khai vào 2 số điện thoại được sử dụng trong các khóa riêng
nó sẽ là khó khăn cho kẻ tấn công để tìm ra khóa riêng
đó sẽ là cần thiết để giải mã thông điệp.
Bây giờ chúng ta hãy đi vào một số chi tiết mức độ thấp của RSA.
Trước tiên hãy xem làm thế nào chúng ta có thể tạo ra một cặp khóa.
Trước tiên, chúng tôi sẽ cần 2 số nguyên tố.
Chúng tôi sẽ gọi những 2 số p và q.
Để nhận p và q, trong thực tế, chúng tôi pseudorandomly sẽ tạo ra
số lượng lớn và sau đó sử dụng một bài kiểm tra để xác định có hay không
những con số có thể là số nguyên tố.
Chúng ta có thể tiếp tục tạo ra các số ngẫu nhiên hơn và hơn nữa
cho đến khi chúng tôi có 2 số nguyên tố mà chúng ta có thể sử dụng.
Ở đây chúng ta hãy chọn p = 23 và q = 43.
Hãy nhớ rằng, trong thực tế, p và q phải là con số lớn hơn nhiều.
Theo như chúng tôi biết, lớn hơn các con số, các khó hơn là
để crack một tin nhắn mã hóa.
Nhưng nó cũng đắt hơn tin nhắn mã hóa và giải mã.
Ngày nay nó thường được khuyên là p và q là ít nhất là 1024 bit,
trong đó đặt mỗi số hơn 300 chữ số thập phân.
Nhưng chúng tôi sẽ chọn những con số nhỏ cho ví dụ này.
Bây giờ chúng ta sẽ nhân p và q với nhau để có được một số thứ 3,
mà chúng ta sẽ gọi n.
Trong trường hợp của chúng tôi, n = 23 * 43 = 989.
Chúng tôi có n = 989.
Tiếp theo chúng ta sẽ nhân p - 1 q - 1
để có được một số thứ 4, mà chúng ta sẽ gọi m.
Trong trường hợp của chúng tôi, m = 22 * ​​42 = 924.
Chúng tôi có m = 924.
Bây giờ chúng ta sẽ cần một e con số đó là tương đối nguyên tố m
và ít hơn m.
Hai số là nguyên tố hoặc nguyên tố cùng nhau
nếu số nguyên duy nhất tích cực chia cả hai đều là 1.
Nói cách khác, ước số chung lớn nhất của e và m
phải là 1.
Trong thực tế, nó phổ biến cho e là số nguyên tố 65.537
miễn là con số này không xảy ra là một yếu tố của m.
Cho các phím của chúng tôi, chúng tôi sẽ chọn e = 5
vì 5 là tương đối nguyên tố 924.
Cuối cùng, chúng tôi sẽ cần một số lượng nhiều hơn, chúng ta sẽ gọi d.
D phải có một số giá trị đáp ứng các phương trình de = 1 (mod m).
M mod này có nghĩa chúng tôi sẽ sử dụng một cái gì đó được gọi là mô-đun số học.
Trong số học modula, một khi một số lượng được cao hơn so với một số ràng buộc trên
nó sẽ quấn lại xung quanh để 0.
Đồng hồ A, ví dụ, sử dụng số học modula.
Một phút sau 1:59, ví dụ, là 2:00,
1:60.
Kim phút đã bao bọc xung quanh là 0
khi đạt đến một ràng buộc trên là 60.
Vì vậy, chúng ta có thể nói 60 là tương đương với 0 (mod 60)
và 125 là tương đương 65 là tương đương với 5 (mod 60).
Khóa công khai của chúng tôi sẽ là cặp e và n
trong trường hợp này e là 5 và n là 989.
Khóa riêng của chúng tôi sẽ là cặp d và n,
mà trong trường hợp của chúng tôi là 185 và 989.
Chú ý rằng các số nguyên tố ban đầu của chúng tôi p và q không xuất hiện
bất cứ nơi nào trong các phím của chúng tôi tư nhân hoặc công cộng.
Bây giờ chúng ta có cặp phím của chúng tôi, chúng ta hãy xem làm thế nào chúng ta có thể mã hóa
và giải mã một tin nhắn.
Tôi muốn gửi một thông điệp tới Rob,
do đó, ông sẽ là một trong để tạo ra cặp khóa.
Sau đó, tôi sẽ yêu cầu Rob khóa công khai của mình, mà tôi sẽ sử dụng
để mã hóa một tin nhắn gửi cho anh ta.
Hãy nhớ rằng, nó hoàn toàn okay cho Rob chia sẻ khóa công khai của mình với tôi.
Nhưng nó sẽ không được chia sẻ khóa riêng của mình.
Tôi không có bất kỳ ý tưởng khóa riêng của mình là gì.
Chúng tôi có thể phá vỡ thông điệp m của chúng tôi lên thành nhiều mẩu
nhỏ hơn n và sau đó mã hóa mỗi của những khối.
Chúng tôi sẽ mã hóa CS50 chuỗi, mà chúng ta có thể chia thành 4 khối,
một cho mỗi thư.
Để mã hóa tin nhắn của tôi, tôi sẽ cần phải chuyển đổi nó thành
một số loại đại diện số.
Hãy nối các giá trị ASCII với các ký tự trong tin nhắn của tôi.
Để mã hóa một thông điệp được đưa ra m
Tôi sẽ cần phải tính toán c = m e (mod n).
Nhưng m phải nhỏ hơn n,
hoặc người nào khác được thông báo đầy đủ không thể được thể hiện modulo n.
Chúng tôi có thể phá vỡ m thành nhiều mẩu, tất cả trong số đó là nhỏ hơn n,
và mã hóa của những khối.
Mã hóa mỗi của các khối, chúng tôi nhận được c1 = 67 đến 5 (mod 989)
mà = 658.
Đối với đoạn thứ hai của chúng tôi, chúng tôi có 83 đến 5 (mod 989)
= 15.
Đối với đoạn thứ ba của chúng tôi, chúng tôi có 53 đến 5 (mod 989)
= 799.
Và cuối cùng, cho đoạn cuối cùng của chúng tôi, chúng tôi có 48 đến 5 (mod 989)
= 975.
Bây giờ chúng ta có thể gửi qua các giá trị này được mã hóa Rob.
Ở đây bạn đi, Rob.
Trong khi thông điệp của chúng tôi là trong chuyến bay, chúng ta hãy có cái nhìn khác
như thế nào, chúng tôi đã nhận rằng giá trị so với d.
D số của chúng tôi cần thiết để đáp ứng 5d = 1 (mod 924).
Điều này làm cho d nghịch đảo nhân của 5 modulo 924.
Với 2 số nguyên, a và b, thuật toán Euclide mở rộng
có thể được sử dụng để tìm ước chung lớn nhất của 2 số nguyên.
Nó cũng sẽ cho chúng ta 2 con số khác, x và y,
đáp ứng các phương trình ax + by = UCLN của a và b.
Làm thế nào để giúp chúng tôi?
Vâng, cắm vào e = 5 cho một
và m = 924 cho b
chúng ta đã biết rằng những con số này là nguyên tố cùng nhau.
Ước số chung lớn nhất của họ là 1.
Điều này cho chúng ta 5x + 924y = 1
hoặc 5x = 1 - 924y.
Nhưng nếu chúng ta chỉ quan tâm về tất cả mọi thứ modulo 924
sau đó chúng ta có thể thả - 924y.
Hãy nhớ lại đồng hồ.
Nếu bàn tay phút là 1 và sau đó đúng 10 giờ vượt qua,
chúng ta biết tay phút vẫn sẽ có trên 1.
Ở đây chúng tôi bắt đầu từ 1 và sau đó quấn xung quanh thời gian chính xác y,
vì vậy chúng tôi vẫn sẽ có tại 1.
Chúng tôi có 5x = 1 (mod 924).
Và đây x này cũng giống như d chúng tôi đang tìm kiếm trước khi,
vì vậy nếu chúng ta sử dụng thuật toán Euclide mở rộng
để có được số x, đó là số lượng, chúng ta nên sử dụng như là d của chúng tôi.
Bây giờ hãy chạy thuật toán Euclide mở rộng cho một 5 =
và b = 924.
Chúng tôi sẽ sử dụng một phương pháp gọi là phương pháp bảng.
Bảng của chúng tôi sẽ có 4 cột, x, y, d, và k.
Bảng của chúng tôi bắt đầu với 2 hàng.
Trong hàng đầu tiên, chúng tôi có 1, 0, sau đó giá trị của chúng tôi, mà là 5,
và hàng thứ hai của chúng tôi là 0, 1, và giá trị của chúng tôi cho b, đó là 924.
Giá trị của cột thứ 4, k, sẽ là kết quả
phân chia giá trị của d trong hàng trên nó với giá trị của d
trên cùng một hàng.
Chúng tôi có 5 chia cho 924 là 0 với phần còn lại một số.
Điều đó có nghĩa là chúng ta có k = 0.
Bây giờ giá trị của tất cả các tế bào khác sẽ là giá trị của 2 dòng tế bào ở trên nó
trừ đi giá trị của hàng trên nó lần k.
Chúng ta hãy bắt đầu với d ở hàng ghế thứ 3.
Chúng tôi có 5 - 924 * 0 = 5.
Tiếp theo, chúng ta có 0 - 1 * 0 mà là 0
và 1 - 0 * 0 mà là 1.
Không quá xấu, vì vậy hãy chuyển sang hàng tiếp theo.
Trước tiên, chúng ta cần giá trị của chúng tôi k.
924 chia cho 5 = 184 với một số còn lại,
do đó, giá trị của chúng tôi cho k là 184.
Bây giờ 924 - 5 * 184 = 4.
1 - 0 * 184 là 1 và 0 - 1 * 184 là -184.
Được rồi, chúng ta hãy làm hàng tiếp theo.
Giá trị của k sẽ là 1 vì
5 chia cho 4 = 1 với một số phần còn lại.
Hãy điền vào các cột khác.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
1 - 184 * 1 là 185.
Hãy xem những gì giá trị tiếp theo của chúng tôi k.
Vâng, có vẻ như chúng ta có 4 chia 1, mà là 4.
Trong trường hợp này, nơi chúng tôi đang chia 1 k như vậy mà là bằng
giá trị của d trong hàng trên có nghĩa rằng chúng tôi đang thực hiện với các thuật toán của chúng tôi.
Chúng ta có thể thấy rằng chúng ta có x = 185 và y = -1 ở hàng cuối cùng.
Bây giờ chúng ta hãy quay trở lại với mục tiêu ban đầu của chúng tôi.
Chúng tôi cho rằng, giá trị của x là kết quả của chạy thuật toán này
sẽ là nghịch đảo nhân (mod b).
Điều đó có nghĩa rằng 185 là nghịch đảo nhân của 5 (mod 924)
điều đó có nghĩa rằng chúng ta có một giá trị trong tổng số 185 d.
Thực tế là d = 1 ở hàng cuối cùng
xác minh điện tử mà nguyên tố cùng nhau m.
Nếu nó không được 1 sau đó chúng tôi sẽ phải chọn một e mới.
Bây giờ chúng ta hãy xem nếu Rob đã nhận được tin nhắn của tôi.
Khi ai đó gửi cho tôi một tin nhắn mã hóa
miễn là tôi đã giữ khoá riêng của tôi một bí mật
Tôi là người duy nhất có thể giải mã thông điệp.
Để giải mã một đoạn c tôi có thể tính toán các thông báo ban đầu
bằng các chunk d điện (mod n).
Hãy nhớ rằng d và n là các từ khóa riêng của tôi.
Để có được một tin nhắn đầy đủ từ các khối của nó chúng ta giải mã từng đoạn
và nối các kết quả.
RSA chính xác như thế nào là an toàn?
Sự thật là, chúng ta không biết.
An ninh được dựa trên bao lâu nó sẽ có được một kẻ tấn công để crack một tin nhắn
mã hóa với RSA.
Hãy nhớ rằng một kẻ tấn công có thể truy cập vào khóa công khai của bạn,
trong đó có cả e và n.
Nếu kẻ tấn công quản lý yếu tố n thành 2 số nguyên tố, p và q,
sau đó cô có thể tính toán d bằng cách sử dụng các thuật toán Euclide mở rộng.
Điều này mang lại cho cô ấy khóa riêng, có thể được sử dụng để giải mã bất kỳ tin nhắn.
Nhưng làm thế nào chúng ta có thể nhanh chóng yếu tố số nguyên?
Một lần nữa, chúng ta không biết.
Không ai đã tìm thấy một cách nhanh chóng làm việc đó,
có nghĩa là cho đủ lớn n
nó sẽ có một kẻ tấn công không thực tế dài
yếu tố trong các số.
Nếu ai đó đã tiết lộ một cách nhanh chóng các số nguyên bao thanh toán
RSA sẽ bị phá vỡ.
Nhưng thừa số nguyên ngay cả khi vốn chậm
thuật toán RSA vẫn có thể có một số lỗ hổng trong nó
cho phép dễ dàng để giải mã các thông điệp.
Không ai đã tìm thấy và tiết lộ một lỗ hổng như vậy,
nhưng điều đó không có nghĩa là không tồn tại.
Về lý thuyết, một người nào đó có thể là có đọc tất cả các dữ liệu được mã hóa với RSA.
Có một chút của một vấn đề riêng tư.
Nếu Tommy mã hóa một số tin nhắn bằng cách sử dụng khóa công cộng của tôi
và một kẻ tấn công mã hóa cùng một thông điệp bằng cách sử dụng khóa công cộng của tôi
kẻ tấn công sẽ thấy 2 thông báo giống hệt nhau
và do đó biết những gì Tommy mã hóa.
Để ngăn chặn điều này, các thông điệp thường được đệm bằng các bit ngẫu nhiên
trước khi được mã hóa để cùng một thông điệp mã hóa
nhiều lần sẽ khác miễn là padding trên tin nhắn khác nhau.
Nhưng hãy nhớ làm thế nào chúng ta phải chia tin nhắn vào khối
để mỗi đoạn nhỏ hơn n?
Padding các khối có nghĩa là chúng ta có thể có để phân chia những thứ lên
thành khối nhiều hơn kể từ khi các chunk đệm phải nhỏ hơn n.
Mã hóa và giải mã tương đối đắt tiền với RSA,
và như vậy cần phải phá vỡ một tin nhắn vào khối có thể rất tốn kém.
Nếu một khối lượng lớn dữ liệu cần phải được mã hóa và giải mã
chúng ta có thể kết hợp những lợi ích của các thuật toán khóa đối xứng
với những người của RSA để có được cả an ninh và hiệu quả.
Mặc dù chúng tôi sẽ không đi vào nó ở đây,
AES là một thuật toán khóa đối xứng như Vigenère và mật mã Caesar
nhưng khó khăn hơn nhiều để crack.
Tất nhiên, chúng tôi không thể sử dụng AES mà không thành lập một khóa chia sẻ bí mật
giữa 2 hệ thống, và chúng tôi thấy vấn đề với trước.
Nhưng bây giờ chúng tôi có thể sử dụng RSA để thiết lập phím chia sẻ bí mật giữa 2 hệ thống.
Chúng tôi sẽ gọi máy tính gửi dữ liệu người gửi
và máy tính nhận dữ liệu nhận.
Nhận có một cặp khóa RSA và gửi
khóa công khai cho người gửi.
Người gửi tạo ra một chìa khóa AES,
mã hóa nó với khóa công khai RSA của người nhận,
và gửi chìa khóa AES cho người nhận.
Người nhận giải mã thông điệp với khóa riêng của nó RSA.
Cả người gửi và người nhận đều có một chìa khóa AES được chia sẻ giữa chúng.
AES, là nhanh hơn nhiều mã hóa và giải mã hơn so với RSA,
bây giờ có thể được sử dụng để mã hóa khối lượng lớn dữ liệu và gửi đến người nhận,
giải mã có thể người sử dụng cùng khóa.
AES, là nhanh hơn nhiều mã hóa và giải mã hơn so với RSA,
bây giờ có thể được sử dụng để mã hóa khối lượng lớn dữ liệu và gửi đến người nhận,
giải mã có thể người sử dụng cùng khóa.
Chúng tôi chỉ cần RSA để chuyển khóa chia sẻ.
Chúng tôi không còn cần phải sử dụng RSA ở tất cả.
Dường như tôi đã nhận được tin nhắn.
Nó không quan trọng nếu có ai đọc những gì trên chiếc máy bay giấy trước khi tôi bắt gặp nó
bởi vì tôi là người duy nhất có khóa riêng.
Hãy giải mã mỗi của các khối trong tin nhắn.
The chunk đầu tiên, 658, chúng tôi nâng cao sức mạnh d, mà là 185,
mod n, đó là 989, bằng 67,
là chữ C trong ASCII.
Bây giờ, vào đoạn thứ hai.
Đoạn thứ hai có giá trị là 15,
mà chúng tôi nâng cao sức mạnh 185,
989 mod, và đây là bằng 83
đó là chữ S trong ASCII.
Bây giờ cho đoạn thứ ba, trong đó có giá trị 799, chúng tôi nâng cao đến 185,
989 mod, và đây là bằng 53,
đó là giá trị của nhân vật 5 trong ASCII.
Bây giờ cho đoạn cuối cùng, trong đó có giá trị 975,
chúng tôi nâng cao đến 185, mod 989,
và điều này là tương đương với 48, đó là giá trị của 0 ký tự trong ASCII.
Tên tôi là Rob Bowden, và đây là CS50.
[CS50.TV]
RSA ở tất cả.
RSA ở tất cả. [Cười]
Tại tất cả.