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

kIlka и AssassiN

Спецвыпуск Xakep, номер #041, стр. 041-004-4

Суть в том, что только AssassiN может вычислить функцию SA() за разумное время, так как только он знает число d. Конечно, злоумышленник может разложить известное ему число n на множители r и h и тем самым определить d. Но существующие ныне алгоритмы будут пыхтеть над разложением n очень долго. Кстати, если кого-то интересует математически строгое обоснование корректности RSA, то найти его можно в [2].

Цифровая подпись

Интересным свойством криптосистем с открытым ключом (и в частности - криптосистемы RSA) является то, что они позволяют не только шифровать сообщения, но и создавать так называемые "цифровые подписи" (digital signature), удостоверяющие авторство и правдивость сообщения.

RSA-алгоритм создания цифровой подписи

Вот как это происходит. AssassiN пишет ответ M kIlk'е, далее вычисляет цифровую подпись E=SA(M) и отсылает пару (M,E) kIlk'е, который, в свою очередь, получает пару (M,E) и убеждается в подлинности послания, проверив равенство M=PA(E). Таким образом можно подписывать, например, банковские поручения, а если нужно сохранить секретность, то пару (M,E) следует тоже зашифровать.

Очевидно, генерируемая таким образом цифровая подпись избыточна – размер ее пропорционален размеру сообщения, а ведь необходимо время на ее создание, пересылку вместе с секретной информацией и дешифрацию. Поэтому для создания цифрового росчерка применяют однонаправленную хеш-функцию. Такая функция (обозначим ее H()) преобразуют сообщения в достаточно короткие "образы". Причем не существует двух различных сообщений A и B, для которых H(A) = H(B) (это предположение верно в разумных пределах, естественно; например, у 128-битной хеш-функции будет 2^128 вариантов хеша, учитывая, что сообщений существует больше, то разумно предположить: существуют некие сообщения M1 и M2, такие, что H(M1) = H(M2) - прим. ред.). AssassiNу достаточно зашифровать с помощью SA() не все сообщение M, а лишь H(M).

Однако и криптографические схемы с открытым ключом не лишены недостатков. Главный из них – невозможность достоверно определить, кому принадлежит открытый ключ. Злоумышленник может перехватить открытый ключ твоего товарища, а вместо него прислать свой. Тогда с дешифровкой у него проблем не возникнет. Для борьбы с такими умниками используется так называемый центр доверия. Образно говоря, это некий чрезвычайно честный человек, имеющий свой открытый ключ. Он может выдавать страждущим справки, подписанные его цифровой подписью, что их открытые ключи принадлежат действительно им.

Под занавес хочется сказать несколько слов о слабых местах криптографических систем. В последнее время в подавляющем большинстве компьютерных программ, использующих криптографию, применяются алгоритмы, надежность которых доказана математически. Но все же конкретная реализация может иметь слабое место, а иногда и не одно. Хранение ключей или незашифрованных данных на жестком диске для лучшей сохранности, утюги и паяльники злоумышленников и тому подобные глупости могут свести на нет всю математическую надежность криптоалгоритма... Вот и я для лучшей защищенности моего PGP диска пойду долбить стенку. С CD как-нибудь разберусь. Думаю, цемент M-500 будет в самый раз =).