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:  sage4.7.2 
Component:  documentation  Keywords:  RSA, publickey cryptosystem, sd32 
Cc:  malb  Merged in:  sage4.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 )
Add the document Number Theory and the RSA Public Key Cryptosystem to the documentation category "Thematic Tutorials". The original proposal can be found on sagedevel and sagecombinatdevel.
Notes: The current ticket needs to be coordinated with #8470.
Prerequisites: #8465
Apply:
Attachments (7)
Change History (25)
comment:1 Changed 9 years ago by
 Description modified (diff)
comment:2 Changed 9 years ago by
 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
 Description modified (diff)
 Status changed from new to needs_review
comment:4 Changed 9 years ago by
comment:5 followup: ↓ 7 Changed 9 years ago by
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 = (p1)*(q1)
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
comment:6 Changed 9 years ago by
 Reviewers set to pang
comment:7 in reply to: ↑ 5 Changed 9 years ago by
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
comment:8 Changed 9 years ago by
 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
comment:9 Changed 9 years ago by
Only the last patch is needed. Sorry for the noise.
Changed 9 years ago by
comment:10 Changed 9 years ago by
When applying the previous version of my patch on top of Sage 4.5.2.rc0, I got the following failure:
[mvngu@sage sagemain]$ hg qimport http://trac.sagemath.org/sage_trac/rawattachment/ticket/8469/trac_8469rsa.patch && hg qpush adding trac_8469rsa.patch to series file applying trac_8469rsa.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_8469rsa.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 295 295 pseudorandom integer uniformly distributed within the closed interval 296 296 `[0, n1]`. 297 297 298 We can compute the value `\varphi(n)` calling the sage function299 ``euler_phi(n)``, but for arbitrar y large prime numbers `p` and `q`,298 We can compute the value `\varphi(n)` by calling the sage function 299 ``euler_phi(n)``, but for arbitrarily large prime numbers `p` and `q`, 300 300 this can take an enormous amount of time. Indeed, the private key 301 301 can be quickly deduced from the public key once you know `\varphi(n)`, 302 302 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:
 Someone needs to sign off on trac_8469rsa.patch. This is my patch, so it requires a reviewer other than myself.
 Someone needs to sign off on trac_8469reviewrebased.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
 Description modified (diff)
comment:12 Changed 8 years ago by
Apply trac_8469rsa.patch, trac_8469reviewrebased.patch
(for patchbot)
comment:13 Changed 8 years ago by
 Status changed from needs_review to needs_work
I suspect that this patch needs to be rebased. When I tried to apply trac_8469rsa.patch to sage4.7.rc3 I got
sage: hg_sage.apply("/home/mariah/trac_8469rsa.patch") cd "/home/mariah/sage/sage4.7.rc3x86_64Linuxcore2fcreview8469/devel/sage" && hg status cd "/home/mariah/sage/sage4.7.rc3x86_64Linuxcore2fcreview8469/devel/sage" && hg status cd "/home/mariah/sage/sage4.7.rc3x86_64Linuxcore2fcreview8469/devel/sage" && hg import "/home/mariah/trac_8469rsa.patch" applying /home/mariah/trac_8469rsa.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
 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
Changed 8 years ago by
comment:15 Changed 8 years ago by
 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 toplevel. 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
 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
 Keywords sd32 added
comment:18 Changed 8 years ago by
 Merged in set to sage4.7.2.alpha3
 Resolution set to fixed
 Status changed from positive_review to closed
Looks good and builds fine. Nice job! ~Mark