Гашков С.Б. Современная элементарная алгебра в задачах и решениях

Подождите немного. Документ загружается.

§ 2.9. Алгебра и криптология 121

шифровалась парой своих координат (i, j) (номерами строки и столб

ца), а передаваться сообщения могли в то время с помощью факелов

––

i факелов в левой руке и j факелов в правой означали пару (i, j).

Кстати, этот шифр представляет, вероятно, первый пример так на

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

каждая буква алфавита сообщения заменяется на слово в более коротком

шифроалфавите.

Дальнейшее развитие идеи алфавитного кодирования принадлежит

знаменитому английскому философу, эзотерику и писателю сэру Френ

сису Бэкону, который начал использовать двоичный алфавит в качестве

шифроалфавита. В криптографии, правда, это не нашло особого при

менения, главным образом из

за пятикратного удлинения шифртекста

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

дов (азбука Морзе), которые сейчас вышли из употребления и их роль

в каком

то смысле играют компьютерные коды, например, ASCII

код,

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

слепых, или штрих

кодов на товарных наклейках *.

Возвращаясь к истории, следует сказать, что первые идеи криптогра

фии, такие, как замена символов, появились в Древнем Египте и Шумере.

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

текстов, медицинских рецептов и пр. Ее развитие сдерживалось слишком

большой сложностью идеографического письма.

Первое применение в политических целях криптографии и крип-

тоанализа, т. е. науки о чтении криптограмм при неизвестном шифре

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

да, не сохранилось информации, как и какие шифры они умели

вскрывать.

С тех пор криптография применялась в основном уже с политически

ми целями. О том, как это делали греки, уже говорилось. После них, как

и в математике, эстафету приняли арабы. Само слово

шифр

арабского

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

Тысячи и од

ной ночи

. Первую в истории книгу, посвященную описанию некоторых

шифров, написал в 855 г. Абу Бакр Ахмед бен Али ан Набати.

В 1412 г. Шехаб аль Кашканди в своей 14

томной энциклопедии

поместил раздел под названием

О сокрытии в буквах тайных сообще

ний

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

сание вскрытия шифров методом частотного анализа. Статистику

встречаемости букв и биграмм он составил на основе текста Корана.

* Черные и белые промежутки в них соответствуют последовательностям нулей и единиц

длины от 1 до 4.

122 Глава II. Числа и группы

С этого момента начинает свою историю криптоанализ. Кстати, этим ме

тодом успешно вскрываются аффинные шифры, описанные выше.

В Европе, после периода застоя в темные века и в раннем средневеко

вье, криптография, как и математика, начала бурно развиваться в Италии.

Первый зашифрованный текст, хранящийся в архивах Ватикана, датиру

ется XIV в., а первый простейший шифр

––

XII в.

В XIV в. секретарь Римского папы Габриэль де Лавинда, помимо

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

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

которые заменялись кодовыми словами. Вообще кодом называется

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

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

номенклатором. Так же стали называться гибридные системы, сочета

ющие в себе свойства и шифра, и кода. Со времен Габриэля де Лавинды

именно номенклаторы стали на 450 лет основой шифровального дела

в Европе.

В 1401 г. в Мантуанском герцогстве был впервые изобретен первый

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

В 1474 г. появилась книга о тайнописи Чико Симонетти, секретаря

Миланского герцога. Это был, вероятно, первый в мире трактат, по

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

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

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

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

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

философ, художник и архитектор Леон Альберти *. В 1466 г. в своем тру

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

движного большого и подвижного малого соосных дисков, на которых

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

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

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

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

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

таким образом, Альберти фактически положил начало многоалфавит-

ным шифрам, которые стали впоследствии основным классом шифров,

используемых с серьезными целями. Кроме того, он составил большой

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

от 11 до 4444. Если слово из номенклатора встречалось в тексте, оно

* Л. Б. Альберти (Leon Battista Alberti, 1404

–

1472). Сформулировал законы перс

пективы.

§ 2.9. Алгебра и криптология 123

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

диска наравне с другими словами. Таким образом, Альберти изобрел ко-

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

в конце XIX в. Свой шифр он назвал

шифром, достойным королей

Следующий шаг в развитии многоалфавитных шифров сделал в XVI в.

знаменитый философ и эзотерик аббат Иоганн Тритемий, написавший

книгу

Стеганография

. В ней впервые появилась квадратная табли

ца для шифрования. В первой ее строке был написан обычный алфа

вит, во второй строке он был циклически сдвинут влево на одну букву

и т. д. Первая буква шифровалась первым алфавитом, вторая

––

вторым

алфавитом и т. д. Таким образом, шифр Тритемия стал первым примером

периодического шифра. Он имел преимущество перед шифром Аль

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

некоторые промежутки, как у Альберти.

В 1553 г. Джованни Баттиста Белазо предложил использовать для

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

паролем. Пароль периодически выписывался над шифруемым текстом

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

рования соответствующей буквы текста.

Через 10 лет 28

летний Джовании делла Порта опубликовал кни

гу

О тайной переписке

, в которой усовершенствовал идеи Тритемия

и Белазо, а также предложил шифр простой биграммной замены.

В нем с помощью специальной таблицы заменялись на шифросимво

лы пары букв открытого текста. Этот шифр стал первым из класса

блочных шифров, в которых текст разбивается на блоки, которые

потом шифруются. Шифры с побуквенным шифрованием называются

поточными.

Знаменитый математик, изобретатель, врач, астролог, эзотерик

и криптограф Джироламо Кардано, имя которого еще встретится да

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

Эту идею развил французский криптограф барон Блез де Виженер,

который предложил также в таблице Тритемия перемешивать алфавит

в первой строке, и с тех пор ее называют таблицей Виженера. В качестве

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

бавленной в его начало секретной ключевой буквой, известной получа

телю.

Несколько отвлекаясь, заметим, что в средние века криптография

связывалась не столько с математикой, сколько с магией. В своей книге

Д. Кан по существу называет это обывательским предрассудком и объяс

няет его происхождение тем, что алхимики и астрологи часто зашифро

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

124 Глава II. Числа и группы

a b c d e g f i j k l m n o p q r s t u v w x y z

b c d e g f i j k l m n o p q r s t u v w x y z a

c d e g f i j k l m n o p q r s t u v w x y z a b

d e g f i j k l m n o p q r s t u v w x y z a b c

e g f i j k l m n o p q r s t u v w x y z a b c d

g f i j k l m n o p q r s t u v w x y z a b c d e

f i j k l m n o p q r s t u v w x y z a b c d e g

i j k l m n o p q r s t u v w x y z a b c d e g f

j k l m n o p q r s t u v w x y z a b c d e g f i

k l m n o p q r s t u v w x y z a b c d e g f i j

l m n o p q r s t u v w x y z a b c d e g f i j k

m n o p q r s t u v w x y z a b c d e g f i j k l

n o p q r s t u v w x y z a b c d e g f i j k l m

o p q r s t u v w x y z a b c d e g f i j k l m n

p q r s t u v w x y z a b c d e g f i j k l m n o

q r s t u v w x y z a b c d e g f i j k l m n o p

r s t u v w x y z a b c d e g f i j k l m n o p q

s t u v w x y z a b c d e g f i j k l m n o p q r

t u v w x y z a b c d e g f i j k l m n o p q r s

u v w x y z a b c d e g f i j k l m n o p q r s t

v w x y z a b c d e g f i j k l m n o p q r s t u

w x y z a b c d e g f i j k l m n o p q r s t u v

x y z a b c d e g f i j k l m n o p q r s t u v w

y z a b c d e g f i j k l m n o p q r s t u v w x

z a b c d e g f i j k l m n o p q r s t u v w x y

Рис. 20. Квадрат Виженера

шифра. Но этот предрассудок дожил почти до нашего времени, и в на

писанной в 1928 г. книге американца Мэнли Холла

Энциклопедическое

изложение масонской, герметической, каббалистической и розенкрейце

ровской философии

, переведенной у нас в 1992 г., есть раздел о крип

тографии, написанный отнюдь не с научных позиций. Заметим еще, что

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

Пико де Мирандолла, Агриппа, Парацельс, Джордано Бруно и другие,

была широко распространена в средневековье. И Тритемий, и Кардано

писали о ней в тех же книгах, в которых они описывали свои шифры *.

Кардано также предложил использовать для шифрования поворот-

ную решетку. Она представляла собой твердый трафаретный лист,

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

* См. об этом книгу Фр. Йейтс

Джордано Бруно и герметическая традиция

§ 2.9. Алгебра и криптология 125

на бумагу того же размера, а в прорезях писалось сообщение. После

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

сообщение.

Подобным методом пользовались, например, кардинал Ришелье

и А. С. Грибоедов во время своей дипломатической работы.

Фактически это был метод не столько шифрования, сколько стегано-

графии. Под стеганографией понимаются сейчас методы скрытия самого

факта передачи секретного сообщения, чем она отличается от криптогра

фии, в которой сам факт передачи криптограммы никак не маскирует

ся. Как стеганографический метод применял свой двоичный код Френ

сис Бэкон. Вместо двоичных цифр он использовал обычный алфавит,

но со шрифтами двух типов. Таким методом можно было в любом тексте

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

чимы.

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

ся наследием возникшего в средневековье тайного мистического ордена

розенкрейцеров, появилась идея, что Френсис Бэкон, которого считали

розенкрейцером, является настоящим автором пьес Шекспира. Нача

ли искать подтверждение этого в шифрах, которые мог оставить Бэкон

в своих книгах, а также в первом знаменитом издании пьес Шекспира.

Было, естественно, найдено много таких, якобы зашифрованных, фраг

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

ном тексте можно при желании и некоторых натяжках найти короткие

фрагменты, напоминающие шифры. Но у сторонников авторства Бэко

на стремление доказать это криптографическим методом приняло форму

мании. Американский миллионер Фабиан даже создал в начале XX в.

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

подобными исследованиями.

Фабиан нанял на работу дипломированного генетика Уильяма Фрид

мана, сына эмигрантов из России. Через некоторое время Фридман уже

возглавлял у Фабиана и лабораторию генетики, имевшую прикладную

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

Доказать авторство Бэкона он не смог, более того, он впоследствии опуб

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

доказательства. Но он не на шутку увлекся криптографией и своей подчи

ненной Элизабет Смит, с которой обвенчался в 1917 г. Они стали самой

знаменитой супружеской парой в истории криптографии. После вступ

ления Америки в войну у него с супругой появилась серьезная работа

по правительственным заказам. После войны он ушел от Фабиана и стал

главным криптографом войск связи. Фридман опубликовал выдающие

ся работы по криптоанализу, частью у Фабиана, частью позднее, где

126 Глава II. Числа и группы

изложил свои методы. Сам термин

криптоанализ

был введен Фрид

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

пурпурного шифра

перед началом Второй мировой войны. Успехи аме

риканского криптоанализа сыграли едва ли не решающую роль в побе

де над Японией.

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

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

лики Джованни Соро

––

первого криптоаналитика, получившего широкую

известность в XVI в., выдающегося математика Франсуа Виета, бывше

го членом тайного совета Генриха IV, Филиппа ван Марникса, автора

мелодии гимна Нидерландов и правой руки Вильгельма Оранского, ко

торый во время восстания голландцев и фламандцев против испанского

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

того английского криптоаналитика Томаса Фелиппеса, который прочитал

шифрованное письмо Марии Стюарт, находившейся в плену у королевы

Елизаветы (и сделал вставку). Эта история закончилась трагически для

Марии и показала еще раз, что слабый шифр еще хуже, чем отсутствие

шифра вообще.

До XVII в. криптоанализ был формально делом любителей, хотя ино

гда и выполнявших важные государственные поручения. В XVII в. в Ев

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

ния, называемые неофициально

черными кабинетами

. Первый такой

кабинет организовал во Франции Ришелье. Начальником кабинета стал

первый профессиональный криптограф Франции Антуан Россиньоль, ко

торый внес большой вклад в дело совершенствования номенклаторов.

Позднее возник такой кабинет и в Англии. В нем работал крупнейший

английский математик того времени Джон Валлис *.

Следующий век не дал новых идей в криптографии, но был временем

расцвета черных кабинетов. Во время царствования Петра I они появи

лись и в России. Сам Петр проявлял интерес к криптографии и обсуждал

эти проблемы с Лейбницем, которого приглашал в Россию для органи

зации Академии наук. Лейбниц в Россию не поехал, но Академия все

равно была создана. Уже после смерти Петра в ней стали работать Эйлер

и Даниил Бернулли. При Елизавете с успехом работал черный кабинет,

в котором играл важную роль приятель Эйлера, известный математик

академик Христиан Гольдбах, получивший за оказанные Российской им

перии услуги звание тайного советника. Благодаря его деятельности чи

талась вся дипломатическая переписка.

* Дж. Валлис (John Wallis, 1616

–

1703)

––

английский математик и криптограф, один из

основателей Лондонского королевского общества.

§ 2.9. Алгебра и криптология 127

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

люционного подъема в XIX в. Но тогда же, в XIX в., возникли новые

идеи в криптографии. Появились первые дисковые шифраторы. Один

из них был изобретен будущим президентом США Томасом Джеффер

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

в его бумагах в 1922 г. Как раз в этом году в армию США стали по

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

Другие варианты дисковых шифраторов были созданы Д. Уодсвортом

в 1817 г. и известным физиком и изобретателем Чарльзом Уитстоном,

показавшим свой шифратор в 1876 г. на Всемирной выставке в Париже.

Уитстон также изобрел шифр, называемый иногда шифром Плейфера,

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

очень на него похожего.

Шифр Плейфера

––

Уитстона является блочным биграммным шиф

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

клетки таблицу записаны в перемешанном виде буквы алфавита. Текст

разбивается на двубуквенные блоки

––

биграммы, промежутки между

словами заменяются самой редкой буквой алфавита. Произвольная

биграмма (a, b) заменяется на биграмму (c, d) которую определяют сле

дующим образом. Находят буквы a, b в таблице Плейфера. Если они

не стоят на одной линии (строке или столбце), то берется прямоугольник

с вершинами в четырех клетках таблицы, в двух противоположных вер

шинах которого стоят буквы биграммы (a, b). Тогда буквы, образующие

вторую диагональ, составляют биграмму (c, d), причем для определен

ности буква c берется с той же вертикальной линии, что и буква a.

Если же буквы a, b стоят на одной линии, то, например, буквы c, d

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

по этой линии в фиксированном направлении (вниз или вправо).

В криптоанализе крупного успеха добились независимо друг от друга

эксцентричный английский математик и изобретатель Чарльз Бэббидж *

и отставной майор прусской пехоты Фридрих Казисски. Им удалось найти

метод вскрытия шифра Виженера. Однако Беббидж не опубликовал сво

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

(в это время шла Крымская война), и о них стало известно лишь недав

но (опубликовано в книге Саймона Сингха (Singh Simon, Code Book,

Doubleday, 1999)). Казисски опубликовал свою книгу в 1863 г., но она

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

графией. Дальнейшее усовершенствование метода Казисски

––

Бэббиджа

опубликовал в своих лекциях по криптоанализу в 1920 г. У. Фридман.

* Ч. Бэбидж (Charles Babbage, 1792

–

1871).

128 Глава II. Числа и группы

В XIX в. криптография впервые стала упоминаться и в художе

ственной литературе. Выдающийся американский писатель и поэт Эдгар

По, мастер мистической и таинственной новеллы, создатель жанра де

тектива и литературы ужасов, написал знаменитый рассказ

Золотой

жук

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

Впоследствии вскрытие шифров описывалось также в рассказах о Шер

локе Холмсе А. Конан Дойля. Эдгар По был криптографом

любителем,

неоднократно писал о криптографии в журналах, с успехом разгадывал

шифровки, присылаемые ему читателями. Он написал также хорошую

популярную статью

Криптография

, перевод которой опубликован

в его двухтомнике, изданном в 1995 г. в Санкт

Петербурге. В част

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

разделе.

В XX в. криптография развивалась очень бурно. В двадцатые годы

были в Голландии Кохом, в Германии Шребиусом, в США Хеберном,

а в Швеции Даммом и Хагелиным запатентованы несколько вариан

тов колесных шифраторов. Но только Борису Хагелину, родившемуся

в России сыну Цезаря Хагелина, управляющего нефтяной компанией

Нобеля, удалось благодаря заказам американской армии добиться ком

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

лионы на криптографии.

Когда компания, основанная Шребиусом, прекратила существование,

производящейся ею шифровальной машиной

Энигма

заинтересовались

в германской армии и она стала широко использоваться, а ее произ

водство было возобновлено. Работавшему на заводе по ее производству

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

до польских криптографов. После начала войны Мариан Режевский, ока

завшийся в Англии, указал английским криптографам на возможность

вскрытия шифров

Энигмы

. В дальнейшей работе участвовал много

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

математик Алан Тьюринг. Если бы немецкие шифровальщики пользо

вались

Энигмой

аккуратно, с соблюдением всех инструкций, то чи

тать их шифровки было бы невозможно. Но разгильдяйство свойственно

и немцам...

Информация о том, что англичанам удалось научиться читать шиф

ровки

Энигмы

, была рассекречена только в 1970

е годы. Одна из при

чин была в том, что после войны в Европе она еще использовалась

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

Успешно развивалась криптография и в США. Во время Первой ми

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

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

§ 2.9. Алгебра и криптология 129

стран. Но знаменитую телеграмму Циммермана, которая послужила для

США одним из формальных поводов объявления войны Германии, прочли

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

то заполучить немец

кие шифры). Однако после войны, вопреки ожиданиям Ярдли, финанси

рование этой деятельности было прекращено и тогдашний госсекретарь

США, впервые узнавший о существовании черного кабинета, произнес

легендарную фразу:

Джентльмены не читают писем друг друга

. Ярдли

оказался без работы и написал книгу о деятельности черного кабине

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

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

ле и японский. Японцы выводов из нее, однако, не сделали и полностью

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

войну на Тихом океане. Во время Второй мировой войны криптографией

занимался выдающийся американский кибернетик Клод Шеннон. Имен

но в это время он заложил основы теории информации и теории связи

в секретных системах.

В XX в. еще активнее теоретического развивался

прикладной крип

тоанализ

, проще говоря, покупка или воровство шифров и шифромашин.

Об успехах в этой области советских спецслужб много написано в книге

Кана и недавно вышедшей у нас книге Б. Анина. Впрочем, и американ

цы не отставали. Об успехах советской теоретической криптографии Кан

отзывается также высоко *, но по понятным причинам имен советских

криптографов, за исключением некоторых, работавших в 20

–

е годы,

он не называет. Вероятно, они останутся в области легенд **.

В 1970

е годы произошла криптографическая революция, вывед

шая криптографию из области секретности. Впервые был опубликован

шифр в качестве стандарта (раньше это словосочетание было просто

нелепостью!)

––

это американская криптосистема DES (первое название

Люцифер

). Она рекомендована для шифрования данных в компью

терах и другой электронной технике. В секрете надо хранить лишь

* В одной своей книге он дал такое определение великой державы: великая страна

––

это страна, имеющая ядерное оружие, межконтинентальные ракеты и криптографию.

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

графические службы, довольно широко известны, например, Глеб Бокий. Д. Кан написал

о нем достаточно подробно, но далеко не все. Недавно Бокий стал, например, героем книги

О. Шишкина

Битва за Гималаи

с подзаголовком

НКВД: магия и шпионаж

, упоминает

ся в книге А. Виноградова

Тайные битвы XX столетия

и др. Там рассказывается о тайных

организациях мистико

масонского типа, в которые он был вхож, о странных экспедициях

в Тибет (Тибетом почему

то интересовались и в гитлеровской Германии), о подчинявшихся

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

Но, возможно, это все тоже легенды. Достоверно известно только, что он был расстрелян

в 1937 г.

9 Гашков

130 Глава II. Числа и группы

битный ключ *. Начали публиковаться в открытой печати и другие

шифры, а также возможные атаки на них. Недавно прошел открытый (!)

конкурс на замену этого стандарта, и уже утвержден новый стандарт **.

Тогда же, в 70

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

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

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

конференции.

Опишем одну из самых простых и самых популярных систем открыто

го шифрования

––

систему RSA (Ривеста

––

Шамира

––

Адлемана). Вся ма

тематика этой системы основана на теореме Эйлера, с помощью которой

доказывается следующее утверждение.

Упражнение 55. Пусть n = pq, где p, q

––

различные простые,

t ∈Z

∗

ϕ(n)

t =

1. Докажите, что отображения x → x

и x → x

являют

ся изоморфизмами группы Z

∗

, взаимно обратными друг другу.

Отображение x → x

группы Z

∗

в себя можно использовать для так

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

стро с помощью компьютера, числа s и n можно сообщить всем же

лающим. Дешифровка также проводится быстро, если известен ключ t.

Проводящему атаку на эту систему для нахождения t из сравнения st ≡1

(mod ϕ(n)) надо знать ϕ(n) = (p − 1)(q −1) = n + 1 − p −q, т. е. p и q.

Вы выбираете p и q очень большими, сообщаете всем n = pq и произ

вольное s, (s, ϕ(n)) = 1, и можете быть уверенными, что пока не будет

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

система будет надежной.

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

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

Задачи и упражнения к § 2.9

1*. (Криптографическая лемма.) В условиях предыдущего упражне

ния докажите, что отображения x →x

и x → x

являются взаимно одно

значными и взаимно обратными не только на подгруппе Z

∗

, но и на всем

кольце вычетов Z

У к а з а н и е. Примените китайскую теорему об остатках.

* Разработчики этого алгоритма из IBM предлагали вначале 128

битный ключ, но под

давлением АНБ

––

Агентства национальной безопасности

––

длина ключа была уменьшена.

Интересно, почему?

** Возможно, в АНБ уже смирились с тем, что криптография выходит из

под контро

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

страны запрещен.