Как найти открытую экспоненту

§ Предисловие

Это алгоритм для шифрования сообщений. Он сложный, трудоемкий и напрямую не используется из-за своей очень невысокой скорости работы. А скорость работы у него невероятно медленная по той причине, что такой алгоритм оперирует гигантскими числами.

§ Открытый и закрытый ключи

Этот алгоритм основан на ключах, один из них открытый, другой — закрытый. Это называется пара ключей (публичный — то есть открытый, и приватный — закрытый). Ключи представляют собой просто очень большое число, то есть реально, просто число, и ничего более, кроме того, что оно гигантское. Для простоты и наглядности ключи у меня будут далее крайне простыми, не превышающие тысячи, поскольку чем больше ключ, тем сложнее его считать.

Теперь представим следующую ситуацию. Есть Алиса, и есть Боб. Они сверхсекретные агенты, и они не могут выдать то, о чем они болтают между собой, и какие сверхсекретные данные передают. Алиса сидит на телефоне, Боб сидит на другом конце телефона а посередине сидит их общий заклятый враг и внимательно слушает, о чем они говорят. Алисе надо передать Бобу очень секретное число, но просто сказать по телефону она ему не может — враг не дремлет.

• Алиса спрашивает у Боба открытый ключ, он ей говорит его по телефону. Ключ становится известен всем, в том числе не только Алисе, но и еще тому, кто сидит и слушает их
• Алиса берет это число (открытый ключ), производит определенные действия над тем числом, что хочет закодировать и отсылает Бобу. Человек посередине эту информацию тоже перехватил.
• Боб же берет закрытый ключ, который он создал вместе с открытым и производя математические действия, расшифровывает число Алисы
• Человек посередине не знает закрытого ключа Боба, а по открытому ключу он не может ничего сделать, потому что расшифровать сообщение можно только с помощью закрытого. Человек с досады кусает свои локти.

Вкратце:

• Боб создает открытый и закрытый ключи (они взаимосвязаны, как Том и Джерри)
• Алиса получает открытый ключ Боба
• Кодирует с его помощью свое число
• Отсылает число по небезопасному каналу связи
• Боб расшифровывает число с помощью закрытого ключа

Более абстрактно:

• Создать открытый и закрытый ключи
• Передать открытый ключ тому, кто будет шифровать
• Зашифровать сообщение с помощью открытого ключа
• Передать зашифрованное сообщение по каналу связи
• Расшифровать сообщение с помощью закрытого ключа

§ Открытый ключ

Задача создать открытый и закрытый ключи — очень сложна, если речь заходит о колоссальных цифрах. Сложность именно в том, как их быстро вычислить. Дело в том, что если взять два гигантских простых числа, и умножить, обратно потом найти эти простые числа уже весьма проблематично. Алгоритм RSA устройчив к взлому исключительно потому, что:

Невозможно быстро и эффективно разложить на множители огромные числа

Вот так вот. Если бы это было реально, то алгоритм RSA утратил бы свою криптостойкость и пришлось бы искать еще какой-нибудь метод. Сейчас рулят эллиптические кривые, но я без понятия как они работают, поэтому расскажу только про RSA.

Шаг 1. Взять два простых числа p и q

Кстати говоря, это далеко не так просто, как кажется. Если речь идет о небольших простых числах, не превышающих к примеру миллиарда, то их нахождение для взломщика не составляет вообще никакого труда. На любом процессоре разложить подобные числа можно за несколько миллисекунд. Однако, как только речь заходит о числах порядка аж 800-1000 десятичных знаков, то тогда никакой сверхмощной видеокарты, да и вообще вычислительной мощности всей планеты не хватит, чтобы даже за 1 год взломать такой код. Единственный, кто может справиться с этой задачей — это алгоритм Шора для квантовых компьютеров, которые сейчас находятся пока что в довольно неразвитой стадии на 2020 год.

Да, простые то числа взять можно, только вот надо чтобы они реально простые были, потому что составные числа работать не будут в RSA вообще. Они будут просто ломать всё. Это значит, что надо бы еще найти простые числа, а это сложная задача. Существуют разные тесты простоты, но в этой статье я их рассматривать не буду.

Получив простые числа p, q, надо их перемножить:

n = pq

И получим n, который будет играть важную роль дальше.

Шаг 2. Вычислить открытую экспоненту e

Перед тем, как вычислить открытую экспоненту, надо рассчитать функцию Эйлера, которая считается для двух простых чисел невероятно простым способом:

phi (n) = (p-1)(q-1)

То есть нужно лишь просто вычесть из p и q по единице и умножить их. Для чего это все? Здесь есть строгое математическое доказательство, приводить которое я тут не буду, потому что сложно и много. Просто надо поверить на слово. А если хочется проверить, то надо смотреть специальную литературу.

Теперь самый ответственный момент. Надо взять наобум число

e

такое, которое бы попало в следующий диапазон:

1 lt e lt phi(n)

И при этом его наибольший общий делитель (НОД) был равен 1, или, другими словами, чтобы ни одно целое число, кроме 1, не смогло поделить

e

и

phi (n)

, то есть, чтобы у этих двух чисел не было наибольшего общего делителя, больше чем 1.

Примеры:

• Числа 5 и 15 имеют НОД(5,15) = 5 — число 15 делится на 5, и 5 делится на 5 без остатка
• НОД(7, 14) = 7 — число 7 делится на 7, и 14 делится на 7 тоже
• НОД(12, 15) = 3 — число 12 делится на 3, число 15 делится на 3
• НОД(9, 11) = 1 — вот это в самый раз, ни одно число не делится, кроме как на 1

Шаг 3. Открытый ключ

Теперь появились все данные, чтобы найти открытый ключ, который представлен как пара {e, n}. Теперь перейду к практической части вычисления открытого ключа.

• Берется (для примера) p=47, q=31, оба числа простые
• Получается n = pq = 47*31 = 1457 — это число часть как открытого, так и закрытого ключа
• Вычисляем
  phi (n) = (p-1)(q-1)

  = (47-1)(31-1) = 1380

• Теперь, надо взять такое
  e

  , чтобы НОД(
  e

  ,
  phi (n)

  ) = 1, берем число e=257 (для примера), проверятся НОД(257, 1380) = 1, все верно

Открытый ключ {e, n} равен {257, 1457}.

§ Закрытый ключ

