SwirlStick
05.06.2011, 03:39
Скучным осенним вечером ко мне в форточку на 9ом этаже постучался мой друг с апельсиновым соком и я решил, что пора написать уже наконец статью.
На самом деле, я решил написать всё это, потому что тема эллиптических кривых показалась мне действительно интересной ну и чтобы в рунете была дока по ECC с примерами. На примерах всё гораздо легче понимается, нежели просто в теории.
Эллиптические кривые (ECC)относительно новое направление в криптографии, однако в некоторых странах уже официально шифруют секретные государственные данные именно этим способом.
В доке будут всякие рисунки, схемы, не знаю в какой программе их рисовать, так что нарисую просто на бумажке, сфоткаю на айфон и вставлю так. Так что не ругайтесь на почерк хихихи.
Ещё для всяких криптографических вычислений могут понадобиться знания некоторых тонкостей вычислений в конечных полях, но не пугайтесь, я попробую всё прояснить.
В конце мы даже зашифруем/рассшифруем какое нибудь небольшое сообщение.
Так же замечу, что ECC требует ключи меньшего размера по сравнению с RSA при этом обеспечивая равно, а может быть и выше равного эффективность и надёжность.
Цель статьи не сделать вас гуру криптографии и ECC в частности, нельзя объять необъятное в одной статье. Цель — дать представление и показать направление, а дальше уж сами. Англоязычных материалов полный интернет, да и википедия не зря существует.
Хватит вступлений, давайте сначала вспомним как выглядит окружность математически.
Кстати да, кое-какие азы математики всё же нужны, поэтому все слабаки, которые срезались в 7ом классе на дробях можете идти дальше спамить вконтакти или что вы там ещё делаете.
Итак, криптография это увлекательно, полезно и интересно и всё такое, давайте наконец уже начнём.
Как вы знаете, в математике формула окружности выглядит как-то вот так: http://img834.imageshack.us/img834/5719/circlek.jpg
Если перед иксом или игреком подставлять какие-нибудь множители, неравные друг другу, то окружность станет эллипсом. Однако в конечных полях всё будет немного не так.
Теперь вкратце о полях Галуа.
Когда мы считаем числа, то мы можем просто считать их до бесконечности, что бесполезно в криптографии. Но один чувак по имени Эварист Галуа, в 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 это точно такой же эллипс, но только в полях Галуа.
Графически формула кривой выглядит примерно вот так:
http://img220.imageshack.us/img220/1218/eccy.jpg
Операции в ECC
http://img691.imageshack.us/img691/7706/img0523ae.jpgВ этой геометрической фигуре для нас важны 2 типа операций — сложение и умножение, которое в случае ECC является ничем иным как дублированием, т.е. умножением точки саму на себя.
На вышеуказанном рисунке красный цвет показывает, как происходит сложение точек, зелёный — умножение.
По сути, если вы хотите считать и шифровать/дешифровать всё побыстрее, никакой пользы это вам не даёт, однако я надеюсь, что кому-то интересна ещё и математическая сторона вопроса.
Далее, мы с вами наконец перейдём уже к вычислениям, а там недалеко уже и до шифрования наконец.
Вы кстати сможете встраивать подобные алгоритмы в ваши крипторы и прочея, дабы взбудоражить общественность антивирусов. Но это чуть позже, а пока давайте посмотрим на формулы, необходимые для вычисления точек на кривой.
http://img696.imageshack.us/img696/7742/eccformulas.jpg
На что стоит обратить внимание:
1 Значение s, которое вычисляется в зависимости от требуемой операции (сложение точки либо умножение)
2 Инверсия по модулю. Для подсчёта инверсии по модулю существует несколько алгоритмов, например усовершенствованный алгоритм Евклида ака EEA, либо малая теорема Ферма ну и ещё несколько, о которых вы при желании сможете узнать в гугле/википедии.
Вдаваться в подробности не буду, это наверное тема отдельной статьи. Для подсчёта инверсии по модулю будем просто пользоваться онлайн калькулятором (который сделал тоже я) по ссылке http://modinverse.110mb.com/ (можно найти любой другой, воспользовавшись гуглом)
Если в кратце, то суть этой инверсии в том, что инверсия числа умноженная на само число даёт единицу. В этом трюке кстати вся соль наверное всех алгоритмов с ассиметричным шифрованием, даже таких как например RSA.
Для более углубленного понимания рекомендую почитать книжки по теории чисел.
Формулы есть, теперь попробуем рассмотреть всё на пример какой нибудь кривой ну и заодно зашифруем/рассшифруем какое-нибудь слово.
Это будет нашей тестовой кривой. Числа в примере совсем маленькие, чтобы было удобно считать. На практике, конечно, используются числа побольше.
http://img17.imageshack.us/img17/1892/primerr.jpgДля обмена ключами между сторонами А и В, которых в криптографии всегда называют Элис и Боб, требуется точка альфа и по случайному числу-ключу для каждой из сторон, это будут их приватные ключи.
На схеме это выглядит так:
http://img263.imageshack.us/img263/2262/keychange.jpgС Элис всё просто, точку пришлось просто умножить один раз саму на себя (смотрим формулу, дублируем точку, всё просто).
У Боба немного сложнее, чтобы точку умножить саму на себя 7 раз требуется немного большая работа.
7P =
1. P*P = 2P;
2. 2P+P = 3P;
3. 3P * 2P = 6P;
4. 6P + P = 7P;
Да, выглядит весьма ресурсоёмко, однако из-за того, что ключи требуются меньшие, ECC всё равно выигрывают по скорости вычислений многие другие алгоритмы с большей длинной ключа.
После того, как стороны обменялись паблик-ключами, они могут высчитать общий ключ и использовать одну его координату для шифрования/дешифрования непосредственно. В нашем случае мы воспользуемся y-координатой.
Ну и теперь мы возьмём какое-нибудь коротенькое слово и зашифруем его для общей картины.
Возьмём к примеру слово КОНЕЦ. Каждой букве присвоим её номер, начиная с А=0.
К-11
О-15
Н-14
Е-5
Ц — 23
Для шифрования/дешифрования нам нужны уже другие ф-ции, возьмём например такие:
http://img814.imageshack.us/img814/7081/lettersp.jpgМодуль 33 взят, как можно догадаться, по той причине, что в русском алфавите всего 33 буквы.
Далее, после несложной математики мы получаем следующие результаты для каждой буквы:
К-26
О-13
Н-8
Е-29
Ц — 20
Теперь попробуем в обратную сторону.
Для расшифровки требуется высчитать инверсию общего ключа, 5 в минус первой степени по модулю 33 в нашем случае.
Посчитали, инверсия равна 20.
Теперь опять немного математики:
К-11
О-15
Н-14
Е-5
Ц — 23
http://img269.imageshack.us/img269/8097/ghcimath.jpgКак видим, всё сходится.
Вообщем всё довольно просто, если может быть не считать специфической для криптографии арифметики. Про неё можно прочитать подробнее в любой книжке по теории чисел.
Задавайте вопросы, постараюсь ответить на адекватные.
ссылки на статейку в пдф, если кому удобнее -
http://www.mediafire.com/?u46nj7ds0d4qo59
На самом деле, я решил написать всё это, потому что тема эллиптических кривых показалась мне действительно интересной ну и чтобы в рунете была дока по ECC с примерами. На примерах всё гораздо легче понимается, нежели просто в теории.
Эллиптические кривые (ECC)относительно новое направление в криптографии, однако в некоторых странах уже официально шифруют секретные государственные данные именно этим способом.
В доке будут всякие рисунки, схемы, не знаю в какой программе их рисовать, так что нарисую просто на бумажке, сфоткаю на айфон и вставлю так. Так что не ругайтесь на почерк хихихи.
Ещё для всяких криптографических вычислений могут понадобиться знания некоторых тонкостей вычислений в конечных полях, но не пугайтесь, я попробую всё прояснить.
В конце мы даже зашифруем/рассшифруем какое нибудь небольшое сообщение.
Так же замечу, что ECC требует ключи меньшего размера по сравнению с RSA при этом обеспечивая равно, а может быть и выше равного эффективность и надёжность.
Цель статьи не сделать вас гуру криптографии и ECC в частности, нельзя объять необъятное в одной статье. Цель — дать представление и показать направление, а дальше уж сами. Англоязычных материалов полный интернет, да и википедия не зря существует.
Хватит вступлений, давайте сначала вспомним как выглядит окружность математически.
Кстати да, кое-какие азы математики всё же нужны, поэтому все слабаки, которые срезались в 7ом классе на дробях можете идти дальше спамить вконтакти или что вы там ещё делаете.
Итак, криптография это увлекательно, полезно и интересно и всё такое, давайте наконец уже начнём.
Как вы знаете, в математике формула окружности выглядит как-то вот так: http://img834.imageshack.us/img834/5719/circlek.jpg
Если перед иксом или игреком подставлять какие-нибудь множители, неравные друг другу, то окружность станет эллипсом. Однако в конечных полях всё будет немного не так.
Теперь вкратце о полях Галуа.
Когда мы считаем числа, то мы можем просто считать их до бесконечности, что бесполезно в криптографии. Но один чувак по имени Эварист Галуа, в 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 это точно такой же эллипс, но только в полях Галуа.
Графически формула кривой выглядит примерно вот так:
http://img220.imageshack.us/img220/1218/eccy.jpg
Операции в ECC
http://img691.imageshack.us/img691/7706/img0523ae.jpgВ этой геометрической фигуре для нас важны 2 типа операций — сложение и умножение, которое в случае ECC является ничем иным как дублированием, т.е. умножением точки саму на себя.
На вышеуказанном рисунке красный цвет показывает, как происходит сложение точек, зелёный — умножение.
По сути, если вы хотите считать и шифровать/дешифровать всё побыстрее, никакой пользы это вам не даёт, однако я надеюсь, что кому-то интересна ещё и математическая сторона вопроса.
Далее, мы с вами наконец перейдём уже к вычислениям, а там недалеко уже и до шифрования наконец.
Вы кстати сможете встраивать подобные алгоритмы в ваши крипторы и прочея, дабы взбудоражить общественность антивирусов. Но это чуть позже, а пока давайте посмотрим на формулы, необходимые для вычисления точек на кривой.
http://img696.imageshack.us/img696/7742/eccformulas.jpg
На что стоит обратить внимание:
1 Значение s, которое вычисляется в зависимости от требуемой операции (сложение точки либо умножение)
2 Инверсия по модулю. Для подсчёта инверсии по модулю существует несколько алгоритмов, например усовершенствованный алгоритм Евклида ака EEA, либо малая теорема Ферма ну и ещё несколько, о которых вы при желании сможете узнать в гугле/википедии.
Вдаваться в подробности не буду, это наверное тема отдельной статьи. Для подсчёта инверсии по модулю будем просто пользоваться онлайн калькулятором (который сделал тоже я) по ссылке http://modinverse.110mb.com/ (можно найти любой другой, воспользовавшись гуглом)
Если в кратце, то суть этой инверсии в том, что инверсия числа умноженная на само число даёт единицу. В этом трюке кстати вся соль наверное всех алгоритмов с ассиметричным шифрованием, даже таких как например RSA.
Для более углубленного понимания рекомендую почитать книжки по теории чисел.
Формулы есть, теперь попробуем рассмотреть всё на пример какой нибудь кривой ну и заодно зашифруем/рассшифруем какое-нибудь слово.
Это будет нашей тестовой кривой. Числа в примере совсем маленькие, чтобы было удобно считать. На практике, конечно, используются числа побольше.
http://img17.imageshack.us/img17/1892/primerr.jpgДля обмена ключами между сторонами А и В, которых в криптографии всегда называют Элис и Боб, требуется точка альфа и по случайному числу-ключу для каждой из сторон, это будут их приватные ключи.
На схеме это выглядит так:
http://img263.imageshack.us/img263/2262/keychange.jpgС Элис всё просто, точку пришлось просто умножить один раз саму на себя (смотрим формулу, дублируем точку, всё просто).
У Боба немного сложнее, чтобы точку умножить саму на себя 7 раз требуется немного большая работа.
7P =
1. P*P = 2P;
2. 2P+P = 3P;
3. 3P * 2P = 6P;
4. 6P + P = 7P;
Да, выглядит весьма ресурсоёмко, однако из-за того, что ключи требуются меньшие, ECC всё равно выигрывают по скорости вычислений многие другие алгоритмы с большей длинной ключа.
После того, как стороны обменялись паблик-ключами, они могут высчитать общий ключ и использовать одну его координату для шифрования/дешифрования непосредственно. В нашем случае мы воспользуемся y-координатой.
Ну и теперь мы возьмём какое-нибудь коротенькое слово и зашифруем его для общей картины.
Возьмём к примеру слово КОНЕЦ. Каждой букве присвоим её номер, начиная с А=0.
К-11
О-15
Н-14
Е-5
Ц — 23
Для шифрования/дешифрования нам нужны уже другие ф-ции, возьмём например такие:
http://img814.imageshack.us/img814/7081/lettersp.jpgМодуль 33 взят, как можно догадаться, по той причине, что в русском алфавите всего 33 буквы.
Далее, после несложной математики мы получаем следующие результаты для каждой буквы:
К-26
О-13
Н-8
Е-29
Ц — 20
Теперь попробуем в обратную сторону.
Для расшифровки требуется высчитать инверсию общего ключа, 5 в минус первой степени по модулю 33 в нашем случае.
Посчитали, инверсия равна 20.
Теперь опять немного математики:
К-11
О-15
Н-14
Е-5
Ц — 23
http://img269.imageshack.us/img269/8097/ghcimath.jpgКак видим, всё сходится.
Вообщем всё довольно просто, если может быть не считать специфической для криптографии арифметики. Про неё можно прочитать подробнее в любой книжке по теории чисел.
Задавайте вопросы, постараюсь ответить на адекватные.
ссылки на статейку в пдф, если кому удобнее -
http://www.mediafire.com/?u46nj7ds0d4qo59