Saturday, June 28, 2008

Secret Splitting

An interesting way to use one-time pad encryption is Secret Splitting. We all know what sharing a secret is (people tend to have problems not to share secrets). The opposite of sharing secrets is to split them.

Suppose Charlie has a secret password or a safe combination he wants to share with someone in case of emergency. Wouldn't it be great if he could split his secret and give one share to Alice and one share to Bob? The secret could only be retrieved when both Alice and Bob agree on sharing their secret. Of course, cutting it simply in two and give each person half the secret would reveal already that part, so that would not be safe.

Well, there's a simple solution and it's called one-time pad. Secret Splitting is a special way of using one-time pad, since you don't send a secret message, and the key isn't destroyed. Here's how it goes: Charlie subtracts a random key, digit by digit, modulo 10 (without borrowing), from his safe combination. For instance, 4 - 6 = 8 because [1]4 - 6 = 8. He gives one share (they key) to Alice and one share (the result) to Bob.

Charlie's Combination      21 46 03 88
Random key (first share) - 25 01 77 61
                           -----------
Seults (second share)      06 45 36 27

Alice's share = 2501 7761
Bob's share   = 0645 3627

To retrieve the original combination, Alice and Bob just add their keys together, again modulo 10 (without carry). For instance 7 + 6 = 3 because 7 + 6 = [1]3. Of course, one could also split text by first converting the letters into digits (f.i. A=01, B=02 and so on through Z=26).

If the original is destroyed there is mathematically no way to retrieve the information without using both shares. There are some interesting applications for this system. It's for instance a secure alternative to keeping passwords in an envelop. It's also a clever way to share things with people who don't trust each other. Suppose grandpa, old and sick, splits the secret combination from the safe that contains his savings and gives each of his children one share of that secret. They can only get their hands on his money if they all agree (not that this will make grandpa live longer).

More about one-time pad and Secret Splitting at this webpage.

8 comments:

[WinAmp] said...

I suppose this could also be used for transferring what one could call "top priority messages" via two different couriers ?

Dirk Rijmenants said...

It is possible, but I would not recommend it for security reasons. Image you as a courier kidnapped and dragged into some deserted factory. And there's your courier partner, completely beaten up. And then the gorilla next to you: "and sir, do you have anything to tell to us?"

[WinAmp] said...

Well, that is if one considers "couriers" as actual people, but I guess I haven't really chosen the right word. Was thinking more like down the lines of sending the info via two different delivery methods.

Good point you've made, though ;)

Dirk Rijmenants said...

Oh I get it :) Sorry for that poor guy I sent out on his kamikaze mission :o Two different ways of relaying the message wouldn't be absolutely secure any more, but the attacker would have to find out how and when it was sent and this would require recources to monitor and intercept various means of communications. It would get very difficult to get hands on the message... but not impossible. You would almost need to have an Echelon-like SIGINT organisation to track down the two shares of the message.

[WinAmp] said...

Well, let's just say that for rather everyday situations (ok, who of us has to transmit communications via encrypted channels on a daily basis? :P) one could decrease the chance of the message being intercepted by sending one via SMS and other via snail mail, for example ? :P

Not meant to be some high security implementation of the method, just making tracing communications for a Joe Average a bit more difficult :P

Dirk Rijmenants said...

Well, not a bad idea, and I added it to the Secret Splitting article on my website ;-)

Amar said...

Hello

I Did not understand the subtraction , Could you please explain how it works.

Thank you

Dirk Rijmenants said...

Hi Amer,

Modulo 10 subtraction is quite simple. You never borrow nor carry. Some examples:
8-5=3 that's obvious
If the subtraction result would be less than 0, you then add 10:
2-4=8 bacause [1]2-4=8