[Powered by Google Translate] [RSA]
[Роб Bowden] [Томи MacWilliam] [Харвардския университет]
[Това е CS50. [CS50.TV]
Нека да погледнем в RSA, широко използвания алгоритъм за криптиране на данни.
Алгоритми за криптиране като Цезар и Vigenère шифри не са много сигурни.
С шифър на Цезар, един нападател, само трябва да се опита на 25 различни ключове
да получите обикновен текст на съобщението.
Докато шифър Vigenère е по-сигурен от шифър на Цезар
поради по-голямо търсене на място за ключове, след като хакер
знае дължина на ключа в шифър Vigenère,
, които могат да бъдат определени чрез анализ на моделите в криптирания текст,
шифъра Vigenère не е, че много по-сигурна от шифър на Цезар.
RSA, от друга страна, не е уязвим за атаки като тази.
Цезар шифър и Vigenère шифър използват един и същ ключ
криптиране и декриптиране на съобщение.
Това свойство го прави тези шифри симетрични алгоритми ключови.
Основен проблем със симетричен и алгоритми
е, че те разчитат на криптиране и изпращане на съобщение
и приемане и декодиране на съобщението
вече са се съгласили предварително на ключа, те ще използват.
Но ние имаме малко на проблема при стартиране.
Как два компютри, които искат да общуват установява на таен ключ между тях?
Ако ключът трябва да бъде тайна, ние се нуждаем от начин да криптира и декриптира ключ.
Ако всичко, което имаме е симетричен ключ, криптография
тогава ние току-що се върна със същия проблем.
RSA, от друга страна, използва двойка ключове,
един за криптиране и за декриптиране.
Един от тях се нарича на публичния ключ, а другият е на частния ключ.
Публичният ключ се използва за криптиране на съобщения.
Както можете да се досетите от името му, ние можем да споделяме публичния ключ с
някой искаме, без да се прави компромис със сигурността на шифровано съобщение.
Съобщения криптира с помощта на публичния ключ
може да бъде разшифрован със съответния частен ключ.
Въпреки че можете да споделите вашия публичен ключ, винаги трябва да си частен ключ тайна.
и само частният ключ може да се използва за дешифриране на съобщенията
ако искате да изпращате съобщения криптирани с RSA 2 потребители
назад и напред двамата потребители трябва да имат свой собствен публичен и частен ключ двойка.
Съобщения от потребител 1 потребител 2
използвате само двойка ключове потребител 2, и съобщения от потребител 2 потребител 1
използвате само двойка ключове потребител 1.
Фактът, че има две отделни ключове за криптиране и декриптиране съобщения
прави RSA асиметричен алгоритъм.
Ние не се нуждаем за криптиране на публичния ключ, за да го изпратите на друг компютър
, тъй като основният е публична, така или иначе.
Това означава, че RSA не имат един и същ проблема при стартиране
както на симетрични и алгоритми.
Така че, ако искате да изпратите съобщение, използвайки RSA криптиране
Роб, аз ще трябва първо Роб публичен ключ.
Да генерира двойка ключове, Роб трябва да вземем две големи прости числа.
Тези номера ще бъдат използвани и в двете публични и частни ключове,
но на публичния ключ ще използвате само продукт на тези две числа,
не самите числа.
След като съм криптира съобщение, използвайки публичния ключ на Роб
Мога да изпратя съобщение на Роб.
За компютър, факторинг номера е труден проблем.
Публичния ключ, не забравяйте, използва продукт на две прости числа.
Този продукт трябва да има само два фактора,
, които се случи да бъде на номерата, които правят на частния ключ.
За да декриптира съобщението, RSA ще използвате този частен ключ
или номера на умножават в процеса на създаване на публичен ключ.
Защото това е изчислително трудно да фактора, броят
в публичен ключ в два номера, използвани в частния ключ
това е трудно за един нападател да разбера на частния ключ
че ще бъде необходимо да декриптира съобщението.
Сега нека отидем в някои по-ниски данни за нивото на RSA.
Нека първо да видим как можем да генерира двойка ключове.
Първо, ще имаме нужда от две прости числа.
Ще наричаме тези две числа Р и Q.
За да получите Р и Q, на практика ние ще pseudorandomly генерира
големи номера и след това да използвате тест за определяне дали или не
тези цифри вероятно са премиер.
Можем да поддържаме генериране на случайни числа отново и отново
докато имаме две прости числа, които можем да използваме.
Тук нека изберем р = 23 и Q = 43.
Не забравяйте, че на практика, Р и Q трябва да бъде много по-големи номера.
Доколкото знаем, толкова по-големи номера, толкова по-трудно е
да се справи шифровано съобщение.
Но това е също по-скъпи за криптиране и декриптиране на съобщения.
Днес тя често се препоръчва п и р са най-малко 1024 бита,
която поставя всеки номер в над 300 десетични цифри.
Но ние ще вземем тези малки номера за този пример.
Сега ние ще се размножават р и р заедно, за да получите 3-ти номер,
която ще наричаме Н.
В нашия случай, N = 23 * 43 = 989.
Ние сме N = 989.
След това ще се размножават стр. - една с р - 1
да получи 4-ти номер, който ще се обадим m.
В нашия случай, m = 22 * ​​42 = 924.
Имаме m = 924.
Сега ще имаме нужда от номер, който е сравнително премиер m
и по-малко от m.
Две числа са сравнително премиер или взаимно прости
ако единственото положително цяло число, което ги разделя, така равномерно е 1.
С други думи, най-голям общ делител на д и м
трябва да бъде 1.
На практика, това е обща за електронно да бъде премиер номер 65537
толкова дълго, колкото този брой не се случи, да бъде фактор на m.
За ключовете ни, ние ще вземем E = 5
от 5 е сравнително премиер до 924.
И накрая, ще имаме нужда от още един номер, който ще се обадя на г.
D трябва да е някаква стойност, която отговаря на уравнение = 1 (МО m).
Това m Министерството на отбраната означава, че ние ще използваме нещо, което се нарича модулна аритметика.
В модулна аритметика, след като броят им се увеличава, отколкото някои горна граница
ще завърши около 0.
Часовник, например, използва модулна аритметика.
Една минута след 1:59, например, е 02:00,
не е 1:60.
Минутната стрелка е увита около 0
при достигане на горната граница на 60.
Така че, можем да кажем, 60 е еквивалентна на 0 (МО 60)
и 125 е еквивалентен на 65 е еквивалентно на 5 (МО 60).
Нашата публика ключът ще бъде двойката д и н
къде в този случай е, № 5 и № е 989.
Нашият частен ключ ще бъде двойката г и н,
който в нашия случай е 185 и 989.
Забележете, че нашата оригинална PRIMES р и р не се появяват
навсякъде в нашите частни или публични ключове.
Сега, когато имаме двойка на ключовете, нека да погледнем как можем да криптирате
и декриптиране на съобщение.
Искам да изпратя съобщение на Роб,
така че той ще бъде да генерира двойка ключове.
Тогава аз ще попитам Роб за публичния му ключ, който ще използвам
за криптиране на съобщение за изпращане към него.
Не забравяйте, че това е напълно добре за Роб, за да сподели своя публичен ключ с мен.
Но това не би било добре да сподели своя частен ключ.
Аз нямам никаква идея какво му частен ключ.
Ние може да се счупят m съобщение на няколко части
всички по-малки от N и след това криптира всеки един от тези парчета.
Ще криптиране на низ CS50, които можем да се разделят на четири парчета,
един на писмо.
За да криптирате моето послание, аз ще трябва да го конвертирате в
някакво цифрово представяне.
Да се ​​слеят ASCII стойности с героите в моето послание.
За да шифровате даден m съобщение
Аз ще трябва да се изчисли C = m д (МО н).
Но m трябва да бъде по-малък от N,
или иначе пълната съобщение не може да бъде изразена по модул N.
Ние може да се счупят m на няколко части, всички от които са по-малки от N,
и криптиране на всяка от тези парчета.
Шифроване на всеки един от тези парчета, ние се c1 = 67 до 5 (МО 989)
= 658.
За втора парче имаме 83 до 5 (МО 989)
= 15.
За третото парче имаме от 53 до 5 (МО 989)
= 799.
И накрая, за последната ни парче имаме 48 до 5 (МО 989)
= 975.
Сега ние можем да изпратим над тези криптирани стойности на Роб.
Заповядай, Роб.
Докато нашето послание е в полет, нека хвърлим още един поглед
как имаме тази стойност за г.
Нашият номер е необходима за изпълнение 5D = 1 (МО 924).
Това прави г мултипликативна обратна на 5 модул 924.
Като се имат предвид две числа А и Б, разширеното евклидово алгоритъм
може да се използва, за да открие най-големия общ делител на тези две числа.
Тя също така ще ни даде два други номера, х и у,
, които удовлетворяват уравнението брадва + = голям общ делител на А и Б.
Как това ни помогне?
Е, включване в електронната = 5 за
и m = 924 за б
ние вече знаем, че тези числа са взаимно прости.
Най-големият им общ делител е 1.
Това ни дава 5x + 924y = 1
или 5x = 1 - 924y.
Но ако ние само се грижи за всичко модул 924
тогава можем да падне - 924y.
Помислете обратно на часовника.
Ако минутната стрелка е на 1 и след това минават точно 10 часа,
ние знаем, минутната стрелка все още ще бъде на 1.
Тук ние започва от 1, а след това увийте около точно Y пъти,
така че ние все още ще бъде в 1.
Имаме 5x = 1 (МО 924).
И тук х е същото като г търсим преди,
така че ако използваме разширен Euclidean алгоритъм
за да получите този х броя, това е номер, ние трябва да използваме като наш г.
Сега нека да изпълните разширеното евклидово алгоритъм за = 5
и б = 924.
Ние ще използваме метод, наречен таблицата метод.
Нашата маса ще има четири колони, X, Y, D, и к.
Нашата маса започва с два реда.
В първия ред имаме 1, 0, тогава стойността ни, което е с 5,
и вторият ни ред е 0, 1 и стойност за б, което е 924.
Стойността на 4-та колона, к, ще бъде резултат
за разделяне на стойността на г в реда над него със стойността на г
на същия ред.
Имаме 5 разделена на 924 с някои остатъка е 0.
Това означава, че имаме к = 0.
Сега стойността на всяка друга клетка ще бъде стойността на клетъчните два реда над него
минус стойността на реда над пъти к.
Нека започнем с г в 3-ти ред.
Имаме 5-924 * 0 = 5.
След това имате 0 - 1 * 0 е 0
и 1 - 0 * 0, което е 1.
Не е много лошо, така че нека да преминем на следващия ред.
Първо трябва стойността на к.
924 делено на 5 = 184 с някои остатъка
стойност за к е 184.
Сега 924-5 * 184 = 4.
1 - 0 * 184 е 1, а 0 - 1 * 184 е -184.
Добре, нека да направим следващия ред.
Стойността на к ще бъде 1, тъй като
5 делено на 4 = 1 с някои остатъка.
Нека да си напълним в другите колони.
5 - 4 * 1 = 1.
0 - 1 * 1 = -1.
И 1-184 * 1 е 185.
Да видим каква ще бъде следващата ни стойността на к.
Е, изглежда, че имаме 4, и разделен от 1, което е с 4.
В този случай, когато сме се дели на една такава, че к е равна на
стойността на г в горния ред означава, че сме готови с нашия алгоритъм.
Ние можем да видим, че тук имаме х = 185 и Y = -1 в последния ред.
Нека сега се върнем към първоначалната ни цел.
Ние казахме, че стойността на х в резултат на използването на този алгоритъм
ще бъде мултипликативна обратна на (МО б).
Това означава, че 185 е мултипликативна обратна на 5 (МО деветстотин двадесет и четири)
което означава, че имат стойност от 185 г.
Фактът, че г = 1 в последния ред
удостоверява, че електронната е взаимно прости m.
Ако не беше 1 и след това ние ще трябва да изберете нова електронна.
Сега нека видим дали Роб е получил моето послание.
Когато някой ме изпраща кодирано съобщение
толкова дълго, колкото съм запазил личния си ключ тайна
Аз съм единственият човек, който може да декриптира съобщението.
За да декодирате парче в мога да изчислите оригиналното съобщение
е равна на парчето г мощност (МО н).
Не забравяйте, че г и т са от личния ми ключ.
За да получите съобщение от неговите парчета разшифровате всеки парче
и да се слеят резултатите.
Точно колко сигурна е RSA?
Истината е, че ние не знаем.
Сигурност се основава на колко време ще е нужно на един нападател да се справи съобщение
криптирани с RSA.
Не забравяйте, че нападателят има достъп до вашия публичен ключ,
, който съдържа д и н.
Ако нападателят успява да вземе предвид N в своите две прости числа, Р и Q,
след това тя може да се изчисли г използвате разширеното евклидово алгоритъм.
Това я дава на частен ключ, който може да се използва за декриптиране всяко съобщение.
Но колко бързо може да сме фактор числа?
Отново, ние не знаем.
Никой не е по-бърз начин да го направите,
което означава, че при достатъчно голям н
че ще вземе нападателя нереално дълго
да вземе предвид броя.
Ако някой разкри бърз начин за факторинг числа
RSA ще бъдат разбити.
Но дори и ако число факторизация по своята същност е бавен
RSA алгоритъм все още може да имат някакъв недостатък в
която дава възможност за лесно декриптиране на съобщения.
Никой не е намерен и разкрива такъв недостатък,
но това не означава, че човек не съществува.
На теория, някой може да чете всички данни, криптирани с RSA.
Налице е още един пример за проблем на неприкосновеността на личния живот.
Ако Томи криптира някакво послание с моя публичен ключ
и нападателя криптира същото съобщение с моя публичен ключ
нападателя ще видите, че две съобщения са идентични
и по този начин да знам какво Томи криптирани.
За да се предотврати това, съобщения обикновено са подплатени с битове
преди да бъдат криптирани, така че едно и също послание криптирани
няколко пъти ще изглежда различно толкова дълго, колкото подложка на съобщението е различно.
Но си спомням как ние трябва да се разделят съобщения на парчета
така, че всяко парче е по-малък от N?
Подложка на парчета означава, че ние може да се наложи да се разделят нещата
още повече парчета от тапицираната парче трябва да бъде по-малък от N.
Криптиране и декриптиране са сравнително скъпи с RSA,
и затова е необходимо да се прекъсне съобщение в много парчета може да бъде много скъпо.
Ако голям обем от данни трябва да бъдат криптирани и разшифрован
ние можем да комбинираме предимствата на симетрични и алгоритми
с тези на RSA, за да получите сигурност и ефективност.
Въпреки, че ние няма да влезем в него тук,
AES е симетричен алгоритъм като Vigenère и Цезар шифри
, но много по-трудно да се справи.
Разбира се, ние не може да използвате AES без създаване на споделен таен ключ
между две системи, и ние видяхме проблема с това преди.
Но сега можем да използваме RSA за установяване на общ таен ключ между две системи.
Ще се обадя на компютъра, изпращащ данните на подателя
и компютърът, получаващ данните на приемника.
Приемникът има двойка ключове RSA и изпраща
публичния ключ на изпращача.
Подателят генерира ключът AES,
криптира с публичен ключ RSA на приемника,
ключът AES и изпраща към приемника.
Приемникът декриптира съобщението с RSA частен ключ.
Както изпращача и получателя, сега имат споделен ключ AES между тях.
AES, която е много по-бързо криптиране и декриптиране от RSA,
може да се използва за криптиране на големи обеми от данни и ги изпраща към приемника,
който може да декриптира като се използва един и същ ключ.
AES, която е много по-бързо криптиране и декриптиране от RSA,
може да се използва за криптиране на големи обеми от данни и ги изпраща към приемника,
който може да декриптира като се използва един и същ ключ.
Ние просто трябваше RSA за прехвърляне на споделен ключ.
Вече не е необходимо да се използва RSA на всички.
Изглежда, че имам съобщение.
Това няма значение, ако някой да прочете това, което е на хартия самолет, преди да го хвана
защото аз съм само един с частния ключ.
Нека да разшифровате всеки от парчета в съобщението.
Първото парче, 658, се повиши на г сила, която е 185,
Министерството на отбраната N, която е 989, е равен на 67,
което е буквата C в ASCII.
Сега, на второто парче.
Второто парче има стойност 15,
които ще се повиши на 185-тият власт,
мод 989, а това е равно на 83
което е буквата S в ASCII.
Сега за третото парче, което има стойност 799, се повиши до 185,
мод 989, а това е равно на 53,
която е стойността на героя 5 в ASCII.
Сега за последното парче, което има стойност 975,
се повиши до 185, мод 989,
и това е равно на 48, което е стойността на характера 0 в ASCII.
Моето име е Роб Боудън, и това е CS50.
[CS50.TV]
RSA на всички.
RSA на всички. [Смях]
На всички.