Transcript Analysis of Algorithms

Numerical Algorithms
Chapter 10
1
Facts About Numbers
• Prime number p:
– p is an integer
– p2
– The only divisors of p are 1and p
• Examples
– 2, 7, 19 are primes
 -3, 1, 6 are not primes
• Prime decomposition of a positive integer n:
n = p1e1  …  pkek
• Example:
– 200 = 23  52
Fundamental Theorem of Arithmetic
The prime decomposition of a positive integer is unique
2
Greatest Common Divisor
• The greatest common divisor (GCD) of two positive
integers a and b, denoted gcd(a, b), is the largest
positive integer that divides both a and b
• The above definition is extended to arbitrary integers
• Examples:
gcd(18, 30) = 6
gcd(-21, 49) = 7
gcd(0, 20) = 20
• Two integers a and b are said to be relatively prime if
they have no common factors:
gcd(a, b) = 1
• Example: Integers 15 and 28 are relatively prime
3
Modular Arithmetic
•
•
•
•
•
Modulo operator for a positive integer n
r = a mod n
equivalent to
a = r + kn
and
r = a - a/n n
Example:
29 mod 13 = 3
29 = 3 + 213
13 mod 13 = 0
13 = 0 + 113
-1 mod 13 = 12
12 = -1 + 113
Facts for Euclids Algorithm: Modulo and GCD: as a mod b = r means a
= r + kb
gcd(a, b) = gcd(b, r+kb) =gcd(b,r) = gcd(b,a mod b)
Why? gcd(a, b) = gcd(b, r+kb) everything that divides b already divides kb,
so the only thing of interest is what divides r. (The kb holds no information as
there is no restriction.)
Example:
gcd(21, 12) = gcd(12, 9)= gcd(9,3) = gcd(3,0) = 3
4
Euclid’s GCD Algorithm
• Euclid’s algorithm for
computing the GCD
repeatedly applies the
formula
gcd(a, b) = gcd(b, a mod b)
• Example
– gcd(412, 260) = 4
– Note b decreases by half in
two iterations
Algorithm EuclidGCD(a, b)
Input integers a and b
Output gcd(a, b)
if b = 0
return a
else
return EuclidGCD(b, a mod b)
a
412
260
152
108
44
20
4
b
260
152
108
44
20
4
0
5
Analysis
• Let ai and bi be the arguments of the i-th recursive call of
algorithm EuclidGCD
• We have
ai + 2 = bi + 1 = ai mod ai + 1 < ai + 1
• Sequence a1, a2, …, an decreases exponentially in two rounds,
namely ai + 2  ½ ai for i > 1
Case 1 ai + 1  ½ ai
Case 2 ai + 1 > ½ ai
ai + 2 < ai + 1  ½ ai
ai + 2 = ai mod ai + 1 = ai - ai + 1  ½ ai
• Thus, the maximum number of recursive calls of algorithm
EuclidGCD(a. b) is
1 + 2 log max(a, b)
• Algorithm EuclidGCD(a, b) executes O(log max(a, b)) arithmetic
operations
6
Euclid’s Binary Algorithm
(Faster on computers)
int Algorithm EuclidBinaryGCD(int a,int b){
if (a==0) return b
if (b==0) return a;
if (a mod 2==0 and b mod 2 ==0)
return 2*EuclidBinaryGCD(a/2,b/2)
if (a mod 2==0 and b mod 2 ==1)
return EuclidBinaryGCD(a/2,b)
if (a mod 2==1 and b mod 2 ==0)
return EuclidBinaryGCD(a,b/2)
// gcd(a,b) = gcd(a mod b , b) = gcd(a-kb,b) for any k
// letting k=1. a-b is even.
// since b is odd, we know 2 isn’t a factor, so we can divide it out
// need min(a,b) or otherwise could make problem larger
return EuclidBinaryGCD(|a-b|/2,min(a,b))
}
7
Prove ab mod n = (a mod n)(b mod n)
mod n
• Let a = c +dn
• Let b = e + fn
• ab mod n = (c +dn)(e + fn) mod n
•
=(ce +cfn +dne +dfn2) mod n
•
= ce mod n
8
Multiplicative Inverses
• The residues modulo a positive integer n are the set
Zn = {0, 1, 2, …, (n - 1)}
• Let x and y be two elements of Zn such that
xy mod n = 1
We say that y is the multiplicative inverse of x in Zn
and we write y = x-1
• Example (can do by trying all possibilities):
– Multiplicative inverses of the residues modulo 11
x
x-1
0
1
1
2
6
3
4
4
3
5
9
6
2
7
8
8
7
9
5
10
10
9
What if n = 12?
Mult
1
2
3
4
5
6
7
8
9
10
11
1
1
2
3
4
5
6
7
8
9
10
11
2
2
4
6
8
10
0
2
4
6
8
10
3
3
6
9
0
3
6
9
0
3
6
9
4
4
8
0
4
8
0
4
8
0
4
8
5
5
10
3
8
1
6
11
4
9
2
7
6
6
0
6
0
6
0
6
0
6
0
6
7
7
2
9
4
11
6
1
8
3
10
5
8
8
4
0
8
4
0
8
4
0
8
4
9
9
6
3
0
9
6
3
0
9
6
3
10
10
8
6
4
2
0
10
8
6
4
2
11
11
10
9
8
7
6
5
4
3
2
1
10
Multiplicative Inverses
What if n=12? Not everything HAD an inverse.
x
x-1
0
1
1
2
3
4
5
5
6
7
7
8
9
10 11
11
11
Questions
• Why would someone want to find inverses?
Helpful for encryption. Multiply by x to encrypt and by x-1 to decrypt.
Example: Want to send a series of numbers privately.
You tell the recipient (via private delivery) that whatever you send
needs to be multiplied by 4 and mod-ed by 11.
I want to send 6, I multiply by 3 (mod 11) and get 7
You take the 7 multiply by 4 (mod 11) and get 6 TADA!!!
• How do you find inverses?
• Can you easily tell if an inverse exists?
12
Theorem 10.3: gcd(a,b) is the smallest positive integer
d such that d= ia+jb (for integers i,j)
Why:
A. anything that divides both a and b clearly divides d, so d gcd(a,b)
B. need to show d  gcd(a,b)
let h=a/d,
by definition of mod
d>a mod d = a-hd = a-h(ia+jb)
=(1-hi)a + (-hj)b
thus a mod d is a linear combination of a,b
But d is the smallest positive linear combination. Problem as we just
found a smaller one (a mod d). Solution – a mod d must be 0 as we
restricted d to be a positive integer.
Thus, d evenly divides a. Through a similar argument, d evenly divides
b, so it is a divisor of a and b. d  gcd(a,b).
13
Theorem 10.6
An element x of Zn has a multiplicative inverse if and
only if x and n are relatively prime
• Example The elements of Z10 with a multiplicative inverse are 1, 3, 5, 7
• Why? Prove each direction separately
 If x and n are relatively prime, x has an inverse
