# bitsNbytes.py David MacQuigg 12-March-2010 ''' Python can work with bits and bytes, although it is not as good as C on the machine-level operations. 1) Easy interactive environment for prototyping and experimentation. 2) Long integers and bytearrays for cryptographic keys, etc. 3) Versatile formatting functions for human-readable forms. Run this file in Python 2.6. Try the commands in the >>> examples. ~''' ### Random Bits from random import getrandbits a,b,m = getrandbits(512), getrandbits(512), getrandbits(384) # long integers ''' >>> a 87638194511408989261438753250719754638828743912429765499507120091357674569882808 90862859998699808605307665820696568046132523175744106743803372585080828726L >>> b 57579891920620594921553065324099857848201813159629630310669085501543819427295796 09887603084816533251318617299467986239404540879435342090928431485352784952L >>> m 33980144669810108281160822352744739279623941703077092883034667556498921065193304 60680842427694402677672470050075321L ''' ### Huge exponentials like a ** b (mod m) are common in crypto systems. exp = pow(a, b, m) # pow() is a function written in C - very fast. ''' >>> pow(a, b, m) 26616164385017850397090293477494464399221960596510492575571803619978316656538353 42475518596170907523282061732994456L ''' ### Binary Data ''' Binary data can be represented in various forms - compact and ugly, or easy to read and manipulate, but not as compact. Here are 7 useful forms. ~''' byteray = bytearray(b'/w9\r\x0d\xc9a\xc4') # 8 bytes of binary data hexstring = '2F77390D0DC961C4' # 16 hexadecimal digits longint = 3420265170239840708L # 19 decimal digits bitblocks = ['00101111', '01110111', '00111001', '00001101', # 8 strings '00001101', '11001001', '01100001', '11000100' ] bitstring = '0010111101110111001110010000110100001101110010010110000111000100' bitlist = [0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, # 64 ints 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 ] hexblocks = ''' a766a602 b65cffe7 73bcf258 26b322b3 d01b1a97 2684ef53 3e3b4b7f 53fd3762 24c08e47 e959b2bc 3b519880 b9286568 247d110f e68de835 329e603c c51e7f02 ''' # multiline string copied from a webpage ### Basic Conversions ## Hex strings are often the easiest way to enter binary data. Sometimes, we # need to squeeze out whitespace, including tabs & newlines. hexdata = ' 2F 77 39 0D \t 0D C9 61 C4 \n' hexlist = hexdata.split() # ['2F', '77', '39', '0D', '0D', 'C9', '61', 'C4'] hexstring2 = ''.join(hexlist) # '2F77390D0DC961C4' # individual bytes as integers intlist2 = [b for b in byteray] # [47, 119, 57, 13, 13, 201, 97, 196] hexlist2 = [format(b, '0>2X') for b in byteray] # ['2F', '77', '39', '0D', '0D', 'C9', '61', 'C4'] bitblocks2 = [format(b, '0>8b') for b in byteray] # ['00101111', '01110111', '00111001', '00001101', # '00001101', '11001001', '01100001', '11000100' ] hexint2 = hex(longint) # '0x2f77390d0dc961c4L' hexblocks2 = [hexstring[n:n+8] for n in range(0,len(hexstring), 8)] # ['2F77390D', '0DC961C4'] int2 = int(hexstring, 16) # 3420265170239840708L bitstring2 = ''.join(bitblocks) # '0010111101110111001110010000110100001101110010010110000111000100' int3 = int(bitstring, 2) # 3420265170239840708L bitlist2 = [int(digit) for digit in bitstring] # [0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, # 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, # 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, # 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 ] bitblocks2 = [bitstring[8*i:(8*i + 8)] for i in range(8)] # ['00101111', '01110111', '00111001', '00001101', # '00001101', '11001001', '01100001', '11000100' ] ### Other Conversion Methods Not sure if we should included these. xxx ## bytearrays have a special method to input from hex. # bray2 = bytearray.fromhex('2F 77 39 0D 0D C9 61 C4') # works in Python 3 # TypeError: fromhex() argument 1 must be unicode, not str ustring = u'2F 77 39 0D 0D C9 61 C4' # need explicit unicode in Python 2 bray2 = bytearray.fromhex(ustring) # bytearray(b'/w9\r\r\xc9a\xc4') ## some useful conversions are found in library packages from Crypto.Util.number import bytes_to_long, long_to_bytes bray3 = long_to_bytes(longint) # '/w9\r\r\xc9a\xc4' \r same as \x0d bray4 = long_to_bytes(longint, blocksize=10) # '\x00\x00/w9\r\r\xc9a\xc4' pad 00 on left int4 = bytes_to_long(bray4) # 3420265170239840708L same as longint ### Bit structure of ints and floats This needs some work to show xxx # 2's complement representation of negative ints, and the signs and exponents # in floats. ''' >>> n = 2**35-1 >>> hex(n) '0x7ffffffffL' >>> m = -(2**33 - 1) >>> hex(m) '-0x1ffffffffL' >>> q = m^n >>> for x in [m, n, q]: print hex(x) -0x1ffffffffL 0x7ffffffffL -0x600000002L ~''' ### Advanced Encryption Standard (AES) S-box # typical problem converting hex data to a usable form # cut-and-paste from (http://en.wikipedia.org/wiki/Rijndael_S-box) ''' | 0 1 2 3 4 5 6 7 8 9 a b c d e f ---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--| 00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0 20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf 60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16 ~''' # Use block mode in a text editor to extract the data. AEStext = ''' 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79 e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08 ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16 ''' AEShex = AEStext.split() # ['63', '7c', '77', ... 'bb', '16'] AESint = [int(hx, 16) for hx in AEShex] # [99, 124, 119, ... 187, 22]