程序代写代做代考 scheme algorithm 17crypto_L09

17crypto_L09

RSA Public Key Encryption

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

1

Reduced Set of Residues

� The RSA algorithm is based on a small amount of number
theory.

� The reduced set of residues (RSR) of a number n is the set
of all integers which have an inverse mod n.

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

2

of all integers which have an inverse mod n.

�In other words, all the numbers a with

� gcd(a, n) = 1

�RSR of 10 = {1, 3, 7, 9}

�RSR of prime p = {1, 2, …, p-1 }

Euler Totient Function

� The Euler Totient Function φ is the size of this set.
� φ(10) = 4.
�φ(p) = p-1, where p is prime.
�φ(pq) =(p-1)(q-1), where p, q are prime.

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

3

�φ(pq) =(p-1)(q-1), where p, q are prime.
�φ(pqr)=(p-1)(q-1)(r-1), where p, q,r are

prime.

� This second result can be proved by counting.

�There are pq-1 numbers in the range 1 .. pq-1

Euler Totient Function (2)

� We do not want factors of p: p,2p,…,(q-1)p
�There are q-1 of these.

� Similarly, there are p-1 factors of q.
� There are no numbers with factors p and q.

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

4

� There are no numbers with factors p and q.
φ(pq) = (pq-1)-(q-1)-(p-1)

= pq-p-q+1

= (p-1)(q-1)

Fermat’s Theorem

� If p is prime and gcd(a,p)=1
�then ap-1 % p = 1.

� Proof from Euler’s generalization, which follows next.

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

5

� Euler’s Generalization of Fermat’s Theorem
� aφ(n) % n = 1, provided gcd(a, n) = 1.
� Proof beyond the scope of this course.

A Probabilistic Primality Test

� Let a be a prime number.
� If an-1 % n ≠ 1, then n is NOT prime.
� If an-1 % n = 1, then n may be a prime, or the result

may be 1 by accident.
� Choose a series of prime numbers a, and calculate an-1%n.

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

6

� Choose a series of prime numbers a, and calculate an-1%n.
� If the answer is 1 in all cases, then we can assume that n is

a prime with a small probability of error.
� Carmichael numbers are not prime but always pass this

test.
�There are not many of them.

Exponentiation Ciphers

� The RSA public key system is a form of exponentiation
cipher, and so we will consider exponentiation ciphers
first.

� The Plaintext Input

Crypto & SecDev 2017 © Ron Poet:
Lecture 9

7

� The Plaintext Input

�Let us choose an integer n and split the plaintext into a
series of messages Pi with 0 ≤ Pi < n. �This can be achieved by splitting the message into blocks �I will drop the i suffix from now on and just consider what happens to one block. Exponentiation Ciphers (2) � Encryption �Choose an integer e and calculate the cipher text C = Pe % n � Decryption �Choose an integer d and recover the message by P = Cd % n � d and e must be inverses, so that Crypto & SecDev 2017 © Ron Poet: Lecture 9 8 � d and e must be inverses, so that �de ≡ 1 mod φ(n) �Hence de = 1 mod λ φ(n) for some integer λ. �We don’t need to know what λ is. �Also gcd(d, φ(n)) = 1 for the inverse to exist. �Therefore d is the unique inverse of e. Proof C = Pe % n P' = Cd % n = Ped % n = P1+λφ(n) % n Crypto & SecDev 2017 © Ron Poet: Lecture 9 9 = P1+λφ(n) % n = P * Pλφ(n) % n = P * (Pφ(n) % n)λ % n = P, since Pφ(n) % n = 1 by Euler's generalisation of Fermat's theorem, assuming gcd(P, n) = 1. Pohlig - Hellman Scheme � Chose n = p, a prime. � Hence φ = p-1 = n-1. � This is not a public key system since �if (n, e), which are necessary for encryption, are Crypto & SecDev 2017 © Ron Poet: Lecture 9 10 �if (n, e), which are necessary for encryption, are made public then � φ can be calculated and hence also d. Rivest Shamir Adleman (RSA) Scheme � Chose n = pq, the product of two primes. � Then φ = (p-1)(q-1) which can only be calculated if n is factored. �We have to know both p and q to calculate φ. Crypto & SecDev 2017 © Ron Poet: Lecture 9 11 �We have to know both p and q to calculate φ. � This is safe provided our enemies cannot factor n into two primes. � gcd(P,n) may not be 1 if P has either p or q as a factor. � The values of p and q are so large that this is very unlikely and can be ignored. Difficulty of Factoring � Factoring is not known to be NP-complete. �Primality testing is similar to factoring. A polynomial time algorithm for primality testing was discovered in 1995. Crypto & SecDev 2017 © Ron Poet: Lecture 9 12 1995. �There is no know polynomial time algorithm for factoring. � The best general purpose factoring algorithm is O(n√(log log n / log n)) � This would involve about 1015 operations for a 100 digit number. The RSA Algorithm 1. Chose the length of n (number of bits) so that it is computationally infeasible to factor n. 2. Chose two primes p and q of near equal length and calculate � n = pq, φ = (p-1)(q-1). φ Crypto & SecDev 2017 © Ron Poet: Lecture 9 13 � Choose p%4 ≠ 1 and q%4 ≠ 1 so that φ does not have too many factors of 2. 3. Choose d as a prime, about the same length as n. 4. Calculate e using the inverse formula. If e is too small (