1 October 2005
Source:
http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=HITOFF&d=PALL&p=1&u=/netahtml/srchnum.htm&r=1&f=G&l=50&s1=6,731,755.WKU.&OS=PN/6,731,755&RS=PN/6,731,755
Wikipedia on Clifford Cocks, chief mathematician at GCHQ:
http://en.wikipedia.org/wiki/Clifford_Cocks
More on the British invention of public key cryptography (first called "non-secret encryption"):
The Possibility of Non-Secret Encryption by J H Ellis (1970)http://www.cesg.gov.uk/site/publications/media/possnse.pdfA Note on Non-Secret Encryption by C Cocks (1973)
http://www.cesg.gov.uk/site/publications/media/notense.pdfNon-Secret Encryption Using a Finite Field by M Williamson (1974)
http://www.cesg.gov.uk/site/publications/media/secenc.pdfThoughts On Cheaper Non-Secret Encryption by M Williamson (1976)
http://www.cesg.gov.uk/site/publications/media/cheapnse.pdfThe Story of Non-Secret Encryption by J H Ellis (1987)
http://www.cesg.gov.uk/site/publications/media/ellis.pdfThe Code Book, by Simon Singh
http://cryptome.org/ukpk-alt.htm[Excerpt]
For the next three years, GCHQ's brightest minds struggled to find a one-way function that satisfied Ellis's requirements, but nothing emerged. Then, in September 1973, a new mathematician joined the team. Clifford Cocks had recently graduated from Cambridge University, where he had specialised in number theory, one of the purest forms of mathematics. When he joined GCHQ he knew very little about encryption and the shadowy world of military and diplomatic communication, so he was assigned a mentor, Nick Patterson, who guided him through his first few weeks at GCHQ.
After about six weeks, Patterson told Cocks about 'a really whacky idea'. He outlined Ellis's theory for public-key cryptography, and explained that nobody had yet been able to find a mathematical function that fitted the bill. Patterson was telling Cocks because this was the most titillating cryptographic idea around, not because he expected him to try to solve it. However, as Cocks explains, later that day he set to work: 'There was nothing particular happening, and so I thought I would think about the idea. Because I had been working in number theory, it was natural to think about one-way functions, something you could do but not undo. Prime numbers and factoring was a natural candidate, and that became my starting point.' Cocks was beginning to formulate what would be known as the RSA asymmetric cipher. Rivest, Shamir and Adleman discovered their formula for public-key cryptography in 1977, but four years earlier the young Cambridge graduate was going through exactly the same thought processes. Cocks recalls: 'From start to finish, it took me no more than half an hour. I was quite pleased with myself. I thought, "Ooh, that's nice. I've been given a problem, and I've solved it." '
Cocks did not fully appreciate the significance of his discovery. He was unaware of the fact that GCHQ's brightest minds had been struggling with the problem for three years, and had no idea that he had made one of the most important cryptographic breakthroughs of the century. Cocks's naivety may have been part of the reason for his success, allowing him to attack the problem with confidence, rather than timidly prodding at it. Cocks told his mentor about his discovery, and it was Patterson who then reported it to the management. Cocks was quite diffident and very much still a rookie, whereas Patterson fully appreciated the context of the problem and was more capable of addressing the technical questions that would inevitably arise. Soon complete strangers started approaching Cocks the wonderkid, and began to congratulate him. One of the strangers was James Ellis, keen to meet the man who had turned his dream into a reality. Because Cocks still did not understand the enormity of his achievement the details of this meeting did not make a great impact on him, and so now, over two decades later, he has no memory of Ellis's reaction.
Note below under "foreign application priority data" that Cocks filed his Great Britain patent application for this invention in July 1997 at about the time the story of non-secret encryption was first becoming public. That approval of this US patent took four and a half years for approval is noteworthy. Whether the delay was for technical or national security reasons, or both, is not clear.
No other patents for GCHQ or Clifford Cocks are listed at the US Patent Office. This does not mean there may not be patents not yet made public -- it is fairly common for new cryptographic inventions to be withheld by government order.
Cryptome filed a freedom of information request with the National Security Agency for information on non-secret encryption in 1999. After NSA asked Cryptome to refine the topic that was done, and search fees were paid. Later, NSA said it has files on the subject, that the request is in the queue for answering, and a case officer has been assigned to answer. Nothing yet.
http://cryptome.org/ukpk-diffie.htm
Cryptome would appreciate pointers to articles or reports on this invention
and its patent; a single citation of the patent appears on Google under a
patent listing service. Send to jya[at]pipeline.com.
United States Patent | 6,731,755 |
Cocks | May 4, 2004 |
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=p.sub.1 +p.sub.2 . . . p.sub.n and Q=q.sub.1 +q.sub.2 . . . p.sub.n 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 p.sub.i, q.sub.i, 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 p.sub.j, q.sub.j, 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.
Inventors: | Cocks; Clifford C (Cheltenham, GB) |
Assignee: | The Director, Government Communications Headquarters (Cheltenham, GB) |
Appl. No.: | 446827 |
Filed: | December 29, 1999 |
PCT Filed: | July 13, 1998 |
PCT NO: | PCT/GB98/02055 |
PCT PUB.NO.: | WO99/05818 |
PCT PUB. Date: | February 4, 1999 |
Jul 28, 1997[GB] | 9715761 | |
Nov 28, 1997[GB] | 9725190 |
Current U.S. Class: | 380/30; 380/277; 380/278; 380/282; 380/283 |
Intern'l Class: | H04K 001/00; H04L 009/00 |
Field of Search: | 380/277,278,30 |
5588061 | Dec., 1996 | Ganesan et al. | 380/30. |
Cocks, "Split knowledge generation of RSA parameters", Cryptography and Coding. 6.sup.th IMA International Conference. Proceedings, Proceedings of Cryptography, Cirencester, UK, Dec. 17-19, 1997, pp. 89-95. |
Primary Examiner: Sheikh; Ayaz
Assistant Examiner: Vaughan; Michael
Attorney, Agent or Firm: Nixon & Vanderhye P.C.
FIG. 2 shows the sequence, in principle, of operating a cryptographic system
according to the present invention to generate the RSA secret parameters.
FIG. 3 shows the sequence, in principle, of operating an RSA cryptographic
system according to the present invention to decrypt an RSA cyphertext message.
FIG. 4 shows a schematic representation of a split-key cryptographic system
according to the present invention, operable in accordance with the sequences
of FIG. 1.
EXAMPLE 1
An example is described below with reference to FIGS. 1 to 3 in which the
method according to the present invention is used in a cryptographic system
in which aplaintext message is converted to a cyphertext message which is
then transmitted to co-operative computers which must act in concert to reproduce
the plaintext message. This consists in essence of three parts as presented
in FIGS. 1, 2 and 3. These parts comprise:
a. A procedure to enable two entities, which may be for example suitably
programmed computers or dedicated-microprocessors linked via a communications
channel, to generate a public RSA modulus, N, that is (to a high probability)
the product of two primes P and Q, such that neither entity can recover P
or Q with a feasible amount of work; (FIG. 1)
b. A procedure for the two entities to generate their shares d.sub.1 and
d.sub.2 of the secret RSA key d, given a public encryption key e; (FIG. 2)
and
c. A procedure to allow co-operative recovery of a ciphertext message, encrypted
from a plaintext message using the RSA algorithm with the public parameters
N and e. (FIG. 3)
a. To begin with A selects its own RSA modulus M and public key e(M), either
by user input or by a suitably coded algorithm. These two numbers are transmitted
to B. A's secret decryption key will be d(M). The value of M must be at least
as big as that of the largest size of the public modulus N which they will
generate. Then A transmits to B the quantities p.sub.1.sup.e(M) mod M and
q.sub.1.sup.e(M) mod M.
B now calculates the three numbers (p.sub.1 q.sub.2).sup.e(M) mod M, (p.sub.2
q.sub.1).sup.e(M) mod M and (p.sub.2 q.sub.2).sup.e(M) mod M. These three
quantities will be referred to as z.sub.1, z.sub.2 and z.sub.3 respectively.
B also generates a set of numbers b.sub.i,j for i=1, 2, 3 and j=1, 2, . .
. , K. The preferred value of K will be discussed later. The b.sub.i,j are
selected to be random modulo M, subject to the constraints: .SIGMA..sub.j
b.sub.1,j =.SIGMA..sub.j b.sub.2,j =.SIGMA..sub.j b.sub.3,j =1.
B then generates the set of numbers x.sub.i,j =z.sub.i b.sub.i,j.sup.e(M)
mod M and transmits these to A but in a new order. The ordering must be such
that it is computationally unfeasible to recover the values of i and j from
the set x.sub.i,j as sent. Thus a random order, or a sorted order are both
acceptable.
A now calculates y.sub.i,j =x.sub.i,j.sup.d(M) mod M. Thus y.sub.i,j =b.sub.i,j
z.sub.i.sup.d(M) mod M, and hence A can determine N=(p.sub.1 +p.sub.2)(q.sub.1
+q.sub.2)=p.sub.1 q.sub.1 +.SIGMA..sub.i,j y.sub.i,j mod M, which is transmitted
to B.
As it stands A could substitute any N of its choice at this point (although
if done, it is not clear that A will be able to complete the later steps
of the method in a satisfactory fashion). Nevertheless, this can be prevented
by making the above procedure symmetrical. To do this B produces its own
modulus and executes the above exchange using the same values of p.sub.1,
p.sub.2, q.sub.1 and q.sub.2, and for this exchange it will be A which is
programmed to produce the set of random values. Then A and B will both know
N. A so called "hash" of N may then be exchanged between A and B in order
to confirm that they have recovered the same value.
There is no guarantee that the public modulus, N, generated in this way is
of a form suitable for use as an RSA modulus. Therefore N must be tested
and the above procedure repeated until an N suitable for use as an RSA modulus.
A suitable algorithm to test for N being of the right form is therefore needed.
One such algorithm is to test for the condition that x.sup.N+1 =x.sup.P+Q
mod N for many x. (In practice almost all N not of the correct form will
fail on the first x tested.) This condition does not guarantee that P and
Q are prime, for example either of them could be Carmichael numbers. However,
even if they are not prime we can use the N as an RSA modulus, but being
a product of more than two primes may make such N easier to factorise and
hence make the system less secure.
Now, to test whether N is of the right form using the above algorithm, A
and B will be programmed to employ an identical set of x. A is programmed
to calculate x.sup.N+1-p1-q1 mod N and B to calculate x.sup.p2+q2 mod N.
A hash (using a secure hash function) of these values is then exchanged between
the computers A and B which will be sufficient to tell if they are equal.
Once an N has been found that passes the above test it is possible to use
the test of Boneh and Franklin to increase confidence in the fact that P
and Q are both prime, so that N can be used as a "high security" RSA modulus
with greater confidence. To make use of this Boneh and Franklin test it is
necessary that P.ident.3 (mod 4) and Q.ident.3 (mod 4). This can be achieved
by having A and B control the values of p.sub.1, p.sub.2, q.sub.1 and q.sub.2
modulo 4. The test, described below, is executed k times, where k is set
according to the level of confidence required. A number N of the correct
form will always pass the test, whilst if either P or Q is composite the
test will fail with a probability of at least 1/2 at each of the k iterations.
Each iteration comprises two parts. In the first part A and B use a common
random integer x in the range 1 to N-1 such that the Jacobi symbol (x/N)
equals +1. A is programmed to calculate a hash of each of the two values
.+-.x.sup.(N+1+1-p1-q1)/ 4 mod(N). The other entity, B is programmed to calculate
a hash of x.sup.(1+p2+q2)/4 mod(N), where 1=0, 1, 2 or 3 according to the
values of p.sub.1, p.sub.2, q.sub.1 and q.sub.2 modulo 4. The hashed values
are compared and the test is failed if they do not match and the second part
need not be undertaken.
In the second part A and B use the same two randomly chosen co-prime integers
in the range 1 to N-1, u and v say. Working in a ring of polynomials Z.sub.N
[X] A computes the remainder when (uX+v).sup.N+1+p1+q1 is divided by X.sup.2
+1 and B computes the remainder when (uX+v) is divided by X.sup.2 +1. Writing
these polynomials as u.sub.1 X+v.sub.1 and u.sub.2 X+v.sub.2 respectively,
A calculates a hash of v.sub.1 /u.sub.1 mod(N) and B calculates a hash of
-v.sub.2 /u.sub.2 mod(N). The hashed values are compared and the test fails
if the two values differ.
b. Once an acceptable modulus has been found, the next step is to generate
the public encryption key, e and the secret decryption key d. This is done
in such a way that d is held by the co-operating computers A and B in two
parts d.sub.1 and d.sub.2, where d=d.sub.1 +d.sub.2. The algorithm employed
to generate these parameters is as follows:
Firstly, the public key e is determined and shared between A and B. Preferably,
this should be chosen so that P-1 and Q-1 are likely to be co-prime to e,
but at the same time e should not be too large as A and B will have to share
(p.sub.1 +q.sub.1) mod e and (p.sub.2 +q.sub.2) mod e with each other. A
value such as e=2.sup.16 +1 should be satisfactory.
Now A transmits (p.sub.1 +q.sub.1) mod e to B and B transmits (p.sub.2 +q.sub.2)
mod e to A, so they can both calculate f=P+Q-N-1 (mod e). If f is non zero
and co-prime to e then they can both calculate g=f.sup.-1 (mod e). The secret
decryption key will be:
d=(1+(N+1-P-Q)g)/e; but A will calculate:
##EQU1##
and
B will calculate: ##EQU2##
A person skilled in the art can easily verify that d=d.sub.1 +d.sub.2. Such
a skilled person would also appreciate that in the alternative d.sub.1 may
be rounded up and d.sub.2 rounded down.
c. In order to decrypt an RSA encrypted plain text message, x, the cyphertext
message y=x.sup.e mod N, A and B must be programmed to act in co-operation.
One way this may be achieved is to have A receive the cypher text message
and decrypt it partly using the RSA algorithm to produce a "part" plaintext
message x.sub.1 =y.sup.d1 mod N which is transmitted to B which stores it
in a computer memory location. B is programmed to receive the original cyphertext
message also and to calculate its own "part" plaintext message x.sub.2 =y.sup.d2
mod N. B may then be programmed to reproduce the original plaintext message
x=x.sub.1 x.sub.2 mod N which may be output to a display device or to a storage
device for later viewing.
Referring now to FIG. 4, two co-operating entities, shown as computers A
and B, are linked via a conventional unsecured communications channel C,
for example an internet connection, which they are programmed to use in order
to transmit data between themselves. In this example this communications
channel C is also accessible to one or more encryption computers (not shown)
which can access the public RSA parameters and supply a suitably encrypted
cyphertext message to either or both computers A and B.
In operation computer A is programmed to generate two numbers p.sub.1 and
q.sub.1 (not necessarily prime) and computer B is programmed to generate
two numbers p.sub.2 and q.sub.2. Co-operative exchange of data between A
and B allows the generation of the public modulus N=PQ, where P=p.sub.1 +p.sub.2
and Q=q.sub.1 +q.sub.2 and x.sup.(N+1).ident.x.sup.P+Q mod (N) in such a
way that neither A nor B alone has access to both P and Q. In this example
the public encryption key, e, is generated by A but a person skilled in the
art would appreciate that as knowledge of this key would not in itself compromise
security the only requirement is that this key is made known to computers
A and B. The numbers N and e can then be made publicly available for encrypting
a plaintext message using the RSA algorithim using the communication channel
C. The cyphertext message is then passed to A and B for co-operative decryption.
Employing the method outlined-above with, reference to FIG. 3, computer A
is programmed to provide a partly decrypted message to computer B which is
itself programmed to generate its own partly decrypted message. Computer
B is also programmed to combine the two partly decrypted messages to provide
a plaintext output, for example on a computer screen or on a computer data
storage device.
Alternatively, it may be desirable that neither computer A nor computer B
can reproduce the original plaintext message. In this circumstance the
cryptographic system may additionally comprise a third, decryption computer,
D (shown as a broken box in FIG. 4). The cyphertext message y is received
from the communication channel C by A and B. These two computers are programmed
to calculate their respective "part" plaintext messages x.sub.1 mod N and
x.sub.2 mod N respectively which are transmitted to D, preferably using a
secure communications channel. Thus D can be programmed to determine x=x.sub.1
x.sub.2 mod N.
EXAMPLE 2
This example describes the use of the system shown in FIG. 4 and the method
described in conjunction with FIG. 1 to implement the well known Fiat Shamir
scheme ["How to Prove Yourself: Practical solutions to Identification and
Signature Problems", Advances in Cryptology-Crypto '86 Lecture Notes in Computer
Science Vol 263, pp186-194]. In this case, where A and B will essentially
substitute for "the single trusted centre", a third computer D will need
to present values v.sub.j derived via its personal identity and a universal
hash function, and obtain data that will allow D's calculations of s.sub.j
where s.sub.j.sup.2 =v.sub.j mod N whenever v.sub.j has a square root. The
public modulus N may be determined by A and B according to the method provided
at step a. of Example 1.
To implement the scheme by utilising the method and system according to the
present invention, suitable programming must be made to ensure that P.ident.3
(mod 4) and Q.ident.3 (mod 4), and note that if d=((P-1)(Q-1)+4)/8, then
whenever v.sub.j is a square modulo N d then s.sub.j =v.sub.j.sup.d mod N
is a square root of v.sub.j. The secret decryption key, being the exponent,
d will be held in two parts d.sub.1 and d.sub.2 by A and B respectively.
In this case.
for A:
d.sub.1 =((N+5)/2-p.sub.1 -q.sub.1)/8
for B:
d.sub.2 =((N+5)/2-p.sub.2 -q.sub.2))/8
(As in Example 1 the rounding of the two parts of the decryption key may
be reversed)
Then if presented with a value of v.sub.j, A and B must check that the Jacobi
symbol (v.sub.j /N) equals 1. If so A will calculate w.sub.j,1 =v.sub.j.sup.d1
mod N and B will calculate w.sub.j,2 =v.sub.j.sup.d2 mod N. D will calculate
w.sub.j =w.sub.j,1 w.sub.j,2 mod N, which will either be the square root
of v.sub.j mod N, or will be the square root of N-v.sub.j mod N. In the latter
case D will reject this particular v.sub.j.
EXAMPLE 3
This example describes the extension of the method described in example 1
to allow an arbitary number of parties to co-operate in generating the parameters
for an RSA encryption system to allow the parties to decode a cyphertext
message to reproduce the plaintext message. The method consists in essence
of the three parts a, b and c described in the previous example, generalised
for an arbitary number of parties.
a. Initially each party or entity i produces their own RSA modulus M.sub.i
and public key e.sub.i. These two numbers are broadcast to the other parties.
The modulus M.sub.i should be at least as big as n times N.sub.L, the largest
possible value of the public modulus N that may be produced, where N=(p.sub.1
+p.sub.2 + . . . +p.sub.n) (q.sub.1 +q.sub.2 + . . . +q.sub.n). Then each
party i broadcasts to the other parties the quantities p.sub.i.sup.ei mod
M.sub.i and q.sub.i.sup.ei mod M.sub.i.
Each party i also produces a set of additives a.sub.ij, for j=1,2, . . .
,n, where the a.sub.ij are randomly chosen in the range 0<a.sub.ij
<N.sub.L, unless i=j. These numbers must satisfy the equation .SIGMA..sub.j
a.sub.ij =0. Thus a.sub.ii will be negative.
Each party i now calculates, for sending to the other parties j, the three
numbers (p.sub.i q.sub.j).sup.ej mod M.sub.j, (p.sub.j q.sub.i).sup.ej mod
M.sub.j and a.sub.ij.sup.ej mod M.sub.j. As in example 1, these three quantities
will be referred to as z.sub.1, z.sub.2 and z.sub.3 respectively. However,
before sending these numbers to j, each is split into K parts using the same
technique as described in example 1. In detail, suppose that X is one of
the numbers to be sent. Then party i generates K numbers x.sub.k, randomly
chosen modulo M.sub.j such that .SIGMA..sub.k x.sub.k =1 mod M.sub.j. Then
the K parts that i sends to j are X x.sub.k.sup.ej mod M.sub.j. The 3K values
are sent in a new order such that j does not know which parts corresponds
to each of the three numbers that i is sending. The security of the scheme
depends on making K large enough and the same considerations apply as in
example 1.
By decrypting and summing the RSA encrypted data sent to him, each party
i will have received enough information to enable him to calculate:
.SIGMA..sub.i.noteq.j p.sub.i q.sub.j +.SIGMA..sub.i.noteq.j p.sub.j q.sub.i
+.SIGMA..sub.i.noteq.j a.sub.ji mod M.sub.i. But because M.sub.i was chosen
to be sufficiently large, this must equal: .SIGMA..sub.i.noteq.j p.sub.i
q.sub.j +.SIGMA..sub.i.noteq.j p.sub.j q.sub.i +.SIGMA..sub.i.noteq.j a.sub.ji.
Hence by adding in terms that he knows himself, party i can calculate: N.sub.i
=.SIGMA..sub.j p.sub.i q.sub.j +.SIGMA..sub.j p.sub.j q.sub.i +.SIGMA..sub.j
a.sub.ji.
Note, that this sum includes all the diagonal terms p.sub.i q.sub.i and a.sub.ii.
By sharing N.sub.i, all parties will be able to determine the sum of these
quantities: .SIGMA..sub.i N.sub.i =2(p.sub.1 +p.sub.2 + . . . +p.sub.n)(q.sub.1
+q.sub.2 + . . . +q.sub.n). Alternatively, by sharing only N.sub.i mod M,
for some commonly agreed odd modulus M, the participants will be able to
determine N mod M.
As in example 1, there is no particular reason to expect that P=(p.sub.1
+p.sub.2 + . . . +p.sub.n) and Q=(q.sub.1 +q.sub.2 + . . . +q.sub.n) are
both prime, and so many candidate N will need to be tested until one is found
that is satisfactory. Initial testing is done by selecting random values
x, and having each party calculate x.sup.pi+qi mod N. Then, if N is the product
of two primes, the product of all these numbers will equal x.sup.N+1- mod
N.
There is still the requirement to eliminate Carmichael numbers which the
above test will pass. The Boneh and Franklin test, described in example 1,
can be readily extended to the multiple party situation of the present example.
To use this test it is necessary that P and Q are congruent to 3 modulo 4,
and thus the participants will have to decide in advance on the values of
p.sub.i and q.sub.i modulo 4, for every i.
The process of generating a suitable N is made more efficient if the numbers
p.sub.i and q.sub.i are controlled to ensure that neither P nor Q is a multiple
of the first few primes. This can be done in much the same way as proposed
in example 1, either by agreeing on the value of p.sub.i and q.sub.i modulo
p for primes p<n, or by making p.sub.i and q.sub.i less than [n/p] for
small primes p larger than n.
b. Once an acceptable modulus has been found, the next step is to generate
the public encryption key, e and the secret decryption key d. This is done
in such a way that d is held by the co-operating parties i in n parts, where
d=(d.sub.1 +d.sub.2 + . . . d.sub.n)+c. The algorithm employed to generate
these parameters is as follows:
Firstly, the public key e is agreed. All parties will need to share p.sub.i
+q.sub.i mod e, so e should not be too large. Also, P-1 and Q-1 have to be
coprime to e and if they are not then N has to be rejected or a different
value of e must be selected. The decryption key will satisfy:
ed=1 mod(N+1-P-Q)
Thus, ed.ident.1+k(N+1-(p.sub.1 +p.sub.2 + . . . +p.sub.n)-(q.sub.1 +q.sub.2
+ . . . +q.sub.n)), where k is chosen to make the right hand side a multiple
of e, allowing k to be determined by all parties from the shared values of
p.sub.i and q.sub.i modulo e.
The individual decryption key, known only by participant i, d.sub.i say,
is then determined by: ##EQU3##
Hence the decryption key d will satisfy d=(d.sub.1 +d.sub.2 + . . . +d.sub.n)+c,
where c will lie between 0 and n-1. One trial decryption will be sufficient
to identify c, and all parties may know c.
c. In order to decrypt an RSA encrypted, cyphertext message y, participant
i will calculate y.sup.di mod N, and the decrypted, plaintext message will
be the product of these n terms together with y.sup.c mod N.
A person skilled in the art will easily be able to adapt the system configuration
shown in FIG. 4 and the associated description provided in example 1, to
provide a system in which a plurality of co-operating entities, for example
computers, linked via an unsecured communications channel, can exchange encrypted
data using the method outlined in this example.
EXAMPLE 4
The multi party method described in example 3 can also be used to enable
arbitary encryption keys to be used. The inventor achieves this by following
the method of Boneh and Franklin, substituting the principles described in
example 3 for their BGW protocol. The method is described below, where e
is the encryption key. In the following, assume that e is large (of the same
order as the modulus N) and in this case the moduli M.sub.i used in the method
according to the invention will need to be at least nN.sup.2 in size.
Define .phi..sub.1 =(N+1)-p.sub.1 -q.sub.1 mod e and .phi..sub.i =-p.sub.i
-q.sub.i mod e, for i>1, which is computable by party i.
Each participant i generates an arbitrary value mod e, r.sub.i say. Then
they execute the method described in example 3, with party i using r.sub.i
and .phi..sub.i as input values, p.sub.i and q.sub.i. They share their recoveries
modulo e, so that they can all determine:
.PSI.=(.SIGMA..sub.i r.sub.i)(.SIGMA..sub.i.phi..sub.i)mod e
If .PSI.=0, they restart with new values of r.sub.i. If this fails repeatedly
then they will need to either choose a different modulus N or a different
exponent e.
Each party i now calculates .zeta..sub.i =-r.sub.i /.PSI. mod e. Thus:
.SIGMA..sub.i.zeta..sub.i =-(.SIGMA..sub.i r.sub.i).PSI..sup.-1
=-(.SIGMA..sub.i.phi..sub.i).sup.-1 mod e
Finally the parties use the method described in example 3, with inputs
.zeta..sub.i, .phi..sub.i as p.sub.i and q.sub.i respectively. If the output
recovered by party i is .eta..sub.i, then:
.SIGMA..sub.i.eta..sub.i =(.SIGMA..sub.i.zeta..sub.i
(.SIGMA..sub.i.phi..sub.i).ident.-1 mod e
Thus the decription key, ##EQU4##
The individual decryption key, d.sub.i, known only by participant i, is given
by: ##EQU5##
Hence the decryption key d will satisfy d=(d.sub.1 +d.sub.2 + . . . d.sub.n)+c,
where c lies between 0 and n-1. One trial decryption will be sufficient to
identify c. Thus as in the small exponent case, in order to decrypt an RSA
encrypted, cyphertext message y, participant i will calculate y.sup.di mod
N, and the decrypted, plaintext message will be the product of these n terms
together with y.sup.c mod N.
It is possible to use the approach outlined above, even if the encryption
key, e, is much smaller than the generated modulus N. However, a change to
the method is required in order to retain security. Before using r.sub.i,
.phi..sub.i and .zeta..sub.I in the method described in example 3, the parties
should add to them random multiples of e to bring the sum up to a limit L.
The moduli M.sub.i must be at least nL.sup.2 in size. A value of L=N is
recommended.
In any use of the method and system according to the present invention a
critical security question is the size of K, the number of fragments into
which a party splits each of the three quantities z.sub.1, z.sub.2 and z.sub.3
and although in theory K may be different for each of these three quantities
the overall security of the system will be dependent on the smallest value
of K used. Thus practically it reduces computational expenditure to choose
the same K values for each of the three quantities.
Considering the case where two entities A and B are co-operating, by way
of example, A receives (encrypted under its modulus) p.sub.1 q.sub.2 b.sub.1,j,
p.sub.2 q.sub.1 b.sub.2,j and p.sub.2 q.sub.2 b.sub.3,j. A can then be programmed
to recover the factorisation of N if it can identify which fragment is associated
with each of the three quantities p.sub.1 q.sub.2, p.sub.2 q.sub.1 and p.sub.2
q.sub.2.
However, by selecting a value of K so that the total number of possible
arrangements (3K)!/(K!).sup.3 exceeds M.sup.2 then for most guesses by A
as to the value of p.sub.1 q.sub.2, p.sub.2 q.sub.1 and p.sub.2 q.sub.2 (subject
to their sum being the value recovered) it will be ensured that there will
be a partition of the 3K fragments into 3 sets which produce these three
values. In other words, A gains negligible additional information about the
values of p.sub.1 q.sub.2, p.sub.2 q.sub.1 and p.sub.2 q.sub.2 from the fact
that they can be obtained from a partition of the 3K pieces. If M is 512
bits in size then K will need to be at least 218 to achieve this bound. In
practice it is likely that a smaller value of K will provided adequate security.
Finally, assuming that A's public encryption exponent e(M) is small, the
principal amount of work is performed by A, which calculates 3K decryptions
for each trial N. As the probability that N is a product of two primes is
about the total amount of work A will expect to have to do amounts to 0.75K(log
N).sup.2 decryptions. Assuming that P and Q are of similar size. For numbers
of size 512 bits, with K equal to 218, this is about 20.6 million decryptions.
Clearly it is desirable to cut this down if at all possible. One way to do
this is to increase the probability that P and Q will be prime. This can
be achieved by taking a set of small primes: 3,5,7, . . . ,R say and agreeing
that both A and B will choose p.sub.i mod S and q.sub.i mod S to be less
than (S/2) for each prime S in this range, and also agree that only one of
them can choose numbers that are a multiple of S. For the prime 2, they must
be programmed such that it is known which will select a multiple of 2 and
which will choose an odd number. (If they are going to use the Boneh and
Franklin test then they will control the values of p.sub.i and q.sub.i modulo
4 as well).
Each small prime places 1 bit of constraint for A and B on the choice of
p.sub.i and q.sub.i, but significantly reduces the number of candidate moduli
N that need to be tested. An alternative would be to use zero knowledge methods
to ensure that p.sub.1 mod S.noteq.-p.sub.2 mod S and that q.sub.1 mod
S.noteq.q.sub.2 mod S, but this will not be necessary if the number of primes
to be controlled is small. For example, if the first 10 primes are controlled
so that R=29, the number of decryptions A makes drops by a factor of 40 to
around 514000. Using the first 20 primes drops the expected number to around
336000. Although large, this is quite practical for generating long term
system wide RSA parameters. For example, for a 512 bit modulus the calculations
would take a little over one day to complete using MATHEMATICA.TM. on a
SPARC10.TM. workstation.
It will be obvious to those skilled in the art that the transfer of information
between the microprocessors A and B, or between the multiple parties i, may
be done using the publicly accessible communication channel C or may be made
via separate dedicated communications channels.