RSA-енкрипција. Опис и имплементација на RSA алгоритамот

RSA-енкрипција е еден од првите практични јавен клуч cryptosystems која се користи за безбеден пренос на податоци. Нејзината главна разлика од слични услуги е дека клуч за криптирање е отворен и се разликува од клучот за декриптирање, која се чува во тајност. технологија на RSA , оваа асиметрија е врз основа на практични тешкотии на факторинг репродукција на две големи прости броеви (проблемот на факторинг).

Историја на создавањето

RSA Името состои од почетните букви на презимињата Rivest, Самир и Adleman - научниците кои за прв пат јавно опиша овие алгоритми за енкрипција во 1977 година. Klifford Koks, англиски математичар, кој работел за британските разузнавачки служби, прв да се развие еквивалентен систем во 1973 година, но тоа не беше декласифицирани до 1997 година

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

RSA алгоритамот е релативно бавно, поради што не е толку широко се користи директно да го криптирате на корисникот. Во повеќето случаи, овој метод се користи за пренос на споделени клуч шифрирана за клучните симетрична енкрипција, што пак може да врши операции рефус енкрипција и декрипција на многу поголема брзина.

Кога имаше cryptosystem во нејзината сегашна форма?

Идејата на асиметрични криптографски клуч му се припишува на Diffie и Хелман, кој објави концептот во 1976 година, за воведување на дигитални потписи, и се обидува да ја применуваат теоријата на броеви. Нивната формулација користи една заедничка таен клуч генерирана од одреден број на степенување modulo прост број. Сепак, тие го оставија отворено и прашањето за реализација на оваа функција, со оглед на принципите на факторинг не е добро разбрана во тоа време.

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

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

Дигитален потпис или електронски потпис, е составен дел на видови на електронски документ. Таа е формирана во одреден криптографски податоци промени. Со можни овој атрибут да се провери интегритетот на документот, неговата доверливост, како и да се утврди кој го поседува. Всушност, алтернатива на обичните стандарден потпис.

Ова cryptosystem (RSA заштита), нуди јавен клуч, за разлика од симетрична. Неговиот принцип на работа е што се користат две различни клучеви - затворен (шифрирана) и на отворено. Првиот се користи за генерирање на дигитален потпис, а потоа може да ја декриптира текстот. Второ - за вистинските енкрипција и електронски потпис.

Користење на потписи за да се разбере подобро на RSA енкрипција, пример за тоа што може да се намали како нормален тајна "затворена од љубопитните очи," документот.

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

RSA алгоритамот се состои од четири чекори: клучот за производство, дистрибуција, енкрипција и декрипција. Како што веќе рековме, RSA-енкрипција вклучува јавен клуч и приватен клуч. На отворено може да биде позната на сите и се користи за криптирање на пораките. Нејзината суштина лежи во фактот дека пораките криптирана со јавниот клуч може да се декриптира само во даден период на време со користење на таен клуч.

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

Јавниот клуч се состои од модул и јавна експонент. Внатрешна единица и се состои од приватна личност, која треба да се чуваат во тајност.

RSA енкрипција на датотеки и слабости

Сепак, постојат голем број на едноставни хакирање механизми RSA. Кога криптирате со ниска и мали вредности на шифра броеви може лесно да се отвори, ако одбереш корен ciphertext во текот на цели броеви.

Од RSA-енкрипција е детерминистички алгоритам (на пример, нема случајна компонента), напаѓачот може успешно лансирање на избраниот текст отворен напад против cryptosystem од страна на енкрипција, најверојатно plaintexts под јавен клуч и проверка на тоа дали тие се еднакви ciphertext. Семантички безбедна cryptosystem се нарекува во случај дека напаѓачот не може да се прави разлика помеѓу двете енкрипција едни од други, дури и ако тој ја знае релевантни текстови во проширена форма. Како што е опишано погоре, RSA други услуги без баласт не е семантички безбеден.

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

За да се избегне горенаведените проблеми, во практичната имплементација на RSA обично се вметне во некоја форма на структурирани, рандомизирана полнење пред енкрипција. Ова осигурува дека содржината не спаѓаат во рамките на опсегот на несигурни plaintexts, и дека оваа порака не може да се реши по случаен избор.

RSA безбедност cryptosystem и енкрипција врз основа на две математички проблеми: проблемот на факторинг голем број и вистинскиот RSA проблем. Целосно обелоденување на ciphertext и потпис во RSA се смета за неприфатлива врз претпоставката дека и двете од овие проблеми не може да се реши колективно.

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

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

На алатка, наречена Yafu, може да се користи за да се оптимизира процесот. Автоматизација во YAFU е напредна функција која ги комбинира факторизација алгоритми во интелектуална и применлива методологија што ја минимизира времето да се најде на факторите на произволно внесување броеви. Повеќето имплементации многонишкови алгоритам овозможува Yafu целосна употреба на мулти или многу мулти-кор процесори (вклучувајќи SNFS, SIQS и СКМ). Прво на сите, тоа е контролирана од страна на командната линија алатка. Времето поминато во потрага за енкрипција Yafu фактор користење на конвенционален компјутер, тоа може да се намали на 103,1746 секунди. Алатката ги процесира бинарни капацитет од 320 бита или повеќе. Ова е многу комплексен софтвер кој бара одредена количина на технички вештини за да се инсталира и конфигурира. Така, RSA-енкрипција може да се ранливи В.

Хакирањето обиди во последните времиња

Во 2009 година, Bendzhamin Mudi Користење на RSA-512 клучните малку работи на дешифрирање kriptoteksta за 73 дена, со користење само добро познат софтвер (GGNFS) и просечната десктоп (dual-core Athlon64 во 1900 MHz). Како што е прикажано од страна на искуство, потребни нешто помалку од 5 GB простор на дискот и околу 2,5 гигабајти на меморија за процесот на "вовлекува".

Почнувајќи од 2010 година, најголем број беше констатирано RSA 768 парчиња долги (232 децимали, или RSA-768). откривање неговата траеше две години, на неколку стотици компјутери одеднаш.

Во пракса, RSA клучеви се долги - обично 1024-4096 бита. Некои експерти веруваат дека копчињата со 1024 битна може да станат несигурни во блиска иднина, или дури и подолго може да биде разбиена многу добро финансирани од напаѓачите. Сепак, неколку ќе тврдат дека 4096-битна клучеви исто така може да бидат обелоденети во блиска иднина.

изгледите

Затоа, како по правило, се претпоставува дека RSA е безбеден ако броевите се доволно големи. Ако основата број од 300 бита или пократки, а ciphertext дигиталниот потпис може да се распаднат во рок од неколку часа на персонален компјутер со помош на софтвер на располагање веќе во јавниот домен. Клучен должина 512 бита, како што е прикажано, може да се отвори уште во 1999 година, со употреба на неколку стотици компјутери. Денес тоа е можно во неколку недели користење на јавно достапни хардвер. Така, тоа е можно дека во buduschembudet лесно откриени RSA-шифрирана на прсти, а системот ќе стане безнадежно застарени.

Официјално во 2003 година, е доведено во прашање безбедноста на копчињата со 1024 битна. Во моментов, тоа е препорачливо да имаат минимум должина од 2048 битови.