Cryptography: RSA

•The RSA scheme is a block cipher in which the plaintext and ciphertext are integers between 0 and n - 1 for some n.

•A typical size for n is 1024 bits, or 309 decimal digits. That is, n is less than 21024.

•Where does the name come from?

Ron Rivest

Adi Shamir

Leonard Adleman

 
 Description of the Algorithm 

•RSA makes use of an expression with exponentials.

–Based on exponentiation in a finite field over integers modulo a prime

•Plaintext is encrypted in blocks, with each block having a binary value less than some number n.

•Block size must be less than or equal to log2(n) + 1; in practice, the block size is i bits, where

2i < n £ 2i+1.

•Encryption and decryption are of the following form, for some plaintext block M and ciphertext block C.

C = Me mod n

M=Cd mod n = (Me)d mod n = Med mod n

•Both sender and receiver must know the value of n.

•The sender knows the value of e, and only the receiver knows the value of d.

•Thus, this is a public-key encryption algorithm with a public key of PU = {e, n} and a private key of PR = {d, n}.

For this algorithm to be satisfactory for public-key encryption, the following requirements must be met.

1.It is possible to find values of e, d, n such that Med mod n = M for all M < n. 


2.It is relatively easy to calculate Me mod n and Cd mod n for all values of M < n. 


3.It is infeasible to determine d given e and n.

●

 

Med mod n = M

•This relationship holds if e and d are multiplicative inverses modulo  Ø (n), where  Ø (n) is the Euler totient function.

For p, q prime, Ø (pq) = (p - 1)(q - 1).

•The relationship between e and d: ed mod Ø (n) = 1

•This is equivalent to saying

ed ≡ 1 mod Ø (n)

d ≡ e-1 mod  Ø (n)

•That is, e and d are multiplicative inverses mod Ø (n).

Essentials Ingredients of RSA

•The private key consists of {d, n} and the public key consists of {e, n}.

•Suppose that user A has published its public key and that user B wishes to send the message M to A.

•Then B calculates C = Me mod n and transmits C.

•On receipt of this cipher-text, user A decrypts by calculating M = Cd mod n.

 

 

Cryptography: The Chinese Remainder Theorem

•One of the most useful results of number theory is the Chinese remainder theorem (CRT).

•In essence, the CRT says it is possible to reconstruct integers in a certain range from their residues modulo a set of pairwise relatively prime moduli.

•The CRT is so called because it is believed to have been discovered by the Chinese mathematician Sun-Tsu in around 100 A.D.

•CRT says that in modulo M arithmetic, if M can be expressed as a product of n integers that are pairwise coprime, then every integer in the set ZM = {0, 1, 2, ...., M − 1} can be reconstructed from residues with respect to those n numbers.

•For example, the prime factors of 10 are 2 and 5. Now let’s consider an integer 9 in Z10. Its residue modulo 2 is 1 and the residue modulo 5 is 4. So, according to CRT, 9 can be represented by the tuple (1, 4).

 

 

 

Usefulness of CRT  

•CRT is extremely useful for manipulating very large integers in modulo arithmetic. We are talking about integers with over 150 decimal digits (that is, numbers potentially larger than 10150).

•Let’s say that we want to do arithmetic on integers modulo 8633. That is, M = 8633. This modulus has the following decomposition into two pairwise coprimes:

  8633 = 89×97
So we have m1 = 89 and m2 = 97. The corresponding Mi

Integers are M1 = M/m1 = 97 and M2 = M/m2 = 89.

•By using the Extended Euclid’s Algorithm we can next figure out the multiplicative inverse for M1 modulo m1 and the multiplicative inverse for M2 modulo m2.

M−11 mod m1 = 78

M−12 mod m2 = 12

•Now let’s say that we want to add two integers 2345 and 6789 modulo 8633.

•We first express the operand 2345 by its CRT representation, which is (31, 17) since 2345 mod 89 = 31 and 2345 mod 97 = 17.

•We next express the operand 6789 by its CRT representation, which is (25, 96) since 6789 mod 89 = 25 and 6789 mod 97 = 96.

•To add the two “large” integers, we simply add the two corresponding CRT tuples modulo the respective moduli. This gives us (56, 16). For the second of these two numbers, we initially get 113, which modulo 97 is 16.

•To recover the result as a single number, we use the formula

a1 × M1 × M−1 + a2 × M2 × M−1 mod M

