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

*From*: "ping pong" <mosescuadro@xxxxxxxx>*Date*: Sat, 9 Apr 2011 11:45:37 +0930

"unruh" <unruh@xxxxxxxxxxxxxxxxxxxxxxx> wrote in message news:slrnips6hv.pnt.unruh@xxxxxxxxxxxxxxxxxxxxxxxxxx

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

"unruh" <unruh@xxxxxxxxxxxxxxxxxxxxxxx> wrote in message

news:slrniprtgf.gmr.unruh@xxxxxxxxxxxxxxxxxxxxxxxxxx

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.

Sorry about rambling, I am trying to learn o.k.?

I plead for patience.

That's interesting:

You mean, to be, explicit, that the numbers to be considered for p and q

being "prime" shall not be

zero or or one but shall be selected from possibilities between:

2^(b-1) ... 2^b - 1?

They start at 2 when b = 2?

If so that requirement escaped me, and I thank you all for pointing that out

(if that is the cause of the vanishing of 0 and 1 from the list

of possibilities. Please be patient now. These are considerations likely

obvious to you that are new to me with respect to p and q.

Where is the start when b = 512, or 2048?

Since k1 and k2 ( usually called p and q) are to give a number of length 512

or 2048, then p and q should each have length 256 or 1024 respectively.

Ie, be from 2^255 to 2^256-1 each ( or 2^1023 to 2^1024-1 respectively)

Ie, have length 256 or 1024 each.

Confused by what is going on and why?

Length is the number of bits in the number once all leading 0 bits are

discarded. That is the definition of length.

I understand now.

Thanks for that.

.Please be patient with my basic questions.

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

**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

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

**Re: 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:*unruh

- Prev by Date:
**Re: Protecting a client's automated auth secret** - 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):