Comments 44
Интересный и несложный алгоритм. Спасибо.

P.S. Переместите в блог «Алгоритмы».
По поводу «несложный» отписал ниже. Попробуйте придумать свой уникальный и криптостойкий алгоритм шифрования, пуст даже простой. Поймете, что не все так просто как кажется на первый взгляд.
Мы в свое время в институте тоже разрабатывали в качестве курсовой работы несложные алгоритмы наподобие DES — предмет назывался«Основы криптографии» или как-то так.

Кстати не так давно разбирался с RSA и Rijndael — но исключительно как пользователсь уже готовых классов .NET Framework. Просто понадобилось в процессе подготовки к сдаче проекта защитить все конфигурационные файлы от просмотра и модификации. Как выяснилось это все достаточно несложно — за один день разобрался и написал. Если нужно — могу написать об этом статью.
Мне было бы интересно про RSA почитать. С этим алгоритмом я ещё не разбирался.
RSA намного проще, главное вспомнить малую теорему Ферма.

Вообще не припомню не одного сверх-сложного криптографического алгоритма. Когда все подробно распишут — на первый взгляд просто. Но попробуйте придумать что-то аналогичное... Сразу поймете что не так все просто, как кажется на первый взгляд. Даже оценить криптостойкость алгоритма — уже мало кто сможет.
Да, RSA — он хитрый местами. Бывает, что и не сразу поймешь/вспомнишь как оно работает.
Тоже вот недавно столкнулся с его применением при помощи 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…

>>вычисляется D по формуле (E*D) % ((p-1)*(q-1)) = 1

Кстати, 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 народ то и не знает — минусы ставит.
Угу, посмотрел внимательнее, да. Даже использовал уже это когда генерацию ключей свою делал…
Из асимметричной криптографии ElGamal в несколько раз проще и доступнее для понимания чем RSA.

Во-первых, ElGamal основан на математической неразрешимости только одной задачи, а не двух как RSA.
Во-вторых, математика генерации ключа гораздо проще, а операция из «длинной арифметики» вообще всего одна — возведение в степень по длинному модулю.
Посмотрите, ниже отписал про g. Он примитивен до тех пор, пока не вдаешься в детали… Дьявол в деталях.
Большое спасибо за пост. Неплохо разбираться в алгоритмах шифрования, особенно когда временами нужно шифровать «на лету» исполняемые файлы.
Спасибо за статью!

Однако, теперь вам нужно писать следующую. Сказали А — говорите и Б ;)
Всё-таки вы чересчур упростили проблему. На алгоритм в том виде, как вы описали (а именно, режим ECB), возможны разнообразные атаки. Например: тот факт, что блоки у вас не зависят друг от друга, означает, что два одинаковых блока в результате дадут одинаковый шифртекст. И значит, по шифртексту мы можем знать, что в исходном тексте были одинаковые блоки, и какие это блоки. Зная, что расстояния между ними кратны 128-битам, можно даже делать предположения о том, что там за данные зашифрованы. Если зашифровать картинку высокого разрешения, например, есть вероятность, что вы вообще не защитите информацию никак (форму объектов, хотя и несколько огрубленную, можно будет видеть даже непосредственно по шифртексту!).

Это не единственная атака, которая тут возможна, я не буду описывать их все. Именно для защиты от подобных атак и используются всякие усложения, типа режимов шифрования блочных шифров.

Так вот, пишите теперь про векторы инициализации и более продвинутые режимы CBC, XCB, OFB и прочие. Развивайте тему ;)
Кто-то из нас чего-то недопонял. А разве расписание ключей и процесс его получения не решают именно эту задачу?
Не эту.

Расписание ключей — это какой ключ применять на каком раунде шифрования данного блока. Однако, для всех раундов разных блоков будет применено одно и то же расписание.
Точное замечание :) Как применять AES это тема отдельной статьи. Когда я писал эту статью, то посмотрел на неё и прикинул сколько нужно будет крутить колесико мышки, чтобы прочитать всё и выкинул половину текста.

Я запланировал написать ещё пару-тройку статей. После них возьмусь за продолжение темы AES. Если смогу написать компактно, добавлю пример как MS Excel шифрует бинарные xls файлы.
Был тут пост про AES, кто пропустил — вот наглядная флешка.
www.cs.bc.edu/~straubin/cs381-05/blockciphers/rijndael_ingles2004.swf
На мой взгляд, AES шикарен не тем, что он прост, а тем, что он изначально оптимизирован под современные 8-битные архитектуры
8-битные? а такие остались еще? :)
я немного ембеддедом занимаюсь, и все с чем работал уже давно 32битное…
а чего же не 31-битное? Как была кратность 8 бит, так и осталась. Как были команды доступа к байтам и словам, так и остались.
ну, звиняйте. msm эт только частный случай. я и под mips'ы уже пишу (и зачем я роутер блин купил), и под ppc.
про армы вообще молчу ))

осознал свою матем. неграмотность. ну не показался мне алгоритм простым(
Если не влезать в алгебру, то особо сложного тут нет.

Но вообще понять, как работает финитное поле, стоит. Оно не только в шифровании используется. Другое характерное применение этого же поля — это алгоритм, на котором основана устойчивость RAID6.
Спасибо за статью. Правда не математику тяжело продвинуться дальше

> У сложения есть простые свойства:
> 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 == a + (-b) == 0. Для любого поля. А в бинарном это утверждение еще и очень легко проверить. Да и вообще с описанием поля автор налажал. Технически операции показаны верно, но вот понять что такое поле из этого материала невозможно.
Так,… извиняюсь. Конец рабочего дня и с операцией я все перепутал. Все верно было в комментариях выше.
Вообще не ясно о каком поле (какой примитивный элемент использован при его построении) идет речь, как оно задано?
спасибо за статью.

Как уже было отмечено, кроме простейшего режима шифрования ECB, есть другие, более безопасные режимы, которые меньше поддаются анализу — CBC, OFB, CFB, CTR.
Для шифрования сообщений любым шифром знать его устройство не обязательно (действуй по инструкции), а вот взламывать шифр, не зная как он устроен и работает, — невозможно (инструкции -то нет). Не владея алгеброй (высшей) понять ничего нельзя из статьи. Правда у автора есть оправдание — конец рабочего дня. Но причем здесь читатель?
>Почему выбран именно такой m? У этого многочлена есть только два делителя-многочлена на >которых он делится без остатка: единица и он сам.
Как Вы это объясняете?
Над каким полем Вами выполняется деление? Основная теорема алгебры говорит о чем?
Что Вы нагородили, вводите людей в заблуждение или возможно сами не понимаете?
>Поле GF(2^8) это числа 0..255 для которых определили особое умножение и особое сложение.
Это не числовое поле, а поле расширения, поле многочленов и манипуляции с его элементами требуют сравнения по двойному модулю. У Вас ничего этого не показано.
Only those users with full accounts are able to leave comments. Log in, please.