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

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

Сначала было такое сообщение:
Dima TGennadiy 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 ферзей для построения алгоритмов для криптографии?

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

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

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

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

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

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

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

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

А могут быть и "сложения" решений. Ведь задача N ферзей и криптография построены на одном принципе: mod.

Aleksandr SharahovGennadiy UsovА почему бы не применить алгоритмы поиска решений задачи N ферзей для построения алгоритмов для криптографии?
о применении каких алгоритмов речь? ссылочки можно?Понимаю, читаете по диагонали другой страницы.

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

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

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

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

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

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

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

Чем-то эти цифры напоминают координаты ферзей на доске 1000х1000.

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

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

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

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

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

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

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

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

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

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

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

Поторопился:

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

Причем, полные перестановки!

А тут есть новая идея (наверное, уже она не раз рассматривалась):

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

Конечно, могут быть и повороты, и перемешивания, и что-то ещё.

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

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

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

Осталось найти алгоритм...

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

Ключ, пока, как и раньше :
два простых числа, работа по mod, пара чисел ключей, обмен закрытыми и открытыми ключами.
как написано в литературе.
И уже эти две пары чисел ключей ( а может быть больше) определяют (в зависимости от алгоритма):
- сочетания,
- перестановки,
- номер решения,
- и т.д.

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

Как-то мы уже говорили, что слона надо есть по кусочкам.

Новый алгоритм - это система, которую нужно последовательно и неспеша нагружать, а не валить на неё всю тяжесть содеяного всем миром.

Предлагаю очень простенький пример:
доска 13х13, на доске - ладейное решение, в клетках решения - буковки, которые по оси Х представляют собой слово, а по оси Y получается абракадабра:
а н ж в а р е я н х д с е

За сколько времени Вы найдете слово?

А далее будем усложнять примеры.

Dima TGennadiy UsovПредлагаю очень простенький пример:
доска 13х13, на доске - ладейное решение, в клетках решения - буковки, которые по оси Х представляют собой слово, а по оси Y получается абракадабра:
а н ж в а р е я н х д с е
За сколько времени Вы найдете слово?
А далее будем усложнять примеры.Не совсем понятна постановка, если 13 букв, то должны быть "абвгдеёжзиклм", откуда "нрхс" - непонятно. Доску надо побольше чтобы все буквы и цифры вошли.
Как понимаю идея шифра в том что одна буква подменяется другой, например а->e, б->к и т.д.На доске 13х13 стоит 13 ладей, и мы подряд по вертикалям вместо ладьи в клетку заносим очередную букву из слова.
После того как заменили все ладьи на буквы, считываем эти буквы подряд по каждой горизонтали.

Здесь нет подмены букв!

maytonЯ сразу скажу что мне такой шифр не интересен. В силу ладейных ограничений.А можно узнать эти ограничения?

Чтобы уже сейчас отбросить эти ладейные решения.

Кстати, всего ладейных решений на доске 13х13 - 6227020800 решения. (13!)

Одно из них приведено в примере.

maytonВ ключе из 13 символов и алфавита из 13 букв я могу создать комбинаций. Это есть область допустимых значений.

В вашем варианте с ладьями я могу сделать 13! (13 факториал) ключей. Даже не вычисляя это число я могу
сказать что 13 в степени 13 во много раз (многократно) превышает по ОДЗ фактриал.

Не беря во внимание прочие аспекты мне эта постановка уже не нравится и сама по себе ладейность как свойство ключа несет в себе уязвимость
к будущим атакам. Особенно на метод открытого текста где есть известные комбинации букв. =3,02875E+14. Это не серьёзная ставка!

Я предлагаю доску 40х40, где 8,15915E+47 ладейных решений или 815 915 283 247 898 000 000 000 000 000 000 000 000 000 000 000 (0 из-за ячейки).
Ваша ставка?

Если нужно, могу отправить очередную абракадабру из 40 букв.

alex55555Gennadiy UsovА тут есть новая идея (наверное, уже она не раз рассматривалась):
матрица NxN заполняется буквами алфавита в произвольном порядкеТакая идея рассматривалась уже сотни лет назад.
Брали некую книгу и в ней случайным образом выбирали страницу, а на странице - букву, потом индексы страницы и буквы вставляли в сообщение. И так для каждой буквы. У вас те же индексы, но ещё и вместе с книгой. То есть ваш шифр слабее, потому что переписывавшиеся сотни лет назад обычно не рассказывали никому, какую книгу они использовали.
Хотя есть отличие - вы задаёте сразу набор индексов. То есть решение для фигур даёт сразу N индексов. Но таких групп индексов можно предложить бесконечное количество. И лучше такие группы вообще не сводить к каким-то известным алгоритмам. То есть группу можно формировать случайным образом, тогда надёжность шифра ещё повысится. А у вас группа не случайная, что опять даёт некую гипотетическую возможность для нахождения ответа в полиномиальное время.Смысл заполнения всей доски буквами заключается в сокрытии основных букв: теперь надо рассматривать не N букв, a NxN букв. Тем более, если все буквы на доске ещё прошли через ключ.
Остаётся только путь через сочетания, а их очень много. И равно числу перестановок N! А наше перестановка для ладейного решения выбирается с помощью ключа (если получится).

Доска предварительно заполняется буквами случайным образом. Может быть упор делать на более и на менее встречающиеся буквы.

mayton Вы лучше расскажите практическое применение
с точки зрения use case.
Например. Тезисно.В существующей литературе по криптографии определены 3 основных этапа работ по передаче сообщений:
- подготовка ключей
- шифрование
- расшифровка.
Я сейчас рассматриваю этап 2 в той его части, где определяются блоки для передачи сообщений, и где пока не всё ясно.
Остальное - буду рассматривать позднее, когда разберусь с блоками, и как они взаимодействуют с ключами, какие могут быть сдвиги, повороты и прочее.

Мы с Вами договорились, что занимаюсь математикой. А она в алгоритме и в ключе. Так что всё нормально.
А протоколы передачи пусть остаются без изменения.