Хэш-функция

Что такое электронная подпись

Элек­трон­ная под­пись — это тех­но­ло­гия, кото­рая помо­га­ет под­твер­дить под­лин­ность элек­трон­но­го доку­мен­та: дого­во­ра, справ­ки, выпис­ки или чего-то ещё. 

Если упро­щён­но, рабо­та­ет так: 

👉 Есть некий доку­мент, под­пи­сан­ный ЭП

👉 С помо­щью спе­ци­аль­ной про­грам­мы мож­но про­ве­рить под­лин­ность этой под­пи­си и документа

✅ Если про­грам­ма гово­рит, что всё окей, то мы можем быть уве­ре­ны: доку­мент под­пи­сал имен­но тот, кто в нём ука­зан; и с момен­та под­пи­са­ния в доку­мен­те ниче­го не изменилось. 

❌ Или про­грам­ма может ска­зать, что под­пись не сов­па­ла. Это зна­чит, что либо доку­мент под­пи­сал дру­гой чело­век, либо после под­пи­са­ния кто-то изме­нил этот доку­мент (напри­мер, допи­сал ноль в сто­и­мость кон­трак­та). Так мы пой­мём, что это­му доку­мен­ту нель­зя доверять.

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

Основа эп — асимметричное шифрование

Мы уже писа­ли об асим­мет­рич­ном шиф­ро­ва­нии. Вот основ­ные мысли: 

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

1 Хэш-функции

Определение 9.1Хэш-функции – это функции, предназначенные для “сжатия” произвольного сообщения, записанного, как правило, в двоичном алфавите, в некоторую битовую последовательность фиксированной длины, называемую сверткой.

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

В криптографии хэш-функции применяются для решения следующих задач:

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

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

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

Определение 9.2Обозначим через X множество, элементы которого будем называть сообщениями, n – натуральное число. Хеш-функцией называется всякая легко вычислимая функция h: X rightarrow {0,1}^n.

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

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

Как правило, хеш-функции строят на основе так называемых одношаговых сжимающихся функцийy=f(x_1,x_2)x_1x_2mnnдлина свертки. Для получения значения h(M)Mmдлина сообщения не кратна mM_1, M_2,dots, M_Nvвектор. Если функцияfвектор можно положить равным нулевому вектору. Если же функцияfвектор можно составить из фрагментов указывающих на дату, время, номер сообщения и т.п.При таком подходе свойства хеш-функции hf

2.1 Общие положения

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

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

Задачи, которые решает подпись:

Для реализации схемы ЭЦП необходимы два алгоритма: алгоритм генерации подписи и алгоритм проверки. Надежность схемы ЭЦП определяется сложностью следующих задач:

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

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

2.2 Схема Эль-Гамаля

См. [1]

Безопасность схемы основана на трудности вычисления дискретных логарифмов в конечном поле. Для генерации пары ключей выбирается простое число pgxpy=g^{x} ~(mod  p)y, g, ppgxMkp-1(r, s)

Для проверки подписи нужно убедиться, что

Первое замечание о выборе kkxkkxk

Схема Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам схем подписи.

Пример 9.1Выберем p =11 и g = 2, а секретный ключ x = 8.

Вычислим:

Открытым ключом являются y = 3g = 2p = 11M =5k = 9GCD(9,10) = 1

Теперь находим

Итак, подпись представляет собой пару: r =6s = 3

Для проверки подписи убедимся, что:

Второе замечание. При вычислении подписи целесообразно использовать хэш-образ сообщения, а не само сообщение Mh(M)=5хеширования и шифрования с открытым ключом (в частности, RSA или Эль-Гамаля).

Алгоритм формирования подписи выглядит следующим образом:

  1. Пусть M – подписываемое сообщение. Отправитель вычисляет хеш-значение подписываемого сообщения h=h(M). Значение h должно удовлетворять неравенству 0<h<p.

  2. Отправитель выбирает случайное число k, 0<k<p-1, взаимно простое с p-1, и вычисляет числа:

    k^{-1} – число, обратное k по модулю p-1, k^{-1} существует, так как k и p-1 – взаимно просты.

  3. Подпись (r, s) добавляется к сообщению, и тройка (M, r, s) передается получателю.

Проверка подписи: получатель заново вычисляет хеш-значение присланного сообщения h(M)

