Перейти к содержимому

Рекомендуемые сообщения

4 минуты назад, HeroBrine1st сказал:

1. В начало строки добавляется 4 случайных символа - соль
2. Строка делится на блоки по 4 символа, недостающие символы заполняются нулями

Ага, я, кажется, понял, в чём подвох. Деление на блоки происходит фиксированно, без учёта фактической длины N. А я без затей для тестирования шифрования строки выбрал фразу "TEST", как раз 4 символа. Поэтому она не дробилась. А солью с длиной 4 символа по умолчанию как раз получалось два блока.

11 минуту назад, HeroBrine1st сказал:

Разделить число на два.. вполне возможно

Не-не... я предлагаю не блок дробить на два, но адаптивно подбирать размер блока, чтобы его длина всегда была меньше размера N. Самое простое: если фактическая длина N требует для его кодирования 4 байта, то в шифруемый блок можно поместить не более 3 символов. При желании можно и точное количество бит посчитать, но в этом я уже не вижу большого смысла.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 минуты назад, eu_tomat сказал:

адаптивно подбирать размер блока, 

Однако для этого потребуется уведомлять другую сторону о том. что использована кастомная длина блока. Это, конечно. не проблема, но не проще ведь просто не использовать ключи менее 32 бит?
Тем более, что в библиотеке (вроде) уже есть ограничение на количество бит, а ключи менее 2048 бит являются криптонеустойчивыми

А в идеале нужно сделать шифрование в base64, но я пока не представляю, как это делается.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
27 минут назад, HeroBrine1st сказал:

Однако для этого потребуется уведомлять другую сторону о том. что использована кастомная длина блока.

Если алгоритм на обеих сторонах будет одинаковым, то уведомление не потребуется.

27 минут назад, HeroBrine1st сказал:

но не проще ведь просто не использовать ключи менее 32 бит?

Тут, во-первых, и ключ 32 бита не всегда помогает. А во-вторых, при длине ключа 256 бит шифровать блоки по 4 байта попросту неэффективно. Поэтому нужен адаптивный размер блока. А дальше либо подгонять размер блока под фактическую длину N, либо N формировать так, чтобы он был не меньше заданной длины.

 

Я обратил внимание, как генерирует ключи openssl. Во всех виденных мною ключах всегда есть отличное от нуля число если не в старшем разряде, то в следующем за ним. Разряды там в 16-ричной системе, и двумя разрядами кодируется байт. Получается, что старший байт всегда имеет значение больше нуля. Видимо, так сделано специально. Это позволит, например, при 32-битном ключе гарантированно шифровать блок из 3 байт. Или 15 байт при 128-битном. Возможно, я не видел нулевого старшего байта лишь в силу незначительного шанса на это. Но я запускал на десяток минут бесконечный цикл генерации ключа с фильтрацией по нулю в старшем байте. Всегда старший байт что в модуле, что в закрытой экспоненте имел ненулевое значение.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 минуты назад, eu_tomat сказал:

Возможно, я не видел нулевого старшего байта лишь в силу незначительного шанса на это.

0F = F, нули из начала отсекаются (если я правильно понял).

Как-то не понял самой концепции, ведь если битовая длина числа больше битовой длины модуля, то число%модуль будет меньше числа. Тут хоть все нули заменяй единицами, не поможет.

В библиотеке так же старший разряд имеет ненулевое значение (а если имеет - попросту игнорируется)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
12 минуты назад, HeroBrine1st сказал:

0F = F, нули из начала отсекаются (если я правильно понял).

Ведущий ноль не отсекается. Во-первых, это можно видеть по выводу, выложенному в этом посте, а во-вторых, я сейчас запустил такой же бесконечный цикл, фильтрующий числа короче полного, на выходе ничего не получил.

 

17 минут назад, HeroBrine1st сказал:

Как-то не понял самой концепции, ведь если битовая длина числа больше битовой длины модуля, то число%модуль будет меньше числа. Тут хоть все нули заменяй единицами, не поможет.

Я про это и говорю: длина шифруемого числа, даже если в нём все биты нулевые, должна быть меньше фактической битовой длины модуля. То есть, длину модуля считаем по самому старшему единичному биту или байту. А длину допустимого к шифрованию числа считаем просто по количеству бит или байт, независимо от содержимого.

 

24 минуты назад, HeroBrine1st сказал:

В библиотеке так же старший разряд имеет ненулевое значение (а если имеет - попросту игнорируется)

Не уверен, как это понимать. Если под игнорируется имеется в виду "ищется новое значение", то да, это верный вариант. Но в этом случае максимальное количество шифруемых бит всегда должно быть хотя бы на один меньше. То есть, 32-битным ключом не всегда получится успешно зашифровать и расшифровать 32-битные данные.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
19 часов назад, eu_tomat сказал:

Не уверен, как это понимать

Я вот тоже как-то не понимаю)

Ничего не понял, кроме цитаты выше и следующего за ней текста.

Собственно, библиотека. metaint имеет основание 10^7, т.е. 10 в этой системе = 10^7, а 010 попросту не появляется - все нули с конца массива отсекаются (библиотека пишет число справа налево).

 

Кажется я понял, что вы имеете в виду и зачем это.. Да, я возьму идейку адаптивного размера блока, но пока не предполагаю, как получить битовую длину быстро и эффективно. Наверное, проще будет добавить поддержку настоящих форматов ключей, а там просто по длине base64 вычислять битовую длину. Или логарифмы. посмотрю там.

Возможно потребуется полный рефакторинг, начиная от самого RSAB и заканчивая небольшой доработкой metaint (вставить алгоритм Монтгометри и допилить отрицательные числа). Мне уже самому не нравится такой дикий код)

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
3 часа назад, HeroBrine1st сказал:

Собственно, библиотека. metaint имеет основание 10^7, т.е. 10 в этой системе = 10^7, а 010 попросту не появляется - все нули с конца массива отсекаются (библиотека пишет число справа налево).

 

3 часа назад, HeroBrine1st сказал:

Или логарифмы. посмотрю там.

Да, можно логарифмами. При основании 10^7 каждый разряд числа кроме старшего кодирует log2(10^7)=23.25349 бит информации. Количество бит, кодируемых старшим разрядом, равно логарифму его значения по основанию два. Например, если разряды числа хранятся в таблице, и при этом не хранятся ведущие нули, то максимальное количество шифруемых бит будет равно log2(10^7)*(#t-1) + log2(t[#t]).

 

И, кстати, при генерации простых чисел p и q тоже надо стремиться к выбору чисел из верхнего диапазона, как этого сделано в openssl. Там при хранении числа с необрезанными ведущими нулями старший байт всегда имеет ненулевое значение. Можно было бы и в этой библиотеке при генерации использовать фильтр, чтобы старший разряд всегда превышал некоторое значение. Если попытаться обрезать ведущие нули у такого числа, то обрезать там будет попросту нечего.

 

А ещё нужно помнить, что с каждым отрезанным разрядом падает фактическая длина ключа, что сказывается на его криптостойкости. В openssl больше 7 бит никогда не отрезается от длины ключа. Может, и ещё меньше, я не проверял.

 

3 часа назад, HeroBrine1st сказал:

Наверное, проще будет добавить поддержку настоящих форматов ключей, а там просто по длине base64 вычислять битовую длину.

А это было бы очень интересно. Не все видят смысл в генерации ключей именно этой библиотекой, да и генерируются они неприлично долго. Шифрование, конечно, тоже тормозит, но его алгоритм гораздо проще, что позволит относительно небольшими усилиями оптимизировать его до предела.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Занялся я тут алгоритмом.. Результат - не очень, но что-то есть. Вряд ли кто-то тут разбирается на питоне, но там операция % - это modulo, поэтому я выбрал его ( + это мой основной язык). Вполне рабочий код - https://pastebin.com/N19hz1Qi

Но стоит изменить b на нечетное число (например 5 - оно при этом продолжает соотвествовать требованиям), то результат умножения алгоритмом и обычного с взятием остатка начинает сильно разниться. Но если подставить туда 4 или 2, то все становится нормально. Изменение n так же влечет разницу результатов.

Короче, прошу помощи с разработкой этого алгоритма) В рунете информации очень мало, вообще в интернете как-то тоже, готовых реализаций не видел (хотя искал). Есть только документ на 18 страниц (английский), который составлен с теми же ошибками, что есть на статье русской википедии.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
7 часов назад, HeroBrine1st сказал:

