Форум ''Интернет и Право''

Дискредитирован ли алгоритм RSA?

На сайте "Интернет и Право" опубликована версия алгоритма быстрой факторизации целых чисел. Текст с описанием алгоритма доступен здесь http://www.internet-law.ru/intlaw/articles/urix-qfact.htm.

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

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

Если это так, то, как я понимаю это "пинцет" для существования некоторых так называемых "электронных валют".



Но у меня вопрос посложнее. Есть исследование в области математики, есть автор исследования. Можно ли зарегистрировать/запатентовать "открытие" и/или (как) проверить, "изобрел" ли это кто-то уже раньше? Просто так публиковать "находку" желания особого не возникает. Думается, что в итоге это может найти применение. А публиковать пока не хочется, так как с воровством и приписыванием авторства приходилось сталкиваться неоднократно.

Кратко - в принципе да, но это не в этот раздел.

Для справки, я студент 4 курса, мат-мех, УрГУ.

Статья - полный бред.

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

Во-вторых, автор претендует на решение НП-полной задачи. Специалист такой высокой квалификации обязан знать, что решение одной НП-полной задачи автоматически ведет к решению ВСЕХ НП-полных задач, среди которых есть не менее значительные результаты, чем факторизация больших чисел. Об этом автор не упоминает.

В-третьих, ключевая ошибка автора состоит в утверждении "если существует алгоритм для общего случая, то существует и алгоритм для частного случая, т.к. алгоритм для частного случая может быть легко получен путем замены вырожденных участков графа полного алгоритма простыми дугами". Это фантастических масштабов бред. Снятие ограничений в задаче - есть изменение задачи. И зачастую решения общей и частной задач вообще не имеют ничего общего.

Дальше не стал даже читать, ибо бред и бесполезная трата времени.

Ответ от автора:


Читаем http://www.cryptography.ru/db/msg.html?mid=1169815
Там есть такой "абздец":

На вопрос о том, является ли задача факторизации $\mathrm{NP}$-полной, можно ответить коротко и чисто формально: безусловно, нет. Напомним, что \mathrm{NP} --- это класс языков, или, иначе, задач распознавания (decision problem). Задача факторизации --- это задача поиска решения (search problem) и она, по определению, не может принадлежать классу $\mathrm{NP}$. Но тем не менее, немного изменив подход, вопрос о $\mathrm{NP}$-полноте можно поставить вполне корректно. Например, вместо задачи поиска сомножителей можно рассматривать задачу распознавания языка $L=\{(N,i,\sigma)\}$, где $(N,i,\sigma)\in L$, если $N$ --- составное целое число и $i$-ый бит его максимального множителя равен $\sigma$. Очевидно, что задача факторизации и задача распознавания языка $L$ полиномиально эквивалентны. Альтернативно, можно рассматривать функциональные классы сложностей, состоящие из задач поиска решения. Например, задача ВЫПОЛНИМОСТЬ ставится так: дана булева формула, требуется найти набор знач
 ений переменных, на котором эта формула принимает значение $1$. Функциональные аналоги классов сложностей, как правило, обозначают, добавляя букву F к соответствующему названию: $\mathrm{PF}$, $\mathrm{NPF}$ и т. п. Следует заметить, что соотношение между сложностью задач поиска решения и соответствующих задач распознавания представляет собой нетривиальную проблему. Ее исследование имеет большое значение для теории алгоритмов, теории сложности и математической криптографии. Но это --- тема для отдельного разговора.

Смотрите, как происходит введение ограничений и попадание на замыкание.
Прямо фраза за фразой с комментариями.

1. На вопрос о том, является ли задача факторизации $\mathrm{NP}$-полной, можно ответить коротко и чисто формально: безусловно, нет.
-  Правильно! Факторизация чисел, которые принадлежат бесконечному множеству.

2. Задача факторизации --- это задача поиска решения (search problem) и она, по определению, не может принадлежать классу $\mathrm{NP}$.
-  Абсолютно правильно!

3. Но тем не менее, немного изменив подход, вопрос о $\mathrm{NP}$-полноте можно поставить вполне корректно.
-  Внимание! Идет подготовка к ошибке введения ограничений. Как в карточных
   фокусах отвлекается внимание от самой ошибки подготовительными пасами.

4. Например, вместо задачи поиска сомножителей можно рассматривать задачу распознавания языка $L=\{(N,i,\sigma)\}$, где $(N,i,\sigma)\in L$, если $N$ --- составное целое число и $i$-ый бит его максимального множителя равен $\sigma$.
-  Происходит подмена описания свойств бесконечного множества чисел на описание
   свойств конечного множества алфавита языка. Т.е., делается попытка описать более
   мощную систему высказываний для бесконечного множества чисел в терминах такой
   же или менее мощной системы высказываний для конечного множества алфавита
   языка. Явное противоречие теореме Гёделя "о замыкании". Вот она ошибка! Языки
   с бесконечными алфавитами имеют другие свойства, нежели с конечными. Об этом
   уже сказано выше в этой же статье.

