Keyless Crypto: How Do Bob, Alice and Carol Share A Secret Message?

A problem with encryption, is when someone gets our encryption key. So can we do keyless crypto, where we do not need a key to decrypt an…
Photo by Silas Köhler on Unsplash

Keyless Crypto: How Do Bob, Alice and Carol Share A Secret Message?

Just imagine you could get perfect security, and not have to store encryption keys?

A problem with encryption, is when someone gets our encryption key. So can we do keyless crypto, where we do not need a key to decrypt an encrypted message? Well, yes, with secret shares we can, and where we cipher a message into secret shares, and only when these shares are brought back together can we recover the message.

For example, let’s say that Bob has two secret shares. He stores one share on his computer, and the other one in a Dropbox folder. Then only when they are brought together will the file be recovered. Anyone looking in his Dropbox folder, will not be able to decrypt it, as there is no key, and the only thing that will bring it back is the other share.

So, let’s take an example of having three shares, and give them to Bob, Alice and Carol. Then, only if they all come together, will the secret be revealed. In this case we will keep it simple and just use RSA for the shares.

With standard RSA, we create two prime numbers (p and q). and then calculate the modulus:

We then have Euler’s totient function:

We normally select an e value of 65,537, and then determine d with:

To encrypt, we take the message (M) and we use e and N:

and to decrypt:

With the secret shares, we take the decryption key (d) and split into three with:

Now we can create the shares with:

We can only recover the message then with:

This works because:

In this way, we basically split the decryption key (d) into three (d1, d2 and d3), and then encrypt the same message with each of these to give S1, S2 and S3. Bob, Alice and Carol then take the shares of S1, S2 and S3, respectively. To recover the message, we need to bring them all together and multiply them (mod N).

Coding

The coding is here:

A sample run [here]:

Message: hello
d1: 289905700160545867409203440309689271222627027045
d2: 200616125383676830751386273065097000030078399601
d3: 570032225049789181671077735954796106359771646143
===Shares===
Share1: 312640353343909714778998413583404177752294245438
Share2: 354239355689206362488564999073646819982738062274
Share2: 309021422821488954608815411658554796275362958537
Message=hello
p=727409898448263516029839
q=967136132507534946751867
d=357049654661059556746130251314290317150438895081
e=65537
N=703504395932952323085538892561323016260500959413
Private key (d,n)
Public key (e,n)
cipher=101415703737902830234727631710600449000334199306
decipher=hello

Conclusion

And there you go, keyless cryptography. In this case, though, we need to bring all the shares back together, so it is an All-or-Nothing (AON) method. If we lose one of the shares, we will not be able to recover the message.

If you are interested, I have other examples here:

  • Shamir’s Secret Sharing (Python). Secret shares.
  • Shamir’s Secret Sharing (creator). Shamir.
  • Shamir’s Secret Sharing (decrypt). Shamir.
  • ECC threshold encrytion. ECC.
  • (t,n)-threshold Boneh-Lynn-Shacham (BLS) signature scheme. TBLS. Create n shares and where we need to get t back to verify the signature.
  • Shamir Secret Shares with Go. SSS. Creating Secret Shares.