Opened 8 years ago

Last modified 4 years ago

#11565 needs_work enhancement

RSA Cryptosystem — at Version 18

Reported by: ajeeshr Owned by: mvngu
Priority: major Milestone: sage-6.6
Component: cryptography Keywords: RSA, crypto, public key encryption
Cc: nguyenminh2@… Merged in:
Authors: Peter Story, Ajeesh Ravindran Reviewers:
Report Upstream: N/A Work issues:
Branch: u/peter.story/rsa_cryptosystem (Commits) Commit: 4b667369410afa8400b009b8f4f5cc0ad968c78c
Dependencies: Stopgaps:

Description (last modified by peter.story)

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.

Change History (20)

Changed 8 years ago by ajeeshr

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

comment:1 Changed 8 years ago by ajeeshr

  • Component changed from PLEASE CHANGE to cryptography
  • Owner changed from tbd to mvngu

comment:2 Changed 8 years ago by ajeeshr

  • Description modified (diff)
  • Milestone changed from sage-4.7.2 to sage-4.7.1

comment:3 Changed 8 years ago by tevinjoseph

well done, keep working

comment:4 Changed 8 years ago by leif

  • Authors changed from ajeesh r to Ajeesh Ravindran
  • Description modified (diff)

comment:5 Changed 8 years ago by nbruin

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

comment:6 Changed 8 years ago by ajeeshr

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

comment:7 Changed 6 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:8 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:10 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

Changed 5 years ago by peter.story

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

comment:11 Changed 5 years ago by peter.story

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.

comment:12 Changed 5 years ago by kcrisman

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!

comment:13 Changed 5 years ago by peter.story

  • Branch set to u/peter.story/rsa_cryptosystem

comment:14 Changed 5 years ago by peter.story

  • Commit set to 4b667369410afa8400b009b8f4f5cc0ad968c78c

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

comment:15 Changed 5 years ago by peter.story

  • Authors changed from Ajeesh Ravindran to Peter Story, Ajeesh Ravindran

comment:16 Changed 5 years ago by peter.story

  • Description modified (diff)

comment:17 Changed 5 years ago by leif

  • Milestone changed from sage-6.4 to sage-6.6
  • Status changed from new to needs_review

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


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

comment:18 Changed 5 years ago by peter.story

  • Description modified (diff)

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

Note: See TracTickets for help on using tickets.