RSA криптиране. Описание и реализация на алгоритъма RSA

RSA криптиране е един от първите практически публично-ключовите криптосистеми, че се използва широко за сигурно предаване на данни. Основната му разлика от подобни услуги е, че кодът за шифроване е отворен и се различава от ключа за разшифроване, която се пази в тайна. Технологията на RSA , тази асиметрия се основава на практическото затруднение за факторинг възпроизвеждането на две големи прости числа (проблемът с факторинг).

История на създаване

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

RSA потребител създава и след това публикува публичния ключ на базата на две големи прости числа заедно с помощен стойност. Простите числа трябва да се пази в тайна. Всеки може да използва публичния ключ за криптиране на съобщение, но ако той е достатъчно голям, а след това само някой, който разбира от простите числа могат да разчетат посланието. RSA криптиране разкриване е известен като основният проблем днес е отворена дискусия за това как надежден механизъм.

RSA алгоритъм е сравнително бавен, поради което тя не е най-широко се използва за директно шифроване на потребителя. В повечето случаи този метод се използва за предаване на споделен ключ криптиран за ключ за симетрично криптиране, което от своя страна може да извършва операции насипно криптиране и декриптиране на много по-висока скорост.

Когато имаше криптосистема в сегашния си вид?

Идеята за асиметричен криптографски ключ дължи на Diffie и Hellman, който публикува концепцията през 1976 г., за въвеждане на цифрови подписи, и се опитва да приложи теорията на числата. Тяхното формулиране използва споделена таен ключ, генериран от определен брой степенуване по модул просто число. Въпреки това, те са напуснали отвори въпроса за реализация на тази функция, тъй като принципите на факторинг не е добре разбран по това време.

Rivest, Ади Шамир и Adleman в Масачузетския технологичен институт са направили няколко опита през годините, за да създадете еднопосочна функция, която е трудно да се декодира. Rivest и Шамир (като компютърни специалисти) са предложили много потенциални функции, докато Adleman (като математика) за търсене на "слабите места" на алгоритъма. Те използват много подходи и в крайна сметка се развива окончателно система, сега известна като RSA през април 1977 г..

Електронен подпис и публичния ключ

Електронен подпис или електронен подпис, е неразделна част от видовете електронни документи. Тя се формира в определен криптографски данни промени. С възможно този атрибут, за да проверите целостта на документа, на нейната поверителност, както и да се определи кой е собственикът. В действителност, алтернатива на обикновен стандартен подпис.

Това криптосистема (RSA шифроване) предлага публичния ключ, за разлика от симетричен. Нейната основна операция е, че се използват два различни ключа - затворен (криптирана) и на открито. Първият се използва за генериране на електронен подпис и след това да бъде в състояние да разшифровате текста. Второ - за действителната криптиране и електронния подпис.

Използването на подписи, за да разбере по-добре RSA криптиране, пример за което може да се намали като нормална тайна "е затворен от любопитни очи" на документа.

Каква е алгоритъм?

RSA алгоритъм се състои от четири стъпки: ключов поколение, разпределение, криптиране и декриптиране. Както вече споменахме, RSA криптиране включва публичен ключ и частен ключ. Открит може да бъде известно на всички и се използва за криптиране на съобщения. Същността му се състои в това, че съобщенията шифровани с публичния ключ може да бъде разшифрован само в един определен период от време с помощта на таен ключ.

От съображения за безопасност, числата да бъдат избрани на случаен принцип и да са еднакви по размер, но се различават по дължина с няколко номера, за да факторинг по-трудно. Същото същия номер могат да бъдат ефективно намери при един тест в своята простота, така че криптирането на информация задължително трябва да бъде сложно.

Публичният ключ се състои от модул и Публичен степенен. Вътрешно тяло и се състои от самостоятелна фигура, която трябва да се пази в тайна.

RSA криптиране на файлове и слаби страни

Въпреки това, има няколко прости хакерски механизми RSA. Когато криптиране с ниски и малки стойности на кодови номера могат лесно да се отвори, ако мотика корен ciphertext над целите числа.

Тъй като RSA криптиране е детерминиран алгоритъм (т.е. не е случаен компонент), атакуващият може успешно стартиране на избран текст отворен атаката срещу криптосистема чрез криптиране вероятно plaintexts под публичния ключ и проверки за това дали те са равни ciphertext. Семантично сигурна криптосистема се нарича в случай, че нападателят не може да се прави разлика между двете криптиране един от друг, дори и ако той знае съответните текстове в разширена форма. Както е описано по-горе, RSA други услуги без подложка не е семантично сигурни.

Допълнителни алгоритми за криптиране и защита

За да се избегне по-горе проблеми, в практическото изпълнение на RSA обикновено се поставя в някаква форма на структуриран, рандомизирано пълнене преди криптиране. Това гарантира, че съдържанието не попада в обхвата на несигурните plaintexts и че това съобщение не може да бъде решен чрез случаен подбор.

Сигурност RSA криптосистема и криптиране на базата на две математически задачи: проблемът за факторинг голям брой и действителния RSA проблема. Пълното разкриване на ciphertext и подписа в RSA се смята за недопустимо да се предположи, че и двете от тези проблеми не могат да бъдат решени заедно.

Въпреки това, с възможност да се възстанови основните фактори, атакуващият може да се изчисли тайна експонентата на публичния ключ и декриптира текст чрез стандартната процедура. Въпреки факта, че днес не съществува метод за факторинг големи числа на класически компютър не може да се намери, че не е доказано, че той не съществува.

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

Инструментът, наричан YAFU, може да се използва за оптимизиране на процеса. Автоматизация в YAFU е разширена функция, която съчетава множители алгоритми в интелектуалната и адаптивна методика, която намалява времето за намиране на факторите на произволни въвеждане на числа. Повечето реализации многонишков алгоритъм позволява YAFU пълно използване на мулти- или много многоядрени процесори (включително SNFS, SIQS и ЕСМ). На първо място, тя се управлява от командния ред инструмент. Времето, прекарано в търсене на криптиране YAFU фактор се използва конвенционален компютър, той може да бъде намален до секунди 103.1746. Инструментът обработва двоичен капацитет от 320 бита или повече. Това е един много сложен софтуер, който изисква определена сума на технически умения за инсталиране и конфигуриране. По този начин, RSA шифроване може да бъде уязвим В.

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

През 2009 г. Bendzhamin Муди използване RSA-512 ключ малко се работи по дешифриране kriptoteksta за 73 дни, като се използват само добре познат софтуер (GGNFS) и средната плот (двуядрен 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 бита.