FIT1093 Chap.5 Number Theory Behind Public-Key Cryptography
Number Theory Behind Public-Key Cryptography
Week 4 explains why public-key cryptography is needed and supplies the number theory that makes it work. Symmetric encryption requires both parties to share a secret key in advance, and distributing that key safely over an untrusted network is the key distribution problem.
Public-key encryption removes it: each user generates a key pair, publishes the public key for encryption and keeps the private key for decryption, so the system needs three algorithms, key generation, encryption and decryption.
The idea rests on trapdoor one-way functions, which are easy to compute, impractical to reverse, and easy to reverse for whoever holds a secret. Two such locks appear in the unit.
Multiplying two large primes is easy, but factoring the product is hard, which supports RSA. Raising a base to a power modulo a prime is easy, but recovering the exponent is the discrete logarithm problem, which supports Diffie-Hellman and ElGamal.
The workshop then drills the arithmetic behind these locks.
Students revise primes, divisors, greatest common divisors and relatively prime pairs, then modular addition, subtraction and multiplication, where m mod p is the remainder after division by p. A modular inverse exists only when the GCD of the number and the modulus is 1, and modular division is multiplication by an inverse.
Fast exponentiation by repeated squaring needs only about twice the number of bits of the exponent in multiplications, so honest users can compute huge powers quickly while attackers face an infeasible discrete logarithm. The workshop finishes by comparing bases: modulo 13, the base 2 produces all twelve possible public keys while 4 produces only six, which makes 2 the better choice.
What this chapter covers
- 01
The key distribution problem and the public-key idea
- 02
Key generation, encryption and decryption algorithms
- 03
Trapdoor one-way functions: factoring and discrete logarithms
- 04
Primes, divisors, GCDs and relatively prime pairs
- 05
Modular inverses and modular division
- 06
Square-and-multiply exponentiation
- 07
Choosing a base that generates many public keys
Worked example · free
Find an inverse modulo 23 and a power modulo 13
- 223 is prime and does not divide 5, so an inverse exists. Testing multiples of 5: 5 × 14 = 70 = 3 × 23 + 1, so 5 inverse mod 23 is 14.
- 2Square 6 modulo 13: 6, then 36 ≡ 10, then 100 ≡ 9, then 81 ≡ 3, giving the powers for exponents 1, 2, 4 and 8.
- 2Write 11 = 8 + 2 + 1 and multiply the matching powers: 3 × 10 × 6 = 180, and 180 = 13 × 13 + 11.
Key terms
- Key Distribution Problem
- The difficulty of getting a shared secret key to both parties over a channel an attacker can observe or alter.
- Trapdoor Function
- A function that is easy to compute and hard to invert, except for someone holding a secret piece of information.
- Greatest Common Divisor
- The largest integer that divides two given integers exactly; a GCD of 1 means the integers are relatively prime.
- Modular Inverse
- A number that multiplies with a given number to leave remainder 1 modulo n, existing only when the two are relatively prime.
- Repeated Squaring
- A fast exponentiation method that squares the base repeatedly and multiplies only the powers matching the 1 bits of the exponent.
- Integer Factorisation Problem
- The task of finding the prime factors p and q of a large product n, believed infeasible for well chosen large primes.
Number Theory Behind Public-Key Cryptography FAQ
Why do we need public-key encryption if AES is secure?
AES needs both sides to share a secret key first. Public-key encryption lets anyone encrypt with a published key while only the owner can decrypt, which solves the problem of distributing keys over an untrusted network.
When does a modular inverse not exist?
When the number and the modulus share a factor greater than 1. Workshop 4 shows 3 has no inverse modulo 12, because multiples of 3 only ever leave remainders 3, 6, 9 and 0, never 1.
How do I compute large modular powers by hand?
Square the base repeatedly, reducing modulo n each time, to get the powers for 1, 2, 4, 8 and so on. Then write the exponent in binary and multiply together only the powers whose bit is 1.
Why is publishing the public key safe in discrete-log systems?
Recovering the private exponent from the public value is the discrete logarithm problem, which is computationally infeasible for large primes, while computing the public value from the private key stays fast through repeated squaring.
Which base is better for discrete-log cryptography?
One whose powers produce as many different values as possible. Modulo 13, the workshop shows base 2 produces twelve distinct public keys and base 4 only six, so base 2 gives an attacker more possibilities to search.
Assessment move
Because the in-class test allows no calculator, this chapter is mainly practice. Set yourself ten small problems each session: a GCD by prime factorisation, two inverses by systematic search, one modular division, and one power by repeated squaring, and check each answer by multiplying back or reversing the step.
Keep a short list of the small squares and products modulo a few primes such as 11, 13, 17, 23 and 29, since workshop numbers tend to stay in that range. Learn to state the two hard problems in one sentence each and to say which algorithm depends on which.
Finally, practise explaining why a proposed scheme is insecure when the attacker's computation is as easy as the user's, since that reasoning appears in the sample test's design question.
Working through Number Theory Behind Public-Key Cryptography in FIT1093? Sia is AskSia’s AI Cybersecurity tutor — ask any FIT1093 Number Theory Behind Public-Key Cryptography question and get a clear, step-by-step explanation grounded in how FIT1093 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
