Математические основы защиты информации. Ишмухаметов Ш.Т - 86 стр.

UptoLike

ВУЗ: 

КФУ | Казань

Составители: 

Рубрика: 

Глава 3. Эллиптические кривые 87
и возведения в квадрат элементов поля. Операцию умножения будем
обозначать буквой M (от англ. multiplication), а возведение в квадрат буквой
S (от англ. squaring). Умножения на небольшую константу и сложения
мы не учитываем, поскольку эти операции имеют линейную сложность
относительно длины элементов поля в то время, как операции умножения и
возведения в квадрат имеют квадратичную сложность относительно длины
элементов поля. Операция возведения в квадрат выполняется быстрее, чем
операция умножения, и ее сложность составляет примерно от 0,6 до 0,8 от
сложности умножения.
Expression M S
A
1
= 3X
2
+ aZ
2
0 2
B
1
= 2Y
1
Z
1
1 0
T
1
= Y
1
B
1
1 0
T
2
= 2X
1
T
1
1 0
T
3
= A
2
1
0 1
X
2
= B
1
(T
3
− 2T
2
) 1 0
T
4
= T
2
1
0 1
Y
2
= A
1
(3T
2
− T
3
) − T
4
1 0
Z
2
= B
3
1
1 1
Всего 6 5
Выполним те же расчеты для суммы точек.
λ = (y
2
− y
1
)/(x
2
− x
1
) = (Y
2
Z
1
− Y
1
Z
2
)/(X
2
Z
1
− X
1
Z
2
) = A/B,
x
3
= λ
2
− X
1
/Z
1
− X
2
/Z
2
= A
2
/B
2
− (X
1
Z
2
+ X
2
Z
1
)/Z
1
Z
2
y
3
= A(B
2
(2X
1
Z
2
+ X
2
Z
1
) − A
2
Z
1
Z
2
)/B
3
Z
1
Z
2
− Y
1
/Z
1
Умножая координаты x
3
и y
3
на общий знаменатель B
3
1
Z
1
Z
2
, получим
Глава 3. Эллиптические кривые                                            87

и возведения в квадрат элементов поля. Операцию умножения будем
обозначать буквой M (от англ. multiplication), а возведение в квадрат буквой
S (от англ. squaring). Умножения на небольшую константу и сложения
мы не учитываем, поскольку эти операции имеют линейную сложность
относительно длины элементов поля в то время, как операции умножения и
возведения в квадрат имеют квадратичную сложность относительно длины
элементов поля. Операция возведения в квадрат выполняется быстрее, чем
операция умножения, и ее сложность составляет примерно от 0,6 до 0,8 от
сложности умножения.

        Expression                 M S
        A1 = 3X 2 + aZ 2           0   2
        B1 = 2Y1 Z1                1   0
        T1 = Y1 B1                 1   0
        T2 = 2X1 T1                1   0
        T3 = A21                   0   1
        X2 = B1 (T3 − 2T2 )        1   0
        T4 = T12                   0   1
        Y2 = A1 (3T2 − T3 ) − T4   1   0
        Z2 = B13                   1   1
        Всего                      6   5

       Выполним те же расчеты для суммы точек.


 λ = (y2 − y1 )/(x2 − x1 ) = (Y2 Z1 − Y1 Z2 )/(X2 Z1 − X1 Z2 ) = A/B,

   x3 = λ2 − X1 /Z1 − X2 /Z2 = A2 /B 2 − (X1 Z2 + X2 Z1 )/Z1 Z2


 y3 = A(B 2 (2X1 Z2 + X2 Z1 ) − A2 Z1 Z2 )/B 3 Z1 Z2 − Y1 /Z1

       Умножая координаты x3 и y3 на общий знаменатель B13 Z1 Z2 , получим

Страницы