5. Очевидно, что задача факторизации и задача распознавания языка $L$ полиномиально эквивалентны.
-  Ошибка уже сделана. Получаем математический софизм, основанный на ошибке
   замыкания (IDEM PER IDEM). Дальнейшие рассуждения будут основаны на ошибке,
   не смотря на всю их внешнюю правдоподобность.

Глаз да глаз нужен за этими математиками!

Язык формальной математики менее мощный, чем Русский язык. Поэтому я и сделал
описание алгоритма на Русском языке. Чтобы избежать замыканий. Теперь, надеюсь,
и Реквием стал более понятен?

--
С уважением
Юрий

Антон Серго привел мой ответ по поводу NP и P. Извините, что сам не смог, давно не был, решал свои проблемы и пароль перестал приниматься.

Формальные языки, по определению, имеют конечный алфавит, представляются конечными автоматами с конечным числом состояний, с конечной таблицей переходов и конечной таблицей выводов. Поэтому не могут быть использованы для описания ВСЕХ возможные свойств объектов более мощного бесконечного множества. На этом и попадаются люди. Из "много" можно сделать "мало", а вот из "мало" сделать "много" не получится. Объективные законы сохранения работают. Уж извините за терминологию второй половины прошлого века, нас учили наукообразие терпеть ненавидеть. Тому, что наукообразие сродни мошенничеству и используется как правило для сокрытия ошибок или промахов. Мысли надо излагать понятным языком. В данном случае Русским.

