[Powered by Google Translate] [RSA]
[Роб Бауден] [Томи MacWilliam] [Универзитетот Харвард]
[Ова е CS50.] [CS50.TV]
Ајде да ги разгледаме во RSA, широко се користи алгоритам за енкрипција на податоци.
Енкрипција алгоритми како Цезар и Vigenère шифри не се многу сигурни.
Со Цезар шифра, напаѓачот само треба да се обидат 25 различни клучеви
да се добие обичен текст порака е.
Додека шифра Vigenère е побезбеден отколку Цезар шифра
поради поголемите пребарување простор за клучеви, откако напаѓачот
знае должината на клучот во шифра Vigenère,
која може да се утврди преку анализа на моделите во криптиран текст,
шифра Vigenère не е многу посигурен отколку Цезар број.
RSA, од друга страна, не е подложен на напади се допаѓа ова.
На Цезар шифра и Vigenère шифра користи истиот клуч
за двете криптирате и декриптирање на пораката.
Ова својство го прави овие шифри симетричен клуч алгоритми.
А основниот проблем со симетричен клуч алгоритми
е дека тие се потпираат на една енкрипција и испраќање на порака
и еден примање и декрипција на пораки
на веќе договорени однапред на копчето тие двајцата ќе го користи.
Но ние имаме малку стартување проблем тука.
Како да 2 компјутери кои сакаат да комуницираат воспостави таен клуч меѓу нив?
Ако клучот мора да биде тајна, тогаш ние треба начин да криптирате и декриптирање на клучот.
Ако сите ние имаме е симетричен клуч криптографија
тогаш ние само се врати на истиот проблем.
RSA, од друга страна, пак, користи еден пар на клучеви,
еден за енкрипција, а друг за декрипција.
Една од нив е наречен јавен клуч, а другиот е приватен клуч.
Јавниот клуч се користи за шифрирање на пораките.
Како што може да се погоди од своето име, можеме да ги споделиме нашите јавниот клуч со
секој што сакате, без да се загрозат безбедноста на шифрирана порака.
Пораки шифрирани со јавен клуч
само може да се декриптира со соодветните приватен клуч.
Иако можете да ги споделите вашите јавен клуч, секогаш треба да одржите вашиот приватен клуч тајна.
и само на приватниот клуч може да се користи за дешифрирање пораки
ако 2 корисници сакаат да испраќате пораки шифрирана со RSA
и назад и корисниците треба да имаат свој јавен и приватен клуч пар.
Пораки од корисници 1 до корисникот 2
користат само пар клучеви корисникот 2, и пораки од корисник 2 до корисникот 1
користат само пар клучеви корисникот 1 е.
На фактот дека постојат 2 посебни клучеви за криптирање и декриптирање пораки
прави RSA асиметрична клуч алгоритам.
Ние не треба да го криптирате јавен клуч, со цел да ја испрати на друг компјутер
бидејќи клучот е јавна секој случај.
Ова значи дека RSA не ги имаат истите стартување проблем
како симетричен клуч алгоритми.
Значи, ако сакам да се испрати порака со RSA енкрипција
да му ја одземеш, јас прв ќе мора јавниот клуч на Rob.
Да генерира пар клучеви, Роб треба да ги собереш 2 големи прости броеви.
Овие бројки ќе се користи и во јавниот и приватниот клучеви,
но јавниот клуч само ќе го користи производот на овие 2 броја,
не броевите себе.
Откако сум шифрирана порака користејќи го јавниот клуч на Rob
Јас може да се прати порака до Роб.
За компјутер, факторинг броеви е тешко проблем.
Јавниот клуч, се сеќавам, се користи производот на 2 прости броеви.
Овој производ тогаш мора да има само 2 фактори,
кои се случи да биде на броеви кои го сочинуваат приватен клуч.
Со цел да ја декриптираат пораката, RSA ќе го искористите овој приватен клуч
или броеви помножени заедно во процесот на создавање на јавен клуч.
Затоа што тоа е изчислителна тешко да се фактор број
користи во јавниот клуч во 2 броја се користат во приватен клуч
тоа е тешко за напаѓачот да дознаам на приватниот клуч
кои ќе бидат потребни за дешифрирање на пораката.
Сега ајде да одиме во некои пониско ниво детали на RSA.
Ајде прво да видиме како можеме да генерира пар на клучеви.
Прво, ние ќе треба 2 прости броеви.
Ние ќе го нарекуваме овие 2 броја p и q.
Со цел да ги собереш p и q, во практика pseudorandomly ќе генерира
голем број и потоа користете тест за утврдување на тоа дали или не
тие бројки се веројатно премиер.
Ние може да ги задржи генерирање на случајни броеви одново и одново
додека имаме 2 прости броеви што можеме да го користиме.
Еве, ајде да изберете p = 23 и q = 43.
Запомнете, во пракса, p и q треба да биде многу поголем број.
Колку што знаеме, поголем број, толку потешко е
да попуштат шифрирана порака.
Но, тоа е исто така поскапи за пораки криптирате и декриптирање.
Денес тоа е често препорачливо е p и q се најмалку 1024 бита,
кој го става секој број од над 300 децимални цифри.
Но, ние ќе ги собереш овие мали броеви за овој пример.
Сега ќе се мултиплицираат p и q заедно за да се добие 3 бројот,
кој ќе го наречеме n.
Во нашиот случај, n = 23 * 43, кои = 989.
Имаме n = 989.
Следна ние ќе се мултиплицираат P - 1 со П - 1
да се добие 4 бројот, кој ќе го наречеме м.
Во нашиот случај, m = 22 * ​​42, кои = 924.
Имаме m = 924.
Сега ќе треба голем број е дека е релативно премиер до m
и помалку од m.
Два броја се релативно премиер или coprime
ако само позитивен цел број што ги дели двете еднакво е 1.
Со други зборови, најголемиот заеднички делител на д и м
мора да биде 1.
Во пракса, тоа е заедничка за е да биде прост број 65.537
додека оваа бројка не се случи да биде фактор на М.
За нашите клучеви, ние ќе ги собереш e = 5
од 5 е релативно премиер на 924.
Конечно, ние ќе треба уште еден број, кој ќе го наречеме г.
D мора да биде некоја вредност која ги задоволува равенката де = 1 (mod m).
Овој м мод значи ние ќе го користите нешто што се нарекува модуларен аритметика.
Во модуларен аритметика, откако голем број добива повисока од некои горна граница
тоа ќе заврши назад околу да се 0.
Часовникот, на пример, користи модуларен аритметика.
Една минута по 01:59, на пример, е 02:00,
Не 1:60.
Минута рака ја заврши околу 0
по постигнување на горна граница од 60 години.
Значи, можеме да кажеме дека 60 е еднакво на 0 (МО 60)
и 125 е еквивалентно на 65 е еднакво на 5 (МО 60).
Нашите јавен клуч ќе биде пар е и n
каде што во овој случај е е 5 и n е 989.
Нашите приватен клуч ќе биде пар d и n,
која во нашиот случај е 185 и 989.
Забележете дека нашата изворна прости броеви p и q не се појави
било каде во нашите приватни или јавни клучеви.
Сега дека ние имаме пар на клучеви, ајде да ги разгледаме во тоа како ние може да криптирате
и декриптирање на пораката.
Сакам да испратам порака до Роб,
па тој ќе биде еден да генерира овој пар клучеви.
Тогаш јас ќе побара Роб за неговиот јавен клуч, кој ќе се користи
за да го криптирате порака за да го испратиме него.
Запомни, тоа е сосема во ред за Rob да ги сподели своите јавниот клуч со мене.
Но, тоа не би било во ред да ги споделат своите приватни клучеви.
Јас немам идеја што неговиот приватен клуч е.
Ние може да се скрши нашата порака метри на неколку парчиња
сите помали од n и потоа го криптирате секоја од овие парчиња.
Ние ќе го криптирате стринг CS50, кои можеме да ги растури во 4 парчиња,
еден по буква.
Со цел да го криптирате мојата порака, ќе треба да го претворите во
некој вид на нумеричко претставување.
Ајде да concatenate на ASCII вредности со ликовите во мојата порака.
Со цел да го криптирате дадена пораката m
Ќе треба да се пресмета в = m на e (МО л).
Но m мора да биде помал од n,
или на друго место на целосна порака не може да се изрази модул n.
Ние може да се скрши м на неколку парчиња, од кои сите се помали од n,
и криптирате секоја од овие парчиња.
Енкрипција на секој од овие парчиња, ние се C1 = 67 до 5 (МО 989)
кои = 658.
За нашата втора парче имаме 83 до 5 (МО 989)
кои = 15.
За нашиот трет дел имаме 53 до 5 (МО 989)
кои = 799.
И конечно, за нашиот последен дел имаме 48 до 5 (МО 989)
кои = 975.
Сега можеме да го испрати во текот на овие шифрирана вредности Роб.
Овде и да одите, Роб.
Додека нашата порака е во лет, ајде земи друг изглед
колку имаме таа вредност за г.
Нашиот број г потребни за да ги задоволи 5D = 1 (mod 924).
Ова го прави г помножителен обратен од 5 modulo 924.
Со оглед 2 цели броеви, a и b, продолжениот Евклидовата алгоритам
може да се користи да се најде најголемиот заеднички делител на овие 2 цели броеви.
Исто така, ќе ни даде 2 други броеви, x и y,
кои ги задоволуваат равенката ax + by = најголемиот заеднички делител на a и b.
Како го прави ова ни помогне?
Па, приклучување на e = 5 за
и m = 924 за б
Ние веќе знаеме дека овие бројки се coprime.
Нивниот најголем заеднички делител е 1.
Ова ни дава 5x + 924y = 1
или 5x = 1 - 924y.
Но, ако ние само се грижат за сè modulo 924
тогаш можеме да се откажат од - 924y.
Сетам на часовникот.
Ако минута рака е на 1 и потоа точно 10 часа поминуваат,
знаеме минута рака се уште ќе биде на 1.
Еве ние започне на 1 и потоа заврши околу точно y пати,
па ние се уште ќе биде на 1.
Имаме 5x = 1 (mod 924).
И тука ова x е иста како и на г баравме пред,
па ако ние ги користиме на продолжен Евклидовата алгоритам
да се добие овој број x, тоа е број треба да се користи како наш г.
Сега ајде да се кандидира на подолг Евклидовата алгоритам за = 5
и б = 924.
Ќе се користи метод наречен табелата метод.
Нашата маса ќе има 4 колони, x, y, г, и k.
Нашата маса започнува со 2 реда.
Во првиот ред имаме 1, 0, тогаш нашата вредност на, што е 5,
и нашиот втор ред е 0, 1, и нашите вредности за б, кој е 924.
Вредноста на 4 колона, к, ќе биде резултат
на поделба на вредноста на d во ред над неа со вредноста на г
на истиот ред.
Имаме 5 поделено со 924 е 0 со некои остатокот.
Тоа значи дека имаме k = 0.
Сега вредноста на секој друг мобилен ќе биде вредноста на мобилен 2 реда над неа
минус вредноста на спорот над него пати k.
Да почнеме со г во 3 ред.
Имаме 5-924 * 0 = 5.
Следна имаме 0-1 * 0 кое е 0
и 1-0 * 0 кое е 1.
Не е премногу лоша, па ајде да се движи кон следниот ред.
Прво ние треба нашите вредноста на k.
924 поделено со 5 = 184 со некои остатокот,
така и нашата вредност за k е 184.
Сега 924-5 * 184 = 4.
1-0 * 184 е 1 и 0-1 * 184 е -184.
Добро, ајде да се направи на следниот ред.
Нашите вредноста на k ќе биде 1 затоа што
5 поделено со 4 = 1 со некои остатокот.
Ајде да се пополни во други колумни.
5-4 * 1 = 1.
0-1 * 1 = -1.
И 1-184 * 1 е 185.
Ајде да видиме што нашите следни вредноста на k ќе биде.
Па, изгледа имаме 4 поделено со 1, кој е 4.
Во овој случај каде што ние ги дели од 1 таква што k е еднакво на
вредноста на г во горниот ред значи дека ние сме направиле со нашите алгоритам.
Можеме да видиме тука што имаме x = 185 и y = -1 во последниот ред.
Ајде сега се врати во нашата изворна цел.
Рековме дека вредноста на x како резултат на работењето на овој алгоритам
ќе биде помножителен обратен на (МО б).
Тоа значи дека 185 е помножителен обратен од 5 (МО 924)
што значи дека имаат вредност од 185 за г.
Фактот дека г = 1 во последниот ред
потврдува дека е беше coprime до m.
Ако не беа 1, тогаш ние ќе мора да ги собереш нова e.
Сега да видиме дали Роб доби мојата порака.
Кога некој ми праќа шифрирана порака
колку што јас сум се чуваат мојот приватен клуч тајна
Јас сум единствениот кој може да ја декриптира пораката.
Да се ​​дешифрирате парче в можам да се пресмета оригиналната порака
е еднаква на парче да г моќ (МО л).
Запомнете дека d и n се од мојот приватен клуч.
Да се ​​добие целосна порака од нејзините парчиња се дешифрирате секој дел
и concatenate резултатите.
Точно колку безбедна е RSA?
Вистината е, не знаеме.
Безбедност се базира на тоа колку долго ќе потрае напаѓачот да попуштат порака
криптирани со RSA.
Запомнете дека напаѓачот има пристап до вашиот јавен клуч,
кој ги содржи двете е и n.
Ако напаѓачот успева да фактор n во своите 2 прости броеви, p и q,
тогаш таа може да се пресмета г користење на продолжен Евклидовата алгоритам.
Ова ја дава на приватниот клуч, кој може да се користи за декриптирање било која порака.
Но, колку брзо можеме да се фактор броеви?
Повторно, не знаеме.
Никој не најде брз начин да се направи тоа,
што значи дека со оглед на доволно големи n
ќе ја преземе напаѓачот нереално долг
да се фактор број.
Ако некој открие брзо начин на факторинг броеви
RSA ќе бидат скршени.
Но, дури и ако број factorization е инхерентно бавно
на RSA алгоритамот уште би можеле да имаат некој недостаток во него
кој овозможува лесно декрипција на пораки.
Никој не го најде и да се открие како недостаток, сепак,
но тоа не значи дека не постои.
Во теорија, некој би можел да биде таму читање на сите податоци шифрирани со RSA.
Има уште малку на приватноста прашање.
Ако Томи енкриптира некои порака користејќи мојот јавен клуч
и напаѓачот енкриптира истата порака користење на мојот јавен клуч
напаѓачот ќе видите дека на 2 пораки се идентични
и на тој начин знаеме што Томи шифрирана.
Со цел да се спречи ова, пораки обично се ватирани со случајни битови
пред да бидат криптирани, така што истиот шифрираната порака
повеќе пати ќе изгледаат различно додека Соочи на пораката е поинаква.
Но сетете се колку ние треба да се подели пораки во парчиња
така што секој дел е помал од n?
Соочи на парчиња значи дека ние можеби ќе мора да се подели работите
во уште повеќе парчиња од ватирани парче мора да биде помала од n.
Енкрипција и декрипција се релативно скапи со RSA,
и така има потреба да се пробие до пораката во многу делови може да биде многу скапо.
Ако голем обем на податоци треба да се шифрираат и декриптира
можеме да се комбинираат предностите на симетричен клуч алгоритми
со оние на RSA да добиете и двете безбедност и ефикасност.
Иако ние не би навлегувал во тоа овде,
АЕС е симетричен клуч алгоритам како Vigenère и Цезар шифри
но многу потешко да попуштат.
Се разбира, ние не може да се користи AES без воспоставување на заедничка таен клуч
помеѓу 2 системи, и видовме проблем со тоа порано.
Но сега можеме да го користиме RSA да се воспостави заедничка таен клуч помеѓу 2 системи.
Ние ќе се јавите на компјутерски испраќање на податоци на испраќачот
и компјутерски добивањето на податоците на примачот.
Примачот има RSA пар клучеви и испраќа
јавниот клуч на испраќачот.
Испраќачот генерира клучни AES,
енкриптира со RSA на примачот јавен клуч,
и ја праќа на клучните АЕС до примачот.
Примачот decrypts пораката со 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 на сите. [Смеа]
На сите.