Comments 23
Хранить такую информацию в открытом виде паранойя не позволяет, использовать сторонние сервисы тоже, поэтому после некоторых поисков остановился на стандарте AES.Могу порекомендовать вот это или аналог — отличная штука для таких дел.
Сразу захотелось разобраться и реализовать алгоритм самому, не прибегая к дополнительным модулям.Надеюсь, это только в образовательных целях? Обычно самодельные реализации криптоалгоритмов для практического применения не очень рекомендуется :)
Нашел это по одной из ссылок из статьи :)
Ну, внедрять это куда-то я и не планировал. Зато радость, когда все корректно заработало, была себе доставлена) ибо мат часть заработала не сразу. И конечно же самообразование, без него никуда)
Все правильно сделали :)
Посмотрите на www.matasano.com/articles/crypto-challenges/, там дают задания, постепенно выполняя которые вы научитесь реализовывать различные алгоритмы, и их же ломать. Задания не особо сложные, там есть небольшие подсказки, время выполнения/язык не ограничен. Если для самообразования — самое то.
UFO just landed and posted this here
В общем, пакуем все это дело наглухо в пластик, остекловываем и закапываем на глубине 20метров© DiHalt
Тож в свое время реализовывал AES128: ваял драйвер hdd диска под винду с шифрованием. Но тоже дальше образовательных целей не пошло.
Вообще, делать что-то этакое, как по мне, — хорошая разминка для мозга :)
Вообще, делать что-то этакое, как по мне, — хорошая разминка для мозга :)
Не увидел кода для умножения полиномов, хотя это самое интересное в реализации данного примитива шифрования. Сам еще год назад реализовывал AES на C# для лабораторной, а потом переписывал на С и на Python для курсеровской криптографии (естественно, ECB, тогда еще была только первая или вторая неделя). Сначала использовал gmul отсюда, потом вообще перешел на precomputed tables, как это сделано в OpenSSL.
Да, это хорошая разминка для мозга, но можно довести это и дальше, до authenticated encryption. Или попробовать реализовать теперь уже поточный шифр, например, Salsa20. И так, как у вас есть примитив AES, то написать еще и имитовставку (MAC) Poly1305-AES — и получится криптокоробочка из NaCl.
Да, это хорошая разминка для мозга, но можно довести это и дальше, до authenticated encryption. Или попробовать реализовать теперь уже поточный шифр, например, Salsa20. И так, как у вас есть примитив AES, то написать еще и имитовставку (MAC) Poly1305-AES — и получится криптокоробочка из NaCl.
Пожалуй, это действительно нужно приложить к статье. Универсального умножения я не писал, только на константы из алгоритма. Специально оставил закомменченные варианты вычислений, ибо они понятнее, изящнее, но почему-то работают неправильно. Может кто подскажет почему?
Умножение в поле Галуа
def mul_by_02(num):
if num < 0x80:
res = (num << 1)
else:
res = (num << 1)^0x1b
return res % 0x100
def mul_by_03(num):
return mul_by_02(num)^num
def mul_by_09(num):
#return mul_by_03(num)^mul_by_03(num)^mul_by_03(num) - works wrong, I don't know why
return mul_by_02(mul_by_02(mul_by_02(num)))^num
def mul_by_0b(num):
#return mul_by_09(num)^mul_by_02(num)
return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(num)^num
def mul_by_0d(num):
#return mul_by_0b(num)^mul_by_02(num)
return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^num
def mul_by_0e(num):
#return mul_by_0d(num)^num
return mul_by_02(mul_by_02(mul_by_02(num)))^mul_by_02(mul_by_02(num))^mul_by_02(num)
Почему умножение на {02} выполняется так странно? Умножение на 2 — это умножение на полином 1*x**1+0*x**0 (2_dec=10_bin), то есть это циклический сдвиг влево и всё:
(b7*x**7+b6*x**6+b5*x**5+b4*x**4+b3*x**3+b2*x**2+b1*x**1+b0*x**0)*x = (b6*x**7+b5*x**6+b4*x**5+b3*x**4+b2*x**3+b1*x**2+b0*x**1+b7*x**0).
Откуда там взялось XOR с 1b?..
Умножение на {03} (попросту на тройку) — это умножение на полином (x+1), что даст
((b6+b7)*x**7+(b5+b6)*x**6+(b4+b5)*x**5+(b3+b4)*x**4+(b2+b3)*x**3+(b1+b2)*x**2+(b0+b1)*x**1+(b7+b0)*x**0).
Коэффициенты — биты, поэтому 1+1=0, 0+1=1+0=1, 0+0=0.
Всё просто.
Если они используют модуль x**4+1 с допустимыми коэффициентами {0,1}, то это означает, что x**4 можно заменить на 1, x**5 — на x и так далее x**n на x**(n-4m).
(b7*x**7+b6*x**6+b5*x**5+b4*x**4+b3*x**3+b2*x**2+b1*x**1+b0*x**0)*x = (b6*x**7+b5*x**6+b4*x**5+b3*x**4+b2*x**3+b1*x**2+b0*x**1+b7*x**0).
Откуда там взялось XOR с 1b?..
Умножение на {03} (попросту на тройку) — это умножение на полином (x+1), что даст
((b6+b7)*x**7+(b5+b6)*x**6+(b4+b5)*x**5+(b3+b4)*x**4+(b2+b3)*x**3+(b1+b2)*x**2+(b0+b1)*x**1+(b7+b0)*x**0).
Коэффициенты — биты, поэтому 1+1=0, 0+1=1+0=1, 0+0=0.
Всё просто.
Если они используют модуль x**4+1 с допустимыми коэффициентами {0,1}, то это означает, что x**4 можно заменить на 1, x**5 — на x и так далее x**n на x**(n-4m).
Опровергать вашу теорию не буду, может я и допустил где-то ошибки. Дело было давно, но точно помню, что критерием правильности функций умножения для меня было совпадение их результатов с таблицами в конце этой статьи. В качестве исходных данных брался массив чисел [0..255]. Точно помню, что этот тест мои функции прошли, иначе бы статью здесь я не опубликовал
Так тогда понятно про 0x1b… Кто бы знал про полином
x^8 + x^4 + x^3 + x + 1
из Вашей ссылки… Просто происходит замена x^8 на x^4+x^3+x+1, а это и есть 00011011=0x1b.
Тогда я был частично неправ. Но матрицу 4x4 я проверил — она совпала, но там при умножении полиномов x^4 заменялась на 1, так как там модуль x^4+1 = 0.
x^8 + x^4 + x^3 + x + 1
из Вашей ссылки… Просто происходит замена x^8 на x^4+x^3+x+1, а это и есть 00011011=0x1b.
Тогда я был частично неправ. Но матрицу 4x4 я проверил — она совпала, но там при умножении полиномов x^4 заменялась на 1, так как там модуль x^4+1 = 0.
Мне кажется, что сработает вариант
если num — один байт.
def mul2(num):
return ((num<<1)^(num>>7))
если num — один байт.
Не работает, потому что нельзя раскладывать 9 на сумму 3+3+3, так как в двоичном коде число 9=00001001, а число 3=00000011.
Сумма трёх троек даст опять тройку, так как 11+11+11 = 00+11=11. Ну, или полиномами: x+1+x+1+x+1=x+1 (коэффициенты складываются по модулю два, то есть 3x=(3-2)x=x).
Девятка — это полином x^3+1, а x^3 — это три раза умножить на x, то есть на 2=00000010=>1*x^1+0*x^0, поэтому
n*9=mul2(mul2(mul2(n))) XOR n. Число n — это полином степени 7 с коэффициентами {0,1} (один байт).
Сумма трёх троек даст опять тройку, так как 11+11+11 = 00+11=11. Ну, или полиномами: x+1+x+1+x+1=x+1 (коэффициенты складываются по модулю два, то есть 3x=(3-2)x=x).
Девятка — это полином x^3+1, а x^3 — это три раза умножить на x, то есть на 2=00000010=>1*x^1+0*x^0, поэтому
n*9=mul2(mul2(mul2(n))) XOR n. Число n — это полином степени 7 с коэффициентами {0,1} (один байт).
>Число n — это полином степени 7 с коэффициентами {0,1} (один байт)
Это разные вещи, элемент расширенного поля — многочлен, а числа в нем только 0 и 1.
Это разные вещи, элемент расширенного поля — многочлен, а числа в нем только 0 и 1.
>Пожалуй, это действительно нужно приложить к статье. Универсального умножения я не писал, только на константы из алгоритма. Специально оставил закомменченные варианты вычислений, ибо они понятнее, изящнее, но почему-то работают неправильно. Может кто подскажет почему?
Умножение в поле Галуа
Не работает и не будет работать, потому что поле не построено, потому, что строить его не умеем и учиться этому не хотим. Претензии в названии поста никак и ничем не обоснованы. Писать можно и следует о том в чем хорошо разбираетесь, лучше многих других. А так только позориться перед людьми. О деталях AES — 128 вообще нет ни слова. Детали — это не общие поверхностные рассуждения, а углубленные, не проявляющиеся на поверхности явления.
Умножение в поле Галуа
Не работает и не будет работать, потому что поле не построено, потому, что строить его не умеем и учиться этому не хотим. Претензии в названии поста никак и ничем не обоснованы. Писать можно и следует о том в чем хорошо разбираетесь, лучше многих других. А так только позориться перед людьми. О деталях AES — 128 вообще нет ни слова. Детали — это не общие поверхностные рассуждения, а углубленные, не проявляющиеся на поверхности явления.
Sign up to leave a comment.
AES-128. Детали и реализация на python