1) (2) (3) (4) (5) RSA CRYPTOSYSTEM   1-We have shown that if p is a prime number then for all a, ap = a mod p (Fermat)

Subject:Computer SciencePrice:2.84 Bought6

Share With

1)

(2)

(3)

(4)

(5)

RSA CRYPTOSYSTEM

 

1-We have shown that if p is a prime number then for all a, ap = a mod p (Fermat). Hence if there exists a such that ap ?= a mod p, then p is a composite number (not a prime). Use this to show 231 is composite number.

2-In the following two examples, you are going to extract roots modulo N. In both examples N is prime. This a difficult problem when N is not prime. The RSA encryption is based in this difficulty where the N is product of two large distinct primes (N is published but not its factors).

(a) Use the Euclidean Algorithm to show the gcd(19, 96) = 1. Hence find d such that 19d = 1 mod (97) and solve x19 = 36 mod (97).

(b) Solve x137 = 428 mod 541.

3-Alice publishes her RSA public key: modulus, that means N = 2038667 and exponent e = 103.

(a) Bob wants to send Alice the (plaintext) message m = 892383. What ciphertext does Bob send to Alice?

(b) Alice knows that N factors into two primes one of which is p = 1301. Find the decryption exponent d for Alice.

(c) Alice receives the ciphertext c = 317730 from Bob. Decrypt the message.

4-In an RSA encryption, Bob got a little creative and wanted to guard against trans- mission errors. So he encrypted his message m twice by using two encryption exponents e1 and e2. That is, he transmitted to Alice c1 = me1 and c2 = me2. Now the eves dropper, Eve, has N = pq, e1, e2, c1 and c2. However, Bob made a grave miscalculation: the greatest common divisor of e1 and e2 was 1. Show Eve can recover Bob's plaintext message m without factoring N.

Hint. The gcd(e1, e2) = 1 implies that there are integers n and m such that ne1 + me2 = 1.

Miller-Rabin test for primality.

Theorem 1. Let p be an odd prime number and factor p−1 = 2kq so that q is odd1 Then for all natural numbers a either

 aq=1 mod(p)

1Since p is odd, p − 1 is even. Factor the largest possible power of 2 out of p − 1.

 

5-

RSA CRYPTOSYSTEM 2

or, one of the following numbers is congruent to −1 modulo p aq, a2q,...,a2k−1q.

Hence, by logic, if there exists a natural number a such that aq ?= 1 mod (p) and none of the numbers

aq, a2q ...,a2k−1q

are −1 mod (p), then p is not a prime number.

Let us work through an example to show the Carmichael number p = 118901521

is not a prime number. We will show that a = 2 fulfils both conditions to guarantee that p is not prime. Why did I pick a = 2? That is the smallest number to try; if 2 does not work, try 3....

> sage p=118901521

> sage divmod(p-1,16)

  (7431345, 0) # divmod(p-1,32) will return a non-zero remainder.

   #So highest power of 2 that can be factored from p-1 is 16=2^4; so k=4.

> q=divmod(p-1,16)[0] # the zeroth item of the list divmod is the quotient.

> sage mod(2^q, p), # see what is this. It is not 1.

Now, we will compute 2q, 22q, 24q, 28q modulo p (here 8 = 2k−1; the k for this p was 4). We will verify none of them are −1 modulo p, that is 118901520. We can setup a table of 2q, 22q, a4q, 28q modulo p. The table syntax is table() and rows are in [ ]. So, e.g., table([[1, 2], [3, 4]]) would return a table whose first row is 1, 2 and second row is 3, 4. Look at sage manual for header rows, dividers etc.

Continue the sage worksheet.

> var('x')

> table([(x, mod(2^(q*2^x), p)) for x in [0..3]])

This will return a table that shows the remainder of 2q, 22q, 24q, 28q when divided by p. None of them are −1 mod (p), i.e., none of the remainders were p − 1.

For practice, you verify that the Carmichael number p = 75361 is not a prime. Then test an integer that is in fact prime, p = 104513, using a = 3. What did you notice?

Note: It can be shown that numbers of the form (6k + 1)(12k + 1(18k + 1) are Carmichael numbers if each of the three factors are prime. That is how we know 118901521 = 271 ∗ 541 ∗ 811 is a Carmichael number.