Browse Prior Art Database

System for M of M Component Part RSA Digital Signature Generation

IP.com Disclosure Number: IPCOM000118583D
Original Publication Date: 1997-Apr-01
Included in the Prior Art Database: 2005-Apr-01
Document File: 4 page(s) / 138K

Publishing Venue

IBM

Related People

Johnson, DB: AUTHOR [+2]

Abstract

Disclosed is a method whereby m users in a network using asymmetric cryptography can separately calculate different component part digital signatures for a given message. When combined, the m component part digital signatures will form a single complete signature. The method is based on the security principle of split knowledge and split control of a secret.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 38% of the total text.

System for M of M Component Part RSA Digital Signature Generation

      Disclosed is a method whereby m users in a network using
asymmetric cryptography can separately calculate different component
part digital signatures for a given message.  When combined, the m
component part digital signatures will form a single complete
signature.  The method is based on the security principle of split
knowledge and split control of a secret.

      For example, a company may want two parties to digitally sign
a purchase order but not allow any one of the two parties to sign by
themselves.  Only after both parties sign the purchase order can a
valid complete verifiable digital signature be constructed.

      An RSA digital signature (e.g., based on the ISO 9796 Digital
Signature Standard) takes a formatted data block and raises it to the
power S modulo N, where S is the secret exponent and N is the public
modulus, both of which together comprise the components of an RSA
private key.  To verify the digital signature, one takes the result
of the prior step and raises it to the power V modulo N, where V is
the public exponent and N is (again) the public modulus, both of
which together comprise the components of an RSA public key.  The
modulus N is composed of two large primes.  V is an odd number and
typically is selected as either 3 or (2**16)+1, to increase
performance.  (The notation 2**16 denotes 2 raised to the power 16.)
The value S is then determined using an RSA key generation algorithm
that depends on V and N.  For security reasons, S has the property
that the greatest common divisor of S and N is 1, i.e., GCD(S,N) = 1.

      The described invention assumes that during RSA private
key/public key pair generation the secret exponent S is split into
two or more component parts S1, S2, ...  etc., such that the sum of
the S1, S2, is equal to S.  The public key, consisting of the public
modulus N and the public exponent V, is distributed with integrity to
interested parties.  The component parts of S are also distributed.
A first user is given the private key component S1 and modulus N.  A
second user is given the private key component S2 and modulus N, etc.
The first user knows only S1, N and V.  The second user knows only
S2, N and  V, etc.  No one besides the first user knows S2, no one
besides the second user knows S2, etc.  The value of S is destroyed
after the private key component parts are have been distributed.
Methods for secure component part secret exponent distribution are
described below.

      Consider the following example in which, for simplicity, the
number of users m = 2.  Let H represent a cryptographically strong
one-way hash function such as the NIST Secure Hash Algorithm One
(SHA-1) or the IBM MDC-2 algorithm.  If user 1 desires to sign a
message M1, he  calculates the first component part of the digital
signature as H(M1)**S1  mod N and sends the result to user 2.  The
value H(M1)**S1 m...