Suppose we have this equation c = m ⊕ (m << 6) ⊕ (m << 10) where ⊕ stands for XOR and << for cyclic shift to the left. How can this be written as m in terms of c? What operations must be used?
I tried xoring both sides with c << 6 but didnt result in an equation that has only m
1 Answer 1
Assuming 16 bits for c and m, I started with a system of 16 equations:
m0 = c0 + m6+m10
m1 = c1 + m7+m11
m2 = c2 + m8+m12
m3 = c3 + m9+m13
m4 = c4 + m10+m14
m5 = c5 + m11+m15
m6 = c6 + m0+m12
m7 = c7 + m1+m13
m8 = c8 + m2+m14
m9 = c9 + m3+m15
m10 = c10 + m0+m4
m11 = c11 + m1+m5
m12 = c12 + m2+m6
m13 = c13 + m3+m7
m14 = c14 + m4+m8
m15 = c15 + m5+m9
With an iterative loop of variable eliminations/replacements, I ended up with the following (+ stands for xor):
m0 = c0+c2+c4+c12+c14
m1 = c1+c3+c5+c13+c15
m2 = c0+c2+c4+c6+c14
m3 = c1+c3+c5+c7+c15
m4 = c0+c2+c4+c6+c8
m5 = c1+c3+c5+c7+c9
m6 = c2+c4+c6+c8+c10
m7 = c3+c5+c7+c9+c11
m8 = c4+c6+c8+c10+c12
m9 = c5+c7+c9+c11+c13
m10 = c6+c8+c10+c12+c14
m11 = c7+c9+c11+c13+c15
m12 = c0+c8+c10+c12+c14
m13 = c1+c9+c11+c13+c15
m14 = c0+c2+c10+c12+c14
m15 = c1+c3+c11+c13+c15
On word-level, this can be written as
m = c ⊕ (c << 2) ⊕ (c << 4) ⊕ (c << 12) ⊕ (c << 14)
I wonder, how this word-level form can be derived directly without solving a system of equations.
The bit-level equations are a modulo 2 (GF2) system of equations. This can be solved using Gauss Jordan elimination.
My C# code:
class Program
{
const int Bits = 16;
// several loops make use of this Range
static readonly IEnumerable<int> BitIndices = Enumerable.Range(0, Bits);
// Class represents an xor sum of c and m elements
class CMXorSumExpression
{
int no;
bool[] c = new bool[Bits];
bool[] m = new bool[Bits];
public CMXorSumExpression(int ic)
{
no = ic;
c[ic] = true; // the c bit ic
m[(Bits - 6 + ic) % Bits] = true; // the m << 6 bit
m[(Bits - 10 + ic) % Bits] = true; // the m << 10 bit
}
// Replace m_i element in expression by expression r
public void Replace(int i, CMXorSumExpression r)
{
if ((i != no) && m[i])
// m_i is set => replace it
{
m[i] = false;
c = BitIndices.Select(x => c[x] ^ r.c[x]).ToArray();
m = BitIndices.Select(x => m[x] ^ r.m[x]).ToArray();
}
}
public override string ToString()
{
return $"m{no} = "
+ string.Join("",
BitIndices.Select(x => c[x] ? $"+c{x}" : ""))[1..]
+ " "
+ string.Join("",
BitIndices.Select(x => m[x] ? $"+m{x}" : ""));
}
}
static void Main()
{
// array of bit-level equations
CMXorSumExpression[] cmSumExpressions =
BitIndices.Select(x => new CMXorSumExpression(x)).ToArray();
// show equations
foreach(var e in cmSumExpressions)
{
O($"{e}");
}
// replace operands to eliminate m elements on the right-hand-side
bool changed;
int round = 0;
do
{
changed = false;
O();
O($"round {++round}");
foreach (int i in BitIndices)
foreach (int j in BitIndices)
{
string sBefore = cmSumExpressions[j].ToString();
cmSumExpressions[j].Replace(i, cmSumExpressions[i]);
string sAfter = cmSumExpressions[j].ToString();
if (sBefore != sAfter)
{
O($"before i={i} j={j} cm[j]: {sBefore}");
O($"after i={i} j={j} cm[j]: {sAfter}");
O();
changed = true;
}
}
} while (changed);
// show resulting equations
foreach (var e in cmSumExpressions)
{
O($"{e}");
}
O("ciao!");
}
private static void O(string s = "")
{
Console.WriteLine(s);
}
}
answered Apr 28, 2023 at 17:54
Axel Kemper
11.5k2 gold badges36 silver badges60 bronze badges
Sign up to request clarification or add additional context in comments.
mvalues can produce the samecvalue.