- pick random a< n - check gcd(a,n)=1 - check wether n satisfies Fermat test lemma.

- 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

Public Key Cryptography Flashcards by Lily Huegerich

Primality Testing, why?

RSA needs big primes

How well did you know this?

Not at all

Perfectly

Simple Prime Number Generation

Create random number and check

How well did you know this?

Not at all

Perfectly

Efficient Prime Checker

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?

Not at all

Perfectly

Fermat Test Lemma

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

How well did you know this?

Not at all

Perfectly

Fermat Test

pick random a< n
check gcd(a,n)=1
check wether n satisfies Fermat test lemma.

How well did you know this?

Not at all

Perfectly

Carmichael Number

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?

Not at all

Perfectly

Composite Number

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?

Not at all

Perfectly

How many Carmichael Numbers exist

infinite (Lemma Alford, Granville, Pomerance, 1994)

How well did you know this?

Not at all

Perfectly

Miller-Rabin Test versus Fermat

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

How well did you know this?

Not at all

Perfectly

Miller-Rabin Test

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?

Not at all

Perfectly

Miller-Rabin Test Properties

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?

Not at all

Perfectly

Prime and Prejudice

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?

Not at all

Perfectly

Failure chance against adversary implementations

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?

Not at all

Perfectly

AKS Primality Test

“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?

Not at all

Perfectly

Sieve of Erathosthenes

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?

Not at all

Perfectly

Primality Tests- Overview

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?

Not at all

Perfectly

Prime Generation

The chance of primality is about 1/log n

improve factor by ruling out small primes as divisors

The Factorisation problem

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

Decision Problem

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

Fermat - Factorisation

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

General Factorisation

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

Group Bases Cryptography Motivation

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

The discrete Logarithm Problem (DLP)

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

Diffie-Hellman Key exchange

Ideas

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

Diffie-Hellman Key exchange | Method

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 ```

Elgamal (1985)

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

Attack Scenarios on Diffie-Hellman

``` 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

Shanks Baby - Step - Giant - Step

Attack on DH-key exchange ``` let n=o(g), pick step size k secret x has unique representation x - ki+j with j ```

Pohlig - Hellman Algorithm

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',

Breaking Prime Powers (Hensel Lifting)

Attack on diffie Hellman

Common example of finite groups

- 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

Elliptic Curves

y^2 = x^3 -x +1

What can Quantum computers break in crypto?

Can solve both factoring and DLP Both RSA and DH scheme are broken Even qauntum computers cannot solve NP-hard problems

Post Quantum Crypto Schemes

base crypto scheme on NP-hard problem Most common candidates: - Lattice problems - multivariate polynomials - problem from coding theory

Lattice problem

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}

Lattice Problem Properties

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

Shortest Vector Problem (SVP)

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

Closest Vector Problem (CVP)

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

Shortest Base Problem (SBP)

A Lattice Problem: given B find base B`= {v_1`, ....v_n`} with BZ^n = B`Z^n such that Product ||v_i`|| minimal

NTRU N-th Degree Truncated Polynomial Ring

feasible key size, still unbroken | Post quantum crypto

Multivariate Crypto

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

symmetric versus asymmetric crypto

symmetric- both have the same key (secure channel?) asymmetric- public and private key