Cryptography fundamentals

Terminology

We’re going to focus on math aspects of the cryptography here, but as the base stone of the discussion we assume that cryptographic strength depends on the algorithms selected, but mainly on the key strength.

Modular exponentiation - giving the reminder of raising \(b\) (base) in power \(e\) (the exponent) divided by a positive number \(m\) (modulus):

$$\begin{align*} c \equiv b^e \mod{m} \end{align*}$$

Modular exponentiation is efficient to compute, even for very large integers.

The solution to the discrete logarithm problem is to find some non-negative integer\(x\) satisfying equation \(g^x=a\). In most cases, this operation is believed to be difficult. Thus, making modular exponentiation behave line one-way function and a good candidate in cryptographic algorithms.

For strong cryptography, \(b\) is often at least 1024 bits long.

Efficient calculation of modular exponentiation

The m-th term of any constant-recursive sequence (such as Fibonacci numbers or Perrin numbers) where each term is a linear function of k previous terms can be computed efficiently modulo n by computing A^m mod n, where A is the corresponding k×k companion matrix. The above methods adapt easily to this application. This can be used for primality testing of large numbers n, for example.

Diffy-Hellman common key generating

Diffie-Hellman (DH) algorithm is allowed to generate and use a common secret key over a public channel. Thus, it belongs to the symmetric cryptography, i.e. use a single key to encrypt and decrypt messages. All sides share the common \(g\) and \(p\) values (not a secret).

In the first step, both sides - Alice and Bob - each generate secret values - \(a\) and \(b\) correspondingly - and then calculate

$$A=g^a \bmod p$$

$$B=g^b \bmod p$$

At the second stage, the sides exchange \(A\) and \(B\), and then each one calculates independently

$$K=B^a \bmod p=g^{ba} \bmod p$$

$$K=A^b \bmod p = g^{ab} \bmod p$$

and as it is easy to see got the same number.

RSA algorithm

1. Choose 2 large random prime numbers: \(p\) and \(q\) and calculate their product : \(N= p \cdot q\). For example, let \(p=19, q=41, N=779\).

2. Calculate Euler's totient function: \(\varphi(N) = \varphi(p \cdot q)= (p-1) \cdot (q-1)\)

   (The last equality follows from the definition. Indeed, if \(p\) is prime, then all numbers less than \(p\) are coprime to it, and there are exactly \(p-1\) of them).

   In our example \(\varphi(779)=18 \cdot 40=720\)

3. Select \(e\) that less than \(\varphi(N)\)and coprime with \(\varphi(N)\).

   In our example \(e=691\)

4. Finally, find multiplicative inverse \(d\): \(d \cdot e = 1 \bmod \varphi(n)\). Usually, it may be found with the help of an extended Euclidean algorithm.

   In our example \(d=571\)

After all this:

• \(e\) and \(n\) - public (encryption) key

• \(d\) - private (decryption) key

• A message, represented by an integer \(m\), where \(0 < m < n\), is encrypted by computing \(S=m^e \pmod n\). It is decrypted by computing \(t=S^d \pmod n.\)

• The security of an RSA system would be compromised This if the number \(n\) could be efficiently factored or if \(\varphi(n)\) could be efficiently computed without factoring \(n\).

In our example:

\(\{ 691, 779\}\) - public key

\(\{ 571, 779 \}\)- private key