RSA Cryptosystem

[ce88ad43-83c8-48d1-b184-77ab128e244b]

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.

CC: nguyenminh2@gmail.com

Component: cryptography

Keywords: RSA, public key encryption

Author: Peter Story, Ajeesh Ravindran

Branch/Commit: u/peter.story/rsa_cryptosystem @ c45c4dd

Issue created by migration from https://trac.sagemath.org/ticket/11565

[ce88ad43-83c8-48d1-b184-77ab128e244b]

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!!!

[ce88ad43-83c8-48d1-b184-77ab128e244b]

comment:1

Attachment: rsa_cryptosystem.py.gz

[ce88ad43-83c8-48d1-b184-77ab128e244b]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-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. Generate a pair of public/private keys. Use the public key to encrypt a plaintext. Then decrypt the resulting ciphertext using the private key. Finally, compare the decrypted message with the original plaintext. This is based on the thesis by Minh Van Nguyen about number theory and RSA encryption algorithm. i didnt know how secure it was, so I would like to share this contribution with all of you.
+The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. This was based on the thesis published by minh nguyen about Number theory. The security depends on factoring mersenne primes.  

[e192eba7-dfa6-4939-8dd2-141e97330a7c]

comment:3

well done, keep working

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

Description changed:

--- 
+++ 
@@ -1 +1,2 @@
-The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. This was based on the thesis published by minh nguyen about Number theory. The security depends on factoring mersenne primes.  
+The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. This was based on the thesis published by Minh Nguyen about Number Theory. The security depends on factoring Mersenne primes.
+

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

Changed author from ajeesh r to Ajeesh Ravindran

[nbruin]

comment:5

Just a few quick observations:

• 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.

• In your code you call euler_phi(n) 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 2p-1 and 2q-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).

[ce88ad43-83c8-48d1-b184-77ab128e244b]

comment:6

Thank you nbruin. This was a valid information for me. I will correct it very soon. Keep supporting me in future also

[peterstory]

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

[peterstory]

comment:11

Attachment: rsa_cryptosystem.2.py.gz

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:

• Eliminated calls to euler_phi. These were unnecessary, because we know the primes, and $\phi(pq) = (p-1)*(q-1)$.
• Made primality checks optional (but enabled by default).
• 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.
• 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.
• Added more accessible references.

[kcrisman]

comment:12

Hi! Can you make this a branch on the Trac serve with the git workflow? 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!

[peterstory]

Branch: u/peter.story/rsa_cryptosystem

[peterstory]

comment:14

In the associated branch, I've added RSACryptosystem to the global namespace. Is there any reason why this is a bad idea?

BlumGoldwasser, the public key system already included with Sage, has a very similar API to RSACryptosystem. There are a few differences:

• In RSACryptosystem, I combined the public_key and private_key methods into a single calculate_keys method. This is because the exponent e would have had to be calculated independently (and identically) in the two methods. In BlumGoldwasser, the keys can more naturally be calculated independently.
• I am missing a random_key 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 calculate_keys.

BlumGoldwasser doc: http://www.sagemath.org/doc/reference/cryptography/sage/crypto/public_key/blum_goldwasser.html

[peterstory]

Commit: 4b66736

[peterstory]

Changed author from Ajeesh Ravindran to Peter Story, Ajeesh Ravindran

[peterstory]

Description changed:

--- 
+++ 
@@ -1,2 +1 @@
-The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. This was based on the thesis published by Minh Nguyen about Number Theory. The security depends on factoring Mersenne primes.
-
+The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. The security depends on the difficulty of factoring large primes.

[83660e46-0051-498b-a8c1-f7a7bd232b5a]

comment:17

Presumably rather 6.7, but there's no new milestone yet.

---

By definition, factoring large primes is exceptionally easy... ;-)

[peterstory]

Description changed:

--- 
+++ 
@@ -1 +1 @@
-The Rivest, Shamir and Adleman encryption system is a widely accepted public key encryption scheme. The security depends on the difficulty of factoring large primes.
+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.

[peterstory]

comment:18

Haha, good catch! Changed the description to "factoring the product of large primes."

[videlec]

comment:19

1. If __init__ is empty, you can just avoid it.

2. What is the point of having the comparison implemented?! Moreover, the way you did is completely wrong

   + if self.__repr__() == other.__repr__():
   +     return True

   The following will return True

   sage: rc1 = RSACryptosystem()
   sage: a = str(rc1)
   sage: rc1 == a

3. In the function encrypt in the section TESTS you repeat many times the definition of rc as well as the computation of the keys. Just remove all these duplication.

[nbruin]

comment:20

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.

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.

Do people have some lower level scenario in mind where it's sufficient for the students to play around with a crypto "black box"?

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.

[kcrisman]

comment:21

Trivial comment: a number of things in the documentation are marked as code

``561=3*11*17``

that should probably be marked as math markup

`561=3*11*17`

or something along those lines.

---

Nils' argument presumably applies to nearly all the stuff in the crypto folder, though, doesn't it? Certainly the only current public-key one.

I guess it depends on whether you are going to ask students to code 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.)

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 p and q, 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.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 4b66736 to 3c8e43a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

3c8e43a

Corrected the implementation of ``__eq__``.

[peterstory]

comment:23

@videlec, thanks for bringing the __init__ and __eq__ methods to my attention. I copied the implementations from ajeeshr, who had copied them from BlumGoldwasser, the other PublicKeyCryptosystem. The reason BlumGoldwasser implements them is to override the PublicKeyCryptosystem implementations, which is necessary because BlumGoldwasser doesn't initialize its superclass properly (it may be helpful to read the code for the Cryptosystem class's __init__ and __eq__, which can be found on lines 104-212 in cryptosystem.py).

I modified __eq__ 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 BlumGoldwasser.

However, __init__ will be trickier to fix properly. According to the Cryptosystem class, which RSACryptosystem inherits through PublicKeyCryptosystem, I should be passing the following arguments to my superclass's __init__ method: plaintext_space, ciphertext_space, key_space, block_length=1, period=None. Without fixing this, inherited methods like the following will fail:

  sage: rc = RSACryptosystem()
  sage: rc.key_space()
  AttributeError: 'RSACryptosystem' object has no attribute '_key_space'

The following values seem to make the most sense to me, but I'm not certain:

• plaintext_space = group of all integers
• ciphertext_space = group of all integers
• key_space: I have no idea how to specify this one as a group.

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.

Side note: __init__ will also need to be fixed in BlumGoldwasser:

  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'

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.

[kcrisman]

comment:24

A few comments on this:

• You can open a separate ticket for the BlumGoldwasser stuff, no need to fix it here.
• You should use the TestSuite functionality, I guess, to ensure that all such possible errors are caught.
• One possible option would be to make those spaces be NotImplementedError or something, and then document it as such.
• Another one is that, considering

class PublicKeyCryptosystem(Cryptosystem):
    r"""
    The base class for asymmetric or public-key cryptosystems.
    """

is the entirety of the constructor for PublicKeyCryptosystem, and that several of the systems in the crypto/ folder don't even inherit from Cryptosystem, one could just ignore this altogether and not inherit from it if there seems to be no reason to.

• Or you could use integers.
• Or you could build it in but then RSACryptosystem(n) 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.

[peterstory]

comment:25

Of the options you described, I think the best is simply to not inherit from PublicKeyCryptosystem or Cryptosystem. If I inherit from either of them, implementing the plaintext_space, ciphertext_space, etc. would require accepting p and q when an RSACryptosystem object is initialized. However, since this is a pedagogical module, that is undesirable, since I want to keep calculate_keys(p, q) explicit.

Consequently, in this next patch I have removed inheritance from PublicKeyCryptosystem.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c45c4dd

Stopped inheriting from PublicKeyCryptosystem.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 3c8e43a to c45c4dd