gcd(x,n) = 1 so ix +jn = 1 so ix mod n =1
Tada: i and x are inverses (mod n)!
 if x has a multiplicative inverse, x and n are relatively prime. Proof by
contraction. Assume gcd(x,n) >1 (not relatively prime)
Let y be the inverse – so xy mod n = 1
Thus xy – dn = 1 (for some value, d) by definition of mod
But then 1 would be the gcd(x,n) – contradiction!
14
Thm 10.3: gcd(a,b) is the smallest positive integer d such that d= ia+jb (for integers i,j)
Proof sketch: Try to prove that d gcd(a,b) AND d  gcd(a,b). If we could do that, we
would show d = gcd(a,b).
Part 1: SHOW d gcd(a,b)
1. Anything that divides both a and b clearly divides d = ia +jb
BECAUSE_____________________________________________
2. Therefore…
Part 2: SHOW d  gcd(a,b).
1. let h=a/d
2. d > a mod d
BECAUSE ________________________________________
3. a mod d = a-hd = a-h(ia+jb) =(1-hi)a + (-hj)b
4. So a mod d is a linear combination of a and b.
5. But we have a problem BECAUSE_________________________________________
6. The solution is a mod d = 0
7. But that is GOOD NEWS as d evenly divides a.
Through a similar argument d evenly divides b.
8. Since d divides both a and b, we call it a divisor of a and b (right?)
9. Can d be bigger than the greatest common divisor?
10. Therefore…
15
Theorem 10.6
An element x of Zn has a multiplicative inverse if and only if x and n
are relatively prime
Proof sketch: to prove if and only if, we have to prove in each
direction:
 If x and n are relatively prime, x has an inverse
