1) Modular Arithmetic

Modular arithmetic, also known as "clock arithmetic," is fundamental in almost all cryptosystems, including RSA, Diffie-Hellman, and elliptic curve cryptography (ECC).

• Definition: a ≡ b (mod n) if (a - b) is divisible by n
• Properties:
• Commutative: (a + b) mod n = (b + a) mod n
• Associative: (a + (b + c)) mod n = ((a + b) + c) mod n
• Multiplicative: (a × b) mod n = ((a mod n) × (b mod n)) mod n
• Example: 17 ≡ 5 (mod 12) because 17-5=12 is divisible by 12
• Application: RSA encryption computes c = m^e mod n where n = p×q

Python Example:

# Modular exponentiation for RSA
def mod_exp(base, exponent, modulus):
    result = 1
    base = base % modulus
    while exponent > 0:
        if exponent % 2 == 1:
            result = (result * base) % modulus
        exponent = exponent // 2
        base = (base * base) % modulus
    return result

# Example usage
m = 123
e = 17
n = 3233  # 61 * 53
c = mod_exp(m, e, n)
print("Ciphertext:", c)
    

2) Groups, Rings, and Fields

These algebraic structures provide the rules to perform operations safely in cryptosystems.

• Group: A set with a single operation satisfying closure, associativity, identity, and invertibility. Example: Integers modulo n under addition.
• Ring: A set with two operations (addition, multiplication) satisfying group properties for addition and distributivity. Example: integers mod n
• Field: A ring where every non-zero element has a multiplicative inverse. Example: GF(p), the field of integers modulo prime p

Real-Life Example: AES operates in GF(2^8), ensuring bytes behave predictably during encryption.

Python Code Example: finite field arithmetic:

# Addition and multiplication in GF(7)
p = 7

def gf_add(a, b):
    return (a + b) % p

def gf_mul(a, b):
    return (a * b) % p

print("3+5 mod 7 =", gf_add(3,5))
print("3*5 mod 7 =", gf_mul(3,5))
    

3) Finite Fields GF(2^n)

Finite fields of the form GF(2^n) are used in modern encryption (AES, ECC). They allow us to operate on binary data efficiently.

• Each element is a polynomial of degree < n with coefficients 0 or 1
• Addition: bitwise XOR
• Multiplication: polynomial multiplication modulo an irreducible polynomial
• Example: AES uses GF(2^8) with irreducible polynomial x^8 + x^4 + x^3 + x + 1

Python Example:

# Addition in GF(2^8)
def gf256_add(a, b):
    return a ^ b

# Multiplication (simplified)
def gf256_mul(a, b):
    p = 0
    for i in range(8):
        if b & 1:
            p ^= a
        hi_bit_set = a & 0x80
        a <<= 1
        if hi_bit_set:
            a ^= 0x11b  # AES irreducible polynomial
        b >>= 1
    return p & 0xFF

print("0x57 + 0x83 =", hex(gf256_add(0x57, 0x83)))
print("0x57 * 0x83 =", hex(gf256_mul(0x57, 0x83)))
    

4) Lattices

Lattices are grids of points in n-dimensional space. They are the basis of modern post-quantum cryptography.

• Definition: integer combinations of basis vectors
• Used in: Learning With Errors (LWE), Ring-LWE, NTRU encryption, Kyber KEM
• Security relies on hard problems: Shortest Vector Problem (SVP), Closest Vector Problem (CVP)
• Example in 2D: basis vectors (3,0), (1,2) generate all lattice points

Python Illustration:

import numpy as np

B = np.array([[3,1],[0,2]])  # Basis vectors
v = 4*B[0] + 5*B[1]          # Lattice point
print("Lattice point:", v)
    

5) Elliptic Curves

Elliptic curves are defined by y^2 = x^3 + ax + b over a field. They are used in ECC to provide strong security with small keys.

• Curve over prime field GF(p): y^2 mod p = x^3 + ax + b mod p
• Operations: point addition, doubling, scalar multiplication
• Used in: ECDSA, ECDH, EdDSA, TLS certificates
• Example curve: secp256k1 used in Bitcoin

Python Code Example:

class Point:
    def __init__(self, x, y, curve):
        self.x = x
        self.y = y
        self.curve = curve

def point_add(P, Q, a, p):
    if P.x == Q.x and P.y == Q.y:
        # Point doubling
        s = (3*P.x**2 + a) * pow(2*P.y, -1, p)
    else:
        s = (Q.y - P.y) * pow(Q.x - P.x, -1, p)
    x_r = (s**2 - P.x - Q.x) % p
    y_r = (s*(P.x - x_r) - P.y) % p
    return Point(x_r, y_r, P.curve)

