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

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 2

This algorithm is actually called "Shamir's Secret Sharing" and is a really good way of splitting up secrets. You can split up arbitrarily large secrets which require whichever number of people you want to come together to recover the secret.

I would suggest you generalize slightly and go for a solution that will let you specify that N points are required to solve for the N-1 degree polynomial. You can use Lagrange Polynomials to solve this for you.

The pseudo code at Wikipedia, however, is only good for floats, and needs to be modified slightly for use with integers. Check out my full python implementation if you want some ideas (and assuming it is at all helpful).

It gives me this output:

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

Edit: A year later I have updated the implementation to work within a finite field, which is required for it to be provably secure. Hooray!