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

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

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

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

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

Кстати, d может так-же вычисляться по такой формуле

(e*d*g) % ((p-1)*(q-1)) = g

Т.е. добавляется параметр g (обычно менее 10). При таком d RSA продолжает корректно работать.
+1
Дак он для того и добавляется, чтобы его перебором проще целое D найти. :)
+4
Нет. Вы 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 народ то и не знает — минусы ставит.
0
Угу, посмотрел внимательнее, да. Даже использовал уже это когда генерацию ключей свою делал…
+1
Из асимметричной криптографии ElGamal в несколько раз проще и доступнее для понимания чем RSA.

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

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

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

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

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

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

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

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

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

Как уже было отмечено, кроме простейшего режима шифрования ECB, есть другие, более безопасные режимы, которые меньше поддаются анализу — CBC, OFB, CFB, CTR.
Only those users with full accounts are able to leave comments., please.