Программирование алгоритма цифровой подписи ГОСТ Р 34.10-94
Министерство
высшего образования Российской Федерации
Пензенский государственный университет
Кафедра
«Информационная безопасность систем и технологий»
ПОЯСНИТЕЛЬНАЯ
ЗАПИСКА
курсовой
работе по теме
«Программирование
алгоритма цифровой подписи ГОСТ Р 34.10-94»
ПГУ
3.090105.001 ПЗ
Дисциплина
КМЗИ
Группа
Разработала
студентка
Проект
принят с оценкой
Руководитель
проекта
ПЕНЗА,
2006
Реферат
Пояснительная записка 24 с., 3 источника, 3 прил.
ЦИФРОВАЯ ПОДПИСЬ, ПРОГРАММА, ИНТЕРФЕЙС,
ФУНКЦИЯ, ФАЙЛЫ, ОТКРЫТЫЙ КЛЮЧ, ЗАКРЫТЫЙ КЛЮЧ.
Объект исследования – алгоритм цифровой
подписи ГОСТ Р 34.10-94.
Целью работы является получение навыков
в программировании криптоалгоритмов на примере алгоритма цифровой подписи ГОСТ
Р 34.10-94.
В процессе работы была разработана
программа, которая осуществляет процедуру подписи сообщения и процедуру
проверки подписи.
В результате выполнения работы были
получены навыки в программировании алгоритма цифровой подписи ГОСТ Р 34.10-94.
Содержание
Введение
1.
Пользовательский интерфейс программы
2. Руководство
пользователя
3. Описание
алгоритмов
3.1. Алгоритм
функции формирования подписи
3.2. Алгоритм
функции проверки подписи
Заключение
Список
использованных источников
Блок
схема алгоритма функции формирования подписи
Блок
схема алгоритма функции проверки подписи
Листинг
программы
Введение
В настоящее время широкое
распространение получили персональные компьютеры. Они, без преувеличения, вошли
во все сферы человеческой деятельности. Это максимально облегчило человеческий
труд. Сейчас трудно представить, чтобы делал человек без компьютера.
Предприятия, фирмы, офисы, банки - это ещё далеко не все области применения
персонального компьютера.
Без использования криптографии сегодня
немыслимо решение задач по обеспечению безопасности информации, связанных с
конфиденциальностью и целостностью. Если до 1990г. криптография обеспечивала
закрытие государственных линий связи, то в наши дни использование криптографических
методов получило широкое распространение благодаря развитию компьютерных сетей
и электронного обмена данными в различных областях[3].
Владение языками программирования
позволяет значительно расширить круг выполняемых задач специалистом по защите
информации и более полно использовать возможности компьютера.
Данная курсовая работа написана на языке
С.
С – это универсальный язык
программирования с компактным способом записи выражений, современными
механизмами управления структурами данных и богатым набором операторов[1].
Целью курсовой работы является
разработка программы, которая реализует процедуру подписи сообщения и процедуру
проверки подписи.
1. Пользовательский
интерфейс программы
Интерфейс – аппаратная или программная
система сопряжения объектов с различными характеристиками. Программный
интерфейс позволяет согласовывать программы с различными параметрами, а также
дают возможность пользователю работать в операционной среде с той или иной
степенью комфорта.
Методы и средства взаимодействия с
аппаратными и программными средствами называют пользовательским интерфейсом
[2]. Любая программа должна обладать пользовательским интерфейсом, иначе, кроме
своего разработчика, она будет недоступна в понимании лицу с ней не знакомому.
Интерфейс бывает различных типов.
Разработанная программа обладает интерактивным интерфейсом. Основным
устройством управления в данном случае является клавиатура.
2. Руководство пользователя
Программа предназначена для выполнения подписи
сообщения и проверки подписи.
После запуска программа предлагает выбрать
действие:
Последовательный вызов процедур подписи
сообщения и проверки подписи.
Подписать сообщение.
Проверить подпись.
Входные данные хранятся в файле initial data.txt:
р – простое число, удовлетворяющее требованию 2509<р<2512;
q – простое число, удовлетворяющее требованию 2254<q<2256;
a – число, которое рассчитывается по формуле aq(mod p)=1 и удовлетворяет требованию 1<а<р-1;
x – закрытый ключ, удовлетворяющий требованию 1<x<q;
y – открытый ключ, который рассчитывается по формуле y=ax(mod p);
m – хэш-функция по алгоритму ГОСТ Р 34.11.
Выбрав действие, программа производит
необходимые действия и записывает результаты в файлы: цифровая подпись
записывается в signature.txt, а результат проверки подписи – в verification
result.txt.
3. Описание алгоритмов
3.1 Алгоритм
функции формирования подписи
Функция формирования подписи signature
формирует подпись, используя начальные параметры, расположенные в файле initial
data.txt. Начальные параметры должны удовлетворять следующим условиям:
простое число р: 2509<р<2512;
простое число q: 2254<q<2256;
a: 1<а<р-1, aq(mod p)=1;
закрытый ключ x: 1<x<q;
открытый ключ y: y=ax(mod p);
хэш-функция h(M)=m по алгоритму ГОСТ Р 34.11.
r=ak(mod p)
r’=r(mod q)
s=xr’+km(mod q)
Таким образом, цифровая подпись для
сообщения М есть: <r’>||<s>.
Алгоритм функции формирования подписи
приведен в Приложении А.
3.2 Алгоритм функции проверки подписи
Функция проверки подписи verify проверяет подпись, использую параметры:
цифровую подпись сообщения М;
открытый ключ;
хэш-функцию;
простые числа р и q.
Для проверки подписи необходимо
вычислить:
v=mq-2(mod q)
z1=sv(mod q)
z2=(q-r’)v(mod
q)
u=(az1yz2(mod
p))(mod q)
Если условие r’=u
выполнено – подпись подлинная. Результат проверки подписи находится в файле verification
result.txt.
Алгоритм функции проверки подписи
приведен в Приложении Б.
4.
Отладка и проверка работоспособности программы
Программа была откомпилирована и
отлажена.
Для проверки
работоспособности программы был запущен файл sign.exe, были выбраны
действия, которые необходимо выполнить. Например, необходимо сформировать
цифровую подпись и проверить ее подлинность.
Текст входного файла initial data.txt:
Текст выходного файла signature.txt:
Текст выходного файла verification
result.txt:
Оценка результатов показала, что
программа работает верно.
Листинг
программы приведен в Приложении В.
Заключение
Разработанная программа написана на языке
Си. Программа осуществляет формирование цифровой подписи по алгоритму ГОСТ Р
34.10-94 и проверку цифровой подписи.
Таким образом, задание на курсовую
работу выполнено в полном объеме.
Список использованных
источников
1. Керниган Б., Ритчи Д. Язык программирования Си\ Пер. с
англ., 3-е изд., испр. – СПб.: «Невский диалект», 2001. – 352с.
2. Информатика: Базовый курс \ С.В. Симонович и др. –
СПб,: Питер, 2001. – 640 с.
3. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин
А.В. Основы криптографии: Учебное пособие, 2-е изд., испр. И доп. – М.:Гелиос
АРВ, 2002. – 480с., ил.
ПРИЛОЖЕНИЕ А
Блок схема алгоритма функции формирования подписи
ПРИЛОЖЕНИЕ Б
Блок схема алгоритма функции проверки
подписи
ПРИЛОЖЕНИЕ В
Листинг программы
Sign.cpp
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include
"Interfs.h"
#include
"function.h"
#define LOWORD(T) ((unsigned
short)(T))
#define HIWORD(T) ((unsigned
short)(T>>16))
#define MAKELONG(a,b)
((((unsigned long)(a))<<16)+b)
#define S 32
/*addition*/
void add(unsigned short add_a[],
unsigned short add_b[],unsigned short add_c[], int add_l_a_b)
{unsigned long T;
unsigned short d;
d=0;
for(int i=0;
i<=(add_l_a_b-1); i++)
{T=(unsigned
long)add_a[i]+(unsigned long)add_b[i]+d;
add_c[i]=LOWORD(T);
d=HIWORD(T);}
add_c[add_l_a_b]=d;}
void sub(unsigned short
sub_a[], unsigned short sub_b[],unsigned short sub_c[], int sub_l_a_b)
{unsigned long T;
d=0;
for(int i=0;
i<=(sub_l_a_b-1); i++)
{T=(unsigned
long)sub_a[i]-(unsigned long)sub_b[i]-d;
sub_c[i]=LOWORD(T);
if(HIWORD(T)==0) d=0;
else d=1;}
sub_c[sub_l_a_b]=d;}
/*multiplication c=a*b*/
void mul(unsigned short
mul_a[], unsigned short mul_b[],unsigned short mul_c[],int mul_l_a, int
mul_l_b)
{unsigned long T;
unsigned short d;
for(int z=0;
z<=(mul_l_a-1); z++)
{mul_c[z]=0;}
for(int i=0;
i<=(mul_l_a-1); i++)
{d=0;
for(int j=0;
j<=(mul_l_b-1); j++)
{T=(unsigned long)
mul_c[i+j]+(unsigned long) mul_a[i]*(unsigned long) mul_b[j]+d;
mul_c[i+j]=LOWORD(T);
d=HIWORD(T);}
mul_c[i+mul_l_b]=d;}}
/*c=(a*b) mod m*/
void mul_mod(unsigned short
mm_a[], unsigned short mm_b[], unsigned short mm_n[], unsigned short mm_ost[],
unsigned short w1[], int mm_l_a_b_n, int t)
{unsigned short *mm_d;
mm_d=new(unsigned
short[mm_l_a_b_n+t]);
mul(mm_a, mm_b, mm_d,
mm_l_a_b_n, t);
Div(mm_d, mm_n, w1, mm_ost,
mm_l_a_b_n*2, mm_l_a_b_n);}
/*c=a(exp b) mod n*/
void exp_mod(unsigned short
exp_mod_a[], unsigned short exp_mod_b[], unsigned short exp_mod_n[], unsigned
short exp_mod_c[], unsigned short w1[], int exp_mod_l_a_n, int exp_mod_l_b)
{unsigned short
*exp_mod_c_dop;
exp_mod_c_dop=new(unsigned
short[exp_mod_l_a_n]);
int e;
for(int l=1;
l<=(exp_mod_l_a_n-1); l++)
{exp_mod_c[l]=0;
exp_mod_c_dop[l]=0;}
exp_mod_c_dop[0]=1;
exp_mod_c[0]=1;
for(e=(16*exp_mod_l_b-1);
e>=0; e--)
{mul_mod(exp_mod_c, exp_mod_c,
exp_mod_n, exp_mod_c_dop, w1, exp_mod_l_a_n, exp_mod_l_a_n);
if(exp_mod_b[e/16] &
(1<<(e%16)))
{mul_mod(exp_mod_a,
exp_mod_c_dop, exp_mod_n, exp_mod_c, w1, exp_mod_l_a_n, exp_mod_l_a_n);}
else
{for(int h=0;
h<=exp_mod_l_a_n-1; h++)
{exp_mod_c[h]=exp_mod_c_dop[h];}}}}
/*сравнение*/
int comp (unsigned short a[],
unsigned short p[], int S1)
{int x=1;
for(int i=0; i!=S1; i++)
{if (a[i]!=p[i]) x=0;}
if(x==0) return 1;
else return 0;}
/*чтение из файла*/
int file_read(unsigned short
t[], long curpos, int sz)
{FILE *fp;
unsigned short k;
fp=fopen("initial
data.txt","r");
for(int i=0;i<sz;i++)
{fseek(fp,curpos,SEEK_SET);
fscanf(fp,"%x",&k);
t[i]=k;
curpos=curpos+5;}
fclose(fp);
return curpos;}
/*запись в файл*/
int file_write(unsigned short
t[], long curpos, int sz)
{FILE *fp;
fp=fopen("signature.txt","w");
for(int i=0;i<sz;i++)
fprintf(fp,"%x ",t[i]);
fclose(fp);
return curpos;}
unsigned short sign[S];
{FILE *fp1;
unsigned short p[S];
unsigned short a[S];
unsigned short q[S/2];
unsigned short x[S/2];
unsigned short m[S/2];
unsigned short k[S/2];
unsigned short y[S];
long curpos=3;
long
cp=file_read(p,curpos,S);
curpos=cp+7;
cp=file_read(a,curpos,S);
curpos=cp+7;
cp=file_read(q,curpos,S/2);
curpos=cp+7;
cp=file_read(x,curpos,S/2);
curpos=cp+7;
cp=file_read(m,curpos,S/2);
curpos=cp+7;
cp=file_read(k,curpos,S/2);
curpos=cp+7;
cp=file_read(y,curpos,S);
char symb;
int c;
printf("------------------------------------------------------------\n");
printf("|Select action: |\n");
printf("|1.Serial
calling rountines \"Get signature\" and \"Verify signature\".
|\n");
printf("|2.Get signature
|\n");
printf("|3.Verify signature
|\n");
printf("|Press 0 to exit
|\n");
printf("----------------------------------------------------------\n\n");
do
{symb=getch();
c=atoi(&symb);
int rs;
switch(c)
{case 0:
return 0;
case 1:
signature(p,a,q,x,m,k,sign);
file_write(sign, 0, S);
rs=verify(p,a,q,y,m,sign);
fp1=fopen("verification
result.txt","w+");
if(fp1==NULL)
printf("Error: couldn't open file");
if(rs==0) fprintf(fp1,
"Verification successful: u=r', signature is authentic\n");
else fprintf(fp1,
"WARNING: verification unsuccessful: u!=r', signature is
non-authentic\n");
printf("Operations
complete. Result of operation writed to \"verification result.txt\"\n");
fclose(fp1);
break;
case 2:
signature(p,a,q,x,m,k,sign);
file_write(sign, 0, S);
printf("Operation
complete. Result of operation writed to \"signature.txt\"\n");
break;
case 3:
verify(p,a,q,y,m,sign);
rs=verify(p,a,q,y,m,sign);
if(rs==0) fprintf(fp1,
"Verification successful: u=r', signature is authentic\n");
else fprintf(fp1,
"WARNING: verification unsuccessful: u!=r', signature is
non-authentic\n");
printf("Operation
complete. Result of operation writed to \"verification result.txt\"\n");
break;
default: printf("Wrong
number. Try again\n"); break;}}
while(1);}
Function.cpp
#include
"function.h"
#include
"INTERFS.h"
void signature(unsigned short
sign_p[], unsigned short sign_a[], unsigned short sign_q[], unsigned short
sign_x[], unsigned short sign_m[], unsigned short sign_k[], unsigned short
sign[])
{unsigned short w[S*2];
unsigned short res[S];
unsigned short result[S];
unsigned short tmp1[S/2];
unsigned short sum[S+1];
unsigned short s[S+1];
exp_mod(sign_a,sign_k,sign_p,res,w,S,S/2);
Div(res,sign_q,result,tmp,S,S/2);
mul(sign_x,tmp,res,S/2,S/2);
mul(sign_k,sign_m,result,S/2,S/2);
add(res,result,sum,S);
Div(sum,sign_q,s,tmp1,S,S/2);
for(int i=S/2-1, j=S-1;
i>=0; i--, j--)
{sign[j]=tmp[i];
sign[j-16]=tmp1[i];}}
int verify(unsigned short
p[],unsigned short a[],unsigned short q[],unsigned short y[], unsigned short
m[],unsigned short sign[])
{unsigned short v[16];
unsigned short q_2[16];
unsigned short w[S];
unsigned short s[S/2];
unsigned short tmp[S];
unsigned short tmp_[S];
unsigned short tmp_1[S*2];
unsigned short tmp_2[S*2];
unsigned short tmp1[S/2];
unsigned short z1[S/2];
unsigned short z2[S/2];
unsigned short r_[S/2];
for(int i=S/2-1; i>=0;
i--) q_2[i]=q[i];
q_2[0]=q_2[0]-0x0002;
exp_mod(m,q_2,q,v,w,S/2,S/2);
for(int b=S/2-1, j=S-1;
b>=0; b--, j--)
{s[b]=sign[b];
r_[b]=sign[j];}
mul(s,v,w,S/2,S/2);
Div(w,q,tmp,z1,S,S/2);
sub(q,r_,tmp1,S/2);
mul(tmp1,v,w,S/2,S/2);
Div(w,q,tmp,z2,S,S/2);
exp_mod(a,z1,p,tmp,w,S,S/2);
exp_mod(y,z2,p,tmp_,w,S,S/2);
mul(tmp,tmp_,tmp_1,S,S);
Div(tmp_1,p,tmp_2,tmp,S*2,S);
Div(tmp,q,tmp_,s,S,S/2);
return comp(s,r_,S/2);}