Тема 11. Криптографические шифры

План.

1. Защита информации, понятие шифра и шифрования

2. Простейшие криптографические шифры

Цель. Знакомство с понятием шифр и некоторыми криптографическими шифрами.

Теоретические сведения

1. Защита информации, понятие шифра и шифрования

Как было отмечено в теме Теория и практика кодирования, вместе с проблемой представления ин6формации  компьютере и иных устройствах,  растет проблема не санкционированного доступа к информации. Проблема скрытия информации, вечная. За весь период существования человечества, было изобретено много способов шифровки информации и, не менее бурно, развивалась наука о разгадывании кода информации, его взлома.

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

Проблемами защиты информации занимается наука криптология (от греч. крипто тайный, логос наука), состоящая из криптографии и криптоанализа.

Криптография занимается по­иском и исследованиями математических методов преобразова­ния информации.

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

Современная криптография включает в себя разделы:

~       симметричные криптоносители;

~       криптосистемы с открытым ключом;

~       системы электронной подписи;

~       управление ключами.

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

Криптоаналитики пользуются мате­матическими методами при работе с информацией. Так, методы декодирования включают в себя решение различных уравнений. Первые манипуляции с символами в виде различных кодов возникли с потребностью шифровать информацию.  В старину к проблеме скрытия истинного смысла информации прибегали многое люди, особенно это, касается военных дел, разведки и др.

Разгадывание занимательных заданий, арифметических ребусов, в которых одинаковые цифры заменены одинаковыми буквами, а разные разными, связано с решением уравнений со многими неизвестными и основано на разложении числа по степеням ос­нования q.

Историки и лингвисты используют знания основ криптографии для расшифровки находок, дошедших до нас из глубин веков и выпол­ненных, например, в виде клинописи или иероглифов. В 21 веке удалось расшиф­ровать  древнюю клинопись и  египетскую письменность   иероглифы.

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

Знания математики нужны для того, чтобы найти простую, но надежную систему кодирования, недоступную для расшифровки посторонним лицам, а так же найти способы деко­дирования чужой системы тайнописи, чужих кодов.

Кодирование имеет значение не только в конспиративных целях для шифровки информации. Так, в математике с помощью кодирования изу­чение одних объектов заменяют изучением других, более доступных или уже известных. Ярким примером кодирования в математике является метод координат, введенный Декартом, который дает возможность изучать гео­метрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций формул.

Теория кодирования довольно молодая наука. Исследование надежности кодов получило новый импульс после со­здания в 1948 г. Клодом Эльвудом Шенноном теории информации.

В основе теории информации лежит гипотеза о статистическом ха­рактере источника сообщений. Случайная последовательность знаков не несет информации, так же как и ключ кода. А расшифровать код можно, используя знания о статистических закономерностях сообще­ния и кода. Теория количества информации Шеннона основана на из­вестной со времен Аристотеля альтернативе выбора одного из двух зна­ков между 0 и 1.

С появлением управляющих систем, в частности ЭВМ, роль кодирования существенно возросла и изменилась, так как без кодирования невозможна передача информации. В последнее вре­мя в связи с развитием телекоммуникационных систем и широ­ким использованием вычислительной техники для обработки и хранения информации возникла новая область знаний инфор­мационная безопасность.

Доступность проникновения через Интернет в экономиче­ские, политические, военные системы любой страны выявила новую мировую проблему борьбу с компьютерными взлом­щиками, хакерами, и компьютерными террористами.

Разгадывание занимательных заданий, арифметических ребусов, в которых одинаковые цифры заменены одинаковыми буквами, а разные разными, связано с решением уравнений со многими неизвестными и основано на разложении числа по степеням ос­нования q.

Такие понятия как код, шифр, шифрование, кодирование  давно перешли в разряд математических терминов. Теория шифрования и дешифрования стали очень сложными  разделами математики как науки.

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

1. Найти простую, но надежную систему кодирования, недоступную для расшифровки посторонним лицам,

2. Найти способы деко­дирования чужой системы тайнописи, чужих кодов.

