Ticket #11565: rsa_cryptosystem.2.py

File rsa_cryptosystem.2.py, 22.8 KB (added by peter.story, 4 years ago)

Major rewrite of the module, with the goal of a pedagogical implementation.

Line 
1r"""
2Rivest, Shamir, Adleman public-key encryption scheme.
3
4The Rivest, Shamir, Adleman public-key encryption scheme.
5The Rivest-Shamir-Adleman (RSA) scheme is the most widely accepted and
6implemented general-purpose approach to public-key encryption. See also
7the `Wikipedia article <http://en.wikipedia.org/wiki/RSA>`_ on this scheme.
8
9REFERENCES:
10
11.. David Ireland. *RSA Algorithm*. http://www.di-mgt.com.au/rsa_alg.html. 19 March 2015.
12
13.. William Stallings. *Cryptography and Network Security, Priciples and Practices*, Fourth Edition. Prentice Hall, 16 November 2005.
14
15.. Brian Raiter. *Prime Number Hide-and-Seek: How the RSA Cipher Works*. http://www.muppetlabs.com/~breadbox/txt/rsa.html. Accessed 20 March 2015.
16
17.. Thomas Pornin. *Should RSA public exponent be only in {3, 5, 17, 257 or 65537} due to security considerations?*. http://security.stackexchange.com/questions/2335/should-rsa-public-exponent-be-only-in-3-5-17-257-or-65537-due-to-security-c
18
19.. http://en.wikipedia.org/wiki/RSA_(cryptosystem)#Operation
20
21
22AUTHORS:
23
24-Peter Story (2015-03)- major rewrite with the goal of a pedagogical implementation.
25-Ajeesh R (2011-07)- initial procedural version released as public domain software.
26
27"""
28
29###########################################################################
30# Copyright (c) 2011
31# AJEESH R <iamajeeshr@gmail.com>
32#
33# This program is free software; you can redistribute it and/or modify
34# it under the terms of the GNU General Public License as published by
35# the Free Software Foundation; either version 2 of the License, or
36# (at your option) any later version.
37#
38# This program is distributed in the hope that it will be useful,
39# but WITHOUT ANY WARRANTY; without even the implied warranty of
40# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
41# GNU General Public License for more details.
42#
43# http://www.gnu.org/licenses/
44###########################################################################
45
46from sage.crypto.cryptosystem import PublicKeyCryptosystem
47from sage.rings.arith import euler_phi
48from sage.rings.arith import gcd
49from sage.rings.arith import is_prime
50from sage.rings.arith import power_mod
51from sage.rings.integer import Integer
52from sage.rings.finite_rings.integer_mod import Mod as mod
53from sage.rings.integer_ring import ZZ
54from sage.sets.primes import Primes
55
56class RSACryptosystem(PublicKeyCryptosystem):
57    r"""
58    The Rivest, Shamir, Adleman public-key encryption scheme.
59
60    CAN PROBABLY REMOVE THIS
61    The RSA encryption and decryption algorithms as described in
62    :func:`encrypt() <RSACryptosystem.encrypt>` and
63    :func:`decrypt() <RSACryptosystem.decrypt>`, respectively, make use of the
64
65    EXAMPLES:
66
67    The following is an encryption/decryption example.::
68
69        sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
70        sage: rc = RSACryptosystem(); rc
71        The Rivest, Shamir, Adleman public-key encryption scheme.
72        sage: p = 101; q = 103
73        sage: public, private = rc.calculate_keys(p, q); public, private
74        ((10403, 257), (10403, 5993))
75        sage: P = 9001
76        sage: C = rc.encrypt(P, public); C
77        6022
78        sage: M = rc.decrypt(C, private); M
79        9001
80        sage: M == P
81        True
82    """
83
84    def __init__(self):
85        """
86        Construct the RSA public-key encryption scheme.
87
88        OUTPUT:
89
90        - A ``RSACryptosystem`` object representing the RSA public-key encryption scheme.
91
92        See the class docstring of ``RSACryptosystem`` for detailed documentation.
93
94        EXAMPLES::
95
96            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
97            sage: rc = RSACryptosystem()
98            sage: rc == loads(dumps(rc))
99            True
100        """
101        # no internal data for now; nothing to initialize
102        pass
103
104    def __eq__(self, other):
105        """
106        Compare this ``RSACryptosystem`` object with ``other``.
107
108        INPUT:
109
110        - ``other`` -- a ``RSACryptosystem`` object.
111
112        OUTPUT:
113
114        - ``True`` if both ``self`` and ``other`` are ``RSACryptosystem``
115          objects. ``False`` otherwise.
116
117        Two objects are ``RSACryptosystem`` objects if their string
118        representations are the same.
119
120        EXAMPLES::
121
122            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
123            sage: rc1 = RSACryptosystem()
124            sage: rc2 = RSACryptosystem()
125            sage: rc1 == rc2
126            True
127        """
128        if self.__repr__() == other.__repr__():
129            return True
130        else:
131            return False
132
133    def __repr__(self):
134        """
135        A string representation of this RSA public-key encryption scheme.
136
137        OUTPUT:
138
139        - A string representation of this RSA public-key encryption scheme.
140
141        EXAMPLES::
142
143            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
144            sage: RSACryptosystem()
145            The Rivest, Shamir, Adleman public-key encryption scheme.
146        """
147        return "The Rivest, Shamir, Adleman public-key encryption scheme."
148
149    def decrypt(self, C, K):
150        r"""
151        Apply the RSA public-key encryption scheme to decrypt the ciphertext ``C``
152        using the private key ``K``.
153
154        INPUT:
155
156        - ``C`` -- an integer ciphertext resulting from encrypting a plaintext
157          using the RSA public-key encryption algorithm.
158
159        - ``K`` -- a private key, stored as a tuple ``(n, d)`` where ``n``
160          is the modulus and ``d`` is inverse of the exponent ``mod (phi(n))``.
161
162        OUTPUT:
163
164        - The plaintext resulting from decrypting the ciphertext ``C`` using
165          the RSA public-key decryption algorithm.
166
167        ALGORITHM:
168
169        The RSA public-key decryption algorithm is described as follows:
170
171        #. Let `C` be the ciphertext `C = (M^e) mod n`.
172        #. Let `(n, d)` be the private key whose corresponding
173           public key is `(n, e)`.
174        #. The plaintext is `M = C^d = (M^e)^d mod n`.
175
176        EXAMPLES:
177
178        An example of decryption.::
179
180            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
181            sage: rc = RSACryptosystem()
182            sage: p = 101; q = 103
183            sage: public, private = rc.calculate_keys(p, q)
184            sage: P = 42
185            sage: C = rc.encrypt(P, public); C
186            6270
187            sage: M = rc.decrypt(C, private); M; P == M
188            42
189            True
190
191        TESTS:
192
193        Decryption should recover the original message.::
194
195            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
196            sage: rc = RSACryptosystem()
197            sage: p = 101; q = 103; n = p * q
198            sage: public, private = rc.calculate_keys(p, q)
199            sage: P = 42
200            sage: C = rc.encrypt(P, public)
201            sage: rc.decrypt(C, private) == P
202            True
203            sage: P = ZZ.random_element(2, n)
204            sage: C = rc.encrypt(P, public)
205            sage: rc.decrypt(C, private) == P
206            True
207
208        Ciphertext outside the range ``[2, n-1]`` should be rejected.::
209
210            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
211            sage: rc = RSACryptosystem()
212            sage: p = 101; q = 103; n = p * q
213            sage: public, private = rc.calculate_keys(p, q)
214            sage: C = -5; rc.decrypt(C, private)
215            Traceback (most recent call last):
216            ...
217            ValueError: The ciphertext must be an integer greater than 1 and less than n.
218
219            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
220            sage: rc = RSACryptosystem()
221            sage: p = 101; q = 103; n = p * q
222            sage: public, private = rc.calculate_keys(p, q)
223            sage: C = 0; rc.decrypt(C, private)
224            Traceback (most recent call last):
225            ...
226            ValueError: The ciphertext must be an integer greater than 1 and less than n.
227
228            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
229            sage: rc = RSACryptosystem()
230            sage: p = 101; q = 103; n = p * q
231            sage: public, private = rc.calculate_keys(p, q)
232            sage: C = 1; rc.decrypt(C, private)
233            Traceback (most recent call last):
234            ...
235            ValueError: The ciphertext must be an integer greater than 1 and less than n.
236
237            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
238            sage: rc = RSACryptosystem()
239            sage: p = 101; q = 103; n = p * q
240            sage: public, private = rc.calculate_keys(p, q)
241            sage: C = n; rc.decrypt(C, private)
242            Traceback (most recent call last):
243            ...
244            ValueError: The ciphertext must be an integer greater than 1 and less than n.
245
246            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
247            sage: rc = RSACryptosystem()
248            sage: p = 101; q = 103; n = p * q
249            sage: public, private = rc.calculate_keys(p, q)
250            sage: C = n + 5; rc.decrypt(C, private)
251            Traceback (most recent call last):
252            ...
253            ValueError: The ciphertext must be an integer greater than 1 and less than n.
254
255
256        Ciphertext in the range ``[2, n-1]`` should be accepted.::
257
258            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
259            sage: rc = RSACryptosystem()
260            sage: p = 101; q = 103; n = p * q
261            sage: public, private = rc.calculate_keys(p, q)
262            sage: C = 2; M = rc.decrypt(C, private)
263            sage: C = n - 1; M = rc.decrypt(C, private)
264            sage: C = ZZ.random_element(2, n); M = rc.decrypt(C, private)
265
266        """
267        # private key
268        (n, d) = K
269
270        # sanity check
271        if (C < 2) or (C >= n):
272            raise ValueError("The ciphertext must be an integer greater than 1 and less than n.")
273
274        # perform the decryption
275        return power_mod(C, d, n)
276
277    def encrypt(self, P, K):
278        r"""
279        Apply the RSA public-key encryption scheme to encrypt the plaintext ``P`` using
280        the public key ``K``.
281
282        INPUT:
283
284        - ``P`` -- a number in the range ``[2, n-1]``. Note that a secure
285          implementation of the cryptosystem would add padding to this
286          plaintext, in order to protect against a number of attacks.
287
288        - ``K`` -- a public key, stored as a tuple ``(n, e)`` where ``n``
289          is the modulus and ``e`` is the exponent.
290
291        OUTPUT:
292
293        - The ciphertext resulting from encrypting ``P`` using the public
294          key ``K``.
295
296        ALGORITHM:
297
298        The RSA public-key encryption algorithm is described as follows:
299
300        #. Let `(n, e)` be a public key, where `n = pq` is the product of two
301           distinct primes `p` and `q` and exponent `e` is a positive
302           integer that is co-prime to euler_phi(n).
303        #. Let `P = a string` be the message (plaintext).
304        #. The ciphertext is `C = (P^e) mod n`.
305
306
307        EXAMPLES:
308
309        An example of encryption.
310        ``P = 42`` is our plaintext, and ``C = 6270`` is the resulting ciphertext.::
311
312            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
313            sage: rc = RSACryptosystem()
314            sage: p = 101; q = 103
315            sage: public, private = rc.calculate_keys(p, q)
316            sage: P = 42
317            sage: C = rc.encrypt(P, public); C
318            6270
319
320
321        If the system allowed us to encrypt values greater than ``n-1``, our
322        message could be encrypted to the same value a different messsage.
323        ``P_1`` is our first plaintext, and ``P_2`` is a plaintext greater than
324        ``n - 1``, so it isn't encypted to a distinct value.::
325
326            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
327            sage: rc = RSACryptosystem()
328            sage: p = 101; q = 103; n = p * q
329            sage: public, private = rc.calculate_keys(p, q)
330            sage: e = public[1]
331            sage: P_1 = 42
332            sage: P_2 = 42 + n
333            sage: C_1 = power_mod(P_1, e, n); C_1
334            6270
335            sage: C_2 = power_mod(P_2, e, n); C_2
336            6270
337            sage: C_1 == C_2
338            True
339
340
341        TESTS:
342
343        Plaintext outside the range ``[2, n-1]`` should be rejected.::
344
345            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
346            sage: rc = RSACryptosystem()
347            sage: p = 101; q = 103; n = p * q
348            sage: public, private = rc.calculate_keys(p, q)
349            sage: P = -5; rc.encrypt(P, public)
350            Traceback (most recent call last):
351            ...
352            ValueError: The plaintext must be an integer greater than 1 and less than n.
353
354            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
355            sage: rc = RSACryptosystem()
356            sage: p = 101; q = 103; n = p * q
357            sage: public, private = rc.calculate_keys(p, q)
358            sage: P = 0; rc.encrypt(P, public)
359            Traceback (most recent call last):
360            ...
361            ValueError: The plaintext must be an integer greater than 1 and less than n.
362
363            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
364            sage: rc = RSACryptosystem()
365            sage: p = 101; q = 103; n = p * q
366            sage: public, private = rc.calculate_keys(p, q)
367            sage: P = 1; rc.encrypt(P, public)
368            Traceback (most recent call last):
369            ...
370            ValueError: The plaintext must be an integer greater than 1 and less than n.
371
372            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
373            sage: rc = RSACryptosystem()
374            sage: p = 101; q = 103; n = p * q
375            sage: public, private = rc.calculate_keys(p, q)
376            sage: P = n; rc.encrypt(P, public)
377            Traceback (most recent call last):
378            ...
379            ValueError: The plaintext must be an integer greater than 1 and less than n.
380
381            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
382            sage: rc = RSACryptosystem()
383            sage: p = 101; q = 103; n = p * q
384            sage: public, private = rc.calculate_keys(p, q)
385            sage: P = n + 5; rc.encrypt(P, public)
386            Traceback (most recent call last):
387            ...
388            ValueError: The plaintext must be an integer greater than 1 and less than n.
389
390
391        Plaintext in the range ``[2, n-1]`` should be accepted.::
392
393            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
394            sage: rc = RSACryptosystem()
395            sage: p = 101; q = 103; n = p * q
396            sage: public, private = rc.calculate_keys(p, q)
397            sage: P = 2; C = rc.encrypt(P, public)
398            sage: P = n - 1; C = rc.encrypt(P, public)
399            sage: P = ZZ.random_element(2, n); C = rc.encrypt(P, public)
400
401        """
402        # public key
403        n, e = K
404
405        # sanity check
406        if (P < 2) or (P >= n):
407            raise ValueError("The plaintext must be an integer greater than 1 and less than n.")
408
409        # Encrypt and return the message
410        return power_mod(P, e, n)
411
412    def choose_exponent(self, phi_n):
413        """
414        Choose an exponent relatively prime to the Euler
415        Characteristic of ``n``.
416
417        Using a small number is not a security problem. For pedagogical
418        purposes, we include two different ways of finding ``e``.
419
420        INPUT:
421
422        - ``phi_n`` -- the Euler Characteristic of ``n``
423
424        OUTPUT:
425
426        - A number relatively prime to ``phi_n``
427
428
429        EXAMPLES:
430
431        Get a number relatively prime to ``phi_n``.
432
433            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
434            sage: rc = RSACryptosystem()
435            sage: phi_n = 11020
436            sage: e = rc.choose_exponent(phi_n)
437            sage: gcd(phi_n, e) == 1
438            True
439
440        TESTS:
441
442        The returned value must be relatively prime to ``phi_n``::
443
444            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
445            sage: rc = RSACryptosystem()
446            sage: phi_n = ZZ.random_element(50, 100)
447            sage: e = rc.choose_exponent(phi_n)
448            sage: gcd(phi_n, e) == 1
449            True
450
451
452        Exercise the second method of finding a relatively prime exponent.::
453
454            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
455            sage: rc = RSACryptosystem()
456            sage: e_options = [3, 5, 17, 257, 65537]
457            sage: phi_n = prod(e_options)
458            sage: e = rc.choose_exponent(phi_n)
459            sage: gcd(phi_n, e) == 1
460            True
461            sage: e not in e_options
462            True
463
464        """
465        # Several recommendations for e, according to the SSL specification
466        e_options = [3, 5, 17, 257, 65537]
467        # Seeking an e such that phi_n and e are coprime
468        for e_option in e_options:
469            # Since each e_option is a prime, we can check efficiently
470            # check coprimeness; the only way they wouldn't be coprime would
471            # be if phi_n was a multiple of the e_option
472            if ((phi_n % e_option) != 0): # They are coprime
473                return e_option
474
475        # It is unlikely that none of the e_options will work, but just in case
476        # we provide the option to seek additional values.
477        P = Primes()
478        p = P.first()
479        while (phi_n % p == 0):
480            p = P.next(p)
481        return p
482
483    def calculate_keys(self, p, q, enforce_primes=True):
484        r"""
485        Return an RSA public and private key pair corresponding to the
486        distinct primes ``p`` and ``q``.
487
488        INPUT:
489
490        - ``p`` -- a prime number.
491
492        - ``q`` -- a prime number.
493
494        OUTPUT:
495
496        - The RSA public and private keys as a tuple `((n, e), (n, d))`.
497
498
499        EXAMPLES:
500
501        Compute an RSA public and private key pair corresponding to the
502        supplied primes. The ``d`` in the private key should be the
503        multiplicative inverse of ``e`` mod ``\phi(n)``::
504
505            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
506            sage: rc = RSACryptosystem()
507            sage: public, private = rc.calculate_keys(19, 23); public, private
508            ((437, 5), (437, 317))
509            sage: n = public[0]; e = public[1]; d = private[1]
510            sage: (e * d) % euler_phi(n)
511            1
512
513        For teaching purposes, you can supply two numbers that are not primes.
514        This is also helpful if you are using very large primes, to avoid the
515        expensive computation of checking primeness.
516        In this example, we use prime ``17`` and Carmichael number
517        ``561 = 3 * 11 * 17`` to generate the keys. Note that decrypting
518        doesn't recover the original plaintext.::
519
520            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
521            sage: rc = RSACryptosystem()
522            sage: public, private = rc.calculate_keys(17, 561, False); public, private
523            ((9537, 3), (9537, 2987))
524            sage: P = 1234
525            sage: C = rc.encrypt(P, public); C
526            5794
527            sage: M = rc.decrypt(C, private); M
528            5722
529
530        In this example we use ``p`` and ``q`` which are relatively prime, but
531        ``p`` is not a prime. In this case, only certain plaintexts can be
532        recovered.::
533
534            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
535            sage: rc = RSACryptosystem()
536            sage: public, private = rc.calculate_keys(4, 19, False); public, private
537            ((76, 5), (76, 11))
538            sage: P = 10
539            sage: M = rc.decrypt(rc.encrypt(P, public), private); M
540            48
541            sage: P = 24
542            sage: M = rc.decrypt(rc.encrypt(P, public), private); M
543            24
544
545        However, it is also possible to be build a cryptosystem using a
546        composite which works for all plaintexts.::
547
548            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
549            sage: rc = RSACryptosystem()
550            sage: public, private = rc.calculate_keys(5, 6, False)
551            sage: n = public[0]
552            sage: fail_count = 0
553            sage: for P in range(2, n):
554            ....:     if P != rc.decrypt(rc.encrypt(P, public), private):
555            ....:         fail_count += 1
556            sage: fail_count
557            0
558
559        TESTS:
560
561        Both of the inputs ``p`` and ``q`` must be distinct.::
562
563            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
564            sage: rc = RSACryptosystem()
565            sage: rc.calculate_keys(23, 23)
566            Traceback (most recent call last):
567            ...
568            ValueError: p and q must be distinct.
569
570
571        Both of the inputs ``p`` and ``q`` must be prime.::
572
573            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
574            sage: rc = RSACryptosystem()
575            sage: rc.calculate_keys(13, 21)
576            Traceback (most recent call last):
577            ...
578            ValueError: p and q must be primes.
579
580        Allow ``p`` or ``q`` to be composite if ``enforce_primes`` is set
581        to ``False``.::
582
583            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
584            sage: rc = RSACryptosystem()
585            sage: rc.calculate_keys(13, 21, False)
586            ((273, 17), (273, 113))
587
588        The ``d`` in the private key should be the multiplicative inverse
589        of ``e`` mod ``\phi(n)``::
590
591            sage: from sage.crypto.public_key.rsa_cryptosystem import RSACryptosystem
592            sage: rc = RSACryptosystem()
593            sage: p = next_prime(ZZ.random_element(50, 100)); q = next_prime(ZZ.random_element(150, 200))
594            sage: public, private = rc.calculate_keys(p, q)
595            sage: n = public[0]; e = public[1]; d = private[1]
596            sage: (e * d) % euler_phi(n)
597            1
598
599        """
600        if p == q:
601            raise ValueError("p and q must be distinct.")
602        # Unsure of the following comment:
603        # Unfortunately, we cannot enforce the primeness of ``p`` and ``q``,
604        # since primeness cannot be efficiently verified for large primes.::
605        if enforce_primes and ((not is_prime(p)) or (not is_prime(q))):
606            raise ValueError("p and q must be primes.")
607
608        n = p * q
609        # Compute the Euler Characteristic of ``n``
610        # We can compute this efficiently because we know ``p`` and ``q``
611        phi_n = (p - 1) * (q - 1)
612
613        # Chooses an ``e`` relative prime to ``phi_n``
614        e = self.choose_exponent(phi_n)
615
616        # Generate a number ``d`` such that ``de = 1 mod (\phi(n))``
617        # ``d`` serves as our decryption key, contained in the private key;
618        # it is the multiplicative inverse of ``e``
619
620        # Get the multiplicative inverse of ``e mod (\phi(n))``
621        d = power_mod(e, -1, phi_n)
622
623        private_key = (n, d)
624        public_key = (n, e)
625        return (public_key, private_key)