ббк76. 0 Қ 54 Редакционная коллегия

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

399 

 

  Проверяется  подпись  Назерке  с  использованием  открытых  ключей, 

 

 

  =

5416  

 7387 = 59 

  Таким  образом,  второй  шаг  проверки,  доказывает,  что  текст  был  предварительно 

отправлен системе (Тренду), в которую система поставила свою метку времени и подписала 

своими закрытыми ключами. Третий шаг доказывает, что это текстовое сообщение Назерке 

подписывала собственноручно, после получения метки времени.  

 

Литература: 

 

1.Н. Фергюсон, Б. Шнайер. Практическая криптография. 2005 год. 416 с. 

2.Баричев С.Г., Гончаров В.В., Серов Р.Е. Основы современной криптографии. – М.: Горячая 

линия. Телеком, 2001. – 120с. 

3.Концепции  информационной  безопасности  Республики  Казахстан  до  2016  года 

(http://medialaw.asia/document/-10747) 

 

 

УДК 681.3.067 

 

ШАРИПБАЙ А.А., ТУЛЕГЕНОВ А. А. 

 

ОБ ОДНОМ ГЕНЕТИЧЕСКОМ КРИПТОАЛГОРИТМЕ 

 

(ЕНУ имени Л.Н. Гумилева, г. Астана, Казахстан) 

 

Информация  является  одной  из  самых  главных  ценностей  в  современном  мире. 

Появление  глобальных  компьютерных  сетей  упростило  и  ускорило  получение  доступа  к 

информации  как  для  отдельных  людей,  так  и  для  больших  корпораций.  Но  легкость  и 

скорость  доступа  к  данным  с  помощью  компьютерных  сетей,  таких  как  Интернет,  также 

сделали  значительными  угрозы  безопасности  информации  при  отсутствии  мер  для  её 

защиты: 

В  настоящее  время  при  разработке  информационных  технологий,  обеспечивающих 

информационную  безопасность  и  защиту  информации,  широкое  применение  находят 

криптографические 

системы 

защиты. 

Известны 

симметричные 

криптосистемы, 

асимметричные 

криптосистемы, системы 

электронной цифровой подписи, хеш-функции, 

управляющие  ключами,  получение  скрытой  информации,  автоматная  криптография, 

квантовая криптография, генетическая криптография, нейрокриптография и др. 

В  симметричных  криптосистемах  зашифрование  и  расшифрование  проводится  с 

использованием  одного  и  того  же  секретного  ключа.  При  этом  предполагается,  что 

взаимодействующие  абоненты  осуществили  обмен  ключевой  информацией  по  некоему 

надёжному каналу связи и обладают секретным ключом К.  

Асимметричные  криптосистемы  характерны  тем,  что  в  них  используются  различные 

ключи  для  зашифрования  и  расшифрования  информации.  Ключ  для  зашифрования  можно 

сделать  открытым,  с  тем  чтобы  любой  желающий  мог  зашифровать  сообщение  для 

некоторого  получателя.  Получатель  же,  являясь  единственным  обладателем  ключа  для 

расшифрования,  будет  единственным,  кто  сможет  расшифровать  зашифрованные  для  него 

сообщения. 

Безусловное  преимущество  данного  подхода  состоит  в  том,  что  отпадает 

необходимость организации защищённого канала для распределения ключей. К недостаткам 

можно  отнести  более  низкую  по  сравнению  с  симметричными  криптосистемами  скорость 

шифрования,  а  также  отсутствие  строгого  математического  обоснования  стойкости  ряда 

используемых конструкций.  

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

400 

 

Генетические  алгоритмы  (ГА)  представляет  собой  предложенные  Холландом 

процедуры  поиска  для  решения  стохастических  и  эвристических  оптимизационных  задача 

[2],  основанные  на  механизмах  естественного  отбора  и  наследования,  определенных  в 

теории эволюции Дарвина. 

ГА  работают  с  популяцией,  состоящей  из  конечного  множества  особей.  Каждая  особь 

популяции 

представляется 

хромосомами, 

являющимися 

упорядоченными 

последовательностями  генов  (свойств, 

детекторов), 

которые 

представляют 

собой 

закодированные решения задачи и оцениваются мерой "приспособленности" особи согласно 

тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно 

оценке того, насколько эффективен организм при конкуренции за ресурсы.  

Гены  являются  атомарными  элементами  генотипа  или  хромосомы.  Следовательно, 

особями  популяции  могут  быть  генотипы  либо  единичные  хромосомы.    В  свою  очередь, 

генотип  -  это  закодированные  решения  задачи,  а  фенотип  –  это  декодированные  решения 

задачи. 

В 

генетических 

алгоритмах 

очень  важным 

понятием 

считается 

функция 

приспособленности  (fitness  function).  Она  представляет  меру  приспособленности  данной 

особи  в  популяции  и  позволяет  оценить  степень  приспособленности  конкретных  особей  в 

популяции  и  выбрать  из  них  наиболее  приспособленные  в  соответствии  с  эволюционным 

принципом выживания «сильнейших». Функция приспособленности должна иметь точное и 

корректное определение и всегда принимать неотрицательные значения. На каждой итерации 

генетического  алгоритма  приспособленность  каждой  особи  данной  популяции  оценивается 

при помощи функции приспособленности, и на этой основе создается следующая популяция 

особей, составляющих множество потенциальных решений задачи. 

Классический генетический алгоритм состоит из выбора исходной популяции особей, 

оценки приспособленности хромосом в популяции, проверки  условия остановки алгоритма, 

селекции хромосом, применение генетических операторов, формирование новой популяции 

и выбора “наилучшей” хромосомы. 

Выбор  исходной  популяции  особей  заключается  в  случайном  выборе  заданного 

количества  хромосом,  представляемых  двоичными  последовательностями  фиксированной 

длины. 

Оценивание  приспособленности  хромосом  в  популяции  состоит  в  расчете  функции 

приспособленности для каждой хромосомы этой популяции. 

Проверка  условия  остановки  алгоритма  предполагает,  что  если  условие  остановки 

выполнено,  то  производится  переход  к  завершающему  этапу  выбора  «наилучшей» 

хромосомы, иначе выполняется селекция. 

Селекция  хромосом  заключается  в  выборе  по  рассчитанным  значениям  функции 

приспособленности  тех  хромосом,  которые  будут  участвовать  в  создании  потомков  для 

следующей  популяции.  Существуют  различные  методы  селекции.  Наиболее  популярным 

считается  так  называемый  метод  рулетки  (roulette  wheel  selection),  который  с  помощью 

прокрутки  колеса  рулетки.    Колесо  рулетки  содержит  по  одному  сектору  для  каждого 

хромосома (члена популяции)

  , размер которого  ( ) вычисляется по формуле 

( ) =

( ) ∗ 100% ,  где    ( ) =

( )

∑

( )

 ,        (1) 

причем 

( )>  0  –  значение  функции  приспособленности  хромосомы  ,    –  численность 

популяции, a 

( ) – вероятность селекции хромосомы  .  

Из  (1)  видно,  что  чем  больше  значение  функции  приспособленности,  тем  больше 

размер  сектора  на  колесе  рулетки.  Все  колесо  рулетки  соответствует  сумме  значений 

функции приспособленности всех хромосом рассматриваемой популяции. При таком отборе 

члены популяции с более высокой приспособленностью с большей вероятностью будут чаще 

выбираться, чем особи с низкой приспособленностью. 

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

401 

 

Применение  генетических  операторов  к  хромосомам,  отобранным  с  помощью 

селекции,  приводит  к  формированию  новой  популяции  потомков  от  созданной  на 

предыдущем  шаге  родительской  популяции.  В  классическом  генетическом  алгоритме 

применяются  два  основных  генетических  оператора:  оператор  скрещивания  (crossover)  и 

оператор  мутации  (mutation).  Вероятность  скрещивания  велика,  а  вероятность  мутация 

очень мала. 

Оператор  скрещивания  сначала  выбирает  из  родительской популяции  пары  хромосом 

 и   ( ≠ ,   =  1, 2, … , ;     =  1, 2, … , )   в  соответствии  с    вероятностью  скрещивания 

( ) и 

.   Далее  для  каждой отобранной  пары  родителей  разыгрывается  позиция гена 

(локус)  в  хромосоме,  определяющая  так  называемую  точку  скрещивания.  Если  хромосома 

каждого  из  родителей  состоит  из  L  генов,  то  очевидно,  что  точка  скрещивания  l

k

 

представляет  собой  натуральное  число,  меньшее  L.  Поэтому  фиксация  точки  скрещивания 

сводится к случайному выбору числа из интервала [1, L - 1]. В результате скрещивания пары 

родительских хромосом получается потомки: 

1)  Потомок,  хромосома  которого  на  позициях  от  1  до  l

