Opened 12 years ago

Closed 10 years ago

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

Reported by: Owned by: mvngu mvngu major sage-4.7.2 documentation RSA, public-key cryptosystem, sd32 malb sage-4.7.2.alpha3 Minh Van Nguyen Pablo Angulo, Rob Beezer, Martin Albrecht N/A

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:

### comment:1 Changed 12 years ago by mvngu

• Description modified (diff)

### comment:2 Changed 12 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 12 years ago by mvngu

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

### comment:4 Changed 12 years ago by mjordan7

Looks good and builds fine. Nice job! ~Mark

### comment:5 follow-up: ↓ 7 Changed 12 years ago by pang

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

### comment:6 Changed 12 years ago by pang

• Reviewers set to pang

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

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.

### comment:8 Changed 12 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).

### comment:9 Changed 12 years ago by pang

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

### Changed 11 years ago by mvngu

based on Sage 4.5.2.rc0

### comment:10 Changed 11 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
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 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 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 11 years ago by mvngu

• Description modified (diff)

### comment:12 Changed 11 years ago by davidloeffler

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

(for patchbot)

### comment:13 Changed 11 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 10 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

### comment:15 Changed 10 years ago by rbeezer

• 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 10 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.