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

*From*: Tom St Denis <tom@xxxxxxx>*Date*: Thu, 7 Apr 2011 05:03:50 -0700 (PDT)

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

.

**Follow-Ups**:

**References**:

- Prev by Date:
**Re: Please help me to learn some implications of RSA signature creation equation** - Next by Date:
**Re: Please help me to learn some implications of RSA signature creation equation** - Previous by thread:
**Re: Please help me to learn some implications of RSA signature creation equation** - Next by thread:
**Re: Please help me to learn some implications of RSA signature creation equation** - Index(es):