Ticket #11565: rsa_cryptosystem.py

File rsa_cryptosystem.py, 14.3 KB (added by ajeeshr, 8 years ago)

This is the python code I implemented in python. Just copy this into the public_key folder in crypto, import the class in this code into all.py in the public_key and re-build sage and run it in a worksheet, its simple!!!

Line 
1r"""
2Rivest, Shamir, Adleman public-key encryption scheme.
3
4The Rivest, Shamir, Adleman public-key encryption scheme. The Rivest-Shamir-Adleman (RSA) scheme has since that time reigned supreme as the most widely accepted and implemented general-purpose approach to public-key encryption. See also the `Wikipedia article <http://en.wikipedia.org/wiki/RSA>`_ on this scheme.
5
6REFERENCES:
7
8.. William Stallings. *Cryptography and Network Security, Priciples and Practices*, Fourth Edition. Prentice Hall, 16 November 2005.
9
10.. Anoop MS. *Public Key Cryptography, Applications Algorithms and Mathematical Explanations*. Tata Elxsi Ltd, India anoopms@tataelxsi.co.in.
11
12.. Minh Van Nguyen. *Number Theory and the RSA Public Key Cryptosystem*. nguyenminh2@gmail.com, July 2009.
13
14AUTHORS:
15
16-Ajeesh R (2011-07)- initial procedural version released as public domain software.
17
18"""
19
20###########################################################################
21# Copyright (c) 2011
22# AJEESH R <iamajeeshr@gmail.com>
23#
24# This program is free software; you can redistribute it and/or modify
25# it under the terms of the GNU General Public License as published by
26# the Free Software Foundation; either version 2 of the License, or
27# (at your option) any later version.
28#
29# This program is distributed in the hope that it will be useful,
30# but WITHOUT ANY WARRANTY; without even the implied warranty of
31# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
32# GNU General Public License for more details.
33#
34# http://www.gnu.org/licenses/
35###########################################################################
36
37from sage.crypto.cryptosystem import PublicKeyCryptosystem
38from sage.rings.arith import gcd
39from sage.rings.arith import xgcd
40from sage.rings.arith import is_prime
41from sage.rings.arith import power_mod
42from sage.rings.arith import euler_phi
43from sage.rings.integer import Integer
44from sage.rings.finite_rings.integer_mod import Mod as mod
45from sage.rings.integer_ring import ZZ
46
47class RSACryptosystem(PublicKeyCryptosystem):
48    r"""
49    The Rivest, Shamir, Adleman public-key encryption scheme.
50
51    The RSA encryption and decryption algorithms as described in
52    :func:`encrypt() <RSACryptosystem.encrypt>` and
53    :func:`decrypt() <RSACryptosystem.decrypt>`, respectively, make use of the
54
55    EXAMPLES:
56
57    The following is an encryption/decryption example.::
58
59        sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
60        sage: rc = RSACryptosystem(); rc
61        The Rivest, Shamir, Adleman public-key encryption scheme.
62        sage: p = 31; q = 61;
63        sage: pubkey = rc.public_key(p, q); pubkey
64        (4951760154835678088235319297L, 17)
65        sage: prikey = rc.private_key(p, q); prikey
66        (4951760154835678088235319297L, 4077920125612805357425763753)
67        sage: P = 72697676798779827668
68        sage: C = rc.encrypt(P, pubkey); C
69        2467165704948727396791981601
70        sage: M = rc.decrypt(C, prikey); M
71        72697676798779827668
72        sage: M == P
73        True
74
75    Generate a pair of public/private keys. Use the public key to
76    encrypt a plaintext. Then decrypt the resulting ciphertext using the
77    private key. Finally, compare the decrypted message with the original
78    plaintext.::
79
80        sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
81        sage: rc = RSACryptosystem()
82        sage: P = 72697676798779827668
83        sage: C = rc.encrypt(P, pubkey)
84        sage: M = rc.decrypt(C, prikey)
85        sage: M == P
86        True
87    """
88
89    def __init__(self):
90        """
91        Construct the RSA public-key encryption scheme.
92
93        OUTPUT:
94
95        - A ``RSACryptosystem`` object representing the RSA public-key encryption scheme.
96
97        See the class docstring of ``RSACryptosystem`` for detailed documentation.
98
99        EXAMPLES::
100
101            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
102            sage: rc = RSACryptosystem()
103            sage: rc == loads(dumps(rc))
104            True
105        """
106        # no internal data for now; nothing to initialize
107        pass
108
109    def __eq__(self, other):
110        """
111        Compare this ``RSACryptosystem`` object with ``other``.
112
113        INPUT:
114
115        - ``other`` -- a ``RSACryptosystem`` object.
116
117        OUTPUT:
118
119        - ``True`` if both ``self`` and ``other`` are ``RSACryptosystem``
120          objects. ``False`` otherwise.
121
122        Two objects are ``RSACryptosystem`` objects if their string
123        representations are the same.
124
125        EXAMPLES::
126
127            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
128            sage: rc1 = RSACryptosystem()
129            sage: rc2 = RSACryptosystem()
130            sage: rc1 == rc2
131            True
132        """
133        if self.__repr__() == other.__repr__():
134            return True
135        else:
136            return False
137
138    def __repr__(self):
139        """
140        A string representation of this RSA public-key encryption scheme.
141
142        OUTPUT:
143
144        - A string representation of this RSA public-key encryption scheme.
145
146        EXAMPLES::
147
148            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
149            sage: RSACryptosystem()
150            The Rivest, Shamir, Adleman public-key encryption scheme.
151        """
152        return "The Rivest, Shamir, Adleman public-key encryption scheme."
153
154    def decrypt(self, C, K):
155        r"""
156        Apply the RSA public-key encryption scheme to decrypt the ciphertext ``C``
157        using the private key ``K``.
158
159        INPUT:
160
161        - ``C`` -- a ciphertext resulting from encrypting a plaintext using
162          the RSA public-key encryption algorithm.
163
164        - ``K`` -- a private key `(n, d)` where `n` is the product of two Mersenne
165          primes `p` and `q`, `d` is computed using the extended euclidean algorithm.
166
167        OUTPUT:
168
169        - The plaintext resulting from decrypting the ciphertext ``C`` using
170          the RSA public-key decryption algorithm.
171
172        ALGORITHM:
173
174        The RSA public-key decryption algorithm is described as follows:
175
176        #. Let `C` be the ciphertext `C = (M^e) mod n`.
177        #. Let `(n, d)` be the private key whose corresponding
178           public key is `(n, e)`.
179        #. The plaintext is `M = (C^d) mod n`.
180
181        EXAMPLES:
182
183        The following is a decryption example. Here we decrypt a string of numbers.::
184
185            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
186            sage: rc = RSACryptosystem()
187            sage: p = 31; q = 61;
188            sage: C = 2467165704948727396791981601
189            sage: K = rc.private_key(p, q); K
190            (4951760154835678088235319297L, 4077920125612805357425763753)
191            sage: P = rc.decrypt(C, K); P
192            72697676798779827668
193
194        TESTS:
195
196        The private key `K = (n, d)` must be such that `p` and `q` are
197        distinct prime numbers.::
198
199            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
200            sage: rc = RSACryptosystem()
201            sage: C = 2467165704948727396791981601
202            sage: K = rc.private_key(31, 31);
203            Traceback (most recent call last):
204            ...
205            ValueError: p and q must be distinct primes.
206            sage: K = rc.private_key(31, 61)
207            sage: P =  rc.decrypt(C, K); P
208            72697676798779827668
209        """
210        # private key
211        (n, d) = K
212
213        # perform the decryption
214        return power_mod(C, d, n)
215
216    def encrypt(self, P, K):
217        r"""
218        Apply the RSA public-key encryption scheme to encrypt the plaintext ``P`` using
219        the public key ``K``.
220
221        INPUT:
222
223        - ``P`` -- a non-empty string of plaintext. The string ``""`` is
224          an empty string, whereas ``" "`` is a string consisting of one
225          white space character. The plaintext can be a string of numbers or
226          a string of ASCII characters.
227
228        - ``K`` -- a public key, which is the product of two Mersenne primes and e, 0 < e < euler_phi(n)
229          such that also satisfy the requirement `\gcd(e, euler_phi(n))=1`.
230
231        OUTPUT:
232
233        - The ciphertext resulting from encrypting ``P`` using the public
234          key ``K``.
235
236        ALGORITHM:
237
238        The RSA public-key encryption algorithm is described as follows:
239
240        #. Let `(n, e)` be a public key, where `n = pq` is the product of two
241           distinct Mersenne primes `p` and `q` and `e` is a random positive
242           integer that is co-prime to euler_phi(n).
243        #. Let `P = a string` be the message (plaintext).
244        #. The ciphertext is `C = (P^e) mod n`.
245
246
247        EXAMPLES:
248
249        The following is an encryption example. Here, we encrypt a string of number.::
250
251            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
252            sage: rc = RSACryptosystem()
253            sage: p = 101; q = 103;
254            sage: P = 4
255            sage: C = rc.encrypt(P, K); C
256            4932417489295796679844298689
257
258        Now encrypt another string of numbers. The result is random; no seed is
259        provided to the encryption function so the function generates its
260        own random seed.::
261
262            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
263            sage: rc = RSACryptosystem()
264            sage: p = 31; q = 61;
265            sage: P = 72697676798779827668
266            sage: K = rc.public_key(p, q);
267            sage: C = rc.encrypt(P, K);
268            sage: C
269            2467165704948727396791981601
270
271        TESTS:
272
273        The plaintext cannot be an empty string. ::
274
275            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
276            sage: rc = RSACryptosystem()
277            sage: rc.encrypt("", 3)
278            Traceback (most recent call last):
279            ...
280            ValueError: The plaintext cannot be an empty string.
281        """
282        # public key
283        (n, e) = K
284
285        # sanity check
286        if P == "":
287            raise ValueError("The plaintext cannot be an empty string.")
288
289        else:
290            return power_mod(P, e, n)
291
292    def private_key(self, p, q):
293        r"""
294        Return the RSA private key corresponding to the
295        distinct Mersenne primes ``p`` and ``q``.
296
297        INPUT:
298
299        - ``p`` -- a prime number.
300
301        - ``q`` -- a prime number.
302
303        OUTPUT:
304
305        - The RSA private key `(n, d)` where
306          `de is congruent to (1 mod euler_phi(n))`.
307
308        Both ``p`` and ``q`` must be distinct primes. Let `p` be a
309        positive prime. Then `p` is a Mersenne prime if `p` is equal to `(2^p)-1`.
310
311        EXAMPLES:
312
313        Obtain two distinct primes and compute the RSA
314        private key corresponding to two Mersenne primes generated from the distinct primes.::
315
316            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
317            sage: rc = RSACryptosystem()
318            sage: rc.private_key(19, 23)
319            (4398037598209L, 1173935455331)
320
321        Choose two distinct primes, compute the RSA
322        private key corresponding to two Mersenne primes generated from the distinct primes , and test that the
323        resulting private key `(n, d)` satisfies
324        `\mod(de, euler_phi(n)) = 1`.::
325
326            sage: p = 31
327            sage: q = 61
328            sage: p = (2 ^ p)-1; q = (2 ^ q)-1
329            sage: is_prime(p); is_prime(q)
330            True
331            True
332
333        TESTS:
334
335        Both of the input ``p`` and ``q`` must be distinct primes. ::
336
337            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
338            sage: rc = RSACryptosystem()
339            sage: rc.private_key(78307, 78307)
340            Traceback (most recent call last):
341            ...
342            ValueError: p and q must be distinct primes.
343        """
344        if p == q:
345            raise ValueError("p and q must be distinct primes.")
346        if is_prime(p) and is_prime(q):
347            p = (2**p)-1
348            q = (2**q)-1
349
350            n = p * q
351
352            e = 3
353            while 1:
354                if gcd(euler_phi(n), e) == 1:
355                    break
356                else:
357                    e = e + 2
358
359            # Generate a number d such that de = 1 (mod euler_phi(n))
360            bezout = xgcd(e, euler_phi(n))
361            d = Integer(mod(bezout[1], euler_phi(n)))
362            while mod(d * e, euler_phi(n)) != 1:
363                d = Integer(mod(bezout[1], euler_phi(n)))
364        else:
365            raise ValueError("p and q must be distinct primes.")
366        return (n, d)
367
368    def public_key(self, p, q):
369        r"""
370        Return RSA public key corresponding to the
371        distinct Mersenne primes ``p`` and ``q``.
372
373        INPUT:
374
375        - ``p`` -- a prime number.
376
377        - ``q`` -- a prime number.
378
379        OUTPUT:
380
381        - The RSA public key `n = pq` and `e`.
382
383        Both ``p`` and ``q`` must be distinct primes. Let `p` be a
384        positive prime. Then `p` is a Mersenne prime if `p` is equal to `(2^p)-1`.
385
386        EXAMPLES:
387
388        Obtain two distinct Mersenne primes and compute the RSA
389        public key corresponding to those two Mersenne primes::
390
391            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
392            sage: rc = RSACryptosystem()
393            sage: rc.public_key(31, 61)
394            (4951760154835678088235319297L, 17)
395
396        Choose two distinct primes, compute the RSA
397        public key corresponding to two Mersenne primes generated from the distinct primes.::
398
399            sage: p = 31
400            sage: q = 61
401            sage: p = (2 ^ p)-1; q = (2 ^ q)-1
402            sage: is_prime(p); is_prime(q)
403            True
404            True
405
406        TESTS:
407
408        The input ``p`` and ``q`` must be distinct primes. ::
409
410            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
411            sage: rc = RSACryptosystem()
412            sage: rc.public_key(3, 3)
413            Traceback (most recent call last):
414            ...
415            ValueError: p and q must be distinct primes.
416        """
417        if p == q:
418            raise ValueError("p and q must be distinct primes.")
419        if is_prime(p) and is_prime(q):
420            p = (2**p)-1
421            q = (2**q)-1
422
423            n = p * q
424            # Generate a number e so that gcd(euler_phi(n), e) = 1
425            e = 3
426            while 1:
427                if gcd(euler_phi(n), e) == 1: 
428                    break
429                else:
430                    e = e + 2
431        else:
432            raise ValueError("p and q must be distinct primes.")
433        return (n, e)