Zen

Translation

The security of this protocol relies on the difficulty of computing discrete logarithms, i.e. from the knowledge of :math:`A` (resp. :math:`B`), it is very difficult to extract :math:`\log(A)=\log(g^{a} \mod p)=a` (resp. :math:`\log(B)=\log(g^{b} \mod p)=b`).
0/2590 · 259

Sign in to save translations.

English French Actions
his/her public key
 
a hash of the entire file signed with Ted's private key
 
Then, knowing Ted's public key, anyone can verify the validity of a certificate. When a user sends his/her public key, he/she must also attach the certificate to prove the link between his/her identity and the public key. In practice, certificates are more complex than this. Certificates will often be used to authenticate the server and sometimes to authenticate the client.
 
A possible protocol could then be the following. Alice sends :math:`Cert(Alice_{pub},Ted)`. Bob replies with a random nonce.
 
Until now, we have only discussed the authentication problem. This is an important but not sufficient step to have a secure communication between two users through an insecure network. To securely exchange information, Alice and Bob need to both :
 
mutually authenticate each other
 
agree on a way to encrypt the messages that they will exchange
 
Let us first explore how this could be realized by using public-key cryptography. We assume that Alice and Bob have both a public-private key pair and the corresponding certificates signed by a trusted third party : Ted.
 
A possible protocol would be the following. Alice sends :math:`Cert(Alice_{pub},Ted)`. This certificate provides Alice's identity and her public key. Bob replies with the certificate containing his own public key : :math:`Cert(Bob_{pub},Ted)`. At this point, they both know the other public key and could use it to send encrypted messages. Alice would send :math:`E_p(Bob_{pub},M1)` and Bob would send :math:`E_p(Alice_{pub},M2)`. In practice, using public key encryption techniques to encrypt a large number of messages is inefficient because these cryptosystems require a large number of computations. It is more efficient to use secret key cryptosystems for most of the data and only use a public key cryptosystem to encrypt the random secret keys that will be used by the secret key encryption scheme.
 
Key exchange
 
When users want to communicate securely through a network, they need to exchange information such as the keys that will be used by an encryption algorithm even in the presence of an eavesdropper. The most widely used algorithm that allows two users to safely exchange an integer in the presence of an eavesdropper is the one proposed by Diffie and Hellman [DH1976]_. It operates with (large) integers. Two of them are public, the modulus, p, which is prime and the base, g, which must be a primitive root of p. The communicating users select a random integer, :math:`a` for Alice and :math:`b` for Bob. The exchange starts as :
 
Alice selects a random integer, :math:`a` and sends :math:`A=g^{a} \mod p` to Bob
 
Bob selects a random integer, :math:`b` and sends :math:`B=g^{b} \mod p` to Alice
 
From her knowledge of :math:`a` and :math:`B`, Alice can compute :math:`Secret=B^{a} \mod p= (g^{b} \mod p) ^{a} \mod p=g^{a \times b} \mod p`
 
From is knowledge of :math:`b` and :math:`A`, Bob can compute :math:`Secret=A^{b} \mod p=(g^{a} \mod p) ^{b} \mod p=g^{a \times b} \mod p`
 
The security of this protocol relies on the difficulty of computing discrete logarithms, i.e. from the knowledge of :math:`A` (resp. :math:`B`), it is very difficult to extract :math:`\log(A)=\log(g^{a} \mod p)=a` (resp. :math:`\log(B)=\log(g^{b} \mod p)=b`).
 
An example of the utilization of the Diffie-Hellman key exchange is shown below. Before starting the exchange, Alice and Bob agree on a modulus (:math:`p=23`) and a base (:math:`g=5`). These two numbers are public. They are typically part of the standard that defines the protocol that uses the key exchange.
 
Alice chooses a secret integer : :math:`a=8` and sends :math:`A= g^{a} \mod p= 5^{8} \mod 23=16` to Bob
 
Bob chooses a secret integer : :math:`b=13` and sends :math:`B= g^{b} \mod p=5^{13} \mod 23=21` to Alice
 
Alice computes :math:`S_{A}=B^{a} \mod p= 21^{8} \mod 23=3`
 
Bob computes :math:`S_{B}=A^{b} \mod p= 16^{13} \mod 23=3`
 
Alice and Bob have agreed on the secret information :math:`3` without having sent it explicitly through the network. If the integers used are large enough and have good properties, then even Eve who can capture all the messages sent by Alice and Bob cannot recover the secret key that they have exchanged. There is no formal proof of the security of the algorithm, but mathematicians have tried to solve similar problems with integers during centuries without finding an efficient algorithm. As long as the integers that are used are random and large enough, the only possible attack for Eve is to test all possible integers that could have been chosen by Alice and Bob. This is computationally very expensive. This algorithm is widely used in security protocols to agree on a secret key.
 
Unfortunately, the Diffie-Hellman key exchange alone cannot cope with man-in-the middle attacks. Consider Mallory who sits in the middle between Alice and Bob and can easily capture and modify their messages. The modulus and the base are public. They are thus known by Mallory as well. He could then operate as follows :
 
Alice chooses a secret integer and sends :math:`A= g^{a} \mod p` to Mallory
 
Mallory generates a secret integer, :math:`m` and sends :math:`M=g^{m} \mod p` to Bob
 
Bob chooses a secret integer and sends :math:`B=g^{b} \mod p` to Mallory
 
Mallory computes :math:`S_{A}=A^{m} \mod p` and :math:`S_{B}=B^{m} \mod p`
 
Alice computes :math:`S_{A}=M^{a} \mod p` and uses this key to communicate with Mallory (acting as Bob)
 
Bob computes :math:`S_{B}=M^{b} \mod p` and uses this key to communicate with Mallory (acting as Alice)
 
When Alice sends a message, she encrypts it with :math:`S_{A}`. Mallory decrypts it with :math:`S_{A}` and encrypts the plaintext with :math:`S_{B}`. When Bob receives the message, he can decrypt it by using :math:`S_{B}`.
 
To safely use the Diffie-Hellman key exchange, Alice and Bob must use an `authenticated` exchange. Some of the information sent by Alice or Bob must be signed with a public key known by the other user. In practice, it is often important for Alice to authenticate Bob. If Bob has a certificated signed by Ted, the authenticated key exchange could be organized as follows.
 

Loading…

User avatar None

Source string added
The security of this protocol relies on the difficulty of computing discrete logarithms, i.e. from the knowledge of :math:`A` (resp. :math:`B`), it is very difficult to extract :math:`\log(A)=\log(g^{a} \mod p)=a` (resp. :math:`\log(B)=\log(g^{b} \mod p)=b`).
4 years ago
Browse all string changes

Glossary

English French
No related strings found in the glossary.

30244 String information

Source string location
../../principles/security.rst:940
String age
4 years ago
Last updated
a month ago
Source string age
4 years ago
Translation file
locale/fr/LC_MESSAGES/principles/security.po, string 85