Math220

Question 1

Find the elements in Zn

Answer 1

All primes up to n
eg:
Elements in Z8:
1, 3, 5, 7

If n is prime, all integers 1 -> n-1

Question 2

Find the order of each element in Zn

Answer 2

1^1 = 1
3^1 = 3, 3^2 = 1
5^1 = 5, 5^2 = 1
7^1 = 7, 7^2 = 1

All elements have order 2

Question 3

When does Zn have generators?

Answer 3

Zn has generators if an element(s) powers cover all of Zns elements.

Question 4

How do you get the number of invertible elements?

Answer 4

o(n) = (p-1)(q-1)

Z has o invertible elements

Question 5

What is Euler’s o-function?

Answer 5

o(n) = (p-1)(q-1)

Question 6

Why is 4x+2 not a good function to use in an affine cipher?

Answer 6

Encryption of two different plaintexts can result in the same ciphertext.

eg: f(1) = 6 and f(14) = 6

Question 7

When does Zn always have a generator?

Answer 7

If n is prime.

Question 8

Briefly, how do you decipher c in a Rabin Cipher?

Answer 8

DECIPHERING C: find integers u and v such that pu + qv = 1
THEN FIND: four possible values for m as +-pum_q +-qvm_p.
In particular, c is not uniquely determined by m

Question 9

What are the possible orders of elements in Z23?

Answer 9

The order of an element in Z23 is a divisor of 23-1=22.

So 1,2,11,22 are the possible orders of Z23

Question 10

What does it mean for a cryptosystem to be perfectly secure?

Answer 10

Perfectly secure means that the ciphertext contains no information of the message no matter how much computing or analysis you do.

Question 11

Is the RSA cryptosystem secure? Why?

Answer 11

No.
Because it requires factoring a public key to decipher the message, so, given enough computing and analysis, you can completely recover the message.

Question 12

The one-time pad is perfectly secure. Why is it not more widely used?

Answer 12

The key is as large as the message. So the key exchange problem is just as difficult as the initial problem of exchanging the secure message.

Question 13

When is x its own inverse in Zp?

Answer 13

If x^2 is congruent to 1 modulo p.

Question 14

How do you calculate n in an RSA cipher?

Answer 14

n = pq

Question 15

The equation for showing the encrypted plaintext of Rabin cipher

Answer 15

c => m^2 mod n

Question 16

What is Euler’s formula?

Answer 16

F + V = E + 2,
where F is the number of faces, V the number of vertices, and E the number of edges. A cube, for example, has 6 faces, 8 vertices, and 12 edges and satisfies this formula.