# Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm

*From*: unruh <unruh@xxxxxxxxxxxxxxxxxxxxxxx>*Date*: Thu, 07 Apr 2011 17:36:15 GMT

On 2011-04-07, ping pong <mosescuadro@xxxxxxxx> wrote:

"Francois Grieu" <fgrieu@xxxxxxxxx> wrote in message

news:4d9de112$0$20750$426a74cc@xxxxxxxxxxxxxxx

On 07/04/2011 16:42, ping pong wrote:

Using a previous advice on correct notation and algebra:

All parameters adhering to the RSA standard .

I am hoping I have now achieved a correct staring point for signature

creation in RSA.

As Advised:

1. Pick two large equal sized primes p and q

Question 2:

Sorry: my vision is pretty bad.

I likely cannot locate it in Handbook of applied cryptography (from now

on HAC) after trying many times with maximum effort!

What exactly is the recommendation for the requirement that follows:

1. Generate two large distinct random primes p and q, each roughly the

same size (see 11.3.2)

It is of interest to me.

Can you shed some light on that requirement?

First, let's examine the size requirements.

By definition, a positive integer of b bits is in range

[2^(b-1) .. (2^b)-1].

Checking formulation:

Let b = 2 bits

Formula gives:

(2^(2-1) .. (2^2) -1)

(2 .. 3)

Why not: (0, 1, 2, 3)?

or [0 .... (2^b) - 1]

Because 1 is only 1 bit long, and 0 is zero bits long.

Is the lower limit to be questioned?

Question is all you want. This is the definition of what it means to say

a number is b bits long.

I am not sure at this moment?

In some contexts, p and q must be exactly the same size.

For example, ANSI X9.31 specifies that for a key of 1024+256*s bits,

p and q must be in range [2^(511.5+128*s) .. 2^(512+128*s)-1];

it follows that p and q must be exactly 512+128*s bits.

In some other contexts (e.g. PKCS#1), p and q are allowed to

have slightly different size; typically, the difference is chosen

small (1 or 2 bits).

I had no idea that different contexts had different size requirements for p

and q.

requirements for a key to fall under some specification. Not context.

But I am learning.

I am trying to identify the "basis" version of the RSA algorithm that is

considered "secure".

It's interesting that sometimes p and q are the same bit size? Sometimes

not, by a small bit difference - a couple of "lower bits" - I presume?

In a "basis" study of RSA, which version is normally used? Equality or

small difference between p and q?

It does not matter.

And I wondered about the logic underpinning this decision?

Can some light be shed on these considerations?

You are getting distracted. Certain standards require that the key obey

certain restriction. They have nothing to do with RSA. Their only

purpose is to make the definition clear and to make sure that the system

is hard to break. If one of the keys is a very different length than the

other, RSA becomes easier to break.

Remember that an integer of length n has 2^(n-1) possibilities. So there

are lots and lots of p, q of length n.

Adding in possibilities of length n-1 say only increases this by 50%

(actually slightly more because of the distribution of primes, but that

is straining at gnats)

These factors seem to be subtleties that I cannot readily read in the

standard books,

Because they have nothing to do with RSA.

Or have escaped me in the complexity of the matter

Or my vision is failing me.

I try not to skip text but inevitably I do.

By virtue of making text recognition as painless as possible.

This is partly why I have to read and re-read.

In part however it is not understanding all of the information that my

vision absorbs. I

f you see what I mean?

So please be patient.

With my numerous questions.

.... But I am rambling on .....

Yes.

So, I shall stop and await your reply..

The RSA cryptosystem works just the same, but its implementation

in the CRT variant (especially in hardware) is slightly more

difficult.

Then, the "random" requirement.

Again, depending on context, one might want to use a true or

pseudo-random source.

And there are several techniques to go from a random bitstring

to a random prime; its primality might be probable or provable;

so other characteristics might be required (e.g. "strong" prime,

for some definition of strong).

A free, modern, recognized, almost self-contained standard for

RSA key generation is in

<http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf>

Start reading in appendix B.3

2. Compute n = pq3. Pick a value of e such that gcd(e, lcm(p-1,q-1)) = 1

4. Compute d = 1/e (mod lcm(p-1, q-1))

5. Return (e, n) as the public key and return (d, n) as the private key.

What follows is my real interest:

As Advised:

A signature is then:

1. Compute h the hash of your message = h(m)

2. Compute the padded version of h (see PKCS #1 for instance) =

p(h(m)) = m'

3. Compute s = m'^d mod n

4. Return s= m'^d mod n as the signature

5. Or for my purpose, return:

EQ 1: s = m'^d mod (p * q)

Question 3:

May I ask:

Is EQ 1, the correct RSA signature creation starting point -

(ignoring the likely notational defects)?

This is *ONE* correct RSA signature generation method.

There are many others. In particular:

- in some (relatively rare) contexts (including ISO/IEC 9796-2

with some set of options), an additional step replaces s by s'

with s' = min(s, n-s), making s one bit less than n. If about

half of your signatures are wrong, likely you are hit by

this.

- in many contexts, a final step transforms s or s' into a byte

string of fixed size. If a small fraction of your signatures

are wrong, likely you are hit by this.

Francois Grieu

**Follow-Ups**:

**References**:**2nd try for a "correct" starting point for signature gcreation in RSA algorithm***From:*ping pong

**Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm***From:*Francois Grieu

**Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm***From:*ping pong

- Prev by Date:
**Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm** - Next by Date:
**Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm** - Previous by thread:
**Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm** - Next by thread:
**Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm** - Index(es):