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

## Relevant Pages

• Re: RSA breaking vs. factoring
... affects the two possible usages of RSA both for encryption (first public, ... then private key) and for signing ... are identical to encryption, in reverse order. ... Digital signature generation takes an input message (which may be quite ...
(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: Encryption question
... Digital signature is done by applying the ... sender's private key at the message hash. ... has the sender's public key to check. ... >Alice encrypts her email to Bob using his public key. ...
(Security-Basics)