Cryptography

Exercise 2.1. (Modular Multiplication)

Use the following property of modular multiplication

\[\begin{equation*} (a ⋅ b) \text{ mod } p = (a \text{ mod } p ⋅ b \text{ mod } p) \text{ mod } p, \end{equation*}\]

to show that \((n \text{ mod } p)a \text{ mod } p = na \text{ mod } p\). (Hint: apply an induction argument).

Solution

Step 1

(1)\[\begin{equation} (a\ast b)\text{ mod }p=(a\text{ mod }p\ast b\text{ mod }p)\text{ mod }p? \label{modular_mult} \end{equation}\]

For all \(a\) and \(b\), there exists integers \(\left\{ a_{p},b_{p}\right\} \) and remainders \(\left\{ r_{a},r_{b}\right\} \) such that

\[\begin{eqnarray*} a &=&a_{p}p+r_{a}, \\ b &=&b_{p}p+r_{b}. \end{eqnarray*}\]

Hence

\[\begin{eqnarray*} ab &=&\left( a_{p}p+r_{a}\right) \left( b_{p}p+r_{b}\right) \\ &=&p\left( a_{p}b_{p}p+r_{b}a_{p}+r_{a}b_{p}\right) +r_{a}r_{b}. \end{eqnarray*}\]

Taking the modulo of this expression, we find that

(2)\[\begin{equation} (ab)\text{ mod }p=\left( r_{a}r_{b}\right) \text{ mod }p. \label{modular_mult_2} \end{equation}\]

Let’s check that the right-hand side of \(\left( 1\right) \) has a similar value. First notice that

\[\begin{eqnarray*} a\text{ mod }p\ast b\text{ mod }p=r_{a}r_{b}, \end{eqnarray*}\]

thus

\[\begin{eqnarray*} \left( a\text{ mod }p\ast b\text{ mod }p\right) \text{ mod }p=\left( r_{a}r_{b}\right) \text{ mod }p \end{eqnarray*}\]

which is indeed identical to \(\left( 2\right) .\)

Step 2:

Now let’s applying this property inductively. First assume that

\[\begin{eqnarray*} H:a^{n}\text{ mod }p=\left( a\text{ mod }p\right) ^{n}\text{ mod }p, \end{eqnarray*}\]

then we have

\[\begin{eqnarray*} a^{n+1}\text{ mod }p &=&\left( a^{n}\ast a\right) \text{ mod }p \\ &=&\left( a^{n}\text{ mod }p\ast a\text{ mod }p\right) \text{ mod }p \\ &=&\left( \left( a\text{ mod }p\right) ^{n}\ast a\text{ mod }p\right) \text{ mod }p \\ &=&\left( a\text{ mod }p\right) ^{n+1}\text{ mod }p. \end{eqnarray*}\]

The first equality follows from \(\left( 1\right) \), while the second equality follows from our induction hypothesis \(H\).

Applied to secret sharing, the equality above yields the final result

\[\begin{eqnarray*} s &=&\left( g^{b}\text{ mod }p\right) ^{a}\text{ mod }p \\ &=&g^{ba}\text{ mod }p \\ &=&\left( g^{a}\text{ mod }p\right) ^{b}\text{ mod }p \\ &=&s^{\prime }. \end{eqnarray*}\]

Exercise 2.2.

Use Euler’s Totient Theorem to show that the RSA protocol delivers consistent encryption and decryption.

Hint: You need to prove that \(m =(m^{KB} \text{ mod } nB)^{ kB} \text{ mod } nB\).

Solution

Let’s first recap a series of useful results for our protocol:

1. Euler’s totient function: \(\varphi \left( n\right) \) counts the positive integers up to \(n\) that are relatively prime to \(n\), where relative primes \(n^{\prime }\) are such that \(\gcd (n,n^{\prime })=1.\)

2. Fermat’s little theorem:

\[\begin{eqnarray*} a^{p} &=&a\ (\text{ mod }p),\ \text{for all }a\text{ and all prime }p; \\ a^{p-1} &=&1\ (\text{ mod }p),\ \text{if }a\text{ and }p\ \text{are relative primes.} \end{eqnarray*}\]

3. Euler’s theorem:

\[\begin{eqnarray*} a^{\varphi \left( n\right) }=1\ (\text{ mod }n),\ \text{if }a\text{ and }n\ \text{are relative primes.} \end{eqnarray*}\]

Application to RSA.

Hypothesis:

\[\begin{eqnarray*} n &=&pq, \\ \gcd (K,\varphi \left( n\right) ) &=&1, \\ kK &=&1(\text{ mod }\varphi \left( n\right) ). \end{eqnarray*}\]

