Let’s begin with a brief review of the definition of modular arithmetic. Here is a simple example:
For , mod 2 = least significant bit of =
- 1 if is odd
- 0 if is even
The general definition is the following:
Definition: For integer ,
mod = remainder when divide by
= , where
and for integers .
Example: mod 3 has 3 equivalence classes:
Properties: Given mod and mod , then:
Example: Find mod 31, given 345 = 5 x 69.
Example: input: , where and are -digit numbers, and .
Complexity for the following computations:
- Module: if : output ; else: output .
- Total time:
- Module: compute divided by and output the remainder.
- Total time:
- Easy Idea: Compute . rounds in total and , so the running time is , which is exponential time.
- Improvement: Compute all , where is power of 2 and . And then combine the results to get the final answer. rounds of computation in total, and for each round, and the same for the combining rounds. Thus the total time is .
- Example: , then . And we need to compute , where . We need to do at most multiplications to get these values and another multiplications to get the final result. Thus the total time is .
Definition: is a multiplicative inverse of if , we can also write it as .
Theorem: exists iff , (or in other words, there exists such that ).
Example: , find the inverse of
To find the inverse of , we can first compute to verify that . In addition we can find integers such that . The number here is the inverse of A when .
We can use the Extended Euclid’s Algorithm to find and also these numbers that . Let’s first review the basic Euclid’s algorithm for finding the .
Euclid’s Rule and Euclidean Algorithm
Euclid’s Rule: For such that , .
This follows from the fact that . Euclid’s rule yields a simple divide and conquer algorithm for computing the gcd.
- if :
Claim: If , then .
Hence every other round the first coordinate decreases by at least half. Therefore, the running time satisfies: , here is the number of digit of . Thus Euclid’s Algorithm takes time to compute the .
We can now look at the extended version of the algorithm which also computes the numbers mentioned earlier.
- if :
- Return ()
Here if , then is the inverse of because and mod each side by gives us
Fermat’s Little Theorem and Euler’s Theorem
Fermat’s Little Theorem:
For prime , for all relatively prime to (so all where ), then
Let be a prime and .
It turns out that in general the sets and are identical sets, just possibly have the elements in different order.
Proof of Claim: We’ll show that has distinct and non-zero elements, and therefore it contains all elements of exactly once, so we’ll have that .
Let’s first show that the elements of are distinct. Assume such that and .
Then since , mod p exists.
And this implies , which is a contradiction.
Similarly, if , then .
Thus has the same elements as , which gives us .
Using this claim, we can multiply together the elements of and we’ll get the same result as when we multiply the elements of , hence:
Since is prime, so for .
Thus so we’re left with , and this completes the proof of Fermat’s Little Theorem.
We’ll use the following generalization of Fermat’s little theorem:
For any , given any relatively prime to (So )
where = # integers that are relatively prime to =
For prime , and hence we obtain Fermat’s little theorem in this case.
For primes , let , then . Why? Well let’s look at the numbers between 1 and N and count how many are not relatively prime to . In particular, which of these numbers have a common factor with ? There are multiples of , namely , and for each of these numbers is a common factor of this number and also of . Similarly there are multiples of , namely . And we counted twice. Thus there are numbers between 1 and N which are not relatively prime to N and the others are relatively prime. Therefore, .
So for where , then . This is the key result for the RSA protocol. Let us explore how we use it.
Back to Fermat’s Little Theorem
Take where .
So , which means for some integer . Therefore,
Looking at Euler’s
For primes , let .
Take where . Thus, for some integer . Therefore, for relatively prime to , .
This important property is used in RSA. Someone can find large primes and compute . They keep but give out the public . Anyone who wants to send a secret message can encrypt the original message by to get the encrypted message . When receiving that , they can recover the original message by decrypting using . We’ll talk about the details of the protocol in a moment.
Alice has a message that she wants to send to Bob, but Eve can see the message sent.
Private-key scheme (One-time pad):
Alice & Bob meet beforehand and decide on a -bit string .
Then Alice sends:
. Here is Exclusive OR.
How should they pick ?
Choose a random string, then is also a random string.
1) need to meet or have a secure, private computation beforehand
2) can only use it once.
E.g., suppose Alice sends and using same , then Eve can see
which might have some useful info, e.g. if one of the has a string of 0’s then you see the other one.
Bob publishes a public key: anyone can send a message to Bob uses his public key to encrypt, while Bob uses his private, secret key to decrypt the received message.
1) Bob picks 2 -bit random primes
Choose random -bit numbers and check if they are prime (we’ll see how to do that next class). It has prob of being prime.
2) Bob chooses an relatively prime to
He does this by trying . And he also computes .
3) Bob publishes his public key as where . (he doesn’t reveal or , just )
4) Bob computes his private key
He does this using the extended Euclid algorithm.
to send the message m to Bob
1) She looks up his public key
2) She computes using fast modular exponentiation algorithm that we saw.
3) She sends to Bob
1) He receives and decrypts using using fast modular exponentiation.
Given , it is computationally difficult to determine .
Natural way is to factor to get then one can get .
We saw before that:
Since we have that for some integer . Moreover, if is relatively prime to then by Euler’s theorem . Therefore we have the following:
The remaining case is when has . This case requires the Chinese remainder theorem, which we have not covered so we skip this case but the identity still holds true when . (The proof using the Chinese remainder theorem is not difficult, here’s a good explanation that I found.)
This gives us , so RSA works.
RSA = Rivest-Shamir-Adelman published in 1977.
Clifford Cocks – working for UK intelligence agency described a similar system in ’73.
– Note if (or is small), one needs to make sure otherwise mod isn’t doing anything and to decrypt one can just take
So often “pad” .
– If send same to or more people all using the same then can decrypt (see HW problems).