Теперь задача в том, чтобы сформировать закрытый ключ на числах p, q. Как я и говорил ранее, закрытый ключ нужен, чтобы расшифровать то сообщение, которое было зашифровано с помощью открытого ключа. Закрытый ключ базируется на тех же самых p,q, и потому у него будет точно та же компонента n, что и у открытого ключа. Закрытый же ключ будет представлен как пара {d, n}, где d — закрытая компонента, n = pq.

Существует формула для поиска закрытого ключа:

d = e^{-1} mod phi (n)

Но, ее понять сложно без подготовки. Лучше ее переписать в следующем виде:

(de) mod phi(n) = 1

И что это значит? Это значит, что надо найти

d

такое, что при умножении на

e

и потом после деления на

phi(n)

получился остаток 1.

Вот возьмем простой пример, допустим

e

= 7,

phi(n)

= 60:

7d mod 60 = 1

Теперь надо подобрать такое d, при котором остаток от деления на 60 был бы 1. Пробуем:

• d = 1 — 7*1 mod 60 = 7, не подходит
• d = 9 — 7*9 mod 60 = 63 mod 60 = 3, не подходит
• d = 23 — 23*7 mod 60 = 161 mod 60 = 41, не подходит
• d = 43 — 43*7 mod 60 = 301 mod 60 = 1, подошло

Получается, что для числа

e

= 7 число

d

= 43. Таким образом, мы смогли найти закрытый ключ {43, 77}, при этом открытый ключ был {7, 77}.

Поиск закрытого ключа происходит с помощью расширенного алгоритма Евклида, объяснение которого здесь тоже не приводится.

§ Пример шифрования и дешифрования

А теперь самое главное: как шифровать и дешифровать сообщение.

Шифрование числа происходит по следующей формуле:

b = a^e mod n

Дешифрование происходит так:

a = b^d mod n

И это весь алгоритм. Стоит только учесть, что так как числа

d

и

e

огромны, то не так просто будет возвести такие числа в такую вот степень.

Для начала, составим открытый и закрытый ключи. Генерация открытого ключа происходит по такому алгоритму:

• Возьмем p=11, q=23, n = pq = 253
• Число Эйлера
  phi(n) = (11-1)(13-1) = 220

• Выберем открытую экспоненту
  e

  = 17, ибо НОД(17, 220) = 1

Итак, открытый ключ будет равен {17, 253}. Теперь надо найти закрытый ключ, используя вот это уравнение:

17d mod 253 = 1

Пока что находим перебором, но можно искать с помощью расширенного алгоритма НОД. Но в данном случае просто перебором, про НОД позже расскажу.

Путем подбора (я просто программой перебрал числа d=1..253),

d

оказалось равным 134. Проверим, 134*17 mod 253 = 1, все подошло. Закрытый ключ равен {134, 253}.

Теперь надо попробовать что-нибудь зашифровать и расшифровать. Поскольку число n у нас 253, то зашифровать можно сообщение только от 0 до 252 включительно, ибо если попытаться использовать 253, то такое сообщение просто превратится в 0 при расшифровке. Это не проблема, но надо учитывать, что шифровать число более чем n нельзя.

Выбираем a=110, теперь шифруем с помощью открытого ключа.

b = 110^{17} mod 253 = 77

У нас получился b=77. Даже зная n=253, нельзя получить обратно 110, потому что нужен для этого закрытый ключ. Однако, если разложить 253 на простые множители p, q, то тогда можно найти и закрытый ключ d. Однако, при большом значении n это сделать невозможно. Расшифровка с помощью закрытого ключа делается так:

a = 77^{134} mod 253 = 110

Что и требовалось сделать. Все работает корректно. Процедура для быстрого возведения в степень приведена в этой статье.

§ Нахождение закрытого ключа с помощью расширенного НОД

Существуют способы, при которых можно найти d, зная e, не используя при этом перебор, и этот способ — расширенный алгоритм Евклида, о котором я уже писал ранее в другой статье. То есть как находить коэффициенты к расширенному алгоритму, об этом здесь я говорить не стану, а только опишу самую суть того, почему надо использовать именно этот НОД.

Поскольку числа

e

и

phi(n)

взаимно простые, но их НОД будет равен 1:

НОД(

e

,

phi(n)

) =

xe + yphi(n)

= 1

Здесь значения x, y получаются из решения расширенного алгоритма НОД. Теперь применим модуль к левой и правой части:

xe mod phi(n) + yphi(n) mod phi(n) = 1 mod phi(n)

Поскольку любой модуль от 1 будет 1, а модуль самого от себя,

yphi(n) mod phi(n)

будет равняться 0, то уравнение сокращается:

xe mod phi(n) = 1

Тут сразу же видно, что x — это как раз тот самый искомый d. В общем-то и всё.

§ Программный код

Получение значений расширенного НОД:

int NOD(int a, int b, int & x, int & y) {

    int x1, y1, d;
    if (a == 0) { x = 0; y = 1; return b; }
    d = NOD(b % a, a, x1, y1);
    x = y1 - (int)(b / a) * x1;
    y = x1;
    return d;
}

Быстрое возведение в степень:

unsigned long fpow(unsigned long a, unsigned long b, unsigned long m) {

    int id;
    unsigned long r = 1;
    for (id = 31; id >= 0; id--) {
        if (b & (1 << id)) r = (r * a) % m;
        if (id) r = (r * r) % m;
    }
    return r;
}

22 ноя, 2020

© 2007-2023 Мыш кушает на дому

Кодирование и Шифрование

В наш век интернет-технологий, когда мы доверяем все свои данные интернет-сервисам, нужно знать и понимать, как они их хранят и обрабатывают.

Но зачем это вообще нужно знать? Чтобы попросту не попасть в ситуацию, когда ваши личные данные, пароли от аккаунтов или банковских карт окажутся в руках мошенников. Как говорится: «Доверяй, но проверяй»

Важные аспекты в хранении данных, будь то на внешних серверах или домашнем компьютере, – это прежде всего кодирования и шифрование. Но чем они отличаются друг от друга? Давайте разбираться!

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

Определения и различия

Кодирование – процесс преобразования доступной нам информации в информацию понятную компьютерную.

Шифрование – процесс изменения информации таким образом, чтобы её смогли получить только нужные пользователи.

Шифрование применялось и задолго до создания компьютеров и информатики как таковой. Но зачем? Цели её применения можно было понять из определения, но я опишу их ещё раз более подробно. Главные цели шифрования это:

• конфиденциальность – данные скрыты от посторонних

• целостность – предотвращение изменения информации

