A very brief introduction to cryptography.This post covers one-time pads, a little bit of random numbers and the Diffie-Hellman algorithm.

One-Time Pads

One-time pad is a very basic algorithm but virtually unbreakable if properly implemented. The idea is simple: given a message and a shared secret, we create an encrypted message based on the formula encrypted[i] = original[i] + shared_secret[i]. If the shared_secret is purely random and the key is not intercepted, the algorithm is virtually impossible to crack.

However, in practice, we are limited by the following:

  • the alphabet of the message is limited
  • the alphabet of the shared secret is limited
  • due to practical transmission purposes and due to the limitations of random number generators, the length of the shared_secret is usually less than the length of the original message
  • if humans are used to generating keys, (e.g. entering passwords), then true randomness is even harder to achieve

The above points generate patterns in the encoded message that can be exploited by an attacker.

Let’s consider a 26 letter alphabet, made from letters A to Z. Below you can observe how the secret is looped through in case its length is less than the length of the original message.

    static String parse(String msg, String key, BiFunction<Byte, Byte, Byte> f){

        // ensure we use only our alphabet
        msg = msg.toUpperCase ();
        key = key.toUpperCase ();

        // remove the white spaces because these decrease the randomness of the message
        // and they are not part of our alphabet
        byte[] msgb = msg.replaceAll ("\\s+","") .getBytes (StandardCharsets.US_ASCII);
        byte[] keyb = key.replaceAll ("\\s+",""). getBytes (StandardCharsets.US_ASCII);

        byte[] ret = new byte[msgb.length];

        for(int i = 0; i < msgb.length; i++){
            ret[i] = f.apply (msgb[i], keyb[i%keyb.length]);
        return new String (ret);


    static String encode(String msg, String key){
        return parse (msg, key, (m, k) -> (byte)((m-'A'+k-'A') % COUNT + 'A'));

    static String decode(String msg, String key){
        int n = COUNT;
        return parse (msg, key, (m, k) ->(byte)((m-k>=0)? (m-k+'A') : (m-k+n+'A')));


In the previous section we spoke about message randomness. To measure randomness, we introduce the notion of entropy. Entropy is the number of bits needed to optimally encode a given string.

For a purely random string, composed of equally probable symbols, its entropy is given by the number of bits we need to encode each symbol multiplied by the number of symbols in the string. Variable COUNT in the code below is the number of distinct symbols in the alphabet. In our case, for the A-Z alphabet, it is 26.

    static double symbol_entropy(){
        // log2(x) = log(x) / log(2)
        return (Math.log (COUNT) / Math.log (2));

    static double theoretical_entropy(byte[] sequence){
        return  symbol_entropy () * sequence.length;

But what about the pseudo random number generators? Let’s consider the simplest and most commonly used random number generator is the Linear Congruential Generator. It has a very simple, recursive, form: n_i+1 = (A * n_i + B)%m, with n_-1 being called “seed”.

It is very important to observe that the seed is the only source of randomness (entropy) in the system, thus the maximum theoretical entropy of this RNG is given by log2(symbols_in_the_alphabet), in our case, for our alphabet, log2(26) == 4.7004. That is because the random function depends only on the first seed and the longest possible sequence it can generate is 26 characters before it loops over. In practice, if wrong As and Bs are chosen, the entropy can be much lower, as seen in the following pseudo-random sequence generated with this RNG: QKGUVFLPBA QKGUVFLPBA QKGUVFLPBA QKGUVFLPBA QKGUVFLPBAQKGUVFLPBAQKGUVFLPBAQKGUVFLPBAQKGUVFLPBAQKGUVFLPBA

    static byte randomLetter(int A, int B, int seed){
        int length = COUNT;

        long lA = A;
        long lB = B;
        long lSeed = seed;

        long n = Math.abs (lA * lSeed + lB) % length;

        // there is no additional source of randomness except for the seed
        return (byte)(n + 'A');

    static byte[] random_sequence(int A, int B, int seed, int cnt){
        if (cnt <= 0) throw new IllegalArgumentException ("Count must be larger than 0");

        byte[] ret = new byte[cnt];
        for (int i = 0; i < cnt; i++){
            seed = ret[i] = randomLetter (A, B, seed);
        return ret;


Since the one-time pads are so sensitive to sharing the secret, the question we immediately ask ourselves is how do we transmit secrets over a medium without sharing the secret itself? This question is answered by the Diffie-Hellman key exchange algorithm.

We observe the following:

(p^q)^r = p^(q*r) = p^(r*q) = (p^q)^r

and this property is preserved for modulo n as follows:

(p^q % n)^r % n = (p^r % n)^q % n

This means that, having two actors that communicate over a channel, each actor can reach a consensus on a shared secret, (p^q % n)^r % n = (p^r % n)^q % n, without sharing it explicitly. Let’s see it in code:

    static class Actor {

        private byte[] sharedPass = null;
        private int[] internalRandoms = null;

        private static int PASS_LEN = 10;
        private static int INITIAL_BASE = 5;

        private Actor (){
            Random r = new Random ();

            // STEP: generate a set of internal numbers
            internalRandoms =  IntStream.range (0, PASS_LEN).map (x -> r.nextInt ()).toArray ();

        private Actor(int[] randoms){
            internalRandoms = randoms;

        public static int powModulo(int base, int x, int modulo){
            // https://en.wikipedia.org/wiki/Modular_exponentiation
            if (modulo == 1)
                return 0;

            int result = 1;
            base = base % modulo;

            while (x > 0) {
                if (x % 2 == 1) {
                    result = (result * base) % modulo;
                x = x >> 1;
                base =(base * base) % modulo;
            return result;

        public static int powModulo(int base, int x) {
            return powModulo(base, x, COUNT);

        public static int initialBaseModulo(int x){
            return powModulo (INITIAL_BASE, x);

        public int[] getPublicMessage() {
            // STEP2: share the result of exponentiation on the public channel
            return IntStream.of (internalRandoms). map (Actor::initialBaseModulo).toArray ();

        public void createSharedPass(int[] othersRand){
            // STEP3: raise to the other's public message to the power of internal randoms
            // to get to the commonly shared password
            sharedPass = new byte[PASS_LEN];
            for(int i = 0; i < PASS_LEN; i++)
                sharedPass[i] = (byte)(powModulo (othersRand[i], internalRandoms[i]) + 'A');

        public String encodeMessage(String s){
            // STEP4: communicate
            return encode (s, new String (sharedPass));

        public String decodeMessage(String msg){
            // STEP4: communicate
            return decode (msg, new String (sharedPass));

        public String getPrivatePassword(){
            return new String (sharedPass);

    * Implementation of the actual exchange
    public static void test_diffieHellman() throws Exception {

        var actor1 = new Actor ();
        var actor2 = new Actor ();

        actor2.createSharedPass (actor1.getPublicMessage ());
        actor1.createSharedPass (actor2.getPublicMessage ());

        var msg = actor1.encodeMessage ("HELLOWORLD");
        var decodedMsg = actor2.decodeMessage (msg);

        var pass1 = actor1.getPrivatePassword ();
        var pass2 = actor2.getPrivatePassword ();

        if(!pass1.equals (pass2) || !decodedMsg.equals ("HELLOWORLD"))
            throw new Exception ("Wrong Algorithm");

The most important function here is powModulo. We notice that it base^x % modulo == 0, the result of the power function will be 0 from that point on. So we need to avoid that.


Let’s look at little bit at the results of powModulo:

  • The function starts returning 1.
  • At each step, it returns a value between 0 and n-1. We want to avoid 0s because, otherwise,from that point on, the function will always return 0.
  • The function loops through the same values once it returns 1 again.


What does it mean for someone who is listening to this conversation to guess our initial, hidden number? It means that he/she guesses a number g such that INITIAL_BASE^g % n is the observed number transmitted over the network. He/she can do this by substituting numbers from 1 ... n in the formula and compare the result with the observed number. It is worth to notice that this g does not necessary need to be the number we initially thought of, but rather any value that satisfies the above condition will also satisfy powModulo (othersRand[i], internalRandoms[i] == powModulo (othersRand[i], g[i])), which employed when generating the shared password.

So let’s crack our code:

    public static void test_diffieHellman() throws Exception {  

        [....code from above, new lines added below... ]

        var crackedMessage = crackEncodedMessage (actor1.getPublicMessage (), actor2.getPublicMessage (), msg);

        if (!decodedMsg.equals (crackedMessage))
            throw new Exception ("Wrong Algorithm");


    public static String crackEncodedMessage(
        int[] actor1PublicMessage, 
        int[] actor2PublicMessage, 
        String encodedMessage){

        var crackedInternalRandoms = new int[actor1PublicMessage.length];

        // STEP 1: 
        // for each element in the public message from the first actor,
        // find a number for which the initialPowModulo is equal to the observed value
        // O(pass length * modulo = pass length * 2^no_of_bits_in_modulo_prime_number) algorithm:
        for(int i = 0; i < crackedInternalRandoms.length; i++) {
            for (int j = 0; j < COUNT; j++) {
                if (Actor.initialPowModulo (j) == actor1PublicMessage[i]) {
                    crackedInternalRandoms[i] = j;

        // STEP 2: create an actor with these randoms as the internal password
        var actor3 = new Actor (crackedInternalRandoms);

        // STEP 3: use this fake internal password and the observed responses from 
        // the second actor to re-create the shared password
        actor3.createSharedPass (actor2PublicMessage);

        // STEP 4: decode the message
        return actor3.decodeMessage (encodedMessage);

Since we want for someone in the middle to be as hard as possible to guess which was the initial hidden random number we started with, we want to force them to run through the longest number of trials and errors, thus we want the longest possible sequence of non-1s results, that is we want 1 to be reached again when x==n-1, while avoiding premature cycles.

Fermat’s Little Theorem tells us that INITIAL_BASE^(n-1) % n==1 when n is prime and INITIAL_BASE is not a multiple of n.

Now, even if (INITIAL_BASE^(n-1) mod n) == 1, it might be that 1 is also reached for factors of n-1. For example, if we set INITIAL_BASE = 3, n = 23, we have ones also for 11. In practice, INITIAL_BASE can be a small number, good choices being 2, 3, 5, 7.


This example demonstrate three points:

  • Why we need to choose a large prime number for n, in our case the COUNT variable, usually selected as a prime n=2*q+1, where q is another large prime
  • Why factoring n-1 is important (the factors are the points where loops might start, hence the n=2*q+1 selection)
  • Why Diffie-Hellman does not protect against man-in-the-middle. There’s nothing stopping an attacker to set himself/herself as a middleman between the two communicators. There’s no means for each of the parties communicating to validate their identity to each other.

By today’s standards, a 2048 bit prime number is the minimal recommended requirement to effectively protect against a brute-force attack and asymmetric encryption is the standard in cryptography.