Авторские статьи ECC (Эллиптические кривые)

Discussion in 'Статьи' started by SwirlStick, 5 Jun 2011.

  1. SwirlStick

    SwirlStick Banned

    Joined:
    25 May 2011
    Messages:
    9
    Likes Received:
    16
    Reputations:
    20
    Скучным осенним вечером ко мне в форточку на 9ом этаже постучался мой друг с апельсиновым соком и я решил, что пора написать уже наконец статью.

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

    Эллиптические кривые (ECC) относительно новое направление в криптографии, однако в некоторых странах уже официально шифруют секретные государственные данные именно этим способом.
    В доке будут всякие рисунки, схемы, не знаю в какой программе их рисовать, так что нарисую просто на бумажке, сфоткаю на айфон и вставлю так. Так что не ругайтесь на почерк хихихи.
    Ещё для всяких криптографических вычислений могут понадобиться знания некоторых тонкостей вычислений в конечных полях, но не пугайтесь, я попробую всё прояснить.
    В конце мы даже зашифруем/рассшифруем какое нибудь небольшое сообщение.
    Так же замечу, что ECC требует ключи меньшего размера по сравнению с RSA при этом обеспечивая равно, а может быть и выше равного эффективность и надёжность.
    Цель статьи не сделать вас гуру криптографии и ECC в частности, нельзя объять необъятное в одной статье. Цель — дать представление и показать направление, а дальше уж сами. Англоязычных материалов полный интернет, да и википедия не зря существует.

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

    Как вы знаете, в математике формула окружности выглядит как-то вот так: [​IMG]
    Если перед иксом или игреком подставлять какие-нибудь множители, неравные друг другу, то окружность станет эллипсом. Однако в конечных полях всё будет немного не так.

    Теперь вкратце о полях Галуа.
    Когда мы считаем числа, то мы можем просто считать их до бесконечности, что бесполезно в криптографии. Но один чувак по имени Эварист Галуа, в 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 это точно такой же эллипс, но только в полях Галуа.

    Графически формула кривой выглядит примерно вот так:
    [​IMG]
    Операции в ECC

    [​IMG]
    В этой геометрической фигуре для нас важны 2 типа операций — сложение и умножение, которое в случае ECC является ничем иным как дублированием, т.е. умножением точки саму на себя.
    На вышеуказанном рисунке красный цвет показывает, как происходит сложение точек, зелёный — умножение.
    По сути, если вы хотите считать и шифровать/дешифровать всё побыстрее, никакой пользы это вам не даёт, однако я надеюсь, что кому-то интересна ещё и математическая сторона вопроса.
    Далее, мы с вами наконец перейдём уже к вычислениям, а там недалеко уже и до шифрования наконец.
    Вы кстати сможете встраивать подобные алгоритмы в ваши крипторы и прочея, дабы взбудоражить общественность антивирусов. Но это чуть позже, а пока давайте посмотрим на формулы, необходимые для вычисления точек на кривой.

    [​IMG]

    На что стоит обратить внимание:
    1 Значение s, которое вычисляется в зависимости от требуемой операции (сложение точки либо умножение)
    2 Инверсия по модулю. Для подсчёта инверсии по модулю существует несколько алгоритмов, например усовершенствованный алгоритм Евклида ака EEA, либо малая теорема Ферма ну и ещё несколько, о которых вы при желании сможете узнать в гугле/википедии.
    Вдаваться в подробности не буду, это наверное тема отдельной статьи. Для подсчёта инверсии по модулю будем просто пользоваться онлайн калькулятором (который сделал тоже я) по ссылке http://modinverse.110mb.com/ (можно найти любой другой, воспользовавшись гуглом)
    Если в кратце, то суть этой инверсии в том, что инверсия числа умноженная на само число даёт единицу. В этом трюке кстати вся соль наверное всех алгоритмов с ассиметричным шифрованием, даже таких как например RSA.
    Для более углубленного понимания рекомендую почитать книжки по теории чисел.

    Формулы есть, теперь попробуем рассмотреть всё на пример какой нибудь кривой ну и заодно зашифруем/рассшифруем какое-нибудь слово.
    Это будет нашей тестовой кривой. Числа в примере совсем маленькие, чтобы было удобно считать. На практике, конечно, используются числа побольше.
    [​IMG]
    Для обмена ключами между сторонами А и В, которых в криптографии всегда называют Элис и Боб, требуется точка альфа и по случайному числу-ключу для каждой из сторон, это будут их приватные ключи.
    На схеме это выглядит так:
    [​IMG]
    С Элис всё просто, точку пришлось просто умножить один раз саму на себя (смотрим формулу, дублируем точку, всё просто).
    У Боба немного сложнее, чтобы точку умножить саму на себя 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
    Для шифрования/дешифрования нам нужны уже другие ф-ции, возьмём например такие:
    [​IMG]
    Модуль 33 взят, как можно догадаться, по той причине, что в русском алфавите всего 33 буквы.
    Далее, после несложной математики мы получаем следующие результаты для каждой буквы:
    PHP:
    К 26
    О 
    13
    Н 
    8
    Е 
    29
    Ц — 20
    Теперь попробуем в обратную сторону.
    Для расшифровки требуется высчитать инверсию общего ключа, 5 в минус первой степени по модулю 33 в нашем случае.
    Посчитали, инверсия равна 20.
    Теперь опять немного математики:
    PHP:
    К 11
    О 
    15
    Н 
    14
    Е 
    5
    Ц — 23

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

    ссылки на статейку в пдф, если кому удобнее -
    http://www.mediafire.com/?u46nj7ds0d4qo59
     
    10 people like this.
  2. LastName

    LastName New Member

    Joined:
    4 May 2011
    Messages:
    19
    Likes Received:
    1
    Reputations:
    0
    Молодец, интересно.
     
  3. AlonDelon

    AlonDelon Member

    Joined:
    12 Nov 2010
    Messages:
    336
    Likes Received:
    18
    Reputations:
    -3
    это жесть.
     
  4. heJiZzZ

    heJiZzZ Member

    Joined:
    1 Jun 2009
    Messages:
    58
    Likes Received:
    18
    Reputations:
    10
    не осилил (

    Ачат - форум математиков!
     
  5. Root-access

    Root-access Elder - Старейшина

    Joined:
    18 Jun 2008
    Messages:
    194
    Likes Received:
    195
    Reputations:
    91
    Вроде как статья предназначена для людей, не очень знакомых с предметом, но написано совершенно непонятно, криво, без никаких объяснений, тема не раскрыта.

    Можно было просто написать: "Читайте книжку по криптографии". И всё. Эффект тот же.
     
    1 person likes this.
  6. ShaltaiB

    ShaltaiB New Member

    Joined:
    19 Nov 2010
    Messages:
    3
    Likes Received:
    0
    Reputations:
    0
    При всем желании, вроде не совсем дурак и образование техническое. Но многое тут так и не понял.
     
  7. LastName

    LastName New Member

    Joined:
    4 May 2011
    Messages:
    19
    Likes Received:
    1
    Reputations:
    0
    Вы бы лучше спрашивали что конкретно непонятно, а там глядишь бы и допилили что неясно. Лично я основную идею и ее реализацию из статьи понял, остальное если понадобится буду изучать более глубоко.
     
  8. Amur[чик]

    Amur[чик] New Member

    Joined:
    11 May 2011
    Messages:
    25
    Likes Received:
    1
    Reputations:
    -5
    в принципе все понятно ... по крайней мере мне :) хотя я это знал и до прочтения статьи :cool:
     
  9. GrAmOzEkA

    GrAmOzEkA Elder - Старейшина

    Joined:
    25 Jun 2006
    Messages:
    235
    Likes Received:
    76
    Reputations:
    29
    Не плохая статья для людей знающих матан, остальным не понять :)
     
  10. Lee_fx

    Lee_fx Elder - Старейшина

    Joined:
    27 Sep 2008
    Messages:
    90
    Likes Received:
    14
    Reputations:
    0
    а где он здесь, уважаемый?)
     
  11. zannussi

    zannussi Elder - Старейшина

    Joined:
    22 May 2008
    Messages:
    0
    Likes Received:
    12
    Reputations:
    1
    Прочитал, очень интересно.
    Что-то я не припомню в своем курсе подобного (может потому, что было ооочень много алгоритмов)
    GrAmOzEkA, это скорее не матан ) это теория чисел, в честности теория полей )
    Сейчас летняя расслабленность, но пару вопросов появилось:
    на счет р
    [​IMG]
    и потом у нас р=33.
    a,b,p и точка альфа - это заранее известные величины, как я понял (следуя принципу Кергхоффса) или все же альфа - это секрет, так же как и закрытый ключ?
    --------------------------
    и еще ... р - не должно быть простым?
    все для того, чтоб для любого элемента поля (mod p) был обратаный элемент
     
    #11 zannussi, 6 Jun 2011
    Last edited: 7 Jun 2011
  12. RexTiam

    RexTiam Member

    Joined:
    2 Nov 2009
    Messages:
    115
    Likes Received:
    45
    Reputations:
    5
    очень понравилось, с криптографией не сильно знаком

    долго думал над

    опиши на лёгком примере типа...пошёл в магазин..
     
  13. SwirlStick

    SwirlStick Banned

    Joined:
    25 May 2011
    Messages:
    9
    Likes Received:
    16
    Reputations:
    20
    Секретный только приватный ключ, всё остальное открыто, согласно вышеупомянутому принципу.
    p как раз таки дожно быть простым.
    Ну ок, это примерно как часы и минуты:
    Допустим время у нас 7 часов, 58 минут - через минуту станет 7 часов 59 минут, ещё через одну - 8:00. Точно такой же принцип действует и в конечных полях, за тем лишь исключением, что так называемые"часы" не имеют значения.
     
  14. YaBtr

    YaBtr Members of Antichat

    Joined:
    30 May 2012
    Messages:
    601
    Likes Received:
    350
    Reputations:
    652
    Вчера приводил документы свои в порядок и нашел старую программку, которая наглядно показывает работу систем на базе эллиптических кривых. Сразу захотел написать статью об ecc, но, к сожалению ОЧЕНЬ не успел :)
    Программа была написана года 2-3 назад,так что много косячков.
    В 2012 году был принят новый стандарт цифровой подриси ГОСТ 34.10-2012, поэтому тема очень даже актуальна. Любителям матана и абстрактной алгебры понравится :)

    Пароль antichat2013