• идентифицируемость – возможность определить отправителя данных и невозможность их отправки без отправителя

Оценить стойкость шифра можно с помощью криптографической стойкости.

Криптографическая стойкость – это свойство шифра противостоять криптоанализу, изучению и дешифровки шифра.

Криптостойкость шифра делится на две основные системы: абсолютно стойкие системы и достаточно стойкие системы.

Абсолютно стойкие системы – системы не подверженные криптоанализу. Основные критерии абсолютно стойких систем:

• Ключи должны генерироваться для каждого сообщения отдельно

• Генерация ключей независима

• Длина ключа должна быть не меньше длины сообщения

К сожалению, такие системы не удобны в своём использовании: появляется передача излишней информации, которая требует мощных и сложных устройств. Поэтому на деле применяются достаточно стойкие системы.

Достаточно стойкие системы – системы не могут обеспечить полную защиту данных, но гораздо удобнее абсолютно стойких. Надежность таких систем зависит от возможностей крипто аналитика:

• Количества перехваченных сообщений

• Времени и вычислительных способностей

А также от вычислительной сложности шифра.

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

История шифрования

Шифрование берет своё начало ещё из древних времен. Примерно 1300 лет до нашей эры был создан один из первых методов шифрования – Атбаш. Принцип шифрования заключается в простой подставке символов по формуле:, где:

• n – количество символов в алфавите

• i – порядковый номер символа.

Шифр получил своё название в честь первой, последней, второй и предпоследней буквы Еврейского алфавита — «алеф», «тав», «бет», «шин». Такой шифр имеет низку криптографическую стойкость, потому как алгоритм шифрования довольно прост

С тех самых пор шифрование активно развивалось вместе с развитием нашей цивилизации

Хоть шифры и менялись, но их принцип нет – для расшифровки сообщения требуется ключ. В случае с Абашем ключом может считать последовательность порядковых номеров исходных символов, но этот ключ ещё надо как-то передать. Методы шифрования, которые используются сейчас, научились-таки передавать ключи по открытым и незащищённым каналам связи. Казалось бы, передача ключей шифрования по обычным каналам — это добровольное жертвование своими данными, но не всё так просто. Разберём это на примере популярного алгоритма шифрования «RSA», разработанного в 1977 году.

Первым делом выбирается два случайный простых числа, которые перемножаются друг на друга – именно это и есть открытый ключ.

К слову: Простые числа — это те числа, которые могут делиться без остатка либо на 1, либо на себя.

Длина таких чисел может быть абсолютно любая. К примеру, возьмем два простых числа 223 и 13. Их произведение 2899 – будет являться открытым ключом, который мы и будем передавать по открытому каналу связи. Далее нам необходимо вычислить функцию «Эйлера» для произведения этих чисел.

Функция Эйлера – количество натуральных чисел, меньших чем само число и, которые будут являть взаимно простыми числами с самим числом.

Возможно, звучит непонятно, но давайте это разберем на небольшом примере:

 φ (26) [фи от двадцати шести] = какому-то числу чисел, которое всегда будет меньше 26, а сами числа должны иметь только один общий делитель единицу с 26.

Давайте считать:

1 – подходит всегда, идем дальше;

2 – делится и на 2, и на 1, как и число 26, — не подходит;

3 – делится и на 3, и на 1, а вот число 26 не делится на 3, — подходит;

4 – имеет общие делители 2 и 1 с 26 — не подходит;

5 – только на 1 — подходит;

 6 – на 2 и 1 — не подходит;

7 – только на 1 – подходит;

и так далее до 25.

Общее количество таких чисел будет равно 12. А найти это число можно по формуле: φ(n*k) = (n-1)(k-1) в нашем случае 26 можно представить как 2 * 13, тогда получим φ(26) = φ(2 * 13) = (2-1)*(13-1) = 1 * 12 = 12

Теперь, когда мы знаем, что такое функция Эйлера и умеем её вычислять найдем её для нашего открытого ключа – φ(2899) = φ(223 * 13) =(223 – 1)*(13-1) = 222 * 12 = 2664

После чего нам нужно найти открытую экспоненту. Не пугайтесь, тут будет гораздо проще чем с функцией «Эйлера».

Открытая экспонента – это любое простое число, которое не делится на функцию Эйлера. Для примера возьмем 13. 13 не делится нацело на число 2664. Вообще открытую экспоненту лучше выбирать по возрастанию простым перебором, а не просто брать случайную. Так для нашего примера разумнее было бы взять число 5, но давайте рассмотрим на примере 13

Следующий шаг – закрытая экспонента. Вычисляется она банальным перебором по этому равенству: d * e mod φ(n) = 1, где

• φ(n) — функция Эйлера

• e – открытая экспонента

• mod – остаток отделения

а число d, которое и является закрытой экспонентой, мы должны подобрать перебором, либо попытаться выразить через формулу d = ceil(φ(n) / e), где ceil – округление в большую сторону.

В обоих случаях у нас получится число 205

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

Теперь этому человеку нужно отправить нам сообщение, для простоты предположим, что это какое-то число, например: 92. Для этого ему нужно отправить нам остаток от деления 92 в степени открытой экспоненты на открытый ключ – T ^ e mod n, где

• T – шифруемый текст

• e – открытая экспонента

• n – открытый ключ

• mod – остаток от деления

92 ^ 13 mod 2899 = 235. Именно число 235 он нам и отправит.

Предположим, что и в этот раз сообщение перехватили, но нам оно всё так же дошло

Для расшифровки сообщения нам необходимо зашифрованное сообщение возвести в степень закрытой экспонентой и вычислить остаток от деления на открытый ключ – C ^ d mod n, где

• С – зашифрованный текст

• d – закрытая экспонента

• n – открытый ключ

• mod – остаток от деления

235 ^ 205 mod 2899 = 92.

Вуаля, и мы имеет исходное число. Но, что насчет перехваченных сообщений? У злоумышленника есть сообщение, ключ и экспонента, но как мы помни для дешифровки ему ещё нужна секретная экспонента, она же секретный ключ, но для того, чтобы вычислить её, ему придется разложить исходный ключ 2899 на множители, а сделать это не так уж и просто, особенно когда вместо двух чисел 223 и 13, будут использовать числа длиной несколько десятков символов

Но ничто в мире не идеально, в том числе и этот метод.

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

