Тоже хотел поделиться любимой научной фантастикой, но разочарованно обнаружил, что комментаторы выше меня опередили. Поэтому грустно добавляю в пост немного юмористической литературы:
«Трое в лодке не считая собаки» Джером К. Джером — классика в представлении не нуждающаяся. Читал в детстве, рыдая от счастья.
«Записки сельского ветеринара» Джеймс Хэрриот — собственно название намекает о чем книга. Автор настоящий профессионал, любящий свою работу и умеющий очень смешно о ней рассказать.
«Моя семья и другие звери» Джеральд Даррел — забавная книга о детстве, животных и вообще.
«Я умею прыгать через лужи» Алан Маршалл — в этой книге не так много по настоящему смешных моментов, но она передает уникальное жизнелюбие автора и это подкупает.
А почему бы и нет? Это я про перепись хороших книг. Я понимаю на хабре это выглядело бы немного неуместно, но на новом проекте четкая направленность еще не сформировалась, вот и обсуждает народ то что интересно.
А можете пожалуйста пояснить чем не понравился Криптономикон?
Понимаю что на вкус и цвет фломастеры разные, но это одна из любимейших моих книг, которую советую всем без разбора. В ней хорошо на мой взгляд все и интересный сюжет и технические подробности и вообще криптография! Ну как можно не любить криптографию:) Поэтому хотелось бы понять что с ней не так, чтобы меня при случае не пинали за плохой совет тем кому книга тоже покажется отвратительной вещью:)
Я уже както кратко писал о возможных атаках на Вихрь Мерсенна и регистр с линейной обратной связью тут.
Использование каскадов РСЛОС, как например в сетях GSM, тоже весьма небезопасное решение.
RC4 тоже имеет свои недостатки, позволяющие при наличие большого объема известных пар открытый-закрытый текстов восстановить секретную информацию, скажем куки.
Механизмы атаки зависят от используемого ГПСЧ, но в общем случае почти всегда сводятся к атаке с известным открытым текстом или используют неправильную реализацию(к примеру, шифрование одним и тем же ключевым потоком двух и более сообщений).
И в очередной раз вынужден с вами согласиться:)
Разумеется, AES выглядит куда более предпочтительным решением. Но ситуации бывают всякие и поэтому я и написал в своем комментарии: «в случае крайней нужды».
Да не, я все-таки считаю что стойкость любого черного ящика из той же плоскости что и неуловимость ковбоя Джо. Если это кому-нибудь действительно станет нужно, то проприетарное решение имеет больше шансов оказаться уязвимым, по той простой причине, что не было должным образом исследовано. При этом, учитывая закрытость решения, факт взлома может оставаться в секрете достаточно длительное время и это может привести к большому ущербу.
Часто бывают ситуации когда человек в комментариях указывает на ошибки или недочеты в посте, делиться своими очень дельными мыслями или просто помогает автору разобраться в некоторых спорных моментах. В таких случаях плюс в карму такому человеку это весьма логичный и осмысленный шаг.
С учетом последнего обновления получается, что отблагодарить таких людей в карму больше не получится, по крайней мере тех, которые предпочитают не писать своих постов (назовем таких людей «комментаторами»).
У меня есть одно предложение. deniskin, а можно ли оставить возможность голосовать за карму таким людям(имею в виду тем у кого нет ни одного поста), но при этом, чтобы у голосующего карма уменьшалась на один пункт? Таким образом, с одной стороны у «комментаторов» останется возможность заработать положительную карму, но т.к. голосовать за них будут только те, кому человек действительно принес пользу, это позволит защититься от накруток и махинаций.
Да ради бога)
Процедура генерации ключа на самом деле является просто очень усложненной перестановкой. Я сейчас проверил с учетом всех перестановок у меня получилось что 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] делает все выражение случайным.
Другими словами, существует ли зависимость между 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) также являются независимыми.
В комментарии вы складываете слева 2 бита, а в статье — 2 вектора
И в комментарии и в статье складывается 2 бита информации,
запись вида X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] описывает один бит, полученный сложением по модулю два нескольких разных бит.
Простите, моя вина. В пост вкралась ошибка. Вероятность конечно же равна не (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) не влияет никаким образом.
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
PS: вы правда считаете что перевод статьи господина Мацуи — туториал для чайников?
Да считаю что более подробного материала по теме просто нет. И почему сразу перевод?
Касательно невозможности расшифровать некоторые значения. Я даже не знаю с чего начать, стока прям всего интересного вы понаписали.:)
Во-первых сами же говорите:
Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)
а сами в качестве примера зачем то приводите 2, 4, 9, 111, которые вовсе не взаимно простые с 480. Естественно, это приводит к тому, что расшифровать сообщение невозможно, т.к. эти числа необратимы по модулю φ(n).
Теперь что касается самих шифруемых чисел 187, 341, 154 и 373. Тут от модуля конечно же ничего не зависит. При любом выбранном модуле будут наблюдаться числа, которые при шифровании будут равны сами себе. Об этом можно в 9 главе Handbook of Applied Cryptography почитать.
А вот если мы говорим о числа 187 и 341 то тут на самом деле проблема похлеще существует, чем та которую вы описали. Эти числа имеют общий делитель с числом N. Соответственно вычислив НОД(m, N) для таких сообщений атакующий сразу может вскрыть секретный ключ. Поэтому не стоит особо расстраиваться, что RSA не умеет шифровать такие числа, считайте это фичей.:)
Вы правы. При описанной схеме, эти действия лишены всякого смысла. Я немного изменил пример, добавив дополнительный раунд. Теперь описанная атака будет работать корректно.
Спасибо за замечание такого досадного ляпа.
«Трое в лодке не считая собаки» Джером К. Джером — классика в представлении не нуждающаяся. Читал в детстве, рыдая от счастья.
«Записки сельского ветеринара» Джеймс Хэрриот — собственно название намекает о чем книга. Автор настоящий профессионал, любящий свою работу и умеющий очень смешно о ней рассказать.
«Моя семья и другие звери» Джеральд Даррел — забавная книга о детстве, животных и вообще.
«Я умею прыгать через лужи» Алан Маршалл — в этой книге не так много по настоящему смешных моментов, но она передает уникальное жизнелюбие автора и это подкупает.
Понимаю что на вкус и цвет фломастеры разные, но это одна из любимейших моих книг, которую советую всем без разбора. В ней хорошо на мой взгляд все и интересный сюжет и технические подробности и вообще криптография! Ну как можно не любить криптографию:) Поэтому хотелось бы понять что с ней не так, чтобы меня при случае не пинали за плохой совет тем кому книга тоже покажется отвратительной вещью:)
Использование каскадов РСЛОС, как например в сетях GSM, тоже весьма небезопасное решение.
RC4 тоже имеет свои недостатки, позволяющие при наличие большого объема известных пар открытый-закрытый текстов восстановить секретную информацию, скажем куки.
Механизмы атаки зависят от используемого ГПСЧ, но в общем случае почти всегда сводятся к атаке с известным открытым текстом или используют неправильную реализацию(к примеру, шифрование одним и тем же ключевым потоком двух и более сообщений).
Разумеется, AES выглядит куда более предпочтительным решением. Но ситуации бывают всякие и поэтому я и написал в своем комментарии: «в случае крайней нужды».
С учетом последнего обновления получается, что отблагодарить таких людей в карму больше не получится, по крайней мере тех, которые предпочитают не писать своих постов (назовем таких людей «комментаторами»).
У меня есть одно предложение. deniskin, а можно ли оставить возможность голосовать за карму таким людям(имею в виду тем у кого нет ни одного поста), но при этом, чтобы у голосующего карма уменьшалась на один пункт? Таким образом, с одной стороны у «комментаторов» останется возможность заработать положительную карму, но т.к. голосовать за них будут только те, кому человек действительно принес пользу, это позволит защититься от накруток и махинаций.
Да ради бога)
Процедура генерации ключа на самом деле является просто очень усложненной перестановкой. Я сейчас проверил с учетом всех перестановок у меня получилось что 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] делает все выражение случайным.
Дело в том, что нам не нужно демонстрировать отсутствие зависимости между 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) также являются независимыми.
И в комментарии и в статье складывается 2 бита информации,
запись вида X(2)[3] ⊕ X(2)[8] ⊕ X(2)[14] ⊕ X(2)[25] описывает один бит, полученный сложением по модулю два нескольких разных бит.
Давайте попробуем вместе разобраться откуда взялась такая цифра.
Имеем с одной стороны уравнение:
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) не влияет никаким образом.
Что касается вашего вопроса о вероятности 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
Да считаю что более подробного материала по теме просто нет. И почему сразу перевод?
Во-первых сами же говорите: а сами в качестве примера зачем то приводите 2, 4, 9, 111, которые вовсе не взаимно простые с 480. Естественно, это приводит к тому, что расшифровать сообщение невозможно, т.к. эти числа необратимы по модулю φ(n).
Теперь что касается самих шифруемых чисел 187, 341, 154 и 373. Тут от модуля конечно же ничего не зависит. При любом выбранном модуле будут наблюдаться числа, которые при шифровании будут равны сами себе. Об этом можно в 9 главе Handbook of Applied Cryptography почитать.
А вот если мы говорим о числа 187 и 341 то тут на самом деле проблема похлеще существует, чем та которую вы описали. Эти числа имеют общий делитель с числом N. Соответственно вычислив НОД(m, N) для таких сообщений атакующий сразу может вскрыть секретный ключ. Поэтому не стоит особо расстраиваться, что RSA не умеет шифровать такие числа, считайте это фичей.:)
Спасибо за замечание такого досадного ляпа.
Но в следующий раз пишите все таки в личку:)