# Inverting the encryption equation of a symmetric cipher

I've just started a cryptography course. I am beginning to understand the concepts (I'm only in week 2) but I just can't get my head around the theories and principles when written as equations.

I've been posed the below question to answer:

Consider a very simple symmetric block encryption algorithm in which 64-bit blocks of plaintext are encrypted using a 128-bit key. Encryption is defined as:

$$C = (P ⊕ K_0) ⊞ K_1$$

Show the decryption equation, that is, show the equation for $P$ as a function of $C$, $K_0$ and $K_1$

• $C$ = ciphertext
• $P$ = plaintext
• $K$ = secret key
• $K₀$ = leftmost 64 bits of secret key
• $K₁$ = rightmore 64 bits of secret key
• $⊕$ = bitwise exclusive or (XOR)
• $⊞$ = addition mod $2^{64}$

I simply don't understand what the function of $⊞$ serves.

Can anybody assist me with tackling this problem? I just don't know where to start other than to $P = (C.....)$ possibly? I'm unsure as to what the 'addition mod 2⁶⁴' refers too.

EDITED FOR CLARIFICATION

So if for example, our plaintext is:-

messagea (ASCII)

01101101 01100101 01110011 01110011 01100001 01100111 01100101 01100001 (binary - 64 bit)

and our 128-bit secret key is:-

01101101 01111001 01110011 01100101 01100011 01110010 01100101 01110100 01110000 01100001 01110011 01110011 01110111 01101111 01110010 01100100 (binary - 128 bit)

To achieve the first past of the algorithm, "C=(P⊕K₀)", I XOR the plaintext against the first 8 characters (64 bits) of the secret key to get the following:-

01101101 01100101 01110011 01110011 01100001 01100111 01100101 01100001

01101101 01111001 01110011 01100101 01100011 01110010 01100101 01110100 ⊕

00000000 00011100 00000000 00010110 00000010 00010101 00000000 00010101

Now, how do I then apply '⊞K₁' to the above? I am aware that I need to do something with the above to the last 64-bits of the key but I'm unsure what calculation. If someone could walk me through it, that'd be great. Thanks

-
You mean you don't understand the notation or what modulo is, or why it would be necessary in this particular case (eg. what is gained by using it)? Also please consider adding a link to the course. It's not important, just for completeness sake. Cheers – rath Sep 15 '13 at 16:40
Thanks @rath. Yes, I'm sure as to what "addition mod 2⁶⁴" does in this function. As far as I can understand, the equation means "the ciphertext is equal to the plaintext being XOR'd by the value of the leftmost 64 bits of the secret key and then this value is then XOR'd again with the value of the rightmost 64 bits of the secret key. Am I reading it correctly? – thefragileomen Sep 15 '13 at 17:38
@thefragileomen, no, that's not right. The $\boxplus$ symbol is addition modulo $2^{64}$, not XOR. So, it's not XOR-ed with the rightmost 64 bits of the key, it is added to the rightmost 64 bits of the key (modulo $2^{64}$). Also, can you edit your question to add a link to the course, and to clarify what question you are asking (in response to rath's comments)? You can click the "edit" button below your post to edit it. – D.W. Sep 15 '13 at 18:15
Not to dissuade you from asking cryptography questions here, but that course has a discussion forum with participants and TAs who should be familiar with the current state of the course and the recently covered material, which will give them good insight into answering questions like this. – B-Con Sep 15 '13 at 20:27

Addition modulo $N$ in the above example is another way of key mixing that adds more non-linearity to the cipher as it operates across a group of $N$ bits, vs XOR which is addition modulo 2 on individual bits. For example, where $N=2^6$ or 64:

$44 ⊞ 44 = 24$

$44 ⊕ 44 = 0$

Addition within larger groups is also used in mixing operations such as Pseudo Hadamard Transformations. Key addition instead of XOR also plays a prominent role in the block ciphers Twofish and IDEA.

Edit: Here are posts with more detail on the choice of addition:

What exactly is addition modulo $2^{32}$ in cryptography?

It really just means that when the sum hits $2^{64}$ it loops to 0 and keeps going, since there are only 64 bits to hold the value, and 65 are required for values $2^{64}$ and larger – Richie Frame Sep 19 '13 at 6:08