Если подпись верна, то это равенство выполняется.

Отметим, что число kh(M)

2.3 Скрытый канал

См. [2]

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

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

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

В общем случае организация подсознательного канала выглядит так:

  1. Отправитель создает безобидное сообщение;
  2. Используя общий ключ с получателем сообщения, отправитель подписывает безобидное сообщение, пряча свое подсознательное сообщение в подписи;
  3. Отправитель посылает подписанное сообщение по общедоступному каналу передачи;
  4. Проверяющий читает сообщение и проверяет подпись. Не обнаружив ничего подозрительного, он передает сообщение дальше;
  5. Получатель проверяет подпись под безобидным сообщением, убеждаясь что сообщение получено от отправителя;
  6. Получатель игнорирует безобидное сообщение и, используя общий с отправителем секретный ключ, извлекает подсознательное сообщение;
Читайте также:  Портал поставщиков стал удобнее для самозанятых граждан - Единый портал ЭП

Рассмотрим простейший пример организации подсознательного канала передачи информации используя цифровую подпись реализуемую по методу Эль-Гамаля.

  1. Сначала необходимо сгенерировать пару ключей, для этого выбирается простое p=11 и два случайных g=2 и x=8, причем g<p и x<p. Затем вычисляется y=g^x ~(mod  p), y=2^8 ~(mod  11) =3. Открытым ключом является (y, g, p)=(3,2,11), секретным ключом x=8;

  2. Создают безобидное сообщение M=5 и скрытое сообщение M_1=9, проверяя чтобы эти сообщения были взаимно простые с p, а также чтобы M_1=9 было взаимно простым c (p-1)=10; В нашем случае это так;

  3. Вычисляем значение цифровой подписи (a, b)

    Мы получили подпись (6,3) и в тоже время создали скрытый канал;

  4. Проверяющий может просмотреть безобидное сообщение и удостовериться что сообщение передано от отправителя с подписью (6, 3), для этого он проводит вычисления:
  5. Получатель, обладающий секретным ключом, удостоверяется в том, что сообщение пришло именно от того отправителя, с которым организован скрытый канал, для этого он проводит вычисления:
  6. Получатель восстанавливает скрытое сообщение:

2.4 Цифровая подпись на эллиптических кривых

См. [3]

В качестве международного стандарта принят американский алгоритм цифровой подписи на эллиптических кривых (ECDSA). В этом стандарте используются эллиптические кривые как над полем простого порядка, так и над полем характеристики 2. Однако криптографически стойких кривых над полем характеристики 2 сравнительно мало. Поэтому мы рассмотрим ЭЦП на эллиптических кривых, заданных над полем большей характеристики.

Замечание. В России официально принят стандарт ЭЦП на эллиптических кривых над полем большей характеристики – ГОСТ 34.10-2001 “Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи”. Выбор кривой и точки на ней подразумевает решение ряда вспомогательных задач. Прежде всего, это подсчет количества точек на кривой. Если NEpNGpN

Для получения криптографически стойкой системы ЭЦП должны выполняться следующие условия:

  1. Порядок точки G, используемой в системе ЭЦП, должен быть простым числом n> max left{ {2}^{160},4sqrt{p}right}.
  2. Nneq p и N neq p   1, где N – порядок кривой.
  3. {p}^{k} neq 1 ~(mod  n) для всех k = 1, dots, C, где C настолько велико, что вычислить дискретный логарифм в GF({{p}^{C}}) за приемлемое время невозможно.

Замечание. В настоящее время значение C = 20ENnnNnGG' in E({F}_{p})G=  frac{N}{n}cdot G'G neq mathcal{O}G = mathcal{O}G'd0<d<nQ = d cdot Gh

Второй учебный алгоритм хеширования

В этом алгоритме pM

  1. Начальное значение h_0 принимается равным числу десятичных разрядов в M.

  2. Для каждого десятичного знака M_i числа M вычисляется значение
  3. Значение h_n, вычисленное для последнего символа, увеличенное на 1, является хеш-значением сообщения: h(M)=h_n 1.