1. gcd(x,n) = 1 BECAUSE _____________________________
2. ix +jn = 1 BECAUSE______________________________
3. ix mod n =1 BECAUSE _____________________________
4. Therefore….
 if x has a multiplicative inverse, x and n are relatively prime.
1. Let y be the inverse of x; so xy mod n = 1
2. xy – qn = 1 BECAUSE_____________________________
3. Therefore…
16
Corollary:
If p is prime, every nonzero residue (remainder) in Zp has a
multiplicative inverse
Great! so now know inverses mod p will exist for every number if p
is a prime.
Fill in table below!
x
x-1
0
1
2
3
1
7
9
4
5
6
7
8
9
10 11 12
17
Theorem
A variation of Euclid’s GCD algorithm computes the
multiplicative inverse of an element x of Zn or
determines that it does not exist. All we have to do is
return the coefficients of a and b.
18
Consider an extended version of Euclid algorithm which
not only returns the gcd BUT also the multipliers of a
and b which prove the gcd.
(gcd, amult, bmult) ExtendedEuclidGCD(a,b){
if (b==0) return (a,1,0)
(d,a1,b1)= ExtendedEuclidGCD(b,a mod b)
// d = b*a1 + (a mod b)*b1 (by def of ExtendedEuclid)
// = b*a1+(a -a/bb)*b1
// = b1*a + b(a1- a/b*b1)
return (d,b1,a1-a/b*b1)
}
19
From this algorithm, how find
inverses?
• Theorem 10.6 tells us that x of Zn has an
inverse iff gcd(x,n) = 1
• So…
• use extended Euclid to find gcd(x,n)
• if gcd(x,n) != 1, there is no inverse
• if gcd(x,n) == 1 then ix +jn = 1
• ix = (1-jn)
• ix = 1 (mod n) so i is the inverse of x
• Try to find the inverse of 5 mod 9 using this
technique
20
Corollary (to theorem 10.6)10.7: if
gcd(x,n) = 1 then
Zn={ix mod n:i=0,1,...,n-1}
Nice! used in hash functions to make sure
all entries are reached
Try it: gcd(5,9) = 1
i5 mod 9 (i=0..n-1)=
(0 5 10 15 20 25 30 35 40) mod 9
=(0 5 1 6 2 7 3 8 4 )
21
Proof by contradiction:
Left as exercise to reader
22
Powers
•
•
•
•
•
Let p be a prime
The sequences of successive powers of the elements of Zp (mod p)
exhibit repeating subsequences
The sizes of the repeating subsequences and the number of their
repetitions are the divisors of p - 1
Example (p = 7) Notice how [xp-1 = 1 ] (mod p) for any x!
I don’t know why anyone was prompted to play with this, but wouldn’t it have been exciting
to discover?
x
x2
x3
x4
x5
x6
1
1
1
1
1
1
2
4
1
2
4
1
3
2
6
4
5
1
4
2
1
4
2
1
5
4
6
2
3
1
6
1
6
1
6
1
23
Fermat’s Little Theorem
Stated in 1640, generalized by Euler in 1760.
Let p be a prime. For each nonzero residue x of Zp
we have xp - 1 mod p = 1
• Example (p = 5):
14 mod 5 = 1
34 mod 1 = 81 mod 5 = 1
24 mod 1 = 16 mod 5 = 1
44 mod 1 = 256 mod 5 = 1
**Corollary
Let p be a prime. For each nonzero residue x of Zp
the multiplicative inverse of x is xp - 2 mod p
Proof
x(xp - 2 mod p) mod p = xxp - 2 mod p = xp - 1 mod p = 1
24
Proof of Fermat’s theorem
Let p be a prime. For each nonzero residue x of Zp we have xp - 1
mod p = 1
Sufficient to prove if 0 < x <p because
xp-1 =p (x mod p)p-1
By Corolary 10.7:{1,2,...p-1} = {x*1,x*2,x*3...x*(p-1)}
So their products are equal:
(p-1)! = x*1*x*2*...x*(p-1) = xp-1(p-1)!
Since p is prime, every non null element in Zp has a
multiplicative inverse. So (p-1)! has an inverse.
1 = xp-1
Converse is not true (prove primality by observing mods), although Chinese thought
it was. It is probable that the Chinese observed this experimentally and never
thought to prove it. Numbers which are counter examples are called Carmichael
numbers (pseudoprime to any base) .
25
The multiplicative group for Zn, denoted Z*n, is the subset of
elements of Zn relatively prime with n
A group is an abstract algebra concept:
Given a non-empty set of elements with an operation *
1. Closed
2. is associative
3. has an identity element,e (a*e = a, for all a)
4. every element has an inverse a*a-1 = e
•
The totient (rhymes with quotient) function of n, denoted
f(n), (pronounced “fee of n”) is the size of Z*n
•
Example Z*10 = { 1, 3, 7, 9 }
f(10) = 4
At seats: Prove the group properties.
•
If p is prime, we have
Z*p = {1, 2, …, (p - 1)}
f(p) = p -1
26
Euler’s (pronounced oilers) Theorem
Generalization of Fermat’s thm (as if p is prime f(n) =p-1
(Leonhard Euler was a brilliant Swiss mathematician. Contemporaries said he could
master any problem, although Fermat's last theorem stumped him. He invented
imaginary numbers while trying to prove the theorem. Some of his very advanced
mathematics had no practical use, but recently one of his obscure equations was
rediscovered and helped develop super-string theory.)
Theorem
For each element x of Z*n, we have xf(n) mod n = 1
• Example (n = 10) Z*10 = { 1, 3, 7, 9 }
3f(10) mod 10 = 34 mod 10 = 81 mod 10 = 1
7f(10) mod 10 = 74 mod 10 = 2401 mod 10 = 1
9f(10) mod 10 = 94 mod 10 = 6561 mod 10 = 1
For each element x of Z*n, we have x-1 = xf(n)-1
27
What if p is not the product of two
primes, how do we compute (n)?
• Our text doesn’t tell us.
• There are lots of interesting facts about
totient functions.
• http://mathworld.wolfram.com/TotientFunction.html
28
Generators
• Given a prime p and an integer a between 1 and
p-1, the order of a is the smallest exponent r > 1
such that
ar =1 (mod p)
A generator (also called a primitive root) of Zp is an
element g of Zp with order p-1.
We use the term generator because repeated
exponentiation of g can generate all of Zp*
Theorem 10:10 if p is prime then set Zp has f(p-1)
generators.
29
Example:
if p is prime then set Zp has f(p-1) generators.
(Some of these theorems are poorly motivated. We
could go through the proofs…
)
• p=7, (7-1) = (6) =2
x
x2 x3 x4 x5 x6
generators Z*6 = {1,5}
1
1
1
1
1
1
2
4
1
2
4
1
3
2
6
4
5
1
4
2
1
4
2
1
5
4
6
2
3
1
6
1
6
1
6
1
30
Example:
if p is prime then set Zp has f(p-1) generators.
• p=11, (11-1) = (10) =4 generators
Z*10 = {1,3,7,9} x x x x x x x x
2
3
4
5
6
7
8
x9
x10
1
1
1
1
1
1
1
1
1
1
2
4
8
5
10
9
7
3
6
1
3
9
5
4
1
3
9
5
4
1
4
5
9
3
1
4
5
9
3
1
5
3
4
9
1
5
3
4
9
1
6
3
7
9
10
5
8
4
2
1
7
5
2
3
10
4
6
9
8
1
8
9
6
4
10
3
2
5
7
1
9
4
3
5
1
9
4
3
5
1
10
1
10
1
10
1
10
1
10
1
31
Modular Power:
We need (1) a fast way of computing ap mod n and
(2) a way that takes mods during the process (as
otherwise ap gets too large to store)
Idea: If I wanted to take 221, I wouldn’t really multiply 21
twos together. I would take a shortcut 221 = 2(210)( 210)
With your neighbor, write the recursive algorithm
32
Modular Power:
We need a fast way of computing ap mod n.
The algorithm is easier than the explanation
int FastExp(a,p,n) // return ap mod n
{if p==0 return 1 // anything to the zero power is 1
if p mod2 ==0 {
half = fastExp(a,p/2, n)
return half2 mod n}
// p is odd t
half = fastExp(a,(p-1)/2,n) // take out 1 a; find power of ap-1
return a(half2mod n) mod n
}
33
Pseudoprimality Testing
•
Experimental evidence suggests:The number of primes less than or
equal to n (for large n) is about n / ln n
So if n = 2b = 210, there are about 210/10 primes = 100 primes.
• Testing whether a number is prime (primality testing) is believed to be a
hard problem
• An integer n  2 is said to be a base-x pseudo-prime if
– xn - 1 mod n = 1 (Fermat’s little theorem)
– For example, for n = 341, 2340 mod n = 1 so 341 is pseudoprime to base 2.
•
•
(They often use the term pseudoprime for both primes and non-primes
that pass this test.)
Non-prime base-x pseudoprimes are rare:
– A random 100-bit integer is a composite base-2 pseudoprime with probability
less than 10-13
– The smallest composite base-2 pseudoprime is 341
•
Base-x pseudoprimality testing for an integer n:
– Check whether xn - 1 mod n = 1
– Can be performed efficiently with the repeated squaring algorithm
– If you repeated this for many x’s, you would have greater confidence that n is
prime. (A Monte Carlo approach, right?)
34
Randomized Primality Testing
• Compositeness witness function
isComposite(x, n) with error
probability q for a random variable
x
Case 1: isComposite w(x, n) = true we
know x is not prime!
Case 2: isComposite w(x, n) = false
lies with probability q < 1
• Algorithm RandPrimeTest tests
whether n is prime by repeatedly
evaluating isComposite(x, n)
• A variation of base- x
pseudoprimality provides a
function for randomized primality
testing (Rabin-Miller algorithm)
• isComposite =true if xn-1≠1 (mod
n)
Algorithm RandPrimeTest(n, k)
Input integer n,confidence
parameter k and composite
witness function
isComposite(x,n) with error
probability q
Output an indication of
whether n is composite or prime
with probability 2-k
t  k/log2(1/q)
for i  1 to t
// try same n with different x
x  random()
if isComposite(x,n)= true
return “n is composite”
return “n is prime”
35
• Skip rest of section 10.1.6
36
Encryption
• Scenario:
– Alice wants to send a message (plaintext p) to Bob.
– The communication channel is insecure and can be
eavesdropped. If Alice and Bob have previously agreed on an
encryption scheme (cipher), the message can be sent encrypted
(ciphertext c)
• Issues:
–
–
–
–
What is a good encryption scheme?
What is the complexity of encrypting/decrypting?
What is the size of the ciphertext, relative to the plaintext?
If Alice and Bob have never interacted before, how can they agree
on an encryption scheme?
plaintext
encrypt
ciphertext
decrypt
plaintext
37
Traditional Cryptography
• Ciphers were studied in ancient times
• Caesar’s cipher (replace with symbol X away):
–
–
–
–
replace a with d
replace b with e
...
replace z with c
• Caesar’s cipher is an example of a monoalphabetic substitution
cipher, which permutes the characters
• Armed with simple statistical knowledge, one can easily break a
monoalphabetic substitution cipher
– most frequent letters in English: e, t, o, a, n, i, ...
– most frequent digrams: th, in, er, re, an, ...
– most frequent trigrams: the, ing, and, ion, ...
• The first description of the frequency analysis attack appears in a
book written in the 9th century by the Arab philosopher al-Kindi
38
Decryption
• Code: X Z A V O I D B Y G E R S P C F H J K L M N Q T U W
Org: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Ciphertext:
PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ
LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL, QBOP KBO BXV
OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV
ZOICJO BYS, KXUYPD: “DJOXL EYPD, ICJ X LBCMKXPV XPV CPO
PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL
XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV
XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?”
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK
• Plaintext:
Now during this time Shahrazad had borne King Shahriyar three sons. On the
thousand and first night, when she had ended the tale of Ma'aruf, she rose
and kissed the ground before him, saying: “Great King, for a thousand and
one nights I have been recounting to you the fables of past ages and the
legends of ancient kings. May I make so bold as to crave a favour of your
majesty?”
Epilogue, Tales from the Thousand and One Nights
39
Secret-Key Encryption
• A secret-key cipher uses a unique key K to encrypt and decrypt
• Caesar’s generalized cipher uses the modular addition of each
character (viewed as an integer) with the key:
C[i] = (P[i] + K )mod m (p is plaintext)
P[i] = (C[i] - K) mod m
• More secure secret-key encryption schemes have been devised
in this century
• Examples:
–
–
–
–
DES
3DES
IDEA
BLOWFISH
• With private-key encryption, a distinct secret key must be
established for every pair of parties
40
Public-Key Encryption
• Bob uses a pair of keys (KE,KD) and
– makes encryption key KE public
– keeps decryption key KD private
• Anyone can use the public key KE to encrypt a plaintext into a
ciphertext sent to Bob (who has the decryption key)
• Only Bob can decrypt the ciphertext using the private key KD
• The most popular encryption scheme is RSA, named after its
inventors Rivest, Shamir, and Adleman (1978)
• The RSA patent expired in 2000
public key
plaintext
encrypt
private key
ciphertext
decrypt
plaintext
41
Advantages/Disadvantages of
Public Key Encryption
• Advantages
If two people have never communicated
before, they can still send secure
messages
• Disadvantages
If one of the keys is public, someone may
be able to figure out the private key.
42
• Setup:
RSA Cryptosystem
– n = pq, with p and q primes
– e relatively prime to
f(n) = (p - 1) (q - 1)
– d inverse of e in Zf(n)
• Keys:
– Public key: KE = (n, e)
– Private key: KD =(n,d)
• Encryption:
– Setup:
• p = 7, q = 17
• n = 717 = 119
 f(n) = 616 = 96
• e=5
• d = 77
• ed=1mod 96
– Keys:
– Plaintext M in Zn
– Cyphertext C = Me mod n
• Decryption: xed = x (mod n)
• Example
Thm 10.21
– M = Cd mod n = Med mod n
– ed = kf(n) +1
– Med mod n = M kf(n) +1= (M f(n) )k M=M
–
• public key: (119, 5)
• private key: (119,77)
– Encryption:
• M = 19
• C = 195 mod 119 = 66
– Decryption:
• C = 6677 mod 119 = 1943
Correctness
• We show the correctness of
the RSA cryptosystem for the
case when the plaintext M
has no common factors with
n
• Namely, we show that
(Me)d mod n = M
• Since ed mod f(n) = 1, there is
an integer k such that
ed = kf(n) + 1
• Since gcd(M, n)=1, by Euler’s
theorem we have
Mf(n) mod n = 1
• Thus, we obtain
(Me)d mod n =
Med mod n =
Mkf(n) + 1 mod n =
MMkf(n) mod n =
M (Mf(n))k mod n =
M (Mf(n) mod n)k mod n =
M (1)k mod n =
M mod n =
M
• See the book for the proof of
correctness in the case
when the plaintext M is not
relatively prime with respect
to n
44
Security
• The security of the RSA
cryptosystem is based on the
widely believed difficulty of
factoring large numbers
–The best known factoring
algorithm (general number field
sieve) takes time exponential
in the number of bits of the
number to be factored
• The RSA challenge,
sponsored by RSA Security,
offers cash prizes for the
factorization of given large
numbers
• In April 2002, prizes ranged
from $10,000 (576 bits) to
$200,000 (2048 bits)
• In 1999, a 512-bit number was
factored in 4 months using the
following computers:
–160 175-400 MHz SGI and Sun
– 8 250 MHz SGI Origin
– 120 300-450 MHz Pentium II
– 4 500 MHz Digital/Compaq
• Estimated resources needed to
factor a number within one year
Memory
Bits
PCs
430
1
MB = 106
128MB
760
215,000
GB = 109
4GB
1,020
342106
1,620
1.61015
170GB
TB=1012
120TB
45
Algorithmic Issues
• The implementation of
the RSA cryptosystem
requires various
algorithms
• Overall
–Representation of integers
of arbitrarily large size and
arithmetic operations on
them
• Encryption
• Setup
–Generation of random
numbers with a given
number of bits (to generate
candidates p and q)
–Primality testing (to check
that candidates p and q are
prime)
–Computation of the
multiplicative inverse (to
compute d from e)
–Modular power
• Decryption
–Modular power
46
Information Security
message
M
one-way hash
fingerprint
f = H(M)
47
Digital Signature
•
•
Author A wants to send message M so that the message is known to
come from A and M is known not to have been altered.
A digital signature is a string S associated with a message M and the
author A that has the following properties
Integrity: S establishes that M has not been altered
Nonrepudiation: S unequivocally identifies the author A of M and proves that A did
indeed sign M
•
A digital signature scheme provides algorithms for
– Signing a message by the author
– Verifying the signature of a message by the reader
•
•
A recently passed law (2000) in the US gives digital signatures the same
validity of handwritten signatures
A public-key cryptosystem yields a digital signature scheme provided
encrypt(KE, decrypt(KD, M)) = M (is symmetric – can go both ways)
Signature: Alice (author) computes S = decrypt(KD,M) using her private key KD and
sends both (the pair (M,S)) to Bob
Verification: Bob (reader) computes M´ = encrypt(KE, S) using Alice’s public key KE
and checks that M´ = M
48
RSA Digital Signature
•
Setup:
•
Keys:
•
– n = pq, with p and q primes
– e relatively prime to
f(n) = (p - 1) (q - 1)
– d inverse of e in Zf(n)
– Public key: KE = (n, e)
– Private key: KD = d
Signature: use private key
first
– Message M in Zn
– Signature S = Md mod n
•
Verification (send message
and encrypted message):
•
Setup:
•
Keys:
•
Signature:
•
Verification:
– p = 5, q = 11
n = 511 = 55
 f(n) = 410 = 40
e=3
– d = 27 (327 = 81 = 240 + 1)
– Public key: KE = (55, 3)
– Private key: KD = 27
– M = 51
– S = 5127 mod 55 = 6
– S = 63 mod 55 = 216 mod 55 = 51
– Check that M = Se mod n
49