8
\$\begingroup\$

I am going through the example of SHA256 over at Wikipedia and wanted to make sure I understood all the operations of the manipulation math before trying to actually attempt the implementation itself. The comments explain the entire thing.

Want I want to know is:

  1. Are my operations correct? The SHA256 code seems to be limited to manipulating 32 bit values in a 512 bit array, so I have made the first input 32 bit to make sure that this example rig is adequate.
  2. Can my operations be trivially improved? For example, am I making some awful decisions that are causing massive slowdown? I know compared to real crypto it's not going to even compare, I'm not doing real crypto, I'm just playing, but I would like to know if I have made some mega obvious efficiency mistakes.

# Test rig for simple SHA256 operations

# rightrotate
# rightshift
# XOR
# NOT
# AND

# We'll do most operations to two input binary values
# We'll choose a misc value for rotate and shift
# We'll only operate rotate and shift on the first input

def printtest_set ( test_set ):
    ""
    for x in range(len(test_set[0])):
        print(test_set[0][x],'\t\t',test_set[1][x])

if __name__ == '__main__':

    # Construct expected datatype
    # 32 bit

    # test_set some variables up

    # rotate value
    rotate_amount = 7

    # shift amount
    shift_amount = 7

    # Create the array
    test_set = [[0 for x in range(7)] for x in range(2)]

    # Titles
    test_set[0][0] = 'Input 1'
    test_set[0][1] = 'Input 2'
    test_set[0][2] = 'rightrotate'
    test_set[0][3] = 'rightshift'
    test_set[0][4] = 'XOR    '
    test_set[0][5] = 'NOT    '
    test_set[0][6] = 'AND    '

    # Values 
    test_set[1][0] = '00010001000100010001000100010001'
    test_set[1][1] = '1010101010100001'
    test_set[1][2] = ''
    test_set[1][3] = ''
    test_set[1][4] = ''
    test_set[1][5] = ''
    test_set[1][6] = ''

    print ('\n\nInputs:\n')
    printtest_set(test_set)

    # test_set all data to the same length
    length_max = 0
    for x in range(len(test_set[0])):
        # Get length of data, then store only if it's the largest
        length = len(test_set[1][x])
        if length > length_max:
            length_max = length

    # Now pad the shorter data with '0' until they are all the same length
    for x in range(len(test_set[0])):
        if len(test_set[1][x]) < length_max:
            # Get the length
            current_length = len(test_set[1][x])

            # Now pad with '0'
            for y in range(length_max - current_length):
                test_set[1][x] += '0'

    # Now print the pre-processed values
    print ('\n\nPre-processed inputs:\n')
    printtest_set(test_set)

    # rightrotate
    test_set[1][2] = ''
    tmp = ''

    y = 0
    for x in range(rotate_amount):
        tmp += str(int(test_set[1][0][len(test_set[1][0]) - 1 - y]))
        y += 1

    for x in range(len(test_set[1][0]) - rotate_amount):
        tmp += str(int(test_set[1][0][x]))  

    test_set[1][2] = tmp

    # rightshift
    test_set[1][3] = ''
    tmp = ''
    for x in range(shift_amount):
        tmp += '0'

    for x in range(len(test_set[1][0]) - shift_amount):
        tmp += str(int(test_set[1][0][x]))

    test_set[1][3] = tmp

    # XOR
    # only true if just one of the inputs is true, but not both
    test_set[1][4] = ''
    tmp = ''
    for x in range(len(test_set[1][0])):
        tmp += str(int(test_set[1][0][x]) ^ int(test_set[1][1][x]))

    test_set[1][4] = tmp

    # NOT
    # not x, if x is false then true, else false
    test_set[1][5] = ''
    tmp = ''
    for x in range(len(test_set[1][0])):
        tmp += format(not(test_set[1][0][x] == test_set[1][1][x]), 'x')

    test_set[1][5] = tmp

    # AND
    # If both are true, then true, if any false, then false
    test_set[1][6] = ''
    tmp = ''
    for x in range(len(test_set[1][0])):
        tmp += str(int(test_set[1][0][x]) & int(test_set[1][1][x]))

    test_set[1][6] = tmp

    # Print final results (outputs)

    print ('\n\nOutputs:\n')
    printtest_set(test_set)

Output:

Inputs:

Input 1                  00010001000100010001000100010001
Input 2                  1010101010100001
rightrotate
rightshift
XOR
NOT
AND


Pre-processed inputs:

Input 1                  00010001000100010001000100010001
Input 2                  10101010101000010000000000000000
rightrotate              00000000000000000000000000000000
rightshift               00000000000000000000000000000000
XOR                      00000000000000000000000000000000
NOT                      00000000000000000000000000000000
AND                      00000000000000000000000000000000


Outputs:

Input 1                  00010001000100010001000100010001
Input 2                  10101010101000010000000000000000
rightrotate              10001000001000100010001000100010
rightshift               00000000001000100010001000100010
XOR                      10111011101100000001000100010001
NOT                      10111011101100000001000100010001
AND                      00000000000000010000000000000000
\$\endgroup\$
  • 1
    \$\begingroup\$ the XOR, NOT and AND are simple to tell if they work or not you just line them up and do it manually, and it looks like those three are functioning properly to me \$\endgroup\$ – Malachi Jun 12 '14 at 18:37
  • \$\begingroup\$ What's the difference between my NOT and XOR? They seem to have the exact same output, is that meant to be the case? \$\endgroup\$ – Joseph Jun 12 '14 at 18:44
  • 1
    \$\begingroup\$ the Right Shift looks about right based on en.wikipedia.org/wiki/Logical_right_shift \$\endgroup\$ – Malachi Jun 12 '14 at 18:44
  • \$\begingroup\$ @Joseph they are the same, check this stackoverflow.com/a/4175515/1214743 \$\endgroup\$ – Malachi Jun 12 '14 at 18:44
  • \$\begingroup\$ the right rotate I think might be off though, and you didn't specify if it is a rotate with a carry or without \$\endgroup\$ – Malachi Jun 12 '14 at 18:46
4
\$\begingroup\$

You are using relatively basic Python bitwise operations to do most of your calculations. So there will not be too much efficiency found there; though I do have some pointers:

  1. You can use the right shift operator >> for your right shift calculation.
  2. The logical NOT operation is a unary operation, that is, it only works on one input. So when you calculate your NOT value, instead of using both inputs (i.e. test[1][0] and test[1][1]) you only should use one value.

  3. You do not need to empty out test_set[1][i] before your calculations. You already did this at the beginning of the program.

You an improve on how you go about these operations: list comprehensions and lambdas are your friends here. Using both of those constructs can not only bring most of your calculations into one statement, but also make your code more Pythonic.


As Morwenn said, test_set is better served as a dict. However, unlike his recommendation, I would leave the inputs out of the results dict; and have them in their own structure. It will make processing easier from here on out:

inputs = {'1': '00010001000100010001000100010001', '2': '1010101010100001'}

The maximum length can be easily found using the max function:

max_len = max([len(char) for char in inputs.values()])

Padding on zeros is just as easy:

inputs = {key: num + '0'*(max_len-len(num)) for key, num in inputs.items()}

We only really need to do this on the inputs dictionary because we are just going to programmatically create the outputs. Appending on the zeros to the outputs is simply wasted processing.

To show an example of using lambdas and list comprehensions, to do your XOR function, you can:

xor = lambda x,y: int(x) ^ int(y)
results['XOR'] = ''.join([str(reduce(xor, group)) for group in zip(*inputs.values())])

Here is my version of your code:

NOTE: I've made some changes so that these operations can take an arbitrary number of inputs.

def perform_operations(inputs, rotate=1, shift=4):
    results = {}

    # Find the maximum input length and pad the other inputs with 0's
    max_len = max([len(char) for char in inputs.values()])
    inputs = {key: num + '0'*(max_len-len(num)) for key, num in inputs.items()}

    # Right rotate
    # I chose to build the result instead of calculate the result because that
    # is the simplest solution (plus the way you did it in your original code).
    results['rightrotate'] = {key: num[-rotate:] + num[:-rotate] for num in inputs.values()}

    # Right shift
    results['rightshift'] = {key:'{:0{}b}'.format(int(num, 2) >> shift, max_len)
                             for key, num in inputs.items()}

    # XOR
    xor = lambda x,y: int(x) ^ int(y)
    results['XOR'] = ''.join([str(reduce(xor, group)) for group in zip(*inputs.values())])

    # NOT
    results['NOT'] = {key:''.join(['{:b}'.format(not int(char)) for char in num])
                             for key, num in inputs.items()}

    # AND
    and_op = lambda x,y: int(x) & int(y)
    results['AND'] = ''.join([str(reduce(and_op, group))
                              for group in zip(*inputs.values())])

    return results
\$\endgroup\$
5
\$\begingroup\$

I don't know about optimization, but test_set seems to scream for a dict. It seems more appropriate than a list of lists, especially since the indices are known and the "titles" never mutate:

test_set = {
    'Input 1'       : '00010001000100010001000100010001',
    'Input 2'       : '1010101010100001'
    'rightrotate'   : ''
    'rightshift'    : ''
    'XOR    '       : ''
    'NOT    '       : ''
    'AND    '       : ''
}

This would allow you to simply many of your algorithms, using element-based loops instead of indices-based ones. For example, you could compute length_max with the following one-liner (untested):

length_max = max([len(elem) for elem in test_set.values()])

In Python, try to use indices-based loops (with range) only if you have to, only if you do need the index. Otherwise, try to always use element-based loops.

\$\endgroup\$

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.