Jump to content
¯\_( ツ)_/¯
  • TAD GROUP are currently hiring penetration testers. Please read the topic in Career Central subforum.
  • Sponsored Ad
Avatara

Зaщо RSA е слабо защитена

Recommended Posts

ЗАЩО RSA Е СЛАБО ЗАЩИТЕНА

(материал само за експерти)

За да се разбере защо RSA е една от най-слабо защитените криптосистеми е нужно да притежаваме солидна база от фундаментални познания.

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

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

Като начало ще си припомним, че разчета на секретната експонента в RSA се извършва на базата на зависимостта:

s.t=1(mod(Fi(r))

където:

s - открита експонента ( s e просто число спрямо Fi(r) );

Fi(r) - е познатата ни Ойлерова функция, която се изчислява от зависимостта: Fi(r) = (p-1).(q-1)

Идеята при определяне на секретната експонента на RSA e при изчислена стойност на Fi(r) и избрана стойност на s да се намери такова t, за което е изпълнено

(s.t) div (Fi(r)) = 1

Този постулат е най-уязвимото място в RSA, поради следните причини:

  - Функцията на Ойлер е четно число.

  - Множеството на числата формиращи откритата експонента s е множество от нечетни числа.

  - Секретната експонента t винаги е нечетно число.

 - Ако само едно от простите числа p или q завършва на 1 (едно), тогава Ойлеровата функция Fi(r) ще бъде кратна на 10 (десет).

- Ако Ойлеровата функция Fi(r) е кратна на 10 (десет), то тогава s задължително завършва на 7 (седем), а t ще завършва задължително на 3 (три).

- Ако Ойлеровата функция Fi(r) е кратна на 10 (десет), а s завършва на 3 (три), тогава t ще завършва задължително на 7 (седем).

- Ако Ойлеровата функция Fi(r) е кратна на 10 (десет), а s завършва на 9 (девет), тогава t ще завършва задължително на 9 (девет).

- Ако Ойлеровата функция Fi(r) е кратна на 10 (десет), а s завършва на 1 (едно), тогава t ще завършва задължително на 1 (едно).

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

Нека разгледаме следният пример:

 

Пример:

За да докажем нашите твърдения ще извършим "сух пробег", за който дори не е нужно да ползваме компютър.

Избираме следните прости числа:  Pa:= 97 и Qa:= 191.

Изчисляваме Ойлеровата функция.

Rа:= Pa*Qa;

Fa:= Ra-Qa-Pa+1; 

 

Резултатът за Ойлеровата функция е 18240, а откритата експонента ще бъде 14501.

Взаимопростите числа ще имат следния вид:

 

Pr(18240) = 7, 11, 13, 17, 23 ... 

 

От тук не представлява никакъв проблем да изчислим секретната експонента, като използваме формулата, която разгледахме в началото и получаваме 1 4591 умножено по десет на степен 4. 

 

От тук не е трудно да си направим извода, че при RSA в възможно да бъдат прихванати "ключове близнаци", което води до дискредитация на криптосистемата.

Мисля, че не е трудно да се разбере, че причина за това е самият характер на RSA. както вече споменах, колкото по-сложна е една система, толкова по-уязвима е тя на слаби външни и вътрешни въздействия. RSA е типичен пример за това. Ние използвахме само спецификата на простите числа (както знаем те се делят без остатък само на 1 и на самите себе си).

Много е важно да се знае, че тази уязвимост е известно още от 1978 година (хиляда деветстотин седемдесет и осма година).

За първи път тя се анализира в трудовете на Ривест и Шамир. ( за справка виж. "A Method for Obtaining Digital Signaturest and Public Key Cryptosystems",  Cryptosystems // Communications  of the ACM, . 1978. T.21, No2, Pp 120-126)

 

С това днешният ни урок приключи. :D

 

, , , 

 

Искам да се извиня ако в предишните си постове съм бил рязък. Повярвайте не желая да обидя никого. Просто това, за което пиша не се намира в internet в достъпен за ползване вид. Трудно ще го намерите и в печатни издания. Ако ми позволите ще повторя фразата на Марку Канту от забележителният му труд "Indy in depth" - Забравете за всичко, което си мислите, че знаете.

Истината е, че голяма част от това, което знаем е чиста проба дезинформация, която може да бъде опровергана, ако разполагате с нужните теоретични познания и прилежащият инструментариум, както и специфичен практически опит. Много от фондациите (визирам такива като Linux Foundation, Mozilla Foundation и др.) са на държано финансиране с всички произтичащи от това последствия. Само в България има четири структури (извън ДАНС), които се занимават с контрол върху информацията. За Великобритания тези структури са 27, а за САЩ цифрата надхвърля 30, като в тази цифра не включвам АНС. Тяхната задача е да ви манипулират. Самите вие се превръщате в инструмент (и яростни защитници) на нечия политика.  Знам, че това няма да се хареса на мнозина, но за съжаление това е истината. Събитията от последните няколко дни (визирам промените в европейското законодателство) са ярко доказателство за това.

Горещо ви препоръчвам да се запознаете с трудовете на полк.Бил Хагестат, който е един от най-големите експерти в областта на азиатските структури за киберсигурност. Изключителен ерудит, който познава всичко от първа ръка (над 15 години оперативна дейност в Китай и Република Корея).   

 

RED DRAGON 1949

 

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

 

 

Редактирано от Avatara

Сподели публикацията


Адрес на коментара
Сподели в други сайтове

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

 

За целта поне аз непознавам по-добро от YAFU. https://sourceforge.net/projects/yafu/

 

Интересно е и няма много вземане/даване с другаря Ойлер като суха материя. Доста от математиката е направена на автоматични функции.

Малко битови ключове до 128 бита ги издухва за минути. ;)

  • Thanks 1

Сподели публикацията


Адрес на коментара
Сподели в други сайтове

Това, което мога да кажа е, че RSA, DES и др. са податливи на различни по форма и логика криптоатаки защото са създаване при определени ограничения. :$

Аз личино препоръчвам използване на познатата атака с невъзможни деференциали (impossible differentials), с малка модификация.

Добре е да се ползват и трудовете на Исабел Стантън (Isabelle Stanton), но от Бъркли са покрили много старателно всички нейни публикации. За мен тази жена е ненадминат криптоанализатор.

Сподели публикацията


Адрес на коментара
Сподели в други сайтове

Здравей. Ще можеш ли да кажеш нещо така и за DES-a. To се е видяло че трябва да се науча и да си помогна сам. Или пък ако можеш да помогнеш... Ще дам всичко което е нужно.

 

Редактирано от ivanovbg

Сподели публикацията


Адрес на коментара
Сподели в други сайтове

Създайте нов акаунт или се впишете, за да коментирате

За да коментирате, трябва да имате регистрация

Създайте акаунт

Присъединете се към нашата общност. Регистрацията става бързо!

Регистрация на нов акаунт

Вход

Имате акаунт? Впишете се оттук.

Вписване

  • Потребители разглеждащи страницата   0 потребители

    No registered users viewing this page.

×

Important Information

За да посещавате този уебсайт е необходимо да се съгласите с Terms of Use. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.