PHP code behind my recent blog post.

shamir.php

<?php

/**
 *
 * Shamir's Secret Algorithm Demonstration
 *
 * Copyright (C) 2012 W. Tracz (http://www.willtracz.co.uk)
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
**/

/**
 * Evaulates the polynomial:
 *
 *    f(x) = $secret + ($coefficents[0] * x) + ...
 *
 * For 1 <= x <= count($coefficents)
 *
 * Returns an array of tuples for each (x, f(x))
 *
 * 
 *
 * @param array $coefficents The coefficents of the polynomial.
 * @param int $required The number of pieces required to rebuild the secret.
 * @param int $secret The "secret" coefficent.
 *
 * @return array An array of tuples holding input/output from the polynomial.
 *
 **/
function splitSecretToShare($secret, array $coefficents, $required) {
    
    // Force type to integer.
    $secret = intval((string) $secret);
    $required = intval((string) $required);
    
    // Validate input.
    if ($coefficents == false) {
        throw new InvalidArgumentException('At least one coefficent is required.');
    }
    
    if ($required < 1) {
        throw new OutOfRangeException('At least one point must be generated.');
    }
    
    // Generate a polynominal with the $secret as the y-intercept and $coefficents as higher powers of x.
    array_unshift($coefficents, $secret);    
    
    // Evaluate this polynomial at 1, 2, 3...
    $points = array();
    for ($x = 1; $x < count($coefficents); ++$x) {
    
        $sum = 0;
        for ($exponent = 0; $exponent < $required; ++$exponent) {
            $sum += $coefficents[$exponent] * pow($x, $exponent);
        }
        
        $points[$x - 1] = array($x, $sum);
    }   

    // Return the set of function values.
    return $points;
}

/**
 * Returns the zero'th (i.e. unitary) order-value of the polynomial
 * passing through the set of points.
 *
 * This value is calculated by using Lagrange inteprolation.
 *
 * @param array 
 *
 * @return int|float The zero'th order-value (may be a float due to rounding errors)
 *
 **/
function combineShareToSecret(array $points) {
    
    if ($points == false) {
        throw new InvalidArgumentException('Must provide at least one point.');
    }

    // Lagrange interpolation and evaluation.
    $sum = 0;
    for ($formula = 0; $formula < count($points); ++$formula) {
    
        // Work out the scaling factor for this basis.
        $numerator = 1; $denominator = 1;
        for ($count = 0; $count < count($points); ++$count) {
        
            if ($formula == $count) {
                continue;
            }
            
            $x1 = $points[$formula][0];
            $x2 = $points[$count][0];

            $numerator *= -$x2; // Want the value at x = 0.
            $denominator *= $x1 - $x2;
        }

        // Calculate the basis contribution at x = 0.
        $sum += (($points[$formula][1] * $numerator * 2) + 1) / ($denominator * 2);
        
    }   

    return $sum;
}

// Demonstration has 3 steps: input, challenge, result.
define('STEP_INPUT', 1);
define('STEP_CHALLENGE', 2);
define('STEP_RESULT', 3);

session_start();

$step = STEP_INPUT;
if (array_key_exists('iStep', $_SESSION) == true) {
    $step = $_SESSION['iStep'];
}

// Input stuff.
$errors = array();
if ($_SERVER['REQUEST_METHOD'] == 'POST') {

    switch ($step) {
        case STEP_INPUT:
        
            if (array_key_exists('sSecretValue', $_POST) == false || filter_var($_POST['sSecretValue'], FILTER_VALIDATE_INT) == false) {
                $errors['sSecretValue'] = 'Please enter an integer secret.';
            }
            
            if (array_key_exists('sPassword', $_POST) == false || is_string($_POST['sPassword']) == false || $_POST['sPassword'] == false) {
                $errors['sPassword'] = 'Please enter a password.';
            }
            
            if (array_key_exists('sRequiredCharacters', $_POST) == false || filter_var($_POST['sRequiredCharacters'], FILTER_VALIDATE_INT) == false) {
                $errors['sRequiredCharacters'] = 'Please enter a number of characters.';
            }
            
            if ($errors == false && (strlen($_POST['sPassword']) < $_POST['sRequiredCharacters'] || intval($_POST['sRequiredCharacters']) < 0)) {
                $errors['sRequiredCharacters'] = 'Please enter a number of characters between 1 and ' . strlen($_POST['sPassword']);
            }
            
            if ($errors == false) {
                $step = STEP_CHALLENGE;
                
                // Convert password to ASCII and split.
                $chars = array_map(function($c) { return ord($c); }, str_split($_POST['sPassword']));
                
                $values = splitSecretToShare(
                    (int) $_POST['sSecretValue'],
                    $chars,
                    (int) $_POST['sRequiredCharacters']
                );
                
                // Store the point value offset by the password ASCII value.
                $_SESSION['sSecureData'] = array_map(
                    function($v, $c) { return $v[1] + $c; }, 
                    $values,
                    $chars
                );
                
                // Remember the amount of characters user must input.
                $_SESSION['sSecureInput'] = (int) $_POST['sRequiredCharacters'];
                
                $_SESSION['sSecureHash'] = md5($_POST['sSecretValue']); // XXX: Just keep this to jazz up the result page.
            }
            
            break;
            
        case STEP_CHALLENGE:
        
            if (array_key_exists('sCharacter', $_POST) == false || is_array($_POST['sCharacter']) == false || count(array_filter($_POST['sCharacter'])) < $_SESSION['sSecureInput']) {
                $errors[] = 'Please enter the characters.';
            }
            
            if ($errors == false) {
                $step = STEP_RESULT;
            }
            
            break;

        case STEP_RESULT:
        
            if (array_key_exists('bResetToInput', $_POST) == true) {
                $step = STEP_INPUT;
            }
            
            if (array_key_exists('bResetToChallenge', $_POST) == true) {
                $step = STEP_CHALLENGE;
            }
            
            break;
    }

}