Второй недостаток – так же связан с генерацией ключа. Как мы с вами помним: «ключи должны генерировать независимо от каких-либо факторов», но именно это правило нарушается, когда мы пытается сгенерировать строго простые числа.

Третий недостаток – подбор и перебор чисел для экспонент.

Четвертый – длина ключей. Чем больше длина, тем медленнее идет процесс декодирования, поэтому разработчики пытаются использовать наименьшие по длиннее ключи и экспоненты. Даже я акцентировал на это внимание, когда говорил, что лучше взять число 5, вместо 13 для открытой экспоненты. Именно из-за этого и происходит большая часть взломов и утечек данных

Но не стоит печалиться, ведь как я и говорил: криптография и шифрование развивается вместе с развитием цивилизации. Поэтому довольно скоро все мы будем шифровать свои данные с помощью Квантового шифрование.

Этот метод основывается на принципе квантовой суперпозиции – элементарная частица может сразу находится в нескольких положениях, иметь разную энергию или разное направление вращения одновременно. По такому принципу и работает передача ключей шифрования по протоколу BB-84.

Есть оптоволокно, по которому передаются единичные фотоны света. Мы, как отправитель может сгенерировать абсолютно любой двоичный ключ, по тому же принципу квантовой супер позиции, ну или использовать обычные генераторы псевдослучайных чисел. Допустим мы хотим передать ключ 101001011. Для этого нам нужно принять за обозначение какое положение фотона соответствует единице, а какое нулю. Представим, что вертикальное положение – это 1, а горизонтальное – 0. Если оставить все так, то от передачи ключей таким образом не будет никакого смысла, ведь тогда злоумышленник всегда сможет измерить фотон, получить его значение, создать и отправить точно такой же обратно человеку, которому мы хоти передать ключ. Поэтому были введены ещё два положение – диагональные. Предоставим вертикальную волну, или же значение 1 и отклоним её на 45 градусов влево. Это будет вторая единица. Вернемся обратно и отклоним на 45 градусов вправо – это будет второй 0.

Вернемся к нашему ключу 101001011. Мы случайным образом выбираем направление – обычное или диагональное. Для удобства присвоим обычному номер 1, а диагональному 2.

Давайте отправим ключ – 1(1), 0(2), 1(1), 0(1), 0(1), 1(2), 0(2), 1(1), 1(2). Теперь человеку, которому мы отправляем ключ, нужно точно так же, совершенно случайно, выбрать случайное направление.

Допустим он выбрал направления: 221111212. Поскольку есть всего 2 плоскости отправки: 1 и 2, они же называются: канонический и диагональный базис, то шанс того, что он выбрал правильные направления 50%.

Если он угадал базис – он получил верное значение, если нет – неверное. Учитывая его направления, он получил: 001000011. Теперь нужно отсеять неправильные значения: можно сделать это обменом базисов по любому, даже не защищенному, каналу связи. После этого у нас обоих останется ключ: 0100011. Теперь с помощью его мы можем передавать и кодировать сообщения по обычному методу шифрования.

А что, если кто-то перехватит отправку кода? Тогда ему придется точно также подбирать случайным образом базисы, что добавит ещё 25% погрешности при получении кода человеку, которому мы изначально и отправили его. Чтобы проверить это, после отсеивания мы, как отправитель, должны проверить сколько процентов кода оказалось не верным. В нашем 1 случае это (9 – 7)/9 * 100% = 22%, если это число будет больше 50%, то мы начнем повторную отправку ключей, до тех пор, пока погрешность не будет меньше 50%

Заключение

Причитав и разобрав эту статью, мы с вами узнали, чем отличается кодирование от шифрования, их историю с будущим, узнали каким должен быть идеальный шифр и немного поговорили про крипто анализ. Уже с этими знаниями, которые были предоставлены в этой статье, можно спокойно идти и делать какую-нибудь систему авторизации или пытаться взломать какой-то сайт, главное не перебарщивать.

Список литературы и материалов:

• «RSA» и квантовое шифрование

• Квантовое шифрование

• Алгоритм шифрования: «RSA»

• Алгоритм шифрования: «RSA»

• Шифрование обобщенно

• Что такое кодирование

• Первые в мире шифры

• Что такое экспонента

• Что такое функция «Эйлера»

RSA: найти открытую экспоненту, зная закрытую и модуль

Такой вот этюд по алгоритму RSA: http://ru.wikipedia.org/wiki/RSA

Есть закрытая экспонента и модуль. Обычно открытую экспоненту принимают равной 65537, но в нашем случае использовали большое число. Можем ли как-нибудь найти эту открытую экспоненту?

Re: RSA: найти открытую экспоненту, зная закрытую и модуль

Здравствуйте, Аноним, Вы писали:

А>Такой вот этюд по алгоритму RSA: http://ru.wikipedia.org/wiki/RSA

А>Есть закрытая экспонента и модуль. Обычно открытую экспоненту принимают равной 65537, но в нашем случае использовали большое число. Можем ли как-нибудь найти эту открытую экспоненту?

Насколько я помню, алгоритм RSA с точки зрения экспонент симметричен, т.е. если умышленно сделать открытую экспоненту большой, то сложность её подбора будет эквивалентна сложности подбора закрытой экспоненты (по открытой экспоненте и модулю).

Но всё это при условии, что нам неизвестны вспомогательные числа, которые обычно добавляются в состав закрытого ключа для ускорения вычислений.

Re[2]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, andy1618, Вы писали:

A>Насколько я помню, алгоритм RSA с точки зрения экспонент симметричен, т.е. если умышленно сделать открытую экспоненту большой, то сложность её подбора будет эквивалентна сложности подбора закрытой экспоненты (по открытой экспоненте и модулю).

А не получится ли так, что если e выбрать большим, то d (после вычислений) окажется маленьким?

Re: RSA: найти открытую экспоненту, зная закрытую и модуль

Здравствуйте, Аноним, Вы писали:

А>Есть закрытая экспонента и модуль. Обычно открытую экспоненту принимают равной 65537, но в нашем случае использовали большое число. Можем ли как-нибудь найти эту открытую экспоненту?

То есть, ты знаешь pq и d, и длина d почти равна длине pq?

По этому поводу у Шнейера видел ссылку на одну работу по этой теме:

M.J. Wiener, “Cryptanalysis of Short RSA Secret Exponents,” IEEE Transactions on Information Theory, v. 36, n. 3, May 1990, pp. 553–558.

Впрочем, самой работы еще не видел. Если найдешь, плз выложи здесь ссылку.

