I am writing a module of an encryption function. The algorithm XOR the input with 6-bit left shift and 10-bit left shift of the input itself. Below is the code of the linear transformation.
module linear_transform_enc (
input wire [15:0] m,
output [15:0] L);
wire [15:0] m6, m10;
assign m6 [15:0] = {m[9:0],m[15:10]};
assign m10[15:0] = {m[5:0],m[15:6]};
assign L = m ^ m6 ^ m10;
endmodule
Now, I would like to write the reverse of it as the decryption function. The solution I found from Internet is as shown as below. I dont understand why it need to XOR with 2, 4, 12 and 14 bit shift of the input.... Can anyone explain it ? Much appreciate!!
module linear_transform_dec(
input wire [15:0] L,
output [15:0] m);
wire [15:0] L2, L4, L12, L14;
assign L2 [15:0] = {L[13:0],L[15:14]};
assign L4 [15:0] = {L[11:0],L[15:12]};
assign L12 [15:0] = {L[3:0],L[15:4]};
assign L14 [15:0] = {L[1:0],L[15:2]};
assign m = L ^ L2 ^ L4 ^ L12 ^ L14;
endmodule
EDIT: I have also asked basically the same question on the cryptography stack exchange forum and we now have a strong mathematical proof of how this cipher works!
Your question got me curious, so I looked into it and I have found an explanation for your case, although I wasn't able to find a generalization of the rule.
We need to know only three things to understand why this works:
XORing a number with itself gives 0. And 0 is the identity element for the XOR operation. This gives us the nice property: a^b^b=aXOR operation is commutative, meaning you can rearrange all the terms of a sequence of operations and you get the same result: a^b^c = c^b^a = b^c^aXOR works at the single bit level with no effects on adjacent bits.Now we can look into the cipher algorithm, and we can analyse a bit at a time. Let's focus on what is happening at bit 0.
We should find a formula that gives the index of the bit we receive after left rotating by r bits. For B bits, the formula is the following (I coded my attempts in python):
# returns index i after rotating by r
# Example with 5 bits
# x[4]x[3]x[2]x[1]x[0]
# rotate by 3.
# x[1]x[0]x[4]x[3]x[2]
# At index 0 we there is x[2]. (5-3+0)%5 = 2
# At index 1 we there is x[3]. (5-3+1)%5 = 3
# At index 2 we there is x[4]. (5-3+2)%5 = 4
# At index 3 we there is x[0]. (5-3+3)%5 = 0
# At index 4 we there is x[1]. (5-3+4)%5 = 1
def ri(i,r):
return (B - r + i ) % B #B is global
Now we can use this formula to find all the bits of the encoded value, because we know that
#L[i] = m[i] ^ m[ri(i,6] ^ m[ri(i,10)]
for idx in range(bits):
s = "L[{}] = m[{}] ^ m[{}] ^ m[{}]".format(idx,
idx,
ri(idx,6),
ri(idx,10))
print(s)
Gives:
L[0] = m[0] ^ m[10] ^ m[6]
L[1] = m[1] ^ m[11] ^ m[7]
L[2] = m[2] ^ m[12] ^ m[8]
L[3] = m[3] ^ m[13] ^ m[9]
L[4] = m[4] ^ m[14] ^ m[10]
L[5] = m[5] ^ m[15] ^ m[11]
L[6] = m[6] ^ m[0] ^ m[12]
L[7] = m[7] ^ m[1] ^ m[13]
L[8] = m[8] ^ m[2] ^ m[14]
L[9] = m[9] ^ m[3] ^ m[15]
L[10] = m[10] ^ m[4] ^ m[0]
L[11] = m[11] ^ m[5] ^ m[1]
L[12] = m[12] ^ m[6] ^ m[2]
L[13] = m[13] ^ m[7] ^ m[3]
L[14] = m[14] ^ m[8] ^ m[4]
L[15] = m[15] ^ m[9] ^ m[5]
And this scrambles the data with itself, making it difficult to guess. However we don't have a key, so the original information is still inside, it's just mixed with other original bits.
Let's now see what the decoded functions does. When we say L rotated by r we need to remember that L is just m all mixed up. So when we say L rotated by 2 XOR L rotated by 4 we can substitute that by the equivalent expression in ms.
Again, we can help printing the expression with python:
# Returns the i-th bit of L expressed in terms of m
def L_(i):
return "m[{}] ^ m[{}] ^ m[{}]".format(ri(i,0),ri(i,6),ri(i,10))
#print m as the decipher says, but with all Ls expanded
for idx in range(bits):
s = "m[{}] = {} ^ {} ^ {} ^ {} ^ {}".format(idx,
L_(ri(idx,0)),
L_(ri(idx,2)),
L_(ri(idx,4)),
L_(ri(idx,12)),
L_(ri(idx,14))
)
print(s)
Which gives:
m[0] = m[0] ^ m[10] ^ m[6] ^ m[14] ^ m[8] ^ m[4] ^ m[12] ^ m[6] ^ m[2] ^ m[4] ^ m[14] ^ m[10] ^ m[2] ^ m[12] ^ m[8]
m[1] = m[1] ^ m[11] ^ m[7] ^ m[15] ^ m[9] ^ m[5] ^ m[13] ^ m[7] ^ m[3] ^ m[5] ^ m[15] ^ m[11] ^ m[3] ^ m[13] ^ m[9]
m[2] = m[2] ^ m[12] ^ m[8] ^ m[0] ^ m[10] ^ m[6] ^ m[14] ^ m[8] ^ m[4] ^ m[6] ^ m[0] ^ m[12] ^ m[4] ^ m[14] ^ m[10]
m[3] = m[3] ^ m[13] ^ m[9] ^ m[1] ^ m[11] ^ m[7] ^ m[15] ^ m[9] ^ m[5] ^ m[7] ^ m[1] ^ m[13] ^ m[5] ^ m[15] ^ m[11]
m[4] = m[4] ^ m[14] ^ m[10] ^ m[2] ^ m[12] ^ m[8] ^ m[0] ^ m[10] ^ m[6] ^ m[8] ^ m[2] ^ m[14] ^ m[6] ^ m[0] ^ m[12]
m[5] = m[5] ^ m[15] ^ m[11] ^ m[3] ^ m[13] ^ m[9] ^ m[1] ^ m[11] ^ m[7] ^ m[9] ^ m[3] ^ m[15] ^ m[7] ^ m[1] ^ m[13]
m[6] = m[6] ^ m[0] ^ m[12] ^ m[4] ^ m[14] ^ m[10] ^ m[2] ^ m[12] ^ m[8] ^ m[10] ^ m[4] ^ m[0] ^ m[8] ^ m[2] ^ m[14]
m[7] = m[7] ^ m[1] ^ m[13] ^ m[5] ^ m[15] ^ m[11] ^ m[3] ^ m[13] ^ m[9] ^ m[11] ^ m[5] ^ m[1] ^ m[9] ^ m[3] ^ m[15]
m[8] = m[8] ^ m[2] ^ m[14] ^ m[6] ^ m[0] ^ m[12] ^ m[4] ^ m[14] ^ m[10] ^ m[12] ^ m[6] ^ m[2] ^ m[10] ^ m[4] ^ m[0]
m[9] = m[9] ^ m[3] ^ m[15] ^ m[7] ^ m[1] ^ m[13] ^ m[5] ^ m[15] ^ m[11] ^ m[13] ^ m[7] ^ m[3] ^ m[11] ^ m[5] ^ m[1]
m[10] = m[10] ^ m[4] ^ m[0] ^ m[8] ^ m[2] ^ m[14] ^ m[6] ^ m[0] ^ m[12] ^ m[14] ^ m[8] ^ m[4] ^ m[12] ^ m[6] ^ m[2]
m[11] = m[11] ^ m[5] ^ m[1] ^ m[9] ^ m[3] ^ m[15] ^ m[7] ^ m[1] ^ m[13] ^ m[15] ^ m[9] ^ m[5] ^ m[13] ^ m[7] ^ m[3]
m[12] = m[12] ^ m[6] ^ m[2] ^ m[10] ^ m[4] ^ m[0] ^ m[8] ^ m[2] ^ m[14] ^ m[0] ^ m[10] ^ m[6] ^ m[14] ^ m[8] ^ m[4]
m[13] = m[13] ^ m[7] ^ m[3] ^ m[11] ^ m[5] ^ m[1] ^ m[9] ^ m[3] ^ m[15] ^ m[1] ^ m[11] ^ m[7] ^ m[15] ^ m[9] ^ m[5]
m[14] = m[14] ^ m[8] ^ m[4] ^ m[12] ^ m[6] ^ m[2] ^ m[10] ^ m[4] ^ m[0] ^ m[2] ^ m[12] ^ m[8] ^ m[0] ^ m[10] ^ m[6]
m[15] = m[15] ^ m[9] ^ m[5] ^ m[13] ^ m[7] ^ m[3] ^ m[11] ^ m[5] ^ m[1] ^ m[3] ^ m[13] ^ m[9] ^ m[1] ^ m[11] ^ m[7]
As you can see, by properties (1) and (2), we can rearrange all the terms and each of them cancel out, except for the first term, which is the original bit itself.
And the data is decoded!!