Įssentially, the RSA function (and its inverse) is a simple modular exponentiation.
The inverse RSA function is: c ↦ c d % N, where c ∈ ℤ N. The RSA function is: m ↦ m e % N, where m ∈ ℤ N. These names are historical, but not entirely precise since RSA by itself does not achieve CPA security. That is, e and d are multiplicative inverses mod ϕ( N) - not mod N! e is called the encryption exponent, and d is called the decryption exponent. Let e and d be integers such that ed ≡ ϕ( N) 1. Let p and q be distinct primes (later we will say more about how they are chosen), and let N = pq. 2ĢYou have to handle the case of x ≡ p 0 separately, since 0 ∉ ℤ ∗ p so Euler’s theorem doesn’t apply to it. Here’s an important theorem from abstract algebra:Īs a final corollary, we can deduce Fermat’s “little theorem,” that x p ≡ px for all x, when p is prime. We will see more connections between the difficulty of computing ϕ( n) and the difficulty of factoring n later in this part of the course. General formulas for ϕ( n) exist, but they typically rely on knowing the prime factorization of n. That leaves the rest to reside in ℤ ∗ pq, and there are pq − ( p + q − 1) = ( p − 1)( q − 1) of them. 
We count p + q − 1 elements in ℤ pq which share a common divisor with pq. But pq is larger than any item in these lists. Any item that occurs in both lists would be a common multiple of both p and q, but the least common multiple of p and q is pq since p and q are relatively prime.
We have clearly double-counted element 0 in these lists.
The multiples of q share a common divisor with pq. The multiples of p share a common divisor with pq. To see why, let’s count how many elements in Z pq share a common divisor with pq (i.e., are not in ℤ ∗ pq). We will frequently work modulo n where n is the product of two distinct primes n = pq. We will be working with modular arithmetic, so please review the section on modular arithmetic from the first lecture! We need to understand the behavior of the four basic arithmetic operations in the set ℤ n = because every integer in ℤ n apart from zero is relatively prime to p. Of the techniques currently known for public-key crypto, RSA uses some of the simplest mathematical ideas, so it’s an ideal place to start. In general, public-key cryptography relies on computational problems from abstract algebra. 1Clifford Cocks developed an equivalent scheme in 1973, but it was classified since he was working for British intelligence.
0 kommentar(er)
