[Powered by Google Translate] [СРБ]
[Роб Бовден] [Томи МацВиллиам] [Универзитет Харвард]
[Ово је ЦС50.] [ЦС50.ТВ]
Хајде да погледамо РСА, нашироко користи алгоритам за енкрипцију података.
Алгоритми попут Цезара и Вигенере шифара нису баш сигурни.
Са Цезара шифри, нападач само треба пробати 25 различитих кључева
да обичан текст поруци је.
Док је Вигенере шифра је много сигурније него Цезарова шифра
због већег простора за претрагу кључева, једном нападач
зна дужину кључа у Вигенере шифри,
што се може утврдити путем анализе узорака у шифрованом тексту,
тхе Вигенере шифра није тако много сигурније него Цезарова шифра.
РСА, с друге стране, није рањива на нападе као што је овај.
Цезарова шифра и Вигенере алгоритам користи исти кључ
како за шифровање и дешифровање порука.
Ова особина чини ове шифре симетричне кључне алгоритме.
Основни проблем са симетричним алгоритмима кључним
је да се ослањају на оне криптовање и слање поруке
а онај пријем и дешифровање поруке
да је већ договорено унапред на тастеру ће обоје користе.
Али ми овде имамо мало за покретање проблема.
Како 2 компјутера који желе да комуницирају успостави тајни кључ између њих?
Ако је кључ мора бити тајна, онда морамо начин за шифровање и дешифровање кључ.
Ако је све што имамо је симетрични кључ Криптографија
онда смо управо вратио са истим проблемом.
РСА, с друге стране, користи пар кључева,
један за шифровање и дешифровање други за.
Једна се зове јавни кључ, а други је приватни кључ.
Јавни кључ се користи за шифровање порука.
Као што можете погодити по свом имену, можемо поделити наш јавни кључ са
неко ми желимо, без угрожавања сигурности шифрованом поруком.
Поруке криптовани јавни кључ
може бити дешифрована са одговарајућим приватним кључем.
Иако можете да делите свој јавни кључ, увек треба имати свој приватни кључ тајне.
и само приватни кључ може да се користи за дешифровање порука
ако 2 корисници желе да шаљете поруке шифроване са РСА
и назад и корисници морају да имају своју јавну и приватну пар кључева.
Поруке од корисника 1 до корисника 2
користите само пар кључева, Усер 2 је и порука од корисника до корисника 2 1
користити само Корисник 1 је пар кључева.
Чињеница да постоје 2 одвојена тастера за шифровање и дешифровање порука
чини РСА кључ асиметрични алгоритам.
Ми не треба да шифровање јавни кључ да би га послали на други рачунар
јер је кључ је јавни свеједно.
То значи да РСА нема исти проблем покретања
као симетрични кључ алгоритама.
Дакле, ако желим да пошаљете поруку користећи РСА шифровање
то Роб, ја прво треба Робов јавни кључ.
Да генерише пар кључева, Роб мора да узме 2 велика простих бројева.
Ови бројеви ће се користити у оба јавних и приватних кључева,
али јавни кључ ће користити само производ ових бројева 2,
нису саме бројке.
Једном сам шифроване поруке користећи Робов јавни кључ
Ја могу послати поруку на Роб.
За рачунар, факторинг бројеви је тежак проблем.
Јавни кључ, запамтите, користи производ од 2 простих бројева.
Овај производ мора онда имати само 2 фактора,
што се деси да буду бројеви који чине приватни кључ.
У циљу да дешифрује поруке, РСА ће користити овај приватни кључ
или бројеви множи заједно у процесу креирања јавног кључа.
Зато што је тешко рачунски фактор број
користи у јавним кључем у 2 бројева који се користе у приватном кључу
је тешко нападачу да схватим приватни кључ
да ће бити потребно да дешифрује поруку.
Сада идемо на неким нижим нивоима детаља РСА.
Хајде да прво видимо како можемо генерисати пар кључева.
Прво ћемо морати 2 простих бројева.
Ми ћемо позвати ове 2 броја п и к.
У циљу да изаберете п и к, у пракси псеудорандомли ће генерисати
велики број, а затим користите тест за утврђивање да ли је или не
ови бројеви су вероватно прост.
Можемо задржати генерисање случајних бројева изнова и изнова
док имамо 2 простих бројева које можемо искористити.
Ево идемо покупити П = 23 и К = 43.
Запамтите, у пракси, п и к треба да буду много веће бројеве.
Колико знамо, већи бројева, теже је
да пуца шифровану поруку.
Али то је такође скупљи за шифровање и дешифровање порука.
Данас се често препоручује да п и к су најмање 1024 бита,
који ставља сваки број на преко 300 цифара.
Али ми ћемо покупити ове мале бројеве за овај пример.
Сада ћемо помножити п и к заједно да се 3. број,
који ћемо назвати н.
У нашем случају, н = 23 * 43, који = 989.
Ми смо н = 989.
Следеће што ћемо помножити п - 1 са к - 1
да добију 4. број који ћемо назвати м.
У нашем случају, м = 22 * ​​42, која = 924.
Имамо М = 924.
Сада ћемо потребна е број који је релативно прост до м
и мање од метра.
Два броја су релативно прост и узајамно прости
ако је једини позитиван цео број који дели их обоје подједнако је 1.
Другим речима, највећи заједнички делилац е и м
мора да буде 1.
У пракси, то је уобичајено за е бити прост број 65537
док тај број не деси да буде фактор м.
За наше тастера, узећемо Е = 5
јер 5 је релативно прост да 924.
Коначно, ми ћемо морати још један број, који ћемо назвати д.
Д мора да је нека вредност која задовољава једначину де = 1 (мод м).
Овај мод м означава ћемо користити нешто што се зове модуларна аритметика.
У модуларним аритметици, када број добија већи него неке горње граница
она ће преломити назад около да 0.
Сат, на пример, користи модуларна аритметика.
Један минут након 1:59, на пример, 2:00,
Не 1:60.
Чим рука обмотана око на 0
након достизања горње границе од 60 година.
Дакле, можемо рећи 60 је еквивалентан 0 (мод 60)
а 125 је еквивалентно 65 је еквивалент 5 (мод 60).
Наш јавни кључ ће бити пар е и н
где је у овом случају е је 5 и н 989.
Наш приватни кључ ће бити пар д и н
што у нашем случају је 185 и 989.
Приметимо да је наш оригинални прости п, к не појављују
нигде у нашим приватним или јавним кључевима.
Сада када имамо пар тастера, хајде да погледамо како можемо шифровање
и дешифровање порука.
Желим да пошаљем поруку Роб,
тако да ће бити један до генерисали овај пар кључева.
Онда ћу питати Роб његовог јавног кључа, који ћу користити
за шифровање поруку послати на њега.
Запамтите, то је потпуно у реду Роб да подели своје јавни кључ са мном.
Али то не би било у реду да дели свој приватни кључ.
Немам никакву идеју шта је његов приватни кључ.
Можемо сломити нашу м поруку на неколико комада
Све мањи од н, а затим шифрује сваки од тих комада.
Ми ћемо шифровали ЦС50 ниске, што можемо да се разбије на комаде, 4
један по писму.
У циљу шифровање моју поруку, ја ћу морати да га претворили у
нека врста нумеричке репрезентације.
Идемо повезати у облику ланца АСЦИИ вредности са ликовима у мојој поруци.
У циљу шифровање дати м поруку
Ја ћу морати да израчуна ц = м на е (мод н).
Али сам мора бити мањи од н,
иначе пун порука не може бити изражена по модулу н.
Можемо сломити м на неколико комада, од којих су мањи од н,
и шифровање сваки од тих комада.
Шифровање сваки од ових комаде, добијамо Ц1 = 67 до 5 (мод 989)
која = 658.
За наш други комад имамо 83 до 5 (мод 989)
који = 15.
За наш трећи комад имамо 53 до 5 (мод 989)
која = 799.
И на крају, за наше последње комад имамо 48 до 5 (мод 989)
која = 975.
Сада можемо послати преко ове шифроване вредности Роб.
Изволи, Роб.
Иако је наша порука је у лету, хајде да погледамо још
како смо добили ту вредност за д.
Наш број д потребно да задовољи 5Д = 1 (мод 924).
Ово чини д тхе мултипликативни инверз од 5 924 модулу.
Имајући у виду целих бројева 2, и б, проширени Еуклидов алгоритам
може да се користи да пронађе највећи заједнички делилац ових бројева 2.
Такође ће нам дати 2 других бројева, Кс и И,
које задовољавају секиру једначине + би = највећег заједничког делиоца А и Б.
Како то да нам помогне?
Па, прикључивање Е = 5 за
и м = 924 за б
већ знамо да су ови бројеви су узајамно прости.
Њихов највећи заједнички делилац је 1.
То нам даје 5к + 924и = 1
или 5к = 1 - 924и.
Али, ако смо само стало свему по модулу 924
онда можемо испустити - 924и.
Сетите се сат.
Ако је сказаљка је на 1, а затим тачно 10 сати пролазе,
знамо да је сказаљка ће и даље бити на 1.
Овде ћемо почети од 1. па обмотана тачно и пута,
па ипак ћемо бити на 1.
Имамо 5к = 1 (мод 924).
И овде ово к је исти као д смо тражите раније,
па ако користимо проширени Еуклидов алгоритам
да се овај број к, то је број треба да користимо као наше д.
Сада хајде да проширени Еуклидов алгоритам за а = 5
и б = 924.
Ми ћемо користити метод се назива табела метод.
Наш сто ће имати 4 колоне, к, и, д, к.
Наш сто почиње са 2 реда.
У првом реду имамо 1, 0, онда је наша вредност, што је 5,
и наш други ред је 0, 1, а наша вредност за б, што је 924.
Вредност 4. колоне, К ће бити резултат
поделе вредност Д у реду изнад њега са вредношћу д
на истом реду.
Имамо 5 подељен 924 је 0 са неким остатка.
То значи да имамо К = 0.
Сада је вредност сваке друге ћелије ће бити вредност ћелија 2 реда изнад њега
минус вредност реда изнад њега пута к.
Почнимо са д у 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.
У овом случају смо дели са 1 такав да је к једнако
вредност д у горњој реду значи да смо завршили са нашег алгоритма.
Овде се види да имамо к = 185 и И = -1 у последњем реду.
Хајде сада вратити на наш првобитни циљ.
Рекли смо да је вредност к као резултат води овај алгоритам
ће бити мултипликативни инверз од (мод б).
То значи да је 185 мултипликативни инверз 5 (мод 924)
што значи да имамо вредност од 185 за д.
Чињеница да је д = 1 у последњем реду
проверава да е се узајамно прости са м.
Ако то није било 1, онда бисмо морали да изаберете нову е.
Хајде сада да видимо да ли Роб је добио моју поруку.
Када ми неко пошаље шифровану поруку
док сам задржао мој приватни тастер тајну
Ја сам једини који може да дешифрује поруку.
За дешифровање комад ц могу израчунати оригиналну поруку
једнак комад на д власт (мод н).
Запамтите да је д и н су из мог приватног кључа.
Да би добили потпуну поруку од својих комада можемо да дешифрујемо сваки комад
и повезати у облику ланца резултате.
Тачно како је сигурна је РСА?
Истина је, ми не знамо.
Безбедност је на основу тога колико би времена било потребно нападача да пуца поруку
шифровани РСА.
Сетите се да нападач има приступ вашем јавним кључем,
који садржи и е и н.
Ако нападач успео да фактор н у своје 2 простих бројева, П и К,
онда могли да израчунамо д користи проширени Еуклидов алгоритам.
То јој даје приватни кључ, који се може користити за дешифровање било порука.
Али, колико брзо можемо фактор бројеве?
Опет, ми не знамо.
Нико није нашао брз начин да то раде,
што значи да је дато довољно велике н
било би потребно нападача нереално дуго
да фактор број.
Ако неко открио брз начин факторинг целих бројева
РСА бити сломљен.
Али, чак и ако цео факторизација инхерентно спор
РСА алгоритам и даље могу да имају неку ману у томе
који омогућава лако дешифровање порука.
Нико није нашао и открио још такву грешку,
али то не значи да не постоји.
У теорији, неко би могао да буде тамо чита све податке шифроване РСА.
Постоји још један помало приватности питању.
Ако Томи шифрује неку поруку користећи свој јавни кључ
и нападач шифрује исту поруку користећи свој јавни кључ
нападач ће видети да су 2 поруке су идентичне
па знам шта Томи шифровани.
Да би се ово спречило, поруке су обично јастучићи са случајним битовима
пре него што шифроване тако да се иста порука шифровани
више пута ће изгледати другачије докле год постава на поруци је другачија.
Али запамтите како смо да се раздвојимо порука на комаде
тако да сваки комад је мањи од н?
Постава се ови комади значи да бисмо могли да се раздвојимо ствари
у још више комада од када је обложен комад мора бити мањи од н.
Шифровање и дешифровање су релативно скупи са РСА,
па потребе да разбију поруку на многе делове може бити веома скупо.
Ако велики обим података треба да буде шифрована и дешифрује
можемо да комбинујемо предности симетричних алгоритама кључних
са онима РСА да добијете и сигурност и ефикасност.
Иако нећемо ући у њу овде,
АЕС је симетрични кључ алгоритам као Вигенере и Цезара шифара
али је много теже сломити.
Наравно, не можемо да користимо АЕС без успостављања дељени тајни кључ
између 2 система, и видели смо проблем са тим раније.
Али сада можемо користити СЦГ да успостави заједничку тајни кључ између 2 система.
Ми ћемо позвати рачунар слања података од пошиљаоца
и рачунар прима подацима пријемник.
Пријемник има РСА пара кључева и шаље
јавни кључ пошиљаоца.
Пошиљалац генерише АЕС кључ,
шифрује га са РСА пријемника јавним кључем,
и шаље АЕС кључ пријемник.
Пријемник дешифрује поруку са РСА приватног кључа.
И пошиљалац и прималац сада имају заједничку АЕС кључ између њих.
АЕС, што је много брже него шифровање и дешифровање РСА,
сада се може користити за шифровање велике количине података и послати их на пријемник,
ко може да дешифрује користећи исти тастер.
АЕС, што је много брже него шифровање и дешифровање РСА,
сада се може користити за шифровање велике количине података и послати их на пријемник,
ко може да дешифрује користећи исти тастер.
Ми само треба РСА да пренесе заједничку тастер.
Ми више не морају да користе РСА уопште.
Изгледа да сам добио поруку.
Није битно да ли је неко прочитао оно што је на папиру авиону пре него што сам га ухватио
јер сам једини са приватним кључем.
Идемо дешифровали сваки комаде у поруци.
Први комад, 658, дижемо се д власти, што је 185,
мод н, што је 989, једнака је 67,
што је слово Ц у АСЦИИ.
Сада, на другом комад.
Други комад има вредност 15,
који дижемо до 185. власт,
мод 989, а то је једнако 83
што је слово С у АСЦИИ.
Сада трећи комад који има вредност 799, дижемо до 185,
мод 989, а то је једнако 53,
која је вредност карактера 5 у АСЦИИ.
Сада за последњи комад, који има вредност 975,
дижемо до 185, 989, мод
и то је једнако 48, што је вредност карактера 0 у АСЦИИ.
Моје име је Роб Бовден, а ово је ЦС50.
[ЦС50.ТВ]
РСА уопште.
РСА уопште. [Смех]
На све.