[WIP]: Rsa keygen #733

est31 · 2018-12-06T08:08:54Z

Opened the PR so that I can discuss with @briansmith about the code. Nothing works yet. DON'T MERGE!

List of tasks:

Implement division by small primes as suggested here
Implement miller-rabin primality test based on FIPS 186-4 C.3.1
Tests for the miller-rabin primality test
Implement FIPS 186-4 section B 3.3 algorithm to obtain (p,q) prime pair
Use (p,q) to create the needed p,q,dP,dQ,qInv,r_i,d_i,t_i
DER formatting of the created key
Implement primitive for multiplication
Implement primitive for inverse modulo m

Important reading:

FIPS 186-4: https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.186-4.pdf
https://eprint.iacr.org/2018/749
https://tools.ietf.org/html/draft-mavrogiannopoulos-pkcs8-validated-parameters-00
Formatting of the keys: https://tools.ietf.org/html/rfc5958 and https://tools.ietf.org/html/rfc3447#section-3

Fixes #219

est31 · 2018-12-06T11:00:13Z

src/rsa/key_generation.rs

+        for _ in 1 .. a {
+            // Step 4.5.1
+            // TODO figure out how to make this compile
+            //z_elem = bigint::elem_squared(z_elem, &w_modulus.as_partial());


@briansmith do you know how this can be made compile? Right now I'm getting sth like:

--> src/rsa/key_generation.rs:87:22 | 87 | z_elem = bigint::elem_squared(z_elem, &w_modulus.as_partial()); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected enum `arithmetic::montgomery::Unencoded`, found enum `arithmetic::montgomery::RInverse` | = note: expected type `rsa::bigint::Elem<_, arithmetic::montgomery::Unencoded>` found type `rsa::bigint::Elem<_, arithmetic::montgomery::RInverse>`

For now: multiply z_elem by w_modulus.oneRR before the loop.

Later: Refactor elem_exp_consttime so that it returns an Elem<R> instead of Elem<Unencoded> by moving the into_unencoded() to the caller.

briansmith · 2018-12-06T18:25:05Z

crypto/fipsmodule/bn/bn.c

+ * The licence and distribution terms for any publically available version or
+ * derivative of this code cannot be changed.  i.e. this code cannot simply be
+ * copied and put under another distribution licence
+ * [including the GNU Public Licence.] */


Please add a commit that removes all the code from this file, and the other new imported files, that you didn't use.

Is it okay if I do that once I'm done with the PR? Don't know what else will be needed from the files :).

briansmith · 2018-12-06T18:26:51Z

crypto/internal.h

@@ -370,4 +368,20 @@ static inline uint64_t from_be_u64(uint64_t x) {
  return x;
 }

