Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 45
Интересный и несложный алгоритм. Спасибо.
P.S. Переместите в блог «Алгоритмы».
P.S. Переместите в блог «Алгоритмы».
Мы в свое время в институте тоже разрабатывали в качестве курсовой работы несложные алгоритмы наподобие DES — предмет назывался«Основы криптографии» или как-то так.
Кстати не так давно разбирался с RSA и Rijndael — но исключительно как пользователсь уже готовых классов .NET Framework. Просто понадобилось в процессе подготовки к сдаче проекта защитить все конфигурационные файлы от просмотра и модификации. Как выяснилось это все достаточно несложно — за один день разобрался и написал. Если нужно — могу написать об этом статью.
Кстати не так давно разбирался с RSA и Rijndael — но исключительно как пользователсь уже готовых классов .NET Framework. Просто понадобилось в процессе подготовки к сдаче проекта защитить все конфигурационные файлы от просмотра и модификации. Как выяснилось это все достаточно несложно — за один день разобрался и написал. Если нужно — могу написать об этом статью.
Мне было бы интересно про RSA почитать. С этим алгоритмом я ещё не разбирался.
В RSA матчасть повеселее, вам понравится.
RSA намного проще, главное вспомнить малую теорему Ферма.
Вообще не припомню не одного сверх-сложного криптографического алгоритма. Когда все подробно распишут — на первый взгляд просто. Но попробуйте придумать что-то аналогичное... Сразу поймете что не так все просто, как кажется на первый взгляд. Даже оценить криптостойкость алгоритма — уже мало кто сможет.
Вообще не припомню не одного сверх-сложного криптографического алгоритма. Когда все подробно распишут — на первый взгляд просто. Но попробуйте придумать что-то аналогичное... Сразу поймете что не так все просто, как кажется на первый взгляд. Даже оценить криптостойкость алгоритма — уже мало кто сможет.
Да, RSA — он хитрый местами. Бывает, что и не сразу поймешь/вспомнишь как оно работает.
Тоже вот недавно столкнулся с его применением при помощи wincrypt. Там, правда, не успел все реализовать за один день, так разбирался в том, как же все таки работает это виндовая библиотека, скрывая от пользователя все, что можно и нельзя.
Тоже вот недавно столкнулся с его применением при помощи wincrypt. Там, правда, не успел все реализовать за один день, так разбирался в том, как же все таки работает это виндовая библиотека, скрывая от пользователя все, что можно и нельзя.
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…
>>вычисляется 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 продолжает корректно работать.
Дак он для того и добавляется, чтобы его перебором проще целое D найти. :)
Нет. Вы 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 народ то и не знает — минусы ставит.
Из асимметричной криптографии ElGamal в несколько раз проще и доступнее для понимания чем RSA.
Во-первых, ElGamal основан на математической неразрешимости только одной задачи, а не двух как RSA.
Во-вторых, математика генерации ключа гораздо проще, а операция из «длинной арифметики» вообще всего одна — возведение в степень по длинному модулю.
Во-первых, ElGamal основан на математической неразрешимости только одной задачи, а не двух как RSA.
Во-вторых, математика генерации ключа гораздо проще, а операция из «длинной арифметики» вообще всего одна — возведение в степень по длинному модулю.
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 операции.
Посмотрите, ниже отписал про g. Он примитивен до тех пор, пока не вдаешься в детали… Дьявол в деталях.
Большое спасибо за пост. Неплохо разбираться в алгоритмах шифрования, особенно когда временами нужно шифровать «на лету» исполняемые файлы.
Хорошая статья. Спасибо. Интересно было читать.
Спасибо за статью!
Однако, теперь вам нужно писать следующую. Сказали А — говорите и Б ;)
Всё-таки вы чересчур упростили проблему. На алгоритм в том виде, как вы описали (а именно, режим ECB), возможны разнообразные атаки. Например: тот факт, что блоки у вас не зависят друг от друга, означает, что два одинаковых блока в результате дадут одинаковый шифртекст. И значит, по шифртексту мы можем знать, что в исходном тексте были одинаковые блоки, и какие это блоки. Зная, что расстояния между ними кратны 128-битам, можно даже делать предположения о том, что там за данные зашифрованы. Если зашифровать картинку высокого разрешения, например, есть вероятность, что вы вообще не защитите информацию никак (форму объектов, хотя и несколько огрубленную, можно будет видеть даже непосредственно по шифртексту!).
Это не единственная атака, которая тут возможна, я не буду описывать их все. Именно для защиты от подобных атак и используются всякие усложения, типа режимов шифрования блочных шифров.
Так вот, пишите теперь про векторы инициализации и более продвинутые режимы CBC, XCB, OFB и прочие. Развивайте тему ;)
Однако, теперь вам нужно писать следующую. Сказали А — говорите и Б ;)
Всё-таки вы чересчур упростили проблему. На алгоритм в том виде, как вы описали (а именно, режим ECB), возможны разнообразные атаки. Например: тот факт, что блоки у вас не зависят друг от друга, означает, что два одинаковых блока в результате дадут одинаковый шифртекст. И значит, по шифртексту мы можем знать, что в исходном тексте были одинаковые блоки, и какие это блоки. Зная, что расстояния между ними кратны 128-битам, можно даже делать предположения о том, что там за данные зашифрованы. Если зашифровать картинку высокого разрешения, например, есть вероятность, что вы вообще не защитите информацию никак (форму объектов, хотя и несколько огрубленную, можно будет видеть даже непосредственно по шифртексту!).
Это не единственная атака, которая тут возможна, я не буду описывать их все. Именно для защиты от подобных атак и используются всякие усложения, типа режимов шифрования блочных шифров.
Так вот, пишите теперь про векторы инициализации и более продвинутые режимы CBC, XCB, OFB и прочие. Развивайте тему ;)
Кто-то из нас чего-то недопонял. А разве расписание ключей и процесс его получения не решают именно эту задачу?
Точное замечание :) Как применять AES это тема отдельной статьи. Когда я писал эту статью, то посмотрел на неё и прикинул сколько нужно будет крутить колесико мышки, чтобы прочитать всё и выкинул половину текста.
Я запланировал написать ещё пару-тройку статей. После них возьмусь за продолжение темы AES. Если смогу написать компактно, добавлю пример как MS Excel шифрует бинарные xls файлы.
Я запланировал написать ещё пару-тройку статей. После них возьмусь за продолжение темы AES. Если смогу написать компактно, добавлю пример как MS Excel шифрует бинарные xls файлы.
Был тут пост про AES, кто пропустил — вот наглядная флешка.
www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
На мой взгляд, AES шикарен не тем, что он прост, а тем, что он изначально оптимизирован под современные 8-битные архитектуры
ну, звиняйте. msm эт только частный случай. я и под mips'ы уже пишу (и зачем я роутер блин купил), и под ppc.
про армы вообще молчу ))
про армы вообще молчу ))
Спасибо! Для общего развития почитать не помешает.
осознал свою матем. неграмотность. ну не показался мне алгоритм простым(
Если не влезать в алгебру, то особо сложного тут нет.
Но вообще понять, как работает финитное поле, стоит. Оно не только в шифровании используется. Другое характерное применение этого же поля — это алгоритм, на котором основана устойчивость RAID6.
Но вообще понять, как работает финитное поле, стоит. Оно не только в шифровании используется. Другое характерное применение этого же поля — это алгоритм, на котором основана устойчивость RAID6.
Только он, все-таки, Rijndael
Спасибо за статью. Правда не математику тяжело продвинуться дальше
> У сложения есть простые свойства:
> 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 не равны нулю?
Бинарное же поле.
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
Точнее правильнее назвать не «бинарное», а по модулю 2
Спасибо.
Вот только смысла в таком свойстве немного. a — b == a + (-b) == 0. Для любого поля. А в бинарном это утверждение еще и очень легко проверить. Да и вообще с описанием поля автор налажал. Технически операции показаны верно, но вот понять что такое поле из этого материала невозможно.
спасибо за статью.
Как уже было отмечено, кроме простейшего режима шифрования ECB, есть другие, более безопасные режимы, которые меньше поддаются анализу — CBC, OFB, CFB, CTR.
Как уже было отмечено, кроме простейшего режима шифрования ECB, есть другие, более безопасные режимы, которые меньше поддаются анализу — CBC, OFB, CFB, CTR.
Для шифрования сообщений любым шифром знать его устройство не обязательно (действуй по инструкции), а вот взламывать шифр, не зная как он устроен и работает, — невозможно (инструкции -то нет). Не владея алгеброй (высшей) понять ничего нельзя из статьи. Правда у автора есть оправдание — конец рабочего дня. Но причем здесь читатель?
>Почему выбран именно такой m? У этого многочлена есть только два делителя-многочлена на >которых он делится без остатка: единица и он сам.
Как Вы это объясняете?
Над каким полем Вами выполняется деление? Основная теорема алгебры говорит о чем?
Что Вы нагородили, вводите людей в заблуждение или возможно сами не понимаете?
Как Вы это объясняете?
Над каким полем Вами выполняется деление? Основная теорема алгебры говорит о чем?
Что Вы нагородили, вводите людей в заблуждение или возможно сами не понимаете?
>Поле GF(2^8) это числа 0..255 для которых определили особое умножение и особое сложение.
Это не числовое поле, а поле расширения, поле многочленов и манипуляции с его элементами требуют сравнения по двойному модулю. У Вас ничего этого не показано.
Это не числовое поле, а поле расширения, поле многочленов и манипуляции с его элементами требуют сравнения по двойному модулю. У Вас ничего этого не показано.
Отличная статья. От себя добавлю для тех, кто как я, не сразу разобрался с S-box алгоритмом. Для постороения нового байта надо из матрицы взять тот элемент, номер которого равен первоначальному байту.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как устроен AES