Re[2]: RSA: найти открытую экспоненту, зная закрытую и модул

Re: RSA: найти открытую экспоненту, зная закрытую и модуль

Здравствуйте, Аноним, Вы писали:

А>Такой вот этюд по алгоритму RSA: http://ru.wikipedia.org/wiki/RSA
А>Есть закрытая экспонента и модуль. Обычно открытую экспоненту принимают равной 65537, но в нашем случае использовали большое число. Можем ли как-нибудь найти эту открытую экспоненту?

Ну вообще она на то и открытая, чтобы ее не надо было искать. Или у вас вместо D свободно распространяется E?
В любом случае сообщите N (Public modulus = P * Q) и D или E.

Re[2]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, MozgC, Вы писали:

MC>Или у вас вместо D свободно распространяется E?

Ага.

MC>В любом случае сообщите N (Public modulus = P * Q) и D или E.

То что по n и e невозможно найти d — в этом я не сомневаюсь. А вот возможно ли найти e, зная n и d?

Длина m 128 байт, длина d 127 байт. Можно ли по этим данным сказать какой будет максимум длина e в байтах? Или она может быть любой?

Re[3]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

MC>>Или у вас вместо D свободно распространяется E?
А>Ага.

Ну т.е. я имел в виду наоборот, что вместо E свободно распространяется D, так?

Re[3]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

A>А вот возможно ли найти e, зная n и d?

Можно, сообщите значения N и D.

Re[4]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, MozgC, Вы писали:

MC>Ну т.е. я имел в виду наоборот, что вместо E свободно распространяется D, так?

Да. d есть и n есть. А вот e нету. Длина d и n 128 и 127 байт соответственно. Что можно сказать о e?

Нечетные от 1 до 65537 перебрал — ни одно не подходит. Каков его размер максимум может быть?

Re[4]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, MozgC, Вы писали:

MC>Можно, сообщите значения N и D.

А как хоть примерно это сделать? Можно не сообщать, а то они вроде как секретные и приватные

Re[5]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>А как хоть примерно это сделать? Можно не сообщать, а то они вроде как секретные и приватные

Это же вроде этюд?
И они не секретные и приватные. Секретная у вас E получилась.
К тому же вы под анонином, так что навряд ли знание ваших N и D кому-то что-то даст даже при желании.

Re[6]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, MozgC, Вы писали:

MC>Это же вроде этюд?
MC>И они не секретные и приватные. Секретная у вас E получилась.
MC>К тому же вы под анонином, так что навряд ли знание ваших N и D кому-то что-то даст даже при желании.

Уговорили

Модуль: 056EF0D6CBD4B0E1D6EC4673F553DDECC2EE9491A46C6209A6A48CC5994D7BBE761EF09D657B423C447762B55DC9E46663726ACFD7B9BE6702D04CF3FEC29EFF1F55
Закрытая экспонента: BFBB28AAFE58BDCE1090E367D29BEE6C0CE5A1E69DE08FA05FCC2E1DB3E9A4BD1B59C057880BBF29B113A7FEC237CFB0221B59296C02AEEDA80F8C9EBD0836B27D

Сначала записан старший байт, потом младший. Т.е. на примере модуля — 05 — самый старший байт, а 55 — самый младший. Если нужно в обратной записи, то вот (сначала младший байт, потом старший):

Модуль: 551FFF9EC2FEF34CD00267BEB9D7CF6A726366E4C95DB56277443C427B659DF01E76BE7B4D99C58CA4A609626CA49194EEC2ECDD53F57346ECD6E1B0D4CBD6F06E05
Закрытая экспонента: 7DB23608BD9E8C0FA8EDAE026C29591B22B0CF37C2FEA713B129BF0B8857C0591BBDA4E9B31D2ECC5FA08FE09DE6A1E50C6CEE9BD267E39010CEBD58FEAA28BBBF

Сможете назвать открытую экспоненту?

Re[7]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>Модуль: 056EF0D6CBD4B0E1D6EC4673F553DDECC2EE9491A46C6209A6A48CC5994D7BBE761EF09D657B423C447762B55DC9E46663726ACFD7B9BE6702D04CF3FEC29EFF1F55
А>Сможете назвать открытую экспоненту?

Нет, тут модуль 523 бита, такое факторизовать можно только распределенно, т.е. на одном обычном компе не справиться.

Re[8]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, MozgC, Вы писали:

MC>Нет, тут модуль 523 бита, такое факторизовать можно только распределенно, т.е. на одном обычном компе не справиться.

Ну понятно что факторизация не возможна. Если бы числа можно было быстро раскладывать на множители — то и RSA никто бы не использовал.

А вот можно ли решить без применения факторизации? Насколько я понимаю e не должно быть очень длинным, т.е. порядка 4 байт?

Re[9]: RSA: найти открытую экспоненту, зная закрытую и модул

Re[9]: RSA: найти открытую экспоненту, зная закрытую и модул

Re: RSA: найти открытую экспоненту, зная закрытую и модуль

Здравствуйте, Аноним, Вы писали:

А>Такой вот этюд по алгоритму RSA: http://ru.wikipedia.org/wiki/RSA

А>Есть закрытая экспонента и модуль. Обычно открытую экспоненту принимают равной 65537, но в нашем случае использовали большое число. Можем ли как-нибудь найти эту открытую экспоненту?

Если есть только модуль (n), но нет его составляющих (p, q) или других требуемых по PKCS#1 — то задача вырождается в то же самое, что и при наличии только открытого ключа. Остаётся надеяться, что e таки было небольшим.

Re[2]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, netch80, Вы писали:

N>Если есть только модуль (n), но нет его составляющих (p, q) или других требуемых по PKCS#1 — то задача вырождается в то же самое, что и при наличии только открытого ключа. Остаётся надеяться, что e таки было небольшим.

Фишка в том, что если d большое, значит e маленькое. И наоборот — если e большое, то d будет маленьким. Они же связаны!

Только вот кто может сказать каков будет размер e, если d на 1 байт меньше n?

Re[7]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>Сможете назвать открытую экспоненту?
Что-то у тебя с параметрами не то.
Атака Винера именно на твоих параметрах не срабатывает. А должна, т.к. на других параметрах она работает.
Естественно, доказать, что твои параметры кривые я не могу. Можно только проверить.
Вот тебе проверка: Используя свои N и E зашифруй любую строку. Текст и шифртекст выложи сюда.

PS: вот код атаки (pari/gp):