К тайнописи криптографии прибегал Гай Юлий Цезарь, заменяя в своих тайных записях одни буквы другими. Его шифр основывался  на механической замене одних букв или чисел другими.  Подстановки Цезаря достаточно легко поддается дешифровке. Причем сам процесс декодирования аналогичен решению неопределенных урав­нений со многими неизвестными.

В отличие от любой шифровки, в ос­нове принципа кодирования лежит замена исходной информации циф­рами. Так, первый код, придуманный человеком (автор Полибий), состоял из 25 пар, включающих 25 букв и 5 цифр.

Использовали шифрование не только древнегреческие жрецы, но и ученые Средневековья. К таковым можно отнести итальянского  математика Джероламо Кардано, французского Франсуа Виетта, нидерландского  юриста Гроция, английского философа Фрэнсис Бэкона.

Основателем криптографии считается архитектор Леон Баттиста Альберти, живший в 14 веке, который ввел шифрующие коды и много алфавитные под­становки. Далее  Фрэнсис Бэкон доказал в 1580г для передачи информации достаточно двух знаков.

По мнению Бэ­кона, шифр должен отвечать следующим условиям:

~       простота в работе при шифровании;

~       трудность для дешифровки; его надежность;

~       скрытость, не вызывать подозрений,

Шифры Бэкона представлял собой сочетание шифрованного текста с дезинформа­цией в виде нулей. Двузначные коды и шифры использовались задолго до появления ЭВМ.

В наше время потребность в кодировании ин­формации не менее актуальна, чем в былые времена. Шифруется дипло­матическая и экономическая корреспонденция, военные сообщения и медицинские диагнозы, сенсационные сообщения прессы и информа­ция биржевых маклеров.

Кодирование имеет значение не только в конспиративных целях для шифровки информации. Так, в математике с помощью кодирования изу­чение одних объектов заменяют изучением других, более доступных или уже известных.

Ярким примером кодирования в математике является метод координат, введенный Декартом, который дает возможность изучать гео­метрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций формул.

Теория кодирования довольно молодая наука, возникшая в конце 18 и начале 19 века. Так автором первых цик­лических кодов был Ж.Бодо (1889) и и Грей (1953). Обеспечением надежности телеграфных кодов занимался Ван Дурен (1937). Код, исправляющий ошибки, изобрел Ричард Хемминг (1950) и другие.

Исследование надежности кодов получило новый импульс после со­здания в 1948 г. Клодом Эльвудом Шенноном теории информации.

В основе теории информации лежит гипотеза о статистическом ха­рактере источника сообщений. Случайная последовательность знаков не несет информации, так же как и ключ кода. А расшифровать код можно, используя знания о статистических закономерностях сообще­ния и кода. Теория количества информации Шеннона основана на из­вестной со времен Аристотеля альтернативе выбора одного из двух зна­ков между 0 и 1.

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

В частности, в годы Второй мировой войны в группе дешифровки англичан успешно трудился английский математик Алан Матисон Тьюринг (1912- 1954). Благодаря работе этой группы англичане владели спо­собом дешифровки немецкой криптосистемы и своевременно узнавали о планах противника.

С появлением управляющих систем, в частности ЭВМ, роль кодирования существенно возросла и изменилась, так как без кодирования невозможна передача информации. В последнее вре­мя в связи с развитием телекоммуникационных систем и широ­ким использованием вычислительной техники для обработки и хранения информации возникла новая область знаний инфор­мационная безопасность.

На рубеже XX и XXI вв. потребность в защите информации возросла из-за широкого применения ЭВМ и появления сети Интер­нета. Доступность проникновения через Интернет в экономиче­ские, политические, военные системы любой страны выявила новую мировую проблему борьбу с компьютерными взлом­щиками, хакерами, и компьютерными террористами. С одной стороны, стала актуальной разработка эффективной и надежной защиты, с другой, возросла ответственность за воспитание спе­циалистов по работе с ЭВМ, обладающими моральными и нрав­ственными принципами, не противоречащими общечеловечес­ким нормам.

Задание 11-1. Расшифровать запись, представленная на рисунке, используя десятичную систему счислении или серию дедуктивных умозаключений.

Решение. Во-первых, нужно учесть, что в реальной дешифров­ке результат должен быть единственным.

Составим уравнение из цифр из последнего (справа) столбца: 3·А=К, которое на основе понятии вычета можно представить в виде:

(3 • A) mod 10 = К.

Составим уравнение из цифр из второго (справа) столбца: 3·Н=H, которое на основе понятии вычета можно представить в виде:

(3·Н+(3·А-К):10)mod10 = H

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

Рассмотрим иной подход к решению задачи. Для этого представим зашифрованные числа в виде разложения в мно­гочлен по степеням числа 10:

КРОНА = (К • 10⁴ + Р • 10³ + О • 10² +  Н·10+А·10⁰).

3·(К·10⁴ + Р- 10³ + 0- 10² + Н- 10+А- 10⁰) = Ф • 10* + Р • 10³ + А • 10² + Н • 10 + К • 10⁰. Ребус представился уравнением на множестве цифр {О, 1, 2, , 9}.

. Перенесем не­известные влево. После приведения подобных слагаемых получи­ли одно уравнение с шестью неизвестными:

29999 · К- 10000 · Ф 2000 • Р + 300 · О 97 · А + 20 · Н = 0

Получилось  уравнение с 5 неизвестными., при решении которого надо учесть то,  что все неизвестные цифры от 0 до 9, причем Ф и К не равны нулю.

Одночлены расположены в порядке убывания аб­солютной величины коэффициентов

29999 > 10000 > 20000 > 300 > 97 > 20

Вся сумма равна нулю, поэтом можно предположить, что одночлены со знаком + должны принимать наименьшее значение, а одночлены со знаком - должны принимать наименьшие значения.

29 999 · К – принимает минимум при К=1, тогда:

29 999 · К- 10 000 · Ф= 29 999 · 1- 10 000 · Ф=29 999 – 10 000 · Ф принимает по модулю наименьшее значение при Ф=3, поэтому:

29 999 · К- 10 000 · Ф – 2 000 • Р + 300 · О=29 999 – 10 000 · 3 – 2 000 • Р + 300 · О  или:

29 999 – 10 000 · 3 2000 • Р + 300 · О =29 999 – 30 000  2 000 • Р + 300 · О, тогда:

-1 000  2 000 • Р + 300 · О = 0 – наименьшее значение достигается при Р=0:

-1  - 2 000 • 0 + 300 · О = 0 или -1  + 300 · О = 0 отсюда получим, что О=1 – не может, в виду того, что К=1, поэтому берем О=2.

Получили значения букв:  К=1, Ф=3, Р=0, О=2, подставим их в уравнение:

29 999 · К- 10000 · Ф – 2 000 • Р + 300 · О 97 · А + 20 · Н = 0

29 999 · 1- 10 000 · 3 – 2 000 • 0 + 300 · 2 97 · А + 20 · Н = 0

Рассмотрим выражение: 599 97 · А, оно принимает наименьшее значение по модулю при А=6 или А=7. Проверка показывает, что 599 97 · 6 +20·Н=0 или 17+20·Н=0 – не имеет решения для Н равным одному из оставшихся значений.4,5,7,8,9. Выбираем А=7, тогда:

599 97 · 7 + 20 · Н = 0 или -80+20·Н=0, Н=4.

Итак, К=1, Ф=3, Р=0, О=2, А=7, Н=4

Ответ: КРОНА= 10 247, ФРАНК=30741.

Число слагае­мых в сумме	Вид суммы	Знак последующего слагаемого	Значение буквы	Значение СУММЫ
1	29999 • К	Не использован (-)	К = 1 К¹ 0)	29999
2	29999- 10000-Ф	-	Ф = 3	-1
3	-1-2000 • Р	-	Р=0	-1
4	-1 + 300 • О	-	О = 2 т.л. 1 уже есть	599
5	599 97 • А	+ (при А = 6, 17 ++ 20 Н = 0 не решается)	А=7	-80
6	-80 + 20 Н	-	Н=4	0

Предложенное решение называется методом решения числовых ребусов на чашеч­ных весах. Смысл метода заключается в последовательном подборе таких значений неизвестных, чтобы частичные суммы от последовательного сло­жения одночленов этого многочлена принимали минимальное по модулю значение. Решение таких задач можно оформит в виде таблицы.

Здесь дешифровщик уже знал, в каком алфавите зашифрованы сообщения. Малая мощность алфавита десятичной системы по­зволила бы и без метода чашечных весов путем обыкновенного перебора вариантов легко расшифровать ребус. Но на практике перебор всех вариантов осуществляется с помощью ЭВМ, и даже простейшая задача разложения натурального числа на простые множители (а это необходимо при некоторых способах шифрования и дешифрования) требует заведомо большого времени.

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

.

2. Простейшие криптографические шифры

Не возможно описать все известные шифры. Наиболее простейшими из криптографических шифров являются шифры замены, когда одни символы сообщения заменяются другими символами, согласно некоторому правилу. Примером такого шрифта, упомянутый ранее шифр Цезаря и шифр Инженера как частый случаи шифров замены. Создать такой фор можно по договоренности. Другой разновидностью криптографических шрифтов, являются перестановочные шрифты.  Перестановочные шифры получаются путем перестановки символов в сообщении, что также должно проводится согласно каким то либо закономерностям

Шифры замены и перестановочные шрифты не представляют особого интереса. Ими пользуются при создании развлекательных страничек газет и журналов.

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

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

2.1. Числовой метод контроля

Сущность числового метода заключается в том, что код задан­ного числа определяется как остаток деления числа на выбран­ный модуль р:

R_A = A mod P = А [А/P] · р,

где А контролируемое число, в скобках целая часть от деления числа A на P..

Качество контроля во многом зависит от величины модуля р. Если р = q, где q - основание системы счисления, в которой выражено число, то контроль осуществляется только над млад­шим разрядом числа. Если р = q^т, то контролируются все разряды числа, но не фиксируются ошибки в т старших разрядах.

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

Остаток от деления числа на модуль р сравним с самим чис­лом по модулю р, т.е. если

r_A = A mod p, то А = r_A mod p).

~     для суммы А + В = (r_A +r_B)( mod p),

~     для разности r_а+в = (г_а r_B )(mod p),

~     для произведения r_а-в = (г_а · r_b)(mod p).

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

Задание 11-2. Определить контрольные коды данных чисел их суммы, разности, произведения по модулю р.

1. А = 312 и В = 98, р = 15

Решение. Контрольные коды данных чисел равны  г_а = A mod p.

Тогда R_A= 312 mod 15= 12,  R_B = 98 mod 15 = 8.

Учитывая, что А + В= 312 + 98 = 410, получим  г_а+в = 410 mod 15 = 5.

Значит (r_A + r_s)mod 15 =5

Учитывая, что А - В= 312 98 = 214, получим  г_а-в = 214 mod 15 = 4.

Значит (r_A - r_s)mod 15 =4

Комментарии. Коды суммы и разности можно находить, применив свойства сравнений: (r_A + r_s)mod 15 =(12+8) mod 15 =20 mod 15=5

(r_A r_s)mod 15 =(12-8) mod 15 =4 mod 15=4

2. А = 57 и В = 14, р = 5

Ответ Amod5=2, Bmod5=4, (A+B)mod5=1, (A-B)mod 3, (A·B)mod3

2.2. Цифровой метод контроля.

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

Пусть натуральное число А задано в некоторой системе счисления А = (о,, а_ъ , а„). Для получения контрольного кода при цифровом методе контроля необходимо разделить сумму цифр числа на модуль р

Задание 11-3. Найти контрольные коды чисел А = 312 и В = 98, коды их суммы и разности цифровым методом.

Найдем суммы цифр чисел А и В:

X_a =3 + l + 2 = 6; X_b =9 + 8 = 17.

Найдем контрольные коды этих чисел: R_А = 6 mod 15 =  6, R_B = 17 mod 15 = 2.

Найдем суммы цифр для суммы и разности чисел А и В:

С = А + В = 410, X_c =4 + 1 = 0 = 5;

D = A- B=214, X_D=2+1 + 4 = 7.

Контрольные коды суммы и разности чисел С и D:

R_С =5mod 15 = 5; R_D = 7mod 15 = 7.

Сравнив коды суммы и разности чисел, полученные числовым и цифровым методом, установим, что они разные. Ведь, результат контроля должен быть определен одно­значно.

Оказывается, цифровой метод контроля не всегда дает точный результат. Это связано с тем, что:

1. При выпол­нении арифметических действий над числами нарушаются свойства сравнений из-за переносов единиц из одного разряда на другой. В результате каждого переноса q единиц при сложении  из младшего разряда в очередной старший разряд, число единиц старшего разряда первого компонента увеличивается на 1, а сумма цифр получаемого результата уменьшается на 1. При вычитании едет заем единицы старшего разряда и прибавление q единиц к младшему разряду, поэтому сумма цифр результата увеличивается. В десятичной системе q=10; 100; 100 и т.д.

2. Сумма цифр зависит от системы счисления.

С учетом этих замечаний формулы кодов суммы и разности чисел, полученные цифровым методом, имеют уточненный(скорректированный) вид

Пусть даны числа A и B, записанные в десятичной системе счисления

Обозначим через X_A и X_B сумму цифр каждого числа соответственно, а их цифровые коды  через R_А и R_B. Тогда:

R_A+B = (R_А + R_B – L(q-1)(mod p), где L-число переходов в более старший разряд при сложении чисел A и B.

R_A-B = (R_А R_B +S(q-1)(mod p), еде S-число заёмов в более старшем  разряде при вычитании чисел A и B.

Числа  L и S можно вычислить, используя сумму цифр X_A и X_B данных чисел:

и где число 10 есть основание десятичной системы счисления, а  скобки обозначают целую часть числа.

Задание 11-4. Найти контрольные коды чисел А = 312 и В = 98, коды их суммы и разности  скорректированным цифровым методом, если модуль p=15.

Решение. Согласно заданию 9-4 имеем R_А =  6,  R_B = 2. X_a =6; X_b = 17.

=[(6+17):10]=[2,3]=2;  =  [(6-17):10]=[-1,1]=2

R_A+B = (R_А + R_B – L(q-1)(mod p)=(6+2-2(10-1))(mod15)= -10 mod15= 5

R_A-B = (R_А R_B +S(q-1)(mod p)= (6-2+2(10-1))(mod15)=22mod15=7

Полученные результаты полно­стью совпадают с вычисленным ранее, т.е. с помощью новых фор­мул ошибки цифрового метода удалось избежать.

Задание 11-5. Найти контрольные коды чисел А = 57 и В = 14, коды их суммы и разности  скорректированным цифровым методом, если модуль р = 5

Ответ Amod5=2, Bmod5=4, (A+B)mod5=1, (A-B)mod 3, (A·B)mod3

2.3. Выбор модуля для контроля. Числовой метод контроля имеет весомое преимущество над иными методами. Он использует свой­ства сравнений, имеющие достоверный, а не вероятностный ха­рактер. Однозначность полученных ответов облегчает осуществле­ние контроля выполнения арифметических операций, сокращает затраты времени.

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

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

~                         при появлении любой арифметической или логической ошиб­ки изменять сравнимость контрольных кодов;

~                         получение контрольного кода осуществлять предельно упро­щенными средствами.

Компромиссным вариантом для выбора системы счисления служат системы с основанием q = 2^s. Так, восьмеричная  и шестнадцатеричная системы счисления легко переводятся в двоичную. Для того чтобы осуществить переход из двоичной си­стемы счисления в q = 2^s, необходимо разбить двоичное слово справа на кортежи длины S, а затем суммировать результат по модулю р = 2^s - 1.

Таким образом, при S = 2 вся информация разбивается на пары  диады, при S= 3  на триады, при S= 4  на тетрады и т.д.

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

Такие свертки или свернутые коды получаются в процессе сум­мирования образовавшихся кортежей длины 5 по модулю р.

2.4.Цифровая подпись.

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

Кодирование сообщения А заключается в преобразовании F: A®A^d(mod p), где пара (d, р) называется ключом.

Получатель декодирует его таким же преобразованием с помощью ключа (k, р). Очевидно, что получатель принципиально сможет получить исходное А толь­ко если А < р, поэтому если надо закодировать много информа­ции (большое слово), его надо разбить на кортежи длиной, мень­шей р.

Очевидно, операции кодирования и декодирования информа­ции, по сути, тождественны и отличаются друг от друга лишь показателями степени, поэтому для них выполняется переместительный закон:

А ®(A^k) ^d(mod p) = A^kd(mod p) = A^dk(mod p) = (A^d)^k(mod p),

поэтому   A®.(A^d)^k(mod p)

В практике кодирования используются различные приемы, объ­единенные названием цифровая или электронная подпись.

Отправитель кодирует сообщение А закрытым ключом С= A^d(mod p) и посылает получателю информацию, т.е. пару (d, р) в виде подписанного сообщения. Получатель, получив это сооб­щение, декодирует подпись сообщения открытым ключом (k р), т.е. находит А = C(mod p).

Если А = А, то письмо дошло правильно и без помех или оно было отправлено в нешифрованном виде.

Если А¹А, то сообще­ние при передаче было искажено, т.е. произошла потеря инфор­мации.

В теории вычетов доказывается, что при отсутствии помех и выполнения условия взаимной простоты чисел d,k, р, результат А = А достигается всегда.

Задание 11-6. Зашифруйте сообщение А = (4, 3, 2) ключом (5, 7), а затем дешифруйте  его ключом (11,7).

1. Зашифруем. сообщение ключом (5, 7):

4 ® 4⁵(mod 7) = 1024(mod7) = 2,

3 ® 3⁵(mod 7) = 243(mod7) = 5,

2 ®2⁵(rnod7) = 32(mod7) = 4.

Итого, С= F(A) = (2,5,4) – получись зашифрованное сообщение вместо А = (4, 3, 2).

2. Дешифруем сообщение ключом (11,7).

2 ®2^l1(rnod7) = 2048(mod7) =4,

5 ®5¹¹mod7) = 48828 125(mod7) = 3,

4  ® 4¹¹(mod7) = 4194304(mod7) = 2.

Получили A = F¹(C) = {4, 3, 2} = A.

Замечание. Сообщение шифровалось ключом (5, 7), а дешифровалось ключом (11,7). Числа 5,11,7 – взаимно простые числа, алгоритм выбора таких чисел не рассматривается в данном курсе математики.

Сообщение дошло до получателя без искажений. Однако кроме математических проблем могут возникнуть нрав­ственные, например перехват сообщения и замена ключа, а также подмена сообщений неким злоумышленником. Цифровая подпись лишь констатирует факт, что сообщение пришло от того же от­правителя, что и открытый ключ.

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

На основании теоремы Рабина доказано, что разложение на простые множители двух больших чисел эквивалентно раскры­тию ключа для шифра и практически невозможно в реаль­ном времени с учетом возможностей современных ЭВМ.

Шифры с открытым ключом достаточно просты в обращении, практичны и обладают высокой криптостойкостью.

И хотя срав­нительно просто найти пару больших взаимно простых чисел, к настоящему времени не разработаны эффективные алгоритмы разложения чисел на простые множители. Так, разложение на множители числа в 200 и более цифр займет сотни лет работы компьютера. А так как при употреблении шифра с открытым клю­чом используются очень большие простые числа, содержащие сотни цифр в десятичной системе счисления, то вскрыть такие шифры весьма сложно.

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

Получив сообщение, получатель сначала расшифровывает его закрытым ключом, а затем проверяет его подлинность. Для этого он сравнивает дешифрованный текст с тем, который был полу­чен с помощью открытого ключа.

Алгоритмы кодирования и декодирования на самом деле весь­ма сложны. Основные идеи специальных кодов изложены в соот­ветствующей литературе и защищены от злоумышленников на раз­личных уровнях, включая юридическую защиту.

Задание 11-7. Придумать один из шифров замены и перестановки.

Требования к знаниям умениям и навыкам.

Студенты должны понимать проблему криптографических шифров. Иметь представление о видах криптографических шрифтах