RSA-шыфраванне. Апісанне і рэалізацыя алгарытму RSA

RSA-шыфраванне ўяўляе сабой адну з першых практычных криптосистем з адкрытым ключом, якая шырока выкарыстоўваецца для бяспечнай перадачы дадзеных. Яе асноўнае адрозненне ад падобных сэрвісаў у тым, што ключ шыфравання з'яўляецца адкрытым і адрозніваецца ад ключа дэшыфравання, які трымаецца ў сакрэце. У тэхналогіі RSA гэтая асіметрыя заснавана на практычнай складанасці факторынгавыя прайгравання двух вялікіх простых лікаў (праблема факторынгу).

Гісторыя стварэння

Назва RSA складаецца з пачатковых літар прозвішчаў Ривест, Шамір і Адлеман, - навукоўцаў, якія ўпершыню публічна апісалі падобныя алгарытмы шыфравання ў 1977 годзе. Кліфард Кокс, англійская матэматык, які працаваў на спецслужбы Вялікабрытаніі, упершыню распрацаваў эквівалентную сістэму ў 1973 годзе, але яна не была рассакрэчана да 1997 г.

Карыстальнік RSA стварае і затым публікуе адкрыты ключ, заснаваны на двух вялікіх простых ліках разам з дапаможным значэннем. Простыя лікі павінны захоўвацца ў таямніцы. Любы чалавек можа выкарыстоўваць адкрыты ключ для шыфравання паведамлення, але калі ён досыць вялікі, то толькі хто-небудзь з веданнем простых лікаў можа дэкадаваць паведамленне. Раскрыццё RSA шыфравання вядома як асноўная праблема: сёння застаецца адкрытай дыскусія пра тое, наколькі гэта надзейны механізм.

RSA з'яўляецца адносна павольным алгарытмам, па прычыне чаго ён не так шырока выкарыстоўваецца для непасрэднага шыфравання дадзеных карыстача. Часцей за ўсё гэты метад выкарыстоўваюць для перадачы ў зашыфраваным выглядзе агульных ключоў для сіметрычнага ключа шыфравання, які, у сваю чаргу, можа выконваць аперацыі масавага шыфравання і дэшыфраванні на значна больш высокай хуткасці.

Калі з'явілася крыптасістэмы ў сучасным выглядзе?

Ідэя асіметрычнага ключа крыптасістэмы прыпісваецца Диффи і Хеллману, якія апублікавалі канцэпцыю ў 1976 годзе, прадставіўшы лічбавыя подпісы і паспрабаваўшы прымяніць тэорыю лікаў. Іх фармулёўка выкарыстоўвае агульны сакрэтны ключ, створаны з экспоненциации некаторага ліку па модулю простага ліку. Тым не менш, яны пакінулі адкрытай праблему рэалізацыі гэтай функцыі, паколькі прынцыпы факторынгу не былi добра вывучаны ў той час.

Ривест, Ады Шамір і Адлеман ў Масачусецкім тэхналагічным інстытуце распачалі некалькі спроб на працягу года, каб стварыць Аднанакіраваная функцыю, якую цяжка раскадаваць. Ривест і Шамір (як кампутарныя навукоўцы) прапанавалі мноства патэнцыйных функцый, у той час як Адлеманом (як матэматыкам) ажыццяўляўся пошук «слабых месцаў» алгарытму. Яны выкарыстоўвалі шмат падыходаў і ў канчатковым выніку ў красавіку 1977 года распрацавалі канчаткова сістэму, сёння вядомую як RSA.

ЭЛП і адкрыты ключ

Электронны лічбавы подпіс, ці ЭЛП, уяўляе сабой складаную частку дакументаў электроннага тыпу. Яна утвараецца пры пэўным крыптаграфічным змене дадзеных. З дапамогай гэтага атрыбуту магчыма правесці праверку цэласнасці дакумента, яго прыватнасці, а таксама ўсталяваць, хто з'яўляецца яго ўладальнікам. Па сутнасці, гэта альтэрнатыва звычайнай стандартнай подпісы.