cf(F,n) = {
    a=F[n];
    for(i=1,n-1,a=1/a + F[n-i]);
    return(a);
}

rand_rsa(n,e) = {
    my(p,q);
    p=nextprime(random(2^n));
    q=nextprime(random(2^n));
    return(rsa(p,q,e));
}

RSA=rand_rsa(253,2^90+1)
N=RSA[1]
E=RSA[3]

\N=hex("056EF0D6CBD4B0E1D6EC4673F553DDECC2EE9491A46C6209A6A48CC5994D7BBE761EF09D657B423C447762B55DC9E46663726ACFD7B9BE6702D04CF3FEC29EFF1F55")
\E=hex("BFBB28AAFE58BDCE1090E367D29BEE6C0CE5A1E69DE08FA05FCC2E1DB3E9A4BD1B59C057880BBF29B113A7FEC237CFB0221B59296C02AEEDA80F8C9EBD0836B27D")

RSA=[N,E,0]
M=1234567
C=rsa_enc(RSA,M)

F = contfrac(E/N)
{
    for(i=1,#F,
        a=cf(F,i);
        RSA[3]=denominator(a);
        D=rsa_dec(RSA,C);
        if(M==D,
            printf("found: %d",RSA[3]);
            break;
        );    
    )
}

Re[8]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Естественно, доказать, что твои параметры кривые я не могу. Можно только проверить.
DEA>Вот тебе проверка: Используя свои N и E зашифруй любую строку. Текст и шифртекст выложи сюда.

У меня нету N и E, есть только N и D.

С помощью N и D зашифровал значение 2 (т.е. просто двоичное «10» или десятичное 2):

BB21642279B3DEB587160B31AB2B0786B6118FA36CACE6FA53E3945C239ECCBC472DF183FDC716BBC8592F43A7AB0AEC53C7A471C50395E8650FB218FF4301600803

Обратите внимание: вначале младший байт (т.е. BB) и в самом конце старший.

А что может быть неправильного?

Я нашел эту экспоненту.
Но, всякий труд должен оплачиваться

Подробности шифром.
«181BAD222A8B7594D4CDE3430F89A266346C556603F168EE9400C791D8EC9339443BC7BEE7FD834F4C1F332DA09E7A43BA8C9DF3DDA17FDD03B3729260B0D0DE0FA»
Расшифруй его при помощи N и D, которые у тебя есть. Содержимое сообщения — текстовая строка.
Старшие байты впереди.

Re[3]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, netch80, Вы писали:

N>>Если есть только модуль (n), но нет его составляющих (p, q) или других требуемых по PKCS#1 — то задача вырождается в то же самое, что и при наличии только открытого ключа. Остаётся надеяться, что e таки было небольшим.

А>Фишка в том, что если d большое, значит e маленькое. И наоборот — если e большое, то d будет маленьким. Они же связаны!

Нет такой «фишки». Если бы была, это бы значило, что RSA — не шифр.

А>Только вот кто может сказать каков будет размер e, если d на 1 байт меньше n?

Любой.

Re[4]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, netch80, Вы писали:

N>Нет такой «фишки». Если бы была, это бы значило, что RSA — не шифр.

Как раз есть. Чел выше смог найти эту экспоненту. И это не делает RSA «не шифром». Просто нужно его правильно использовать.

У вас есть какие-нибудь идеи как это было сделано? То-то!

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Я нашел эту экспоненту.
DEA>Но, всякий труд должен оплачиваться

Абсолютно согласен. Только осталось найти дядю, который за весь благой труд согласится заплатить А это не просто.

DEA>Подробности шифром.
DEA>»181BAD222A8B7594D4CDE3430F89A266346C556603F168EE9400C791D8EC9339443BC7BEE7FD834F4C1F332DA09E7A43BA8C9DF3DDA17FDD03B3729260B0D0DE0FA»
DEA>Расшифруй его при помощи N и D, которые у тебя есть. Содержимое сообщения — текстовая строка.
DEA>Старшие байты впереди.

Вы редкий специалист, однако. Я не уверен что удастся сделать на этом даже 1000 у.е.

Вот условия на которых могу сотрудничать. Пока мне нужен ТОЛЬКО 1 бит информации. Если «E» больше 4-х байт — «1», если «E» меньше или равно 4-м байтам «0».

Этот 1 бит информации я хочу получить бесплатно. По сути он мне скажет только смогу ли я на этом что-то заработать.

Если смогу заработать — то готов с вами разделить все 50/50. Если не смогу — то делить будет нечего.

Алгоритм мне нужен будет в любом случае. Но 1 бит информации я бы хотел получить бесплатно.

Если не хотите — думайте сами как на этом заработать (а я сам буду думать как найти E).

Re[5]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>У вас есть какие-нибудь идеи как это было сделано? То-то!
Третий раз повторяю (для очень-очень одаренных Анонимов): Атака Винера. Или в гугле забанили?
Она позволяет не только узнать короткую экспоненту по длинной, но и позволяет полностью вскрыть RSA.
Например, для твоей криптосистемы:
p=1A911A3F……………………………………………C85466AB
q=345B391F………………………………………….265291FF
Код постить не буду. Такая корова нужна самому

ЗЫ. Еще раз убедился, что русскоязычные научные ресурсы полный отстой.
Cсылка на русское описание атаки, которое я давал — кривое дерьмо. То что там описано, будет работать только при g==1, а таких случаев маловато. Поэтому, и первая версия атаки у меня не срабатывала. Чтобы это понять, у меня часа 3 ушло…

Re[6]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Код постить не буду. Такая корова нужна самому

Я вам выше написал условия, на которых могу сотрудничать.

Примерно как найти понял, но все равно у меня отнимет время реализация алгоритма.

Re[5]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, netch80, Вы писали:

N>>Нет такой «фишки». Если бы была, это бы значило, что RSA — не шифр.

А>Как раз есть. Чел выше смог найти эту экспоненту.

То, что есть, не является правилом типа «если d большое, e маленькое, и наоборот».

А> И это не делает RSA «не шифром». Просто нужно его правильно использовать.
А>У вас есть какие-нибудь идеи как это было сделано? То-то!

Что «то-то»? В вашем конкурсе я не собираюсь участвовать независимо от наличия идей, хотя бы потому, что не люблю такие вещи решать с анонимами.

Здравствуйте, 0xDEADBEEF, Вы писали:

А>>Вы редкий специалист, однако. Я не уверен что удастся сделать на этом даже 1000 у.е.
DEA>Расшифровал, аднака

