Содержание
Транскрипт
1 МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «КАЛМЫЦКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им.б.б.городовикова» ФАКУЛЬТЕТ МАТЕМАТИКИ, ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ КАФЕДРА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ ДОПУСТИТЬ К ЗАЩИТЕ Декан ФМФИТ Е.В.Сумьянова 2016г. ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ РАБОТА Цифровая подпись Эль-Гамаля по основной образовательной программе подготовки бакалавров Фундаментальная информатика и информационные технологии Выполнил: / студент 4 курса ФИИТ Джапов Евгений / Научный руководитель: /к.ф.-м. н., доцент Паляева В.Н / Элиста, 2016
3 1. Введение Электронная подпись (ЭП; ранее — электронная цифровая подпись, ЭЦП) является равноценной заменой рукописной подписи. Согласно законодательству Российской Федерации, цифровая подпись имеет полную юридическую силу. ЭП позволяет защитить электронный документ от изменений, проверить его целостность и делает невозможным отказ от авторства, дает возможность доказать это авторство. Для юридических лиц ЭП служит незаменимым инструментом, позволяющим наладить быстрый и удобный оборот документов внутри компании и с внешними контрагентами. Для физических лиц электронная подпись является быстрым и простым способом для взаимодействия, например, с работодателями и учебными учреждениями, а также государственными структурами через Интернет. Сертификат электронной подписи документ, который подтверждает принадлежность открытого ключа (ключа проверки) ЭП владельцу сертификата. Выдаются сертификаты удостоверяющими центрами (УЦ) или их доверенными представителями. Владелец сертификата ЭП физическое лицо, на имя которого выдается сертификат ЭП в удостоверяющем центре. У каждого владельца сертификата на руках два ключа ЭП: закрытый и открытый. Закрытый ключ электронной подписи (ключ ЭП) позволяет генерировать электронную подпись и подписывать электронный документ. Владелец сертификата обязан в тайне хранить свой закрытый ключ. Открытый ключ электронной подписи (ключ проверки ЭП) однозначно связан с закрытым ключом ЭП и предназначен для проверки подлинности ЭП. 2
4 В настоящее время сфера применения ЭЦП достаточно широка. Цели применения цифровых подписей: Электронный документооборот. Технология ЭП широко используется в системах электронного оборота документов разного направления и назначения: внешнего и внутреннего обмена, законотворческого, организационно-распорядительного, торговопромышленного, кадрового и прочего. Это является основным свойством электронной подписи она часто используется для собственноручной подписи и/или печати на бумажном документе. Во внутреннем документообороте ЭП используется в качестве средства визирования и утверждения электронных документов в рамках внутренних процессов. Электронная отчетность для контролирующих органов. Современный способ сдачи отчетности с помощью интернет заключается в том, что клиент может выбрать один из нескольких удобных для себя способов: отдельное ПО, продукты семейства 1C, ФСС, порталы ФНС. Основа этой услуги служит сертификат электронной подписи, который должен быть выпущен надежным удостоверяющим центром. Метод отправки не имеет решающего значения. Такая подпись придает документам юридическую значимость. Электронные торги. Электронные торги устраивают на специальных площадках (сайтах). Поставщики используют электронную подпись на государственных и коммерческих площадках. ЭП поставщиков и заказчиков гарантируют участникам торгов, что они имеют дело с реальными предложениями. Для того чтобы заключенные контракты приобрели юридическую силу, необходима подпись обеих сторон. Арбитражный суд. В качестве доказательства, при возникновении каких-либо споров и разногласий между организациями, в суде могут 3
5 использоваться электронные документы. Полученные посредством факсимильной, электронной или иной связи, подписанные электронной подписью или другим аналогом собственноручной подписи, согласно Арбитражному процессуальному кодексу РФ, относятся к письменным доказательствам. Документооборот с физическими лицами. Надо признать, что данная сфера применения ЭП весьма специфична и используется пока редко, но, тем не менее, возможна. При помощи ЭП заверять различные документы могут физические лица. Физические лица, при помощи ЭП, могут заверять различные документы. Благодаря такой возможности, удаленные работники на основании договоров по оказании услуг, например, могут выставлять акты приемки-сдачи работ в электронном виде. Целью дипломной работы является изучение алгоритма цифровой подписи Эль-Гамаля и ее программная реализация. Дипломная работа состоит из введения, четырех параграфов, заключения, списка литературы и приложения. В первом содержится описание некоторых ЭЦП, рассматривается использование хэш-функции в ЭЦП. В третьем описан алгоритм цифровой подписи Эль-Гамаля. В четвертом приведена программная реализация, в которой подробно описаны шаги выполнения алгоритма на языке программирования C++. 4
7 (США), но НИСТ (Национальный институт стандартов) сделал этот патент доступным для использования без отчислений на лицензию. В России на данный момент используют стандарт цифровой подписи ГОСТ Р Принят и введён в оборот Приказом Федерального агентства по техническому регулированию и метрологии от 7 августа 2012 года. Указанный стандарт состоит из установления процедуры выработки и проверки электронной цифровой подписи (ЭЦП) документов или сообщений, на базе ассиметричного криптографического алгоритма с применением функции хэширования. передаваемых по незащищенным телекоммуникационным каналам общего пользования в системах обработки информации различного назначения. Метод ЕGSА (ЕІ GаmаІ Signaturе Аlgorithm — алгоритм цифровой подписи Эль-Гамаля) заключается в том, что для подтверждения практической невозможности фальсификации, компрометации цифровой подписи может быть применена усложненная вычислительная задача, чем разложение на множители большого целого числа, то есть задача дискретного логарифмирования. К тому же, Эль-Гамаля удалось избежать явной уязвимости алгоритма цифровой подписи RSА, связанной с возможностью фальсификации цифровой подписи без нахождения секретного ключа под некоторыми сообщениями. Использование хэш-функций. Поскольку подписываемые документы используют, как правило, большой объём, поэтому в схемах ЭП зачастую подпись ставится не на сам документ, а на его хэш. Для вычисления хэш-значения используются криптографические хэш-функции, что обеспечивает выявление каких-либо изменений в документе при проверке подлинности подписи. Хэш-функции не входят в часть алгоритма ЭП, поэтому в схеме может быть использована любая надёжная хэш-функция. 6
9 текст будет вычислительно сложно, а значит атака такого типа становится для злоумышленников невозможной. Примером хэш-функции может служить функция, вычисляющая хэш как остаток от деления входных данных на M: h(k)=k mod M, где M — количество всех возможных хэш (выходных данных). При этом очевидно, что при чётном M значение функции будет чётным при чётном k и нечётным — при нечётном k. На практике обычно выбирают простое M, в большинстве случаев этот выбор вполне удовлетворителен. 8
11 и вычисляет с использованием секретного ключа Х целое число b из уравнения m = Х * а + К * b (mod (Р-1)). Для вычисления b можно использовать расширенный алгоритм Евклида. Пара чисел (а,b) образует цифровую подпись S = (а, b), проставляемую под документом М. Описание проверки цифровой подписи на подлинность. Тройка (М, а, b) передается получателю, в то время как значения чисел (Х, К) содержатся отправителем в секрете. После получения подписанного сообщения (М, а, b), получатель должен проверить, соответствует ли подпись S = (а, b) сообщению М. Для этого получатель: 1) вычисляет по полученному сообщению М число m = h(м), т.е. хэширует принятое сообщение М. 2) находит значения А = Y a a b (mod Р) B = G m (mod Р). и признает, что сообщение М является подлинным, если, и только если A=B То есть, получатель проверяет справедливость отношения Y a a b (mod Р) = G m (mod Р). Известно, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(а, b) под документом М получена с помощью именно того секретного ключа X, из которого был сформирован открытый ключ Y. 10
13 5 = (6* 8+9* b)(mod 10) или 9* b=-43(mod 10). Отсюда b = 3. Цифровая подпись: S=(6,3). После этого отправитель передает подписанное сообщение. Приняв сообщение с цифровой подписью и открытым ключом Y = 3, получатель вычисляет хэш-значение для сообщения М: m = 5, а затем находит два значения: A=Yaab (mod Р) = 36 * 63 (mod 11) =10 (mod 11); B=Gm (mod Р) = 25 (mod 11) =10 (mod 11). Так как полученные два целых числа равны, то можно с уверенностью сказать что полученное сообщение М является подлинным. Отметим, что алгоритм Эль-Гамаля является характерным примером подхода, допускающего пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а, b). В таких случаях, чтобы удостовериться в подлинности принятого сообщения, получатель должен проверить соответствие аутентификатора сообщения. Схема цифровой подписи Эль-Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSА: 1. Алгоритм цифровой подписи, при заданном уровне стойкости, использует намного меньше объем памяти благодаря целым числам, имеющих запись на 25% короче, которые уменьшают сложность вычислений почти в два раза. 12
15 4. Программная реализация Алгоритм Эль-Гамаля был реализован на объектно-ориентированном языке программирования C++ при помощи программного инструмента Borland C++ Builder. Для этого: 1. Создана форма TForm1 *Form1 (рис. 1) На созданной форме размещены необходимые объекты, с помощью компонента Label введены названия объектов. Для каждого компонента на форме прописаны необходимые команды для выполнения алгоритма. 14
17 Button3 Генерация простых чисел. С помощью оператора цикла for находим простые числа. При нажатии кнопки будет происходить генерация простых чисел в окне Memo2. Memo2->Visible=true; int i,j; float m,n; i=9999; for(m=1;m<=i;m++) if(m==1) j=0; if(m==2) j=1; if(m>2) for(n=2;n<m;n++) if(m/n-floor(m/n)==0) goto mm; j++; Memo2->Lines->Strings[j]=m; ComboBox1->Items->Strings[j]=m; mm: ; 16
19 char *q2=q1; long n,pp,qq; pp=strtol(p2, &endptr, 10); qq=strtol(q2, &endptr, 10); b+=2; Memo1->Lines->Strings[b]=»Вычислим модуль n по формуле:»; n=pp*qq; nn=n; n_n=n; b++; Memo1->Lines->Strings[b]=«n = p*q = «+p+»*»+q+» = «+nn; Label4->Visible=true; ComboBox3. На данном этапе выбираем секретный ключ X. При этом 1 < Х < (Р-1). int i; b+=2; Memo1->Lines->Strings[b]=»Секретный ключ x:»; b++; i=combobox3->itemindex; Memo1->Lines->Strings[b]=ComboBox3->Items->Strings[i]; ee=memo1->lines->strings[b]; Button6->Visible=true; 18
21 b+=2; Memo1->Lines->Strings[b]=»Открытый ключ y:»; b++; Memo1->Lines->Strings[b]=qq2; YY=qq2; Button7->Visible=true; Button7 Вычисление хэш-значения m. //Шифрование хэш-значения AnsiString h_0,kvadrat1_2,m_v_m2,nomer1,n_n2; long double h0,m_v_m,summa,summa1,kvadrat;//,kvadrat1; double h_0_0,kvadrat1_1,m_v_m1,n_n1; int i,nomer; randomize(); h0=rand()%10000; h_0_0=h0; h_0=h_0_0; 20
23 kvadrat1=kvadrat; nomer=i+1; nomer1=nomer; kvadrat1_1=kvadrat1; kvadrat1_2=kvadrat1_1; n_n1=n_n; n_n2=n_n1; Memo1->Lines->Strings[b]=»H»+nomer1+» = (M»+nomer1+» + H»+i+«)^2 (mod n) = («+m_v_m2+» + «+h_0+«)^2 (mod «+n_n2+») = «+kvadrat1_2; b++; h0=kvadrat1; h_0_0=h0; h_0=h_0_0; b++; Memo1->Lines->Strings[b]=» Хэш-значение m:»; b++; Memo1->Lines->Strings[b]=»m = «+kvadrat1_2; hesch=kvadrat1; Label5->Visible=true; ComboBox4->Visible=true; 22
25 ComboBox4. Производим выбор случайного числа k Button10 Определить значение a. double i,kk,qq,pp,qq1,qq2,qq3; kk=strtoint(k); qq=strtoint(q); qq1=qq; pp=strtoint(p); for(i=1;i<kk;i++) qq2=qq*qq1; if(qq2>pp) qq3=qq2/pp; qq2=qq2-pp*floor(qq3); qq1=qq2; else qq1=qq2; b+=2; 24
27 v2=floor(v1); v2=-1*v2; else v2=floor(v1); v=v-pp*v2; //v (mod p) = v //b+=2; Memo1->Lines->Strings[b]=v; if(v<=0) for(z=1;v!=lll;z++) w=z*pp; g=w/kk; g1=floor(g); LLL=kk*g1-w; if(v>0) for(z=1;v!=lll;z++) w=z*pp; g=w/kk; g1=1+floor(g); LLL=kk*g1-w; 26
29 Button8 Расшифровывание S. Получатель с помощью значений a и b вычисляет подлинность подписи. double i,yy1,yy2,pp,yy3,aa1,aa2,aa3,z,z2,hesch2,qq,qq1,qq2,qq3; AnsiString YY10,A10,B10,hesch10,z10,qq10; pp=strtoint(p); YY1=YY; for(i=1;i<a;i++) YY2=YY*YY1; if(yy2>pp) YY3=YY2/pp; YY3=YY2-pp*floor(YY3); YY1=YY3; else YY1=YY2; AA1=A; for(i=1;i<b;i++) AA2=A*AA1; if(aa2>pp) AA3=AA2/pp; AA3=AA2-pp*floor(AA3); 28
31 b+=2; Memo1->Lines->Strings[b]=»Для проверки подлинности подписи проверяем выполнение условия:»; b++; Memo1->Lines->Strings[b]=»(y^a)*(a^b)(mod p) = (q^m’)(mod p)»; b++; YY10=YY; A10=A; B10=B; hesch10=hesch2; Memo1->Lines- >Strings[b]=»(«+YY10+»^»+A10+»)(«+A10+»^»+B10+«)(mod «+p+») = («+q+»^»+hesch10+«)(mod «+p+»)»; b++; z10=z; qq10=qq1; Memo1->Lines->Strings[b]=z10+«(mod «+p+») = «+qq10+«(mod «+p+»)»; b++; Button9->Visible=true; 30
33 Рис.2. Проверка на подлинность ЭП 32
35 Литература и источники 1. А. П. Алферов, А. Ю. Зубов, А. С. Кузьмин, А. В. Черемушкин. Основы криптографии. Москва Гелиос АРВ, Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Триумф, Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. Под ред. В.Ф. Шаньгина. — 2-е изд., перераб. и доп. — М.: Радио и связь, с.: ил. 4. Конеев И.Р., Беляев А.В. Информационная безопасность предприятия. — СПб.: БХВ-Петербург,
Источник