Functions! I’m sure you have heard this concept in many ways: math,
programming, economics, etc. And they all can be reduced to the same
basic thing: something that takes some inputs and produces some outputs.
Math is the case here, however, there is a lot to add to that short
definition, specially when we apply it to computer security, because
despite you might be unaware, your security totally depend on a special
kind of functions called Trapdoors. ^[1] Let’s
talk about trapdoor functions and how they save you from “letting the
cat out”.

When we talk about inputs producing an output we usually talk about the
reverse process: given the outputs deduce the inputs, this is really
useful in many applications…​ but not in security! knowing an input
from an output is a serious problem, you will see why.

A Trapdoor is essentially something taking an input and producing an
output, but it is extremely difficult to do the reverse process, this is
because to do so you need to know a “secret” called a private key and
you have to be the luckiest guy in all universes to guess it or to guess
the input.

Suppose:

A Trapdoor is a function that encrypts with the properties:

Now, Trapdoors are not the same as the well known hash functions, hash
functions are one-way functions as well, but they are not reversible by
any means, whereas Trapdoors are reversible with the key. This is what
makes them fundamental for Encryption of shared information.

Your lifesaving, precious data is always put in a Trapdoor, encrypted
and transmitted and no one (except the possessor of the secret and the
luckiest guy in all universes) can figure out the data.

Symmetric and Asymmetric Encryption

When two ends have to exchange sensitive data, they must agree on the
key they both use, this is called Symmetric Encryption
^[2] where the same key is used to encrypt and to
decrypt. This key has to be transmitted first for agreement before any
other communication, but how can they prevent a third party sniffs and
retrieve the key? they use a type of Encryption called Asymmetric Encryption: It encrypts the data with one public key and decrypts it
with a different private key

The data is encrypted with

And decrypted with

This Encryption is slow and it’s not commonly used in data
transmission. It’s only used between parties to agree on a shared key
that they use for Symmetric Encryption which is the one used for large
data exchange as it’s faster. The shared key for Symmetric Encryption
is transmitted over Asymmetric Encryption so no attacker can retrieve
this symmetric key.

RSA Encryption

Rivest, Shamir, Adleman, also know as RSA algorithm
^[3] is the most common algorithm for Asymmetric Encryption and it’s based on a Trapdoor function called modular
exponentiation :

In this case knowing P from E is impossible, you need to know a
secret K_S in order to compute it.

RSA algorithm uses prime number arithmetics and modular exponentiation
to encrypt a message, the algorithm can be summarized like this :

1. Choose two prime numbers p and q.

2. Compute n = pq.

3. Compute Euler’s function ϕ = (p – 1)(q – 1).
   ^[5]

4. Choose a number e smaller and coprime
   ^[6] to ϕ.

5. Choose a number d such that (ed – 1) mod ϕ = 0,
   This is know as the modular multiplicative
   inverse,^[7] in other words, ed – 1
   must be divisible entirely by ϕ.

6. (e,n) are the public key whereas (s,n) are
   the private key.

A message m is encrypted into c by

And decrypted by

Thus, anyone can know the public key value e to encrypt but not
the private key value d used to decrypt. What about n ?
could not they use it to come up with d ? Yes, they can, they will
just take tenths of years to do it as n is chosen to be a very big
number, so breaking it into the prime factors p, q used to
get e and therefore d, would take long enough that an
attacker cannot crack the key.

AES Encryption

AES (Advanced Encryption System) ^[4] algorithm,
is usually the chosen one for Symmetric Encryption. This algorithm is
rather procedural than hard mathematical formula computation, it
basically encrypts a table of data in four steps:

1. SubBytes : Each value in a table is substituted by another using a
   table.

2. ShiftRows : Rows of the table are shifted by some offset.

3. MixColumns : Columns are mixed by a matrix operation.

4. AddRoundKey : The public key is performed over the table with an
   XOR operation.

All operations performed are reversible and they are made in order to
eliminate or diffuse any possible pattern or relationship of the
ciphered message to the original one and to the key that might hint an
attack.

Conclusion

You can be sure your data is very well protected and that the
communication won’t be disclosed to any attacker thanks to a Trapdoor,
of course, as computing power continues to develop, we might need to
create new traps, but now the assurance of your privacy on communication
is really high, so every time you browse your social networks, bank
accounts, etc; remember there is a Trapdoor that won’t let any cat
out.

References

1. Trapdoor
   functions

2. Symmetric and Asymmetric
Encryption

3. RSA
   Explained

4. AES
   Explained

5. Euler’s
   function

6. Coprime number

7. Modular multiplicative
   inverse

*** This is a Security Bloggers Network syndicated blog from Fluid Attacks RSS Feed authored by Sebastian Villalobos. Read the original post at: https://fluidattacks.com/blog/trapdoors/