Note that the last two conditions are consistent. Assume that the last one holds, then there exists a \(\lambda \ \)such that

\[\begin{eqnarray*} kK=\lambda \varphi \left( n\right) +1\Rightarrow kK-\lambda \varphi \left( n\right) =1. \end{eqnarray*}\]

Hence if there a exists an integer \(d\) that divides \(K\) and \(\varphi \left( n\right) ,\) it must also divide \(kK-\lambda \varphi \left( n\right) \). Thus \(d\) should divide \(1,\) which implies that \(d=1.\) It follows that

\[\begin{eqnarray*} kK=1(\text{ mod }\varphi \left( n\right) )\Rightarrow \gcd (K,\varphi \left( n\right) )=1. \end{eqnarray*}\]

Step 1. Encryption:

\[\begin{eqnarray*} C=E(M;K)=M^{K}\text{ mod }n. \end{eqnarray*}\]

Step 2. Decryption:

\[\begin{eqnarray*} D(C;k) &=&C^{k}\text{ mod }n \\ &=&\left( M^{K}\right) ^{k}\text{ mod }n \\ &=&M^{\lambda \varphi \left( n\right) +1}\text{ mod }n \\ &=&\left( M^{\lambda \varphi \left( n\right) }\right) M\text{ mod }n \\ &=&\left( M^{\varphi \left( n\right) }\text{ mod }n\right) ^{\lambda }M\text{ mod }n \\ (by\ Euler^{\prime }s\ Theorem) &=&1^{\lambda }M\text{ mod }n \\ &=&M. \end{eqnarray*}\]

So the decryption algorithm returns the original message.

Note that Euler’s theorem holds solely if \(M\) and \(n\) are relative primes. In practice, these are huge numbers, so concerns is not likely to be relevant.

Exercise 2.3.

Describe how the RSA protocol can be used to digitally sign a document.

Solution

1. Use RSA to generate a public-private key pair.

2. You can hash the message \(m\) to generate a message digest. Let’s denote this hash by \(H(m)\).

3. Signing the Document: Encrypts the hash \(H(m)\) using your private key \(k\). The encryption is done computing \(S = H(m)^k \mod n\), generating the signature \(S\). Attach the digital signature \( S\) to the document.

4. Verifying the Signature: The receiver\verifier calculates the hash of the document using the same hash function. Then the verifier decrypts the signature using the signer’s public key \(K\) by computing \( S^K \mod n \), which should yield the original hash \(H(m)\).

Exercise 2.4.

Write a script in Python that implements RSA encryption/decryption.

Solution

Below is a draft of the code. You have to complete its two commented sections starting with ‘#Your code goes here’ to make it work.

p= 23
q= 17
print("Choosen primes:\np=" + str(p) + ", q=" + str(q) + "\n")
n=p*q
print("n = p * q = " + str(n) + "\n")
phi=(p-1)*(q-1)
print("Euler's function (totient) [phi(n)]: " + str(phi) + "\n")
def gcd(a, b):
    while b != 0:
     # Your code goes here
     # Write procedure to compute greatest common denominator gcd
       c = a % b
       a = b
       b = c
    return a
def modinv(a, m):
    for x in range(1, m):
        # Your code goes here
        # Find modular inverse
        if (a * x) % m == 1:
            return x
    return None
def coprimes(a):
    l = []
    for x in range(2, a):
        if gcd(a, x) == 1 and modinv(x,phi) != None:
            l.append(x)
    for x in l:
        if x == modinv(x,phi):
            l.remove(x)
    return l


print("Choose an e from a below coprimes array:\n")
print(str(coprimes(phi)) + "\n")
e= 41
print("You chose e = " + str(e))
d=modinv(e,phi)
print("\nYour public key is a pair of numbers (e=" + str(e) + ", n=" + str(n) + ").\n")
print("Your private key is a pair of numbers (d=" + str(d) + ", n=" + str(n) + ").\n")


def encrypt_block(m):
    c = modinv(m**e, n)
    if c == None: print('No modular multiplicative inverse for block ' + str(m) + '.')
    return c
def decrypt_block(c):
    m = modinv(c**d, n)
    if m == None: print('No modular multiplicative inverse for block ' + str(c) + '.')
    return m
def encrypt_string(s):
    return ''.join([chr(encrypt_block(ord(x))) for x in list(s)])
def decrypt_string(s):
    return ''.join([chr(decrypt_block(ord(x))) for x in list(s)])

    
s = "Hello, World!"
print("\nPlain message: " + s + "\n")

enc = encrypt_string(s)
print("Encrypted message: " + enc + "\n")

dec = decrypt_string(s)
print("Decrypted message: " + dec + "\n")