Transcript x,y

Cryptography: Algorithms on Numbers
A Typical Setting
Alice
x
Encoder
e(x)
Bob
Decoder
x = d(e(x))
Eve
Encryption Function
Decryption Function
e: <messages>  <encoded messages>
d: <encoded messages>  <messages>
Goal: Design e() and d() so that without knowing d(), e(x) gives away
very little information
2
Codes in History
405 BC: the Greek general LYSANDER
OF SPARTA was sent a coded message
about an impending Persian attack
written on the inside of a servant's
belt. To decipher it, it had to be
wound on a staff (scytale). The
spartans were forewarned, and
defeated the persians
Caeser’s cipher: message sent by
Caeser to Cicero during Gallic Wars
3
Codes in History
1586 AD: Mary, Queen of Scotts tried
for plotting against Queen Elizabeth of
England
As evidence, Francis Walsingham
presented encrypted letters written
by Mary, supporting the plot.
4
Codes in History: World War I
Jan 1917: Telegram sent by Arthur
Zimmerman, foreign secretary of
Germany: asking Mexican govt. to
attach United States
Feb 1917: Message was decoded by
British Intelligence and delivered to
president Woodrow Wilson
April 1917: US declares war on
Germany
5
Codes in History: World War II
Bombe: decryption machine
Built by British Intelligence
Blechtley park: center
of British Intelligence
Enigma: German
Encryption machine
German submarine locations were communicated by encrypted messages using Enigma
Made it easy for Allied forces to destroy German submarines
Alan Turing: contributed significantly to Allied cryptography effort
6
Secret Writing
Steganography:
 steganos=covered, graphein=to write
 (Chinese) hidden messages on silk, covered in wax
 (Italy) write message on hard boiled egg that penetrates and stays on the albumen
 Invisible ink that shows up on heating
Cryptography: kryptos=hidden, graphein=to write
7
Private Key Protocols
8
Private-Key Protocol
Alice and Bob meet beforehand and choose secret e() and d() functions
Disadvantage: Need to meet beforehand
Example:
Choose secret string r, e.g. r=01110010
Encryption
e(x) = x  r
e.g. : e(11110000) = 11110000  01110010 = 10000010
Decryption
d(y) = y  r
e.g.: d(10000010) = 10000010  01110010 = 11110000
Problem:
e(x)  e(x’) = (x  r)  (x  r) = (x  x’)
Some information can come out by repeated use
9
Private-Key Protocol: AES
Advanced Encryption Standard (AES)

Also known as Rijndael

Block Cipher
Developed by Belgian mathematicians

Vincent Rijmen Joan Daemen
Approved by the US Govt. in 2001


Repeated use possible

Security not rigorously established..
10
Visual Cryptography
Share 1
original
Share 2
Share 3
Share 4
11
Visual Cryptography
Shares 1, 2
Shares 1,3
Shares 3,4
12
Public Key Protocol
Bob’s padlock (publicly available)
13
Public Key Cryptosystems: RSA

Alice encrypts using Bob’s publicly available key e()

Bob decodes using his private function d()

Alice, Bob need not have met before

Computation easy if e() and d() known
-----BEGIN PGP PUBLIC KEY BLOCK----Version: 2.6.2
mQCNAzKEgQgAAAEEALoDOnC4PKs4+G5LBXm5aP4djv56wm9kOCzpk4eEcpm0jNtl
IKyuAf1EXauFVCFSCri11hwUCXm5kv4x5bNYyE6NqxY29G9VU4Niwmt7L8dGIqHu
kS4FXcufA6sSMfoM8+oIzOv8d18dYhyf4PvAyl43EPgne/pw1c4T3nOFCCzVAAUR
tClEb25hbGQgQSBXYXRyb3VzIDx3YXRyb3VzQGNzLnJ1dGdlcnMuZWR1PokAlQMF
EDLWfyakXBby1t0uxQEBRNYD/jbc7ujRpCSI6uVLdDprzaYiCMgAajLyK53zrMrE
Oj+zURDIMRVtPT2ugVHPUQFoXRMaXKi0IacI2WjetgHgaCwzra2swVj1sp2sFbr1
9bhDzTlf6gosbcmXcRzhGC76jVowphSfw6KN3/VAYyBxI/RtkDN/dKLrRDnniGSO
M6X7iQCVAwUQMoSKmM4T3nOFCCzVAQE7dAP/SjXFV5XdvRLdjh6NoT2NIsaTceMn
mXGsTAk4OM6DQztlM822uru9d0PoeTBu4som50T3C4BS6S54h7QoThwo96s0lgz7
ljcQozW1fKMSGVD+BQ5DO81DNnsZeT48OEZueUEzrMiazPMrlpkZNf1meD1A2JvI
ThxQ3V71HwUvu5Q=
=i41f
-----END PGP PUBLIC KEY BLOCK----14
Rivest-Shamir-Adleman (RSA) Cryptosystem
Need the following tools
 Modular arithmetic
 Euclid’s algorithm
 Primality testing
 Generating random primes
