Скучным осенним вечером ко мне в форточку на 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 это точно такой же эллипс, но только в полях Галуа. Графически формула кривой выглядит примерно вот так: Операции в ECC В этой геометрической фигуре для нас важны 2 типа операций — сложение и умножение, которое в случае ECC является ничем иным как дублированием, т.е. умножением точки саму на себя. На вышеуказанном рисунке красный цвет показывает, как происходит сложение точек, зелёный — умножение. По сути, если вы хотите считать и шифровать/дешифровать всё побыстрее, никакой пользы это вам не даёт, однако я надеюсь, что кому-то интересна ещё и математическая сторона вопроса. Далее, мы с вами наконец перейдём уже к вычислениям, а там недалеко уже и до шифрования наконец. Вы кстати сможете встраивать подобные алгоритмы в ваши крипторы и прочея, дабы взбудоражить общественность антивирусов. Но это чуть позже, а пока давайте посмотрим на формулы, необходимые для вычисления точек на кривой. На что стоит обратить внимание: 1 Значение s, которое вычисляется в зависимости от требуемой операции (сложение точки либо умножение) 2 Инверсия по модулю. Для подсчёта инверсии по модулю существует несколько алгоритмов, например усовершенствованный алгоритм Евклида ака EEA, либо малая теорема Ферма ну и ещё несколько, о которых вы при желании сможете узнать в гугле/википедии. Вдаваться в подробности не буду, это наверное тема отдельной статьи. Для подсчёта инверсии по модулю будем просто пользоваться онлайн калькулятором (который сделал тоже я) по ссылке http://modinverse.110mb.com/ (можно найти любой другой, воспользовавшись гуглом) Если в кратце, то суть этой инверсии в том, что инверсия числа умноженная на само число даёт единицу. В этом трюке кстати вся соль наверное всех алгоритмов с ассиметричным шифрованием, даже таких как например RSA. Для более углубленного понимания рекомендую почитать книжки по теории чисел. Формулы есть, теперь попробуем рассмотреть всё на пример какой нибудь кривой ну и заодно зашифруем/рассшифруем какое-нибудь слово. Это будет нашей тестовой кривой. Числа в примере совсем маленькие, чтобы было удобно считать. На практике, конечно, используются числа побольше. Для обмена ключами между сторонами А и В, которых в криптографии всегда называют Элис и Боб, требуется точка альфа и по случайному числу-ключу для каждой из сторон, это будут их приватные ключи. На схеме это выглядит так: С Элис всё просто, точку пришлось просто умножить один раз саму на себя (смотрим формулу, дублируем точку, всё просто). У Боба немного сложнее, чтобы точку умножить саму на себя 7 раз требуется немного большая работа. Code: 7P = 1. P*P = 2P; 2. 2P+P = 3P; 3. 3P * 2P = 6P; 4. 6P + P = 7P; Да, выглядит весьма ресурсоёмко, однако из-за того, что ключи требуются меньшие, ECC всё равно выигрывают по скорости вычислений многие другие алгоритмы с большей длинной ключа. После того, как стороны обменялись паблик-ключами, они могут высчитать общий ключ и использовать одну его координату для шифрования/дешифрования непосредственно. В нашем случае мы воспользуемся y-координатой. Ну и теперь мы возьмём какое-нибудь коротенькое слово и зашифруем его для общей картины. Возьмём к примеру слово КОНЕЦ. Каждой букве присвоим её номер, начиная с А=0. PHP: К - 11 О - 15 Н - 14 Е - 5 Ц — 23 Для шифрования/дешифрования нам нужны уже другие ф-ции, возьмём например такие: Модуль 33 взят, как можно догадаться, по той причине, что в русском алфавите всего 33 буквы. Далее, после несложной математики мы получаем следующие результаты для каждой буквы: PHP: К - 26 О - 13 Н - 8 Е - 29 Ц — 20 Теперь попробуем в обратную сторону. Для расшифровки требуется высчитать инверсию общего ключа, 5 в минус первой степени по модулю 33 в нашем случае. Посчитали, инверсия равна 20. Теперь опять немного математики: PHP: К - 11 О - 15 Н - 14 Е - 5 Ц — 23 Как видим, всё сходится. Вообщем всё довольно просто, если может быть не считать специфической для криптографии арифметики. Про неё можно прочитать подробнее в любой книжке по теории чисел. Задавайте вопросы, постараюсь ответить на адекватные. ссылки на статейку в пдф, если кому удобнее - http://www.mediafire.com/?u46nj7ds0d4qo59
Вроде как статья предназначена для людей, не очень знакомых с предметом, но написано совершенно непонятно, криво, без никаких объяснений, тема не раскрыта. Можно было просто написать: "Читайте книжку по криптографии". И всё. Эффект тот же.
Вы бы лучше спрашивали что конкретно непонятно, а там глядишь бы и допилили что неясно. Лично я основную идею и ее реализацию из статьи понял, остальное если понадобится буду изучать более глубоко.
Прочитал, очень интересно. Что-то я не припомню в своем курсе подобного (может потому, что было ооочень много алгоритмов) GrAmOzEkA, это скорее не матан ) это теория чисел, в честности теория полей ) Сейчас летняя расслабленность, но пару вопросов появилось: на счет р и потом у нас р=33. a,b,p и точка альфа - это заранее известные величины, как я понял (следуя принципу Кергхоффса) или все же альфа - это секрет, так же как и закрытый ключ? -------------------------- и еще ... р - не должно быть простым? все для того, чтоб для любого элемента поля (mod p) был обратаный элемент
очень понравилось, с криптографией не сильно знаком долго думал над опиши на лёгком примере типа...пошёл в магазин..
Секретный только приватный ключ, всё остальное открыто, согласно вышеупомянутому принципу. p как раз таки дожно быть простым. Ну ок, это примерно как часы и минуты: Допустим время у нас 7 часов, 58 минут - через минуту станет 7 часов 59 минут, ещё через одну - 8:00. Точно такой же принцип действует и в конечных полях, за тем лишь исключением, что так называемые"часы" не имеют значения.
Вчера приводил документы свои в порядок и нашел старую программку, которая наглядно показывает работу систем на базе эллиптических кривых. Сразу захотел написать статью об ecc, но, к сожалению ОЧЕНЬ не успел Программа была написана года 2-3 назад,так что много косячков. В 2012 году был принят новый стандарт цифровой подриси ГОСТ 34.10-2012, поэтому тема очень даже актуальна. Любителям матана и абстрактной алгебры понравится Пароль antichat2013
