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

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

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

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

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

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

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

Вкратце:

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

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

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

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

Задача создать открытый и закрытый ключи – очень сложна, если речь заходит о колоссальных цифрах. Сложность именно в том, как их быстро вычислить. Дело в том, что если взять два гигантских простых числа, и умножить, обратно потом найти эти простые числа уже весьма проблематично. Алгоритм 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 Ситуация улетает беспокойно

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

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

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

Что такое необратимая математическая функция? Это любая функция, которая вычисляется для любых входных данных. Но после вычисления, вновь получить входные данные становится невозможно.

Например, сложение: 3+8. Если мы выполним эту операцию, мы получим 11. А вот после того, как мы провели операцию сложения, мы уже не знаем, какие два числа были сложены, чтобы получить 11. Это может быть и 5+6, и 4+7, и 9+2…

Для расшифровки в нашем случае нужно знать хотя бы одно слагаемое — мы сразу сможем получить второе. Алгоритм расшифровки такой: x=y-z, где x — результат выполнения функции, а y — слагаемое, которое нам известно. Если рассмотреть это по-другому, x — данные в зашифрованном виде, y — ключ шифрования, z — исходные данные.

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

Если вернуться к нашему примеру 3+8=11, 3 — входные данные, 8 — ключ шифрования, 11 — зашифрованные данные. Чтобы расшифровать (получить) исходные данные, нам нужно провести операцию дешифровки: x=11-8. Мы получаем исходные данные — 3. Если не знать ключ шифрования (8), придётся перебирать все возможные данные: 11-0, 11-1, 11-2, 11-3 и так далее.

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

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

Например, популярный алгоритм шифрования RSA устроен так:

Генерация ключей RSA:

• Выбираются два простых числа. Запишем их как q и p;
• Эти числа перемножаются, а результат записывается. Пусть это будет n;
• вычисляется значение функции Эйлера по формуле: (q-1) * (p-1). Запишем это как f;
• Вот здесь сложно. Нам нужно придумать такое число, которое больше единицы, меньше того, что мы получили в третьем пункте и при этом быть с ним взаимно простым. Можно взять 3, 7, 17, 257 или любое другое (если оно соответствует условиям и меньше того, что у вас получилось в третьем пункте. Это число является открытой экспонентой, запишем как e;
• Вычисляем секретную экспоненту. Берём формулу d = (f*k+1)/e. Число k мы должны подобрать сами. Подбираем до тех пор, пока d не станет целым числом.
• В итоге пара (e, n) — открытый ключ; (d, n) — закрытый ключ

Шифрование RSA:

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

Расшифровка RSA:

Предположим, зашифрованные данные (число), это c. Тогда мы c возводим в степень d и находим остаток от деления на n (закрытого ключа).

Конечно на практике применяются куда более большие числа. Например в качестве q и p генерируются числа длиной в 2048 бит. А это, между прочим, числа примерно вот такие: 32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656. Если перемножить два подобных числа, то потом найти один из множетелей даже методом перебора уже тяжеловато.

Т.к. вся информация в компьютерах представлена в виде бит (чисел 0 и 1), в том числе текст, изображения, музыка, видео и т.д., становится не трудно подмешать сюда математику. Абсолютно любую информацию в компьютере можно представить в последовательности чисел и, разумеется, можно делать с ними что угодно.

Давайте теперь попробуем пошифровать так, как это делается на реальной практике. Для этого будем пользоваться инструментарием PGP. Эта штука умеет намного больше, чем шифровать по RSA, но сейчас нас интересует только RSA-шифрование.

Здесь для шифрования будем использовать Linux-систему; потребуется установленный пакет gpg в системе.

Для генерации ключей мы выполним команду gpg —full-generate-key. Команда задаст несколько вопросов. Необходимо на них ответить самостоятельно. Если вы не знаете как отвечать, значит вам эта статья не понятна. Для публичного ключа потребуется указать Имя, Фамилию и почту. Эта информация абсолютно никуда не отправляется и создаётся только для удобства обращения к ключу. Можно ввести любую информацию. После генерации, ключи будут сохранены в системе. При необходимости их можно будет экспортировать.

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

Теперь мы запишем секретную информацию в текстовый файл. Чтобы зашифровать файл, выполним команду gpg -ae secret.txt, где a — означает armored (мы хотим, чтобы зашифрованный вид файла был всё ещё текстовым, а не бинарным), а e — означат encrypt. Утилита спросит каким ключом шифровать, можете просто указать email, который вы указали при генерации ключа.

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

Для расшифровки файла нужно выполнить команду: gpg secret.txt.asc.

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

Команда для экспорта публичного ключа:
gpg —export <email ключа> -o public.key

Команда для импорта публичного ключа:
gpg —import public.key

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

Когда у меня был курс по основам криптографии, меня тогда очень впечатлило, как препод продемонстрировал нам пример реализации этого алгоритма (естественно, с очень малыми числами) прямо в екселе. Мне это почему-то очень сильно запомнилось.

В интернете полно описаний реализации этого алгоритма, тогда как по сути своей матан там вполне суровый.
Цель же данной заметки — просто немного занять свой мозг чем-то другим, повторить пройденное и восхититься необычной математической красотой =)