Вычисленное по этому алгоритму хеш-значение зависит от всех символов сообщения MПример 9.3Известны значения общих параметров системы Эль-Гамаля: p=59, g=14 и открытый ключ абонента y=20. От абонента получено сообщение M=7569, снабженное цифровой подписью Эль-Гамаля r=32, s=46. Проверить подлинность цифровой подписи. Хеш-значение сообщение вычисляется с помощью второго учебного алгоритма.

  1. Вычисляем значения y^{r} ~(mod  p) и r^{s} ~(mod  p), а затем их произведение по модулю p:

    В рассматриваемом примере получаем:

  2. Для полученного сообщения вычисляем хеш-значение h(M) по второму учебному алгоритму.
  3. Вычисляем значение g^{h} ~(mod  p).

    В примере g^{h} ~(mod  p)=14^{21}~(mod 59) = 6.

  4. Проверяем выполнение равенства y^{r}r^{s} ~(mod  p)=g^h ~(mod  p), если равенство выполняется – подпись подлинная, в противном случае – фальшивая.

    В нашем примере 53neq 6. Равенство не выполняется, значит, подпись фальшивая.

Генерация подписи

Входные данные: сообщение M(r, s)

Алгоритм:

Выбрать случайное число k(1, n - 1)

  1. Вычислить (x, y) = k cdot G.
  2. Вычислить r = x ~(mod  n).
  3. Если r = 0, то вернуться к шагу 1.
  4. Вычислить z= {k}^{-1} ~(mod  n).
  5. Вычислить e=h(M).
  6. Вычислить s = z(e   dr) ~(mod  n).
  7. Если s = 0, то вернуться к шагу 1.
  8. Вывести пару (r,s) – подпись к M.

Замечания.

  1. При r = 0 результат вычисления s не зависит от секретного ключа d.
  2. При s = 0 необходимого для проверки подписи числа {s}^{-1} ~(mod  n) не существует.
  3. В качестве хеш-функции h на 6 в стандартах ANSI X9F1 и IEEE P1363 используется SHA-1, в российском стандарте ГОСТ Р 34.10-2001~- хеширование по стандарту ГОСТ Р 34.11-94.

Как работает: алгоритмы шифрования

Допу­стим, вы уже схо­ди­ли в удо­сто­ве­ря­ю­щий центр и полу­чи­ли на флеш­ке сер­ти­фи­кат и ключ элек­трон­ной под­пи­си. Теперь нуж­но ска­чать спе­ци­аль­ный софт, кото­рый и будет под­пи­сы­вать ваши доку­мен­ты и про­ве­рять чужие на подлинность.

Про­бле­ма в том, что ЭП осно­ва­на на алго­рит­мах асим­мет­рич­но­го шиф­ро­ва­ния, а их мно­го: раз­ло­же­ние на про­стые мно­жи­те­ли, дис­крет­ное лога­риф­ми­ро­ва­ние, эллип­ти­че­ские кри­вые и мно­же­ство дру­гих. Ключ из одно­го алго­рит­ма не подой­дёт для исполь­зо­ва­ния в дру­гом, поэто­му в Рос­сии дого­во­ри­лись исполь­зо­вать стан­дарт шиф­ро­ва­ния ГОСТ Р 34.

Это зна­чит, что нам нужен спе­ци­аль­ный софт, в кото­ром уже есть этот алго­ритм. Чаще все­го исполь­зу­ют Крип­то­П­РО, реже — ViPNet CSP. С помо­щью этих про­грамм мож­но под­пи­сать доку­мен­ты и про­ве­рить сер­ти­фи­ка­ты на подлинность.

Как работает: сертификаты

Элек­трон­ная под­пись состо­ит из двух прин­ци­пи­аль­ных частей:

  1. Сер­ти­фи­кат для удо­сто­ве­ре­ния подписывающего.
  2. Крип­то­гра­фи­че­ская часть для про­вер­ки под­лин­но­сти документа.

Гру­бо гово­ря, ЭП долж­на гаран­ти­ро­вать, что доку­мент под­пи­са­ли имен­но вы и что вы под­пи­са­ли имен­но этот документ. 

В сер­ти­фи­ка­те хра­нят­ся дан­ные о вла­дель­це подписи:

  • кто вла­де­лец этой подписи;
  • откры­тый ключ для про­вер­ки подписи;
  • когда закан­чи­ва­ет­ся срок дей­ствия подписи;
  • како­го уров­ня доку­мен­ты мож­но под­пи­сы­вать этой подписью;
  • кто выдал сертификат;
  • и дру­гие слу­жеб­ные данные.

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

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

