2
$\begingroup$

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:-

mysecretpassword (ASCII)

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

|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – rath Sep 15 '13 at 16:40
  • $\begingroup$ 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? $\endgroup$ – thefragileomen Sep 15 '13 at 17:38
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Sep 15 '13 at 18:15
  • 2
    $\begingroup$ 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. $\endgroup$ – B-Con Sep 15 '13 at 20:27
3
$\begingroup$

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?

Why Addition Mod 32?

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks @Richie although still confused somewhat. I've edited my original question to clarify things $\endgroup$ – thefragileomen Sep 18 '13 at 22:26
  • 1
    $\begingroup$ 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 $\endgroup$ – Richie Frame Sep 19 '13 at 6:08
  • $\begingroup$ When the sum of what hits 264? How can binary values of 0 and 1 equal 264 (meant to read as small 64 but unable to type these on phone) $\endgroup$ – thefragileomen Sep 19 '13 at 10:42
  • $\begingroup$ It is not done in binary, it is done on a number line where 18446744073709551616 is equal to 0, it is quite literally addition, just like adding numbers on a calculator. This is not addition in binary (XOR) $\endgroup$ – Richie Frame Sep 19 '13 at 17:02
  • $\begingroup$ Thanks again @Richie. Where did you get the figure of 18446744073709551616 from? The original part is XORd though isn't it or am I wrong in my edited post with XORing the binary? $\endgroup$ – thefragileomen Sep 19 '13 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.