xorshiftcyclic

Xor and Cyclic shift


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


Solution

  • 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);
            }
        }