 |
|
Цифровая подпись EC-DSA
В целом схема аналогична классической DSA, но вместо вычислительно затратной операции модульного экспоненцирования в конечном поле большой характеристики использует умножение точки на скаляр в аддитивной группе точек эллиптической кривой.
Каждый абонент системы генерирует секретный ключ
Открытый ключ Y представляет собой точку эллиптической кривой:
Абонент, желающий подписать сообщение M, выбирает сеансовый ключ:
Подпись представляет собой пару: 
- первая часть подписи, не зависящая от подписываемого сообщения. R служит для неявной передачи эфемерного ключа и, ввиду независимости от подписываемого сообщения, может быть выработано заранее в фоновом режиме.
- вторая часть подписи, связанная с сообщением M.
Для проверки подписи необходимо вычислить два промежуточных параметра:
Подпись считается верной при выполнении равенства:
Задача 5.4. Для заданной кривой E над конечным полем, ее точки P, порядка группы Q и открытого текста M, самостоятельно определить остальные параметры схемы электронно-цифровой подписи EC-DSA и осуществить подписание сообщения. Проверить правильность цифровой подписи. (При решении рекомендуется использовать программу на любом из языков программирования, реализующую сложение и удвоение точек кривой).
Пример решения [10]
Дано:
Q = 197
P(x, y) = P(1, 76)
M = 68, x = 29
| Решение:
|
| Найти: x, Y, k, R, S, A, B, R’ Проверить: R’ = R | |
|
Примеры листингов программ для решения задач 5.3, 5.4 приведены в приложениях 2 и 3.
Варианты заданий для пятой части
| Вариант | Задача 5.1 | Задача 5.2 | Задача 5.3 | Зад. 5.4 | ||||
| P1 | P2 | x | P | x | y | M | x | |
| (0, 1) | (18, 20) | (5, 4) | ||||||
| (1, 7) | (19, 5) | (5, 19) | ||||||
| (1, 22) | (19, 18) | (6, 4) | ||||||
| (3, 10) | (0, 22) | (6, 19) | ||||||
| (3, 13) | (0, 1) | (7, 11) | ||||||
| (5, 4) | (1, 7) | (7, 12) | ||||||
| (5, 19) | (1, 22) | (9, 7) | ||||||
| (6, 4) | (3, 10) | (9, 16) | ||||||
| (6, 19) | (3, 13) | (11, 3) | ||||||
| (7, 11) | (5, 4) | (11, 20) | ||||||
| (7, 12) | (5, 19) | (12, 4) | ||||||
| (9, 7) | (6, 4) | (12, 19) | ||||||
| (9, 16) | (6, 19) | (13, 7) | ||||||
| (11, 3) | (7, 11) | (13, 16) | ||||||
| (11, 20) | (7, 12) | (17, 3) | ||||||
| (12, 4) | (9, 7) | (17, 20) | ||||||
| (12, 19) | (9, 16) | (18, 3) | ||||||
| (13, 7) | (11, 3) | (18, 20) | ||||||
| (13, 16) | (11, 20) | (19, 5) | ||||||
| (17, 3) | (12, 4) | (19, 18) | ||||||
| (17, 20) | (12, 19) | (0, 22) | ||||||
| (18, 3) | (13, 7) | (0, 1) |
Примечания:
Для задач 5.1, 5.2: 
,
Для задач 5.3, 5.4: 
Q = 197, P(1, 76)
ЗАКЛЮЧЕНИЕ
Учебное пособие «Криптографические методы защиты информации» содержит материалы, которые следует использовать при изучении дисциплин криптографической направленности.
Изучение криптографии является одним из важнейших аспектов в специальной подготовке специалистов по защите информации [2]. Успешное освоение данного курса позволяет изучить современные методы криптографической защиты информации. Такие знания необходимы специалисту при разработке систем защиты информации на различных уровнях обеспечения информационной безопасности личности, организации и в целом Российской Федерации. Построение систем защиты информации в современных условиях становится все более актуальным ввиду того, что уровень развития средств несанкционированного добывания информации очень высок, доступность программных средств шпионского толка превращает задачу нелегального добывания информации из уникальной и рискованной операции в достаточно простую задачу. Это значительно увеличивает риск получения больших объемов информации злоумышленниками на безопасном расстоянии от её источников путем её перехвата при обработке и хранении. Практика показывает, что эффективная защита информации с учетом этих тенденций возможна при активном использовании криптографических методов и средств защиты информации.
Содержание предлагаемого учебного пособия не претендует на обобщение всего многообразия вопросов криптографической защиты информации, но авторы надеются, что их работа будет с благодарностью оценена всеми, кому приходится сталкиваться с решением задач информационной безопасности в рамках профессиональной деятельности.
Приложение 1.
Таблица простых чисел p до 997
Примечание: темным цветом выделены p º 3 (mod 4)
Приложение 2
Листинг программы для решения задач 5.3, 5.4 на языке C#
Программа реализует обобщенный алгоритм Евклида, сложение и удвоение точек.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
public class Operations
{
public int Mod(int a,int p)
{
if (a < 0) { a = a + p; }
return a;
}
public int Evc(int h, int k) //Алгоритм Евклида
{
int[,] mt = new int[20, 7];
for (int i = 0; i < 20; i++)
{
for (int j = 0; j < 7; j++) mt[i, j] = -1;
}
mt[0, 0] = 1;
mt[0, 1] = 0;
mt[0, 2] = h;
mt[0, 3] = 0;
mt[0, 4] = 1;
mt[0, 5] = k;
mt[0, 6] = (h - (h % k)) / k;
int n = 0;
while (mt[n, 5] != 0)
{
n++;
int m = 0;
for (m = 0; m < 3; m++)
{
mt[n, m] = mt[n - 1, m + 3];
}
for (m = 3; m < 6; m++)
{
mt[n, m] = mt[n - 1, m - 3] - mt[n - 1, m] * mt[n - 1, 6];
}
if (mt[n, 5] != 0)
{
mt[n, 6] = (mt[n, m - 4] - (mt[n, 2] % mt[n, 5])) / mt[n, 5];
}
}
k = mt[n - 1, 4];
if (k < 0) {k += h; }
return (k);
}
}
class Program
{
static void Main(string[] args)
{
Operations op1 = new Operations();
int x=0;
int y=0;
int k;
int p = 199;
Console.WriteLine("Если требуется удвоение, нажмите 0, если сложение 1");
k = Convert.ToInt32(Console.ReadLine());
if (k==0) //Удвоение
{
Console.WriteLine("Введите координаты, для удвоения");
int x1;
Console.Write("x1=");
x1 = Convert.ToInt32(Console.ReadLine());
int y1;
Console.Write("y1=");
y1 = Convert.ToInt32(Console.ReadLine());
int a;
int a1 = 2*y1 % p;
a1 = op1.Evc(p, a1);
a = (3 * x1 * x1) % p;
a = a + 1;
a = (a * a1) % p;
x = (a * a) % p;
x = x - ((2 * x1)%p);
x = op1.Mod(x, p);
y = x1 - x;
y = op1.Mod(y, p);
y = (y * a) % p;
y = y - y1;
y = op1.Mod(y, p);
}
else //Сложение
{
Console.WriteLine("Введите координаты, для сложения");
int x1;
Console.Write("x1=");
x1 = Convert.ToInt32(Console.ReadLine());
int y1;
Console.Write("y1=");
y1 = Convert.ToInt32(Console.ReadLine());
int x2;
Console.Write("x2=");
x2 = Convert.ToInt32(Console.ReadLine());
int y2;
Console.Write("y2=");
y2 = Convert.ToInt32(Console.ReadLine());
int a;
int a1 = x2-x1;
a1 = op1.Mod(a1, p);
a1 = op1.Evc(p, a1);
a = y2 - y1;
a = op1.Mod(a, p);
a = (a * a1) % p;
x = (a * a) % p;
x = x - x1;
x = op1.Mod(x, p);
x = x - x2;
x = op1.Mod(x, p);
x = x % p;
y = (x1 - x);
y = op1.Mod(y, p);
y = (y * a) % p;
y = y - y1;
y = op1.Mod(y, p);
}
Console.WriteLine("x=" + x);
Console.WriteLine("y=" + y);
Console.ReadKey();
}
}
}
Приложение 3
Листинг программы для решения задач 5.3, 5.4 на языке Pascal
Программа реализует обобщенный алгоритм Евклида, сложение и удвоение точек, а также умножение точки на скаляр с использованием схемы Горнера.
var
a:array[1..10]of boolean;
xn,yn,p,k,xk,yk,i,j,x,y:integer;
function ee(pe,ae:integer):integer;
var u1,u2,u3,v1,v2,v3,t1,t2,t3,q:integer;
begin
u1:=1; u2:=0; u3:=pe;
v1:=0; v2:=1; v3:=ae;
while v3>0 do
begin
q:=trunc(u3/v3);
t1:=u1-v1*q;
t2:=u2-v2*q;
t3:=u3-v3*q;
u1:=v1;
u2:=v2;
u3:=v3;
v1:=t1;
v2:=t2;
v3:=t3;
end;
if u3=1
then if u2>0
then ee:=u2
else ee:=pe+u2
else ee:=0
end;
procedure dub(x1,y1,pm:integer; var x3,y3:integer);
var lam:integer;
begin
lam:=((3*x1*x1+1)mod pm)*ee(pm,(2*y1)mod pm);
lam:=lam mod pm;
x3:=(lam*lam)mod pm - (2*x1)mod pm;
while x3<0 do x3:=x3+pm;
x3:=x3 mod pm;
y3:=(x1-x3)*lam - y1;
while y3<0 do y3:=y3+pm;
y3:=y3 mod pm;
end;
procedure ad(x1,y1,x2,y2,pm:integer; var x3,y3:integer);
var lam,chz,znam:integer;
begin
chz:=y2 - y1;
while chz<0 do chz:=chz+pm;
znam:=x2 - x1;
while znam<0 do znam:=znam+pm;
lam:=(chz)*ee(pm,znam);
lam:=lam mod pm;
x3:=(lam*lam)mod pm - x1 - x2;
while x3<0 do x3:=x3+pm;
y3:=(x1-x3)*lam - y1;
while y3<0 do y3:=y3+pm;
y3:=y3 mod pm;
end;
begin
write('x=');readln(xn);
write('y=');readln(yn);
{write('p=');readln(p);}p:=199;
write('k=');readln(k);
j:=0;
while k>0 do
begin
j:=j+1;
if odd(k) then a[j]:=true
else a[j]:=false;
k:=k div 2
end;
x:=xn;y:=yn;
for i:=j-1 downto 1 do
begin
if a[i]
then
begin
dub(x,y,p,xk,yk);x:=xk;y:=yk;
ad(x,y,xn,yn,p,xk,yk)
end
else dub(x,y,p,xk,yk);
x:=xk;y:=yk;
end;
{dub(xn,yn,p,x,y);
for i:=2 to k-1 do
begin
ad(x,y,xn,yn,p,xk,yk);
x:=xk;
y:=yk;
end;}
writeln(x,' ',y)
end.