FeistelCipher.cs

using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithms.Encoders;

/// <summary>
///     Encodes using Feistel cipher.
///     https://en.wikipedia.org/wiki/Feistel_cipher
///     In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher)
///     is a symmetric structure used in the construction of block ciphers,
///     named after the German-born physicist and cryptographer Horst Feistel
///     who did pioneering research while working for IBM (USA)
///     A large proportion of block ciphers use the scheme, including the US DES,
///     the Soviet/Russian GOST and the more recent Blowfish and Twofish ciphers.
/// </summary>
public class FeistelCipher : IEncoder<uint>
{
    // number of rounds to transform data block, each round a new "round" key is generated.
    private const int Rounds = 32;

    /// <summary>
    ///     Encodes text using specified key,
    ///     where n - text length.
    /// </summary>
    /// <param name="text">Text to be encoded.</param>
    /// <param name="key">Key that will be used to encode the text.</param>
    /// <exception cref="ArgumentException">Error: key should be more than 0x00001111 for better encoding, key=0 will throw DivideByZero exception.</exception>
    /// <returns>Encoded text.</returns>
    public string Encode(string text, uint key)
    {
        List<ulong> blocksListPlain = SplitTextToBlocks(text);
        StringBuilder encodedText = new();

        foreach (ulong block in blocksListPlain)
        {
            uint temp = 0;

            // decompose a block to two subblocks 0x0123456789ABCDEF => 0x01234567 & 0x89ABCDEF
            uint rightSubblock = (uint)(block & 0x00000000FFFFFFFF);
            uint leftSubblock = (uint)(block >> 32);

            uint roundKey;

            // Feistel "network" itself
            for (int round = 0; round < Rounds; round++)
            {
                roundKey = GetRoundKey(key, round);
                temp = rightSubblock ^ BlockModification(leftSubblock, roundKey);
                rightSubblock = leftSubblock;
                leftSubblock = temp;
            }

            // compile text string formating the block value to text (hex based), length of the output = 16 byte always
            ulong encodedBlock = leftSubblock;
            encodedBlock = (encodedBlock << 32) | rightSubblock;
            encodedText.Append(string.Format("{0:X16}", encodedBlock));
        }

        return encodedText.ToString();
    }

    /// <summary>
    ///     Decodes text that was encoded using specified key.
    /// </summary>
    /// <param name="text">Text to be decoded.</param>
    /// <param name="key">Key that was used to encode the text.</param>
    /// <exception cref="ArgumentException">Error: key should be more than 0x00001111 for better encoding, key=0 will throw DivideByZero exception.</exception>
    /// <exception cref="ArgumentException">Error: The length of text should be divisible by 16 as it the block lenght is 16 bytes.</exception>
    /// <returns>Decoded text.</returns>
    public string Decode(string text, uint key)
    {
        // The plain text will be padded to fill the size of block (16 bytes)
        if (text.Length % 16 != 0)
        {
            throw new ArgumentException($"The length of {nameof(key)} should be divisible by 16");
        }

        List<ulong> blocksListEncoded = GetBlocksFromEncodedText(text);
        StringBuilder decodedTextHex = new();

        foreach (ulong block in blocksListEncoded)
        {
            uint temp = 0;

            // decompose a block to two subblocks 0x0123456789ABCDEF => 0x01234567 & 0x89ABCDEF
            uint rightSubblock = (uint)(block & 0x00000000FFFFFFFF);
            uint leftSubblock = (uint)(block >> 32);

            // Feistel "network" - decoding, the order of rounds and operations on the blocks is reverted
            uint roundKey;
            for (int round = Rounds - 1; round >= 0; round--)
            {
                roundKey = GetRoundKey(key, round);
                temp = leftSubblock ^ BlockModification(rightSubblock, roundKey);
                leftSubblock = rightSubblock;
                rightSubblock = temp;
            }

            // compose decoded block
            ulong decodedBlock = leftSubblock;
            decodedBlock = (decodedBlock << 32) | rightSubblock;

            for(int i = 0; i < 8; i++)
            {
                ulong a = (decodedBlock & 0xFF00000000000000) >> 56;

                // it's a trick, the code works with non zero characters, if your text has ASCII code 0x00 it will be skipped.
                if (a != 0)
                {
                    decodedTextHex.Append((char)a);
                }

                decodedBlock = decodedBlock << 8;
            }
        }

        return decodedTextHex.ToString();
    }

    // Using the size of block = 8 bytes this function splts the text and returns set of 8 bytes (ulong) blocks
    // the last block is extended up to 8 bytes if the tail of the text is smaller than 8 bytes
    private static List<ulong> SplitTextToBlocks(string text)
    {
        List<ulong> blocksListPlain = new();
        byte[] textArray = Encoding.ASCII.GetBytes(text);
        int offset = 8;
        for(int i = 0; i < text.Length; i += 8)
        {
            // text not always has len%16 == 0, that's why the offset should be adjusted for the last part of the text
            if (i > text.Length - 8)
            {
                offset = text.Length - i;
            }

            string block = Convert.ToHexString(textArray, i, offset);
            blocksListPlain.Add(Convert.ToUInt64(block, 16));
        }

        return blocksListPlain;
    }

    // convert the encoded text to the set of ulong values (blocks for decoding)
    private static List<ulong> GetBlocksFromEncodedText(string text)
    {
        List<ulong> blocksListPlain = new();
        for(int i = 0; i < text.Length; i += 16)
        {
            ulong block = Convert.ToUInt64(text.Substring(i, 16), 16);
            blocksListPlain.Add(block);
        }

        return blocksListPlain;
    }

    // here might be any deterministic math formula
    private static uint BlockModification(uint block, uint key)
    {
        for (int i = 0; i < 32; i++)
        {
            // 0x55555555 for the better distribution 0 an 1 in the block
            block = ((block ^ 0x55555555) * block) % key;
            block = block ^ key;
        }

        return block;
    }

    // There are many ways to generate a round key, any deterministic math formula does work
    private static uint GetRoundKey(uint key, int round)
    {
        // "round + 2" - to avoid a situation when pow(key,1) ^ key  = key ^ key = 0
        uint a = (uint)Math.Pow((double)key, round + 2);
        return a ^ key;
    }
}