# Real-life: this function underlies ECC-based Bitcoin keys and TLS keys
    

A) Calculation/Problem Solving (15 Questions)

1. Question 1: Compute 17^23 mod 43 using modular exponentiation.
   Answer:

   Step 1: Use repeated squaring:

   17^1 ≡ 17 mod 43
   17^2 ≡ 17*17 = 289 ≡ 289-43*6=289-258=31
   17^4 ≡ 31^2=961 ≡ 961-43*22=961-946=15
   17^8 ≡ 15^2=225 ≡ 225-43*5=225-215=10
   17^16 ≡ 10^2=100 ≡ 100-43*2=100-86=14
   
   Now combine: 17^23=17^16*17^4*17^2*17^1 ≡ 14*15*31*17
   Step2: Multiply sequentially modulo 43:
   14*15=210 ≡ 210-43*4=210-172=38
   38*31=1178 ≡ 1178-43*27=1178-1161=17
   17*17=289 ≡ 31 mod 43
    So, 17^23 mod 43 = 31
           

2. Question 2: Solve x in 5x ≡ 3 (mod 11)
   Answer:

   Step1: Find multiplicative inverse of 5 mod 11: 5*y ≡ 1 (mod11)

   Test y=9: 5*9=45 ≡ 1 (mod11), correct!

   Then x ≡ 3*9 ≡ 27 ≡ 5 (mod11)

   Solution: x = 5
3. Question 3: Compute LCM and GCD of 210 and 462.
   Answer:

   Prime factorization:

   • 210=2*3*5*7
   • 462=2*3*7*11

   GCD = product of common primes = 2*3*7=42

   LCM = product of all primes max powers = 2*3*5*7*11=2310

   GCD=42, LCM=2310
4. Question 4: Find all elements with multiplicative inverse in GF(7)
   Answer:

   Field GF(7) elements: {0,1,2,3,4,5,6}

   All non-zero elements have inverses:

   • 1*1=1
   • 2*4=8≡1
   • 3*5=15≡1
   • 6*6=36≡1
5. Question 5: AES GF(2^8) addition: compute 0x57 + 0x83
   Answer:

   Addition = XOR: 0x57 ^ 0x83 = 0xd4

6. Question 6: Compute lattice vector 4*b1 + 5*b2 with b1=(3,0), b2=(1,2)
   Answer:

   4*b1=(12,0), 5*b2=(5,10)

   Sum=(12+5,0+10)=(17,10)

7. Question 7: Elliptic curve point doubling on y^2=x^3+2x+3 mod 97 at P=(3,6)
   Answer:

   Slope s = (3*x^2 + a)/(2*y) mod 97
   s = (3*3^2 +2)/(2*6) = (3*9+2)/12 = (27+2)/12 =29/12
   Compute modular inverse of 12 mod97 = 12^-1 ≡ 89
   s=29*89=2581 ≡ 2581-97*26=2581-2522=59
   x_r = s^2 -2*x = 59^2-6=3481-6=3475 ≡ 3475-97*35=3475-3395=80
   y_r = s*(x - x_r)-y =59*(3-80)-6=59*(-77)-6=-4543-6=-4549 ≡ -4549+97*47= -4549+4559=10
   Point doubled: 2P=(80,10)
           

8. Question 8: Solve 2^x ≡ 3 mod 11
   Answer:

   Compute powers of 2 mod11:

   • 2^1=2
   • 2^2=4
   • 2^3=8
   • 2^4=16≡5
   • 2^5=10
   • 2^6=9
   • 2^7=7
   • 2^8=3

   So x=8

9. Question 9: Compute 123^456 mod 17 efficiently
   Answer:

   Use 123 mod17=4, then compute 4^456 mod17 using repeated squaring (exercise similar to Q1)

   Step-by-step: 4^1=4,4^2=16,4^4=1,4^8=1,...

   4^456 ≡ 1 mod17

10. Question 10: Find inverse of 7 mod 26
    Answer:

    Extended Euclidean Algorithm: 7*y ≡1 mod26

    Compute: 26=3*7+5,7=1*5+2,5=2*2+1 → backsolve → y=15

    7*15=105 ≡1 mod26
11. Question 11: Solve x^2+2x+3 ≡ 0 mod 5
    Answer:

    Check x=0,1,2,3,4:

    • x=1 →1+2+3=6≡1≠0
    • x=2 →4+4+3=11≡1
    • x=3 →9+6+3=18≡3
    • x=4 →16+8+3=27≡2

    No solution mod5

