Page 327 - Discrete Mathematics and Its Applications

306 4 / Number Theory and Cryptography

Key Terms and Results

TERMS crytanalysis: the process of recovering the plaintext from ci-
phertext without knowledge of the encryption method, or
a | b (a divides b): there is an integer c such that b = ac
a and b are congruent modulo m: m divides a − b with knowledge of the encryption method, but not the key
modular arithmetic: arithmetic done modulo an integer cryptosystem: a five-tuple (P, C, K, E, D) where P is the set
m ≥ 2 of plaintext messages, C is the set of ciphertext messages,
prime: an integer greater than 1 with exactly two positive K is the set of keys, E is the set of encryption functions,
integer divisors and D is the set of decryption functions
composite: an integer greater than 1 that is not prime private key encryption: encryption where both encryption
p
Mersenneprime:aprimeoftheform2 − 1,wherep isprime keys and decryption keys must be kept secret
gcd(a, b) (greatest common divisor of a and b): the largest public key encryption: encryption where encryption keys are
integer that divides both a and b public knowledge, but decryption keys are kept secret
relatively prime integers: integers a and b such that RSA cryptosystem: the cryptosystem where P and C are
gcd(a, b) = 1 both Z 26 , K is the set of pairs k = (n, e) where n = pq
pairwise relatively prime integers: a set of integers with the where p and q are large primes and e is a positive integer,
d
e
property that every pair of these integers is relatively prime E k (p) = p mod n, and D k (c) = c mod n where d is the
lcm(a, b) (least common multiple of a and b): the smallest inverse of e modulo (p − 1)(q − 1)
positive integer that is divisible by both a and b key exchange protocol: a protocol used for two parties to
a mod b: the remainder when the integer a is divided by the generate a shared key
positive integer b digital signature: a method that a recipient can use to deter-
a ≡ b (mod m)(a is congruent to b modulo m): a − b is mine that the purported sender of a message actually sent
divisible by m the message
n = (a k a k−1 ...a 1 a 0 ) b : the base b representation of n
binary representation: the base 2 representation of an integer
RESULTS
octal representation: the base 8 representation of an integer
hexadecimal representation: the base 16 representation of division algorithm: Let a and d be integers with d positive.
an integer Then there are unique integers q and r with 0 ≤ r< d such
linear combination of a and b with integer coefficients: an that a = dq + r.
expression of the form sa + tb, where s and t are integers Let b be an integer greater than 1. Then if n is a pos-
Bézout coefficients of a and b: integers s and t such that the itive integer, it can be expressed uniquely in the form
k
Bézout identity sa + tb = gcd(a, b) holds n = a k b + a k−1 b k−1 + ··· + a 1 b + a 0 .
inverse of a modulo m: an integer a such that aa ≡ 1 (mod m) The algorithm for finding the base b expansion of an integer
linearcongruence:acongruenceoftheformax ≡ b(mod m), (see Algorithm 1 in Section 4.2)
where x is an integer variable The conventional algorithms for addition and multiplication
pseudoprime to the base b: a composite integer n such that of integers (given in Section 4.2)
b n−1 ≡ 1 (mod n) The modular exponentiation algorithm (see Algorithm 5 in
Carmichael number: a composite integer n such that n is a Section 4.2)
pseudoprime to the base b for all positive integers b with Euclidean algorithm: for finding greatest common divisors
gcd(b, n) = 1 by successively using the division algorithm (seeAlgorithm
primitive root of a prime p: an integer r in Z p such that every 1 in Section 4.3)
integer not divisible by p is congruent modulo p to a power Bézout’s theorem: If a and b are positive integers, then
of r
gcd(a, b) is a linear combination of a and b.
discrete logarithm of a to the base r modulo p: the integer e
e
with 0 ≤ e ≤ p − 1 such that r ≡ a (mod p) sieve of Eratosthenes: A procedure for finding all primes not
exceeding a specified number n, described in Section 4.3
encryption: the process of making a message secret
fundamental theorem of arithmetic: Every positive integer
decryption: the process of returning a secret message to its
can be written uniquely as the product of primes, where the
original form
prime factors are written in order of increasing size.
encryption key: a value that determines which of a family of
encryption functions is to be used If a and b are positive integers, then ab = gcd(a, b)· lcm(a, b).
shift cipher: a cipher that encrypts the plaintext letter p as If m is a positive integer and gcd(a, m) = 1, then a has a
(p + k) mod m for an integer k unique inverse modulo m.
affine cipher: a cipher that encrypts the plaintext letter p as Chinese remainder theorem:A system of linear congruences
(ap + b) mod m for integers a and b with gcd(a, 26) = 1 modulo pairwise relatively prime integers has a unique so-
character cipher: a cipher that encrypts characters one by one lution modulo the product of these moduli.
block cipher: a cipher that encrypts blocks of characters of a Fermat’s little theorem: If p is prime and p | a, then
fixed size a p−1 ≡ 1 (mod p).