Как быстро посчитать M! mod N?

ECk

точней даже для нашего времени

 

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

 

crypto
Зря ты столь низкого мнения о современных криптоаналитиках - они решают задачки по - сложней
A. О чём текст?
B. А текст ли это??
C. Генератор псевдослучайных чисел??
Вопросы для особо одарённых:

Какой длины ключ?
А тот ли алгос они юзали???...??

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

 

UbIvItS
Где ты в моей фразе нашел "низкое мнение"?

 

crypto

чему криптоаналитик тут может позавидовать(?): он не знает о чём текст.., впрочем, я этот вопрос изложил в топике #23

 

UbIvItS

Это не задача криптоаналитика, другое дело, что знание контекста может существенно помочь. (см. мой пост 22). Учет специфики переписки (использование бюрократических штампов, к примеру, "На Ваш запрос относительно поставки ракет...") упрощает задачу. Был период, когда в аппаратуре засекречивания телефонных каналов шифровалась только речь, а паузы оставались чистенькими. Оказывается одной этой информации было достаточно для восстановления открытого текста.
C. Генератор псевдослучайных чисел??
Непонятно, что ты имел в виду. Электронные шифраторы всегда используют генератор псевдослучайных чисел. Есть специальные "рандомные" устройства, которые служат исключительно для задания случайного начального состояния. Если ты имел в виду восстановление алгоритма работы этого генератора, то да, согласен, задача криптоаналитика найти его неизвестную секретную составляющую. Только это задача из разряда неблагодарных, как только появились машинные шифры, она стала практически нерешаемой. И здесь поможет либо бог в лице шифровальщика, допустившего серьезную ошибку, либо техническая или прочая разведка, стащившая блок-схему генератора. В общем, из этого сейчас и исходят - знания алгоритма работы шифроатора.
А если ошибок не было, то как говорят спецы, пряча шифрованное сообщение в сейф до лучших времен, "Где сядешь, там и слезешь".

При чем здесь длина? Задача состоит в определении ключа. Такая характеристика, как длина, считается известной (см. выше).

Поясни, что ты имел в виду.

Если подвести маленькое резюме, то работа современного криптоаналитика в основном заключается в стандартном прогоне известных алгоритмов и в 99.99% случаев произнесении магической фразы "Где сядешь, там и слезешь". Существенные прорывы случаются редко, но они конечно же впечатляют!!!
В качестве примерчика технической ошибки могу вспомнить нелепый случай с машинкой "Хагеллин", когда некая страна, которая ее приобрела, долгое время использовала в качестве ключа ключ из технического мануала

 

в том то и дело, что числа псевдослучайны: алгоритмы генерации могут быть различны и таблицы этих чисел могут быть различны.

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

довольно просто настрокать свой сим. шифр - достаточно надёжный.

точней в 99, 99..9%. вообще мат. методики дешифровки сим. шифров в своей эффективности в основновном на нуле

 

UbIvItS

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

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

Твоя загадочная фраза так и осталась для меня загадочной.

 

алгосы генерации псевдослучайных чисел юзают таблицы случайных чисел.

алгос, коим шифровали, не всегда известен.

 

В общем случае никак, а вот для шифрования на секретном RSA ключе можно применить китайскую теорему остатков.

 

UyTvGauG
а ты пробовал??

 

UbIvItS

Да ну? Значит я отстал от этой жизни. (Если ты конечно не имеешь в виду создание начального состояния, в котором в принципе такое может иметь место быть).

Блин, уже устал повторять: криптоаналитики исходят из посылки, что как раз алгоритм то известен (а иначе совсем труба!), неизвестны его секретные параметры.

 

crypto

угу - я именно об этом.

даже если алгос известен, все параметры шифрования могут быть основаны на ключе, а он как раз и не известен

 

UbIvItS

О чем я тебе и талдычил - секретные (или ключевые) параметры алгоритма и являются целью криптоанализа.

 

crypto

тогда получается, что в начале мы друг друга не поняли: уж о чём я спорить не собирался, так это о целях криптоанализа)

 

Конечно пробовал, и активно юзаю в реализациях RSA.

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

 

UyTvGauG
меня больше интересует слом рса

 

кому не влом, подумайте вот над чем: довольно просто для числа N находить числа вида: px1+qx2 (x1, x2==??) - вот и вопрос как эти нумберы заюзать??

 

а это вообще реально? Я конечно не гуру криптографии, но о такой сенсации пока не слышал

 

MSoft

официально известных методик нет, но исключать, что кому - то они известны нельзя.