РСА шифровање. Опис и имплементација РСА алгоритма

РСА енкрипција је један од првих практичних јавно-кључних криптосистеми који се широко користе за безбедан пренос података. Његова главна разлика у односу на сличне услуге је да кључ за шифровање је отворен и разликује од кључ за дешифровање, који се држи у тајности. РСА технологија , ово асиметрија се заснива на практичне тешкоће факторинг репродукцију две велике простих бројева (проблем факторинга).

Историја стварања

СЦГ Име се састоји од почетних слова презимена Ривеста, Схамира и Адлеман - научника који први пут јавно описали ове алгоритама за шифровање 1977. године. Клиффорд Кокс Број, енглески математичар, који је радио за британске обавештајне службе, први развије еквивалентан систем у 1973., али није скинута ознака поверљивости до 1997. године

СЦГ корисник креира, а затим објављује јавни кључ на основу две велике простих бројева, заједно са помоћним вредности. Прости бројеви треба држати у тајности. Свако може користити јавни кључ за шифровање поруке, али ако је довољно велика, онда само неко са знањем простих бројева може да декодира поруку. РСА шифровање обелодањивање је познат као главни проблем данас је отворена расправа о томе како поузданог механизма.

РСА алгоритам је релативно споро, због чега се није толико широко користи за директно шифровање корисника. У већини случајева, ова метода се користи за пренос у заједничком кључу шифрованог за симетрично кључа за шифровање, што заузврат може обављати послове булк шифровање и дешифровање на много већим брзинама.

Када је дошло до криптосистем у свом садашњем облику?

Идеја асиметричне криптографски кључ приписују Диффие и Хеллман, који је објавио концепт у 1976, увођење дигиталних потписа, и покушава да примени теорију бројева. Њихова формулација користи дељени тајни кључ генерисан из одређени број степеновање модулу од простог броја. Међутим, они су напустили отвори питање реализације ове функције, јер су принципи факторинга није добро схваћена у то време.

Ривеста, Ади Шамир, анд Адлемана на МИТ-а су у неколико наврата покушали током година да створи једну функцију правцу који је тешко за декодирање. Ривест и Шамир (као компјутерских научника) предложили многе потенцијалне функције, док Адлемана (као математика) за претраживање за "слабе тачке" из алгоритма. Користили су много приступа и на крају развити коначну систем, сада познат као РСА у априлу 1977.

Електронски потпис и јавни кључ

Дигитални потпис или електронски потпис, је саставни део електронских врста докумената. Формирана је у одређеним криптографских промене података. Са овог додатка могуће проверити интегритет документа, његова поверљивост, као и да се утврди ко је власник. У ствари, алтернатива обичном стандардном потпис.

Ово криптосистем (РСА кодиран) нуди јавни кључ, за разлику од симетрично. Принцип рада је да се два различита тастера користи - затворен (кодиран) и на отвореном. Први се користи за генерисање дигиталног потписа, а затим бити у стању да дешифрује текст. Друго - за стварне шифровање и електронског потписа.

Коришћење потписа да боље разумеју РСА шифровање, пример који се може смањити као нормалну тајну "затворен од радозналих очију," документа.

Шта је алгоритам?

РСА алгоритам се састоји од четири корака: Кеи производњу, дистрибуцију, шифровање и дешифровање. Као што је већ поменуто, РСА шифровање укључује јавни кључ и приватни кључ. Оутдоор може бити познат свима и користи се за шифровање порука. Његова суштина лежи у чињеници да се поруке шифровани јавним кључем се дешифровати само у одређеном временском периоду, користећи тајни кључ.

Из безбедносних разлога, цели бројеви да буде изабран насумице и да буду исти по величини, али се разликују у дужини од неколико бројева да би факторинг теже. Исти исти број може бити ефикасно наћи тестом у својој једноставности, тако да је шифровање података мора нужно бити компликовано.

Јавни кључ се састоји од модула и јавни експонент. Унутрашња јединица и састоји се од приватног фигура, која би требало да буде тајна.

РСА шифровање датотека и слабости

