Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Secure Cryptography > Public Key Cryptography > Flashcards

Public Key Cryptography Flashcards

1
Q

Primality Testing, why?

A

RSA needs big primes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Simple Prime Number Generation

A

Create random number and check

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Efficient Prime Checker

A 
Miller Rabin (Method of Choice)
Just as fast as fermat, less error.

______________
Fermat Test

quick O(||n||) operations per run

run t times with different a

correct answer if n prime

may give false answer for composite number

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Fermat Test Lemma

A

if p is prime and gcd(a,p)=1 then aˆ(p-1)=1 (mod p)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Fermat Test

A
  • pick random a< n
  • check gcd(a,n)=1
  • check wether n satisfies Fermat test lemma.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Carmichael Number

A

is a composite number that passes the Fermat test for every base a. (561 is the smallest Carmichael number)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Composite Number

A

A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, or the unit 1, so the composite numbers are exactly the numbers that are not prime and not a unit.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

How many Carmichael Numbers exist

A

infinite (Lemma Alford, Granville, Pomerance, 1994)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Miller-Rabin Test versus Fermat

A

Miller -rabin : Primality test without the problem of Carmichael numbers (that occur in Fermats test)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Miller-Rabin Test

A

Idea:
if n prime, then xˆ2=1 mod n only has x = +1

in Fermat aˆ(n-1) is an even power

taking roots we should arrive at -1

for odd powers, we cannot compute root (Find root equivalent to factoring), so we must stop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Miller-Rabin Test Properties

A

if n not prime <= p(n)/4 choices of a failed

run test t times, takes O(t * ||n||) arithmetic operations

—-> error chance <= (1/4)ˆt

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Prime and Prejudice

A
  • usually testing few small numbers suffices
  • many implementation fix(ed?) t or bases a_i
  • but error chance needs randomness
  • in crypto always consider adversarial input
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Failure chance against adversary implementations

A

OpenSSl 1.1.1pre6 fix t=2 for log n >=1300, failure chance 1/16

GNU GMP bases a_i depend deterministically on n, 100% failure for t<=15

LibTomMath t<= 256 use first t primes as bases 100 % failure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

AKS Primality Test

A

“Primes in P” -2002 paper- first provable polynomial-time algorithm

Idea Let a,n in Natural numbers.

We have (x+a)ˆn= xˆn + a in Z[x] if n is prime

reduce this modulo smaller polynomial

takes time O(||n||ˆ(6+e)). —> too long

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Sieve of Erathosthenes

A
  • Not a primality test
  • Good method to generate all primes p<=n

Function E(n):

create array a_i= 1 for i<=n
i=2
while iˆ2 <=n do
    if a_i = 1 then
        for j =2 , ...., round_down(n/i) do
            a_(i*j) =0
return {p: a_p=1}

_________________