Я, молодой человек, учился давно. На работах Хомского, Ахо, Дейкстры, Ульмана. Последние годы слежу за новинками только в силу необходимости. Когда Вас еще в проекте не существовало, будучи школьником старших классов я нашел элегантное решение дифференциальной игры "вор-полицейский". Это решение я привел в статье RUSSIAN FIREWALL (http://www.internet-law.ru/intlaw/articles/firewall.htm)

Посмотрел я Ваш комментарий и стало мне Вас жалко. Русский язык, как система высказываний, более мощный, чем формальный язык математики. Поэтому описание и сделано на Русском языке, дабы избежать замыканий. Но этому уже оказывается на мехмате "скудентов не учуть". Они уже не знают даже теоремы Гёделя. И про NP-полноту только наслышаны, а толком ничего о ней не знают. Суррогатное знание, так его нехорошо.

Ну не будешь же прямо в статье всем объяснять, что  описание алгоритма сделано таким специально, для серьезных людей и по правилам японского языка, когда все самое главное находится в конце, до которого еще дойти надо. Такую статью легко осилит человек взрослый, с большим опытом, самостоятельный, умеющий слышать и понимать высказывания других, а не только слушать самого себя. А хацкеры это как раз в своем большинстве желторотые птенцы, которые могут только чирикать и еще не знают почем фунт лиха. А значит, им такие вещи и читать не надо, чтоб не делали чего не надо. Они все равно вряд ли что поймут. Им терпения не должно хватать даже до конца дочитать статью. А когда поймут будет же поздно. Нагадить сильно не смогут.

Статью читал, но не понял. Ниасилил.

Поэтому спрошу со сталинской прямотой. Каков практический результат?  Алгоритм сработал? Число факторизовалось? Взлетел ваш самолёт? Если взлетел - наградить. Если нет - расстрелять.

Год назад тратилось двое суток на число из первого сообщения об RSA. Все делалось только в двоичной системе счисления, поэтому приходилось изгаляться всячески. И "загоны" искались методом, который мог давать ошибку. Поэтому получалось медленно и не очень надежно. И окончательный "загон" содержал более миллиона чисел, которые надо было проверить. Очень узенький "загончик" по сравнению с самим числом. Но достаточно большой для перебора.

Для этого алгоритма я еще не успел дописать программу. Есть тексты других рабочих вариантов. И заготовка для этого. Антон видел ход моей мысли, поэтому может подтвердить, что окончательно решение сформировалось неделю назад, когда я по его просьбе поднял старые версии. Дописать прогу я просто не успел.

Работать должно и очень быстро, поскольку я ничего нового не изобретал. Все это известные вещи. Самое главное это было применение цифровой голографии (муаровые решетки) для нахождения сразу всех делителей числа, а не сначала первого, потом второго и т.д.

Тяжелый случай.
Мне бы не хотелось делать резких заявлений, но по-моему, Вы сошли с ума.

Если Вы сомневаетесь в моей (или чьей-то еще) квалификации - пожалуйста, опубликуйте свои результаты в серьезном научном журнале (желательно, зарубежном) и вступите в дискуссию со всеми математиками мира. Надеюсь, хоть в чьей-то квалификации сомнений нет?

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

Попытаюсь еще раз образумить...

Вернитесь к самому началу и задайте себе вопрос: является ли задача поиска целых делителей заданного числа частным случаем задачи поиска действительных делителей?

Для Вас очевидно, что существует бесконечное число действительных делителей любого числа?
Для Вас очевидно, что нахождение некоторой пары действительных делителей ничего не дает в плане нахождения пары ЦЕЛЫХ делителей?

Наконец, если ответы на предыдущие два вопроса положительные, стало ли Вам понятно, что ваш алгоритм являет собой ничто иное, как полный перебор?

Если нет, то я уже ничем не смогу помочь...

Urix, поскольку великий русский язык, оказался настолько могуч, что осилить всю статью и я не смог, мои скромные попытки ограничились переводом на убогий, но зато понятный мне язык цифр только основополагающей теоремы и одного утверждения, входящего в ее доказательство. Наверное где-то при переводе что-то пошло не так, поскольку в переведенном тексте отмечен ряд расхождений с оригиналом. Ничего, если выравненные значения, или как вы их еще называете мантисcы я буду обозначать штрихом, как вы это сделали в одном месте статьи, но затем прочему-то перестали?
Итого дано:
P=5
Q=11 и соответственно
N=55, sqrt(N)=7,4161984870956629487113974408007, N²=3025
конечно точность расчетов можно и увеличить, но мне показалось, что пока можно ограничиться точностью стандартного калькулятора от Microsoft.
Положим a=10, а соответственно получим n=1 aⁿ=10 и aⁿ⁺¹=100
Если мой перевод был точен, то мы просто обязаны получить также следующее
P'=50
Q'=11
(sqrt(N))'= 74,161984870956629487113974408007
N^2'=30,25
Повторюсь, опять же, если мой перевод с великого и могучего позволил передать все нюансы, то как мне кажется условие вашей зверской теоремы выполняется
N^2' < N < (sqrt(N))' < aⁿ⁺¹
30,25 < 55 < 74,161984870956629487113974408007 < 100
Однако я не понимаю, каким образом хотя бы одно из чисел P, Q, P' или Q' (5, 11, 50, 11) попадает в интервал [N;aⁿ⁺¹ ] ([55;100]), как это постулируется в вашей теореме.
Более того при выводе теоремы прозвучал тезис:"Тогда мантисса числа sqrt(N) так же будет являться средним геометрическим пар мантисс чисел P, Q ..."
(sqrt(N))'=74,161984870956629487113974408007
sqrt(P' ^. Q')=sqrt(50 ^. 11)=sqrt(550)=23,452078799117147772828150567722
Как видите, мой перевод и здесь отличается от оригинала.
Был бы очень признателен, если бы вы смогли указать в каком месте ошибся переводчик.

Urix,

Рад что Вы снова с нами, а также тому, что Вы, судя по всему все в прежней форме.

Не влезая в Ваши математические рассуждения хочу заметить, что если Вы проставляете знак авторской охраны, то нужно это делать по правилам.
Или российским:
"Обладатель исключительных авторских прав для оповещения о своих правах вправе использовать знак охраны авторского права, который помещается на каждом экземпляре произведения и состоит из трех элементов;
     латинской буквы "С" в окружности: С;
     имени (наименования) обладателя исключительных авторских прав;
     года первого опубликования произведения." ( абз. 2 п. 1 ст. 9 ЗоАП);

Или международным:

"Любое Договаривающееся Государство, которое в соответствии со своим внутренним законодательством требует в качестве условия охраны авторского права соблюдение ... формальностей, ... будет считать эти условия выполненными ... если, начиная с первого выпуска этого произведения, все его экземпляры, выпущенные с разрешения автора или другого лица, обладающего авторским правом, будут иметь знак (с) с именем лица, обладающего авторским правом, и с указанием года его первого выпуска; знак, имя и год выпуска должны быть указаны таким способом и на таком месте, чтобы было ясно видно, что права автора охраняются." (п. 1 ст. III Всемирной конвенции об авторском праве).

Таким образом, не говоря о других мелочах употребление в знаке правовой охраны "1999-2002-2005" сводит на нет какую либо ценность этого знака. Более того, в некоторых странах указание неверной даты первого выпуска влечет серьезные последствия вплоть до утраты лицом авторских прав на объект.  

Так что будьте аккуратнее, а то одна ошибка может обесценить весь многолетний труд.

Угу. Например в низу каждой страницы данного форума: и ещё:

ННФ,

такое встречается в случаях когда можно говорить о ряде выпусков произведения, определенной периодичности и т.п., поскольку подразумевается группа объектов, обнародованных в разное время. И здесь есть определенные тонкости, но это уже должен сам человек, проставляющий знак охраны авторского права, соображать.

Когда же речь идет об отдельном самостоятельном объекте,этот вариант является некорректным.  К сожалению, у нас многие ЗоАП не читали, поэтому ошибки и допускают. Ну а указывать три даты - это вообще шедевр.

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

Я специально для рассмотрения частоты повторяемости условия теоремы добавил приложение №3 и поправил кое-какие неточности. И в  самом алгоритме это тоже нашло свое отражение в функции огораживания.

Частота получения случаев, удовлетворяющих теореме "о загоне", достаточно высока. Пусть из требующихся 1000 случаев первой части алгоритма для разложения 1000-разрядного числа встретится не 50%, а всего лишь 10%, то и тогда это будет уже 100 линеек с прозрачными участками. Это что-то вроде восстановления всей голограммы по ее фрагменту. Потери информации есть, но они незначительны. В данном случае потери проявляются в расширении "загонов". И потерями оказывается можно управлять. А значит можно управлять еще и скоростью работы самого алгоритма.

Вы взяли немного неудачный случай. В других системах счисления для Вашего случая условие теоремы может выполняться. Вечером поищу. Либо предложу другие случаи.

Основание системы счисления - это как свет определнной длины волны.

Николай Николавич! Имя Жан Поль Бельмондо с точки зрения привычных нам, русским, имен абсурдно. Не может быть в России у человека двух имен. Но это не означает, что такого не может быть во Франции.

В общем, это право автора на свое произведение, которое Вы пытаетесь у него ограничить.

Три даты стоят потому, что первая - это начало работы, вторая фиксирует некий качественный этап в работе, а третья - окончание работы. На каждом этапе производились публикации, которые автор не отделяет от окончательной версии. С точки зрения автора это разные части одного произведения.

Вас так устроит? А Закон?

Уважаемый тезка! Вашу теорию на язык математиики не Виталий перевел, а Дмитрий.

Давно не был, глаз отвык. Сразу не сориентировался. Тогда Дмитрий.

Да. А про ограничение количества дат в копирайте это Виталий.
Николай Николаевич развлекался.

А ННФ писал про самолеты, которые не летают.

Поэтому предположу, что ответ ННФ в действительности адресован мне. Если это не так, прошу прощения, Юрий.

Конечно, Вы можете ставить в конце работы любые значки, тем более, что в России это никак не будет ущемлять Ваших прав на территории нашей страны. Вопрос как раз о защите за рубежом, если Вы не будете соблюдать простых правил, которые указаны во Всемирной конвенции (я их уже привел Вам), то в определенной стране Вы можете оказаться без авторских прав. Судебная практика по миру на эту тему имеется. Это не я Вас прав лишаю (как Вы пишите), а может сделать закон другой страны.
Точка зрения автора (о которой Вы пишите) иностранный суд вряд ли волновать будет. Не выполнили правила - свободны.
Мне кажется проще вначале посмотреть закон, чем судиться потом.

2 All: держитесь в рамках темы (см. сабж.)!

Дмитрий! Я подобрал для Вас пример. В качестве делителей берутся простые 5 и 7. Как видно, мантиссы чисел (второй числовой столбик) удовлетворяют условию теоремы. И окончательные "загоны", особенно последний. 3,501<5<7<9,999.

Все дело в том, что если указанные в теореме числа не удовлетворяют условию теоремы "о загоне", то об их взаимном расположении говорить хотя и сложно, но можно. Это хорошо видно на "стеклянной" модели алгоритма. Но нужен был простой алгоритм, поэтому все остальные случаи просто отбрасываются и не рассматриваются.

Да, а 9999, 3501 и 1001 получаются потому, что я сразу исключаю тривиальные случаи 1 и N.

E2    1,00   9999
 P      7,00   7000
 M      5,92   5916
 Q      5,00   5000
 N    35,00   3501
N2 1225,00   1225
E1    1,00   1001
====================
3   9999,0   3501,0
2   999,90   350,10
1   99,990   35,010
0   9,9990   3,5010

SQRT((E2+1)*N)=5916,0797
SQRT(P*Q)=5916,0797
SQRT((E2+1)*N2)=3500

Что касается русского языка, то в нем очень важную роль играет слово "если".

P.S. Где-нибудь на следующей неделе я опубликую в приложении №4 программу, реализующую целочисленную часть алгоритма. Потом, где-то через месяц полный алгоритм уже в приложении №5. И в приложении №6 приведу алгоритм, вычислительная сложность которого для больших чисел является логарифмом от квадрата логарифма N. log2(log2(N)^2)=20 операций "огораживания" для 1000-разрядных чисел.

Или дать кому-то из молодых возможность отличиться самостоятельно? Ваше мнение, друзья?

Виталий!

Как там было? "Не учите меня жить, а лучше помогите материально".

Пожалуйста, если не сложно, скажите Антону, что точно должно стоять и он поправит. А то я ему шлю текст, он его потом переводит для сайта, а текст на экране расползается. Оба мы в это время материмся...

По-моему, нужно просто дать уважаемому Urix сообщение, зашифрованное алгоритмом RSA с хорошей длиной ключа, и попросить расшифровать его за сутки. :)

