Криптография и Свобода - 2
Сказка про числа, которые не хотели ни с кем делиться
В действительном множестве, рациональном подмножестве жили-были натуральные числа. То есть числа 1, 2, 3, 4, 5 и т.д. Их еще иногда «числами в натуре» называли. Основным занятием натуральных чисел было умножаться-делиться в соответствии с операциями умножения и деления. Про умножение - все понятно, любое число могло умножаться с любым другим числом без проблем, а вот с делением все обстояло куда как сложнее. Не со всяким другим числом могло делиться натуральное число, бывало заартачится: не хочу с ним делиться, хоть обнуляйте меня совсем! Столько споров и дискуссий вызывала эта операция деления натуральных чисел, что в конце концов она-то и стала главной в этой сказке.
Понятно, что все делились с числом 1, это число было вроде как Царь-Батюшка во всем множестве натуральных чисел (МНЧ). Но деление с этим числом было совсем безобидное, в результате такого деления каким было число до деления, таким и оставалось после него, вроде как лозунг «Коммунизм победит» в советское время - количество мяса в магазинах от него не изменялось. Поэтому все натуральные числа периодически исполняли этот религиозный обряд - деление на 1 - без каких-либо последствий для себя, просто как символ верности МНЧ и проводимой им политике арифметических операций.
У числа 1, как и у любого нормального Царя, была своя Администрация, где утверждали важнейшие арифметические Законы МНЧ: кто, с кем и как будет делиться. А в штате Администрации были молоденькие запятые, которые целыми днями отпечатывали эти законы на пишущих машинках, ибо компьютеров в те далекие времена в МНЧ еще не знали.
Ну а о другом важном числе - 0 - нельзя со 100% уверенностью сказать, что оно жило в МНЧ. У него был специальный особняк, который все другие числа называли Конторой числа 0, или просто Конторой. Все числа из МНЧ побаивались числа 0, а причина - простая. Само число 0 могло делиться на кого угодно, после чего результат навсегда попадал в Контору, а вот если кто-то сам пытался делиться на 0, то его без лишних эмоций превращали в лагерную пыль. То есть число 0 жило по своим арифметическим законам, отличным от законов МНЧ, и ожидать от него можно было всего, чего угодно.
Число 2 было хитрым. Оно разделило ровно пополам всех обитателей МНЧ на тех, кто с ним делился, и тех, кто это делать категорически отказывался. Первых число 2 называло честными и даже создало из них специальную партию: Партию Честных Чисел. Мы ее, для краткости и по привычке, всюду в этой сказке будем звать просто партией. В партии, как и положено, было создано Политбюро из наиболее известных честных чисел: 2,4,6 и 8. Параграф 1 Устава партии гласил, что в ней могут состоять любые числа, признающие Устав и Программу партии и оканчивающиеся на одного из членов Политбюро. Устав приняли под бурные и продолжительные аплодисменты, но когда число 2 принесло его на согласование в Контору, там параграф 1 дополнили: и 0. Так его и утвердил Царь. А Программа партии была простая: наша цель - бесконечность. Эту программу Царь признал светлым будущим всех прогрессивных чисел из МНЧ.
В партии сразу же появились карьеристы, которые стремились поделиться с числом 2 не один, а целых два раза. Они попытались было, по примеру старших товарищей, создать партию честных - пречестных чисел, но Царь сказал, что и одной партии вполне достаточно, две народ просто не прокормит. Так что название «честное-пречестное число» осталось на уровне анекдотов и народного фольклора.
Число 2, как партийный вождь, было очень идейным. «Удвоение ВВП», «Две нормы за смену» - такие лозунги постоянно появлялись на улицах МНЧ. Оно также очень скрупулезно следило за чистотой партийных рядов, не разрешая одному члену партии делиться на другого. Иногда за такие проступки могли и партбилет отобрать.
А вот за числом 3 закрепилась - как бы это поделикатнее сказать - отличная от числа 2 репутация. Алкогольная. Как соберутся в weekend числа отметить какое-нибудь событие, так обязательно разобьются на группы по три числа в каждой. Часто болела головушка у числа 3, допилось оно в результате до чертиков и стало мистическим символом МНЧ: три богатыря, три белых коня, пятилетку - в три года. Тяжело было числам из МНЧ строить свое светлое будущее - бесконечность, вот и почитателей у числа 3 было достаточно. Вместо красных носов у чисел ходило такое правило: число является алкоголиком, если сумма его цифр - алкоголик. Так и утвердил это правило Царь.
Еще пару слов про число 5. Оно было в Президиуме всех праздничных собраний и юбилейных дат, все в наградах и орденах аж до самого своего нижнего кончика, поэтому и звали число 5 нашим дежурным юбиляром. Безобидное число, партий своих создавать не пыталось, а на выборах всегда выдвигалось от единого и нерушимого блока честных и беспартийных. Делились на него те, у кого на конце было 5. Или 0, справедливо дополнили меня в Конторе.
Кстати, о Конторе. Там собирали разные сплетни из жизни МНЧ и вот какую историю я узнал от местных аборигенов.
В гости к жителям МНЧ часто заезжали другие, ненатуральные числа. И вот как-то раз приехал важный гость - заморское число π, ему как раз на днях исполнилось ровно 100 лет - два честных-пречестных юбиляра-разюбиляра. Естественно, по такому случаю число π устроило праздничный банкет, на который пригласило число 100 и другие числа: 1, 2, 4, 5, 10, 20, 25, 50, но только не 3. Число π терпеть не могло этого алкоголика, с которым его вечно путали. Ну, понятное дело, дым коромыслом, праздник в разгаре, гости начали разбиваться на группы по 3 числа. А число π никак не хочет принимать участие в группе из 3-х чисел, и, прихватив число 100, нашло себе компаньона - какого-то генерала с денщиком. Получилась как бы группа не на троих, а, с учетом денщика, на 3,14. Число π было жутко довольно, и, как потом писало число 100 в донесении числу 0, рассказывало неприличные истории про число 3. В частности, американский алгоритм шифрования 3DES - Triple DES - обзывало «Триппер DES».
Генерал хохотал весь вечер, к концу совсем расслабился, пил с π и с 100 на брудершафт, потом его повели к очаровательным запятым из ведомства числа 1 - в общем, жизнь удалась. Наутро, не желая оставаться в долгу, генерал заявил, что никогда не забудет этого банкета и в память о нем назовет какое-нибудь оружие.
Так в армии появился пистолет.
Но были в МНЧ и диссиденты: числа, не вступившие в партию, и вообще, не желавшие ни с кем делиться, кроме Царя. В народе их называли еще простыми числами. Строго говоря, и всеми уважаемые числа 2, 3 и 5 тоже были простыми диссидентами, но благодаря куче поклонников - других чисел из МНЧ, которые с ними делились, - Царь считал их «своими» диссидентами и никаких репрессий к ним не применял. А вот числу 13 не повезло. Оно жило рядом с честным-пречестным числом 12 и постоянно пыталось отучить его от алкоголизма. Как бы не так! Число 12 написало кляузу в Контору, после чего отдел Пропаганды Царя-Батюшки объявил число 13 причиной всех бед и несчастий в МНЧ и обозвал его «чертовой дюжиной».
Так и жили тысячу лет в МНЧ, умножались и делились, стремясь достигнуть светлой цели, записанной в Программе правящей партии - бесконечности, но никак не могли этого сделать. А когда провозглашается что-то заведомо недостижимое, то в конце концов народ начинает выражать свое недовольство: умножаемся, делимся, а все без толку, бесконечности так и нет. Решив стравить пар народного недовольства, партийные вожди однажды провозгласили перестройку: «Давайте делиться с остатком!». Мол побесятся натуральные числа, наиграются, и все вернется к прежним умножению и делению, когда никаких тебе остатков, все - общее.
А народ в МНЧ был такой, что палец ему в рот не клади - руку по локоть откусят. Раз провозгласила правящая партия деление с остатком, то все сразу смекнули, что остаток-то - штука неплохая. Главное, чтобы он в 0 не обратился, как было в прежней, доперестроечной жизни. И вот ведь что еще негодяи придумали - конечные группы. До того всем числам на всех политзанятиях только и внушали: наша цель - бесконечность, а тут - упала дисциплина, перестали слушать партийных пропагандистов, а на улицах стали появляться антиправительственные листовки: наша цель - конечная группа. Сам такую листовку раз видел на площади прямо около Конторы. Прихватил ее с собой, вот она.
Наша цель - конечная группа!
Всем! Всем! Всем!
Натуральные числа! Не слушайте пропагандистов из партии честных чисел - никакие они не честные! Врут они нам, что наша цель - бесконечность, не достигнуть ее ни через 100, ни через 1000 лет, сколько бы мы ни умножались и делились. Наша цель - конечная группа!
Вам забивают голову этой мистической бесконечностью, а мы расскажем вам, как быстро создать реальную конечную группу.
Выбирайте себе модуль, умножайтесь и делитесь на него с остатком! Частное выбрасывайте, а остатки образуют конечную группу.
Нет бесконечности!!!
Контора сперва хотела принять радикальное решение: показать всем этим вольнолюбцам настоящую бесконечность, обратив их в лагерную пыль. Но хитрое число 2 надоумило Контору не делать глупостей - не 37 год на дворе, надо действовать тоньше и с выгодой для себя. Надо просто подсунуть горлопанам подходящий модуль. Например, честного-пречестного алкоголика - число 12.
Идет как-то на нетвердых ногах число 3, а навстречу ему прямо сияет честное-пречестное число 8.
- Давай вступим в конечную группу по модулю 12.
- Давай!
Вступили. Перемножились. Раньше такое сколько раз вытворяли и в Контору за это никто не попадал. А тут как только привели результат по модулю 12, глазом не успели моргнуть, как он уже в Конторе.
Ну что, сынки, помогло вам ваше деление с остатком?
Возмутились числа: что такое, в конечной группе могут быть делители нуля! Не делители, а осведомители - поправили их в Конторе.
Приуныли натуральные числа. Неужели опять - все по-старому, наша цель - бесконечность? А нельзя ли как-то получить конечную группу без конторских осведомителей?
День думали, два, а на третий вспомнили о простых числах, тех, которые ни с кем не делятся. Взяли, к примеру, соседа числа 12 - бедное и затравленное число 13. И, о чудо! Кто с кем в его конечной группе ни умножался по модулю 13, а результат в Контору так и не попал! Не верите? Проверьте сами.
И стали в МНЧ очень популярны числа, которые не хотели ни с кем делиться. Как только выберут такое число модулем, так в его конечной группе законность и порядок, все арифметические операции выполняются четко и правильно, без всяких чуровых и делителей-осведомитлей числа 0. Старик Евклид придумал способ, как не только умножаться, но и делиться в такой конечной группе, причем как умножаться, так и делиться стали абсолютно все, от мала до велика, кто на кого захочет. Кроме, естественно, числа 0, которому в этой группе места уже не было.
Контора была в ярости. Это кто ж теперь в модулях ходит? Без 0 в конце, беспартийные, непьющие, без юбилейных медалей! По-обычному ни с кем не делятся - простые! Да таких простых - раз два - и обчелся! А как же светлое будущее - бесконечность? С кем его строить-то будем, если все простые скоро закончатся?
Не закончатся - ответил Конторе старик Евклид в своих «Началах».
На всякий случай в Конторе решили поставить все конечные группы на учет под буквой Z, от слова zero - агентурной клички числа 0: Z/2 - группа по модулю 2, Z/3 - группа по модулю 3 и так далее. А натуральные числа, для конспирации, чтобы не употреблять раздражающее Контору выражение «делиться в конечной группе» заменили его на благородное «решать сравнение первой степени по модулю».
Группа Z/2 была совсем неинтересной и состояла из одного Царя-Батюшки - числа 1.
Группа Z/3 состояла из Царя и партийного Вождя - числа 2. Забавные превращения там получались. Партийный вождь, перемножившись сам с собой, превращался в Царя. Ну это еще можно понять, такие превращения бывали не только у натуральных чисел. А вот Царь-то, Царь - хорош гусь! Поделившись на партийного Вождя, сам становился партийным Вождем! Такие чудеса происходили только в этой VIP-группе, в других группах и народу было поболее, и умножение-деление повеселее.
Вскоре из конечных групп стали создавать нечто вроде ночных клубов для отдыха трудящихся чисел: «Семеро козлят», «Футбольная команда», «Чертова дюжина», «17 мгновений весны» и прочая, прочая, прочая.
Натуральные числа были рады их появлению. Особенно рад был Царь-Батюшка. Сидит, бывало, в своем дворце целыми днями один-одинешенек, и поделиться-то не с кем, ни на кого он не делился. А тут, в конечной группе - делись с кем хочешь, хоть до утра. И число 2 меньше стало внимания уделять своей партии - надоели, зануды. Пойдут, бывало, Царь вместе с партийным Вождем в weekend в какие-нибудь «Мгновения» душу отвести, наделиться всласть на всю трудовую неделю вперед, а там уже и число 3 (меньше пить стало!) и 5 (без медалек!) и 12, подружившееся с 13, все веселые, друг с другом делятся. Да и вообще, все сразу же перевернулось с ног на голову, какие тут партии и партбилеты! Без особых проблем число 2 согласилось на переименование своей партии в множество, а тут еще запятая из Администрации Царя, перепечатывая Указ о деполитизации в МНЧ и думая о чем-то своем, девичьем, пропустила одну букву, и вместо Ума, Чести и Совести нашей эпохи - Партии Честных Чисел - получилось самое обыкновенное множество четных чисел.
Но все это было несерьезно, развлекалочки какие-то. Серьезные дела начались в МНЧ с появлением там персональных компьютеров. Первым по достоинству оценило их появление число 2. Оно ведь было не только хитрым, но и умным числом. Вместо прикрытой за ненадобностью Партии Честных Чисел число 2 создало очень нужную для компьютеров двоичную систему счисления и теперь каждое число из МНЧ имело свое двоичное представление на компьютере. В МНЧ появились и такие немыслимые раньше слова, как информационные технологии, информационная безопасность, электронно-цифровая подпись, RSA. А вот RSA как раз и стал таким алгоритмом, в котором без простых чисел обойтись никак невозможно. Только простые числа p и q для RSA нужны большие - ведь они же секретный ключ! Думало - думало об этом число 2 и решило, что длина простого числа в RSA, как правило, должна быть 512 или 1024 бит. Пол-литра и литр - по-своему расшифровало эти значения число 3.
И брошен был клич: все на поиски больших простых чисел, пол-литровых и литровых, ибо без них не будет в МНЧ ни Internet Banking, ни электронной коммерции, ни современной цивилизации, а будем только вечно к бесконечности стремиться. А простые числа - скромные, тихо сидят себе по своим конечным группам, никаких явных признаков у них нет. Как их отыскать в многотриллионном множестве натуральных чисел?
Задачу эту поручили Конторе. Ну а Контора - что с нее взять - выполнила это поручение так, как умела.
Переписали в Конторе все простые числа до 256 и поехали по отдаленным уголкам необъятного множества натуральных чисел. Случайно заезжают в какую-нибудь глухомань и хватают там первого попавшегося пол-литрового аборигена.
- Говори, падла, с кем делишься?
- Что Вы, что Вы, гражданин начальник, ни с кем не делюсь.
- Врешь, гад!
- Клянусь: век бесконечности не видать!
И начинают его делить на все припасенные простые числа, да еще при каждом делении запятую к заду норовят присоединить. Отвалилась запятая - врет, делится. Но даже если выдержал мужичок все эти пытки, то Контора на этом не успокаивается.
- Говори, паскуда, сколько у тебя свидетелей простоты?
И вот только после того, как найдет такое число m достаточное (log 2(m)) число свидетелей своей простоты, сажают его в машину и везут в столицу: RSA-ключом будет. Всю эту садистскую процедуру прозвали в МНЧ тестом Миллера-Рабина.
Вылавливают таким образом пару пол-литровых мужичков - числа p и q, и готов секретный ключ. Перемножают их, получают литровый открытый ключ - n, который затем одевают в нарядный сертификат.
И, надо признаться, даже несмотря на эту садистскую процедуру, чисел, желающих вырваться из деревенской глуши в столицу в качестве RSA-ключей было предостаточно. А о том, чтобы всех их просто пересчитать, не говоря уже об опробовании, не могло быть и речи. Слишком много. Поэтому алгоритм RSA для пол-литровых и литровых простых чисел был признан стойким.
Вот так и получилось, что весь прогресс в МНЧ обеспечили простые числа, т.е. числа, которые не хотели ни с кем делиться. А современные информационные технологии целиком держатся на глубинке множества натуральных чисел - случайных простых числах длиной 512 и 1024 бит.
Назад Продолжение
В начало книги Криптография и Свобода - 2