eu_tomat 2 148 Опубликовано: 8 сентября, 2019 4 минуты назад, HeroBrine1st сказал: 1. В начало строки добавляется 4 случайных символа - соль 2. Строка делится на блоки по 4 символа, недостающие символы заполняются нулями Ага, я, кажется, понял, в чём подвох. Деление на блоки происходит фиксированно, без учёта фактической длины N. А я без затей для тестирования шифрования строки выбрал фразу "TEST", как раз 4 символа. Поэтому она не дробилась. А солью с длиной 4 символа по умолчанию как раз получалось два блока. 11 минуту назад, HeroBrine1st сказал: Разделить число на два.. вполне возможно Не-не... я предлагаю не блок дробить на два, но адаптивно подбирать размер блока, чтобы его длина всегда была меньше размера N. Самое простое: если фактическая длина N требует для его кодирования 4 байта, то в шифруемый блок можно поместить не более 3 символов. При желании можно и точное количество бит посчитать, но в этом я уже не вижу большого смысла. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 8 сентября, 2019 2 минуты назад, eu_tomat сказал: адаптивно подбирать размер блока, Однако для этого потребуется уведомлять другую сторону о том. что использована кастомная длина блока. Это, конечно. не проблема, но не проще ведь просто не использовать ключи менее 32 бит? Тем более, что в библиотеке (вроде) уже есть ограничение на количество бит, а ключи менее 2048 бит являются криптонеустойчивыми А в идеале нужно сделать шифрование в base64, но я пока не представляю, как это делается. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 8 сентября, 2019 27 минут назад, HeroBrine1st сказал: Однако для этого потребуется уведомлять другую сторону о том. что использована кастомная длина блока. Если алгоритм на обеих сторонах будет одинаковым, то уведомление не потребуется. 27 минут назад, HeroBrine1st сказал: но не проще ведь просто не использовать ключи менее 32 бит? Тут, во-первых, и ключ 32 бита не всегда помогает. А во-вторых, при длине ключа 256 бит шифровать блоки по 4 байта попросту неэффективно. Поэтому нужен адаптивный размер блока. А дальше либо подгонять размер блока под фактическую длину N, либо N формировать так, чтобы он был не меньше заданной длины. Я обратил внимание, как генерирует ключи openssl. Во всех виденных мною ключах всегда есть отличное от нуля число если не в старшем разряде, то в следующем за ним. Разряды там в 16-ричной системе, и двумя разрядами кодируется байт. Получается, что старший байт всегда имеет значение больше нуля. Видимо, так сделано специально. Это позволит, например, при 32-битном ключе гарантированно шифровать блок из 3 байт. Или 15 байт при 128-битном. Возможно, я не видел нулевого старшего байта лишь в силу незначительного шанса на это. Но я запускал на десяток минут бесконечный цикл генерации ключа с фильтрацией по нулю в старшем байте. Всегда старший байт что в модуле, что в закрытой экспоненте имел ненулевое значение. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 8 сентября, 2019 2 минуты назад, eu_tomat сказал: Возможно, я не видел нулевого старшего байта лишь в силу незначительного шанса на это. 0F = F, нули из начала отсекаются (если я правильно понял). Как-то не понял самой концепции, ведь если битовая длина числа больше битовой длины модуля, то число%модуль будет меньше числа. Тут хоть все нули заменяй единицами, не поможет. В библиотеке так же старший разряд имеет ненулевое значение (а если имеет - попросту игнорируется) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 8 сентября, 2019 12 минуты назад, HeroBrine1st сказал: 0F = F, нули из начала отсекаются (если я правильно понял). Ведущий ноль не отсекается. Во-первых, это можно видеть по выводу, выложенному в этом посте, а во-вторых, я сейчас запустил такой же бесконечный цикл, фильтрующий числа короче полного, на выходе ничего не получил. 17 минут назад, HeroBrine1st сказал: Как-то не понял самой концепции, ведь если битовая длина числа больше битовой длины модуля, то число%модуль будет меньше числа. Тут хоть все нули заменяй единицами, не поможет. Я про это и говорю: длина шифруемого числа, даже если в нём все биты нулевые, должна быть меньше фактической битовой длины модуля. То есть, длину модуля считаем по самому старшему единичному биту или байту. А длину допустимого к шифрованию числа считаем просто по количеству бит или байт, независимо от содержимого. 24 минуты назад, HeroBrine1st сказал: В библиотеке так же старший разряд имеет ненулевое значение (а если имеет - попросту игнорируется) Не уверен, как это понимать. Если под игнорируется имеется в виду "ищется новое значение", то да, это верный вариант. Но в этом случае максимальное количество шифруемых бит всегда должно быть хотя бы на один меньше. То есть, 32-битным ключом не всегда получится успешно зашифровать и расшифровать 32-битные данные. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 9 сентября, 2019 19 часов назад, eu_tomat сказал: Не уверен, как это понимать Я вот тоже как-то не понимаю) Ничего не понял, кроме цитаты выше и следующего за ней текста. Собственно, библиотека. metaint имеет основание 10^7, т.е. 10 в этой системе = 10^7, а 010 попросту не появляется - все нули с конца массива отсекаются (библиотека пишет число справа налево). Кажется я понял, что вы имеете в виду и зачем это.. Да, я возьму идейку адаптивного размера блока, но пока не предполагаю, как получить битовую длину быстро и эффективно. Наверное, проще будет добавить поддержку настоящих форматов ключей, а там просто по длине base64 вычислять битовую длину. Или логарифмы. посмотрю там. Возможно потребуется полный рефакторинг, начиная от самого RSAB и заканчивая небольшой доработкой metaint (вставить алгоритм Монтгометри и допилить отрицательные числа). Мне уже самому не нравится такой дикий код) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 9 сентября, 2019 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 вычислять битовую длину. А это было бы очень интересно. Не все видят смысл в генерации ключей именно этой библиотекой, да и генерируются они неприлично долго. Шифрование, конечно, тоже тормозит, но его алгоритм гораздо проще, что позволит относительно небольшими усилиями оптимизировать его до предела. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 10 сентября, 2019 Занялся я тут алгоритмом.. Результат - не очень, но что-то есть. Вряд ли кто-то тут разбирается на питоне, но там операция % - это modulo, поэтому я выбрал его ( + это мой основной язык). Вполне рабочий код - https://pastebin.com/N19hz1Qi Но стоит изменить b на нечетное число (например 5 - оно при этом продолжает соотвествовать требованиям), то результат умножения алгоритмом и обычного с взятием остатка начинает сильно разниться. Но если подставить туда 4 или 2, то все становится нормально. Изменение n так же влечет разницу результатов. Короче, прошу помощи с разработкой этого алгоритма) В рунете информации очень мало, вообще в интернете как-то тоже, готовых реализаций не видел (хотя искал). Есть только документ на 18 страниц (английский), который составлен с теми же ошибками, что есть на статье русской википедии. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 11 сентября, 2019 7 часов назад, HeroBrine1st сказал: Занялся я тут алгоритмом. Алгоритмом умножения Монтгомери, насколько я понимаю. Прошу сразу уточнять такие детали. А то до этого мы говорили об алгоритмах выбора оптимального размера блока, и вдруг внезапно появляется "Алгоритм". Повторюсь: В 26.08.2019 в 09:47, eu_tomat сказал: В статье введено понятие n-остатка. И умножение Монтгомери работает не с исходными числами, и с их n-остатками. То есть, сначала числа преобразуются в их n-остатки, которые затем перемножаются по алгоритму Монтгомери. На выходе процедуры умножения также получается n-остаток. И для последующей работы его требуется преобразовать в исходную форму. В твоём же коде print(mon_pro(a_n, b)). Во-первых, вторым аргументом нужно подавать не b, а также его n-остаток. Во-вторых, результат умножения требует обратного преобразования. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 11 сентября, 2019 (изменено) 9 часов назад, eu_tomat сказал: Во-первых, вторым аргументом нужно подавать не b, а также его n-остаток. Во-вторых, результат умножения требует обратного преобразования. Я не нашел образования n-остатка у b и просто забил на это, подав сам b . По идее это будет b*r % n, что я тоже пытался и не помогало. А вот обратным преобразованием я решил пренебречь, ибо при умножении a и b классическим путем я так же взял остаток. После сна я понял ("утро вечера мудренее"), что там вычисляется не a*b % n, а a*b*r^-1 mod n. Поработаю с преобразованием и n-остатком b, посмотрю что получится (возможно в комплексе будет работать) Да, я говорил про алгоритм монтгомери - название сложное просто Изменено 11 сентября, 2019 пользователем HeroBrine1st А нет, не получилось Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 14 сентября, 2019 Наверное, получился этот алгоритм Монтгомери. Наугад. На картинке ниже (это из PDF) я нашел две переменные, которые нигде не определены и по названию не совсем понятно, как их вычислять (j - вообще не указано, ei - тоже как-то не понятно, да и зачем там r на 1 умножать?): Собственно, ссылочка https://pastebin.com/KbpTxj9N Тем не менее, проблемы все еще существуют - подходят не все пары n и r (из тех, что изначально подходят по требованиям). Возможно проблема в коротких числах. Посмотрю пока metaint, добавлю отрицательные числа и перенесу эту штучку в луа, может быть проблемы исчезнут. Я не слишком силен в настолько сложной математике, так что помощь тоже не помешает) Зачем я вообще за RSA взялся.. сидел бы ботов кодил, моды писал в конце-концов, может уравнения решал всякие. Ну, хотя бы знаю обратную сторону этой штуки) P.s. Задержка связана с тем, что я взял коньюнкцию вместо возведения в степень и не сразу это понял) только проверив дополнительно на калькуляторе нашел ошибку Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
eu_tomat 2 148 Опубликовано: 14 сентября, 2019 17 минут назад, HeroBrine1st сказал: На картинке ниже (это из PDF) я нашел две переменные, которые нигде не определены и по названию не совсем понятно, как их вычислять (j - вообще не указано, ei - тоже как-то не понятно, да и зачем там r на 1 умножать?): j это длина экспоненты в битах, i индексирует биты. ej - это очередной бит экспоненты. В Си-подобных языках нумерация выполняется в диапазоне [0..n-1] в отличие от [1..n] в Луа. Единицу на r умножать не надо, такая запись применена для наглядности: сначала получаем n-остаток исходного числа и n-остаток единицы, затем выполняем серию умножений по Монтгомери, а на последнем шаге выполняем обратное преобразование результирующего n-остатка через фиктивное умножение Монтгомери. 1 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 14 сентября, 2019 1 час назад, eu_tomat сказал: В Си-подобных языках нумерация выполняется в диапазоне [0..n-1] в отличие от [1..n] в Луа. range(a, b) итерируется как целочисленное множество от a до b-1 Например, list(range(0,2)) равен [0,1] По остальному согласен, благодарю. Не понимаю, как у меня получилось без этого возвести в степень xD Приму к сведению, пойду исправлять скрипт Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах