Note: Descriptions are shown in the official language in which they were submitted.
EXPONENTIATION CRYP~OGRAPHIC APPAR~TUS A~ID r~THOD
The invention relates to cryptographic systems.
The Government has rights in this invention pursuant to grant
no. ENG-10173 of the National Science Foundation and IPA No.
0005. ~- -
5 Cryptographic systems are widely used to ensure the privacy - ;
and authenticity of messages communicated over insecure com- -
munication channels. A privacy system prevents unauthorized
parties from extracting information from messages transmitted - --
over an insecure channel, thus assuring the sender of a
10 message that it is being read only by the intended receiver. --
An authentication system prevents the unauthorized injection
of messages into an insecure channel, assuring the receiver -
of the message of the legitimacy of its sender.: - ;
',~ . ' -
One of the principal difficulties with existing cryptographic
~ystems is the difficulty of assessing their security level.Most cryptographic systems utilize many, complex operations so
that a mathematical statement that describes their security -
level is also complex and difficult, if not impossible, to
evaluate.
20 Accordingly, it is an object of the invention to allow auth- --
orized parties to a conversation (conversers~ to establish a -
.
secret cipher key and then converse privately even though an
unauthorized party (eavesdropper~ intercepts their communications. ~ -
:' "' '-'-
,,, ,~ ,
,, . . , ,, , . , .. , _ .. ,, .... , . . , , , ,. , :
~5;~9Z
-2~
Another object of this invention is to allow a converser on
an insecure channel to authenticate another converser's
identitv-
~
Another object of this invention is to provide a cryDtographic
system with a more easily evalu~ted securitv level.
An illustrated embodiment of the present invention describesa method and apparatus for communicating securelv over an
insecure channel with prearrangement of a secret ciDher key.
The secret cipher key is used to encipher and decipher mes-
sages via transformations which are computationally infeasibleto invert without the secret cipher key,~ the enciphered
message is transmitted over an insecure channel with a more
easily evaluated security level. ,~
In the present invention, a secret enciphering key is gen-
erated and is known by a transmitter but not known by an
eavesdropper, A secret deciphering key is generated and is
known hy a receiver but not known by the eavesdropper. The
transmitter generates an enciphered message bv transforming
a message with'the secret enciphering key, which trans-
formation is computationally infeasible to invert without thesecret deciphering key. The enciphered message is transmitted
over the insecure channel to the receiver. The receiver '' '
deciphers the message by inverting said transformation with '
the secret deciphering key, which inversion is computationally
infeasible to perform without the secret ~eciphering key.
Another illustrated embodiment of the present invention ,'
describes a method for allowing a receiver to authenticate
a transmitter as the source of an enciphered message. A secret ''~
enciphering key is generated and is known by a transmitter but
not known by an eavesdropper. A secret deciphering key is
generated and is known by a receiver but not known b,y the
eavesdropper. The receiver receives an enciphered message
and deciphers the message by transforming the enciphered
message with the secret deciphering key, which transformation
3~ is computationally infeasible to invert wi,thout the secret
``` liS;ZS~Z
deciphering key. The receiver authenticates the transmitter as
the source of the enciphered message by the transmitter's ability
to transmit a meaningful enciphered message.
Thus, in accordance with one broad aspect of the
invention, there is provided, in a method of communicating securely
over an insecure communication channel of the type which communi-
cates a message from a transmitter to a receiver by enciphering
the message with a secret enciphering key at the transmitter, :
transmitting the enciphered message from the transmitter to the
receiver, and deciphering the enciphered message with a secret ~ .
deciphering key at the receiver, the improvement characterized by ~.
generating the secret deciphering key as the multiplicative
inverse, in modular arithmetic, of the secret enciphering key;
generating the enciphered message by exponentiating, in modular . .
arithmetic, the message with the secret enciphering key; and
deciphering the enciphered message by exponentiating, in modular : -
arithmetic, the enciphered message with the secret deciphering key.
In accordance with another broad aspect of the invention
there is provided, in an apparatus for communicating securely over
an insecure communication channel, of the type which communicates
a message from a transmitter to a receiver comprising means for
enciphering the message with a secret enciphering key at the :
transmitter, means for transmitting the enciphered message from
the transmitter to the receiver, and means for deciphering the
enciphered message with a secret deciphering key at the receiver,
the improvement characterized by means for generating the secret
deciphering key as the multiplicative inverse, in modular
arithmetic, of the secret enciphering key; means for generating
- 3 -
.; '
:~, ' . . -
, " . .. ,, ., . . , .. - . - ; - .. ., ., l . .. . ~ . . .... . . : -
`` 11525~Z
the enciphered message by exponentiating, in modular arithmetic,
the message with the secret enciphering key, having an input
connected to receive the secret enciphering key, having another
input connected to receive the message, and having an output that
generates the enciphered message; and means for deciphering the
enciphered message by exponentiating, in modular arithmetic, the
enciphered message with the secret deciphering key, having an
input connected to receive the secret deciphering key, having
another input connected to receive the enciphered message, and
having an output that generates the message.
The invention will now be further described in
conjunction with the accompanying drawings, in which:
Figure 1 is a block diagram of a cryptographic system
that transmits a computationally secure cryptogram over an
insecure communication channel.
Figure 2 is a block diagram of a cryptographic apparatus
for raising various numbers to various powers in modulo arithmetic.
Figure 3 is a block diagram of a multiplier for perform-
ing multiplications in the cryptographic apparatus of Figure 2. -
Figure 4 is a detailed schematic diagram of an adder
for performing additions in the multiplier of Figure 3.
Figure 5 is a detailed schematic diagram of a comparator
for performing magnitude comparisons in the multiplier of Figure 3.
Figure 6 is a detailed schematic diagram of a subtractor
for performing subtractions in the multiplier of Figure 3.
Referring to Figure 1, a cryptographic system is shown
in which communications take place over an insecure communication -
channel 19, for example a telephone line. Two-way communication
- 3a -
- .. - .
,. . .. : : . - , ,-, . ::: -: . - . .. -, . ,- .: , .::: . .: : . . :: - - .: -.: : ~ .
llS;~5~2
is exchanged on the insecure channel 19 between converser 11 and
converser 12 using transmitter/receivers 31 and 32, for example
modems such as sell 201 modems. Converser 11 possesses a sequence -
of unenciphered or plaintext messages Pl, P2,... to be communicated
to converser 12. Converser 11 and converser 12 include crypto-
graphic devices 15 and 16 respectively, for enciphering and
deciphering information under the action of a secret enciphering
key K and secret deciphering key D, respectively. The crypto-
graphic device 15 enciphers the ith plaintext message Pi into an ~ :-
enciphered message or ciphertext Ci that is transmitted by
converser 11 through the insecure channel 19; the ciphertext Ci
is received by :
- 3b -
-- 115Z5~2
converser 12 and deciphered by cryptographic device 16 to
obtain the plaintext message Pi. An unauthorized party or
eavesdropper 13 is assumed to have a cryptographic device 17
and to have access to the insecure channel 19, and therefore
to Cl, C2, ..., Ci. ~e is also assumed to have access to some
or all of the past plaintext messages Pl, P2~ ~ ~i 1' as
through the public release of previousl~ enciphered messages
(e.g., timed press releases) represented hy the variable
delay 22. He uses his knowledge of Pl, P2, ..., Pi 1 and
Cl, C2, ..., Ci 1 to attempt to determine Pi from Ci or to
determine how to alter Ci so that when deciphered by the con-
verser 12 it will convey a false meaning of the eavesdropper's
choice.
Converser 11 includes an independent key source 25 which gen-
erates numbers or signals that represent numbers. Eor example,
the key source may be a random number generator that is im-
plemented from a noisy am~lifier (e.g., Fairchild u 709
operational amplifier) with a polarity detector. Key source
25 ge~erates three signals, q, K and ~. Signals q and D are
transmitted secretly via a secure means 26 such as courier
or registered mail to converser 12. q is chosen to be a large
prime number; K is an independent random number chosen
uniformly from the set of integers (1,2, ..., q-2)- and D is
the multiplicative inverse in modular q-l arith~etic of R,
25 chosen so that the product KD is congruent to 1 modulo q-l. -~
That is, if KD is divided by q-l, then the remainder is 1.
-. ~
The calculation of D from K and q is easilv carried out using
Euclid's algorithm (see, for example, Knuth, The Art of
Computer Programming, Vol. 2, Seminumerical Algorithms,
Addison-Wesley, Reading, Mass., 1969, p. 315, exercise 15,
p. 523 solution to exerc~se 15 and p. 302 algorithm X).
Euclid's algorithm can be carried out usin~ hardware of the
type described later in this application.
It is well known that if q is prime then
zq 1 = 1 (mod a), 1~ z< q-l (1)
5~2
-5~-
Conse~uently ari.thmetic in the exponent is done modulo q-l,
not modulo q~ That is :~
zx = Zx~mod q-ll Cmod q2
for all integers x. As an example, 28 = 256 = 4 (mod 7) as
is 2 ~ecause the exponents 8 and 2 are congruent mod q-l = 6.
To construct a cryptosystem, let P, K, C and D denote the
plaintext message, secret enciphering key, ciphertext (or
cryptograml~ and secret deciphering key respectively with the
restri.ction~
1 < P < q-l (3)
1 < C < q-l (4)
1 < K < q-2 (5)
GCD(K, q-12 = 1 (6)
In practice, P probably would be limited to be an Q bit integer .:.
where Q = log2 (q-l). Also, K = 1 probably would be ex-
cluded because then P = C. Equation (6) implies that K is
relatively prime to q-l so that
D -= K tmod q-l) (7)
is well defined with .: :
1 ~ D < q-2; thus,
D, the secret deciphering key, is generated from a multipli-
cative inverse in modular q-l arithmetic of the secret en-
ciphering key, K. Now let .
C = P (mod q) (9) ..
25 be the enciphering operation; and, the enciphered message or -~.
ciphertext C is generated by exponentiating, in modular q .: ::
arithmetic, a plaintext message P with the secret enciphering :. .
key K. Then .
P = C (mod q) (10) .
30 is the deciphering operation; and, the plaintext message P is ::.
deciphered from the ciphertext C by exponentiating, in modular ~ -:
q arithmetic, the enciphered message or ciphertext C with the
secret deciphering key D. Each operation, enciphering and
deciphering, is easily performed with the hardware described
below. Computing D from K need only be done once and requires : :~
only on the order of log q operations using Euclid's algorithm ~ -
(Knuth, ~ Cit, Section 4.5.2). .~
~lS~S~2
-
-6-
Cryptanalysis, on the other hand, is equivalent to computing
a logarithm over GF(q), the finite field with q elements, and
is thus computationally infeasible for a properly chosen value
of q. A task is considered computationally infeasible if its
cost as measured by either the amount of memory used or the
computing time is finite but impossibly large, for example,
on the order of approximately 103 operations with existing
computational methods and equipment. This task is infeasible
because
K = logpc over GF(q) (11)
so that even though the cryptanalyst knows plaintext-ciphertext
pairs, it is as hard to find the key as to find a logarithm
mod q. Such a known plaintext cryptanalytic attack is a
standard test applied to certify a system as secure. It, and
variations, occur in practice as well. The best, known algo-
rithms for computing a logarithm over GF(g) require at least~
operations if q is properly chosen. If q is a 200 digit number
then ~rq is approximately 101 and performing this many oper-
ations is infeasible. On the other hand, enciphering and -
deciphering require only one exponentiation mod q and are
easily implemented.
.
The cryptographic devices 15 and 16, for raising various ~- -
numbers to various powers modulo q, can be implemented in
electronic circuitry as shown in Fig. 2. For ease of illus-
tration, Fig. 2 depicts raising P to the K power modulo q;
raising C to the D power modulo q is obtained by initially
loading C and D instead of P and K, into the P and K registers
43 and 41.
Figure 2 shows the irii~al contents of three registers 41, 42
and 43. The binary representation of K(kQ 1~ kQ 2~ ...,kl,ko)
is loaded into the R register 41; 1 is loaded into the R
register 42; and, the binary representation of P is loaded
into the P register 43, corresponding to i = 0. The number
number of bits Q in each regi~ter is the least integer such
that 2Q > q, If Q = 200~ then all three registers can be
` ~15;~5~?~
-7~
obtained from a single 1024 bit random access memory (RAM) such
as the Intel 2102. The implementation of multiplier 44, for
multiplying two numbers modulo q, will be described in more -
detail later.
Referring to Fig. 2, if the low order bit, containing ko ~
the K register 41 equals 1 then the R register 42 and the P
register 43 contents are multiplied modulo q and their product, -~
also an Q bit quantity, replaces the contents of the R
register 42, If ko = O, the R register 42 contents are let
unchanged. In either case, the P register 43 is then loaded
twice into the multiplier 44 so that the square, modulo q, of
the P register 43 contents is computed. This value,
p(2i+l~ replaces the contents of the P register 43. The K
register 41 contents are shifted one bit to the right and a O
is shifted in at the left so its contents are now
kQ 1'kQ-2'''k2kl
The low order bit, containing kl, of the K register 41 is
exa~ined. If it equals one then, as before, the R register ;
42 and P register 43 contents are multiplied modulo q and
their product replaces the contents of the R register 42.
If ko = a, the R register 42 contents are left unchanged. In
either case, the contents of the P register 43 are replaced
by the square, modulo q, of the previous contents. The K
register 41 contents are shifted one bit to the right and a O ~-
is shifted in at the left so its contents are now
oOkQ l~kQ-2~---k3~k2-
This process continues until the K register 41 contains all
O's, at which point the value of pX modulo q is stored in the
R register 42.
An ex~mple is helpful in following this process. Taking
q = 23, we find Q= 5 from 2 > q. If P = 7 and
K = 18, then pK = 718 = 1628413597910449 = 23(70800591213497)
+ 18 so pK modulo q equals 18. This straightforward but
laborious method of computing pK modulo q is used as a check
to show that the method of Fig. 2~ shown below, yields the
... . . . . ..
:` llS~S5~2
-8-
correct result The R regi.ster 42 and P register 43 contents
are shown in decimal form to faci.litate understanding~
i K Cin binary-~. R P
Q 10010 1 7
1 01001 1 3
-2 00100 3 9
3 ~0010 3 12 .
4 00001 3 6
00000 18 13 ~.
10 The row marked i - 0 coresponds to the initial contents of . --
each register, K = 18~ R = 1 and P = 7. Then, as described ~-
ahove~ because the low order bit of K register 41 is 0, the
R regi.ster 42 contents are left unchanged, the contents of the ..
P register 43 are replaced by the square, modulo 23, of its
15 previous contents C72 = 49 = 2 x 23 + 3 = 3 modulo 23), the
contents of the K register 41 are shifted one bit to the right, .
and the process continues. Only when i = 1 and 4 do the low .~
order bit of the K register 41 contents equal 1, so only going ~ -
from i = 1 to 2 and from 1 = 4 to 5 is the R register 42
20 replaced by RP modulo q. When i = 5, K = 0 so.the process is -
comple*e and the result, 18, is in the R register 42.
Note that the same result, 18, is obtained here as in the -: .
straig~tforward calculation of 718 modulo 23, but that here
large numbers never resulted. ... :.:
Another way to understand the process is to note that the P
register contains p, p2, p4, p8 and pl6 when i = 0,1,2,3, and :
4 respecti.vely, and that pl8 = pl6 p2, so only these two .. ~ ~
values need to be multiplied. :
Fi.gure 3 continues the description of this illustrative ~: .
implementation by depicting an implementation of the modulo q
multiplier 44 in Fig~ 2. The two numbers, y and z, to be
multiplied are loaded into the Y and Z registers 51 and 52 -
respectively, and q is loaded i.n th.e Q register 53. The
product yz modulo q will be produced in the F register 54 which - .
is initially set to 0. If = 20Q, then all four registers
can be obtained from a single 1024 bit RAM such as the Intel
,,,~, ~ ,.
ll5;~S~Z
g
2102. The implementation of Fig. 3 is based on the fact
that yz mod q = yOz mod q + 2ylz mod q + 4Y2Z mod q + ...
+ 2 YQ_lz mod q.
To multiply y times z, if the right-most bit, containing
yO, of the Y register 51 is 1, then the contents of the Z
register 53 are added to the F register 54 by adder 55.
If yO = 0, then the F register 54 is unchanged. Then the ~-
Q and F register contents are compared by comparator 56 to
determine if the contents of the F register 54 are greater
than or equal to q, the contents of the Q register 53. If -
the contents of the F register 54 are greater than or
equal to q then subtractor 57 subtracts q from the contents
of the F register 54 and places the difference in the F
register 54, if less than q the F register 54 is unchanged.
Next, the contents of Y register 51 are shifted one bit to
the right and a 0 is shifted in at the left so its contents
~YQ_l,YQ_2,..~Y2,Yl, so that Yl is ready for com-
puting 2ylz mod q. The quantity 2z mod q is computed for
this purpose by using adder 55 to add z to itself, using
comparator 56 to determine if the result. 2z, is less than
q, and using subtractor 57 for subtracting q from 2z if the
result is not less than q. The result~ 2z mod q is then -
stored in the Z register 52 The right-most bit, containing
Ylr of the Y register 51 is then examined, as before~ and --
the process repeats.
This process is repeated a maximum of Q times or until the
Y register 51 contains all O's, at which point xy modulo
q is stored in the F register 54
As an example of these operations, consider the problem of
computing 7 x 7 modulo 23 needed to produce the second state
of the P register when 718 mod 23 was computed. The follow-
ing steps show the successive contents of the Y, Z and F
registers which result in the answer 7 x 7 = 3 modulo 23.
.. . .. . .
115~5~;~
-10- ',
iy (in binary) Z F
0 00111 7 0
1 00011 14 0 + 7 = 7
2 00001 5 7 + 14 = 21
3 00000 10 21 + 5 = 3 mod 23
Figure 4 depicts an implementation of an adder 55 for ad- -
ding two Q bit numbers p and z. The numbers are presented
one bit at a time to the device, low order bit first~ and
the delay element 66, which stores the binary carry bit,
is initially set to 0. The A~ID gate 61 determines if the
carry bit should be a 1 based on fi and Zi both being 1
and the AND gate 62 determines if the carry should be a
1 based on the previous carry being a 1 and one ' fi or
Zi being 1.
If either of these two conditions is met, the OR gate 63 ~-
has an output of 1 indicating a carry to the next stage.
The two exclusive-or (XOR) gates 64 and 65 determine the
ith bit of the sum, si, as the modulo-2 sum of fi~ Zi and
the carry bit from the previous stage. The delay 66 --
stores the previous carry bit. Typical parts for imple-
menting these gates and the delay are SN7400, SN7404, and
SN7474.
Figure 5 depicts an implementation of a comparator 56 for
comparing two numbers f and q. The two numbers are pre-
sented one bit at a time, high order bit first. If neither -~
the f<q nor the f>q outputs have been triggered after the
last bits f0 and q0 have been presented, then f = q. The
first triggering of either the f<q or the f>q output causes -
the comparison operation to cease. The two AND gates 71
and 72 each have one input inverted (denoted by a circle -
at the input). An SN7400 and SN7404 provide all of the
needed logic circuits.
Figure 6 depicts an implementation of a subtractor 57 for
subtracting two numbers~ Because the numbers subtracted
in Fig. 3 always produce a non-negative difference there
:. -
....... ... . .. .. . .
ll5;;~S~2
is no need to worry about negative differences, The largernumber, the minuend, is labeled f and the smaller number, the
subtrahend, is labeled q. Both f and q are presented ser-
ially to the subtractor 57, low order bit first. AND gates
81 and 83, OR gate 84 and XOR gate 82 determine if borrowing
(negative carrying) is in effect. A borrow occurs if either
fi = and qi = 1, or fi = qi and borrowing occurred in the
previous stage. The delay 85 stores the previous borrow
state. The ith bit of the difference, di, is computed as the
XOR, or modulo-2 difference, of fi, qi and the borrow bit.
The output of XOR gate 82 gives the modulo-2 difference
between fi and qi, and XOR gate 86 takes the modulo-2
difference of this with the previous borrow bit. Typical
parts for implementing these gates and the delay are SN7400,
SN7404 and SN7474.
The eavesdropper 13 is assumed to have a cryptographic device
17 and to have access to all signals Cl,D2,.... ,Ci trans- -
mitted through the insecure channel 19. He also may have past
plaintext messages Pl,P2,...., Pi 1 as represented by the
variable delay 22. The eavesdropper in theory could obtain
K or D from q, Pl and Cl by raising Pl to the first, second,
third, etc., powers until Cl was obtained; the power which
successfully yields Cl may be K. This search is prevented
by choosing q to be a large number; if q is a 200 bit
quantity, the average number of trials before success is on
the order of 2199 = 8 x 1059 and is ~omputationally infeasible.
Improved algorithms for computin~ logarithms over C.F(q)
(if y = aX mod q, X is the logarithm of Y to the base over
GF(q)) are known but, if q = 2r + 1 with q and r being prime,
then the most efficient known algorithm requires approximately
ql/2 operations. Taking q to be a 200 bit number, about
21 = 103 operations are required, still computationally
infeasible. An example of such a pair is r = (2121- 5 7
112 13 17 19 23 29 31 37 41 43 47 53
35 59) + 1 and q = 2r + 1. Other restrictions on q or K or D ~ ~-
may also be imposed.
5~2
There are many methods for implementing this form of
the invention. The signal q could be public knowledge rather than
generated by the key source 25; or the key source 25 could be
located at conversor 12 instead of at conversor 11.
In some applications, it will prove valuable to use the
insecure channel 19, instead of the secure channel 26, to exchange
the keying information. This can be done as described in the
Canadian patent application "Cryptographic Apparatus and Method"
of Hellman, et al, Serial Number 314,862, filed October 30, 1978.
Authentication is obtained because an opponent must
determine the key if he is to inject a message in enciphered form
that will be deciphered into a meaningful message of his choosing.
The difficulty involved in foiling the authentication protection
of the system is therefore equal to the difficulties involved in
foiling its privacy protection.
Variations on the above described embodiment are possible.
For example, in the above method based on logarithms over GF(q),
m-dimensional vectors, each of whose components are between 0 and
q-l also could be used. Then all operations are performed in the
finite field with qm elements, GF(qm), which operations are well
described in the literature. Or, q need not be prime, in which
case D must equal the multiplicative inverse of K modulo ~ (q).
The function ~ (q) is known as Euler's totient function and equals
the number of-positive integers less than q and relatively prime
to q. When q is prime ~ (q) = q-l so equation (7) is a special -~
case of this more general rule. As a small example, consider q = -
15 so ~ (q) = 8 (1,2,4,7,8,11,13 and 14 are relatively prime to 15). -~
Taking K=3 then D=K 1 mod ~ (q) = 3 (in general K and D will be
-12-
~,'J. ; : ~
~1525~2
different~. If P=2 then C=PKmod q = 8 and P can be recovered by
the receiver 12 as CD mod q = 83 mod 15 = 2, which is correct. If
the factorization of q contains a repeated factor, then a problem
arises in that C=pK mod q and p=CD mod q are not always inverse
transformations, even if D = K l mod ~ (q). This problem can be
overcome by
-12a- -~
. ' :
~,, ':
-` 115~5~2
-13~
avoiding certain values of P. For example, if q=44=2 11,
then any value of P which is divisible by 2, but not by 4,
will not be obtained by enciphering and then deciphering.
As an example, when K=3, D=7 and ~ (q) = 20, if P=2 then
c=pK mod q=9 but CP mod q = 87 mod 44 = 24~P.
Thus, although the best mode contemplated or carrying out
the present invention has been herein shown and described,
it will be apparent that modification and variation may be
made without departing from what is regarded to be the subject
matter of this invention.
~ ~ ... .. . ~ . . . .