Међутим, постоји велики број једноставних хакирање РСА механизама. Када се шифровање са ниским и малим вредностима кодни бројеви могу лако да се отвори, ако је избор корен шифрат преко целих бројева.

Пошто РСА-енкрипција је детерминистички алгоритам (тј, нема случајан компоненту), нападач може успешно покренути изабраног текста отворени напад на криптосистема шифрирањем вероватне отворене текстове под јавним кључем и проверава о томе да ли су једнаки шифрата. Семантички сигурно криптосистем се зове у случају да нападач не може да разликује између два шифровање једни од других, чак и ако зна релевантне текстове у проширеном облику. Као што је горе описано, РСА другим услугама без постава није семантички безбедна.

Додатни алгоритми за енкрипцију и заштиту

Да бисте избегли горње проблеме, у практичној примени РСА обично уметнути у неком облику структурирано, насумично пуњење пре шифровање. Ово осигурава да садржај не спада у распону од несигурних отворене текстове, и да ова порука не може да се реши методом случајног избора.

Сигурност РСА криптосистем и енкрипција на основу два математичких проблема: проблем факторинг велики број и стварни РСА проблем. Пуна откривање шифрату и потпис на РСА сматра неприхватљивом на претпоставци да оба ова проблема не може бити решен колективно.

Међутим, са могућношћу да се опорави просте факторе, нападач може да израчуна тајни експонент јавног кључа, а затим дешифрује текст користећи стандардну процедуру. Упркос чињеници да данас не постоје методе за факторинг великих природних бројева на класичне рачунару не може да се нађе, то није доказано да он не постоји.

аутоматизација

Алат, под називом ИАФУ, може да се користи за оптимизацију процеса. Аутоматизација у ИАФУ је напредна функција која комбинује алгоритама у интелектуалном и прилагођеној методологији која минимизира времена да пронађе факторе произвољним улазних бројева. Већина имплементација Мултитхреадед алгоритам омогућава ИАФУ потпуности искористе мулти- или многих мулти-цоре процесора (укључујући то алгоритам, СИКС и ЕЦМ). Пре свега, она је под контролом командне линије алат. Време проведено у потрази за шифровање ИАФУ фактор користећи конвенционални рачунара, може се смањити на секунди 103.1746. Алат обрађује бинарни капацитет од 320 бита или више. Ово је веома сложен софтвер који захтева одређену количину техничких вјештина за инсталацију и подешавање. Стога, РСА-енцриптион може бити рањиве Ц.

Хацкинг покушаја у последње време

У 2009. години, Бенџамин Муди користећи РСА 512 битни кључ је радио на дешифровање криптотекста за 73 дана, користећи само добро познату софтвера (ГГНФС) и просечну десктоп (дуал-цоре Атхлон64 на 1900 МХз). Као што показује искуство, потребно нешто мање од 5 ГБ диск и око 2,5 гигабајта меморије за процес "просејавање."

Од 2010. године, највећи број је урачунат РСА 768 бита (232 децималне, или РСА-768). Његов откривање трајао две године на неколико стотина рачунара одједном.

У пракси, РСА тастери су дуго - обично од 1024 до 4096 бита. Неки стручњаци верују да 1024-битни тастери може да постане непоуздан у блиској будућности, или чак и дуже може бити сломљени веома добро финансиране нападаче. Међутим, мало ће тврдити да је можда 4096-битне кључеве такође бити објављени у блиској будућности.

изгледи

Према томе, по правилу, претпоставља се да је РСА сигуран да ли су бројке довољно велики. Ако је основа број 300 бита или краће, и шифрату дигиталног потписа може се раставити у року од неколико сати на персоналном рачунару помоћу софтвера доступан је већ у јавном домену. А кључни дужина 512 бита, као што је приказано, може да се отвори још 1999. године, уз примену неколико стотина рачунара. Данас је могуће у наредних неколико недеља, користећи јавно доступне хардвер. Стога, могуће је да у будусцхембудет лако откривен РСА кодиран на прстима, а систем ће постати безнадежно застарела.

Званично је 2003. године, је доведена у питање безбедност 1024-битне кључеве. Тренутно, препоручује се да има минималну дужину од 2048 бита.