Сравнительный обзор алгоритмов PGP

Со 128-битным ключом у нас 2^128 таблиц размером 2^64 каждая.

Тогда не возникает ли в пространстве 2^128 таблиц повторяющихся таблиц?

Тогда не возникает ли в пространстве 2^128 таблиц повторяющихся таблиц?

Я несколько неправильно дал ответ выше. Исправляюсь. Вот как легко запутаться даже в таких элементарных понятиях!

Перестановка для 64-битного блочного шифра считается как факториал:
(2^64)!
Все пространство перестановок значительно больше, но ключи размером и 2^64 и 2^128 и 2^256
дают лишь ничтожную выборку значений из этого гигантского пространства. Смотрите более
подробные расчеты в специальной литературе.


Вообще это важное понятие в криптоанализе – любая атака начинается в построении различителя шифра от случайной перестановки, затем идет к восстановлению ключа, поэтому в литературе по криптоанализу эти перестановки служат отправной точкой.

Насчет собственно повторяющихся таблиц, конечно они могут с ничтожной долей вероятности совпасть и стать одинаковыми для разных ключей, тогда речь идет об эквивалентных ключах или коллизиях ключей. Это похоже на естественные коллизии в хэш-функциях. Главные, чтобы они не были "неестественными", встречающимися чаще, чем по вероятности им положено или по какой-то закономерности, облегчающей криптоанализ.

Вот ссылки на определения "Pseudorandom functions and permutations", которые являются базовыми в построении блочных шифров:

http://www.cs.berkeley.edu/~da.....ing/cs276-s04/03b.ps
http://www.cs.berkeley.edu/~da.....ing/cs276-s04/04a.ps
http://www.cs.berkeley.edu/~da.....ing/cs276-s04/04b.ps

Попробуйти найти что-то более легкое для понимания, если сможете.

Или просто запомните, что ключи размером 64 или 256 бит дают намного меньше вариантов отображений открытого текста в шифртекст, чем возможно в блоке размером 64 бита.

(Иначе бы например 3-DES образовывал бы группу, хотя доказано, что комбинация трех разных ключей не сводится к одному ключу, т.е. дает иное отображение, не входящее в множество 64 (56)-битных ключей. Тут относительно не такая очевидная и простая математика, как кажется и "на пальцах" это все не объяснить).

... А ответ на самом деле надо было дать простой:

Nb – длина блока. Nk – длина ключа.
Для фиксированного ключа мы имеем 2^Nb входов и (2^Nb)! Всех возможных псевдослучайных перестановок.
Для всего множества ключей: (2^Nb)!^(2^Nk)

Если я в очередной раз ничего не перепутал. ;-)

unknown, простите, что за ps файл? Скачал, не знаю чем открывать.

unknown, простите, что за ps файл? Скачал, не знаю чем открывать.

Не знаю чем Вам помочь. Если бы Вы были в Линуксе, то такой бы вопрос у Вас бы даже не возник. ps.gz – "стандарт де факто" (В крайнем случае .pdf). для научных работ и статей и набор программ для работы с ним большой (начиная от gv).


Может под Win его тоже какой нибудь акробат-reader открывает?

P. S. Научные статьи в формате оффиса мне встречались только из России, Украины и Польши. Да и то от этого стараются уходить.

Гость,
GSView
http://www.cs.wisc.edu/~ghost/gsview/index.htm

unknown, Вам большое спасибо за ответы и интересную инфу. Acrobat Reader такие файлы не открывает, к сожалению.
sentaus, спасибо, скачал, но теперь еще нужно Ghostscript качать.

unknown, Вам большое спасибо за ответы и интересную инфу. Acrobat Reader такие файлы не открывает, к сожалению.

Всегда рад, когда кого-то интересуют вопросы криптографии и всего что с ней связано.

sentaus, спасибо, скачал, но теперь еще нужно Ghostscript качать.

[offtopic] Вот после этого Линукс у меня становится навязчивой идеей. ;-)
Как все проще.
Просто для примера:
Нам нужен просмотрщик для файлов postscript

Набираем: apt-cache search postscript | grep view

Выбираем подходящий по описанию, ставим тоже одной простой командой при этом смотрим, какие пакеты он по зависимостям требует и сколько будет качать или ставить с диска. По умолчанию все само, что нам надо для просмотра postscipt скачается и настроится. Даже думать не надо. Хотя можно вмешаться и вручную контролировать этот процесс.

И так (почти) для любого формата файлов или любой задачи.
Т.е. даже не надо узнавать, что нужно для просмотра файлов или решения какой-то задачи. Есть огромный массив программ для поиска, дистростроители уже сами обо всем позаботились и упаковали в пакеты с нужными зависимостями.

Например, на запрос apt-cache search | grep network | grep anonimity среди разных вариантов можно получить tor, а при попытке его поставить будут предложены privoxy и соксификаторы.

[/offtopic]