public key cryptography

Question 1

public key crypto system

Answer 1

for each k, e_k is the inverse of d_k
e_k(x) and d_k(y) are easy to compute
computationally infeasible to derive d_k from e_k
feasible to compute e_k and d_k from k

Question 2

one-way function

Answer 2

easy to compute f(x)
but computationally infeasible to find x from y

Question 3

trap-door one way function

Answer 3

given trapdoor Information it becomes feasible

Question 4

Euler phi-function

Answer 4

φ(n)=number of integers less than n and relatively prime to n

Question 5

Fermat’s little theorem

Answer 5

suppose p prime and b in invertible in Zp then b^p=b mod p

Question 6

Euler

Answer 6

for all b in Zn*, b^φ(n)=1 mod n

Question 7

public key (RSA)

Answer 7

(n,b) where b is the encryption exponent

Question 8

private key (RSA)

Answer 8

(p,q,a) where a is the decryption exponent

Question 9

basic method for generating big primes

Answer 9

generate a large number and test for primality

Question 10

RSA problem

Answer 10

recover x given x^b mod n, n and b

Question 11

splitting

Answer 11

find n=ab where a,b are non-trivial factors of n

Question 12

strong prime

Answer 12

p-1 has a large prime factor, say r
p+1 has a large prime factor
r-1 has a large prime factor

Question 13

when do strong primes offer no protection?

Answer 13

Elliptic curve method

Question 14

x is B-smooth

Answer 14

all prime factors of x are <=B

Question 15

factor base

Answer 15

set of primes below some bound B

Question 16

framework for congruent squares algorithm

Answer 16

select the factor base
collect relations between elements of the factor base producing squares
find dependencies: reduce exponents modulo 2 and use linear algebra to find a dependency modulo 2

Question 17

Dixon’s random squares

Answer 17

select z at random

Question 18

Is RSA semantically secure?

Answer 18

No, because the attacker can distinguish cipher texts

Question 19

how is decryption if we use small private exponent?

Answer 19

use CRT

Question 20

broadcast attack

Answer 20

Oscar is an external attacker. He doesn’t have a key

Question 21

Coppersmith’s theorem

Answer 21

let p be monic polynomial of degree d in one variable modulo n (of unknown factorisation)
one can find in time polynomial (long,d) all integers x0 such that p(x0)=0 mod n and |x0|<=n^{1/d}

Question 22

coppersmith’s short padding

Answer 22

let n be l bits long and x be at most l-[l/b^2] bits
if the message is sent twice with different random paddings of length less than [l/b^2] then an attacker can efficiently recover x given only the ciphertexts

Question 23

cryptographic primitive

Answer 23

basic RSA

Question 24

protocols

Answer 24

built of many primitives to achieve secure communication (perhaps data integrity too)

Question 25

most important RSA protocol

Answer 25

Optical Asymmetric Encryption Padding

Question 26

order of a group

Answer 26

number of elements

Question 27

finite group

Answer 27

order is finite

Question 28

order of an element

Answer 28

smallest positive integer m such that g^m=1

Question 29

cyclic group

Answer 29

there exists an element with order equal to the order of the group

Question 30

primitive element mod p

Answer 30

a in Zp* with order p-1

Question 31

theorem for finding primitive elements

Answer 31

a is a primitive element iff a^{(p-1)/q}/=1 for all primes q|(p-1)

Question 32

c is discrete logarithm of b in Zp*

Answer 32

a^c=b mod p