Неинициализированный bool нормально сравнится, оба if будут ложными либо сравнение на true будет заменено компилятором на "не ноль". Дальше если оптимизатор вырезал "недостижимый" код, то все плохо, иначе сработает последний return и всё хорошо.
toString для bool можно сделать как return constantStrings[boolValue], которая полагается на то, что bool превращается в 0 или 1. Неинициализированный, соответственно, даст выход за границы массива и там можно схватить вообще что угодно, NPE в том числе. Но тут надо будет старательно завернуть всё в unsafe и выкрутить оптимизатор.
Как проверить, что функция, перемножающая два числа и делящая результат на третье, работает всегда корректно? Кроме "открыть, почитать, подумать", я другого способа не вижу. Можно скормить ей произвольные данные, но это будет вероятностный тест. Вдруг внутри этой функции какое-то значение промежуточного результата используется как код ошибки? Это отсылка к функции MulDiv из winbase.h.
Потому что, согласно спецификации, работа toString гарантируется только на корректных входных данных, а здесь на вход пришли неинициализированные. На корректных тестах всё работало. Undefined behavior, однако.
Это, конечно, была ирония. Протестировать тестами полностью всё невозможно — два int' а во входных данных уже дадут де-факто бесконечное время для перебора.
За эти «три дня» в прошлом году пара сотрудников полиции лишилась работы. Это произошло с моим знакомым. А человек, которого искали, и не терялся, как оказалось.
Тут возникает сложный вопрос: а если бы не было Спейс шаттла, то какую схему выбрал бы Маск для многоразового корабля/ракеты? Легко понять недостатки шаттла, когда он уже летает, но до этого? Вдруг SpaceX стала бы делать по аналогичной схеме и разорилась бы? История не терпит сослагательного наклонения, я не спорю, но отрицательные результаты шаттла тоже являются базой для Фалькона. Возможно даже в большей степени, чем какие-либо конкретные механизмы.
P.S. 14 человек, имхо, сравнивать с Союзом некорректно — всё-таки половина из них погибли при посадке, где у Союза тоже нет САС. Если бы у Союза отошла термозащита, он бы точно так же сгорел. А вот семерых погибших на старте сравнивать можно, но тогда уж с нулём Союза, если не ошибаюсь.
Я хотел оспорить заявление nicholas_k о том, что Фалькон был сделан с нуля, но промахнулся первым комментарием и обсуждение пошло не туда.
Маршевые двигатели многоразового запуска на Шаттле — это база для разработок Фалькона.
Многоразовость Шаттла обуславливалась в первую очередь двигателями многократного запуска и широкого диапазона тяги. Ракетная схема для схода с орбиты, кмк, не очень. Тот же SpaceX сажал пока только бустеры, а не орбитальные корабли.
Очень интересный эксперимент, спасибо автору.
А вы можете проделать этот эксперимент с «армейской» формой наказания, когда штраф получает не только попавшийся индивид, но и его «взвод»? Тут можно сделать даже в двух вариантах — раздавать штраф клетке и её геометрическим соседям или клетке и её «родственникам». Второй вариант теоретически может решить изначальную цель оптимизации.
За что купил, за то и продаю.
Возможно, в 90х ситуация отличалась — TSMC была образована в 1987 году. Скорее всего речь шла не о контрактах на микропроцессоры, а на устройства попроще (Эльбрус так-то тоже был не на острие техпроцесса). А возможно, Борис Арташесович слегка лукавил, и проблема была не столько в этом, а просто фабрика пыталась выбить себе условия повыгоднее. В любом случае мой посыл был в том, что
> А в чем проблема предложить военным ARM, сделанный на современной фабрике?
заключена в том, что фабрике могут просто не дать произвести этот процессор с помощью экономических или политических рычагов. Если для гражданской электроники это скорее относится к мифам и легендам, то для военных это вполне себе риск, причем существенный. Краем уха слышал, что для какой-то техники РФ уходит даже с минских грузовых шасси, а тут процессор и в далекой Тайвани. Возможно, эта далекая Тайвань стала ближе из-за текущей дружбы с Китаем, но, имхо, именно для военных такой подход так себе.
А если фабрика откажется его производить? Бабаян в приватном разговоре как-то сказал, что попытки эльбрусовцев выйти на фабрики пресекались интелом. То есть фабрике ставилось условие: или вы производите всё, что хотите, или у вас есть контракты с Интел. В принципе, вполне рыночный механизм. И это было ещё в 90х, когда был мир-дружба-жвачка. (Хотя я думаю, что он слегка лукавит). Сейчас, я надеюсь, на Интел все не настолько завязаны, но ведь появился механизм "санкций", а военным очень не нравится, когда производство их игрушек может быть остановлено третьей страной.
Для p в 2048 бит и q на 40 бит получилось примерно 500 дней. Для 1024 — 109 дней.
В один поток в самописной длинной арифметике — без SSE и на 32 битах. Процентов 30, я думаю, еще можно было бы добиться, если сделать аккуратнее. Плюс многопоточность.
А дальше надо считать. Чтобы отрезать 10 бит, необходимо перебрать порядка 2^10 вариантов k. Расположены они более-менее равномерно, я проверил.
Раз вы апеллируете к стоимости билета, то я тоже буду ссылаться на физические ограничения. Если билет выписывается раз в пять минут (на мобильном терминале), то сколько бит мы сможем на STM32 выиграть? А с другой стороны у нас целая общага, где у каждого — отдельный комп.
Нет здесь любых h->g. Для проверки подписи на стороне верификатора надо четко знать g — нам надо его в степень возводить. Поэтому как бы вы их не запаковывали, распакуются они быстрее проверки подписи.
Ну и вы забыли про публичный ключ g^x. Он тоже должен как-то на той стороне очутиться. Это сложно сделать с произвольным g.
Т.е. если g не опубликовывать, а короткое h зависимо "примешать" в подпись, то подбирать нужно будет не только k, но и g (от неизвестной вычисляемой h).
Подбор g потребует времени меньше, чем проверка подписи. Хотя бы потому, что для проверки подписи надо знать g :)
Всего?!
Перебрать каким действием?
Умножаем g на себя, берем остаток от деления на p, запоминаем (пусть будет G). Берем остаток от деления на q, проверяем.
Если не совпало, берем G, умножаем на g, берем остаток от деления на p, запоминаем (пусть будет G). Берем остаток от деления на q, проверяем.
И так далее. На проверку одного k необходима одна операция умножения, две взятия остатка, одно сравнение.
Я это взял дословно из вашей википедии (раз уж вы все время на нее ссылались, типа "надо не RFC читать, а arXiv.org или хотя бы википедию.").
Какая же жесть на русской википедии творится… Извините, я смотрел только английскую.
Вы надеюсь понимаете что короткий "оттиск" подписи по модулю q, не приближает вас никак к отгадыванию x из секрета.
Потому что x — то есть только часть ибо это экспонента в полном "закрытом" ключе (напрямую для y и опосредствованно для s).
Еще раз, не нужно путать x с закрытым ключом.
Которым оно де факто не является как можно было подумать, читая стандарт. А вся комбинация (x, p, q, h) ну или (x, p, q, g) в некоторых вариантах (просто g вычисляемо от h,p,q).
То что при этом (p, q, g) и даже y известны/опубликованы, вам никак не поможет.
Т.е. в реальности подбор этого "короткого" x, на "длинном" поле открытых значений p, q, g, есть настолько ресурсозатратная задача, что....
Обычно p, q, g называют "доменными параметрами", x — приватным ключом, y — публичным. Знания x и доменных параметров хватает для создания подписи.
g — это генератор подгруппы размера q. Т.е. g^i mod p = g^(i+q) mod p для любого i. Поэтому k лежит в области [0;q) — любое значение сверх q даёт тот же результат, что в остатке от деления на q. Т.е. надо перебрать всего 2^40 значений, чтобы его восстановить. Аналогично x и любое другое число, в которое возводится g.
С двумя часами поспешил, конечно. Чуть побольше надо времени, день-два. Главное, не забыть кешировать результат после mod p, а не после mod q. Ну и расчет чудесно параллелится.
А ладно, вам другой вопрос — вы когда нибудь ключи эльгамаля вообще генерировали?
Нет. Это имеет отношение к вопросу?
Эльгамаль-ключ?!.. Даже DSA-шный…
Подберётся?!.. Для p какой длинны?...
Вы невнимательно прочитали описание DSA. Не торопитесь, пожалуйста. DSAшный не подберётся, там q минимум в 160 бит. Дьявол — он в деталях.
А то есть вы теперь на DSA перепрыгнули… Ну ладно, давайте про DSA (хотя DSA — есть не самая лучшая производная эльджамаля...).
Давайте не DSA. Только давайте вы мне сразу ссылку на правильное описание рассматриваемой схемы дадите, а то вот с википедией я промахнулся. Иначе дискуссия у нас всё время в сторону уходит.
Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел (s,m) на пару чисел (s mod q, m mod q), где q является каким-то простым делителем числа (p−1). При этом сравнение для проверки подписи по модулю p нужно заменить на новое сравнение по модулю q: ( y^A ⋅ r^B) mod p = g^C (mod q). Так сделано в американском стандарте DSS
Я не знаю, откуда вы взяли это, но это неверно. Подписью является пара (r, s) или, если брать всю передаваемую информацию, (r, s, m). Сокращенный вариант — (r mod q, s mod q, m). Это видно из вашей же цитаты:
При этом сравнение для проверки подписи по модулю p нужно заменить на новое сравнение по модулю q: ( y^A ⋅ r^B) mod p = g^C (mod q).
r должна быть известна верификатору. Её нельзя фиксировать, её нельзя вычислять offline, т.к. по ней нельзя восстановить k, необходимый для подписи. Следовательно, её необходимо передавать.
Неинициализированный bool нормально сравнится, оба if будут ложными либо сравнение на true будет заменено компилятором на "не ноль". Дальше если оптимизатор вырезал "недостижимый" код, то все плохо, иначе сработает последний return и всё хорошо.
toString для bool можно сделать как return constantStrings[boolValue], которая полагается на то, что bool превращается в 0 или 1. Неинициализированный, соответственно, даст выход за границы массива и там можно схватить вообще что угодно, NPE в том числе. Но тут надо будет старательно завернуть всё в unsafe и выкрутить оптимизатор.
Как проверить, что функция, перемножающая два числа и делящая результат на третье, работает всегда корректно? Кроме "открыть, почитать, подумать", я другого способа не вижу. Можно скормить ей произвольные данные, но это будет вероятностный тест. Вдруг внутри этой функции какое-то значение промежуточного результата используется как код ошибки? Это отсылка к функции MulDiv из winbase.h.
Потому что, согласно спецификации, работа toString гарантируется только на корректных входных данных, а здесь на вход пришли неинициализированные. На корректных тестах всё работало. Undefined behavior, однако.
Это, конечно, была ирония. Протестировать тестами полностью всё невозможно — два int' а во входных данных уже дадут де-факто бесконечное время для перебора.
Тут да, чёт категорично сморозил глупость. Спишемся это на болезнь.
Тут возникает сложный вопрос: а если бы не было Спейс шаттла, то какую схему выбрал бы Маск для многоразового корабля/ракеты? Легко понять недостатки шаттла, когда он уже летает, но до этого? Вдруг SpaceX стала бы делать по аналогичной схеме и разорилась бы? История не терпит сослагательного наклонения, я не спорю, но отрицательные результаты шаттла тоже являются базой для Фалькона. Возможно даже в большей степени, чем какие-либо конкретные механизмы.
P.S. 14 человек, имхо, сравнивать с Союзом некорректно — всё-таки половина из них погибли при посадке, где у Союза тоже нет САС. Если бы у Союза отошла термозащита, он бы точно так же сгорел. А вот семерых погибших на старте сравнивать можно, но тогда уж с нулём Союза, если не ошибаюсь.
Извините, но заминусованный комментарий воспринимался прямо противоположно. Хорошо, что позиция прояснилась.
Я хотел оспорить заявление nicholas_k о том, что Фалькон был сделан с нуля, но промахнулся первым комментарием и обсуждение пошло не туда.
Маршевые двигатели многоразового запуска на Шаттле — это база для разработок Фалькона.
Многоразовость Шаттла обуславливалась в первую очередь двигателями многократного запуска и широкого диапазона тяги. Ракетная схема для схода с орбиты, кмк, не очень. Тот же SpaceX сажал пока только бустеры, а не орбитальные корабли.
Space Shuttle. Он не просто челнок, он своими двигателями вполне себе работал на старте.
А вы можете проделать этот эксперимент с «армейской» формой наказания, когда штраф получает не только попавшийся индивид, но и его «взвод»? Тут можно сделать даже в двух вариантах — раздавать штраф клетке и её геометрическим соседям или клетке и её «родственникам». Второй вариант теоретически может решить изначальную цель оптимизации.
Возможно, в 90х ситуация отличалась — TSMC была образована в 1987 году. Скорее всего речь шла не о контрактах на микропроцессоры, а на устройства попроще (Эльбрус так-то тоже был не на острие техпроцесса). А возможно, Борис Арташесович слегка лукавил, и проблема была не столько в этом, а просто фабрика пыталась выбить себе условия повыгоднее. В любом случае мой посыл был в том, что
> А в чем проблема предложить военным ARM, сделанный на современной фабрике?
заключена в том, что фабрике могут просто не дать произвести этот процессор с помощью экономических или политических рычагов. Если для гражданской электроники это скорее относится к мифам и легендам, то для военных это вполне себе риск, причем существенный. Краем уха слышал, что для какой-то техники РФ уходит даже с минских грузовых шасси, а тут процессор и в далекой Тайвани. Возможно, эта далекая Тайвань стала ближе из-за текущей дружбы с Китаем, но, имхо, именно для военных такой подход так себе.
Кстати, нашел, что Интел таки сотрудничала с TSMC: www.oregonlive.com/business/index.ssf/2009/03/intel_outsourcing_some_atom_ma.html
Но судя по тексту, это был их первый раз.
А если фабрика откажется его производить? Бабаян в приватном разговоре как-то сказал, что попытки эльбрусовцев выйти на фабрики пресекались интелом. То есть фабрике ставилось условие: или вы производите всё, что хотите, или у вас есть контракты с Интел. В принципе, вполне рыночный механизм. И это было ещё в 90х, когда был мир-дружба-жвачка. (Хотя я думаю, что он слегка лукавит). Сейчас, я надеюсь, на Интел все не настолько завязаны, но ведь появился механизм "санкций", а военным очень не нравится, когда производство их игрушек может быть остановлено третьей страной.
В один поток в самописной длинной арифметике — без SSE и на 32 битах. Процентов 30, я думаю, еще можно было бы добиться, если сделать аккуратнее. Плюс многопоточность.
А дальше надо считать. Чтобы отрезать 10 бит, необходимо перебрать порядка 2^10 вариантов k. Расположены они более-менее равномерно, я проверил.
Раз вы апеллируете к стоимости билета, то я тоже буду ссылаться на физические ограничения. Если билет выписывается раз в пять минут (на мобильном терминале), то сколько бит мы сможем на STM32 выиграть? А с другой стороны у нас целая общага, где у каждого — отдельный комп.
Но сама идея предварительно накопить r — здравая.
Ну и вы забыли про публичный ключ g^x. Он тоже должен как-то на той стороне очутиться. Это сложно сделать с произвольным g.
Поэтому h и g — одно.
Подбор g потребует времени меньше, чем проверка подписи. Хотя бы потому, что для проверки подписи надо знать g :)
Умножаем g на себя, берем остаток от деления на p, запоминаем (пусть будет G). Берем остаток от деления на q, проверяем.
Если не совпало, берем G, умножаем на g, берем остаток от деления на p, запоминаем (пусть будет G). Берем остаток от деления на q, проверяем.
И так далее. На проверку одного k необходима одна операция умножения, две взятия остатка, одно сравнение.
Какая же жесть на русской википедии творится… Извините, я смотрел только английскую.
Обычно p, q, g называют "доменными параметрами", x — приватным ключом, y — публичным. Знания x и доменных параметров хватает для создания подписи.
g — это генератор подгруппы размера q. Т.е. g^i mod p = g^(i+q) mod p для любого i. Поэтому k лежит в области [0;q) — любое значение сверх q даёт тот же результат, что в остатке от деления на q. Т.е. надо перебрать всего 2^40 значений, чтобы его восстановить. Аналогично x и любое другое число, в которое возводится g.
С двумя часами поспешил, конечно. Чуть побольше надо времени, день-два. Главное, не забыть кешировать результат после mod p, а не после mod q. Ну и расчет чудесно параллелится.
Нет. Это имеет отношение к вопросу?
Вы невнимательно прочитали описание DSA. Не торопитесь, пожалуйста. DSAшный не подберётся, там q минимум в 160 бит. Дьявол — он в деталях.
Давайте не DSA. Только давайте вы мне сразу ссылку на правильное описание рассматриваемой схемы дадите, а то вот с википедией я промахнулся. Иначе дискуссия у нас всё время в сторону уходит.
Правда.
Я не знаю, откуда вы взяли это, но это неверно. Подписью является пара (r, s) или, если брать всю передаваемую информацию, (r, s, m). Сокращенный вариант — (r mod q, s mod q, m). Это видно из вашей же цитаты:
r должна быть известна верификатору. Её нельзя фиксировать, её нельзя вычислять offline, т.к. по ней нельзя восстановить k, необходимый для подписи. Следовательно, её необходимо передавать.
Вот сам стандарт http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf, смотреть страницу 19.
Получается, что подпись (r mod q, s mod q), если она 80 бит, то q — 40. Ну и далее я уже расписывал.