|
|
Международный алгоритм шифрования данных IDEA
Шифр IDEA (International Data Encryption Algorithm) был разработан Лэй и Мэсси из ETH в Цюрихе. Этот шифр, наряду с RSA, применяется в популярной компьютерной криптосистеме PGP (Pretty Good Privacy).
IDEA представляет собой блочный шифр, использующий 128 битный ключ, для преобразования открытых 64 битных текстовых блоков.
Графическая схема алгоритма IDEA
64 битный текстовый блок подвергается в ходе шифрования следующим процедурам:
· A^B - побитовое сложение по модулю 2;
если A+B=>2, то A^B=А+B-2
если A+B<2 , то A^B<А+B, где A и B 1-битные числа.
· A(+)B - сложение по модулю 216;
если A+B=>216, то A(+)B=A+B-216
если A+B<216 , то A(+)B=A+В, где A и B 16-битные числа.
· A(*)B - умножение по модулю 216+1;
если A* B=>216+1, то A(*)B=A*B-216-1
если A* B<216+1 , то A(*)B=A*B, где A и B 16-битные числа.
Процесс шифрования представляет собой цикл из восьми шагов:
На первом шаге:
p1 (*) s1 --> d1 p2 (+) s2 --> d2 p3 (+) s3 --> d3 p4 (*) s4 --> d4
d1 ^ d3 --> d5 d2 ^ d4 --> d6
d5 (*) s5 --> d7 d6 (+) d7 --> d8 d8 (*) s6 --> d9 d7 (+) d9 --> d10
d1 ^ d9 --> d11 d3 ^ d9 --> d12 d2 ^ d10 --> d13 d4 ^ d10 --> d14
p1, p2, p3, p4 – четыре 16 битных блока, на которые разбиваются один блок исходного текста
s1, s2, s3, s4, s5, s6 – шесть 16 битных подключей.
На следующем шаге в качестве p1, p2, p3, p4 используют d11, d13, d12, d14 и новые шесть подключей. Полученные четыре последние 16 битных блока и есть зашифрованный текст. Процесс дешифрования осуществляется аналогично.
Шифрование и дешифрование отличаются только подключами. Первые восемь подключей определяются с помощью 128 битного ключа, который разделяется на восемь частей. Новые восемь подключей определяются следующим образом: начальный ключ смещается на 25 бит, и разделяется на восемь частей.
Подключи для дешифрования определяются таблицей:
1 шаг s49* s50# s51# s52* s47 s48
2 шаг s43* s45# s44# s46* s41 s42
3 шаг s37* s39# s38# s39* s35 s36
4 шаг s31* s33# s32# s34* s29 s30
5 шаг s25* s27# s26# s28* s23 s24
6 шаг s19* s21# s20# s22* s17 s18
7 шаг s13* s15# s14# s16* s11 s12
8 шаг s7* s9# s8# s10* s5 s6
Последнее преобразование s1* s2# s3# s4*
sXX* = мультипликативная инверсия sXX по модулю 216+1
sXX# = аддитивная инверсия sXX по модулю 216
Алгоритм RSA
Как бы ни были сложны и надежны криптографические системы - их слабое место при практической реализации - проблема распределения ключей. Для того чтобы был возможен обмен конфиденциальной информацией между двумя субъектами ИС, ключ должен быть сгенерирован одним из них, а затем, в конфиденциальном порядке, передан другому. Т.е. в общем случае для передачи ключа опять же требуется использование какой-то криптосистемы.
Для решения этой проблемы на основе результатов, полученных классической и современной алгеброй, были предложены системы с открытым ключом.
Суть их состоит в том, что каждым адресатом ИС генерируются два ключа, связанные между собой по определенному правилу. Один ключ объявляется открытым, а другой закрытым. Открытый ключ публикуется и доступен любому, кто желает послать сообщение адресату. Секретный ключ сохраняется в тайне.
Исходный текст шифруется открытым ключом адресата и передается ему. Зашифрованный текст в принципе не может быть расшифрован тем же открытым ключом. Дешифрование сообщение возможно только с использованием закрытого ключа, который известен только самому адресату.
Асимметричные криптографические системы используют так называемые необратимые или односторонние функции, которые обладают следующим свойством: при заданном значении x относительно просто вычислить значение f(x), однако если y=f(x), то нет простого пути для вычисления значения x.
Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах. Так, алгоритм RSA стал мировым стандартом де-факто для открытых систем.
Алгоритмы криптосистем с открытым ключом можно использовать в 3 назначениях.
1. Как самостоятельные средства защиты передаваемых и хранимых данных.
2. Как средства для распределения ключей.
3. Средства аутентификации пользователей.
Алгоритмы криптосистем с открытым ключом более трудоемки, чем традиционные криптосистемы, поэтому использование их в качестве самостоятельных средств защиты нерационально.
Поэтому на практике рационально с помощью криптосистем с открытым ключом распределять ключи, объем которых как информации незначителен. А потом с помощью обычных алгоритмов осуществлять обмен большими информационными потоками.
Несмотря на довольно большое число различных криптосистем с открытым ключом, наиболее популярна - криптосистема RSA, разработанная в 1977 году и получившая название в честь ее создателей: Ривеста, Шамира и Эйдельмана.
Ривест, Шамир и Эйдельман воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо. Доказано (теорема Рабина), что раскрытие шифра RSA эквивалентно такому разложению. Поэтому для любой длины ключа можно дать нижнюю оценку числа операций для раскрытия шифра, а с учетом производительности современных компьютеров оценить и необходимое на это время.
Пусть n=p*q, где p и q - различные простые числа, и e и d удовлетворяют уравнению
e*d (mod (p-1)*(q-1))= 1
Если p и q - достаточно большие простые числа, то разложение n практически не осуществимо. Это и заложено в основу системы шифрования RSA.
{e,n} образует открытый ключ, а {d,n} - закрытый (можно взять и наоборот).
Открытый ключ публикуется и доступен каждому, кто желает послать владельцу ключа сообщение, которое зашифровывается указанным алгоритмом. После шифрования, сообщение невозможно раскрыть с помощью открытого ключа. Владелец же закрытого ключа без труда может расшифровать принятое сообщение.
Шифрование осуществляется по формуле: Sшифр = Se mod N
Шифрование осуществляется по формуле: S = Sdшифр mod N
Где S – исходный текст, Sшифр – преобразованный текст, при этом S < N
Оценка надежности криптосистем
Группа известных специалистов-криптографов, созданная под эгидой Альянса производителей программного обеспечения для бизнеса (промышленной организации, препятствующей незаконному использованию программного обеспечения), пришла к выводу, что необходимая длина ключа в настоящее время должна быть не менее 75 битов с дальнейшим увеличением в течение последующих 20 лет до 90 битов. Проверим данное утверждение.
Проблема поиска ключей симметричной криптосистемы путем перебора всех возможных ключей относится к классу задач, допускающих распараллеливание. Применение распределенных вычислений для организации перебора таких ключей позволяет эффективно решать трудоемкие задачи в этой области. Экспоненциальная динамика роста с течением времени производительности вычислительных систем (10 раз за 5 лет) оказывает еще более существенное влияние на рост производительности системы в целом. Таким образом, прогресс в этой области возможен за счет:
1) использования достижений научно-технического прогресса и применения технологических новинок для увеличения производительности отдельного устройства;
2) увеличения количества таких устройств в системе.
C физической точки зрения тот тип транзистора, который является основой современной интегральной схемы, может быть уменьшен еще примерно в 10 раз, до размера 0,03 мк. За этой гранью процесс включения/выключения микроскопических переключателей станет практически невозможным. Таким образом максимальное быстродействие составит - 1016 операций/секунду, а предел роста наступит приблизительно в 2030 г.
Других способов повышения вычислительной мощности нет. Таким образом, с точки зрения защиты информации криптографическими методами, анализ потенциальных возможностей метода распределенных вычислений представляет как для криптоаналитиков, так и для разработчиков криптографических систем значительный интерес. Попробуем, поэтому, проанализировать предельные значения двух указанных тенденций.
Из списка, появившегося летом 1999 года, следует, что по быстродействию суперкомпьютеры распределились следующим образом:
с мощностью порядка 1012 FLOPS 3 экз.;
с мощностью порядка 1011 FLOPS 54 экз.;
с мощностью порядка 1010 FLOPS 428 экз.;
При использовании материалов активная ссылка на источник обязательна.