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

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.

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.
In part however it is not understanding all of the information that my
vision absorbs. I
f you see what I mean?

With my numerous questions.

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

Yes.

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>

2. Compute n = pq
3. 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:
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:
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: