Найти случайную точку вдоль линии

Question

Я пишу небольшую программу для разделения паролей (объяснение см. Ниже)

У меня есть код для преобразования текста в int (text-ascii binary -> dec int)

так что в этом случае слово «тест» будет = 1952805748

Теперь интересная часть. (Кодировка пароля)

Я бы тогда взял x1 = 1952805748 и y1 = 0

тогда я составляю случайную точку, где x2 = 7 и y2 = 142

это нарисует линию между x1, y1 и x2, y2 (используя Y = mx + B)

Мне нужно, как найти любую случайную точку вдоль линии, которую создают эти две точки (ну, назовите это x3, y3)

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

++ Почему + ++

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

если вы воспользуетесь этим методом, они получат по одной точке каждый, и из этой единственной точки будет математически невозможно определить, где линия пересекается с x (x =? Y = 0) чтобы вы чувствовали себя в безопасности, передавая один набор очков своему адвокату, а другой - своей жене

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

Answer 1

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

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

Plaintext -> Encrypted1 (with password 1)
Encrypted1 -> Encrypted2 (with password 2)

Encrypted2 это то, что вы храните. Выбрось Encrypted1.

Чтобы расшифровать, просто расшифруйте Encrypted2 с паролем 2, чтобы получить Encrypted1, затем расшифруйте Encrypted1, чтобы вернуться к открытому тексту.

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

РЕДАКТИРОВАТЬ: В качестве еще более простого решения просто придумайте действительно длинный пароль и дайте каждой стороне половину его. Например, зашифруйте файл с помощью ключа «это очень длинный пароль» и укажите широкому «это очень», а своему юристу «длинный пароль». Очевидно, вам нужно правильно выбрать пароль, чтобы знание одной половины не давало подсказок о другой.

Answer 2

Этот алгоритм на самом деле называется « Shamir's Secret Sharing » и является действительно хорошим способом разделения секретов. Вы можете разделить произвольно большие секреты, которые требуют от любого количества людей, которых вы хотите собрать, чтобы восстановить секрет.

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

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

Это дает мне такой вывод:

1 -- 50383220533284199945706810754936311181214547134666382315016772033813961148457676
2 -- 125723425896904546349739165166331731432281836699962161072279259011758052396215820
3 -- 235794378436564714387676526976517945151880763730707233042654663244625708155520494
'This is my super secret password.'

Редактировать: Год спустя я обновил реализацию, чтобы она работала в рамках конечного поля, которое требуется для обеспечения надежной защиты. Ура!

Answer 3

Если ваши конечные точки (x1, y1) и (x2, y2) и у вас есть случайное число r в диапазоне от 0 до 1, точка вдоль линии будет:

(x1+(x2-x1)*r,y1+(y2-y1)*r)

С заданными вами конечными точками (1952805748,0) и (7,42) со случайным значением 0,5 (на полпути вдоль линии) вы получите:

(976402877.5,21)

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

После вашего комментария (перефразировано):

I may not have explained this properly: one person would be given (x1,y1) different person would be given (x3,y3). At no point would a person be able to take a single point and figure out where the line crosses x (N,0).

Учитывая, что ваш (x1, y1) был (1952805748,0), тот, кто имеет это, знает пересечение оси x (так как y = 0). Звучит так, будто вы хотите две точки вдоль линии, где ни одна не находится на оси х. Это означает, что одна сторона должна получить вашу случайно выбранную конечную точку (7,42), а другая - вашу случайную точку на линии (976402877.5,21) - ни одна из этих точек не должна иметь значение y, равное нулю. Этого можно добиться, убедившись, что случайное значение было в диапазоне от 0,2 до 1,0, а не от 0,0 до 1,0 (при условии, что ваш y1 всегда равен 0).

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

Кроме того, в этом случае округление или ордината не будут подходящими, вам придется сопоставить их, например (976402877.5,21), став (1952805755,42) [умножить на 2, что является простейшим целочисленным соотношением].

Answer 4

//Assume x1, x2, and m, b exist as ints
Random r = new Random();
int x3 = r.Next(Math.Min(x1, x2), Math.Max(x1, x2));
int y3 = m * x3 + b;

По сути, мы выбираем некоторый x между двумя x (гарантируя правильную область и ограничения вашей линейной функции, правильный диапазон) и решаем его для y. Не слишком сложно.

Answer 5

Нет необходимости искать неизвестную координату. Просто нужно подключить зашифрованный файл к генератору последовательных чисел. Вы существенно сократили сложность шифрования в несколько раз. Вместо того, чтобы каждый символ был 1 из ~ 94 (набираемые символы на стандартной клавиатуре), вы уменьшили его до 1 к 10 (1 к 11, если вы разрешаете десятичные дроби).

Я бы советовал против этого метода. Как упоминал Скитер, просто зашифруйте файл дважды.