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

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.

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

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.

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

## Relevant Pages

• Re: Weak keys for RSA ?
... Robert D. Silverman RSA Public Key Validation, ... that p,q are so-called strong primes. ... outline how to guard against the Bach/Shallit ... a standard. ...
(sci.crypt)
• Re: RSA keygen recommendations
... promote a contrived key generation process for RSA keys despite the ... value in deterministic key generation, but couldn't they just say seed ... Certicom clearly wanted to keep it from ever becoming a standard. ... The bankers wanted "strong primes" because it gave them a warm fuzzy ...
(sci.crypt)
• Re: RSA Decryption with public key?
... private key by encrypting our data with the private key and giving us back ... The thingy that with RSA often referred as ... "Decryption with public key" is actually a *Signature Verification ... encryption vs signature. ...
(microsoft.public.dotnet.security)
• Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm
... All parameters adhering to the RSA standard. ... I am hoping I have now achieved a correct staring point for signature ... I had no idea that different contexts had different size requirements for p ...
(sci.crypt)
• Re: 2nd try for a "correct" starting point for signature gcreation in RSA algorithm
... All parameters adhering to the RSA standard. ... I am hoping I have now achieved a correct staring point for signature creation in RSA. ... I had no idea that different contexts had different size requirements for p and q. ...
(sci.crypt)