running time O(n log log n)
space O(n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Primality Tests- Overview

A

Fermat : easy, fast, can have errors, fails for some numbers

Miller -Rabin: Method of choice
as fast as fermat
also one sided error
repeated independent calls reduce error to a direction of 0
in most libraries, but many implementations were (are?) vulnerable to malicious input (prime and prejudice)

AKS: no error, slow

Erathosthenes: no test, but a method to generate all primes.
only recommended for n

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Prime Generation

A

The chance of primality is about 1/log n

improve factor by ruling out small primes as divisors

18
Q

The Factorisation problem

A

Task: Given n in Natural number find a non-trivial divisor d of n.

-wether such d exists is primality testing

___________
problem is neither known to be in P nor NP-complete

some variants lie in intersection of NP and coNP

19
Q

Decision Problem

A

Given n,l,u in Natural numbers does n have a divisor d with l<=d<=u?

20
Q

Fermat - Factorisation

A

Let n=pq, if p, q are close, we can factor n.

21
Q

General Factorisation

A
  • primality test
  • Check whether n is (prime)power
  • assume n has two different divisors
  • look for any non trivial factor
  • recursively yields prime factorisation
22
Q

Group Bases Cryptography Motivation

A
  • RSA works in Z_n for n=pq
  • mathematical problem is e-th root
  • now we regard systems that work in arbitray groups but regard cyclic subgroup (g)<=G for some g in G
  • the underlying problem is the discrete logarithm problem (DLP)
  • framework for cryptosystem until we decide which group comparable to abstract classes in programming
  • keywords- Diffe-Hellman, Ellipitic, Curves, DSA , ElGamal
23
Q

The discrete Logarithm Problem (DLP)

A

given g, g ˆx= a in G find min x in Natural Numbers

24
Q

Diffie-Hellman Key exchange

Ideas

A
  • First published idea of public Key cryptography
  • no crypto system, but key exchange
  • we do not encode messages (yet), but get a common key
  • also solves problem from symmetric encryption
25
Q

Diffie-Hellman Key exchange

Method

A

Alices chooses a < o(g), computes A= g^a sends A to Bob

Bob chooses b< o(g) computes B= g^b, sends B to alice

Alice computes key K= B^a

Bob computes key K= A^b

-------------------------------
works because (g^a)^b= g^(ab)= g^(ba)= (g^b)^a
26
Q

Elgamal (1985)

A

secret key: choose random a < o(g)

public key A= g^a

Usage:
Encrypt: choose random b < o(g), send (B, c)= (g^b, m * A^b)
send (B, c)= (g^b, m* A^b)

Decrypt: get (B, c), compute m= c* (B^a) ^-1

__________________________
in fact a special case of Diffie -Hellman

27
Q

Attack Scenarios on Diffie-Hellman

A 
Discrete Logarithm (DLP)
given g, g^x find x secret key

Computational DH (CDH)
given g, g^a, g^b find g^(ab)
find session key

Decisional DH (DDH): given g, g^a, g^b, h decide g^(ab) =h decide which cipher belongs to message

trivially have hierarchy

DDH<=_p CDH <=_p <=_p DLP

28
Q

Shanks Baby - Step - Giant - Step

A

Attack on DH-key exchange

let n=o(g), pick step size k
secret x has unique representation x - ki+j with j
29
Q

Pohlig - Hellman Algorithm

A

attack on diffie Hellman

-improve computation of n= o(g) is known
-solve problem for subgroups of prime power size
-compose with CRT
-let p be largest prime division of n, running time
O(poly (||n||)* square_root(p))

protection:
ensure n has large prime divisor

“safe prime” p: select p such that (p-1)/2 also is prime, if G=Z_p^* then n=p-1 ensured n=2 * p’,

30
Q

Breaking Prime Powers (Hensel Lifting)

A

Attack on diffie Hellman

31
Q

Common example of finite groups

A
  • additive group (Z_n, +)
  • multiplicative group (Z_n ^*, *)
  • symmetric group S_n (permutations)
  • invertible matrices GL(n, p^k)={M in GF(p^k)^(n x m) : det M not equal 0}

Do not yield Significant cryptographic advantage over RSA

32
Q

Elliptic Curves

A

y^2 = x^3 -x +1

33
Q

What can Quantum computers break in crypto?

A

Can solve both factoring and DLP

Both RSA and DH scheme are broken

Even qauntum computers cannot solve NP-hard problems

34
Q

Post Quantum Crypto Schemes

A

base crypto scheme on NP-hard problem

Most common candidates:

- Lattice problems
- multivariate polynomials
- problem from coding theory
35
Q

Lattice problem

A

Given a base of vectors B = {v_1, ….., v_n}, their lattice is

L=span_Z(B) = BZ^n= {sum(a_i* v_i : a_i in Z}) for i=1->n}

36
Q

Lattice Problem Properties

A

Bases A,B create same lattice if A=UB for some U in Z^(nxm)
with det U=+1 (U is unimodular)

isomorphism l aprox Z^n for every lattice but isomorphism destroys angles and distances

37
Q

Shortest Vector Problem (SVP)

A

A Lattice Problem:

given B, find a vector v in L with ||v|| minimal

NP hard under randomised reduction, with n calls on SVP can solve CVP, short base makes both problems much easier

38
Q

Closest Vector Problem (CVP)

A

A Lattice Problem:

given B and u in Z^n find a vector v in L, with ||u-v|| minimal

39
Q

Shortest Base Problem (SBP)

A

A Lattice Problem:

given B find base B= {v_1, ….v_n} with BZ^n = BZ^n such that Product ||v_i`|| minimal

40
Q

NTRU N-th Degree Truncated Polynomial Ring

A

feasible key size, still unbroken

Post quantum crypto

41
Q

Multivariate Crypto

A

post quantum

Given finite field K, polynomial f_i in K[x_1,….x_n] of degree 2

Task: find x in K^n with f_i(x)=0 for all i

can encode SAT, easiest for K = Z_2, via x ∧ y = x · y and
x ∨ y = x + y − xy and auxiliary variables ⇒ NP-hard

Basic Idea
additional secret information allows to solve hard problem

42
Q

symmetric versus asymmetric crypto

A

symmetric- both have the same key (secure channel?)

asymmetric- public and private key

Secure Cryptography (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions