Encryption and Decryption using Vigenere with Cipher Block Chaining: Up to 50 dollars will be given
Number Systems Dr. Y. Chu CIS3360: Security in Computing 0R02 Spring 2018
1
Information
Required reading: slides
Reference:
http://sandbox.mc.edu/~bennet/cs110/textbook/index.html
2
Importance of Number Systems
Number systems are used in representing addresses and data in computers and networks
Often use binary and hex systems
Some of attacks might cause number overflows
3
Review of Decimal Number System
Decimal system is our everyday number system
Base 10 number system
Digits: 0,1,2,3,4,5,6,7,8,9
Examples
Expansions using powers of 10:
304 = (3x102) + (0x101) + (4x100)
2047 = (2x103) + (0x102) + (4x101) + (7x100)
12.3 = (1x101) + (2x100) + (3x10-1)
43.57 = (4 x 101) + (3 x 100) + (5 x 10-1)
+ (7 x 10-2)
4
Negative exponent
100= 1 (n0 = 1 for all n≠0)
10-1 = 1/101= 0.1(a-b = 1/ab, for all a≠0)
Binary Number System
Foundation of digital system
Base 2 system
0, 1
A binary digit is called a bit
Example: 1010 has 4 bits
Expansion using powers of 2:
1010 = (1x23) + (0x22) + (1x21) + (0x20)
110 = (1x22) + (1x21) + (0x20)
Convert to decimal
Carry out the expansion calculation using decimal expressions
1010 = (1x23) + (0x22) + (1x21) + (0x20) = 8 + 0 + 2 + 0 =10
110 = (1x22) + (1x21) + (0x20) = 4 + 2 + 0 =6
5
Binary Number System
Convert from decimal to binary
6
220
2
110
0
Remainder
2
Quotient
55
2
0
27
2
1
13
2
1
1
6
2
3
2
1
2
0
0
1
1
Result: 11011100
Binary Number System
Bit field
Example
2-bit field has 4 possible combinations: 00, 01, 10, 11. The total number of bit patterns is 4.
Bit field of width n
The total number of bit patterns (possible combinations) is 2n.
The range of numbers that can be represented is 0 to 2n-1.
Recall the relationship between key size and number of possible keys
Byte
8-bit field: 256 different bit patterns and number range from 0 to 255
Significant bit
Left-most bit is the most significant bit, right-most bit is the least significant bit
7
Other Number Systems
Facts
Computers use binary numbers for storage and computation.
Binary numbers are hard for people to work with because they are so long and repetitive
Converting decimal to binary is tedious, at best
Octal and hexadecimal number systems
Higher base than binary
Convert easily from/to binary
8
Octal Number System
Base 8 system
0, 1, 2, 3, 4, 5, 6, 7
3 binary digits represent one octal digit
0 = 000, 1 = 001, 2 = 010, 3 = 011
4 = 100, 5 = 101, 6 = 110, 7 = 111
Octal to binary
Example: 75 octal = 111 101 binary
Binary to Octal
Take 3 bits at a time from right to left.
Replace each 3 bits by a octal digit.
At the end, if you have less than 3 bits left, add zeroes at the left end to make the result an even 3 bits
Replace those 3 bits by an octal digit
Octal to decimal
Expansions to convert to decimal
Example: 75 octal = 7x81 + 5x80 = 61 decimal
9
Hexadecimal Number System
Base 16 number system
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F
4 binary digits represent one hexadecimal digit
0 = 0000, 1 = 0001, 2 = 0010, 3 = 0011
4 = 0100, 5 = 0101, 6 = 0110, 7 = 0111
8 = 1000, 9 = 1001, A = 1010, B = 1011
C = 1100, D = 1101, E = 1110, F = 1111
Works well with byte (8 bits)
1 byte has 2 hexadecimal digits
Hexadecimal (hex) to binary
Example: A5 hex = 1010 0101 binary
Binary to hex
Take 4 bits at a time from right to left.
Replace each 4 bits by a hex digit.
At the end, if you have less than 4 bits left, add zeroes at the left end to make the result an even 4 bits
Replace those 4 bits by a hex digit
Hex to decimal
Expansions to convert to decimal
Example: A5 hex = Ax161 + 5x160 = 10x16 + 5x1 = 165 decimal
10
Negative Numbers
Recall in decimal number system, negative numbers use minus sign (“-”)
Negative numbers in binary number system use sign bits
If the most significant bit (MSB) is a 1, then it represents a negative number
One possibility: One’s complement
Use unsigned binary values for positive numbers
To get the negative value, just "flip" each bit of the positive numbers.
Problem: extra 0
11
Two’s Complement Number System
The other possibility: two’s complement number system
Use unsigned binary values for positive numbers
To get the corresponding negative value, "flip" each bit and add 1 to result
no extra zero this time, and we also have an additional negative value
12
Decimal Expansion for Two’s Complement
The sign bit is the leftmost bit is also MSB
If it is a 1, then it represents a negative number. If it is a 0, it represents a positive number
Decimal expansion
Given n-bit binary number, the value of MSB is either 0 (for positive number) or (-1)x 2(n-1)
The rest digits are expanded as usual
Example: 8-bit binary numbers
11011010
= (-1x27) + (1x26) + (0x25) + (1x24) + (1x23) + (0x22) + (1x21) + (0x20)
= -128 + 64 + 0 + 16 + 8 + 0 + 2 + 0 = -38
1000000
= (-1x27) + (0x26) + (0x25) + (0x24) + (0x23) + (0x22) + (0x21) + (0x20)
= -128 + 0
= -128
11111111
= (-1x27) + (1x26) + (1x25) + (1x24) + (1x23) + (1x22) + (1x21) + (1x20)
= -128 + 64 + 32 + 16 + 8 + 4 +2 +1
= -1
01111111
= (0x27) + (1x26) + (1x25) + (1x24) + (1x23) + (1x22) + (1x21) + (1x20)
= 0 + 64 + 32 + 16 + 8 + 4 + 2 + 1
= 127
13
Largest number in 8-bit two’s complement
Smallest negative number in 8-bit two’s complement
Two’s Complement Arithmetic
Addition
Basics
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0, plus a carry of 1
1 + 1 + 1 = 1, plus a carry of 1
We add bits from right to left and ignore the carries past bit-field width
Example: 4-bit field
Negate
Negate a binary number
Just change all 0s to 1s and 1s to 0s (i.e., flip all bits), and then add 1
Example: 8-bit two’s complement number 0000 1111 (decimal 15)
Flip the bits to get 1111 0000
Add 1, we get 1111 0001
Verify decimal value of 1111 0001
Decimal expansion is: -128 + 64 + 32 + 16 + 1 = -128 + 113 = -15 decimal
Example: 8-bit two’s complement number 1000 1111 (decimal -113)
Flip the bits to get 0111 0000
Add 1, we get 0111 0001
Verify decimal value of 0111 0001
Decimal expansion is: 64 + 32 + 16 + 1 = 113 decimal
14
Two’s Complement Arithmetic
Subtraction
In subtraction, negate the number that is to be subtracted (even if it is negative already), and then add the two numbers
Example: 7-5 (4-bit field)
Negate 5 decimal
5 = 0101
Flip 0101 and add 1, we get 1011
Add 7 and (-5)
7 = 0111, -5 = 1011
Ignore carry into 5th bit, since it is 4-bit field
Then the result is 0010 = 2 in decimal
15
0111
+1011
10010
Carries 1 1 1
Overflow in Two’s Complement
Given a bit-field width, only a limited number of numbers can be represented
The two’s complement arithmetic may generate numbers beyond the limit
Overflow examples
Two positive numbers
4-bit field: 7 + 5
In two’s complement, 1100 = -4 decimal
It is incorrect. Overflow occurs.
4-bit two’s complement can only represent numbers from -8 to +7
The result is beyond the limit
Two negative numbers
4-bit field: (-4) + (-6)
Ignore the carry in 5th bit since it is 4-bit field
0110 = 6 decimal
It is incorrect. Overflow occurs.
4-bit two’s complement can only represent numbers from -8 to +7
16
0111
+0101
1100
Carries 1 1 1
1100
+1010
10110
Overflow Rules in Two’s Complement
Remember we still ignore the carry beyond the bit-field width
Rules for adding numbers of same sign
If we add two positive numbers but get a negative result, the overflow occurs and the result cannot be used.
If we add two negative numbers but get a positive result, the overflow occurs and the result cannot be used.
For subtraction, after negating the number that is to be subtracted, we treat it as addition and follow the same rules
17
Unsigned Binary Number
Given bit-field width of n, unsigned binary numbers can represent numbers 0 to 2n -1
For unsigned binary number, the MSB does not indicate sign but simply a value
The decimal expansions are different for signed and unsigned binary numbers
Example: 4-bit field
1101 is decimal -3 in two’s complement (signed binary number)
1101 is decimal 13 in unsigned binary number
Addition is same process for unsigned as for signed
The results are interpreted differently
Always know you are dealing with signed or unsigned binary numbers
18
Summary
Review of Decimal Number System
Binary Number System
Convert from decimal to binary
Bit field, byte and significant bit
Why We Need Other Number Systems
Octal Number System
Hexadecimal Number System
Negative binary numbers
One’s complement vs. two’s complement
Decimal Expansion for Two’s Complement
Two’s Complement Arithmetic
Addition
Negate
Subtraction
Overflow in Two’s Complement
Unsigned Binary Number
19