Если вам совсем ничего не понятно, то сперва стоит осилить следующие статейки:
http://ru.wikipedia.org/wiki/RSA
простое число
взаимно простые числа
возведение в степень

О том, в каком порядке выполняются арифметические операции, и как пользоваться калькулятором — вы, думаю, и без меня знаете.

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

Итак, P = 23, Q = 17 Это наши два простых числа. Простота чисел очень важна в данном случае.
Перемножить их тривиально: n = P*Q = 23*17 = 391. Вот это произведение — основа нашей ключевой пары, не зная которой, невозможно произвести вычисления. Каждый ключ в РСА — это ПАРА чисел, и одно из них — это всегда этот самый n. Именно через него устроена связь секретного ключа с публичным. С ростом исходных чисел p и q произведение растёт вместе с ними, и в практически применяемых ключах длина этого самого произведения в битах и называется длиной ключа. То есть если вы видите, что ключ RSA для протокола SSH у сервера — 2048 бит, то это значит, что произведение этих самых двух простых чисел, сгенерированных при настройке сервера как раз лежит в промежутке между единицей и 2^2048 (2 в степени 2048).

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

Самое главное — в уже открывшемся сеансе bc написать команду scale = 0, чтобы bc считал с точностью до целого. Проверяем:

$ bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
scale=0

1/2
0

3%2
1

11%5
1

11%6
5


Как видим, остатки считаются правильно. При ненулевых значения scale программа bc будет округлять до сответсвующих знаков после запятой, что явно не наш случай.
Тяжело представить число 2^2048. Это больше, чем АТОМОВ во Вселенной. Совершенно запредельно. Но нам пофиг, считаем:

2^2048
32317006071311007300714876688669951960444102669715484032130345427524
65513886789089319720141152291346368871796092189801949411955915049092
10950881523864482831206308773673009960917501977503896521067960576383
84067568276792218642619756161838094338476170470581645852036305042887
57589154106580860755239912393038552191433338966834242068497478656456
94948561760353263220580778056593310261927084603141502585928641771167
25943603718461857357598351152301645904403697613233287231227125684710
82020972515710172693132346967854258065669793504599726835299863821552
51663894373355436021354332296046453184786049521481935558536110595962
30656

Расчёт происходит мгновенно. Получилось десятичное число с более чем 600 знаками. Длина ключа теоретически не ограничена — у меня применяются ключи длиной 8192 бит (в десятичном виде — число с почти 2500 знаков), и они прекрасно работают.
Есть ли практические лимиты в этой простой операции по времени ? В программе bc ощутимая задержка начинает ощущаться только когда показатель и основание степени становится более пяти-шести знаков.

