Opened 9 years ago

Closed 8 years ago

#8469 closed enhancement (fixed)

add "Number Theory and the RSA Public Key Cryptosystem" to "Thematic Tutorials"

Reported by: mvngu Owned by: mvngu
Priority: major Milestone: sage-4.7.2
Component: documentation Keywords: RSA, public-key cryptosystem, sd32
Cc: malb Merged in: sage-4.7.2.alpha3
Authors: Minh Van Nguyen Reviewers: Pablo Angulo, Rob Beezer, Martin Albrecht
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by rbeezer)

Add the document Number Theory and the RSA Public Key Cryptosystem to the documentation category "Thematic Tutorials". The original proposal can be found on sage-devel and sage-combinat-devel.

Notes: The current ticket needs to be coordinated with #8470.

Prerequisites: #8465

Apply:

  1. trac_8469-rsa-rebase.patch
  2. trac_8469-review-rebased.patch
  3. trac_8469-rsa-bibliography.patch

Attachments (7)

trac_8469_add_a_space.patch (751 bytes) - added by pang 9 years ago.
trac_8469_review.patch (5.2 KB) - added by pang 9 years ago.
trac_8469_review_final.patch (6.4 KB) - added by pang 9 years ago.
trac_8469-rsa.patch (19.1 KB) - added by mvngu 9 years ago.
based on Sage 4.5.2.rc0
trac_8469-review-rebased.patch (3.8 KB) - added by mvngu 9 years ago.
trac_8469-rsa-rebase.patch (18.2 KB) - added by rbeezer 8 years ago.
trac_8469-rsa-bibliography.patch (2.2 KB) - added by rbeezer 8 years ago.

Download all attachments as: .zip

Change History (25)

comment:1 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:2 Changed 9 years ago by mvngu

  • Description modified (diff)
  • Summary changed from add "Number Theory and the RSA Public Key Cryptosystem" to "Sage HOWTOs" to add "Number Theory and the RSA Public Key Cryptosystem" to "Thematic Tutorials"

comment:3 Changed 9 years ago by mvngu

  • Authors set to Minh Van Nguyen
  • Description modified (diff)
  • Status changed from new to needs_review

comment:4 Changed 9 years ago by mjordan7

Looks good and builds fine. Nice job! ~Mark

comment:5 follow-up: Changed 9 years ago by pang

Two comments:

  • In this tutorial, euler_phi(n) is called several times. The whole security of RSA lies in the fact that euler_phi takes a long time if you don't know the factorization. I'd suggest using a variable:
phi = (p-1)*(q-1)

When I've taught about RSA, I've used big primes:

p = next_prime(randint(10^100,10^101))
q = next_prime(randint(10^100,10^101))

and euler_phi would take for ever, of course. If this is reasonable to you, I'll be glad to write a patch, of course.

  • A missing space was generating a minor problem with latex. I attach a patch only for that, waiting for your opinions on the first item.

Changed 9 years ago by pang

comment:6 Changed 9 years ago by pang

  • Reviewers set to pang

comment:7 in reply to: ↑ 5 Changed 9 years ago by mvngu

Replying to pang:

If this is reasonable to you, I'll be glad to write a patch, of course.

That would be nice. Thank you.

  • A missing space was generating a minor problem with latex. I attach a patch only for that

Your patch looks OK to me.

Also, could you put your real name in the "Reviewer(s):" field? That way, it makes it easier to credit you for your contribution.

Changed 9 years ago by pang

comment:8 Changed 9 years ago by pang

  • Reviewers changed from pang to Pablo Angulo

