Հայաստանի ատենախոսությունների բաց մատչելիության պահոց = Open Access Repository of the Armenian Electronic Theses and Dissertations (Armenian ETD-OA) = Репозиторий диссертаций Армении открытого доступа

Հաշվողական խմբերի տեսության մեթոդների կիրառումը ծածկագրման մեջ

Սողոյան, Արմեն Վահանի (2013) Հաշվողական խմբերի տեսության մեթոդների կիրառումը ծածկագրման մեջ. PhD thesis, ԵՊՀ.

[img]
Preview
PDF (Abstract)
Available under License Creative Commons Attribution.

Download (336Kb) | Preview

    Abstract

    Ատենախոսությունում առաջարկված են գաղտնի բանալիով (սիմետրիկ) և բաց բանալիով (ասիմետրիկ) ծածկագրման նոր սխեմաներ, որոնք հիմնված են հաշվողական խմբերի տեսության հիմնարար և կարևորագույն Սիմսի (Շրայեր-Սիմսի) ալգորիթմի և տեղադրությունների խմբի "ուժեղ" ծնիչների բազմության գաղափարի օգտագործման վրա: Տեղադրությունների խմբի "ուժեղ" ծնիչների բազմությունը թույլ է տալիս միարժեքորեն ներկայացնել խմբի տարրերը ծնիչների բազմության տարրերի արտադրյալների միջոցով և հնարավորություն է տալիս էֆեկտիվ եղանակով թվարկել և առանց կրկնողությունների գեներացնել խմբի տեղադրությունները: Այն նաև թույլ է տալիս էֆեկտիվորեն լուծել մի շարք կարևոր խնդիրներ այնպիսին ինչպես տրված խմբին տրված տեղադրության պատկանելիության հարցը, տեղադրությունների տրված բազմության տարրերի արտադրյալի միջոցով տրված տեղադրության ներկայացման հնարավորության հարցը, ենթախմբի նորմալ լինելը և այլն: Սիմսի ալգորիթմը բազմանդամային ժամանակում կառուցում է տեղադրությունների խմբի "ուժեղ" ծնիչների բազմությունն ելնելով խմբի որևէ ծնիչների բազմությունից: XX դարի կեսին հաշվողական տեխնիկայի հայտնագործությունը և դրա կիրառումն ինֆորմացիայի կոդավորման և ծածկագրման համակարգերի ստեղծման գործում, ինչպես նաև դիսկրետ մաթեմատիկայի բուռն զարգացումը և կարևորագույն արդյունքների ստացումը հանգեցրեցին այն բանին, որ մաթեմատիկայի այնպիսի զուտ տեսական համարվող ճյուղերը ինչպես թվերի տեսությունը կամ խմբերի տեսությունը հանկարծակի դարձան կարևորագույն գործիք ինֆորմացիայի մշակման համակարգերի ստեղծման բնագավառում: Ներկայումս ալգորիթմական թվերի տեսությունը և հաշվողական խմբերի տեսությունը մաթեմատիկայի ինքնուրույն և բուռն զարգացում ապրող ճյուղեր են: Հաշվողական խմբերի տեսության որպես ինքնուրույն ոլորտի ձևավորումը հիմնադրվեց 1970 թվականին, երբ Չարլզ Սիմսը առաջարկեց տեղադրությունների խմբի "ուժեղ" ծնիչների բազմության հիման վրա ստեղծված ալգորիթմական մեթոդները: Սիմսի ալգորիթմը (որը նաև հայտնի է որպես Շրայեր-Սիմսի ալգորիթմ) հաշվողական խմբերի տեսության հիմնարար մեթոդներից մեկն է: Դրա դերը համեմատելի է գծային հանրահաշվում գծային հավասարումների համակարգերի լուծման Գաուսի մեթոդի դերին: Диссертационная работа посвящена применению алгоритма Симса (Шрейера-Симса) для построения новых криптографических схем, основанных на использовании систем “сильных” образующих для групп подстановок. Алгоритм Симса является основным инструментом вычислительной теории групп, из которого по-существу и выросла современная вычислительная теория групп. Алгоритм Симса строит систему “сильных” образующих для группы подстановок, заданной какой-либо системой образующих. Для заданной группы подстановок. С рассматривается бащня подгрупп С > Сх > Сп > ... > СПкЛ > ... > С12кП_х = СПк„ = {<?}, где С12..л - подгруппа в С , являющаяся пересечением стабилизаторов чисел 1,2,., г . Система “сильных” образующих для С представляется в виде прямоугольной таблицы, в которой ячейки г -ой строки содержат трансверсаль (систему различных С '12...г С однозначно задается произведением вида gl g 2 ... g п-1, где gi - подстановка из г -ой строки таблицы системы “сильных” образующих. Общая схема щифрования с симметричным ключом задается таблицей Т системы “сильных” образующих симметрической группы $ п и пары отображений Ф и Ф 1, где Ф отображает множество X входных бинарных строк в множество векторов вида (Ур у2,., у 1) , в которых у - это порядковый номер подстановки в I -ой строки таблицы. Тройка (Т, Ф, Ф 1) служит секретным ключом. В работе приводятся три алгоритма, реализующие данную схему, оптимальные по порядку длины входных блоков. An application of the Sims (Schreier-Sims) algorithm is considered in construction of new cryptographic schemes based on sets of “strong” generators for permutation groups. The Sims algorithm is one of basic instruments of the computational group theory, which laid the foundation for the contemporary computational group theory. The algorithm of Sims constructs a set of “strong” generators for a permutation group given by a set of generators. Consider a subgroup tower G > G1 > Gu >... > GUKJ >... > G12K„_I = GUK„ = {e} f°r a given permutation group G in which G^ ; is a subgroup in G coinciding with the intersection of stabilizers for the numbers 1,2,..., i . A set of “strong” generators for product gi g 2 ... g i, where g; is a permutation from the i -th row of the table of the “strong” generators set. The symmetric key encryption general scheme is defined by a table T of a “strong” generators set for the symmetric group S n and a pair of mappings $ and $-1 1, where $ maps the set of binary input strings X into the set of vectors (yv y2,K, yn-1) in which y; is a sequence number of a permutation in the i -th row of the table. The triplet (T, $, $ 1) serves as a secret key. We present three algorithms realizing the general scheme that are optimal by the order of the length of the input blocks.

    Item Type: Thesis (PhD)
    Additional Information: Применение методов вычислительной теории групп в криптографии. Application of computational group theory methods in cryptography.
    Uncontrolled Keywords: Согоян Армен Ваганович, Soghoyan Armen
    Subjects: Mathematics and Cybernetics
    Divisions: UNSPECIFIED
    Depositing User: NLA Circ. Dpt.
    Date Deposited: 15 Mar 2017 10:09
    Last Modified: 15 Mar 2017 10:09
    URI: http://etd.asj-oa.am/id/eprint/4270

    Actions (login required)

    View Item