Modular Arithmetic

Vernam Cipher is a #Substitution Cryptographic #algorithm invented by Gilbert Vernam in 1918. It works on the binary data with bit-wise XOR operation (or in Modular Arithmetic, \(\mod 2\)) and chooses a key with no statistical relationship with the plaintext. It is widely adopted as it could be implemented easily using hardware circuits. The encryption scheme is formalised using the following equations:

RSA is an #Asymmetric Cryptography scheme based on exponentiation in a Galois Field over integers modulo a prime which utilises integers as large as 1024 bits. The running time for exponentiation is \(o((\log n^3))\) operations, which is reasonable. However, to break the #algorithm, it needs \(o(e^{\log n \log \log n})\) factorisations, thus it is hard to crack#.

RSA works in both encryption and decryption due to the nature of the equation \(de = 1 \mod \phi(n)\) which can be reformed into the equation \(de = 1 + k \phi(n)\) (Modular Arithmetic#) and the fact that \(M^{\phi(n)} \mod n = 1\) (Euler’s Theorem#). From decryption equation \(C^d = M^{e \cdot d} = M^{1 + k \cdot \phi(n)} = M^1 \cdot (M^{\phi(n)})^k = M^1 \cdot 1^k = M^1 = M \mod n\), thus proved that RSA works.

Modulus \(g(D)\) is done by eliminating similar Ds until we reach the lowest exponentiation using long division. Use the highest possible degree polynomial to divide \(g(D)\) using \(D^{n-k} m(D)\). The long division shown below illustrates how to do it:

From #Modular Arithmetic, \(b\) is a residue of \(a \mod n\) as it could be written in \(a = qn + b\). Finding the next in line residue is by choosing the smallest positive remainder from the equation as residue. Such process is similar to the following example:

Common in Cryptography#, \(GF(p)\) is a Set# where \(\{a \in P | a \in \mathbb{Z} \text{ and } 0 \le a \le p - 1 \}\) with modulo# prime \(p\) as its arithmetic operations. For example, \(GF(7)\) multiplication looks like the table below.

In Modular Arithmetic#, the find the multiplicative inverse of a number \(a\) is by the equation, where \(a\) is relatively prime to \(n\):

Euclidean Algorithm is used to find the #Greatest Common Divisor (GCD) between the number \(a\) and \(b\), typically denoted as \(EUCLID(a, n)\). It uses the modulo nature# of two numbers, where \(a = qn + b\), \(b\) as the remainder of \(a \mod n\), following the steps:

If the number \(b\) could be used to divide another number \(a\) without any remainder, then \(b\) is said to be a divisor (or a factor as it implies to be multipliable by \(b\)) to \(a\), which can be denoted as \(b | a\).

DLOG is a hard problem in mathematics which is the inverse problem of exponentiation of a number modulo# \(p\). For instance, to find \(x\) in \(y = g^x (\mod p)\), it is written as \(x = \log_g y (\mod p)\). If \(g\) is a Primitive Root#, then DLOG always exists, otherwise it may not.

Due to the nature of Cyclic Code, we can state that a binary polynomial of order \(n-1\) or less is a code word polynomial if and only if it is a multiple of \(g(D)\)#. Multiply a polynomial with \(D^i\) modulus with \(D^n + 1\) can be viewed as a \(i\) right cyclic shift.

Most encryption algorithms use exponentiation, accompany by Modular Arithmetic# as shown in the following equation:

Note: \(ed = 1\) due to \(de = 1 + k \phi(n)\) (Modular Arithmetic#) and \(M^{\phi(n)} \mod n = 1\) (Euler’s Theorem#). Full proof is shown in #Rivest-Shamir-Adleman (RSA).

CRT is used to speed up modulo computations by computing smaller moduli \(m_i\) in the Set \(\mod M = m_1 m_2 \ldots m_3\) instead of full modulus \(M\).