# US 6,731,755 B1 · Split-key cryptographic system and method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,731,755 B1
- Document ID: US6731755B1
- Status: Granted
- Kind: B1
- Application number: 09/446,827
- Filed: 1999-12-29
- Granted: 2004-05-04
- Earliest claimed: 1997-07-28
- Assignees: The Director, Government Communications Headquarters
- Inventors: Clifford C Cocks
- Web page: https://patentgrep.com/patent/US6731755B1

## CPC

- H04L 9/302: {involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A method of operating a split-key cryptographic system having two or more co-operating microprocessors, i, linked via a communications channel, involving the generation of a public modulus, N, being the multiple of two integers, P,Q, where P=p1+p2 . . . pn and Q=q1+q2 . . . pn in such a way that none of the microprocessors; individually has the ability to decrypt encrypted data. Microprocessor i selects a temporary public modulus and the integers pi, qi, a function of which is transmitted to the other microprocessors, j. Every microprocessor j uses the function to generate a set of numbers which are dependent on integers pj, qj, which are secret to each microprocessor j. Each Microprocessor i then uses these numbers to co-operate to generate the public modulus N. N is thus generated without any party having full knowledge of the integers P and Q.

## Claims

### Claim 1

A method of operating a split-key cryptographic system having a plurality of co-operating microprocessors, i, linked via a communications channel, involving the generation of a public modulus, N, being the multiple of two integers, P,Q, where P=(p1+p2 . . . pn) and Q=(q1+q2+ . . . qn) characterized by the following steps:
i) having each microprocessor, i, select integers pi, qi
ii) having each microprocessor, i, determine a public modulus, Mi, public key ei and private key di such that di ei≡1 mod Φ (Mi);
iii) having each microprocessor, i, generate the quantities piei mod Mi and qiei mod Mi and transmitting them to the other microprocessor or microprocessors, j, via the communications channel;
iv) having each microprocessor i generate three numbers, z1,z2,z3, which are respectively (piqj)ej mod Mj, (pjqi)ej mod Mj and ai,jej mod Mj, with ai,j, for i≠j chosen to be random between 0 and the maximum desired public modulus N, subject to the constraint Σjai,j=0, and generate a set of numbers, bl,k for l=1, 2, 3 and k=1, 2, . . . , K with bl,k being chosen to be random modulo Mj, subject to the constraints: Σkb1,k:=Σkb2,k=Σkb3,k=1 Mod Mj, having microprocessor i generate a set of numbers, xl,k=zlbl,ke(M) mod Mj and transmitting this set of numbers to each microprocessors j in a new order determined by microprocessor i;
v) having microprocessor i calculate yjl,k=xl,kdi mod Mi, for each term xl,k received from each other microprocessor j, and the public modulus Ni=Σj,l,kyj,l,k+2piqi+aii;
vi) having each microprocessor i broadcast Ni to each of the other microprocessors, j and having all microprocessors calculate 2N=ΣiNi
vii) testing that N is of a suitable form for use as an RSA modulus and repeating steps i) to vi) with a new set of integer values at step i) if test failed.

### Claim 2 (depends on 1)

A method of operating a split-key cryptographic system as claimed in claim 1, having two co-operating microprocessors, wherein by prior agreement a2,1 is selected to equal p2q2 such that microprocessor 2 does not need to carry out step iii), microprocessor 1 does not need to carry out step iv) and microprocessor 1 can calculate directly the public modulus N=p1q1+Σl,ky2,l,k mod M1.

### Claim 3 (depends on 2)

A method of operating a split-key cryptographic system as claimed in claim 2 characterized in that steps ii)-vi) are repeated substituting microprocessor 2 for microprocessor 1 and vice versa in the steps and using the same values p1,p2, q1, q2 but changing the subscripts according to the substitution and in that microprocessor 1 and microprocessor 2 are further programmed to confirm the generation of identical values of N before N is made available to one or more further microprocessors.

### Claim 4 (depends on 1)

A method of operating a split-key cryptographic system as claimed in claim 1, characterized in that there is provided a further step of having the microprocessors i co-operate to test the likelihood, to a predetermined level, of P and Q being prime and rejecting values of N not being the product of two prime numbers to that level of likelihood.

### Claim 5 (depends on 1)

A method of operating a split-key cryptographic system as claimed in claim 1 to provide a plaintext message, x, from an RSA ciphertext message y, characterized in that there is provided further steps:
viii) ensuring the microprocessors i receive parameters N and a public encryption key, e;
ix) having each microprocessor i generate the value (pi+qi) mod e and transmit it to each microprocessor j,
x) having all microprocessors calculate the values f=P+Q−N−1 (mod e) and k=f−1 mod(e);
xi) having each microprocessor i calculate di = ⌊ ( 1 / n ) + ( k / n ) ⁢ ( N + 1 ) - kp i ⁢ kq i ⌋ e
xii) involving each microprocessor i to produce a partly decrypted a ciphertext message, xi, from a plain text message y enciphered using a formula of the form y=xe mod N according to a formula of the form xi=ydi mod N;
xiii) producing and outputting the plaintext message x=ηiydi mod N·yc mod N, where c lies between 0 and n−1 and is known by all microprocessors.

### Claim 6 (depends on 1)

A split-key encryption system comprising a communications channel accessible by an encryption microprocessor and a plurality of decryption microprocessors operably coupled to exchange data and operably connectable to the communications channel characterized in that the decryption microprocessors are programmed to co-operate in the generation of a public modulus N according to the method claimed in claim 1.

### Claim 7 (depends on 5)

A split-key encryption system as characterized in that the plurality of decryption microprocessors are further programmed to operate according to the method of claim 5.

### Claim 8 (depends on 7)

A split-key encryption system as claimed in claim 7 characterized in that there is additionally provided a third microprocessor operably connectable to the decryption microprocessors and configured to receive and decrypt to plaintext a plurality of partly decrypted ciphertext messages output from the corresponding decryption microprocessors.

### Claim 9 (depends on 6)

A split-key encryption system as claimed in claim 6 characterized in that the microprocessors are incorporated into at least one suitably programmed computer.
