Generating keys

End-to-end criptography

In the first part presented, everyone who knew the keyword would be able to decipher the coded expression. A new problem then arises – how to send the code word, or key, safely? This issue is intimately associated with modern cryptography and some of the solutions are still used today in bank passwords, network encryption, etc. Key exchanges, in general, are performed by protocols that somehow generate numeric codes that can, in direct examples, be associated with letters in different ways, for example, via ASCII code or position in the alphabet.

Let us use perhaps the first symmetric key exchange method proposed by Whitfield Diffie and Martin Hellman in 1976. In this ingenious but simple process, two people can share keywords without ever transmitting them directly. This process takes place from a set of public and private numbers.

Let’s explain the method through an activity, for example, in class.

• Two students are chosen to participate in the activity, for example, Enzo (E) and Valentina (V).
• Define-se uma tabela de conversão de números para letras, neste caso, 0 – a, 1 – b, 2 – c, \cdots, 25-z
• The duo defines two numbers that will be public, for example, a = 17 and m = 342. (Note that the condition a < m is required, and the larger the numbers, the greater the possibility of large and therefore less decipherable keys. The choice will naturally be made according to the computational tools available – or not – in the presentation.)
• Each one chooses, for himself, a number (secret key), let’s assume that Enzo and Valen-tina’s choices are, respectively \gamma_E=11 e \gamma_V=13.
• Enzo calculates 0<\lambda_E<m congruent to a^{\gamma_E}\mod m, in other words, the remainder of the integer division a^{\gamma_E}\div m is sent to Valentina (confidentiality is not necessary). Valentina does the same starting from a^{\gamma_E}\mod m. With the proposed numbers, we would have \lambda_E=251 e \lambda_V=35.
• The secret key \kappa between the two would be calculated by Enzo and Valentina as follows: \kappa=\lambda_V^{\gamma_E}=\lambda_E^{\gamma_V}\mod m, with 0<\kappa<m. With the given numbers, we would have \kappa=161 and, in a simplified manner, we could use the keyword “bgb”.

Why does it work?

The secret of the method lies in the fact that, assuming a,\lambda and m are known in

a^\gamma=\lambda \mod m,

solving the above equation, i.e., finding the value of \gamma is computationally very expensive, especially if the known numbers are sufficiently large. That said, if the transmission of \lambda is intercepted, it will be practically impossible to find the value of \gamma and consequently discover the secret key.

On the other hand, assuming that person 1 (P1) has \gamma_1, as their secret key, they will transmit the number a^\gamma_1\mod m and analogously, they will receive the number a^\gamma_2\mod m.

Based on the received number, P1 will perform the calculation (a^\gamma_2)^{\gamma_ 1}\mod m which, due to the properties of exponentiation and congruence modulo m, will have the same value as the calculation to be performed by P2, namely, a^\gamma_1)^{\gamma_ 2}\mod m. In this way, both individuals will obtain the same number without ever knowing each other’s secret key, but they will be able to exchange codes from end to end.

Shall we implement the method in the application below?

1. Define a public key, meaning the values of a and m.
2. Each participant, on different computers, chooses their Private Key.
3. Using the Private Key \gamma, the application calculates a^\gamma\mod m and generates the Transfer Number.
4. This number must be passed from one participant to the other using any means (WhatsApp, piece of paper, shouting, etc).
5. In possession of the number (Person 2’s Key), each participant writes it below the Received section, and the application will generate, if there hasn’t been any error, the exact same Numeric Key and consequently the same keyword.

There you go! With the generated keyword (code), participants can exchange encrypted messages.

To make things easier, below is the application for encoding-decoding encrypted words. Enjoy!