k

  состоит  из  генов  первого 

родителя, а на позициях от k + 1 до L - из генов второго родителя; 

2)  Потомок,  хромосома  которого  на  позициях  от  1  до  k  состоит  из  генов  второго 

родителя, а на позициях от l

k

 + 1 до L - из генов первого родителя. 

Например, пусть 

= 01##1, 

= 10010, тогда случайным образом выбирается точка 

разрыва  –  участок  между  соседними  двоичными  цифрами  в  обеих  хромосомах,  т.е.  обе 

хромосомы  разрываются  на  два  сегмента  по  этой  точке.  Затем,  соответствующие  сегменты 

различных родителей склеиваются и получаются два генотипа потомков.  

Оператор мутации с вероятностью р

т

 изменяет значение гена в заданном хромосоме 

на  любое  другое  возможное  значение.  Например,  если  в  хромосоме 

= 1#011  мутации 

подвергается ген на позиции 4, то его значение, равное 1, изменяется на 0.  

Формирование  новой  популяции  происходит  в  результате  применения  генетических 

операторов  к  хромосомам  временной  родительской  популяции.  В  результате  поучится 

текущая  популяция  для  данной  итерации  генетического  алгоритма.  Выполнения 

классического  генетического  алгоритма  приведет  к  тому,  что  вся  предшествующая 

