[Powered by Google Translate] [RSA]
[Rob Боуден] [Tommy MacWilliam] [Harvard University]
[Гэта CS50.] [CS50.TV]
Давайце зірнем на RSA, шырока выкарыстоўваецца алгарытм шыфравання дадзеных.
Алгарытмы шыфравання, як Цэзара і Виженера шыфры не вельмі бяспечна.
З шыфр Цэзара, зламысніку трэба толькі паспрабаваць 25 розных ключоў
каб атрымаць тэкст паведамлення.
У той час як шыфр Виженера з'яўляецца больш бяспечнай, чым шыфр Цэзара
з-за большага прасторы пошуку для ключоў, калі зламыснік
ведае, што даўжыня ключа ў шыфра Виженера,
што можа быць вызначана з дапамогай аналізу заканамернасцяў ў зашыфраваны тэкст,
Шыфр Виженера не нашмат больш бяспечным, чым шыфр Цэзара.
RSA, з іншага боку, не ўразлівыя для нападаў падобнага.
Шыфр Цэзара і Виженера Шыфр выкарыстоўваць той жа ключ
для шыфравання і расшыфроўкі паведамленняў.
Гэта ўласцівасць робіць гэтыя шыфры алгарытмы сіметрычнага ключа.
Асноўная праблема з сіметрычным ключом Алгарытмы
з'яўляецца тое, што яны належаць на адной шыфраванне і адпраўка паведамленняў
і той, атрымання і расшыфроўкі паведамленні
да ўжо дамовіліся загадзя на ключ, то яны будуць выкарыстоўваць.
Але ў нас ёсць трохі праблем з запускам тут.
Як 2 кампутары, якія хочуць мець зносіны стварэнні сакрэтнага ключа паміж імі?
Калі ключ павінен быць тайным, то нам патрэбен спосаб для шыфравання і дэшыфраванні ключа.
Калі ўсе мы маем, з'яўляецца сіметрычным ключом
Затым мы толькі вяртаемся да той жа праблеме.
RSA, з другога боку, выкарыстоўвае пару ключоў,
адзін для шыфравання, а іншы для расшыфроўкі.
Адна з іх завецца адкрытым ключом, а другі закрытым ключом.
Адкрыты ключ выкарыстоўваецца для шыфравання паведамленняў.
Як можна здагадацца па яго назве, мы можам падзяліцца нашым адкрытым ключом з
каго мы хочам без шкоды для бяспекі зашыфраванае паведамленне.
Паведамленні шыфруюцца з дапамогай адкрытага ключа
могуць быць расшыфраваны толькі з дапамогай адпаведнага закрытага ключа.
У той час як вы можаце падзяліцца сваім адкрытым ключом, вы заўсёды павінны мець асабістыя сакрэтны ключ.
і толькі закрыты ключ можа быць выкарыстаны для расшыфроўкі паведамленняў
калі 2 карыстальнікі хочуць, каб адправіць паведамленні, зашыфраваныя RSA
наперад і назад, як карыстальнікі павінны мець свае ўласныя дзяржаўныя і прыватныя пары ключоў.
Паведамленні ад карыстальнікаў з 1 па карыстальнік 2
выкарыстоўваць толькі пара ключоў карыстальніка 2, і паведамленняў ад карыстальнікаў 2 да карыстальніка 1
выкарыстоўваць толькі пара ключоў карыстальніка 1.
Справа ў тым, што ёсць 2 асобныя ключы для шыфравання і расшыфроўкі паведамленняў
RSA робіць асіметрычных ключоў алгарытму.
Нам не трэба, каб зашыфраваць адкрытым ключом для таго, каб адправіць яго на іншы кампутар
З ключавым з'яўляецца грамадскім любым выпадку.
Гэта азначае, што RSA не маюць той жа праблема запуску
як сіметрычны ключ алгарытму.
Так што, калі я хачу адправіць паведамленне з дапамогай шыфравання RSA
Адзежу, я ў першую чаргу неабходна адкрытага ключа Роба.
Для генерацыі пары ключоў, Роб неабходна выбраць 2 вялікіх простых лікаў.
Гэтыя лічбы будуць выкарыстоўвацца як у адкрытых і закрытых ключоў,
але адкрыты ключ будзе выкарыстоўваць толькі прадукт гэтых 2 нумары,
Не самі ліку.
Як толькі я зашыфраваў паведамленне, выкарыстоўваючы адкрыты ключ Адзежа
Я магу адправіць паведамленне Роб.
Для кампутара, факторынг лікаў з'яўляецца цяжкай задачай.
Адкрыты ключ, памятаеце, выкарыстоўвалі прадукт з 2 простых лікаў.
Гэты прадукт павінен гэта значыць толькі 2 фактару,
якія, здараецца, лічбы, якія складаюць закрыты ключ.
Для таго, каб расшыфраваць паведамленне, RSA будзе выкарыстоўваць гэты сакрэтны ключ
ці ліку перамнажаць ў працэсе стварэння адкрытага ключа.
Таму што гэта вылічальныя цяжка раскласці лік
выкарыстоўваць у адкрытых ключоў у 2 лікаў, якія выкарыстоўваюцца ў закрыты ключ
гэта цяжка для зламысніка, каб высветліць закрытага ключа
, Якія будуць неабходныя для расшыфроўкі паведамленні.
Зараз давайце ўвойдзем у некаторых нізкім узроўні дэталі RSA.
Давайце спачатку паглядзім, як мы можам генерыраваць пары ключоў.
Па-першае, нам трэба 2 простых ліку.
Мы называем гэтыя 2 ліку р і ц.
Для таго, каб падабраць р і д, на практыцы мы будзем генераваць псеўдавыпадковых
вялікіх колькасцях, а затым выкарыстоўваць тэст для вызначэння ці з'яўляецца
гэтыя лічбы, верагодна, простае.
Мы можам трымаць генерацыі выпадковых лікаў зноў і зноў
да таго часу, пакуль у нас ёсць 2 простых лікаў, мы можам выкарыстоўваць.
Вось давайце абярэм р = 23 і Q = 43.
Памятаеце, што на практыцы, р і д павінна быць значна большай колькасці.
Наколькі мы ведаем, чым больш лік, тым цяжэй
для ўзлому зашыфраваных паведамленняў.
Але гэта таксама больш дарагім для шыфравання і расшыфроўкі паведамленняў.
Сёння гэта часта рэкамендуецца, каб р і д па крайняй меры 1024 біт,
які ставіць кожны нумар у больш чым 300 дзесятковых лічбаў.
Але мы абярэм гэтых невялікіх колькасцях для гэтага прыкладу.
Цяпер мы памножым р і д разам, каб атрымаць 3-і нумар,
які мы будзем называць п.
У нашым выпадку N = 23 * 43, = 989.
Мы N = 989.
Далей мы памножым р - 1 з д - 1
каб атрымаць 4-ы нумар, які мы будзем называць м.
У нашым выпадку М = 22 * ​​42, = 924.
Мы маем т = 924.
Цяпер нам трэба лік е, што з'яўляецца адносна простым з м
і менш метраў.
Два ліку, узаемна простыя ці ўзаемна
калі толькі станоўчае цэлы лік, якое дзеліць іх абодвух раўнамерна 1.
Іншымі словамі, найбольшы агульны дзельнік е і т
павінна быць 1.
На практыцы, гэта агульныя для электроннага быць простым лікам 65537
тых часоў, пакуль гэта лік не апынуцца фактарам м.
Для нашых ключоў, мы абярэм е = 5
З 5 ўзаемна простае з 924.
Нарэшце, мы павінны будзем яшчэ адзін нумар, які мы будзем называць г.
D павінна быць некаторы значэнне, якое задавальняе раўнанню дэ = 1 (той т).
Гэта м мод азначае мы будзем выкарыстоўваць тое, што называецца модулярный арыфметыкі.
У модульнай арыфметыкі, калі побач аказваецца вышэй некаторага верхняя мяжа
яна будзе абгарнуць назад да 0.
Гадзіннік, напрыклад, выкарыстоўвае модульную арыфметыку.
Праз хвіліну пасля 1:59, напрыклад, 2:00,
Ня 1:60.
Хвілінная стрэлка была абгорнутая вакол да 0
пры дасягненні верхняй мяжы 60.
Такім чынам, мы можам сказаць, 60 гэта эквівалентна 0 (мода 60)
і 125 эквівалентна 65 эквівалентна 5 (мода 60).
Наш адкрыты ключ будзе электроннай пары і п
дзе ў дадзеным выпадку е-5 і п 989.
Наш прыватны ключ будзе пара г і н,
якая ў нашым выпадку складае 185 і 989.
Звярніце ўвагу, што нашы арыгінальныя простых р і д не з'яўляюцца
у любым месцы нашай прыватнай або дзяржаўнай ключы.
Зараз, калі ў нас ёсць пара ключоў, давайце паглядзім, як мы можам зашыфраваць
і расшыфраваць паведамленне.
Я хачу паслаць паведамленне Роб,
так што ён будзе адзін для стварэння гэтага ключа.
Тады я спытаю Rob за ягоны адкрыты ключ, які я буду выкарыстоўваць
Для шыфравання паведамленні, каб адправіць яго.
Памятаеце, што гэта цалкам нармальна для Роба падзяліцца сваім адкрытым ключом са мной.
Але гэта не было б добра, каб падзяліцца сваім закрытым ключом.
Я не маю ніякага ўяўлення, што яго закрыты ключ.
Мы можам разбіць нашы паведамленні м ўверх у некалькі кавалкаў
Усё менш п, а затым зашыфраваць кожны з гэтых кавалкаў.
Мы будзем шыфраваць радок CS50, якія мы можам разбіць на 4 кавалкаў,
па адным у лісце.
Для таго, каб зашыфраваць сваё пасланне, мне трэба, каб пераўтварыць яго ў
свайго роду лікавага прадстаўлення.
Давайце аб'яднаць ASCII значэння з сімвалаў у маім паведамленні.
Для таго, каб зашыфраваць дадзенае паведамленне м.
Мне трэба вылічыць з = м да е (той п).
Але м павінна быць менш, чым п,
ці ж поўнае паведамленне не можа быць выяўленае па модулю п.
Мы можам разбіць м на некалькі кавалкаў, кожны з якіх менш, чым п,
і шыфраваць кожны з гэтых кавалкаў.
Шыфраванне кожны з гэтых кавалкаў, мы атрымліваем c1 = 67 да 5 (мод 989)
які = 658.
Для нашага другога блока мы маем 83 да 5 (мод 989)
які = 15.
Для нашага трэцяга блока ў нас ёсць 53 да 5 (мод 989)
які = 799.
І, нарэшце, для нашага апошні кавалак у нас ёсць 48 да 5 (мод 989)
які = 975.
Цяпер мы можам напісаць за гэтыя зашыфраваныя значэння Роб.
Тут вы ідзяце, Роб.
У той час як нашы паведамленні ў палёце, давайце яшчэ раз паглядзім
на тое, як мы атрымалі, што значэнне D.
Наш нумар D, неабходны для задавальнення 5D = 1 (той 924).
Гэта робіць г мультыплікатыўны зваротнага з 5 па модулю 924.
Улічваючы, 2 цэлых лікаў, а, б, пашыраны алгарытм Эўкліда
можа быць выкарыстаны, каб знайсці найбольшы агульны дзельнік гэтых 2 цэлых лікаў.
Гэта таксама дасць нам 2 іншых нумары, х і у,
, Што задавальняе раўнанню ах + Ьу = найбольшы агульны дзельнік а і Ь.
Як гэта нам дапаможа?
Ну, падлучыўшы е = 5 для
і т = 924 для б
Мы ўжо ведаем, што гэтыя лікі ўзаемна простыя.
Іх найбольшы агульны дзельнік роўны 1.
Гэта дае нам 5x + 924y = 1
або 5x = 1 - 924y.
Але калі мы клапоцімся толькі пра ўсё па модулю 924
Затым можна апусціць - 924y.
Успомніце гадзіны.
Калі хвілінная стрэлка на 1, а затым роўна ў 10 гадзін пройдзе,
мы ведаем, што хвілінная стрэлка ўсё роўна будзе на 1.
Тут пачынаюцца з 1, а затым абгарнуць вакол менавіта ў разы,
такім чынам, мы ўсё яшчэ будзем ў 1.
У нас ёсць 5x = 1 (той 924).
І вось гэтая х гэтак жа, як г мы шукалі раней,
Такім чынам, калі мы выкарыстоўваем пашыраны алгарытм Эўкліда
каб атрымаць гэты лік х, гэты лік мы павінны выкарыстоўваць як наша г.
Зараз давайце запусцім пашыраны алгарытм Эўкліда для = 5
і B = 924.
Мы будзем выкарыстоўваць метад, званы табліцай метад.
Наша табліца будзе мець 4 калонкі, х, у, г, а к.
Наш стол пачынаецца з 2 шэрагу.
У першым шэрагу ў нас ёсць 1, 0, то наша значэнне, якое з'яўляецца 5,
і наша другі радок 0, 1, і наша значэнне б, які з'яўляецца 924.
Кошт 4-га слупка, к, будзе вынік
дзялення значэння D у радку вышэй яго значэнне D
на той жа радку.
У нас ёсць 5 падзеленае на 924 = 0 з некаторым астаткам.
Гэта азначае, што мы маем да = 0.
Зараз кошт кожнай іншай клетцы будзе значэнне вочка 2 шэрагу вышэй
мінус значэнне радкі над ім да раз.
Давайце пачнем з D у 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 такой, што да роўна
Значэнне D у прыведзенай вышэй радку азначае, што мы зрабілі з нашым алгарытмам.
Мы бачым тут, што мы маем х = 185, у = -1 ў апошнім шэрагу.
Давайце зараз вернемся да нашай першапачатковай мэты.
Мы сказалі, што значэнне х у выніку выканання гэтага алгарытму
будзе мультыплікатыўны зваротным (той бы).
Гэта азначае, што 185 з'яўляецца мультыплікатыўны зваротным 5 (мод 924)
Гэта азначае, што ў нас ёсць значэнне 185 для г.
Той факт, што D = 1 у апошняй радку
правярае, што е было ўзаемна проста з м.
Калі б гэта было не 1, то мы павінны былі б выбраць новы электронны.
Зараз давайце паглядзім, калі Роб атрымаў маё паведамленне.
Калі нехта пасылае мне зашыфраванае паведамленне
тых часоў, як я трымаў мой закрыты ключ таямніцу
Я адзіны, хто можа расшыфраваць паведамленне.
Для расшыфроўкі блока з I можна вылічыць зыходнае паведамленне
роўна кавалак у г Магутнасць (той п).
Памятаеце, што г і п ад майго закрытага ключа.
Каб атрымаць поўнае паведамленне з кавалкаў мы расшыфраваць кожны кавалак
і аб'яднаць вынікі.
Сапраўды, як забяспечваецца бяспека RSA?
Праўда, мы не ведаем.
Бяспека на аснове, як доўга гэта зойме зламысніку ўзламаць паведамленне
зашыфраваныя з RSA.
Памятаеце, што зламыснік мае доступ да вашых адкрытым ключом,
які змяшчае е і п.
Калі зламысніку атрымоўваецца раскласці п на сваіх 2 простых ліку, р і д,
тады яна магла б разлічваць D з дапамогай пашыранага алгарытму Еўкліда.
Гэта дае ёй сакрэтны ключ, які можа быць выкарыстаны для расшыфроўкі паведамленні.
Але як хутка мы можам раскласці цэлыя лікі?
Зноў жа, мы не ведаем.
Ніхто не знайшоў хуткі спосаб зрабіць гэта,
Гэта азначае, што гэты досыць вялікіх п
спатрэбіцца зламысніку нерэальна доўга
на множнікі ліку.
Калі хтосьці паказаў хуткі спосаб факторизации цэлых лікаў
RSA будзе парушаная.
Але нават калі цэлалікавых факторизации па сутнасці сваёй павольнай
RSA алгарытм можа яшчэ ёсць нейкі загана ў ім
, Што дазваляе лёгка расшыфроўкі паведамленняў.
Ніхто не знайшоў і паказаў такі загана не менш,
але гэта не азначае, што не існуе.
У тэорыі, хто-то можа быць там чытаць усе дадзеныя, зашыфраваныя з RSA.
Там іншая трохі пытанне прыватнасці.
Калі Томі шыфруе некаторыя паведамленні, выкарыстоўваючы мой адкрыты ключ
і зламыснік шыфруе паведамленне, выкарыстоўваючы той жа мой адкрыты ключ
Зламыснік ўбачыць, што 2 паведамленні ідэнтычныя
і, такім чынам, ведаем, што Томі зашыфраваныя.
Для таго, каб прадухіліць гэта, паведамленні, як правіла, дапаўняюцца выпадковымі бітамі
Перад зашыфраваныя так, што тое ж самае паведамленне, зашыфраванае
некалькі разоў будзе выглядаць па-рознаму тых часоў, як абіўка на паведамленне розныя.
Але памятаю, як мы павінны падзяліць паведамленні на кавалкі
так, каб кожны кавалак менш, чым п?
Padding кавалкі азначае, што мы, магчыма, прыйдзецца падзяліць рэчы
ў яшчэ больш кавалкаў, так як мяккі кавалак павінен быць менш, чым л.
Шыфраванне і дэшыфраванне з'яўляюцца адносна дарагімі з RSA,
і таму маюць патрэбу, каб разбіць паведамленне на мноства кавалкаў можа быць вельмі дарагім.
Калі вялікі аб'ём дадзеных павінен быць зашыфраваны і расшыфраваны
мы можам аб'яднаць перавагі сіметрычнага ключа Алгарытмы
з тымі RSA, каб атрымаць бяспеку і эфектыўнасць.
Хоць мы не будзем удавацца ў гэта тут,
AES з'яўляецца сіметрычным ключом, алгарытм, як Виженера і Цэзара шыфры
але значна больш складана узламаць.
Вядома, мы не можам выкарыстоўваць AES без стварэння агульнага сакрэтнага ключа
паміж 2 сістэмамі, і мы ўбачылі праблемы з гэтым раней.
Але цяпер мы можам выкарыстоўваць RSA для ўстанаўлення агульнага сакрэтнага ключа паміж 2 сістэмамі.
Мы будзем называць кампутар адпраўкі дадзеных адпраўніка
і кампутара атрымання дадзеных прымачом.
Прымач мае пару ключоў RSA і пасылае
адкрыты ключ адпраўніка.
Адпраўнік генеруе ключ AES,
шыфруе яго з дапамогай адкрытага ключа RSA прымача,
і адпраўляе ключ AES ў прыёмнік.
Прымач расшыфроўвае паведамленне з дапамогай свайго закрытага ключа RSA.
І адпраўнік і атрымальнік зараз ёсць ключ AES паміж імі.
AES, які з'яўляецца значна хутчэй шыфравання і дэшыфраванні, чым RSA,
Зараз можна выкарыстоўваць для шыфравання вялікіх аб'ёмаў дадзеных і адправіць іх на прыёмнік,
хто можа расшыфраваць, выкарыстоўваючы той жа ключ.
AES, які з'яўляецца значна хутчэй шыфравання і дэшыфраванні, чым RSA,
Зараз можна выкарыстоўваць для шыфравання вялікіх аб'ёмаў дадзеных і адправіць іх на прыёмнік,
хто можа расшыфраваць, выкарыстоўваючы той жа ключ.
Мы проста мелі патрэбу RSA для перадачы агульнага ключа.
Нам больш не трэба выкарыстоўваць RSA наогул.
Падобна на тое, я атрымаў паведамленне.
Гэта не мае значэння, калі хто чытаў, што на папяровы самалёцік, перш чым я злавіў яго
таму што я адзіны з зачыненым ключом.
Давайце расшыфроўка кожнага з кавалкаў ў паведамленні.
Першы кавалак, 658, мы падымаем да ўзроўню Д ўлада, якая складае 185,
мод п, што 989, роўная 67,
якая з'яўляецца літара С у ASCII.
Цяпер, на другім блоку.
Другі блок мае значэнне 15,
якія мы падымаем на 185-й улады,
мод 989, а гэта роўна 83
якая з'яўляецца лісце S у ASCII.
Цяпер у трэці кавалак, які мае значэнне 799, мы падымаем да 185,
мод 989, а гэта роўна 53,
якая з'яўляецца значэнне сімвала 5 у ASCII.
Зараз за апошні кавалак, які мае значэнне 975,
мы падымаем да 185, мод 989,
а гэта роўна 48, што значэнне сімвала 0 у ASCII.
Мяне клічуць Боб Боуден, і гэта CS50.
[CS50.TV]
RSA наогул.
RSA наогул. [Смех]
На ўсіх.