r"""
Diffie–Hellman Key exchange Scheme.
The Diffie–Hellman Key exchange Scheme. This scheme was originally described in [DiffieHellman] and the `Wikipedia article ` on this scheme.
REFERENCES:
.. [J. H. Ellis], J. H. Ellis, *The possibility of Non-Secret digital encryption*, 1996.
.. [Dieter Gollmann (2006)] Dieter Gollmann. *Computer Security *, Second Edition West Sussex, England: John Wiley & Sons
AUTHORS:
- Tevin Joseph K.O.
"""
###########################################################################
# Copyright (c) 2011
# TEVIN JOSEPH K.O.
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU General Public License for more details.
#
# http://www.gnu.org/licenses/
###########################################################################
from sage.crypto.cryptosystem import PublicKeyCryptosystem
from sage.rings.arith import power_mod
from sage.rings.finite_rings.integer_mod import Mod as mod
from sage.rings.finite_rings.integer_mod_ring import IntegerModFactory
from sage.rings.arith import random_prime
class DiffieHellman(PublicKeyCryptosystem):
r"""
The Diffie-Hellman key exchange algorithm.
The Diffie-Hellman signing and verifying algorithms as described in
:func:`sign() ` and
:func:`verify() `, respectively, Diffie–Hellman key exchange (D–H) is a specific method of exchanging keys. It is one of the earliest
practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior
knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent
communications using a symmetric key cipher.
The scheme was first published by Whitfield Diffie and Martin Hellman in 1976, although it later emerged that it had been separately invented a few years earlier
within GCHQ, the British signals intelligence agency, by Malcolm J. Williamson but was kept classified. In 2002, Hellman suggested the algorithm be called Diffie–
Hellman–Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography (Hellman, 2002).
Although Diffie–Hellman key agreement itself is an anonymous (non-authenticated) key-agreement protocol, it provides the basis for a variety of authenticated
protocols, and is used to provide perfect forward secrecy in Transport Layer Security's ephemeral modes (referred to as EDH or DHE depending on the cipher suite).
EXAMPLES:
The following is a sign/verfy example::
sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
sage: dh = DiffieHellman(); dh
The DiffieHellman key exchange scheme.
sage:n = random_prime(12345,1)
sage:g = primitive_root(n)
sage:x = randint(1,12345);
sage:X = mod(g^x,n); X
sage:y = randint(1,12345);
sage:Y = mod(g^y,n); Y
sage:S = dh.sign(Y,x,n);
sage:V = dh.verify(X,y,n);
sage:S == V
True
"""
def __init__(self):
"""
Construct the DiffieHellman key exchange scheme.
OUTPUT:
- A ``DiffieHellman`` object representing the DiffieHellman
key exchange scheme.
See the class docstring of ``DiffieHellman`` for detailed
documentation.
EXAMPLES::
sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
sage: dh = DiffieHellman()
sage: dh == loads(dumps(bg))
True
"""
# no internal data for now; nothing to initialize
pass
def __eq__(self, other):
"""
Compare this ``DiffieHellman`` object with ``other``.
INPUT:
- ``other`` -- a ``DiffieHellman`` object.
OUTPUT:
- ``True`` if both ``self`` and ``other`` are ``DiffieHellman``
objects. ``False`` otherwise.
Two objects are ``DiffieHellman`` objects if their string
representations are the same.
EXAMPLES::
sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
sage: dh1 = DiffieHellman()
sage: dh2 = DiffieHellman()
sage: dh1 == dh2
True
"""
if self.__repr__() == other.__repr__():
return True
else:
return False
def __repr__(self):
"""
A string representation of this DiffieHellman key Exchange scheme.
OUTPUT:
- A string representation of this DiffieHellman key Exchange scheme.
EXAMPLES::
sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
sage: DiffieHellman()
The DiffieHellman key exchange scheme.
"""
return "The DiffieHellman key exchange scheme."
def verify(self, X, y, n):
r"""
Apply the Diffie-Hellman to verify the key ``K1`` using the random integer ``y``, ``X`` and random prime ``n``.
INPUT:
- ``y`` -- Bob chooses a random large integer y and sends.
- ``n`` -- Alice and Bob agree on a large prime, n.
- ``X`` -- X = mod(g^x, n).
OUTPUT:
- A secure key ``K1`` is exchanged between Alice and Bob.
ALGORITHM:
The Diffie-Hellman verifying algorithm works as follows:
# `K1 = mod(X^y, n)`.
EXAMPLES:
The following verifying example is taken from Applied Cryptography, Second edition by Bruce Schneier. Here we verify the key ``K1``::
sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
sage: dh = DiffieHellman()
sage: n = random_prime(12345,1)
sage: g = primitive_root(n)
sage: x = randint(1,12345);
sage: X = mod(g^x,n);
sage: y = randint(1,12345);
sage: V = dh.verify(X, y, n);
"""
K1 = mod(X**y, n)
return K1
def sign(self, Y, x, n):
r"""
Apply the Diffie-Hellman to sign the key ``K2`` using the random integer ``x``, ``Y`` and random prime ``n``.
INPUT:
- ``x`` -- Bob chooses a random large integer x and sends.
- ``n`` -- Alice and Bob agree on a large prime, n.
- ``Y`` -- Y = mod(g^y, n).
OUTPUT:
- A secure key ``K2`` is exchanged between Alice and Bob.
ALGORITHM:
The Diffie-Hellman signing algorithm works as follows:
# `K2 = mod(Y^x, n)`.
EXAMPLES:
The following signing example is taken from Applied Cryptography, Second edition by Bruce Schneier. Here we sign the key ``K2``::
sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
sage: dh = DiffieHellman ()
sage: n = random_prime(12345,1)
sage: g = primitive_root(n)
sage: y = randint(1,12345);
sage: Y = mod(g^y, n);
sage: x = randint(1,12345);
sage: S = dh.sign(Y, x, n);
"""
K2 = mod(Y**x, n)
return K2