// View stuff.
switch ($step) {
    case STEP_INPUT:
        break;
        
    case STEP_CHALLENGE:
    
        // Generate sequence of required characters at random.
        $chars = array(); $last = -1; $max = count($_SESSION['sSecureData']);
        for ($i = 0; $i < $_SESSION['sSecureInput']; ++$i) {
            $char = rand($last + 1, $max - ($_SESSION['sSecureInput'] - $i));
            
            $chars[] = $char + 1;
            
            $last = $char;
        }
    
        break;
        
    case STEP_RESULT:
    
        // Collect entered values and convert to ASCII value array.
        $chars = array_combine(
            array_keys($_POST['sCharacter']),
            array_map(function($c) { return ord($c); }, $_POST['sCharacter'])
        );
    
        // Using the stored values, subtract off relevant ASCII value to obtain a set of original values.
        $points = array(); $point = 0;
        foreach($chars as $index => $value) {
            $points[$point] = array($index, $_SESSION['sSecureData'][$index - 1] - $value);
            
            ++$point;
        }
        
        // Interpolate and obtain the secret.
        $result = combineShareToSecret($points);

        // Quick check if this is what was entered at the start.
        if (md5($result) != $_SESSION['sSecureHash']) {
            $result = false;    
        }
    
        break;
}

$_SESSION['iStep'] = $step;

?>
<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8" />
	<title>Example</title>
    <link rel="stylesheet" type="text/css" href="//cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/2.2.1/css/bootstrap.min.css"/>
    <script src="//cdnjs.cloudflare.com/ajax/libs/twitter-bootstrap/2.2.1/bootstrap.min.js" type="text/javascript"></script>
</head>
<body>
    <?php if ($step == STEP_INPUT) { ?>
    <form method="post" action="" class="form-horizontal">
        <fieldset>
            <legend>Enter a Secret</legend>
            
            <p>Enter a secret number and a password below. Also indicate how many characters are required to retrieve the secret number.</p>
            
            <div class="control-group">
                <label for="sSecretValue" class="control-label">Secret Number:</label>
                <div class="controls">
                    <input type="text" maxlength="9" class="span3" value="" name="sSecretValue" id="sSecretValue" autofocus/>
                    <?php if (array_key_exists('sSecretValue', $errors) == true) { ?>
                    <p class="text-error"><?php echo $errors['sSecretValue']; ?></p>
                    <?php } ?>
                </div>
            </div>
            
            <div class="control-group">
                <label for="sPassword" class="control-label">Password:</label>
                <div class="controls">
                    <input type="password" value="" class="span4" name="sPassword" id="sPassword"/>
                    <?php if (array_key_exists('sPassword', $errors) == true) { ?>
                    <p class="text-error"><?php echo $errors['sPassword']; ?></p>
                    <?php } ?>
                </div>
            </div>
                        
            <div class="control-group">
                <label for="sRequiredCharacters" class="control-label">Required Characters:</label>
                <div class="controls">
                    <input type="text" placeholder="3" class="span1" name="sRequiredCharacters" id="sRequiredCharacters"/>
                    <?php if (array_key_exists('sRequiredCharacters', $errors) == true) { ?>
                    <p class="text-error"><?php echo $errors['sRequiredCharacters']; ?></p>
                    <?php } ?>
                </div>
            </div>
            
            <p><i class="icon-info-sign"></i> After this step, your secret number will be encoded and discarded.</p>

            <button type="submit" class="btn btn-primary">Encode Secret</button>

        </fieldset>
    </form>
    <?php } ?>

    <?php if ($step == STEP_CHALLENGE) { ?>
    <form method="post" action="" class="form-horizontal" autocomplete="off">
        <fieldset>
            <legend>Enter the Characters</legend>
            
            <p>You're secret has now been encoded and discarded. To get it back, you'll need to enter some characters from your password.</p>
            
            <pre><?php echo print_r($_SESSION, true); ?></pre>
            
            <?php for ($i = 0; $i < count($chars); ++$i) { ?>
            <div class="control-group">
                <label for="sCharacter<?php $i; ?>" class="control-label">Character <strong><?php echo $chars[$i]; ?></strong>:</label>
                <div class="controls">
                    <input type="text" class="span1" maxlength="1" id="sCharacter<?php $i; ?>" name="sCharacter[<?php echo $chars[$i]; ?>]" <?php if($i == 0) { echo 'autofocus'; } ?>/>
                </div>
            </div>
            <?php } ?>
          
            <button type="submit" class="btn btn-primary">Decode Secret</button>
            
        </fieldset>
    </form>
    <?php } ?>

    <?php if ($step == STEP_RESULT) { ?>
    <form action="" method="post">
        <fieldset>
            <legend>Your Secret is..</legend>
            
            <?php if ($result !== false) { ?>
            <p class="lead text-success">Your Secret Number is <strong><?php echo $result; ?></strong>.</p>
            <?php } else { ?>
            <p class="lead text-warning">Did you enter the characters correctly?</p>
            <?php } ?>
            
            <button type="submit" class="btn" name="bResetToInput">Start Again</button>
            <button type="submit" class="btn" name="bResetToChallenge">Re-enter Characters</button> 
        </fieldset>
    </form>
    <?php } ?>
</body>
</html>