Комментарии 45
Интересный и несложный алгоритм. Спасибо.
P.S. Переместите в блог «Алгоритмы».
P.S. Переместите в блог «Алгоритмы».
0
Мы в свое время в институте тоже разрабатывали в качестве курсовой работы несложные алгоритмы наподобие DES — предмет назывался«Основы криптографии» или как-то так.
Кстати не так давно разбирался с RSA и Rijndael — но исключительно как пользователсь уже готовых классов .NET Framework. Просто понадобилось в процессе подготовки к сдаче проекта защитить все конфигурационные файлы от просмотра и модификации. Как выяснилось это все достаточно несложно — за один день разобрался и написал. Если нужно — могу написать об этом статью.
Кстати не так давно разбирался с RSA и Rijndael — но исключительно как пользователсь уже готовых классов .NET Framework. Просто понадобилось в процессе подготовки к сдаче проекта защитить все конфигурационные файлы от просмотра и модификации. Как выяснилось это все достаточно несложно — за один день разобрался и написал. Если нужно — могу написать об этом статью.
+1
Мне было бы интересно про RSA почитать. С этим алгоритмом я ещё не разбирался.
+2
В RSA матчасть повеселее, вам понравится.
0
RSA намного проще, главное вспомнить малую теорему Ферма.
Вообще не припомню не одного сверх-сложного криптографического алгоритма. Когда все подробно распишут — на первый взгляд просто. Но попробуйте придумать что-то аналогичное... Сразу поймете что не так все просто, как кажется на первый взгляд. Даже оценить криптостойкость алгоритма — уже мало кто сможет.
Вообще не припомню не одного сверх-сложного криптографического алгоритма. Когда все подробно распишут — на первый взгляд просто. Но попробуйте придумать что-то аналогичное... Сразу поймете что не так все просто, как кажется на первый взгляд. Даже оценить криптостойкость алгоритма — уже мало кто сможет.
+2
Да, RSA — он хитрый местами. Бывает, что и не сразу поймешь/вспомнишь как оно работает.
Тоже вот недавно столкнулся с его применением при помощи wincrypt. Там, правда, не успел все реализовать за один день, так разбирался в том, как же все таки работает это виндовая библиотека, скрывая от пользователя все, что можно и нельзя.
Тоже вот недавно столкнулся с его применением при помощи wincrypt. Там, правда, не успел все реализовать за один день, так разбирался в том, как же все таки работает это виндовая библиотека, скрывая от пользователя все, что можно и нельзя.
-1
RSA вообще примитивен :)
там всего несколько простейших формул, и арифметика достаточно простая
для справки опишу:
основной ключ, принято называть N, modulus, модуль — является произведением 2х больших (длиной в половину от желаемого размера ключа) простых чисел p и q:
N = p * q
этот N является общей частью и публичного и приватного ключей
далее вычисляется вторая часть приватного ключа (D, экспонента приватного ключа) — вычисляетя значение (p-1)*(q-1) и выбирается значение E, по принципу 1<E<(p-1)*(q-1)
обычно для E берут число 65537, оно будет публичной экспонентой, второй частью открытого ключа.
ну и наконец вычисляется D по формуле (E*D) % ((p-1)*(q-1)) = 1, в качестве D подходит любое целочисленное решение данного уравнения.
таким образом, получаются 2 ключа: E,N — публичный и D,N — приватный.
сам алгоритм шифрования еще проще.
сообщение M (длиной не более N) шифруется по формуле
C = M^E % N (зашифрованное сообщение C = остатку от деления на N сообщения M в степени E)
расшифровывается по формуле M = C^D % N
т.е. зашифровать сообщение может любой, обладающий открытым ключем, а прочитать — только владелец приватного ключа.
так-же пара ключей может быть использована для «цифрововой подписи»:
пдопись S = M^D % N, проверка M = S ^ E % N
т.е. создать «подписть» сообщения может только автор, а расшифровать и проверить — любой обладающий открытым ключем.
вот и весь RSA…
там всего несколько простейших формул, и арифметика достаточно простая
для справки опишу:
основной ключ, принято называть N, modulus, модуль — является произведением 2х больших (длиной в половину от желаемого размера ключа) простых чисел p и q:
N = p * q
этот N является общей частью и публичного и приватного ключей
далее вычисляется вторая часть приватного ключа (D, экспонента приватного ключа) — вычисляетя значение (p-1)*(q-1) и выбирается значение E, по принципу 1<E<(p-1)*(q-1)
обычно для E берут число 65537, оно будет публичной экспонентой, второй частью открытого ключа.
ну и наконец вычисляется D по формуле (E*D) % ((p-1)*(q-1)) = 1, в качестве D подходит любое целочисленное решение данного уравнения.
таким образом, получаются 2 ключа: E,N — публичный и D,N — приватный.
сам алгоритм шифрования еще проще.
сообщение M (длиной не более N) шифруется по формуле
C = M^E % N (зашифрованное сообщение C = остатку от деления на N сообщения M в степени E)
расшифровывается по формуле M = C^D % N
т.е. зашифровать сообщение может любой, обладающий открытым ключем, а прочитать — только владелец приватного ключа.
так-же пара ключей может быть использована для «цифрововой подписи»:
пдопись S = M^D % N, проверка M = S ^ E % N
т.е. создать «подписть» сообщения может только автор, а расшифровать и проверить — любой обладающий открытым ключем.
вот и весь RSA…
+4
>>вычисляется D по формуле (E*D) % ((p-1)*(q-1)) = 1
Кстати, d может так-же вычисляться по такой формуле
(e*d*g) % ((p-1)*(q-1)) = g
Т.е. добавляется параметр g (обычно менее 10). При таком d RSA продолжает корректно работать.
Кстати, d может так-же вычисляться по такой формуле
(e*d*g) % ((p-1)*(q-1)) = g
Т.е. добавляется параметр g (обычно менее 10). При таком d RSA продолжает корректно работать.
+1
Дак он для того и добавляется, чтобы его перебором проще целое D найти. :)
+1
Нет. Вы c k путаете.
Эту тонкость мало кто знает. Обычно g равен единице, но иногда (в некоторых реализациях) принимают другое значение. Я когда атаки Винера реализовывал — сначала облажался, т.к. не знал про это g и что оно может быть отличным от единицы.
Обычно формула такая:
d*e = 1 + k*f (f — функция эйлера от n, k — любое число, чтобы получилось целое d)
А в случае с добавлением g, она принимает вид:
d*e*g = g + k*f
Вот с таким добавлением g RSA все равно работает и на практике это g иногда добавляется (в частности, ключ WebMoney Keeper Classic его использует, а вот Windows CSP не использует).
Вы говорите просто — а оказывается не все так просто. Тонкостей, которые не описаны в wiki народ то и не знает — минусы ставит.
Эту тонкость мало кто знает. Обычно g равен единице, но иногда (в некоторых реализациях) принимают другое значение. Я когда атаки Винера реализовывал — сначала облажался, т.к. не знал про это g и что оно может быть отличным от единицы.
Обычно формула такая:
d*e = 1 + k*f (f — функция эйлера от n, k — любое число, чтобы получилось целое d)
А в случае с добавлением g, она принимает вид:
d*e*g = g + k*f
Вот с таким добавлением g RSA все равно работает и на практике это g иногда добавляется (в частности, ключ WebMoney Keeper Classic его использует, а вот Windows CSP не использует).
Вы говорите просто — а оказывается не все так просто. Тонкостей, которые не описаны в wiki народ то и не знает — минусы ставит.
+4
Из асимметричной криптографии ElGamal в несколько раз проще и доступнее для понимания чем RSA.
Во-первых, ElGamal основан на математической неразрешимости только одной задачи, а не двух как RSA.
Во-вторых, математика генерации ключа гораздо проще, а операция из «длинной арифметики» вообще всего одна — возведение в степень по длинному модулю.
Во-первых, ElGamal основан на математической неразрешимости только одной задачи, а не двух как RSA.
Во-вторых, математика генерации ключа гораздо проще, а операция из «длинной арифметики» вообще всего одна — возведение в степень по длинному модулю.
+1
P.S. Я имею в виду установку ключа по Эль-Гамалю (её еще называют схема «1/2 Диффи-Хеллмана»):
www.gnu.org/software/gnu-crypto/manual/api/gnu/crypto/key/dh/ElGamalKeyAgreement.html
Как видно по ссылке — всего 2 операции.
www.gnu.org/software/gnu-crypto/manual/api/gnu/crypto/key/dh/ElGamalKeyAgreement.html
Как видно по ссылке — всего 2 операции.
+1
Посмотрите, ниже отписал про g. Он примитивен до тех пор, пока не вдаешься в детали… Дьявол в деталях.
0
Большое спасибо за пост. Неплохо разбираться в алгоритмах шифрования, особенно когда временами нужно шифровать «на лету» исполняемые файлы.
-1
Хорошая статья. Спасибо. Интересно было читать.
-1
Спасибо за статью!
Однако, теперь вам нужно писать следующую. Сказали А — говорите и Б ;)
Всё-таки вы чересчур упростили проблему. На алгоритм в том виде, как вы описали (а именно, режим ECB), возможны разнообразные атаки. Например: тот факт, что блоки у вас не зависят друг от друга, означает, что два одинаковых блока в результате дадут одинаковый шифртекст. И значит, по шифртексту мы можем знать, что в исходном тексте были одинаковые блоки, и какие это блоки. Зная, что расстояния между ними кратны 128-битам, можно даже делать предположения о том, что там за данные зашифрованы. Если зашифровать картинку высокого разрешения, например, есть вероятность, что вы вообще не защитите информацию никак (форму объектов, хотя и несколько огрубленную, можно будет видеть даже непосредственно по шифртексту!).
Это не единственная атака, которая тут возможна, я не буду описывать их все. Именно для защиты от подобных атак и используются всякие усложения, типа режимов шифрования блочных шифров.
Так вот, пишите теперь про векторы инициализации и более продвинутые режимы CBC, XCB, OFB и прочие. Развивайте тему ;)
Однако, теперь вам нужно писать следующую. Сказали А — говорите и Б ;)
Всё-таки вы чересчур упростили проблему. На алгоритм в том виде, как вы описали (а именно, режим ECB), возможны разнообразные атаки. Например: тот факт, что блоки у вас не зависят друг от друга, означает, что два одинаковых блока в результате дадут одинаковый шифртекст. И значит, по шифртексту мы можем знать, что в исходном тексте были одинаковые блоки, и какие это блоки. Зная, что расстояния между ними кратны 128-битам, можно даже делать предположения о том, что там за данные зашифрованы. Если зашифровать картинку высокого разрешения, например, есть вероятность, что вы вообще не защитите информацию никак (форму объектов, хотя и несколько огрубленную, можно будет видеть даже непосредственно по шифртексту!).
Это не единственная атака, которая тут возможна, я не буду описывать их все. Именно для защиты от подобных атак и используются всякие усложения, типа режимов шифрования блочных шифров.
Так вот, пишите теперь про векторы инициализации и более продвинутые режимы CBC, XCB, OFB и прочие. Развивайте тему ;)
+11
Кто-то из нас чего-то недопонял. А разве расписание ключей и процесс его получения не решают именно эту задачу?
0
Точное замечание :) Как применять AES это тема отдельной статьи. Когда я писал эту статью, то посмотрел на неё и прикинул сколько нужно будет крутить колесико мышки, чтобы прочитать всё и выкинул половину текста.
Я запланировал написать ещё пару-тройку статей. После них возьмусь за продолжение темы AES. Если смогу написать компактно, добавлю пример как MS Excel шифрует бинарные xls файлы.
Я запланировал написать ещё пару-тройку статей. После них возьмусь за продолжение темы AES. Если смогу написать компактно, добавлю пример как MS Excel шифрует бинарные xls файлы.
+1
Был тут пост про AES, кто пропустил — вот наглядная флешка.
www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
+5
На мой взгляд, AES шикарен не тем, что он прост, а тем, что он изначально оптимизирован под современные 8-битные архитектуры
0
ну, звиняйте. msm эт только частный случай. я и под mips'ы уже пишу (и зачем я роутер блин купил), и под ppc.
про армы вообще молчу ))
про армы вообще молчу ))
0
Спасибо! Для общего развития почитать не помешает.
0
осознал свою матем. неграмотность. ну не показался мне алгоритм простым(
0
Если не влезать в алгебру, то особо сложного тут нет.
Но вообще понять, как работает финитное поле, стоит. Оно не только в шифровании используется. Другое характерное применение этого же поля — это алгоритм, на котором основана устойчивость RAID6.
Но вообще понять, как работает финитное поле, стоит. Оно не только в шифровании используется. Другое характерное применение этого же поля — это алгоритм, на котором основана устойчивость RAID6.
0
Только он, все-таки, Rijndael
+3
Спасибо за статью. Правда не математику тяжело продвинуться дальше
> У сложения есть простые свойства:
> a + a = 0
> -a = 0 — a = a
> a — b = a + (-b) = a + b
Как такое возможно если a и b не равны нулю?
> У сложения есть простые свойства:
> a + a = 0
> -a = 0 — a = a
> a — b = a + (-b) = a + b
Как такое возможно если a и b не равны нулю?
0
Бинарное же поле.
a, b in {0, 1}
1 + 1 == 0
=>
-1 == 1
-0 == 0 (очевидно)
=> -x == x
=> a — b == a + (-b) == a + b
a, b in {0, 1}
1 + 1 == 0
=>
-1 == 1
-0 == 0 (очевидно)
=> -x == x
=> a — b == a + (-b) == a + b
0
Спасибо.
0
Вот только смысла в таком свойстве немного. a — b == a + (-b) == 0. Для любого поля. А в бинарном это утверждение еще и очень легко проверить. Да и вообще с описанием поля автор налажал. Технически операции показаны верно, но вот понять что такое поле из этого материала невозможно.
0
спасибо за статью.
Как уже было отмечено, кроме простейшего режима шифрования ECB, есть другие, более безопасные режимы, которые меньше поддаются анализу — CBC, OFB, CFB, CTR.
Как уже было отмечено, кроме простейшего режима шифрования ECB, есть другие, более безопасные режимы, которые меньше поддаются анализу — CBC, OFB, CFB, CTR.
0
Для шифрования сообщений любым шифром знать его устройство не обязательно (действуй по инструкции), а вот взламывать шифр, не зная как он устроен и работает, — невозможно (инструкции -то нет). Не владея алгеброй (высшей) понять ничего нельзя из статьи. Правда у автора есть оправдание — конец рабочего дня. Но причем здесь читатель?
0
>Почему выбран именно такой m? У этого многочлена есть только два делителя-многочлена на >которых он делится без остатка: единица и он сам.
Как Вы это объясняете?
Над каким полем Вами выполняется деление? Основная теорема алгебры говорит о чем?
Что Вы нагородили, вводите людей в заблуждение или возможно сами не понимаете?
Как Вы это объясняете?
Над каким полем Вами выполняется деление? Основная теорема алгебры говорит о чем?
Что Вы нагородили, вводите людей в заблуждение или возможно сами не понимаете?
0
>Поле GF(2^8) это числа 0..255 для которых определили особое умножение и особое сложение.
Это не числовое поле, а поле расширения, поле многочленов и манипуляции с его элементами требуют сравнения по двойному модулю. У Вас ничего этого не показано.
Это не числовое поле, а поле расширения, поле многочленов и манипуляции с его элементами требуют сравнения по двойному модулю. У Вас ничего этого не показано.
0
Отличная статья. От себя добавлю для тех, кто как я, не сразу разобрался с S-box алгоритмом. Для постороения нового байта надо из матрицы взять тот элемент, номер которого равен первоначальному байту.
0
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.
Как устроен AES