Transcript COMP4690 Tutorial

COMP4690 Tutorial
Cryptography
&
Number Theory
Outline




DES Example
Number Theory
RSA Example
Diffie-Hellman Example
DES

Some remarks
 DES works on bits
 DES works by encrypting groups of 64 bits, which is the same as
16 hexadecimal numbers
 DES uses keys which are also apparently 64 bits long. However,
every 8th key bit is ignored in the DES algorithm, so the effective
key size is 56 bits.
 If the length of the message to be encrypted is not a multiple of
64 bits, it must be padded. E.g.:



The plaintext message "Your lips are smoother than vaseline" is, in
hexadecimal, "596F7572206C6970 732061726520736D
6F6F746865722074 68616E2076617365 6C696E650D0A".
We then pad this message with some 0s on the end, to get a total of
80 hexadecimal digits: "596F7572206C6970 732061726520736D
6F6F746865722074 68616E2076617365 6C696E650D0A0000".
Then apply DES.
Key generation example



Let K be the hexadecimal key K =
133457799BBCDFF1. This gives us as the
binary key :
K = 0001 0011 0011 0100 0101 0111 0111
1001 1001 1011 1011 1100 1101 1111 1111
0001
16 subkeys (48-bit) will be generated from K.
Key generation example




Based on table PC-1 (Permuted Choice 1),
we get the 56-bit permutation
K+ = 1111000 0110011 0010101 0101111
0101010 1011001 1001111 0001111
Next, split this key into left and right halves,
C0 and D0, where each half has 28 bits.
C0 = 1111000 0110011 0010101 0101111
D0 = 0101010 1011001 1001111 0001111
Key generation example

we now create sixteen blocks Cn and Dn,
1<=n<=16. Each pair of blocks Cn and Dn is
formed from the previous pair Cn-1 and Dn-1,
respectively, for n = 1, 2, ..., 16, using a
“schedule of left shifts".
Round
number
1
2
3
4
5
6
7
8
9
10 11 12 13 14 15 16
Bits
rotated
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1
Key generation example





C0 = 1111000011001100101010101111
D0 = 0101010101100110011110001111
C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110
C2 = 1100001100110010101010111111
D2 = 0101010110011001111000111101
C3 = 0000110011001010101011111111
D3 = 0101011001100111100011110101
……
Key generation example


We now form the subkeys Kn, for 1<=n<=16,
by applying the table PC-2 (Permutation
Choice Two) to each of the concatenated
pairs CnDn.
For the first subkey, we have



C1D1 = 1110000 1100110 0101010 1011111
1010101 0110011 0011110 0011110
After we apply the permutation PC-2:
K1 = 000110 110000 001011 101111 111111
000111 000001 110010
Modular Arithmetic



Two integers a and b are said to be
congruent modulo n, if :
(a mod n) = (b mod n)
This is written as a≡b mod n
Define Zn as the set of nonnegative integers
less than n: Zn={0,1,…,(n-1)}
Modular Arithmetic

Properties of modular arithmetic
Modular Arithmetic



Define Zp as the set of nonnegative integers
less than a given prime number p:
Zp={0,1,…,(p-1)}
Because p is prime, all of the nonzero
integers in Zp are relatively prime to p.
There exists a multiplicative inverse for all of
the nonzero integers in Zp :

For each nonzero w in Zp, there exists a z in Zp
such that w x z ≡ 1 mod p. z is called the
multiplicative inverse of w. Or, z = w-1.
Number Theory


Fermat’s Little Theorem:
ap-1 ≡ 1 mod p


where p is prime and gcd(a,p)=1
E.g.






a = 7, p = 19
72=49≡11 mod 19
74≡121≡7 mod 19
78≡49≡11 mod 19
716≡121≡7 mod 19
ap-1=718=716x72≡7x11=77≡1 mod 19
Number Theory


An alternative form of Fermat’s Little
Theorem:
ap ≡ a mod p


where p is prime and a is any positive integer
E.g.


p=5,a=3,35=243≡3 mod 5
p=5,a=10,105=100000≡10 mod 5≡0
Number Theory

Euler’s Totient Function ø(n)


For prime number p,


The number of positive integers less than n and
relatively prime to n
ø(n)= p – 1
For n = pq where p and q are two different
prime numbers

ø(n)= (p – 1) (q – 1)
Number Theory




Example: ø(21)
From 1 to 21, totally 21 numbers
21 = 3x7, 3 and 7 are prime
3’s multiples:


7’s multiples:


3, 6, 9, 12, 15, 18, 21
7, 14, 21
Other numbers are all relatively prime to 21

21-7-3+1 = (3-1)x(7-1)
Number Theory


Euler’s Theorem
aø(n) ≡ 1 mod n


where gcd(a,n)=1
E.g.




a=3;n=10; ø(10)=4;
hence 34 = 81 ≡ 1 mod 10
a=2;n=11; ø(11)=10;
hence 210 = 1024 ≡ 1 mod 11
Number Theory


The powers of an integer a, modulo n
 a, a2, a3, … (mod n)
If a and n are relatively prime, based on Euler’s theorem, we
have aø(n) ≡ 1 mod n
 a, a2, a3, … will have a repeated pattern
 E.g., ø(5)=4, 3ø(5)=81≡1 mod 5



3, 4, 2, 1, 3, 4, 2, 1, …
There may exist lots of m such that am ≡ 1 mod n
The least positive exponent m such that am ≡ 1
mod n is referred to as



the order of a (mod n)
the exponent to which a belongs (mod n)
the length of the period generated by a
Number Theory
Number Theory

Primitive root


Property of primitive root



If a number’s order (mod n) is ø(n), this number is called a
primitive root of n
If a is a primitive root of n, then its powers a,a2, a3,…,
aø(n) are distinct (mod n), and are all relatively prime to n.
In particular, for a prime number p, if a is a primitive root of
p, then a,a2, a3,…, ap-1 are distinct (mod p).
From the previous table, we can see that prime number 19’s
primitive roots are 2, 3, 10, 13, 14, and 15.
RSA Example
Select primes: p=17 & q=11
Compute n = pq =17×11=187
Compute ø(n)=(p–1)(q-1)=16×10=160
Select e: gcd(e,160)=1; choose e=7
Determine d: de=1 mod 160 and d < 160
1.
2.
3.
4.
5.
•
6.
7.
d=23 since 23×7=161= 10×160+1
Publish public key KU={7,187}
Keep secret private key KR={23,17,11}
RSA Example

given message M = 88

encryption:
C = 887 mod 187 = 11

decryption:
M = 1123 mod 187 = 88
RSA Example

Fast Modular Exponentiation
 To calculate 887 mod 187





881 mod 187 = 88
882 mod 187 = 7744 mod 187 = 77
884 mod 187 = 772 mod 187 = 132
887 mod 187 = 884+2+1 mod 187 = 132x77x88 mod 187 = 894,432
mod 187 = 11
To calculate 1123 mod 187






111 mod 187 = 11
112 mod 187 = 121
114 mod 187 = 14,641 mod 187 = 55
118 mod 187 = 552 mod 187 = 33
1116 mod 187 = 332 mod 187 = 154
1123 mod 187 = 1116+4+2+1 mod187 = 154x55x121x11 mod 187 =
11,273,570 mod 187 = 88
Diffie-Hellman
Key Exchange
Diffie-Hellman Key Exchange

users Alice & Bob who wish to swap keys:
agree on prime q=7 and α=5

select random secret keys:



compute public keys:



A chooses xA=3, B chooses xB=2
3
yA=5 mod 7 = 6
2
yB=5 mod 7 = 4
(Alice)
(Bob)
compute shared session key as:
Alice: KAB=
Bob: KAB=
xA
yB
x
yA B
3
mod 7 = 4 mod 7 = 1
2
mod 7 = 6 mod 7 = 1
Diffie-Hellman Key Exchange

users Alice & Bob who wish to swap keys:
agree on prime q=353 and α=3

select random secret keys:



compute public keys:



A chooses xA=97, B chooses xB=233
97
yA=3 mod 353 = 40
233
yB=3
mod 353 = 248
(Alice)
(Bob)
compute shared session key as:
Alice: KAB=
Bob: KAB=
xA
yB
x
yA B
97
mod 353 = 248 mod 353 = 160
233
mod 353 = 40
mod 353 = 160