Шифр на основе случайных чисел с неравномерным распределением
Предложен новый принцип построения криптографических систем с применением шифра на основе случайных чисел с неравномерным распределением. Показано, что данный метод шифрования обладает высокой степенью устойчивости к традиционным криптографическим атакам, таким как: перебор всех вариантов ключа, и...
Saved in:
| Date: | 2011 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/51003 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Шифр на основе случайных чисел с неравномерным распределением / Р.М. Михерский // Пробл. програмув. — 2011. — № 4. — С. 90-95. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-51003 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-510032025-02-10T00:06:32Z Шифр на основе случайных чисел с неравномерным распределением Михерский, Р.М. Програмні системи захисту інформації Предложен новый принцип построения криптографических систем с применением шифра на основе случайных чисел с неравномерным распределением. Показано, что данный метод шифрования обладает высокой степенью устойчивости к традиционным криптографическим атакам, таким как: перебор всех вариантов ключа, известный исходный текст и специально подобранные исходные тексты. 2011 Article Шифр на основе случайных чисел с неравномерным распределением / Р.М. Михерский // Пробл. програмув. — 2011. — № 4. — С. 90-95. — Бібліогр.: 14 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/51003 004.056.55 ru application/pdf Інститут програмних систем НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Програмні системи захисту інформації Програмні системи захисту інформації |
| spellingShingle |
Програмні системи захисту інформації Програмні системи захисту інформації Михерский, Р.М. Шифр на основе случайных чисел с неравномерным распределением |
| description |
Предложен новый принцип построения криптографических систем с применением шифра на основе
случайных чисел с неравномерным распределением. Показано, что данный метод шифрования обладает высокой степенью устойчивости к традиционным криптографическим атакам, таким как: перебор
всех вариантов ключа, известный исходный текст и специально подобранные исходные тексты. |
| format |
Article |
| author |
Михерский, Р.М. |
| author_facet |
Михерский, Р.М. |
| author_sort |
Михерский, Р.М. |
| title |
Шифр на основе случайных чисел с неравномерным распределением |
| title_short |
Шифр на основе случайных чисел с неравномерным распределением |
| title_full |
Шифр на основе случайных чисел с неравномерным распределением |
| title_fullStr |
Шифр на основе случайных чисел с неравномерным распределением |
| title_full_unstemmed |
Шифр на основе случайных чисел с неравномерным распределением |
| title_sort |
шифр на основе случайных чисел с неравномерным распределением |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2011 |
| topic_facet |
Програмні системи захисту інформації |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/51003 |
| citation_txt |
Шифр на основе случайных чисел с неравномерным
распределением / Р.М. Михерский // Пробл. програмув. — 2011. — № 4. — С. 90-95. — Бібліогр.: 14 назв. — рос. |
| work_keys_str_mv |
AT miherskiirm šifrnaosnoveslučainyhčiselsneravnomernymraspredeleniem |
| first_indexed |
2025-12-02T00:43:48Z |
| last_indexed |
2025-12-02T00:43:48Z |
| _version_ |
1850355204470341632 |
| fulltext |
Програмні системи захисту інформації
90
УДК 004.056.55
Р.М. Михерский
ШИФР НА ОСНОВЕ СЛУЧАЙНЫХ ЧИСЕЛ
С НЕРАВНОМЕРНЫМ РАСПРЕДЕЛЕНИЕМ
Предложен новый принцип построения криптографических систем с применением шифра на основе
случайных чисел с неравномерным распределением. Показано, что данный метод шифрования облада-
ет высокой степенью устойчивости к традиционным криптографическим атакам, таким как: перебор
всех вариантов ключа, известный исходный текст и специально подобранные исходные тексты.
Введение
В настоящее время для криптогра-
фической защиты информации, в системах
с секретным ключом, наиболее часто ис-
пользуются блочные шифры. Как правило,
при создании современных блочных шиф-
ров их авторам приходится идти на ком-
промисс между скоростью шифрования и
устойчивостью к криптографическим ата-
кам. На сегодняшний момент в среде раз-
работчиков криптографических систем
сложилось мнение, что нужно гарантиро-
вать безопасность системы на протяжении
50 лет с момента ее создания [1]. Тем не
менее, практика показывает, что системы
шифрования оказываются взломанными
гораздо раньше, чем на это рассчитывают
их создатели. Показателен пример шифра
DES, который, принят в 1977 году в США
как официальный стандарт шифрования
[2], к концу 90-х годов 20 века уже безна-
дежно устарел и не мог противостоять
криптографическим атакам [3]. По мнению
ряда авторов, используемый в настоящее
время, в США как официальный стандарт,
шифр AES может быть уязвимым к атакам
с использованием алгоритма XSL [4], к
атакам с использованием информации о
времени выполнения операций [5] и к ата-
кам с применением дифференциального
анализа ошибок [6]. Хотя подобные атаки
на практике пока еще не реализованы, нет
снований утверждать, что они не будут
реализованы в ближайшем будущем.
В данной работе предложен новый
принцип построения криптографических
систем, обладающих значительно большей
устойчивостью к атакам, чем ныне суще-
ствующие коммерчески используемые
системы.
Алгоритм шифрования на основе
случайных чисел с неравномер-
ным распределением
Пусть абоненты А и В решили ор-
ганизовать секретную связь друг с другом.
Для этого они выбирают в качестве ключа
последовательность n случайных целых
чисел }{ ic . Закон распределения этих чи-
сел может быть равномерным, нормаль-
ным, либо любым другим. Значение чисел
выбирается в интервале от 0 до 255.
Пусть абонент А решил переслать
абоненту В секретное сообщение }{ ia
размера N. Числовые значения элементов
сообщения лежат в интервале от 0 до 255.
Для этого он генерирует новую по-
следовательность n случайных целых чи-
сел }{ id . Закон распределения этих чисел
может быть нормальным, либо любым
другим, кроме равномерного распределе-
ния. Значение чисел выбирается в интер-
вале от 0 до 255.
Далее эта последовательность ко-
дируется методом Хаффмана или другим
алгоритмом кодирования с минимальной
избыточностью. Получается новая после-
довательность }{ ig размера 1n , причем
© Р.М. Михерский, 2011
ISSN 1727-4907. Проблеми програмування. 2011. № 4
Програмні системи захисту інформації
91
число элементов в новой последовательно-
сти меньше чем в предыдущей, т. е. nn <1 .
Затем к этой последовательности добавля-
ется nn −1 элементов из шифруемого со-
общения. В результате получается новая
последовательность }{ if размера n (в ре-
альной системе, вообще говоря, число до-
бавляемых элементов шифруемой после-
довательности будет меньше, так как не-
обходимо добавить элементы с информа-
цией о том, где заканчивается последова-
тельность }{ ig , и начинаются элементы
шифруемого сообщения). Далее находится
последовательность }{ ib как сумма соот-
ветствующих элементов ключа }{ ic и по-
следовательности }{ if по модулю 256
т. е.:
)256(modiii cfb += (i=1,…,n). (1)
Затем последовательность }{ ib пе-
редается от абонента А к абоненту В по
открытому каналу. Получив последова-
тельность }{ ib , абонент В находит после-
довательность }{ if по формуле:
)256(modiii cbf −= (i=1,...,n). (2)
Из этой последовательности выде-
ляется nn −1 элементов шифруемого со-
общения, а так же последовательность
}{ ig , которая декодируется методом
Хаффмана или другим соответствующим
алгоритмом кодирования с минимальной
избыточностью. В результате абоненту В
становится известна последовательность
}{ id , а так же nn −1 элементов шифруе-
мого сообщения.
На следующем шаге абонентами А
и В в качестве ключа }{ ic выбирается по-
следовательность }{ id и весь вышеприве-
денный алгоритм повторяется для остав-
шихся элементов последовательности
}{ ia . Подобные циклы продолжаются до
тех пор, пока не будут переданы все N
элементов сообщения }{ ia . При этом,
абоненты будут знать новый секретный
ключ }{ ic размера n, который можно бу-
дет использовать для передачи нового со-
общения.
Недостатки метода шифрования
на основе случайных чисел с не-
равномерным распределением
Следует отметить некоторые недос-
татки вышеизложенного метода шифрова-
ния.
Во-первых, объем зашифрованного
сообщения всегда больше объема исход-
ного. Данный недостаток может быть дос-
таточно серьезным, если необходимо пе-
редавать большие объемы зашифрованной
информации через низкоскоростной канал
связи. Решить эту проблему можно пред-
варительным архивированием исходного
сообщения, что, в свою очередь, также по-
высит устойчивость к атакам зашифрован-
ного сообщения.
Во-вторых, в данной системе шиф-
рования невозможен произвольный доступ
к блокам зашифрованных данных, так как
для того, что бы расшифровать данные в
каком-то из блоков, необходимо расшиф-
ровать все предыдущие блоки.
В-третьих, для эффективной работы
вышеописанной системы шифрования, не-
обходимо применять высокоскоростной
генератор случайный чисел с распределе-
нием отличным от равномерного и обла-
дающий достаточно высокой устойчиво-
стью к криптографическим атакам. Реали-
зация такого генератора является доста-
точно не тривиальной задачей. Рассмотрим
данный вопрос подробней.
Генерация случайных чисел с не-
равномерным распределением
Для генерации случайных чисел, в
настоящее время, используется два подхо-
да. Первый из них связан с созданием и
применением специальных устройств, ис-
пользующих какие-либо физические ис-
Програмні системи захисту інформації
92
точники шума. Естественно, что шум в
них должен иметь доказуемо случайное
поведение. На практике в качестве таких
источников использовались: нулевые ва-
куумные колебания электромагнитного
поля [7], нестабильность частоты свободно
колеблющегося осциллятора [8], тепловой
шум полупроводникового диода [9], пока-
зания счётчика Гейгера [10] и т. д.
Как правило, подобные генераторы
позволяют получить случайные числа с
распределением отличным от равномерно-
го, что и нужно для работы вышеописан-
ного алгоритма шифрования.
Однако часто стоит задача получе-
ния случайных величин на обычном пер-
сональном компьютере без применения
дополнительного оборудования. Учитывая
это, зачастую более актуальным является
второй подход, связанный с использовани-
ем событий от стандартных устройств
компьютера: нажатий пользователем кно-
пок на клавиатуре или «мыши»; движение
пользователем мыши; время откликов
принтеров, сканеров, жестких дисков [11];
взаимодействие между потоками; «шум»
видеокарты, счетчик тактов процессора и
пр. Однако каждый из этих способов гене-
рации энтропии имеет свои недостатки.
Так, например, нажатие пользователем
кнопок на клавиатуре или мыши обеспе-
чивает достаточно медленный поток эн-
тропии, кроме этого требует в процессе
работы криптографической системы уча-
стие пользователя, что не всегда возмож-
но. К недостаткам самого распространен-
ного способа генерации энтропии – ис-
пользования счетчика тактов процессора,
можно отнести чувствительность фазового
шума генераторов частоты к внешним по-
мехам, а значит, возможность влиять на
генератор случайных чисел извне [12].
Отметим, что счетчики тактов про-
цессора позволяют получать равномерно
распределенные случайные числа. Для
большинства современных систем шифро-
вания это является преимуществом, так
как именно с такими числами эти системы
и работают. Однако, в данной работе в
описываемой системе, используются не-
равномерно распределенные случайные
числа, поэтому непосредственное приме-
нение генератора случайных чисел на ос-
нове счетчика тактов процессора пред-
ставляется затруднительным.
В работе [13] предложен способ ге-
нерации случайных чисел с помощью оп-
тического манипулятора «мышь». Было
показано, что в определенных, специально
созданных условиях, оптический манипу-
лятор может стать эффективным источни-
ком энтропии в системах криптографиче-
ской защиты информации.
Схема эксперимента показана на
рис. 1.
Рис. 1. Схема эксперимента по ге-
нерации случайных чисел с помощью оп-
тического манипулятора
Оптический манипулятор «мышь»
помещается на поверхность со сложным
рельефом. При этом плоскость нижней по-
верхности мыши ориентируется не строго
параллельно рабочей поверхности как в
стандартном режиме использования, а под
углом в 2 градуса. Это достигается увели-
чением высоты ножек с одной стороны
мыши на 3 мм.
При выполнении вышеприведенных
условий, курсор оптического манипулято-
ра выходит из стабильного положения и
начинает случайным образом перемещать-
ся по экрану монитора. Это связано с тем,
что система обработки изображений ма-
нипулятора в данном случае не может пра-
вильно сфокусироваться на поверхности, и
в системе возникает достаточно сильный
Програмні системи захисту інформації
93
«шум». Координаты X и Y, перемещающе-
гося курсора, определяются и записывают-
ся на жесткий диск с помощью специально
разработанной компьютерной программы.
В качестве случайных чисел в та-
ком генераторе использовались ненулевые
значения цепных абсолютных приростов
XΔ и YΔ координат X и Y.
Гистограммы частот этих величин
показаны на рис. 2 и 3. Там же для сравне-
ния приведены графики нормального рас-
пределения частот.
Рис. 2. Гистограмма частот f нену-
левых цепных абсолютных приростов ко-
ординат XΔ
Рис. 3. Гистограмма частот f нену-
левых цепных абсолютных приростов ко-
ординат YΔ
Как видно из рис. 2 и 3 распределе-
ние случайных чисел, полученных с по-
мощью оптического манипулятора, отлич-
но от равномерного распределения. Это
позволяет использовать полученные таким
образом случайные числа в вышеприве-
денном алгоритме шифрования.
Следует обратить внимание на сле-
дующий недостаток. Скорость генерации
энтропии в таком источнике составляет
всего 971 бит/с. Поэтому использование
подобного метода генерации случайных
чисел не позволит создать высокоскорост-
ную систему шифрования.
Более быстрым и эффективным ме-
тодом генерации случайных чисел с не-
равномерным распределением может ока-
заться использование шума ПЗС-матрицы
подключенной к компьютеру фото- и ви-
део- техники. Однако, данный вопрос тре-
бует подробного дополнительного изуче-
ния.
Преимущества метода шифрова-
ния на основе случайных чисел с
неравномерным распределением
Несмотря на вышеперечисленные
недостатки и трудности, предложенный
способ шифрования обладает достаточным
набором преимуществ. Прежде всего, это
высокий уровень криптографической
стойкости, приближающийся к безуслов-
ной стойкости.
Пусть, например, в качестве ключа
выбрана последовательность 10000 слу-
чайных чисел изменяющихся в пределах
от 0 до 255 и имеющих нормальное рас-
пределение со среднеквадратическим от-
клонением 8=σ .
Тогда энтропия сН , приходящаяся
на один символ этой последовательности,
определяется по формуле [14]:
2
2 2log πσeH с = (3)
и равна 047096,5=сН .
Соответственно энтропия Н , при-
ходящаяся на 10000 символов: 50471=Н .
Таким образом, для подбора ключа необ-
ходим перебор 504712 вариантов, что при
современном развитии вычислительной
техники не представляется возможным. И
маловероятно, что такой перебор удастся
Програмні системи захисту інформації
94
осуществить при любом развитии вычис-
лительной техники в обозримом будущем.
Следует отметить, что вышеопи-
санный метод шифрования так же является
устойчивым к традиционным криптогра-
фическим атакам на основе известного ис-
ходного текста и на основе специально по-
добранных исходных текстов. Действи-
тельно, знание злоумышленником текста,
передаваемого в каком-то из блоков, рав-
носильно знанию им части последователь-
ности }{ ia . Но известные элементы по-
следовательности }{ ia никак не влияют
на генерацию последовательности случай-
ных чисел }{ id используемых для шиф-
рования неизвестных элементов последо-
вательности }{ ia .
Другими словами, знание зло-
умышленником текста, передаваемого в
каком-то из блоков, не поможет ему узнать
сжатый ключ, находящийся в этом же бло-
ке. Соответственно, он никак не сможет
определить текст, зашифрованный в сле-
дующем блоке.
Для любого шифра, применяемого
на практике, одной из самых важных ха-
рактеристик является скорость шифрова-
ния данных. Оценим ее для вышеприве-
денного метода. Как видно из приведенно-
го ранее алгоритма, наиболее ресурсоем-
кими являются операции связанные с ко-
дированием и декодированием методом
Хаффмана. Поэтому скорость шифрования
данных, по порядку величины, будет близ-
ка к скорости кодирования ключевых по-
следовательностей случайных чисел мето-
дом Хаффмана. Следует, отметить, что в
реальных системах, скорость шифрования
скорей всего будет ограничиваться скоро-
стью работы генератора случайных чисел с
неравномерным распределением.
Таким образом, можно сделать вы-
вод, что вышеописанный метод шифрова-
ния может быть применен в криптографи-
ческих системах с повышенными требова-
ниями к безопасности, передаваемой ин-
формации.
1. Фергюсон Н., Шнайдер Б. Практическая
криптография.: Пер. с англ. – М.: Изда-
тельский дом «Вильямс», 2005. – 424 с.
2. ANSI X3.92, “American National Standard
for Data Encryption Algorithm (DEA),”
American National Standards Institute, 1981.
3. Авдошин С.М., Савельева А.А. Криптогра-
фические методы защиты информацион-
ных систем // Известия АИН им. А.М.
Прохорова. Бизнес-информатика. – 2006. –
Т. 17. – С. 91–99.
4. Courtois N., Pieprzyk J. Cryptanalysis of
Block Ciphers with Overdefined Systems of
Equations // Advances in Cryptology –
ASIACRYPT 2002 8th International Confer-
ence on the Theory Application of Cryptology
and Information Security Queenstown, New
Zealand, December 1–5, 2002 Proceedings.
Lecture Notes in Computer Science (2501). –
Springer, 2002. – P. 267–287.
5. Osvik D. A., Shamir A. and Tromer E. Cache
Attacks and Countermeasures: the Case of
AES // Topics in Cryptology - CT-RSA 2006,
The Cryptographers’ Track at the RSA Con-
ference. – Springer-Verlag, 2005. – P. 1–20.
6. Saha D., Mukhopadhyay D., RoyChowdhury
D. A Diagonal Fault Attack on the Advanced
Encryption Standar // Cryptology ePrint Ar-
chive. – 2009.
7. Gabriel C., Wittmann C., Sych D. Dong R.,
Mauerer W., Andersen U. L., Marquard C.
and Leuchs G. A Generator for Unique Quan-
tum Random Numbers Based on Vacuum
States // Nature Photonics.– 2010. – № 4. –
P. 711 – 715.
8. Fairfield R.C., Mortenson R.L. and Koulthart
K.B. An LSI Random Number Generator,
Advances in Cryptology: Proceedings of
CRYPTO 84, Springer Verlag.– 1985. –
P. 203 – 230.
9. Richter M. Fin Rauschgenerator zur Gewin-
nung won quasi-idealen Zufallszahlen fur die
stochastische Simulation.: Ph.D. dissertation,
Aechen University of Technology, 1992.
10. Schneier B. Applied Cryptography, Second
Edition, Protocols, Algorithms, and Source
Code in C. - John Wiley & Sons, Inc., 1996.
11. Davis D., Ihaka R., Fenstermacher P. Cryp-
tographic Randomnes from Air Turbulence in
Disk Drives. – In: Desmedit Y. G. (ed). Ad-
vances in Cryptology – CRYPTO 94. Lecture
Notes in Computer Science. Springer-Verlag.
– 1994. – Vol. 839. – P. 114–120.
12. Ковалев А.В. Реализация генераторов слу-
чайных чисел. – М.: Научная сессия МИ-
ФИ, 2007. – Том 12. – C. 176–177.
Програмні системи захисту інформації
95
13. Михерский Р.М., Попов О.И. Генерация
случайных чисел с помощью оптического
манипулятора // Международный научно-
технический журнал «Проблемы управле-
ния и информатики». – 2011. – № 4. –
C. 152–155.
14. Корн Г., Корн Т. Справочник по математи-
ке (для научных работников и инженеров):
Пер. с англ. – М.: Наука, 1973. – 832 с.
Получено 15.06.2011
Об авторе:
Михерский Ростислав Михайлович,
кандидат физико-математических наук,
заведующий кафедрой «Информатики и
естественно-научных дисциплин».
Место работы автора:
Крымский филиал
Европейского университета,
г. Симферополь,
ул. Трубаченко/Поповкина 10/22.
Тел.: (0652) 49 9969.
mrm03@mail.ru
|