Return to Answer

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that; you might want to learn the basics with a prime field (which is what you're using) first.

In any case, to address your question:

So, in order to use shamirs scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the field size, we generally divide the secret into a number of smaller secrets, and share each subsecret independantly.

For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatinate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in Wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that; you might want to learn the basics with a prime field (which is what you're using) first.

In any case, to address your question:

So, in order to use Shamir's scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the field size, we generally divide the secret into a number of smaller secrets, and share each subsecret independently.

For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatenate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel that getting into a discussion of what a field is (look it up in wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that.

In any case, to address your question:

So, in order to use shamirs scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the secret size, we generally divide the secret into a number of smaller secrets, and share each subsecret independantly.

For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatinate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel like getting into a discussion of what a field is (look it up in wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that; you might want to learn the basics with a prime field (which is what you're using) first.

In any case, to address your question:

So, in order to use shamirs scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the field size, we generally divide the secret into a number of smaller secrets, and share each subsecret independantly.

For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatinate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel that getting into a discussion of what a field is (look it up in wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that.

In any case, to address your question:

So, in order to use shamirs scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the secret size, we generally divide the secret into a number of smaller secrets, and share each subsecret independantly.

For example, if you have a 16 byte secret, we may divide that into the 16 byte values; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatinate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...

So the gist of my question here is about the usage of my field size, that I use for modulo.

Well, the first thing to notice is the definition of a 'field' (which is a term from mathematics); I don't feel that getting into a discussion of what a field is (look it up in wikipedia if you're interested), however addition and multiplication modulo a composite (such as 50) is not a field, and Shamir Secret Sharing won't work there.

If you replace 50 with 53 (which is prime), then it would work.

In practice, we often use a extension field $GF(2^k)$ for $k$ perhaps 8 or 16 or 32; that makes things nicely line up in bytes, however the operations are not modulo the field size (the 'addition' operation is actually exclusive-or, and the multiplication operation is significantly different than what you're used to). Of course, it's up to you if you want to look into that.

In any case, to address your question:

So, in order to use shamirs scheme with a field, is it necessary for the field to be larger than my secret? or is there some trick I can do to reconstruct it?

Well, a single iteration of Shamir's secret sharing will always return a field element (that can be interpreted as a value between 0 and the field size minus one); hence if you need to share a secret that may be larger than the secret size, we generally divide the secret into a number of smaller secrets, and share each subsecret independantly.

For example, if you have a 16 byte secret, we may divide that into the 16 values of one byte each; for each byte value, we may generate a secret polynomial modulo 257 (a prime), and distribute shares for that. When it comes time to reconstruct, we construct each of the byte values independently, and then concatinate them to form the original 16 byte secret.

Just a word of warning: you must generate an independent secret polynomial for each byte - reusing the same polynomial (except for the constant term) breaks the system. On the other hand, you can use the same $x$ coordinate for each of the subsecrets when you give a share to someone.

Now, with $p=257$, each share will be somewhat larger than the original secret (because each secret share is a value between 0 and 256; that doesn't quite fit into a byte). That's why using $GF(256)$ is popular; each secret share is a value between 0 and 255, and so everything fits nicely...