The last patch includes the previous one (I can't find a wat to delete it).

Changed 9 years ago by pang

comment:9 Changed 9 years ago by pang

Only the last patch is needed. Sorry for the noise.

Changed 9 years ago by mvngu

based on Sage 4.5.2.rc0

Changed 9 years ago by mvngu

comment:10 Changed 9 years ago by mvngu

When applying the previous version of my patch on top of Sage 4.5.2.rc0, I got the following failure:

[mvngu@sage sage-main]$ hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/ticket/8469/trac_8469-rsa.patch && hg qpush 
adding trac_8469-rsa.patch to series file
applying trac_8469-rsa.patch
patching file doc/en/thematic_tutorials/index.rst
Hunk #1 FAILED at 13
1 out of 1 hunks FAILED -- saving rejects to file doc/en/thematic_tutorials/index.rst.rej
patch failed, unable to continue (try -v)
patch failed, rejects left in working dir
errors during apply, please fix and refresh trac_8469-rsa.patch

I have rebased my patch against Sage 4.5.2.rc0 in order to resolve the above failure.

The content of pang's patch trac_8469_review_final.patch is mostly OK, but the way the patch itself is structured is frowned upon. From the way it looks, I guess that the patch was put together by concatenating many patches together into one file. That's not how you should put patches together. Use Mercurial queue to concatenate patches into one patch. I have done this and uploaded an updated version of pang's patch, which also fixes some typos found in his original patch. For reference, here are the fixed typos:

  • doc/en/thematic_tutorials/numtheory_rsa.rst

    a b  
    295295pseudo-random integer uniformly distributed within the closed interval
    296296`[0, n-1]`. 
    297297
    298 We can compute the value `\varphi(n)` calling the sage function
    299 ``euler_phi(n)``, but for arbitrary large prime numbers `p` and `q`,
     298We can compute the value `\varphi(n)` by calling the sage function
     299``euler_phi(n)``, but for arbitrarily large prime numbers `p` and `q`,
    300300this can take an enormous amount of time. Indeed, the private key
    301301can be quickly deduced from the public key once you know `\varphi(n)`,
    302302so it is an important part of the security of the RSA cryptosystem that

Pang's updated patch and the typo fixes are all rolled into one patch. See the ticket description for instructions on applying the relevant patches.

For ticket to be closed, the following must happen:

  1. Someone needs to sign off on trac_8469-rsa.patch. This is my patch, so it requires a reviewer other than myself.
  2. Someone needs to sign off on trac_8469-review-rebased.patch. This is pang's original patch together with some typo fixes by me. I'm happy with pang's content. But someone other than myself needs to go over the fixes I included in this updated patch.

comment:11 Changed 9 years ago by mvngu

  • Description modified (diff)

comment:12 Changed 8 years ago by davidloeffler

Apply trac_8469-rsa.patch, trac_8469-review-rebased.patch

(for patchbot)

comment:13 Changed 8 years ago by mariah

  • Status changed from needs_review to needs_work

I suspect that this patch needs to be rebased. When I tried to apply trac_8469-rsa.patch to sage-4.7.rc3 I got

sage: hg_sage.apply("/home/mariah/trac_8469-rsa.patch")
cd "/home/mariah/sage/sage-4.7.rc3-x86_64-Linux-core2-fc-review-8469/devel/sage" && hg status
cd "/home/mariah/sage/sage-4.7.rc3-x86_64-Linux-core2-fc-review-8469/devel/sage" && hg status
cd "/home/mariah/sage/sage-4.7.rc3-x86_64-Linux-core2-fc-review-8469/devel/sage" && hg import   "/home/mariah/trac_8469-rsa.patch"
applying /home/mariah/trac_8469-rsa.patch
patching file doc/en/thematic_tutorials/index.rst
Hunk #1 FAILED at 16
1 out of 1 hunks FAILED -- saving rejects to file doc/en/thematic_tutorials/index.rst.rej
abort: patch failed to apply
sage:

comment:14 Changed 8 years ago by rbeezer

  • Description modified (diff)
  • Reviewers changed from Pablo Angulo to Pablo Angulo, Rob Beezer
  • Status changed from needs_work to needs_info

This all looks very good. I have posted a rebase of the main patch, it was just a matter of getting the table of contents aligned with new additions.

The "Menezes" citation appears twice, it seems to be in the bibliography for the Lie group stuff, so that needs to be removed.

The RSA bibliography appears as a section of its own at the same level as the different topics. Maybe it should just be added directly into the new file of RSA material at the end? (In other words, not in its own file that is included at a level I think is one too high.)

I am at Bug Days 32 and this is on the list of priority tickets. I can make a patch rearranging the bibliography or I can review a change. If there is interest, please respond and let me know which approach to take.

Rob

Changed 8 years ago by rbeezer

Changed 8 years ago by rbeezer

comment:15 Changed 8 years ago by rbeezer

  • Cc malb added
  • Description modified (diff)
  • Status changed from needs_info to needs_review

Forgot to post the rebased patch. That is fixed.

"rebase" patch: removes RSA bibliography file from top-level. Reviewer should check that there is no "bibliography.html" at the same level as the four or five other tutorial files. Still fixes rebasing problem.

"bibliography" patch: moves RSA bibliography to the end of the actual tutorial file. Removed duplicate citation from the Lie group bibliography file.

comment:16 Changed 8 years ago by malb

  • Reviewers changed from Pablo Angulo, Rob Beezer to Pablo Angulo, Rob Beezer, Martin Albrecht
  • Status changed from needs_review to positive_review

I read the patches and skimmed the produced HTML which suffices for me to give a positive review.

comment:17 Changed 8 years ago by was

  • Keywords sd32 added

comment:18 Changed 8 years ago by leif

  • Merged in set to sage-4.7.2.alpha3
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.