Программирование алгоритма цифровой подписи ГОСТ Р 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. Руководство пользователя

Программа предназначена для выполнения подписи сообщения и проверки подписи.

После запуска программа предлагает выбрать действие:

Последовательный вызов процедур подписи сообщения и проверки подписи.

Подписать сообщение.

Проверить подпись.

Входные данные хранятся в файле initialdata.txt:

р – простое число, удовлетворяющее требованию 2⁵⁰⁹<р<2⁵¹²;

q – простое число, удовлетворяющее требованию 2²⁵⁴<q<2²⁵⁶;

a – число, которое рассчитывается по формулеa^q(modp)=1 и удовлетворяет требованию 1<а<р-1;

x – закрытый ключ, удовлетворяющий требованию 1<x<q;

y – открытый ключ, который рассчитывается по формуле y=a^x(modp);

m – хэш-функция по алгоритму ГОСТ Р 34.11.

Выбрав действие, программа производит необходимые действия и записывает результаты в файлы: цифровая подпись записывается в signature.txt, а результат проверки подписи – в verification result.txt.

3. Описание алгоритмов

3.1 Алгоритм функции формирования подписи

Функция формирования подписи signature формирует подпись, используя начальные параметры, расположенные в файле initial data.txt. Начальные параметры должны удовлетворять следующим условиям:

простое число р: 2⁵⁰⁹<р<2⁵¹²;

простое число q: 2²⁵⁴<q<2²⁵⁶;

a: 1<а<р-1, a^q(modp)=1;

закрытый ключ x: 1<x<q;

открытый ключ y: y=a^x(modp);

хэш-функция 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=m^q-2(mod q)

z₁=sv(mod q)

z₂=(q-r’)v(mod q)

u=(a^z1y^z2(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;

unsigned short d;

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];

int main()

{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("----------------------------------------------------------nn");

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 authenticn");

else fprintf(fp1, "WARNING: verification unsuccessful: u!=r', signature is non-authenticn");

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 authenticn");

else fprintf(fp1, "WARNING: verification unsuccessful: u!=r', signature is non-authenticn");

printf("Operation complete. Result of operation writed to "verification result.txt"n");

break;

default: printf("Wrong number. Try againn"); 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 tmp[S/2];

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);}