+static inline void *OPENSSL_memmove(void *dst, const void *src, size_t n) {


Everywhere you see OPENSSL_memmove and OPENSSL_memset being used, just use memmove and memset.

briansmith · 2018-12-06T18:32:51Z

crypto/limbs/limbs.c

@@ -99,6 +99,11 @@ Limb LIMBS_less_than_limb(const Limb a[], Limb b, size_t num_limbs) {
  return constant_time_select_w(lo, hi, lo);
 }

+void LIMBS_sub_limb(Limb r[], const Limb a[], const Limb b,
+               size_t num_limbs) {
+  limbs_sub_limb(r, a, b, num_limbs);


Replace this with

void LIMBS_odd_sub_one(Limb r[], size_t num_limbs) { assert(num_limbs > 0); assert(!LIMBS_are_even(r, num_limbs)); r[0] &= ~1; }

briansmith · 2018-12-06T18:34:27Z

src/limb.rs

+}
+
+#[cfg(feature = "rsa_keygen")]
+pub fn limbs_copy(r: &mut [Limb], a: &[Limb]) {


You can do the copying in pure Rust code. (In ring, we can copy secret values from one place to another in Rust, we just don't do any arithmetic in Rust get.)

briansmith · 2018-12-06T18:34:49Z

src/limb.rs

+
+
+#[cfg(feature = "rsa_keygen")]
+pub fn limbs_rshift(r: &mut [Limb], n: u16) {


This should have secret_shift in the name.

briansmith · 2018-12-06T18:35:48Z

src/rsa/bigint.rs

@@ -67,7 +67,7 @@ struct Width<M> {
 }

 /// All `BoxedLimbs<M>` are stored in the same number of limbs.
-struct BoxedLimbs<M> {
+pub struct BoxedLimbs<M> {


Let's make the primality test code a submodule of bigint so that we don't need to increase the visibility of things in bigint.

briansmith · 2018-12-06T18:36:58Z

src/rsa/key_generation.rs

@@ -0,0 +1,147 @@
+// Copyright 2018 Brian Smith.


If you copied some of my code, please keep this copyright line. Please add your own copyright line.

briansmith · 2018-12-06T18:38:46Z

src/rsa/key_generation.rs

+/// Implementation of the algorithm as it
+/// is described in FIPS 186-4 C.3.1
+fn miller_rabin_test(
+    w: &[u64],


You have written this whole thing in terms of Limb but it would be a lot clearer to write it in terms of bigint::Nonnegative, I think.

briansmith · 2018-12-06T18:42:25Z

src/rsa/key_generation.rs

+    // Step 1.
+    let mut w_m1 = vec![0; w.len()];
+    limb::limbs_sub_limb(&mut w_m1, w, 1);
+    let a = limb::limbs_count_low_zero_bits(&w_m1);


// for w: &Nonnegative let w_minus_1 = w.odd_minus_1()?; let a = w.trailing_zeros();

briansmith · 2018-12-06T18:48:32Z

src/rsa/key_generation.rs

+    // preparation
+    let boxed_w = bigint::BoxedLimbs::<()>::minimal_width_from_unpadded(&w);
+    let w_modulus = bigint::Modulus::from_boxed_limbs(boxed_w)?.0;
+    let boxed_m = bigint::BoxedLimbs::<()>::minimal_width_from_unpadded(&m);


see Modulus::from_nonnegative_with_bit_length().

briansmith · 2018-12-06T18:52:37Z

src/rsa/key_generation.rs

+            unsafe {
+                let b_mut_ptr = (&mut b[..]).as_mut_ptr() as * mut u8;
+                let b_mut_slice = core::slice::from_raw_parts_mut(b_mut_ptr, b.len() * 8);
+                rng.fill(b_mut_slice)?;


This should probably be factored out into a impl Elem { fn random(rng: &SecureRandom) -> Result<Self, error::Unspecified> } method.

briansmith · 2018-12-06T18:57:40Z

src/rsa/key_generation.rs

+            // TODO figure out how to make this compile
+            //z_elem = bigint::elem_squared(z_elem, &w_modulus.as_partial());
+            // Step 4.5.2
+            if limb::limbs_equal_limbs_consttime(&z_elem.limbs, &w_m1) == LimbMask::True {


You will need to convert w_m1 to an Elem<W> and then use the Elem comparison functions.

briansmith · 2018-12-06T18:58:52Z

src/rsa/key_generation.rs

+                continue;
+            }
+            // Step 4.5.1
+            if z_elem.is_one() {


You will need to create a value oneR: Elem<W, R> with value 1 * w_modulus.oneRR and then compare using the element comparison functions.

briansmith · 2018-12-06T19:00:57Z

src/rsa/key_generation.rs

+///
+/// Implementation of the algorithm as it
+/// is described in FIPS 186-4 C.3.1
+fn miller_rabin_test(


I think this function's type should be something like like fn miller_rabin_test<M: Prime>(w: Nonnegative, iterations: u32, rng: &SecureRandom) -> Result<Modulus<M>, error::Unspecified>.

What should the returned modulus contain? Will we need that value somewhere? To me it seems that only bool yes/no output is needed.

What should the returned modulus contain? Will we need that value somewhere? To me it seems that only bool yes/no output is needed.

At least, for example, we need to calculate q**-1 (mod p) to construct the RSA key. IIUC, this function already constructs the Modulus for the prime so we might as well return it. OTOH, if the function doesn't end up constructing the Modulus already then we can just return a ().

briansmith · 2018-12-06T19:06:55Z

OK, I can see now that this is going to be a lot of work from both of us. Before we do any more work, let's clarify the IPR part:

Who is the copyright holder for new the code that contributing? Please add the Copyright lines that says who the copyright holder is, to the tops of the files with new code before we continue.
Do you have the permission of the copyright holder to contribute this code?
Please add the contributor statement at https://github.com/briansmith/ring#contributing to the end of every commit message (you can skip the ones that only add unmodified BoringSSL code).

briansmith · 2018-12-06T19:15:17Z

In order for me to effectively review this code, we need to refactor it into at least two parts: low-level routines and high-level routines. The M-R test itself should be a high-level routine that takes a Nonnegative, does some operations on Nonnegatives, Elems, and Moduluss, and returns a Modulus. There probably should not be any mention of Limb or u64 in the M-R code at all.

Anything that deals with Limb or &[Limb] or BoxedLimbs needs to be encapsulated in a new extension of the bigint API. For example, subtracting 1 from an odd number m to produce an even m - 1 needs to be a method of Nonnegative. Counting the trailing zeros of a Nonnegative needs to be a method of Nonnegative. When possible, use the standard Rust names for these functions, e.g. trailing_zeros().

est31 · 2018-12-07T10:28:46Z

Ready again for review @briansmith .

est31 · 2018-12-09T15:38:47Z

Rebased. ATM blocked on getting advice: #219 (comment)

I agree to license my contributions to each file under the terms given at the top of each file I changed.

We still need to do a few more checks to generate the (p,q) primes in a valid fashion. I agree to license my contributions to each file under the terms given at the top of each file I changed.

I agree to license my contributions to each file under the terms given at the top of each file I changed.

Some lower level stuff is still left TODO. I agree to license my contributions to each file under the terms given at the top of each file I changed.

I agree to license my contributions to each file under the terms given at the top of each file I changed.

est31 · 2018-12-25T10:33:27Z

Rebased. Multiplication still left to do, waiting on input by @briansmith .

I agree to license my contributions to each file under the terms given at the top of each file I changed.

est31 · 2019-01-01T21:07:44Z

@briansmith any news? you said:

I can probably come up with a special case thing for the N = P * Q calculation.

I stopped my work on porting the multiplication functions due to that, waiting for your input. Should I continue?

briansmith · 2019-01-02T00:27:45Z

I stopped my work on porting the multiplication functions due to that, waiting for your input. Should I continue?

I don't know when I'll be able to write the multiplication code. It is fine to use bn_mul_normal from BoringSSL in the meantime if that would unblock you.

est31 · 2019-01-02T03:06:29Z

Thanks for the info. You have a concrete idea how to implement it. That's great to hear! I guess I'll wait then.

briansmith · 2019-01-03T23:17:32Z

For future reference: https://eprint.iacr.org/2018/367.pdf

briansmith · 2019-02-09T16:56:14Z

@est31 Are you planning to finish this? If so, please email me at brian@briansmith.org to discuss the IPR stuff. Otherwise, let's just close this.

est31 · 2019-02-09T17:10:34Z

@briansmith no my intention is not to close this PR. I've put already a ton of time into it and closing would mean that the time was wasted which I don't want it to be. I've also sent you an E-Mail.

briansmith · 2019-02-14T03:18:37Z

Regarding the divisibility check, check out section "3.2 Fast Divisibility Check with a Single Multiplication" in https://arxiv.org/pdf/1902.01961.pdf. Note in particular that reference [5] may or may not a better starting point than the new method that paper presents.

est31 · 2019-02-14T16:13:40Z

@briansmith do you think I need to implement that before merging? Otherwise I'd leave it as a post-merge project.

est31 · 2019-02-23T08:08:05Z

@briansmith is the IPR stuff cleared now? I haven't gotten any E-Mail replies.

est31 · 2019-09-04T02:30:59Z

Still no reaction...

So now I stand before the choice of bumping this yet again, waiting more time, or simply closing for being ghosted by the maintainer. I choose to close it, because I'm doubtful it'll ever be merged: At the start of this PR, it got tons of reactions by the maintainer and judging from that the general view was that this feature is wanted and the PR welcome. The atmosphere was quite positive until this comment which suggested to close the PR without any reason. It took me quite by surprise because I was waiting for @briansmith to contribute their part like they said above, and now I'm expected to finish it while the IPR situation is still not clear. There has neither been a yes nor a no in all the months since that communication and this kind of treatment is simply not okay. Also, given that I have invested so much time into my PR, the suggestion to "just close this" is quite insulting.

Of course, ultimately it's their project and up to them to accept or reject stuff.

I've considered closing this multiple times already but every time I stopped in the last moment, hoping that maybe if I wait a little there'd be a reply or something. After all I'm throwing away a ton of work and invested time here. What a shame :/.

In retrospect, I probably shouldn't have started this project without previously doing smaller PRs to change readmes or whatever to probe how receptive the maintainer is. I used to do this but in this case, I let my guard down. My fault. Ultimately, I don't need RSA keygen as much as I used to, as I made it for rcgen which is using multiple other encryption algorithms now. But it would still have been cool to have contributed such a major thing to a crypto library.

That your contribution gets rejected is always a risk of open source but it still hurts every time, especially as I have spent a good deal of time with it. Time to move on.

PS: For all the people who want to add RSA key generation support, first a warning. I don't know why the maintainer has ghosted me, maybe it's because of IPR, maybe it's because the maintainer doesn't like RSA and hopes to be able to wait until RSA is deprecated, never having to worry about key generation at all. Who knows what the reason is. So before you waste time, please make sure you are ready to take the risk of your change being rejected like my PR was. I also suggest not looking at my PR or building onto it unless there are confirmations by the maintainer that this is okay (I'd personally be okay with it). Sorry that I couldn't help you.

est31 changed the title ~~[WIP]: Rsa keygen new~~ [WIP]: Rsa keygen Dec 6, 2018

est31 force-pushed the rsa_keygen_new branch 2 times, most recently from c6005ff to 9cd2288 Compare December 6, 2018 08:13

est31 commented Dec 6, 2018

View reviewed changes

est31 mentioned this pull request Dec 6, 2018

Add RSA key generation #219

Open

est31 force-pushed the rsa_keygen_new branch from 96824c5 to 9dc496b Compare December 6, 2018 11:23

briansmith reviewed Dec 6, 2018

View reviewed changes

est31 force-pushed the rsa_keygen_new branch 2 times, most recently from f4a92ba to 6e0cdf1 Compare December 7, 2018 10:28

est31 force-pushed the rsa_keygen_new branch 3 times, most recently from 34aa5c3 to 97f3c18 Compare December 9, 2018 15:37

est31 force-pushed the rsa_keygen_new branch from 97f3c18 to 3a05856 Compare December 9, 2018 15:41

est31 added 10 commits December 25, 2018 11:29

No more unsafe

7ce70c0

I agree to license my contributions to each file under the terms given at the top of each file I changed.

Compilation fixes due to rebase

9db7635

I agree to license my contributions to each file under the terms given at the top of each file I changed.

Add (p,q) prime generation with a few TODOs inside

2e8e4e7

We still need to do a few more checks to generate the (p,q) primes in a valid fashion. I agree to license my contributions to each file under the terms given at the top of each file I changed.

Add a key generation function with some TODOs to the public API

43c9ba2

I agree to license my contributions to each file under the terms given at the top of each file I changed.

Add div.c from boringssl commit 7494428

f7d1b58

Add a modulo function from C

98bf7cf

I agree to license my contributions to each file under the terms given at the top of each file I changed.

Zero is being serialized in a different way

5e8a240

I agree to license my contributions to each file under the terms given at the top of each file I changed.

Finish the DER generation

e9aca9c

Some lower level stuff is still left TODO. I agree to license my contributions to each file under the terms given at the top of each file I changed.

Add gcd_extra.c from boringssl commit 7494428

d10e746

Implement computing the inverse modulo

2688ecd

I agree to license my contributions to each file under the terms given at the top of each file I changed.

est31 force-pushed the rsa_keygen_new branch from 666a1db to 6ae912e Compare December 25, 2018 10:30

Implement the remaining checks for the FIPS algo

8f2bd17

I agree to license my contributions to each file under the terms given at the top of each file I changed.

est31 force-pushed the rsa_keygen_new branch from 6ae912e to 8f2bd17 Compare December 25, 2018 10:47

est31 mentioned this pull request Jun 3, 2019

crypto and TLS implementation support breard-r/acmed#2

Open

barzamin mentioned this pull request Jul 23, 2019

Use native-tls to make Windows / Mac development easier rustodon/rustodon#246

Open

est31 closed this Sep 4, 2019

This was referenced Jan 4, 2021

Implement webcrypto APIs. denoland/deno#1891

Closed

feat(op_crates/crypto): Introduce Web Crypto API denoland/deno#8984

Closed

cpu mentioned this pull request Dec 13, 2023

feature request: RSA key generation support aws/aws-lc-rs#296

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[WIP]: Rsa keygen #733

[WIP]: Rsa keygen #733

est31 commented Dec 6, 2018 •

edited

est31 Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

est31 Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

briansmith Dec 6, 2018

est31 Dec 6, 2018

briansmith Dec 6, 2018

briansmith commented Dec 6, 2018 •

edited

briansmith commented Dec 6, 2018 •

edited

est31 commented Dec 7, 2018

est31 commented Dec 9, 2018

est31 commented Dec 25, 2018

est31 commented Jan 1, 2019

briansmith commented Jan 2, 2019

est31 commented Jan 2, 2019

briansmith commented Jan 3, 2019

briansmith commented Feb 9, 2019

est31 commented Feb 9, 2019

briansmith commented Feb 14, 2019

est31 commented Feb 14, 2019

est31 commented Feb 23, 2019

est31 commented Sep 4, 2019



		#[cfg(feature = "rsa_keygen")]
		pub fn limbs_rshift(r: &mut [Limb], n: u16) {

[WIP]: Rsa keygen #733

[WIP]: Rsa keygen #733

Conversation

est31 commented Dec 6, 2018 • edited

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

briansmith commented Dec 6, 2018 • edited

briansmith commented Dec 6, 2018 • edited

est31 commented Dec 7, 2018

est31 commented Dec 9, 2018

est31 commented Dec 25, 2018

est31 commented Jan 1, 2019

briansmith commented Jan 2, 2019

est31 commented Jan 2, 2019

briansmith commented Jan 3, 2019

briansmith commented Feb 9, 2019

est31 commented Feb 9, 2019

briansmith commented Feb 14, 2019

est31 commented Feb 14, 2019

est31 commented Feb 23, 2019

est31 commented Sep 4, 2019

est31 commented Dec 6, 2018 •

edited

briansmith commented Dec 6, 2018 •

edited

briansmith commented Dec 6, 2018 •

edited