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

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

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

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

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

В конце мы даже зашифруем/рассшифруем какое нибудь небольшое сообщение.

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

Цель статьи не сделать вас гуру криптографии и ECC в частности, нельзя объять необъятное в одной статье. Цель — дать представление и показать направление, а дальше уж сами. Англоязычных материалов полный интернет, да и википедия не зря существует.

Хватит вступлений, давайте сначала вспомним как выглядит окружность математически.

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

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

Как вы знаете, в математике формула окружности выглядит как-то вот так:

Если перед иксом или игреком подставлять какие-нибудь множители, неравные друг другу, то окружность станет эллипсом. Однако в конечных полях всё будет немного не так.

Теперь вкратце о полях Галуа.

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

Вся их фишка в том, что при раскладе a mod p, а не может быть больше p. Давайте рассмотрим на примере:

3 mod 5. Если мы добавим к трём единицу, то получится 4 mod 5, если ещё одну, то выйдет 5 mod 5. Так как 5=5, то буфер как бы переполняется и у нас получается 0 mod 5. При следующей инкрементации у нас выйдет 1. И так далее.

Если кто не понял, то mod это тоже самое, что и оператор деления с остатком в программировании — т.*е. 7 mod 5 эквивалентно 7%5 и в обоих случаях выходит 2.

Вообщем выходит, что ECC это точно такой же эллипс, но только в полях Галуа.

В этой геометрической фигуре для нас важны 2 типа операций — сложение и умножение, которое в случае ECC является ничем иным как дублированием, т.е. умножением точки саму на себя.

На вышеуказанном рисунке красный цвет показывает, как происходит сложение точек, зелёный — умножение.

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

Далее, мы с вами наконец перейдём уже к вычислениям, а там недалеко уже и до шифрования наконец.

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


На что стоит обратить внимание:

1 Значение s, которое вычисляется в зависимости от требуемой операции (сложение точки либо умножение)

2 Инверсия по модулю. Для подсчёта инверсии по модулю существует несколько алгоритмов, например усовершенствованный алгоритм Евклида ака EEA, либо малая теорема Ферма ну и ещё несколько, о которых вы при желании сможете узнать в гугле/википедии.

Вдаваться в подробности не буду, это наверное тема отдельной статьи. Для подсчёта инверсии по модулю будем просто пользоваться онлайн калькулятором (который сделал тоже я) по ссылке http://modinverse.110mb.com/ (можно найти любой другой, воспользовавшись гуглом)

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

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

Формулы есть, теперь попробуем рассмотреть всё на пример какой нибудь кривой ну и заодно зашифруем/рассшифруем какое-нибудь слово.

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

Для обмена ключами между сторонами А и В, которых в криптографии всегда называют Элис и Боб, требуется точка альфа и по случайному числу-ключу для каждой из сторон, это будут их приватные ключи.

На схеме это выглядит так:

С Элис всё просто, точку пришлось просто умножить один раз саму на себя (смотрим формулу, дублируем точку, всё просто).

У Боба немного сложнее, чтобы точку умножить саму на себя 7 раз требуется немного большая работа.

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

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

Ну и теперь мы возьмём какое-нибудь коротенькое слово и зашифруем его для общей картины.

Возьмём к примеру слово КОНЕЦ. Каждой букве присвоим её номер, начиная с А=0.

Для шифрования/дешифрования нам нужны уже другие ф-ции, возьмём например такие:

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

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

Теперь попробуем в обратную сторону.

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

Посчитали, инверсия равна 20.

Теперь опять немного математики:

Как видим, всё сходится.

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

Задавайте вопросы, постараюсь ответить на адекватные.

ссылки на статейку в пдф, если кому удобнее -

http://www.mediafire.com/?u46nj7ds0d4qo59