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
,
Remember, these prime numbers are of equal size, each 300 digits long
Compute and
(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 only when are primes.
Choose Public Exponent
Choose such that and
Let’s pick
Compute Private Key
We need such that:
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: ()
Private Key: ()
Encrypt a Message
The encryption formula to create the ciphertext:
, , , ,
So the encrypted text is 13.
Decrypting the Ciphertext
, ,
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ă