Number Theory and Asymmetric Cryptography - Paiet/Tech-Journal-for-Everything GitHub Wiki

Diffusion: Having changes to one character in the plaintext affect multiple characters in the ciphertext.

Confusion: Making the relationship between the statistical frequencies of the ciphertext and the actual key as complex as possible. This occurs by using a complex substitution algorithm.

Avalanche: A small change yields large effects in the output. This is Feistel's varaiation on Shannon's concept of Diffusion. Ideally, a change in one bit in the plaintext would affect all the bits of the ciphertext. This would be a complete avalanche.

In information theory, entropy is a measure of the uncertainty associated with a random variable.

Shannon's source coding theorem: it is impossible to compress the data such that the code rate is less than the Shannon entropy of the source, without it being virtually certain that information will be lost.

Number Groupings:

    N = Natural Numbers (1,2,3,4,etc..)
    Z = Integers (Natural numbers + 0 + negative numbers | any number that can be written without a fractional component)
    Q = Rational numbers (numbers expressed as the ratio of integers, or fractions)
    R = Real numbers (include all the rational numbers, such as the integer -3 and the fraction 5/4, and all the irrational numbers, such as √2)
    i = Imaginary numbers (numbers whose square is a negative)

Prime Numbers - any number whose factors are 1 and itself

Co-Prime Numbers - a number that has no factors in common with another number ( 3 & 7 )

Eulers Totient - counts the positive integers up to a given integer n that are relatively prime to n. For example, 7 has six numbers that are co-prime to it.

Modulus Operator - divide A by N and return the remainder. (sometimes symbolized as %, as in 9 % 2 = 1)
    5 mod 2 = 1
    12 mod 5 = 2

Fibonacci Numbers - Sequence of numbers derived by adding the last number in the sequence to the previous one to create the next
    Example:  1,1,2,3,5,8,13,21,35,56,91

Birthday Problem/Paradox - "How likely it is that any two people in a room of 23 would have the same birthday?"

(22+21+20+19+18+17+16+15+14+13+12+11+10+9+8+7+6+5+4+3+2+1 = 253) - total number of possible combinations among a group of 23 people

The probability reaches 100% when the number of people reaches 367 (since there are only 366 possible birthdays, including February 29). 99.9% probability is reached with just 70 people, and 50% probability with 23 people.

Birthday Attack - A birthday attack is a name used to refer to a class of brute force attacks based on the birthday paradox.

If you have an encryption algorithm with a key space of 32 bits, you can generate √4,294,967,295 random keys, (65,535 keys) and have a 50% chance of finding the right key. For a guaranteed match, you would have to generate 4,294,967,295 random keys. The birthday paradox means that one can try a set of random keys that is much smaller than the entire key space, and have a good chance of getting a match.

Pseudo-random number generators (PRNGs) are algorithms that can create long runs of numbers with good random properties, but eventually the sequence repeats.

The German Federal Office for Information Security (BSI) has established four criteria for quality of random number generators:  

    K1: A sequence of random numbers with a low probability of containing identical consecutive elements.  
    K2: A sequence of numbers which is indistinguishable from "true random" numbers according to specified statistical tests. 
    K3: It should be impossible for any attacker to calculate, or otherwise guess, from any given subsequence, any previous or future values in the sequence.
    K4: 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.

To be suitable for cryptography, any PRNG should meet K3 and K4 standards.

Examples of PRNGs:

    Naor-Reingold
    Mersenne Twister
    Linear Congruential Generator
    Lehmer Random Number Generator (twisted generalized feedback shift registers)
    Lagged Fibonacci Genrator (LFG) - If addition is used, then it is an Additive Lagged Fibonacci Generator or ALFG. If multiplication is used, it is a Multiplicative Lagged Fibonacci Generator or MLFG. If the XOR operation is used, it is called a two-tap generalized feedback shift register, or GFS.

Diffie-Helmann: (The first publically described asymmetric algorithm)

    A cryptographic protocol that allows two parties to establish a shared key over an insecure channel. Often used to allow parties to exchange a symmetric key through some unsecure medium, such as the Internet. It was developed by Whitfield Diffie and Martin Hellman in 1976.

RSA - developed in 1977 by three mathematicians, Ron Rivest, Adi Shamir, and Len Adleman. Based on the practical difficulty of factoring the product of two large prime numbers. Key sizes are typically from 1,024 - 4,096 bits.

Menezes-Qu-Vanstone (MQV) - A protocol used for key agreement that is based on Diffie-Hellman. It is incorporated in the public key standard IEEE P1363.

Digital Signature Algorithm (DSA) - described in U.S. Patent 5,231,668, filed July 26, 1991, and attributed to David W. Kravitz. It was adopted by the U.S. government in 1993 with FIPS 186.

Elliptic Curve Cryptography (ECC) - The security of Elliptic Curve cryptography is based on the fact that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is difficult to the point of being impractical to do so.

    Elliptic Curve Diffie Hellman (used for key exchange)  
    Elliptic Curve Digital Signature Algorithm (ECDSA)  
    Elliptic Curve MQV key agreement protocol

ElGamal - Based on Diffie-Hellman and was invented in 1984 by Taher Elgamal. It is used in some PGP implementations as well as GNU Privacy Guard software. The algorithm consists of three parts: the key generator, the encryption algorithm, and the decryption algorithm.

\