RSA explained with PHP

rsa-bignum.php

<?php

function rsa_demo(){
    list( $p, $q ) = get_2_primes();
    
    echo "p = $p\n";
    echo "q = $q\n";

    $n = bcmul( $p, $q );
    echo "n = p * q = $n\n";

    $t = bcmul( bcsub( $p, "1" ), bcsub( $q, "1" ) );
    echo "t = (p-1)(q-1) = $t\n";

    $e = "65537";
    $eok = ( bcmod( $t, $e ) !== "0" ) ? "OK" : "ERROR";
    echo "e = $e [$eok]\n";

    echo "Public key: [$e, $n]\n";

    $size = strlen( $n ) * 3.322;
    echo "Length: $size bits\n";

    echo "d * e = 1 (mod t)\n";
    echo "d * $e = 1 (mod $t)\n";
    echo "d * $e mod $t = 1\n";
    $d = invmod( "$e", "$t" );
    echo "d = $d\n";

    echo "Private key: [$d, $n]\n";

    $message = some_big_number();
    echo "message = $message\n";

    echo "encr = message^e (mod n)\n";
    $encr = bcpowmod( $message, $e, $n );
    echo "encr = $encr\n";

    echo "decr = encr^d (mod n)\n";
    $decr = bcpowmod( $encr, $d, $n );
    echo "decr = $decr\n";

    $ok = (bccomp( $message, $decr ) === 0) ? "OK" : "FAILED";
    echo "Result: $ok\n";

    $command = some_big_number();
    echo "command = $command\n";

    echo "sign = command^d (mod n)\n";
    $sign = bcpowmod( $command, $d, $n );
    echo "sign = $sign\n";

    echo "vrfy = sign^e (mod n)\n";
    $vrfy = bcpowmod( $sign, $e, $n );
    echo "vrfy = $vrfy\n";

    $ok = (bccomp( $vrfy, $command ) === 0) ? "OK" : "FAILED";
    echo "Result: $ok\n";
}

function invmod( $a, $b ) {
    $n=$b;
    $x=0; $lx=1; $y=1; $ly=0;
    while ($b) {
      $t=$b;
      $q=bcdiv($a,$b,0);
      $b=bcmod($a,$b);
      $a=$t;
      $t=$x; $x=bcsub($lx,bcmod(bcmul($q,$x),$n)); $lx=$t;
      $t=$y; $y=bcsub($ly,bcmod(bcmul($q,$y),$n)); $ly=$t;
    }
    if (bccomp($lx,0) == -1)
      $lx=bcadd($lx,$n);
    return $lx;
}


function is_prime( $n ){
    if ( $n === "1" ) return null;
    $nsq = bcsqrt( $n ) + 1;
    for ( $i = "2"; bccomp( $i, $nsq ) === -1; $i = bcadd( $i, "1" ) ){
        if ( bcmod( $n, $i ) === "0" ) return false;
    }
    return true;
}

function get_prime( ){
    echo "generating prime: \n";
    $tries = 0;

    pick_a_candidate:
    $p = some_big_number();
    $checks = 0;
    $tries++;
    if ( $tries % 3 === 1 ) echo ".";

    check:
    $a = some_big_number();
    $a = bcmod( $a, $p );
    
    $res = bcpowmod( $a, bcsub( $p, "1" ), $p );

    if ( $res == "1" ){
        $checks++;
        if ( $checks % 10 === 1 ) echo '!';
        if ( $checks > 50 ){
            goto found;
        }
        goto check;
    }
    else {
        if ( $checks > 1 ){
            echo "FUCK ";
        }
        goto pick_a_candidate;
    }

    found:
    echo " found $p in $tries tries\n";
    return $p;
}

function get_2_primes(){
    $a = get_prime();
    $b = get_prime();
    return $a !== $b ? [$a,$b] : get_2_primes();
}

function some_big_number(){
    $n = 1;
    for( $i = 0; $i < 20; $i++ ) {
        $n = bcmul( $n, 10 );
        $n = bcadd( $n, rand( 0, 9 ) );
    }
    return $n;
}

rsa_demo();

rsa-naive.php

<?php

function rsa_demo(){
    list( $p, $q ) = get_2_primes();

    echo "p = $p\n";
    echo "q = $q\n";

    $n = bcmul( $p, $q );
    echo "n = p * q = $n\n";

    $t = bcmul( bcsub( $p, "1" ), bcsub( $q, "1" ) );
    echo "t = (p-1)(q-1) = $t\n";

    $e = "65537";
    $eok = ( bcmod( $t, $e ) !== "0" ) ? "OK" : "ERROR";
    echo "e = $e [$eok]\n";

    echo "Public key: [$e, $n]\n";

    echo "d * e = 1 (mod t)\n";
    echo "d * $e = 1 (mod $t)\n";
    echo "d * $e mod $t = 1\n";
    $d = invmod( "$e", "$t" );
    echo "d = $d\n";

    echo "Private key: [$d, $n]\n";

    $message = some_big_number();
    echo "message = $message\n";

    $encr = bcpowmod( $message, $e, $n );
    echo "encr = $encr\n";

    $decr = bcpowmod( $encr, $d, $n );
    echo "decr = $decr\n";

    $ok = (bccomp( $message, $decr ) === 0) ? "OK" : "FAILED";
    echo "Result: $ok\n";

    $command = some_big_number();
    echo "command = $command\n";

    $sign = bcpowmod( $command, $d, $n );
    echo "sign = $sign\n";

    $vrfy = bcpowmod( $sign, $e, $n );
    echo "vrfy = $vrfy\n";

    $ok = (bccomp( $vrfy, $command ) === 0) ? "OK" : "FAILED";
    echo "Result: $ok\n";

}

function invmod( $a, $b ) {
    $n=$b;
    $x=0; $lx=1; $y=1; $ly=0;
    while ($b) {
      $t=$b;
      $q=bcdiv($a,$b,0);
      $b=bcmod($a,$b);
      $a=$t;
      $t=$x; $x=bcsub($lx,bcmod(bcmul($q,$x),$n)); $lx=$t;
      $t=$y; $y=bcsub($ly,bcmod(bcmul($q,$y),$n)); $ly=$t;
    }
    if (bccomp($lx,0) == -1)
      $lx=bcadd($lx,$n);
    return $lx;
}


function is_prime( $n ){
    if ( $n === "1" ) return null;
    $nsq = bcsqrt( $n ) + 1;
    for ( $i = "2"; bccomp( $i, $nsq ) === -1; $i = bcadd( $i, "1" ) ){
        if ( bcmod( $n, $i ) === "0" ) return false;
    }
    return true;
}

function get_prime( $start = null ){
    if ( $start === null ){
        $start = some_big_number();
    }
    $candidate = $start;
    do {
        $candidate = bcadd( $candidate, "1" );
    }
    while ( ! is_prime( $candidate ) );
    return $candidate;
}

function get_2_primes(){
    $a = get_prime();
    $b = get_prime();
    return $a !== $b ? [$a,$b] : get_2_primes();
}

function some_big_number(){
    $num = rand( 100, 999 );
    return $num;
}

rsa_demo();