Занялся я тут алгоритмом.

Алгоритмом умножения Монтгомери, насколько я понимаю. Прошу сразу уточнять такие детали. А то до этого мы говорили об алгоритмах выбора оптимального размера блока, и вдруг внезапно появляется "Алгоритм".

 

Повторюсь:

В 26.08.2019 в 09:47, eu_tomat сказал:

В статье введено понятие n-остатка. И умножение Монтгомери работает не с исходными числами, и с их n-остатками. То есть, сначала числа преобразуются в их n-остатки, которые затем перемножаются по алгоритму Монтгомери. На выходе процедуры умножения также получается n-остаток. И для последующей работы его требуется преобразовать в исходную форму.

В твоём же коде print(mon_pro(a_n, b)). Во-первых, вторым аргументом нужно подавать не b, а также его n-остаток. Во-вторых, результат умножения требует обратного преобразования.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
9 часов назад, eu_tomat сказал:

Во-первых, вторым аргументом нужно подавать не b, а также его n-остаток. Во-вторых, результат умножения требует обратного преобразования.

Я не нашел образования n-остатка у b и просто забил на это, подав сам b :). По идее это будет b*r % n, что я тоже пытался и не помогало.

А вот обратным преобразованием я решил пренебречь, ибо при умножении a и b классическим путем я так же взял остаток. После сна я понял ("утро вечера мудренее"), что там вычисляется не a*b % n, а a*b*r^-1 mod n. Поработаю с преобразованием и n-остатком b, посмотрю что получится (возможно в комплексе будет работать)

Да, я говорил про алгоритм монтгомери - название сложное просто :)

Изменено пользователем HeroBrine1st
А нет, не получилось

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Наверное, получился этот алгоритм Монтгомери. Наугад.

На картинке ниже (это из PDF) я нашел две переменные, которые нигде не определены и по названию не совсем понятно, как их вычислять (j - вообще не указано, ei - тоже как-то не понятно, да и зачем там r на 1 умножать?):

image.png.a3fa425ace38fd55a373f7c4cdebeee1.png

Собственно, ссылочка https://pastebin.com/KbpTxj9N

Тем не менее, проблемы все еще существуют - подходят не все пары n и r (из тех, что изначально подходят по требованиям). Возможно проблема в коротких числах. Посмотрю пока metaint, добавлю отрицательные числа и перенесу эту штучку в луа, может быть проблемы исчезнут.

Я не слишком силен в настолько сложной математике, так что помощь тоже не помешает) Зачем я вообще за RSA взялся.. сидел бы ботов кодил, моды писал в конце-концов, может уравнения решал всякие. Ну, хотя бы знаю обратную сторону этой штуки)

 

P.s. Задержка связана с тем, что я взял коньюнкцию вместо возведения в степень и не сразу это понял) только проверив дополнительно на калькуляторе нашел ошибку

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
17 минут назад, HeroBrine1st сказал:

На картинке ниже (это из PDF) я нашел две переменные, которые нигде не определены и по названию не совсем понятно, как их вычислять (j - вообще не указано, ei - тоже как-то не понятно, да и зачем там r на 1 умножать?):

j это длина экспоненты в битах, i индексирует биты. ej - это очередной бит экспоненты. В Си-подобных языках нумерация выполняется в диапазоне [0..n-1] в отличие от [1..n] в Луа.

 

Единицу на r умножать не надо, такая запись применена для наглядности: сначала получаем n-остаток исходного числа и n-остаток единицы, затем выполняем серию умножений по Монтгомери, а на последнем шаге выполняем обратное преобразование результирующего n-остатка через фиктивное умножение Монтгомери.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
1 час назад, eu_tomat сказал:

В Си-подобных языках нумерация выполняется в диапазоне [0..n-1] в отличие от [1..n] в Луа.

range(a, b) итерируется как целочисленное множество от a до b-1 :) Например, list(range(0,2)) равен [0,1]

image.png.c1d0f808a266ecd64eacd3b24269f1d2.png

По остальному согласен, благодарю. Не понимаю, как у меня получилось без этого возвести в степень xD
Приму к сведению, пойду исправлять скрипт

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

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

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...