Skip to content

Commit 8105424

Browse files
GF1977GF1977
authored
Add Feistel Cipher (Feistel network) (TheAlgorithms#271)
1 parent f2796e2 commit 8105424

File tree

3 files changed

+223
-0
lines changed

3 files changed

+223
-0
lines changed

‎Algorithms.Tests/Encoders/FeistelCipherTest.cs

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
using Algorithms.Encoders;
2+
using NUnit.Framework;
3+
using NUnit.Framework.Internal;
4+
using System;
5+
6+
namespace Algorithms.Tests.Encoders
7+
{
8+
public static class FeistelCipherTests
9+
{
10+
[Test]
11+
public static void DecodedStringIsTheSame([Random(100)] uint key)
12+
{
13+
// Arrange
14+
var encoder = new FeistelCipher();
15+
var random = new Randomizer();
16+
17+
int len_of_string = random.Next(1000);
18+
19+
string message = random.GetString(len_of_string);
20+
21+
// Act
22+
var encoded = encoder.Encode(message, key);
23+
var decoded = encoder.Decode(encoded, key);
24+
25+
// Assert
26+
Assert.AreEqual(message, decoded);
27+
}
28+
29+
[Test]
30+
[TestCase("00001111", (uint)0x12345678)]
31+
[TestCase("00001111222233334444555566667", (uint)0x12345678)]
32+
[TestCase("000011112222333344445555666677", (uint)0x12345678)]
33+
[TestCase("0000111122223333444455556666777", (uint)0x12345678)]
34+
// The plain text will be padded to fill the size of block (16 bytes), so the encoded message should be aligned with the rule
35+
// (text.Length % 16 == 0)
36+
public static void TestEncodedMessageSize(string TestCase, uint Key)
37+
{
38+
// Arrange
39+
var encoder = new FeistelCipher();
40+
41+
// Assert
42+
Assert.Throws<ArgumentException>(() => encoder.Decode(TestCase, Key));
43+
}
44+
}
45+
}

‎Algorithms/Encoders/FeistelCipher.cs

Lines changed: 177 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,177 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Text;
4+
5+
namespace Algorithms.Encoders
6+
{
7+
/// <summary>
8+
/// Encodes using Feistel cipher.
9+
/// https://en.wikipedia.org/wiki/Feistel_cipher
10+
/// In cryptography, a Feistel cipher (also known as Luby–Rackoff block cipher)
11+
/// is a symmetric structure used in the construction of block ciphers,
12+
/// named after the German-born physicist and cryptographer Horst Feistel
13+
/// who did pioneering research while working for IBM (USA)
14+
/// A large proportion of block ciphers use the scheme, including the US DES,
15+
/// the Soviet/Russian GOST and the more recent Blowfish and Twofish ciphers.
16+
/// </summary>
17+
public class FeistelCipher : IEncoder<uint>
18+
{
19+
// number of rounds to transform data block, each round a new "round" key is generated.
20+
private const int Rounds = 32;
21+
22+
/// <summary>
23+
/// Encodes text using specified key,
24+
/// where n - text length.
25+
/// </summary>
26+
/// <param name="text">Text to be encoded.</param>
27+
/// <param name="key">Key that will be used to encode the text.</param>
28+
/// <exception cref="ArgumentException">Error: key should be more than 0x00001111 for better encoding, key=0 will throw DivideByZero exception.</exception>
29+
/// <returns>Encoded text.</returns>
30+
public string Encode(string text, uint key)
31+
{
32+
List<ulong> blocks_list_plain = SplitTextToBlocks(text);
33+
StringBuilder encoded_text = new StringBuilder();
34+
35+
foreach (ulong block in blocks_list_plain)
36+
{
37+
uint temp = 0;
38+
39+
// decompose a block to two subblocks 0x0123456789ABCDEF => 0x01234567 & 0x89ABCDEF
40+
uint right_subblock = (uint)(block & 0x00000000FFFFFFFF);
41+
uint left_subblock = (uint)(block >> 32);
42+
43+
uint round_key;
44+
45+
// Feistel "network" itself
46+
for (int round = 0; round < Rounds; round++)
47+
{
48+
round_key = GetRoundKey(key, round);
49+
temp = right_subblock ^ BlockModification(left_subblock, round_key);
50+
right_subblock = left_subblock;
51+
left_subblock = temp;
52+
}
53+
54+
// compile text string formating the block value to text (hex based), length of the output = 16 byte always
55+
ulong encoded_block = left_subblock;
56+
encoded_block = (encoded_block << 32) | right_subblock;
57+
encoded_text.Append(string.Format("{0:X16}", encoded_block));
58+
}
59+
60+
return encoded_text.ToString();
61+
}
62+
63+
/// <summary>
64+
/// Decodes text that was encoded using specified key.
65+
/// </summary>
66+
/// <param name="text">Text to be decoded.</param>
67+
/// <param name="key">Key that was used to encode the text.</param>
68+
/// <exception cref="ArgumentException">Error: key should be more than 0x00001111 for better encoding, key=0 will throw DivideByZero exception.</exception>
69+
/// <exception cref="ArgumentException">Error: The length of text should be divisible by 16 as it the block lenght is 16 bytes.</exception>
70+
/// <returns>Decoded text.</returns>
71+
public string Decode(string text, uint key)
72+
{
73+
// The plain text will be padded to fill the size of block (16 bytes)
74+
if (text.Length % 16 != 0)
75+
{
76+
throw new ArgumentException($"The length of {nameof(key)} should be divisible by 16");
77+
}
78+
79+
List<ulong> blocks_list_encoded = GetBlocksFromEncodedText(text);
80+
StringBuilder decoded_text_hex = new StringBuilder();
81+
82+
foreach (ulong block in blocks_list_encoded)
83+
{
84+
uint temp = 0;
85+
86+
// decompose a block to two subblocks 0x0123456789ABCDEF => 0x01234567 & 0x89ABCDEF
87+
uint right_subblock = (uint)(block & 0x00000000FFFFFFFF);
88+
uint left_subblock = (uint)(block >> 32);
89+
90+
// Feistel "network" - decoding, the order of rounds and operations on the blocks is reverted
91+
uint round_key;
92+
for (int round = Rounds - 1; round >= 0; round--)
93+
{
94+
round_key = GetRoundKey(key, round);
95+
temp = left_subblock ^ BlockModification(right_subblock, round_key);
96+
left_subblock = right_subblock;
97+
right_subblock = temp;
98+
}
99+
100+
// compose decoded block
101+
ulong decoded_block = left_subblock;
102+
decoded_block = (decoded_block << 32) | right_subblock;
103+
104+
for(int i = 0; i < 8; i++)
105+
{
106+
ulong a = (decoded_block & 0xFF00000000000000) >> 56;
107+
108+
// it's a trick, the code works with non zero characters, if your text has ASCII code 0x00 it will be skipped.
109+
if (a != 0)
110+
{
111+
decoded_text_hex.Append((char)a);
112+
}
113+
114+
decoded_block = decoded_block << 8;
115+
}
116+
}
117+
118+
return decoded_text_hex.ToString();
119+
}
120+
121+
// Using the size of block = 8 bytes this function splts the text and returns set of 8 bytes (ulong) blocks
122+
// the last block is extended up to 8 bytes if the tail of the text is smaller than 8 bytes
123+
private static List<ulong> SplitTextToBlocks(string text)
124+
{
125+
List<ulong> blocks_list_plain = new List<ulong>();
126+
byte[] text_array = Encoding.ASCII.GetBytes(text);
127+
int offset = 8;
128+
for(int i = 0; i < text.Length; i += 8)
129+
{
130+
// text not always has len%16 == 0, that's why the offset should be adjusted for the last part of the text
131+
if (i > text.Length - 8)
132+
{
133+
offset = text.Length - i;
134+
}
135+
136+
string block = Convert.ToHexString(text_array, i, offset);
137+
blocks_list_plain.Add(Convert.ToUInt64(block, 16));
138+
}
139+
140+
return blocks_list_plain;
141+
}
142+
143+
// convert the encoded text to the set of ulong values (blocks for decoding)
144+
private static List<ulong> GetBlocksFromEncodedText(string text)
145+
{
146+
List<ulong> blocks_list_plain = new List<ulong>();
147+
for(int i = 0; i < text.Length; i += 16)
148+
{
149+
ulong block = Convert.ToUInt64(text.Substring(i, 16), 16);
150+
blocks_list_plain.Add(block);
151+
}
152+
153+
return blocks_list_plain;
154+
}
155+
156+
// here might be any deterministic math formula
157+
private static uint BlockModification(uint block, uint key)
158+
{
159+
for (int i = 0; i < 32; i++)
160+
{
161+
// 0x55555555 for the better distribution 0 an 1 in the block
162+
block = ((block ^ 0x55555555) * block) % key;
163+
block = block ^ key;
164+
}
165+
166+
return block;
167+
}
168+
169+
// There are many ways to generate a round key, any deterministic math formula does work
170+
private static uint GetRoundKey(uint key, int round)
171+
{
172+
// "round + 2" - to avoid a situation when pow(key,1) ^ key = key ^ key = 0
173+
uint a = (uint)Math.Pow((double)key, round + 2);
174+
return a ^ key;
175+
}
176+
}
177+
}

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@ This repository contains algorithms and data structures implemented in C# for ed
1919
* [Hill](./Algorithms/Encoders/HillEncoder.cs)
2020
* [NYSIIS](./Algorithms/Encoders/NysiisEncoder.cs)
2121
* [Soundex](./Algorithms/Encoders/SoundexEncoder.cs)
22+
* [Feistel](./Algorithms/Encoders/FeistelCipher.cs)
2223
* [Graph](./Algorithms/Graph)
2324
* [BreadthFirstSearch](./Algorithms/Graph/BreadthFirstSearch.cs)
2425
* [DepthFirstSearch](./Algorithms/Graph/DepthFirstSearch.cs)

0 commit comments

Comments
 (0)