Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 9
С вашего позволения:
Если T > N/2, где N — число открытых текстов.
И действительно, легко заметить (с).
что такое PL, CL и CR? Не очень понятна связь между стат. аналогами каждого из блоков и стат. аналогом всего шифра (мы его получили?). Как так получилось, что на каждом из раундов s-блок имеет аналог заданного вида с вероятностью не более 1/4, а в сумме все раунды имеют полученный аналог с вероятностью 0.7?
PS: вы правда считаете что перевод статьи господина Мацуи — туториал для чайников?
Если T>1/2
Если T > N/2, где N — число открытых текстов.
Очевидно, что успех алгоритма напрямую зависит...
И действительно, легко заметить (с).
= PL[3] ⊕ PL[8] ⊕ PL[14]
что такое PL, CL и CR? Не очень понятна связь между стат. аналогами каждого из блоков и стат. аналогом всего шифра (мы его получили?). Как так получилось, что на каждом из раундов s-блок имеет аналог заданного вида с вероятностью не более 1/4, а в сумме все раунды имеют полученный аналог с вероятностью 0.7?
PS: вы правда считаете что перевод статьи господина Мацуи — туториал для чайников?
enrupt, спасибо за замечания.
Что касается вашего вопроса о вероятности 0.7, мы имеем выражение X=0, выполняющееся с вероятностью P1=12/64. И выражение Y=0, выполняющееся с вероятность P2=12/64.
Легко заметить (с), что Выражение X ⊕ Y = 0 выполняется либо когда X = 0 и Y = 0 (P=P1*P2) либо когда X = 1 и Y =1 (P=((1-P1)*(1-P2)). Следовательно вероятность X ⊕ Y = 0 равна P = P1*P2 + (1-P1)*(1-P2) = (12/64)2+(1-12/64)2 = 0.7
Да считаю что более подробного материала по теме просто нет. И почему сразу перевод?
Что касается вашего вопроса о вероятности 0.7, мы имеем выражение X=0, выполняющееся с вероятностью P1=12/64. И выражение Y=0, выполняющееся с вероятность P2=12/64.
Легко заметить (с), что Выражение X ⊕ Y = 0 выполняется либо когда X = 0 и Y = 0 (P=P1*P2) либо когда X = 1 и Y =1 (P=((1-P1)*(1-P2)). Следовательно вероятность X ⊕ Y = 0 равна P = P1*P2 + (1-P1)*(1-P2) = (12/64)2+(1-12/64)2 = 0.7
PS: вы правда считаете что перевод статьи господина Мацуи — туториал для чайников?
Да считаю что более подробного материала по теме просто нет. И почему сразу перевод?
Выражение X ⊕ Y = 0 выполняется...
Простите, мне пока не очень легко. Например мы получили, что уравнение, предшествующее (5), выполняется с вероятностью (12/64)^2(1-12/64)^2. Откуда взялась сумма вероятностей, если мы просто заменили X(1) = PR и X(3) = CR и перенесли слагаемые? В комментарии вы складываете слева 2 бита, а в статье — 2 вектора, или я что-то упустил?
Простите, моя вина. В пост вкралась ошибка. Вероятность конечно же равна не (12/64)^2(1-12/64)^2, а (12/64)^2+(1-12/64)^2.
Давайте попробуем вместе разобраться откуда взялась такая цифра.
Имеем с одной стороны уравнение:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] = PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26]
перенесем все слагаемые влево и получим:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] = 0 (1). Это уравнение выполняется с вероятностью P=12/64. Если не понятен этот пункт пожалуйста спрашивайте.
Идем дальше
С другой стороны имеется уравнение:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] = СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26]
опять перенесем все члены влево и получим
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26] = 0 (2) с вероятностью P=12/64.
Теперь сложим оба уравнения по модулю два и получаем:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] ⊕ X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26] =
=PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] ⊕ СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26 (3). Вычислим какова вероятность, что полученное уравнение равно нулю?
При каких условиях уравнение (3) будет равно 0? Когда уравнение (1) и (2) оба равны нулю или единице, т.е. с вероятностью (12/64)^2+(1-12/64)^2.
Теперь вернемся к уравнению (3) в нем осталось два неизвестных бита X(1)[17] и X(3)[17] но если внимательно посмотреть на схему DES видно что по сути это биты входной и выходной последовательности соответственно, т.е. мы можем заменить обозначение X(1)[17] на PR[17] и X(3)[17] на CR[17]. Это действие на вероятность выполнения уравнения (3) не влияет никаким образом.
Давайте попробуем вместе разобраться откуда взялась такая цифра.
Имеем с одной стороны уравнение:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] = PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26]
перенесем все слагаемые влево и получим:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] = 0 (1). Это уравнение выполняется с вероятностью P=12/64. Если не понятен этот пункт пожалуйста спрашивайте.
Идем дальше
С другой стороны имеется уравнение:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] = СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26]
опять перенесем все члены влево и получим
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26] = 0 (2) с вероятностью P=12/64.
Теперь сложим оба уравнения по модулю два и получаем:
X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] ⊕ X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26] =
=PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] ⊕ СL[3] ⊕ СL[8] ⊕ СL[14] ⊕ СL[25] ⊕ X(3)[17] ⊕ K3[26 (3). Вычислим какова вероятность, что полученное уравнение равно нулю?
При каких условиях уравнение (3) будет равно 0? Когда уравнение (1) и (2) оба равны нулю или единице, т.е. с вероятностью (12/64)^2+(1-12/64)^2.
Теперь вернемся к уравнению (3) в нем осталось два неизвестных бита X(1)[17] и X(3)[17] но если внимательно посмотреть на схему DES видно что по сути это биты входной и выходной последовательности соответственно, т.е. мы можем заменить обозначение X(1)[17] на PR[17] и X(3)[17] на CR[17]. Это действие на вероятность выполнения уравнения (3) не влияет никаким образом.
хм, давайте попробуем… хотя мне больше импонирует подход как в статье:
— по всей видимости, приравниваются левые части. Итак, мы имеем {a, x1, x2 in {0, 1}} a = x1 с вероятностью p1 и a = x2 с той же вероятностью, будет ли условная вероятность a = x2|a=x1 равна безусловной чтобы можно было просто сложить? Другими словами, существует ли зависимость между PL[3, 8, 14, 25], CL[3, 8, 14, 25] и X(2)[3,8,14,25]?
И чтобы не плодить комментарии — да, не сразу понял что обозначение X отличается от принятого в статье, отсюда и вектор.
Приравняв правые части уравнений (3) и (4)
— по всей видимости, приравниваются левые части. Итак, мы имеем {a, x1, x2 in {0, 1}} a = x1 с вероятностью p1 и a = x2 с той же вероятностью, будет ли условная вероятность a = x2|a=x1 равна безусловной чтобы можно было просто сложить? Другими словами, существует ли зависимость между PL[3, 8, 14, 25], CL[3, 8, 14, 25] и X(2)[3,8,14,25]?
И чтобы не плодить комментарии — да, не сразу понял что обозначение X отличается от принятого в статье, отсюда и вектор.
Другими словами, существует ли зависимость между PL[3, 8, 14, 25], CL[3, 8, 14, 25] и X(2)[3,8,14,25]?
Дело в том, что нам не нужно демонстрировать отсутствие зависимости между PL[3, 8, 14, 25], CL[3, 8, 14, 25] и X(2)[3,8,14,25].
Посмотрите внимательно на уравнение (1) из моего комментария выше. Обратите внимание на участие в нем бита K1[26]. Теперь заметьте участие бита K3[26] в уравнении (2). Оба эти бита взаимнонезависимы. И разумеется оба бита не зависят ни от значения PL ни от значения CL. А следовательно выражения (1) и (2) также являются независимыми.
Оба эти бита взаимнонезависимы.
Позвольте танкисту последний вопрос — а почему? Принимая во внимание процедуру генерации ключа (перестановки, сдвиги, исключение битов), действительно ли бит ключа на первом раунде не влияет на бит в той же позиции на третьем? И даже если это так, то как из этого следует независимость (1) и (2)? Например, кажется очевидной зависимость битов CL от PL и CL от X(2).
Позвольте танкисту последний вопрос — а почему?
Да ради бога)
Процедура генерации ключа на самом деле является просто очень усложненной перестановкой. Я сейчас проверил с учетом всех перестановок у меня получилось что K1[26] это 20 бит ключа K, а K3[26] это 64 бит ключа K. Т.е. это совершенно разные биты, сгенерированные независимо друг от друга.
Что касается второй части вопроса, то тут я с вами согласен связь CL со входной последовательностью PL действительно очевидна.
Но ведь мы рассматриваем общее уравнение X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] ⊕ K1[26] в которое включен независимый бит K1[26]. Т.е. даже если часть уравнения X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] ⊕ PL[3] ⊕ PL[8] ⊕ PL[14] ⊕ PL[25] ⊕ X(1)[17] имеет сильную зависимость между составными битами и, скажем, всегда равна 0. Даже в этом случае добавление одного по настоящему случайного бита K1[26] делает все выражение случайным.
Я кажется понял в чем возникло недопонимание:
И в комментарии и в статье складывается 2 бита информации,
запись вида X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] описывает один бит, полученный сложением по модулю два нескольких разных бит.
В комментарии вы складываете слева 2 бита, а в статье — 2 вектора
И в комментарии и в статье складывается 2 бита информации,
запись вида X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] описывает один бит, полученный сложением по модулю два нескольких разных бит.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Линейный криптоанализ для чайников