12. Question 12: Compute multiplicative inverse in GF(2^8) of 0x53 using AES irreducible poly
    Answer:

    Use Extended Euclidean Algorithm in GF(2^8) → inverse=0xca

13. Question 13: Compute 3^200 mod13
    Answer:

    3^1=3,3^2=9,3^4=9^2=81≡3, pattern repeats: 3,9,1,3,9,1...

    Cycle length=3, 200 mod3=2 → result=9

14. Question 14: Solve discrete log 5^x ≡ 8 mod23
    Answer:

    Compute 5^1=5,5^2=2,5^3=10,5^4=4,5^5=20,5^6=8

    x=6

15. Question 15: Compute lattice point sum: 3*(1,2,3)+2*(0,1,4)
    Answer:

    3*(1,2,3)=(3,6,9), 2*(0,1,4)=(0,2,8)

    Sum=(3+0,6+2,9+8)=(3,8,17)

B) Coding Problems (5 Questions)

1. Q16: Write Python function for modular exponentiation.
   

   def mod_exp(base, exp, mod):
       result = 1
       base %= mod
       while exp>0:
           if exp%2==1:
               result = (result*base)%mod
           exp//=2
           base=(base*base)%mod
       return result
   print(mod_exp(17,23,43))  # Output 31
           

2. Q17: Python code to compute multiplicative inverse modulo n.
   

   def mod_inv(a,n):
       for x in range(1,n):
           if (a*x)%n==1:
               return x
   print(mod_inv(7,26))  # Output 15
           

3. Q18: Python code for addition/multiplication in GF(2^8)
   

   def gf_add(a,b): return a^b
   def gf_mul(a,b):
       p=0
       for i in range(8):
           if b&1: p^=a
           hi=a&0x80
           a<<=1
           if hi: a^=0x11b
           b>>=1
       return p&0xFF
   print(hex(gf_mul(0x57,0x83)))
           

4. Q19: Python code for lattice point generation
   

   import numpy as np
   B=np.array([[3,0],[1,2]])
   def lattice_point(a,b):
       return a*B[0]+b*B[1]
   print(lattice_point(4,5))  # Output [17,10]
           

5. Q20: Python code for ECC point addition modulo p
   

   def point_add(P,Q,a,p):
       if P==Q:
           s=(3*P[0]**2 + a)*pow(2*P[1],-1,p)
       else:
           s=(Q[1]-P[1])*pow(Q[0]-P[0],-1,p)
       x_r=(s**2-P[0]-Q[0])%p
       y_r=(s*(P[0]-x_r)-P[1])%p
       return (x_r,y_r)
   print(point_add((3,6),(3,6),2,97))  # Output (80,10)
           

C) Theory / Conceptual Questions (10 Questions)

1. Q21: Explain why modular arithmetic is essential in RSA and ECC.
   A21: It ensures numbers wrap around, enabling finite sets for secure key generation and preventing overflow.
2. Q22: Define a group, ring, and field. Give cryptography examples.
   A22: Group=closure+assoc+identity+inverse; Ring=group+distributive multiplication; Field=Ring with multiplicative inverses. Examples: GF(p), integers mod n, AES field GF(2^8).
3. Q23: Why finite fields GF(2^n) are used in AES?
   A23: Because bytes can be treated as polynomials with predictable arithmetic and invertible elements for S-boxes.
4. Q24: Explain concept of elliptic curve point addition and scalar multiplication.
   A24: Adding points follows curve geometry rules; scalar multiplication repeatedly adds points. Basis of ECC key exchange and signatures.
5. Q25: How lattices provide post-quantum security?
   A25: Hard problems like SVP/CVP resist quantum algorithms; used in LWE, Kyber.
6. Q26: Explain the difference between discrete logarithm problem and integer factorization problem.
   A26: DLP: find x such that g^x=h mod p; IF: find primes p,q from n=p*q. Both are one-way functions in crypto.
7. Q27: Describe multiplicative inverse and how it is computed in modular arithmetic.
   A27: x is inverse of a if a*x ≡1 mod n. Computed via extended Euclidean algorithm or trial multiplication.
8. Q28: Explain why small AES operations use GF(2^8) instead of integers.
   A28: Ensures predictable, invertible byte operations; prevents overflow and simplifies hardware/software implementation.
9. Q29: Describe the purpose of irreducible polynomials in GF(2^n).
   A29: They act like “modulus” in polynomials, ensuring every non-zero element has an inverse, essential for AES and ECC.
10. Q30: Explain why repeated squaring is efficient for modular exponentiation.
    A30: Reduces number of multiplications from O(n) to O(log n); essential in RSA, DH for large exponents.