Bitwise operation for PRESENT cipher

Question

I am trying to understand the bitwise operation for generating roundkeys. Below is the code given to me:

def generateRoundkeys80(key, rounds):
    """Generate the roundkeys for a 80-bit key
    Input:
            key:    the key as a 80-bit integer
            rounds: the number of rounds as an integer
    Output: list of 64-bit roundkeys as integers"""
    roundkeys = []
    for i in xrange(1, rounds + 1):  # (K1 ... K32)
        # rawkey: used in comments to show what happens at bitlevel
        # rawKey[0:64]
        roundkeys.append(key >> 16)
        # 1. Shift
        # rawKey[19:len(rawKey)]+rawKey[0:19]
        key = ((key & (2 ** 19 - 1)) << 61) + (key >> 19)
        # 2. SBox
        # rawKey[76:80] = S(rawKey[76:80])
        key = (Sbox[key >> 76] << 76) + (key & (2 ** 76 - 1))
        #3. Salt
        #rawKey[15:20] ^ i
        key ^= i << 15
    return roundkeys

What I understood was at (1) we do a 61-bit left rotation (I implemented key = (key << 61)|(key >> (len(key) - 61)) instead) and (2) apply sbox to the leftmost 4 bits and (3) XOR the round counter with bits 15-19. However, I don't understand the meaning of ** and also + when it comes to bitwise operation. Any explanation would be appreciated!

Answer 1

Let's consider the following line in your code and hopefully all of the operations will become clear:

key = ((key & (2 ** 19 - 1)) << 61) + (key >> 19)

Let's start with the expression (2 ** 19 - 1). The operator ** is exponentiation. In the code you presented, it is used to construct binary numbers that will be used as masks in the operations. For example, the number 2 ** 19 in binary will be a "1" followed by 19 zeroes. The number 2 ** 19 - 1 is 19 ones.

When you do (key & (2 ** 19 - 1)), it is a bitwise AND that will give you the last 19 bits of the key and << 61 will add 61 zeroes at the right, so you end up with the last 19 digits of the key followed by 61 zeroes.

(key >> 19) will dump the rightmost 19 digits in the key and move the rest of the digits up, padding with 19 zeroes at the left. So when you add both numbers together, each number only has zeroes where the other has data. + is effectively just putting them together.

You can use print {0.b}.format(key) to see the binary string representation of the number if you want to follow along Python's calculations.