Вы — молодцы, проект просто великолепный! Тоже когда-то будучи студентом писал интерпретатор НА. Но это было в 19-м веке, под DOS и на Паскале. Результат — трассировка выполнения писалась в файл в формате HTML с указанием правила и выделением изменившихся подстрок. Этот файл можно было распечатать и приложить в качестве ответа на домашнюю работу по теории алгоритмов. Да, в консоли тоже все выводилось с подсветкой.
Спасибо за статью! Однако хочу заметить, что генерация псевдослучайных чисел — это по своей природе последовательный процесс, который обычно не распараллеливается (кроме некоторых специальных случаев, например, в криптографии: AES-CTR или Yarrow). Последовательный он потому, что по определению предусматривает возможность полностью воссоздать всю последовательность псевдослучайных чисел, задав исходное зерно (seed).
Генератор обычно устроен таким образом: он хранит в себе некоторое состояние, при каждом обращении он генерирует новое число, исходя из этого состояния, затем меняет состояние. Таким образом, даже MKL-евский генератор имеет ограничение по эффективности.
Благодаря вашей статье, я пошел разбираться в технологии бутстреппинга. Оказалось это — отличная, простая и очень удобная техника. Однако, поскольку идентичность результата при одном и том же зерне в вашем случае не важна, я бы предложил другой подход. Создал бы собственный класс генератора случайных чисел, чтобы каждый поток мог создать себе экземпляр такого класса с разным зерном. Для статистического моделирования я бы взял самый простой генератор Multiply with carry. Сам я обычно использую в качестве генератора ПСЧ алгоритм поточного шифрования RC4. Он имеет лучшие статистические характеристики, чем встроенный генератор, и чем MWC. И к тому же RC4 имеет очень простую реализацию, порядка десяти строчек кода (собственно для самой криптографии он уже устарел, хотя и используется по умолчанию многими серверами на SSL).
После того, как генератор есть, я бы дал каждому потоку по своему экземпляру класса генератора, инициализированного разными зернами (лучше всего использовать умножение значения таймера системы на уникальное для потока простое число, так больше энтропии). После этого каждый параллельный поток работал бы со своим генератором и, конечно, загрузил бы все ядра на полную катушку.
Спасибо за вопросы. Здесь есть два момента.
1. Многие схемы шифрования не обеспечивают должной защиты, если для шифрования сообщений используются ключи, которые не сильно отличаются один от другого. При этом сообщение, зашифрованное с ключом «asdf» и другое сообщение, зашифрованное с ключем «bsdf», будет иметь статистическое отклонение от случайной последовательности данных, а значит возможна потенциальная атака. Кстати, таким свойством обладает и ASE-256. Хэши от «asdf» и «bsdf» будут сщественно отличаться, поэтому шифрованные ими сообщения уже не будут обладать статистическим отклонением.
2.Конкретно применительно к DH: применение хэша к выходной последовательности «рамазывает» мощное множество выходных данных, не обладающих равномерным распределением значений, и делает его как-бы равномерным. Обратите внимание, что ключ, сгенерированный DF имеет длину 2048, а для генерации пары ключей AES-256 нам достаточно 512 бит. С одной стороны хэш уменьшает длину ключа, но с другой — делает этот ключ неотличимым от равномерно распределенного.
Кстати, если протокол будет корректироваться, хочу добавить от себя по поводу
key = (pow(g_b, a) mod dh_prime)
Как нам рассказывал D. Boneh на курсах криптографии, это выражение выдает не равномерно распреленную величину, поэтому его следует пропустить через KDF, на основе какого-нибуть стойкого хэша (SHA-256?), а не использовать на прямую как материал ключа.
И еще вопрос. Почему бы не использовать устоявшийся подход TLS (SSL) для обмена ключами? В нем всякие подобные детали (в том числе проблема слабой энтопии на клиенте) уже проверены (и исправлены) временем.
Подобное есть и в IT. Вот новость о создании сверхбыстрого компьютера, построенного на «старых советских технологиях», который собрали студенты и который обгонит по прозводительности на Linpack японский «K Computer».
Очень хороший пример принципа, согласно которому алгоритм шифрования, обеспечивающий секретность, но не целостность, в конченом счете не обеспечивает и секретности, т.к. нестойкий к активным атакам (схемы ECB, CTR, CBC).
Например, вы знаете, что кто-то посылает по сети электронный зашифрованный чек на сумму 100$. Вы также знаете позицию, в которой расположена сумма (допустим она записана строкой). Перехватив сообщение и не зная ни ключа, ни остального его содержания вы можете занемить 100$ на 900$ заменив позицию в которой записана «1» (в зашиврованном виде это некий X) значением (X xor «1» xor «9»).
Тут все аналогично, только позиция и значение перебиралось наугад.
dtach -A /tmp/session.dt bash Ctrl + \ — detach
Есть удобная команда 'dtach', которую иногда удобнее использовать вместо 'disown'. Она перенаправляет stdin/stdout в unix-сокет, к которому позже можно подключиться. На сокет можно настроить права на запись и чтение и несколько пользователей могут работать с сокетом одновременно. Очень удобно, если нужно, например, транслировать группе людей окно терминала. Есть патч, позволяющий работать с сокетом, доступным только для чтения.
1. Зачем две константы, если они эквивалентны?
2. В каких случаях может возникнуть необходимость сравнивать беззнаковое целое с отрицательным числом вместо использования положительной константы?
3. Приведенный вами код выглядит подозрительно, возможно некоторые компиляторы даже генерируют предупреждение. Неужели для сокетов корректно писать «if (socket==-1)»?
Здесь мы имеем дело с двоичным представлением числа «101» со сдвигом запятой на несколько разрядов влево. 1,01 — это двоичное представление, означающее 1*20 + 0*2-1 + 1*2-2 (где * — умножение). Сдвинув запятую на три позиции влево получим «1,01e-3» = 1*2-3 + 0*2-4 + 1*2-5 = 1*0,125 + 0*0,0625 + 1*0,03125 = 0,125 + 0,03125 = 0,15625.
Еще можно использовать лицензию WTFPL, хотя ее текст граничит с шуткой. Можно использовать двойное лицензирование — общественное достояние и WTFPL, а пользователь сам выберет. Так сделали в LibTom*, например.
Да, теоретически закрытый код != коммерческий проект. Но Linux скорее исключение, большинство программ никто бы не покупал, если бы их исходники были доступны. Но отдавая код в свободное сообщество я хочу пользоваться своим кодов как хочу, даже если кто-нибудь что-нибудь в нем улучшит.
Есть еще модель двойного лицензирования — GPL+коммерческая лицензия (как, например, в MatrixSSL, PolarSSL). Я как-то пробовал сделать контрибуцию в один такой проект. Так мой код так изменили (это мое предположение), чтобы я никоим образом не смог доказать, что идея этих нескольких строчек кода — моя, т.к. они бы не смогли распространять код по «Коммерческой» лицензии (для закрытых проектов).
Линус Торвальдс придумал GPL для того, чтобы каждый, кто улучшит код и распространяет результат возвращал улучшения (производные работы) в сообщество. Это разумно и я полностью с этим согласен и поддерживаю. Но современный GPL (начиная с 2) требует открытия кода всей программы, если я использую крохотную GPL-библиотеку или хотя бы маленький кусочек GPL-кода. Даже если я использую GPL-ную DLL. Это очень широкая формулировка термина «производная работа». А для Web этот термин вообще не ясен до конца.
И еще один нюанс GPL, который я не могу принять. GPL диктует не только то, что я могу или не могу делать с самим GPL-ным кодом, а накладывает обязательства на мой собственный код, который автор GPL-ного кода не писал. Таким образом я как бы лишаюсь права поступать со своим кодом так, как захочу (не могу закрыть), если в нем есть кусочек GPL. Я не юрист, но при обсуждении GPL на форумах часто возникает вопрос о том, возможно ли вообще законодательно в лицензии на один код накладывать ограничение на другой.
Но не поймите меня неверно, я с удовольствием по возможности вношу контрибуции в проекты на GPL. Но если я делюсь чем-то своим, делаю это под BSD.
Да, в GPL вы можете потребовать исходники, если кто-то распространяет программу, использующую ваш код. Но когда вы получите этот кот, вы не сможете использовать его в коммерческих целях, т.к. исходники таких проектов придется открыть. Даже вашу собственную библиотеку вы не сможете закрыть без согласия всех контрибьюторов. Очень хорошо сказали выше: GPL — это свобода софта, MIT/BSD — свобода разработчика. Лично я раньше тоже склонялся к GPL, потом разобрался что к чему и открываю код только по лицензии BSD.
Как вы узнаете, можно ли доверять приложению, пока оно не начнет открывать соединения по сети или не начнет куда-нибудь внедряться? Outpost так сказать ловит приложение «на гарячем», тогда как в Linux все обязательно нужно знать заранее, а остальное — запретить.
Ну, параллельный компьютер, для которого все делается справится с этой задачей быстрее. А посчитать пи до 15 знаков может любая персоналка за доли секунды. Зачем тогда весь этот параллелизм?
Генератор обычно устроен таким образом: он хранит в себе некоторое состояние, при каждом обращении он генерирует новое число, исходя из этого состояния, затем меняет состояние. Таким образом, даже MKL-евский генератор имеет ограничение по эффективности.
Благодаря вашей статье, я пошел разбираться в технологии бутстреппинга. Оказалось это — отличная, простая и очень удобная техника. Однако, поскольку идентичность результата при одном и том же зерне в вашем случае не важна, я бы предложил другой подход. Создал бы собственный класс генератора случайных чисел, чтобы каждый поток мог создать себе экземпляр такого класса с разным зерном. Для статистического моделирования я бы взял самый простой генератор Multiply with carry. Сам я обычно использую в качестве генератора ПСЧ алгоритм поточного шифрования RC4. Он имеет лучшие статистические характеристики, чем встроенный генератор, и чем MWC. И к тому же RC4 имеет очень простую реализацию, порядка десяти строчек кода (собственно для самой криптографии он уже устарел, хотя и используется по умолчанию многими серверами на SSL).
После того, как генератор есть, я бы дал каждому потоку по своему экземпляру класса генератора, инициализированного разными зернами (лучше всего использовать умножение значения таймера системы на уникальное для потока простое число, так больше энтропии). После этого каждый параллельный поток работал бы со своим генератором и, конечно, загрузил бы все ядра на полную катушку.
1. Многие схемы шифрования не обеспечивают должной защиты, если для шифрования сообщений используются ключи, которые не сильно отличаются один от другого. При этом сообщение, зашифрованное с ключом «asdf» и другое сообщение, зашифрованное с ключем «bsdf», будет иметь статистическое отклонение от случайной последовательности данных, а значит возможна потенциальная атака. Кстати, таким свойством обладает и ASE-256. Хэши от «asdf» и «bsdf» будут сщественно отличаться, поэтому шифрованные ими сообщения уже не будут обладать статистическим отклонением.
2.Конкретно применительно к DH: применение хэша к выходной последовательности «рамазывает» мощное множество выходных данных, не обладающих равномерным распределением значений, и делает его как-бы равномерным. Обратите внимание, что ключ, сгенерированный DF имеет длину 2048, а для генерации пары ключей AES-256 нам достаточно 512 бит. С одной стороны хэш уменьшает длину ключа, но с другой — делает этот ключ неотличимым от равномерно распределенного.
Как нам рассказывал D. Boneh на курсах криптографии, это выражение выдает не равномерно распреленную величину, поэтому его следует пропустить через KDF, на основе какого-нибуть стойкого хэша (SHA-256?), а не использовать на прямую как материал ключа.
И еще вопрос. Почему бы не использовать устоявшийся подход TLS (SSL) для обмена ключами? В нем всякие подобные детали (в том числе проблема слабой энтопии на клиенте) уже проверены (и исправлены) временем.
Долго всматривался и думал: «1С, что-ли?»
Статья понравилась, особенно про «осенизм». Весной и осенью у шизофреников обостряется активность, так что очень верно подмечено.
Например, вы знаете, что кто-то посылает по сети электронный зашифрованный чек на сумму 100$. Вы также знаете позицию, в которой расположена сумма (допустим она записана строкой). Перехватив сообщение и не зная ни ключа, ни остального его содержания вы можете занемить 100$ на 900$ заменив позицию в которой записана «1» (в зашиврованном виде это некий X) значением (X xor «1» xor «9»).
Тут все аналогично, только позиция и значение перебиралось наугад.
dtach -A /tmp/session.dt bash
Ctrl + \
— detachЕсть удобная команда 'dtach', которую иногда удобнее использовать вместо 'disown'. Она перенаправляет stdin/stdout в unix-сокет, к которому позже можно подключиться. На сокет можно настроить права на запись и чтение и несколько пользователей могут работать с сокетом одновременно. Очень удобно, если нужно, например, транслировать группе людей окно терминала. Есть патч, позволяющий работать с сокетом, доступным только для чтения.
2. В каких случаях может возникнуть необходимость сравнивать беззнаковое целое с отрицательным числом вместо использования положительной константы?
3. Приведенный вами код выглядит подозрительно, возможно некоторые компиляторы даже генерируют предупреждение. Неужели для сокетов корректно писать «if (socket==-1)»?
Что бы это значило?
Есть еще модель двойного лицензирования — GPL+коммерческая лицензия (как, например, в MatrixSSL, PolarSSL). Я как-то пробовал сделать контрибуцию в один такой проект. Так мой код так изменили (это мое предположение), чтобы я никоим образом не смог доказать, что идея этих нескольких строчек кода — моя, т.к. они бы не смогли распространять код по «Коммерческой» лицензии (для закрытых проектов).
Линус Торвальдс придумал GPL для того, чтобы каждый, кто улучшит код и распространяет результат возвращал улучшения (производные работы) в сообщество. Это разумно и я полностью с этим согласен и поддерживаю. Но современный GPL (начиная с 2) требует открытия кода всей программы, если я использую крохотную GPL-библиотеку или хотя бы маленький кусочек GPL-кода. Даже если я использую GPL-ную DLL. Это очень широкая формулировка термина «производная работа». А для Web этот термин вообще не ясен до конца.
И еще один нюанс GPL, который я не могу принять. GPL диктует не только то, что я могу или не могу делать с самим GPL-ным кодом, а накладывает обязательства на мой собственный код, который автор GPL-ного кода не писал. Таким образом я как бы лишаюсь права поступать со своим кодом так, как захочу (не могу закрыть), если в нем есть кусочек GPL. Я не юрист, но при обсуждении GPL на форумах часто возникает вопрос о том, возможно ли вообще законодательно в лицензии на один код накладывать ограничение на другой.
Но не поймите меня неверно, я с удовольствием по возможности вношу контрибуции в проекты на GPL. Но если я делюсь чем-то своим, делаю это под BSD.
Задача была бы на мой взгляд намного интереснее, если рассчитать, скажем, миллион знаков, а для представления чисел использовать gmp/mpfr.