популяция хромосом замещается новой популяцией потомков, имеющей ту же численность. 

Выбор  “наилучшей”  хромосомы.  Если  условие  остановки  алгоритма  выполнено,  то 

следует  вывести  результат  работы,  т.е.  представить  искомое  решение  задачи.  Лучшим 

решением считается хромосома с наибольшим значением функции приспособленности. 

Работа  ГА  представляет  собой  итерационный  процесс,  который  продолжается  до  тех 

пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. 

На  каждом  поколении  ГА  реализуется  отбор  пропорционально  приспособленности, 

кроссовер и мутация.  

Генетический ассиметричный криптоалгоритм состоит из шагов [3]: 

Шаг 1. Генерация 4 точек для скрещивания и 3 для операции мутации в диапазоне от 0 

до15. 

Шаг 2. Сортировка этих числа в порядке увеличения.  

Шаг 3. Генерация случайного числа перестановки в диапазоне от 1 до 7. 

Шаг 4. Генерация случайного закрытого ключа в диапазоне от 0 до15.  

Шаг  5.  Генерация  открытого  ключа 

О

,  состоящего  из  точек  скрещивания,  мутации, 

коэффициента перестановки и случайного числа. 

Шаг 6. Генерация закрытого ключа 

З

 

 по формуле 

З

=

О

  ⊕   . Здесь  R - 36 битное 

бинарное  число,  полученное  путем  повторения  закрытого  случайного  числа  9  раз,  а 

⊕  – 

операция  «логического  или»(xor)

 

Так  как.  операции  симметричны  можно  будет  получить 

открытый ключ из закрытого: 

О

=

З

  ⊕   .  

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

402 

 

Следовательно, если текст будет зашифрован открытым ключом значит он сможет быть 

расшифрован закрытым ключом с связи с зеркальностью задействованных операций.  

Шаг 7. Запись пары ключей в файл. 

Шаг 8. Чтение 2 блоков по 16 байт каждый из файла для шифрации. 

Шаг 9. Если количество байтов достаточно переходим к шагу 11. 

Шаг  10.  Если  байтов  недостаточно  добавляем  пробелы,  чтобы  получить  16  байтные 

блоки. 

Шаг 11. Производим перевод полученных байтовых блоков информации. 

Шаг 12. Операции скрещивания и мутации над блоками на 11 шаге. 

Шаг 13. Запись зашифрованных блоков в файл. 

Шаг 14. Если имеется дополнительная информации к шифрации, то повторить действие 

с 8 шага. 

Предложен  алгоритм  генерации  ассиметричных  ключей,  основанных  на  генетических 

операциях  скрещивания  и  мутации  для  шифрации  и  дешифрации  сообщений.  Для  работы 

алгоритма  использованы  4  точки  скрещивания  и  3  точки  мутации,  1  байт  перестановки,  1 

байт  случайного  числа  и  длина  ключа  составила  36  бита.  Алгоритм  может  быть  усложнен 

для  взлома,  если  стороны  заранее  утвердят  секретный  фактор  перестановки.  Это  в  купе  с 

случайностью делает алгоритм сложным для взлома.  

 

Литература: 

 

1. Menezes A. J., van Orshot P. S., Vanstone, Handbook of applied cryptography. CRC Press. 1997. 

2.  J.  H.  Holland.  Adaptation  in  natural  and  artificial  systems.  University  of  Michigan  Press,  Ann 

Arbor, 1975.  

3.  Dr.  Poornima  G.  Naik,  Asymmetric  Key  Encryption  using  Genetic  Algorithm,  International 

Journal of Latest Trends in Engineering and Technology (IJLTET), Vol. 3 Issue 3 January 2014. 

 

 

УДК 519.7 

 

ШАРИПБАЙ А.А. 

 

АВТОМАТНЫЕ МОДЕЛИ ШИФРАТОРОВ В ЭЛЕКТРОНИКЕ И КРИПТОГРАФИИ 

 

(ЕНУ имени Л.Н. Гумилева, г. Астана, Казахстан) 

 

В  работе  предлагаются  комбинационные  и  последовательные  автоматные  модели 

шифраторов, используемые в электронике и криптографии, показываются их достоинства и 

недостатки, а также обсуждаются возможность программной и аппаратной реализации этих 

моделей. 

Сначала  дается  определение  комбинационного  и  последовательного  автомата  из 

теории автоматов, затем определение шифратора и дешифратора.  

Автомат – это математическая модель дискретного устройства и в зависимости от его 

возможности  может  быть  распознающим  или  преобразующим.  Нас  интересуют  только 

преобразующие  автоматы,  которые  распознают  входные  последовательности  и  порождают 

выходные  последовательности,  т.е.  выполняет  некоторую  функцию,  определенную  на 

множестве  входной  последовательности  и  выдающую  результат  из  множества  выходной 

последовательности.  В  свою  очередь,  преобразующие  автоматы  подразделяются  на 

комбинационные  автоматы  (автоматы  без  памяти)  и  последовательные  автоматы 

(автоматы с памятью) [1]. 

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

403 

 

Шифратор 

(кодер) 

– 

это 

математическая 

модель  

устройства, 

выполняющего логическую  функцию (операцию)   преобразование  дискретного  сигнала 

(дискретной информации) из одного (исходного) представления в другое (результирующее) 

представление.  

Дешифратор  (декодер) -  это  математическая  модель устройства,  преобразующего 

результирующее  представление  в  исходное  представление.  Другими  словами,  дешифратор 

осуществляет выполнение обратной функции  

Шифраторы  и  дешифраторы широко  используются  в  электронике  и      криптографии.  

В  электронике  их  можно  моделировать  с  помощью  комбинационных  автоматов,  а  в 

криптографии – с помощью последовательных автоматов.    

Ниже  описываются  комбинационные  и  последовательные  автоматы  и  использую 

материалы из [2, 3] строятся автоматные модели шифратора в электронике и криптографии 

соответственно.   

Комбинационный  автомат  является  однотактным  и  задается  своими  входными  и 

выходными  сигналами,  которые  представляются  двоичными  векторами,  и  функциональной 

моделью в виде систем логических уравнений.   

Если через векторов 

)

,...,

,

(

2

1

x

x

x

n

 и 

)

,...,

,

(

2

1

y

y

y

m

 обозначим входные и выходные 

сигналы,  а  через 







m

,...,

,

2

1

  -  логические  функции,  то  функциональная  модель  

комбинационного  автомата  можно  представить  в  виде  следующей  системы  логических 

уравнений:  















)

,...,

,

(

)

,...,

,

