5 ms·

Shamir's Secret Sharing

66 points by simplect 10y ago

deleted 10y ago
[deleted]
ryan-c 10y ago
Some software using this algorithm: http://www.digital-scurf.org/software/libgfshare http://www.digital-scurf.org/software/libgfshare https://github.com/ryancdotorg/threshcrypt https://github.com/ryancdotorg/threshcrypt (uses libgfshare, written by me - handles large files by splitting a key into shares and encrypting them with password-derived keys) https://github.com/amper5and/secrets.js/ https://github.com/amper5and/secrets.js/ http://passguardian.com/ http://passguardian.com/ (uses secrets.js) http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/
jpgvm 10y ago
Super simple implementation in C: https://github.com/duncanburke/libshamir https://github.com/duncanburke/libshamir
Xcelerate 10y ago
I've been wanting to use this in combination with Rabin's Information Dispersal algorithm to create an autonomous distributed file storage system. You would have redundancy, but redundancy in a way that you only require k of n "pieces" to recover your original file (or data object). This is pretty cool, because you don't need to have 10 copies of a 1 GB file (10 GB total) spread about the web in order to achieve a high probability of being able to recover your data.
- dlgeek 10y ago
  When you encode information with Shamir Secret Sharing, each share is actually bigger than the original secret. The computation requirements also don't scale very well. What you want is called Erasure Coding. (https://en.wikipedia.org/wiki/Erasure_code https://en.wikipedia.org/wiki/Erasure_code)
  - heinrich5991 10y ago
    >each share is actually bigger than the original secret This is not true according to the Wikipedia article: Shamir's secret sharing is minimal, i.e. the size of each piece does not exceed the size of the original data. https://en.wikipedia.org/w/index.php?title=Shamir%27s_Secret_Sharing&oldid=717238585#Properties https://en.wikipedia.org/w/index.php?title=Shamir%27s_Secret....
- lolidaisuki 10y ago
  Sounds a lot like Tahoe-LAFS[1]. [1]: https://tahoe-lafs.org/trac/tahoe-lafs https://tahoe-lafs.org/trac/tahoe-lafs
ed0wolf 10y ago
This reminds me of the Simpsons episode with the Flying Hellfish: https://en.wikipedia.org/wiki/Raging_Abe_Simpson_and_His_Grumbling_Grandson_in_%22The_Curse_of_the_Flying_Hellfish%22 https://en.wikipedia.org/wiki/Raging_Abe_Simpson_and_His_Gru...
j2kun 10y ago
Vault uses this technique https://www.vaultproject.io/ https://www.vaultproject.io/
- simplect 10y ago
  I came across the algorithm while going through the project. One interesting feature of the technique is that it is possible to set the threshold less that total number of parts to recreate the secret and it is used by the software.
ianpurton 10y ago
The wikipedia link gets mathematical very quickly. With Shamir's secret sharing you can take a file and split it for example into 3 parts. Only 2 parts would need to be combined to re-create the original. This would be 2 of 3 in Bitcoin parlance.
vecter 10y ago
I learned this from reading the original paper [0], which is only two pages and is easily accessible to anyone with a high school level understanding of math. [0] http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf
homero 10y ago
That's how I protect my bitcoin
Rygu 10y ago
Open source implementations available on GitHub: Python - https://github.com/blockstack/secret-sharing https://github.com/blockstack/secret-sharing PHP - https://github.com/mathieuk/secretsharer https://github.com/mathieuk/secretsharer Node - https://github.com/amper5and/secrets.js https://github.com/amper5and/secrets.js Go - https://github.com/codahale/sss https://github.com/codahale/sss C - https://github.com/fletcher/c-sss https://github.com/fletcher/c-sss Ruby - https://github.com/lian/shamir-secret-sharing https://github.com/lian/shamir-secret-sharing Java - https://github.com/timtiemens/secretshare https://github.com/timtiemens/secretshare Rust - https://github.com/sellibitze/secretshare https://github.com/sellibitze/secretshare
- tehrei 10y ago
  You should be a bit careful with implementations and keep in mind that you can't split a number larger than the prime you've picked. I've seen people go "oh I'll just split an N-byte value into M * N-byte values, splitting each byte separately with the largest prime < 256, surely the loss of a few values per byte won't be of consequence...". It might not be in your case, but you need to be aware of that.
yoo1I 10y ago
I run a small operation providing websites/online storage/email for a couple of friends and small businesses, and I use this as recovery solution to a master key. I distributed the encrypted very big master key, full system documentation and a part of the decryption key to the master key to a couple of people including a public notary. This way, should it ever get necessary, it will be possible for them to access my encrypted files. Say I get hit by a bus or something similar. Thank you, Shamir!
jacobkg 10y ago
What's especially cool about this technique is that unlike most crypto proofs it does not assume the existence of one-way functions (none have been found yet) nor does it require a computationally bounded adversary. Instead this technique is information theoretically secure so even an adversary with the ability to perform exponentially slow algorithms instantly could not find the secret. All this in a two page paper that only required high school math! PS - The "Shamir" who found this technique is the S in RSA
moserware 10y ago
I created a C# implementation and explained how the math works in http://www.moserware.com/2011/11/life-death-and-splitting-secrets.html http://www.moserware.com/2011/11/life-death-and-splitting-se...

66 points by simplect 10y ago

