Форум ''Интернет и Право''
24 Октябрь 2018, 09:28:02 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
Новости: Форум "Интернет и Право" прекратил свою работу с 01 января 2013 г.
 
   Начало   Помощь Поиск Войти Регистрация  
В закладки:
Страниц: [1] 2 3 ... 6   Вниз
  Печать  
Автор Тема: Дискредитирован ли алгоритм RSA?  (Прочитано 29113 раз)
Антон Серго
Администратор
Internet-law team
*****
Офлайн Офлайн

Пол: Мужской
Сообщений: 7029


Юридическая фирма "Интернет и Право"


WWW E-mail
« : 15 Октябрь 2005, 21:50:43 »

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

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

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

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

Сообщений: 802


No comments


« Ответ #1 : 16 Октябрь 2005, 07:07:42 »

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

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

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

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


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



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

Пол: Мужской
Сообщений: 7029


Юридическая фирма "Интернет и Право"


WWW E-mail
« Ответ #2 : 16 Октябрь 2005, 12:32:52 »

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

Сообщений: 5


С любовью к ближнему


« Ответ #3 : 16 Октябрь 2005, 21:05:12 »

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

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

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

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

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

Дальше не стал даже читать, ибо бред и бесполезная трата времени.
Записан
Антон Серго
Администратор
Internet-law team
*****
Офлайн Офлайн

Пол: Мужской
Сообщений: 7029


Юридическая фирма "Интернет и Право"


WWW E-mail
« Ответ #4 : 17 Октябрь 2005, 00:35:42 »

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


Читаем 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). Дальнейшие рассуждения будут основаны на ошибке,
   не смотря на всю их внешнюю правдоподобность.

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

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

--
С уважением
Юрий
Записан
Urix
Гость


E-mail
« Ответ #5 : 17 Октябрь 2005, 01:41:32 »

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

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

Я, молодой человек, учился давно. На работах Хомского, Ахо, Дейкстры, Ульмана. Последние годы слежу за новинками только в силу необходимости. Когда Вас еще в проекте не существовало, будучи школьником старших классов я нашел элегантное решение дифференциальной игры "вор-полицейский". Это решение я привел в статье RUSSIAN FIREWALL

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

Ну не будешь же прямо в статье всем объяснять, что  описание алгоритма сделано таким специально, для серьезных людей и по правилам японского языка, когда все самое главное находится в конце, до которого еще дойти надо. Такую статью легко осилит человек взрослый, с большим опытом, самостоятельный, умеющий слышать и понимать высказывания других, а не только слушать самого себя. А хацкеры это как раз в своем большинстве желторотые птенцы, которые могут только чирикать и еще не знают почем фунт лиха. А значит, им такие вещи и читать не надо, чтоб не делали чего не надо. Они все равно вряд ли что поймут. Им терпения не должно хватать даже до конца дочитать статью. А когда поймут будет же поздно. Нагадить сильно не смогут.
« Последнее редактирование: 17 Октябрь 2005, 02:11:32 от Urix » Записан
Николай Николаевич Федотов
Ведущий
Internet-law team
*****
Офлайн Офлайн

Пол: Мужской
Сообщений: 4531


Мафия бессмертна, сыск вечен!

263087756
WWW E-mail
« Ответ #6 : 17 Октябрь 2005, 11:56:11 »

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

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

Форензика - компьютерная криминалистика: http://forensics.ru/
Urix
Гость


E-mail
« Ответ #7 : 17 Октябрь 2005, 16:52:53 »

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

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

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

Сообщений: 5


С любовью к ближнему


« Ответ #8 : 17 Октябрь 2005, 17:38:56 »

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

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

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

Сообщений: 5


С любовью к ближнему


« Ответ #9 : 17 Октябрь 2005, 17:56:18 »

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

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

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

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

Если нет, то я уже ничем не смогу помочь...
Записан
Страниц: [1] 2 3 ... 6   Вверх
  Печать  
 
Перейти в:  

Яндекс цитирования © Антон Серго, 1998-2018. Правовая информация.
Карта сайта "Интернет и Право" (internet-law.ru).
Rambler's Top100

Произвольная ссылка:

Powered by SMF 1.1.21 | SMF © 2011, Simple Machines