Re: Please help me to learn some implications of RSA signature creation equation



On Apr 7, 7:38 am, "ping pong" <mosescua...@xxxxxxxx> wrote:
Dear friends

I have already referred to the handbook of applied cryptography as
recommened by one of you (thanks for that):
           http://www.cacr.math.uwaterloo.ca/hac/
The complexity of what is written there has induced me to seek your help.

I wish to be instructed  about some of the implications of the RSA signature
equation (only signature please)  , as in what follows:

eq 1.  s  = ((hash(m)^e) mod n                    %  The book shows hash(m)
as m-squiggle (tilda?)
          where s is a signature
          of a hash of message m
          and  (n, e) is a  public pair
          and k1 and k2 suitable required primes
In fact, the whole equation and its parameters are constrained
according to the  requirements of the RSA algorithm standard.
(if you see what I mean by this?)

I shall have a number of questions and hope that you might be able to
clarify some things for me as we go.
Please be patient o.k.!
              :)
Because even after reading as much as I can
I cannot decode all of the  known and obviously complex implications of  the
RSA signature creation algorithm.

Lets see how we go o.k.?

Question 1:
1.1  I have written k1 and k2 as keys.
Is it correct to view them as keys?

The terminology is non standard but ... assuming n = k1*k2 then yes,
k1/k2 are part of the private key. They're not "keys" in a symmetric
sense [like for AES or CMAC] but simply prime numbers used to form a
composite 'n'.

1.2 . Is it suitable to view this equation as a definition of a cipher
device that employs  "two keys" -  k1, k2.
A 2-key system?

No. And in fact you're missing the whole point of RSA in the first
place. It's a public key system (I know for a fact that HAC covers
the concept of public key crypto in depth... so read up!!!) where you
can hand someone a public key corresponding to your private key.
They're asymmetric in that the private key can do things the public
key cannot.

Typically RSA works as follows

1. Pick two large equal sized primes p and q
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.

In PKCS #1 they specify you compute a few other values for CRT
computations (it speeds up private key operations) but right now
that's all you need to get going.

The system is such that any unit in Z_n can be transformed such that a
== (a^e)^d mod n and vice versa. This allows the private key to
permute a value such that the public key can undo the mapping but
cannot compute the mapping. E.g. given A = a^d mod n, I can compute
'a' from A and the public key, but given 'a' I cannot compute A.

A signature is then

1. Compute h the hash of your message.
2. Compute P the padded version of h (see PKCS #1 for instance)
3. Compute s = P^d mod n
4. Return s as the signature.

Verification is then

1. Compute P = s^e mod n
2. Unpad P to reveal h
3. Compare h against the hash [you computed] of the message claimed
to have been signed.
4. Return valid if the hashes match.

Tom
.