15
Two’s complement method for storing signed integers
n-bits used to represent numbers in the range [-2n-1,2n-1-1]
n-1-1: in regular binary
 Storing positive numbers in the range 0 to 2
with leading bit 0
n-1:
 Storing negative numbers -x with 1 ≤ x ≤ 2
Construct x in binary
Flip all bits of x
Add 1
 Equivalent description:
Store modulo 2n
Negative numbers get stored as 2n - x = 2n-1 - x + 1
 Example: n=4
(5)10 = (0101)2
-5 stored as 1010+1 = 1011
Equivalently: 1111 - 0101 + 1 = 1010 + 1









16
Integer Multiplication
1 3
X 1 1
1 3
1 3
1 4 3
1 1 0 1
X 1 0 1 1
(13)2
(11)2
1 1 0 1
1 1 0 1
0 0 0 0
1 1 0 1
1 0 0 0 1 1 1 1
(143)2
Time Complexity
• Each row has n bits
• n rows
• O(n2) time
17
Al-Khwarizmi’s method

Write #s next to each other
11
13

Divide first # by 2, multiply second
5
26
2
52
1
104
by 2, rounding the result

Keep going till first # gets down to 1

Strike out all rows in which first #
is even

143
Add what remains in column 2
Combination of Binary and Decimal!
18
Al-Khwarizmi’s method
Multiply (x,y)
Input: two n-bit #s x,y
Recursive algorithm
Output: their product

If y=0, return 0

z = Multiply (x, y/2)

If y is even return 2z

Else return x+2z
Running Time

Each recursive call halves y  #bits
reduces by 1  O(n) recursive calls

Each recursive call:




Division by 2: O(n) steps
Test for odd/even: O(1)
Still O(n2) time overall
Can we muliply faster?
Divide-and-Conquer approach gives
a o(n2) time algorithm
One addition: O(n)
O(n) per recursive call
19
Integer Division
Divide(x,y)
Example:
Input: n-bit integers x,y, with y≥ 1
Output: Quotient q and remainder r of
Divide(11,3):
x divided by y
11 = 3· 3 + 2

If x=0: return (q,r) = (0,0)
q = 3, r = 2

(q,r) = divide(x/2,y)

q = 2q, r = 2r
(1,2) = divide(5,3)

If x is odd: r=r+1
q = 2, r = 4

If r ≥ y: r = r-y, q = q+1
11 is odd => r=5

return (q,r)
r=5 > 3 => r = 2, q = 3
20
Factorization
Factors and prime numbers
Simplest algorithms for finding factors
21
Prime Numbers
Definition A number a if prime if the only factors it has are 1 and a
Examples 6 is not a prime: it has factors 2 and 3
5 is a prime
Checking for primality of number N
 Naive method: test all numbers 2 ,…, N-1 for factors
 Suffices to test only up to √N
25 tests to make!
 Too slow to do if N has 500 bit - 2
 Faster method based on Fermat’s theorem
