Cryptography

Question 1

Caesar cipher

Answer 1

Encrypt with x + 3
Decrypt with x - 3

Question 2

Vigenere cipher

Answer 2

Given vector responding to keyword eg. ABC is 123
Then
Hello = 8,5,11,11,14
Goes to
8+1, 5+2, 11+3, 11+1, 14+2
9,7,14,12,16

Question 3

In RSA one chooses

Answer 3

• 2 large primes p != q to form n=pq
• 2<=e<=φ(n) such that gcd(e, φ(n)) = 1
  -compute 2<=s<=φ(n) such that es = 1 mod(φ(n))

e is encryption s is decryption

Question 4

Public key in RSA

Answer 4

k^p = (n,e)

Question 5

RSA secret key

Answer 5

K^s = (n,s)

Question 6

RSA encryption function

Answer 6

Question 7

RSA decryption function

Answer 7

Question 8

RSA plaintext and cipher text alphabets

Answer 8

Question 9

RSA key space

Answer 9

Question 10

Prove

Answer 10

Question 11

To send plaintext, RSA

Answer 11

-Compute c = m^e mod(n)
Where m is message

Question 12

To decipher c, RSA

Answer 12

Compute (by FLT and Euler’s Theorem)

Question 13

Quick way to calculate φ(n) for RSA

Answer 13

Φ(n) = (p-1)(q-1) where pq=n (primes p!=q)

Question 14

Basic principle

Answer 14

Question 15

Proof of basic principle

Answer 15

Question 16

Fermats primality test

Answer 16

Question 17

Carmichael’s numbers

Answer 17

Question 18

What implies that n is squarefree?

Answer 18

Implies n is squarefree

Question 19

Let n>1 be an odd integer. n-1=2^k * u (for odd u), then?

Answer 19

-n is prime <=>

Question 20

Miller Rabin primality test

Answer 20

Question 21

Miller Rabin witness to the compositness of n

Answer 21

Question 22

Theorem that states that Miller Rabin test has a very high probability of deciding wether a given integer is composite

Answer 22

Question 23

To compute p and q from n = pq and φ(n)

Answer 23