66)Эллиптические кривые. Назначение. Уравнения. Виды. Свойства

Эллиптической кривой Е называется кривая, задаваемая уравнением вида:

аi – некоторые константы.

Обычно используется кривая следующего вида.

Е: у²= х³+aх+b

Эта кривая симметрична оси ОХ что-бы найти кривую необходимо найти кубическое уравнение.

Поскольку Y= ^{± корень} (х³+ах+b), график кривой. Что-бы найти точки его пересекают с осью ОХ необходимо кубическое уравнение:

Р=4а³+27b²

Если дискриминант D<0 два корня

При D=0 корней 3 и по крайней мере 2 равны

При D>0 корень один

67).Криптосистемы на основе эллиптических кривых

68).Кривые над конечными полями. Поле . Поле .

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

- для ЕСС используется поля F_р (р- простое число) F_2^m.

Поле F_р: -элементы поля числа 0,1,…,р-1

- все операции выполняются по модулю р

- сумма х и у есть (х+у) mod p, произведение х и у х*у mod p

- обратное к х есть такое число х^-1 из F_р что х*х^-1 mod p =1

- частное х и у есть х*у^-1 mod p

Кривая над F_p уравнение рассматриваемое по модулю р

у²= х³+ахb (mod p)

Поле F_2^m: - элементы поля 0,1, … , 2^m-1

- элементы можно считать бинарными векторами длины m

- координаты векторов соответствуют коэффициенту многочлена степени m-1, поэтому элементы поля можно считать многочленами

- все операции выполняются по модулю специального многочлена степени m, фиксированного для поля

- все операции сводятся к целочисленной арифметике по модулю 2^m.

69).Задача о дискретном логарифме. Использование ecc.

В основе любой криптосистеме лежит задача, для котор не известны эффективные методы решения. В основе ЕСС лежит задача о дискретном логарифме.

Точки кривой можно умножать на число: P+P+…+P=KP=Q

Проблема если известны Р и Q как определить К за разумное время?

Максимальны размер поля, для которого был дискретный логарифм , имеет длину 112 бит, Вычисление заняло около 6 месяцев на кластере из двухсот консолей Play Station 3.

Применение ЕСС.

- Стороны должны договариваться об общем наборе параметров.

- Для F_p: (р,а,b,G,n,h ) p- простое число, размер поля.

а,b- коэффициенты уравнения кривой, G- точка на кривой ( гениратор)

n- такое число, что nG=0 (порядок кривой)

- h=E(F_p)/n-сомножитель где Е(F_p)- числовая точка кривой.

-Для F_2^m: (m,f(x),a,b,G,n,h)

m- простое число

f(x)- не сократимый многочлен степени m, играет роль модуля при операциях

остальные анологично параметрам F_p

70).Алгоритм Диффи – Хеллмана. Формирование цифровой подписи.

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

Использование алгоритма Диффи-Хеллмана не ограничивается двумя участниками. Он может быть применен на неограниченное количество пользователей. Рассмотрим ситуацию, когда Алиса, Боб и Кэрол вместе генерируют исходный ключ. В данном случае последовательность действий будет следующая:

1. Стороны договариваются о параметрах алгоритма p и g

2. Стороны генерируют свои ключи — a, b и c

3. Алиса вычисляет  и посылает его Бобу

4. Боб вычисляет = и посылает его Кэрол

5. Боб вычисляет и посылает его Кэрол

6. Кэрол вычисляет и посылает его Алисе.

7. Алиса вычисляет и использует его как свою тайну.

8. Кэрол вычисляет и посылает его Алисе

9. Алиса вычисляет и посылает его Бобу

10. Боб вычисляет и использует его как свою тайну

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

-Передача ключа должна начинаться с «пустого» ключа g. Весь секрет состоит в повышении текущего значения показателя каждого участника один раз;

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