Написал вам личное сообщение.

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Я нашел эту экспоненту.
…
DEA>Подробности шифром.
DEA>»181BAD222A8B7594D4CDE3430F89A266346C556603F168EE9400C791D8EC9339443BC7BEE7FD834F4C1F332DA09E7A43BA8C9DF3DDA17FDD03B3729260B0D0DE0FA»
DEA>Расшифруй его при помощи N и D, которые у тебя есть.

Да, красивое zero-knowledge доказательство, что экспонента действительно найдена!

Re[3]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

A>>Насколько я помню, алгоритм RSA с точки зрения экспонент симметричен, т.е. если умышленно сделать открытую экспоненту большой, то сложность её подбора будет эквивалентна сложности подбора закрытой экспоненты (по открытой экспоненте и модулю).

А>А не получится ли так, что если e выбрать большим, то d (после вычислений) окажется маленьким?

Хороший вопрос! Навскидку мне кажется, что чёткой связи «большое e -> малое d» не будет.
В частности, в русской Википедии есть такой абзац:

По эвристическим оценкам длина секретной экспоненты d, нетривиальным образом зависящей от открытой экспоненты e и модуля n, с большой вероятностью близка к длине n. Поэтому расшифрование данных идёт медленнее чем шифрование, а проверка подписи быстрее чем подписание.

Re[4]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, andy1618, Вы писали:

A>Хороший вопрос! Навскидку мне кажется, что чёткой связи «большое e -> малое d» не будет.

Когда кажется — креститься нада

Если вы не в теме, то зачем колебать воздух?

Я проверил. d вычисляется по e, с помощью расширенного алгоритма Евклида: http://algolist.manual.ru/maths/teornum/nod.php

И там ВСЕГДА получается при большом e маленькое d. Можете проверить.

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Расшифровал, аднака

Вы получаете мои сообщения? Проверьте спам на всякий случай.

Re[5]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>И там ВСЕГДА получается при большом e маленькое d. Можете проверить.

А хотя нет, погорячился. Не всегда получаются маленькие d при больших e. Извиняюсь.

Re[14]: Я ЕЕ ТОЖЕ ЗНАЮ!!!

Здравствуйте, 0xDEADBEEF, Вы писали:

Вот вам:

045548C0EBA23A0E43A5BF02B45C7802B043AC071B18A89D1527234200F440AD11CECD152220117646CD97A82B34996B971013718963BB5289EEF4DAD96BD3937638

Re[15]: Я ЕЕ ТОЖЕ ЗНАЮ!!!

Здравствуйте, Аноним, Вы писали:

А>045548C0EBA23A0E43A5BF02B45C7802B043AC071B18A89D1527234200F440AD11CECD152220117646CD97A82B34996B971013718963BB5289EEF4DAD96BD3937638
Молодец. Поздравляю.
А если не секрет, как вскрыл?

ЗЫ. А атака Винера меня всерьез заинтересовала. Нарыл литературы и читаю. Похоже на то, что есть возможность вскрывать d, вплоть до размера N^0.5

Re[16]: Я ЕЕ ТОЖЕ ЗНАЮ!!!

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>А если не секрет, как вскрыл?

Использовал ту работу, ссылку на которую вы привели в самом начале. Т.к. вы не отвечали — решил сам попробовать. Когда ответили — я уже решил. Кстати, спасибо за ссылку.

DEA>ЗЫ. А атака Винера меня всерьез заинтересовала. Нарыл литературы и читаю. Похоже на то, что есть возможность вскрывать d, вплоть до размера N^0.5

Я тоже об этом подумал, но мысль отогнал. Вы же парализуете всю систему безопасности человечества, вплоть до разрушения финансовой системы. Скорее всего вас просто убьют, не дав возможности на этом заработать.

Re[17]: Я ЕЕ ТОЖЕ ЗНАЮ!!!

Re[6]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

А>>И там ВСЕГДА получается при большом e маленькое d. Можете проверить.

А>А хотя нет, погорячился. Не всегда получаются маленькие d при больших e. Извиняюсь.

Кстати, а какой длины e в итоге получилось?

Re[7]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, andy1618, Вы писали:

A>Кстати, а какой длины e в итоге получилось?

6 байт.

Re[8]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, Аноним, Вы писали:

A>>Кстати, а какой длины e в итоге получилось?

А>6 байт.

Да, действительно, длина небольшая. Интересно, зачем вообще понадобилось такое делать.

Re[9]: RSA: найти открытую экспоненту, зная закрытую и модул

Здравствуйте, andy1618, Вы писали:

A>Да, действительно, длина небольшая. Интересно, зачем вообще понадобилось такое делать.

Насколько я знаю, обычно это банально ошибка того, кто использовал RSA для организации защиты.

Re[9]: RSA: найти открытую экспоненту, зная закрытую и модул

Кадр из доклада Бена Переза на конференции SummerCon 2019

Опубликованный в 1977 году алгоритм RSA стал революционным для своего времени. В том же году был представлен протокол Диффи — Хеллмана для обмена ключами, а со временем криптосистемы с открытым ключом стали мейнстримом. До сих пор самой популярной среди них является RSA, названная по именам трёх авторов, которые опубликовали алгоритм: Ривест, Шамир и Адлеман.

Но некоторые эксперты призывают отказаться от RSA прямо сейчас, указывая на ряд критических недостатков в криптосистеме, которую почти невозможно грамотно реализовать на практике.

RSA вкратце

Алиса для генерации должна выбрать два простых числа

и

, произведение которых называется «модулем»:

. Затем она выбирает открытую экспоненту

и секретную экспоненту

таким образом, что

. В принципе,

и

должны быть обратными друг другу.

После выбора параметров пользователь Боб может отправить Алисе сообщение

, вычислив

. Алиса может расшифровать этот текст, вычислив

. И наоборот, если Алиса хочет подписать сообщение

, она вычисляет

. Любой пользователь может удостовериться в аутентичности подписи, проверив

.