Дадзеная крыптасістэмы (RSA-шыфраванне) прапануе адкрыты ключ, чым адрозніваецца ад сіметрычных. Прынцып яе функцыянавання ў тым, што ўжываюць два розных ключа - закрыты (зашыфраваны), а таксама адкрытае. Першы ўжываюць для таго, каб згенераваць ЭЛП і пасля атрымаць магчымасць расшыфроўкі тэксту. Другі - для ўласна шыфравання і праверкі ЭЛП.

Выкарыстанне подпісы дазваляе лепш зразумець шыфраванне RSA, прыклад якога можна прывесці як звычайны засакрэчаны «закрыты ад старонніх вачэй» дакумент.

У чым сутнасць алгарытму?

Алгарытм RSA складаецца з чатырох этапаў: генерацыі ключоў, іх размеркавання, шыфравання і дэшыфраванні. Як ужо было паказана, RSA-шыфраванне ўключае ў сябе адкрыты ключ і закрыты ключ. Адкрыты можа быць вядомы ўсім і выкарыстоўваецца для шыфравання паведамленняў. Сутнасць яго складаецца ў тым, што паведамленні, зашыфраваныя з дапамогай адкрытага ключа, могуць быць расшыфраваны толькі ў пэўны прамежак часу з выкарыстаннем сакрэтнага ключа.

У мэтах бяспекі цэлыя лікі павінны быць выбраны выпадковым чынам і быць аднолькавымі па велічыні, але пры гэтым адрознівацца па даўжыні на некалькі лічбаў, каб зрабіць факторынг складаней. Аднолькавыя самай даты могуць быць эфектыўна знойдзены з дапамогай тэсту на іх прастату, таму шыфраванне інфармацыі павінна абавязкова ўскладняцца.

Адкрыты ключ складаецца з модуля і публічнай экспаненты. Закрыты складаецца з модуля і прыватнага паказчыка, які павінен захоўвацца ў таямніцы.

Шыфраванне файлаў RSA і слабыя месцы

Аднак існуе цэлы шэраг механізмаў па ўзломе простага RSA. Пры шыфраванні з нізкімі паказчыкамі і малымі значэннямі лікаў шыфр можа быць лёгка раскрыты, калі падабраць корань шифротекста над цэлымі лікамі.

Паколькі RSA-шыфраванне з'яўляецца дэтэрмінаваных алгарытмам (г.зн. не мае выпадковай складнікам), зламыснік можа паспяхова запусціць абраны адкрыты тэкст атакі супраць крыптасістэмы шляхам шыфравання верагодных адкрытых тэкстаў пад адкрытым ключом і праверкамі на прадмет таго, роўныя ці яны шифротексту. Крыптасістэмы завецца семантычна бяспечнай ў тым выпадку, калі зламыснік не зможа адрозніць дзве шыфроўкі адзін ад аднаго, нават калі ён ведае адпаведныя тэксты ў расчыненым выглядзе. Як было апісана вышэй, RSA без дапаўненні іншымі сэрвісамі не з'яўляецца семантычна бяспечнай.

Дадатковыя алгарытмы шыфравання і абароны

Каб пазбегнуць вышэйзгаданых праблем, пры практычнай рэалізацыі RSA звычайна ўбудоўваюць некаторую форму структураванага, рандомізірованного запаўнення перад шыфраваннем. Гэта гарантуе, што змест не трапляе ў дыяпазон небяспечных адкрытых тэкстаў і што дадзенае паведамленне не зможа быць раскрыта шляхам выпадковага падбору.

Бяспеку крыптасістэмы RSA і шыфраванне інфармацыі заснаваныя на двух матэматычных задачах: праблемы разлажэння на множнікі вялікіх лікаў і ўласна праблемы RSA. Поўнае раскрыццё шифротекста і ЭЛП ў RSA лічыцца недапушчальным на той здагадцы, што абедзве гэтыя праблемы немагчыма вырашыць у сукупнасці.

