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

[sagetrac-mvngu]

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. attachment: trac_8469-rsa-rebase.patch
2. attachment: trac_8469-review-rebased.patch
3. attachment: trac_8469-rsa-bibliography.patch

CC: @malb

Component: documentation

Keywords: RSA, public-key cryptosystem, sd32

Author: Minh Van Nguyen

Reviewer: Pablo Angulo, Rob Beezer, Martin Albrecht

Merged: sage-4.7.2.alpha3

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

[sagetrac-mvngu]

Author: Minh Van Nguyen

[sagetrac-mjordan7]

comment:4

Looks good and builds fine. Nice job!
~Mark

[sagetrac-pang]

comment:5

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.

[sagetrac-pang]

Reviewer: pang

[sagetrac-pang]

comment:6

Attachment: trac_8469_add_a_space.patch.gz

[sagetrac-mvngu]

comment:7

Replying to @sagetrac-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.

[sagetrac-pang]

Changed reviewer from pang to Pablo Angulo

[sagetrac-pang]

comment:8

Attachment: trac_8469_review.patch.gz

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

[sagetrac-pang]

comment:9

Attachment: trac_8469_review_final.patch.gz

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

[sagetrac-mvngu]

Attachment: trac_8469-rsa.patch.gz

based on Sage 4.5.2.rc0

[sagetrac-mvngu]

comment:10

Attachment: trac_8469-review-rebased.patch.gz

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 https://github.com/sagemath/sage-prod/files/10648450/trac_8469-rsa.patch.gz && 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 attachment: 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:

--- a/doc/en/thematic_tutorials/numtheory_rsa.rst
+++ b/doc/en/thematic_tutorials/numtheory_rsa.rst
@@ -295,8 +295,8 @@
 pseudo-random integer uniformly distributed within the closed interval
 `[0, n-1]`.  
 
-We can compute the value `\varphi(n)` calling the sage function
-``euler_phi(n)``, but for arbitrary large prime numbers `p` and `q`,
+We can compute the value `\varphi(n)` by calling the sage function
+``euler_phi(n)``, but for arbitrarily large prime numbers `p` and `q`,
 this can take an enormous amount of time. Indeed, the private key
 can be quickly deduced from the public key once you know `\varphi(n)`,
 so 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 attachment: trac_8469-rsa.patch. This is my patch, so it requires a reviewer other than myself.
2. Someone needs to sign off on attachment: 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.

[loefflerd]

comment:12

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

(for patchbot)

[sagetrac-mariah]

comment:13

I suspect that this patch needs to be rebased. When I tried to apply attachment: 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:

[rbeezer]

Changed reviewer from Pablo Angulo to Pablo Angulo, Rob Beezer

[rbeezer]

comment:14

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

[rbeezer]

Attachment: trac_8469-rsa-rebase.patch.gz

[rbeezer]

Attachment: trac_8469-rsa-bibliography.patch.gz

[rbeezer]

comment:15

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.

[malb]

comment:16

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

[malb]

Changed reviewer from Pablo Angulo, Rob Beezer to Pablo Angulo, Rob Beezer, Martin Albrecht

[williamstein]

Changed keywords from RSA, public-key cryptosystem to RSA, public-key cryptosystem, sd32

[nexttime]

Merged: sage-4.7.2.alpha3