Find random point along a line

Question

I'm writing a small program to help split passwords ( see below for explanation)

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

so in this case the word "test" would = 1952805748

Now the interesting part.(encoding the password)

I would then take x1 = 1952805748 and y1 = 0

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

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

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

If anyone has any ideas i would love to hear them. Im trying to work out the code that both points are ints ( its easier on everyone if we dont have huge decimal points behind each number)

++ The why ++

the general idea is that if you had to split up a password between two parties that one party could possibly figure out the password based on the string they were given

if you use this method they would get a single point each and from that single point it would be mathmaticly impossible to deterimine where the line meets x (x=? y =0) so you could feel safe handing one set of points to your lawyer and one to your wife

they would do the math (entering it into a program) then they would get a number that would be decode to say a password that could decrpt a file with your will or some other sensitve document that you wouldnt want them to access with out the other preseent

Answer 1

//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 pick some x between the two xs (guaranteeing the correct domain, and by constraints on your linear function, the correct range) and solve it for y. Not too difficult.

Answer 2

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

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

With your given endpoints (1952805748,0) and (7,42) with a random value 0.5 (halfway along the line), you end up with:

(976402877.5,21)

which you can easily work out as the midpoint. You can round any co-ordinates if you need integers.

Following your comment (paraphrased):

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), whoever has that know the intersection of the x-axis (since y = 0). It sounds like you want two points along the line where neither are on the x-axis. That means one party should be given your randomly chosen end-point (7,42) and the other party your random point on the line (976402877.5,21) - neither of those point should have a y-value of zero. This could be acheived by ensuring the random value was in the range .2 to 1.0 rather than 0.0 to 1.0 (assuming your y1 is always 0).

Neither of the parties could work out the x-axis intersect with their one co-ordinate but the two co-ordinates combined would give you that information.

Also, in that case, rounding or ordinates would not be suitable, you would have to map them, for example (976402877.5,21) becoming (1952805755,42) [multiply by 2, which is the simplest integer ratio].

Answer 3

Other answers have addressed your mathematical idea, but on the encryption front I would strongly recommend that you don't try to work out your own encryption scheme.

If you want to encrypt something with two passwords such that both are necessary, there's a much easier way to do it: encrypt the file twice:

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

Encrypted2 is what you store. Throw away Encrypted1.

To decrypt, just decrypt Encrypted2 with password 2 to get Encrypted1, then decrypt Encrypted1 to get back to the plaintext.

Either password on its own is useless, just as intended, and you don't need to work out any encryption algorithms/code.

EDIT: As an even simpler solution, just make up a really long password and give each party half of it. For instance, encrypt the file with the key "this is a very long password" and give your wide "this is a very" and your lawyer " long password". Obviously you need to choose the password appropriately so that knowing one half doesn't give any hints about the other.

Answer 4

One wouldn't have to solve for some unknown coordinate.. One would simply have to plug your encrypted file into a sequential number generator. You have effectively reduced the complexity of brute-forcing the encryption by several times. Instead of each character being 1 of ~94 (typable characters on a standard keyboard), you've reduced it to 1 in 10 (1 in 11 if you allow decimals).

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