Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 13   вперед  Ctrl
 Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
В разделе «Расстановка ферзей» все сообщения были на тему поиска алгоритмов определения решений задачи N ферзей. И не было сообщений на тему использования алгоритмов поиска решений для решения конкретных прикладных задач.

В данном разделе будет рассмотрена попытка применения таких алгоритмов в других задачах.
В начале было:
mayton
Чем планируешь занятся в отсутствие шахмат?
mayton
К примеру:
Криптография (актуально сейчас в эпоху bitcoins, darknet, tor).
......
Меня заинтересовало применение алгоритмов поиска решений задачи N ферзей к задачам криптографии.
Тем более, были такие сообщения.

Сначала было такое сообщение:
Dima T
Gennadiy Usov
Вариантов где-то 7,3787E+19.

Давай я за тебя посчитаю: если обрабатывать миллиард (1E+9) в секунду, то потребуется 7,3787E+10 секунд или 2000+ лет
Далее было такое сообщение
Gennadiy Usov
Можно рассмотреть такой вариант: доска 1001х1001.
Возможные случаи алгоритма МММ:
{{13, 11}, 7}, {13, {11, 7}}, и т.д. Всего 12 случаев.

Для случая {{11, 7}, 13} при применении алгоритма МММ с перемещением ферзей могут быть получены 1,0Е+330 решений
Для случая {{13, 7}, 11} при применении алгоритма МММ с перемещением ферзей могут быть получены 1,0Е+394 решений
Для случая {{13, 11}, 7} при применении алгоритма МММ с перемещением ферзей могут быть получены 1,0Е+372 решений

Конечны, эти количества решений интересны, и не более того. Быстродействие ЭВМ не позволяет определить все эти решения.
Найти конкретное решение из перечня, равного 1,0Е+330 решений, будет очень проблематично.
Поэтому возникает вопрос:

А почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?
2 янв 19, 20:02    [21777661]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Я если честно хотел вас вытащить из этого болота под названием Queen-Problem.

А вы принесли это болото в новый топик. Ну дела...
2 янв 19, 21:45    [21777697]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
Gennadiy Usov
А почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?


о применении каких алгоритмов речь? ссылочки можно?
2 янв 19, 23:29    [21777722]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Есть применение колоды из 53 игральных карт к перестановочному шифру. Но мне кажется что
ферзи имеют настолько много ограничений что сама их попытка применить к возможному
ключу вызывает подозрения в слабости ключа.

А что мы делаем с шифрами которые подозреваем на слабость? Мы их выбрасываем сразу. Не жалея.
2 янв 19, 23:40    [21777729]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
mayton
Я если честно хотел вас вытащить из этого болота под названием Queen-Problem.
А вы принесли это болото в новый топик. Ну дела...
Если влезать в какую-то задачу, то только для того, чтобы что-то поменять, внести что-то новое.

По криптографии куча литературы, разные мнения.
Только одно незыблемо: алгоритм и ключ.

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

mayton,
а что Вы хотели, когда вытаскивали меня из "болота", что надо что-то сделать в криптографии, "почистить" цифирки?

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

Пока я нашел алгоритм ( и не один), где очень много решений.
3 янв 19, 07:22    [21777787]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
mayton
Есть применение колоды из 53 игральных карт к перестановочному шифру. Но мне кажется что
ферзи имеют настолько много ограничений что сама их попытка применить к возможному
ключу вызывает подозрения в слабости ключа.
А что мы делаем с шифрами которые подозреваем на слабость? Мы их выбрасываем сразу. Не жалея.
Когда кажется....

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

А могут быть и "сложения" решений. Ведь задача N ферзей и криптография построены на одном принципе: mod.
3 янв 19, 07:27    [21777789]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
Aleksandr Sharahov
Gennadiy Usov
А почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?

о применении каких алгоритмов речь? ссылочки можно?
Понимаю, читаете по диагонали другой страницы.

Выше был указан алгоритм МММ, или по древнему - так называемое "фрактальное решение".
3 янв 19, 07:30    [21777790]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей.  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4242
Gennadiy Usov
Поэтому возникает вопрос:

А почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?
Правильно поставленный вопрос это пол ответа.
Системы с открытым ключом (на всякий случай, мы же их подразумеваем?) построены на функции, вычисление которой в обратную сторону затруднено.
Например, в RSA это умножение двух простых чисел. Что будет в данном случае выступать такой функцией?
3 янв 19, 09:12    [21777811]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 1730
mayton
Есть применение колоды из 53 игральных карт к перестановочному шифру.


даешь следующий AES на игральных картах )

Gennadiy Usov
Aleksandr Sharahov
о применении каких алгоритмов речь? ссылочки можно?


Понимаю, читаете по диагонали другой страницы.

Выше был указан алгоритм МММ, или по древнему - так называемое "фрактальное решение".


спросил, чтобы уточнить, как далеко все зашло )
3 янв 19, 10:42    [21777824]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Aleksandr Sharahov
Member

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

Пока я нашел алгоритм ( и не один), где очень много решений.


Это даже бредом не назвать. Ужас.


Gennadiy Usov
Ведь задача N ферзей и криптография построены на одном принципе: mod.


А ракетостроение - на принципе реактивного движения.

Стройте ракеты. Избавьте нас от новых алгоритмов.
3 янв 19, 10:58    [21777827]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
kealon(Ruslan)
Gennadiy Usov
Поэтому возникает вопрос:
А почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?
Правильно поставленный вопрос это пол ответа.
Системы с открытым ключом (на всякий случай, мы же их подразумеваем?) построены на функции, вычисление которой в обратную сторону затруднено.
Например, в RSA это умножение двух простых чисел. Что будет в данном случае выступать такой функцией?

Прекрасный вопрос!

А вот что говорят специалисты:
mayton
Алгоритм - это дорогой и сложный ресурс. Его долго разрабатывают. Доказывают. Тестируют.
Оптимизируют.
А ключ - дешевый ресурс. Я чисто для демонстрации сгенерировал ключик. И еще сделаю таких
тыщу. Мне не жалко.
Я - не специалист.
Вы хотите сразу получить и алгоритм, и ключик к нему? И всё это за одну неделю?

Давайте вместе поищем этот затерявшийся ключик.
3 янв 19, 13:02    [21777864]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Gennadiy Usov
mayton
Алгоритм - это дорогой и сложный ресурс. Его долго разрабатывают. Доказывают. Тестируют.
Оптимизируют.
А ключ - дешевый ресурс. Я чисто для демонстрации сгенерировал ключик. И еще сделаю таких
тыщу. Мне не жалко.
Я - не специалист.
Вы хотите сразу получить и алгоритм, и ключик к нему? И всё это за одну неделю?

Давайте вместе поищем этот затерявшийся ключик.

Я? Хочу? Я в этом форуме давно уже ничего не хочу.

В терминах Великой Британской империи - всё есть игра. И ради игры затеваются войны и интриги.
Ради мозговой игры я расставлял коней и ферзей на доске. Игры разума есть большинство
моих топиков здесь. Под ними - нет материального основания.

А вы - разве нет? Не ради игры расставляли ферзей?
3 янв 19, 14:37    [21777895]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 47076
Gennadiy Usov
Главное в алгоритме - получить как можно больше различных вариантов построения цифр, т.е. решений, чтобы кто-то не мог все эти решения перебрать за обозримое время. Запутать перестановками, сдвигами и т.д.

Это не главное. Главное это чтобы ключ генерировался за приемлемое время, а подбирался - за неприемлемое. У твоего алгоритма есть второе, но нет первого.
3 янв 19, 14:38    [21777896]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
mayton
Gennadiy Usov
Давайте вместе поищем этот затерявшийся ключик.

Я? Хочу? Я в этом форуме давно уже ничего не хочу.
В терминах Великой Британской империи - всё есть игра. И ради игры затеваются войны и интриги.
Ради мозговой игры я расставлял коней и ферзей на доске. Игры разума есть большинство
моих топиков здесь. Под ними - нет материального основания.
А вы - разве нет? Не ради игры расставляли ферзей?
Наверное, это есть игра - отыскивать новые алгоритмы, и если получится, то их применение.

А приглашение в поиске я сделал для всех, кто интересуется данной проблемой.

Кстати, нашел в эллиптических кривых такое выражение:

Чем-то эти цифры напоминают координаты ферзей на доске 1000х1000.
3 янв 19, 16:34    [21777936]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
alex55555
Member

Откуда:
Сообщений: 1711
Gennadiy Usov
Меня заинтересовало применение алгоритмов поиска решений задачи N ферзей к задачам криптографии.

Здесь уже накидали критерии для криптографических решений, вы их прочитали? Никакой не mod, а простая невозможность найти решение быстро. Поэтому для перехода к криптографии необходимо доказать две части - быстрое нахождение ключа для себя и долгое нахождение ключа со стороны "дяди". В общем случае это про классификацию алгоритмов - в полиномиальное время или в экспоненциальное находится решение. Где доказательство экспоненты для взлома и полинома для генерации?
3 янв 19, 17:20    [21777947]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
alex55555
Member

Откуда:
Сообщений: 1711
Gennadiy Usov
Давайте вместе поищем этот затерявшийся ключик.

Это занимательно, да, но времени убивается очень много. А время нам нужно.

Криптографию вы вполне можете придумать, но это даже не начало, это лишь взгляд в направлении. А далее вам её нужно внедрить. И вот это - смерть вашей идее. Я на 99.99% уверен, что внедрить вы не сможете (это вполне обычное явление). А вот те, кто может внедрить (находятся в нужном месте и в нужное время), какую лажу только не внедряют. Так уже где-то встречал криптографию на степенях полинома, которые нужно подобрать для зашифрованного сообщения, а выросло всё из банальной задачи аппроксимации набора точек полиномом. Там как раз доказали, что известными средствами степени полинома по данным зашифрованного сообщения подбирать очень долго.

Но вообще далее встанет теоретическая проблема - можно ли все алгоритмы привести к полиномиальным? В смысле исполняемым за полиномиальное время. Этот вопрос в математике пока открыт, но если закроют с ответом "да", то все ферзи и степени полиномов и простые числа сразу пойдут лесом.
3 янв 19, 17:29    [21777955]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Gennadiy Usov
Чем-то эти цифры напоминают координаты ферзей на доске 1000х1000.

Кто о чём а лысый - о расчёске! Давай уже.. избавляйся от старого балласта.
4 янв 19, 00:32    [21778130]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
kealon(Ruslan)
Gennadiy Usov
Поэтому возникает вопрос:
А почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?
Правильно поставленный вопрос это пол ответа.
Системы с открытым ключом (на всякий случай, мы же их подразумеваем?) построены на функции, вычисление которой в обратную сторону затруднено.
Например, в RSA это умножение двух простых чисел. Что будет в данном случае выступать такой функцией?
В данном случае, будет тоже умножение двух простых чисел.

Трудно придумать что-то более надежное, чем два простых числа, работа по mod, обмен закрытыми и открытыми ключами.
Далее шифрование сообщения с выравниванием, с разбивкой по блокам, c перепутыванием (можно что-то ещё придумать), причем шифруется каждая буква после предыдущих «доработок».
Естественно, расшифрование – всё наоборот.
(может быть я что-то ещё упустил, более современное и надежное).

В данном варианте текст сообщения расположен в виде одномерного массива, некоторой длины.

А если представить, что текст располагается в клетках доски NxN, в виде некоторого ферзевого или ладейного решения.
При этом «заносим» буквы со стороны Х, а читаем со стороны Y.

Наверное, такое дополнение к существующему шифрованию будет выглядеть более надежным.
4 янв 19, 13:56    [21778352]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
mayton
Я если честно хотел вас вытащить из этого болота под названием Queen-Problem.
А вы принесли это болото в новый топик. Ну дела...
Нашел возможность ответить на это сообщение.

Хотели вытащить из одного болота, а получилось, что попал ещё в более топкое…
mayton
Gennadiy Usov
Но если в этих темах есть что-то, где имеется математика + логика + код, то можно попробовать.
Правда, я ещё далек от современного построения ВТ.
В Криптографии достаточно много рассуждений математического толка.
И КМК их лучше понимают математики. Особенно в части криптоанализа.
Посмотрите
http://cryptowiki.net/index.php?title=Актуальные_направления_и_нерешенные_проблемы_криптографии
Есть что-нибудь что вас зацепило? Или интересно.

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

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

Поэтому первой идеей была рассмотрение алгоритма построение ферзевых, а затем ладейных решений на доске NxN.
Если рассматривать ладейные решения на доске NxN, то получаем N! (факториал) решений (перестановки вертикалей).
Для доски 170х170 имеем 7,2574E+306 решений.
Можно ещё увеличивать размер доски.
Будем считать, что размер доски, это размер блока при шифровании.

При определении ключа выбирается сочетание вертикалей конкретного ладейного решения в виде одного очень большого числа, которое потом раскладывается на биты (сочетания).
При этом может оказаться, что сочетание получается таким, что могут быть несколько вертикалей идти «без перемешивания».
Поэтому необходимо предварительное или дополнительное перемешивание.
Например, поворачиваем доску и применяем тот же массив сочетаний.
Можно делать несколько поворотов.
А есть ещё отображения относительно главных диагоналей.

А далее, заносим буквы текста (или что-то другое) в ячейки ладейного окончательного решения на доске по оси Х, а передаем сообщение по оси Y.
alex55555
Криптографию вы вполне можете придумать, но это даже не начало, это лишь взгляд в направлении. А далее вам её нужно внедрить. И вот это - смерть вашей идее. Я на 99.99% уверен, что внедрить вы не сможете (это вполне обычное явление).

Тут серьёзные фирмы осуществляют внедрение алгоритмов криптографии. Где уж мне. За мной – только общая идея, для души, как новая тропочка в движении.
5 янв 19, 01:04    [21778624]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
Поторопился:

не сочетания, а перестановки.

Причем, полные перестановки!
5 янв 19, 09:07    [21778661]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
А тут есть новая идея (наверное, уже она не раз рассматривалась):

матрица NxN заполняется буквами алфавита в произвольном порядке,
далее в эту матрицу на места ферзей решения задачи N ферзей ставятся буквы из сообщения,
далее вся эта матрица передается как шифрованная,
далее расшифровка.

Конечно, могут быть и повороты, и перемешивания, и что-то ещё.
5 янв 19, 09:12    [21778662]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
А тут ещё с точки зрения заполнения матрицы NxN сообщениями:
в матрицу записываем не 1 сообщение, а N сообщений.

В СУДОКУ рассматривалась матрица 9х9, и в ней имеется 9 решений по количеству цифр.

Оказывается, что можно построить и БОЛЬШУЮ СУДОКУ: 16х16, 25х25, и т.д., кратную квадрату натурального числа. И точно так же, имеем N квадратов, в которых располагаются объекты от 1 до N.
Таким образом, можно записать N сообщений и передавать их одной матрицей.

Осталось найти алгоритм...
5 янв 19, 09:22    [21778665]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Напомню что существуют правила Керхгофса при разработке криптосистем.

Один из пунктов говорит что генерация ключа не должна быть слишком сложной.
5 янв 19, 11:19    [21778685]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1391
mayton
Напомню что существуют правила Керхгофса при разработке криптосистем.
Один из пунктов говорит что генерация ключа не должна быть слишком сложной.
А в последних сообщениях почти нет ни слова о ключе.
Идет разработка алгоритма шифрования или подготовка массива к шифрованию.

Ключ, пока, как и раньше :
два простых числа, работа по mod, пара чисел ключей, обмен закрытыми и открытыми ключами.
как написано в литературе.
И уже эти две пары чисел ключей ( а может быть больше) определяют (в зависимости от алгоритма):
- сочетания,
- перестановки,
- номер решения,
- и т.д.
5 янв 19, 11:26    [21778687]     Ответить | Цитировать Сообщить модератору
 Re: Криптография и алгоритмы определения решений задачи N ферзей  [new]
mayton
Member

Откуда: loopback
Сообщений: 39224
Давайте вернёмся в начало.



Криптография решает следующие задачи:
- обеспечивает скрытность
- целостность
- аутентификацию.

В качестве основных методов использует:
- симметричое шифрование
- несимметричное
- оба метода ( в моём примере с сайтом дойче банка)
- расчёт контрольных сумм (хешей ) для сообщений (Md5, sha1)
- генерацию последовательности чисел
- генерацию псевдо случайных чисел
- сбор энтропии из внешних источников ( системные часы, мак-адрес, серийный номер железа)

Сертификация
- иерархическая (x509)
- горизонтальная (возм. Pgp)

Прочие сущности мира криптографии
- парольная фраза
- salt
- вектор инициализации
5 янв 19, 11:57    [21778695]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3 4 5 6 7 8 9 10 .. 13   вперед  Ctrl
Все форумы / Программирование Ответить