Private/Shamir/Invoke-SecretSharingShamirInterpolation.ps1
|
function Invoke-SecretSharingShamirInterpolation { <# .SYNOPSIS Reconstructs the byte-array value of a GF(256) polynomial at a given x-coordinate from a set of known points, via Lagrange interpolation. .DESCRIPTION Every point's Value must be the same length; the polynomial is evaluated byte-position by byte-position, treating each byte as an independent GF(256) Shamir scheme sharing the same x-coordinates. If X matches one of the supplied points' X exactly, that point's Value is returned directly with no arithmetic. Mirrors the interpolation formula used by the SLIP-0039 reference implementation (trezor/python-shamir-mnemonic), computed in the log domain via Get-SecretSharingFieldTable so that division becomes subtraction of logarithms. #> [CmdletBinding()] [OutputType([byte[]], [System.Object[]])] param( [Parameter(Mandatory)] [PSObject[]]$Point, [Parameter(Mandatory)] [byte]$X ) if ($Point.Count -eq 0) { throw 'Invalid set of points. At least one point is required.' } $uniqueXCount = ($Point | ForEach-Object { $_.X } | Select-Object -Unique | Measure-Object).Count if ($uniqueXCount -ne $Point.Count) { throw 'Invalid set of points. Point X-coordinates must be unique.' } $valueLength = $Point[0].Value.Length foreach ($p in $Point) { if ($p.Value.Length -ne $valueLength) { throw 'Invalid set of points. All point values must have the same length.' } } foreach ($p in $Point) { if ($p.X -eq $X) { return , $p.Value } } $table = Get-SecretSharingFieldTable # log of the product of (point.X xor X) across every point $logProduct = 0 foreach ($p in $Point) { $logProduct += $table.Log[$p.X -bxor $X] } $result = [byte[]]::new($valueLength) foreach ($p in $Point) { $logDenominator = 0 foreach ($other in $Point) { if ($other.X -ne $p.X) { $logDenominator += $table.Log[$p.X -bxor $other.X] } } $logBasis = (($logProduct - $table.Log[$p.X -bxor $X] - $logDenominator) % 255 + 255) % 255 for ($i = 0; $i -lt $valueLength; $i++) { $byteValue = $p.Value[$i] if ($byteValue -ne 0) { $term = $table.Exp[($table.Log[$byteValue] + $logBasis) % 255] $result[$i] = $result[$i] -bxor $term } } } return , $result } |