which for our example becomes

56 × 97 × 78 + 16 × 89 × 12 mod 8633

that returns the result 501. You can verify this result by directly computing 2345 + 6789 mod 8633 and getting the same answer.

 

Cryptography: Test for Primality

•For many cryptographic algorithms, it is necessary to select one or more very large prime numbers at random.

–Thus, we are faced with the task of determining whether a given large number is prime.

•Traditional method: divide by all numbers (primes) in turn less than the square root of the number.

–only works for small numbers

•Alternatively use statistical primality tests based on properties of primes for which all primes numbers satisfy property

–but some composite numbers, called pseudo-primes, also satisfy the property

 

•One attractive and popular algorithm:

  Miller-Rabin Algorithm

•A most notable feature of this algorithm is that it only makes a probabilistic assessment of primality: If the algorithm says that the number is composite (the same thing as not a prime), then the number is definitely not a prime.

•On the other hand, if the algorithm says that the number is a prime, then with a very small probability the number may not actually be a prime.

–With proper algorithmic design, this probability can be made so small that, as someone has said, there would be a greater probability that, as you are sitting at a workstation, you’d win a lottery and get hit by a bolt of lightening at the same time.

•This algorithm used to test a large number for primality.

•Miller-Rabin Algorithm is Based on an Intuitive Decomposition of an Even Number into Odd and Even Parts

•Basic:

Any positive odd integer n ≥ 3 can be expressed as

  n - 1 = 2kq with k > 0, q odd

Properties of Prime Numbers 

For any numbers to be prime, two properties needs to be satisfied.

The first property is stated as follows:

If p is prime and a is a positive integer less than p, then a2 mod p = 1 if and only if either

  a mod p = 1 or a mod p = -1 mod p = p - 1.

•By the rules of modular arithmetic
(a mod p)(a mod p) = a2 mod p.

•Thus, if either a mod p = 1 or a mod p = -1, then a2 mod p = 1.

•Conversely, if a2 mod p = 1, then (a mod p)2 = 1, which is true only for a mod p = 1 or a mod p = -1

●   Miller-Rabin Algorithm

TEST (n) is:

1. Find integers k, q, k > 0, q odd, so that (n–1)=2kq

2. Select a random integer a, 1<a<n–1

3. if aq mod n = 1 then return (“inconclusive");

4. for j = 0 to k – 1 do

  5. if (a2jq mod n = n-1)

    then return(“inconclusive")

6.   else return (“composite")

 

•Given an odd number n that is not prime and a randomly chosen integer, a with 1 < a < n - 1, the probability that TEST will return inconclusive (i.e., fail to detect that n is not prime) is less than 1/4.

•Thus, if t different values of a are chosen, the probability that all of them will pass TEST (return inconclusive) for n is less than (1/4)t.

•For example, for t = 10, the probability that a nonprime number will pass all ten tests is less than 10-6.

•Thus, for a sufficiently large value of t, we can be confident that n is prime if Miller’s test always returns inconclusive.

•This gives us a basis for determining whether an odd integer n is prime with a reasonable degree of confidence.

•The procedure is as follows: Repeatedly invoke TEST (n) using randomly chosen values for a.

•If, at any point, TEST returns composite, then n is determined to be nonprime.

•If TEST continues to return inconclusive for t tests, then for a sufficiently large value of t, assume that n is prime.

Cryptography: FERMAT’S AND EULER’S THEOREMS

Two theorems that play important roles in public-key cryptography are Fermat’s theorem and 

Euler’s theorem.

Fermat’s Theorem

Fermat’s theorem states: If p is prime and a is a positive integer not divisible by p, then

  ap-1 º 1(mod p)  Alternatively ap º a (mod p)

useful in public key and primality testing

Note: º indicates congruence

 

Euler’s Totient Function   

•Euler’s totient function, written Ø(n), and defined as the number of positive integers less than n and relatively prime to n.

Ø(1)=1

Ø(3) = (3-1)=2

Ø(4)={1,3}=2

•Thus for prime number Ø(p) = p – 1

•Suppose we have two prime numbers p and q with p ≠ q. For n = pq, what is Ø(n)?

Ø(n) = Ø(pq) = Ø (p) x Ø(q) = (p-1) x (q-1)   

•Euler’s theorem states that for every a and n that are relatively prime:

aØ(n) º 1 (mod n)

•Also,

aØ(n) + 1 º a (mod n)