•French lawyer, govt. official, did math in his spare time
•Fermat’s last theorem took 357 years to be proved!
1601-1665
22
Modular Arithmetic
Seconds: counted modulo 60
Minutes: counted modulo 60
Hours: counted modulo 12
Days of the week: counted modulo 7
Keeps numbers from getting too big
Computer Arithmetic: modulo 232
23
Modular Arithmetic
x  y (mod N)  N divides (x-y)
Complexity of computing x (mod N)
Examples:
253  13 (mod 60)
59  -1 (mod 60)
Equivalence classes:
Modular arithmetic deals with all integers but divides them into
N equivalence classes of the form {i+kN : k is an integer}
Equivalence classes modulo 3:
…..
…..
…..
-9 -6 -3 0 3 6 9
-8 -5 -2 1 4 7 10
-7 -4 -1 2 5 8 11
…….
…….
……..
24
Modular Arithmetic
Substitution Rule
If x  y (mod N) and x’  y’ (mod N), then:
x + x’  y + y’ (mod N), and xx’  yy’ (mod N)
Proof?
Example: 14 + 10 (mod 3)  2 + 1 (mod 3)  0 (mod 3)
14 · 10 (mod 3)  2 · 1  (mod 3)  2 (mod 3)
Associative rule: x + (y + z)  (x + y) + z
x(yz)  (xy)z
(mod N)
(mod N)
Commutative rule: x + y  y + x
xy  yx
(mod N)
(mod N)
Distributive rule: x(y+z)  xy + xz
(mod N)
Example: (2)345  (25)69  (32)69  (1)69  1 (mod 31)
25
Implementing modular addition and multiplication
Adding x and y mod N
 Compute x+y  {0,..,2(N-1)}
 If sum exceeds N-1, subtract N
 Running time O(n), where n = log N
Multiplying x and y mod N
2
 Compute x · y  {0,…,(N-1) }
 Number of bits needed to store x · y ≤ 2n
 Divide x · y by N to find remainder
2
 O(n ) running time
26
Modular Division
Multiplicative inverse in real arithmetic
 Every number a  0 has an inverse 1/a
 Example: inverse of 5 is 1/5 = 0.2
 Division by number a  0 is equivalent to multiplying by 1/a
 Example: 10/5 = 10·(1/5) = 10 · (0.2) = 2
Multiplicative inverse modulo N
 x is the multiplicative inverse of a modulo N if ax  1 (mod N)
-1 = 3 (mod 5)
 Example: 2 · 3  1 (mod 5). So (2)
-1 (mod 6)?
 Sometimes there may be no inverse: (2)
 For any x, 2x (mod 6) is even - therefore there is no x such that
2x  1 (mod 6)
27
Modular Exponentiation
Common operation: compute xy (mod N)
 Numbers can become huge:
x, y are 20-bit numbers => xy can be 10 million bits long
 Can be computed by repeated multiplications
x mod N  x2 mod N  ….  xy mod N
Take y multiplications
Suppose y is 500 bits long? 2500 multiplications!




28
Repeated Squaring
Modexp(x, y, N)
Input: n-bit integers x and N, and
integer exponent y
Recursive rule
Output: xy mod N

If y=0: return 1

z = modexp(x, y/2, N)

If y is even: return z2 mod N

Else: return x·z2 mod N
(xy/2)2, if y is even
xy =
x· (xy/2)2, if y is odd
Running Time

Each recursive call halves the
exponent

O(n) multiplications

O(n3) time overall
29
Greatest Common Divisor
Given numbers a, b:
gcd(a,b) = largest number d that divides both a and b
Example
1035 = 32 · 5· 23, 759 = 3 · 11 · 23
gcd( 1035, 759) = 3 · 23 = 69
gcd can be computed by complete factorization, but no efficient
algorithm is known for factorization
Euclid’s algorithm: First known algorithm
in history
BC 325-265
30
Useful properties for computing gcd
Symmetry
gcd(x,y) = gcd(y,x)
Euclid’s Rule
If x, y are positive integers with x ≥ y, then
gcd(x,y) = gcd (x mod y, y)
Example
gcd(24, 15) = gcd(23· 3, 3·5) = 3
gcd(24 mod 15, 15) = gcd(9, 15) = gcd(32, 3·5) = 3
31
Proof of Euclid’s Rule

Sufficient to show that gcd(x,y) = gcd(x-y, y):
Suppose x = qy+r
gcd(x,y) = gcd(x-y,y) = gcd(x-2y, y) = … = gcd(x-qy, y)



Suppose d divides x, y
Then d divides x-y
Therefore, gcd(x,y) ≤ gcd (x-y, y)
Suppose d divides x-y, y
Then d divides x, y
Therefore, gcd(x-y, y) ≤ gcd(x,y)

Property: if d divides x,y,
then d divides ax+by





Therefore, gcd(x,y) = gcd(x-y, y)
32
Euclid’s Algorithm
Euclid(a,b)
Input: Integers a,b with a ≥ b
Output: gcd(a,b)


If b=0: return a
return Euclid(b, a mod b)
Running Time: Need to know how fast the arguments are reducing
33
Analysis of Euclid’s Algorithm
Lemma: If a ≥ b, then a mod b < a/2
Proof:
Case I: b ≤ a/2
a mod b < b ≤ a/2
b a/2
a
Case II: b > a/2
Then, a mod b = a-b < a/2
a/2
b
a mod b
a
a mod b
Running Time:
 In two rounds, both arguments are halved
 #bits reduces by 1 for both arguments
 Base case reached in ≤ 2n recursive calls
2
 Each recursive call: O(n ) time division
3
 O(n ) time overall
34
Another Useful Property
Lemma: If d divides a and b, and d = ax+by for some integers x and y,
then necessarily d = gcd(a,b)
Proof Since d divides a and b, d ≤ gcd(a,b)
Since gcd(a,b) divides a and b, gcd(a,b) divides ax+by = d
 gcd(a,b) ≤ d
Therefore, gcd(a,b) = d
Example
24·2 + 15·(-3) = 3, and 3 divides 24, 15
gcd(24, 15) = 3
When can gcd(a,b) be expressed as ax+by?
Always!!
35
Extended Euclid’s Algorithm
Extended-euclid(a,b)
Input: Positive integers a,b with a ≥ b ≥ 0
Output: Integers x, y, d such that d = gcd(a,b) and ax+by=d



If b = 0: return (1,0,a)
(x’, y’, d) = Extended-euclid(b, a mod b)
return (y’, x’ - a/by’, d)
Example: a = 25, b = 11
25 = 2· 11 + 3
11 = 3· 3 + 2
3 = 1· 2 + 1
2 = 2· 1 + 0
gcd(25, 11) = gcd(11,3)
= gcd(3, 2)
= gcd(2, 1)
= gcd(1, 0)
=1
36
Example (contd.)
25 = 2· 11 + 3
11 = 3· 3 + 2
3 = 1· 2 + 1
2 = 2· 1 + 0
Extended-euclid(1,0) gives: ( 1, 0, 1)
Extended-euclid(2,1) gives: ( 0, 1 - 2·0, 1) = ( 0, 1, 1)
Extended-euclid(3,2) gives: ( 1, 0 - 1·1, 1) = ( 1, -1, 1)
Extended-euclid(11,3) gives: ( -1, 1 - 3·(-1), 1) = ( -1, 4, 1)
Extended-euclid(25,11) gives: ( 4, -1 - 2·4, 1) = (4, -9, 1)
25 · 4 + 11 · (-9) = 1
37
Proof of Extended Euclid’s algorithm
Lemma: For any positive integers a and b, extended-euclid(a,b) returns
integers a, y and d such that gcd(a,b) = d = ax + by
Proof: The computation of gcd is unchanged. So d = gcd(a,b)
Proof by induction on b:
Base case: b=0. Then gcd(a,0)=a = a·1 + b·0
Induction: consider extended-euclid(a,b)
Since a mod b < b, by induction, we have integers x’, y’ such that
gcd(b, a mod b) = bx’ + (a mod b)y’
= bx’ + (a - a/bb)y’
= ay’ + b(x’ - a/by’)
Therefore, gcd(a,b) = gcd(b, a mod b) = ax + by,
where x = y’, y = x’ - a/by’
38
Modular Division
Recall
x is the multiplicative inverse of a modulo N if ax  1 (mod N)
Some times there is no inverse, e.g. (2)-1 (mod 6)
Modular division theorem For any a mod N, a has a multiplicative
inverse modulo N if and only if gcd(a,N)=1. When this inverse exists, it
can be computed in O(n3) time by the Extended-euclid algorithm.
Proof
Suppose (a,N)=1
 Extended-euclid() algorithm gives us integers a, y s.t. ax + Ny = 1
 Therefore, ax  1 (mod N)
Suppose there is an x s.t. ax 1 (mod N). Suppose gcd(a,N) = d.
 Then ax = Nq + 1 for some integer q
 d divides ax and Nq. Therefore, d divides 1, i.e., d=1
39
Prime Numbers
Definition A number a if prime if the only factors it has are 1 and a
Examples 6 is not a prime: it has factors 2 and 3
5 is a prime
Checking for primality of number N
 Naive method: test all numbers 2 ,…, N-1 for factors
 Suffices to test only up to √N
25 tests to make!
 Too slow to do if N has 500 bit - 2
 Faster method based on Fermat’s theorem
•French lawyer, govt. official, did math in his spare time
•Fermat’s last theorem took 357 years to be proved!
1601-1665
40
Fermat’s Little Theorem
Theorem (year 1640) If p is a prime, then for every 1 ≤ a < p,
ap-1  1 (mod p).
Example p = 5
24 = 16  1 (mod 5)
34 = 92  42 = 16  1 (mod 5)
44 = 162  12 = 1 (mod 5)
p=7, a=3
36  (32)3  23  1 (mod 7)
41
Effect of multiplying by a
p = 7, S = { 1, 2, 3, 4, 5, 6}
Multiplying by a=3 has the effect of permuting the elements of S
1
2
1
2
3
3
4
4
5
5
6
6
S = { 1, 2, 3, 4, 5, 6}
= { 3 · 1 mod 7, 3 · 2 mod 7, 3 · 3 mod 7,
3 · 4 mod 7, 3 · 5 mod 7, 3 · 6 mod 7 }
Multiplying the elements of both sets gives
6!  36 · 6! mod 7
Dividing by 6! (why can we do this?):
36  1 (mod 7)
Can we do this for any p?
42
Proof of Fermat’s Little Theorem
S = { 1, 2, …, p-1}
Claim The numbers a · i mod p are distinct for i  S
Proof Suppose a · i  a · j mod p. Dividing by a, we have i  j mod p
Therefore, S = { a · 1 mod p, a · 2 mod p, … , a · (p-1) mod p }
Multiplying the elements of both sets
(p-1)!  ap-1 (p-1)! mod p
Dividing by (p-1)!, we get ap-1  1 (mod p)
43
A “factorless” test for Primality
Pick
Some a
Is aN-1  1 mod N ?
Pass
Fail
“prime”
“composite”
Problem Fermat’s test is not an if-and-only-if test
 Does not say what happens if N is not a prime
 Example: N=341 = 11·13 is not a prime, but 2340  1 mod 341  2 is
a witness for 341 being composite
 If N is composite, are there a lot of witnesses?
 True for almost all composite numbers
44
Example
N=9
28  4 (mod 9)
38  0 (mod 9)
48  7 (mod 9)
58  7 (mod 9)
68  0 (mod 9)
78  4 (mod 9)
88  1 (mod 9)
Algorithm makes a mistake only if it chooses a=8
let A = { a: aN-1  1 (mod N) }
If we pick a not in A, aN-1  1 (mod N) : such a number is a “witness” for
the non-primality of N
How many witnesses can there be for a composite number?
45
Carmichael Numbers
Definition N is a carmichael number if for every number a < N, we have
aN-1  1 (mod N)
Smallest carmichael number: 561 = 3 · 11 · 17
Such numbers are exceedingly rare….
For almost all composite numbers, there are enough witnesses
46
Using Fermat’s Little Theorem
Lemma If aN-1  1 mod N for some a relatively prime to N, then it must
hold for at least half the choices of a < N
Proof Fix some value of a such that aN-1  1 mod N. Suppose b < N
Satisfies the test, i.e., bN-1  1 mod N.
Then, (a·b)N-1  aN-1·bN-1  aN-1  1 mod N
Let S be the set of all b < N that pass the test. Then, all the numbers a
· b, where b  S, fail the test. These numbers are distinct (why?).
Therefore, ignoring Carmichael numbers, we can assert the following:
If N is prime, then aN-1  1 (mod N) for all a < N
If N is not prime, then aN-1  1 (mod N) for at most half the values of a
<N
47
Test for Primality
Primality ( N)
Input: Positive integer N
Output: yes/no
 Pick a positive integer a < N uniformly at random