(

2

1

2

1

1

1

x

x

x

y

x

x

x

y

n

m

m

n







                          (1) 

Теперь рассмотрим задачу синтеза комбинационных автоматов, которая сводится к их 

построению по заданному поведению вход-выход и включает несколько этапов [4]: 

1. 

Блочный синтез, в котором сложный автомат разделяется на более простые 

блоки с определением их входов и выходов, связей между самими блоками и внешней среды 

в  различных  режимах  работы  автомата,  решаемых  задач  блоками  и  общего  плана  обмена 

между ними;    

2. 

Логический  синтез,  который  состоит  из  двух  подэтапов:  абстрактного  и 

структурного синтеза: 

2.1. Абстрактный синтез, в котором осуществляется переход от словесного описания 

условий работы автомата к построению таблиц переходов и выходов; 

2.2. Структурный  синтез,  в  котором  определяются  состав  элементов  и  связи  между 

ними с применением аппарата алгебры логики.  

3. 

Технический  синтез,  в  котором  решаются  технологические  вопросы 

аппаратной реализации автомата. 

Здесь  этап блочного синтеза при синтеза простого автомата не нужен, а при синтеза 

сложного автомата возможно неоднократное возвращение к нему.  

Среди  указанных  этапов  наиболее  сложным  является  логический  синтез,  который 

сводится к построению логических функций с помощью логических выражений и разработке 

функциональных схем из логических элементов.  При этом число логических функций равно 

числу выходов дискретного автомата. 

Последовательный  автомат,  в    отличие  от  комбинационного  автомата,  помимо 

входных и выходных сигналов наделен внутренними состояниями, позволяющими ему быть 

многотактным.  Символы,  обозначающие  внутренние  состояния  автомата  хранятся  в  его 

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

404 

 

внутренней  памяти.  Поэтому  последовательный  автомат  иногда  называют  автоматом  с 

памятью. 

Формально последовательный автомат определяется как пятерка 

 

,

,

,

,

,









Y

X

S

A

     (2) 

где:  

}

,...,

,

{

2

1

s

s

s

S

l



– конечный алфавит символов состояний; 

}

,...,

,

{

2

1

x

x

x

X

n



– конечный алфавит входных символов; 

}

,...,

,

{

2

1

y

y

y

Y

m



– конечный алфавит выходных символов; 

S

X

S





:



– функция переходов; 

Y

X

S





:



– функция выходов;  

Если функции переходов δ и функции выходов λ однозначно определены для каждой 

пары (s

k

,  x

i

)SX  (k=1,  2,  …,  l;    i=1,  2,  …,  n),  то  последовательный  автомат  называется 

детерминированным  автоматом  или  полностью  определенным,  а  в  противном  случае  - 

недетерминированным  автоматом  или  частично  определенным  автоматом,  т.е.  область 

определения  функции  D(δ)    и    D(λ)  являются  подмножествами  множества  SX:  D(δ)

⊆SX, 

D(λ)

⊆SX.  Если  автомат  имеет  выделенное  начальное состояние s

0

S,  то  он 

   

называется 

инициальным автоматом.  

Последовательный  автомат  функционирует  в  дискретные  моменты  времени:  в 

каждый  момент  времени  автомат,  находясь  в  определенном  состоянии  и  распознав 

очередной  входной  символ  переходит  в  следующее  состояние  и  порождает  следующий 

выходной  символ.  Иначе  говоря,  последовательный  автомат  для  последовательности 

входных символов 

],...

3

[

],

2

[

],

1

[

3

2

1

x

x

x

i

i

i

  разворачивает в моменты времени t = 1, 2, 3, …  

последовательность 

очередных 

состояний 

автомата 

],...

3

[

],

2

[

],

1

[

3

2

1

s

s

s

k

k

k

 

и 

последовательность выходных символов

],...

3

[

],

2

[

],

1

[

3

2

1

y

y

y

j

j

j

 .  

По 

способу 

формирования 

функций 

выходов 

автоматы 

делятся 

на 

автомат Мили и автомат Мура. 

Функционирование  автомата  Мили  в  дискретные  моменты  времени  t  для  всех 

значений k=1, 2, …, l;  i=1, 2, …, n;   j=1, 2, …, m   может быть описано следующей системой 

рекуррентных соотношений:  



















))

(

),

(

(

)

(

))

(

),

(

(

)

1

(

1

t

x

t

s

t

y

t

x

t

s

t

s

i

k

j

i

k

k

t

t

t

t

t

t





               (3) 

Функциональная схема автомата Мили представлена на рисунке 1. 

 

 

жүктеу/скачать 14,62 Mb.

Достарыңызбен бөлісу: