Opened 9 years ago

Last modified 9 years ago

#9726 needs_work enhancement

An educational RSA crpytosystem

Reported by: gauravluthra Owned by: mvngu
Priority: minor Milestone:
Component: cryptography Keywords: RSA, educational
Cc: kcrisman Merged in:
Authors: Gaurav Luthra(gauravluthra) Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

A stand alone function srsa.py to implement an educational version of the RSA cryptosystem.This is the first native version of the RSA in SAGE.

Attachments (3)

srsa.patch (2.5 KB) - added by gauravluthra 9 years ago.
trac_9726-srsa.patch (2.3 KB) - added by mvngu 9 years ago.
srsa.2.patch (11.5 KB) - added by gauravluthra 9 years ago.

Download all attachments as: .zip

Change History (10)

Changed 9 years ago by gauravluthra

comment:1 Changed 9 years ago by gauravluthra

  • Status changed from new to needs_review

comment:2 Changed 9 years ago by wdj

  • Status changed from needs_review to needs_work

I am really happy that this is here. Although RSA is almost trivial to implement, it is nice to have a version that anyone (eg, a very lazy or tired student) can just use without having to set up anything. However, I would prefer that Minh eventually comment on this since he knows the crypto class structure of sage better than I do.

Note that examples are completely missing from the docstrings, so this cannot go in "as is" and I am marking this as "needs work".

However, thank you for creating this!

comment:3 Changed 9 years ago by mvngu

Rather than listing what needs to be done, let me try to write a reviewer patch that would bring gauravluthra's implementation up to the standard that is expected of any code that goes into the Sage library. In case you haven't done so, please refer to the Developer's Guide for guidelines on contributing to Sage.

The name RSA for the class is misleading because the stated purpose of this class is to be an implementation of RSA for educational purposes. We don't want to give the misleading impression that srsa.py can be used for industrial purposes. I'll change that name to ToyRSA in my reviewer patch. By the way, what does the letter "s" in "srsa.py" mean?

PS: There's a simplified version of RSA called Kid RSA that is suitable for teaching cryptography to high school students. See this book (which is in progress) for details.

Changed 9 years ago by mvngu

comment:4 Changed 9 years ago by mvngu

The patch trac_9726-srsa.patch is the same as srsa.patch, but here are the crucial differences:

  • Put the ticket number in the commit message.
  • Get rid of Windows newline convention. Use Unix style end of line characters.

Changed 9 years ago by gauravluthra

comment:5 Changed 9 years ago by wdj

Is this ready for review? If so. what patches should be applied in what order?

comment:6 Changed 9 years ago by mvngu

Some problems with srsa.2.patch:

  • What if I want n to be odd? In that case, I get an error:
    sage: from sage.crypto.public_key.srsa import RSA
    sage: RSA(11, 2)
    ---------------------------------------------------------------------------
    TypeError                                 Traceback (most recent call last)
    
    /dev/shm/mvngu/sage-4.5.3.alpha0/<ipython console> in <module>()
    
    /dev/shm/mvngu/sage-4.5.3.alpha0/local/lib/python2.6/site-packages/sage/crypto/public_key/srsa.pyc in __init__(self, n, e)
        152             1234567890
        153         """
    --> 154         p = random_prime(2**((n/2)-1), 2**(n/2))
        155         q = random_prime(2**((n/2)-1), 2**(n/2))
        156         while( q == p ):
    
    /dev/shm/mvngu/sage-4.5.3.alpha0/local/lib/python2.6/site-packages/sage/rings/arith.pyc in random_prime(n, proof, lbound)
       1139     from sage.structure.proof.proof import get_flag
       1140     proof = get_flag(proof, "arithmetic")
    -> 1141     n = ZZ(n)
       1142     if n < lbound:
       1143         raise ValueError, "n must be greater than lbound: %s"%(lbound)
    
    /dev/shm/mvngu/sage-4.5.3.alpha0/local/lib/python2.6/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6407)()
    
    /dev/shm/mvngu/sage-4.5.3.alpha0/local/lib/python2.6/site-packages/sage/structure/coerce_maps.so in sage.structure.coerce_maps.NamedConvertMap._call_ (sage/structure/coerce_maps.c:4053)()
    
    /dev/shm/mvngu/sage-4.5.3.alpha0/local/lib/python2.6/site-packages/sage/symbolic/expression.so in sage.symbolic.expression.Expression._integer_ (sage/symbolic/expression.cpp:4034)()
    
    TypeError: unable to convert x (=16*sqrt(2)) to an integer
    

  • Running doctests over srsa.py fails with the following message:
    [mvngu@sage sage-4.5.3.alpha0]$ ./sage -t -long devel/sage-main/sage/crypto/public_key/srsa.py 
    sage -t -long "devel/sage-main/sage/crypto/public_key/srsa.py"
    Exception raised by doctesting framework. Use -verbose for details.
             [1.8 s]
     
    ----------------------------------------------------------------------
    The following tests failed:
    
    
            sage -t -long "devel/sage-main/sage/crypto/public_key/srsa.py" # Exception from doctest framework
    Total time for all tests: 1.8 seconds
    

This patch needs a lot of work and a lot of redesign.

comment:7 Changed 9 years ago by kcrisman

  • Cc kcrisman added
Note: See TracTickets for help on using tickets.