N-1  1 (mod N): return yes
 if a
 else: return no
Running Time O(n3)
let A = { a: aN-1  1 (mod N) }
Property
Pr[ Primality(N) returns yes when N is prime] = 1
Pr[ Primality(N) returns yes when N is not prime]
= |A|/(N-1) ≤ 1/2
Error
probability
48
Reducing the error probability
Primality2 (N)
Input: Positive integer N
Output: yes/no



Pick positive integers a1, a2, …, ak < N at random
If aiN-1  1 (mod N) for all i=1, …, k:
– return yes
Else: return no
Running Time O(kn3)
Pr[ Primality2(N) returns yes when N is not prime] ≤ 1/2k
For k=10, error probability ≤ 0.001
49
RSA Protocol
Bob chooses his public and secret keys
 Pick two large n-bit random primes p and q
 His public key is (N,e), where N = pq, and e is any 2n-bit number
relatively prime to (p-1)(q-1)
-1 (mod (p-1)(q-1)), computed using Extended His secret key is d = (e)
euclid algorithm
Alice wishes to send message x to Bob
 She looks up his public key (N,e)
e
 She sends him y = x mod N, computed using algorithm modexp
Bob decodes message y
d
 He computes x = y mod N
50
Example: RSA protocol
Let p = 5, q = 11
Then, N = 5 · 11 = 55
Let e = 3. Then, d = (e)-1 (mod 40) = 27 (mod 40)
gcd( e, (p-1)(q-1)) = gcd( 3, 40) = 1
Encryption of message x
y = x3 (mod 55)
e.g. x = 13
Then, y = 133 ( mod 55)  169 · 13 (mod 55)
 4 · 13 (mod 55)  52 (mod 55)
Decryption of y
x = y27 (mod 55)
For y = 52, x = (52)27 mod 55  (-3)27 mod 55  13 mod 55
51
Analyzing RSA
Property: Let p and q be two primes and N=pq. For any e relatively
prime to (p-1)(q-1):
1. The mapping x  xe mod N is a bijection on {0, …, N-1}
2. The inverse mapping is simple: let d = (e)-1 mod (p-1)(q-1). Then, for
all x  {0, …, N-1}:
(xe)d  x (mod N)
Property 1  every message is encoded in a unique manner - no
information is lost
Property 2  decoding possible
52
Proof






Property 2  the map in Prop. 1 is invertible  it is a bijection
– Suffices to prove property 2
ed  1 mod (p-1)(q-1)
 ed = 1+k(p-1)(q-1) for some integer k
Then, xed - x = x1+k(p-1)(q-1) - x
Statement true if x  0 (mod p) and x  0 (mod q)
Suppose x  0 (mod p) and x  0 (mod q)
Then, xp-1  1 (mod p) and xq-1  1 (mod q)
x1+k(p-1)(q-1) - x  0 (mod p)
x1+k(p-1)(q-1) - x  0 (mod q)
Therefore, pq=N divides xde - x
Suppose x  0 (mod p). Then x  0 (mod q)
x1+k(p-1)(q-1) - x  0 (mod q), as before
x1+k(p-1)(q-1) - x  0 (mod p), since p divides x
Therefore, N=pq divides xde - x








53
Security of RSA protocol
Given y = xe mod N, and (N,e), how can x be retrieved?




Blind guess? Too many choices
Factor N to compute p, q and then find d=(e)-1 mod (p-1)(q-1)
Factorization is believed to be hard
Small errors in estimation of d can lead to significant # errors
p=5, q=11, N=55
e = 3. Then, d = (e)-1 (mod 40) = 27 (mod 40)
Let x=13. Then y = x3 (mod 55)  52 (mod 55), y27 mod 55  13
Suppose d’=25 (slightly incorrect estimate of secret key)
y25 mod 55  (-3)25  (-3)6X4+1  (14)4(-3)  32





54
Authentication


Anyone can pretend to be Alice and send a message to Bob
Using RSA to authenticate the message: digital signatures
55