Прочность криптосистемы RSA основана на сложности факторизации натуральных чисел. Разложение на множители изучалось с античности, так то любой прорыв в это математической дисциплине станет громкой новостью. С другой стороны, конкретно для этой задачи созданы специализированные алгоритмы, такие как Quadratic Sieve и General Number Field Sieve, а закон Мура вынуждает постоянно увеличивать размер ключа, что делает RSA, возможно, не самым оптимальным вариантом для будущего криптографии. Альтернативный вариант — криптография на эллиптических кривых.
На портале поддержки GlobalSign, можно найти краткую информацию о ECC, плюсах, отличии от RSA и генерации ключей.
К сожалению, пока еще не все стали задумываться о преимуществах ECC. Так, один наш крупный клиент, социальная сеть Рунета, год назад довольно серьезно решил подойти к защите данных пользователей, использовав ECC для защиты своих доменов и поддоменов. Однако столкнулся с тем, что не все международные УЦ смогли предложить поддержку генерации SSL-сертификатов с ключами на эллиптических кривых. Почему — для нас на тот момент осталось вопросом.

Но RSA критикуют не за теоретические уязвимости, а за проблемы с практической реализацией.

Доклад на эту тему прочитал инженер по безопасности Бен Перез (Ben Perez) на недавней конференции SummerCon 2019. Он приводит несколько доводов, что эта «хрупкая криптосистема предлагает много способов выстрелить себе в ногу». Да, у RSA прочная теоретическая основа, но на практике разработчики очень часто принимают рискованные решения: «Хотя теоретически возможно правильно реализовать RSA, но десятилетия разрушительных атак доказали, что такой подвиг может быть недостижим на практике».

Ниже перечислены типичные ошибки разработчиков.

Выбор простых чисел

Безопасность RSA основана на том факте, что (большое) число

, которое является произведением двух простых чисел

и

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

Например, если

и

хоть где-то используются повторно, то их можно легко вычислить. Плохие генераторы случайных чисел делают этот сценарий довольно распространённым. Исследование показало, что примерно 1% трафика TLS в 2012 году было уязвимо для такой атаки. Кроме того,

и

следует выбирать независимо, иначе их тоже будет легко подобрать. Даже выбор алгоритма проверки простых чисел имеет последствия для безопасности.

То есть надёжный выбор простых чисел — сама по себе нетривиальная задача. Один из самых известных примеров — уязвимость ROCA в RSALib, которая затронула многие смарт-карты, криптопроцессоры Trusted Platform Module и даже ключи Yubikey. Там для ускорения вычислений при генерации ключей использовались только простые числа определённой формы.

Секретная экспонента

Поскольку выбор большого закрытого ключа негативно влияет на скорость расшифровки и подписи, у разработчиков есть стимул выбирать маленькую секретную экспоненту

, особенно на маломощном железе типа смарт-карт. Но это позволяет злоумышленнику восстановить секретный ключ, что было продемонстрировано в реальных атаках.

Открытая экспонента

Как и в случае с секретной экспонентой, разработчики пытаются использовать маленькие открытые публичные экспоненты для ускорения шифрования и проверки. Часто они выбирают

, что приводит к множеству уязвимостей в криптосистемах RSA.

Иногда разработчики даже используют , что фактически аннулирует шифрование текста. Скриншот из доклада Бена Переза на конференции SummerCon 2019

Выбор параметров

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

Повсеместные атаки типа padding oracle

Заполнение (padding) — добавление ничего не значащих данных к зашифровываемой информации, чтобы повысить криптостойкость. Без него злоумышленнику гораздо проще расшифровать сообщение по контексту.

К сожалению, для заполнения чаще всего используется схема PKCS #1 v1.5, уязвимая для атак типа padding oracle.

«Оракулы заполнения» довольно сложны, но высокоуровневая идея заключается в том, что любое заполнение требует от получателя дополнительной проверки — правильно ли заполнено сообщение. Когда заполнение неправильное, то сервер выдаёт сообщение invalid padding. Одного этого уже достаточно, чтобы медленно расшифровать шифротекст. Процесс утомителен и включает в себя манипулирование зашифрованным текстом миллионы раз, чтобы изолировать изменения, которые приводят к допустимому заполнению. Но атаки реальны. Они особенно опасны, поскольку злоумышленники могут использовать их для восстановления предварительных секретов в сеансах TLS. Подробнее об атаках такого типа см. здесь.

Хотя уязвимость в PKCS #1 v1.5 обнаружили в далёком 1998 году, от неё до сих пор страдают многие реальные системы.

Конечно, алгоритм RSA тут ни при чём, но суть в том, что заполнение (padding) — абсолютно необходимая процедура при использовании RSA, что добавляет лишнюю сложность в криптосистему.

Шпаргалка Mozilla по протоколам безопасности

Современные практики безопасности рекомендуют в первую очередь использовать эллиптическую криптографию.

Ниже краткая шпаргалка Mozilla по внедрению протоколов безопасности. Во второй колонке указана важность защиты (security benefit), в третьей — сложность реализации (implementation difficulty).

В четвёртой колонке указан порядок реализации протоколов со стороны веб-разработчика или администратора. Это рекомендуемый порядок, основанный на комбинации важности защиты и простоты реализации (разработка и поддержка).

HTTPS предполагается как обязательный протокол для всех сайтов.

Для настройки SSL/TLS удобно воспользоваться инструментом SSL Configuration Generator от Mozilla. Он предлагает для серверов три конфигурации:

• Современная: для работы с клиентами, которые поддерживают TLS 1.3, без обратной совместимости. В данный момент поддерживает Firefox 63+, Android 10+, Chrome 70+, Edge 75+, Java 11+, OpenSSL 1.1.1, Opera 57+, Safari 12.1+.
• Промежуточная: рекомендуемая конфигурация для большинства серверов.
• Устаревшая: доступ к сервису осуществляется с помощью очень старых клиентов или библиотек, таких как Internet Explorer 8 (Windows XP), Java 6 или OpenSSL 0.9.8.

Так, в современной конфигурации рекомендуется тип сертификатов ECDSA (P-256) вместо RSA (2048 бит).

«RSA был важной вехой в защите коммуникаций, но последние два десятилетия криптографических исследований сделали его устаревшим. Алгоритмы на эллиптических кривых для обмена ключами и цифровых подписей стандартизированы ещё в 2005 году и с тех пор интегрированы в интуитивно понятные и устойчивые к неправильному использованию библиотеки, такие как libsodium. Тот факт, что RSA по-прежнему широко используется, говорит о неспособности криптографов адекватно сформулировать риски RSA, а также о переоценке со стороны разработчиков своей способности успешно применять эту криптосистему, — делает вывод Бен Перез. — В конечном счёте, за всё заплатят пользователи. Вот почему мы должны согласиться, что использовать RSA в 2019 году абсолютно неприемлемо. Без исключений».