Browse Prior Art Database

System for M of N Component Part RSA Digital Signature Generation

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

Publishing Venue

IBM

Related People

Johnson, DB: AUTHOR [+2]

Abstract

Disclosed is a method whereby any m of n 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 disclosure is an extension of (*). For example, a company may want any two of three parties to digitally sign a purchase order but not allow any one of the parties to sign by themselves. Only after two parties sign the purchase order can a valid complete verifiable digital signature be constructed.

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

System for M of N Component Part RSA Digital Signature Generation

      Disclosed is a method whereby any m of n 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 disclosure is an
extension of (*).  For example, a company may want any two of three
parties to digitally sign a purchase order but not allow any one of
the parties to  sign by themselves.  Only after two 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 part sets, as follows:
  Set A = (SA1, SA2, ...) such that SA1 + SA2 + ...  = S.
  Set B = (SB1, SB2, ...) such that SB1 + SB2 + ...  = S.
  Set C = (SC1, SC2, ...) such that SC1 + SC2 + ...  = S.
  and so forth as needed.

      As in (*), suitable tests are made to ensure that each
component part secret exponent does not share a factor with the
modulus.  The public key consisting of the public modulus N and
public exponent V are distributed with integrity to interested
parties.  For simplicity, consider the following example in which the
number of users n = 3 and m = 2, that is, any 2 of 3 users can cause
a valid signature to be formed:
  Set SA is calculated as follows: SA = (SA1, SA2) such that
                                    SA1 + SA2 = S.
  Set SB is calculated as follows: SB = (SB1, SB2) such that
                                    SB1 + SB2 = S.
  Set SC is calculated as follows: SC = (SC1, SC2) such that
                                    SC1 + SC2 = S.

    ...