Некоторые наиболее употребительные схемы эцп

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

Первый учебный алгоритм хеширования

Входом для данного алгоритма является строка, состоящая из букв русского языка.

  1. Выбирается число h_0 – вектор инициализации. Число h_0 равно длине сообщения в символах.

  2. Для каждого символа сообщения вычисляется значение h_i=(n_i h_{i-1})^2 ~(mod  p)$, $i=1,dots,n, где n_i – номер i-й буквы сообщения в алфавите. Для удобства вычислений ниже приведен нумерованный алфавит.

  3. Значение h_n, вычисленное для последнего символа, является хеш-значением сообщения: h(M)=h_n.

Следует отметить, что вычисленное по этому алгоритму хеш-значение зависит от всех символов сообщения Mp=79g=15xkMПример 9.2Выполнить вычисление и проверку подписи сообщения M=text{"БЛЕФ"} по алгоритму Эль-Гамаля. Использовать параметры подписи:

  1. Сформируем хэш-сумму сообщения. Начальное значение h_0 равно количеству символов сообщения: h_0=4. Далее,
  2. Вычисляем число r по формуле r=g^k ~(mod  p). Для рассматриваемого примера получили:
  3. Вычисляем число u по формуле u=(h-xr) (mod p-1), для рассматриваемого примера
  4. Вычисляем значение k^{-1} по модулю p-1 с помощью расширенного алгоритма Евклида. Для рассматриваемого примера значение k^{-1}=23.

    Примечание: если полученное значение k^{-1} – отрицательное, следует взять его по модулю p-1.

  5. Вычисляем число s по формуле s=k^{-1}u (mod p-1). В примере
  6. Цифровая подпись сообщения для рассматриваемого примера: (14,37).

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

  1. Сформируем открытый ключ y абонента по формуле y=g^{x} ~(mod  p):

    Для рассматриваемого примера y=15^{34} ~(mod  79) = 38.

  2. Аналогичным образом вычисляем значения y^{r} ~(mod  p) и r^{s} ~(mod  p), а затем их произведение по модулю p.

    В примере получаем:

  3. Вычисляем значение g^{h} ~(mod  p), значение h было получено ранее.

    В примере g^{h} ~(mod  p)=15^{13} ~(mod  79)= 78.

  4. Проверяем выполнение равенства y^{r}r^{s} ~(mod  p)=g^h ~(mod  p), если равенство выполняется – подпись подлинная, то есть она была вычислена правильно.

    В примере получили 78=78, равенство выполняется, значит, подпись сгенерирована правильно.

Пример генерации подписи

Наша цель – показать особенности алгоритма, не зависящие от разрядности чисел.

Пример 9.4Пусть используется эллиптическая кривая {E}_{751}(-1,1) и генерирующая точка G = (384, 475) порядка n = 13 (13 – наибольший из делителей порядка кривой N = 728). Предположим, абонент подписывает личным секретным ключом d = 12 сообщение, хеш-свертка которого равна e = 12. Сгенерировать подпись.Пусть абонент, подписывающий сообщение, выбрал случайное k = 3kG = (x, y) = 3 cdot (384, 475) = (596, 318)r = x ~(mod  n)= 596 ~(mod  13) = 11z =  {k}^{-1}~(mod  n) =  {3}^{-1} ~(mod  13) = 93 cdot 9 = 27 equiv 1 ~(mod  13)s = z(e   dr) ~(mod  n) =9 cdot (12  12 cdot 11) ~(mod  13) = 9(r, s) = (11,9)

В реально использующихся системах ЭЦП по российскому стандарту числа имеют порядка 60 десятичных знаков.

Принцип работы электронной подписи

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

Подписание документа производится в несколько этапов:

  1. Хеш документа шифруется с помощью закрытого ключа.
  2. Полученная подпись добавляется к документу.
  3. К документу прикрепляется сертификат проверки.

Проверка подписи

Входные данные: сообщение MM

Выходные данные: заключение о подлинности или фальсификации подписи.

