Module 3- Number Theory and Asymmetric Crypography

Question 1

AKA public key cryptography.

Uses a public and a private key.

Answer 1

Asymmetric Cryptography

Question 2

Denotes the natural numbers. 1, 2, 3, etc.

Answer 2

N

Question 3

Denotes the integers. These are whole numbers -1, 0, 1, 2 etc.

Answer 3

Z

Question 4

Denotes the rational numbers (ratio of integers). Any number that can be expressed as a ratio of two integers 3/2, 17/4, 1/5 etc.

Answer 4

Q

Question 5

Denotes the real numbers. This includes the rational numbers as well as numbers that cannot be expressed as a ratio of two integers, for example √2

Answer 5

R

Question 6

Denotes imaginary numbers. These are numbers whose square is a negative. √-1 = 1i

Answer 6

i

Question 7

A measure of the uncertainty associated with a random variable

Answer 7

Entropy

Question 8

Any number whose factors are 1 and itself. Example 2, 3, 5, 7, 11, 13, 17, 23

Answer 8

Prime Number

Question 9

If a random number N is selected, the chance of it being prime is approx. 1/ln(N), where ln(N) denotes the natural logarithm of N.

Answer 9

Prime Number Theorem

Question 10

Uses a formula, Mn = 2n − 1 where n is a prime number, to generate primes. Works for 2, 3, 5, 7 but fails on 11 and on many other n values.

Answer 10

Mersenne Primes

Question 11

A number that has no factors in common with another number. For example, 3 and 7 are this.

Answer 11

Co-prime Numbers

Question 12

The number of positive integers less than or equal to n that are co-prime to n is called the * *** of n. For example the number 6; 4 and 5 are co-prime with 6. Therefore, ** **=2. Symbolized by ϕ(n). For a prime number p, ϕ(n) is always p-1.
Part of the RSA algorithm!

Answer 12

Euler’s Totient

Question 13

Used in a number of cryptography algorithms. Simply divide A by N and return the remainder.

• So 5 mod 2 = 1
• So 12 mod 5 = 2
• Sometimes symbolized as % as in 5 % 2 = 1

Answer 13

Modulus Operator

Question 14

Named after Leonardo of Pisa who was also known a *******. Sequence of numbers are derived by adding the last two numbers to create the next number, N1 + N2 = n3. Example, 0, 1, 1, 2, 3, 5, 8, 13, 21, 35, 56. Some random number generators use this.

Answer 14

Fibonacci Numbers

Question 15

The number of people you would have to invite to a party so that two will have the same birthday (with high probability). √365
You need √N to have a high probability of collision.
Answer is approximately 1.174 √365 to have a high probability of collision.

Answer 15

Birthday Theorem

Question 16

The number of people you need to have a high likelihood that two share the same birthday. The answer is 23. This is a classic math problem that relates to hashes.

Answer 16

Birthday Paradox

Question 17

Name used to refer to a class of brute force attacks against hashes. Attempts to find a collision.

Answer 17

Birthday Attack

Question 18

random number generator is most often used in cryptography and produces a pseudo random number.

Answer 18

-Algorithmic (software)

Question 19

The three types of random number generators

Answer 19

• Table look-up
• Hardware
• Algorithmic (software)

Question 20

A sequence of random numbers with a low probability of containing identical consecutive elements.

Answer 20

K1

Question 21

A sequence of numbers which is indistinguishable from true random according to statistical tests.

Answer 21

K2

Question 22

It should be impossible for an attacker to calculate any previous or future values.

Answer 22

K3

Question 23

It should be impossible for an attacker to calculate or guess from an inner state of the generator any previous numbers in the sequence or any previous inner generator states.

Answer 23

K4

Question 24

Traits of a good Pseudorandom Number Generator (PRNG)

Answer 24

Uncorrelated sequences

Long period

Question 25

Created in 1997 by Moni Naor and Omer Reingold. The mathematics of this function are complex for non-mathematicians.

Answer 25

Naor-Reingold pseudorandom function

Question 26

Originally not suitable for cryptography but permutations of it are. Created by Makoto Matsumoto and Takuji Nishimura. Has a very large period, greater than many other generators.

Answer 26

Mersenne Twistter pseudorandom function

Question 27

Determined by the following four integer values:
m the modulus m>0
a the multiplier 0, 0

Answer 27

Linear Congruential Generator

Question 28

Created by D. H. Lehmer. It is a classic example of a Linear congruential generator. A PRNG type of linear congruential generator (LCG) that operates in multiplicative group of integers modulo n.
The basic algorithm is Xi+1=(aXi + c) mod m, with 0 ≤ Xi ≤ m

Answer 28

Lehmer Random Number Generator

Question 29

A type of pseudorandom number generator. If addition is used, then it is an ALFG. If multiplication is used then it is a MLFG. If XOR is used it is called a two-gap generalized feedback shift register, or GFS.

Answer 29

Lagged Fibonacci Generator

Question 30

Created in 1986 by Lenore Blum, Manuel Blum, and Michael Shub. Format is Xn+1 = Xn2 Mod M
The main difficulty of predicting the output of this is the difficulty of the “quadratic residuosity problem”. As difficult as breaking the RSA public-key cryptosystem.

Answer 30

Blum Blum Shub

Question 31

Algorith that was created by Bruce Schneier, John Kelsey, and Niels Ferguson. No longer recommended, Fortuna is recommended instead. Consists of four parts:

• Entropy Accumulator
• Generation Mechanism
• Reseed Mechanism
• Reseed Control

Answer 31

Yarrow

Question 32

A group of PRNGs that has many options for whoever implements the algorithm. Consists of three parts:

• A generator
• An entropy accumulator
• A seed file

Answer 32

Fortuna

Question 33

A cryptographic protocol that allows two parties to establish a shared key over an insecure channel. Released in 1976, developed earlier by British Intelligence Service. Used for the exchange of symmetric keys.

Answer 33

Diffie-Hellman

Question 34

Created in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman at MIT. Most widely used public key cryptography algorithm. Based on relationships with prime numbers. This algorithm is secure because it is difficult to factor a large integer composed of two or more large prime factors.

Answer 34

RSA

Question 35

A protocol for key aggreement based on Diffie-Hellman. Created in 1995. Incorporated into the public key standard IEEE P1363.

Answer 35

Menezes-Qu-Vanstone (MQV)

Question 36

Filed July 26, 1991 under U.S. Patent 5,231,668. Adopted by the U.S. Government in 1993 with FIPS186.
Choose a hash function (traditionally SHA1). Select a key length L and N. Choose a prime number q that must be less than or equal to the hash output length. Choose a prime number p such that p-1 is a multiple of q. Choose g, this number must be a number whose multiplicitive order modulo is q. Choose a random number x, where 0

Answer 36

Digital Signature Algorithm (DSA)

Question 37

Let H be the hashing function and m the message. Generate a random value for each message k where 0

Answer 37

Signing with DSA

Question 38

Created in 1985 by Victor Miller, IBM. Endorsed by the NSA, schemes based on it for Suite B. Protects information classified up to top secret with 384bit keys. Based on y2 = x3 + Ax + B.

Answer 38

Elliptic Curve

Question 39

Elliptic Curve Variations

Answer 39

• Elliptic Curve Diffe-Hellman (used for key exchange)
• Elliptic Curve Digital Signature Algorith (ECDSA)
• Elliptic Curve MQV key agreement protocol

Question 40

Created in 1984 by Taher ***. Used in some PGP implementations as well as GNU Privacy Guard software. Consists of three parts: key generator, encryption algorithm, decryption algorithm. This encryption is probabilistic.

Answer 40

ElGamal