eu_tomat

@serafim А какой смысл дублировать на pastebin? Там же всё есть в репозитории.

Я тоже проверю свои телепатические способности. Речь, скорее всего, идёт об этой программе: https://github.com/ATastyPeanut/OpenComputers-Minecraft-Lua/blob/master/Ticks-Second-Tools/TPS-Holo-Display.lua Картинка тоже нашлась.

j это длина экспоненты в битах, i индексирует биты. ej - это очередной бит экспоненты. В Си-подобных языках нумерация выполняется в диапазоне [0..n-1] в отличие от [1..n] в Луа. Единицу на r умножать не надо, такая запись применена для наглядности: сначала получаем n-остаток исходного числа и n-остаток единицы, затем выполняем серию умножений по Монтгомери, а на последнем шаге выполняем обратное преобразование результирующего n-остатка через фиктивное умножение Монтгомери.

Алгоритмом умножения Монтгомери, насколько я понимаю. Прошу сразу уточнять такие детали. А то до этого мы говорили об алгоритмах выбора оптимального размера блока, и вдруг внезапно появляется "Алгоритм". Повторюсь: В твоём же коде print(mon_pro(a_n, b)). Во-первых, вторым аргументом нужно подавать не b, а также его n-остаток. Во-вторых, результат умножения требует обратного преобразования.

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

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

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

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

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

У меня результат заметно хуже, даже на CPU Core i7-4770K. 128-битный ключ генерируется в диапазоне 423-130 секунд. А 256-битный -- 377-895 секунд. Нижняя граница: запущен лишь Майнкрафт. Верхняя: во время активной работы в редакторе и браузере. Генерация 512-битного ключа обрывается по TLWY. Я подсунул ключи от openssl, сообщение было даже успешно зашифровано, но дешифрация также оборвалась по TLWY. Генерацию ключей я не смотрел, но шифрование точно имеет хороший потенциал для оптимизации. Мне вот, что непонятно. При шифровании с солью в выходной таблице появляется не одно число, а два. Это разделение на два независимых блока? И если так, то что мешает разделять любое сообщение даже без соли, если его размер превышает N? А если моя догадка неверна, то какую роль играет второе число при шифровании с солью?

Ого! На что только ни идут люди ради комфортной игры в Майнкрафт!

@HeroBrine1st Похоже, в библиотеке есть ошибка. Если исходное число превышает N, то после шифрования и дешифрования сообщение превращается в кашу. Или это так и задумано, и ответственность по выбору длины сообщения лежит на пользователе?

Да, в этом случае нажатия обрабатываются через listener, а внутрь цикла добавляется os.sleep, потому что события обрабатываются внутри него.

К слову, Atom тоже написан на Node.js/Electron. Всё говорит о том, что автор на верном пути.

@Doob Таковы этапы эволюции: Кирилл хочет, чтобы кто-то написал игру для него; Артур хочет сам написать OpenComputers Studio для других; Игорь уже написал MineCode IDE.

Упал, отжался, отозвался. Да, человечество уже давно мечтает о программе, которая позволит легко создавать lua скрипты. Но дальше разговоров дело не продвинулось до сих пор. Создавать lua скрипты стало даже сложнее, чем 20 лет назад. Обязательно! Но только если создавать lua скрипты в такой программе и вправду будет легко. В идеале нужно максимально упростить интерфейс. Если можно, оставить лишь две кнопки: "создать lua скрипт" и "создать графический интерфейс", а всё остальное программа должна сделать сама. Это очень бы упростило бы процесс создания lua скриптов и графических интерфейсов. Взаимно)

В Linux это проверяется так: создать ключ длиной 1024 бита: $ ssh-keygen -t rsa -b 1024 -N '' -f tmp-rsa-1024b вывести содержимое ключа в читаемом виде (длинные строки я обрезал для удобства): $ openssl asn1parse -in tmp-rsa-1024b 0:d=0 hl=4 l= 605 cons: SEQUENCE 4:d=1 hl=2 l= 1 prim: INTEGER :00 7:d=1 hl=3 l= 129 prim: INTEGER :B266CDD0ACA7CDB61DA3852B8E831690DFC36C8425E32C449B79D85AF6... 139:d=1 hl=2 l= 3 prim: INTEGER :010001 144:d=1 hl=3 l= 128 prim: INTEGER :6901C7DD2EF32A4B2A90E83EA60894CCBB58BCD3DFB5228653795996D9... 275:d=1 hl=2 l= 65 prim: INTEGER :E518DC47E852FE31DDDA8DB6A3B4D1D5BE1E7A65D55AFDC1E8D7BDDF98... 342:d=1 hl=2 l= 65 prim: INTEGER :C759EDF190F560FA22A4F590888F2FB6077091C18C9EAB6CE3B04D3916... 409:d=1 hl=2 l= 64 prim: INTEGER :68D3463FB4C2FCC28E73A9322F97D6078A156205E468DD0173EBFB5A2A... 475:d=1 hl=2 l= 65 prim: INTEGER :942F591C943092A1DD56D9E3525F7D8BC603FB94F03E921723394E6DFD... 542:d=1 hl=2 l= 65 prim: INTEGER :D8ED49BDBF7135BEC25E68E3762AEEAE997406C8CD91715B44C9A43274... Сопоставить вывод предыдущей команды с этим документом: https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pem RSAPrivateKey ::= SEQUENCE { version Version, modulus INTEGER, -- n publicExponent INTEGER, -- e privateExponent INTEGER, -- d prime1 INTEGER, -- p prime2 INTEGER, -- q exponent1 INTEGER, -- d mod (p-1) exponent2 INTEGER, -- d mod (q-1) coefficient INTEGER, -- (inverse of q) mod p otherPrimeInfos OtherPrimeInfos OPTIONAL } Как видно, готовый 1024-битный ключ содержит: модуль длиной длиной 128 байт (1024 бита); открытую экспоненту со стандартным значением, специально выбранным для упрощения вычислений на всякого рода умных кофеварках; закрытую экспоненту длиной 128 байт (1024 бита); Где-то вместо 128 указано 129 байт и 65 вместо 64. Это связано с тем, что стандарт подразумевает использование целых чисел со знаком, в которых старший бит числа интерпретируется как знак. Чтобы избежать этого, числа с единичным старшим битом расширяются на один байт.

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

Кстати, а ты можешь доступно объяснить, за счёт чего становится возможным получить остаток от деления без, собственно, деления на целевое число, чисто отсечением старших или младших разрядов? Так, чтобы было понятно ученикам средней школы. Про алгоритм Евклида, конечно, все знают, но уже его расширенный вариант для многих неочевиден.

Это да. По крайней мере, в Lua от OpenComputers нет заметной разницы во времени выполнения операций сложения, умножения, деления или сдвига для числовых типов. И задействование именно битовых операций вряд ли будет существенным. Но в длинной арифметике количество отдельных операций, необходимых для сложения, умножения, а тем более деления, существенно различается. Например, затраты на сдвиг длинного числа эквивалентны его умножению на короткое число и они меньше затрат на сложение двух длинных чисел. Умножение Монтгомери заменяет операцию взятия остатка от деления последовательностью более быстрых операций: одно сравнение одно или два сложения два умножения одно отсечение младших разрядов одно отсечение старших разрядов В этом весь смысл добавления новых сущностей в старую задачу.

На пальцах не объясню, но дам намёки. На Википедии есть статья про умножение Монтгомери. Но она носит справочный характер, а не обучающий. При её чтении надо обратить внимание на следующие моменты: В статье введено понятие n-остатка. И умножение Монтгомери работает не с исходными числами, и с их n-остатками. То есть, сначала числа преобразуются в их n-остатки, которые затем перемножаются по алгоритму Монтгомери. На выходе процедуры умножения также получается n-остаток. И для последующей работы его требуется преобразовать в исходную форму. Преобразования чисел требуют дополнительных вычислений, и на отдельно взятом умножении они лишь ухудшат производительность. Но приятная особенность в том, что самые тяжёлые вычисления выполняются на этапе преобразования чисел в n-остатки. Само умножение и обратное преобразование выполняются заметно быстрее за счёт замены операций деления сдвигами (битовыми в случае двоичной системы). Поэтому существенная экономия достигается при возведении числа в степень, где достаточно один раз выполнить преобразование в n-остатки, выполнить серию умножений n-остатков, а к результату применить обратное преобразование. Обратное преобразование уже присутствует в самой процедуре умножения Монтгомери, и её можно применить для этой цели без изменений, передав в качестве аргументов n-остаток числа и единицу. Результатом умножения будет искомое число. Самая большая магия (которую я сейчас пояснить не могу) происходит в этой стоке: u = (t+(t*n' % r)*n)/r. После её выполнения, возможно, потребуется выполнить u=u-n. Выглядит сложновато, и в выражении даже присутствуют два деления, но за счёт правильного выбора r операция деления легко заменяется сдвигом разрядов числа. Набросок алгоритма возведения в степень, приведённый в статье, вроде бы достаточно хорошо иллюстрирует его применение. Для оптимизации шифрования RSA очень пригодится.

Неожиданно выяснилось, что плата редстоуна из OC может выдавать и воспринимать сигналы в диапазоне [0..2^31-1]. Я, конечно, не знаю возможностей счётчика мобов из MineFactory Reloaded, но OC точно не будет узким местом. Тут скорее Майнкрафт повиснет от такого обилия скота.

А что будет при количестве мобов больше 15? Каков максимальный уровень сигнала?

Разные игроки мониторят. Это лучше для всех игроков? Предположим, не заставляешь. Тогда почему составляешь фразу в форме приказа, выраженного в категоричной форме?

А лучше для кого?