Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
 Скачать 3.25 Mb.
|
|
Методы Джунемана Этот MAC также называют квадратичным конгруэнтным кодом обнаружения манипуляции ( quadratic con- gruential manipulation detection code, QCMDC) [792, 789]. Сначала разделим сообщение на m-битовые блоки. Затем: H 0 = I H , , где I H - секретный ключ H i = (H i-1 + M i ) 2 mod p, где p - простое число, меньшее 2 m -1, а + обозначает целочисленное сложение. Джунеман (Jueneman) предлагает n = 16 и p = 2 31 -1. В [792] он также предлагает, чтобы H 1 использовался в качестве дополнительного ключа , а действительное сообщение начиналось бы с H 2 Из-за множества вскрытий типа дня рождения, выполненных в сотрудничестве с Доном Копперсмитом , Джунеман предложил вычислять QCMDC четыре раза, используя результат одной итерации в качестве IV для следующей итерации, а затем результаты объединяются в 128-битовое хэш-значение [793]. В дальнейшем эта идея была усилена за счет параллельного выполнения четырех итераций с поперечными связями между ними [790, 791]. Эта схема была взломана Копперсмитом [376]. В другом варианте [432, 434] операция сложения заменена XOR, и используются блоки сообщения, намного меньшие p. Кроме того, был задан H 0 , что превратило алгоритм в однонаправленную хэш-функцию без ключа . После того, как эта схема была вскрыта [612], она была усилена для использования в качестве части проекта European Open Shop Information-TeleTrust [1221], процитирована в CCITT X.509 [304] и принята ISO в 10118 [764, 765]. К сожалению Копперсмит взломал и эту схему [376]. В ряде исследований изучалась возможность использовать отличные от 2 основания экспоненты [603], но ни одно не оказалось перспективным. RIPE-MAC RIPE-MAC был изобретен Бартом Пренелом [1262] и использован в проекте RIPE [1305] (см. раздел 18.8). Он основан на ISO 9797 [763] и использует DES в качестве функции блочного шифрования . Существует два варианта RIPE-MAC: один, который использует обычный DES, называется RIPE-MAC1, а другой, использую- щий для еще большей безопасности тройной DES, называется RIPE-MAC3. RIPE-MAGI использует одно шиф- рование DES на 64-битовый блок сообщения, а RIPE-MAC3 - три. Алгоритм состоит из трех частей. Во первых, сообщение увеличивается так, чтобы его длина была кратна 64 битам. Затем, увеличенное сообщение разбивается на 64-битовые блоки. Для хэширования этих блоков в один блок используется функция сжатия, зависящая от секретного ключа . На этом этапе используется либо DES, либо тройной DES. Наконец, выход этой функции сжатия подвергается еще одному DES-шифрованию с другим клю- чом, полученным из ключа, используемого при сжатии . Подробности можно найти в [1305]. IBC-хэш IBC-хэш - это еще один MAC, используемый в проекте RIPE [1305] (см. раздел 18.8). Он интересен потому, что его безопасность доказана, вероятность успешного вскрытия может быть оценена количественно . К сожале- нию каждое сообщение должно хэшироваться новым ключом . Выбранный уровень безопасности ограничивает максимальный размер хэшируемого сообщения, чего не делает ни одна другая из рассмотренных в этой главе функция. С учетом этих соображений в отчете RIPE рекомендуется, чтобы IBC-хэш использовалась бы только для длинных, редко посылаемых сообщений. Ядром функции является h i = ((M i mod p) + v) mod 2 n Секретный ключ представляет собой пару p и v, где p - n-битовое простое число, а v - случайное число, меньшее 2 n . Значения M i получаются с помощью строго определенной процедуры дополнения . Вероятности вскрыть как однонаправленность, так и устойчивость к столкновениям, могут быть оценены количественно, и пользователи, меняя параметры, могут выбрать нужный уровень безопасности . Однонаправленная хэш-функция MAC В качестве MAC может быть использована и однонаправленная хэш-функция [1537]. Пусть Алиса и Боб ис- пользуют общий ключ K, и Алиса хочет отправить Бобу MAC сообщения M. Алиса объединяет K и M, и вычис- ляет однонаправленную хэш-функцию объединения: H(K,M). Это хэш-значение и является кодом MAC. Так как Боб знает K, он может воспроизвести результат Алисы, а Мэллори, которому ключ неизвестен, не сможет это сделать. Со методами MD-усиления этот способ работает, но есть серьезные проблемы. Мэллори всегда может доба- вить новые блоки к концу сообщения и вычислить правильный MAC. Это вскрытие может быть предотвращено, если к началу сообщения добавить его длину , но Пренел сомневается в этой схеме [1265]. Лучше добавлять ключ к концу сообщения, H(M,K), но при этом также возникают проблемы [1265]. Если H однонаправленная функция, которая не защищена от столкновений , Мэллори может подделывать сообщения. Еще лучше H(K,M,K) или H(K l ,M,K 2 ), где K l и K 2 различны [1537]. Пренел не уверен и в этом [1265]. Безопасными кажутся следующие конструкции : H(K l , H(K 2 , M)) H(K, H(K,M)) H(K, p,M,K)), где p дополняет K до полного блока сообщения. Лучшим подходом является объединение с каждым блоком сообщения по крайней мере 64 битов ключа. Это делает однонаправленную функцию менее эффективной, так как уменьшаются блоки сообщения, но так она становится намного безопаснее [1265]. Или используйте однонаправленную хэш-функцию и симметричный алгоритм . Сначала хэшируйте файл, потом зашифруйте хэш-значение. Это безопаснее, чем сначала шифровать файл, а затем хэшировать зашифр о- ванный файл, но эта схема чувствительна к тому же вскрытию, что и конструкция H(M,K) [1265]. MAC с использованием потокового шифра Эта схема MAC использует потоковые шифры (см. 3-й) [932]. Криптографически безопасный генератор псевдослучайных битов демультиплексирует поток сообщения на два подпотока . Если на выходе генератора битов k i единица, то текущий бит сообщения m i отправляется в первый подпоток, если ноль, то m i отправляется во второй подпоток. Каждый подпоток отправляется на свой LFSR (раздел 16.2). Выходом MAC просто являет- ся конечное состояние обоих регистров. К несчастью этот метод небезопасен по отношению к небольшим изменениям в сообщении [1523]. Например, если изменить последний бит сообщения, то для создания поддельного MAC нужно будет изменить только 2 бита соответствующего MAC; это может быть выполнено с заметной вероятностью . Автор предлагает более безопасный, и более сложный, вариант . Сдвиговый регистр 1 Сдвиговый регистр 1 CSPRNG Пере- ключатель Поток сообщения Рис. 18-15. MAC с использованием потокового шифра. Глава 19 Алгоритмы с открытыми ключами 19.1 Основы Концепция криптографии с открытыми ключами была выдвинута Уитфилдом Диффи ( Whitfield Diffie) и Мартином Хеллманом (Martin Hellman), и независимо Ральфом Мерклом (Ralph Merkle). Их вкладом в крипто- графию было убеждение, что ключи можно использовать парами - ключ шифрования и ключ дешифрирования - и что может быть невозможно получить один ключ из другого (см. Раздел 2.5). Диффи и Хеллман впервые представили эту идею на Национальной компьютерной конференции ( National Computer Conference) 1976 года [495], через несколько месяцев была опубликована их основополагающая работа "New Directions in Cryptogra- phy'' ("Новые направления в криптографии") [496]. (Из-за бесстрастного процесса публикации первый вклад Меркла в эту область вышел появился только в 1978 году [1064].) С 1976 года было предложено множество криптографических алгоритмов с открытыми ключами . Многие из них небезопасны. Из тех, которые являются безопасными, многие непригодны для практической реализации . Либо они используют слишком большой ключ, либо размер полученного шифротекста намного превышает ра з- мер открытого текста. Немногие алгоритмы являются и безопасными, и практичными . Обычно эти алгоритмы основаны на одной из трудных проблем, рассмотренных в разделе 11.2. Некоторые из этих безопасных и практичных алгоритмов подходят только для распределения ключей . Другие подходят для шифрования (и для распределения ключей) . Третьи полезны только для цифровых подписей . Только три алгоритма хорошо работают как при шифровании, так и для цифровой подписи: RSA, EIGamal и Rabin. Все эти алгоритмы медленны. Они шифруют и дешифри- руют данные намного медленнее, чем симметричные алгоритмы. Обычно их скорость недостаточна для шифр о- вания больших объемов данных. Гибридные криптосистемы (см. раздел 2.5) позволяют ускорить события: для шифрования сообщения ис- пользуется симметричный алгоритм со случайным ключом, а алгоритм с открытым ключом применяется для шифрования случайного сеансового ключа. Безопасность алгоритмов с открытыми ключами Так как у криптоаналитика есть доступ к открытому ключу, он всегда может выбрать для шифрования любое сообщение. Это означает, что криптоаналитик при заданном C = E K (P) может попробовать угадать значение P и легко проверить свою догадку. Это является серьезной проблемой, если количество возможных открытых те к- стов настолько мало, что делает возможным исчерпывающий поиск, но эту проблему легко можно решить, д о- полняя сообщения строкой случайных битов . Это приводит к тому, что идентичным открытым текстам соотве т- ствуют различные шифротексты. (Более подробно эта идея описана в разделе 23.15.) Это особенно важно, если алгоритм с открытым ключом используется для шифрования сеансового ключа . Ева может создать базу данных всех возможных сеансовых ключей, зашифрованных открытым ключом Боба . Конечно, это потребует много времени и памяти, но взлом грубой силой разрешенного к экспорту 40-битового ключа или 56-битового ключа DES потребует намного больше времени и памяти . Как только Ева создаст такую базу данных, она получит ключ Боба и сможет читать его почту . Алгоритмы с открытыми ключами спроектированы так, чтобы противостоять вскрытиям с выбранным о т- крытым текстом. Их безопасность основана как на трудности получения секретного ключа по открытому, так и на трудности получить открытый текст по шифротексту . Однако большинство алгоритмов с открытым ключом особенно чувствительны к вскрытию с выбранным шифротекстом (см. раздел 1.1). В системах, в которых операция, обратная шифрованию, используется для цифровой подписи, это вскрытие невозможно предотвратить, если для шифрования и подписей использовать одинаковые ключи . Следовательно, важно увидеть всю систему целиком, а не только составные части . Хорошие протоколы с от- крытыми ключами спроектированы таким образом, чтобы различные стороны не могли расшифровать прои з- вольные сообщения, генерированные другими сторонами, - хорошим примером являются протоколы доказ а- тельства идентичности (см. раздел 5.2). 19.2 Алгоритмы рюкзака Первым алгоритмом для обобщенного шифрования с открытым ключом стал алгоритм рюкзака, разраб о- танный Ральфом Мерклом и Мартином Хеллманом [713, 1074]. Он мог быть использован только для шифров а- ния, хотя позднее Ади Шамир адаптировал систему для цифровой подписи [1413]. Безопасность алгоритмов рюкзака опирается на проблему рюкзака , NP-полную проблему. Хотя позже было обнаружено, что этот алг о- ритм небезопасен, его стоит изучить, так как он демонстрирует возможность применения NP-полной проблемы в криптографии с открытыми ключами. Проблема рюкзака несложна. Дана куча предметов различной массы, можно ли положить некоторые из этих предметов в рюкзак так, чтобы масса рюкзака стала равна определенному значению ? Более формально, дан набор значений M l , M 2 , . . . , M n и сумма S, вычислить значения b i , такие что S = b l M 1 + b 2 M 2 + . . . + b n M n b i может быть либо нулем, либо единицей. Единица показывает, что предмет кладут в рюкзак, а ноль - что не кладут. Например, массы предметов могут иметь значения 1 , 5, 6, 11, 14 и 20. Вы можете упаковать рюкзак так, чтобы его масса стала равна 22, использовав массы 5, 6 и 11. Невозможно упаковать рюкзак так, чтобы его ма с- са была равна 24. В общем случае время, необходимое для решения этой проблемы, с ростом количества пре д- метов в куче растет экспоненциально. В основе алгоритма рюкзака Меркла-Хеллмана лежит идея шифровать сообщение как решение набора пр о- блем рюкзака. Предметы из кучи выбираются с помощью блока открытого текста, по длине равного количеству предметов в куче (биты открытого текста соответствуют значениям b), а шифротекст является полученной сум- мой. Пример шифротекста, зашифрованного с пом ощью проблемы рюкзака, показан на . Открытый текст 1 1 1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 Рюкзак 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20 1 5 6 11 14 20 Шифротекст 1+5+6+20=32 5+11+14=30 0=0 5+6=11 Рис. 19-1. Шифрование с рюкзаками Фокус в том, что на самом деле существуют две различные проблемы рюкзака , одна решается за линейное время, а другая, как считается, - нет. Легкую проблему можно превратить в трудную . Открытый ключ представ- ляет собой трудную проблему, которую легко использовать для шифрования, но невозможно для дешифриров а- ния сообщений. Закрытый ключ является легкой проблемой, давая простой способ дешифрировать сообщения . Тому, кто не знает закрытый ключ, придется попытаться решить трудную проблему рюкзака . Сверхвозрастающие рюкзаки Что такое легкая проблема рюкзака? Если перечень масс представляет собой сверхвозрастающую последо- вательность, то полученную проблему рюкзака легко решить. Сверхвозрастающая последовательность - это последовательность, в которой каждой член больше суммы всех предыдущих членов . Например, последова- тельность {1,3,6,13,27,52} является сверхвозрастающей, а {1,3,4,9, 15,25} - нет. Решение сверхвозрастающего рюкзака найти легко. Возьмите полный вес и сравните его с самым бол ь- шим числом последовательности. Если полный вес меньше, чем это число, то его не кладут в рюкзак . Если пол- ный вес больше или равен этому числу, то оно кладется в рюкзак . Уменьшим массу рюкзака на это значение и перейдем к следующему по величине числу последовательности . Будем повторять, пока процесс не закончится . Если полный вес уменьшится до нуля, то решение найдено. В противном случае , there isn't. Например, пусть полный вес рюкзака - 70, а последовательность весов {2,3,6, 13,27,52}. Самый большой вес, 52, меньше 70, поэтому кладем 52 в рюкзак. Вычитая 52 из 70, получаем 18. Следующий вес, 27, больше 18, поэтому 27 в рюкзак не кладется. вес, 13,меньше 18, поэтому кладем 13 в рюкзак. Вычитая 13 из 18, полу- чаем 5. Следующий вес, 6, больше 5, поэтому 6 не кладется в рюкзак. Продолжение этого процесса покажет, что и 2, и 3 кладутся в рюкзак, и полный вес уменьшается до 0, что сообщает о найденном решении. Если бы это был блок шифрования методом рюкзака Меркла-Хеллмана , открытый текст, полученный из значения шифр о- текста 70, был бы равен 110101. Не сверхвозрастающие, или нормальные, рюкзаки представляют собой трудную проблему - быстрого алг о- ритма для них не найдено. Единственным известным способом определить, какие предметы кладутся в рюкзак, является методическая проверка возможных решений, пока вы не наткнетесь на правильное . Самый быстрый алгоритм, принимая во внимание различную эвритсику , имеет экспоненциальную зависимость от числа во з- можных предметов. Добавьте к последовательности весов еще один член, и найти решение станет вдвое труднее. Это намного труднее сверхвозрастающего рюкзака, где, если вы добавите один предмет к последов а- тельности, поиск решения увеличится на одну операцию . Алгоритм Меркла-Хеллмана основан на этом свойстве . Закрытый ключ является последовательностью весов проблемы сверхвозрастающего рюкзака. Открытый ключ - это последовательность весов проблемы нормально- го рюкзака с тем же решением. Меркл и Хеллман, используя модульную арифметику, разработали способ пр е- образования проблемы сверхвозрастающего рюкзака в проблему нормального рюкзака. Создание открытого ключа из закрытого Рассмотрим работу алгоритма, не углубляясь в теорию чисел : чтобы получить нормальную последовател ь- ность рюкзака, возьмем сверхвозрастающую последовательность рюкзака, например, {2,3,6,13,27,52}, и умно- жим по модулю m все значения на число n. Значение модуля должно быть больше суммы всех чисел последов а- тельности, например, 105. Множитель должен быть взаимно простым числом с модулем, например, 31. Нор- мальной последовательностью рюкзака будет 2*31 mod 105 = 62 3*31 mod 105 = 93 6*31 mod 105 = 81 13*31 mod 105 = 88 27*31 mod 105 = 102 52*31 mod 105 = 37 Итого - {62,93,81,88,102,37}. Сверхвозрастающая последовательность рюкзака является закрытым ключом, а нормальная последовател ь- ность рюкзака - открытым. Шифрование Для шифрования сообщение сначала разбивается на блоки, равные по длине числу элементов последов а- тельности рюкзака. Затем, считая, что единица указывает на присутствие члена последовательности, а ноль - на его отсутствие, вычисляем полные веса рюкзаков - по одному для каждого блока сообщения . Например, если сообщение в бинарном виде выглядит как 011000110101101110, шифрование, использую- щее предыдущую последовательность рюкзака, будет происходить следующим образом : сообщение = 011000 110101 101110 011000 соответствует 93 + 81 = 174 110101 соответствует 62 + 93 + 88 + 37 = 280 101110 соответствует 62 + 81 + 88 + 102 = 333 Шифротекстом будет последовательность 174,280,333 Дешифрирование Законный получатель данного сообщения знает закрытый ключ: оригинальную сверхвозрастающую посл е- довательность, а также значения n и m, использованные для превращения ее в нормальную последовательность рюкзака. Для дешифрирования сообщения получатель должен сначала определить n -1 , такое что n(n -1 )?1 (mod m). Каждое значение щифротекста умножается на n -1 mod m, а затем разделяется с помощью закрытого ключа, чтобы получить значения открытого текста. В нашем примере сверхвозрастающая последовательность - {2,3,6,13,27,52), m равно 105, а n - 31. Шифро- текстом служит 174,280,333. В этом случае n -1 равно 61, поэтому значения шифротекста должны быть умнож е- ны на 61 mod 105. 174*61 mod 105 = 9 = 3 + 6, что соответствует 011000 280*61 mod 105 = 70 = 2 + 3 + 13 + 52, что соответствует 110101 333*61 mod 105 = 48 = 2 + 6 + 13 + 27, что соответствует 101110 Расшифрованным открытым текстом является 011000 110101 101110. |