Crypto-boun

First questions up to 1.4 all use some form of shift value, and just push letters to some other place in the alphabet. Cipher wheel, an encryption table, Caesar cipher, whatever you call it. They are fundamentally the same. There is an implementation of this below. For decryption, shifting is done backwards.

Encrypt

Decrypt

If you wish to use these tools for a range of shift values, you may do so here.

Encrypt in a range

Decrypt in a range

Here is the function behind these operations for the interested reader. Many languages already use some structure like an ASCII table to represent letters. Therefore, implementation of a caesar cipher is shockingly simple.

<?php
function caesar_encrypt($plaintext, $shiftvalue)
    {
        $length = strlen($plaintext);
        for ($i=0; $i < $length; $i++) { 
            // getting the ascii value for the current letter
            $ascii_value = ord($plaintext[$i]);
            for ($j=0; $j < $shiftvalue; $j++) { 
                // at the end points of the alphabet, we connect the ends
                if ($ascii_value == 90){ // 'Z'
                    $ascii_value = 65; // 'A'
                }
                else $ascii_value++;
            }
            // after shifting, we get the actual letter, represented by the ASCII value
            $plaintext[$i] = chr($ascii_value);
        }
        return $plaintext; // at the end, this is in fact ciphertext, don't let the name fool you
    }
?>

Decryption is done very similarly, instead of incresing values, we simply decrease them. Same thing on the reverse direction.

Question 1.11

Question 1.12

This question is about Extended Euclidean Algorithm. There is a program below that calculates greatest common divisor of two given numbers, together with two values u and v, where au + bv = gdc(a, b).

There is a much cleaner way of doing this computationally, but I stayed loyal to the texbook, which defines the algorithm a bit confusingly.

Here is the function behind this operation, for the interested reader:

<?php
    
    function extended_euclidean($a, $b){

        if($b == 0){
            return [$a, 1, 0];
        }

        $u = 1; $g = $a; $x = 0; $y = $b;
        
        while(true){
            if($y == 0){
                $v = floor(($g - $a * $u) / $b);
                return [$g, $u, $v];
            }
            $q = floor($g / $y); // g = qy + t
            $t = $g % $y;  // modula operation
            $s = $u - $q * $x;
            $u = $x; $g = $y;
            $x = $s; $y = $t;
        }       
    }

?>

Question 1.14

Question 1.19

Question 1.21

Question 1.25

At its core, the idea behing this algorithm is not too complicated. The aim is to calculate some big power of a number under the modula operation. As you probably know, after some finite number it starts to repeat itself.

For that reason, it is convenient to represent the exponent using powers of a number. You could theoratically choose any number, it could have been even 462. However, choosing 2 makes it easier, because computers represent numbers in base 2, which we call binary. Therefore, if your exponent is a power of 2, it is computed faster because of its very nature.

The only remaning concern is memory, which is not that much of an issue in today's modern hardware, but ... hey! it is an improvement. The algorithm below makes the necessary operations while we're trying to decompose the exponent as a sum of powers of 2. The value is used immediately, so there is no need to store it. We simply overwrite the existing memory block. How cool is that =) You may try it below.

Here is the function behind this operation, for the interested reader:

<?php
    
    function square_n_multiply($N, $g, $A){
        $a = $g; $b = 1; //setting necessary variables
        while($A > 0){
            if(($A % 2) == 1) $b = ($b * $a) % $N;
            // We will not be storing different values
            // of $A , therefore we do the necessary
            // operation on the fly 
            $a = ($a * $a) % $N; 
            // updating 'A' for the next cycle
            $A = floor($A / 2);
        }
        return $b;
    }
?>

Question 1.27

I feel like this is one of the best questions in the entire chapter. I'm sure there is a more elegant way to do all of this, but this is the best I can do with my horrendous number theory skills.

Question 1.28

This is normally not included in the list of recommended questions. However, there is something about this question that makes me want to do it. I don't know how to define it. This is also called Euclid's Theorem, and chances are you've already seen this a million times before, if you're interested in number theory.

Chapter 1

A simple Caesar cipher