Find a random point along the line

Question

I am writing a small program that will help separate passwords (see explanation below)

I have code to convert text to int (text-ascii binary -> dec int)

therefore, in this case, the word "test" will be = 1952805748

Now the interesting part (password encoding)

Then I would take x1 = 1952805748 and y1 = 0

then I make up a random point where x2 = 7 and y2 = 142

this will result in a line between x1, y1 and x2, y2 (using Y = mx + B)

I need to find any random point along the line that these two points create (well name x3, y3)

If anyone has any ideas, I would like to hear them. I am trying to work out code that both points are ints (easier for everyone if we do not have huge decimal points for each number)

++ Why ++

the general idea is that if you had to split the password between the two sides, then one of the parties could determine the password based on the line they gave

if you use this method, they will get one point each and from this single point, it would be mathematically impossible to determine where the line corresponds to x (x =? y = 0) so that you can feel safe passing one set of points to your lawyer, and one to his wife.

they will do the math (entering it into the program), then they will get a number that will be decoded to say a password that can decrypt a file with your will or some other sensitive document that you would not want them to have access to help from another preseent

Answer 1

This algorithm is actually called " Shamir Secret Sharing " and is a really good way of breaking secrets. You can share arbitrarily large secrets that require how many people you want to bring together to restore the secret.

I would suggest you generalize a bit and go to a solution that allows you to indicate that N points need to be solved for a polynomial of degree N-1. You can use Lagrange Polynomials to solve this problem for you.

The Wikipedia pseudo-code, however, is only good for floats and needs a little change for use with integers. Check out my full python implementation if you need any ideas (and assuming this is generally useful).

He gives me this result:

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

Edit: After a year, I updated the implementation to work in the final field, which is necessary for its reliable protection. Hooray!

Answer 2

Other answers relate to your mathematical idea, but on the encryption front, I strongly recommend that you not try to develop your own encryption scheme.

If you want to encrypt something with two passwords, so both of them are necessary, it is much easier to do this: double-encrypt the file:

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

Encrypted2 is what you store. Drop Encrypted1 .

To decrypt, simply decrypt Encrypted2 with password 2 to get Encrypted1 , then decrypt Encrypted1 to return to plaintext.

Any password in itself is useless, as expected, and you do not need to develop encryption algorithms / code.

EDIT: As an even simpler solution, just create a very long password and give it to each half. For example, encrypt the file with the key “this is a very long password” and give your broad “this very” and your lawyer a “long password”. Obviously, you need to choose the right password so that to know half does not give any hints to others.

Answer 3

If your endpoints are (x1, y1) and (x2, y2) and you have a random number r int in the range from 0 to 1, the point along the line will be:

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

With your endpoints (1952805748.0) and (7.42) with a random value of 0.5 (halfway along the line) you will get:

 (976402877.5,21) 

which you can easily use as a midpoint. You can combine any coordinates if you need integers.

Following your comment (rephrasing):

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).

Given that your (x1, y1) was (1952805748.0), the one who knows this intersection of the x axis (since y = 0). It looks like you want the two points along the line not to be on the x axis. This means that one side should be provided with your randomly selected endpoint (7.42), and the other side should be your random point on the line (976402877,5,21) - none of these points should have a y value, equal to zero. This can be achieved by ensuring that the random value is in the range of 0.2 to 1.0, and not from 0.0 to 1.0 (assuming your y1 is always 0).

None of the parties could work out the intersection of the x axis with their one coordinate, but two combined combinations would provide you with this information.

In addition, in this case, rounding or ordinates are not suitable, you will have to compare them, for example (976402877.5,21), becoming (1952805755,42) [multiply by 2, which is the simplest integer].

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; 

Basically, we select some x between two xs (guaranteeing the correct domain and restrictions on your linear function, the correct range) and solve it for y. Not too complicated.

Answer 5

It would not be necessary to solve some unknown coordinate. It would just be necessary to connect your encrypted file to the sequential number generator. You have effectively reduced the complexity of coarse encryption forcing several times. Instead of each character equal to 1 out of ~ 94 (typical characters on a standard keyboard), you reduced it to 1 out of 10 (1 out of 11 if you allow decimal places).

I would advise against this method. As Skiter mentioned, just encrypt the file twice.