Естественно, надо это малость побенчить, мы всё-таки одмины, а не бешеные математики, и знание о сложности и времени выполнения для нас даже более важны =)
Пишем простейший скрипт:

#!/bin/bash

echo " Hi. Make calculation-time tests for bc, a^b, scale = 0";

for a in `seq 1 3`
do
    echo "====== $a ====";
    for b in `seq 1 5`
    do
        d1=`date "+%s.%N"`;
        res=`echo "scale=0; $a^$b" | bc`;
        d2=`date "+%s.%N"`;
        ct=`echo "scale=0; ($d2-$d1)/1" | bc`;  # calculate time
        echo "  a^b = $a^$b = $res : $ct sec";
    done
done

Запустим и проверим, что у нас всё ок:

$ bash /tmp/1.sh 
 Hi. Make calculation-time tests for bc, a^b, scale = 0
====== 1 ====
  a^b = 1^1 = 1 : 3.355310 millisec
  a^b = 1^2 = 1 : 2.419569 millisec
  a^b = 1^3 = 1 : 1.655505 millisec
  a^b = 1^4 = 1 : 1.444963 millisec
  a^b = 1^5 = 1 : 1.484685 millisec
====== 2 ====
  a^b = 2^1 = 2 : 1.442135 millisec
  a^b = 2^2 = 4 : 1.457245 millisec
  a^b = 2^3 = 8 : 1.539088 millisec
  a^b = 2^4 = 16 : 1.513932 millisec
  a^b = 2^5 = 32 : 1.543942 millisec
====== 3 ====
  a^b = 3^1 = 3 : 1.518090 millisec
  a^b = 3^2 = 9 : 1.430215 millisec
  a^b = 3^3 = 27 : 1.480445 millisec
  a^b = 3^4 = 81 : 1.449416 millisec
  a^b = 3^5 = 243 : 1.484290 millisec

Немного увеличим значения для циклов, скроем доли секунды и уберем вывод результата, поскольку нам интересно лишь время выполнения. Памяти оно ест мало, а вот процессор грузит полностью, но только в один поток. Немного нагрев помещение, смотрим результаты.
Сперва с моей домашней машинки (Core2 Duo E6850 @ 3.00GHz) :

$ bash /tmp/1.sh 
 Hi. Make calculation-time tests for bc, a^b, scale = 0
====== 50 ====
  a^b = 50^50  : 0 sec
  a^b = 50^200050  : 2 sec
  a^b = 50^400050  : 8 sec
  a^b = 50^600050  : 18 sec
  a^b = 50^800050  : 25 sec
====== 200050 ====
  a^b = 200050^50  : 0 sec
  a^b = 200050^200050  : 37 sec
  a^b = 200050^400050  : 113 sec
  a^b = 200050^600050  : 220 sec                            
  a^b = 200050^800050  : 342 sec
====== 400050 ====
  a^b = 400050^50  : 0 sec
  a^b = 400050^200050  : 40 sec
  a^b = 400050^400050  : 120 sec
  a^b = 400050^600050  : 235 sec
  a^b = 400050^800050  : 361 sec
====== 600050 ====
  a^b = 600050^50  : 0 sec
  a^b = 600050^200050  : 41 sec
  a^b = 600050^400050  : 125 sec
  a^b = 600050^600050  : 243 sec
  a^b = 600050^800050  : 375 sec
====== 800050 ====
  a^b = 800050^50  : 0 sec
  a^b = 800050^200050  : 42 sec
  a^b = 800050^400050  : 129 sec
  a^b = 800050^600050  : 255 sec
  a^b = 800050^800050  : 389 sec

Хотя офисная рабочая машина справилась заметно быстрее, ибо Core i7-2600K @ 3.40GHz — штука мощная:

$ bash /tmp/1.sh
 Hi. Make calculation-time tests for bc, a^b, scale = 0