deleted 10y ago

[deleted]

Some software using this algorithm: http://www.digital-scurf.org/software/libgfshare http://www.digital-scurf.org/software/libgfshare https://github.com/ryancdotorg/threshcrypt https://github.com/ryancdotorg/threshcrypt (uses libgfshare, written by me - handles large files by splitting a key into shares and encrypting them with password-derived keys) https://github.com/amper5and/secrets.js/ https://github.com/amper5and/secrets.js/ http://passguardian.com/ http://passguardian.com/ (uses secrets.js) http://point-at-infinity.org/ssss/ http://point-at-infinity.org/ssss/

jpgvm 10y ago

Super simple implementation in C: https://github.com/duncanburke/libshamir https://github.com/duncanburke/libshamir

Xcelerate 10y ago

I've been wanting to use this in combination with Rabin's Information Dispersal algorithm to create an autonomous distributed file storage system. You would have redundancy, but redundancy in a way that you only require k of n "pieces" to recover your original file (or data object). This is pretty cool, because you don't need to have 10 copies of a 1 GB file (10 GB total) spread about the web in order to achieve a high probability of being able to recover your data.

dlgeek 10y ago
When you encode information with Shamir Secret Sharing, each share is actually bigger than the original secret. The computation requirements also don't scale very well. What you want is called Erasure Coding. (https://en.wikipedia.org/wiki/Erasure_code https://en.wikipedia.org/wiki/Erasure_code)
- heinrich5991 10y ago
  >each share is actually bigger than the original secret This is not true according to the Wikipedia article: Shamir's secret sharing is minimal, i.e. the size of each piece does not exceed the size of the original data. https://en.wikipedia.org/w/index.php?title=Shamir%27s_Secret_Sharing&oldid=717238585#Properties https://en.wikipedia.org/w/index.php?title=Shamir%27s_Secret....
lolidaisuki 10y ago
Sounds a lot like Tahoe-LAFS[1]. [1]: https://tahoe-lafs.org/trac/tahoe-lafs https://tahoe-lafs.org/trac/tahoe-lafs

ed0wolf 10y ago

This reminds me of the Simpsons episode with the Flying Hellfish: https://en.wikipedia.org/wiki/Raging_Abe_Simpson_and_His_Grumbling_Grandson_in_%22The_Curse_of_the_Flying_Hellfish%22 https://en.wikipedia.org/wiki/Raging_Abe_Simpson_and_His_Gru...

j2kun 10y ago

Vault uses this technique https://www.vaultproject.io/ https://www.vaultproject.io/

simplect 10y ago
I came across the algorithm while going through the project. One interesting feature of the technique is that it is possible to set the threshold less that total number of parts to recreate the secret and it is used by the software.

ianpurton 10y ago

The wikipedia link gets mathematical very quickly. With Shamir's secret sharing you can take a file and split it for example into 3 parts. Only 2 parts would need to be combined to re-create the original. This would be 2 of 3 in Bitcoin parlance.

vecter 10y ago

I learned this from reading the original paper [0], which is only two pages and is easily accessible to anyone with a high school level understanding of math. [0] http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf http://cs.jhu.edu/~sdoshi/crypto/papers/shamirturing.pdf

homero 10y ago

That's how I protect my bitcoin

Rygu 10y ago

Open source implementations available on GitHub: Python - https://github.com/blockstack/secret-sharing https://github.com/blockstack/secret-sharing PHP - https://github.com/mathieuk/secretsharer https://github.com/mathieuk/secretsharer Node - https://github.com/amper5and/secrets.js https://github.com/amper5and/secrets.js Go - https://github.com/codahale/sss https://github.com/codahale/sss C - https://github.com/fletcher/c-sss https://github.com/fletcher/c-sss Ruby - https://github.com/lian/shamir-secret-sharing https://github.com/lian/shamir-secret-sharing Java - https://github.com/timtiemens/secretshare https://github.com/timtiemens/secretshare Rust - https://github.com/sellibitze/secretshare https://github.com/sellibitze/secretshare

tehrei 10y ago
You should be a bit careful with implementations and keep in mind that you can't split a number larger than the prime you've picked. I've seen people go "oh I'll just split an N-byte value into M * N-byte values, splitting each byte separately with the largest prime < 256, surely the loss of a few values per byte won't be of consequence...". It might not be in your case, but you need to be aware of that.

yoo1I 10y ago

I run a small operation providing websites/online storage/email for a couple of friends and small businesses, and I use this as recovery solution to a master key. I distributed the encrypted very big master key, full system documentation and a part of the decryption key to the master key to a couple of people including a public notary. This way, should it ever get necessary, it will be possible for them to access my encrypted files. Say I get hit by a bus or something similar. Thank you, Shamir!

jacobkg 10y ago

What's especially cool about this technique is that unlike most crypto proofs it does not assume the existence of one-way functions (none have been found yet) nor does it require a computationally bounded adversary. Instead this technique is information theoretically secure so even an adversary with the ability to perform exponentially slow algorithms instantly could not find the secret. All this in a two page paper that only required high school math! PS - The "Shamir" who found this technique is the S in RSA

moserware 10y ago

I created a C# implementation and explained how the math works in http://www.moserware.com/2011/11/life-death-and-splitting-secrets.html http://www.moserware.com/2011/11/life-death-and-splitting-se...