Sage: Ticket #11565: RSA Cryptosystem
https://trac.sagemath.org/ticket/11565
<p>
The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. The security depends on the difficulty of factoring the product of large primes.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/11565
Trac 1.2Ajeesh RavindranSun, 03 Jul 2011 11:26:27 GMTattachment set
https://trac.sagemath.org/ticket/11565
https://trac.sagemath.org/ticket/11565
<ul>
<li><strong>attachment</strong>
set to <em>rsa_cryptosystem.py</em>
</li>
</ul>
<p>
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!!!
</p>
TicketAjeesh RavindranSun, 03 Jul 2011 11:27:52 GMTowner, component changed
https://trac.sagemath.org/ticket/11565#comment:1
https://trac.sagemath.org/ticket/11565#comment:1
<ul>
<li><strong>owner</strong>
changed from <em>tbd</em> to <em>Minh Van Nguyen</em>
</li>
<li><strong>component</strong>
changed from <em>PLEASE CHANGE</em> to <em>cryptography</em>
</li>
</ul>
TicketAjeesh RavindranSun, 03 Jul 2011 14:12:18 GMTdescription, milestone changed
https://trac.sagemath.org/ticket/11565#comment:2
https://trac.sagemath.org/ticket/11565#comment:2
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11565?action=diff&version=2">diff</a>)
</li>
<li><strong>milestone</strong>
changed from <em>sage-4.7.2</em> to <em>sage-4.7.1</em>
</li>
</ul>
TicketTevin JosephSun, 03 Jul 2011 16:55:37 GMT
https://trac.sagemath.org/ticket/11565#comment:3
https://trac.sagemath.org/ticket/11565#comment:3
<p>
well done, keep working
</p>
TicketLeif LeonhardySun, 03 Jul 2011 18:52:07 GMTdescription, author changed
https://trac.sagemath.org/ticket/11565#comment:4
https://trac.sagemath.org/ticket/11565#comment:4
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11565?action=diff&version=4">diff</a>)
</li>
<li><strong>author</strong>
changed from <em>ajeesh r</em> to <em>Ajeesh Ravindran</em>
</li>
</ul>
TicketNils BruinSun, 03 Jul 2011 20:27:31 GMT
https://trac.sagemath.org/ticket/11565#comment:5
https://trac.sagemath.org/ticket/11565#comment:5
<p>
Just a few quick observations:
</p>
<ul><li>What is the intended use of the code one included in Sage? If it's for teaching you would probably want to expose more of the details. In fact, for educational purposes it's probably better to do the whole construction "in the open" instead of wrapping it in a class, unless the educational part is wrapping things in classes. For actual cryptographic use, one would probably prefer a whole protocol library. The algorithm is a very small part of deploying cryptography in a secure manner.
</li></ul><ul><li>In your code you call <code>euler_phi(n)</code> to compute the private key d from e. Since the public key is (n,e), anyone could do that same calculation. That means that if it is doable for you to compute the private part of the key, then it is also doable for anyone. You don't have an advantage. (HINT: the key is that euler_phi computes the factorisation of n. If you would make sure that 2<strong>p-1 and 2</strong>q-1 are actually prime, you would know the factorization of n and hence euler_phi(n). But you should not call euler_phi(n), because that throws away your advantage).
</li></ul>
TicketAjeesh RavindranMon, 04 Jul 2011 01:48:39 GMT
https://trac.sagemath.org/ticket/11565#comment:6
https://trac.sagemath.org/ticket/11565#comment:6
<p>
Thank you nbruin. This was a valid information for me. I will correct it very soon. Keep supporting me in future also
</p>
TicketJeroen DemeyerTue, 13 Aug 2013 15:35:53 GMTmilestone changed
https://trac.sagemath.org/ticket/11565#comment:7
https://trac.sagemath.org/ticket/11565#comment:7
<ul>
<li><strong>milestone</strong>
changed from <em>sage-5.11</em> to <em>sage-5.12</em>
</li>
</ul>
TicketFor batch modificationsThu, 30 Jan 2014 21:20:52 GMTmilestone changed
https://trac.sagemath.org/ticket/11565#comment:8
https://trac.sagemath.org/ticket/11565#comment:8
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.1</em> to <em>sage-6.2</em>
</li>
</ul>
TicketFor batch modificationsTue, 06 May 2014 15:20:58 GMTmilestone changed
https://trac.sagemath.org/ticket/11565#comment:9
https://trac.sagemath.org/ticket/11565#comment:9
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.2</em> to <em>sage-6.3</em>
</li>
</ul>
TicketFor batch modificationsSun, 10 Aug 2014 16:51:03 GMTmilestone changed
https://trac.sagemath.org/ticket/11565#comment:10
https://trac.sagemath.org/ticket/11565#comment:10
<ul>
<li><strong>milestone</strong>
changed from <em>sage-6.3</em> to <em>sage-6.4</em>
</li>
</ul>
TicketPeter StoryWed, 25 Mar 2015 22:21:16 GMTattachment set
https://trac.sagemath.org/ticket/11565
https://trac.sagemath.org/ticket/11565
<ul>
<li><strong>attachment</strong>
set to <em>rsa_cryptosystem.2.py</em>
</li>
</ul>
<p>
Major rewrite of the module, with the goal of a pedagogical implementation.
</p>
TicketPeter StoryWed, 25 Mar 2015 22:28:56 GMT
https://trac.sagemath.org/ticket/11565#comment:11
https://trac.sagemath.org/ticket/11565#comment:11
<p>
I've rewritten ajeeshr's original module, to address nbruin's concerns and to have an implementation that is simpler and better suited for teaching. In summary, I made the following changes:
</p>
<ul><li>Eliminated calls to euler_phi. These were unnecessary, because we know the primes, and $\phi(pq) = (p-1)*(q-1)$.
</li><li>Made primality checks optional (but enabled by default).
</li><li>Combined the methods that generate public and private keys into a single method, calculate_keys. This is more representative of how actual keygen programs are used.
</li><li>Stopped using Mersenne Primes. The original author seems to have been using them to allow the encoding of large messages, but I don't think this is necessary for a teaching module.
</li><li>Added more accessible references.
</li></ul>
TicketKarl-Dieter CrismanSat, 28 Mar 2015 00:35:15 GMT
https://trac.sagemath.org/ticket/11565#comment:12
https://trac.sagemath.org/ticket/11565#comment:12
<p>
Hi! Can you make this a branch on the Trac serve with the <a class="ext-link" href="http://www.sagemath.org/doc/developer/#git-for-sage-development"><span class="icon"></span>git workflow</a>? Also, what connection will this have to the (thus far) only currently implemented public system in that folder in Sage? Finally, should this be globally imported, or imported the way that one is? Thanks!
</p>
TicketPeter StorySat, 28 Mar 2015 14:27:24 GMTbranch set
https://trac.sagemath.org/ticket/11565#comment:13
https://trac.sagemath.org/ticket/11565#comment:13
<ul>
<li><strong>branch</strong>
set to <em>u/peter.story/rsa_cryptosystem</em>
</li>
</ul>
TicketPeter StorySat, 28 Mar 2015 14:50:20 GMTcommit set
https://trac.sagemath.org/ticket/11565#comment:14
https://trac.sagemath.org/ticket/11565#comment:14
<ul>
<li><strong>commit</strong>
set to <em>4b667369410afa8400b009b8f4f5cc0ad968c78c</em>
</li>
</ul>
<p>
In the associated branch, I've added RSACryptosystem to the global namespace. Is there any reason why this is a bad idea?
</p>
<p>
BlumGoldwasser, the public key system already included with Sage, has a very similar API to RSACryptosystem. There are a few differences:
</p>
<ul><li>In RSACryptosystem, I combined the <code>public_key</code> and <code>private_key</code> methods into a single <code>calculate_keys</code> method. This is because the exponent <code>e</code> would have had to be calculated independently (and identically) in the two methods. In BlumGoldwasser, the keys can more naturally be calculated independently.
</li><li>I am missing a <code>random_key</code> method. This would be an easy addition, but I'm not sure how valuable it is; for RSACryptosystem it would only need to find two primes, and plug them into <code>calculate_keys</code>.
</li></ul><p>
BlumGoldwasser doc:
<a class="ext-link" href="http://www.sagemath.org/doc/reference/cryptography/sage/crypto/public_key/blum_goldwasser.html"><span class="icon"></span>http://www.sagemath.org/doc/reference/cryptography/sage/crypto/public_key/blum_goldwasser.html</a>
</p>
TicketPeter StorySat, 28 Mar 2015 14:52:15 GMTauthor changed
https://trac.sagemath.org/ticket/11565#comment:15
https://trac.sagemath.org/ticket/11565#comment:15
<ul>
<li><strong>author</strong>
changed from <em>Ajeesh Ravindran</em> to <em>Peter Story, Ajeesh Ravindran</em>
</li>
</ul>
TicketPeter StorySat, 28 Mar 2015 14:53:29 GMTdescription changed
https://trac.sagemath.org/ticket/11565#comment:16
https://trac.sagemath.org/ticket/11565#comment:16
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11565?action=diff&version=16">diff</a>)
</li>
</ul>
TicketLeif LeonhardySat, 28 Mar 2015 16:05:01 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/11565#comment:17
https://trac.sagemath.org/ticket/11565#comment:17
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-6.6</em>
</li>
</ul>
<p>
Presumably rather 6.7, but there's no new milestone yet.
</p>
<hr />
<p>
By definition, <em>factoring large primes</em> is exceptionally easy... ;-)
</p>
TicketPeter StorySat, 28 Mar 2015 16:10:20 GMTdescription changed
https://trac.sagemath.org/ticket/11565#comment:18
https://trac.sagemath.org/ticket/11565#comment:18
<ul>
<li><strong>description</strong>
modified (<a href="/ticket/11565?action=diff&version=18">diff</a>)
</li>
</ul>
<p>
Haha, good catch!
Changed the description to "factoring <strong>the product</strong> of large primes."
</p>
TicketVincent DelecroixMon, 30 Mar 2015 16:10:18 GMTstatus changed
https://trac.sagemath.org/ticket/11565#comment:19
https://trac.sagemath.org/ticket/11565#comment:19
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<ol><li>If <code>__init__</code> is empty, you can just <strong>avoid</strong> it.
</li></ol><ol start="2"><li>What is the point of having the comparison implemented?! Moreover, the way you did is completely wrong
<pre class="wiki">+ if self.__repr__() == other.__repr__():
+ return True
</pre>The following will return <code>True</code>
<pre class="wiki">sage: rc1 = RSACryptosystem()
sage: a = str(rc1)
sage: rc1 == a
</pre></li></ol><ol start="3"><li>In the function <code>encrypt</code> in the section <code>TESTS</code> you repeat many times the definition of <code>rc</code> as well as the computation of the keys. Just remove all these duplication.
</li></ol>
TicketNils BruinMon, 30 Mar 2015 16:26:07 GMT
https://trac.sagemath.org/ticket/11565#comment:20
https://trac.sagemath.org/ticket/11565#comment:20
<p>
Before people spend too much time on the code here: Is there a reasonable scenario that justifies having this in the library? We're not going to use it for industrial encryption applications, so I think people think it's for teaching. However, when I teach RSA, the students have to *see* the exponentiation and the construction of the moduli. At that point, the fact that you can do square-and-multiply to do the exponentiation efficiently is already a worthwhile revelation for them.
</p>
<p>
So having that all wrapped up in library routines is no help at all. They're going to have these things in front of them on a worksheet.
</p>
<p>
Do people have some lower level scenario in mind where it's sufficient for the students to play around with a crypto "black box"?
</p>
<p>
I don't mind if it gets included for a good reason, but if the code here isn't going to be used properly and frequently in teaching I'd rather not have it in there, because it will take away from the excitement that students get from implementing their own RSA if there's already such an implementation available in sage.
</p>
TicketKarl-Dieter CrismanWed, 01 Apr 2015 01:47:23 GMT
https://trac.sagemath.org/ticket/11565#comment:21
https://trac.sagemath.org/ticket/11565#comment:21
<p>
Trivial comment: a number of things in the documentation are marked as code
</p>
<pre class="wiki">``561=3*11*17``
</pre><p>
that should probably be marked as math markup
</p>
<pre class="wiki">`561=3*11*17`
</pre><p>
or something along those lines.
</p>
<hr />
<p>
Nils' argument presumably applies to nearly all the stuff in the <code>crypto</code> folder, though, doesn't it? Certainly the only current public-key one.
</p>
<p>
I guess it depends on whether you are going to ask students to <em>code</em> things like DH or RSA, or only to "do" them. For my own purposes, I think it could be useful to have a well-commented implementation of this (assuming this is in fact a well-commented implementation) that could be used by any given instructor who may not want to/have the expertise to implement something well. (Mathematicians, not programmers.)
</p>
<p>
That said, I agree that the utility of this is clearly as a pedagogical tool, so a lot of examples of it (and/or why RSA could fail to be particularly secure with some choices of <code>p</code> and <code>q</code>, etc.) along with examples of "brute-force" or other attacks would seem to be the main use of this. So that one can demonstrate such things without having to recode it all from scratch - built-in, as it were.
</p>
TicketgitMon, 06 Apr 2015 14:05:08 GMTcommit changed
https://trac.sagemath.org/ticket/11565#comment:22
https://trac.sagemath.org/ticket/11565#comment:22
<ul>
<li><strong>commit</strong>
changed from <em>4b667369410afa8400b009b8f4f5cc0ad968c78c</em> to <em>3c8e43ae07f14dbc6c42f42c5e91cfee5b3f2e45</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=3c8e43ae07f14dbc6c42f42c5e91cfee5b3f2e45"><span class="icon"></span>3c8e43a</a></td><td><code>Corrected the implementation of ``__eq__``.</code>
</td></tr></table>
TicketPeter StoryMon, 06 Apr 2015 14:44:00 GMT
https://trac.sagemath.org/ticket/11565#comment:23
https://trac.sagemath.org/ticket/11565#comment:23
<p>
@vdelecroix, thanks for bringing the <code>__init__</code> and <code>__eq__</code> methods to my attention. I copied the implementations from ajeeshr, who had copied them from <code>BlumGoldwasser</code>, the other <code>PublicKeyCryptosystem</code>. The reason <code>BlumGoldwasser</code> implements them is to override the <code>PublicKeyCryptosystem</code> implementations, which is necessary because <code>BlumGoldwasser</code> doesn't initialize its superclass properly (it may be helpful to read the code for the Cryptosystem class's <code>__init__</code> and <code>__eq__</code>, which can be found on lines 104-212 in cryptosystem.py).
</p>
<p>
I modified <code>__eq__</code> to fix the issue you identified. Now, the method just compares the class of the two objects being compared. This is a change that should also be made to <code>BlumGoldwasser</code>.
</p>
<p>
However, <code>__init__</code> will be trickier to fix properly. According to the <code>Cryptosystem</code> class, which <code>RSACryptosystem</code> inherits through <code>PublicKeyCryptosystem</code>, I should be passing the following arguments to my superclass's <code>__init__</code> method: <code>plaintext_space, ciphertext_space, key_space, block_length=1, period=None</code>. Without fixing this, inherited methods like the following will fail:
</p>
<pre class="wiki"> sage: rc = RSACryptosystem()
sage: rc.key_space()
AttributeError: 'RSACryptosystem' object has no attribute '_key_space'
</pre><p>
The following values seem to make the most sense to me, but I'm not certain:
</p>
<ul><li>plaintext_space = group of all integers
</li><li>ciphertext_space = group of all integers
</li><li>key_space: I have no idea how to specify this one as a group.
</li></ul><p>
Ideally, I would give plaintext_space and ciphertext_space as integers mod n, instead of the group of all integers. However, this would require giving the RSACryptosystem class state, recording public and private keys internally. This would have the effect of making it more opaque, since users wouldn't need to explicitly pass keys to encrypt and decrypt. Thus, I think it makes sense to keep plaintext_space and ciphertext_space as the groups of all integers. Comments on this would be appreciated.
</p>
<p>
Side note: <code>__init__</code> will also need to be fixed in <code>BlumGoldwasser</code>:
</p>
<pre class="wiki"> sage: from sage.crypto.public_key.blum_goldwasser import BlumGoldwasser
sage: bs = BlumGoldwasser()
sage: bs.key_space()
AttributeError: 'BlumGoldwasser' object has no attribute '_key_space'
</pre><p>
Also, as suggested by kcrisman, I corrected several formatting issues with the documentation. Thanks to vdelecroix, I removed unnecessary redeclarations of variables in my tests, except where redeclaring improved readability.
</p>
TicketKarl-Dieter CrismanFri, 01 May 2015 17:34:47 GMT
https://trac.sagemath.org/ticket/11565#comment:24
https://trac.sagemath.org/ticket/11565#comment:24
<p>
A few comments on this:
</p>
<ul><li>You can open a separate ticket for the <code>BlumGoldwasser</code> stuff, no need to fix it here.
</li><li>You should use the <code>TestSuite</code> functionality, I guess, to ensure that all such possible errors are caught.
</li><li>One possible option would be to make those spaces be <code>NotImplementedError</code> or something, and then document it as such.
</li><li>Another one is that, considering
<pre class="wiki">class PublicKeyCryptosystem(Cryptosystem):
r"""
The base class for asymmetric or public-key cryptosystems.
"""
</pre>is the entirety of the constructor for <code>PublicKeyCryptosystem</code>, and that several of the systems in the <code>crypto/</code> folder don't even inherit from <code>Cryptosystem</code>, one could just ignore this altogether and not inherit from it if there seems to be no reason to.
</li><li>Or you could use integers.
</li><li>Or you could build it in but then <code>RSACryptosystem(n)</code> would be needed. That's sort of like how the other ciphers require you to put in the alphabet, so it isn't totally farfetched.
</li></ul>
TicketPeter StoryWed, 13 May 2015 13:38:06 GMT
https://trac.sagemath.org/ticket/11565#comment:25
https://trac.sagemath.org/ticket/11565#comment:25
<p>
Of the options you described, I think the best is simply to not inherit from <code>PublicKeyCryptosystem</code> or <code>Cryptosystem</code>. If I inherit from either of them, implementing the <code>plaintext_space</code>, <code>ciphertext_space</code>, etc. would require accepting <code>p</code> and <code>q</code> when an <code>RSACryptosystem</code> object is initialized. However, since this is a pedagogical module, that is undesirable, since I want to keep <code>calculate_keys(p, q)</code> explicit.
</p>
<p>
Consequently, in this next patch I have removed inheritance from <code>PublicKeyCryptosystem</code>.
</p>
TicketgitWed, 13 May 2015 13:44:12 GMTcommit changed
https://trac.sagemath.org/ticket/11565#comment:26
https://trac.sagemath.org/ticket/11565#comment:26
<ul>
<li><strong>commit</strong>
changed from <em>3c8e43ae07f14dbc6c42f42c5e91cfee5b3f2e45</em> to <em>c45c4dd7966114639a5d39b1e526729235d14e7a</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=c45c4dd7966114639a5d39b1e526729235d14e7a"><span class="icon"></span>c45c4dd</a></td><td><code>Stopped inheriting from PublicKeyCryptosystem.</code>
</td></tr></table>
Ticket