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

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

История на творението

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

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

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

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

Идеята за асиметричен ключ на криптосистемата се приписва на Дифи и Хелман, които публикуват концепцията през 1976 г., като представят цифрови подписи и се опитват да прилагат теорията на числата. Тяхната формулировка използва общ таен ключ, създаден от експроницирането на число модул номер едно. Независимо от това, те оставиха отворен проблема за осъществяването на тази функция, тъй като принципите на факторинга не бяха добре разбрани по онова време.

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

EDS и публичен ключ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Опити за пробив в съвременното време

През 2009 г. Бенджамин Moody използване RSA-512 ключ малко се работи по дешифриране kriptoteksta за 73 дни, като се използват само добре познат софтуер (GGNFS) и средната плот (двуядрен Athlon64 при 1900 MHz). Както се вижда от този опит, процесът на "пресяване" е отнел малко по-малко от 5 гигабайта диск и около 2,5 гигабайта RAM.

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

На практика, обаче, RSA ключове имат дълга дължина - обикновено от 1024 до 4096 бита. Някои експерти смятат, че 1024-битовите ключове могат да станат ненадеждни в близко бъдеще или дори вече да могат да бъдат смазани от добре финансиран нападател. Малцина обаче твърдят, че 4096-битовите ключове също могат да бъдат разкрити в обозримо бъдеще.

перспективи

Следователно, обикновено се приема, че RSA е безопасна, ако числата са достатъчно големи. Ако основният номер е 300 бита или по-кратък, шифрова текстът и цифровият подпис могат да бъдат разградени няколко часа на персонален компютър, като се използва софтуер, който вече е на разположение в публичния домейн. Ключовете с дължина 512 бита, както беше доказано, могат да бъдат отворени през 1999 г., използвайки няколкостотин компютъра. Днес това е възможно в рамките на няколко седмици с използването на публичен хардуер. По този начин е възможно RSA кодирането на пръстите лесно да бъде разкрито в бъдеще и системата ще стане безнадеждно остаряла.

Официално през 2003 г. беше поставена под съмнение сигурността на 1024-битовите ключове. Понастоящем се препоръчва да има дължина от най-малко 2048 бита.