====== 50 ====
  a^b = 50^50  : 0 sec
  a^b = 50^200050  : 2 sec
  a^b = 50^400050  : 6 sec
  a^b = 50^600050  : 13 sec
  a^b = 50^800050  : 18 sec
====== 200050 ====
  a^b = 200050^50  : 0 sec
  a^b = 200050^200050  : 26 sec
  a^b = 200050^400050  : 79 sec
  a^b = 200050^600050  : 152 sec
  a^b = 200050^800050  : 236 sec
====== 400050 ====
  a^b = 400050^50  : 0 sec
  a^b = 400050^200050  : 28 sec
  a^b = 400050^400050  : 86 sec
  a^b = 400050^600050  : 165 sec
  a^b = 400050^800050  : 253 sec
====== 600050 ====
  a^b = 600050^50  : 0 sec
  a^b = 600050^200050  : 29 sec
  a^b = 600050^400050  : 87 sec
  a^b = 600050^600050  : 170 sec
  a^b = 600050^800050  : 264 sec
====== 800050 ====
  a^b = 800050^50  : 0 sec
  a^b = 800050^200050  : 30 sec
  a^b = 800050^400050  : 90 sec
  a^b = 800050^600050  : 180 sec
  a^b = 800050^800050  : 272 sec

Желающие могут построить красивый трехмерный график =)
То есть основное время выполнения у bc растет при росте показателя степени, тогда как основание степени влияет заметно меньше. Вообщем, нам хватит =)

Ну а теперь вернемся к нашему алгоритму RSA.
Вспоминаем: P = 23, Q = 17, n = P*Q = 23*17 = 391.
Теперь нам нужно значение функции Эйлера:
f(n) = f(p*q) = (p-1)(q-1) = 22 * 16 = 352. Именно функция Эйлера и Китайская теорема об остатках дают нам работоспобоную асимметричную криптографию RSA.
Потом нужно выбрать (случайно) целое положительное число, меньшее чем значение функции Эйлера и большее единицы, взаимно простое с f(n). При размерах ключей в тысячи бит — там этих чисел хватит на всех =)
Я для примера взял число 5, обозначив его как e1. Это и будет наша первая экспонента. Оно простое, 352 на него не делится стопудофф =).

С вычислением этого произведения, как и с поиском такого числа, проблем в вычислительном плане никаких нет. Правда, когда считать его надо не слишком часто 😀 😀

Вторая экспонента (e2) связана с первой таким уравнением:
( e1 * e2 ) mod f(n) = 1
В нашем случае: ( 5 * e2 ) mod 352 = 1
Ищем e2 : e2 = 2*round((352 / 5)) + 1 = 141. Бинго! Это наша вторая экспонента. Перемножив эти экспоненты между собой и поделив в целых их произведение на f(n), получим единицу в остатке: ( 5 * 141 ) mod 352 = 1 .

И вот эти две экспоненты и образуют вторые части ключевых пар. Одна из экспонент держится в секрете, а вторая — может быть опубликована. Причём совершенно неважно, какая из двух экспонент будет засекречена — работать будет в обоих случаях одинаково.
Пусть первая экспонента уйдёт в закрытый ключ, а вторая — в открытый.

Тогда открытый ключ — это пара чисел (141, 391), а закрытый ключ — пара (5, 391).
Шифрование и расшифрование делается по одной и той же формуле — число, соответствующее символу текста, возводится в соответствующую степень, и от этого произведения вычисляется остаток от деления на n.

Попробуем. Пусть наш текст — набор цифр 1,2,3,55,56,60,61. Каждый символ для большей наглядности будем шифровать независимо.

Стандартный калькулятор тут малость бесполезен — при попытке возвести в сотую с фигом степень, ответ будет вида
x.xxxx E YYYYY. Нам же, чтобы ощутить всю радость жизни, надо знать число абсолютно точно, да и на его размер глянуть.
Тут очень рулит именно консольный калькулятор bc. Знак процента в bc (впрочем, как и ещё в ряде языков программирования) означает получение остатка от целочисленного деления.