Аднак дзякуючы магчымасці аднаўлення простых множнікаў, зламыснік можа вылічыць сакрэтны паказчык з адкрытага ключа, а затым расшыфраваць тэкст з дапамогай стандартнай працэдуры. Нягледзячы на тое што сёння ні адзін існуючы метад для факторизации вялікіх лікаў на класічным кампутары не знойдзены, не было даказана, што ён не існуе.

аўтаматызацыя

Інструмент, званы Yafu, можа быць выкарыстаны для аптымізацыі гэтага працэсу. Аўтаматызацыя ў YAFU ўяўляе сабой сучасную функцыю, якая спалучае алгарытмы факторизации ў інтэлектуальнай і адаптыўнай метадалогіі, якая зводзіць да мінімуму час, каб знайсці фактары адвольных ўваходных лікаў. Большасць рэалізацый алгарытму шматструменныя, што дазваляе Yafu ў поўнай меры выкарыстаць мульты- або шмат шмат'ядравыя працэсары (у тым ліку SNFS, SIQS і ECM). Перш за ўсё, гэта кіраваны інструмент каманднага радка. Час, затрачаны на пошук фактару шыфравання з выкарыстаннем Yafu на звычайным кампутары, можа быць паменшана да 103.1746 секунд. Інструмент вырабляе апрацоўку бінарных файлаў ёмістасцю 320 біт або больш. Гэта вельмі складанае праграмнае забеспячэнне, якое патрабуе пэўнага колькасці тэхнічных навыкаў для ўстаноўкі і настройкі. Такім чынам, RSA-шыфраванне C можа апынуцца уразлівым.

Спробы ўзлому ў найноўшы час

У 2009 годзе Бенджамін Мудзі з дапамогай бітавага ключа RSA-512 працаваў над расшыфроўкай криптотекста на працягу 73 дзён, выкарыстоўваючы толькі агульнавядомае праграмнае забеспячэнне (GGNFS) і сярэднестатыстычны настольны кампутар (двух'ядравы Athlon64 пры 1900 Мгц). Як паказаў дадзены вопыт, спатрэбілася крыху менш за 5 гігабайт дыска і каля 2,5 гігабайт аператыўнай памяці для працэсу «прасейвання».

Па стане на 2010 год, самы вялікі факторизованный нумар RSA быў 768 біт даўжынёй (232 дзесятковыя лічбы, або RSA-768). Яго раскрыццё доўжылася два гады на некалькіх сотнях кампутараў адначасова.

На практыцы ж ключы RSA маюць вялікую даўжыню - як правіла, ад 1024 да 4096 біт. Некаторыя эксперты лічаць, што 1024-бітныя ключы могуць стаць ненадзейнымі ў найбліжэйшай будучыні або нават ужо могуць быць ўзламаныя дастаткова добра фінансуюцца атакуючым. Аднак, мала хто стане сцвярджаць, што 4096-бітныя ключы могуць быць таксама раскрыты ў агляднай будучыні.

перспектывы

Таму, як правіла, мяркуецца, што RSA з'яўляецца бяспечным, калі колькасці досыць вялікія. Калі ж асноўная колькасць 300 біт або карацей, шифротекст і ЭЛП можа быць раскладзены на працягу некалькіх гадзін на персанальным кампутары з выкарыстаннем праграмнага забеспячэння, наяўнага ўжо ў вольным доступе. Ключы даўжынёй 512 біт, як было даказана, маглі быць выкрытыя ўжо ў 1999 годзе з выкарыстаннем некалькіх сотняў кампутараў. У нашы дні гэта магчыма на працягу некалькіх тыдняў з выкарыстаннем агульнадаступнага апаратнага забеспячэння. Такім чынам, цалкам магчыма, што ў будущембудет лёгка раскрывацца RSA-шыфраванне на пальцах, і сістэма стане безнадзейна састарэлай.

Афіцыйна ў 2003 годзе была пастаўлена пад сумнеў бяспека 1024-бітных ключоў. У цяперашні час рэкамендуецца мець даўжыню не менш 2048 біт.