Diffie-Hellman-Merkle

Alice and Bob agree two numbers:

  • Alice and Bob each choose a secret random integer:

    a={{ a }} and b={{ b }} <

    Create two integers A and B that they send to each other.

    • Alice sends A = ga mod p = {{ A }} to Bob.
    • Bob sends B = gb mod p = {{ B }} to Alice.

    Alice and Bob now compute the same shared secret, s.

    • sa = Ba mod p = (gb mod p)a mod p = gba mod p = {{ sa }}
    • sb = Ab mod p = (ga mod p)b mod p = gab mod p = {{ sb }}
    • ∴ sa = sb = s

    Alice and Bob now share the same secret s={{ sa }} and use this to encrypt and decrypt messages.

    About

    Diffie-Hellman key exchange is a means to agree a secret number to encrypt and decrypt messages.

    Number theory may seems very abstract but this is a very practical application. It is used by TLS, which is the protocol used to secure requests the URLs with the https:// prexix.

    An intuitive way to understand this is that Alice chooses a secret color she mixes with red and Bob chooses a secret color he mixes with blue. They send the mixes to each other. Alice adds her secret color to Bob's mix and Bob adds his to Alices, each ends up with the same colour. Thus secrets colors remain secret if eavesdroppers are unable to separate mixes.

    The random integers are kept secret, never sent over a network and the bigger the numbers the more secure but the slower the calculation. Any eavesdropper would see the numbers A and B but not a and b. To calculate these would require too much computing power to be practical.

    Note that the secret number is always less than the chosen prime (s<p) because operations are mod p.

    Arbitrary precision arithmetic

    Since the Math.pow function produces numbers far larger than can fit into the IEEE 754 double precision numbers provided by Javascript. This algorithm needs arbitrary precision arithmetic, gratefully provided bignumber.js for this implementation.

    One can implement the algorithm in Python trivially since it has arbitrary precision arithmetic built into the language.
    $ p=23;g=5;a=18;b=17; $ A=g**a % p; B=g**b % p; $ sa=B**a % p; sb=A**b %p) $ sa,sb (12, 12)

    In practice one would use Modular exponentiation.

    • Greatest common divisor

    Given two numbers: and

    Using Euclid's algorithm:

    Greatest common divisor (GCD) {{ gcd }}
    Lowest common multiple are (LCM) {{ lcm }}

    $$lcm(a,b) = \frac{|a.b|}{gcd(a,b)}$$

    The greatest common divisor and the lowest common multiple between two numbers.

    Sieve of Eratosthenes

    Using the Sieve of Eratosthenes. The prime numbers up to:


    {{ prime }}

    Plot against logarithm
    Primitive root of a prime number r modulo n
    Given a prime number

    The primitive roots of {{ nn }} are: {{ primitiveRoots }}.

    {{root}}

    {{ root }} is a primitive root of {{ nn }} because all the following results differ:

  • {{ root }} ^ {{ ii }} mod {{ nn }} = {{ Math.pow(root, ii) % nn }}
    • Introduce Euler’s Totient Function
    Floating point numbers

    In JavaScript all numbers are double-precision 64-bit floating point, stored according to the IEEE 754 standard. Floating point numbers look like decimals or real numbers but they are really just approximations. Please see What Every Engineer Should Know About Floating Point?

    Rounding errors

    Enter a floating point number:

    Ceiling= {{ Math.ceil(float) }} and Floor= {{ Math.floor(float) }}

    Binary floating point numbers divide exactly by two but not by 3 or 10:


    {{float}} ÷ 2 = {{ float / 2 }}
    {{float}} ÷ 3 = {{ float / 3 }}
    {{float}} ÷ 10 = {{ float / 10 }}

    Summing

    Summing a series of floating point numbers can lead to small errors accumulating into bigger error. The Kahan Summation Algorithm addresses this by keeping a running compensation.

    Order of Magnitude

    The order of magnitude of the above ({{ float }}) is {{ orderOfMagnitude(float) }}. or to the power ten: {{ Math.pow(10, orderOfMagnitude(float)) }}.

    This is calculated using the following Javascript:

    const CORRECTION = 0.000000001 return number == 0 ? 0 : Math.floor(Math.log(number) / Math.LN10 + CORRECTION)

    Constants

    ConstantValueNote
    E{{ Math.E }}
    LN10{{ Math.LN10 }}
    LN2{{ Math.LN2 }}
    LOG10E{{ Math.LOG10E }}
    LOG2E{{ Math.LOG2E }}
    PI (π) {{ Math.PI }}
    √ ½ {{ Math.SQRT1_2 }}
    √ 2 {{ Math.SQRT2 }}
    EPSILON{{ Number.EPSILON }}(difference between 1 and the smallest floating point number greater than 1)
    MAX SAFE INTEGER {{ Number.MAX_SAFE_INTEGER }}
    MIN SAFE INTEGER {{ Number.MIN_SAFE_INTEGER }}
    MAX VALUE {{ Number.MAX_VALUE }}
    MIN VALUE{{ Number.MIN_VALUE }}
    -INFINITY{{ Number.NEGATIVE_INFINITY }}
    NaN{{ Number.NaN }}
    INFINITY{{ Number.POSITIVE_INFINITY }}