Asymmetric Cryptography

Question 1

Asymmetric Cryptography

Answer 1

AKA public key cryptography. Slower than symmetric key cryptography. Developed to overcome weaknesses in symmetric cryptography. Uses a public and a private key.

Question 2

N

Answer 2

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

Question 3

Z

Answer 3

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

Question 4

Q

Answer 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.

Question 5

R

Answer 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

Question 6

i

Answer 6

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

Question 7

Entropy

Answer 7

A measure of the uncertainty associated with a random variable.

Question 8

Prime Number

Answer 8

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

Question 9

Prime Number Theorem

Answer 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.

Question 10

Mersenne Primes

Answer 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.

Question 11

Co-prime Numbers

Answer 11

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

Question 12

Euler’s Totient

Answer 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!

Question 13

Modulus Operator

Answer 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

Question 14

Fibonacci Numbers

Answer 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.

Question 15

Birthday Theorem

Answer 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.

Question 16

Birthday Paradox

Answer 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.

Question 17

Birthday Attack

Answer 17

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

Question 18

The three types of random number generators

Answer 18

• Table look-up
• Hardware
• Algorithmic (software) - this category is most often used in cryptography and produces a pseudo random number.

Question 19

K1

Answer 19

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

Question 20

K2

Answer 20

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

Question 21

K3

Answer 21

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

Question 22

K4

Answer 22

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.

Question 23

Traits of a good Pseudorandom Number Generator (PRNG)

Answer 23

Uncorrelated sequences and Long period

Question 24

Naor-Reingold pseudorandom function

Answer 24

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

Question 25

Mersenne Twistter pseudorandom function

Answer 25

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.

Question 26

Linear Congruential Generator

Answer 26

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

Question 27

Lehmer Random Number Generator

Answer 27

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

Question 28

Lagged Fibonacci Generator

Answer 28

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.

Question 29

Blum Blum Shub

Answer 29

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.

Question 30

Yarrow

Answer 30

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

Question 31

Fortuna

Answer 31

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

Question 32

Diffie-Hellman

Answer 32

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.

Question 33

RSA

Answer 33

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.

Question 34

Menezes-Qu-Vanstone (MQV)

Answer 34

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

Question 35

Digital Signature Algorithm (DSA)

Answer 35

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

Question 36

Signing with DSA

Answer 36

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

Question 37

Elliptic Curve

Answer 37

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.

Question 38

Elliptic Curve Variations

Answer 38

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

Question 39

ElGamal

Answer 39

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.