Skip to content

Applied Cryptograph Notes



GCD of two integer is the largest integer that divide both given integers.


Factorization method

Find the integer factorization of the two integer first, find the common factors and multiply together.

Euclidean Algorithm

The key idea of Euclidean algorithm is to use the smaller integer to "measure" the larger integer, then use the reminder to "measure" the smaller integer, and so on, untill the reminder is 0. Generally, gcd(a, b) can be obtained by apply the following sequence of equations until r_k = 0.

a = q_0 b + r_0
b = q_1 r_0 + r_1
r_0 = q_2 r_1 + r_2
r_{k - 3} = q_{k-1} r_{k - 2} + r_{k - 1}
r_{k - 2} = q_{k-1} r_{k - 1} + r_{k}

Because the qotient isn't needed in find the GCD. We can replace the iteration r_{k-2} = q_k r_{k-1} + r_k with modulo operations r_k = r_{k-2} \mod r_{k-1}.

Modular multiplicative inverse (modular division)


A modular multiplicative inverse of an integer a is an integer x such that the product ax is congruent to 1 with respect to the modulus m. The congruence is written as ax \equiv 1 \pmod m. Two integers a and b are said to be congruent modulo m if m divides their differences, denoted by a \equiv b \pmod m.


The modular multiplicative inverse x of an integer a may have zero, one or several solutions. But with the condition \gcd(a, m) = 1 hold, there exists exactly one solution. This is the basis of the theory used to calculate the private key d in RSA. Now we could use Extended Euclidean Algorithm to calculate d.

Extended Euclidean Algorithm

def EEA(r0, r1):
    ''' Extended Euclidean algorithm'''
    # ensure r0 > r1
    if r0 < r1:
        r0 ^= r1
        r1 ^= r0
        r0 ^= r1

    # init value
    s0, s1, t0, t1 = 1, 0, 0, 1

    while True:
        ri = r0 % r1
        q = (r0 - ri) / r1
        si = s0 - q * s1
        ti = t0 - q * t1
        if ri == 0:

        r0, r1 = r1, ri
        s0, s1 = s1, si
        t0, t1 = t1, ti

    return r1, s1, t1

Euler's \Phi function

Definition: The number of integers in \mathbb{Z}_m relatively prime to m is denoted by \Phi(m). \mathbb{Z}_m is interger set. \mathbb{Z}_6 = \{0,1,2,3,4,5\}.

How to calculate \Phi(m)

Let m have the folllowing canonical factorization

m = p^{e_1}_{1} \cdot p^{e_2}_{2} \cdot, \dots, \cdot p^{e_n}_{n}

Where the p_i are distinct prime numbers and e_i are positive integers, then

\Phi(m) = \prod_{i = 1}^{n}{(p^{e_i}_{i} - p^{e_i - 1}_{i})}.

For example:

  1. m = 240 = 2^4 \cdot 3 \cdot 5, \Phi(240) = (2^4 - 2^3)\cdot (3^1 - 3^0) \cdot (5^1 - 5^0) = 8 \cdot 2 \cdot 4 = 64
  2. m = 21 = 3 \cdot 7, \Phi(21) = (3^1 - 3^0)\cdot (7^1 - 7^0) = 2\cdot6 = 12

Remark 1: The security of RSA is based on the fact that Euler's function \Phi(m) is hard to be calculated for large integers, as we know it is compuationally hard to do prime factorization for a large integer.

Euler's Theorem

Definition: Let a and m be integers with gcd(a, m) = 1, then: a^{\Phi(m)} \equiv1\pmod m.

Fermat's Little Theorem

Definition: Let a be an integer and p be a prime, then: a^p \equiv a \pmod p. It can also be stated in the form: a^{p-1} \equiv 1 \pmod p.

RSA Algorithm

Key generation

  1. Choose large primes p and q.
  2. Calculate n = p\cdot q. Calculate \Phi(n) = (p-1)(q-1).
  3. Choose public key K_{pub}=e \in \{1,2,\cdots,\Phi(n)-1\} such that \gcd(e, \Phi(n)) = 1 (e and \Phi(n) are co-prime).
  4. Compute the private key K_{priv}=d such that d\cdot e \equiv 1\pmod {\Phi(n)} using the Extended Euclidean Algorithm. EEA: gcd(e, \Phi(n)) = 1 \Rightarrow gcd(e, \Phi(n)) = d\cdot e + t\cdot \Phi(n) \Rightarrow d\cdot e \equiv 1\pmod {\Phi(n)}.
  5. Output of the routine: 1. K_{pub}=(n,e), 2. K_{priv}=d

Remark 1

The gcd condition is necessary to ensure the modular inverse of e, which is d, is unique.

Remark 2

Eve have K_{pub} = (n, e), but not \Phi(n). In order to compute the private key d. He have to first compute \Phi(n). To compute \Phi(n), he need to compute the primie factorization of n, which is very hard to compute when n is very large, such as a 2048-bit integer. This ensure the security of RSA.


Given public key K_{pub} = (n, e) and the plain text message x \in Z_n = \{0, 1, \cdots, n-1\}, the encrypted y is computed by

y = ENC_{k_{pub}}(x) \equiv x^e\bmod n


Given private key K_{priv}=d and the cipher text y \in Z_n = \{0, 1, \cdots, n-1\}, the message can be decrypted as

x = DEC_{k_{priv}}(y) \equiv y^d\bmod n

Fast exponentiation


RSA one-way function, 1. encryption and decryption, 2. use n and e to compute d.