eonootz

Trapdoor function

July 22, 2025

Modern asymmetric encryption is based on two mathematical hard problems to solve: Prime Factorization and the Discrete Logarithm Problem.

Let’s talk about prime factorization, and it’s role public / private key encryption.

It just seems so unnatural to lock something up with a key but to be unable to unlock it with the same key. To complicate things, you can only unlock it with a different key. That is the essence of RSA

To be able to do this, we need something called a trapdoor function, meaning you can calculate it in one direction, but if you want to trace back your steps it’s impossible without the second key.

It’s a mathematical construct, a (sort of) one way function, easy in one direction, computationally expensive to reverse.

Going through the steps, we will use small numbers, in practice the numbers used are quite large. For 2048 bit RSA implementations p and q are 1024 bits long ~300 digits

Choose Two Prime Numbers

p=5p = 5 , q=11q = 11

Remember, these prime numbers are of equal size, each 300 digits long

Compute nn and ϕ(n)\phi(n)

n=pq=511=55n = p \cdot q = 5 \cdot 11 = 55

ϕ(n)=(p1)(q1)=410=40\phi(n) = (p - 1)(q - 1) = 4 \cdot 10 = 40

ϕ\phi(n) returns the number of relatively primes up to n, meaning all the numbers from 1 to n, that n does not divide. The formula is (p1)(q1),(p - 1)(q - 1), only when p,qp,q are primes.

Choose Public Exponent ee

Choose ee such that 1<e<ϕ(n)1 < e < \phi(n) and gcd(e,ϕ(n))=1\gcd(e, \phi(n)) = 1

Let’s pick e=3e = 3

Compute Private Key dd

We need dd such that:

ed1(modϕ(n))e \cdot d \equiv 1 \pmod{\phi(n)}

3d1(mod40)d=273 \cdot d \equiv 1 \pmod{40} \Rightarrow d=27

The private key is the modular inverse

Modular arithmetic is another key point in encryption, because without the mod we cannot reverse the encryption operation


Keys

Public Key: (e=3,n=55e = 3, n = 55)

Private Key: (d=27,n=55d = 27, n = 55)


Encrypt a Message

The encryption formula to create the ciphertext:

c=mec = m^{e}, c=memodnc = m^e \bmod n, c=73mod55c = 7^3 \bmod 55, c=343mod55c = 343 \bmod 55, c=13c = 13

So the encrypted text is 13.


Decrypting the Ciphertext

m=cdmodnm = c^d \bmod n, m=1327mod55m = 13^{27} \bmod 55, m=7m = 7

So the original message is: 7


Getting back to the article’s spoiler, the above function has proven to be very useful, you can sign with the private key and anyone with the public key can decrypt, which provides proof that the author is genuine. Or you can sign the message with the public key, so that only the owner of the private key can decypher.


Articol în română