(1^141) % 391 = 1
(2^141) % 391 = 2787593149816327892691964784081045188247552 mod 391 = 236
(3^141) % 391 = 18797362446533911137768672583025790996620083340431995824578794152403 mod 391 = 386
(55^141) % 391 =
24611564330920293149498027019449369938626596620824346991722539486855
03446295406984290788359569732220360630380785948062132031694807450607
22049384415635669069451059720063834707789262119358866483850966969094
097025472223094766377471387386322021484375 % 391 = 140
Оопс! Это ещё всего лишь тестовый пример, не обладающий даже малейшим намёком
на криптографическую стойкость, а тут уже няшные четырехстрочные числа 😀
(56^141) % 391 =
31225673034125965570835931407246832392516748597154292059508414938634
15021504782417093492810298708223720171827020967538963618595753456915
11587954419307384901952399397150061521397212480805717448858157412506
4777182100104736438971904737309919077728256 % 391 = 20
(60^141) % 391 =
52399398790572620757964850071485835892981764632281000292535663884918
08059451990888503282979921293143677966745600000000000000000000000000
00000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000 % 391 = 297
Кто сосчитал число нулей в уме и с первого прочтения — тот монстр =)
(61^141) % 391 =
53889820437744572226071012523544360408317743194467789053035182987276
03746266121005976016674508209588229326835722319842077407370913968084
55524466514472282857995060826885344978103866679907381502571817688886
892037267801790468017505688425549722812506500461 % 391 = 198
Ура, выдохнули.

Наш открытый текст (1,2,3,55,56,60,61) превратился в шифр-текст (1,236,386,140,20,297,198)
Не зная второй экспоненты, обратное преобразование произвести невозможно — очень сложно угадать, что за фигня была возведена в степень, давшая в итоге полученный остаток.

Но! Отсюда же очевидно, что применять «в лоб» алгоритм RSA сразу к осмысленному тексту категорически недопустимо! Ключ вы этим конечно не раскроете, но и защиты не будет.

Если у вас в тексте есть фраза «привет, Вася!!!», то при прогоне она будет давать один и тот же шифртекст, содержащий в конце три одинаковых цифры.
А значит — привет, частотный анализ и прочая классика. Впрочем, из-за необходимости вычислять чудовищные степени и указанных особенностей никто так алгоритм RSA и не применяет. Его путь — шифрование сессионных ключей, которые генерируются случайно, ничего осмысленного в себе не несут и повторно никогда не используются.
Ну и в качестве числа используются НАМНОГО более крупные блоки, чем байт. Степени при этом становятся совсем уж чудовищные. Именно из-за этого асимметричная криптография столь медленна по сравнению с симметричной!
Под вычисления таких громадных чисел никаких специальных регистров в процессоре не предусмотрено, и алгоритмы работы из-за этого весьма и весьма медленные.

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

(1^5) % 391 = 1
(236^5) % 391 = 732082482176 % 391 = 2
(386^5) % 391 = 8569125894176 % 391 = 3
(140^5) % 391 = 53782400000 % 391 = 55
(20^5) % 391 = 3200000 % 391 = 56
(297^5) % 391 = 2310905821257 % 391 = 60
(198^5) % 391 = 304316815968 % 391 = 61

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

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

Ну а теперь немного поиграемся с реальным криптософтом. Обычно чаще всего используются SSH и PGP, но их для оценки использовать не особо удобно. ssh-keygen требует интерактивного взаимодействия, да и параметр там всего один — длина ключа (-b). В GnuPG тоже генерация ключей чуть более сложная и требует указания ряда значений.
Так что сперва помучаем наши машины путем генерации ключей средствами OpenSSL. В самом OpenSSL конечно есть бенч, но он измеряет именно производительность операций шифрования, а нас пока что интересует время генерации ключей, поскольку она тоже не халявная.
Берём такой скрипт:

#!/bin/bash

echo " Hi. Make calculation-time tests for openssl genrsa";
for a in `seq 512 512 33280`
do
        d1=`date "+%s.%N"`;
        res=`openssl genrsa $a > /dev/null 2> /dev/null`;
        d2=`date "+%s.%N"`;
        ct=`echo "scale=2; ($d2-$d1)/1" | bc`;  # calculate time
        echo "  RSA-$a : $ct sec";
done

и запускаем. Грузит он одно ядро целиком, но не более того. Немного согреем помещение суровой сибирской зимой =)
К моему огромному удивлению, некоторые ключи генерировались существенно быстрее. И хотя с ростом длины ключа растёт время его генерации, зависимость не без странностей.

Время генерации (в секундах) ключевой пары RSA в OpenSSL 
(версия: OpenSSL 1.0.0k-fips 5 Feb 2013), в зависимости от длины ключа.

  Ключ        Core 2 Duo              Core i7
           E6850 @ 3.00 GHz        2600K @ 3.40GHz

RSA-512            0.05             0.07
RSA-1024           0.05             0.01
RSA-1536           0.02             0.22
RSA-2048           0.23             0.25
RSA-2560           1.18             0.77
RSA-3072           2.23             0.60
RSA-3584           1.81             0.43
RSA-4096           4.10             3.60
RSA-4608           5.37             1.10
RSA-5120           8.62             5.16
RSA-5632           36.05            8.23
RSA-6144           8.82             13.11
RSA-6656           2.39             15.16
RSA-7168           60.53            28.94
RSA-7680           15.28            20.45
RSA-8192           99.36            24.98
RSA-8704           53.38            110.36
RSA-9216           211.79           28.30
RSA-9728           231.94           32.82
RSA-10240          45.60            52.47
RSA-10752          187.26           249.42
RSA-11264          97.97            94.74
RSA-11776          213.02           376.66
RSA-12288          315.34           221.01
RSA-12800          66.22            161.17
RSA-13312          383.11           89.18
RSA-13824          388.31           615.12
RSA-14336          59.76            180.02
RSA-14848          1030.60          435.93
RSA-15360          437.27           653.71
RSA-15872          273.42           350.05
RSA-16384          2911.01          834.40
RSA-16896          1664.64          415.60
RSA-17408          1473.09          637.16
RSA-17920          1063.90          1576.45
RSA-18432          2905.21          1055.57
RSA-18944          3366.05          617.51
RSA-19456          2394.12          2486.13
RSA-19968          2001.94          1222.62
RSA-20480          2798.44          577.88
RSA-20992          1259.38          2737.42
RSA-21504          1964.91          354.19
RSA-22016          584.14           1206.87
RSA-22528          2545.75          2805.34
RSA-23040          4163.64          1960.22
RSA-23552          6541.05          1145.15
RSA-24064          8544.41          3674.17
RSA-24576          2020.58          1523.39
RSA-25088          2013.43          1822.39
RSA-25600          8140.80          7331.52
RSA-26112          21281.48         2911.39
RSA-26624          4732.62          4368.14
RSA-27136          7055.22          3882.78
RSA-27648          12578.72         4124.65
RSA-28160          7220.34          2042.86
RSA-28672          6460.51          4826.69
RSA-29184          6403.41          13630.68
RSA-29696          8632.35          4769.27
RSA-30208          18503.07         4181.68
RSA-30720          9017.39          1896.43
RSA-31232          14344.90         5669.59
RSA-31744          4631.25          12766.81
RSA-32256          5023.82          8129.61
RSA-32768          829.25           4802.20
RSA-33280          8477.86          7511.91

Вахх. Время генерации длинных ключей совершенно непредсказуемо меняется! Почему — даже предположить не берусь.
На графике выглядит совсем безумно — при больших длинах ключей время генерации меняется непредсказуемо:

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

Вот такие вот игрища. В следующий раз ещё над чем-нибудь поэкспериментирую, если меня муха какая укусит. 😀 😀

RSA. Нахождение секретной экспоненты.

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей: