Как сохранить информацию в тайне?
Как передать информацию адресату в тайне от других?
Этим проблемам информационной безопасности насчитывается несколько тысяч лет.
Способы решения этих проблем можно условно разбить на три группы:
1. cоздание абсолютно надежного хранилища или недоступного для других канала связи между абонентами;
2. маскировка или скрытие фактов наличия информации или ее передачи по общедоступному каналу связи;
Разработкой средств и методов скрытия факта передачи сообщения (тайнописи) занимается стеганография1).
Историческая справка. Первые следы стеганографических методов теряются в глубокой древности.
Греку Гистиею, жившему при дворе персидского царя Дария, нужно было переслать важное сообщение своему родственнику — тирану Милета Аристагору. Гистией не мог послать письмо: его бы перехватили по дороге. Тогда он обрил голову своего верного раба, наколол на голой коже его черепа сообщение татуировкой и подождал пока отрастут волосы. После этого послал раба в Милет. По прибытии раб склонился перед Аристагором и сказал: «Обрей меня». Сделав это, Аристагор прочитал: «Восставай».
Из детективов известны различные способы тайнописи между строк обычного, незащищаемого текста: молоком — с нагреванием письма получателем (см. ☞ milk.doc) или специальными химическими составами, предполагающими более сложную обработку после доставки. Опять же из детективов известен метод микроточки: с помощью современной техники сообщение заносится на очень маленький носитель (микроточку), который пересылается обычным письмом, например, под маркой или в каком-нибудь другом, предварительно обусловленном месте.
Хорошая обзорная статья по современным методам стеганографии ☞ [1].
3. хранение информации в общедоступном месте или ее передача по общедоступному каналу связи в преобразованном виде: так, чтобы восстановить ее мог лишь тот, кому она предназначена.
Криптография2) — наука о способах преобразования (шифрования) информации с целью обеспечения ее конфиденциальности: защиты ее от несанкционированного доступа.
Что общего у криптографии с деревом кедр ?
Истоки криптографии также можно найти в глубокой древности [2]. Шифры создавали многие — ученые, дипломаты, cвященнослужители, пираты, военные и, разумеется, разведчики. Приведем примеры нескольких классических шифров, интересных и с методической точки зрения. По ходу изложения будем вводить и терминологию.
Открытым текстом будем называть сообщение, которое подлежит шифрованию, а результат применения к нему алгоритма шифрования будем называть шифровкой. Будем обозначать элемент открытого текста через $ x_{} $, а шифровки — через3) $ c_{} $.
реализует следующее преобразование открытого текста: каждая его буква заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т.е. для русского алфавита4) после буквы я следует буква а:
a | б | в | г | … | ь | э | ю | я |
---|---|---|---|---|---|---|---|---|
$ \downarrow $ | $ \downarrow $ | $ \downarrow $ | $ \downarrow $ | … | $ \downarrow $ | $ \downarrow $ | $ \downarrow $ | $ \downarrow $ |
г | д | е | ё | … | я | а | б | в |
Если закодировать буквы русского алфавита числами в десятичном представлении:
a | б | в | г | д | е | ё | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ъ | ы | ь | э | ю | я |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
то шифр Цезаря можно представить в виде функции $$x \mapsto c=x+3 \pmod{33} \ , $$ где $ x_{} $ — номер буквы открытого текста в алфавите. Здесь число $ 3_{} $ указывает величину сдвига алфавита; понятно, что она могла быть выбранной любой: $$x \mapsto c=x+k \pmod{33} \ , $$ лишь бы только число $ k\in \{1,2,\dots,32\} $ было известно адресату. Дешифрование им полученного текста производится «сдвигом» в противоположную сторону: $$ x=c - k \pmod{33} \ \iff \ x = c + (33-k) \pmod{33} . $$ Здесь $ c $ означает номер буквы шифровки в алфавите. ♦
Шифр Цезаря относится к классу шифров замены. Тривиальный шифр замены:
буква $ \mapsto $ произвольный (фиксированный) символ
«взламывается» частотным анализом достаточно длинного шифрованного сообщения. Известна [7]
Частота встречаемости букв в обычном (неспециальном) тексте (без учета пробелов):
a | б | в | г | д | е,ё | ж | з | и | й | к | л | м | н | о | п | р | с | т |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0.075 | 0.017 | 0.046 | 0.016 | 0.03 | 0.087 | 0.009 | 0.018 | 0.075 | 0.012 | 0.034 | 0.042 | 0.031 | 0.065 | 0.110 | 0.028 | 0.048 | 0.055 | 0.065 |
у | ф | х | ц | ч | ш | щ | ъ,ь | ы | э | ю | я | |||||||
0.025 | 0.002 | 0.011 | 0.005 | 0.015 | 0.007 | 0.004 | 0.017 | 0.019 | 0.003 | 0.007 | 0.022 |
Следовательно, имеет смысл посчитать количества совпадающих символов в шифровке и ранжировать полученное: наиболее часто встречаемый символ, скорее всего, соответствует букве5) о, следующий по частоте — возможно, букве е и т.д.
Дешифруйте:
NEGJVEGHJUHFVVBCNEBRKFDBFNEHFYTGJVJUFTN.
Открытый текст представляет собой фразу на русском языке.
Можно повысить безопасность шифра Цезаря, сделав величину $ k_{} $ контекстно зависимой, т.е. зависящей от места буквы в открытом тексте.
как раз и реализует это. Для шифрования некоторого сообщения, например:
OБ АЛГЕБРАИЧЕСКИХ ПРЕОБРАЗОВАНИЯХ
выбираем произвольное сочетание букв, скажем, КРИПТО, которое предполагается секретным для всех, кроме адресата. Буква сообщения сдвигается по алфавиту на величину, равную порядковому номеру в алфавите соответствующей буквы секретного слова:
15 | $ ^1 $ | 0 | $ ^{12} $ | 3 | $ ^5 $ | |||||||||||||||||||||||||
О | Б | А | Л | Г | Е | Б | Р | А | И | Ч | Е | С | К | И | Х | П | Р | Е | О | Б | Р | А | З | О | В | А | Н | И | Я | Х |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
К | Р | И | П | Т | О | |||||||||||||||||||||||||
11 | $ ^{17} $ | 9 | $ ^{16} $ | 19 | $ ^{15} $ | |||||||||||||||||||||||||
Щ | С | И | Ы | Х | У | |||||||||||||||||||||||||
26 | $ ^{18} $ | 9 | $ ^{28} $ | 22 | $ ^{20} $ |
Итак, первые 6 букв сообщения зашифрованы. Как поступить с оставшимися? Можно зашифровать их с помощью того же секретного слова:
1 | $ ^{17} $ | 0 | $ ^9 $ | 24 | $ ^5 $ | 18 | $ ^{11} $ | 9 | $ ^{22} $ | 16 | $ ^{17} $ | 5 | $ ^{15} $ | 1 | $ ^{17} $ | 0 | $ ^8 $ | 15 | $ ^2 $ | 0 | $ ^{14} $ | 9 | $ ^{32} $ | 22 | |||||||
О | Б | А | Л | Г | Е | Б | Р | А | И | Ч | Е | С | К | И | Х | П | Р | Е | О | Б | Р | А | З | О | В | А | Н | И | Я | Х | открытый текст |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
К | Р | И | П | Т | О | К | Р | И | П | Т | О | К | Р | И | П | Т | О | К | Р | И | П | Т | О | К | Р | И | П | Т | О | К | |
11 | $ ^{17} $ | 9 | $ ^{16} $ | 19 | $ ^{15} $ | 11 | $ ^{17} $ | 9 | $ ^{16} $ | 19 | $ ^{15} $ | 11 | $ ^{17} $ | 9 | $ ^{16} $ | 19 | $ ^{15} $ | 11 | $ ^{17} $ | 9 | $ ^{16} $ | 19 | $ ^{15} $ | 11 | |||||||
Щ | С | И | Ы | Х | У | Л | Б | И | Ш | Й | У | Ь | Ы | С | Е | В | Я | П | Я | Й | А | Т | Ц | Щ | Т | И | Э | Ы | Н | А | шифровка |
12 | $ ^{34} $ | 9 | $ ^{25} $ | 43 | $ ^{20} $ | 29 | $ ^{28} $ | 18 | $ ^{38} $ | 35 | $ ^{32} $ | 16 | $ ^{32} $ | 10 | $ ^{33} $ | 19 | $ ^{23} $ | 26 | $ ^{19} $ | 9 | $ ^{30} $ | 28 | $ ^{47} $ | 33 | |||||||
$ ^{\equiv 1} $ | $ ^{\equiv 10} $ | $ ^{\equiv 5} $ | $ ^{\equiv 2} $ | $ ^{\equiv 0} $ | $ ^{\equiv 14} $ | $ ^{\equiv 0} $ |
Аналитическое задание этого шифра: $$x_{i+6k} \mapsto c_{i+6k}= x_{i+6k}+ \varepsilon_i \pmod{33} \ , $$ где $ i\in \{0,1,2,3,4,5 \} \, , k\in \{0,1,2,3,\dots \} $, а число $ \varepsilon_i $ определяется как номер $ i $-й буквы секретного слова в алфавите. Ту же формулу можно записать в еще более компактном виде $$x_i \mapsto c_{i}= x_i + \varepsilon_{i\pmod{6}} \pmod{33} \ , \quad npu \quad i\in \{0,1,2,\dots \} \ . $$ Для дешифрования получателю достаточно применить обратное преобразование: $$x_{i+6k}=c_{i+6k} - \varepsilon_i \pmod{33} \ \iff \ x_{i+6k}=c_{i+6k}+ (33- \varepsilon_i) \pmod{33} \ ,$$ т.е. ему необходимо знать либо секретное шифрующее слово, либо же дешифрующее слово, образованное как раз из букв, соответствующих числам $ 33- \varepsilon_i $, т.е. ХПЧРНС:
26 | $ ^{18} $ | 9 | $ ^{28} $ | 22 | $ ^{20} $ | 12 | $ ^{34} $ | 9 | $ ^{25} $ | 43 | $ ^{20} $ | 29 | $ ^{28} $ | 18 | $ ^{38} $ | 35 | $ ^{32} $ | 16 | $ ^{32} $ | 10 | $ ^{33} $ | 19 | $ ^{23} $ | 26 | $ ^{19} $ | 9 | $ ^{30} $ | 28 | $ ^{47} $ | 33 |
Щ | С | И | Ы | Х | У | Л | Б | И | Ш | Й | У | Ь | Ы | С | Е | В | Я | П | Я | Й | А | Т | Ц | Щ | Т | И | Э | Ы | Н | А |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Х | П | Ч | Р | Н | С | Х | П | Ч | Р | Н | С | Х | П | Ч | Р | Н | С | Х | П | Ч | Р | Н | С | Х | П | Ч | Р | Н | С | Х |
22 | $ ^{16} $ | 24 | $ ^{17} $ | 14 | $ ^{18} $ | 22 | $ ^{16} $ | 24 | $ ^{17} $ | 14 | $ ^{18} $ | 22 | $ ^{16} $ | 24 | $ ^{17} $ | 14 | $ ^{18} $ | 22 | $ ^{16} $ | 24 | $ ^{17} $ | 14 | $ ^{18} $ | 22 | $ ^{16} $ | 24 | $ ^{17} $ | 14 | $ ^{18} $ | 22 |
О | Б | А | Л | Г | Е | Б | Р | А | И | Ч | Е | С | К | И | Х | П | Р | Е | О | Б | Р | А | З | О | В | А | Н | И | Я | Х |
15 | $ ^1 $ | 0 | $ ^{12} $ | 3 | $ ^5 $ | 1 | $ ^{17} $ | 0 | $ ^9 $ | 24 | $ ^5 $ | 18 | $ ^{11} $ | 9 | $ ^{22} $ | 16 | $ ^{17} $ | 5 | $ ^{15} $ | 1 | $ ^{17} $ | 0 | $ ^8 $ | 15 | $ ^2 $ | 0 | $ ^{14} $ | 9 | $ ^{32} $ | 22 |
Фактически шифр Цезаря является вырожденным, частным случаем шифра Виженера, когда секретное слово тривиально состоит из одной только буквы г. Другая крайность заключается в использовании достаточно длинной секретной фразы:
1 | $ ^{17} $ | 0 | $ ^9 $ | 24 | $ ^5 $ | 18 | $ ^{11} $ | 9 | $ ^{22} $ | 16 | $ ^{17} $ | 5 | $ ^{15} $ | 1 | $ ^{17} $ | 0 | $ ^8 $ | 15 | $ ^2 $ | 0 | $ ^{14} $ | 9 | $ ^{32} $ | 22 | |||||||
О | Б | А | Л | Г | Е | Б | Р | А | И | Ч | Е | С | К | И | Х | П | Р | Е | О | Б | Р | А | З | О | В | А | Н | И | Я | Х | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
К | Р | И | П | Т | О | Г | Р | А | Ф | И | Я | Д | О | Л | Ж | Н | А | Б | Ы | Т | Ь | Э | К | О | Н | О | М | Н | О | Й | секретная фраза |
3 | $ ^{17} $ | 0 | $ ^{21} $ | 9 | $ ^{32} $ | 4 | $ ^{15} $ | 12 | $ ^{7} $ | 14 | $ ^{0} $ | 1 | $ ^{28} $ | 19 | $ ^{29} $ | 30 | $ ^{11} $ | 15 | $ ^{14} $ | 15 | $ ^{13} $ | 14 | $ ^{15} $ | 10 | |||||||
Щ | С | И | Ы | Х | У | Д | Б | А | Э | А | Д | Х | Щ | Ф | Ь | Э | Р | Ё | Й | У | М | Э | Т | Э | П | О | Ъ | Ц | Н | Я | шифровка |
4 | $ ^1 $ | 0 | $ ^{30} $ | 0 | $ ^4 $ | 22 | $ ^{26} $ | 21 | $ ^{29} $ | 30 | $ ^{17} $ | 6 | $ ^{10} $ | 20 | $ ^{13} $ | 30 | $ ^{19} $ | 30 | $ ^{16} $ | 15 | $ ^{27} $ | 23 | $ ^{14} $ | 32 |
А для шифрования длинного сообщения можно взять отрывок из какой-нибудь книги. Понятно, что законный получатель шифровки должен знать и книгу, и место, с которого ему надо осуществить «привязку» отрывка текста к шифровке. И хотя такой подход кажется очень трудоемким, не будем отметать его сходу… ♦
приписывается итальянскому математику, астрологу, медику и мистику Кардано6). Шифр можно рассматривать как вариант шифра Виженера, и начальная стадия у них одинакова: первые буквы отрытого текста шифруются с помощью секретного слова. Остроумие идеи Кардано заключается в том, что шифрование оставшейся части текста осуществляется с помощью самого этого текста:
15 | $ ^1 $ | 0 | $ ^{12} $ | 3 | $ ^5 $ | 1 | $ ^{17} $ | 0 | $ ^9 $ | 24 | $ ^5 $ | 18 | $ ^{11} $ | 9 | $ ^{22} $ | 16 | $ ^{17} $ | 5 | $ ^{15} $ | 1 | $ ^{17} $ | 0 | $ ^8 $ | 15 | $ ^2 $ | 0 | $ ^{14} $ | 9 | $ ^{32} $ | 22 | |
О | Б | А | Л | Г | Е | Б | Р | А | И | Ч | Е | С | К | И | Х | П | Р | Е | О | Б | Р | А | З | О | В | А | Н | И | Я | Х | открытый текст |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
К | Р | И | П | Т | О | О | Б | А | Л | Г | Е | Б | Р | А | И | Ч | Е | С | К | И | Х | П | Р | Е | О | Б | Р | А | З | О | секретное слово & открытый текст |
15 | $ ^1 $ | 0 | $ ^{12} $ | 3 | $ ^5 $ | 1 | $ ^{17} $ | 0 | $ ^9 $ | 24 | $ ^5 $ | 18 | $ ^{11} $ | 9 | $ ^{22} $ | 16 | $ ^{17} $ | 5 | $ ^{15} $ | 1 | $ ^{17} $ | 0 | $ ^8 $ | 15 | |||||||
Щ | С | И | Ы | Х | У | П | С | А | Ф | Ъ | Й | Т | Ы | И | Ю | Ж | Х | Ц | Щ | Й | Ё | П | Ш | У | Р | Б | Ю | И | Ж | Д | шифровка |
16 | $ ^{18} $ | 0 | $ ^{21} $ | 27 | $ ^{10} $ | 19 | $ ^{28} $ | 9 | $ ^{31} $ | 7 | $ ^{22} $ | 23 | $ ^{26} $ | 10 | $ ^{6} $ | 16 | $ ^{25} $ | 20 | $ ^{17} $ | 1 | $ ^{31} $ | 9 | $ ^{40} $ | 4 |
В самом деле, только зная секретное слово КРИПТО можно восстановить первые $ 6_{} $ букв сообщения, с их помощью можно восстановить следующие $ 6_{} $ букв и т.д. ♦
Под ключом в криптографии понимают сменный элемент шифра, который применяется для шифрования или дешифрования конкретного сообщения.
Например, в шифре Цезаря ключом является $ k_{} $ — величина сдвига алфавита, в шифре Виженера — секретное слово или фраза.
Во всех приведенных выше примерах процесс шифрования оказалось удобным описывать посредством предварительной операции над буквами открытого текста — их представлением в виде чисел. Сама процедура такой замены
буква $ \mapsto $ символ (совокупность символов)
называется кодированием. С формальной точки зрения кодирование можно рассматривать как частный случай шифрования (см. шифр замены ). Однако в современной криптографической литературе эти две операции принято различать по целям их применения: шифрование предназначено для скрытия информации, в то время как кодирование — для удобства ее хранения и передачи. Например, для передачи информации по каналу связи, подверженному воздействию помех (шумов), используются коды, исправляющие ошибки, когда символы сообщения представляются такими цепочками битов, чтобы «порча» любого бита (или фиксированного числа битов) при передаче не помешала получателю однозначно восстановить (декодировать) передаваемый символ.
В дальнейшем мы будем часто использовать кодировку, которую назовем стандартной:
а | б | в | г | д | е,ё | ж | з | и | й | к | л | м | н | о | п | р | с | т | у | ф | х | ц | ч | ш | щ | ъ | ы | ь | э | ю | я |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 |
пробел | |||||||||||||||||||||||||||||||
00 |
Итак, шифрование можно представить как некоторую операцию над числами кодировки. И собственно ключ также может быть выражен в виде числа. Оптимальным был бы абсолютно непредсказуемый, случайный выбор последовательности цифр ключа — тогда перехвативший шифровку злоумышленник не сможет предугадать закон формирования его элементов. Если иметь в виду соображения удобств технической реализации, то и числа кодировки и ключ следует представлять не в десятичной, а в двоичной системе; иначе говоря, объектами корреспонденции становятся последовательности из нулей и единиц. При шифровании каждый бит открытого текста преобразуется в бит шифротекста по некоторому правилу с использованием битов ключа.
Вернам предложил использовать для шифрования преобразование $$ x_i \mapsto c_i=x_i + \varepsilon_{i} \pmod{2} \ ,$$ где $ x_i $ представляет бит открытого текста, а $ \varepsilon_{i} $ — бит ключа; при этом последовательность битов ключа формируется случайным образом. Будем использовать обозначение $ \oplus $ для операции побитного сложения по модулю $ 2_{} $ чисел, представленных в двоичной системе счисления (XOR): если $ A=\underline{{\mathfrak a}_1{\mathfrak a}_2 \dots {\mathfrak a}_s {\mathfrak a}_{s+1}} $ и $ B=\underline{{\mathfrak b}_1{\mathfrak b}_2 \dots {\mathfrak b}_s {\mathfrak b}_{s+1}} $ два числа, представленных в такой системе, то $$A\oplus B = \underline{{\mathfrak c}_1{\mathfrak c}_2 \dots {\mathfrak c}_s {\mathfrak c}_{s+1}} \ , npu \ {\mathfrak c}_j = {\mathfrak a}_j + {\mathfrak b}_j \pmod{2} \ . $$ Таким образом: $$ 0 \oplus 0 = 0,\ 0 \oplus 1 = 1 \oplus 0 =1, \ 1 \oplus 1 = 0 \ , $$ и
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | … | открытый текст |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | … | ключ |
1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | … | шифровка |
Законный адресат (получатель шифровки) должен иметь в своем распоряжении дубликат ключа, т.е. фактически ему должна быть заранее передана последовательность битов, не меньшая (по длине) возможной шифровки. Подобное решение проблемы конфидециальности переписки на первый взгляд кажется порочным кругом: для соблюдения секретности передаваемого сообщения необходимо предварительно передать корреспонденту по абсолютно надежному каналу ключ той же длины. Но противоречие это только кажущееся: на самом деле секрет «разделяется». Ключ передается корреспонденту с надежным курьером — например, с офицером дипломатической почты. После одноразового использования ключа для шифрования и дешифрования сообщения, ключ уничтожается. В случае перехвата курьера потенциальный противник получит в свое распоряжение лишь бессмысленный набор символов, и тогда ключ просто меняется на другой; опасность же возможного копирования ключа (посредством подкупа курьера) может быть заблокирована техническими средствами… Шифр «одноразового блокнота» считается абсолютно надежным, и, по некоторым данным, именно им до последнего времени обеспечивалась секретность канала «горячей линии» между Кремлем и Белым Домом.
Для шифра Вернама ключ дешифрования совпадает с ключом шифрования; так, для приведенного примера получаем:
1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | … | шифровка |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | … | ключ |
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | … | открытый текст |
Исторические заметки о Гильберте Вернаме ☞ ЗДЕСЬ.
известен по крайней мере со времен Пелопоннесской войны (431-404 гг. до н.э.) Спарты потив Афин.
Источник. Плутарх. Избранные жизнеописания. Лисандр и Сулла.
Итак, скитала — цилиндрический жезл7). На него виток к витку наматывалась лента, на которую вдоль оси скиталы записывался открытый текст, например: ТРИСТАСПАРТАНЦЕВИДУТФЕРМОПИЛАМ. Лента разматывалась и получалось, что поперек нее в беспорядке написаны какие-то буквы, что-то наподобие
Эта лента отправлялась адресату.
Итак, адресат брал такую же скиталу, таким же образом наматывал на нее полученную ленту и читал сообщение вдоль оси скиталы.
В этом шифре преобразование открытого текста в шифрованный заключается в определенной перестановке букв открытого текста, что и позволяет отнести шифр скиталы к классу шифров перестановки.
Для удобства последующего анализа перепишем шифровку, повернув в ней буквы:
ТРИСТАСПАРТАНЦЕВИДУТФЕРМОПИЛАМ $ \mapsto $ ТССРНВУЕОЛРТПТЦИТРПАИАААЕДФМИМ.
ХАРИТОН МАКЕНТИН $ \mapsto $ АНТИОХ КАНТЕМИР8) ;
а также для анонсирования приоритетных научных результатов:
CCEIIINOSSTTUV $ \mapsto $ UTTENSIOSICVIC9).
Cм. также анаграмму основной задачи дифференциального исчисления ☞ ЗДЕСЬ
Для шифра скиталы принцип кодирования букв не имеет значения, а существенно лишь их место в сообщении. Например, если последовательно, начиная с нуля, пронумеровать буквы открытого текста о спартанцах, то в шифровке они займут места в соответствии со следующей схемой:
$ ^{0} $ | 1 | $ ^{2} $ | 3 | $ ^{4} $ | 5 | $ ^{6} $ | 7 | $ ^{8} $ | 9 | $ ^{10} $ | 11 | $ ^{12} $ | 13 | $ ^{14} $ | 15 | $ ^{16} $ | 17 | $ ^{18} $ | 19 | $ ^{20} $ | 21 | $ ^{22} $ | 23 | $ ^{24} $ | 25 | $ ^{26} $ | 27 | $ ^{28} $ | 29 |
Т | Р | И | С | Т | А | С | П | А | Р | Т | А | Н | Ц | Е | В | И | Д | У | Т | Ф | Е | Р | М | О | П | И | Л | А | М |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | $ ^{10} $ | 20 | $ ^1 $ | 11 | $ ^{21} $ | 2 | $ ^{12} $ | 22 | $ ^3 $ | 13 | $ ^{23} $ | 4 | $ ^{14} $ | 24 | $ ^5 $ | 15 | $ ^{25} $ | 6 | $ ^{16} $ | 26 | $ ^7 $ | 17 | $ ^{27} $ | 8 | $ ^{18} $ | 28 | $ ^{9} $ | 19 | $ ^{29} $ |
Функция, задающая процедуру шифрования, может быть представлена в виде: $$ x \mapsto c=10\,x \pmod{29} \ , $$ где $ x $ — место символа в открытом тексте. Исключением для этой формулы является последняя буква открытого текста М — она остается на месте. Ключом в шифре скиталы является ее диаметр, или — в переводе на язык цифр — сомножитель, на который надо умножить номер буквы в открытом тексте.
Построение обратной, т.е. дешифрующей, функции потребует уже некоторых усилий. Найдем число обратное числу $ 10_{} $ относительно умножения по модулю $ 29_{} $: $$3\times 10 = 30 \equiv 1 \pmod{29} \ .$$ Тогда соотношение $ x \equiv 3\,c \pmod{29} $ позволяет дешифровать полученную шифровку : буква Т, стоящая на нулевом месте в шифровке, останется на том же месте в открытом тексте; буква С, стоящая на $ 1 $-м месте шифровки, должна перейти на $ 3_{} $-е место в открытом, следующая буква С станет $ 6 $-й, и т.д., Ф ($ 26 $-я в шифровке) — $ 20_{} $-й (поскольку $ 3 \cdot 26 \equiv 20 \pmod{29} $). Исключение составляет последняя буква шифровки М: вместо того, чтобы встать в начало открытого текста, она оставляется на месте.
Перехваченное сообщение английского резидента имеет вид:
ПОПЯДЕДРОЕЕГРББТИИЛМРОЕОУАТИЬЬВАЛНДУОНС
Дешифруйте его, если по оперативным данным известно, что в нем упоминается имя секретного агента: БОНД. Найдите функции шифрования и дешифрования.
Рассмотренные выше шифры можно комбинировать, строя из них новые. Так, например, очевидным обобщением шифров Цезаря и скиталы является аффинный10) шифр, задаваемый функцией $$f(x)=\alpha\, x+\beta \pmod{M} \quad npu \ 0\le \alpha, \beta< M\ u \ \operatorname{HOD} (\alpha,M)=1 \ .$$ Последнее условие гарантирует существование и единственность решения сравнения $ \alpha\, x+\beta \equiv c \pmod{M} $ во множестве $ \{0,1,\dots,M-1\} $, т.е. возможность дешифрования сообщения.
Подведем некоторые итоги. С формальной точки зрения шифрование и дешифрование текстов можно представить себе как операции над целыми числами. Выделяется подходящий математический объект, с помощью которого происходит формализация процедуры шифрования, а именно класс вычетов $ \mathbb Z_M $ по некоторому модулю $ M_{} $; сама процедура шифрования сводится при этом к элементарной алгебраической операции $ f_{}(x) $ над $ x\in \mathbb Z_M $. Эта алгебраическая операция зависит от некоторого параметра — ключа, который предполагается неизвестным противнику. Проблема дешифрования сообщения $ c=f(x) $ заключается в решении уравнения относительно $ x\in \mathbb Z_M $, т.е. нахождении функции, обратной $ f_{}(x) $ по модулю $ M_{} $. Эта обратная функция ищется в том же классе, что и сама функция $ f_{}(x) $, меняется лишь величина ключа. По известному ключу шифрования ключ дешифрования устанавливается практически мгновенно.
Схема шифрования называется схемой симметричных ключей, если для любой соответствующей пары
ключ шифрования $ \leftrightarrow $ ключ дешифрования
знание одной составляющей этой пары позволяет сравнительно легко вычислить другую составляющую.
Передаче шифрованного сообщения должна предшествовать процедура обмена ключами между корреспондентами. Этот обмен и организация хранения ключа (в случае предполагаемого неоднократного его использования) должны обеспечиваться гораздо более надежными средствами, чем те, что используются для передачи собственно сообщений, этим ключом зашифрованных. Поэтому часто схему симметричных ключей называют схемой секретных ключей.
А можно ли сконструировать функцию $ f_{}(x) $ так, чтобы нахождение дешифрующей функции представляло трудноразрешимую проблему даже при открытом ключе шифрования ?
Рассмотрим некоторую функцию $ F(x)_{} $, определенную на множестве $ \mathbb A_{} $ и отображающую это множество во множество $ \mathbb B_{} $: $ F(x): \mathbb A \mapsto \mathbb B $. Мы не будем заранее предполагать что это отображение взаимно однозначно, поэтому в дальнейшем, говоря об обратимости $ F(x)_{} $, будем иметь в виду — в зависимости от контекста — либо задачу определения всех прообразов данного значения $ y\in \mathbb B $ этой функции, либо задачу нахождения какого-то одного из них. Иначе говоря, идет речь о поиске решений уравнения $ F(x)=y $ относительно $ x\in \mathbb A $ при заданном $ y \in \mathbb B $.
Функция $ F(x)_{} $ называется односторонней, если она обладает свойствами:
1. простоты вычисления: для $ \forall x\in \mathbb A $ значения $ F(x)_{} $ вычисляются просто;
2. сложности обращения : для практически всех значений $ y \in \mathbb B $ нахождение хотя бы одного прообраза представляет вычислительно крайне трудоемкую задачу.
Слова «сложность» и «простота» требуют дополнительных пояснений. Кратко их можно формализовать в терминах разработанных на настоящий день алгоритмов, допускающих компьютерную реализацию.
Пример. Функция $ f(x) = 3^{x} \pmod{17} $ отображает множество $ \mathbb A =\{1,\dots,16\} $ в себя:
$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline x&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16 \\ \hline 3^{x} \pmod{17} &3&9&10&13&5&15&11&16&14&8&7&4&12&2&6&1 \\ \hline \end{array} $$ Существует и обратная функция — индекс $ \operatorname{ind}_{_3} y $, которую легко построить, имея перед глазами только что выписанную таблицу. Однако нереально построить такую таблицу для больших простых чисел $ p_{} $ — порядка $ 10^{60} $; но, как отмечалось ☞ ЗДЕСЬ , в настоящее время не известен иной регулярный алгоритм нахождения $ \operatorname{ind}_{_{\Lambda}} B $, т.е. решения задачи дискретного логарифмирования. ♦
Односторонней функцией с лазейкой11) называется односторонняя функция, обладающая еще и свойством
3. при некоторой дополнительной информации о $ F(x)_{} $, обращение этой функции становится простой задачей.
Для пояснения идеи снова обратимся к истории — для определенности до 1700 г. Противник ведет осаду неприступной крепости. Фортификационные особенности допускают единственную тактику приступа: штурмом мощно укрепленных ворот «в лоб». Однако имеется секретный лаз, ведущий из крепости к какому-то укромному месту за ее пределами — например, к реке. Через этот лаз любой защитник крепости может незаметно для осаждающих покинуть ее пределы. Напомним известную классическую сцену осады запорожцами польского города Дубно из повести Н.В.Гоголя «Тарас Бульба».
— Подземным ходом.
— Разве есть подземный ход?
— Есть.
— Где?
— Ты не выдашь, рыцарь?
— Клянусь крестом святым!
— Спустясь в яр и перейдя поток, там, где тростник.
— И выходит в самый город?
— Прямо к городскому монастырю.
— Идем, идем сейчас!
Строго говоря, для осаждающих имеются две возможности проникновения в крепость: прямой кровопролитной атакой ворот или же через секретный лаз, если, разумеется, этот лаз удастся обнаружить. В последнем случае, достаточно просочиться в крепость небольшой группе диверсантов, чтобы, перебив внезапным нападением охрану ворот, открыть их основным силам штурмующих. Итак, как для защитников крепости, так и для ее осаждающих информация о секретном лазе является ключевой.
Пример. Найти отображение, обратное отображению
$$x \mapsto f(x)=x^{7} \pmod{187}$$ множества $ \mathbb A= \{0,1,\dots,186\} $.
Решение. Нахождение значения $ f(x)_{} $ для заданного $ x_{} $ не представляет трудности: см. ☞ алгоритм "квадрирования-умножения". Таблица значений $$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline x&0&1&2&3&4&5&6&7&8&\dots &185&186 \\ \hline x^{7} \pmod{187} &0&1&128&130&115&146&184&182&134&\dots &15&142 \\ \hline \end{array} $$ демонстрирует, во-первых, взаимную однозначность отображения $ x \mapsto f(x) $ множества $ \mathbb A_{} $, и, во-вторых, хорошо организованную хаотичность перемешивания содержимого $ \mathbb A_{} $: близкие числа $ x_{j} $ отображаются, как правило, в далеко разнесенные $ f(x_j) $, так что практически для любого числа $ y\in \mathbb A $ визуальным наблюдением трудно определить, где искать его прообраз.
Является ли «случайная величина»
$$ \{j^{7} \pmod{187}\}_{j=0}^{186} $$ равномерно распределенной на интервале $ [0, 186] $ ? Вычислить среднее значение и коэффициент корреляции Пирсона для выборок
$$ X=[0,1,\dots,186] \quad u \quad Y=\left[0^{7} \pmod{187},1^{7} \pmod{187},\dots,186^{7} \pmod{187}\right] \, . $$
Вместе с тем, в настоящее время известен единственный универсальный алгоритм быстрого обращения степенной функции $ x^n \pmod{M} $ — т.е. вычисления корня степени $ n_{} $ по модулю $ M_{} $ — и этот алгоритм предполагает знание канонического разложения $ M_{} $.
Так, обнаружив, что $ M=187=11 \cdot 17 $, мы, следуя рассуждениям из ☞ ПУНКТА, разобьем сравнение $$ x^7 \equiv y \pmod{187} $$ на два по составляющим модуль множителям: $$ x^7 \equiv y \pmod{11} \quad u \quad x^7 \equiv y \pmod{17} \ . $$ Поскольку $ \operatorname{HOD}(7,11-1)=1 $ и $ \operatorname{HOD}(7,17-1)=1 $, то (см. ☞ теорему Эйлера ) каждое из этих сравнений имеет единственное решение во множествах $ \{0,1, \dots, 10\} $ и $ \{0,1, \dots, 16\} $ соответственно, и эти решения могут быть найдены по ☞ алгоритму решения двучленного сравнения: $$ \alpha_1=y^3 \pmod{11} \ u \ \alpha_2 = y^7 \pmod{17} \ . $$ Следовательно, и само сравнение $ x^7 \equiv y \pmod{187} $ при любом $ y_{} $ имеет единственное решение среди чисел множества $ \mathbb A_{} $, и это решение удовлетворяет системе сравнений $$x \equiv \alpha_1 \pmod{11} \ u \ x \equiv \alpha_2 \pmod{17} .$$ С помощью китайской теоремы об остатках мы сможем найти это значение $ x_{} $. Можно получить (см. упражнение ☞ ЗДЕСЬ ) и аналитическое представление для $ x_{} $ как функции от $ y_{} $, т.е. искомой обратной функции для функции $ x^{7} \pmod{187} $: $$ x=17^{10} y^3 +11^{16} y^7 \pmod{187} = 34\, y^3 + 154\, y^7 \pmod{187} \ .$$
Ответ. $ x=34\, y^3 + 154\, y^7 \pmod{187} $.
В следующем пункте будет приведено более компактное представление для корня n-й степени из числа y по модулю $ M_{} $, равном произведению двух простых множителей: оказывается, что функция, обратная $ x^n \pmod{M} $, может быть представлена также степенной функцией $ y^m \pmod{M} $ при некотором $ m\in \mathbb N $. Очевидно, что показатель $ m_{} $ может тогда считаться ключом дешифрования. Пока же подчеркнем еще раз тот факт, что если модуль $ M_{} $ является произведением различных простых и достаточно больших (порядков $ 10^{80} $) множителей, и эти множители известны, то обращение функции $ f(x)=x^{n} \pmod{M} $ не составит большой вычислительной трудности — хотя бы по алгоритму, использованному при решении предыдущего примера. Если же эти множители заранее не известны, то практически для всех значений $ y\in \{0,1,\dots, M-1\} $ — даже с использованием современных вычислительных мощностей — крайне трудно решить сравнение $$y\equiv x^{n} \pmod{M} $$ относительно $ x_{} $. Таким образом, структура канонического разложения $ M_{} $ оказывается секретной лазейкой для односторонней функции $ f(x)=x^{n} \pmod{M} $.
Теперь осталось формализовать идею последнего примера и показать, как можно использовать одностороннюю функцию с лазейкой для решения проблемы шифрования. В качестве такой функции, действующей на множестве $ \mathbb A = \{0,\dots,M-1\} $ , предлагается взять степенную $$ f(x)= x^{\mathbf E} \pmod{M} $$ при некотором фиксированном показателе $ \mathbf E $ и некотором составном модуле $ M_{} $. При определенных условиях на указанные числа эта функция взаимно-однозначно отображает множество $ \mathbb A_{} $ в себя и тогда ею можно шифровать закодированные открытые тексты: $$ x \mapsto c =x^{\mathbf E} \pmod{M} \quad npu \quad \forall x \in \mathbb A \ .$$ Дешифрование сообщения $ c=f(x) $ сводится к решению сравнения $$ x^{\mathbf E} \equiv c \pmod{M} \ , $$ которое имеет единственное решение $ x \in \mathbb A $.
Подчеркнем еще раз, принципиальной особенностью этого алгоритма шифрования является открытость ключа шифрования для любого желающего, т.е. пара $ M_{} $ и $ \mathbf E $ считается доступной даже для потенциального злоумышленника, стремящегося ознакомиться с перепиской между создателем (владельцем) ключа — и его «законным» корреспондентом. Любой желающий может зашифровать свой открытый текст нашим шифром. Но вот дешифровать чужой текст12), зашифрованный тем же шифром, ему будет весьма трудно, поскольку структура канонического разложения $ M_{} $ не известна никому кроме создателя ключа. Теперь осталось только выяснить как владельцу ключа воспользоваться этой информацией (секретной лазейкой) для того, чтобы дешифровать сообщение $ c_{} $, которое он получил от своего корреспондента (или любого желающего), зашифровавшего открытым ключом свое сообщение. В самом деле, создатель ключа шифрования должен же сам обладать ключом дешифрования!
Алгоритм RSA [8]
построения ключей шифрования и дешифрования.
1. Случайным образом выбираются два достаточно больших простых числа $ p_1 $ и $ p_2 $ и вычисляется их произведение: $$M=p_1\cdot p_2 \ ;$$ число $ M_{} $ не скрывается (открыто), но его множители $ p_1,p_2 $ держатся в секрете.
2. Случайным образом выбирается достаточно большое число $ \mathbf D $, взаимно простое с $ (p_1-1)(p_2-1) = \phi(M) $ (здесь $ \phi(M) $ означает функцию Эйлера от числа $ M_{} $): $$\operatorname{HOD} \left( \mathbf D, \phi(M) \right)=1 \ ; $$ число $ \mathbf D $ держится в секрете.
3. Вычисляется число $ \mathbf E $ обратное $ \mathbf D $ относительно умножения по модулю $ \phi(M) $: $$ \mathbf E \cdot \mathbf D \equiv 1 \pmod{\phi(M)} \ ; $$ число $ \mathbf E $ не скрывается (открыто).
Пара $ ( \mathbf E,M) $ составляет ключ шифрования , а пара $ (\mathbf D,M) $ — ключ дешифрования13).
Теорема. При числе $ \mathbf E $, выбранном по алгоритму RSA, сравнение
$$ x^{\mathbf E} \equiv c \pmod{M} $$ имеет единственное решение, которое может быть найдено по формуле $$ x=c^{\mathbf D} \pmod{M} \, .$$
Доказательство ☞ ЗДЕСЬ.
Показать, что число $ \mathbf E $, выбираемое по алгоритму RSA, не может быть четным.
Указать явное выражение $ \mathbf D $ через $ \mathbf E $ и функцию Эйлера
$$ \phi(M)=(p_1-1)(p_2-1) \, . $$
Показать, что при
$$ \operatorname{HOD} ( p_1-1, 3)=\operatorname{HOD} ( p_2-1, 3)=1 $$ ключу шифрования $ {\mathbf E}=3 $ соответствует ключ дешифрования, вычисляемый по формуле $$ {\mathbf D}=\phi (M)-\frac{1}{3}\left(\phi (M)-1 \right)\ . $$
Теперь проиллюстрируем работу алгоритма шифрования на примерах; начиная с этого места, при кодировании открытых текстов мы используем стандартную кодировку.
Пример 1. Резидент разведки хочет секретно переслать Центру сообщение, состоящее из одного слова РЯД. Опишем действия участников процесса.
1. Работа Центра. Случайным образом выбираются простые числа $ p_1 $ и $ p_2 $. Например: $$p_1=23,p_2=43 \quad \Rightarrow \quad M=989,\quad \phi (M)=(23-1)\times (43-1)=924 \ . $$ Далее случайным образом выбирается ключ дешифрования $ \mathbf D $ из единственного ограничения $ \operatorname{HOD} (\mathbf D ,\phi (M))=1 $. Такому условию удовлетворяет, например, $ \mathbf D=47 $. В качестве ключа шифрования $ \mathbf E $ берется обратное числу $ \mathbf D $ относительно умножения по модулю $ \phi (M) $. Алгоритм, приведенный ☞ ЗДЕСЬ, даст $ \mathbf E=59 $. Ключ шифрования $ (\mathbf E,M) $ сообщается резиденту (возможно, и по открытому каналу связи — т.е. специальные меры его защиты не предпринимаются).
2. Работа резидента. Получив ключ шифрования (и удостоверившись, что этот ключ принадлежит, действительно, Центру), резидент сначала кодирует сообщение: $ x=173205 $. Далее он обращает внимание на то, что $ x>M $, и если он формально зашифрует открытый текст по схеме алгоритма RSA, т.е. $ x \mapsto c=x^{\mathbf E} \pmod{M} $, то восстановить открытый текст $ x_{} $ Центр не сможет. В самом деле, указанная схема эквивалентна $$ x \mapsto \left(x \pmod{M} \right)^{\mathbf E} \pmod M \ , $$ иначе говоря, Центр сможет восстановить только число $ x \pmod{M} $, т.е. остаток от деления $ x_{} $ на $ M_{} $, а вовсе не исходное число $ x_{} $. Итак, резидент разбивает $ x_{} $ на блоки $ x_{j} $, по величине меньшие модуля $ M_{} $, которые и будет шифровать. Например: $$x=\big[ \underbrace{173}_{x_1}\big|\underbrace{205}_{x_2} \big] \ .$$ Способы разбиения закодированного сообщения на блоки оговариваются заранее между Центром и резидентом.
Теперь резидент шифрует блоки $ x_{j} $ по формуле $ x_j^{\mathbf E} \pmod{M} $ с использованием алгоритма "квадрирования-умножения". $$ \begin{array}{|c|c|c|c|c|c|c|} \hline j & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline {\mathfrak b}_j & 1 & 1 & 1 & 0 & 1 &1 \\ \hline x_1=173 &{\scriptstyle 173} & {\scriptstyle 173^2\times 173} & {\scriptstyle 302^2 \times 173} & {\scriptstyle 775^2\times 1} & {\scriptstyle 302^2 \times 173} & {\scriptstyle 775^2 \times 173} \\ & {\scriptstyle \equiv_{_{989}} 173} & {\scriptstyle \equiv_{_{989}} 302} & {\scriptstyle \equiv_{_{989}} 775} & {\scriptstyle \equiv_{_{989}} 302} & {\scriptstyle \equiv_{_{989}} 775} & {\scriptstyle \equiv_{_{989}} 818} \\ \hline x_2=205 & {\scriptstyle 205} & {\scriptstyle 205^2\times 205} & {\scriptstyle 935^2 \times 205} & {\scriptstyle 424^2\times 1} & {\scriptstyle 767^2 \times 205} & {\scriptstyle 585^2 \times 205} \\ & {\scriptstyle \equiv_{_{989}} 205} & {\scriptstyle \equiv_{_{989}} 935} & {\scriptstyle \equiv_{_{989}} 424} & {\scriptstyle \equiv_{_{989}} 767} & {\scriptstyle \equiv_{_{989}} 585} & {\scriptstyle \equiv_{_{989}} 421} \\ \hline \end{array} $$ Итак, $ c_1=818,\, c_2=421 $ и полностью зашифрованное сообщение выглядит теперь как $ c=818421 $. Эта шифровка открыто посылается Центру.
3. Работа Центра. Получив шифровку и убедившись, что она пришла действительно от резидента, Центр разбивает ее на блоки, дешифрует известным ему ключом дешифрования $ ({\mathbf D},M) $ (см. пункт 1 решения): $$818^{47} \equiv_{_{989}} 173 \ , \quad 421^{47} \equiv_{_{989}} 205 \ , $$ и декодирует текст.
Понятно, что если Центру надо послать ответ резиденту, то адресаты меняются ролями: у резидента имеется свой ключ шифрования $ (\tilde{\mathbf E}, \tilde M) $, который он выкладывает для открытого доступа и т.д. ♦
Теперь смоделируем поведение злоумышленника.
Пример 2. Шифровка разведчика
$$c=29002476253519483189074002430375 $$ зашифрована ключом $ \mathbf E=19, M=3233 $. Какие действия для дешифрования может предпринять контрразведчик, перехвативший сообщение?
Решение. По виду модуля контрразведчик может предположить, что шифруемые блоки имеют длину, не большую 4. Разбив шифровку на блоки именно такой длины: $ c=\big[c_1\big|c_2\big|\dots \big|c_8\big] $, он приступает к поиску ключа дешифрования $ \mathbf D $. Он может попытаться найти это число методом «грубой силы», т.е. последовательного перебора: поскольку открытый текст $ x_{j} $ совпадает с некоторой степенью числа $ c_{j} $ (по модулю $ M_{} $), то можно пытаться выявить осмысленный текст последовательным вычислением и декодированием блоков $$c_j \pmod{M}, c_j^2 \pmod{M}, c_j^3 \pmod{M},\dots $$ Можно прикинуть объем необходимых вычислений, посмотрев величину $ \mathbf D $, установленную ниже.
Для установления $ \mathbf D $ умный контрразведчик попытается решить сравнение $$ \mathbf E \cdot \mathbf D \equiv 1 \pmod{\phi(M)} \ , $$ но для этого необходимо сначала разложить $ M_{} $ на множители. В нашем примере это делается быстро: $ p_1=53,\, p_2=61 $ и, таким образом, $ \phi(M)=(p_1-1)(p_2-1)=3120 $. Теперь для решения сравнения $ 19 \cdot {\mathbf D} \equiv 1 \pmod{3120} $ вычисляются частные по алгоритму Евклида нахождения $ \operatorname{HOD} (19,3120) $: $ q_1=164,q_2=4, q_3=1 $. По алгоритму нахождения обратного по модулю: $ \tilde u=-K(q_1,q_2,q_3)=-821 $; и, следовательно, число $ {\mathbf D}=3120-821=2299 $ является искомым ключом дешифрования. Далее — дело техники: $$2900^{2299}\equiv_{_{3233}} 1806,\ 2476^{2299}\equiv_{_{3233}} 1117,\ 2535^{2299}\equiv_{_{3233}} 619=0619, \dots $$ Декодировав открытый текст $$x=1806\ 1117\ 0619\ 1415\ 0600\ 1609\ 1829\ 1315 \ ,$$ контрразведчик узнает исключительно важную информацию… ♦
Теория вскрытия шифра очевидна. Обсудим теперь, какой из ее этапов окажется для противника наиболее трудозатратным. Для вычисления функции $ x^{\mathbf E} $ достаточно знать числа $ \mathbf E $ и $ M_{} $ открытого ключа шифрования. А вот для вычисления обратной функции требуется знать секретное число $ \mathbf D $. Казалось бы, ничего не стоит, зная число $ M_{} $, разложить его на простые сомножители $ p_{1} $ и $ p_{2} $, вычислить затем $ \phi (M)=(p_1-1)(p_2-1) $ и, наконец, решив сравнение $ \mathbf E \cdot \mathbf D \equiv 1 \pmod{\phi(M)} $ относительно $ \mathbf D $ с помощью алгоритма, приведенного ☞ ЗДЕСЬ, восстановить ключ дешифрования. Все шаги этого алгоритма могут быть организованы достаточно быстро за исключением первого. Именно разложение $ M_{} $ на простые множители и составляет наиболее трудоемкую часть вычислений. Можно, разумеется, «просеять» $ M_{} $ сквозь решето Эратосфена, т.е. проверить его на делимость всеми простыми числами от 2 до $ \sqrt {M} $. Используя оценку Чебышева для количества простых чисел в этом промежутке, находим, что при $ M_{} $, записываемом $ 100_{} $ десятичными цифрами, найдется не менее $ 8 \times 10^{47} $ простых чисел, на которые нам придется поделить. Трудно представить себе таблицу, содержащую все эти числа. Очень грубые прикидки показывают, что компьютеру, выполняющему миллион делений в секунду, для факторизации числа $ M>10^{99} $ таким способом потребуется не менее $ 10^{35} $ лет.
Пример 3. Спецслужбой перехвачена шифровка террориста
$$ c= {\scriptstyle 9976044038299515658442835231516441812701086458822122421813996750926221914204989573850605} \ . $$ Известно, что сообщение состоит из одного блока, открытый текст закодирован стандартной кодировкой и зашифрован ключом $${\mathbf E}=7,\ M=\underbrace{{\scriptstyle 338821824671069882129800491138113464794971343556136506208048590265703663071343680581191959}}_{90}\ . $$ За какое время спецслужба сможет дешифровать это сообщение, если в ее распоряжении имеется пакет компьютерной алгебры MAPLE V Release $ 12_{} $, установленный на ноутбуке с процессором Core 2 Duo 2 GHz, модель T5750, ОЗУ 2 Gb?
Решение. Программа разложит число $ M_{} $ в произведение двух простых чисел за 2.5 часа.
Ключ дешифрования $ {\mathbf D} $ мгновенно найдется как решение сравнения $ {\mathbf D} \cdot {\mathbf E} \equiv 1 \pmod{(p_1-1)(p_2-1)} $: $${\mathbf D}={\scriptstyle 145209353430458520912771639059191484912130575309666969203242663234000998420752133501571703} \ ,$$ и также мгновенно восстановится открытый текст: $ x=c^{{\mathbf D}} \pmod{M}= $
02 | 15 | 13 | 02 | 01 | 00 | 03 | 08 | 15 | 17 | 03 | 06 | 19 | 18 | 32 | 00 | 24 | 06 | 17 | 06 | 08 | 00 | 24 | 01 | 18 |
б | о | м | б | а | в | з | о | р | в | е | т | с | я | ч | е | р | е | з | ч | а | с |
---|
Его содержание к моменту дешифрования уже потеряет актуальность… ♦
Есть, разумеется, вероятность, что противник, перехвативший сообщение, оказывается исключительно везучим человеком — простым перебором чисел он случайно наткнется на ключ дешифрования $ {\mathbf D} $; случается также, что и обладатель ключа — невнимательный растяпа…
Для $ M=989 $
а) найти ключ дешифрования $ {\mathbf D} $ при ключе шифрования $ {\mathbf E}=43 $ (или $ {\mathbf E}=155 $);
б) закодировать сообщение «БУХ» стандартной кодировкой и зашифровать ключом $ {\mathbf E}=29 $.
…однако подобные случаи следует отнести к категории маловероятных: благодать и глупость — это дары Божие и, будучи таковыми, научному анализу не подлежат!
Пример 4. Для иллюстрации надежности RSA, авторы алгоритма в $ 1977 $г. закодировали14) числом $ x_{} $ некоторую английскую фразу15) и зашифровали ее ключом $ {\mathbf E}=9007 $,
$$ M= {\scriptstyle 114381625757888867669325779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541} \ . $$ Здесь $ M_{} $ состоит из $ 129 $ знаков. Эти два числа и шифротекст $$ c= {\scriptstyle 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154} $$ были опубликованы известным американским популяризатором науки Мартином Гарднером [9]; дополнительно сообщалось, что $ M=p_1p_2 $, где $ p_{1} $ и $ p_{2} $ — простые числа, записываемые $ 64 $ и $ 65 $ десятичными знаками соответственно. Первому, кто дешифрует сообщение была обещана награда в $ 100_{} $ $ $ $ .
Эта история завершилась $ 17 $ лет спустя, в $ 1994 $ г., когда под руководством авторов проекта [10] число $ M_{} $ было факторизовано за $ 220 $ дней работы примерно $ 1600 $ компьютеров и $ 600 $ добровольцев, объединенных сетью Интернет. ♦
Как найти достаточно большие простые числа?
Действительно, стойкость алгоритма RSA основана на возможности выбора простых чисел, состоящих из не менее $ 100 $ десятичных знаков. Поиск таких чисел последовательным перебором всех нечетных, начиная с некоторого стартового, и последующим «просеиванием» через решето Эратосфена весьма затруднителен. (Известно, например, что для любого натурального $ k_{} $ существует такое натуральное число $ N_{} $, что все числа $ N+1,N+2,\dots,N+k $ будут составными; см. ☞ ЗДЕСЬ.) Проблему решают обходным маневром. Возможного кандидата на простое число подвергают испытанию серией однотипных и легко осуществимых тестов. Положительность результата хотя бы одного теста однозначно свидетельствует о том, что кандидат является числом составным; с другой стороны, отрицательный результат теста не дает абсолютной гарантии простоты кандидата, но свидетельствует о том, что вероятность его быть составным уменьшилась на определенную величину, скажем, в два раза. Тогда с увеличением количества отрицательных результатов все меньше шансов у испытуемого числа оказаться составным. Организовав серию испытаний из большого количества — например, $ 100 $ — тестов и получив все их результаты отрицательными, мы имеем право сказать, что кандидат является скорее всего («вроде бы») простым, с вероятностью не менее $$ (1-0.5^{100}) \approx 99.\underbrace{99\dots99}_{28} \% . $$
Алгоритмы подобных испытаний
☞
ЗДЕСЬ.
разбирается ☞ ЗДЕСЬ.
Как только будет найден быстрый метод факторизации больших целых чисел или изобретен алгоритм решения сравнения $ x^{\mathbf E} \equiv c \pmod{M} $, не требующий предварительной факторизации модуля $ M_{} $, использование алгоритма RSA для целей криптографии потеряет смысл. Использование этого алгоритма основано на уверенности в том, что уж если за последние три века не было создано универсального способа факторизации, то трудно ожидать, что он будет придуман нашими современниками.
Однако, иногда — из-за неудачного выбора параметров алгоритма — возможна достаточно быстрая факторизация модуля; иногда удается даже вытянуть из шифровок содержание открытого текста без предварительного определения ключа дешифрования.
Подробнее об потенциальных угрозах взлома ключа или шифровки
☞
ЗДЕСЬ.
Сама идея открытости ключа шифрования была революционной. Оказывается, однако, что ее можно использовать не только для решения задачи конфиденциальности переписки, но и для для другой проблемы — подтверждения авторства и неподдельности полученного сообщения. Грубо говоря, можно попробовать «привязать» автора сообщения к его ключу шифрования — хотя бы для того, чтобы иметь гарантию, что пришедшее какому-то адресату сообщение (даже открытое, нешифрованное) принадлежит именно законному отправителю, а не подменено «по пути».
Подробнее о проблеме подмены сообщения и о цифровой подписи
☞
ЗДЕСЬ.
[1]. Владимир Николаевич. Тайнопись. «Компьютерра» N 14-15 от 23 мая 2003. Текст ☞ ЗДЕСЬ
[2]. Жельников В. Криптография от папируса до компьютера. М.: АВР,1996.
[3]. Саломаа А. Криптография с открытым ключом. М., 1996.
[4]. Масленников М. Криптография и свобода. 2009 (?) Текст ☞ ЗДЕСЬ
[5]. Введение в криптографию. Под ред. В.В.Ященко. М., 1998.
[6]. Утешев А.Ю., Черкасов Т.М., Шапошников А.А. Цифры и шифры.СПб.: Изд-во СПбГУ, 2001.
[7]. Яглом А.М., Яглом И.М. Вероятность и информация. М. ГТТИ. 1957.
[8]. Menezes A.J., van Oorschot P.C., Vanstone P.C. Handbook of Applied Cryptography. CRC Press, 1996.
[9]. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public key cryptosystems. Communications of the ACM. 1978. Vol. 21. N 2. P. 120-126.
[10]. Gardner M. A new kind of cipher that would take millions of years to break. Scientific American. 1977. Vol. 237. N 2. P. 120-124.
[11]. Atkins D., Graff M., Lenstra A.K., Leyland P.C. The magic words are squeamish ossifrage16). Advances in Cryptology - ASIACRYPT'94, Lecture Notes in Comput. Sci. Vol. 917. Berlin, 1995. P. 263-277.