Ticket #11568: diffie_hellman.py

File diffie_hellman.py, 7.5 KB (added by tevinjoseph, 10 years ago)
Line 
1r"""
2Diffie–Hellman Key exchange Scheme.
3The Diffie–Hellman Key exchange Scheme. This scheme was originally described in [DiffieHellman] and the `Wikipedia article <http://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange>` on this scheme.
4
5REFERENCES:
6
7.. [J. H. Ellis], J. H. Ellis, *The possibility of Non-Secret digital encryption*, 1996.
8
9.. [Dieter Gollmann (2006)] Dieter Gollmann. *Computer Security *, Second Edition West Sussex, England: John Wiley & Sons
10
11AUTHORS:
12
13- Tevin Joseph K.O.
14
15"""
16
17###########################################################################
18# Copyright (c) 2011
19#  TEVIN JOSEPH K.O.<tevinjosephko@gmail.com>
20#
21# This program is free software; you can redistribute it and/or modify
22# it under the terms of the GNU General Public License as published by
23# the Free Software Foundation; either version 2 of the License, or
24# (at your option) any later version.
25#
26# This program is distributed in the hope that it will be useful,
27# but WITHOUT ANY WARRANTY; without even the implied warranty of
28# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
29# GNU General Public License for more details.
30#
31# http://www.gnu.org/licenses/
32###########################################################################
33
34from sage.crypto.cryptosystem import PublicKeyCryptosystem
35from sage.rings.arith import power_mod
36from sage.rings.finite_rings.integer_mod import Mod as mod
37from sage.rings.finite_rings.integer_mod_ring import IntegerModFactory
38from sage.rings.arith import random_prime
39
40class DiffieHellman(PublicKeyCryptosystem):
41    r"""
42    The Diffie-Hellman key exchange algorithm.
43
44    The Diffie-Hellman signing and verifying algorithms as described in
45    :func:`sign() <DiffieHellman.sign>` and
46    :func:`verify() <DiffieHellman.verify>`, respectively, Diffie–Hellman key exchange (D–H) is a specific method of exchanging keys. It is one of the earliest
47    practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior
48    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
49    communications using a symmetric key cipher.
50    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
51    within GCHQ, the British signals intelligence agency, by Malcolm J. Williamson but was kept classified. In 2002, Hellman suggested the algorithm be called Diffie–
52    Hellman–Merkle key exchange in recognition of Ralph Merkle's contribution to the invention of public-key cryptography (Hellman, 2002).
53    Although Diffie–Hellman key agreement itself is an anonymous (non-authenticated) key-agreement protocol, it provides the basis for a variety of authenticated
54    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).
55
56    EXAMPLES:
57
58    The following is  a sign/verfy example::
59
60        sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
61        sage: dh = DiffieHellman(); dh
62        The DiffieHellman key exchange scheme.
63        sage:n = random_prime(12345,1)
64        sage:g = primitive_root(n)
65        sage:x = randint(1,12345);
66        sage:X = mod(g^x,n); X
67        sage:y = randint(1,12345);
68        sage:Y = mod(g^y,n); Y
69        sage:S = dh.sign(Y,x,n);
70        sage:V = dh.verify(X,y,n);
71        sage:S == V
72        True
73    """
74
75    def __init__(self):
76        """
77        Construct the DiffieHellman key exchange scheme.
78
79        OUTPUT:
80
81        - A ``DiffieHellman`` object representing the DiffieHellman
82          key exchange scheme.
83
84        See the class docstring of ``DiffieHellman`` for detailed
85        documentation.
86
87        EXAMPLES::
88
89            sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
90            sage: dh = DiffieHellman()
91            sage: dh == loads(dumps(bg))
92            True
93        """
94        # no internal data for now; nothing to initialize
95        pass
96
97    def __eq__(self, other):
98        """
99        Compare this ``DiffieHellman`` object with ``other``.
100
101        INPUT:
102
103        - ``other`` -- a ``DiffieHellman`` object.
104
105        OUTPUT:
106
107        - ``True`` if both ``self`` and ``other`` are ``DiffieHellman``
108          objects. ``False`` otherwise.
109
110        Two objects are ``DiffieHellman`` objects if their string
111        representations are the same.
112
113        EXAMPLES::
114
115            sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
116            sage: dh1 = DiffieHellman()
117            sage: dh2 = DiffieHellman()
118            sage: dh1 == dh2
119            True
120        """
121        if self.__repr__() == other.__repr__():
122            return True
123        else:
124            return False
125
126    def __repr__(self):
127        """
128        A string representation of this DiffieHellman key Exchange scheme.
129
130        OUTPUT:
131
132        - A string representation of this DiffieHellman key Exchange scheme.
133
134        EXAMPLES::
135
136            sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
137            sage: DiffieHellman()
138            The DiffieHellman key exchange scheme.
139        """
140        return "The DiffieHellman key exchange scheme."
141
142    def verify(self, X, y, n):
143        r"""
144        Apply the Diffie-Hellman to verify the key ``K1`` using the random integer ``y``, ``X`` and random prime ``n``.
145
146        INPUT:
147
148        - ``y`` -- Bob chooses a random large integer y and sends.
149
150        - ``n`` -- Alice and Bob agree on a large prime, n.
151
152        - ``X`` -- X = mod(g^x, n).
153
154        OUTPUT:
155
156        - A secure key ``K1`` is exchanged between Alice and Bob.
157
158        ALGORITHM:
159
160        The Diffie-Hellman verifying algorithm works as follows:
161
162        # `K1 = mod(X^y, n)`.
163       
164        EXAMPLES:
165
166        The following verifying example is taken from Applied Cryptography, Second edition by Bruce Schneier. Here we verify the key  ``K1``::
167
168            sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
169            sage: dh = DiffieHellman()
170            sage: n = random_prime(12345,1)
171            sage: g = primitive_root(n)
172            sage: x = randint(1,12345);
173            sage: X = mod(g^x,n);
174            sage: y = randint(1,12345);
175            sage: V = dh.verify(X, y, n);
176        """
177        K1 = mod(X**y, n)
178        return K1
179
180    def sign(self, Y, x, n):
181        r"""
182        Apply the Diffie-Hellman to sign the key ``K2`` using the random integer ``x``, ``Y`` and random prime ``n``.
183
184        INPUT:
185
186        - ``x`` -- Bob chooses a random large integer x and sends.
187
188        - ``n`` -- Alice and Bob agree on a large prime, n.
189 
190        - ``Y`` -- Y = mod(g^y, n).
191
192        OUTPUT:
193
194        - A secure key ``K2`` is exchanged between Alice and Bob.
195
196        ALGORITHM:
197
198        The Diffie-Hellman signing algorithm works as follows:
199
200        # `K2 = mod(Y^x, n)`.
201       
202        EXAMPLES:
203
204        The following signing example is taken from Applied Cryptography, Second edition by Bruce Schneier. Here we sign the key  ``K2``::
205
206            sage: from sage.crypto.public_key.diffie_hellman import DiffieHellman
207            sage: dh = DiffieHellman ()
208            sage: n = random_prime(12345,1)
209            sage: g = primitive_root(n)
210            sage: y = randint(1,12345);
211            sage: Y = mod(g^y, n);
212            sage: x = randint(1,12345);
213            sage: S = dh.sign(Y, x, n);
214        """
215        K2 = mod(Y**x, n)   
216        return K2