А там видно будет, кто здесь прав.

Как вам такой вариант?

Urix, я чрезвычайно рад, что вы все-таки сумели найти пример, подтверждающий вашу теорему. Хочу только обратить ваше внимание, что в математике нет такого понятия как доказывающий пример, зато есть понятие опровергающего примера. И неважно сколько подтверждающих примеров найдено, если известен хоть один опровергающий (см. мое предыдущее сообщение), все остальные пасы руками бесполезны - фокус провалился, теорема неверна. Поэтому повторюсь - мне очень нравится факторизовать число 55. Поэтому разрешите я в соответствии с вашим алгоритмом QFACT начну его факторизовать прямо здесь.

N=55 < 2⁶-1, следовательно  k=6  и i=0, 1,...5

i = 0 a₀=2

E2	1.00	4096
M	7.42	3797
N	55.00	3520
N2	3025.00	3025
E1	1.00	2048

Ура, условие теоремы выполнено M > N > N2, значит можно начинать загонять львов в загон [N;E2]

3520 - 4096
1760 - 2048
880 - 1024
440 - 512
220 - 256
110 - 128
55 - 64
27 - 32
13 - 16
6 - 8
3 - 4
1 - 2

Ooops (I did it again). Мы еще даже ружья не достали, а наши львы 5 и 11 похоже уже видали в гробу всякие загоны, муары, голограммы и Геделя и гуляют себе на свободе несмотря (или здесь все-таки не смотря) на все наши шаманские танцы с бубнами. Все Uriх, ну нафиг такую охоту, сожрут еще, охотьтесь один.

PS. Если вы обратили внимание я изменил порядок перебора i, начав с 0. Можете проверить на досуге, здесь нет никакой хитрости. Мне посто не хотелось утомлять других наблюдением того, как охотники сначала бестолково слоняются по заповедникам, где охота запрещена, а потом молча наблюдают за тем, как львы начинают разбегаться сначала по одному прежде чем рвануть из загона сразу всей стаей.

Дмитрий! Спасибо, что поправили.

Антон не даст соврать, у него есть одно из первых описаний, в котором еще присутствует теорема о проекциях чисел на интервале выравнивания. Совсем упустил ее из виду когда занимался сокращениями текста. В самой первой версии, которую никто не видел, было 11 лемм и 2 теоремы на 34 листах. Вот Вам и пример того, как проявляет себя суррогратное, упрощенное знание. Из-за потери нюансов получается нонсенс. Необходимое условие осталось, а вот достаточное утеряно.

Смысл теремы о проекциях в том, что если в границы "загона" не попадает число sqrt(a)*a^n, то берутся два загона [N:a*a^n],[N/sqrt(2):sqrt(a)*a^n] для sqrt(a)*a^n<N<E2 и [a^n:N],[sqrt(a)*a^n:sqrt(a)*N] для E1<N<sqrt(a)*a^n. В основе теоремы лежат свойства произведений sqrt(a)*sqrt(a)=a, sqrt(a)/sqrt(a)=1 и M*M=N*E=P*Q

Для рассматриваемого случая имеем
2^12/sqrt(2)=2896,30937...
N''=N'/sqrt(2)=2489,01586...

Соотвественно, дополнительные загоны получаются такими:
2489,0158 - 2896,3093
1244,5079 - 1448,1546
622,2539 - 724,0773
311,1269 - 362,0386
155,5634 - 181,0193
77,7817 - 90,5096
38,8908 - 45,2548
19,4454 - 22,6274
9,7227 - 11,3137
4,8613 - 5,6568
2,4306 - 2,8284
1,2153 - 1,4142

Как видно, целые делители четко попадают в дополнительные "загоны". Так что "львам" все равно деваться некуда. Они пойманы. И голограммы теперь уже на каждом углу можно встретить. И Гёделя пока никто не опроверг. И из "мало" нельзя сделать "много".

Сегодня вечером дополню описание алгоритма.

Юрий, я рад, что смог хоть чем-то оказаться полезным и буду с нетерпением ожидать внесения необходимых исправленний, но тем не менее хотел бы:
1. Обратить ваше внимание, что в рассмотренном случае для нахождения делителей числа 55 достаточно было перебрать всего 6 чисел, ни одно из которых с учетом новых дополнений так и не было отсеяно. Возможно в других случаях и будет достигнут какой-то выигрыш, но пока сама его возможность, не говоря уж о его величине, для меня увы не очевидны.
2. Торжественно заявить, что пока вы сами не произнесете здесь что-то типа: "Мамой клянусь, вот текст, в котором никто не забыт, и ничто не забыто!" - даже не взгляну на него больше.

ЗЫ. Да, совсем забыл, когда будете вносить изменения, обратите пожалуйста также внимание, что для рассмотренного случая отмечен также тот прискорбный факт
SQRT((E2)*N)=3797,09
SQRT(P*Q)=SQRT(2560*2816)=2684,95
Правда зато
SQRT((E1)*N)=2684,95, но тогда хотелось бы более четкого понимания, каковы точные границы интервалов.

Я этим алгоритмом занимась давно и он мне надоел хуже горькой редьки. Хочу побыстрее выловить всех bug-ов в описании и забыть о нем раз и навсегда. Есть вещи поинтереснее.

Тут Вы ошиблись. Перебрать надо не 6, а всего 3 числа: 2,3,5 до первого делителя. Тривиальные случаи рассматривать нет смысла. Учитывать их надо, но не тратить на них время. Отсев в алгоритме осуществляется на шаге №5. Или, что возможно будет лучше, делать компромисс между вычислениями "загонов" и проверками на делимость прямо в функции "огораживания". Поэтому, в приведенном мной примере первым числом, которое нужно проверить на делимость будет целое число 5, как попавшее в интервал 4,8613 - 5,6568, а в Вашем примере число 7, как попавшее в интервал 6-8. Но, 5 проверяется раньше, значит надо сделать всего одну проверку на делимость, а не три. Вот Вам уже и выигрыш, хотя и маленький, по числу проверок на делимость.

Что касается неочевидной малости затрат. Надеюсь, что Вы не сможете опровергнуть, что для 1000-разрядного числа надо построить всего 1000 или 2000 проекций "загонов" на числовую ось для основания 2. А учитывать надо всего лишь 500 или 1000, поскольку хотябы один делитель, если число не простое, обязательно меньше sqrt(N). Для других целых оснований, больших 2, проекций "загонов" на числовую ось будет меньше. Вот Вам и чисто логарифмическая зависимость. Я еще пока не встречал алгоритмов, которые давали бы логарифмические зависимости роста вычислительной сложности от роста числа N. Это первый. Существенный выигрыш должен проявлять себя на больших числах, поскольку операция "огораживания" сама по себе достаточно трудоемка. При росте числа оснований, совместные интервалы очень быстро уменьшаются в ширине и их количество сокращается, поэтому нет необходимости строить все проекции "загонов" для добавляемого основания. Это еще одно уменьшение вычислительных затрат.

P.S. Если Вы никогда ранее не видели датчиков положения, основанных на муаровых решетках с числом штрихов n/n+1, то советую Вам с ними ознакомиться. Многое прояснится и станет более понятным, поскольку это уже можно "пощупать руками".
P.P.S. Мамой клянусь - это выкручивание рук. Деструктивный подход. Я изложил идею, не нравится - не пользуйтесь. Я Вас не заставляю. Изложение идеи или даже сама идея может содержать ошибки, но это не основание для выкручивания рук.

Признаю, после того как до трех ночи заборы в пустыне строишь и не такого еще можно написать. :)

Дмитрий! Я поправил статью и выслал её Антону Серго. Смотрите, что получается в результате на Вашем примере.

E2                   4096
sqrt(2)*P            3982
sqrt(N)               3797
sqrt(2)*Q            3620
N                     3520
sqrt(2)*E1           2896
P                     2816
sqrt(2)*sqrt(N)      2685
Q                     2560
sqrt(2)*N            2489
E1                   2048


Окончательные границы "загонов", которые надо проецировать на числовую ось, будут такими: 2489-2897 и 3520-4096. 2897 вместо 2896 появилось из-за ошибок округления. Соответственно, из-за ошибок округления интервалы, содержащие сами делители, будут 5-5 и 10-11, а не 4-5 и 9-11.

sqrt(2) появилось потому, что 5*512=2560 и 11*256=2816, и степень "хвоста" 512*256=2^9*2^8=2^17 получается нечетной, в то время как степень "хвоста" sqrt(N)*sqrt(N) будет четной. Для получения точного равенства E2*N=M*M=P*Q приходится домножать P и Q на sqrt(2). Иначе не выполняется A<C<D<B, если A*B=C*D, A<B, C<D, A<C.

И еще. Вполне возможно, что алгоритм не работает для каких-то чисел. Но для некоторых он работает и мы с Вами в этом убедились. Я брал большее количество чисел и больших значений. Если не для всех чисел работает, тогда это означает, что класс чисел, которые могут быть использованы для RSA, сужен. Вопрос - на сколько. И тогда это всего лишь еще один "камень в огород" RSA, а не на его "могилу". Но и это уже хорошо. Значит, надо исследовать, для каких чисел этот алгоритм не работает и почему. Так что...

P.S. А я пока допишу программулину и буду сам смотреть, что и как.

Dia+ifXBs0WVwQUnh/WCUFJHuRRReeBAEABvEjf5S0lKlHGq5sQa01HDnAOYQjp274Dwc26uQZZ/PHFoVcTUdA==

Вот короткое сообщение, зашифрованное RSA с ключом 256 бит (использована библиотека криптокомпонентов для Delphi TPLockBox). Хотелось бы посмотреть, как уважаемый аффтар его расшифрует. Мне кажется это прежде всего в его интересах.
Я бы на месте Urixa сначала написал бы программу, потом бы уже обнародовал свои исследования. Истории о потерянных исходниках и злых желторотых "хацкеров", которые ждут-недождутся готовой программы доверия не прибавляют.

Я не занимаюсь взломами шифров и дешифрованием сообщений, которые так же могут быть зашифрованы и алгоритмом RSA.

Посему, представьте в двоичной, десятичной или шестнадцатиричной системах счисления число N, которое требует разложения на множители.

Urix, Вы нам скажите, какой длины число сможете реально за день разложить.
Мы же не знаем, какая у Вас система.

Зачем изобретать велосипед, когда все уже придумано до нас?!
Вот вам число:

Name:         RSA-640
Prize:        $20000
Digits:       193
Digit Sum:    806
31074182404900437213507500358885679300373460228427275457201619488
23206440518081504556346829671723286782437916272838033415471073108
501919548529007337724822783525742386454014691736602477652346609

Urix, когда факторизуете, результаты отправьте сюда - http://www.rsasecurity.com/rsalabs/node.asp?id=2095
Думаю что если вы правы и все так как вы говорите и пишете в своей статье, то вознаграждение в 20000 долларов США, покроет ваши затраты на факторизацию этого числа. Кстати судя по архивам этого форума, Вам уже предлагали принять участие в этом... Странно что имея на руках действующий алгоритм, вы до сих пор этого не сделали.


//Админ: [/b]"число" я разбил на три строки по техническим причинам и для удобства восприятия страницы.

2Admin:
А на сайте сейчас последняя версия статьи висит или предыдущая?

Вопрос к автору, но ИМХО, последняя из мной полученных.

однако автор молчит, и ничего не отвечает ни про текст статьи ни про числа. Никак не понять, или он факторизацией занят или с юристами спорит в сосдених ветках.
Urix Ау!!!

Вы бы нам сказали беретесь вы за факторизацию предложенного числа или нет? И последняя версия статьи висит на сайте или нет?

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

В любой из версий описания алгоритма приводятся все идеи алгоритма, поэтому не важно, какая версия сейчас висит на сайте. Основными идеями являются:
1. использование всех положительных действительных чисел, а не только целых или рациональных;
2. использование меры порядка на основе среднего геометрического;
3. использование различных позиционных систем счисления;
4. операция выравнивания чисел на интервал или ее аналог операция нормализации мантиссы;
5. использование муаровых решеток, период которых в логарифмических координатах задается основанием системы счисления;
6. вычисление сразу всех делителей числа за счет применения муаровых решеток.

Вот Вам реализация первой целочисленной части алгоритма. На выдачу выдаются те интервалы, где НЕ могут быть делители. Проверяйтесь. Все работает. Я брал более ста разных чисел.
В тексте первой части программы я оставил данные для 575-разрядного числа. Текст на экране разъезжается.

# cat qfact_step1.bc
#!/usr/bin/bc -q

define encl (n, a, m)
{
    auto a2,e0,e1,e2,n0,n1,m0,m1,l0,r0,l1,r1;

    a2 = a^2;
    e0 = 1; e2 = a2;
    while (e2 < n) { e0 = e2; e2 *= a2; }
    e1 = e0 * a;
    m0 = sqrt(n*e0^2);
    while (m0 > e2) { m0 /= a2; }
    if (m0 > e1) { m1 = m0;  m0 /= a; } else { m1 = m0*a; }
    if (n < e1) { n0 = n; n1 = n0 * a; } else { n1 = n; n0 = n1 / a; }
    if (m0 < n0) {
        l0 = n0; r0 = e1;
        l1 = n1; r1 = e2;
    } else {
        l0 = e0; r0 = n0;
        l1 = e1; r1 = n1;
    }
    print "\n===================================\n"
    while (l0 > 1) {
        if (l1 < m) {
            print l1,"-"
            if (r1 < m) { print r1,"\n" } else { print m,"\n"  }
        }
        if (l0 < m) {
            print l0,"-"
            if (r0 < m) { print r0,"\n" } else { print m,"\n" }
        }
        l0 /= a2; r0 /= a2;
        l1 /= a2; r1 /= a2;
    }
}

p = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
q = 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
n = p*q;
m = sqrt(n)

print "n  = ",n,"\n"
print "m  = ",m,"\n"
print "p  = ",p,"\n"
print "q  = ",q,"\n"

a = 2;
while (a < m) { a *= 2; }
for (a /= 2; a > 0; a /= 2) { ret = encl(n,a+1,m) }

quit

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

P = 3.98075...*10⁸⁶
Q = 4.72772...*10⁸⁶
N = P*Q = 1.881987...*10¹⁷³

Напомню, что исходное число для факторизации было 3.1074...*10¹⁹²

А, смотрю, что пока писал у вас текст сообщения слегка поменялся. Я так понимаю, что вы все-таки другое число факторизовали, которое уже было факторизовано?

Вы внимательно читайте то, что пишут другие. А то у меня создается впечатление, что Вы слышите только то, что хотите слушать. Односторонняя такая система.

Число, которое приведено в примере - это то число, о факторизации которого достаточно недавно было сообщено. И это не окончательный вариант программы, а только тот, который реализует лишь первую целочисленную часть алгоритма. Я его выложил для того, чтобы Вы могли проверять его работу на разных числах. А не для того, что бы Вы факторизовывали с его помощью большие числа. Для больших чисел нужна вторая рациональная часть алгоритма, которую я сейчас дописываю и отлаживаю.

P.S. Я понял, как надо оптимизировать метод. И, естественно, сразу нашел нижнюю границу вычислительных затрат на факторизацию. Затраты не могут быть меньше, чем 2*int(log2(2*int(log2(N))+1))+1 операций "огораживания".
P.P.S. Я это число использовал лишь как тест. Факторизовывал, естественно, гораздо меньшие числа, но не такие маленькие, как 5 и 11.

Господа, предлагаю не торопится - пусть Urix допишет программу, проверит ее, а потом факторизует предложенное RSA-640 число. Посмотрим сколько это займет времени.
Urix вопрос про версию статьи был связан с тем, что вы написали Dmitry (я это процитировал), что выслали исправленный вариант Антону, так как копии первой версии статьи у меня нет, я и спросил - Это тот самый исправленный вариант? То есть последний?.

Вообщем предлагаю подождать. Urix, вы хотя бы примерные сроки скажите, сколько это может занять времени?

Дело не в копиях. А в идеях. Идеи алгоритма и сам алгоритм не изменялись. Менялась лишь теоретическая часть.

P.S. Можете ждать, можете не ждать. Это Ваше право. Но на Вашем месте я бы проверил работу приведенной программы на малых числах, порядка 10-20-30 разрядов. Как это сделал Дмитрий. Мне тоже будет интересен результат. Возможно, Вы найдете случаи, когда алгоритм не работает.

Urix, дело действительно не в копиях - меня волнует одна вещь - это полное описание идеи или вы что то "забыли" (как было при проверках Дмитрия) - поэтому и спрашиваю.

Видите ли Юрий, впервыя с вашей идеей я столкнулся в конце 2002 года, и судя по всему, коренных изменений она не претерпела. Но у Вас по прежнему нет реализации, которая бы подтверждала вашу точку зрения. Я имею ввиду программу, которая за приемлимое время факторизовала бы числа, типа того, которое я вам предложил. Раз вы говорите, что дорабатываете программу, я предпочту подождать некоторое время, чтобы увидеть результаты. Надеюсь это будет все таки в обозримом будующем. И при моей жизни.

Urix, от чистого сердца желаю вам удачи. Хочется поскорее увидеть окончательную версию программы.

В 1999 году я обнаружил принципиальную очень тонкую ошибку в формализованном описании алгоритма, поэтому тогда мне стало понятно, что алгоритм долго не проживет. Ошибка связана с неявным наложением ограничений. В 2002 году только наметился подход, но еще не были ясны механизмы его реализации. Год назад я "топтался" на уровне 2-х суток для первого числа из сообщения об RSA из-за того, что неточно использовал свойства среднего геометрического, использовал только двоичную систему счисления, не использовал в явном виде обратное проецирование "загонов" на числовую ось, ошибочно делал поиск одного делителя, а не всех сразу. Из-за этого алгоритм работал с откатами, т.е. имел полиноминальные затраты с регулируемым порядком полинома. Хотя в идеале затраты должны били рости пропорционально корню квадратному от n=log2(N). Для 423-разрядного числа это было примерно 2^22 степени операций. Но сами операции были вычислительно достаточно сложными и старшие 100 разрядов находились за 2,5 часа, а с учетом откатов это должно было составлять около двух суток на процессоре CELERON-500.

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

Urix, есть ли какие-нибудь новости???

Не могу выбрать несколько спокойных часов, чтобы закончить программу.

Кроме того, мы с Антоном немного пообсуждали еще и нематематические проблемы вокруг этого дела.

В общем, ждем-с. Я и так уже сказал более, чем достаточно.

RSA-640     $20,000     Factored     November 2, 2005     F. Bahr et al.
:)

Интересны данные о затратахпроцессорного времени и календарном времени, потраченном на факторизацию. Но вообще то ничего неожиданного нет. Этой теме уже не один год, и я думаю что обсуждения будут продолжаться еще и не один год, в то время как другие люди будут заниматься факторизацией и получать деньги.

2Urix: Ну почему опять не на профильном форуме??????

Потому, что именно юристы придумывают RUSSIAN FIREWALL-s, из-за которых потом и начинаются всякие глюки. Программеры же и секьюрити осознают опасность.

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

Найден принципиальный способ подбора криптографических ключей

22 ноября 2006 года, 15:09
Текст: Владимир Парамонов

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

Как сообщает New Scientist Tech со ссылкой на заявления специалиста в области криптографии Жана-Пьера Зайферта, предложенная методика основана на эксплуатации особенностей системы прогнозирования ветвлений, которая реализована в компьютерных процессорах. Комплекс прогнозирования ветвлений представляет собой метод увеличения скорости вычислений, основанный на предугадывании дальнейших операций по результатам текущих действий.

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

Подобные методики взлома криптографических ключей существовали и раньше, однако они требовали длительных наблюдений. Теперь же исследователи утверждают, что при помощи новой технологии, получившей название "простой анализ прогнозирования ветвлений" (Simple Branch Prediction Analysis), 512-битный ключ можно подобрать за тысячные доли секунды. Для этого необходимо внедрить на компьютер жертвы специальный шпионский модуль, что можно сделать, например, через дыры в программном обеспечении.

Результаты своих изысканий исследователи намерены представить на конференции RSA Security в феврале следующего года.

http://security.compulenta.ru/295965/

Офф-топик, по-моему.  :-\ Вычисление секретных показателей асимметричной криптосистемы и взлом той или иной аппаратной реализации (пусть даже целого класса) -- далеко не одно и то же.

По-моему тоже (офф-топ). Угадывание результата работы random-функции и поиск уязвимостей в самом алгоритме шифрования — это разные темы.

Полный оффтоп. По сути и по смыслу.
Жалко плюсомета нет.

Если кому итнересно, то профессор будет выступать 8го числа. Думюа что результаты его доклада будут доступны в скором времени после окончания конференции. http://www.rsaconference.com/2007/US/ (http://www.rsaconference.com/2007/US/)

Можно устно раздать. Три плюса я овеществлю.