Алгоритм:

  1. Если хотя бы одно из условий 1 leq  r leq n - 1, 1leq s leq n - 1 нарушается, то подпись фальшивая и работа алгоритма закончена.
  2. Вычислить e = h(M).
  3. Вычислить v =  {s}^{-1} ~(mod  n).
  4. Вычислить {u}_{1} = e r ~(mod  n).
  5. Вычислить {u}_{2} = r v ~(mod  n).
  6. Вычислить X =  {u}_{1} cdot G    {u}_{2} cdot Q = (x, y).
  7. Если r = x ~(mod  n), то подпись действительная, иначе подпись фальшивая.

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

Пример 9.5Требуется проверить подлинность подписи (11,9) для сообщения M, хэш-образ которого e=12.Секретный ключ нам неизвестен, открытый ключ абонента, подписавшего сообщение, равен Q = dG = (384, 276).Проверка подписи начинается с проверки условий 1 leq r leq n -11leq s leq n -1

Находим точку

Наконец, сравниваем значения r = 11x ~(mod  n) = 596 ~(mod  13) = 11

Приведем пример системы электронной подписи на эллиптической кривой, пригодный для практического применения.

Пример 9.6Рассмотрим эллиптическую кривую

Её порядок

является простым числом, а порождающим элементом группы является точка

Для построения электронной подписи нужно выбрать закрытый ключ dQ=dcdot G.

Система цифровой подписи построена.

Если читатель не имеет инструмента для работы с кривыми таких размеров, предлагаем небольшую программу на языке с , вызывающую функцию библиотеки cryptopp для перемножение точек:

Для её сборки нужно подключить библиотеку cryptopp (см. параграф 1.16.2). Допустим, мы собрали программу в исполняемый файл mulpoint (или mulpoint.exe под Windows).

Программа запускается из командной строки:

и выводит результат через стандартный выходной поток. Например:

(здесь $ – приглашение командной строки linux). В нашем случае, помимо a=-3

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

  1. Васильева И.Н. Защита информации — СПб, 2009. — 136 с.
  2. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Триумф, 2003. — 816 с.
  3. Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии — Минск: БГУ, 1999. — 319 с.
  4. Жданов О.Н., Чалкин В.А. Эллиптические кривые. Основы теории и криптографические приложения — М.: УРСС, 2021.
  5. Schoof, R. Counting points on elliptic curves over finite fields //J. de Th'{e}orie des Nombres de Bordeaux. — textnumero 7 (1995). — p. 219-254.
  6. Lercier, R., Morain, F. Counting the number of points on elliptic curves over finite fields: strategies and performances,
  7. In L. C. Guillou and J.-J. Quisquater, editors, Advances in cryptology — EUROCRYPT’95, textnumero 921 (1995) of Lecture Notes in Comput. Sci. p. 79-94.
  8. NIST FIPS 186-4, July 2021.

Хеш-функции

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

Хеш-функции имеются практически в любом языке программирования. Например, они используются для реализации хеш-таблиц и множеств (HashMap/HashSet в Java, dict и set в Python, Map, Set и объекты в JavaScript и так далее). Отдельная категория хеш-функций — криптографические хеш-функции.

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

Поэкспериментировать с хеш-функциями можно, написав простую программу на Python:

import hashlib
def hash_hex(message):
    return hashlib.sha256(message.encode()).hexdigest()


Функция hash_hex() рассчитывает представление хеша в шестнадцатеричной записи для строки. В приведенном примере используется функция SHA-256 — та же, что и в биткойне.

Хорошая хеш-функция обеспечивает защиту от коллизий (невозможно получить два одинаковых хеша при разных начальных данных) и обладает так называемым эффектом лавины, когда малейшее изменение входных данных значительно преобразует выходное значение. Эффект лавины в хеш-функции SHA-256 выглядит следующим образом:

Электронная цифровая подпись для чайников: с чем ее есть и как не подавиться. часть 3

Часть 1
Часть 2

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

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

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

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

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

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

А почему бы не сделать так, чтобы способ шифрования был сразу известен всем, но расшифровать наши данные было бы нельзя без какого-то ключа? Ведь ключ (в отличие от всего алфавита) маленький, его достаточно легко сделать новый, если что (опять же, в отличие от переработки всего алфавита), легко спрятать. Наиболее наглядно плюсы ключевых систем показывает следующий пример: получателю надо прочитать сосланное вами сообщение. Обычное, на бумаге. Допустим, вы используете секретный алфавит. Тогда, чтобы прочитать сообщение, получатель должен знать алфавит, иметь большой пыльный талмуд, в котором описаны способы расшифровки (ведь алфавит должен быть сложным, чтобы быть надежным) и понимать, как же с этим талмудом работать. С ключами же все проще: вы кладете сообщение в коробку с замком, а получателю достаточно просто вставить подходящий ключик, а знать, как же устроен замок ему совершенно но нужно.
Итак, общеизвестные «алфавиты» и ключи — механизм, существенно более удобный, чем просто алфавиты. Но как же так зашифровать, чтобы все расшифровывалось простым ключом? И вот тут нам на помощь приходит математика, а конкретнее – математические функции, которые можно использовать для замены наших исходных символов на новые.

Вспомним же, что такое функция. Это некоторое соотношение, по которому из одного числа можно получить другое. Зная x и подставляя его в известное нам соотношение y=A*x, мы всегда получим значение y. Но ведь, как правило, верно и обратное: зная y, мы можем получить и x.
Как правило, но далеко не всегда. Для многих зависимостей получить y легко, тогда как x – уже очень трудно, и его получение займет продолжительное время. Вот именно на таких зависимостях и базируется используемое сейчас шифрование.

Но, вернемся к самому шифрованию. Шифрование подразделяют на симметричное, асимметричное и комбинированное. Рассмотрим, в чем суть каждого из них.

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

Асимметричное шифрование поступает несколько хитрее. Здесь и у нас, и у нашего получателя есть уже два ключа, которые называют открытый и закрытый. Закрытый ключ мы и получатель храним у себя (заметьте, каждый хранит только свой ключ, а значит, мы уже выходим за пределы той самой поговорки про двоих знающих), а открытый мы и получатель можем спокойно передавать кому угодно – наш закрытый, секретный, по нему восстановить нельзя. Итого, мы используем открытый ключ получателя для шифрования, а получатель, в свою очередь, использует свой закрытый ключ для расшифровывания. Плюс данного подхода очевиден: мы легко можем начать обмениваться секретной информацией с разными получателями, практически ничем (принимая условие, что наш получатель свой закрытый ключ не потерял/отдал и т.п., то есть не передал его в руки нехорошего человека) не рискуем при передаче информации. Но, без огромного минуса не обойтись. И здесь он в следующем: шифрование и расшифровывание в данном случае идут очень, очень, очень медленно, на два-три порядка медленнее, чем аналогичные операции при симметричном шифровании. Кроме того, ресурсов на это шифрование тратится также значительно больше. Да и сами ключи для данных операций существенно длиннее аналогичных для операций симметричного шифрования, так как требуется максимально обезопасить закрытый ключ от подбора по открытому. А значит, большие объемы информации данным способом шифровать просто невыгодно.
Хэш-функция
Пример использования асимметричного шифрования [Wikipedia]
e — открытый ключ получателя B
d — закрытый ключ получателя B
m — исходная информация отправителя A
c — зашифрованная исходная информация

И снова возникает вопрос: что же делать? А делать нужно следующее: взять, и скомбинировать оба способа. Собственно, так мы и получаем комбинированное шифрование. Наш большой объем данных мы зашифруем по первому способу, а чтобы донести ключ, с помощью которого мы их зашифровали, до получателя, мы сам ключ зашифруем по второму способу. Тогда и получим, что хоть асимметричное шифрование и медленное, но объем зашифрованных данных (то есть ключа, на котором зашифрованы большие данные) будет маленьким, а значит расшифровывание пройдет достаточно быстро, и дальше уже в дело вступит более быстрое симметричное шифрование.

Хэш-функция
Пример применения комбинированной системы [Wikipedia]

Все эти механизмы нашли свое применение на практике, и оба наших больших лагеря PGP и S/MIME их используют. Как говорилось в первой статье, асимметричное шифрование используется для цифровой подписи (а именно, для шифрования нашего хэша). Отличие данного применения от обычного асимметричного шифрования в том, что для шифрования используется наш закрытый ключ, а для расшифровывания достаточно наличие связанного с ним (то есть, тоже нашего) открытого ключа. Поскольку открытый ключ мы не прячем, наш хэш можем прочитать кто угодно, а не только отдельный получатель, что и требуется для цифровой подписи.
Комбинированное же шифрование применяется в обоих стандартах непосредственно для шифрования отправляемых данных.

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector