沿着一条直线找到随机点

Question

沿着一条直线找到随机点

c#.netencryptiongeometry

4

我正在编写一个小程序来帮助拆分密码（见下文解释）

我有代码将文本转换为整数（文本-ASCII二进制 -> 十进制整数）

所以在这种情况下，单词“test”将等于1952805748

现在是有趣的部分。（加密密码）

然后我会取x1 = 1952805748和y1 = 0

然后我会随意选取一个点，其中x2 = 7，y2 = 142

这将在x1，y1和x2，y2之间绘制一条线（使用Y = mx + B）

我需要如何找到这两个点创建的线上的任意随机点（我们称之为x3，y3）

如果有人有任何想法，我很乐意听取他们的意见。我正在尝试编写代码，使这两个点都是整数（如果每个数字后面没有巨大的小数点，则对所有人都更容易）

++ 为什么 ++

一般的想法是，如果您必须在两个参与者之间拆分密码，那么一个参与者可能会根据他们得到的字符串推断出密码

如果您使用此方法，他们将获得单个点，并且从该单个点开始，根据数学上的不可能确定线在哪里与x相交（x =？y = 0）因此，您可以放心地将一组点交给您的律师和另一组点交给您的妻子

他们将进行数学计算（输入到程序中），然后他们将获得一个数字，该数字将被解码为可以解密具有您的遗嘱或其他敏感文件的密码，这些文件如果没有另一个人在场，您不希望他们访问。

- Crash893

5个回答

6

这个算法实际上被称为“Shamir的秘密共享”，是一种非常好的分割秘密的方法。您可以分割任意大的秘密，需要任意数量的人来一起恢复秘密。

我建议您略微概括，并选择一种解决方案，使您可以指定需要N个点来解决N-1次多项式。您可以使用拉格朗日插值法来解决这个问题。

然而，维基百科上的伪代码仅适用于浮点数，并且需要稍作修改才能与整数一起使用。如果您想要一些想法（并且假设它有所帮助），请查看我的完整Python实现。

它给我这个输出：

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

编辑：一年后，我已更新实现方式以在有限域内运行，这是确保安全性所必需的。太好了！

- Mike Boers

我很高兴知道它有一个实际的名称。我会看看是否可以在C#中实现它。 - Crash893

4

如果你的端点是（x1，y1）和（x2，y2），并且你有一个在0到1范围内的随机数r，则沿着该线的点将是：

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

使用给定的端点 (1952805748,0) 和 (7,42)，以及随机值 0.5（在线段的中间位置），您得到以下结果：

(976402877.5,21)

可以轻松计算出中点，您可以四舍五入任何坐标以获得整数。

根据您的评论（改写）：

我可能没有恰当地解释清楚：一个人会被给予（x1，y1），另一个人会被给予（x3，y3）。任何时候，一个人都无法仅凭一个点确定直线与x（N，0）相交的位置。

鉴于您的（x1，y1）是（1952805748，0），拥有该坐标的人知道x轴的交点（因为y = 0）。听起来您想要沿着该直线两个不在x轴上的点。这意味着一方应该得到您随机选择的终点（7,42），而另一方应该得到您在线上的随机点（976402877.5,21） - 这两个点都不应该具有零的y值。这可以通过确保随机值处于.2到1.0的范围而不是0.0到1.0的范围（假设您的y1始终为0）来实现。

两个人都无法计算出与他们的坐标轴相交的x轴，但是两个坐标组合起来将给出您该信息。

此外，在这种情况下，舍入或坐标不适合，您必须进行映射，例如（976402877.5,21）变为（1952805755,42）[乘以2，这是最简单的整数比率]。

- Pax

我可能没有解释清楚。1）一个人会得到x1y1，另一个人会得到x3y3，在任何时候，一个人都不能仅凭一个点就能确定直线与x轴的交点（x=任意值，y=0）。P3可以在P1和P2之间，也可以在整条线上的任何位置。 - Crash893

请查看更新。基本上，给出的两个点都不应该具有y=0。 - paxdiablo

2

//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的值。这并不太难。

- Patrick

这看起来可能是答案。等我回到工作岗位时，我会尝试一下。 - Crash893

除了它选择一个整数x值并“假设”它会产生一个整数y值之外，我不认为这将是准确的。 - Jon Skeet

@jon skeet：如果m/x3/b都是整数，乘法和加法的性质保证这将始终产生一个整数。 - Steven Evers

@SnOrfus，我们真的没有理由相信m和b是整数。生成m的计算很可能会产生小数结果。我们可以四舍五入这些值，但这可能会对解密器造成问题。 - Karl

我知道如何找到斜率，但我怎么找到B呢？ - Crash893

显示剩余3条评论

1

不需要解决某个未知坐标..只需将加密文件插入顺序号生成器即可。您已经将破解加密的复杂性有效地降低了数倍。每个字符不再是 ~94（标准键盘上可输入的字符之一）中的1个，而是变成了10中的1个（如果允许小数，则为11中的1个）。

我建议不要使用这种方法。正如Skeeter所提到的，只需将文件加密两次即可。

- Boo

我觉得你误解了这个程序找到的"Number"会解码成ASCII文本，作为密码使用。所以密码的复杂性保持不变。（所有95个可打印字符）我不明白这种方式与使用普通密码有何区别。 - Crash893

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jon Skeet · Accepted Answer

其他回答已经讨论了你的数学想法，但在加密方面，我强烈建议你不要尝试自己设计加密方案。

如果你想使用两个密码进行加密，以便两者都是必需的，有一种更简单的方法：对文件加密两次。

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

Encrypted2是您存储的内容。丢弃Encrypted1。

要解密，只需使用密码2解密Encrypted2以获取Encrypted1，然后解密Encrypted1以返回明文。

任何一个密码单独使用都是无用的，正如预期的那样，而且您不需要计算任何加密算法/代码。

编辑：作为一种更简单的解决方案，只需编写一个非常长的密码并将其分给每个参与者的一半。例如，使用键“this is a very long password”加密文件，并将“this is a very”部分提供给您的配偶，“ long password”部分提供给您的律师。显然，您需要适当地选择密码，以便知道其中一个部分不会给出有关另一个部分的任何提示。